Permalink copied!
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));
}
const integers = integers_starting_from(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);
117
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 constant 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))));
}
const primes = sieve(integers_starting_from(2));
Now to find a particular prime we need only ask for it:
stream_ref(primes, 50);
233
It is interesting to contemplate the signal-processing system set up
by sieve, shown in the
[2]
Henderson diagramin figure 3.56.
The input stream feeds into an
unpairerthat 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 adjoined to 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.
Figure 3.56
The prime sieve viewed as a signal-processing system.
Each solid line represents a
stream of values being transmitted. The dashed line from the
head
to the
pair
and the filter indicates that this is a single
value rather than a stream.
The integers and
fibs streams above were defined by specifying
generatingfunctions 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 statement defines the stream ones to be an infinite stream of ones:
const ones = pair(1, () => ones);
This works much like the declaration 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_map_2((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:
\[
\begin{array}{ccccccccccccl}
& & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & \ldots & = & \texttt{stream}\mathtt{\_}\texttt{tail(fibs)} \\
& & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & \ldots & = & \texttt{fibs} \\ \hline
0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & \ldots & = & \texttt{fibs}
\end{array}
\]
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));
produces the stream of powers of 2:
$1, 2, 4, 8, 16, 32,$ ….
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]
Without running the program, describe the elements of the
stream defined by
const s = pair(1, () => add_streams(s, s));
This program defines s to be a stream whose
first element is 1 and each next element is the double of the stream's previous
element. The elements of s are therefore
1, 2, 4, 8, 16,... .
Define a
function
mul_streams,
analogous to
add_streams,
that produces the elementwise product of its two input streams. Use this
together with the stream of integers to
complete the following definition of the stream whose
$n$th element (counting from 0) is
$n+1$ factorial:
const factorials = pair(1, () => mul_streams($\langle{}$??$\rangle$, $\langle{}$??$\rangle$));
const factorials = pair(1, () => mul_streams(factorials, integers));
Define a
function
partial_sums
that takes as argument a stream $S$ and returns
the stream whose elements are
$S_0, S_0+S_1, S_0+S_1+S_2,$ ….
For example,
partial_sums(integers)
should be the stream $1, 3, 6, 10, 15,\ldots$.
function partial_sums(s) {
return pair(head(s),
() => add_streams(stream_tail(s),
partial_sums(s)));
}
A famous problem, first raised by
R. Hamming, is to enumerate, in ascending order with no repetitions, all
positive integers with no prime factors other than 2, 3, or 5. One obvious
way to do this is to simply test each integer in turn to see whether it has
any factors other than 2, 3, and 5. But this is very inefficient, since, as
the integers get larger, fewer and fewer of them fit the requirement. As
an alternative, let us call the required stream of numbers
S and notice the following facts about it.
- S begins with 1.
- The elements of scale_stream(S, 2) are also elements of S.
- The same is true for scale_stream(S, 3) and scale_stream(S, 5).
- These are all the elements of S.
Now all we have to do is combine elements from these sources. For this we
define a
function
merge that combines two ordered
streams into one ordered result stream, eliminating repetitions:
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);
return s1head < s2head
? pair(s1head, () => merge(stream_tail(s1), s2))
: s1head > s2head
? pair(s2head, () => merge(s1, stream_tail(s2)))
: pair(s1head, () => merge(stream_tail(s1), stream_tail(s2)));
}
}
Then the required stream may be constructed with
merge, as follows:
const S = pair(1, () => merge($\langle{}$??$\rangle$, $\langle{}$??$\rangle$));
Fill in the missing expressions in the places marked
$\langle{}$??$\rangle$ above.
const S = pair(1, () => merge(scale_stream(S, 2),
merge(scale_stream(S, 3),
scale_stream(S, 5))));
How many additions are performed when we compute the
$n$th Fibonacci number using the declaration of
fibs based on the
add_streams function?
Show that this number is exponentially greater than the number
of additions performed if
add_streams had used the function
stream_map_2_optimized
described in exercise 3.50.
[5]
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Give an interpretation of the stream computed by the
function
function expand(num, den, radix) {
return pair(math_trunc((num * radix) / den),
() => expand((num * radix) % den, den, radix));
}
where
math_trunc
discards the fractional part of its argument, here the remainder
of the division.
What are the successive elements produced by
expand(1, 7, 10)?
What is produced by
expand(3, 8, 10)?
This function will produce a infinite stream of numbers which represent the digits of
num / den
in base-radix
system.
expand(1, 7, 10)
will produce a infinite stream of numbers: 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7... While
expand(3, 8, 10)
will produce a stream of numbers: 3, 7, 5, 0, 0, 0, 0 ...
In section 2.5.3 we saw how to implement a
polynomial arithmetic system representing polynomials as lists of
terms. In a similar way, we can work with
power series, such as
\[
\begin{array}{rll}
e^{x} &=&
1+x+\dfrac{x^{2}}{2}+\dfrac{x^{3}}{3\cdot2}
+\dfrac{x^{4}}{4\cdot 3\cdot 2}+\cdots, \\[9pt]
\cos x &=& 1-\dfrac{x^{2}}{2}+\dfrac{x^{4}}{4\cdot 3\cdot 2}-\cdots, \\[9pt]
\sin x &=& x-\dfrac{x^{3}}{3\cdot 2}
+\dfrac{x^{5}}{5\cdot 4\cdot 3\cdot 2}- \cdots,
\end{array}
\]
represented as infinite streams.
We will represent the series
$a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$
as the stream whose elements are the coefficients
$a_0, a_1, a_2, a_3,$ ….
-
The integral of the series $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$ is the series \[ \begin{array}{l} c + a_0 x + \frac{1}{2}a_1 x^2 + \frac{1}{3}a_2 x^3 + \frac{1}{4}a_3 x^4 + \cdots \end{array} \] where $c$ is any constant. Define a function integrate_series that takes as input a stream $a_0, a_1, a_2,\ldots$ representing a power series and returns the stream $a_0, \frac{1}{2}a_1, \frac{1}{3}a_2,\ldots$ of coefficients of the nonconstant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate_series, we will use pair to adjoin the appropriate constant to the beginning of the stream.)
-
The function $x\mapsto e^x$ is its own derivative. This implies that $e^x$ and the integral of $e^x$ are the same series, except for the constant term, which is $e^0 = 1$. Accordingly, we can generate the series for $e^x$ as
const exp_series = pair(1, () => integrate_series(exp_series));
Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:const cosine_series = pair(1, $\langle{}$??$\rangle$); const sine_series = pair(0, $\langle{}$??$\rangle$);
function integrate_series(s) {
function helper(ss, iter) {
return pair(head(ss) / iter, () => helper(stream_tail(ss), iter + 1));
}
return helper(s, 1);
}
const cos_series = pair(1, () => integrate_series(
pair(0,
() => stream_map(
(x) => (-x),
integrate_series(cos_series)))));
const sin_series = pair(0, () => integrate_series(
pair(1,
() => integrate_series(
stream_map(x => -x, sin_series)
))
));
With
power series represented as streams of coefficients as in
exercise 3.59, adding series is implemented
by
add_streams.
Complete the declaration of
the following
function
for multiplying series:
function mul_series(s1, s2) {
pair($\langle{}$??$\rangle$, () => add_streams($\langle{}$??$\rangle$, $\langle{}$??$\rangle$));
}
You can test your
function
by verifying that $sin^2 x + cos^2 x = 1$,
using the series from exercise 3.59.
function mul_series(s1, s2) {
return pair(head(s1) * head(s2),
() => add_streams(
mul_series(stream_tail(s1), s2),
scale_stream(stream_tail(s2), head(s1))));
}
Let $S$ be a power series
(exercise 3.59)
whose constant term is 1. Suppose we want to find the power series
$1/S$, that is, the series
$X$ such that
$S\cdot X= 1$.
Write $S=1+S_R$ where
$S_R$ is the part of
$S$ after the constant term. Then we can solve
for $X$ as follows:
\[
\begin{array}{rll}
S \cdot X &=& 1 \\
(1+S_R)\cdot X &=& 1 \\
X + S_R \cdot X &=& 1 \\
X &=& 1 - S_R \cdot X
\end{array}
\]
In other words, $X$ is the power series whose
constant term is 1 and whose higher-order terms are given by the negative of
$S_R$ times $X$.
Use this idea to write a
function
invert_unit_series
that computes $1/S$ for a power series
$S$ with constant term 1. You will need to use
mul_series
from exercise 3.60.
function invert_unit_series(s) {
return pair(1, () => stream_map(x => -x,
mul_series(stream_tail(s), invert_unit_series(s))));
}
Use the results of exercises 3.60
and 3.61
to define a
function
div_series
that divides two power series.
The function
div_series
should work for any two series, provided that the denominator series begins
with a nonzero constant term. (If the denominator has a zero constant term,
then
div_series
should signal an error.) Show how to use
div_series
together with the result of exercise 3.59
to generate the power series for
tangent.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
[1]
Eratosthenes,
a third-century BCE
Alexandrian Greek philosopher, is famous for giving the first accurate
estimate of the
circumference of the Earth, which he computed by
observing shadows cast at noon on the day of the summer solstice.
Eratosthenes's sieve method, although ancient, has formed the basis
for special-purpose hardware
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.
[2]
We have named these
figures after
Peter Henderson, who was the first person to show us diagrams of this sort
as a way of thinking about stream processing.
[4]
This last point is very
subtle and relies on the fact that $p_{n+1} \leq p_{n}^2$. (Here, $p_{k}$ denotes the
$k$th prime.) Estimates such as these are very
difficult to establish. The ancient proof by
Euclid that there are an infinite number of primes shows that
$p_{n+1}\leq p_{1} p_{2}\,\cdots\,\, p_{n} +1$,
and no substantially better result was proved until 1851, when the Russian
mathematician
P. L. Chebyshev established
that $p_{n+1}\leq 2p_{n}$ for all
$n$. This result, originally conjectured in
1845, is known as
Bertrand's hypothesis. A proof can be
found in section 22.3 of
Hardy and Wright 1960 .
[5]
This
exercise shows how call-by-need is closely related to
ordinary memoization as described in
exercise 3.27. In that exercise, we used
assignment to explicitly construct a local table. Our call-by-need stream
optimization effectively constructs such a table automatically, storing
values in the previously forced parts of the stream.
3.5.2
Infinite Streams