possible way to improve "lazy"

possible way to improve "lazy"

[Jeffrey Loren Shaw]

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 

Re: possible way to improve "lazy"

[Zheng Li]

Hi,

"Jeffrey Loren Shaw" <shawjef3@msu.edu> writes:
> let cons a b = Cons (lazy a, lazy b) 
Note that there is nothing wrong with this expression, it has valid semantics,
just not the semantics you want. 

> 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. 
Yes, OCaml use eager (strict) evaluation, which is CBV by default. If you want
lazy, you must make it explicit, and more important, explicit it before any
thing happens -- the first "anything" is the evaluation of arguments not the
function call.

> 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. 
I'm afraid that's not easy, at least when talking about a universal
solution. It's the base of evaluation model. Your proposal means the model must
be intelligent enough to know what should be evaluated eagerly what should be
evaluated lazily. 

> The fix for now is to define cons as 
> let cons a b = Cons (a,b) 
> let fib =
> let rec aux a b =
>   cons (lazy a) (lazy (aux b (a+b)))
> in
>   aux 0 1 

Maybe this way is clearer:
$ ocaml -rectypes
# type 'a t = 'a * 'a t Lazy.t;;
# let fib = let rec aux a b = a, (lazy (aux b (a+b))) in aux 1 2;;

and you don't reinvent wheels, there's a nice Stream module in OCaml
$ ocaml camlp4o.cma
# let fib = let rec aux x y = [< 'x; aux y (x + y) >] in aux 1 2;;


Regardz
-- 
Zheng Li
http://www.pps.jussieu.fr/~li

Re: [Caml-list] possible way to improve "lazy"

[Daniel Bünzli]

Le 20 mars 07 à 19:50, Jeffrey Loren Shaw a écrit :

> Please consider this suggestion for an improvement of how caml  
> handles lazy evaluation.

At a certain point there was this discussion [1], but I guess the  
subsequent proposal never materialized because of tricky issues.

Daniel

[1] http://caml.inria.fr/pub/ml-archives/caml-list/ 
2004/07/2461a873d5d45c22fef8816d4fe08d6b.fr.html

Re: [Caml-list] possible way to improve "lazy"

[Jeffrey Loren Shaw]

Daniel, 

Thanks for that link! It looks like this has been discussed at some length. 

Well hm, I guess consider my post a request for renewed effort on this 
front. Lazy evaluation can be very useful, and since caml already supports 
it, it'd be nice if it were easier to use. 

Zheng Li,
Yes that's exactly what I'm asking for! It'd be really cool to have in caml 
IMO. 

type 'a t = 'a * 'a t Lazy.t;; 

This will work for infinite lists, but there is no empty list, so it's not 
quite a proper lazy list. 

And streams aren't right either, because they are destructive. If you ask 
for the 3rd element on a lazy list, you can still ask for the 1st and 2nd 
elements, whereas streams are unable to recover the previous values. This 
has its applications but it's not the same as a list. 

Thanks for the posts! I'll keep plugging away to try and get my 
combinatorial parser to work perfectly lazy. I'm close but I'm having 
trouble with sequencing. 

Jeff