3.5 - Streams

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

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

;; -------------------------------------------------------------------
;; Exercise 3.50
;; -------------------------------------------------------------------

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

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)

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 `sum' after each of the above expressions is evaluated? What is the printed response to evaluating the `stream-ref' and `display-stream' expressions? Would these responses differ if we had implemented `(delay <EXP>)' simply as `(lambda () <EXP>)' without using the optimization provided by `memo-proc'? Explain

1 ]=> sum
;Value: 210

1 ]=> (stream-head y 10)

;Value 18: (210 204 200 182 174 144 132 90 74 20)

1 ]=> (display-stream z)

210
200
195
165
155
105
90
20
;Value: done

After the definition of seq, sum is equal to 210. It remains at 210 through the remainder of the operations.This would not be the case if delay were not memoized, as without being so it would be recalculated each time the items in the node were resolved, adding to the value of sum each time, and changing the results captured by y and z.

Without running the program, describe the elements of the stream defined by

(define s (cons-stream 1 (add-streams s s)))

\[ \sum_{i=1}^\infty 2^i \]

Define a procedure `mul-streams', analogous to `add-streams', that produces the elementwise product of its two input streams. Use this together with the stream of `integers' to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:

(define factorials (cons-stream 1 (mul-streams <??> <??>)))

(define (mul-streams s1 s2)
  (stream-map * s1 s2))

(define factorials (cons-stream 1 (mul-streams (add-streams ones integers) factorials)))

Define a procedure `partial-sums' that takes as argument a stream S and returns the stream whose elements are S_0, S_0 + S_1, S_0 + S_1 + S_2, …. For example, `(partial-sums integers)' should be the stream 1, 3, 6, 10, 15, ….

We can model a changing quantity, such as the local state of some object, using a stream that represents the time history of successive states. In essence, we represent time explicitly, using streams, so that we decouple time in our simulated world from the sequence of events that take place during evaluation.

Events over time can be merged / serialized (deterministically?) into a stream of events.

This is precisely the same constraint that we had to deal with in 3.4.1, where we found the need to introduce explicit synchronization to ensure a “correct” order of events in concurrent processing of objects with state. Thus, in an attempt to support the functional style, the need to merge inputs from different agents reintroduces the same problems that the functional style was meant to eliminate.

With a working merge solution, a system can be designed in a functional way, operating on a stream of state and inputs.

The Erlang/OTP generic server, generic fsm and other behaviours are implemented in such a way that input streams received concurrently are merged by the vm and combined with the state of the process as a single stream pairing the current state with the next input to process, allowing an Erlang developer to build a functional interface with the complexities of concurrency abstracted away.