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:
Original
JavaScript
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
This makes sense because integers will be a
pair whose
carhead
is 1 and whose
cdrtail
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:
Original
JavaScript
(define (divisible? x y) (= (remainder x y) 0))
function is_divisible(x, y) { return x % y === 0; }
Original
JavaScript
(define no-sevens
(stream-filter (lambda (x) (not (divisible? x 7)))
integers))
Then we can find integers not divisible by 7 simply by accessing
elements of this stream:
Original
JavaScript
(stream-ref no-sevens 100)
117
stream_ref(no_sevens, 100);
117
In analogy with integers, we can define the
infinite stream of Fibonacci numbers:
Original
JavaScript
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
function fibgen(a, b) {
return pair(a, () => fibgen(b, a + b));
}
const fibs = fibgen(0, 1);
FibsThe constant fibs
is a pair whose
carhead
is 0 and whose
cdrtail
is a promise to evaluate
(fibgen 1 1).fibgen(1, 1).
When we evaluate this delayed
(fibgen 1 1),fibgen(1, 1),
it will produce a pair whose
carhead
is 1 and whose
cdrtail
is a promise to evaluate
(fibgen 1 2),fibgen(1, 2),
and so on.
For a look at a more exciting infinite stream, we can generalize the
no-sevensno_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:
Original
JavaScript
(stream-ref primes 50)
233
stream_ref(primes, 50);
233
It is interesting to contemplate the signal-processing system set up
by sieve, shown in the
Henderson diagram in
figure 3.55figure 3.56.[2] The input stream feeds into an
unconserunpairer
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
consed
onto the output of the internal sieve to form the output stream.
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.
Original
JavaScript
Defining streams implicitly
The integers and
fibs streams above were defined by specifying
generatingproceduresfunctions
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
expressionstatement
defines the
stream ones to be an infinite stream of ones:
Original
JavaScript
(define ones (cons-stream 1 ones))
const ones = pair(1, () => ones);
This works much like the declaration of a recursive
procedure:function:ones is a pair whose
carhead
is 1 and whose
cdrtail
is a promise to evaluate ones. Evaluating the
cdrtail
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,add_streams,
which produces the elementwise sum of two given streams:[3]
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:
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:
Scale-stream
is another useful procedure
The function
scale_stream
is also useful
in formulating such stream definitions. This multiplies each item in a
stream by a given constant:
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:
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
prime?is_prime
predicate, which itself uses the primes stream.
The reason this
procedurefunction
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]
Exercise 3.56
Without running the program, describe the elements of the
stream defined by
Original
JavaScript
(define s (cons-stream 1 (add-streams s s)))
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,... .
Exercise 3.57
Define a
procedurefunctionmul-streams,mul_streams,
analogous to
add-streams,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:
Exercise 3.58
Define a
procedurefunctionpartial-sumspartial_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)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)));
}
Exercise 3.59
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)scale_stream(S, 2)
are also elements of S.
The same is true for
(scale-stream S 3)scale_stream(S, 3)
and
(scale-stream S 5).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
procedurefunctionmerge that combines two ordered
streams into one ordered result stream, eliminating repetitions:
Exercise 3.60
How many additions are performed when we compute the
$n$th Fibonacci number using the definition of
fibs based on the
add-streams procedure?
Show that the number of additions would be exponentially greater if we
had implemented (delay exp) simply as
(lambda () exp), without using the
optimization provided by the memo-proc
procedure described in
section 3.5.1.[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.53.[6]
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.
Exercise 3.61
Give an interpretation of the stream computed by the
following procedure:function
Original
JavaScript
(define (expand num den radix)
(cons-stream
(quotient (* num radix) den)
(expand (remainder (* num radix) den) den radix)))
function expand(num, den, radix) {
return pair(math_trunc((num * radix) / den),
() => expand((num * radix) % den, den, radix));
}
(Quotient
is a primitive that returns the
integer quotient of two integers.)
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)?
expand(1, 7, 10)?
What is produced by
(expand 3 8 10)?
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 ...
Exercise 3.62
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
procedurefunctionintegrate-seriesintegrate_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,integrate_series,
we will
cons on the appropriate constant.)
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
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:
Exercise 3.63
With
power series represented as streams of coefficients as in
exercise 3.62, adding series is implemented
by add-streams. Complete the declaration of
the following
procedurefunction
for multiplying series:
Exercise 3.64
Let $S$ be a power series
(exercise 3.62)
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
procedurefunctioninvert-unit-seriesinvert_unit_series
that computes $1/S$ for a power series
$S$ with constant term 1. You will need to use
mul-seriesmul_series
from exercise 3.63.
Exercise 3.65
Use the results of exercises 3.63
and 3.64
to define a
procedurefunctiondiv-seriesdiv_series
that divides two power series.
Div-seriesThe 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-seriesdiv_series
should signal an error.) Show how to use
div-seriesdiv_series
together with the result of exercise 3.62
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 sieves that, 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.
This uses the generalized version of
stream-map
from exercise 3.50.
This uses the function
stream_map_2
from exercise 3.53.
[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.
[6]
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.