Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
Structure and Interpretation of Computer Programs (69 page)
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:
(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))
Calls to
make-simplified-withdraw
produce computational objects,
each with a local state variable
balance
that is decremented by
successive calls to the object. The object takes an
amount
as
an argument and returns the new balance. We can imagine the user of a
bank account typing a sequence of inputs to such an object and
observing the sequence of returned values shown on a display screen.
Alternatively, we can model a withdrawal processor as a procedure that
takes as input a balance and a stream of amounts to withdraw and
produces the stream of successive balances in the account:
(define (stream-withdraw balance amount-stream)
(cons-stream
balance
(stream-withdraw (- balance (stream-car amount-stream))
(stream-cdr amount-stream))))
Stream-withdraw
implements a well-defined mathematical function whose
output is fully determined by its input. Suppose, however, that the
input
amount-stream
is the stream of successive values typed by
the user and that the resulting stream of balances is displayed.
Then, from the perspective of the user who is typing values and
watching results, the stream process has the same behavior as the
object created by
make-simplified-withdraw
. However, with the
stream version, there is no assignment, no local state variable, and
consequently none of the theoretical difficulties that we encountered
in section
3.1.3
. Yet the system has state!
This is really remarkable. Even though
stream-withdraw
implements a
well-defined mathematical function whose behavior does not change, the
user's perception here is one of interacting with a system that has a
changing state. One way to resolve this paradox is to realize that it
is the user's temporal existence that imposes state on the system. If
the user could step back from the interaction and think in terms of
streams of balances rather than individual transactions, the system
would appear stateless.
73
From the point of view of one part of a complex process, the other
parts appear to change with time. They have hidden time-varying local
state. If we wish to write programs that model this kind of natural
decomposition in our world (as we see it from our viewpoint as a part of
that world) with
structures in our computer, we make computational objects that are not
functional – they must change with time. We model state with local
state variables, and we model the changes of state with assignments to
those variables. By doing this we make the time of execution of a
computation model time in the world that we are part of, and thus we
get “objects” in our computer.
Modeling with objects is powerful and intuitive, largely because this
matches the perception of interacting with a world of which we are
part. However, as we've seen repeatedly throughout this chapter,
these models raise thorny problems of constraining the order of events
and of synchronizing multiple processes. The possibility of avoiding
these problems has stimulated the development of
functional
programming languages
, which do not include any provision for
assignment or mutable data. In such a language, all procedures
implement well-defined mathematical functions of their arguments,
whose behavior does not change. The functional approach is extremely
attractive for dealing with concurrent systems.
74
On the other hand, if we look closely, we can see time-related
problems creeping into functional models as well. One particularly
troublesome area arises when we wish to design interactive systems,
especially ones that model interactions between independent entities.
For instance, consider once more the implementation a banking system
that permits joint bank accounts. In a conventional system using
assignment and objects, we would model the fact that Peter and Paul
share an account by having both Peter and Paul send their transaction
requests to the same bank-account object, as we saw in
section
3.1.3
.
From the stream point of view, where there are no “objects”
per
se
, we have already indicated that a bank account can be modeled as a
process that operates on a stream of transaction requests to produce a
stream of responses. Accordingly, we could model the fact that Peter
and Paul have a joint bank account by merging Peter's stream of
transaction requests with Paul's stream of requests and feeding the
result to the bank-account stream process, as shown in
figure
3.38
.
 |
The trouble with this formulation is in the notion of
merge
. It
will not do to merge the two streams by simply taking alternately one
request from Peter and one request from Paul. Suppose Paul accesses
the account only very rarely. We could hardly force Peter to wait for
Paul to access the account before he could issue a second transaction.
However such a merge is implemented, it must interleave the two
transaction streams in some way that is constrained by “real
time” as perceived by Peter and Paul, in the sense that, if Peter and
Paul meet, they can agree that certain transactions were processed
before the meeting, and other transactions were processed after the
meeting.
75
This is precisely the same constraint that we had to deal with in
section
3.4.1
, where we found the need to introduce
explicit synchronization to ensure a “correct” order of events in
concurrent processing of objects with state. Thus, in an attempt to
support the functional style, the need to merge inputs from different
agents reintroduces the same problems that the functional style was
meant to eliminate.
We began this chapter with the goal of building computational models
whose structure matches our perception of the real world we are trying
to model. We can model the world as a collection of separate,
time-bound, interacting objects with state, or we can model the world
as a single, timeless, stateless unity. Each view has powerful
advantages, but neither view alone is completely satisfactory. A
grand unification has yet to emerge.
76
52
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
.
53
Assume that we have a
predicate
prime?
(e.g., as in section
1.2.6
) that
tests for primality.
54
In the MIT implementation,
the-empty-stream
is the
same as the empty list
'()
, and
stream-null?
is the same
as
null?
.
55
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.
56
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
<
a
> <
b
>)
would automatically cause <
b
> to be evaluated, which is
precisely what we do not want to happen. For the same reason,
delay
must be a special form, though
force
can be an ordinary
procedure.
57
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.
58
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
.
59
Exercises such as
3.51
and
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.
60
Eratosthenes, a third-century
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
.
61
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.
62
This uses the generalized version
of
stream-map
from exercise
3.50
.
63
This last point is
very subtle and relies on the fact that
p
n
+1
<
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
<
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
<
2
p
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.
64
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.
65
We can't use
let
to bind the local variable
guesses
, because the value of
guesses
depends on
guesses
itself. Exercise
3.63
addresses why
we want a local variable here.
66
As in section
2.2.3
,
we represent a pair of integers as a list rather than a Lisp pair.
67
See exercise
3.68
for some insight
into why we chose this decomposition.
68
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).
69
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.
70
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.
71
This procedure is not guaranteed to work in all Scheme
implementations, although for any implementation there is a simple
variation that will work. The problem has to do with subtle
differences in the ways that Scheme implementations handle internal
definitions. (See section
4.1.6
.)
72
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.
73
Similarly in physics, when we observe a moving particle, we
say that the position (state) of the particle is changing. However,
from the perspective of the particle's
world line in space-time there
is no change involved.
74
John Backus, the inventor of Fortran, gave high
visibility to functional programming when he was awarded
the ACM Turing award in 1978. His acceptance speech (Backus 1978)
strongly advocated the functional approach. A good overview of
functional programming is given in Henderson 1980 and in Darlington,
Henderson, and Turner 1982.
75
Observe that, for any two streams, there is in general more than one
acceptable order of interleaving. Thus, technically, “merge” is a
relation rather than a function – the answer is not a deterministic
function of the inputs. We already mentioned
(footnote
39
) that nondeterminism is
essential when dealing with concurrency. The merge relation
illustrates the same essential nondeterminism, from the functional
perspective. In section
4.3
, we
will look at nondeterminism from yet another point of view.
76
The object model approximates the world by
dividing it into separate pieces. The functional model does not
modularize along object boundaries. The object model is useful when
the unshared state of the “objects” is much larger than the state
that they share. An example of a place where the object viewpoint
fails is
quantum
mechanics, where thinking of things as individual particles leads to
paradoxes and confusions. Unifying the object view with the
functional view may have little to do with programming, but rather
with fundamental epistemological issues.
