We have seen how to support the illusion of manipulating streams as complete entities even though, in actuality, we compute only as much of the stream as we need to access. We can exploit this technique to represent sequences efficiently as streams, even if the sequences are very long. What is more striking, we can use streams to represent sequences that are infinitely long. For instance, consider the following definition of the stream of positive integers:
function integers_starting_from(n) { return pair(n, () => integers_starting_from(n + 1) ); }
This makes sense because integers will be a pair whose head is 1 and whose tail is a promise to produce the integers beginning with 2. This is an infinitely long stream, but in any given time we can examine only a finite portion of it. Thus, our programs will never know that the entire infinite stream is not there.
Using integers we can define other infinite streams, such as the stream of integers that are not divisible by 7:
function is_divisible(x, y) { return x % y === 0; } const no_sevens = stream_filter(x => ! is_divisible(x, 7), integers);
Then we can find integers not divisible by 7 simply by accessing elements of this stream:
stream_ref(no_sevens, 100);
In analogy with integers, we can define the infinite stream of Fibonacci numbers:
function fibgen(a, b) { return pair(a, () => fibgen(b, a + b)); } const fibs = fibgen(0, 1);
The function fibs is a pair whose head is 0 and whose tail is a promise to evaluate fibgen(1, 1). When we evaluate this delayed fibgen(1, 1), it will produce a pair whose head is 1 and whose tail is a promise to evaluate fibgen(1, 2), and so on.
For a look at a more exciting infinite stream, we can generalize the no_sevens example to construct the infinite stream of prime numbers, using a method known as the sieve of Eratosthenes.[1] We start with the integers beginning with 2, which is the first prime. To get the rest of the primes, we start by filtering the multiples of 2 from the rest of the integers. This leaves a stream beginning with 3, which is the next prime. Now we filter the multiples of 3 from the rest of this stream. This leaves a stream beginning with 5, which is the next prime, and so on. In other words, we construct the primes by a sieving process, described as follows: To sieve a stream S, form a stream whose first element is the first element of S and the rest of which is obtained by filtering all multiples of the first element of S out of the rest of S and sieving the result. This process is readily described in terms of stream operations:
function sieve(stream) { return pair(head(stream), () => sieve(stream_filter( x => !is_divisible(x, head(stream)), stream_tail(stream) ) ) ); }
It is interesting to contemplate the signal-processing system set up
by sieve, shown in the
Henderson diagram
in
Figure 3.31.[2]
The input stream feeds into an
unpairer
that separates the first element of the stream from the
rest of the stream.
The first element is used to construct a divisibility filter, through
which the rest is passed, and the output of the filter is fed to
another sieve box. Then the original first element is paired onto the
output of the internal sieve to form the output stream. Thus, not
only is the stream infinite, but the signal processor is also
infinite, because the sieve contains a sieve within it.
The integers and fibs
streams above were defined by specifying generating
functions
that explicitly compute the
stream elements one by one. An alternative way to specify streams is
to take advantage of delayed evaluation to define streams implicitly.
For example, the following expression defines the stream
ones to be an infinite stream of ones:
const ones = pair(1, () => ones);
This works much like the definition of a recursive function: ones is a pair whose head is 1 and whose tail is a promise to evaluate ones. Evaluating the tail gives us again a 1 and a promise to evaluate ones, and so on.
We can do more interesting things by manipulating streams with operations such as add_streams, which produces the elementwise sum of two given streams:[3]
function add_streams(s1, s2) { return stream_combine((x1, x2) => x1 + x2, s1, s2); }
Now we can define the integers as follows:
const integers = pair(1, () => add_streams(ones, integers));
This defines integers to be a stream whose first element is 1 and the rest of which is the sum of ones and integers. Thus, the second element of integers is 1 plus the first element of integers, or 2; the third element of integers is 1 plus the second element of integers, or 3; and so on. This definition works because, at any point, enough of the integers stream has been generated so that we can feed it back into the definition to produce the next integer.
We can define the Fibonacci numbers in the same style:
const fibs = pair(0, () => pair(1, () => add_streams(stream_tail(fibs), fibs) ) );
This definition says that fibs is a stream beginning with 0 and 1, such that the rest of the stream can be generated by adding fibs to itself shifted by one place:
The function scale_stream is also useful in formulating such stream definitions. This multiplies each item in a stream by a given constant:
function scale_stream(stream, factor) { return stream_map(x => x * factor, stream); }
For example,
const double = pair(1, () => scale_stream(double, 2));
An alternate definition of the stream of primes can be given by starting with the integers and filtering them by testing for primality. We will need the first prime, 2, to get started:
const primes = pair(2, () => stream_filter( is_prime, integers_starting_from(3)) );
This definition is not so straightforward as it appears, because we will test whether a number $n$ is prime by checking whether $n$ is divisible by a prime (not by just any integer) less than or equal to $\sqrt{n}$:
function is_prime(n) { function iter(ps) { return square(head(ps)) > n ? true : is_divisible(n, head(ps)) ? false : iter(stream_tail(ps)); } return iter(primes); }
This is a recursive definition, since primes is defined in terms of the is_prime predicate, which itself uses the primes stream. The reason this function works is that, at any point, enough of the primes stream has been generated to test the primality of the numbers we need to check next. That is, for every $n$ we test for primality, either $n$ is not prime (in which case there is a prime already generated that divides it) or $n$ is prime (in which case there is a prime already generated—i.e., a prime less than $n$—that is greater than $\sqrt{n}$).[4]
const s = pair(1, () => add_streams(s, s));
// mul_streams to be written by students const factorials = pair(1, () => mul_streams(???, ???));
function merge(s1, s2) { if (is_null(s1)) { return s2; } else if (is_null(s2)) { return s1; } else { const s1head = head(s1); const s2head = head(s2); if (s1head < s2head) { return pair(s1head, () => merge(stream_tail(s1), s2) ); } else if (s1head > s2head) { return pair(s2head, () => merge(s1, stream_tail(s2)) ); } else { return pair(s1head, () => merge(stream_tail(s1), stream_tail(s2)); } } }
const S = pair(1, () => merge(??, ??));
function expand(num, den, radix) { return pair(quotient(num * radix, den), expand((num * radix) % den, den, radix)); }
const exp_series = pair(1, () => integrate_series(exp_series));
const cosine_series = pair(1, ??); const sine_series = pair(0, ??);
function mul_series(s1, s2) { pair(??, add_streams(??, ??)); }
sievesthat, until the 1970s, were the most powerful tools in existence for locating large primes. Since then, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1.2.6.