streams and lazy evaluation

streams and lazy evaluation

[Laurent CHENO]

I have obtained:

>       Caml Light version 0.7mac

#let rec from n = [< 'n ; from (n+1) >] ;;
from : int -> int stream = <fun>
#let rec version1 flot = match flot with
    [< 'n >] -> [< '(2*n) ; version1 flot >] ;;
version1 : int stream -> int stream = <fun>
#version1 (from 0) ;;
- : int stream = <abstr>
#let rec version2 flot = match flot with
    [< 'n ; version2 reste >] -> [< '(2*n) ; reste >] ;;
version2 : int stream -> int stream = <fun>
#version2 (from 0) ;;
Uncaught exception: Out_of_memory
#

Why ??
Thank's for the answer.

-------------------------------------------------------------------
Laurent CHENO teaching at / enseignant au
        Lycée Louis-le-Grand - 123 rue Saint-Jacques
        75231 PARIS CEDEX 05 - FRANCE
personal phone (33) 1 48 05 16 04 - fax  (33) 1 48 07 80 18
-------------------------------------------------------------------

Re: streams and lazy evaluation

[Pierre Weis]

> #let rec from n = [< 'n ; from (n+1) >] ;;
> from : int -> int stream = <fun>
> #let rec version2 flot = match flot with
>     [< 'n ; version2 reste >] -> [< '(2*n) ; reste >] ;;
> version2 : int stream -> int stream = <fun>
> #version2 (from 0) ;;
> Uncaught exception: Out_of_memory

This is due to the evaluation strategy. You force the evaluation of
the lazy thunk by your pattern matching, since to prove that your
stream can be matched by the pattern:

  [< 'n ; version2 reste >]

the compiler must generate code to call version2 on the tail of the
stream. This falls in an infinite loop.

In contrast, in your first version, the recursive call to version is
in the right hand-side of the clause, when you build the final
result. This way it can be left unevaluated, until some piece of code
has to do some pattern matching on this stream result.

> #let rec version1 flot = match flot with
>     [< 'n >] -> [< '(2*n) ; version1 flot >] ;;
> version1 : int stream -> int stream = <fun>

To sumarize: stream construction leads to lazyness, while stream
pattern matching leads to unfrozing.

Pierre Weis
----------------------------------------------------------------------------
WWW Home Page: http://pauillac.inria.fr/~weis
Projet Cristal
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
Fax: +33 1 39 63 53 30
----------------------------------------------------------------------------