Series vs. streams

A generator is an abstraction of a sequence of values. It is a procedure that returns the next value in the sequence each time it is invoked. The generator can run out of items to return at some point if the sequence is finite, or it can keep generating values if the sequence is ininite.

A generator is decidely non-functional. Each time it is called it has the potential to return a different value. But let's make it functional. Instead of returning a single value, let's return two values: the next value in the sequence and the next state of the generator. The generator can now be pure functional and return the exact same two values each time. The caller will keep track of the current generator will replace the current generator with the next one returned by the call.

We implement generators as a promise that returns a pair of the next value and the next generator. The returned pair is what S&ICP call a stream. In other words, a stream is output of a functional generator that is 180 degrees out of phase of the generator.

Streams are similar to series in that you can write computations that operate on the aggregate stream, but it will be piplined to operate one element at time. But rather than having the compiler perform a code walk to set up an explicit pipeline, the runtime system sets up an implicit pipeline through the constraints of the promises. This makes streams a bit more flexible than series.

Series are more efficient than streams because the compiler can turn the implicit pipeline into an explicit one that is easy to optimize. Streams turn into a series of nested lexical closures with the attendant overhead.

One of the difficulties in using streams is that you often have to pay very careful attention to avoid fencepost errors and generating elements one beyond what is necessary. This isn't just a matter of using up a tad more storage, but it can lead to unexpected infinite loops because you attempt to reach one beyond the base case. Very often you find that you need two versions of each function: one that takes a stream argument, and one that takes a generator argument that you are careful to avoid calling unless necessary.

Streams are lazy by nature. Laziness introduces a need for static types. If you have a computed value, you can examine it to find out its type, but if you have a promise, you cannot tell what type of object it will return without forcing the promise. You cannot do a type dispatch on a promise because you don't know what it will return. A static type would indicate the type of the returned value without forcing the promise.

Series requires that the entire pipeline from source to sink be visible to the compiler. Streams do not have this requirement.

Despite their drawbacks, I rather like streams. I use them in my linear-fractional-transformations package to represent exact real numbers as streams of linear fractional transformations. I also use streams of integers to represent the continued fraction expansion of exact real numbers.