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 \begin{eqnarray*} \mbox{(stream-car (cons-stream x y))} &=& \mbox{x} \\ \mbox{(stream-cdr (cons-stream x y))} &=& \mbox{y} \end{eqnarray*} There is a distinguishable object, the-empty-stream, which cannot be the result of any cons-stream operation, and which can be identified with the predicate stream-null?.[2]

Thus we can make and use streams, in just the same way as we can make and use lists, to represent aggregate data arranged in a sequence. In particular, we can build stream analogs of the list operations from chapter 2, such as list-ref, map, and for-each:[3] (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)))))

Stream-for-each is useful for viewing streams: (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 2.1.2, 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 cdr of the pair we will put there a promise to compute the rest if it is ever requested. Stream-car and stream-cdr can now be defined as procedures: (define (stream-car stream) (car stream)) (define (stream-cdr stream) (force (cdr stream)))

Stream-car selects the car of the pair; stream-cdr selects the cdr of the pair and evaluates the delayed expression found there to obtain the rest of the stream.[4]

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 2.2.3): (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 stream-enumerate-interval, formed by the cons-stream, is[5] (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 2.2.3): (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))))) Stream-filter tests the stream-car of the stream (the car of the pair, which is 10,000). Since this is not prime, stream-filter examines the stream-cdr of its input stream. The call to stream-cdr forces evaluation of the delayed stream-enumerate-interval, which now returns (cons 10001 (delay (stream-enumerate-interval 10002 1000000))) Stream-filter now looks at the stream-car of this stream, 10,001, sees that this is not prime either, forces another stream-cdr, and so on, until stream-enumerate-interval yields the prime 10,007, whereupon stream-filter, according to its definition, returns (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 stream-cdr in our original expression. This forces the delayed stream-filter, which in turn keeps forcing the delayed stream-enumerate-interval until it finds the next prime, which is 10,009. Finally, the result passed to stream-car in our original expression is (cons 10009 (delay (stream-filter prime? (cons 10010 (delay (stream-enumerate-interval 10011 1000000)))))) Stream-car returns 10,009, and the computation is complete. Only as many integers were tested for primality as were necessary to find the second prime, and the interval was enumerated only as far as was necessary to feed the prime filter.

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)

Force simply calls the procedure (of no arguments) produced by delay, so we can implement force as a procedure: (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 3.60.) 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 3.27. 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))))

Delay is then defined so that (delay exp) is equivalent to (memo-proc (lambda () exp)) and force is as defined previously.[6]

To accomplish this, we will construct streams using pairs, with the first item of the stream in the head of the pair. However, rather than placing the value of the rest of the stream into the tail of the pair, we will put there a promise to compute the rest if it is ever requested. If we have a data item h and a stream t, we construct a stream whose head is h and whose tail is t by evaluating pair(h, () => t)—the tail t of a stream is wrapped in a function of no arguments, so that its evaluation will be delayed. The empty stream is null, the same as the empty list.

To access the first data item of a nonempty stream, we simply select the head of the pair, as with a list. But to access the tail of a stream, we need to evaluate the delayed expression. For convenience, we define function stream_tail(stream) { return tail(stream)(); } This selects the tail of the pair and applies the function found there to obtain the next pair of the stream (or null if the tail of the stream is empty)—in effect, forcing the function in the tail of the pair to fulfill its promise.

We can make and use streams, in just the same way as we can make and use lists, to represent aggregate data arranged in a sequence. In particular, we can build stream analogs of the list operations from chapter 2, such as list_ref, map, and for_each:[8] function stream_ref(s, n) { return n === 0 ? head(s) : stream_ref(stream_tail(s), n - 1); } function stream_map(f, s) { return is_null(s) ? null : pair(f(head(s)), () => stream_map(f, stream_tail(s))); } function stream_for_each(fun, s) { if (is_null(s)) { return true; } else { fun(head(s)); return stream_for_each(fun, stream_tail(s)); } } The function stream_for_each is useful for viewing streams: function display_stream(s) { return stream_for_each(display, s); }

To make the stream implementation automatically and transparently interleave the construction of a stream with its use, we have arranged for the tail of a stream to be evaluated when it is accessed by the stream_tail function rather than when the stream is constructed by pair. This implementation choice is reminiscent of our discussion of rational numbers in section 2.1.2, 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 head and the tail are evaluated at construction time. With streams, the tail is evaluated at selection time.

Streams in action

To see how this data structure behaves, let us analyze the outrageous prime computation we saw above, reformulated in terms of streams: head(stream_tail(stream_filter( is_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. The function stream_enumerate_interval is the stream analog of enumerate_interval (section 2.2.3): function stream_enumerate_interval(low, high) { return low > high ? null : pair(low, () => stream_enumerate_interval(low + 1, high)); } and thus the result returned by stream_enumerate_interval, formed by the pair, is[9] pair(10000, () => stream_enumerate_interval(10001, 1000000)); That is, stream_enumerate_interval returns a stream represented as a pair whose head is 10,000 and whose tail 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 function (section 2.2.3): function stream_filter(pred, stream) { return is_null(stream) ? null : pred(head(stream)) ? pair(head(stream), () => stream_filter(pred, stream_tail(stream))) : stream_filter(pred, stream_tail(stream)); } The function stream_filter tests the head of the stream (which is 10,000). Since this is not prime, stream_filter examines the tail of its input stream. The call to stream_tail forces evaluation of the delayed stream_enumerate_interval, which now returns pair(10001, () => stream_enumerate_interval(10002, 1000000)); The function stream_filter now looks at the head of this stream, 10,001, sees that this is not prime either, forces another stream_tail, and so on, until stream_enumerate_interval yields the prime 10,007, whereupon stream_filter, according to its definition, returns pair(head(stream), () => stream_filter(pred, stream_tail(stream))); which in this case is pair(10007, () => stream_filter( is_prime, pair(10008, () => stream_enumerate_interval(10009, 1000000)))); This result is now passed to stream_tail in our original expression. This forces the delayed stream_filter, which in turn keeps forcing the delayed stream_enumerate_interval until it finds the next prime, which is 10,009. Finally, the result passed to head in our original expression is pair(10009, () => stream_filter( is_prime, pair(10010, () => stream_enumerate_interval(10011, 1000000)))); The function head returns 10,009, and the computation is complete. Only as many integers were tested for primality as were necessary to find the second prime, and the interval was enumerated only as far as was necessary to feed the prime filter.

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 functions. We write functions as if the streams existed all at once when, in reality, the computation is performed incrementally, as in traditional programming styles.

An optimization

When we construct stream pairs, we delay the evaluation of their tail expressions by wrapping these expressions in a function. We force their evaluation when needed, by applying the function.

This implementation suffices for streams to work as advertised, but there is an important optimization that we shall consider where needed. 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 3.60.) 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 the construction of stream pairs as a memoized function similar to the one described in exercise 3.27. One way to accomplish this is to use the following function, which takes as argument a function (of no arguments) and returns a memoized version of the function. The first time the memoized function is run, it saves the computed result. On subsequent evaluations, it simply returns the result.[10] function memo(fun) { let already_run = false; let result = undefined; return () => { if (!already_run) { result = fun(); already_run = true; return result; } else { return result; } }; }

We can make use of memo whenever we construct a stream pair. For example, instead of function stream_map(f, s) { return is_null(s) ? null : pair(f(head(s)), () => stream_map(f, stream_tail(s))); } we can define an optimized function stream_map as follows: function stream_map_optimized(f, s) { return is_null(s) ? null : pair(f(head(s)), memo(() => stream_map_optimized(f, stream_tail(s)))); }