[Caml-list] Trying to understand recursion curiosity

[Caml-list] Trying to understand recursion curiosity

[Jonathan Roewen]

Hi,

I have some code for implementing some parser combinators, and have
stumbled upon some unexpected behaviour in my definition of a
combinator that's recursive.

Here's the definitions:

> (* some parsers *)
> let x = literal "x"
> let s = literal ","

> (* initial definition *)
> let rec one_or_more_with_sep pa ps =
>     try_with
>        (then3 (fun x y z -> x :: z) pa ps (one_or_more_with_sep pa ps))
>        (pa --> (fun x -> [x]))

> (* try to define a parser *)
> let xs = one_or_more_with_sep x s

Stack overflow during evaluation (looping recursion?).

> (* new definition *)
> let rec one_or_more_with_sep pa ps = fun ts ->
>     try_with
>         (then3 (fun x y z -> x :: z) pa ps (one_or_more_with_sep pa ps))
>         (pa --> (fun x -> [x]))
>         ts

> (* try to define a parser with amended definition *)
> let xs = one_or_more_with_sep x s

val xs : string list -> (string list * string list) list = <fun>

I've omitted the definitions of try_with, then3, and apply (-->).
try_with tries the first parser, and if it returns the empty list,
uses the second.

BTW: a parser returns a list of possible parses.

Kindest Regards,

Jonathan Roewen