Structure and Interpretation of Computer Programs (57 page)
Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
(define (adder a1 a2 sum)
(define (process-new-value)
(cond ((and (has-value? a1) (has-value? a2))
(set-value! sum
(+ (get-value a1) (get-value a2))
me))
((and (has-value? a1) (has-value? sum))
(set-value! a2
(- (get-value sum) (get-value a1))
me))
((and (has-value? a2) (has-value? sum))
(set-value! a1
(- (get-value sum) (get-value a2))
me))))
(define (process-forget-value)
(forget-value! sum me)
(forget-value! a1 me)
(forget-value! a2 me)
(process-new-value))
(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- ADDER" request))))
(connect a1 me)
(connect a2 me)
(connect sum me)
me)
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
27
in
section
3.3.4
) are used in conjunction with the
dispatch:
(define (inform-about-value constraint)
(constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
(constraint 'I-lost-my-value))
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.
(define (multiplier m1 m2 product)
(define (process-new-value)
(cond ((or (and (has-value? m1) (= (get-value m1) 0))
(and (has-value? m2) (= (get-value m2) 0)))
(set-value! product 0 me))
((and (has-value? m1) (has-value? m2))
(set-value! product
(* (get-value m1) (get-value m2))
me))
((and (has-value? product) (has-value? m1))
(set-value! m2
(/ (get-value product) (get-value m1))
me))
((and (has-value? product) (has-value? m2))
(set-value! m1
(/ (get-value product) (get-value m2))
me))))
(define (process-forget-value)
(forget-value! product me)
(forget-value! m1 me)
(forget-value! m2 me)
(process-new-value))
(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- MULTIPLIER" request))))
(connect m1 me)
(connect m2 me)
(connect product me)
me)
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.
(define (constant value connector)
(define (me request)
(error "Unknown request -- CONSTANT" request))
(connect connector me)
(set-value! connector value me)
me)
Finally, a probe prints a message about the setting or unsetting of
the designated connector:
(define (probe name connector)
(define (print-probe value)
(newline)
(display "Probe: ")
(display name)
(display " = ")
(display value))
(define (process-new-value)
(print-probe (get-value connector)))
(define (process-forget-value)
(print-probe "?"))
(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- PROBE" request))))
(connect connector me)
me)
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.
(define (make-connector)
(let ((value false) (informant false) (constraints '()))
(define (set-my-value newval setter)
(cond ((not (has-value? me))
(set! value newval)
(set! informant setter)
(for-each-except setter
inform-about-value
constraints))
((not (= value newval))
(error "Contradiction" (list value newval)))
(else 'ignored)))
(define (forget-my-value retractor)
(if (eq? retractor informant)
(begin (set! informant false)
(for-each-except retractor
inform-about-no-value
constraints))
'ignored))
(define (connect new-constraint)
(if (not (memq new-constraint constraints))
(set! constraints
(cons new-constraint constraints)))
(if (has-value? me)
(inform-about-value new-constraint))
'done)
(define (me request)
(cond ((eq? request 'has-value?)
(if informant true false))
((eq? request 'value) value)
((eq? request 'set-value!) set-my-value)
((eq? request 'forget) forget-my-value)
((eq? request 'connect) connect)
(else (error "Unknown operation -- CONNECTOR"
request))))
me))
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.
32
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:
(define (for-each-except exception procedure list)
(define (loop items)
(cond ((null? items) 'done)
((eq? (car items) exception) (loop (cdr items)))
(else (procedure (car items))
(loop (cdr items)))))
(loop list))
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:
(define (has-value? connector)
(connector 'has-value?))
(define (get-value connector)
(connector 'value))
(define (set-value! connector new-value informant)
((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
((connector 'forget) retractor))
(define (connect connector new-constraint)
((connector 'connect) new-constraint))
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))
<
alternative1
>)
<
alternative2
>))
(define (process-forget-value) <
body1
>)
(define (me request) <
body2
>)
<
rest of definition
>
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:
(for-each-except setter inform-about-value constraints)
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.
33
16
Set-car!
and
set-cdr!
return implementation-dependent
values. Like
set!
, they should be used only for their effect.
17
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.
18
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
.
19
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.
20
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.
21
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.
22
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.
23
Be careful not to
make the interpreter try to print a structure that contains cycles.
(See exercise
3.13
.)
24
Because
assoc
uses
equal?
, it can recognize keys that are symbols, numbers,
or list structure.
25
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.
26
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
i
n
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
o
u
t
, which is the
carry bit to be propagated to the left.
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.
28
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).
29
Observe that the
if
expression in
this procedure has no
<
alternative
> 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
<
alternative
>.
30
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.
31
Constraint propagation
first appeared in the incredibly forward-looking
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.
32
The
setter
might not be a constraint. In our
temperature example, we used
user
as the
setter
.
33
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.