Lecture 10: Lazy Evaluation

===============================================================
Lazy evaluation.

ML: 

(* non-tail-recursive version *)
fun range (n,m) = if m<n then [] else n :: range(n+1,m);

(* tail recursive version *)
fun range1 (n,m,xs) = if m<n then xs else range1(n,m-1,m::xs);
fun range'(n,m) = range1(n,m,[]);

val big = range'(1,10000000);

val bigbig = big @ big   (* how many operations? *)

Haskell:

  let big = [1..10000000]

  let bigbig = big ++ big    -- how many operations?


---------------
Controlling order of operations in ML

  fun f(x,y) = if odd x then [0] else y
  val f = fn : int * int list -> int list

  f(3, big@big);

Suspended computation:

  fun f'(x,y) = if odd x then [0] else y() 
  val f = fn : int * (unit -> int list) -> int list

  val thunk = fn () => big@big;
  val thunk : unit -> int list

  f'(3,thunk);

This returns [0] without having to compute big@big.

Another example: a conditional function

  fun cond(true,x,_) = x
    | cond(false,_,y) = y

Because of call-by-value, cond is not a substitute
for conditional expressions, i.e.

  if e1 then e2 else e3  

is not equivalent to 

  cond(e1,e2,e3)

because the latter evaluates both branch expressions
e1 and e2 before testing the value of e1.

But we can simulate if-then-else as a function
by using suspended expression evaluation (thunks):

  fun cond(true,x,_) = x()
    | cond(false,_,y) = y()

and translating

  if e1 then e2 else e3  

into

  cond(e1, fn()=>e2, fn()=>e3)

But in Haskell, all expressions are implicitly
suspended thunks!

  cond :: Bool -> t -> t -> t
  cond True x y = x
  cond False x y = y

  f :: Int -> Int
  f x = f x
 
  cond True 3 (f 1)   ==>   3

So this cond function behaves like if-then-else.
This is also why

  let bigbig = big ++ big

takes no time to compute.

We can create infinite lists:

  let posints = [1..]

We can concatenate an infinite list onto another list:

  let x = posints ++ []

We can define infinite lists by recursive equations:

  let ones = 1:ones

  let posints = 1 : (map (1+) posints)


----------------------------------------------------------------------
Example: Primes -- the sieve of Eratosthenes

1. Start with all candidates 

  nums = [2..]

2. take first element, 2, and eliminate its multiples
from the rest

  let notdivisibleby x y = mod y x /= 0

  primes = 2: ...

  nums2 = filter (notdivisibleby 2) nums

      nums2 = [3,5,...]

3. take first element of nums2, 3, and eliminate its
multiples

  primes = 2:3: ...

  nums3 = filter (notdivisbleby 3) nums2

4. repeat forever

Putting it together, we get a recursive definition

  let sieve (x:xs) = x : sieve (filter (notdivisibleby x) xs)

  let primes = sieve [2..]


Fibonacci numbers

  let fibs = 1:1:(zipWith (+) fibs (tail fibs))

where zipWith is a map function, but for binary functions
applied to respective elements of two lists:

  let zipWith f l1 l2 = map (uncurry f) (zip l1 l2)

We can call these infinite lists "streams".

----------------------------------------------------------------------
Example: Streams in ML

datatype 'a stream = S of unit -> 'a * 'a stream;

fun nums (n:int) : int stream = S(fn () => (n, nums (n+1)));

fun shd (S s) = #1(s ());
fun stl (S s) = #2(s ());

fun stake 0 (S s) = []
  | stake n (S s) = let val (x,s') = s() in x::(stake (n-1) s') end

val posints = nums 1;

- stake 10 posints;
val it = [1,2,3,4,5,6,7,8,9,10] : int list


What's missing?  Memoization!

Here is a memoized version of streams in ML.

------------------------------------------------------------
(* file: stream2.sml *)

datatype 'a susp = UNEVAL of unit -> 'a | EVAL of 'a;

(* stream datatype, using susp for suspensions, and a
 * ref cell for memoization *)
datatype 'a stream = S of ('a * 'a stream) susp ref;

(* strict cons, for use when we already have a stream *)
fun scons (x, s) = S(ref(EVAL(x,s)));

(* lazy cons, for when we are defining a stream whose tail has not been computed yet *)
fun lcons f = S(ref(UNEVAL f))

(* shd and stl are stream versions of list hd and tl.
 * note the memoization effect in the UNEVAL case. *)
fun shd (S r) =
    case !r
      of EVAL(x,s) => x
       | UNEVAL(f) => let val p as (x,s) = f() in r := EVAL p; x end;

fun stl (S r) =
    case !r
      of EVAL(x,s) => s
       | UNEVAL(f) => let val p as (x,s) = f() in r := EVAL p; s end;

(* destruct a stream into its head and tail elements *)
fun sdest (S r) =
    case !r
      of EVAL(x,s) => (x,s)
       | UNEVAL(f) => let val p as (x,s) = f() in r := EVAL p; p end;

fun stake 0 s = []
  | stake n s = shd s :: stake (n-1) (stl s);

(* generate the infinite stream of successive numbers starting with n *)
fun nums n = lcons(fn() => (n, nums(n+1)));

(* stream of all positive ints:  1,2,3,... *)
val posints = nums 1;


(* Sieve of Eratosthenes *)

fun notdivisibleby n m = m mod n <> 0;

(* note the use of lcons in sfilter and sieve. scons won't work *)
fun sfilter f s =
    let val (x,s') = sdest s
     in if f x then lcons(fn () => (x, sfilter f s'))
        else sfilter f s'
    end;

fun sieve s = 
    let val (x,s') = sdest s 
     in lcons(fn () => (x, sieve(sfilter (notdivisibleby x) s')))
    end;

(* stream of prime numbers *)
val primes = sieve (nums 2);

fun first_n_primes n = stake n primes;

------------------------------------------------------------