Streams Are Delayed Lists

As we saw in section ,
sequences can serve as standard interfaces for combining program
modules. We formulated powerful abstractions for manipulating
sequences, such as `map`, `filter`, and `accumulate`, that
capture a wide variety of operations in a manner that is both succinct
and elegant.

Unfortunately, if we represent sequences as lists, this elegance is bought at the price of severe inefficiency with respect to both the time and space required by our computations. When we represent manipulations on sequences as transformations of lists, our programs must construct and copy data structures (which may be huge) at every step of a process.

To see why this is true, let us compare two programs for computing the
sum of all the prime numbers in an interval. The first program is
written in standard iterative style:^{}

(define (sum-primes a b) (define (iter count accum) (cond ((> count b) accum) ((prime? count) (iter (+ count 1) (+ count accum))) (else (iter (+ count 1) accum)))) (iter a 0))The second program performs the same computation using the sequence operations of section :

(define (sum-primes a b) (accumulate + 0 (filter prime? (enumerate-interval a b))))

In carrying out the computation, the first program needs to store only
the sum being accumulated. In contrast, the filter in the second
program cannot do any testing until `enumerate-interval` has
constructed a complete list of the numbers in the interval. The
filter generates another list, which in turn is passed to `
accumulate` before being collapsed to form a sum. Such large
intermediate storage is not needed by the first program, which we can
think of as enumerating the interval incrementally, adding each prime
to the sum as it is generated.

The inefficiency in using lists becomes painfully apparent if we use the sequence paradigm to compute the second prime in the interval from 10,000 to 1,000,000 by evaluating the expression

(car (cdr (filter prime? (enumerate-interval 10000 1000000))))This expression does find the second prime, but the computational overhead is outrageous. We construct a list of almost a million integers, filter this list by testing each element for primality, and then ignore almost all of the result. In a more traditional programming style, we would interleave the enumeration and the filtering, and stop when we reached the second prime.

Streams are a clever idea that allows one to use sequence manipulations without incurring the costs of manipulating sequences as lists. With streams we can achieve the best of both worlds: We can formulate programs elegantly as sequence manipulations, while attaining the efficiency of incremental computation. The basic idea is to arrange to construct a stream only partially, and to pass the partial construction to the program that consumes the stream. If the consumer attempts to access a part of the stream that has not yet been constructed, the stream will automatically construct just enough more of itself to produce the required part, thus preserving the illusion that the entire stream exists. In other words, although we will write programs as if we were processing complete sequences, we design our stream implementation to automatically and transparently interleave the construction of the stream with its use.

On the surface, streams are just lists with different names for the
procedures that manipulate them. There is a constructor,
`cons-stream`, and two selectors,
`stream-car` and
`
stream-cdr`, which satisfy the constraints

There is a distinguishable object,

(define (stream-ref s n) (if (= n 0) (stream-car s) (stream-ref (stream-cdr s) (- n 1)))) (define (stream-map proc s) (if (stream-null? s) the-empty-stream (cons-stream (proc (stream-car s)) (stream-map proc (stream-cdr s))))) (define (stream-for-each proc s) (if (stream-null? s) 'done (begin (proc (stream-car s)) (stream-for-each proc (stream-cdr s)))))

(define (display-stream s) (stream-for-each display-line s))(define (display-line x) (newline) (display x))

To make the stream implementation automatically and transparently
interleave the construction of a stream with its use, we will arrange
for the `cdr` of a stream to be evaluated when it is accessed by
the `stream-cdr` procedure rather than when the stream is
constructed by `cons-stream`. This implementation choice is
reminiscent of our discussion of rational numbers in
section , where we saw that we can
choose to implement rational numbers so that the reduction of
numerator and denominator to lowest terms is performed either at
construction time or at selection time. The two rational-number
implementations produce the same data abstraction, but the choice has
an effect on efficiency. There is a similar relationship between
streams and ordinary lists. As a data abstraction, streams are the
same as lists. The difference is the time at which the elements are
evaluated. With ordinary lists, both the `car` and the `cdr`
are evaluated at construction time. With streams, the `cdr` is
evaluated at selection time.

Our implementation of streams will be based on a special form called
`delay`. Evaluating `(delay exp)` does not
evaluate the expression exp, but rather returns a so-called
*
delayed object*, which we can think of as a ``promise'' to evaluate
exp at some future time. As a companion to `delay`, there is
a procedure called
`force` that takes a delayed object as
argument and performs the evaluation--in effect, forcing the
`delay` to fulfill its promise. We will see below how `delay`
and `force` can be implemented, but first let us use these to
construct streams.

`Cons-stream` is a special form defined so that

(cons-stream a b)is equivalent to

(cons a (delay b))What this means is that we will construct streams using pairs. However, rather than placing the value of the rest of the stream into the

(define (stream-car stream) (car stream))(define (stream-cdr stream) (force (cdr stream)))

The stream implementation in action

To see how this implementation behaves, let us analyze the ``outrageous'' prime computation we saw above, reformulated in terms of streams:

(stream-car (stream-cdr (stream-filter prime? (stream-enumerate-interval 10000 1000000))))We will see that it does indeed work efficiently.

We begin by calling `stream-enumerate-interval` with
the arguments 10,000 and 1,000,000. `Stream-enumerate-interval`
is the stream analog of `enumerate-interval`
(section ):

(define (stream-enumerate-interval low high) (if (> low high) the-empty-stream (cons-stream low (stream-enumerate-interval (+ low 1) high))))and thus the result returned by

(cons 10000 (delay (stream-enumerate-interval 10001 1000000)))

That is, `stream-enumerate-interval`
returns a stream represented as a pair whose `car`
is 10,000 and whose `cdr` is a promise to enumerate more of the
interval if so requested. This stream is now filtered for primes,
using the stream analog of the `filter` procedure
(section ):

(define (stream-filter pred stream) (cond ((stream-null? stream) the-empty-stream) ((pred (stream-car stream)) (cons-stream (stream-car stream) (stream-filter pred (stream-cdr stream)))) (else (stream-filter pred (stream-cdr stream)))))

(cons 10001 (delay (stream-enumerate-interval 10002 1000000)))

(cons-stream (stream-car stream) (stream-filter pred (stream-cdr stream)))which in this case is

(cons 10007 (delay (stream-filter prime? (cons 10008 (delay (stream-enumerate-interval 10009 1000000))))))This result is now passed to

(cons 10009 (delay (stream-filter prime? (cons 10010 (delay (stream-enumerate-interval 10011 1000000))))))

In general, we can think of delayed evaluation as ``demand-driven'' programming, whereby each stage in the stream process is activated only enough to satisfy the next stage. What we have done is to decouple the actual order of events in the computation from the apparent structure of our procedures. We write procedures as if the streams existed ``all at once'' when, in reality, the computation is performed incrementally, as in traditional programming styles.

Implementing `delay` and `force`

Although `delay` and `force` may seem like mysterious
operations, their implementation is really quite straightforward.
`Delay` must package an expression so that it can be evaluated
later on demand, and we can accomplish this simply by treating the
expression as the body of a procedure. `Delay` can be a special
form such that

(delay exp)is syntactic sugar for

(lambda () exp)

(define (force delayed-object) (delayed-object))

This implementation suffices for `delay` and `force` to work
as advertised, but there is an important optimization that we can
include. In many applications, we end up forcing the same delayed object
many times. This can lead to serious inefficiency in recursive
programs involving streams. (See
exercise .) The solution is to build
delayed objects so that the first time they are forced, they store the
value that is computed. Subsequent forcings will simply return the
stored value without repeating the computation. In other words, we
implement `delay` as a special-purpose memoized procedure similar
to the one described in exercise . One way to
accomplish this is to use the following procedure, which takes as
argument a procedure (of no arguments) and returns a memoized version
of the procedure. The first time the memoized procedure is run, it
saves the computed result. On subsequent evaluations, it simply
returns the result.

(define (memo-proc proc) (let ((already-run? false) (result false)) (lambda () (if (not already-run?) (begin (set! result (proc)) (set! already-run? true) result) result))))

(memo-proc (lambda () exp))and

**Exercise.** Complete the following definition, which
generalizes `stream-map` to allow procedures that
take multiple arguments, analogous to `map` in
section , footnote .

(define (stream-map proc . argstreams) (if (?? (car argstreams)) the-empty-stream (?? (apply proc (map ?? argstreams)) (apply stream-map (cons proc (map ?? argstreams))))))

**Exercise.** In order to take a closer look at delayed evaluation, we will use the
following procedure, which simply returns its argument after printing it:

(define (show x) (display-line x) x)What does the interpreter print in response to evaluating each expression in the following sequence?

(define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7)

**Exercise.**
Consider the sequence of expressions

(define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) (stream-ref y 7) (display-stream z)What is the value of