As we saw in section 2.2.3, 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:[1]
Original  JavaScript 
(define (sumprimes 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))  function sum_primes(a, b) { function iter(count, accum) { return count > b ? accum : is_prime(count) ? iter(count + 1, count + accum) : iter(count + 1, accum); } return iter(a, 0); } 
Original  JavaScript 
(define (sumprimes a b) (accumulate + 0 (filter prime? (enumerateinterval a b))))  function sum_primes(a, b) { return accumulate((x, y) => x + y, 0, filter(is_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 enumerateinterval 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
Original  JavaScript 
(car (cdr (filter prime? (enumerateinterval 10000 1000000))))  head(tail(filter(is_prime, enumerate_interval(10000, 1000000)))); 
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.
Original  JavaScript  
On the surface, streams are just lists with different names for the procedures that manipulate them. There is a constructor, consstream, and two selectors, streamcar and streamcdr, which satisfy the constraints \begin{eqnarray*} \mbox{(streamcar (consstream x y))} &=& \mbox{x} \\ \mbox{(streamcdr (consstream x y))} &=& \mbox{y} \end{eqnarray*} There is a distinguishable object, theemptystream, which cannot be the result of any consstream operation, and which can be identified with the predicate streamnull?.[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 listref, map, and foreach:[3] (define (streamref s n) (if (= n 0) (streamcar s) (streamref (streamcdr s) ( n 1)))) (define (streammap proc s) (if (streamnull? s) theemptystream (consstream (proc (streamcar s)) (streammap proc (streamcdr s))))) (define (streamforeach proc s) (if (streamnull? s) 'done (begin (proc (streamcar s)) (streamforeach proc (streamcdr s))))) Streamforeach is useful for viewing streams: (define (displaystream s) (streamforeach displayline s)) (define (displayline 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 streamcdr procedure rather than when the stream is constructed by consstream. 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 rationalnumber 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 socalled
delayed object, which we can think of as a
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. Streamcar and streamcdr can now be defined as procedures: (define (streamcar stream) (car stream)) (define (streamcdr stream) (force (cdr stream))) Streamcar selects the car of the pair; streamcdr selects the cdr of the pair and evaluates the delayed expression found there to obtain the rest of the stream.[4]
To see how this implementation behaves, let us analyze the
We begin by calling streamenumerateinterval with the arguments 10,000 and 1,000,000. Streamenumerateinterval is the stream analog of enumerateinterval (section 2.2.3): (define (streamenumerateinterval low high) (if (> low high) theemptystream (consstream low (streamenumerateinterval (+ low 1) high)))) and thus the result returned by streamenumerateinterval, formed by the consstream, is[5] (cons 10000 (delay (streamenumerateinterval 10001 1000000))) That is, streamenumerateinterval 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 (streamfilter pred stream) (cond ((streamnull? stream) theemptystream) ((pred (streamcar stream)) (consstream (streamcar stream) (streamfilter pred (streamcdr stream)))) (else (streamfilter pred (streamcdr stream))))) Streamfilter tests the streamcar of the stream (the car of the pair, which is 10,000). Since this is not prime, streamfilter examines the streamcdr of its input stream. The call to streamcdr forces evaluation of the delayed streamenumerateinterval, which now returns (cons 10001 (delay (streamenumerateinterval 10002 1000000))) Streamfilter now looks at the streamcar of this stream, 10,001, sees that this is not prime either, forces another streamcdr, and so on, until streamenumerateinterval yields the prime 10,007, whereupon streamfilter, according to its definition, returns (consstream (streamcar stream) (streamfilter pred (streamcdr stream))) which in this case is (cons 10007 (delay (streamfilter prime? (cons 10008 (delay (streamenumerateinterval 10009 1000000)))))) This result is now passed to streamcdr in our original expression. This forces the delayed streamfilter, which in turn keeps forcing the delayed streamenumerateinterval until it finds the next prime, which is 10,009. Finally, the result passed to streamcar in our original expression is (cons 10009 (delay (streamfilter prime? (cons 10010 (delay (streamenumerateinterval 10011 1000000)))))) Streamcar 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
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 delayedobject) (delayedobject)) 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 specialpurpose 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 (memoproc proc) (let ((alreadyrun? false) (result false)) (lambda () (if (not alreadyrun?) (begin (set! result (proc)) (set! alreadyrun? true) result) result)))) Delay is then defined so that (delay exp) is equivalent to (memoproc (lambda () exp)) and force is as defined previously.[6] There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

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 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 rationalnumber 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.
To see how this data structure behaves, let us analyze the
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
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)))); } There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
