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=SUBJECT_EXCESS_QP 
	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 45362BC69
	for <caml-list@yquem.inria.fr>; Tue, 20 Mar 2007 19:50:05 +0100 (CET)
Received: from sys25.mail.msu.edu (sys25.mail.msu.edu [35.9.75.125])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l2KIo3vx028525
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
	for <caml-list@inria.fr>; Tue, 20 Mar 2007 19:50:04 +0100
Received: from shawjef3 by sys25.mail.msu.edu with local (Exim 4.52 #1)
	id 1HTjPH-00082g-6M
	for caml-list@inria.fr; Tue, 20 Mar 2007 14:50:03 -0400
From: "Jeffrey Loren Shaw" <shawjef3@msu.edu>
To: caml-list@inria.fr
Subject: possible way to improve =?utf-8?Q?=22lazy=22?=
Date: Tue, 20 Mar 2007 14:50:02 -0400
Mime-Version: 1.0
Content-Type: text/plain; format=flowed; charset="utf-8"
Content-Transfer-Encoding: 7bit
Message-Id: <E1HTjPH-00082g-6M@sys25.mail.msu.edu>
X-Virus: None found by Clam AV
X-Miltered: at concorde with ID 46002CDB.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; stack:01 recursion:01 val:01 stack:01 cheers:01 rec:01 rec:01 int:01 fib:01 fib:01 define:01 argument:02 lazy:02 lazy:02 caml:02 

Dear Caml team, 

Please consider this suggestion for an improvement of how caml handles lazy 
evaluation. First I give an example. 

type 'a t = Cons of 'a Lazy.t * ('a t) Lazy.t | Nil 

let cons a b = Cons (lazy a, lazy b) 

Suppose I want to build the Fibonacci sequence using the above function, 
cons. 

# let fib =
 let rec aux a b =
   cons a (aux b (a+b))
 in
   aux 0 1;;
       Stack overflow during evaluation (looping recursion?). 

whereas 

# let fib =
 let rec aux a b =
   Cons(lazy a, lazy (aux b (a+b)))
 in
   aux 0 1;;
       val fib : int t = Cons (<lazy>, <lazy>) 

After a while I realized that there is a stack overflow because calling cons 
evaluates its arguments *before* making them. This causes the infinite loop. 

Now suppose we have a function like the above cons. Because the b argument 
is never used in an eager way in the function, couldn't the interpreter say 
"oh, b should not be evaluated"? This would allow the first example of fib 
work, which looks like it should work unless you know what's going on behind 
the scenes. 

The fix for now is to define cons as 

let cons a b = Cons (a,b) 

so that whatever calls cons is forced to make sure a and b are already lazy. 

let fib =
 let rec aux a b =
   cons (lazy a) (lazy (aux b (a+b)))
 in
   aux 0 1 

But this also forces the calling function to be less clear. I would prefer 
to be able to write 

let fib =
 let rec aux a b =
   cons a (aux b (a+b))
 in
   aux 0 1;; 

and rest assured that Caml would understand that cons does not need its 
arguments evaluated. 

Cheers,
Jeff