streams.md

Streams

Definition: Important to keep in mind! Will help you reason about streams and guide you when you get confused.

Wishful thinking: Useful strategy for thinking about recursion and infinite things. Basically you assume that the function you are writing already has a correct implementation, and you use that assumption to write its recursive case. Keeping the return type of the function in mind can help.

Infinity: Streams can be finite or infinite.

Some functions can only deal with finite streams, for example stream_length and stream_append (first argument should be finite). They need to evaluate an entire stream to have an effect.

Others, like stream_ref, only need to evaluate a stream up till a certain point to produce a value. Yet others, like stream_map and stream_filter, are lazy (as opposed to eager/strict): they don't evaluate the stream at all to return a result, so their effects will only kick in when the stream is actually evaluated. Both of these types of functions can handle infinite streams.

Imperative (how) vs declarative (what):

// Declarative
var repeating = pair(1, function() {
    return pair(2, function() {
        return pair(3, function() {
            return repeating;
        });
    });
});

// Imperative
function repeating_stream (from, to, current) {
    return pair(current, function () {
        if (current === to) {
            return repeating_stream(from, to, from);
        } else {
            return repeating_stream(from, to, current + 1);
        }
    });
}
var repeating = repeating_stream(1, 3, 1);

• The declarative way is usually shorter and more elegant but is all about wishful thinking.
• The imperative way, however, is formulaic and dependable. The function that you use to create your stream can be parameterised by anything, which helps you maintain state across the elements of your stream.

Laziness: We've seen laziness at three levels: in data structures, in functions, and in programming languages.

Streams are lazy data structures. The laziness is a consequence of how they are defined. We may have lazy trees, lazy queues, etc.

Functions like stream_map and stream_filter are lazy. Notice how stream_map has O(1) time complexity -- no work is actually done when it returns. The work is deferred til the stream is evaluated.

Finally, there is laziness at the language level. JediScript is not a lazy language: arguments are evaluated before functions are called, and we must express laziness explicitly, using special data structures or functions (previous two points). stream_append_pickle can be thought of as a workaround for this lack of laziness.

Memoizing streams: The tail of a stream is a thunk (a deferred computation, represented in JediScript by a function of no arguments). When these computations are expensive to perform (for example, the sieve of Erastosthenes gets more and more expensive the more elements are evaluated), we might want to replace the thunk in the tail with another thunk that just returns whatever the original would have, trading time for space complexity. The computation performed by the stream must be pure for this to compute the right result.