From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 0341ABC69 for ; Fri, 20 Oct 2006 05:31:02 +0200 (CEST) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9K3Uxoc003750 for ; Fri, 20 Oct 2006 05:31:00 +0200 Received: from localhost (orion [130.54.16.5]) by kurims.kurims.kyoto-u.ac.jp (8.13.7/8.13.7) with ESMTP id k9K2hf1l013906; Fri, 20 Oct 2006 11:43:42 +0900 (JST) Date: Fri, 20 Oct 2006 11:43:38 +0900 (JST) Message-Id: <20061020.114338.132764090.garrigue@math.nagoya-u.ac.jp> To: jhf@hex.no Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Haskell parser combinators in OCaml? From: Jacques Garrigue In-Reply-To: <20061019220131.GA18656@hex.no> References: <20061019220131.GA18656@hex.no> X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 453842F3.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; haskell:01 parser:01 combinators:01 ocaml:01 haskell:01 combinator:01 parsers:01 citeseer:01 combinator:01 parsers:01 lalr:01 grammars:01 ocaml:01 parser:01 forall:01 From: Jorgen Hermanrud Fjeld > From the world of Haskell, the work of S. Doaitse Swierstra in the paper > "Combinator Parsers: From Toys to Tools" > "http://citeseer.ist.psu.edu/363886.html", introduces some very nice > combinator parsers that parse LALR(k) grammars, and give good error > messages. > > I would love too express something equivalent in OCaml, but I'm not sure > how to translate the concepts used into concepts in OCaml. > > I am hoping some of the type theorists out there would glance at the > paper, and bestow some reflection, advice or warning upon me. > > There are several issues: > 1) How to express the lazy lookahead data structure? > 3) How to express the type of the parser in OCaml? > > Some details: > 1) The lazy data structure in 4.1 can not be expressed directly, > and I believe some kind of explicit fixed point is needed. > Would one need fixed points with deBruijn indexes? > Do you know of any similar examples that I may look at for > inspiration? I don't see why you can't. OCaml has a lazy type, so you can define all the lazy data structures you want easily. Of course you have to define your own type of lazy lists, and insert lots of lazy's all over the place, but there is no real difficulty. > 2) The parser has the haskell type > type Parser a = > forall b result . > Future b result > -> Stack a b > -> Errs > -> Input > -> Steps result > which I can not express in OCaml. My attempts at encoding this > using an encoding that express existential types, have so far not > worked out. I always end up with a type error, and do not see how > to better design it. > ######## The type error > File "parser.ml", line 154, characters 21-26: > This field value has type > ('a, 'a) future -> > (symbol, 'a) stack -> (errors -> errors) -> input -> ('a * errors) steps > which is less general than > 'b 'c. > ('b, 'c) future -> > ('d, 'b) stack -> (errors -> errors) -> input -> ('c * errors) steps Your encoding uses universal types, not existential. But this seems the correct thing to do, as far as I can understand the code. The reasons for the above type error seem double: * You annotate you local "parse" function in "mkparser" with the type ('a * errors). The trouble is that named type variables in ocaml are not locally polymorphic. So this is ok to use them for a toplevel function, but not for local definitions (if you want them to be polymorphic). Just remove the annotation, or replace 'a by _ (the anonymous type variable). * The definition of parse itself seems wrong: Stop(stack p, errors) will have type 'cont steps, when you want something of type 'result steps. If you unify the two, you don't have enough polymorphism. The first problem is easily solved, but I don't understand enough to correct the second one. And the rest of the code does not typecheck anyway. Jacques Garrigue