5/5.1 Streams. Streams Are Delayed Lists

Is there a alternative approach to assignment when it comes to modeling state? Think of the way a mathematical function of time x(t) describes the time-varying behavior of a quantity x. In a certain sense, it describes the history of values. Streams, the new data structure introduced in this section, allow us to ``model change in terms of sequences that represent the time histories of the systems being modeled.'' So, yes. Systems with state can be modeled without ever using assignment (or mutable data). Assignment's drawbacks are sidestepped, but new challenges show up.

Streams Are Delayed Lists

Sequences have proven themselves useful for formulating powerful abstractions (think of map, filter, etc.). However, representing sequences as lists means buying elegance at the price of (space and time) inefficiency. Think of how outrageously inefficient the following operation is¹:

(car (cdr (filter prime? (enumerate-interval 10000 1000000))))

As far as I understand, stream are just a different, more efficient, implementation of sequences. This means we can get elegance without inefficiency. The trick is ``delayed evaluation''; a streams construct itself only when somebody needs it. Construction and use are interleaved. ``On the surface, streams are just lists with different names for the procedures that manipulate them.'' (319)

Exercise 3.50

Exercise:

Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2-2-3, footnote 12.

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

Answer:

As far as I can see, Authors haven't shown the implementation of the map procedure presented in the footnote 12. Let's implement that first. I will call it map*.

(define (map* proc . args)
  (if (null? (car args))
      nil
      (cons
       (apply proc (map car args))
       (apply map* (cons proc (map cdr args))))))

Here is the stream version:

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

Exercise 3.51

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?(7)
(define x (stream-map show (stream-enumerate-interval 0 10)))

(stream-ref x 5)

(stream-ref x 7)

Answer:

;; relevant code
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

(define (show x)
  (display-line x)
  x)

(define (display-line x)
  (newline)
  (display x))

(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-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream low
                   (stream-enumerate-interval (+ low 1) high))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (- n 1) (stream-cdr s))))

Executing (define x (stream-map show (stream-enumerate-interval 0 10))) only prints 0.

First, (stream-enumerate-interval 0 10) evaluates to a list (stream) whose car is 0 and whose cdr is a promise:

(0 . #<promise>)

Then we apply stream-map to show and to that list (stream) (0 . #<promise>).

stream-map evaluates to a list whose cdr is a promise; its car is (show (stream-car (0 . #<promise>))). This latter expression evaluates to 0, but it also has the side effect of printing a new line and 0.

So, when evaluating (define x (stream-map show (stream-enumerate-interval 0 10))), the interpreter prints 0.

When we evaluate (stream-ref x 5), stream-cdr is repeatedly called and the stream is consumed until the value 5 is found. Therefore, we print all the numbers from 1 to 5 (and the whole expression evaluates to 5).

←

Footnotes:

See p. 318 for another, less outrageous, example.