January 2003

Semantics of Lazy Evaluation

Introduction

This document does not cover the use of lazy evaluation in the implementation layer of a computing system. Instead we use Haskell to touch on the lazy evaluation semantics, and give a feel for yet another language feature.

Lazy Evaluation semantics are quite simple and can be implemented with a set of Design Patterns in an OO system. This is because the semantics take advantage of simple recursive definitions to generate apparently infinite sets. These semantics can be easily implemented by any university student.

Linear Recursive Structure

Here are two of the most common examples of Haskell code that use the recursive definitions. Comments are in blue for clarity.

The first, "iterate", takes a function and a value and returns a list

iterate :: (a -> a) -> a -> [a]
--The result is going to be the list of [x, f(x), f(f(x)), ...]
--Haskell uses nested ordered pairs to define sequences:
--     [a, b, c, d, e] = [a, [b, [c, [d, e]]]]
--Using standard function notation, iterate() is recursively defined as:
--     iterate(f, x) = [x, iterate(f, f(x))]
iterate f x = x : iterate f (f x)

The second example makes the set of primes. Two functions are declared here; the latter to support the former

--return list of primes
all'primes :: [Int]
--The magic is done by using the sieve function on list of all integers >= 2
all'primes = sieve [2 ..]

--Number sieve
--Take a list of numbers and return a list of numbers
sieve :: [Int] -> [Int]
--Pattern match first entry (p), assume prime.
--Rest of list consists of all x xs that are not divisible by p
sieve (p : xs) = p : sieve [x | x <- xs, x 'mod' p /= 0]

Application

I find that there is only a small domain of problems where these Lazy evaluation semantics are useful, and that is in the domain of infinite sets, or more specifically in numerical problems. Therefore do not expect this feature to be useful in most programming problems.

One Other Note

I am at a loss to know where I can put the following, so here is something I got off the net. The only item worth elaborating is that Lazy evaluation is called "Confusing to program" because the continuations used to implement lazy evaluation are often not true continuations, often missing important bindings to environmental variables. Other times the computing system does not track the dependencies among side effects making expected side effects (using strict evaluation assumptions) not appear when required.

Disadvantages of Lazy Evaluation: http://www.cs.oberlin.edu/~jwalker/bscheme/rationale/lazyEval.html

Call by Need (lazy)	Call by Value (strict)
Advantages Infinite Lists Never compute unneeded values Don't get stuck on infinite recursions if not used Used to easily implement IF, AND, OR Provides explanation and implementation of the ',' evaluation operator	Advantages Simple and well understood Predictable Easily implementable Interacts well with other languages
Disadvantages Confusing to program Difficult to predict esp. with side effects Almost impossible to implement. Doesn't link well to other languages Still requires macros	Disadvantages Doesn't allow infinite lists May compute unneeded values Doesn't explain ',' evaluation operator, this must be tacked on. More things must be macros

Some References

• Lazy Eval Overview: http://cs.anu.edu.au/Student/comp3610/lectures/lazy_06.pdf (cache)
• Design Patterns for Lazy Evaluation: http://exciton.cs.rice.edu/research/SIGCSE00/DPLazy.pdf (cache)