Streams Quick Review

Stream = Sequence of values (can be infinite) with a car and a cdr (just like lists), but where each value is not computed until it is forced to be computed. We always define a stream using the cons-stream function.

Lazy computation

Each value isn’t computed until it’s forced? What does that mean? Well, streams use what’s called lazy computation or lazy evaluation, which means that when a stream is defined, its car is some value, but its cdr is what’s called a promise. That means that, unlike lists, we don’t actually know what all of the values in the stream are until we force them (which I’ll explain how to do in a bit). The cool thing about this is it means that streams can actually be infinite, since at a stream’s definition, we don’t need to know all of the values inside of it.

Now let’s talk about how to force a value in a stream. We can always do that by using the cdr-stream function. Calling (cdr-stream some-stream) will force the second value in our stream, calling (cdr-stream (cdr-stream some-stream)) will force the third value in our stream, and so on. Once a value in the stream has been forced, its value is set forever, and any subsequent (cdr-stream some-stream) calls will produce the same value.

Now let’s look at an example to make it a bit more clear.

> (define (f x) (+ x 1))
> (define n (cons-stream (f 1) n))
> (car n)

The car of n is (f 1), which will give us 1 + 1, which is 2.

> (cdr n)

Now hang on, I mentioned what cdr-stream does on a stream, but not what cdr does. The key thing to remember here is that the cdr of a stream is always a promise, and a promise can either be forced, or not forced. So basically, if we call (cdr some-stream), we will either get #[promise (not forced)] or #[promise (forced)]. In this case, we have not forced the second value of our stream, so we will get #[promise (not forced)].

> (cdr-stream n)

cdr-stream will force the next value in the stream. Now the next value in our stream n is actually n, which we defined to be (cons-stream (f 1) n). This means that we can write out n as (cons-stream (f 1) (cons-stream (f 1) n)), so the next value that we need to calculate in our stream is (f 1) again, which we know is 2.

> (cdr n)
> (cdr (cdr n))

We’ve now forced the next value in our stream, so cdr of n will now give us #[promise (forced)]. However, we haven’t forced the third value in our stream, so (cdr (cdr n)) is still #[promise (not forced)].

> (define (f x) (+ x 2))
> (cdr-stream n)

Okay, so we’ve redefined f, and (cdr-stream n) requires us to calculate (f 1) right? So should we use the new f or the old f? This is a trick question! Like I said earlier, once we have forced a promise and calculated a value, we will NEVER recalculate it. So the answer is still 2.