lazy vs fun

lazy vs fun

[Warren Harris]

Is there any advantage to using lazy evaluation in ocaml rather than  
just using thunks to defer evaluation? E.g.

let x = lazy (3+4)
let y = Lazy.force x

vs:

let x = fun () -> 3+4
let y = x ()

Perhaps it's just that the type int lazy_t is more informative than  
unit -> int?

Warren

Re: [Caml-list] lazy vs fun

[Jake Donham]

On Mon, Aug 24, 2009 at 2:57 PM, Warren Harris<warren@metaweb.com> wrote:
> Is there any advantage to using lazy evaluation in ocaml rather than just
> using thunks to defer evaluation? E.g.
>
> let x = lazy (3+4)
> let y = Lazy.force x
>
> vs:
>
> let x = fun () -> 3+4
> let y = x ()

Lazy cells don't just defer, they also memoize the returned value once
the cell is forced.

  # let x = lazy (print_endline "forced"; 1);;
  val x : int lazy_t = <lazy>
  # Lazy.force x;;
  forced
  - : int = 1
  # Lazy.force x;;
  - : int = 1

They even memoize exceptions:

  # let x = lazy (print_endline "forced"; failwith "failed");;
  val x : 'a lazy_t = <lazy>
  # Lazy.force x;;
  forced
  Exception: Failure "failed".
  # Lazy.force x;;
  Exception: Failure "failed".

Jake

Re: [Caml-list] lazy vs fun

[Warren Harris]

On Aug 24, 2009, at 3:04 PM, Jake Donham wrote:

>
> Lazy cells don't just defer, they also memoize the returned value once
> the cell is forced.

Thanks Jake - I guess I overlooked that in the manual.

Warren

Re: [Caml-list] lazy vs fun

[Jake Donham]

On Mon, Aug 24, 2009 at 3:15 PM, Warren Harris<warrensomebody@gmail.com> wrote:
>> Lazy cells don't just defer, they also memoize the returned value once
>> the cell is forced.
>
> Thanks Jake - I guess I overlooked that in the manual.

Hope you're doing well. Best of luck on the CUFP talk.

Jake

Re: [Caml-list] lazy vs fun

[Stéphane Glondu]

Warren Harris a écrit :
> Is there any advantage to using lazy evaluation in ocaml rather than
> just using thunks to defer evaluation? [...]

Two things I can think of right now: they are evaluated only once (even
if you call Lazy.force several times), and you can do pattern matching
with them.

> Perhaps it's just that the type int lazy_t is more informative than unit -> int?

That one, too.


Cheers,

-- 
Stéphane

Re: [Caml-list] lazy vs fun

[Martin Jambon]

Stéphane Glondu wrote:
> Warren Harris a écrit :
>> Is there any advantage to using lazy evaluation in ocaml rather than
>> just using thunks to defer evaluation? [...]
> 
> Two things I can think of right now: they are evaluated only once (even
> if you call Lazy.force several times), and you can do pattern matching
> with them.


Note that the memoization feature can be implemented like this:

let lz f =
  let result = ref `None in
  fun () ->
    match !result with
        `None ->
          (try
	     let y = f () in
             result := `Result y;
	     y
           with e ->
	     result := `Exn e;
	     raise e
	  )
      | `Result y -> y
      | `Exn e -> raise e


# #load"unix.cma";;
# let first_date = lz Unix.gettimeofday;;
val first_date : unit -> float = <fun>
# first_date ();;
- : float = 1251151837.4585979
# first_date ();;
- : float = 1251151837.4585979


However this is slightly less efficient than how "lazy" is implemented, and of
course you don't have the nice syntax nor the (recent) pattern matching feature.



Martin

-- 
http://mjambon.com/

Re: [Caml-list] lazy vs fun

[Martin Jambon]

Martin Jambon wrote:
> Stéphane Glondu wrote:
>> Warren Harris a écrit :
>>> Is there any advantage to using lazy evaluation in ocaml rather than
>>> just using thunks to defer evaluation? [...]
>> Two things I can think of right now: they are evaluated only once (even
>> if you call Lazy.force several times), and you can do pattern matching
>> with them.
> 
> 
> Note that the memoization feature can be implemented like this:
> 
> let lz f =
>   let result = ref `None in
>   fun () ->
>     match !result with
>         `None ->
>           (try
> 	     let y = f () in
>              result := `Result y;
> 	     y
>            with e ->
> 	     result := `Exn e;
> 	     raise e
> 	  )
>       | `Result y -> y
>       | `Exn e -> raise e


Oops.
The following makes it possible for f to be garbage-collected:


let lz f =
  let result = ref (`None f) in
  fun () ->
    match !result with
        `None f ->
          (try
	     let y = f () in
             result := `Result y;
	     y
           with e ->
	     result := `Exn e;
	     raise e
	  )
      | `Result y -> y
      | `Exn e -> raise e



Martin

-- 
http://mjambon.com/

Re: [Caml-list] lazy vs fun

[Warren Harris]

On Aug 24, 2009, at 4:11 PM, Martin Jambon wrote:

>
> Oops.
> The following makes it possible for f to be garbage-collected:
>
[...]

If I understand correctly, the closure associated with f will be  
collectable after the lazy_t is forced, whereas before its lifetime  
would be bound to the lifetime of the lazy_t. That's very subtle. It  
would have taken me some time to track that one down if it had come up  
in practice. Thanks,

Warren

Re: [Caml-list] lazy vs fun

[rixed]

> Oops.
> The following makes it possible for f to be garbage-collected:

...?
Because the fact that the fun calls f does not count as a reference ?

RE: [Caml-list] lazy vs fun

[David Allsopp]

rixed@happyleptic.org wrote:
> > Oops.
> > The following makes it possible for f to be garbage-collected:
> 
> ...?
> Because the fact that the fun calls f does not count as a reference ?

The anonymous function in the second version of Martin's function doesn't
"call" [f] (at least directly): imagine if the `None case had been written
with [g]s instead:

let lz f =
  let result = ref (`None f) in
  fun () ->
    match !result with
        `None g ->
          (try
	     let y = g () in
             result := `Result y;
	     y
           with e ->
	     result := `Exn e;
	     raise e
	  )
      | `Result y -> y
      | `Exn e -> raise e

The [fun] only "calls" (uses) [result]. In the first version, [f] could only
be collected after the [fun] had been collected (i.e. when the lazy value
itself is collected - not good). In the second version, [f] can be garbage
collected if the lazy value has already been forced (meaning that "[result =
`Result y | `Exn e]" so there will be no more references to [f]) - a clear
optimisation with no performance penalty in terms of space. 

The optimisation would be irrelevant if the ocaml compiler was lazy and just
included all of the scope in the closure for [fun], but minimising (and
eliminating, where possible) closures is a critical part of ML compilers
(I'd be amazed if it's not covered in all of the books you've mentioned
previously and I wish I could remember the name usually given to the
problem... but I'm sure someone will chip in with it!)


David

Re: [Caml-list] lazy vs fun

[rixed]

I had to read it three times, but I now understand the issue.
I initialy though the first version was somewhat bugged :-)

Now I understand why the second one is better. This kind of
optimisation is very interresting (not capturing all the scope
when building a closure). I will look for it now.

And BTW, if I find the proper name for this technique in the
book that I'm currently reading (The Impl. of Func. Prog. Lang.)
then I will post it here to refresh your memory :)