Streams as Lazy Lists

In section , we showed how to implement streams
as delayed lists. We introduced special forms `delay` and `
cons-stream`, which allowed us to construct a ``promise'' to compute
the `cdr` of a stream, without actually fulfilling that promise
until later. We could use this general technique of introducing
special forms whenever we need more control over the evaluation process,
but this is awkward. For one thing, a special form is not a
first-class object like a procedure, so we cannot use it together with
higher-order procedures.
^{} Additionally,
we were forced to create streams as a new kind of data object
similar but not identical to lists, and this required us to
reimplement many ordinary list operations (`map`, `append`, and
so on) for use with streams.

With lazy evaluation, streams and lists can be identical, so there is
no need for special forms or for separate list and stream operations.
All we need to do is to arrange matters so that `cons` is
non-strict. One way to accomplish this is to extend the lazy
evaluator to allow for non-strict primitives, and to implement `
cons` as one of these. An easier way is to recall
(section ) that there is no fundamental need to
implement `cons` as a primitive at all. Instead, we can represent
pairs as procedures:
^{}

(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))

In terms of these basic operations, the standard definitions of the list operations will work with infinite lists (streams) as well as finite ones, and the stream operations can be implemented as list operations. Here are some examples:

(define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1)))) (define (map proc items) (if (null? items) '() (cons (proc (car items)) (map proc (cdr items))))) (define (scale-list items factor) (map (lambda (x) (* x factor)) items)) (define (add-lists list1 list2) (cond ((null? list1) list2) ((null? list2) list1) (else (cons (+ (car list1) (car list2)) (add-lists (cdr list1) (cdr list2)))))) (define ones (cons 1 ones)) (define integers (cons 1 (add-lists ones integers))) ;;; L-Eval input: (list-ref integers 17) ;;; L-Eval value: 18

Note that these lazy lists are even lazier than the streams of
chapter 3: The `car` of the list, as well as the `cdr`, is
delayed.
^{}
In fact, even accessing the `car` or `cdr` of a lazy
pair need not force the value of a list element. The value will be
forced only when it is really needed--e.g., for use as the
argument of a primitive, or to be printed as an answer.

Lazy pairs also help with the problem that arose with streams in
section , where we found that
formulating stream models of systems with loops may require us to
sprinkle our programs with
explicit `delay` operations, beyond the
ones supplied by `cons-stream`. With lazy evaluation, all
arguments to procedures are delayed uniformly. For instance, we can
implement procedures to integrate lists and solve differential
equations as we originally intended in
section :

(define (integral integrand initial-value dt) (define int (cons initial-value (add-lists (scale-list integrand dt) int))) int) (define (solve f y0 dt) (define y (integral dy y0 dt)) (define dy (map f y)) y) ;;; L-Eval input: (list-ref (solve (lambda (x) x) 1 0.001) 1000) ;;; L-Eval value: 2.716924

**Exercise.**
Give some examples that illustrate the difference between the streams
of chapter 3 and the ``lazier'' lazy lists described in this section.
How can you take advantage of this extra laziness?

**Exercise.**
Ben Bitdiddle tests the lazy list implementation given above by
evaluating the expression

(car '(a b c))To his surprise, this produces an error. After some thought, he realizes that the ``lists'' obtained by reading in quoted expressions are different from the lists manipulated by the new definitions of

**Exercise.**
Modify the driver loop for the evaluator so that lazy pairs and lists
will print in some reasonable way. (What are you going to do about
infinite lists?) You may also need to modify the representation of
lazy pairs so that the evaluator can identify them in order
to print them.