11.4.2 Lazy Programming

Lazy evaluation enables programming constructs that are not possible with eager evaluation. For example, with lazy evaluation we can define a procedure that behaves like the if expression special form.
We first define true and false as procedures that take two parameters and output the first or second parameter:

(define true (lambda (a b) a))
(define false (lambda (a b) b))

Then, this definition defines a procedure with behavior similar to the if special form:

(define ifp (lambda (p c a) (p c a)))

With eager evaluation, this would not work since all operands would be evaluated; with lazy evaluation, only the operand that corresponds to the appropriate consequent or alternate expression is evaluated.

Lazy evaluation also enables programs to deal with seemingly infinite data structures. This is possible since only those values of the apparently infinite data structure that are used need to be created.

Suppose we define procedures similar to the Scheme procedures for manipulating pairs:

(define cons (lambda (a b) (lambda (p) (if p a b))))
(define car (lambda (p) (p true)))
(define cdr (lambda (p) (p false)))
(define null false)
(define null? (lambda (x) (= x false)))

These behave similarly to the corresponding Scheme procedures, except in LazyCharme their operands are evaluated lazily. This means, we can define an infinite list:

(define ints-from (lambda (n) (cons n (ints-from (+ n 1)))))

With eager evaluation, (ints-from 1) would never finish evaluating; it has no base case for stopping the recursive applications. In LazyCharme, however, the operands to the cons application in the body of ints-from are not evaluated until they are needed. Hence, (ints-from 1) terminates and produces a seemingly infinite list, but only the evaluations that are needed are performed:

LazyCharme> (car (ints-from 1))
LazyCharme> (car (cdr (cdr (cdr (ints-from 1)))))

Some evaluations fail to terminate even with lazy evaluation. For example, assume the standard definition of list-length:

(define list-length
   (lambda (lst) (if (null? lst) 0 (+ 1 (list-length (cdr lst))))))

An evaluation of (length (ints-from 1)) never terminates. Every time an application of list-length is evaluated, it applies cdr to the input list, which causes ints-from to evaluate another cons, increasing the length of the list by one. The actual length of the list is infinite, so the application of list-length does not terminate.

Lists with delayed evaluation can be used in useful programs. Reconsider the Fibonacci sequence from Chapter 7. Using lazy evaluation, we can define a list that is the infinitely long Fibonacci sequence:1

(define fibo-gen (lambda (a b) (cons a (fibo-gen b (+ a b)))))
(define fibos (fibo-gen 0 1))

The $n^{th}$ Fibonacci number is the $n^{th}$ element of fibos:

(define fibo
  (lambda (n)
    (list-get-element fibos n)))

where list-get-element is defined as it was defined in Chapter 5.

Another strategy for defining the Fibonacci sequence is to first define a procedure that merges two (possibly infinite) lists, and then define the Fibonacci sequence recursively. The merge-lists procedure combines elements in two lists using an input procedure.

(define merge-lists
  (lambda (lst1 lst2 proc)
    (if (null? lst1) null
        (if (null? lst2) null
            (cons (proc (car lst1) (car lst2))
                  (merge-lists (cdr lst1) (cdr lst2) proc))))))

We can define the Fibonacci sequence as the combination of two sequences, starting with the 0 and 1 base cases, combined using addition where the second sequence is offset by one position:

(define fibos (cons 0 (cons 1 (merge-lists fibos (cdr fibos) +))))

The sequence is defined to start with 0 and 1 as the first two elements. The following elements are the result of merging fibos and (cdr fibos) using the + procedure. This definition relies heavily on lazy evaluation; otherwise, the evaluation of (merge-lists fibos (cdr fibos) +) would never terminate: the input lists are effectively infinite.

Exercise 11.3. Define the sequence of factorials as an infinite list using delayed evaluation.

Exercise 11.4. Describe the infinite list defined by each of the following definitions. (Check your answers by evaluating the expressions in LazyCharme.) a. (define p (cons 1 (merge-lists p p +)))
b. (define t (cons 1 (merge-lists t (merge-lists t t +) +)))
c. (define twos (cons 2 twos))
d. (define doubles (merge-lists (ints-from 1) twos *))

Exercise 11.5. $\left[\star \right]$ $\left[\star \right]$ A simple procedure known as the Sieve of Eratosthenes for finding prime numbers was created by Eratosthenes, an ancient Greek mathematician and astronomer. The procedure imagines starting with an (infinite) list of all the integers starting from 2. Then, it repeats the following two steps forever:

  1. Circle the first number that is not crossed off; it is prime.
  2. Cross off all numbers that are multiples of the circled number.

To carry out the procedure in practice, of course, the initial list of numbers must be finite, otherwise it would take forever to cross off all the multiples of 2. But, with delayed evaluation, we can implement the Sieve procedure on an effectively infinite list.

Implement the sieve procedure using lists with lazy evaluation. You may find the list-filter and merge-lists procedures useful, but will probably find it necessary to define some additional procedures.

  1. This example is based on Abelson and Sussman, Structure and Interpretation of Computer Programs, Section 3.5.2, which also presents several other examples of interesting programs constructed using delayed evaluation.