sequence is unrelated to the preceding number. The relation between ``real
randomness'' and so-called pseudo-random
sequences, which are
produced by well-determined computations and yet have suitable statistical
properties, is a complex question involving difficult issues in mathematics and
philosophy. Kolmogorov, Solomonoff, and Chaitin have made great progress in
clarifying these issues; a discussion can be found in Chaitin 1975.
We can implement rand as a procedure with a local state variable
x that is initialized to some fixed value random-init . Each call
to rand computes rand-update of the current value of x ,
returns this as the random number, and also stores this as the new value of
x .
Of course, we could generate the same sequence of random numbers without using
assignment by simply calling rand-update directly. However, this would
mean that any part of our program that used random numbers would have to
explicitly remember the current value of x to be passed as an argument
to rand-update . To realize what an annoyance this would be, consider
using random numbers to implement a technique called Monte Carlo
simulation
.
The Monte Carlo method consists of choosing sample experiments at random from a
large set and then making deductions on the basis of the probabilities
estimated from tabulating the results of those experiments. For example, we
can approximate [pi] using the fact that 6/[pi]^2 is the probability
that two integers chosen at random will have no factors in common; that is,
that their greatest common divisor will be 1.
This theorem is due to
E. Ces@`aro. See section 4.5.2 of Knuth 1981 for a discussion and a proof.
To
obtain the approximation to [pi], we perform a large number of experiments.
In each experiment we choose two integers at random and perform a test to see
if their @acronym{GCD} is 1. The fraction of times that the test is passed
gives us our estimate of 6/[pi]^2, and from this we obtain our
approximation to [pi].
The heart of our program is a procedure monte-carlo , which takes as
arguments the number of times to try an experiment, together with the
experiment, represented as a no-argument procedure that will return either true
or false each time it is run. Monte-carlo runs the experiment for the
designated number of trials and returns a number telling the fraction of the
trials in which the experiment was found to be true.
Now let us try the same computation using rand-update directly rather
than rand , the way we would be forced to proceed if we did not use
assignment to model local state:
While the program is still simple, it betrays some painful breaches of
modularity. In our first version of the program, using rand , we can
express the Monte Carlo method directly as a general monte-carlo
procedure that takes as an argument an arbitrary experiment procedure.
In our second version of the program, with no local state for the random-number
generator, random-gcd-test must explicitly manipulate the random numbers
x1 and x2 and recycle x2 through the iterative loop as the
new input to rand-update . This explicit handling of the random numbers
intertwines the structure of accumulating test results with the fact that our
particular experiment uses two random numbers, whereas other Monte Carlo
experiments might use one random number or three. Even the top-level procedure
estimate-pi has to be concerned with supplying an initial random number.
The fact that the random-number generator's insides are leaking out into other
parts of the program makes it difficult for us to isolate the Monte Carlo idea
so that it can be applied to other tasks. In the first version of the program,
assignment encapsulates the state of the random-number generator within the
rand procedure, so that the details of random-number generation remain
independent of the rest of the program.
The general phenomenon illustrated by the Monte Carlo example is this: 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 computer programs whose structure reflects this decomposition, we make
computational objects (such as bank accounts and random-number generators)
whose behavior changes with time. We model state with local state variables,
and we model the changes of state with assignments to those variables.
It is tempting to conclude this discussion by saying that, by introducing
assignment and the technique of hiding state in local variables, we are able to
structure systems in a more modular fashion than if all state had to be
manipulated explicitly, by passing additional parameters. Unfortunately, as we
shall see, the story is not so simple.
Exercise 3.5: Monte Carlo integration
is a method of estimating definite integrals by means of Monte Carlo
simulation. Consider computing the area of a region of space described by a
predicate P(x, y) that is true for points (x, y) in the
region and false for points not in the region. For example, the region
contained within a circle of radius 3 centered at (5, 7) is described by the
predicate that tests whether (x - 5)^2 + (y - 7)^2 <= 3^2. To estimate
the area of the region described by such a predicate, begin by choosing a
rectangle that contains the region. For example, a rectangle with diagonally
opposite corners at (2, 4) and (8, 10) contains the circle above. The desired
integral is the area of that portion of the rectangle that lies in the region.
We can estimate the integral by picking, at random, points (x,y) that
lie in the rectangle, and testing P(x, y) for each point to
determine whether the point lies in the region. If we try this with many
points, then the fraction of points that fall in the region should give an
estimate of the proportion of the rectangle that lies in the region. Hence,
multiplying this fraction by the area of the entire rectangle should produce an
estimate of the integral.
Implement Monte Carlo integration as a procedure estimate-integral that
takes as arguments a predicate P , upper and lower bounds x1 ,
x2 , y1 , and y2 for the rectangle, and the number of trials
to perform in order to produce the estimate. Your procedure should use the
same monte-carlo procedure that was used above to estimate [pi].
Use your estimate-integral to produce an estimate of [pi] by
measuring the area of a unit circle.
You will find it useful to have a procedure that returns a number chosen at
random from a given range. The following random-in-range procedure
implements this in terms of the random procedure used in section
1-2-6, which returns a nonnegative number less than its
input.
@acronym{MIT
Scheme provides such a procedure. If
random is given an exact integer (as in section 1-2-6) it returns
an exact integer, but if it is given a decimal value (as in this exercise) it
returns a decimal value.}
Exercise 3.6: It is useful to be able to reset a
random-number generator to produce a sequence starting from a given value.
Design a new rand procedure that is called with an argument that is
either the symbol generate or the symbol reset and behaves as
follows: (rand 'generate) produces a new random number; ((rand
'reset) >) resets the internal state variable to the
designated . Thus, by resetting the state, one can generate
repeatable sequences. These are very handy to have when testing and debugging
programs that use random numbers.
The Costs of Introducing Assignment
As we have seen, the set! operation enables us to model objects that
have local state. However, this advantage comes at a price. Our programming
language can no longer be interpreted in terms of the substitution model of
procedure application that we introduced in section 1-1-5. Moreover, no
simple model with ``nice'' mathematical properties can be an adequate framework
for dealing with objects and assignment in programming languages.
So long as we do not use assignments, two evaluations of the same procedure
with the same arguments will produce the same result, so that procedures can be
viewed as computing mathematical functions. Programming without any use of
assignments, as we did throughout the first two chapters of this book, is
accordingly known as functional programming
.
To understand how assignment complicates matters, consider a simplified version
of the make-withdraw procedure of section 3-1-1 that does not
bother to check for an insufficient amount:
(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))
(define W (make-simplified-withdraw 25))
(W 20)
5
(W 10)
- 5
Compare this procedure with the following make-decrementer procedure,
which does not use set! :
Make-decrementer returns a procedure that subtracts its input from a
designated amount balance , but there is no accumulated effect over
successive calls, as with make-simplified-withdraw :
(define D (make-decrementer 25))
(D 20)
5
(D 10)
15
We can use the substitution model to explain how make-decrementer works.
For instance, let us analyze the evaluation of the expression
((make-decrementer 25) 20)
We first simplify the operator of the combination by substituting 25 for
balance in the body of make-decrementer . This reduces the
expression to
((lambda (amount) (- 25 amount)) 20)
Now we apply the operator by substituting 20 for amount in the body of
the lambda expression:
(- 25 20)
The final answer is 5.
Observe, however, what happens if we attempt a similar substitution analysis
with make-simplified-withdraw :
((make-simplified-withdraw 25) 20)
We first simplify the operator by substituting 25 for balance in the
body of make-simplified-withdraw . This reduces the expression
to
We don't substitute for the occurrence of balance in the
set! expression because the in a set! is not
evaluated. If we did substitute for it, we would get (set! 25 (- 25
amount)) , which makes no sense.
Now we apply the operator by substituting 20 for amount in the body of
the lambda expression:
(set! balance (- 25 20)) 25
If we adhered to the substitution model, we would have to say that the meaning
of the procedure application is to first set balance to 5 and then
return 25 as the value of the expression. This gets the wrong answer. In
order to get the correct answer, we would have to somehow distinguish the first
occurrence of balance (before the effect of the set! ) from the
second occurrence of balance (after the effect of the set! ), and
the substitution model cannot do this.
The trouble here is that substitution is based ultimately on the notion that
the symbols in our language are essentially names for values. But as soon as
we introduce set! and the idea that the value of a variable can change,
a variable can no longer be simply a name. Now a variable somehow refers to a
place where a value can be stored, and the value stored at this place can
change. In section 3-2 we will see how environments play this role of
``place'' in our computational model.
Sameness and change
The issue surfacing here is more profound than the mere breakdown of a
particular model of computation. As soon as we introduce change into our
computational models, many notions that were previously straightforward become
problematical. Consider the concept of two things being ``the same.''
Suppose we call make-decrementer twice with the same argument to create
two procedures:
Are D1 and D2 the same? An acceptable answer is yes, because
D1 and D2 have the same computational behavior---each is a
procedure that subtracts its input from 25. In fact, D1 could be
substituted for D2 in any computation without changing the result.
Contrast this with making two calls to make-simplified-withdraw :
Are W1 and W2 the same? Surely not, because calls to W1
and W2 have distinct effects, as shown by the following sequence of
interactions:
(W1 20)
5
(W1 20)
- 15
(W2 20)
5
Even though W1 and W2 are ``equal'' in the sense that they are
both created by evaluating the same expression, (make-simplified-withdraw
25) , it is not true that W1 could be substituted for W2 in any
expression without changing the result of evaluating the expression.
A language that supports the concept that ``equals can be substituted for
equals'' in an expresssion without changing the value of the expression is said
to be referentially transparent
. Referential transparency is
violated when we include set! in our computer language. This makes it
tricky to determine when we can simplify expressions by substituting equivalent
expressions. Consequently, reasoning about programs that use assignment
becomes drastically more difficult.
Once we forgo referential transparency, the notion of what it means for
computational objects to be ``the same'' becomes difficult to capture in a
formal way. Indeed, the meaning of ``same'' in the real world that our
programs model is hardly clear in itself. In general, we can determine that
two apparently identical objects are indeed ``the same one'' only by modifying
one object and then observing whether the other object has changed in the same
way. But how can we tell if an object has ``changed'' other than by observing
the ``same'' object twice and seeing whether some property of the object
differs from one observation to the next? Thus, we cannot determine ``change''
without some a priori notion of ``sameness,'' and we cannot determine
sameness without observing the effects of change.
As an example of how this issue arises in programming, consider the situation
where Peter and Paul have a bank account with $100 in it. There is a
substantial difference between modeling this as
In the first situation, the two bank accounts are distinct. Transactions made
by Peter will not affect Paul's account, and vice versa. In the second
situation, however, we have defined paul-acc to be the same thing
as peter-acc . In effect, Peter and Paul now have a joint bank account,
and if Peter makes a withdrawal from peter-acc Paul will observe less
money in paul-acc . These two similar but distinct situations can cause
confusion in building computational models. With the shared account, in
particular, it can be especially confusing that there is one object (the bank
account) that has two different names ( peter-acc and paul-acc );
if we are searching for all the places in our program where paul-acc can
be changed, we must remember to look also at things that change
peter-acc .
The phenomenon of a single computational object
being accessed by more than one name is known as aliasing
. The joint
bank account situation illustrates a very simple example of an alias. In
section 3-3 we will see much more complex examples, such as ``distinct''
compound data structures that share parts. Bugs can occur in our programs if
we forget that a change to an object may also, as a ``side effect,'' change a
``different'' object because the two ``different'' objects are actually a
single object appearing under different aliases. These so-called
side-effect bugs
are so difficult to locate and to analyze that some
people have proposed that programming languages be designed in such a way as to
not allow side effects or aliasing (Lampson et al. 1981; Morris, Schmidt, and
Wadler 1980).
With reference to the above remarks on ``sameness'' and ``change,'' observe
that if Peter and Paul could only examine their bank balances, and could not
perform operations that changed the balance, then the issue of whether the two
accounts are distinct would be moot. In general, so long as we never modify
data objects, we can regard a compound data object to be precisely the totality
of its pieces. For example, a rational number is determined by giving its
numerator and its denominator. But this view is no longer valid in the
presence of change, where a compound data object has an ``identity'' that is
something different from the pieces of which it is composed. A bank account is
still ``the same'' bank account even if we change the balance by making a
withdrawal; conversely, we could have two different bank accounts with the same
state information. This complication is a consequence, not of our programming
language, but of our perception of a bank account as an object. We do not, for
example, ordinarily regard a rational number as a changeable object with
identity, such that we could change the numerator and still have ``the same''
rational number.
Pitfalls of imperative programming
In contrast to functional programming, programming that makes extensive use of
assignment is known as imperative programming
. In addition to
raising complications about computational models, programs written in
imperative style are susceptible to bugs that cannot occur in functional
programs. For example, recall the iterative factorial program from section
1-2-1:
Instead of passing arguments in the internal iterative loop, we could adopt a
more imperative style by using explicit assignment to update the values of the
variables product and counter :
This does not change the results produced by the program, but it does introduce
a subtle trap. How do we decide the order of the assignments? As it happens,
the program is correct as written. But writing the assignments in the opposite
order
would have produced a different, incorrect result. In general, programming
with assignment forces us to carefully consider the relative orders of the
assignments to make sure that each statement is using the correct version of
the variables that have been changed. This issue simply does not arise in
functional programs.
In view of this, it is ironic that introductory
programming is most often taught in a highly imperative style. This may be a
vestige of a belief, common throughout the 1960s and 1970s, that programs that
call procedures must inherently be less efficient than programs that perform
assignments. (Steele (1977) debunks this argument.) Alternatively it may
reflect a view that step-by-step assignment is easier for beginners to
visualize than procedure call. Whatever the reason, it often saddles beginning
programmers with ``should I set this variable before or after that one''
concerns that can complicate programming and obscure the important ideas.
The complexity of imperative programs becomes even worse if we consider
applications in which several processes execute concurrently. We will return
to this in section 3-4. First, however, we will address the issue of
providing a computational model for expressions that involve assignment, and
explore the uses of objects with local state in designing simulations.
Exercise 3.7: Consider the bank account objects
created by make-account , with the password modification described in
Exercise 3-3. Suppose that our banking system requires the ability to
make joint accounts. Define a procedure make-joint that accomplishes
this. Make-joint should take three arguments. The first is a
password-protected account. The second argument must match the password with
which the account was defined in order for the make-joint operation to
proceed. The third argument is a new password. Make-joint is to create
an additional access to the original account using the new password. For
example, if peter-acc is a bank account with password
open-sesame , then
will allow one to make transactions on peter-acc using the name
paul-acc and the password rosebud . You may wish to modify your
solution to Exercise 3-3 to accommodate this new feature
Exercise 3.8: When we defined the evaluation
model in section 1-1-3, we said that the first step in evaluating an
expression is to evaluate its subexpressions. But we never specified the order
in which the subexpressions should be evaluated (e.g., left to right or right
to left). When we introduce assignment, the order in which the arguments to a
procedure are evaluated can make a difference to the result. Define a simple
procedure f such that evaluating (+ (f 0) (f 1)) will return 0 if
the arguments to + are evaluated from left to right but will return 1 if
the arguments are evaluated from right to left.
The Environment Model of Evaluation
When we introduced compound procedures in Chapter 1, we used the
substitution model of evaluation (section 1-1-5) to define what is meant
by applying a procedure to arguments:
To apply a compound procedure to arguments, evaluate the body of the procedure
with each formal parameter replaced by the corresponding argument.
Once we admit assignment into our programming language, such a definition is no
longer adequate. In particular, section 3-1-3 argued that, in the
presence of assignment, a variable can no longer be considered to be merely a
name for a value. Rather, a variable must somehow designate a ``place'' in
which values can be stored. In our new model of evaluation, these places will
be maintained in structures called environments
.
An environment is a sequence of frames
. Each frame is a table
(possibly empty) of bindings
, which associate variable names with
their corresponding values. (A single frame may contain at most one binding
for any variable.) Each frame also has a pointer to its enclosing
environment
, unless, for the purposes of discussion, the frame is considered
to be global
. The value of a variable
with respect to an
environment is the value given by the binding of the variable in the first
frame in the environment that contains a binding for that variable. If no
frame in the sequence specifies a binding for the variable, then the variable
is said to be unbound
in the environment.
Figure 3-1 shows a simple environment structure consisting of three
frames, labeled I, II, and III. In the diagram, A, B, C, and D are pointers to
environments. C and D point to the same environment. The variables z
and x are bound in frame II, while y and x are bound in
frame I. The value of x in environment D is 3. The value of x
with respect to environment B is also 3. This is determined as follows: We
examine the first frame in the sequence (frame III) and do not find a binding
for x , so we proceed to the enclosing environment D and find the binding
in frame I. On the other hand, the value of x in environment A is 7,
because the first frame in the sequence (frame II) contains a binding of
x to 7. With respect to environment A, the binding of x to 7 in
frame II is said to shadow
the binding of x to 3 in frame I.
The environment is crucial to the evaluation process, because it determines the
context in which an expression should be evaluated. Indeed, one could say that
expressions in a programming language do not, in themselves, have any meaning.
Rather, an expression acquires a meaning only with respect to some environment
in which it is evaluated. Even the interpretation of an expression as
straightforward as (+ 1 1) depends on an understanding that one is
operating in a context in which + is the symbol for addition. Thus, in
our model of evaluation we will always speak of evaluating an expression with
respect to some environment. To describe interactions with the interpreter, we
will suppose that there is a global environment, consisting of a single frame
(with no enclosing environment) that includes values for the symbols associated
with the primitive procedures. For example, the idea that + is the
symbol for addition is captured by saying that the symbol + is bound in
the global environment to the primitive addition procedure.
@menu
* 3-2-1:: The Rules for Evaluation
* 3-2-2:: Applying Simple Procedures
* 3-2-3:: Frames as the Repository of Local State
* 3-2-4:: Internal Definitions
@end menu
The Rules for Evaluation
The overall specification of how the interpreter evaluates a combination
remains the same as when we first introduced it in section 1-1-3:
To evaluate a combination:
Evaluate the subexpressions of the combination.
ssignment introduces a
subtlety into step 1 of the evaluation rule. As shown in Exercise 3-8,
the presence of assignment allows us to write expressions that will produce
different values depending on the order in which the subexpressions in a
combination are evaluated. Thus, to be precise, we should specify an
evaluation order in step 1 (e.g., left to right or right to left). However,
this order should always be considered to be an implementation detail, and one
should never write programs that depend on some particular order. For
instance, a sophisticated compiler might optimize a program by varying the
order in which subexpressions are evaluated.
Apply the value of the operator subexpression to the values of the operand
subexpressions.
The environment model of evaluation replaces the substitution model in
specifying what it means to apply a compound procedure to arguments.
In the environment model of evaluation, a procedure is always a pair consisting
of some code and a pointer to an environment. Procedures are created in one
way only: by evaluating a lambda expression. This produces a procedure
whose code is obtained from the text of the lambda expression and whose
environment is the environment in which the lambda expression was
evaluated to produce the procedure. For example, consider the procedure
definition
(define (square x)
(* x x))
evaluated in the global environment. The procedure definition syntax is just
syntactic sugar for an underlying implicit lambda expression. It would
have been equivalent to have used
(define square
(lambda (x) (* x x)))
which evaluates (lambda (x) (* x x)) and binds square to the
resulting value, all in the global environment.
Figure 3-2 shows the result of evaluating this define expression.
The procedure object is a pair whose code specifies that the procedure has one
formal parameter, namely x , and a procedure body (* x x) . The
environment part of the procedure is a pointer to the global environment, since
that is the environment in which the lambda expression was evaluated to
produce the procedure. A new binding, which associates the procedure object
with the symbol square , has been added to the global frame. In general,
define creates definitions by adding bindings to frames.
Figure 3.2: Environment structure produced by
evaluating (define (square x) (* x x)) in the global environment.
+----------------------+
| other variables |
global --->| |
env | square: --+ |
+-----------|----------+
| ^
(define (square x) | |
(* x x)) V |
.---.---. |
| O | O-+---+
`-|-^---'
|
V
parameters: x
body: (* x x)
Now that we have seen how procedures are created, we can describe how
procedures are applied. The environment model specifies: To apply a procedure
to arguments, create a new environment containing a frame that binds the
parameters to the values of the arguments. The enclosing environment of this
frame is the environment specified by the procedure. Now, within this new
environment, evaluate the procedure body.
To show how this rule is followed, Figure 3-3 illustrates the environment
structure created by evaluating the expression (square 5) in the global
environment, where square is the procedure generated in Figure
3-2. Applying the procedure results in the creation of a new environment,
labeled E1 in the figure, that begins with a frame in which x , the
formal parameter for the procedure, is bound to the argument 5. The pointer
leading upward from this frame shows that the frame's enclosing environment is
the global environment. The global environment is chosen here, because this is
the environment that is indicated as part of the square procedure
object. Within E1, we evaluate the body of the procedure, (* x x) .
Since the value of x in E1 is 5, the result is (* 5 5) , or 25.
Figure 3.3: Environment created by evaluating
(square 5) in the global environment.
+------------------------------------+
| other variables |
global -->| |
env | square: --+ |
+-----------|---------------------+--+
| ^ ^
(square 5) | | |
V | |
.---.---. | +---+--+
| O | O-+---+ E1 -->| x: 5 |
`-|-^---' +------+
|
V
parameters: x
body: (* x x)
The environment model of procedure application can be summarized by two rules:
A procedure object is applied to a set of arguments by constructing a frame,
binding the formal parameters of the procedure to the arguments of the call,
and then evaluating the body of the procedure in the context of the new
environment constructed. The new frame has as its enclosing environment the
environment part of the procedure object being applied.
A procedure is created by evaluating a lambda expression relative to a
given environment. The resulting procedure object is a pair consisting of the
text of the lambda expression and a pointer to the environment in which
the procedure was created.
We also specify that defining a symbol using define creates a binding in
the current environment frame and assigns to the symbol the indicated
value.
If there is already a binding for the variable in the current
frame, then the binding is changed. This is convenient because it allows
redefinition of symbols; however, it also means that define can be used
to change values, and this brings up the issues of assignment without
explicitly using set! . Because of this, some people prefer
redefinitions of existing symbols to signal errors or warnings.
Finally, we
specify the behavior of set! , the operation that forced us to introduce
the environment model in the first place. Evaluating the expression
(set! > <@var{value>)} in some environment locates the
binding of the variable in the environment and changes that binding to indicate
the new value. That is, one finds the first frame in the environment that
contains a binding for the variable and modifies that frame. If the variable
is unbound in the environment, then set! signals an error.
These evaluation rules, though considerably more complex than the substitution
model, are still reasonably straightforward. Moreover, the evaluation model,
though abstract, provides a correct description of how the interpreter
evaluates expressions. In Chapter 4 we shall see how this model can
serve as a blueprint for implementing a working interpreter. The following
sections elaborate the details of the model by analyzing some illustrative
programs.
Applying Simple Procedures
When we introduced the substitution model in section 1-1-5 we showed how
the combination (f 5) evaluates to 136, given the following procedure
definitions:
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
We can analyze the same example using the environment model. Figure 3-4
shows the three procedure objects created by evaluating the definitions of
f , square , and sum-of-squares in the global environment.
Each procedure object consists of some code, together with a pointer to the
global environment.
Figure 3.4: Procedure objects in the global frame.
+--------------------------------------------+
| sum-of-squares: |
global -->| square: |
env | f: --+ |
+------|--------------+--------------+-------+
| ^ | ^ | ^
| | | | | |
V | V | V |
.---.---. | .---.---. | .---.---. |
| O | O-+-+ | O | O-+-+ | O | O-+-+
`-|-^---' `-|-^---' `-|-^---'
| | |
V V V
parameters: a parameters: x parameters: x, y
body: (sum-of-squares body: (* x x) body: (+ (square x)
(+ a 1) (square y))
(* a 2))
In Figure 3-5 we see the environment structure created by evaluating the
expression (f 5) . The call to f creates a new environment E1
beginning with a frame in which a , the formal parameter of f , is
bound to the argument 5. In E1, we evaluate the body of f :
(sum-of-squares (+ a 1) (* a 2))
Figure 3.5: Environments created by evaluating
(f 5) using the procedures in Figure 3-4.
To evaluate this combination, we first evaluate the subexpressions. The first
subexpression, sum-of-squares , has a value that is a procedure object.
(Notice how this value is found: We first look in the first frame of E1, which
contains no binding for sum-of-squares . Then we proceed to the
enclosing environment, i.e. the global environment, and find the binding shown
in Figure 3-4.) The other two subexpressions are evaluated by applying
the primitive operations + and * to evaluate the two combinations
(+ a 1) and (* a 2) to obtain 6 and 10, respectively.
Now we apply the procedure object sum-of-squares to the arguments 6 and
10. This results in a new environment E2 in which the formal parameters
x and y are bound to the arguments. Within E2 we evaluate the
combination (+ (square x) (square y)) . This leads us to evaluate
(square x) , where square is found in the global frame and
x is 6. Once again, we set up a new environment, E3, in which x
is bound to 6, and within this we evaluate the body of square , which is
(* x x) . Also as part of applying sum-of-squares , we must
evaluate the subexpression (square y) , where y is 10. This
second call to square creates another environment, E4, in which
x , the formal parameter of square , is bound to 10. And within E4
we must evaluate (* x x) .
The important point to observe is that each call to square creates a new
environment containing a binding for x . We can see here how the
different frames serve to keep separate the different local variables all named
x . Notice that each frame created by square points to the global
environment, since this is the environment indicated by the square
procedure object.
After the subexpressions are evaluated, the results are returned. The values
generated by the two calls to square are added by sum-of-squares ,
and this result is returned by f . Since our focus here is on the
environment structures, we will not dwell on how these returned values are
passed from call to call; however, this is also an important aspect of the
evaluation process, and we will return to it in detail in Chapter 5.
Exercise 3.9: In section 1-2-1 we used the
substitution model to analyze two procedures for computing factorials, a
recursive version
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Show the environment structures created by evaluating (factorial 6)
using each version of the factorial procedure.
The environment
model will not clarify our claim in section 1-2-1 that the interpreter
can execute a procedure such as fact-iter in a constant amount of space
using tail recursion. We will discuss tail recursion when we deal with the
control structure of the interpreter in section 5-4.
Frames as the Repository of Local State
We can turn to the environment model to see how procedures and assignment can
be used to represent objects with local state. As an example, consider the
``withdrawal processor'' from section 3-1-1 created by calling the
procedure
Figure 3-6 shows the result of defining the make-withdraw
procedure in the global environment. This produces a procedure object that
contains a pointer to the global environment. So far, this is no different
from the examples we have already seen, except that the body of the procedure
is itself a lambda expression.
Figure 3.6: Result of defining make-withdraw
in the global environment.
+---------------------------+
global -->| make-withdraw: --+ |
env +------------------|--------+
| ^
V |
.---.---. |
| O | O-+--+
`-|-^---'
|
V
parameters: balance
body: (lambda (amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
The interesting part of the computation happens when we apply the procedure
make-withdraw to an argument:
(define W1 (make-withdraw 100))
We begin, as usual, by setting up an environment E1 in which the formal
parameter balance is bound to the argument 100. Within this
environment, we evaluate the body of make-withdraw , namely the
lambda expression. This constructs a new procedure object, whose code
is as specified by the lambda and whose environment is E1, the
environment in which the lambda was evaluated to produce the procedure.
The resulting procedure object is the value returned by the call to
make-withdraw . This is bound to W1 in the global environment,
since the define itself is being evaluated in the global environment.
Figure 3-7 shows the resulting environment structure.
Figure 3.7: Result of evaluating (define W1
(make-withdraw 100)) .
Now we can analyze what happens when W1 is applied to an argument:
(W1 50)
50
We begin by constructing a frame in which amount , the formal parameter
of W1 , is bound to the argument 50. The crucial point to observe is
that this frame has as its enclosing environment not the global environment,
but rather the environment E1, because this is the environment that is
specified by the W1 procedure object. Within this new environment, we
evaluate the body of the procedure:
The resulting environment structure is shown in Figure 3-8. The
expression being evaluated references both amount and balance .
Amount will be found in the first frame in the environment, while
balance will be found by following the enclosing-environment pointer to
E1.
Figure 3.8: Environments created by applying the
procedure object W1 .
+---------------------------------------------------+
| make-withdraw: ... |
global -->| |
env | W1: --+ |
+-------|-------------------------------------------+
| ^
| |
| +-------+------+ Here is the balance
| E1 -->| balance: 100 | that will be changed
| +--------------+ by the set!.
V ^ ^
.---.---. | +----+
| O | O-+-----------+ |
`-|-^---' +------+-----+
| | amount: 50 |
V +------------+
parameters: amount (if (>= balance amount)
body: ... (begin (set! balance
(- balance amount))
balance)
"Insufficient funds")
When the set! is executed, the binding of balance in E1 is
changed. At the completion of the call to W1 , balance is 50, and
the frame that contains balance is still pointed to by the procedure
object W1 . The frame that binds amount (in which we executed the
code that changed balance ) is no longer relevant, since the procedure
call that constructed it has terminated, and there are no pointers to that
frame from other parts of the environment. The next time W1 is called,
this will build a new frame that binds amount and whose enclosing
environment is E1. We see that E1 serves as the ``place'' that holds the local
state variable for the procedure object W1 . Figure 3-9 shows the
situation after the call to W1 .
Observe what happens when we create a second ``withdraw'' object by making
another call to make-withdraw :
(define W2 (make-withdraw 100))
This produces the environment structure of Figure 3-10, which shows that
W2 is a procedure object, that is, a pair with some code and an
environment. The environment E2 for W2 was created by the call to
make-withdraw . It contains a frame with its own local binding for
balance . On the other hand, W1 and W2 have the same code:
the code specified by the lambda expression in the body of
make-withdraw .
Whether W1 and W2 share the same
physical code stored in the computer, or whether they each keep a copy of the
code, is a detail of the implementation. For the interpreter we implement in
Chapter 4, the code is in fact shared.
We see here why W1 and
W2 behave as independent objects. Calls to W1 reference the
state variable balance stored in E1, whereas calls to W2
reference the balance stored in E2. Thus, changes to the local state of
one object do not affect the other object.
Figure 3.10: Using (define W2 (make-withdraw
100)) to create a second object.
Exercise 3.10: In the make-withdraw
procedure, the local variable balance is created as a parameter of
make-withdraw . We could also create the local state variable
explicitly, using let , as follows:
Show that the two versions of make-withdraw create objects with the same
behavior. How do the environment structures differ for the two versions?
Internal Definitions
Section 1-1-8 introduced the idea that procedures can have internal
definitions, thus leading to a block structure as in the following procedure to
compute square roots:
Now we can use the environment model to see why these internal definitions
behave as desired. Figure 3-11 shows the point in the evaluation of the
expression (sqrt 2) where the internal procedure good-enough? has
been called for the first time with guess equal to 1.
Figure 3.11: Sqrt procedure with internal
definitions.
Observe the structure of the environment. Sqrt is a symbol in the
global environment that is bound to a procedure object whose associated
environment is the global environment. When sqrt was called, a new
environment E1 was formed, subordinate to the global environment, in which the
parameter x is bound to 2. The body of sqrt was then evaluated
in E1. Since the first expression in the body of sqrt is
evaluating this expression defined the procedure good-enough? in the
environment E1. To be more precise, the symbol good-enough? was added
to the first frame of E1, bound to a procedure object whose associated
environment is E1. Similarly, improve and sqrt-iter were defined
as procedures in E1. For conciseness, Figure 3-11 shows only the
procedure object for good-enough? .
After the local procedures were defined, the expression (sqrt-iter 1.0)
was evaluated, still in environment E1. So the procedure object bound to
sqrt-iter in E1 was called with 1 as an argument. This created an
environment E2 in which guess , the parameter of sqrt-iter , is
bound to 1. Sqrt-iter in turn called good-enough? with the value
of guess (from E2) as the argument for good-enough? . This set up
another environment, E3, in which guess (the parameter of
good-enough? ) is bound to 1. Although sqrt-iter and
good-enough? both have a parameter named guess , these are two
distinct local variables located in different frames. Also, E2 and E3 both
have E1 as their enclosing environment, because the sqrt-iter and
good-enough? procedures both have E1 as their environment part. One
consequence of this is that the symbol x that appears in the body of
good-enough? will reference the binding of x that appears in E1,
namely the value of x with which the original sqrt procedure was
called.
The environment model thus explains the two key properties that make local
procedure definitions a useful technique for modularizing programs:
The names of the local procedures do not interfere with names external to the
enclosing procedure, because the local procedure names will be bound in the
frame that the procedure creates when it is run, rather than being bound in the
global environment.
The local procedures can access the arguments of the enclosing procedure,
simply by using parameter names as free variables. This is because the body of
the local procedure is evaluated in an environment that is subordinate to the
evaluation environment for the enclosing procedure.
Exercise 3.11: In section 3-2-3 we saw how
the environment model described the behavior of procedures with local state.
Now we have seen how internal definitions work. A typical message-passing
procedure contains both of these aspects. Consider the bank account procedure
of section 3-1-1:
Where is the local state for acc kept? Suppose we define another
account
(define acc2 (make-account 100))
How are the local states for the two accounts kept distinct? Which parts of
the environment structure are shared between acc and acc2 ?
Modeling with Mutable Data
Chapter 2 dealt with compound data as a means for constructing computational
objects that have several parts, in order to model real-world objects that have
several aspects. In that chapter we introduced the discipline of data
abstraction, according to which data structures are specified in terms of
constructors, which create data objects, and selectors, which access the parts
of compound data objects. But we now know that there is another aspect of data
that Chapter 2 did not address. The desire to model systems composed of
objects that have changing state leads us to the need to modify compound data
objects, as well as to construct and select from them. In order to model
compound objects with changing state, we will design data abstractions to
include, in addition to selectors and constructors, operations called
mutators
, which modify data objects. For instance, modeling a
banking system requires us to change account balances. Thus, a data structure
for representing bank accounts might admit an operation
(set-balance! )
that changes the balance of the designated account to the designated new value.
Data objects for which mutators are defined are known as mutable data
objects
.
Chapter 2 introduced pairs as a general-purpose ``glue'' for synthesizing
compound data. We begin this section by defining basic mutators for pairs, so
that pairs can serve as building blocks for constructing mutable data objects.
These mutators greatly enhance the representational power of pairs, enabling us
to build data structures other than the sequences and trees that we worked with
in section 2-2. We also present some examples of simulations in which
complex systems are modeled as collections of objects with local state.
@menu
* 3-3-1:: Mutable List Structure
* 3-3-2:: Representing Queues
* 3-3-3:: Representing Tables
* 3-3-4:: A Simulator for Digital Circuits
* 3-3-5:: Propagation of Constraints
@end menu
Mutable List Structure
The basic operations on pairs--- cons , car , and cdr ---can
be used to construct list structure and to select parts from list structure,
but they are incapable of modifying list structure. The same is true of the
list operations we have used so far, such as append and list ,
since these can be defined in terms of cons , car , and cdr .
To modify list structures we need new operations.
Figure 3.12: Lists x : ((a b) c d)
and y : (e f) .
+---+---+ +---+---+ +---+---+
x -->| * | *-+---->| * | *-+---->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+
| V V
| +---+ +---+
| | c | | d |
| +---+ +---+
| +---+---+ +---+---+
+---------->| * | *-+---->| * | / |
+-|-+---+ +-|-+---+
V V
+---+ +---+
| a | | b |
+---+ +---+
+---+---+ +---+---+
y -->| * | *-+---->| * | / |
+-|-+---+ +-|-+---+
V V
+---+ +---+
| e | | f |
+---+ +---+
Figure 3.13: Effect of (set-car! x y) on
the lists in Figure 3-12.
+---+---+ +---+---+ +---+---+
x -->| * | *-+---->| * | *-+---->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+
| V V
| +---+ +---+
| | c | | d |
| +---+ +---+
| +---+---+ +---+---+
| | * | *-+---->| * | / |
| +-|-+---+ +-|-+---+
| V V
| +---+ +---+
| | a | | b |
| +---+ +---+
+---------->+---+---+ +---+---+
| * | *-+---->| * | / |
y -->+-|-+---+ +-|-+---+
V V
+---+ +---+
| e | | f |
+---+ +---+
Figure 3.14: Effect of (define z (cons y
(cdr x))) on the lists in Figure 3-12.
+---+---+ +---+---+ +---+---+
x -->| * | *-+---->| * | *-+---->| * | / |
+-|-+---+ +-->+-|-+---+ +-|-+---+
| | V V
| | +---+ +---+
| | | c | | d |
| | +---+ +---+
| | +---+---+ +---+---+
+-------+-->| * | *-+---->| * | / |
| +-|-+---+ +-|-+---+
+---+---+ | V V
z -->| * | *-+-+ +---+ +---+
+-|-+---+ | a | | b |
| +---+ +---+
+---------->+---+---+ +---+---+
| * | *-+---->| * | / |
y -->+-|-+---+ +-|-+---+
V V
+---+ +---+
| e | | f |
+---+ +---+
Figure 3.15: Effect of (set-cdr! x y) on
the lists in Figure 3-12.
+---+---+ +---+---+ +---+---+
x -->| * | * | | * | *-+---->| * | / |
+-|-+-|-+ +-|-+---+ +-|-+---+
| | V V
| | +---+ +---+
| | | c | | d |
| | +---+ +---+
| | +---+---+ +---+---+
+---+------>| * | *-+---->| * | / |
| +-|-+---+ +-|-+---+
| V V
| +---+ +---+
| | a | | b |
| +---+ +---+
+------>+---+---+ +---+---+
| * | *-+---->| * | / |
y -->+-|-+---+ +-|-+---+
V V
+---+ +---+
| e | | f |
+---+ +---+
The primitive mutators for pairs are set-car! and
set-cdr! . Set-car! takes two arguments, the first of which must
be a pair. It modifies this pair, replacing the car pointer by a
pointer to the second argument of set-car! .
Set-car! and
set-cdr! return implementation-dependent values. Like set! , they
should be used only for their effect.
As an example, suppose that x is bound to the list ((a b) c d)
and y to the list (e f) as illustrated in Figure 3-12.
Evaluating the expression (set-car! x y) modifies the pair to which
x is bound, replacing its car by the value of y . The
result of the operation is shown in Figure 3-13. The structure x
has been modified and would now be printed as ((e f) c d) . The pairs
representing the list (a b) , identified by the pointer that was
replaced, are now detached from the original structure.
We see from
this that mutation operations on lists can create ``garbage'' that is not part
of any accessible structure. We will see in section 5-3-2 that Lisp
memory-management systems include a garbage collector
, which
identifies and recycles the memory space used by unneeded pairs.
Compare Figure 3-13 with Figure 3-14, which illustrates the result
of executing (define z (cons y (cdr x))) with x and y
bound to the original lists of Figure 3-12. The variable z is now
bound to a new pair created by the cons operation; the list to which
x is bound is unchanged.
The set-cdr! operation is similar to set-car! . The only
difference is that the cdr pointer of the pair, rather than the
car pointer, is replaced. The effect of executing (set-cdr! x y)
on the lists of Figure 3-12 is shown in Figure 3-15. Here the
cdr pointer of x has been replaced by the pointer to (e
f) . Also, the list (c d) , which used to be the cdr of x ,
is now detached from the structure.
Cons builds new list structure by creating new pairs, while
set-car! and set-cdr! modify existing pairs. Indeed, we could
implement cons in terms of the two mutators, together with a procedure
get-new-pair , which returns a new pair that is not part of any existing
list structure. We obtain the new pair, set its car and cdr
pointers to the designated objects, and return the new pair as the result of
the cons .
Get-new-pair is one of the operations that
must be implemented as part of the memory management required by a Lisp
implementation. We will discuss this in section 5-3-1.
(define (cons x y)
(let ((new (get-new-pair)))
(set-car! new x)
(set-cdr! new y)
new))
Exercise 3.12: The following procedure for
appending lists was introduced in section 2-2-1:
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
Append forms a new list by successively cons ing the elements of
x onto y . The procedure append! is similar to
append , but it is a mutator rather than a constructor. It appends the
lists by splicing them together, modifying the final pair of x so that
its cdr is now y . (It is an error to call append! with an
empty x .)
(define (append! x y)
(set-cdr! (last-pair x) y)
x)
Here last-pair is a procedure that returns the last pair in its
argument:
Draw a box-and-pointer diagram that shows the structure z created by
(define z (make-cycle (list 'a 'b 'c)))
What happens if we try to compute (last-pair z) ?
Exercise 3.14: The following procedure is quite
useful, although obscure:
(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))
Loop uses the ``temporary'' variable temp to hold the old value
of the cdr of x , since the set-cdr! on the next line
destroys the cdr . Explain what mystery does in general. Suppose
v is defined by (define v (list 'a 'b 'c 'd)) . Draw the
box-and-pointer diagram that represents the list to which v is bound.
Suppose that we now evaluate (define w (mystery v)) . Draw
box-and-pointer diagrams that show the structures v and w after
evaluating this expression. What would be printed as the values of v
and w ?
Sharing and identity
We mentioned in section 3-1-3 the theoretical issues of ``sameness'' and
``change'' raised by the introduction of assignment. These issues arise in
practice when individual pairs are shared
among different data
objects. For example, consider the structure formed by
(define x (list 'a 'b))
(define z1 (cons x x))
As shown in Figure 3-16, z1 is a pair whose car and
cdr both point to the same pair x . This sharing of x by
the car and cdr of z1 is a consequence of the
straightforward way in which cons is implemented. In general, using
cons to construct lists will result in an interlinked structure of pairs
in which many individual pairs are shared by many different structures.
Figure 3.16: The list z1 formed by
(cons x x) .
+---+---+
z1 -->| * | * |
+-|-+-|-+
V V
+---+---+ +---+---+
x -->| * | *-+---->| * | / |
+-|-+---+ +-|-+---+
V V
+---+ +---+
| a | | b |
+---+ +---+
Figure 3.17: The list z2 formed by
(cons (list 'a 'b) (list 'a 'b)) .
In contrast to Figure 3-16, Figure 3-17 shows the structure created
by
(define z2 (cons (list 'a 'b) (list 'a 'b)))
In this structure, the pairs in the two (a b) lists are distinct,
although the actual symbols are shared.
The two pairs are distinct
because each call to cons returns a new pair. The symbols are shared;
in Scheme there is a unique symbol with any given name. Since Scheme provides
no way to mutate a symbol, this sharing is undetectable. Note also that the
sharing is what enables us to compare symbols using eq? , which simply
checks equality of pointers.
When thought of as a list, z1 and z2 both represent ``the same''
list, ((a b) a b) . In general, sharing is completely undetectable if we
operate on lists using only cons , car , and cdr . However,
if we allow mutators on list structure, sharing becomes significant. As an
example of the difference that sharing can make, consider the following
procedure, which modifies the car of the structure to which it is
applied:
Even though z1 and z2 are ``the same'' structure, applying
set-to-wow! to them yields different results. With z1 , altering
the car also changes the cdr , because in z1 the car
and the cdr are the same pair. With z2 , the car and
cdr are distinct, so set-to-wow! modifies only the car :
z1
((a b) a b)
(set-to-wow! z1)
((wow b) wow b)
z2
((a b) a b)
(set-to-wow! z2)
((wow b) a b)
One way to detect sharing in list structures is to use the predicate
eq? , which we introduced in section 2-3-1 as a way to test whether
two symbols are equal. More generally, (eq? x y) tests whether
x and y are the same object (that is, whether x and
y are equal as pointers). Thus, with z1 and z2 as defined
in figures Figure 3-16 and Figure 3-17, (eq? (car z1) (cdr
z1)) is true and (eq? (car z2) (cdr z2)) is false.
As will be seen in the following sections, we can exploit sharing to greatly
extend the repertoire of data structures that can be represented by pairs. On
the other hand, sharing can also be dangerous, since modifications made to
structures will also affect other structures that happen to share the modified
parts. The mutation operations set-car! and set-cdr! should be
used with care; unless we have a good understanding of how our data objects are
shared, mutation can have unanticipated results.
The subtleties of
dealing with sharing of mutable data objects reflect the underlying issues of
``sameness'' and ``change'' that were raised in section 3-1-3. We
mentioned there that admitting change to our language requires that a compound
object must have an ``identity'' that is something different from the pieces
from which it is composed. In Lisp, we consider this ``identity'' to be the
quality that is tested by eq? , i.e., by equality of pointers. Since in
most Lisp implementations a pointer is essentially a memory address, we are
``solving the problem'' of defining the identity of objects by stipulating that
a data object ``itself'' is the information stored in some particular set of
memory locations in the computer. This suffices for simple Lisp programs, but
is hardly a general way to resolve the issue of ``sameness'' in computational
models.
Exercise 3.15: Draw box-and-pointer diagrams to
explain the effect of set-to-wow! on the structures z1 and
z2 above.
Exercise 3.16: Ben Bitdiddle decides to write a
procedure to count the number of pairs in any list structure. ``It's easy,''
he reasons. ``The number of pairs in any structure is the number in the
car plus the number in the cdr plus one more to count the current
pair.'' So Ben writes the following procedure:
Show that this procedure is not correct. In particular, draw box-and-pointer
diagrams representing list structures made up of exactly three pairs for which
Ben's procedure would return 3; return 4; return 7; never return at all.
Exercise 3.17: Devise a correct version of the
count-pairs procedure of Exercise 3-16 that returns the number of
distinct pairs in any structure. (Hint: Traverse the structure, maintaining an
auxiliary data structure that is used to keep track of which pairs have already
been counted.)
Exercise 3.18: Write a procedure that examines a
list and determines whether it contains a cycle, that is, whether a program
that tried to find the end of the list by taking successive cdr s would
go into an infinite loop. Exercise 3-13 constructed such lists.
Exercise 3.19: Redo Exercise 3-18 using an
algorithm that takes only a constant amount of space. (This requires a very
clever idea.)
Mutation is just assignment
When we introduced compound data, we observed in section 2-1-3 that pairs
can be represented purely in terms of procedures:
(define (cons x y)
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
(else (error "Undefined operation -- CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
The same observation is true for mutable data. We can implement mutable data
objects as procedures using assignment and local state. For instance, we can
extend the above pair implementation to handle set-car! and
set-cdr! in a manner analogous to the way we implemented bank accounts
using make-account in section 3-1-1:
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y!  As soon as we admit set! to our language, we raise all
the issues, not only of assignment, but of mutable data in general.
On
the other hand, from the viewpoint of implementation, assignment requires us to
modify the environment, which is itself a mutable data structure. Thus,
assignment and mutation are equipotent: Each can be implemented in terms of the
other.
Exercise 3.20: Draw environment diagrams to
illustrate the evaluation of the sequence of expressions
(define x (cons 1 2))
(define z (cons x x))
(set-car! (cdr z) 17)
(car x)
17
using the procedural implementation of pairs given above. (Compare
Exercise 3-11.)
Representing Queues
The mutators set-car! and set-cdr! enable us to use pairs to
construct data structures that cannot be built with cons , car ,
and cdr alone. This section shows how to use pairs to represent a data
structure called a queue. Section 3-3-3 will show how to represent data
structures called tables.
A queue
is a sequence in which items are inserted at one end (called
the rear
of the queue) and deleted from the other end (the
front
). Figure 3-18 shows an initially empty queue in which
the items a and b are inserted. Then a is removed,
c and d are inserted, and b is removed. Because items are
always removed in the order in which they are inserted, a queue is sometimes
called a FIFO
(first in, first out) buffer.
Figure 3.18: Queue operations.
Operation Resulting Queue
(define q (make-queue))
(insert-queue! q 'a) a
(insert-queue! q 'b) a b
(delete-queue! q) b
(insert-queue! q 'c) b c
(insert-queue! q 'd) b c d
(delete-queue! q) c d
In terms of data abstraction, we can regard a queue as defined by the following
set of operations:
a constructor: (make-queue) returns an empty queue (a queue containing
no items).
two selectors:
(empty-queue? )
tests if the queue is empty.
(front-queue )
returns the object at the front of the queue, signaling an error if the queue
is empty; it does not modify the queue.
two mutators:
(insert-queue! )
inserts the item at the rear of the queue and returns the modified queue as its
value.
(delete-queue! )
removes the item at the front of the queue and returns the modified queue as
its value, signaling an error if the queue is empty before the deletion.
Because a queue is a sequence of items, we could certainly represent it as an
ordinary list; the front of the queue would be the car of the list,
inserting an item in the queue would amount to appending a new element at the
end of the list, and deleting an item from the queue would just be taking the
cdr of the list. However, this representation is inefficient, because
in order to insert an item we must scan the list until we reach the end. Since
the only method we have for scanning a list is by successive cdr
operations, this scanning requires [theta](n) steps for a list of n
items. A simple modification to the list representation overcomes this
disadvantage by allowing the queue operations to be implemented so that they
require [theta](1) steps; that is, so that the number of steps needed is
independent of the length of the queue.
The difficulty with the list representation arises from the need to scan to
find the end of the list. The reason we need to scan is that, although the
standard way of representing a list as a chain of pairs readily provides us
with a pointer to the beginning of the list, it gives us no easily accessible
pointer to the end. The modification that avoids the drawback is to represent
the queue as a list, together with an additional pointer that indicates the
final pair in the list. That way, when we go to insert an item, we can consult
the rear pointer and so avoid scanning the list.
A queue is represented, then, as a pair of pointers, front-ptr and
rear-ptr , which indicate, respectively, the first and last pairs in an
ordinary list. Since we would like the queue to be an identifiable object, we
can use cons to combine the two pointers. Thus, the queue itself will
be the cons of the two pointers. Figure 3-19 illustrates this
representation.
Figure 3.19: Implementation of a queue as a list
with front and rear pointers.
+---+---+
q -->| * | *-+-------------------+
+-|-+---+ |
| |
| front-ptr | rear-ptr
V V
+---+---+ +---+---+ +---+---+
| * | *-+--->| * | *-+--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+
V V V
+---+ +---+ +---+
| a | | b | | c |
+---+ +---+ +---+
To define the queue operations we use the following procedures, which enable us
to select and to modify the front and rear pointers of a queue:
The make-queue constructor returns, as an initially empty queue, a pair
whose car and cdr are both the empty list:
(define (make-queue) (cons '() '()))
To select the item at the front of the queue, we return the car of the
pair indicated by the front pointer:
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))
To insert an item in a queue, we follow the method whose result is indicated in
Figure 3-20. We first create a new pair whose car is the item to
be inserted and whose cdr is the empty list. If the queue was initially
empty, we set the front and rear pointers of the queue to this new pair.
Otherwise, we modify the final pair in the queue to point to the new pair, and
also set the rear pointer to the new pair.
Figure 3.20: Result of using (insert-queue!
q 'd) on the queue of Figure 3-19.
+---+---+
q -->| * | *-+--------------------------------+
+-|-+---+ |
| |
| front-ptr | rear-ptr
V V
+---+---+ +---+---+ +---+---+ +---+---+
| * | *-+--->| * | *-+--->| * | *-+--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
V V V V
+---+ +---+ +---+ +---+
| a | | b | | c | | d |
+---+ +---+ +---+ +---+
To delete the item at the front of the queue, we merely modify the front
pointer so that it now points at the second item in the queue, which can be
found by following the cdr pointer of the first item (see Figure
3-21):
If the first item is the final item in the queue, the front
pointer will be the empty list after the deletion, which will mark the queue as
empty; we needn't worry about updating the rear pointer, which will still point
to the deleted item, because empty-queue? looks only at the front
pointer.
Figure 3.21: Result of using (delete-queue!
q) on the queue of Figure 3-20.
+---+---+
q -->| * | *-+--------------------------------+
+-|-+---+ |
+------------+ |
front-ptr | | rear-ptr
V V
+---+---+ +---+---+ +---+---+ +---+---+
| * | *-+--->| * | *-+--->| * | *-+--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
V V V V
+---+ +---+ +---+ +---+
| a | | b | | c | | d |
+---+ +---+ +---+ +---+
(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))
Exercise 3.21: Ben Bitdiddle decides to test the
queue implementation described above. He types in the procedures to the Lisp
interpreter and proceeds to try them out:
(define q1 (make-queue))
(insert-queue! q1 'a)
((a) a)
(insert-queue! q1 'b)
((a b) b)
(delete-queue! q1)
((b) b)
(delete-queue! q1)
(() b)
``It's all wrong!'' he complains. ``The interpreter's response shows that the
last item is inserted into the queue twice. And when I delete both items, the
second b is still there, so the queue isn't empty, even though it's
supposed to be.'' Eva Lu Ator suggests that Ben has misunderstood what is
happening. ``It's not that the items are going into the queue twice,'' she
explains. ``It's just that the standard Lisp printer doesn't know how to make
sense of the queue representation. If you want to see the queue printed
correctly, you'll have to define your own print procedure for queues.'' Explain
what Eva Lu is talking about. In particular, show why Ben's examples produce
the printed results that they do. Define a procedure print-queue that
takes a queue as input and prints the sequence of items in the queue.
Exercise 3.22: Instead of representing a queue
as a pair of pointers, we can build a queue as a procedure with local state.
The local state will consist of pointers to the beginning and the end of an
ordinary list. Thus, the make-queue procedure will have the form
Complete the definition of make-queue and provide implementations of the
queue operations using this representation.
Exercise 3.23: A deque
(``double-ended
queue'') is a sequence in which items can be inserted and deleted at either the
front or the rear. Operations on deques are the constructor make-deque ,
the predicate empty-deque? , selectors front-deque and
rear-deque , and mutators front-insert-deque! ,
rear-insert-deque! , front-delete-deque! , and
rear-delete-deque! . Show how to represent deques using pairs, and give
implementations of the operations.
Be careful not to make the
interpreter try to print a structure that contains cycles. (See Exercise
3-13.)
All operations should be accomplished in [theta](1) steps.
Representing Tables
When we studied various ways of representing sets in Chapter 2, we
mentioned in section 2-3-3 the task of maintaining a table of records
indexed by identifying keys. In the implementation of data-directed
programming in section 2-4-3, we made extensive use of two-dimensional
tables, in which information is stored and retrieved using two keys. Here we
see how to build tables as mutable list structures.
We first consider a one-dimensional table, in which each value is stored under
a single key. We implement the table as a list of records, each of which is
implemented as a pair consisting of a key and the associated value. The records
are glued together to form a list by pairs whose car s point to
successive records. These gluing pairs are called the backbone
of
the table. In order to have a place that we can change when we add a new
record to the table, we build the table as a headed list
. A headed
list has a special backbone pair at the beginning, which holds a dummy
``record''---in this case the arbitrarily chosen symbol *table* .
Figure 3-22 shows the box-and-pointer diagram for the table
a: 1
b: 2
c: 3
Figure 3.22: A table represented as a headed list.
+---+---+ +---+---+ +---+---+ +---+---+
| * | *-+--->| * | *-+--->| * | *-+--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
| | | |
V V V V
+---------+ +---+---+ +---+---+ +---+---+
| *table* | | * | * | | * | * | | * | * |
+---------+ +-|-+-|-+ +-|-+-|-+ +-|-+-|-+
| | | | | |
V V V V V V
+---+ +---+ +---+ +---+ +---+ +---+
| a | | 1 | | b | | 2 | | c | | 3 |
+---+ +---+ +---+ +---+ +---+ +---+
To extract information from a table we use the lookup procedure, which
takes a key as argument and returns the associated value (or false if there is
no value stored under that key). Lookup is defined in terms of the
assoc operation, which expects a key and a list of records as arguments.
Note that assoc never sees the dummy record. Assoc returns the
record that has the given key as its car .
Because assoc
uses equal? , it can recognize keys that are symbols, numbers, or list
structure.
Lookup then checks to see that the resulting record
returned by assoc is not false, and returns the value (the cdr )
of the record.
To insert a value in a table under a specified key, we first use assoc
to see if there is already a record in the table with this key. If not, we
form a new record by cons ing the key with the value, and insert this at
the head of the table's list of records, after the dummy record. If there
already is a record with this key, we set the cdr of this record to the
designated new value. The header of the table provides us with a fixed
location to modify in order to insert the new record.
Thus, the first
backbone pair is the object that represents the table ``itself''; that is, a
pointer to the table is a pointer to this pair. This same backbone pair always
starts the table. If we did not arrange things in this way, insert!
would have to return a new value for the start of the table when it added a new
record.
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value) (cdr table)))))
'ok)
To construct a new table, we simply create a list containing the symbol
*table* :
(define (make-table)
(list '*table*))
Two-dimensional tables
In a two-dimensional table, each value is indexed by two keys. We can
construct such a table as a one-dimensional table in which each key identifies
a subtable. Figure 3-23 shows the box-and-pointer diagram for the table
math:
+: 43
-: 45
*: 42
letters:
a: 97
b: 98
which has two subtables. (The subtables don't need a special header symbol,
since the key that identifies the subtable serves this purpose.)
Figure 3.23: A two-dimensional table.
table
|
V
+---+---+ +---+---+ +---+---+
| * | *-+-->| * | *-+-->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+
V | V
+-------+ | +---+---+ +---+---+ +---+---+
|*table*| | | * | *-+-->| * | *-+-->| * | / |
+-------+ | +-|-+---+ +-|-+---+ +-|-+---+
| V V V
| +-------+ +---+---+ +---+---+
| |letters| | * | * | | * | * |
| +-------+ +-|-+-|-+ +-|-+-|-+
| V V V V
| +---+ +---+ +---+ +---+
| | a | | 97| | b | | 98|
| +---+ +---+ +---+ +---+
V
+---+---+ +---+---+ +---+---+ +---+---+
| * | *-+-->| * | *-+-->| * | *-+-->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
V V V V
+------+ +---+---+ +---+---+ +---+---+
| math | | * | * | | * | * | | * | * |
+------+ +-|-+-|-+ +-|-+-|-+ +-|-+-|-+
V V V V V V
+---+ +---+ +---+ +---+ +---+ +---+
| + | | 43| | - | | 45| | * | | 42|
+---+ +---+ +---+ +---+ +---+ +---+
When we look up an item, we use the first key to identify the correct subtable.
Then we use the second key to identify the record within the subtable.
To insert a new item under a pair of keys, we use assoc to see if there
is a subtable stored under the first key. If not, we build a new subtable
containing the single record ( key-2 , value ) and insert it into
the table under the first key. If a subtable already exists for the first key,
we insert the new record into this subtable, using the insertion method for
one-dimensional tables described above:
The lookup and insert! operations defined above take the table as
an argument. This enables us to use programs that access more than one table.
Another way to deal with multiple tables is to have separate lookup and
insert! procedures for each table. We can do this by representing a
table procedurally, as an object that maintains an internal table as part of
its local state. When sent an appropriate message, this ``table object''
supplies the procedure with which to operate on the internal table. Here is a
generator for two-dimensional tables represented in this fashion:
Using make-table , we could implement the get and put
operations used in section 2-4-3 for data-directed programming, as
follows:
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
Get takes as arguments two keys, and put takes as arguments two
keys and a value. Both operations access the same local table, which is
encapsulated within the object created by the call to make-table .
Exercise 3.24: In the table implementations
above, the keys are tested for equality using equal? (called by
assoc ). This is not always the appropriate test. For instance, we
might have a table with numeric keys in which we don't need an exact match to
the number we're looking up, but only a number within some tolerance of it.
Design a table constructor make-table that takes as an argument a
same-key? procedure that will be used to test ``equality'' of keys.
Make-table should return a dispatch procedure that can be used to
access appropriate lookup and insert! procedures for a local
table.
Exercise 3.25: Generalizing one- and
two-dimensional tables, show how to implement a table in which values are
stored under an arbitrary number of keys and different values may be stored
under different numbers of keys. The lookup and insert!
procedures should take as input a list of keys used to access the table.
Exercise 3.26: To search a table as implemented
above, one needs to scan through the list of records. This is basically the
unordered list representation of section 2-3-3. For large tables, it may
be more efficient to structure the table in a different manner. Describe a
table implementation where the (key, value) records are organized using a
binary tree, assuming that keys can be ordered in some way (e.g., numerically
or alphabetically). (Compare Exercise 2-66 of Chapter 2.)
Exercise 3.27: Memoization
(also
called tabulation
) is a technique that enables a procedure to record,
in a local table, values that have previously been computed. This technique
can make a vast difference in the performance of a program. A memoized
procedure maintains a table in which values of previous calls are stored using
as keys the arguments that produced the values. When the memoized procedure is
asked to compute a value, it first checks the table to see if the value is
already there and, if so, just returns that value. Otherwise, it computes the
new value in the ordinary way and stores this in the table. As an example of
memoization, recall from section 1-2-2 the exponential process for
computing Fibonacci numbers:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
The memoized version of the same procedure is
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
where the memoizer is defined as
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
Draw an environment diagram to analyze the computation of (memo-fib 3) .
Explain why memo-fib computes the nth Fibonacci number in a number
of steps proportional to n. Would the scheme still work if we had simply
defined memo-fib to be (memoize fib) ?
A Simulator for Digital Circuits
Designing complex digital systems, such as computers, is an important
engineering activity. Digital systems are constructed by interconnecting
simple elements. Although the behavior of these individual elements is simple,
networks of them can have very complex behavior. Computer simulation of
proposed circuit designs is an important tool used by digital systems
engineers. In this section we design a system for performing digital logic
simulations. This system typifies a kind of program called an
event-driven simulation
, in which actions (``events'') trigger
further events that happen at a later time, which in turn trigger more events,
and so so.
Our computational model of a circuit will be composed of objects that
correspond to the elementary components from which the circuit is constructed.
There are wires
, which carry digital signals
. A digital
signal may at any moment have only one of two possible values, 0 and 1. There
are also various types of digital function boxes
, which connect wires
carrying input signals to other output wires. Such boxes produce output
signals computed from their input signals. The output signal is delayed by a
time that depends on the type of the function box. For example, an
inverter
is a primitive function box that inverts its input. If the
input signal to an inverter changes to 0, then one inverter-delay later the
inverter will change its output signal to 1. If the input signal to an
inverter changes to 1, then one inverter-delay later the inverter will change
its output signal to 0. We draw an inverter symbolically as in Figure
3-24. An and-gate
, also shown in Figure 3-24, is a primitive
function box with two inputs and one output. It drives its output signal to a
value that is the logical and
of the inputs. That is, if both of its
input signals become 1, then one and-gate-delay time later the and-gate will
force its output signal to be 1; otherwise the output will be 0. An
or-gate
is a similar two-input primitive function box that drives its
output signal to a value that is the logical or
of the inputs. That
is, the output will become 1 if at least one of the input signals is 1;
otherwise the output will become 0.
Figure 3.24: Primitive functions in the digital
logic simulator.
We can connect primitive functions together to construct more complex
functions. To accomplish this we wire the outputs of some function boxes to
the inputs of other function boxes. For example, the half-adder
circuit shown in Figure 3-25 consists of an or-gate, two and-gates, and
an inverter. It takes two input signals, A and B, and has two output signals,
S and C. S will become 1 whenever precisely one of A and B is 1, and C will
become 1 whenever A and B are both 1. We can see from the figure that, because
of the delays involved, the outputs may be generated at different times. Many
of the difficulties in the design of digital circuits arise from this fact.
Figure 3.25: A half-adder circuit.
+--------------------------------------+
| ____ |
A --------*---\ \ D ___ |
| | > >---------------| \ |
| +--|---/___/ | )----- S
| | | |\ E +--|___/ |
| | | +--| >o---+ |
| | | ___ | |/ |
| | +---| \ | |
| | | )--*----------------------- C
B -----*------|___/ |
| |
+--------------------------------------+
We will now build a program for modeling the digital logic circuits we wish to
study. The program will construct computational objects modeling the wires,
which will ``hold'' the signals. Function boxes will be modeled by procedures
that enforce the correct relationships among the signals.
One basic element of our simulation will be a procedure make-wire , which
constructs wires. For example, we can construct six wires as follows:
(define a (make-wire))
(define b (make-wire))
(define c (make-wire))
(define d (make-wire))
(define e (make-wire))
(define s (make-wire))
We attach a function box to a set of wires by calling a procedure that
constructs that kind of box. The arguments to the constructor procedure are
the wires to be attached to the box. For example, given that we can construct
and-gates, or-gates, and inverters, we can wire together the half-adder shown
in Figure 3-25:
(or-gate a b d)
ok
(and-gate a b c)
ok
(inverter c e)
ok
(and-gate d e s)
ok
Better yet, we can explicitly name this operation by defining a procedure
half-adder that constructs this circuit, given the four external wires
to be attached to the half-adder:
(define (half-adder a b s c)
(let ((d (make-wire)) (e (make-wire)))
(or-gate a b d)
(and-gate a b c)
(inverter c e)
(and-gate d e s)
'ok))
The advantage of making this definition is that we can use half-adder
itself as a building block in creating more complex circuits. Figure
3-26, for example, shows a full-adder
composed of two half-adders
and an or-gate.
A full-adder is a basic circuit element used in adding
two binary numbers. Here A and B are the bits at corresponding positions in
the two numbers to be added, and C_(in) is the carry bit from the
addition one place to the right. The circuit generates SUM, which is the sum
bit in the corresponding position, and C_(out), which is the carry
bit to be propagated to the left.
We can construct a full-adder as follows:
(define (full-adder a b c-in sum c-out)
(let ((s (make-wire))
(c1 (make-wire))
(c2 (make-wire)))
(half-adder b c-in s c1)
(half-adder a s sum c2)
(or-gate c1 c2 c-out)
'ok))
Having defined full-adder as a procedure, we can now use it as a
building block for creating still more complex circuits. (For example, see
Exercise 3-30.)
Figure 3.26: A full-adder circuit.
+----------------------------------+
| +-------+ |
A -----------------+ full +-------------- SUM
| +-------+ | adder | ____ |
B -----+ half +---+ +---\ \ |
| | adder | +-------+ >or >----- Cout
C -----+ +---------------/___/ |
| +-------+ |
+----------------------------------+
In essence, our simulator provides us with the tools to construct a language of
circuits. If we adopt the general perspective on languages with which we
approached the study of Lisp in section 1-1, we can say that the
primitive function boxes form the primitive elements of the language, that
wiring boxes together provides a means of combination, and that specifying
wiring patterns as procedures serves as a means of abstraction.
Primitive function boxes
The primitive function boxes implement the ``forces'' by which a change in the
signal on one wire influences the signals on other wires. To build function
boxes, we use the following operations on wires:
(get-signal )
returns the current value of the signal on the wire.
(set-signal! )
changes the value of the signal on the wire to the new value.
(add-action! )
asserts that the designated procedure should be run whenever the signal on the
wire changes value. Such procedures are the vehicles by which changes in the
signal value on the wire are communicated to other wires.
In addition, we will make use of a procedure after-delay that takes a
time delay and a procedure to be run and executes the given procedure after the
given delay.
Using these procedures, we can define the primitive digital logic functions.
To connect an input to an output through an inverter, we use add-action!
to associate with the input wire a procedure that will be run whenever the
signal on the input wire changes value. The procedure computes the
logical-not of the input signal, and then, after one
inverter-delay , sets the output signal to be this new value:
An and-gate is a little more complex. The action procedure must be run if
either of the inputs to the gate changes. It computes the logical-and
(using a procedure analogous to logical-not ) of the values of the
signals on the input wires and sets up a change to the new value to occur on
the output wire after one and-gate-delay .
Exercise 3.28: Define an or-gate as a primitive
function box. Your or-gate constructor should be similar to
and-gate .
Exercise 3.29: Another way to construct an
or-gate is as a compound digital logic device, built from and-gates and
inverters. Define a procedure or-gate that accomplishes this. What is
the delay time of the or-gate in terms of and-gate-delay and
inverter-delay ?
Exercise 3.30: Figure 3-27 shows a
ripple-carry adder
formed by stringing together n full-adders.
This is the simplest form of parallel adder for adding two n-bit binary
numbers. The inputs A_1, A_2, A_3, ..., A_n and B_1, B_2, B_3,
..., B_n are the two binary numbers to be added (each A_k and
B_k is a 0 or a 1). The circuit generates S_1, S_2, S_3, ..., S_n,
the n bits of the sum, and C, the carry from the addition. Write a
procedure ripple-carry-adder that generates this circuit. The procedure
should take as arguments three lists of n wires each---the A_k, the
B_k, and the S_k---and also another wire C. The major drawback of the
ripple-carry adder is the need to wait for the carry signals to propagate.
What is the delay needed to obtain the complete output from an n-bit
ripple-carry adder, expressed in terms of the delays for and-gates, or-gates,
and inverters?
Figure 3.27: A ripple-carry adder for n-bit
numbers.
A wire in our simulation will be a computational object with two local state
variables: a signal-value (initially taken to be 0) and a collection of
action-procedures to be run when the signal changes value. We implement
the wire, using message-passing style, as a collection of local procedures
together with a dispatch procedure that selects the appropriate local
operation, just as we did with the simple bank-account object in section
3-1-1:
The local procedure set-my-signal! tests whether the new signal value
changes the signal on the wire. If so, it runs each of the action procedures,
using the following procedure call-each , which calls each of the items
in a list of no-argument procedures:
The local procedure accept-action-procedure! adds the given procedure to
the list of procedures to be run, and then runs the new procedure once. (See
Exercise 3-31.)
With the local dispatch procedure set up as specified, we can provide
the following procedures to access the local operations on
wires:
[Footnote 27] These procedures are simply
syntactic sugar that allow us to use ordinary procedural syntax to access the
local procedures of objects. It is striking that we can interchange the role
of ``procedures'' and ``data'' in such a simple way. For example, if we write
(wire 'get-signal) we think of wire as a procedure that is called
with the message get-signal as input. Alternatively, writing
(get-signal wire) encourages us to think of wire as a data object
that is the input to a procedure get-signal . The truth of the matter is
that, in a language in which we can deal with procedures as objects, there is
no fundamental difference between ``procedures'' and ``data,'' and we can
choose our syntactic sugar to allow us to program in whatever style we choose.
Wires, which have time-varying signals and may be incrementally attached to
devices, are typical of mutable objects. We have modeled them as procedures
with local state variables that are modified by assignment. When a new wire is
created, a new set of state variables is allocated (by the let
expression in make-wire ) and a new dispatch procedure is
constructed and returned, capturing the environment with the new state
variables.
The wires are shared among the various devices that have been connected to
them. Thus, a change made by an interaction with one device will affect all
the other devices attached to the wire. The wire communicates the change to
its neighbors by calling the action procedures provided to it when the
connections were established.
The agenda
The only thing needed to complete the simulator is after-delay . The
idea here is that we maintain a data structure, called an agenda
,
that contains a schedule of things to do. The following operations are defined
for agendas:
(make-agenda) returns a new empty agenda.
(empty-agenda? >) is true if the specified agenda is
empty.
(first-agenda-item >) returns the first item on the
agenda.
(remove-first-agenda-item! >) modifies the agenda by
removing the first item.
(add-to-agenda!
The particular agenda that we use is denoted by the-agenda . The
procedure after-delay adds new elements to the-agenda :
The simulation is driven by the procedure propagate , which operates on
the-agenda , executing each procedure on the agenda in sequence. In
general, as the simulation runs, new items will be added to the agenda, and
propagate will continue the simulation as long as there are items on the
agenda:
The following procedure, which places a ``probe'' on a wire, shows the
simulator in action. The probe tells the wire that, whenever its signal
changes value, it should print the new signal value, together with the current
time and a name that identifies the wire:
Next we connect the wires in a half-adder circuit (as in Figure 3-25),
set the signal on input-1 to 1, and run the simulation:
(half-adder input-1 input-2 sum carry)
ok
(set-signal! input-1 1)
done
(propagate)
sum 8 New-value = 1
done
The sum signal changes to 1 at time 8. We are now eight time units from
the beginning of the simulation. At this point, we can set the signal on
input-2 to 1 and allow the values to propagate:
The carry changes to 1 at time 11 and the sum changes to 0 at
time 16.
Exercise 3.31: The internal procedure
accept-action-procedure! defined in make-wire specifies that when
a new action procedure is added to a wire, the procedure is immediately run.
Explain why this initialization is necessary. In particular, trace through the
half-adder example in the paragraphs above and say how the system's response
would differ if we had defined accept-action-procedure! as
Finally, we give details of the agenda data structure, which holds the
procedures that are scheduled for future execution.
The agenda is made up of time segments
. Each time segment is a pair
consisting of a number (the time) and a queue (see Exercise 3-32) that
holds the procedures that are scheduled to be run during that time segment.
(define (make-time-segment time queue)
(cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))
We will operate on the time-segment queues using the queue operations described
in section 3-3-2.
The agenda itself is a one-dimensional table of time segments. It differs from
the tables described in section 3-3-3 in that the segments will be sorted
in order of increasing time. In addition, we store the current time
(i.e., the time of the last action that was processed) at the head of the
agenda. A newly constructed agenda has no time segments and has a current time
of 0:
The agenda is a headed list, like the tables in section
3-3-3, but since the list is headed by the time, we do not need an
additional dummy header (such as the *table* symbol used with tables).
To add an action to an agenda, we first check if the agenda is empty. If so,
we create a time segment for the action and install this in the agenda.
Otherwise, we scan the agenda, examining the time of each segment. If we find
a segment for our appointed time, we add the action to the associated queue.
If we reach a time later than the one to which we are appointed, we insert a
new time segment into the agenda just before it. If we reach the end of the
agenda, we must create a new time segment at the end.
The procedure that removes the first item from the agenda deletes the item at
the front of the queue in the first time segment. If this deletion makes the
time segment empty, we remove it from the list of segments:
Observe
that the if expression in this procedure has no
expression. Such a ``one-armed if statement'' is used to decide whether
to do something, rather than to select between two expressions. An if
expression returns an unspecified value if the predicate is false and there is
no .
The first agenda item is found at the head of the queue in the first time
segment. Whenever we extract an item, we also update the current
time:
In this way, the current time will always be the time of the
action most recently processed. Storing this time at the head of the agenda
ensures that it will still be available even if the associated time segment has
been deleted.
Exercise 3.32: The procedures to be run during
each time segment of the agenda are kept in a queue. Thus, the procedures for
each segment are called in the order in which they were added to the agenda
(first in, first out). Explain why this order must be used. In particular,
trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the
same segment and say how the behavior would differ if we stored a segment's
procedures in an ordinary list, adding and removing procedures only at the
front (last in, first out).
Propagation of Constraints
Computer programs are traditionally organized as one-directional computations,
which perform operations on prespecified arguments to produce desired outputs.
On the other hand, we often model systems in terms of relations among
quantities. For example, a mathematical model of a mechanical structure might
include the information that the deflection d of a metal rod is related to
the force f on the rod, the length L of the rod, the cross-sectional
area A, and the elastic modulus E via the equation
dAE = FL
Such an equation is not one-directional. Given any four of the quantities, we
can use it to compute the fifth. Yet translating the equation into a
traditional computer language would force us to choose one of the quantities to
be computed in terms of the other four. Thus, a procedure for computing the
area A could not be used to compute the deflection d, even though the
computations of A and d arise from the same
equation.
Constraint propagation first appeared in the incredibly
forward-looking @acronym{SKETCHPAD
system of Ivan Sutherland (1963). A
beautiful constraint-propagation system based on the Smalltalk language was
developed by Alan Borning (1977) at Xerox Palo Alto Research Center. Sussman,
Stallman, and Steele applied constraint propagation to electrical circuit
analysis (Sussman and Stallman 1975; Sussman and Steele 1980). TK!Solver
(Konopasek and Jayaraman 1984) is an extensive modeling environment based on
constraints.}
In this section, we sketch the design of a language that enables us to work in
terms of relations themselves. The primitive elements of the language are
primitive constraints
, which state that certain relations hold
between quantities. For example, (adder a b c) specifies that the
quantities a, b, and c must be related by the equation a +
b = c, (multiplier x y z) expresses the constraint xy =
z, and (constant 3.14 x) says that the value of x must be 3.14.
Our language provides a means of combining primitive constraints in order to
express more complex relations. We combine constraints by constructing
constraint networks
, in which constraints are joined by
connectors
. A connector is an object that ``holds'' a value that may
participate in one or more constraints. For example, we know that the
relationship between Fahrenheit and Celsius temperatures is
9C = 5(F - 32)
Such a constraint can be thought of as a network consisting of primitive adder,
multiplier, and constant constraints (Figure 3-28). In the figure, we
see on the left a multiplier box with three terminals, labeled m1, m2,
and p. These connect the multiplier to the rest of the network as follows:
The m1 terminal is linked to a connector C, which will hold the Celsius
temperature. The m2 terminal is linked to a connector w, which is also
linked to a constant box that holds 9. The p terminal, which the
multiplier box constrains to be the product of m1 and m2, is linked to
the p terminal of another multiplier box, whose m2 is connected to a
constant 5 and whose m1 is connected to one of the terms in a sum.
Figure 3.28: The relation 9C = 5(F - 32)
expressed as a constraint network.
+---------+ +---------+ v +---------+
C -----+ m1 | u | m1 +-------+ a1 |
| * p +-----+ p * | | * s +---- F
+--+ m2 | | m2 +--+ +--+ a2 |
| +---------+ +---------+ | | +---------+
w | x| |y
| +-----+ +-----+ | | +-----+
+----+ 9 | | 5 +-----+ +-----+ 32 |
+-----+ +-----+ +-----+
Computation by such a network proceeds as follows: When a connector is given a
value (by the user or by a constraint box to which it is linked), it awakens
all of its associated constraints (except for the constraint that just awakened
it) to inform them that it has a value. Each awakened constraint box then
polls its connectors to see if there is enough information to determine a value
for a connector. If so, the box sets that connector, which then awakens all of
its associated constraints, and so on. For instance, in conversion between
Celsius and Fahrenheit, w, x, and y are immediately set by the
constant boxes to 9, 5, and 32, respectively. The connectors awaken the
multipliers and the adder, which determine that there is not enough information
to proceed. If the user (or some other part of the network) sets C to a
value (say 25), the leftmost multiplier will be awakened, and it will set u
to 25*9 = 225. Then u awakens the second multiplier, which sets v to
45, and v awakens the adder, which sets f to 77.
Using the constraint system
To use the constraint system to carry out the temperature computation outlined
above, we first create two connectors, C and F , by calling the
constructor make-connector , and link C and F in an
appropriate network:
(define C (make-connector))
(define F (make-connector))
(celsius-fahrenheit-converter C F)
ok
The procedure that creates the network is defined as follows:
(define (celsius-fahrenheit-converter c f)
(let ((u (make-connector))
(v (make-connector))
(w (make-connector))
(x (make-connector))
(y (make-connector)))
(multiplier c w u)
(multiplier v x u)
(adder v y f)
(constant 9 w)
(constant 5 x)
(constant 32 y)
'ok))
This procedure creates the internal connectors u , v , w ,
x , and y , and links them as shown in Figure 3-28 using the
primitive constraint constructors adder , multiplier , and
constant . Just as with the digital-circuit simulator of section
3-3-4, expressing these combinations of primitive elements in terms of
procedures automatically provides our language with a means of abstraction for
compound objects.
To watch the network in action, we can place probes on the connectors C
and F , using a probe procedure similar to the one we used to
monitor wires in section 3-3-4. Placing a probe on a connector will
cause a message to be printed whenever the connector is given a value:
(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)
Next we set the value of C to 25. (The third argument to
set-value! tells C that this directive comes from the
user .)
The probe on C awakens and reports the value. C also propagates
its value through the network as described above. This sets F to 77,
which is reported by the probe on F .
Now we can try to set F to a new value, say 212:
(set-value! F 212 'user)
Error! Contradiction (77 212)
The connector complains that it has sensed a contradiction: Its value is 77,
and someone is trying to set it to 212. If we really want to reuse the network
with new values, we can tell C to forget its old value:
C finds that the user , who set its value originally, is now
retracting that value, so C agrees to lose its value, as shown by the
probe, and informs the rest of the network of this fact. This information
eventually propagates to F , which now finds that it has no reason for
continuing to believe that its own value is 77. Thus, F also gives up
its value, as shown by the probe.
Now that F has no value, we are free to set it to 212:
This new value, when propagated through the network, forces C to have a
value of 100, and this is registered by the probe on C . Notice that the
very same network is being used to compute C given F and to
compute F given C . This nondirectionality of computation is the
distinguishing feature of constraint-based systems.
Implementing the constraint system
The constraint system is implemented via procedural objects with local state,
in a manner very similar to the digital-circuit simulator of section
3-3-4. Although the primitive objects of the constraint system are
somewhat more complex, the overall system is simpler, since there is no concern
about agendas and logic delays.
The basic operations on connectors are the following:
(has-value? >) tells whether the connector has a value.
(get-value >) returns the connector's current value.
(set-value! > <@var{new-value> )}
indicates that the informant is requesting the connector to set its value to
the new value.
(forget-value! > <@var{retractor>)} tells the connector
that the retractor is requesting it to forget its value.
(connect > <@var{new-constraint>)} tells the connector
to participate in the new constraint.
The connectors communicate with the constraints by means of the procedures
inform-about-value , which tells the given constraint that the connector
has a value, and inform-about-no-value , which tells the constraint that
the connector has lost its value.
Adder constructs an adder constraint among summand connectors a1
and a2 and a sum connector. An adder is implemented as a
procedure with local state (the procedure me below):
Adder connects the new adder to the designated connectors and returns it
as its value. The procedure me , which represents the adder, acts as a
dispatch to the local procedures. The following ``syntax interfaces'' (see
footnote Footnote 27 in section 3-3-4) are used in conjunction with
the dispatch:
The adder's local procedure process-new-value is called when the adder
is informed that one of its connectors has a value. The adder first checks to
see if both a1 and a2 have values. If so, it tells sum to
set its value to the sum of the two addends. The informant argument to
set-value! is me , which is the adder object itself. If a1
and a2 do not both have values, then the adder checks to see if perhaps
a1 and sum have values. If so, it sets a2 to the
difference of these two. Finally, if a2 and sum have values,
this gives the adder enough information to set a1 . If the adder is told
that one of its connectors has lost a value, it requests that all of its
connectors now lose their values. (Only those values that were set by this
adder are actually lost.) Then it runs process-new-value . The reason
for this last step is that one or more connectors may still have a value (that
is, a connector may have had a value that was not originally set by the adder),
and these values may need to be propagated back through the adder.
A multiplier is very similar to an adder. It will set its product to 0
if either of the factors is 0, even if the other factor is not known.
A constant constructor simply sets the value of the designated
connector. Any I-have-a-value or I-lost-my-value message sent to
the constant box will produce an error.
A connector is represented as a procedural object with local state variables
value , the current value of the connector; informant , the object
that set the connector's value; and constraints , a list of the
constraints in which the connector participates.
The connector's local procedure set-my-value is called when there is a
request to set the connector's value. If the connector does not currently have
a value, it will set its value and remember as informant the constraint
that requested the value to be set.
The setter might not be a
constraint. In our temperature example, we used user as the
setter .
Then the connector will notify all of its participating
constraints except the constraint that requested the value to be set. This is
accomplished using the following iterator, which applies a designated procedure
to all items in a list except a given one:
If a connector is asked to forget its value, it runs the local procedure
forget-my-value , which first checks to make sure that the request is
coming from the same object that set the value originally. If so, the
connector informs its associated constraints about the loss of the value.
The local procedure connect adds the designated new constraint to the
list of constraints if it is not already in that list. Then, if the connector
has a value, it informs the new constraint of this fact.
The connector's procedure me serves as a dispatch to the other internal
procedures and also represents the connector as an object. The following
procedures provide a syntax interface for the dispatch:
Exercise 3.33: Using primitive multiplier,
adder, and constant constraints, define a procedure averager that takes
three connectors a , b , and c as inputs and establishes the
constraint that the value of c is the average of the values of a
and b .
Exercise 3.34: Louis Reasoner wants to build a
squarer, a constraint device with two terminals such that the value of
connector b on the second terminal will always be the square of the
value a on the first terminal. He proposes the following simple device
made from a multiplier:
(define (squarer a b)
(multiplier a a b))
There is a serious flaw in this idea. Explain.
Exercise 3.35: Ben Bitdiddle tells Louis that
one way to avoid the trouble in Exercise 3-34 is to define a squarer as a
new primitive constraint. Fill in the missing portions in Ben's outline for a
procedure to implement such a constraint:
(define (squarer a b)
(define (process-new-value)
(if (has-value? b)
(if (< (get-value b) 0)
(error "square less than 0 -- SQUARER" (get-value b))
)
))
(define (process-forget-value) )
(define (me request) )
me)
Exercise 3.36: Suppose we evaluate the following
sequence of expressions in the global environment:
(define a (make-connector))
(define b (make-connector))
(set-value! a 10 'user)
At some time during evaluation of the set-value! , the following
expression from the connector's local procedure is evaluated:
Draw an environment diagram showing the environment in which the above
expression is evaluated.
Exercise 3.37: The
celsius-fahrenheit-converter procedure is cumbersome when compared with
a more expression-oriented style of definition, such as
(define (celsius-fahrenheit-converter x)
(c+ (c* (c/ (cv 9) (cv 5))
x)
(cv 32)))
(define C (make-connector))
(define F (celsius-fahrenheit-converter C))
Here c+ , c* , etc. are the ``constraint'' versions of the
arithmetic operations. For example, c+ takes two connectors as
arguments and returns a connector that is related to these by an adder
constraint:
(define (c+ x y)
(let ((z (make-connector)))
(adder x y z)
z))
Define analogous procedures c- , c* , c/ , and cv
(constant value) that enable us to define compound constraints as in the
converter example above.
The expression-oriented format is convenient
because it avoids the need to name the intermediate expressions in a
computation. Our original formulation of the constraint language is cumbersome
in the same way that many languages are cumbersome when dealing with operations
on compound data. For example, if we wanted to compute the product (a +
b) * (c + d), where the variables represent vectors, we could work
in ``imperative style,'' using procedures that set the values of designated
vector arguments but do not themselves return vectors as values:
(v-sum a b temp1)
(v-sum c d temp2)
(v-prod temp1 temp2 answer)
Alternatively, we could deal with expressions, using procedures that return
vectors as values, and thus avoid explicitly mentioning temp1 and
temp2 :
(define answer (v-prod (v-sum a b) (v-sum c d)))
Since Lisp allows us to return compound objects as values of procedures, we can
transform our imperative-style constraint language into an expression-oriented
style as shown in this exercise. In languages that are impoverished in
handling compound objects, such as Algol, Basic, and Pascal (unless one
explicitly uses Pascal pointer variables), one is usually stuck with the
imperative style when manipulating compound objects. Given the advantage of
the expression-oriented format, one might ask if there is any reason to have
implemented the system in imperative style, as we did in this section. One
reason is that the non-expression-oriented constraint language provides a
handle on constraint objects (e.g., the value of the adder procedure) as
well as on connector objects. This is useful if we wish to extend the system
with new operations that communicate with constraints directly rather than only
indirectly via operations on connectors. Although it is easy to implement the
expression-oriented style in terms of the imperative implementation, it is very
difficult to do the converse.
Concurrency: Time Is of the Essence
We've seen the power of computational objects with local state as tools for
modeling. Yet, as section 3-1-3 warned, this power extracts a price: the
loss of referential transparency, giving rise to a thicket of questions about
sameness and change, and the need to abandon the substitution model of
evaluation in favor of the more intricate environment model.
The central issue lurking beneath the complexity of state, sameness, and change
is that by introducing assignment we are forced to admit time
into
our computational models. Before we introduced assignment, all our programs
were timeless, in the sense that any expression that has a value always has the
same value. In contrast, recall the example of modeling withdrawals from a
bank account and returning the resulting balance, introduced at the beginning
of section 3-1-1:
(withdraw 25)
75
(withdraw 25)
50
Here successive evaluations of the same expression yield different values.
This behavior arises from the fact that the execution of assignment statements
(in this case, assignments to the variable balance ) delineates
moments in time
when values change. The result of evaluating an
expression depends not only on the expression itself, but also on whether the
evaluation occurs before or after these moments. Building models in terms of
computational objects with local state forces us to confront time as an
essential concept in programming.
We can go further in structuring computational models to match our perception
of the physical world. Objects in the world do not change one at a time in
sequence. Rather we perceive them as acting concurrently
---all at
once. So it is often natural to model systems as collections of computational
processes that execute concurrently. Just as we can make our programs modular
by organizing models in terms of objects with separate local state, it is often
appropriate to divide computational models into parts that evolve separately
and concurrently. Even if the programs are to be executed on a sequential
computer, the practice of writing programs as if they were to be executed
concurrently forces the programmer to avoid inessential timing constraints and
thus makes programs more modular.
In addition to making programs more modular, concurrent computation can provide
a speed advantage over sequential computation. Sequential computers execute
only one operation at a time, so the amount of time it takes to perform a task
is proportional to the total number of operations performed.
Most real
processors actually execute a few operations at a time, following a strategy
called pipelining
. Although this technique greatly improves the
effective utilization of the hardware, it is used only to speed up the
execution of a sequential instruction stream, while retaining the behavior of
the sequential program.
However, if it is possible to decompose a problem
into pieces that are relatively independent and need to communicate only
rarely, it may be possible to allocate pieces to separate computing processors,
producing a speed advantage proportional to the number of processors available.
Unfortunately, the complexities introduced by assignment become even more
problematic in the presence of concurrency. The fact of concurrent execution,
either because the world operates in parallel or because our computers do,
entails additional complexity in our understanding of time.
@menu
* 3-4-1:: The Nature of Time in Concurrent Systems
* 3-4-2:: Mechanisms for Controlling Concurrency
@end menu
The Nature of Time in Concurrent Systems
On the surface, time seems straightforward. It is an ordering imposed on
events.
To quote some graffiti seen on a Cambridge building wall:
``Time is a device that was invented to keep everything from happening at
once.''
For any events A and B, either A occurs before B,
A and B are simultaneous, or A occurs after B. For instance,
returning to the bank account example, suppose that Peter withdraws $10 and
Paul withdraws $25 from a joint account that initially contains $100, leaving
$65 in the account. Depending on the order of the two withdrawals, the
sequence of balances in the account is either $100 -> $90 -> $65 or $100 -> $75
-> $65. In a computer implementation of the banking system, this changing
sequence of balances could be modeled by successive assignments to a variable
balance .
In complex situations, however, such a view can be problematic. Suppose that
Peter and Paul, and other people besides, are accessing the same bank account
through a network of banking machines distributed all over the world. The
actual sequence of balances in the account will depend critically on the
detailed timing of the accesses and the details of the communication among the
machines.
This indeterminacy in the order of events can pose serious problems in the
design of concurrent systems. For instance, suppose that the withdrawals made
by Peter and Paul are implemented as two separate processes sharing a common
variable balance , each process specified by the procedure given in
section 3-1-1:
If the two processes operate independently, then Peter might test the
balance and attempt to withdraw a legitimate amount. However, Paul
might withdraw some funds in between the time that Peter checks the
balance and the time Peter completes the withdrawal, thus invalidating
Peter's test.
Things can be worse still. Consider the expression
(set! balance (- balance amount))
executed as part of each withdrawal process. This consists of three steps: (1)
accessing the value of the balance variable; (2) computing the new
balance; (3) setting balance to this new value. If Peter and Paul's
withdrawals execute this statement concurrently, then the two withdrawals might
interleave the order in which they access balance and set it to the new
value.
The timing diagram in Figure 3-29 depicts an order of events where
balance starts at 100, Peter withdraws 10, Paul withdraws 25, and yet
the final value of balance is 75. As shown in the diagram, the reason
for this anomaly is that Paul's assignment of 75 to balance is made
under the assumption that the value of balance to be decremented is 100.
That assumption, however, became invalid when Peter changed balance to
90. This is a catastrophic failure for the banking system, because the total
amount of money in the system is not conserved. Before the transactions, the
total amount of money was $100. Afterwards, Peter has $10, Paul has $25, and
the bank has $75.
An even worse failure for this system could occur if
the two set! operations attempt to change the balance simultaneously, in
which case the actual data appearing in memory might end up being a random
combination of the information being written by the two processes. Most
computers have interlocks on the primitive memory-write operations, which
protect against such simultaneous access. Even this seemingly simple kind of
protection, however, raises implementation challenges in the design of
multiprocessing computers, where elaborate cache-coherence
protocols
are required to ensure that the various processors will maintain a consistent
view of memory contents, despite the fact that data may be replicated
(``cached'') among the different processors to increase the speed of memory
access.
The general phenomenon illustrated here is that several processes may share a
common state variable. What makes this complicated is that more than one
process may be trying to manipulate the shared state at the same time. For the
bank account example, during each transaction, each customer should be able to
act as if the other customers did not exist. When a customer changes the
balance in a way that depends on the balance, he must be able to assume that,
just before the moment of change, the balance is still what he thought it was.
Correct behavior of concurrent programs
The above example typifies the subtle bugs that can creep into concurrent
programs. The root of this complexity lies in the assignments to variables
that are shared among the different processes. We already know that we must be
careful in writing programs that use set! , because the results of a
computation depend on the order in which the assignments occur.
The
factorial program in section 3-1-3 illustrates this for a single
sequential process.
With concurrent processes we must be especially careful
about assignments, because we may not be able to control the order of the
assignments made by the different processes. If several such changes might be
made concurrently (as with two depositors accessing a joint account) we need
some way to ensure that our system behaves correctly. For example, in the case
of withdrawals from a joint bank account, we must ensure that money is
conserved. To make concurrent programs behave correctly, we may have to place
some restrictions on concurrent execution.
Figure 3.29: Timing diagram showing how
interleaving the order of events in two banking withdrawals can lead to an
incorrect final balance.
| Peter Bank Paul
| ____
| / \
| .--------------| $100 |-------------.
| | \____/ |
| V V
| .----------------------. .----------------------.
| | Access balance: $100 | | Access balance: $100 |
| `----------+-----------' `----------+-----------'
| V V
| .----------------------. .----------------------.
| | new value: 100-10=90 | | new value: 100-25=75 |
| `----------+-----------' `----------+-----------'
| V |
| .----------------------. |
| | set! balance to $90 | |
| `----------+-----------' ____ |
| | / \ |
| `------------->| $ 90 | V
| \____/ .----------------------.
| | new value: 100-25=75 |
| ____ `----------+-----------'
| / \ |
| | $ 90 |<------------'
V \____/
time
One possible restriction on concurrency would stipulate that no two operations
that change any shared state variables can occur at the same time. This is an
extremely stringent requirement. For distributed banking, it would require the
system designer to ensure that only one transaction could proceed at a time.
This would be both inefficient and overly conservative. Figure 3-30
shows Peter and Paul sharing a bank account, where Paul has a private account
as well. The diagram illustrates two withdrawals from the shared account (one
by Peter and one by Paul) and a deposit to Paul's private account.
The
columns show the contents of Peter's wallet, the joint account (in Bank1),
Paul's wallet, and Paul's private account (in Bank2), before and after each
withdrawal (W) and deposit (D). Peter withdraws $10 from Bank1; Paul deposits
$5 in Bank2, then withdraws $25 from Bank1.
The two withdrawals from the
shared account must not be concurrent (since both access and update the same
account), and Paul's deposit and withdrawal must not be concurrent (since both
access and update the amount in Paul's wallet). But there should be no problem
permitting Paul's deposit to his private account to proceed concurrently with
Peter's withdrawal from the shared account.
Figure 3.30: Concurrent deposits and withdrawals
from a joint account in Bank1 and a private account in Bank2.
A less stringent restriction on concurrency would ensure that a concurrent
system produces the same result as if the processes had run sequentially in
some order. There are two important aspects to this requirement. First, it
does not require the processes to actually run sequentially, but only to
produce results that are the same as if they had run sequentially. For
the example in Figure 3-30, the designer of the bank account system can
safely allow Paul's deposit and Peter's withdrawal to happen concurrently,
because the net result will be the same as if the two operations had happened
sequentially. Second, there may be more than one possible ``correct'' result
produced by a concurrent program, because we require only that the result be
the same as for some sequential order. For example, suppose that Peter
and Paul's joint account starts out with $100, and Peter deposits $40 while
Paul concurrently withdraws half the money in the account. Then sequential
execution could result in the account balance being either $70 or $90 (see
Exercise 3-38).
[Footnote 39] A more formal
way to express this idea is to say that concurrent programs are inherently
nondeterministic
. That is, they are described not by single-valued
functions, but by functions whose results are sets of possible values. In
section 4-3 we will study a language for expressing nondeterministic
computations.
There are still weaker requirements for correct execution of concurrent
programs. A program for simulating diffusion (say, the flow of heat in an
object) might consist of a large number of processes, each one representing a
small volume of space, that update their values concurrently. Each process
repeatedly changes its value to the average of its own value and its neighbors'
values. This algorithm converges to the right answer independent of the order
in which the operations are done; there is no need for any restrictions on
concurrent use of the shared values.
Exercise 3.38: Suppose that Peter, Paul, and
Mary share a joint bank account that initially contains $100. Concurrently,
Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in
the account, by executing the following commands:
List all the different possible values for balance after these three
transactions have been completed, assuming that the banking system forces the
three processes to run sequentially in some order.
What are some other values that could be produced if the system allows the
processes to be interleaved? Draw timing diagrams like the one in Figure
3-29 to explain how these values can occur.
Mechanisms for Controlling Concurrency
We've seen that the difficulty in dealing with concurrent processes is rooted
in the need to consider the interleaving of the order of events in the
different processes. For example, suppose we have two processes, one with
three ordered events (a,b,c) and one with three ordered events
(x,y,z). If the two processes run concurrently, with no
constraints on how their execution is interleaved, then there are 20 different
possible orderings for the events that are consistent with the individual
orderings for the two processes:
As programmers designing this system, we would have to consider the effects of
each of these 20 orderings and check that each behavior is acceptable. Such an
approach rapidly becomes unwieldy as the numbers of processes and events
increase.
A more practical approach to the design of concurrent systems is to devise
general mechanisms that allow us to constrain the interleaving of concurrent
processes so that we can be sure that the program behavior is correct. Many
mechanisms have been developed for this purpose. In this section, we describe
one of them, the serializer
.
Serializing access to shared state
Serialization implements the following idea: Processes will execute
concurrently, but there will be certain collections of procedures that cannot
be executed concurrently. More precisely, serialization creates distinguished
sets of procedures such that only one execution of a procedure in each
serialized set is permitted to happen at a time. If some procedure in the set
is being executed, then a process that attempts to execute any procedure in the
set will be forced to wait until the first execution has finished.
We can use serialization to control access to shared variables. For example,
if we want to update a shared variable based on the previous value of that
variable, we put the access to the previous value of the variable and the
assignment of the new value to the variable in the same procedure. We then
ensure that no other procedure that assigns to the variable can run
concurrently with this procedure by serializing all of these procedures with
the same serializer. This guarantees that the value of the variable cannot be
changed between an access and the corresponding assignment.
Serializers in Scheme
To make the above mechanism more concrete, suppose that we have extended Scheme
to include a procedure called parallel-execute :
(parallel-execute ... )
Each
must be a procedure of no arguments. Parallel-execute
creates a separate process for each
, which applies
(to no
arguments). These processes all run
concurrently.
Parallel-execute is not part of standard Scheme,
but it can be implemented in @acronym{MIT
Scheme. In our implementation, the
new concurrent processes also run concurrently with the original Scheme
process. Also, in our implementation, the value returned by
parallel-execute is a special control object that can be used to halt
the newly created processes.}
As an example of how this is used, consider
(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
(lambda () (set! x (+ x 1))))
This creates two concurrent processes---P_1, which sets x to
x times x , and P_2, which increments x . After
execution is complete, x will be left with one of five possible values,
depending on the interleaving of the events of P_1 and P_2:
101: P_1 sets x to 100 and then P_2 increments
x to 101.
121: P_2 increments x to 11 and then P_1 sets
x to x times x .
110: P_2 changes x from 10 to 11 between the two
times that P_1 accesses the value of x during
the evaluation of (* x x) .
11: P_2 accesses x , then P_1 sets x to
100, then P_2 sets x .
100: P_1 accesses x (twice), then P_2 sets
x to 11, then P_1 sets x .
We can constrain the concurrency by using serialized procedures, which are
created by serializers
. Serializers are constructed by
make-serializer , whose implementation is given below. A serializer
takes a procedure as argument and returns a serialized procedure that behaves
like the original procedure. All calls to a given serializer return serialized
procedures in the same set.
Thus, in contrast to the example above, executing
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
(s (lambda () (set! x (+ x 1)))))
can produce only two possible values for x , 101 or 121. The other
possibilities are eliminated, because the execution of P_1 and P_2
cannot be interleaved.
Here is a version of the make-account procedure from section
3-1-1, where the deposits and withdrawals have been serialized:
With this implementation, two processes cannot be withdrawing from or
depositing into a single account concurrently. This eliminates the source of
the error illustrated in Figure 3-29, where Peter changes the account
balance between the times when Paul accesses the balance to compute the new
value and when Paul actually performs the assignment. On the other hand, each
account has its own serializer, so that deposits and withdrawals for different
accounts can proceed concurrently.
Exercise 3.39: Which of the five possibilities
in the parallel execution shown above remain if we instead serialize execution
as follows:
(define x 10)
(define s (make-serializer))
(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))
(s (lambda () (set! x (+ x 1)))))
Exercise 3.40: Give all possible values of
x that can result from executing
(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
(lambda () (set! x (* x x x))))
Which of these possibilities remain if we instead use serialized procedures:
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
(s (lambda () (set! x (* x x x)))))
Exercise 3.41: Ben Bitdiddle worries that it
would be better to implement the bank account as follows (where the commented
line has been changed):
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
;; continued on next page
(let ((protected (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (protected withdraw))
((eq? m 'deposit) (protected deposit))
((eq? m 'balance)