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.

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

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 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.

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)].

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.