Streams
We've gained a good understanding of assignment as a tool in modeling, as well as an appreciation of the complex problems that assignment raises. It is time to ask whether we could have gone about things in a different way, so as to avoid some of these problems. In this section, we explore an alternative approach to modeling state, based on data structures called streams . As we shall see, streams can mitigate some of the complexity of modeling state.
Let's step back and review where this complexity comes from. In an attempt to model real-world phenomena, we made some apparently reasonable decisions: We modeled real-world objects with local state by computational objects with local variables. We identified time variation in the real world with time variation in the computer. We implemented the time variation of the states of the model objects in the computer with assignments to the local variables of the model objects.
Is there another approach? Can we avoid identifying time in the computer with time in the modeled world? Must we make the model change with time in order to model phenomena in a changing world? Think about the issue in terms of mathematical functions. We can describe the time-varying behavior of a quantity x as a function of time x(t). If we concentrate on x instant by instant, we think of it as a changing quantity. Yet if we concentrate on the entire time history of values, we do not emphasize change---the function itself does not change.@footnote{Physicists sometimes adopt this view by introducing the ``world lines'' of particles as a device for reasoning about motion. We've also already mentioned (section 2.2.3) that this is the natural way to think about signal-processing systems. We will explore applications of streams to signal processing in section 3.5.3.}
If time is measured in discrete steps, then we can model a time function as a (possibly infinite) sequence. In this section, we will see how to model change in terms of sequences that represent the time histories of the systems being modeled. To accomplish this, we introduce new data structures called streams . From an abstract point of view, a stream is simply a sequence. However, we will find that the straightforward implementation of streams as lists (as in section 2.2.1) doesn't fully reveal the power of stream processing. As an alternative, we introduce the technique of delayed evaluation , which enables us to represent very large (even infinite) sequences as streams.
Stream processing lets us model systems that have state without ever using assignment or mutable data. This has important implications, both theoretical and practical, because we can build models that avoid the drawbacks inherent in introducing assignment. On the other hand, the stream framework raises difficulties of its own, and the question of which modeling technique leads to more modular and more easily maintained systems remains open.
3.5.1 Streams Are Delayed Lists
As we saw in section 2.2.3, sequences can serve as standard interfaces for combining program modules. We formulated powerful abstractions for manipulating sequences, such as map, filter, and accumulate, that capture a wide variety of operations in a manner that is both succinct and elegant.
Unfortunately, if we represent sequences as lists, this elegance is bought at the price of severe inefficiency with respect to both the time and space required by our computations. When we represent manipulations on sequences as transformations of lists, our programs must construct and copy data structures (which may be huge) at every step of a process.
To see why this is true, let us compare two programs for computing the sum of all the prime numbers in an interval. The first program is written in standard iterative style:@footnote{Assume that we have a predicate prime? (e.g., as in section 1.2.6) that tests for primality.}
The second program performs the same computation using the sequence operations of section 2.2.3:
In carrying out the computation, the first program needs to store only the sum being accumulated. In contrast, the filter in the second program cannot do any testing until enumerate-interval has constructed a complete list of the numbers in the interval. The filter generates another list, which in turn is passed to accumulate before being collapsed to form a sum. Such large intermediate storage is not needed by the first program, which we can think of as enumerating the interval incrementally, adding each prime to the sum as it is generated.
The inefficiency in using lists becomes painfully apparent if we use the sequence paradigm to compute the second prime in the interval from 10,000 to 1,000,000 by evaluating the expression
This expression does find the second prime, but the computational overhead is outrageous. We construct a list of almost a million integers, filter this list by testing each element for primality, and then ignore almost all of the result. In a more traditional programming style, we would interleave the enumeration and the filtering, and stop when we reached the second prime.
Streams are a clever idea that allows one to use sequence manipulations without incurring the costs of manipulating sequences as lists. With streams we can achieve the best of both worlds: We can formulate programs elegantly as sequence manipulations, while attaining the efficiency of incremental computation. The basic idea is to arrange to construct a stream only partially, and to pass the partial construction to the program that consumes the stream. If the consumer attempts to access a part of the stream that has not yet been constructed, the stream will automatically construct just enough more of itself to produce the required part, thus preserving the illusion that the entire stream exists. In other words, although we will write programs as if we were processing complete sequences, we design our stream implementation to automatically and transparently interleave the construction of the stream with its use.
On the surface, streams are just lists with different names for the procedures that manipulate them. There is a constructor, cons-stream, and two selectors, stream-car and stream-cdr, which satisfy the constraints
(stream-car (cons-stream x y)) = x (stream-cdr (cons-stream x y)) = y
There is a distinguishable object, the-empty-stream, which cannot be the result of any cons-stream operation, and which can be identified with the predicate stream-null?.@footnote{In the @acronym{MIT} implementation, the-empty-stream is the same as the empty list '(), and stream-null? is the same as null?.} Thus we can make and use streams, in just the same way as we can make and use lists, to represent aggregate data arranged in a sequence. In particular, we can build stream analogs of the list operations from Chapter 2, such as list-ref, map, and for-each:@footnote{This should bother you. The fact that we are defining such similar procedures for streams and lists indicates that we are missing some underlying abstraction. Unfortunately, in order to exploit this abstraction, we will need to exert finer control over the process of evaluation than we can at present. We will discuss this point further at the end of section 3.5.4. In section 4.2, we'll develop a framework that unifies lists and streams.}
To make the stream implementation automatically and transparently interleave the construction of a stream with its use, we will arrange for the cdr of a stream to be evaluated when it is accessed by the stream-cdr procedure rather than when the stream is constructed by cons-stream. This implementation choice is reminiscent of our discussion of rational numbers in section 2.1.2, where we saw that we can choose to implement rational numbers so that the reduction of numerator and denominator to lowest terms is performed either at construction time or at selection time. The two rational-number implementations produce the same data abstraction, but the choice has an effect on efficiency. There is a similar relationship between streams and ordinary lists. As a data abstraction, streams are the same as lists. The difference is the time at which the elements are evaluated. With ordinary lists, both the car and the cdr are evaluated at construction time. With streams, the cdr is evaluated at selection time.
Our implementation of streams will be based on a special form called delay. Evaluating (delay What this means is that we will construct streams using pairs. However, rather than placing the value of the rest of the stream into the cdr of the pair we will put there a promise to compute the rest if it is ever requested. Stream-car and stream-cdr can now be defined as procedures:
Stream-car selects the car of the pair; stream-cdr selects the cdr of the pair and evaluates the delayed expression found there to obtain the rest of the stream.@footnote{Although stream-car and stream-cdr can be defined as procedures, cons-stream must be a special form. If cons-stream were a procedure, then, according to our model of evaluation, evaluating (cons-stream To see how this implementation behaves, let us analyze the ``outrageous'' prime computation we saw above, reformulated in terms of streams:
We will see that it does indeed work efficiently.
We begin by calling stream-enumerate-interval with the arguments 10,000 and 1,000,000. Stream-enumerate-interval is the stream analog of enumerate-interval (section 2.2.3):
and thus the result returned by stream-enumerate-interval, formed by the cons-stream, is@footnote{The numbers shown here do not really appear in the delayed expression. What actually appears is the original expression, in an environment in which the variables are bound to the appropriate numbers. For example, (+ low 1) with low bound to 10,000 actually appears where 10001 is shown.}
That is, stream-enumerate-interval returns a stream represented as a pair whose car is 10,000 and whose cdr is a promise to enumerate more of the interval if so requested. This stream is now filtered for primes, using the stream analog of the filter procedure (section 2.2.3):
Stream-filter tests the stream-car of the stream (the car of the pair, which is 10,000). Since this is not prime, stream-filter examines the stream-cdr of its input stream. The call to stream-cdr forces evaluation of the delayed stream-enumerate-interval, which now returns
Stream-filter now looks at the stream-car of this stream, 10,001, sees that this is not prime either, forces another stream-cdr, and so on, until stream-enumerate-interval yields the prime 10,007, whereupon stream-filter, according to its definition, returns
This result is now passed to stream-cdr in our original expression. This forces the delayed stream-filter, which in turn keeps forcing the delayed stream-enumerate-interval until it finds the next prime, which is 10,009. Finally, the result passed to stream-car in our original expression is
Stream-car returns 10,009, and the computation is complete. Only as many integers were tested for primality as were necessary to find the second prime, and the interval was enumerated only as far as was necessary to feed the prime filter.
In general, we can think of delayed evaluation as ``demand-driven''programming, whereby each stage in the stream process is activated only enough to satisfy the next stage. What we have done is to decouple the actual order of events in the computation from the apparent structure of our procedures. We write procedures as if the streams existed ``all at once'' when, in reality, the computation is performed incrementally, as in traditional programming styles.
Although delay and force may seem like mysterious operations, their implementation is really quite straightforward. Delay must package an expression so that it can be evaluated later on demand, and we can accomplish this simply by treating the expression as the body of a procedure. Delay can be a special form such that
is syntactic sugar for
Force simply calls the procedure (of no arguments) produced by delay, so we can implement force as a procedure:
This implementation suffices for delay and force to work as advertised, but there is an important optimization that we can include. In many applications, we end up forcing the same delayed object many times. This can lead to serious inefficiency in recursive programs involving streams. (See Exercise 3-57.) The solution is to build delayed objects so that the first time they are forced, they store the value that is computed. Subsequent forcings will simply return the stored value without repeating the computation. In other words, we implement delay as a special-purpose memoized procedure similar to the one described in Exercise 3-27. One way to accomplish this is to use the following procedure, which takes as argument a procedure (of no arguments) and returns a memoized version of the procedure. The first time the memoized procedure is run, it saves the computed result. On subsequent evaluations, it simply returns the result.
Delay is then defined so that (delay and force is as defined previously.@footnote{There are many possible implementations of streams other than the one described in this section. Delayed evaluation, which is the key to making streams practical, was inherent in Algol 60's call-by-name parameter-passing method. The use of this mechanism to implement streams was first described by Landin (1965). Delayed evaluation for streams was introduced into Lisp by Friedman and Wise (1976). In their implementation, cons always delays evaluating its arguments, so that lists automatically behave as streams. The memoizing optimization is also known as call-by-need . The Algol community would refer to our original delayed objects as call-by-name thunks and to the optimized versions as call-by-need thunks .}
Exercise 3.50: Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote Footnote 12.
Exercise 3.51: In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:
What does the interpreter print in response to evaluating each expression in the following sequence?@footnote{Exercises such as Exercise 3-51 and Exercise 3-52 are valuable for testing our understanding of how delay works. On the other hand, intermixing delayed evaluation with printing---and, even worse, with assignment---is extremely confusing, and instructors of courses on computer languages have traditionally tormented their students with examination questions such as the ones in this section. Needless to say, writing programs that depend on such subtleties is odious programming style. Part of the power of stream processing is that it lets us ignore the order in which events actually happen in our programs. Unfortunately, this is precisely what we cannot afford to do in the presence of assignment, which forces us to be concerned with time and change.}
What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay 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:
This makes sense because integers will be a pair whose car is 1 and whose cdr 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:
Then we can find integers not divisible by 7 simply by accessing elements of this stream:
In analogy with integers, we can define the infinite stream of Fibonacci numbers:
Fibs is a pair whose car is 0 and whose cdr is a promise to evaluate (fibgen 1 1). When we evaluate this delayed (fibgen 1 1), it will produce a pair whose car is 1 and whose cdr 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 .@footnote{Eratosthenes, a third-century @acronym{B.C.} 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 recently, were the most powerful tools in existence for locating large primes. Since the 70s, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1.2.6.} 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:
Now to find a particular prime we need only ask for it:
It is interesting to contemplate the signal-processing system set up by sieve, shown in the ``Henderson diagram'' in Figure 3-31.@footnote{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. Each solid line represents a stream of values being transmitted. The dashed line from the car to the cons and the filter indicates that this is a single value rather than a stream.} The input stream feeds into an ``unconser'' 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. 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'' procedures 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:
This works much like the definition of a recursive procedure: ones is a pair whose car is 1 and whose cdr is a promise to evaluate ones. Evaluating the cdr 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:@footnote{This uses the generalized version of stream-map from Exercise 3-50.}
Now we can define the integers as follows:
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 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):
This is a recursive definition, since primes is defined in terms of the prime? predicate, which itself uses the primes stream. The reason this procedure 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)).@footnote{This last point is very subtle and relies on the fact that p_(n+1) <= p_n^2. (Here, p_k denotes the kth 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)<= p_1 p_2...p_n + 1, and no substantially better result was proved until 1851, when the Russian mathematician P. L. Chebyshev established that p_(n+1)<= 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.}
The stream implementation in action
Implementing delay and force
3.5.2 Infinite Streams
+---------------------------------------------------------------+
| sieve |
| |
| __/| |\__ |
| __/car|........................................| \__ |
| _/ | : | \_ |
----><_ | V | cons _>---->
| \__ | +------------+ +------------+ | __/ |
| \cdr|--->| filter: | | sieve |--->| __/ |
| \| | |--->| | |/ |
| | not | | | |
| | divisible? | | | |
| +------------+ +------------+ |
+---------------------------------------------------------------+
Defining streams implicitly
1 1 2 3 5 8 13 21 ... = (stream-cdr fibs)
0 1 1 2 3 5 8 13 ... = fibs
0 1 1 2 3 5 8 13 21 34 ... = fibs
Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:
x^2 x^3 x^4
e^x = 1 + x + ----- + ----- + --------- + ...
2 3 * 2 4 * 3 * 2
x^2 x^4
cos x = 1 - ----- + --------- - ...
2 4 * 3 * 2
x^3 x^5
sin x = x - ----- + ------------- - ...
3 * 2 5 * 4 * 3 * 2
represented as infinite streams. We will represent the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... as the stream whose elements are the coefficients a_0, a_1, a_2, a_3, ....
@item
The integral of the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... is the series
1 1 1
c + a_0 x + --- x_1 r^2 + --- a_2 r^3 + --- a_3 r^4 + ...
2 3 4
where c is any constant. Define a procedure integrate-series that takes as input a stream a_0, a_1, a_2, ... representing a power series and returns the stream a_0, (1/2)a_1, (1/3)a_2, ... of coefficients of the non-constant 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 cons on the appropriate constant.)
@item
The function x |-> 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
S * X = 1
(1 + S_R) * X = 1
X + S_R * X = 1
X = 1 - S_R * X
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 procedure 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.
3.5.3 Exploiting the Stream Paradigm
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 procedure 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 procedure that improves guesses:
[pi] 1 1 1
---- = 1 - --- + --- - --- + ...
4 3 5 7
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 procedure of Exercise 3-55) and scale the result by 4:
(S_(n+1) - S_n)^2
S_(n+1) - ------------------------
S_(n-1) - 2S_n + S_(n+1)
Thus, if the original sequence is represented as a stream of values, the transformed sequence is given by
s_00 s_01 s_02 s_03 s_04 ...
s_10 s_11 s_12 s_13 ...
s_20 s_21 s_22 ...
...
Finally, we form a sequence by taking the first term in each row of the tableau:
1 1 1
ln 2 = 1 - --- + --- - --- + ...
2 3 4
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?
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 procedure of section 2.2.3 to produce the stream of pairs of all integers (i,j) with i <= j such that i + j is prime. If int-pairs is the sequence of all pairs of integers (i,j) with i <= j, then our required stream is simply@footnote{As in section 2.2.3, we represent a pair of integers as a list rather than a Lisp pair.}
(S_0, T_0) (S_0, T_1) (S_0, T_2) ...
(S_1, T_0) (S_1, T_1) (S_1, T_2) ...
(S_2, T_0) (S_2, T_1) (S_2, T_2) ...
...
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
(S_0, T_0) (S_0, T_1) (S_0, T_2) ...
(S_1, T_1) (S_1, T_2) ...
(S_2, T_2) ...
...
(If we take both S and T to be the stream of integers, then this will be our desired stream int-pairs.)
Call the general stream of pairs (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:@footnote{See Exercise 3-68 for some insight into why we chose this decomposition.}
(S_0, T_0) | (S_0, T_1) (S_0, T_2) ...
-----------+-----------------------------
| (S_1, T_1) (S_1, T_2) ...
| (S_2, T_2) ...
| ...
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) and (stream-cdr T). Also note that the second piece (the rest of the first row) is
@item
the stream of all pairs of positive integers (i,j) with i <= j
ordered according to the sum i + j
@item
the stream of all pairs of positive integers (i,j) with i <= 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.
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
i
---
S_i = C + > x_j dt
---
j=1
and returns the stream of values S = (S_i). The following integral procedure is reminiscent of the ``implicit style'' definition of the stream of integers (section 3.5.2):
initial-value
|
+-----------+ | |\__
input | | |\__ +-->| \_ integral
------>| scale: dt +----->| \_ |cons_>--*------->
| | | add_>---->| __/ |
+-----------+ +-->| __/ |/ |
| |/ |
| |
+------------------------+
+ -
->----'\/\/\,---| |---
i C
/ t
| i
v = v + | dt + R i
0 |
/ 0
+--------------+
+-->| scale: R |---------------------+ |\_
| +--------------+ | | \_
| +-->| \ v
i | +--------------+ +------------+ | add >--->
----+-->| scale: 1/C |---->| integral |----->| _/
+--------------+ +------------+ | _/
|/
3.5.4 Streams and Delayed Evaluation
The integral procedure at the end of the preceding section shows how we can use streams to model signal-processing systems that contain feedback loops. The feedback loop for the adder shown in Figure 3-32 is modeled by the fact that integral's internal stream int is defined in terms of itself:
y_0
|
V
+----------+ dy +----------+ y
+-->| map: f +------>| integral +--*----->
| +----------+ +----------+ |
| |
+------------------------------------+
dy_0 y_0
| |
V V
ddy +----------+ dy +----------+ y
+--------->| integral +-----*--+ integral +--*--->
| +----------+ | +----------+ |
| | |
| +----------+ | |
| __/|<--+ scale: a |<--+ |
| _/ | +----------+ |
+--<_add | |
\__ | +----------+ |
\|<--+ scale: b |<-------------------+
+----------+
d^2 y d y
----- - a ----- - by = 0
d t^2 d t
The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d^2y/dt^2 depends upon the values of y and dy/dt and both of these are determined by integrating d^2y/dt^2. The diagram we would like to encode is shown in Figure 3-35. Write a procedure solve-2nd that takes as arguments the constants a, b, and dt and the initial values y_0 and dy_0 for y and dy/dt and generates the stream of successive values of y.
v_R = i_R R
d_(i L)
v_L = L ---------
d t
d v_C
i_C = C -------
d t
and the circuit connections dictate the relations
i_R = i_L = -i_C
v_C = v_L + v_R
Combining these equations shows that the state of the circuit (summarized by v_C, the voltage across the capacitor, and i_L, the current in the inductor) is described by the pair of differential equations
d v_C i_L
----- = - ---
d t C
d i_L 1 R
----- = --- v_C - --- i_L
d t L L
The signal-flow diagram representing this system of differential equations is shown in Figure 3-37.
Figure 3.36: A series RLC circuit.
+ v_R -
i_R
+--->----'\/\/\,--------+
| | i_L
\|/ R \|/
+ | i_C |_ +
-+- __)
v_C -+- C (_) v_L
| __)
- | | -
+-----------------------+
+-------------+
+----------------+ scale: l/L |<--+
| +-------------+ |
| |
| +-------------+ | v_C
| dv_C +-->| integral +---*------>
| | +-------------+
| | ^
| | | v_(C_0)
| |
| | +-------------+
| +---+ scale: -l/C |<--+
| +-------------+ |
| |\__ |
+->| \_ di_L +-------------+ | i_L
| add_>------>| integral +---*------>
+->| __/ +-------------+ |
| |/ ^ |
| | i_(L_0) |
| |
| +-------------+ |
+----------------+ scale: -R/L |<--+
+-------------+
Normal-order evaluation
The examples in this section illustrate how the explicit use of delay and force provides great programming flexibility, but the same examples also show how this can make our programs more complex. Our new integral procedure, for instance, gives us the power to model systems with loops, but we must now remember that integral should be called with a delayed integrand, and every procedure that uses integral must be aware of this. In effect, we have created two classes of procedures: ordinary procedures and procedures that take delayed arguments. In general, creating separate classes of procedures forces us to create separate classes of higher-order procedures as well.@footnote{This is a small reflection, in Lisp, of the difficulties that conventional strongly typed languages such as Pascal have in coping with higher-order procedures. In such languages, the programmer must specify the data types of the arguments and the result of each procedure: number, logical value, sequence, and so on. Consequently, we could not express an abstraction such as ``map a given procedure proc over all the elements in a sequence'' by a single higher-order procedure such as stream-map. Rather, we would need a different mapping procedure for each different combination of argument and result data types that might be specified for a proc. Maintaining a practical notion of ``data type'' in the presence of higher-order procedures raises many difficult issues. One way of dealing with this problem is illustrated by the language ML (Gordon, Milner, and Wadsworth 1979), whose ``polymorphic data types'' include templates for higher-order transformations between data types. Moreover, data types for most procedures in ML are never explicitly declared by the programmer. Instead, ML includes a type-inferencing mechanism that uses information in the environment to deduce the data types for newly defined procedures.}
One way to avoid the need for two different classes of procedures is to make all procedures take delayed arguments. We could adopt a model of evaluation in which all arguments to procedures are automatically delayed and arguments are forced only when they are actually needed (for example, when they are required by a primitive operation). This would transform our language to use normal-order evaluation, which we first described when we introduced the substitution model for evaluation in section 1.1.5. Converting to normal-order evaluation provides a uniform and elegant way to simplify the use of delayed evaluation, and this would be a natural strategy to adopt if we were concerned only with stream processing. In section 4.2, after we have studied the evaluator, we will see how to transform our language in just this way. Unfortunately, including delays in procedure calls wreaks havoc with our ability to design programs that depend on the order of events, such as programs that use assignment, mutate data, or perform input or output. Even the single delay in cons-stream can cause great confusion, as illustrated by Exercise 3-51 and Exercise 3-52. As far as anyone knows, mutability and delayed evaluation do not mix well in programming languages, and devising ways to deal with both of these at once is an active area of research.
3.5.5 Modularity of Functional Programs and Modularity of Objects
As we saw in section 3.1.2, one of the major benefits of introducing assignment is that we can increase the modularity of our systems by encapsulating, or ``hiding,'' parts of the state of a large system within local variables. Stream models can provide an equivalent modularity without the use of assignment. As an illustration, we can reimplement the Monte Carlo estimation of [pi], which we examined in section 3.1.2, from a stream-processing point of view.
The key modularity issue was that we wished to hide the internal state of a random-number generator from programs that used random numbers. We began with a procedure rand-update, whose successive values furnished our supply of random numbers, and used this to produce a random-number generator:
A functional-programming view of time
Let us now return to the issues of objects and state that were raised at the beginning of this chapter and examine them in a new light. We introduced assignment and mutable objects to provide a mechanism for modular construction of programs that model systems with state. We constructed computational objects with local state variables and used assignment to modify these variables. We modeled the temporal behavior of the objects in the world by the temporal behavior of the corresponding computational objects.
Now we have seen that streams provide an alternative way to model objects with local state. We can model a changing quantity, such as the local state of some object, using a stream that represents the time history of successive states. In essence, we represent time explicitly, using streams, so that we decouple time in our simulated world from the sequence of events that take place during evaluation. Indeed, because of the presence of delay there may be little relation between simulated time in the model and the order of events during the evaluation.
In order to contrast these two approaches to modeling, let us reconsider the implementation of a ``withdrawal processor'' that monitors the balance in a bank account. In section 3.1.3 we implemented a simplified version of such a processor:
Peter's requests +---------+ +---------+
------------------>| | | |
Paul's requests | merge |---->| bank |---->
------------------>| | | account |
+---------+ +---------+
Notes
Based on Structure and Interpretation of Computer Programs, a work at https://mitpress.mit.edu/sicp/.
