(This is a post for CS320 Boston University.)

In most programming languages, expressions are evaluated right after it is bound to a variable. This is eager evaluation.

However, you can't always evaluate an expression immediately.

// pseudo code
val natlist = 0 :: 1 :: 2 :: ....


An infinite list can't be expressed in a eager evaluation manner because that will cause a infinite loop and eventually corrupt your stack.

For such a reason, we need lazy evaluation which will defer the computation of an expression until it is actually needed. This is also known as call-by-need.

// pseudo code
val lazylist = $delay (0 :: 1 :: 2 :: ...) // here we have to evaluate the first 10 elements val _ = show (lazylist, 10)  Lazy evaluation has other advantages. Since lazy evaluation usually comes together with memorization, efficiency could be improved. Suppose we have a complex experssion consists of several subexpression, e.g. (1+2)-(1+2) • for eager evaluation: every subexpression (1+2) will be evaluated right away no matter they are the same or not. • for lazy evaluation with memorization: subexpression evaluation will be deferred until the evaluation of top-level expression (...) - (...). Also, when a subexp (1+2) is evaluated, the result will be memorized and when the same subexp is evaluated for the second time, we just retrieve the result without actual computation. ### Lazy Evaluation in ATS In ATS, we use $delay (exp) to delay the evaluation of some expression exp. And we use lazy () to get a lazy type from an existing type.

If the type of exp is T, then \$delay (exp) will have type lazy (exp).

We use !exp to force the evaluation of some lazy expression exp.

### Example and Exercise

Please read the following code carefully, especially the definition of lazy list, those signatures of lazy functions, and an example of an infinite fibonacci number list.

• from (n:int): generate an infinite integer list from n
• sieve (xs:lazy(list(int))): lazy (list (int)): generate an infinite prime number list using this algorithm
• intpairs(n:int): lazy (list (@(int, int))): generate integer pairs as shown here
(0,0),
...