Re: [Caml-list] Haskell parser combinators in OCaml?

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Jorgen Hermanrud Fjeld <jhf@hex.no>
> 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