From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <shawjef3@msu.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 8C1F1BC69
	for <caml-list@yquem.inria.fr>; Sat, 24 Mar 2007 02:28:19 +0100 (CET)
Received: from sys29.mail.msu.edu (sys29.mail.msu.edu [35.9.75.129])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l2O1SHCw007777
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
	for <caml-list@inria.fr>; Sat, 24 Mar 2007 02:28:19 +0100
Received: from shawjef3 by sys29.mail.msu.edu with local (Exim 4.52 #1)
	id 1HUv3J-0002P1-Bt
	for caml-list@inria.fr; Fri, 23 Mar 2007 21:28:17 -0400
From: "Jeffrey Loren Shaw" <shawjef3@msu.edu>
To: caml-list@inria.fr
Subject: lazy evaluation of combinator parsers
Date: Fri, 23 Mar 2007 21:28:16 -0400
Mime-Version: 1.0
Content-Type: text/plain; format=flowed; charset="utf-8"
Content-Transfer-Encoding: 7bit
Message-Id: <E1HUv3J-0002P1-Bt@sys29.mail.msu.edu>
X-Virus: None found by Clam AV
X-j-chkmail-Score: MSGID : 46047EB2.000 on concorde : j-chkmail score : X : 0/20 1 0.000 -> 1
X-Miltered: at concorde with ID 46047EB2.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; combinator:01 parsers:01 camlers:01 combinator:01 parser:01 ocaml:01 syntax:01 seq:01 stack:01 seq:01 regex:01 regex:01 rec:01 rec:01 functions:01 

Hello fellow Camlers, 

I'm trying to write a combinator parser in ocaml that uses lazy evaluation. 
My goal is that it won't get stuck on infinite loops. So for instance I want 
to be able to parse something like (in regex syntax) 

a* 

let alt p1 p2 xs = append (p1 xs) (p2 xs) 

(* regex ? *)
let opt a = alt a epsilon 

let rec recseq a =
 seq
   a
   (recseq a) 

(* regex * *)
let rec star a =
 recseq (opt a) 

However, "star (symbol 'a')" causes a stack overflow. I'm not sure why, 
since my seq and alt functions are lazy. seq depends on fold_right, map and 
append, and alt depends on append. fold_right, map and append are all lazy. 
The definitions of alt and seq contain no Lazy.forces. 

sources: 

http://www.msu.edu/~shawjef3/combparslazy3.ml
http://www.msu.edu/~shawjef3/lazylist3.ml 

I would greatly appreciate any help! 

Jeff