Streams with delayed evaluation can be a powerful modeling tool,
providing many of the benefits of local state and assignment.
Moreover, they avoid some of the theoretical tangles that accompany
the introduction of assignment into a programming language.
The stream approach can be illuminating because it allows us to build
systems with different
module boundaries than systems organized around
assignment to state variables. For example, we can think of an entire
time series (or signal) as a focus of interest, rather than the values
of the state variables at individual moments. This makes it
convenient to combine and compare components of state from different
moments.
Formulating iterations as stream processes
In section 1.2.1, we introduced
iterative processes, which proceed by updating state variables. We know now
that we can represent state as a timeless stream of values
rather than as a set of variables to be updated. Let's adopt this
perspective in revisiting the square-root
procedurefunction
from section 1.1.7. Recall that the idea is to
generate a sequence of better and better guesses for the square root of
$x$ by applying over and over again the
procedurefunction
that improves guesses:
Original
JavaScript
(define (sqrt-improve guess x)
(average guess (/ x guess)))
function sqrt_improve(guess, x) {
return average(guess, x / guess);
}
In our original
sqrtprocedure,function,
we made these guesses be the successive values of a state variable. Instead
we can generate the infinite stream of guesses, starting with an initial
guess of 1:[1]
guess of 1:
We can generate more and more terms of the stream to get better and
better guesses. If we like, we can write a
procedurefunction
that keeps generating terms until the answer is good enough.
(See exercise 3.67.)
Another iteration that we can treat in the same way is to generate an
approximation to
$\pi$, based upon the
alternating series that we saw in
section 1.3.1:
\[
\begin{array}{lll}
\dfrac {\pi}{4} &=& 1-\dfrac{1}{3}+\dfrac{1}{5}-\dfrac{1}{7}+\cdots
\end{array}
\]
We first generate the stream of summands of the series (the reciprocals
of the odd integers, with alternating signs). Then we take the stream
of sums of more and more terms (using the
partial-sums procedurepartial_sums function
of exercise 3.58) and scale the result by 4:
This gives us a stream of better and better approximations to
$\pi$, although the approximations converge
rather slowly. Eight terms of the sequence bound the value of
$\pi$ between 3.284 and 3.017.
So far, our use of the stream of states approach is not much different
from updating state variables. But streams give us an opportunity to do
some interesting tricks. For example, we can transform a stream with a
sequence accelerator that converts a sequence of approximations to a
new sequence that converges to the same value as the original, only faster.
One such accelerator, due to the eighteenth-century Swiss mathematician
Leonhard Euler, works well with sequences that are partial sums of
alternating series (series of terms with alternating signs). In
Euler's technique, if $S_n$ is the
$n$th term of the original sum sequence, then
the accelerated sequence has terms
\[
\begin{array}{l}
S_{n+1} - \dfrac{(S_{n+1}-S_n)^2}{S_{n-1}-2S_n+S_{n+1}}
\end{array}
\]
Thus, if the original sequence is represented as a stream of values,
the transformed sequence is given by
Note that we make use of the memoization optimization of
section 3.5.1, because in the
following we will rely on repeated evaluation of the resulting stream.
We can demonstrate Euler acceleration with our sequence of
approximations to $\pi$:
Even better, we can accelerate the accelerated sequence, and recursively
accelerate that, and so on. Namely, we create a stream of streams (a
structure we'll call a
tableau) in which each stream is the transform of the preceding one:
Original
JavaScript
(define (make-tableau transform s)
(cons-stream s
(make-tableau transform
(transform s))))
The tableau has the form
\[
\begin{array}{llllll}
s_{00} & s_{01} & s_{02} & s_{03} & s_{04} & \ldots\\
& s_{10} & s_{11} & s_{12} & s_{13} & \ldots\\
& & s_{20} & s_{21} & s_{22} & \ldots\\
& & & & \ldots &
\end{array}
\]
Finally, we form a sequence by taking the first term in each row of
the tableau:
The result is impressive. Taking eight terms of the sequence yields the
correct value of $\pi$ to 14 decimal places.
If we had used only the original $\pi$ sequence,
we would need to compute on the order of $10^{13}$
terms (i.e., expanding the series far enough so that the individual terms
are less then $10^{-13}$) to get that much
accuracy!
We could have implemented these acceleration techniques without using
streams. But the stream formulation is particularly elegant and convenient
because the entire sequence of states is available to us as a data structure
that can be manipulated with a uniform set of operations.
Louis Reasoner asks why the
sqrt-stream procedure
was not written in the following more straightforward way, without
the local variable guesses:
(define (sqrt-stream x)
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
(sqrt-stream x))))
Alyssa P. Hacker replies that this version of the procedure
is considerably less efficient because it performs redundant computation.
Explain Alyssa's answer. Would the two versions still differ in
efficiency if our implementation of delay
used only (lambda () exp)
without using the optimization provided by
memo-proc
(section 3.5.1)?
Louis Reasoner is not happy with the performance of the stream
produced by the
sqrt_stream function and
tries to optimize it using memoization:
function sqrt_stream_optimized(x) {
return pair(1,
memo(() => stream_map(guess =>
sqrt_improve(guess, x),
sqrt_stream_optimized(x))));
}
Alyssa P. Hacker instead proposes
function sqrt_stream_optimized_2(x) {
const guesses = pair(1,
memo(() => stream_map(guess =>
sqrt_improve(guess, x),
guesses)));
return guesses;
}
and claims that Louis's version is
considerably less efficient than hers, because it performs
redundant computation. Explain Alyssa's answer.
Would Alyssa's approach without memoization be more
efficient
than the original sqrt_stream?
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.67
Write a
procedure stream-limitfunction stream_limit
that takes as arguments a stream
and a number (the tolerance). It should examine the stream until it
finds two successive elements that differ in absolute value by less
than the tolerance, and return the second of the two elements. Using
this, we could compute square roots up to a given tolerance by
Original
JavaScript
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
function sqrt(x, tolerance) {
return stream_limit(sqrt_stream(x), tolerance);
}
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.68
Use the series
\[
\begin{array}{lll}
\ln 2 &=& 1-\dfrac{1}{2}+\dfrac{1}{3}-\dfrac{1}{4}+\cdots
\end{array}
\]
to compute three sequences of approximations to the natural logarithm of 2,
in the same way we did above for $\pi$.
How rapidly do these sequences converge?
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.
Infinite streams of pairs
In section 2.2.3, we saw how the
sequence paradigm handles traditional nested loops as processes defined
on sequences of pairs. If we generalize this technique to infinite streams,
then we can write programs that are not easily represented as loops, because
the looping must range over an infinite set.
For example, suppose we want to generalize the
prime-sum-pairs procedureprime_sum_pairs function
of section 2.2.3 to produce the stream
of pairs of all integers $(i,j)$ with
$i \leq j$ such that
$i+j$
is prime. If
int-pairsint_pairs
is the sequence of all pairs of integers $(i,j)$
with $i \leq j$, then our required stream is
simply[2]
Our problem, then, is to produce the stream
int-pairs.int_pairs.
More generally, suppose we have two streams
$S = (S_i)$ and
$T = (T_j)$,
and imagine the infinite rectangular array
\[
\begin{array}{cccc}
(S_0,T_0) & (S_0,T_1) & (S_0, T_2) & \ldots\\
(S_1,T_0) & (S_1,T_1) & (S_1, T_2) & \ldots\\
(S_2,T_0) & (S_2,T_1) & (S_2, T_2) & \ldots\\
\ldots
\end{array}
\]
We wish to generate a stream that contains all the pairs in the array
that lie on or above the diagonal, i.e., the pairs
\[
\begin{array}{cccc}
(S_0,T_0) & (S_0,T_1) & (S_0, T_2) & \ldots\\
& (S_1,T_1) & (S_1, T_2) & \ldots\\
& & (S_2, T_2) & \ldots\\
& & & \ldots
\end{array}
\]
(If we take both $S$ and
$T$ to be the stream of integers, then this
will be our desired stream
int-pairs.)int_pairs.)
Call the general stream of pairs
(pairs S T),pairs(S, T),
and consider it to be composed of three parts: the pair
$(S_0,T_0)$, the rest of the pairs in the first
row, and the remaining pairs:[3]
\[
\begin{array}{c|ccc}
(S_0,T_0) & (S_0,T_1) & (S_0, T_2) & \ldots\\
\hline{} %--------------------------------------------------- \\
& (S_1,T_1) & (S_1, T_2) & \ldots\\
& & (S_2, T_2) & \ldots\\
& & & \ldots
\end{array}
\]
Observe that the third piece in this decomposition (pairs that are not in
the first row) is (recursively) the pairs formed from
(stream-cdr S)stream_tail(S)
and
(stream-cdr T).stream_tail(T).
Also note that the second piece (the rest of the first row) is
In order to complete the
procedure,function,
we must choose some way to
combine the two inner streams. One idea is to
use the stream analog of the appendprocedurefunction
from section 2.2.1:
This is unsuitable for infinite streams, however, because it takes all the
elements from the first stream before incorporating the second stream. In
particular, if we try to generate all pairs of positive integers using
Original
JavaScript
(pairs integers integers)
pairs(integers, integers);
our stream of results will first try to run through all pairs with the
first integer equal to 1, and hence will never produce pairs with any
other value of the first integer.
To handle infinite streams, we need to devise an order of combination
that ensures that every element will eventually be reached if we let
our program run long enough. An elegant way to accomplish this is
with the following interleaveprocedurefunction:[4]
Since interleave takes elements alternately
from the two streams, every element of the second stream will eventually
find its way into the interleaved stream, even if the first stream is
infinite.
We can thus generate the required stream of pairs as
Exercise 3.69
Examine the stream
(pairs integers integers).pairs(integers, integers).
Can you make any general comments about the order in which the pairs are
placed into the stream? For example, approximately how many pairs precede
the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make
precise mathematical statements here, all the better. But feel free to give
more qualitative answers if you find yourself getting bogged down.)
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.70
Modify the pairsprocedurefunction
so that
(pairs integers integers)pairs(integers, integers)
will produce the stream of all pairs of integers
$(i,j)$ (without the condition
$i \leq j$). Hint: You will need to
mix in an additional stream.
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.71
Louis Reasoner thinks that building a stream of pairs from three parts is
unnecessarily complicated. Instead of separating the pair
$(S_0,T_0)$ from the rest of the pairs in the
first row, he proposes to work with the whole first row, as follows:
Does this work? Consider what happens if we evaluate
(pairs integers integers)pairs(integers, integers)
using Louis's definition of pairs.
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.72
Write a
procedurefunctiontriples that takes three infinite streams,
$S$, $T$, and
$U$, and produces the stream of triples
$(S_i,T_j,U_k)$ such that
$i \leq j \leq k$. Use
triples to generate the stream of all
Pythagorean triples of positive integers, i.e., the triples
$(i,j,k)$ such that
$i \leq j$ and
$i^2 + j^2 =k^2$.
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.73
It would be nice to be able to generate
streams in which the pairs
appear in some useful order, rather than in the order that results
from an ad hoc interleaving process. We can use a technique
similar to the mergeprocedurefunction
of exercise 3.59, if we define a way to say that
one pair of integers is less than another. One way to do
this is to define a
weighting function
$W(i,j)$ and stipulate that
$(i_1,j_1)$ is less than
$(i_2,j_2)$ if
$W(i_1,j_1) < W(i_2,j_2)$. Write a
procedure merge-weightedfunction merge_weighted
that is like merge, except that
merge-weightedmerge_weighted
takes an additional argument weight, which is a
procedurefunction
that computes the weight of a pair, and is used to determine the order in
which elements should appear in the resulting merged stream.[5] Using this, generalize pairs
to a
procedure weighted-pairsfunction weighted_pairs
that takes two streams, together with a
procedurefunction
that computes a weighting function, and generates the stream of pairs,
ordered according to weight. Use your
procedurefunction
to generate
the stream of all pairs of positive integers
$(i,j)$ with $i \leq
j$ ordered according to the sum
$i + j$
the stream of all pairs of positive integers
$(i,j)$ with $i \leq
j$, where neither $i$ nor
$j$ is divisible by 2, 3, or 5, and the
pairs are ordered according to the sum
$2 i + 3 j + 5 i j$.
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.74
Numbers that can be expressed as the sum of two cubes in more than one
way are sometimes called
Ramanujan numbers, in honor of the
mathematician Srinivasa Ramanujan.[6] Ordered streams of pairs provide an elegant solution
to the problem of computing these numbers. To find a number that can be
written as the sum of two cubes in two different ways, we need only generate
the stream of pairs of integers $(i,j)$ weighted
according to the sum $i^3 + j^3$ (see
exercise 3.73), then search the stream for
two consecutive pairs with the same weight. Write a
procedurefunction
to generate the Ramanujan numbers. The first
such number is 1,729. What are the next five?
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.75
In a similar way to exercise 3.74 generate
a stream of all numbers that can be written as the sum of two squares in
three different ways (showing how they can be so written).
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.
Streams as signals
We began our discussion of streams by describing them as computational
analogs of the signals in signal-processing systems.
In fact, we can use streams to model signal-processing systems in a very
direct way, representing the values of a signal at successive time
intervals as consecutive elements of a stream. For instance, we can
implement an
integrator or
summer that, for an input stream
$x=(x_{i})$, an initial value $C$, and a small increment $dt$,
accumulates the sum
\[
\begin{array}{lll}
S_i &=& C +\sum_{j=1}^{i} x_{j} \, dt
\end{array}
\]
and returns the stream of values $S=(S_{i})$.
The following integralprocedurefunction
is reminiscent of the implicit style definition of the
stream of integers (section 3.5.2):
Figure 3.57 The integral
procedure viewed as a signal-processing system.
Figure 3.58 The integral
function viewed as a signal-processing system.
Figure 3.57
Figure 3.58
is a picture of a signal-processing
system that corresponds to the integralprocedure.function.
The input stream is scaled by $dt$ and passed
through an adder, whose output is passed back through the same adder.
The self-reference in the definition of
intinteg
is reflected in the figure by the feedback loop that
connects the output of the adder to one of the inputs.
Exercise 3.76
We can model electrical circuits using streams to represent the values
of currents or voltages at a sequence of times. For instance, suppose
we have an
RC circuit consisting of a resistor of resistance
$R$ and a capacitor of capacitance
$C$ in series. The voltage response
$v$ of the circuit to an injected current
$i$ is determined by the formula in
figure 3.59, whose structure is shown by the
accompanying signal-flow diagram.
Figure 3.59 An RC circuit and the associated
signal-flow diagram.
Write a
procedurefunctionRC that models this circuit.
RC should take as inputs the values of
$R$, $C$, and
$dt$ and should return a
procedurefunction
that takes as inputs a stream representing the current
$i$ and an initial value for the capacitor
voltage $v_{0}$ and produces as output the
stream of voltages $v$. For example, you
should be able to use RC to model an RC
circuit with $R = 5$ ohms,
$C = 1$ farad, and a 0.5-second time step by
evaluating
(define RC1 (RC 5 1 0.5)).
const RC1 = RC(5, 1, 0.5).
This defines RC1 as a
procedurefunction
that takes a stream representing the time sequence of currents and an
initial capacitor voltage and produces the output stream of voltages.
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.77
Alyssa P. Hacker is designing a system to process signals coming from
physical sensors. One important feature she wishes to produce is a signal
that describes the
zero crossings of the input signal. That is,
the resulting signal should be $+1$ whenever the
input signal changes from negative to positive,
$-1$ whenever the input signal changes from
positive to negative, and 0 otherwise. (Assume that the sign of a 0 input
is positive.) For example, a typical input signal with its associated
zero-crossing signal would be
In Alyssa's system, the signal from the sensor is represented as a
stream
sense-datasense_data
and the stream
zero-crossingszero_crossings
is the corresponding stream of zero crossings. Alyssa first writes a
procedurefunctionsign-change-detectorsign_change_detector
that takes two values as arguments and compares the signs of the values to
produce an appropriate $0$,
$1$, or $-1$. She
then constructs her zero-crossing stream as follows:
Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is
approximately equivalent to the following one, which uses
the generalized version of
stream-map
from exercise 3.50:
the function
stream_map_2
from exercise 3.53:
Complete the program by supplying the indicated
$expression$.
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.78
Unfortunately, Alyssa's
zero-crossing detector in
exercise 3.77 proves to be insufficient,
because the noisy signal from the sensor leads to spurious zero crossings.
Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the
signal to filter out the noise before extracting the zero crossings.
Alyssa takes his advice and decides to extract the zero crossings from
the signal constructed by averaging each value of the sense data with
the previous value. She explains the problem to her assistant, Louis
Reasoner, who attempts to implement the idea, altering Alyssa's
program as follows:
This does not correctly implement Alyssa's plan.
Find the bug that Louis has installed
and fix it without changing the structure of the program. (Hint: You
will need to increase the number of arguments to
make-zero-crossings.)
make_zero_crossings.)
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.79
Eva Lu Ator has a criticism of Louis's approach in
exercise 3.78.
The program he wrote is
not modular, because it intermixes the operation of smoothing with the
zero-crossing extraction. For example, the extractor should not have
to be changed if Alyssa finds a better way to condition her input
signal. Help Louis by writing a
procedurefunctionsmooth that takes a stream as input and
produces a stream in which each element is the average of two successive
input stream elements. Then use smooth as a
component to implement the zero-crossing detector in a more modular style.
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]
We can't use
let to bind the local variable
guesses because the value of
guesses depends on
guesses itself.
Exercise 3.66
addresses why we want
a local name here.
[2]
As in
section 2.2.3, we
represent a pair of integers as a list rather than a
Lisp
pair.
[3]
See
exercise 3.71 for some insight into why we
chose this decomposition.
[4]
The
precise statement of the required property on the order of combination is
as follows: There should be a function $f$ of
two arguments such that the pair corresponding to
element $i$ of the first stream and
element $j$ of the second stream will
appear as element number $f(i,j)$ of the output
stream. The trick of using interleave
to accomplish this was shown to us by
David Turner, who employed it in the language
KRC (Turner 1981).
[5]
We
will require that the weighting function be such that the weight of a pair
increases as we move out along a row or down along a column of the array of
pairs.
[6]
To quote from G. H.
Hardy's obituary of
Ramanujan (Hardy 1921): It was
Mr. Littlewood
(I believe) who remarked that every positive integer was one of his
friends. I remember once going to see him when he was lying ill
at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number
seemed to me a rather dull one, and that I hoped it was not an unfavorable
omen. No, he replied, it is a very interesting number;
it is the smallest number expressible as the sum of two cubes in two
different ways. The trick of using weighted pairs to
generate the Ramanujan numbers was shown to us by
Charles
Leiserson.
