From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jonathan.roewen@gmail.com>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
	by yquem.inria.fr (Postfix) with ESMTP id 0E04ABBBB
	for <caml-list@yquem.inria.fr>; Fri, 31 Mar 2006 05:00:51 +0200 (CEST)
Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.201])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k2V30okF001323
	for <caml-list@yquem.inria.fr>; Fri, 31 Mar 2006 05:00:50 +0200
Received: by zproxy.gmail.com with SMTP id 13so601775nzp
        for <caml-list@yquem.inria.fr>; Thu, 30 Mar 2006 19:00:49 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=AJPL+bSHomFAfWzIs5W2aI4c4eltVVbXI272gzgnWn5/dkv4WY1ibD+28rd96bT1Sjrl9UEGauC/wCnhFBjqPzucCdIumRqChdSE1zdmC2PAvZqNh6uSDG7ARMZU/l21nlac/HkxVnvUzAGu8X2W0lcfhZ1QN6QjnYMFFndFhhk=
Received: by 10.36.224.52 with SMTP id w52mr45912nzg;
        Thu, 30 Mar 2006 19:00:49 -0800 (PST)
Received: by 10.36.119.15 with HTTP; Thu, 30 Mar 2006 19:00:49 -0800 (PST)
Message-ID: <ad8cfe7e0603301900p461a05c5xb3961b11f98c2910@mail.gmail.com>
Date: Fri, 31 Mar 2006 15:00:49 +1200
From: "Jonathan Roewen" <jonathan.roewen@gmail.com>
To: OCaml <caml-list@yquem.inria.fr>
Subject: [Caml-list] Trying to understand recursion curiosity
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
X-Miltered: at nez-perce with ID 442C9B62.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; recursion:01 parser:01 combinators:01 combinator:01 recursive:01 parsers:01 rec:01 parser:01 stack:01 recursion:01 rec:01 val:01 omitted:01 parses:01 caml-list:01 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled 
	version=3.0.3

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 =3D literal "x"
> let s =3D literal ","

> (* initial definition *)
> let rec one_or_more_with_sep pa ps =3D
>     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 =3D one_or_more_with_sep x s

Stack overflow during evaluation (looping recursion?).

> (* new definition *)
> let rec one_or_more_with_sep pa ps =3D 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 =3D one_or_more_with_sep x s

val xs : string list -> (string list * string list) list =3D <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