((protected (lambda () balance)))) ; serialized
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
because allowing unserialized access to the bank balance can result in
anomalous behavior. Do you agree? Is there any scenario that demonstrates
Ben's concern?
Exercise 3.42: Ben Bitdiddle suggests that it's
a waste of time to create a new serialized procedure in response to every
withdraw and deposit message. He says that make-account
could be changed so that the calls to protected are done outside the
dispatch procedure. That is, an account would return the same
serialized procedure (which was created at the same time as the account) each
time it is asked for a withdrawal procedure.
Is this a safe change to make? In particular, is there any difference in what
concurrency is allowed by these two versions of make-account ?
Complexity of using multiple shared resources
Serializers provide a powerful abstraction that helps isolate the complexities
of concurrent programs so that they can be dealt with carefully and (hopefully)
correctly. However, while using serializers is relatively straightforward when
there is only a single shared resource (such as a single bank account),
concurrent programming can be treacherously difficult when there are multiple
shared resources.
To illustrate one of the difficulties that can arise, suppose we wish to swap
the balances in two bank accounts. We access each account to find the balance,
compute the difference between the balances, withdraw this difference from one
account, and deposit it in the other account. We could implement this as
follows:
We have simplified exchange by exploiting the fact
that our deposit message accepts negative amounts. (This is a serious
bug in our banking system!)
This procedure works well when only a single process is trying to do the
exchange. Suppose, however, that Peter and Paul both have access to accounts
a1, a2, and a3, and that Peter exchanges a1 and a2 while
Paul concurrently exchanges a1 and a3. Even with account deposits and
withdrawals serialized for individual accounts (as in the make-account
procedure shown above in this section), exchange can still produce
incorrect results. For example, Peter might compute the difference in the
balances for a1 and a2, but then Paul might change the balance in
a1 before Peter is able to complete the exchange.
If the account
balances start out as $10, $20, and $30, then after any number of concurrent
exchanges, the balances should still be $10, $20, and $30 in some order.
Serializing the deposits to individual accounts is not sufficient to guarantee
this. See Exercise 3-43.
For correct behavior, we must arrange for the
exchange procedure to lock out any other concurrent accesses to the
accounts during the entire time of the exchange.
One way we can accomplish this is by using both accounts' serializers to
serialize the entire exchange procedure. To do this, we will arrange
for access to an account's serializer. Note that we are deliberately breaking
the modularity of the bank-account object by exposing the serializer. The
following version of make-account is identical to the original version
given in section 3-1-1, except that a serializer is provided to protect
the balance variable, and the serializer is exported via message passing:
We can use this to do serialized deposits and withdrawals. However, unlike our
earlier serialized account, it is now the responsibility of each user of
bank-account objects to explicitly manage the serialization, for example as
follows:
Exercise 3-45 investigates why deposits and withdrawals
are no longer automatically serialized by the account.
Exporting the serializer in this way gives us enough flexibility to implement a
serialized exchange program. We simply serialize the original exchange
procedure with the serializers for both accounts:
Exercise 3.43: Suppose that the balances in
three accounts start out as $10, $20, and $30, and that multiple processes run,
exchanging the balances in the accounts. Argue that if the processes are run
sequentially, after any number of concurrent exchanges, the account balances
should be $10, $20, and $30 in some order. Draw a timing diagram like the one
in Figure 3-29 to show how this condition can be violated if the
exchanges are implemented using the first version of the account-exchange
program in this section. On the other hand, argue that even with this
exchange program, the sum of the balances in the accounts will be
preserved. Draw a timing diagram to show how even this condition would be
violated if we did not serialize the transactions on individual accounts.
Exercise 3.44: Consider the problem of
transferring an amount from one account to another. Ben Bitdiddle claims that
this can be accomplished with the following procedure, even if there are
multiple people concurrently transferring money among multiple accounts, using
any account mechanism that serializes deposit and withdrawal transactions, for
example, the version of make-account in the text above.
Louis Reasoner claims that there is a problem here, and that we need to use a
more sophisticated method, such as the one required for dealing with the
exchange problem. Is Louis right? If not, what is the essential difference
between the transfer problem and the exchange problem? (You should assume that
the balance in from-account is at least amount .)
Exercise 3.45: Louis Reasoner thinks our
bank-account system is unnecessarily complex and error-prone now that deposits
and withdrawals aren't automatically serialized. He suggests that
make-account-and-serializer should have exported the serializer (for use
by such procedures as serialized-exchange ) in addition to (rather than
instead of) using it to serialize accounts and deposits as make-account
did. He proposes to redefine accounts as follows:
Explain what is wrong with Louis's reasoning. In particular, consider what
happens when serialized-exchange is called.
Implementing serializers
We implement serializers in terms of a more primitive synchronization mechanism
called a mutex
. A mutex is an object that supports two
operations---the mutex can be acquired
, and the mutex can be
released
. Once a mutex has been acquired, no other acquire
operations on that mutex may proceed until the mutex is released.
The
term ``mutex'' is an abbreviation for mutual exclusion
. The general
problem of arranging a mechanism that permits concurrent processes to safely
share resources is called the mutual exclusion problem. Our mutex is a simple
variant of the semaphore
mechanism (see Exercise 3-47), which
was introduced in the ``THE'' Multiprogramming System developed at the
Technological University of Eindhoven and named for the university's initials
in Dutch (Dijkstra 1968a). The acquire and release operations were originally
called P and V, from the Dutch words passeren (to pass) and
vrijgeven (to release), in reference to the semaphores used on railroad
systems. Dijkstra's classic exposition (1968b) was one of the first to clearly
present the issues of concurrency control, and showed how to use semaphores to
handle a variety of concurrency problems.
In our implementation, each
serializer has an associated mutex. Given a procedure p , the serializer
returns a procedure that acquires the mutex, runs p , and then releases
the mutex. This ensures that only one of the procedures produced by the
serializer can be running at once, which is precisely the serialization
property that we need to guarantee.
The mutex is a mutable object (here we'll use a one-element list, which we'll
refer to as a cell
) that can hold the value true or false. When the
value is false, the mutex is available to be acquired. When the value is true,
the mutex is unavailable, and any process that attempts to acquire the mutex
must wait.
Our mutex constructor make-mutex begins by initializing the cell
contents to false. To acquire the mutex, we test the cell. If the mutex is
available, we set the cell contents to true and proceed. Otherwise, we wait in
a loop, attempting to acquire over and over again, until we find that the mutex
is available.
In most time-shared operating systems, processes that
are blocked by a mutex do not waste time ``busy-waiting'' as above. Instead,
the system schedules another process to run while the first is waiting, and the
blocked process is awakened when the mutex becomes available.
To release the
mutex, we set the cell contents to false.
Test-and-set! tests the cell and returns the result of the test. In
addition, if the test was false, test-and-set! sets the cell contents to
true before returning false. We can express this behavior as the following
procedure:
However, this implementation of test-and-set! does not suffice as it
stands. There is a crucial subtlety here, which is the essential place where
concurrency control enters the system: The test-and-set! operation must
be performed atomically
. That is, we must guarantee that, once a
process has tested the cell and found it to be false, the cell contents will
actually be set to true before any other process can test the cell. If we do
not make this guarantee, then the mutex can fail in a way similar to the
bank-account failure in Figure 3-29. (See Exercise 3-46.)
The actual implementation of test-and-set! depends on the details of how
our system runs concurrent processes. For example, we might be executing
concurrent processes on a sequential processor using a time-slicing mechanism
that cycles through the processes, permitting each process to run for a short
time before interrupting it and moving on to the next process. In that case,
test-and-set! can work by disabling time slicing during the testing and
setting.
In @acronym{MIT
Scheme for a single processor, which uses a
time-slicing model, test-and-set! can be implemented as follows:
Without-interrupts disables time-slicing interrupts while its procedure
argument is being executed.} Alternatively, multiprocessing computers provide
instructions that support atomic operations directly in
hardware.
There are many variants of such instructions---including
test-and-set, test-and-clear, swap, compare-and-exchange, load-reserve, and
store-conditional---whose design must be carefully matched to the machine's
processor-memory interface. One issue that arises here is to determine what
happens if two processes attempt to acquire the same resource at exactly the
same time by using such an instruction. This requires some mechanism for
making a decision about which process gets control. Such a mechanism is called
an arbiter
. Arbiters usually boil down to some sort of hardware
device. Unfortunately, it is possible to prove that one cannot physically
construct a fair arbiter that works 100% of the time unless one allows the
arbiter an arbitrarily long time to make its decision. The fundamental
phenomenon here was originally observed by the fourteenth-century French
philosopher Jean Buridan in his commentary on Aristotle's De caelo.
Buridan argued that a perfectly rational dog placed between two equally
attractive sources of food will starve to death, because it is incapable of
deciding which to go to first.
Exercise 3.46: Suppose that we implement
test-and-set! using an ordinary procedure as shown in the text, without
attempting to make the operation atomic. Draw a timing diagram like the one in
Figure 3-29 to demonstrate how the mutex implementation can fail by
allowing two processes to acquire the mutex at the same time.
Exercise 3.47: A semaphore (of size n) is a
generalization of a mutex. Like a mutex, a semaphore supports acquire and
release operations, but it is more general in that up to n processes can
acquire it concurrently. Additional processes that attempt to acquire the
semaphore must wait for release operations. Give implementations of semaphores
in terms of mutexes
in terms of atomic test-and-set! operations.
Deadlock
Now that we have seen how to implement serializers, we can see that account
exchanging still has a problem, even with the serialized-exchange
procedure above. Imagine that Peter attempts to exchange a1 with a2
while Paul concurrently attempts to exchange a2 with a1. Suppose that
Peter's process reaches the point where it has entered a serialized procedure
protecting a1 and, just after that, Paul's process enters a serialized
procedure protecting a2. Now Peter cannot proceed (to enter a serialized
procedure protecting a2) until Paul exits the serialized procedure
protecting a2. Similarly, Paul cannot proceed until Peter exits the
serialized procedure protecting a1. Each process is stalled forever,
waiting for the other. This situation is called a deadlock
.
Deadlock is always a danger in systems that provide concurrent access to
multiple shared resources.
One way to avoid the deadlock in this situation is to give each account a
unique identification number and rewrite serialized-exchange so that a
process will always attempt to enter a procedure protecting the lowest-numbered
account first. Although this method works well for the exchange problem, there
are other situations that require more sophisticated deadlock-avoidance
techniques, or where deadlock cannot be avoided at all. (See Exercise
3-48 and Exercise 3-49.)
The general technique for avoiding
deadlock by numbering the shared resources and acquiring them in order is due
to Havender (1968). Situations where deadlock cannot be avoided require
deadlock-recovery
methods, which entail having processes ``back out''
of the deadlocked state and try again. Deadlock-recovery mechanisms are widely
used in database management systems, a topic that is treated in detail in Gray
and Reuter 1993.
Exercise 3.48: Explain in detail why the
deadlock-avoidance method described above, (i.e., the accounts are numbered,
and each process attempts to acquire the smaller-numbered account first) avoids
deadlock in the exchange problem. Rewrite serialized-exchange to
incorporate this idea. (You will also need to modify make-account so
that each account is created with a number, which can be accessed by sending an
appropriate message.)
Exercise 3.49: Give a scenario where the
deadlock-avoidance mechanism described above does not work. (Hint: In the
exchange problem, each process knows in advance which accounts it will need to
get access to. Consider a situation where a process must get access to some
shared resources before it can know which additional shared resources it will
require.)
Concurrency, time, and communication
We've seen how programming concurrent systems requires controlling the ordering
of events when different processes access shared state, and we've seen how to
achieve this control through judicious use of serializers. But the problems of
concurrency lie deeper than this, because, from a fundamental point of view,
it's not always clear what is meant by ``shared state.''
Mechanisms such as test-and-set! require processes to examine a global
shared flag at arbitrary times. This is problematic and inefficient to
implement in modern high-speed processors, where due to optimization techniques
such as pipelining and cached memory, the contents of memory may not be in a
consistent state at every instant. In contemporary multiprocessing systems,
therefore, the serializer paradigm is being supplanted by new approaches to
concurrency control.
One such alternative to serialization is called
barrier synchronization
. The programmer permits concurrent processes
to execute as they please, but establishes certain synchronization points
(``barriers'') through which no process can proceed until all the processes
have reached the barrier. Modern processors provide machine instructions that
permit programmers to establish synchronization points at places where
consistency is required. The PowerPC^( TM), for example, includes for
this purpose two instructions called SYNC and EIEIO (Enforced In-order
Execution of Input/Output).
The problematic aspects of shared state also arise in large, distributed
systems. For instance, imagine a distributed banking system where individual
branch banks maintain local values for bank balances and periodically compare
these with values maintained by other branches. In such a system the value of
``the account balance'' would be undetermined, except right after
synchronization. If Peter deposits money in an account he holds jointly with
Paul, when should we say that the account balance has changed---when the
balance in the local branch changes, or not until after the synchronization?
And if Paul accesses the account from a different branch, what are the
reasonable constraints to place on the banking system such that the behavior is
``correct''? The only thing that might matter for correctness is the behavior
observed by Peter and Paul individually and the ``state'' of the account
immediately after synchronization. Questions about the ``real'' account
balance or the order of events between synchronizations may be irrelevant or
meaningless.
This may seem like a strange point of view, but there are
systems that work this way. International charges to credit-card accounts, for
example, are normally cleared on a per-country basis, and the charges made in
different countries are periodically reconciled. Thus the account balance may
be different in different countries.
The basic phenomenon here is that synchronizing different processes,
establishing shared state, or imposing an order on events requires
communication among the processes. In essence, any notion of time in
concurrency control must be intimately tied to communication.
For
distributed systems, this perspective was pursued by Lamport (1978), who showed
how to use communication to establish ``global clocks'' that can be used to
establish orderings on events in distributed systems.
It is intriguing that a
similar connection between time and communication also arises in the Theory of
Relativity, where the speed of light (the fastest signal that can be used to
synchronize events) is a fundamental constant relating time and space. The
complexities we encounter in dealing with time and state in our computational
models may in fact mirror a fundamental complexity of the physical universe.
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.
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.
@menu
* 3-5-1:: Streams Are Delayed Lists
* 3-5-2:: Infinite Streams
* 3-5-3:: Exploiting the Stream Paradigm
* 3-5-4:: Streams and Delayed Evaluation
* 3-5-5:: Modularity of Functional Programs and Modularity of
Objects
@end menu
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:
Assume that we have a predicate prime? (e.g.,
as in section 1-2-6) that tests for primality.
(define (sum-primes a b)
(define (iter count accum)
(cond ((> count b) accum)
((prime? count) (iter (+ count 1) (+ count accum)))
(else (iter (+ count 1) accum))))
(iter a 0))
The second program performs the same computation using the sequence operations
of section 2-2-3:
(define (sum-primes a b)
(accumulate +
0
(filter prime? (enumerate-interval a b))))
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? .
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 :
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 >) does not evaluate the
expression , but rather returns a so-called delayed
object
, which we can think of as a ``promise'' to evaluate at some
future time. As a companion to delay , there is a procedure called
force that takes a delayed object as argument and performs the
evaluation---in effect, forcing the delay to fulfill its promise. We
will see below how delay and force can be implemented, but first
let us use these to construct streams.
Cons-stream is a special form defined so that
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.
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 > <@var{b>)
would
automatically cause 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.}
The stream implementation in action
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
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):
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(stream-filter pred
(stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream)))))
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
(cons-stream (stream-car stream)
(stream-filter pred (stream-cdr stream)))
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.
Implementing delay and force
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
(delay )
is syntactic sugar for
(lambda () )
Force simply calls the procedure (of no arguments) produced by
delay , so we can implement force as a procedure:
(define (force delayed-object)
(delayed-object))
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 >) is equivalent
to
(memo-proc (lambda () ))
and force is as defined previously.
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:
(define (show x)
(display-line x)
x)
What does the interpreter print in response to evaluating each expression in
the following sequence?
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.
(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)
Exercise 3.52: Consider the sequence of
expressions
(define sum 0)
(define (accum x)
(set! sum (+ x sum))
sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
seq))
(stream-ref y 7)
(display-stream z)
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 >) simply as (lambda () >)
without using the optimization provided by memo-proc ? Explain
Infinite Streams
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:
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
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:
(define (divisible? x y) (= (remainder x y) 0))
(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:
(stream-ref no-sevens 100)
117
In analogy with integers , we can define the infinite stream of Fibonacci
numbers:
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
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
.
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:
(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-31.
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 ``un cons er'' 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
cons ed 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.
Figure 3.31: The prime sieve viewed as a
signal-processing system.
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:
(define ones (cons-stream 1 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:
This uses the generalized version of stream-map from
Exercise 3-50.
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:
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)).
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.
Exercise 3.53: Without running the program,
describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
Exercise 3.54: Define a procedure
mul-streams , analogous to add-streams , that produces the
elementwise product of its two input streams. Use this together with the
stream of integers to complete the following definition of the stream
whose nth element (counting from 0) is n + 1 factorial:
Exercise 3.55: Define a procedure
partial-sums that takes as argument a stream S and returns the
stream whose elements are S_0, S_0 + S_1, S_0 + S_1 +
S_2, .... For example, (partial-sums integers) should be the
stream 1, 3, 6, 10, 15, ....
Exercise 3.56: A famous problem, first raised by
R. Hamming, is to enumerate, in ascending order with no repetitions, all
positive integers with no prime factors other than 2, 3, or 5. One obvious way
to do this is to simply test each integer in turn to see whether it has any
factors other than 2, 3, and 5. But this is very inefficient, since, as the
integers get larger, fewer and fewer of them fit the requirement. As an
alternative, let us call the required stream of numbers S and notice the
following facts about it.
S begins with 1.
The elements of (scale-stream S 2) are also
elements of S .
The same is true for (scale-stream S 3)
and (scale-stream 5 S) .
These are all the elements of S .
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:
Then the required stream may be constructed with merge , as follows:
(define S (cons-stream 1 (merge ?> ?>)))
Fill in the missing expressions in the places marked ?> above.
Exercise 3.57: How many additions are performed
when we compute the nth 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
>) simply as (lambda () >), without using the
optimization provided by the memo-proc procedure described in section
3-5-1.
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.
Exercise 3.58: Give an interpretation of the
stream computed by the following procedure:
(define (expand num den radix)
(cons-stream
(quotient (* num radix) den)
(expand (remainder (* num radix) den) den radix)))
( Quotient is a primitive that returns the integer quotient of two
integers.) What are the successive elements produced by (expand 1 7
10) ? What is produced by (expand 3 8 10) ?
Exercise 3.59: 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
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, ....
The integral of the series a_0 + a_1 x + a_2 x^2 + a_3
x^3 + ... is the series
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.)
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
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.60: With power series represented as
streams of coefficients as in Exercise 3-59, adding series is implemented
by add-streams . Complete the definition of the following procedure for
multiplying series:
You can test your procedure by verifying that sin^2 x +
cos^2 x = 1, using the series from Exercise 3-59.
 Suppose we want to find the
power series 1/S, that is, the series X such that S * 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:
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.
Exercise 3.62: Use the results of Exercise
3-60 and Exercise 3-61 to define a procedure div-series that
divides two power series. Div-series should work for any two series,
provided that the denominator series begins with a nonzero constant term. (If
the denominator has a zero constant term, then div-series should signal
an error.) Show how to use div-series together with the result of
Exercise 3-59 to generate the power series for tangent.
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:
(define (sqrt-improve guess x)
(average guess (/ x guess)))
In our original sqrt procedure, 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:
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.
We can generate more and more terms of the stream to get better and better
guesses. If we like, we can write a procedure that keeps generating terms
until the answer is good enough. (See Exercise 3-64.)
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:
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:
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 nth term of the original sum sequence, then the
accelerated sequence has terms
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:
(define (make-tableau transform s)
(cons-stream s
(make-tableau transform
(transform s))))
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.
Exercise 3.63: Louis Reasoner asks why the
sqrt-stream procedure was not written in the following more
straightforward way, without the local variable guesses :
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 () >) without
using the optimization provided by memo-proc (section 3-5-1)?
Exercise 3.64: Write a procedure
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
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
Exercise 3.65: Use the series
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
As in section
2-2-3, we represent a pair of integers as a list rather than a Lisp
pair.
Our problem, then, is to produce the stream int-pairs . More generally,
suppose we have two streams S = (S_i) and T = (T_j),
and imagine the infinite rectangular array
(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:
See Exercise 3-68 for
some insight into why we chose this decomposition.
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
In order to complete the procedure, we must choose some way to combine the two
inner streams. One idea is to use the stream analog of the append
procedure 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
(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
interleave procedure:
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).
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.66: Examine the stream (pairs
integers integers) . Can you make any general comments about the order in which
the pairs are placed into the stream? For example, about 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.)
Exercise 3.67: Modify the pairs procedure
so that (pairs integers integers) will produce the stream of all
pairs of integers (i,j) (without the condition i <= j). Hint:
You will need to mix in an additional stream.
Exercise 3.68: 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) using Louis's definition of pairs .
Exercise 3.69: Write a procedure triples
that takes three infinite streams, S, T, and U, and produces the
stream of triples (S_i,T_j,U_k) such that i <=
j <= k. Use triples to generate the stream of all Pythagorean
triples of positive integers, i.e., the triples (i,j,k) such that
i <= j and i^2 + j^2 = k^2.
Exercise 3.70: 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 merge procedure of Exercise 3-56, 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-weighted that is like merge , except that
merge-weighted takes an additional argument weight , which is a
procedure that computes the weight of a pair, and is used to determine the
order in which elements should appear in the resulting merged
stream.
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.
Using this, generalize pairs to a procedure
weighted-pairs that takes two streams, together with a procedure that
computes a weighting function, and generates the stream of pairs, ordered
according to weight. Use your procedure to generate
the stream of all pairs of positive integers (i,j) with i <= j
ordered according to the sum i + j
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.
Exercise 3.71: 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.
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.
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-70), then search the stream for two
consecutive pairs with the same weight. Write a procedure to generate the
Ramanujan numbers. The first such number is 1,729. What are the next five?
Exercise 3.72: In a similar way to Exercise
3-71 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).
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):
Figure 3-32 is a picture of a signal-processing system that corresponds
to the integral procedure. 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 int is reflected in the figure
by the feedback loop that connects the output of the adder to one of the
inputs.
Figure 3.32: The integral procedure viewed
as a signal-processing system.
Exercise 3.73: 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-33, whose structure is shown by the
accompanying signal-flow diagram.
Write a procedure RC that models this circuit. RC should take as
inputs the values of R, C, and dt and should return a procedure
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)) . This defines RC1 as a
procedure that takes a stream representing the time sequence of currents and an
initial capacitor voltage and produces the output stream of voltages.
Figure 3.33: An RC circuit and the associated
signal-flow diagram.
+ -
->----'\/\/\,---| |---
i C
/ t
| i
v = v + | dt + R i
0 |
/ 0
+--------------+
+-->| scale: R |---------------------+ |\_
| +--------------+ | | \_
| +-->| \ v
i | +--------------+ +------------+ | add >--->
----+-->| scale: 1/C |---->| integral |----->| _/
+--------------+ +------------+ | _/
|/
Exercise 3.74: 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-data and the stream zero-crossings is the corresponding
stream of zero crossings. Alyssa first writes a procedure
sign-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:
Exercise 3.75: Unfortunately, Alyssa's
zero-crossing detector in Exercise 3-74 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 .)
Exercise 3.76: Eva Lu Ator has a criticism of
Louis's approach in Exercise 3-75. 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
procedure smooth 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.
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:
(define int
(cons-stream initial-value
(add-streams (scale-stream integrand dt)
int)))
The interpreter's ability to deal with such an implicit definition depends on
the delay that is incorporated into cons-stream . Without this
delay , the interpreter could not construct int before evaluating
both arguments to cons-stream , which would require that int
already be defined. In general, delay is crucial for using streams to
model signal-processing systems that contain loops. Without delay , our
models would have to be formulated so that the inputs to any signal-processing
component would be fully evaluated before the output could be produced. This
would outlaw loops.
Unfortunately, stream models of systems with loops may require uses of
delay beyond the ``hidden'' delay supplied by cons-stream .
For instance, Figure 3-34 shows a signal-processing system for solving
the differential equation dy/dt = f(y) where f is a given
function. The figure shows a mapping component, which applies f to its
input signal, linked in a feedback loop to an integrator in a manner very
similar to that of the analog computer circuits that are actually used to solve
such equations.
Figure 3.34: An ``analog computer circuit'' that
solves the equation dy/dt = f(y).
y_0
|
V
+----------+ dy +----------+ y
+-->| map: f +------>| integral +--*----->
| +----------+ +----------+ |
| |
+------------------------------------+
Assuming we are given an initial value y_0 for y, we could try to model
this system using the procedure
(define (solve f y0 dt)
(define y (integral dy y0 dt))
(define dy (stream-map f y))
y)
This procedure does not work, because in the first line of solve the
call to integral requires that the input dy be defined, which
does not happen until the second line of solve .
On the other hand, the intent of our definition does make sense, because we
can, in principle, begin to generate the y stream without knowing
dy . Indeed, integral and many other stream operations have
properties similar to those of cons-stream , in that we can generate part
of the answer given only partial information about the arguments. For
integral , the first element of the output stream is the specified
initial-value . Thus, we can generate the first element of the output
stream without evaluating the integrand dy . Once we know the first
element of y , the stream-map in the second line of solve
can begin working to generate the first element of dy , which will
produce the next element of y , and so on.
To take advantage of this idea, we will redefine integral to expect the
integrand stream to be a delayed argument
. Integral will
force the integrand to be evaluated only when it is required to generate
more than the first element of the output stream:
Now we can implement our solve procedure by delaying the evaluation of
dy in the definition of y :
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.)
(define (solve f y0 dt)
(define y (integral (delay dy) y0 dt))
(define dy (stream-map f y))
y)
In general, every caller of integral must now delay the integrand
argument. We can demonstrate that the solve procedure works by
approximating eapprox 2.718 by computing the value at y = 1 of the
solution to the differential equation dy/dt = y with initial
condition y(0) = 1:
Exercise 3.77: The integral procedure
used above was analogous to the ``implicit'' definition of the infinite stream
of integers in section 3-5-2. Alternatively, we can give a definition of
integral that is more like integers-starting-from (also in
section 3-5-2):
When used in systems with loops, this procedure has the same problem as does
our original version of integral . Modify the procedure so that it
expects the integrand as a delayed argument and hence can be used in the
solve procedure shown above.
Figure 3.35: Signal-flow diagram for the solution
to a second-order linear differential equation.
dy_0 y_0
| |
V V
ddy +----------+ dy +----------+ y
+--------->| integral +-----*--+ integral +--*--->
| +----------+ | +----------+ |
| | |
| +----------+ | |
| __/|<--+ scale: a |<--+ |
| _/ | +----------+ |
+--<_add | |
\__ | +----------+ |
\|<--+ scale: b |<-------------------+
+----------+
Exercise 3.78: Consider the problem of designing
a signal-processing system to study the homogeneous second-order linear
differential equation
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.
Exercise 3.79: Generalize the solve-2nd
procedure of Exercise 3-78 so that it can be used to solve general
second-order differential equations d^2 y/dt^2 =
f(dy/dt, y).
Exercise 3.80: A series RLC circuit
consists of a resistor, a capacitor, and an inductor connected in series, as
shown in Figure 3-36. If R, L, and C are the resistance,
inductance, and capacitance, then the relations between voltage (v) and
current (i) for the three components are described by the equations
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
| __)
- | | -
+-----------------------+
Figure 3.37: A signal-flow diagram for the
solution to a series RLC circuit.
Write a procedure RLC that takes as arguments the parameters R,
L, and C of the circuit and the time increment dt. In a manner
similar to that of the RC procedure of Exercise 3-73, RLC
should produce a procedure that takes the initial values of the state
variables, v_(C_0) and i_(L_0), and produces a pair (using
cons ) of the streams of states v_C and i_L. Using
RLC , generate the pair of streams that models the behavior of a series
RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt
= 0.1 second, and initial values i_(L_0) = 0 amps and v_(C_0) =
10 volts.
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.
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.
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:
The cesaro-stream is now fed to a monte-carlo procedure, which
produces a stream of estimates of probabilities. The results are then
converted into a stream of estimates of [pi]. This version of the program
doesn't need a parameter telling how many trials to perform. Better estimates
of [pi] (from performing more experiments) are obtained by looking farther
into the pi stream:
There is considerable modularity in this approach, because we still can
formulate a general monte-carlo procedure that can deal with arbitrary
experiments. Yet there is no assignment or local state.
Exercise 3.81: Exercise 3-6 discussed
generalizing the random-number generator to allow one to reset the
random-number sequence so as to produce repeatable sequences of ``random''
numbers. Produce a stream formulation of this same generator that operates on
an input stream of requests to generate a new random number or to
reset the sequence to a specified value and that produces the desired
stream of random numbers. Don't use assignment in your solution.
Exercise 3.82: Redo Exercise 3-5 on Monte
Carlo integration in terms of streams. The stream version of
estimate-integral will not have an argument telling how many trials to
perform. Instead, it will produce a stream of estimates based on successively
more trials.
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:
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:
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.
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.
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.
John Backus, the
inventor of Fortran, gave high visibility to functional programming when he was
awarded the @acronym{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.}
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.
Figure 3.38: A joint bank account, modeled by
merging two streams of transaction requests.
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.
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.
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.
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.
@chapter Metalinguistic Abstraction
... It's in words that the magic is---Abracadabra, Open Sesame, and the
rest---but the magic words in one story aren't magical in the next. The real
magic is to understand which words work, and when, and for what; the trick is
to learn the trick.
... And those words are made from the letters of our alphabet: a
couple-dozen squiggles we can draw with the pen. This is the key! And the
treasure, too, if we can only get our hands on it! It's as if---as if the key
to the treasure is the treasure!
---John Barth, @cite{Chimera}
In our study of program design, we have seen that expert programmers control
the complexity of their designs with the same general techniques used by
designers of all complex systems. They combine primitive elements to form
compound objects, they abstract compound objects to form higher-level building
blocks, and they preserve modularity by adopting appropriate large-scale views
of system structure. In illustrating these techniques, we have used Lisp as a
language for describing processes and for constructing computational data
objects and processes to model complex phenomena in the real world. However,
as we confront increasingly complex problems, we will find that Lisp, or indeed
any fixed programming language, is not sufficient for our needs. We must
constantly turn to new languages in order to express our ideas more
effectively. Establishing new languages is a powerful strategy for controlling
complexity in engineering design; we can often enhance our ability to deal with
a complex problem by adopting a new language that enables us to describe (and
hence to think about) the problem in a different way, using primitives, means
of combination, and means of abstraction that are particularly well suited to
the problem at hand.
The same idea is pervasive throughout all of
engineering. For example, electrical engineers use many different languages
for describing circuits. Two of these are the language of electrical
networks
and the language of electrical systems
. The
network language emphasizes the physical modeling of devices in terms of
discrete electrical elements. The primitive objects of the network language
are primitive electrical components such as resistors, capacitors, inductors,
and transistors, which are characterized in terms of physical variables called
voltage and current. When describing circuits in the network language, the
engineer is concerned with the physical characteristics of a design. In
contrast, the primitive objects of the system language are signal-processing
modules such as filters and amplifiers. Only the functional behavior of the
modules is relevant, and signals are manipulated without concern for their
physical realization as voltages and currents. The system language is erected
on the network language, in the sense that the elements of signal-processing
systems are constructed from electrical networks. Here, however, the concerns
are with the large-scale organization of electrical devices to solve a given
application problem; the physical feasibility of the parts is assumed. This
layered collection of languages is another example of the stratified design
technique illustrated by the picture language of section 2-2-4.
Programming is endowed with a multitude of languages. There are physical
languages, such as the machine languages for particular computers. These
languages are concerned with the representation of data and control in terms of
individual bits of storage and primitive machine instructions. The
machine-language programmer is concerned with using the given hardware to erect
systems and utilities for the efficient implementation of resource-limited
computations. High-level languages, erected on a machine-language substrate,
hide concerns about the representation of data as collections of bits and the
representation of programs as sequences of primitive instructions. These
languages have means of combination and abstraction, such as procedure
definition, that are appropriate to the larger-scale organization of systems.
Metalinguistic abstraction
---establishing new languages---plays an
important role in all branches of engineering design. It is particularly
important to computer programming, because in programming not only can we
formulate new languages but we can also implement these languages by
constructing evaluators. An evaluator
(or interpreter
) for
a programming language is a procedure that, when applied to an expression of
the language, performs the actions required to evaluate that expression.
It is no exaggeration to regard this as the most fundamental idea in
programming:
The evaluator, which determines the meaning of expressions in a programming
language, is just another program.
To appreciate this point is to change our images of ourselves as programmers.
We come to see ourselves as designers of languages, rather than only users of
languages designed by others.
In fact, we can regard almost any program as the evaluator for some language.
For instance, the polynomial manipulation system of section 2-5-3
embodies the rules of polynomial arithmetic and implements them in terms of
operations on list-structured data. If we augment this system with procedures
to read and print polynomial expressions, we have the core of a special-purpose
language for dealing with problems in symbolic mathematics. The digital-logic
simulator of section 3-3-4 and the constraint propagator of section
3-3-5 are legitimate languages in their own right, each with its own
primitives, means of combination, and means of abstraction. Seen from this
perspective, the technology for coping with large-scale computer systems merges
with the technology for building new computer languages, and computer science
itself becomes no more (and no less) than the discipline of constructing
appropriate descriptive languages.
We now embark on a tour of the technology by which languages are established in
terms of other languages. In this chapter we shall use Lisp as a base,
implementing evaluators as Lisp procedures. Lisp is particularly well suited
to this task, because of its ability to represent and manipulate symbolic
expressions. We will take the first step in understanding how languages are
implemented by building an evaluator for Lisp itself. The language implemented
by our evaluator will be a subset of the Scheme dialect of Lisp that we use in
this book. Although the evaluator described in this chapter is written for a
particular dialect of Lisp, it contains the essential structure of an evaluator
for any expression-oriented language designed for writing programs for a
sequential machine. (In fact, most language processors contain, deep within
them, a little ``Lisp'' evaluator.) The evaluator has been simplified for the
purposes of illustration and discussion, and some features have been left out
that would be important to include in a production-quality Lisp system.
Nevertheless, this simple evaluator is adequate to execute most of the programs
in this book.
The most important features that our evaluator leaves
out are mechanisms for handling errors and supporting debugging. For a more
extensive discussion of evaluators, see Friedman, Wand, and Haynes 1992, which
gives an exposition of programming languages that proceeds via a sequence of
evaluators written in Scheme.
An important advantage of making the evaluator accessible as a Lisp program is
that we can implement alternative evaluation rules by describing these as
modifications to the evaluator program. One place where we can use this power
to good effect is to gain extra control over the ways in which computational
models embody the notion of time, which was so central to the discussion in
Chapter 3. There, we mitigated some of the complexities of state and
assignment by using streams to decouple the representation of time in the world
from time in the computer. Our stream programs, however, were sometimes
cumbersome, because they were constrained by the applicative-order evaluation
of Scheme. In section 4-2, we'll change the underlying language to
provide for a more elegant approach, by modifying the evaluator to provide for
normal-order evaluation
.
Section 4-3 implements a more ambitious linguistic change, whereby
expressions have many values, rather than just a single value. In this
language of nondeterministic computing
, it is natural to express
processes that generate all possible values for expressions and then search for
those values that satisfy certain constraints. In terms of models of
computation and time, this is like having time branch into a set of ``possible
futures'' and then searching for appropriate time lines. With our
nondeterministic evaluator, keeping track of multiple values and performing
searches are handled automatically by the underlying mechanism of the language.
In section 4-4 we implement a logic-programming
language in
which knowledge is expressed in terms of relations, rather than in terms of
computations with inputs and outputs. Even though this makes the language
drastically different from Lisp, or indeed from any conventional language, we
will see that the logic-programming evaluator shares the essential structure of
the Lisp evaluator.
@menu
* 4-1:: The Metacircular Evaluator
* 4-2:: Variations on a Scheme -- Lazy Evaluation
* 4-3:: Variations on a Scheme -- Nondeterministic Computing
* 4-4:: Logic Programming
@end menu
The Metacircular Evaluator
Our evaluator for Lisp will be implemented as a Lisp program. It may seem
circular to think about evaluating Lisp programs using an evaluator that is
itself implemented in Lisp. However, evaluation is a process, so it is
appropriate to describe the evaluation process using Lisp, which, after all, is
our tool for describing processes.
Even so, there will remain
important aspects of the evaluation process that are not elucidated by our
evaluator. The most important of these are the detailed mechanisms by which
procedures call other procedures and return values to their callers. We will
address these issues in Chapter 5, where we take a closer look at the
evaluation process by implementing the evaluator as a simple register machine.
An evaluator that is written in the same language that it evaluates is said to
be metacircular
.
The metacircular evaluator is essentially a Scheme formulation of the
environment model of evaluation described in section 3-2. Recall that
the model has two basic parts:
To evaluate a combination (a compound expression other than a special form),
evaluate the subexpressions and then apply the value of the operator
subexpression to the values of the operand subexpressions.
To apply a compound procedure to a set of arguments, evaluate the body of the
procedure in a new environment. To construct this environment, extend the
environment part of the procedure object by a frame in which the formal
parameters of the procedure are bound to the arguments to which the procedure
is applied.
These two rules describe the essence of the evaluation process, a basic cycle
in which expressions to be evaluated in environments are reduced to procedures
to be applied to arguments, which in turn are reduced to new expressions to be
evaluated in new environments, and so on, until we get down to symbols, whose
values are looked up in the environment, and to primitive procedures, which are
applied directly (see Figure 4-1).
If we grant ourselves the
ability to apply primitives, then what remains for us to implement in the
evaluator? The job of the evaluator is not to specify the primitives of the
language, but rather to provide the connective tissue---the means of
combination and the means of abstraction---that binds a collection of
primitives to form a language. Specifically:
The evaluator enables us to deal with nested expressions. For example,
although simply applying primitives would suffice for evaluating the expression
(+ 1 6) , it is not adequate for handling (+ 1 (* 2 3)) . As far
as the primitive procedure + is concerned, its arguments must be
numbers, and it would choke if we passed it the expression (* 2 3) as an
argument. One important role of the evaluator is to choreograph procedure
composition so that (* 2 3) is reduced to 6 before being passed as an
argument to + .
The evaluator allows us to use variables. For example, the primitive procedure
for addition has no way to deal with expressions such as (+ x 1) . We
need an evaluator to keep track of variables and obtain their values before
invoking the primitive procedures.
The evaluator allows us to define compound procedures. This involves keeping
track of procedure definitions, knowing how to use these definitions in
evaluating expressions, and providing a mechanism that enables procedures to
accept arguments.
The evaluator provides the special forms, which must be evaluated differently
from procedure calls.
This evaluation cycle will be embodied by the interplay between the two
critical procedures in the evaluator, eval and apply , which are
described in section 4-1-1 (see Figure 4-1).
The implementation of the evaluator will depend upon procedures that define the
syntax
of the expressions to be evaluated. We will use data
abstraction to make the evaluator independent of the representation of the
language. For example, rather than committing to a choice that an assignment
is to be represented by a list beginning with the symbol set! we use an
abstract predicate assignment? to test for an assignment, and we use
abstract selectors assignment-variable and assignment-value to
access the parts of an assignment. Implementation of expressions will be
described in detail in section 4-1-2. There are also operations,
described in section 4-1-3, that specify the representation of procedures
and environments. For example, make-procedure constructs compound
procedures, lookup-variable-value accesses the values of variables, and
apply-primitive-procedure applies a primitive procedure to a given list
of arguments.
@menu
* 4-1-1:: The Core of the Evaluator
* 4-1-2:: Representing Expressions
* 4-1-3:: Evaluator Data Structures
* 4-1-4:: Running the Evaluator as a Program
* 4-1-5:: Data as Programs
* 4-1-6:: Internal Definitions
* 4-1-7:: Separating Syntactic Analysis from Execution
@end menu
The Core of the Evaluator
Figure 4.1: The eval - apply cycle
exposes the essence of a computer language.
The evaluation process can be described as the interplay between two
procedures: eval and apply .
Eval
Eval takes as arguments an expression and an environment. It classifies
the expression and directs its evaluation. Eval is structured as a case
analysis of the syntactic type of the expression to be evaluated. In order to
keep the procedure general, we express the determination of the type of an
expression abstractly, making no commitment to any particular representation
for the various types of expressions. Each type of expression has a predicate
that tests for it and an abstract means for selecting its parts. This
abstract syntax
makes it easy to see how we can change the syntax of
the language by using the same evaluator, but with a different collection of
syntax procedures.
@b{Primitive expressions}
For self-evaluating expressions, such as numbers, eval returns the
expression itself.
Eval must look up variables in the environment to find their values.
@b{Special forms}
For quoted expressions, eval returns the expression that was quoted.
An assignment to (or a definition of) a variable must recursively call
eval to compute the new value to be associated with the variable. The
environment must be modified to change (or create) the binding of the variable.
An if expression requires special processing of its parts, so as to
evaluate the consequent if the predicate is true, and otherwise to evaluate the
alternative.
A lambda expression must be transformed into an applicable procedure by
packaging together the parameters and body specified by the lambda
expression with the environment of the evaluation.
A begin expression requires evaluating its sequence of expressions in
the order in which they appear.
A case analysis ( cond ) is transformed into a nest of if
expressions and then evaluated.
@b{Combinations}
For a procedure application, eval must recursively evaluate the operator
part and the operands of the combination. The resulting procedure and
arguments are passed to apply , which handles the actual procedure
application.
For clarity, eval has been implemented as a case analysis using
cond . The disadvantage of this is that our procedure handles only a few
distinguishable types of expressions, and no new ones can be defined without
editing the definition of eval . In most Lisp implementations,
dispatching on the type of an expression is done in a data-directed style.
This allows a user to add new types of expressions that eval can
distinguish, without modifying the definition of eval itself. (See
Exercise 4-3.)
Apply
Apply takes two arguments, a procedure and a list of arguments to which
the procedure should be applied. Apply classifies procedures into two
kinds: It calls apply-primitive-procedure to apply primitives; it
applies compound procedures by sequentially evaluating the expressions that
make up the body of the procedure. The environment for the evaluation of the
body of a compound procedure is constructed by extending the base environment
carried by the procedure to include a frame that binds the parameters of the
procedure to the arguments to which the procedure is to be applied. Here is
the definition of apply :
When eval processes a procedure application, it uses
list-of-values to produce the list of arguments to which the procedure
is to be applied. List-of-values takes as an argument the operands of
the combination. It evaluates each operand and returns a list of the
corresponding values:
We could have simplified the application?
clause in eval by using map (and stipulating that operands
returns a list) rather than writing an explicit list-of-values
procedure. We chose not to use map here to emphasize the fact that the
evaluator can be implemented without any use of higher-order procedures (and
thus could be written in a language that doesn't have higher-order procedures),
even though the language that it supports will include higher-order
procedures.
Eval-if evaluates the predicate part of an if expression in the
given environment. If the result is true, eval-if evaluates the
consequent, otherwise it evaluates the alternative:
The use of true? in eval-if highlights the issue of the
connection between an implemented language and an implementation language. The
if-predicate is evaluated in the language being implemented and thus
yields a value in that language. The interpreter predicate true?
translates that value into a value that can be tested by the if in the
implementation language: The metacircular representation of truth might not be
the same as that of the underlying Scheme.
In this case, the language
being implemented and the implementation language are the same. Contemplation
of the meaning of true? here yields expansion of consciousness without
the abuse of substance.
Sequences
Eval-sequence is used by apply to evaluate the sequence of
expressions in a procedure body and by eval to evaluate the sequence of
expressions in a begin expression. It takes as arguments a sequence of
expressions and an environment, and evaluates the expressions in the order in
which they occur. The value returned is the value of the final expression.
The following procedure handles assignments to variables. It calls eval
to find the value to be assigned and transmits the variable and the resulting
value to set-variable-value! to be installed in the designated
environment.
Definitions of variables are handled in a similar manner.
This
implementation of define ignores a subtle issue in the handling of
internal definitions, although it works correctly in most cases. We will see
what the problem is and how to solve it in section 4-1-6.
We have chosen here to return the symbol ok as the value of an
assignment or a definition.
As we said when we introduced
define and set! , these values are implementation-dependent in
Scheme---that is, the implementor can choose what value to return.
Exercise 4.1: Notice that we cannot tell whether
the metacircular evaluator evaluates operands from left to right or from right
to left. Its evaluation order is inherited from the underlying Lisp: If the
arguments to cons in list-of-values are evaluated from left to
right, then list-of-values will evaluate operands from left to right;
and if the arguments to cons are evaluated from right to left, then
list-of-values will evaluate operands from right to left.
Write a version of list-of-values that evaluates operands from left to
right regardless of the order of evaluation in the underlying Lisp. Also write
a version of list-of-values that evaluates operands from right to left.
Representing Expressions
The evaluator is reminiscent of the symbolic differentiation program discussed
in section 2-3-2. Both programs operate on symbolic expressions. In
both programs, the result of operating on a compound expression is determined
by operating recursively on the pieces of the expression and combining the
results in a way that depends on the type of the expression. In both programs
we used data abstraction to decouple the general rules of operation from the
details of how expressions are represented. In the differentiation program
this meant that the same differentiation procedure could deal with algebraic
expressions in prefix form, in infix form, or in some other form. For the
evaluator, this means that the syntax of the language being evaluated is
determined solely by the procedures that classify and extract pieces of
expressions.
Here is the specification of the syntax of our language:
ize
The only self-evaluating items are numbers and strings:
As
mentioned in section 2-3-1, the evaluator sees a quoted expression as a
list beginning with quote , even if the expression is typed with the
quotation mark. For example, the expression 'a would be seen by the
evaluator as (quote a) . See Exercise 2-55.
Conditionals begin with if and have a predicate, a consequent, and an
(optional) alternative. If the expression has no alternative part, we provide
false as the alternative.
The value of an if expression
when the predicate is false and there is no alternative is unspecified in
Scheme; we have chosen here to make it false. We will support the use of the
variables true and false in expressions to be evaluated by
binding them in the global environment. See section 4-1-4.
Begin packages a sequence of expressions into a single expression. We
include syntax operations on begin expressions to extract the actual
sequence from the begin expression, as well as selectors that return the
first expression and the rest of the expressions in the
sequence.
These selectors for a list of expressions---and the
corresponding ones for a list of operands---are not intended as a data
abstraction. They are introduced as mnemonic names for the basic list
operations in order to make it easier to understand the explicit-control
evaluator in section 5-4.
A procedure application is any compound expression that is not one of the above
expression types. The car of the expression is the operator, and the
cdr is the list of operands:
Some special forms in our language can be defined in terms of expressions
involving other special forms, rather than being implemented directly. One
example is cond , which can be implemented as a nest of if
expressions. For example, we can reduce the problem of evaluating the
expression
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))
to the problem of evaluating the following expression involving if and
begin expressions:
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
Implementing the evaluation of cond in this way simplifies the evaluator
because it reduces the number of special forms for which the evaluation process
must be explicitly specified.
We include syntax procedures that extract the parts of a cond
expression, and a procedure cond->if that transforms cond
expressions into if expressions. A case analysis begins with
cond and has a list of predicate-action clauses. A clause is an
else clause if its predicate is the symbol else .
The
value of a cond expression when all the predicates are false and there
is no else clause is unspecified in Scheme; we have chosen here to make
it false.
Expressions (such as cond ) that we choose to implement as syntactic
transformations are called derived expressions
. Let
expressions are also derived expressions (see Exercise
4-6).
Practical Lisp systems provide a mechanism that allows a user
to add new derived expressions and specify their implementation as syntactic
transformations without modifying the evaluator. Such a user-defined
transformation is called a macro
. Although it is easy to add an
elementary mechanism for defining macros, the resulting language has subtle
name-conflict problems. There has been much research on mechanisms for macro
definition that do not cause these difficulties. See, for example, Kohlbecker
1986, Clinger and Rees 1991, and Hanson 1991.
Exercise 4.2: Louis Reasoner plans to reorder the
cond clauses in eval so that the clause for procedure
applications appears before the clause for assignments. He argues that this
will make the interpreter more efficient: Since programs usually contain more
applications than assignments, definitions, and so on, his modified eval
will usually check fewer clauses than the original eval before
identifying the type of an expression.
What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with
the expression (define x 3) ?)
Louis is upset that his plan didn't work. He is willing to go to any lengths
to make his evaluator recognize procedure applications before it checks for
most other kinds of expressions. Help him by changing the syntax of the
evaluated language so that procedure applications start with call . For
example, instead of (factorial 3) we will now have to write (call
factorial 3) and instead of (+ 1 2) we will have to write (call +
1 2) .
Exercise 4.3: Rewrite eval so that the
dispatch is done in data-directed style. Compare this with the data-directed
differentiation procedure of Exercise 2-73. (You may use the car
of a compound expression as the type of the expression, as is appropriate for
the syntax implemented in this section.)
Exercise 4.4: Recall the definitions of the
special forms and and or from Chapter 1:
and : The expressions are evaluated from left to right. If any
expression evaluates to false, false is returned; any remaining expressions are
not evaluated. If all the expressions evaluate to true values, the value of
the last expression is returned. If there are no expressions then true is
returned.
or : The expressions are evaluated from left to right. If any expression
evaluates to a true value, that value is returned; any remaining expressions
are not evaluated. If all expressions evaluate to false, or if there are no
expressions, then false is returned.
Install and and or as new special forms for the evaluator by
defining appropriate syntax procedures and evaluation procedures
eval-and and eval-or . Alternatively, show how to implement
and and or as derived expressions.
Exercise 4.5: Scheme allows an additional syntax
for cond clauses, (> => <@var{recipient>)}. If
evaluates to a true value, then is evaluated.
Its value must be a procedure of one argument; this procedure is then invoked
on the value of the , and the result is returned as the value of
the cond expression. For example
returns 2. Modify the handling of cond so that it supports this
extended syntax.
Exercise 4.6: Let expressions are derived
expressions, because
(let (() ... ())
)
is equivalent to
((lambda ( ... )
)
...
)
Implement a syntactic transformation let->combination that reduces
evaluating let expressions to evaluating combinations of the type shown
above, and add the appropriate clause to eval to handle let
expressions.
Exercise 4.7: Let* is similar to
let , except that the bindings of the let variables are performed
sequentially from left to right, and each binding is made in an environment in
which all of the preceding bindings are visible. For example
(let* ((x 3)
(y (+ x 2))
(z (+ x y 5)))
(* x z))
returns 39. Explain how a let* expression can be rewritten as a set of
nested let expressions, and write a procedure let*->nested-lets
that performs this transformation. If we have already implemented let
(Exercise 4-6) and we want to extend the evaluator to handle let* ,
is it sufficient to add a clause to eval whose action is
(eval (let*->nested-lets exp) env)
or must we explicitly expand let* in terms of non-derived expressions?
Exercise 4.8: ``Named let '' is a variant
of let that has the form
(let )
The and are just as in ordinary let ,
except that is bound within to a procedure whose body
is and whose parameters are the variables in the .
Thus, one can repeatedly execute the by invoking the procedure
named . For example, the iterative Fibonacci procedure (section
1-2-2) can be rewritten using named let as follows:
(define (fib n)
(let fib-iter ((a 1)
(b 0)
(count n))
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))
Modify let->combination of Exercise 4-6 to also support named
let .
Exercise 4.9: Many languages support a variety of
iteration constructs, such as do , for , while , and
until . In Scheme, iterative processes can be expressed in terms of
ordinary procedure calls, so special iteration constructs provide no essential
gain in computational power. On the other hand, such constructs are often
convenient. Design some iteration constructs, give examples of their use, and
show how to implement them as derived expressions.
Exercise 4.10: By using data abstraction, we
were able to write an eval procedure that is independent of the
particular syntax of the language to be evaluated. To illustrate this, design
and implement a new syntax for Scheme by modifying the procedures in this
section, without changing eval or apply .
Evaluator Data Structures
In addition to defining the external syntax of expressions, the evaluator
implementation must also define the data structures that the evaluator
manipulates internally, as part of the execution of a program, such as the
representation of procedures and environments and the representation of true
and false.
Testing of predicates
For conditionals, we accept anything to be true that is not the explicit
false object.
(define (true? x)
(not (eq? x false)))
(define (false? x)
(eq? x false))
Representing procedures
To handle primitives, we assume that we have available the following
procedures:
(apply-primitive-procedure > <@var{args>)}
applies the given primitive procedure to the argument values in the list
and returns the result of the application.
(primitive-procedure? >)
tests whether is a primitive procedure.
These mechanisms for handling primitives are further described in section
4-1-4.
Compound procedures are constructed from parameters, procedure bodies, and
environments using the constructor make-procedure :
The evaluator needs operations for manipulating environments. As explained in
section 3-2, an environment is a sequence of frames, where each frame is
a table of bindings that associate variables with their corresponding values.
We use the following operations for manipulating environments:
(lookup-variable-value > <@var{env>)}
returns the value that is bound to the symbol in the environment
, or signals an error if the variable is unbound.
(extend-environment > <@var{values> )}
returns a new environment, consisting of a new frame in which the symbols in
the list are bound to the corresponding elements in the list
, where the enclosing environment is the environment
.
(define-variable! > <@var{value> )}
adds to the first frame in the environment a new binding that
associates the variable with the value .
(set-variable-value! > <@var{value> )}
changes the binding of the variable in the environment
so that the variable is now bound to the value , or signals an
error if the variable is unbound.
To implement these operations we represent an environment as a list of frames.
The enclosing environment of an environment is the cdr of the list. The
empty environment is simply the empty list.
Each frame of an environment is represented as a pair of lists: a list of the
variables bound in that frame and a list of the associated
values.
Frames are not really a data abstraction in the following
code: Set-variable-value! and define-variable! use
set-car! to directly modify the values in a frame. The purpose of the
frame procedures is to make the environment-manipulation procedures easy to
read.
(define (make-frame variables values)
(cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame))))
To extend an environment by a new frame that associates variables with values,
we make a frame consisting of the list of variables and the list of values, and
we adjoin this to the environment. We signal an error if the number of
variables does not match the number of values.
(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
(cons (make-frame vars vals) base-env)
(if (< (length vars) (length vals))
(error "Too many arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))
To look up a variable in an environment, we scan the list of variables in the
first frame. If we find the desired variable, we return the corresponding
element in the list of values. If we do not find the variable in the current
frame, we search the enclosing environment, and so on. If we reach the empty
environment, we signal an ``unbound variable'' error.
To set a variable to a new value in a specified environment, we scan for the
variable, just as in lookup-variable-value , and change the corresponding
value when we find it.
To define a variable, we search the first frame for a binding for the variable,
and change the binding if it exists (just as in set-variable-value! ).
If no such binding exists, we adjoin one to the first frame.
(define (define-variable! var val env)
(let ((frame (first-frame env)))
(define (scan vars vals)
(cond ((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame)
(frame-values frame))))
The method described here is only one of many plausible ways to represent
environments. Since we used data abstraction to isolate the rest of the
evaluator from the detailed choice of representation, we could change the
environment representation if we wanted to. (See Exercise 4-11.) In a
production-quality Lisp system, the speed of the evaluator's environment
operations---especially that of variable lookup---has a major impact on the
performance of the system. The representation described here, although
conceptually simple, is not efficient and would not ordinarily be used in a
production system.
The drawback of this representation (as well as the
variant in Exercise 4-11) is that the evaluator may have to search
through many frames in order to find the binding for a given variable. (Such
an approach is referred to as deep binding
.) One way to avoid this
inefficiency is to make use of a strategy called lexical addressing
,
which will be discussed in section 5-5-6.
Exercise 4.11: Instead of representing a frame
as a pair of lists, we can represent a frame as a list of bindings, where each
binding is a name-value pair. Rewrite the environment operations to use this
alternative representation.
Exercise 4.12: The procedures
set-variable-value! , define-variable! , and
lookup-variable-value can be expressed in terms of more abstract
procedures for traversing the environment structure. Define abstractions that
capture the common patterns and redefine the three procedures in terms of these
abstractions.
Exercise 4.13: Scheme allows us to create new
bindings for variables by means of define , but provides no way to get
rid of bindings. Implement for the evaluator a special form
make-unbound! that removes the binding of a given symbol from the
environment in which the make-unbound! expression is evaluated. This
problem is not completely specified. For example, should we remove only the
binding in the first frame of the environment? Complete the specification and
justify any choices you make.
Running the Evaluator as a Program
Given the evaluator, we have in our hands a description (expressed in Lisp) of
the process by which Lisp expressions are evaluated. One advantage of
expressing the evaluator as a program is that we can run the program. This
gives us, running within Lisp, a working model of how Lisp itself evaluates
expressions. This can serve as a framework for experimenting with evaluation
rules, as we shall do later in this chapter.
Our evaluator program reduces expressions ultimately to the application of
primitive procedures. Therefore, all that we need to run the evaluator is to
create a mechanism that calls on the underlying Lisp system to model the
application of primitive procedures.
There must be a binding for each primitive procedure name, so that when
eval evaluates the operator of an application of a primitive, it will
find an object to pass to apply . We thus set up a global environment
that associates unique objects with the names of the primitive procedures that
can appear in the expressions we will be evaluating. The global environment
also includes bindings for the symbols true and false , so that
they can be used as variables in expressions to be evaluated.
It does not matter how we represent the primitive procedure objects, so long as
apply can identify and apply them by using the procedures
primitive-procedure? and apply-primitive-procedure . We have
chosen to represent a primitive procedure as a list beginning with the symbol
primitive and containing a procedure in the underlying Lisp that
implements that primitive.
Setup-environment will get the primitive names and implementation
procedures from a list:
Any procedure defined in the underlying Lisp
can be used as a primitive for the metacircular evaluator. The name of a
primitive installed in the evaluator need not be the same as the name of its
implementation in the underlying Lisp; the names are the same here because the
metacircular evaluator implements Scheme itself. Thus, for example, we could
put (list 'first car) or (list 'square (lambda (x) (* x x))) in
the list of primitive-procedures .
To apply a primitive procedure, we simply apply the implementation procedure to
the arguments, using the underlying Lisp
system:
Apply-in-underlying-scheme is the apply
procedure we have used in earlier chapters. The metacircular evaluator's
apply procedure (section 4-1-1) models the working of this
primitive. Having two different things called apply leads to a
technical problem in running the metacircular evaluator, because defining the
metacircular evaluator's apply will mask the definition of the
primitive. One way around this is to rename the metacircular apply to
avoid conflict with the name of the primitive procedure. We have assumed
instead that we have saved a reference to the underlying apply by doing
(define apply-in-underlying-scheme apply)
before defining the metacircular apply . This allows us to access the
original version of apply under a different name.
For convenience in running the metacircular evaluator, we provide a
driver loop
that models the read-eval-print loop of the underlying
Lisp system. It prints a prompt
, reads an input expression,
evaluates this expression in the global environment, and prints the result. We
precede each printed result by an output prompt
so as to distinguish
the value of the expression from other output that may be printed.
The
primitive procedure read waits for input from the user, and returns the
next complete expression that is typed. For example, if the user types
(+ 23 x) , read returns a three-element list containing the symbol
+ , the number 23, and the symbol x . If the user types 'x ,
read returns a two-element list containing the symbol quote and
the symbol x .