index

Streams

3.5
  • We’ve used assignment as a powerful tool and dealt with some of the complex problems it raises.
  • Now we will consider another approach to modeling state, using data structures called streams.
  • We want to avoid identifying time in the computer with time in the modeled world.
  • If xx is a function of time x(t)x(t), we can think of the identify xx as a history of values (and these don’t change).
  • With time measured in discrete steps, we can model a time function as a sequence of values.
  • Stream processing allows us to model state without assignments.

Streams Are Delayed Lists

  • If we represent streams as lists, we get elegance at the price of severe inefficiency (time and space).
  • Consider adding all the primes in an interval. Using filter and reduce, we waste a lot of space storing lists.
  • Streams are lazy lists. They are the clever idea of using sequence manipulations without incurring the cost.
  • We only construct an item of the stream when it is needed.
  • We have cons-stream, stream-car, stream-cdr, the-empty-stream, and stream-null?.
  • The cons-stream procedure must not evaluate its second argument until it is accessed by stream-cdr.
  • To implement streams, we will use promises. (delay exp) does not evaluate the argument but returns a promise. (force promise) evaluates a promise and returns the value.
  • (cons-stream a b) is a special form equivalent to (cons a (delay b)).

The stream implementation in action

In general, we can think of delayed evaluation as “demand-driven” programming, we herby each stage in the stream process is activated only enough to satisfy the next stage.

Implementing delay and force

  • Promises are quite straightforward to implement.
  • (delay exp) is syntactic sugar for (lambda () exp).
  • force simply calls the procedure. We can optimize it by saving the result and not calling the procedure a second time.
  • The promise stored in the cdr of the stream is also known as a thunk.

Exercises: 3.50 3.51 3.52

Infinite Streams

  • With lazy sequences, we can manipulate infinitely long streams!
  • We can define Fibonacci sequence explicitly with a generator:
(define (fibgen a b) (cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
  • As long as we don’t try to display the whole sequence, we will never get stuck in an infinite loop.
  • We can also create an infinite stream of primes.

Defining streams implicitly

  • Instead of using a generator procedure, we can define infinite streams implicitly, taking advantage of the laziness.
(define fibs
  (cons-stream
   0
   (cons-stream 1 (stream-map + fibs (stream-cdr fibs)))))
(define pot
  (cons-stream 1 (stream-map (lambda (x) (* x 2)) pot)))
  • This implicit technique is known as corecursion. Recursion works backward towards a base case, but corecursion works from the base and creates more data in terms of itself.

Exercises: 3.53 3.54 3.55 3.56 3.57 3.58 3.59 3.60 3.61 3.62

Exploiting the Stream Paradigm

  • Streams can provide many of the benefits of local state and assignment while avoiding some of the theoretical tangles.
  • Using streams allows us to have different module boundaries.
  • We can focus on the whole stream/series/signal rather than on individual values.

Formulating iterations as stream processes

  • Before, we made iterative processes by updating state variables in recursive calls.
  • To compute the square root, we improved a guess until the values didn’t change very much.
  • We can make a stream that converges on the square root of x, and a stream to approximate π\pi.
  • One neat thing we can do with these streams is use sequence accelerators, such as Euler’s transform.

Exercises: 3.63 3.64 3.65

Infinite streams of pairs

  • Previously, we handled traditional nested loops as processes defined on sequences of pairs.
  • We can find all pairs (i,j)(i,j)