Streams

In Python, we can use iterators to represent infinite sequences (for example, the generator for all natural numbers). However, Scheme does not support iterators.

Let’s see what happens when we try to use a Scheme list to represent an infinite sequence of natural numbers:

scm> (define (naturals n) 
       (cons n (naturals (+ n 1))))
naturals
scm> (naturals 0)
Error: maximum recursion depth exceeded

Because cons is a regular procedure and both its operands must be evaluted before the pair is constructed, we cannot create an infinite sequence of integers using a Scheme list. Instead, our Scheme interpreter supports streams, which are lazy Scheme lists. The first element is represented explicitly, but the rest of the stream’s elements are computed only when needed. Computing a value only when it’s needed is also known as lazy evaluation.

scm> (define (naturals n)
       (cons-stream n (naturals (+ n 1))))
naturals
scm> (define nat (naturals 0))
nat
scm> (car nat)
0
scm> (cdr nat)
#[promise (not forced)]
scm> (car (cdr-stream nat))
1
scm> (car (cdr-stream (cdr-stream nat)))
2

We use the special form cons-stream to create a stream:

(cons-stream <operand1> <operand2>)

cons-stream is a special form because the second operand is not evaluated when evaluating the expression. To evaluate this expression, Scheme does the following:

  1. Evaluate the first operand.
  2. Construct a promise containing the second operand.
  3. Return a pair containing the value of the first operand and the promise.

To actually get the rest of the stream, we must call cdr-stream on it to force the promise to be evaluated. Note that this argument is only evaluated once and is then stored in the promise; subsequent calls to cdr-stream returns the value without recomputing it. This allows us to efficiently work with infinite streams like the naturals example above. We can see this in action by using a non-pure function to compute the rest of the stream:

scm> (define (compute-rest n)
       (print 'evaluating!)
       (cons-stream n nil))
compute-rest
scm> (define s (cons-stream 0 (compute-rest 1)))
s
scm> (car (cdr-stream s))
evaluating!
1
scm> (car (cdr-stream s))
1

Here, the expression (compute-rest 1) is only evaluated the first time cdr-stream is called, so the symbol evaluating! is only printed the first time.

When displaying a stream, the first element of the stream and the promise are displayed separated by a dot (this indicates that they are part of the same pair, with the promise as the cdr). If the value in the promise has not been evaluated by calling cdr-stream, we consider it to be not forced. Otherwise, we consider it forced.

scm> (define s (cons-stream 1 nil))
s
scm> s
(1 . #[promise (not forced)])
scm> (cdr-stream s) ; nil
()
scm> s
(1 . #[promise (forced)])

Streams are very similar to Scheme lists in that they are also recursive structures. Just like the cdr of a Scheme list is either another Scheme list or nil, the cdr-stream of a stream is either a stream or nil. The difference is that whereas both arguments to cons are evaluated upon calling cons, the second argument to cons-stream isn’t evaluated until the first time that cdr-stream is called.

Here’s a summary of what we just went over:

  • nil is the empty stream
  • cons-stream constructs a stream containing the value of the first operand and a promise to evaluate the second operand
  • car returns the first element of the stream
  • cdr-stream computes and returns the rest of stream