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