(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),