We saw earlier in this section how to evaluate simple queries in the absence of
rules. Now that we have seen how to apply rules, we can describe how to
evaluate simple queries by using both rules and assertions.
Given the query pattern and a stream of frames, we produce, for each frame in
the input stream, two streams:
a stream of extended frames obtained by matching the pattern against all
assertions in the data base (using the pattern matcher), and
a stream of extended frames obtained by applying all possible rules (using the
unifier).
Since unification is a generalization of matching, we could
simplify the system by using the unifier to produce both streams. Treating the
easy case with the simple matcher, however, illustrates how matching (as
opposed to full-blown unification) can be useful in its own right.
Appending these two streams produces a stream that consists of all the ways
that the given pattern can be satisfied consistent with the original frame.
These streams (one for each frame in the input stream) are now all combined to
form one large stream, which therefore consists of all the ways that any of the
frames in the original input stream can be extended to produce a match with the
given pattern.
The query evaluator and the driver loop
Despite the complexity of the underlying matching operations, the system is
organized much like an evaluator for any language. The procedure that
coordinates the matching operations is called qeval , and it plays a role
analogous to that of the eval procedure for Lisp. Qeval takes as
inputs a query and a stream of frames. Its output is a stream of frames,
corresponding to successful matches to the query pattern, that extend some
frame in the input stream, as indicated in Figure 4-4. Like eval ,
qeval classifies the different types of expressions (queries) and
dispatches to an appropriate procedure for each. There is a procedure for each
special form ( and , or , not , and lisp-value ) and one
for simple queries.
The driver loop, which is analogous to the driver-loop procedure for the
other evaluators in this chapter, reads queries from the terminal. For each
query, it calls qeval with the query and a stream that consists of a
single empty frame. This will produce the stream of all possible matches (all
possible extensions to the empty frame). For each frame in the resulting
stream, it instantiates the original query using the values of the variables
found in the frame. This stream of instantiated queries is then
printed.
The reason we use streams (rather than lists) of frames is
that the recursive application of rules can generate infinite numbers of values
that satisfy a query. The delayed evaluation embodied in streams is crucial
here: The system will print responses one by one as they are generated,
regardless of whether there are a finite or infinite number of responses.
The driver also checks for the special command assert! , which signals
that the input is not a query but rather an assertion or rule to be added to
the data base. For instance,
The means of combination used in the query language may at first seem identical
to the operations and , or , and not of mathematical logic,
and the application of query-language rules is in fact accomplished through a
legitimate method of inference.
That a particular method of inference
is legitimate is not a trivial assertion. One must prove that if one starts
with true premises, only true conclusions can be derived. The method of
inference represented by rule applications is modus ponens
, the
familiar method of inference that says that if A is true and A
implies B is true, then we may conclude that B is true.
This
identification of the query language with mathematical logic is not really
valid, though, because the query language provides a control
structure
that interprets the logical statements procedurally. We can often
take advantage of this control structure. For example, to find all of the
supervisors of programmers we could formulate a query in either of two
logically equivalent forms:
If a company has many more supervisors than programmers (the usual case), it is
better to use the first form rather than the second because the data base must
be scanned for each intermediate result (frame) produced by the first clause of
the and .
The aim of logic programming is to provide the programmer with techniques for
decomposing a computational problem into two separate problems: ``what'' is to
be computed, and ``how'' this should be computed. This is accomplished by
selecting a subset of the statements of mathematical logic that is powerful
enough to be able to describe anything one might want to compute, yet weak
enough to have a controllable procedural interpretation. The intention here is
that, on the one hand, a program specified in a logic programming language
should be an effective program that can be carried out by a computer. Control
(``how'' to compute) is effected by using the order of evaluation of the
language. We should be able to arrange the order of clauses and the order of
subgoals within each clause so that the computation is done in an order deemed
to be effective and efficient. At the same time, we should be able to view the
result of the computation (``what'' to compute) as a simple consequence of the
laws of logic.
Our query language can be regarded as just such a procedurally interpretable
subset of mathematical logic. An assertion represents a simple fact (an atomic
proposition). A rule represents the implication that the rule conclusion holds
for those cases where the rule body holds. A rule has a natural procedural
interpretation: To establish the conclusion of the rule, establish the body of
the rule. Rules, therefore, specify computations. However, because rules can
also be regarded as statements of mathematical logic, we can justify any
``inference'' accomplished by a logic program by asserting that the same result
could be obtained by working entirely within mathematical logic.
We
must qualify this statement by agreeing that, in speaking of the ``inference''
accomplished by a logic program, we assume that the computation terminates.
Unfortunately, even this qualified statement is false for our implementation of
the query language (and also false for programs in Prolog and most other
current logic programming languages) because of our use of not and
lisp-value . As we will describe below, the not implemented in
the query language is not always consistent with the not of mathematical
logic, and lisp-value introduces additional complications. We could
implement a language consistent with mathematical logic by simply removing
not and lisp-value from the language and agreeing to write
programs using only simple queries, and , and or . However, this
would greatly restrict the expressive power of the language. One of the major
concerns of research in logic programming is to find ways to achieve more
consistency with mathematical logic without unduly sacrificing expressive
power.
Infinite loops
A consequence of the procedural interpretation of logic programs is that it is
possible to construct hopelessly inefficient programs for solving certain
problems. An extreme case of inefficiency occurs when the system falls into
infinite loops in making deductions. As a simple example, suppose we are
setting up a data base of famous marriages, including
(assert! (married Minnie Mickey))
If we now ask
(married Mickey ?who)
we will get no response, because the system doesn't know that if A is
married to B, then B is married to A. So we assert the rule
(assert! (rule (married ?x ?y)
(married ?y ?x)))
and again query
(married Mickey ?who)
Unfortunately, this will drive the system into an infinite loop, as follows:
The system finds that the married rule is applicable; that is, the rule
conclusion (married ?x ?y) successfully unifies with the query pattern
(married Mickey ?who) to produce a frame in which ?x is bound to
Mickey and ?y is bound to ?who . So the interpreter
proceeds to evaluate the rule body (married ?y ?x) in this frame---in
effect, to process the query (married ?who Mickey) .
One answer appears directly as an assertion in the data base: (married
Minnie Mickey) .
The married rule is also applicable, so the interpreter again evaluates
the rule body, which this time is equivalent to (married Mickey ?who) .
The system is now in an infinite loop. Indeed, whether the system will find
the simple answer (married Minnie Mickey) before it goes into the loop
depends on implementation details concerning the order in which the system
checks the items in the data base. This is a very simple example of the kinds
of loops that can occur. Collections of interrelated rules can lead to loops
that are much harder to anticipate, and the appearance of a loop can depend on
the order of clauses in an and (see Exercise 4-64) or on low-level
details concerning the order in which the system processes
queries.
This is not a problem of the logic but one of the procedural
interpretation of the logic provided by our interpreter. We could write an
interpreter that would not fall into a loop here. For example, we could
enumerate all the proofs derivable from our assertions and our rules in a
breadth-first rather than a depth-first order. However, such a system makes it
more difficult to take advantage of the order of deductions in our programs.
One attempt to build sophisticated control into such a program is described in
deKleer et al. 1977. Another technique, which does not lead to such serious
control problems, is to put in special knowledge, such as detectors for
particular kinds of loops (Exercise 4-67). However, there can be no
general scheme for reliably preventing a system from going down infinite paths
in performing deductions. Imagine a diabolical rule of the form ``To show
P(x) is true, show that P(f(x)) is true,'' for some
suitably chosen function f.
Problems with not
Another quirk in the query system concerns not . Given the data base of
section 4-4-1, consider the following two queries:
These two queries do not produce the same result. The first query begins by
finding all entries in the data base that match (supervisor ?x ?y) , and
then filters the resulting frames by removing the ones in which the value of
?x satisfies (job ?x (computer programmer)) . The second query
begins by filtering the incoming frames to remove those that can satisfy
(job ?x (computer programmer)) . Since the only incoming frame is empty,
it checks the data base to see if there are any patterns that satisfy
(job ?x (computer programmer)) . Since there generally are entries of
this form, the not clause filters out the empty frame and returns an
empty stream of frames. Consequently, the entire compound query returns an
empty stream.
The trouble is that our implementation of not really is meant to serve
as a filter on values for the variables. If a not clause is processed
with a frame in which some of the variables remain unbound (as does ?x
in the example above), the system will produce unexpected results. Similar
problems occur with the use of lisp-value ---the Lisp predicate can't
work if some of its arguments are unbound. See Exercise 4-77.
There is also a much more serious way in which the not of the query
language differs from the not of mathematical logic. In logic, we
interpret the statement ``not P'' to mean that P is not true. In the
query system, however, ``not P'' means that P is not deducible from the
knowledge in the data base. For example, given the personnel data base of
section 4-4-1, the system would happily deduce all sorts of not
statements, such as that Ben Bitdiddle is not a baseball fan, that it is not
raining outside, and that 2 + 2 is not 4.
Consider the query
(not (baseball-fan (Bitdiddle Ben))) . The system finds that
(baseball-fan (Bitdiddle Ben)) is not in the data base, so the empty
frame does not satisfy the pattern and is not filtered out of the initial
stream of frames. The result of the query is thus the empty frame, which is
used to instantiate the input query to produce (not (baseball-fan
(Bitdiddle Ben))) .
In other words, the not of logic programming
languages reflects the so-called closed world assumption
that all
relevant information has been included in the data base.
A discussion
and justification of this treatment of not can be found in the article
by Clark (1978).
Exercise 4.64: Louis Reasoner mistakenly deletes
the outranked-by rule (section 4-4-1) from the data base. When he
realizes this, he quickly reinstalls it. Unfortunately, he makes a slight
change in the rule, and types it in as
Just after Louis types this information into the system, DeWitt Aull comes by
to find out who outranks Ben Bitdiddle. He issues the query
(outranked-by (Bitdiddle Ben) ?who)
After answering, the system goes into an infinite loop. Explain why.
Exercise 4.65: Cy D. Fect, looking forward to
the day when he will rise in the organization, gives a query to find all the
wheels (using the wheel rule of section 4-4-1):
Exercise 4.66: Ben has been generalizing the
query system to provide statistics about the company. For example, to find the
total salaries of all the computer programmers one will be able to say
In general, Ben's new system allows expressions of the form
(accumulation-function )
where accumulation-function can be things like sum ,
average , or maximum . Ben reasons that it should be a cinch to
implement this. He will simply feed the query pattern to qeval . This
will produce a stream of frames. He will then pass this stream through a
mapping function that extracts the value of the designated variable from each
frame in the stream and feed the resulting stream of values to the accumulation
function. Just as Ben completes the implementation and is about to try it out,
Cy walks by, still puzzling over the wheel query result in exercise
Exercise 4-65. When Cy shows Ben the system's response, Ben groans,
``Oh, no, my simple accumulation scheme won't work!''
What has Ben just realized? Outline a method he can use to salvage the
situation.
Exercise 4.67: Devise a way to install a loop
detector in the query system so as to avoid the kinds of simple loops
illustrated in the text and in Exercise 4-64. The general idea is that
the system should maintain some sort of history of its current chain of
deductions and should not begin processing a query that it is already working
on. Describe what kind of information (patterns and frames) is included in
this history, and how the check should be made. (After you study the details
of the query-system implementation in section 4-4-4, you may want to
modify the system to include your loop detector.)
Exercise 4.68: Define rules to implement the
reverse operation of Exercise 2-18, which returns a list
containing the same elements as a given list in reverse order. (Hint: Use
append-to-form .) Can your rules answer both (reverse (1 2 3) ?x)
and (reverse ?x (1 2 3)) ?
Exercise 4.69: Beginning with the data base and
the rules you formulated in Exercise 4-63, devise a rule for adding
``greats'' to a grandson relationship. This should enable the system to deduce
that Irad is the great-grandson of Adam, or that Jabal and Jubal are the
great-great-great-great-great-grandsons of Adam. (Hint: Represent the fact
about Irad, for example, as ((great grandson) Adam Irad) . Write rules
that determine if a list ends in the word grandson . Use this to express
a rule that allows one to derive the relationship ((great . ?rel) ?x
?y) , where ?rel is a list ending in grandson .) Check your rules
on queries such as ((great grandson) ?g ?ggs) and (?relationship
Adam Irad) .
Implementing the Query System
Section 4-4-2 described how the query system works. Now we fill in the
details by presenting a complete implementation of the system.
@menu
* 4-4-4-1:: The Driver Loop and Instantiation
* 4-4-4-2:: The Evaluator
* 4-4-4-3:: Finding Assertions by Pattern Matching
* 4-4-4-4:: Rules and Unification
* 4-4-4-5:: Maintaining the Data Base
* 4-4-4-6:: Stream Operations
* 4-4-4-7:: Query Syntax Procedures
* 4-4-4-8:: Frames and Bindings
@end menu
@subsubsection The Driver Loop and Instantiation
The driver loop for the query system repeatedly reads input expressions. If
the expression is a rule or assertion to be added to the data base, then the
information is added. Otherwise the expression is assumed to be a query. The
driver passes this query to the evaluator qeval together with an initial
frame stream consisting of a single empty frame. The result of the evaluation
is a stream of frames generated by satisfying the query with variable values
found in the data base. These frames are used to form a new stream consisting
of copies of the original query in which the variables are instantiated with
values supplied by the stream of frames, and this final stream is printed at
the terminal:
Here, as in the other evaluators in this chapter, we use an abstract syntax for
the expressions of the query language. The implementation of the expression
syntax, including the predicate assertion-to-be-added? and the selector
add-assertion-body , is given in section 4-4-4-7.
Add-rule-or-assertion! is defined in section 4-4-4-5.
Before doing any processing on an input expression, the driver loop transforms
it syntactically into a form that makes the processing more efficient. This
involves changing the representation of pattern variables. When the query is
instantiated, any variables that remain unbound are transformed back to the
input representation before being printed. These transformations are performed
by the two procedures query-syntax-process and
contract-question-mark (section 4-4-4-7).
To instantiate an expression, we copy it, replacing any variables in the
expression by their values in a given frame. The values are themselves
instantiated, since they could contain variables (for example, if ?x in
exp is bound to ?y as the result of unification and ?y is
in turn bound to 5). The action to take if a variable cannot be instantiated
is given by a procedural argument to instantiate .
The procedures that manipulate bindings are defined in section 4-4-4-8.
@subsubsection The Evaluator
The qeval procedure, called by the query-driver-loop , is the
basic evaluator of the query system. It takes as inputs a query and a stream
of frames, and it returns a stream of extended frames. It identifies special
forms by a data-directed dispatch using get and put , just as we
did in implementing generic operations in Chapter 2. Any query that is
not identified as a special form is assumed to be a simple query, to be
processed by simple-query .
Type and contents , defined in section 4-4-4-7, implement
the abstract syntax of the special forms.
Simple queries
The simple-query procedure handles simple queries. It takes as
arguments a simple query (a pattern) together with a stream of frames, and it
returns the stream formed by extending each frame by all data-base matches of
the query.
For each frame in the input stream, we use find-assertions (section
4-4-4-3) to match the pattern against all assertions in the data base,
producing a stream of extended frames, and we use apply-rules (section
4-4-4-4) to apply all possible rules, producing another stream of
extended frames. These two streams are combined (using
stream-append-delayed , section 4-4-4-6) to make a stream of all
the ways that the given pattern can be satisfied consistent with the original
frame (see Exercise 4-71). The streams for the individual input frames
are combined using stream-flatmap (section 4-4-4-6) to form one
large stream of all the ways that any of the frames in the original input
stream can be extended to produce a match with the given pattern.
Compound queries
And queries are handled as illustrated in Figure 4-5 by the
conjoin procedure. Conjoin takes as inputs the conjuncts and the
frame stream and returns the stream of extended frames. First, conjoin
processes the stream of frames to find the stream of all possible frame
extensions that satisfy the first query in the conjunction. Then, using this
as the new frame stream, it recursively applies conjoin to the rest of
the queries.
sets up qeval to dispatch to conjoin when an and form is
encountered.
Or queries are handled similarly, as shown in Figure 4-6. The
output streams for the various disjuncts of the or are computed
separately and merged using the interleave-delayed procedure from
section 4-4-4-6. (See Exercise 4-71 and Exercise 4-72.)
The predicates and selectors for the syntax of conjuncts and disjuncts are
given in section 4-4-4-7.
Filters
Not is handled by the method outlined in section 4-4-2. We
attempt to extend each frame in the input stream to satisfy the query being
negated, and we include a given frame in the output stream only if it cannot be
extended.
Lisp-value is a filter similar to not . Each frame in the stream
is used to instantiate the variables in the pattern, the indicated predicate is
applied, and the frames for which the predicate returns false are filtered out
of the input stream. An error results if there are unbound pattern variables.
(define (lisp-value call frame-stream)
(stream-flatmap
(lambda (frame)
(if (execute
(instantiate
call
frame
(lambda (v f)
(error "Unknown pat var -- LISP-VALUE" v))))
(singleton-stream frame)
the-empty-stream))
frame-stream))
(put 'lisp-value 'qeval lisp-value)
Execute , which applies the predicate to the arguments, must eval
the predicate expression to get the procedure to apply. However, it must not
evaluate the arguments, since they are already the actual arguments, not
expressions whose evaluation (in Lisp) will produce the arguments. Note that
execute is implemented using eval and apply from the
underlying Lisp system.
The always-true special form provides for a query that is always
satisfied. It ignores its contents (normally empty) and simply passes through
all the frames in the input stream. Always-true is used by the
rule-body selector (section 4-4-4-7) to provide bodies for rules
that were defined without bodies (that is, rules whose conclusions are always
satisfied).
The selectors that define the syntax of not and lisp-value are
given in section 4-4-4-7.
@subsubsection Finding Assertions by Pattern Matching
Find-assertions , called by simple-query (section 4-4-4-2),
takes as input a pattern and a frame. It returns a stream of frames, each
extending the given one by a data-base match of the given pattern. It uses
fetch-assertions (section 4-4-4-5) to get a stream of all the
assertions in the data base that should be checked for a match against the
pattern and the frame. The reason for fetch-assertions here is that we
can often apply simple tests that will eliminate many of the entries in the
data base from the pool of candidates for a successful match. The system would
still work if we eliminated fetch-assertions and simply checked a stream
of all assertions in the data base, but the computation would be less efficient
because we would need to make many more calls to the matcher.
Check-an-assertion takes as arguments a pattern, a data object
(assertion), and a frame and returns either a one-element stream containing the
extended frame or the-empty-stream if the match fails.
The basic pattern matcher returns either the symbol failed or an
extension of the given frame. The basic idea of the matcher is to check the
pattern against the data, element by element, accumulating bindings for the
pattern variables. If the pattern and the data object are the same, the match
succeeds and we return the frame of bindings accumulated so far. Otherwise, if
the pattern is a variable we extend the current frame by binding the variable
to the data, so long as this is consistent with the bindings already in the
frame. If the pattern and the data are both pairs, we (recursively) match the
car of the pattern against the car of the data to produce a
frame; in this frame we then match the cdr of the pattern against the
cdr of the data. If none of these cases are applicable, the match fails
and we return the symbol failed .
(define (pattern-match pat dat frame)
(cond ((eq? frame 'failed) 'failed)
((equal? pat dat) frame)
((var? pat) (extend-if-consistent pat dat frame))
((and (pair? pat) (pair? dat))
(pattern-match (cdr pat)
(cdr dat)
(pattern-match (car pat)
(car dat)
frame)))
(else 'failed)))
Here is the procedure that extends a frame by adding a new binding, if this is
consistent with the bindings already in the frame:
(define (extend-if-consistent var dat frame)
(let ((binding (binding-in-frame var frame)))
(if binding
(pattern-match (binding-value binding) dat frame)
(extend var dat frame))))
If there is no binding for the variable in the frame, we simply add the binding
of the variable to the data. Otherwise we match, in the frame, the data
against the value of the variable in the frame. If the stored value contains
only constants, as it must if it was stored during pattern matching by
extend-if-consistent , then the match simply tests whether the stored and
new values are the same. If so, it returns the unmodified frame; if not, it
returns a failure indication. The stored value may, however, contain pattern
variables if it was stored during unification (see section 4-4-4-4). The
recursive match of the stored pattern against the new data will add or check
bindings for the variables in this pattern. For example, suppose we have a
frame in which ?x is bound to (f ?y) and ?y is unbound,
and we wish to augment this frame by a binding of ?x to (f b) .
We look up ?x and find that it is bound to (f ?y) . This leads us
to match (f ?y) against the proposed new value (f b) in the same
frame. Eventually this match extends the frame by adding a binding of
?y to b . ?X remains bound to (f ?y) . We never
modify a stored binding and we never store more than one binding for a given
variable.
The procedures used by extend-if-consistent to manipulate bindings are
defined in section 4-4-4-8.
Patterns with dotted tails
If a pattern contains a dot followed by a pattern variable, the pattern
variable matches the rest of the data list (rather than the next element of the
data list), just as one would expect with the dotted-tail notation described in
Exercise 2-20. Although the pattern matcher we have just implemented
doesn't look for dots, it does behave as we want. This is because the Lisp
read primitive, which is used by query-driver-loop to read the
query and represent it as a list structure, treats dots in a special way.
When read sees a dot, instead of making the next item be the next
element of a list (the car of a cons whose cdr will be the
rest of the list) it makes the next item be the cdr of the list
structure. For example, the list structure produced by read for the
pattern (computer ?type) could be constructed by evaluating the
expression (cons 'computer (cons '?type '())) , and that for
(computer . ?type) could be constructed by evaluating the expression
(cons 'computer '?type) .
Thus, as pattern-match recursively compares car s and cdr s
of a data list and a pattern that had a dot, it eventually matches the variable
after the dot (which is a cdr of the pattern) against a sublist of the
data list, binding the variable to that list. For example, matching the
pattern (computer . ?type) against (computer programmer trainee)
will match ?type against the list (programmer trainee) .
@subsubsection Rules and Unification
Apply-rules is the rule analog of find-assertions (section
4-4-4-3). It takes as input a pattern and a frame, and it forms a stream
of extension frames by applying rules from the data base.
Stream-flatmap maps apply-a-rule down the stream of possibly
applicable rules (selected by fetch-rules , section 4-4-4-5) and
combines the resulting streams of frames.
Apply-a-rule applies rules using the method outlined in section
4-4-2. It first augments its argument frame by unifying the rule
conclusion with the pattern in the given frame. If this succeeds, it evaluates
the rule body in this new frame.
Before any of this happens, however, the program renames all the variables in
the rule with unique new names. The reason for this is to prevent the
variables for different rule applications from becoming confused with each
other. For instance, if two rules both use a variable named ?x , then
each one may add a binding for ?x to the frame when it is applied.
These two ?x 's have nothing to do with each other, and we should not be
fooled into thinking that the two bindings must be consistent. Rather than
rename variables, we could devise a more clever environment structure; however,
the renaming approach we have chosen here is the most straightforward, even if
not the most efficient. (See Exercise 4-79.) Here is the
apply-a-rule procedure:
The selectors rule-body and conclusion that extract parts of a
rule are defined in section 4-4-4-7.
We generate unique variable names by associating a unique identifier (such as a
number) with each rule application and combining this identifier with the
original variable names. For example, if the rule-application identifier is 7,
we might change each ?x in the rule to ?x-7 and each ?y in
the rule to ?y-7 . ( Make-new-variable and
new-rule-application-id are included with the syntax procedures in
section 4-4-4-7.)
The unification algorithm is implemented as a procedure that takes as inputs
two patterns and a frame and returns either the extended frame or the symbol
failed . The unifier is like the pattern matcher except that it is
symmetrical---variables are allowed on both sides of the match.
Unify-match is basically the same as pattern-match , except that
there is extra code (marked `` *** '' below) to handle the case where the
object on the right side of the match is a variable.
In unification, as in one-sided pattern matching, we want to accept a proposed
extension of the frame only if it is consistent with existing bindings. The
procedure extend-if-possible used in unification is the same as the
extend-if-consistent used in pattern matching except for two special
checks, marked `` *** '' in the program below. In the first case, if the
variable we are trying to match is not bound, but the value we are trying to
match it with is itself a (different) variable, it is necessary to check to see
if the value is bound, and if so, to match its value. If both parties to the
match are unbound, we may bind either to the other.
The second check deals with attempts to bind a variable to a pattern that
includes that variable. Such a situation can occur whenever a variable is
repeated in both patterns. Consider, for example, unifying the two patterns
(?x ?x) and (?y >)} in a
frame where both ?x and ?y are unbound. First ?x is
matched against ?y , making a binding of ?x to ?y . Next,
the same ?x is matched against the given expression involving ?y .
Since ?x is already bound to ?y , this results in matching
?y against the expression. If we think of the unifier as finding a set
of values for the pattern variables that make the patterns the same, then these
patterns imply instructions to find a ?y such that ?y is equal to
the expression involving ?y . There is no general method for solving
such equations, so we reject such bindings; these cases are recognized by the
predicate depends-on? .
In general, unifying ?y with an
expression involving ?y would require our being able to find a fixed
point of the equation ?y = ?y >. It
is sometimes possible to syntactically form an expression that appears to be
the solution. For example, ?y = (f ?y) seems to have the fixed
point (f (f (f ... ))) , which we can produce by beginning with the
expression (f ?y) and repeatedly substituting (f ?y) for
?y . Unfortunately, not every such equation has a meaningful fixed
point. The issues that arise here are similar to the issues of manipulating
infinite series in mathematics. For example, we know that 2 is the solution to
the equation y = 1 + y/2. Beginning with the expression 1 + y/2
and repeatedly substituting 1 + y/2 for y gives
Although the formal manipulations used in deriving these two equations are
identical, the first result is a valid assertion about infinite series but the
second is not. Similarly, for our unification results, reasoning with an
arbitrary syntactically constructed expression may lead to errors.
On the
other hand, we do not want to reject attempts to bind a variable to itself.
For example, consider unifying (?x ?x) and (?y ?y) . The second
attempt to bind ?x to ?y matches ?y (the stored value of
?x ) against ?y (the new value of ?x ). This is taken care
of by the equal? clause of unify-match .
(define (extend-if-possible var val frame)
(let ((binding (binding-in-frame var frame)))
(cond (binding
(unify-match
(binding-value binding) val frame))
((var? val) ; ***
(let ((binding (binding-in-frame val frame)))
(if binding
(unify-match
var (binding-value binding) frame)
(extend var val frame))))
((depends-on? val var frame) ; ***
'failed)
(else (extend var val frame)))))
Depends-on? is a predicate that tests whether an expression proposed to
be the value of a pattern variable depends on the variable. This must be done
relative to the current frame because the expression may contain occurrences of
a variable that already has a value that depends on our test variable. The
structure of depends-on? is a simple recursive tree walk in which we
substitute for the values of variables whenever necessary.
(define (depends-on? exp var frame)
(define (tree-walk e)
(cond ((var? e)
(if (equal? var e)
true
(let ((b (binding-in-frame e frame)))
(if b
(tree-walk (binding-value b))
false))))
((pair? e)
(or (tree-walk (car e))
(tree-walk (cdr e))))
(else false)))
(tree-walk exp))
@subsubsection Maintaining the Data Base
One important problem in designing logic programming languages is that of
arranging things so that as few irrelevant data-base entries as possible will
be examined in checking a given pattern. In our system, in addition to storing
all assertions in one big stream, we store all assertions whose car s are
constant symbols in separate streams, in a table indexed by the symbol. To
fetch an assertion that may match a pattern, we first check to see if the
car of the pattern is a constant symbol. If so, we return (to be tested
using the matcher) all the stored assertions that have the same car . If
the pattern's car is not a constant symbol, we return all the stored
assertions. Cleverer methods could also take advantage of information in the
frame, or try also to optimize the case where the car of the pattern is
not a constant symbol. We avoid building our criteria for indexing (using the
car , handling only the case of constant symbols) into the program;
instead we call on predicates and selectors that embody our criteria.
Get-stream looks up a stream in the table and returns an empty stream if
nothing is stored there.
(define (get-stream key1 key2)
(let ((s (get key1 key2)))
(if s s the-empty-stream)))
Rules are stored similarly, using the car of the rule conclusion. Rule
conclusions are arbitrary patterns, however, so they differ from assertions in
that they can contain variables. A pattern whose car is a constant
symbol can match rules whose conclusions start with a variable as well as rules
whose conclusions have the same car . Thus, when fetching rules that
might match a pattern whose car is a constant symbol we fetch all rules
whose conclusions start with a variable as well as those whose conclusions have
the same car as the pattern. For this purpose we store all rules whose
conclusions start with a variable in a separate stream in our table, indexed by
the symbol ? .
Add-rule-or-assertion! is used by query-driver-loop to add
assertions and rules to the data base. Each item is stored in the index, if
appropriate, and in a stream of all assertions or rules in the data base.
The following procedures define how the data-base index is used. A pattern (an
assertion or a rule conclusion) will be stored in the table if it starts with a
variable or a constant symbol.
Exercise 4.70: What is the purpose of the
let bindings in the procedures add-assertion! and
add-rule! ? What would be wrong with the following implementation of
add-assertion! ? Hint: Recall the definition of the infinite stream of
ones in section 3-5-2: (define ones (cons-stream 1 ones)) .
@subsubsection Stream Operations
The query system uses a few stream operations that were not presented in
Chapter 3.
Stream-append-delayed and interleave-delayed are just like
stream-append and interleave (section 3-5-3), except that
they take a delayed argument (like the integral procedure in section
3-5-4). This postpones looping in some cases (see Exercise 4-71).
Stream-flatmap , which is used throughout the query evaluator to map a
procedure over a stream of frames and combine the resulting streams of frames,
is the stream analog of the flatmap procedure introduced for ordinary
lists in section 2-2-3. Unlike ordinary flatmap , however, we
accumulate the streams with an interleaving process, rather than simply
appending them (see Exercise 4-72 and Exercise 4-73).
The evaluator also uses the following simple procedure to generate a stream
consisting of a single element:
(define (singleton-stream x)
(cons-stream x the-empty-stream))
@subsubsection Query Syntax Procedures
Type and contents , used by qeval (section 4-4-4-2),
specify that a special form is identified by the symbol in its car .
They are the same as the type-tag and contents procedures in
section 2-4-2, except for the error message.
The following procedures, used by query-driver-loop (in section
4-4-4-1), specify that rules and assertions are added to the data base by
expressions of the form (assert! >):
Query-driver-loop (section 4-4-4-1) calls
query-syntax-process to transform pattern variables in the expression,
which have the form ?symbol , into the internal format (? symbol) .
That is to say, a pattern such as (job ?x ?y) is actually represented
internally by the system as (job (? x) (? y)) . This increases the
efficiency of query processing, since it means that the system can check to see
if an expression is a pattern variable by checking whether the car of
the expression is the symbol ? , rather than having to extract characters
from the symbol. The syntax transformation is accomplished by the following
procedure:
Most Lisp systems give the user the ability to modify the
ordinary read procedure to perform such transformations by defining
reader macro characters
. Quoted expressions are already handled in
this way: The reader automatically translates 'expression into
(quote expression) before the evaluator sees it. We could arrange for
?expression to be transformed into (? expression) in the same
way; however, for the sake of clarity we have included the transformation
procedure here explicitly.
Expand-question-mark and contract-question-mark use several
procedures with string in their names. These are Scheme primitives.
Once the variables are transformed in this way, the variables in a pattern are
lists starting with ? , and the constant symbols (which need to be
recognized for data-base indexing, section 4-4-4-5) are just the symbols.
Unique variables are constructed during rule application (in section
4-4-4-4) by means of the following procedures. The unique identifier for
a rule application is a number, which is incremented each time a rule is
applied.
When query-driver-loop instantiates the query to print the answer, it
converts any unbound pattern variables back to the right form for printing,
using
Exercise 4.71: Louis Reasoner wonders why the
simple-query and disjoin procedures (section 4-4-4-2) are
implemented using explicit delay operations, rather than being defined
as follows:
Can you give examples of queries where these simpler definitions would lead to
undesirable behavior?
Exercise 4.72: Why do disjoin and
stream-flatmap interleave the streams rather than simply append them?
Give examples that illustrate why interleaving works better. (Hint: Why did we
use interleave in section 3-5-3?)
Exercise 4.73: Why does flatten-stream
use delay explicitly? What would be wrong with defining it as follows:
Exercise 4.74: Alyssa P. Hacker proposes to use
a simpler version of stream-flatmap in negate , lisp-value ,
and find-assertions . She observes that the procedure that is mapped
over the frame stream in these cases always produces either the empty stream or
a singleton stream, so no interleaving is needed when combining these streams.
Fill in the missing expressions in Alyssa's program.
Does the query system's behavior change if we change it in this way?
Exercise 4.75: Implement for the query language
a new special form called unique . Unique should succeed if there
is precisely one item in the data base satisfying a specified query. For
example,
(unique (job ?x (computer wizard)))
should print the one-item stream
(unique (job (Bitdiddle Ben) (computer wizard)))
since Ben is the only computer wizard, and
(unique (job ?x (computer programmer)))
should print the empty stream, since there is more than one computer
programmer. Moreover,
(and (job ?x ?j) (unique (job ?anyone ?j)))
should list all the jobs that are filled by only one person, and the people who
fill them.
There are two parts to implementing unique . The first is to write a
procedure that handles this special form, and the second is to make
qeval dispatch to that procedure. The second part is trivial, since
qeval does its dispatching in a data-directed way. If your procedure is
called uniquely-asserted , all you need to do is
(put 'unique 'qeval uniquely-asserted)
and qeval will dispatch to this procedure for every query whose
type ( car ) is the symbol unique .
The real problem is to write the procedure uniquely-asserted . This
should take as input the contents ( cdr ) of the unique
query, together with a stream of frames. For each frame in the stream, it
should use qeval to find the stream of all extensions to the frame that
satisfy the given query. Any stream that does not have exactly one item in it
should be eliminated. The remaining streams should be passed back to be
accumulated into one big stream that is the result of the unique query.
This is similar to the implementation of the not special form.
Test your implementation by forming a query that lists all people who supervise
precisely one person.
Exercise 4.76: Our implementation of and
as a series combination of queries (Figure 4-5) is elegant, but it is
inefficient because in processing the second query of the and we must
scan the data base for each frame produced by the first query. If the data
base has n elements, and a typical query produces a number of output frames
proportional to n (say n/k), then scanning the data base for each
frame produced by the first query will require n^2/k calls to the
pattern matcher. Another approach would be to process the two clauses of the
and separately, then look for all pairs of output frames that are
compatible. If each query produces n/k output frames, then this means
that we must perform n^2/k^2 compatibility checks---a factor of k
fewer than the number of matches required in our current method.
Devise an implementation of and that uses this strategy. You must
implement a procedure that takes two frames as inputs, checks whether the
bindings in the frames are compatible, and, if so, produces a frame that merges
the two sets of bindings. This operation is similar to unification.
Exercise 4.77: In section 4-4-3 we saw
that not and lisp-value can cause the query language to give
``wrong'' answers if these filtering operations are applied to frames in which
variables are unbound. Devise a way to fix this shortcoming. One idea is to
perform the filtering in a ``delayed'' manner by appending to the frame a
``promise'' to filter that is fulfilled only when enough variables have been
bound to make the operation possible. We could wait to perform filtering until
all other operations have been performed. However, for efficiency's sake, we
would like to perform filtering as soon as possible so as to cut down on the
number of intermediate frames generated.
Exercise 4.78: Redesign the query language as a
nondeterministic program to be implemented using the evaluator of section
4-3, rather than as a stream process. In this approach, each query will
produce a single answer (rather than the stream of all answers) and the user
can type try-again to see more answers. You should find that much of
the mechanism we built in this section is subsumed by nondeterministic search
and backtracking. You will probably also find, however, that your new query
language has subtle differences in behavior from the one implemented here. Can
you find examples that illustrate this difference?
Exercise 4.79: When we implemented the Lisp
evaluator in section 4-1, we saw how to use local environments to avoid
name conflicts between the parameters of procedures. For example, in
evaluating
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(sum-of-squares 3 4)
there is no confusion between the x in square and the x in
sum-of-squares , because we evaluate the body of each procedure in an
environment that is specially constructed to contain bindings for the local
variables. In the query system, we used a different strategy to avoid name
conflicts in applying rules. Each time we apply a rule we rename the variables
with new names that are guaranteed to be unique. The analogous strategy for
the Lisp evaluator would be to do away with local environments and simply
rename the variables in the body of a procedure each time we apply the
procedure.
Implement for the query language a rule-application method that uses
environments rather than renaming. See if you can build on your environment
structure to create constructs in the query language for dealing with large
systems, such as the rule analog of block-structured procedures. Can you
relate any of this to the problem of making deductions in a context (e.g., ``If
I supposed that P were true, then I would be able to deduce A and
B.'') as a method of problem solving? (This problem is open-ended. A good
answer is probably worth a Ph.D.)
@chapter Computing with Register Machines
My aim is to show that the heavenly machine is not a kind of divine, live
being, but a kind of clockwork (and he who believes that a clock has soul
attributes the maker's glory to the work), insofar as nearly all the manifold
motions are caused by a most simple and material force, just as all motions of
the clock are caused by a single weight.
Johannes Kepler (letter to Herwart von Hohenburg, 1605)
We began this book by studying processes and by describing processes in terms
of procedures written in Lisp. To explain the meanings of these procedures, we
used a succession of models of evaluation: the substitution model of
Chapter 1, the environment model of Chapter 3, and the metacircular
evaluator of Chapter 4. Our examination of the metacircular evaluator,
in particular, dispelled much of the mystery of how Lisp-like languages are
interpreted. But even the metacircular evaluator leaves important questions
unanswered, because it fails to elucidate the mechanisms of control in a Lisp
system. For instance, the evaluator does not explain how the evaluation of a
subexpression manages to return a value to the expression that uses this value,
nor does the evaluator explain how some recursive procedures generate iterative
processes (that is, are evaluated using constant space) whereas other recursive
procedures generate recursive processes. These questions remain unanswered
because the metacircular evaluator is itself a Lisp program and hence inherits
the control structure of the underlying Lisp system. In order to provide a
more complete description of the control structure of the Lisp evaluator, we
must work at a more primitive level than Lisp itself.
In this chapter we will describe processes in terms of the step-by-step
operation of a traditional computer. Such a computer, or register
machine
, sequentially executes instructions
that manipulate the
contents of a fixed set of storage elements called registers
. A
typical register-machine instruction applies a primitive operation to the
contents of some registers and assigns the result to another register. Our
descriptions of processes executed by register machines will look very much
like ``machine-language'' programs for traditional computers. However, instead
of focusing on the machine language of any particular computer, we will examine
several Lisp procedures and design a specific register machine to execute each
procedure. Thus, we will approach our task from the perspective of a hardware
architect rather than that of a machine-language computer programmer. In
designing register machines, we will develop mechanisms for implementing
important programming constructs such as recursion. We will also present a
language for describing designs for register machines. In section 5-2 we
will implement a Lisp program that uses these descriptions to simulate the
machines we design.
Most of the primitive operations of our register machines are very simple. For
example, an operation might add the numbers fetched from two registers,
producing a result to be stored into a third register. Such an operation can
be performed by easily described hardware. In order to deal with list
structure, however, we will also use the memory operations car ,
cdr , and cons , which require an elaborate storage-allocation
mechanism. In section 5-3 we study their implementation in terms of more
elementary operations.
In section 5-4, after we have accumulated experience formulating simple
procedures as register machines, we will design a machine that carries out the
algorithm described by the metacircular evaluator of section 4-1. This
will fill in the gap in our understanding of how Scheme expressions are
interpreted, by providing an explicit model for the mechanisms of control in
the evaluator. In section 5-5 we will study a simple compiler that
translates Scheme programs into sequences of instructions that can be executed
directly with the registers and operations of the evaluator register machine.
@menu
* 5-1:: Designing Register Machines
* 5-2:: A Register-Machine Simulator
* 5-3:: Storage Allocation and Garbage Collection
* 5-4:: The Explicit-Control Evaluator
* 5-5:: Compilation
@end menu
Designing Register Machines
To design a register machine, we must design its data paths
(registers and operations) and the controller
that sequences these
operations. To illustrate the design of a simple register machine, let us
examine Euclid's Algorithm, which is used to compute the greatest common
divisor (@acronym{GCD}) of two integers. As we saw in section 1-2-5,
Euclid's Algorithm can be carried out by an iterative process, as specified by
the following procedure:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
A machine to carry out this algorithm must keep track of two numbers, a and
b, so let us assume that these numbers are stored in two registers with
those names. The basic operations required are testing whether the contents of
register b is zero and computing the remainder of the contents of
register a divided by the contents of register b . The remainder
operation is a complex process, but assume for the moment that we have a
primitive device that computes remainders. On each cycle of the @acronym{GCD}
algorithm, the contents of register a must be replaced by the contents
of register b , and the contents of b must be replaced by the
remainder of the old contents of a divided by the old contents of
b . It would be convenient if these replacements could be done
simultaneously, but in our model of register machines we will assume that only
one register can be assigned a new value at each step. To accomplish the
replacements, our machine will use a third ``temporary'' register, which we
call t . (First the remainder will be placed in t , then the
contents of b will be placed in a , and finally the remainder
stored in t will be placed in b .)
We can illustrate the registers and operations required for this machine by
using the data-path diagram shown in Figure 5-1. In this diagram, the
registers ( a , b , and t ) are represented by rectangles.
Each way to assign a value to a register is indicated by an arrow with an
X behind the head, pointing from the source of data to the register. We
can think of the X as a button that, when pushed, allows the value at
the source to ``flow'' into the designated register. The label next to each
button is the name we will use to refer to the button. The names are
arbitrary, and can be chosen to have mnemonic value (for example, a<-b
denotes pushing the button that assigns the contents of register b to
register a ). The source of data for a register can be another register
(as in the a<-b assignment), an operation result (as in the t<-r
assignment), or a constant (a built-in value that cannot be changed,
represented in a data-path diagram by a triangle containing the constant).
An operation that computes a value from constants and the contents of registers
is represented in a data-path diagram by a trapezoid containing a name for the
operation. For example, the box marked rem in Figure 5-1
represents an operation that computes the remainder of the contents of the
registers a and b to which it is attached. Arrows (without
buttons) point from the input registers and constants to the box, and arrows
connect the operation's output value to registers. A test is represented by a
circle containing a name for the test. For example, our @acronym{GCD} machine
has an operation that tests whether the contents of register b is zero.
A test also has arrows from its input registers and constants, but it has no
output arrows; its value is used by the controller rather than by the data
paths. Overall, the data-path diagram shows the registers and operations that
are required for the machine and how they must be connected. If we view the
arrows as wires and the X buttons as switches, the data-path diagram is
very like the wiring diagram for a machine that could be constructed from
electrical components.
Figure 5.1: Data paths for a @acronym{GCD} machine.
___
+-----+ +-----+ / \
| a |<--(X)----| b +--->| = |
+--+--+ a<-b +-+---+ \___/
| | ^ ^
+------+ +----+ | |
| | (X) b<-t |
.--+---+--. | / \
\ rem / | / O \
\_____/ | +-----+
| |
(X) t<-r |
| |
V |
+-----+ |
| t +------+
+-----+
In order for the data paths to actually compute @acronym{GCD}s, the buttons
must be pushed in the correct sequence. We will describe this sequence in
terms of a controller diagram, as illustrated in Figure 5-2. The
elements of the controller diagram indicate how the data-path components should
be operated. The rectangular boxes in the controller diagram identify
data-path buttons to be pushed, and the arrows describe the sequencing from one
step to the next. The diamond in the diagram represents a decision. One of
the two sequencing arrows will be followed, depending on the value of the
data-path test identified in the diamond. We can interpret the controller in
terms of a physical analogy: Think of the diagram as a maze in which a marble
is rolling. When the marble rolls into a box, it pushes the data-path button
that is named by the box. When the marble rolls into a decision node (such as
the test for b = 0), it leaves the node on the path determined by the
result of the indicated test. Taken together, the data paths and the
controller completely describe a machine for computing @acronym{GCD}s. We
start the controller (the rolling marble) at the place marked start ,
after placing numbers in registers a and b . When the controller
reaches done , we will find the value of the @acronym{GCD} in register
a .
Figure 5.2: Controller for a @acronym{GCD} machine.
start
|
V
/ \ yes
+--->< = >-----> done
| \ /
| | no
| V
| +------+
| | t<-r |
| +---+--+
| |
| V
| +------+
| | a<-b |
| +---+--+
| |
| V
| +------+
+--+ b<-t |
+------+
Exercise 5.1: Design a register machine to
compute factorials using the iterative algorithm specified by the following
procedure. Draw data-path and controller diagrams for this machine.
@menu
* 5-1-1:: A Language for Describing Register Machines
* 5-1-2:: Abstraction in Machine Design
* 5-1-3:: Subroutines
* 5-1-4:: Using a Stack to Implement Recursion
* 5-1-5:: Instruction Summary
@end menu
A Language for Describing Register Machines
Data-path and controller diagrams are adequate for representing simple machines
such as @acronym{GCD}, but they are unwieldy for describing large machines such
as a Lisp interpreter. To make it possible to deal with complex machines, we
will create a language that presents, in textual form, all the information
given by the data-path and controller diagrams. We will start with a notation
that directly mirrors the diagrams.
We define the data paths of a machine by describing the registers and the
operations. To describe a register, we give it a name and specify the buttons
that control assignment to it. We give each of these buttons a name and
specify the source of the data that enters the register under the button's
control. (The source is a register, a constant, or an operation.) To describe
an operation, we give it a name and specify its inputs (registers or
constants).
We define the controller of a machine as a sequence of instructions
together with labels
that identify entry points
in the
sequence. An instruction is one of the following:
The name of a data-path button to push to assign a value to a register. (This
corresponds to a box in the controller diagram.)
A test instruction, that performs a specified test.
A conditional branch ( branch instruction) to a location indicated by a
controller label, based on the result of the previous test. (The test and
branch together correspond to a diamond in the controller diagram.) If the
test is false, the controller should continue with the next instruction in the
sequence. Otherwise, the controller should continue with the instruction after
the label.
An unconditional branch ( goto instruction) naming a controller label at
which to continue execution.
The machine starts at the beginning of the controller instruction sequence and
stops when execution reaches the end of the sequence. Except when a branch
changes the flow of control, instructions are executed in the order in which
they are listed.
Figure 5.3: A specification of the @acronym{GCD}
machine.
Figure 5-3 shows the @acronym{GCD} machine described in this way. This
example only hints at the generality of these descriptions, since the
@acronym{GCD} machine is a very simple case: Each register has only one button,
and each button and test is used only once in the controller.
Unfortunately, it is difficult to read such a description. In order to
understand the controller instructions we must constantly refer back to the
definitions of the button names and the operation names, and to understand what
the buttons do we may have to refer to the definitions of the operation names.
We will thus transform our notation to combine the information from the
data-path and controller descriptions so that we see it all together.
To obtain this form of description, we will replace the arbitrary button and
operation names by the definitions of their behavior. That is, instead of
saying (in the controller) ``Push button t<-r '' and separately saying
(in the data paths) ``Button t<-r assigns the value of the rem
operation to register t '' and ``The rem operation's inputs are
the contents of registers a and b ,'' we will say (in the
controller) ``Push the button that assigns to register t the value of
the rem operation on the contents of registers a and b .''
Similarly, instead of saying (in the controller) ``Perform the = test''
and separately saying (in the data paths) ``The = test operates on the
contents of register b and the constant 0,'' we will say ``Perform the
= test on the contents of register b and the constant 0.'' We
will omit the data-path description, leaving only the controller sequence.
Thus, the @acronym{GCD} machine is described as follows:
(controller
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)
This form of description is easier to read than the kind illustrated in
Figure 5-3, but it also has disadvantages:
It is more verbose for large machines, because complete descriptions of the
data-path elements are repeated whenever the elements are mentioned in the
controller instruction sequence. (This is not a problem in the @acronym{GCD}
example, because each operation and button is used only once.) Moreover,
repeating the data-path descriptions obscures the actual data-path structure of
the machine; it is not obvious for a large machine how many registers,
operations, and buttons there are and how they are interconnected.
Because the controller instructions in a machine definition look like Lisp
expressions, it is easy to forget that they are not arbitrary Lisp expressions.
They can notate only legal machine operations. For example, operations can
operate directly only on constants and the contents of registers, not on the
results of other operations.
In spite of these disadvantages, we will use this register-machine language
throughout this chapter, because we will be more concerned with understanding
controllers than with understanding the elements and connections in data paths.
We should keep in mind, however, that data-path design is crucial in designing
real machines.
Exercise 5.2: Use the register-machine language
to describe the iterative factorial machine of Exercise 5-1.
Actions
Let us modify the @acronym{GCD} machine so that we can type in the numbers
whose @acronym{GCD} we want and get the answer printed at our terminal. We
will not discuss how to make a machine that can read and print, but will assume
(as we do when we use read and display in Scheme) that they are
available as primitive operations.
This assumption glosses over a
great deal of complexity. Usually a large portion of the implementation of a
Lisp system is dedicated to making reading and printing work.
Read is like the operations we have been using in that it produces a
value that can be stored in a register. But read does not take inputs
from any registers; its value depends on something that happens outside the
parts of the machine we are designing. We will allow our machine's operations
to have such behavior, and thus will draw and notate the use of read
just as we do any other operation that computes a value.
Print , on the other hand, differs from the operations we have been using
in a fundamental way: It does not produce an output value to be stored in a
register. Though it has an effect, this effect is not on a part of the machine
we are designing. We will refer to this kind of operation as an
action
. We will represent an action in a data-path diagram just as
we represent an operation that computes a value---as a trapezoid that contains
the name of the action. Arrows point to the action box from any inputs
(registers or constants). We also associate a button with the action. Pushing
the button makes the action happen. To make a controller push an action button
we use a new kind of instruction called perform . Thus, the action of
printing the contents of register a is represented in a controller
sequence by the instruction
(perform (op print) (reg a))
Figure 5-4 shows the data paths and controller for the new @acronym{GCD}
machine. Instead of having the machine stop after printing the answer, we have
made it start over, so that it repeatedly reads a pair of numbers, computes
their @acronym{GCD}, and prints the result. This structure is like the driver
loops we used in the interpreters of Chapter 4.
Figure 5.4: A @acronym{GCD} machine that reads
inputs and prints results.
.--------.
\ read /
\____/
|
+-------*------+
| |
a<-rd (X) (X) b<-rd
| |
V V ___
+-----+ +-----+ / \
| a |<--(X)--+ b +----->| = |
+-+-+-+ a<-b +-+---+ \___/
| | | ^ ^
+--+ +----+ +--+ | |
| | | (X) b<-t / \
V V V | / O \
.---------. .---------. | /_____\
--(X)->\ print / \ rem / |
P \_____/ \_____/ |
| |
(X) t<-r |
| |
V |
+-----+ |
| t +----+
+-----+
(controller
gcd-loop
(assign a (op read))
(assign b (op read))
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done
(perform (op print) (reg a))
(goto (label gcd-loop)))
Abstraction in Machine Design
We will often define a machine to include ``primitive'' operations that are
actually very complex. For example, in sections 5-4 and 5-5 we
will treat Scheme's environment manipulations as primitive. Such abstraction
is valuable because it allows us to ignore the details of parts of a machine so
that we can concentrate on other aspects of the design. The fact that we have
swept a lot of complexity under the rug, however, does not mean that a machine
design is unrealistic. We can always replace the complex ``primitives'' by
simpler primitive operations.
Consider the @acronym{GCD} machine. The machine has an instruction that
computes the remainder of the contents of registers a and b and
assigns the result to register t . If we want to construct the
@acronym{GCD} machine without using a primitive remainder operation, we must
specify how to compute remainders in terms of simpler operations, such as
subtraction. Indeed, we can write a Scheme procedure that finds remainders in
this way:
(define (remainder n d)
(if (< n d)
n
(remainder (- n d) d)))
We can thus replace the remainder operation in the @acronym{GCD} machine's data
paths with a subtraction operation and a comparison test. Figure 5-5
shows the data paths and controller for the elaborated machine. The
instruction
Figure 5.5: Data paths and controller for the
elaborated @acronym{GCD} machine.
Begin by assuming that good-enough? and improve operations are
available as primitives. Then show how to expand these in terms of arithmetic
operations. Describe each version of the sqrt machine design by drawing
a data-path diagram and writing a controller definition in the register-machine
language.
Subroutines
When designing a machine to perform a computation, we would often prefer to
arrange for components to be shared by different parts of the computation
rather than duplicate the components. Consider a machine that includes two
@acronym{GCD} computations---one that finds the @acronym{GCD} of the contents
of registers a and b and one that finds the @acronym{GCD} of the
contents of registers c and d . We might start by assuming we
have a primitive gcd operation, then expand the two instances of
gcd in terms of more primitive operations. Figure 5-7 shows just
the @acronym{GCD} portions of the resulting machine's data paths, without
showing how they connect to the rest of the machine. The figure also shows the
corresponding portions of the machine's controller sequence.
Figure 5.7: Portions of the data paths and
controller sequence for a machine with two @acronym{GCD} computations.
___ ___
+-----+ +-----+ / \ +-----+ +-----+ / \
| a |<-(X)---+ b |--->| = | | c |<-(X)---+ d |--->| = |
+--+--+ a<-b ++----+ \___/ +--+--+ c<-d ++----+ \___/
| | ^ ^ | | ^ ^
`----. .---' | | `----. .---' | |
V V (X) b<-t | V V (X) d<-t |
------- | / \ ------- | / \
\ rem / | /_0_\ \ rem / | /_0_\
--+-- | --+-- |
| | | |
(X) t<-r | (X) s<-r |
| | | |
V | V |
+-----+ | +-----+ |
| t +-----' | s +-----'
+-----+ +-----+
gcd-1
(test (op =) (reg b) (const 0))
(branch (label after-gcd-1))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-1))
after-gcd-1
...
gcd-2
(test (op =) (reg d) (const 0))
(branch (label after-gcd-2))
(assign s (op rem) (reg c) (reg d))
(assign c (reg d))
(assign d (reg s))
(goto (label gcd-2))
after-gcd-2
This machine has two remainder operation boxes and two boxes for testing
equality. If the duplicated components are complicated, as is the remainder
box, this will not be an economical way to build the machine. We can avoid
duplicating the data-path components by using the same components for both
@acronym{GCD} computations, provided that doing so will not affect the rest of
the larger machine's computation. If the values in registers a and
b are not needed by the time the controller gets to gcd-2 (or if
these values can be moved to other registers for safekeeping), we can change
the machine so that it uses registers a and b , rather than
registers c and d , in computing the second @acronym{GCD} as well
as the first. If we do this, we obtain the controller sequence shown in
Figure 5-8.
We have removed the duplicate data-path components (so that the data paths are
again as in Figure 5-1), but the controller now has two @acronym{GCD}
sequences that differ only in their entry-point labels. It would be better to
replace these two sequences by branches to a single sequence---a gcd subroutine
---at the end of which we branch back to the correct place
in the main instruction sequence. We can accomplish this as follows: Before
branching to gcd , we place a distinguishing value (such as 0 or 1) into
a special register, continue . At the end of the gcd subroutine
we return either to after-gcd-1 or to after-gcd-2 , depending on
the value of the continue register. Figure 5-9 shows the relevant
portion of the resulting controller sequence, which includes only a single copy
of the gcd instructions.
Figure 5.8: Portions of the controller sequence for
a machine that uses the same data-path components for two different
@acronym{GCD} computations.
gcd-1
(test (op =) (reg b) (const 0))
(branch (label after-gcd-1))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-1))
after-gcd-1
...
gcd-2
(test (op =) (reg b) (const 0))
(branch (label after-gcd-2))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-2))
after-gcd-2
Figure 5.9: Using a continue register to
avoid the duplicate controller sequence in Figure 5-8.
gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(test (op =) (reg continue) (const 0))
(branch (label after-gcd-1))
(goto (label after-gcd-2))
...
;; Before branching to gcd from the first place where
;; it is needed, we place 0 in the continue register
(assign continue (const 0))
(goto (label gcd))
after-gcd-1
...
;; Before the second use of gcd , we place 1 in the continue register
(assign continue (const 1))
(goto (label gcd))
after-gcd-2
Figure 5.10: Assigning labels to the
continue register simplifies and generalizes the strategy shown in
Figure 5-9.
gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(goto (reg continue))
...
;; Before calling gcd , we assign to continue
;; the label to which gcd should return.
(assign continue (label after-gcd-1))
(goto (label gcd))
after-gcd-1
...
;; Here is the second call to gcd , with a different continuation.
(assign continue (label after-gcd-2))
(goto (label gcd))
after-gcd-2
This is a reasonable approach for handling small problems, but it would be
awkward if there were many instances of @acronym{GCD} computations in the
controller sequence. To decide where to continue executing after the
gcd subroutine, we would need tests in the data paths and branch
instructions in the controller for all the places that use gcd . A more
powerful method for implementing subroutines is to have the continue
register hold the label of the entry point in the controller sequence at which
execution should continue when the subroutine is finished. Implementing this
strategy requires a new kind of connection between the data paths and the
controller of a register machine: There must be a way to assign to a register a
label in the controller sequence in such a way that this value can be fetched
from the register and used to continue execution at the designated entry point.
To reflect this ability, we will extend the assign instruction of the
register-machine language to allow a register to be assigned as value a label
from the controller sequence (as a special kind of constant). We will also
extend the goto instruction to allow execution to continue at the entry
point described by the contents of a register rather than only at an entry
point described by a constant label. Using these new constructs we can
terminate the gcd subroutine with a branch to the location stored in the
continue register. This leads to the controller sequence shown in
Figure 5-10.
A machine with more than one subroutine could use multiple continuation
registers (e.g., gcd-continue , factorial-continue ) or we could
have all subroutines share a single continue register. Sharing is more
economical, but we must be careful if we have a subroutine ( sub1 ) that
calls another subroutine ( sub2 ). Unless sub1 saves the contents
of continue in some other register before setting up continue for
the call to sub2 , sub1 will not know where to go when it is
finished. The mechanism developed in the next section to handle recursion also
provides a better solution to this problem of nested subroutine calls.
Using a Stack to Implement Recursion
With the ideas illustrated so far, we can implement any iterative process by
specifying a register machine that has a register corresponding to each state
variable of the process. The machine repeatedly executes a controller loop,
changing the contents of the registers, until some termination condition is
satisfied. At each point in the controller sequence, the state of the machine
(representing the state of the iterative process) is completely determined by
the contents of the registers (the values of the state variables).
Implementing recursive processes, however, requires an additional mechanism.
Consider the following recursive method for computing factorials, which we
first examined in section 1-2-1:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
As we see from the procedure, computing n! requires computing (n - 1)!.
Our @acronym{GCD} machine, modeled on the procedure
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
similarly had to compute another @acronym{GCD}. But there is an important
difference between the gcd procedure, which reduces the original
computation to a new @acronym{GCD} computation, and factorial , which
requires computing another factorial as a subproblem. In @acronym{GCD}, the
answer to the new @acronym{GCD} computation is the answer to the original
problem. To compute the next @acronym{GCD}, we simply place the new arguments
in the input registers of the @acronym{GCD} machine and reuse the machine's
data paths by executing the same controller sequence. When the machine is
finished solving the final @acronym{GCD} problem, it has completed the entire
computation.
In the case of factorial (or any recursive process) the answer to the new
factorial subproblem is not the answer to the original problem. The value
obtained for (n - 1)! must be multiplied by n to get the final answer.
If we try to imitate the @acronym{GCD} design, and solve the factorial
subproblem by decrementing the n register and rerunning the factorial
machine, we will no longer have available the old value of n by which to
multiply the result. We thus need a second factorial machine to work on the
subproblem. This second factorial computation itself has a factorial
subproblem, which requires a third factorial machine, and so on. Since each
factorial machine contains another factorial machine within it, the total
machine contains an infinite nest of similar machines and hence cannot be
constructed from a fixed, finite number of parts.
Nevertheless, we can implement the factorial process as a register machine if
we can arrange to use the same components for each nested instance of the
machine. Specifically, the machine that computes n! should use the same
components to work on the subproblem of computing (n - 1)!, on the
subproblem for (n - 2)!, and so on. This is plausible because, although
the factorial process dictates that an unbounded number of copies of the same
machine are needed to perform a computation, only one of these copies needs to
be active at any given time. When the machine encounters a recursive
subproblem, it can suspend work on the main problem, reuse the same physical
parts to work on the subproblem, then continue the suspended computation.
In the subproblem, the contents of the registers will be different than they
were in the main problem. (In this case the n register is decremented.)
In order to be able to continue the suspended computation, the machine must
save the contents of any registers that will be needed after the subproblem is
solved so that these can be restored to continue the suspended computation. In
the case of factorial, we will save the old value of n , to be restored
when we are finished computing the factorial of the decremented n
register.
One might argue that we don't need to save the old n ;
after we decrement it and solve the subproblem, we could simply increment it to
recover the old value. Although this strategy works for factorial, it cannot
work in general, since the old value of a register cannot always be computed
from the new one.
Since there is no a priori limit on the depth of nested recursive calls,
we may need to save an arbitrary number of register values. These values must
be restored in the reverse of the order in which they were saved, since in a
nest of recursions the last subproblem to be entered is the first to be
finished. This dictates the use of a stack
, or ``last in, first
out'' data structure, to save register values. We can extend the
register-machine language to include a stack by adding two kinds of
instructions: Values are placed on the stack using a save instruction
and restored from the stack using a restore instruction. After a
sequence of values has been save d on the stack, a sequence of
restore s will retrieve these values in reverse order.
In
section 5-3 we will see how to implement a stack in terms of more
primitive operations.
With the aid of the stack, we can reuse a single copy of the factorial
machine's data paths for each factorial subproblem. There is a similar design
issue in reusing the controller sequence that operates the data paths. To
reexecute the factorial computation, the controller cannot simply loop back to
the beginning, as with an iterative process, because after solving the (n -
1)! subproblem the machine must still multiply the result by n. The
controller must suspend its computation of n!, solve the (n - 1)!
subproblem, then continue its computation of n!. This view of the
factorial computation suggests the use of the subroutine mechanism described in
section 5-1-3, which has the controller use a continue register to
transfer to the part of the sequence that solves a subproblem and then continue
where it left off on the main problem. We can thus make a factorial subroutine
that returns to the entry point stored in the continue register. Around
each subroutine call, we save and restore continue just as we do the
n register, since each ``level'' of the factorial computation will use
the same continue register. That is, the factorial subroutine must put
a new value in continue when it calls itself for a subproblem, but it
will need the old value in order to return to the place that called it to solve
a subproblem.
Figure 5-11 shows the data paths and controller for a machine that
implements the recursive factorial procedure. The machine has a stack
and three registers, called n , val , and continue . To
simplify the data-path diagram, we have not named the register-assignment
buttons, only the stack-operation buttons ( sc and sn to save
registers, rc and rn to restore registers). To operate the
machine, we put in register n the number whose factorial we wish to
compute and start the machine. When the machine reaches fact-done , the
computation is finished and the answer will be found in the val
register. In the controller sequence, n and continue are saved
before each recursive call and restored upon return from the call. Returning
from a call is accomplished by branching to the location stored in
continue . Continue is initialized when the machine starts so
that the last return will go to fact-done . The val register,
which holds the result of the factorial computation, is not saved before the
recursive call, because the old contents of val is not useful after the
subroutine returns. Only the new value, which is the value produced by the
subcomputation, is needed.
Although in principle the factorial computation requires an infinite machine,
the machine in Figure 5-11 is actually finite except for the stack, which
is potentially unbounded. Any particular physical implementation of a stack,
however, will be of finite size, and this will limit the depth of recursive
calls that can be handled by the machine. This implementation of factorial
illustrates the general strategy for realizing recursive algorithms as ordinary
register machines augmented by stacks. When a recursive subproblem is
encountered, we save on the stack the registers whose current values will be
required after the subproblem is solved, solve the recursive subproblem, then
restore the saved registers and continue execution on the main problem. The
continue register must always be saved. Whether there are other
registers that need to be saved depends on the particular machine, since not
all recursive computations need the original values of registers that are
modified during solution of the subproblem (see Exercise 5-4).
A double recursion
Let us examine a more complex recursive process, the tree-recursive computation
of the Fibonacci numbers, which we introduced in section 1-2-2:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
Just as with factorial, we can implement the recursive Fibonacci computation as
a register machine with registers n , val , and continue .
The machine is more complex than the one for factorial, because there are two
places in the controller sequence where we need to perform recursive
calls---once to compute Fib(n - 1) and once to compute Fib(n - 2). To
set up for each of these calls, we save the registers whose values will be
needed later, set the n register to the number whose Fib we need to
compute recursively (n - 1 or n - 2), and assign to continue the
entry point in the main sequence to which to return ( afterfib-n-1 or
afterfib-n-2 , respectively). We then go to fib-loop . When we
return from the recursive call, the answer is in val . Figure 5-12
shows the controller sequence for this machine.
(controller
(assign continue (label fact-done)) ; set up final return address
fact-loop
(test (op =) (reg n) (const 1))
(branch (label base-case))
;; Set up for the recursive call by saving n and continue .
;; Set up continue so that the computation will continue
;; at after-fact when the subroutine returns.
(save continue)
(save n)
(assign n (op -) (reg n) (const 1))
(assign continue (label after-fact))
(goto (label fact-loop))
after-fact
(restore n)
(restore continue)
(assign val (op *) (reg n) (reg val)) ; val now contains n(n - 1)!
(goto (reg continue)) ; return to caller
base-case
(assign val (const 1)) ; base case: 1! = 1
(goto (reg continue)) ; return to caller
fact-done)
Figure 5.12: Controller for a machine to compute
Fibonacci numbers.
(controller
(assign continue (label fib-done))
fib-loop
(test (op <) (reg n) (const 2))
(branch (label immediate-answer))
;; set up to compute Fib(n - 1)
(save continue)
(assign continue (label afterfib-n-1))
(save n) ; save old value of n
(assign n (op -) (reg n) (const 1)); clobber n to n - 1
(goto (label fib-loop)) ; perform recursive call
afterfib-n-1 ; upon return, val contains Fib(n - 1)
(restore n)
(restore continue)
;; set up to compute Fib(n - 2)
(assign n (op -) (reg n) (const 2))
(save continue)
(assign continue (label afterfib-n-2))
(save val) ; save Fib(n - 1)
(goto (label fib-loop))
afterfib-n-2 ; upon return, val contains Fib(n - 2)
(assign n (reg val)) ; n now contains Fib(n - 2)
(restore val) ; val now contains Fib(n - 1)
(restore continue)
(assign val ; Fib(n - 1) + Fib(n - 2)
(op +) (reg val) (reg n))
(goto (reg continue)) ; return to caller, answer is in val
immediate-answer
(assign val (reg n)) ; base case: Fib(n) = n
(goto (reg continue))
fib-done)
Exercise 5.4: Specify register machines that
implement each of the following procedures. For each machine, write a
controller instruction sequence and draw a diagram showing the data paths.
Recursive exponentiation:
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
Iterative exponentiation:
(define (expt b n)
(define (expt-iter counter product)
(if (= counter 0)
product
(expt-iter (- counter 1) (* b product))))
(expt-iter n 1))
Exercise 5.5: Hand-simulate the factorial and
Fibonacci machines, using some nontrivial input (requiring execution of at
least one recursive call). Show the contents of the stack at each significant
point in the execution.
Exercise 5.6: Ben Bitdiddle observes that the
Fibonacci machine's controller sequence has an extra save and an extra
restore , which can be removed to make a faster machine. Where are these
instructions?
Instruction Summary
A controller instruction in our register-machine language has one of the
following forms, where each is either (reg
>) or (const >). These
instructions were introduced in section 5-1-1:
The use of registers to hold labels was introduced in section 5-1-3:
(assign (label ))
(goto (reg ))
Instructions to use the stack were introduced in section 5-1-4:
(save )
(restore )
The only kind of we have seen so far is a number,
but later we will use strings, symbols, and lists.
For example,@*
(const "abc") is the string "abc" ,@*
(const abc) is the symbol abc ,@*
(const (a b c)) is the list (a b c) ,@*
and (const ()) is the empty list.
A Register-Machine Simulator
In order to gain a good understanding of the design of register machines, we
must test the machines we design to see if they perform as expected. One way
to test a design is to hand-simulate the operation of the controller, as in
Exercise 5-5. But this is extremely tedious for all but the simplest
machines. In this section we construct a simulator for machines described in
the register-machine language. The simulator is a Scheme program with four
interface procedures. The first uses a description of a register machine to
construct a model of the machine (a data structure whose parts correspond to
the parts of the machine to be simulated), and the other three allow us to
simulate the machine by manipulating the model:
(make-machine )
constructs and returns a model of the machine with the given registers,
operations, and controller.
(set-register-contents! )
stores a value in a simulated register in the given machine.
(get-register-contents )
returns the contents of a simulated register in the given machine.
(start )
simulates the execution of the given machine, starting from the beginning of
the controller sequence and stopping when it reaches the end of the sequence.
As an example of how these procedures are used, we can define
gcd-machine to be a model of the @acronym{GCD} machine of section
5-1-1 as follows:
(define gcd-machine
(make-machine
'(a b t)
(list (list 'rem remainder) (list '= =))
'(test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)))
The first argument to make-machine is a list of register names. The
next argument is a table (a list of two-element lists) that pairs each
operation name with a Scheme procedure that implements the operation (that is,
produces the same output value given the same input values). The last argument
specifies the controller as a list of labels and machine instructions, as in
section 5-1.
To compute @acronym{GCD}s with this machine, we set the input registers, start
the machine, and examine the result when the simulation terminates:
This computation will run much more slowly than a gcd procedure written
in Scheme, because we will simulate low-level machine instructions, such as
assign , by much more complex operations.
Exercise 5.7: Use the simulator to test the
machines you designed in Exercise 5-4.
@menu
* 5-2-1:: The Machine Model
* 5-2-2:: The Assembler
* 5-2-3:: Generating Execution Procedures for Instructions
* 5-2-4:: Monitoring Machine Performance
@end menu
The Machine Model
The machine model generated by make-machine is represented as a
procedure with local state using the message-passing techniques developed in
Chapter 3. To build this model, make-machine begins by calling
the procedure make-new-machine to construct the parts of the machine
model that are common to all register machines. This basic machine model
constructed by make-new-machine is essentially a container for some
registers and a stack, together with an execution mechanism that processes the
controller instructions one by one.
Make-machine then extends this basic model (by sending it messages) to
include the registers, operations, and controller of the particular machine
being defined. First it allocates a register in the new machine for each of
the supplied register names and installs the designated operations in the
machine. Then it uses an assembler
(described below in section
5-2-2) to transform the controller list into instructions for the new
machine and installs these as the machine's instruction sequence.
Make-machine returns as its value the modified machine model.
We will represent a register as a procedure with local state, as in
Chapter 3. The procedure make-register creates a register that
holds a value that can be accessed or changed:
We can also represent a stack as a procedure with local state. The procedure
make-stack creates a stack whose local state consists of a list of the
items on the stack. A stack accepts requests to push an item onto the
stack, to pop the top item off the stack and return it, and to
initialize the stack to empty.
The make-new-machine procedure, shown in Figure 5-13, constructs
an object whose local state consists of a stack, an initially empty instruction
sequence, a list of operations that initially contains an operation to
initialize the stack, and a register table
that initially contains
two registers, named flag and pc (for ``program counter''). The
internal procedure allocate-register adds new entries to the register
table, and the internal procedure lookup-register looks up registers in
the table.
The flag register is used to control branching in the simulated machine.
Test instructions set the contents of flag to the result of the
test (true or false). Branch instructions decide whether or not to
branch by examining the contents of flag .
The pc register determines the sequencing of instructions as the machine
runs. This sequencing is implemented by the internal procedure execute .
In the simulation model, each machine instruction is a data structure that
includes a procedure of no arguments, called the instruction execution
procedure
, such that calling this procedure simulates executing the
instruction. As the simulation runs, pc points to the place in the
instruction sequence beginning with the next instruction to be executed.
Execute gets that instruction, executes it by calling the instruction
execution procedure, and repeats this cycle until there are no more
instructions to execute (i.e., until pc points to the end of the
instruction sequence).
As part of its operation, each instruction execution procedure modifies
pc to indicate the next instruction to be executed. Branch and
goto instructions change pc to point to the new destination. All
other instructions simply advance pc , making it point to the next
instruction in the sequence. Observe that each call to execute calls
execute again, but this does not produce an infinite loop because
running the instruction execution procedure changes the contents of pc .
Make-new-machine returns a dispatch procedure that implements
message-passing access to the internal state. Notice that starting the machine
is accomplished by setting pc to the beginning of the instruction
sequence and calling execute .
For convenience, we provide an alternate procedural interface to a machine's
start operation, as well as procedures to set and examine register
contents, as specified at the beginning of section 5-2:
The assembler transforms the sequence of controller expressions for a machine
into a corresponding list of machine instructions, each with its execution
procedure. Overall, the assembler is much like the evaluators we studied in
Chapter 4---there is an input language (in this case, the
register-machine language) and we must perform an appropriate action for each
type of expression in the language.
The technique of producing an execution procedure for each instruction is just
what we used in section 4-1-7 to speed up the evaluator by separating
analysis from runtime execution. As we saw in Chapter 4, much useful
analysis of Scheme expressions could be performed without knowing the actual
values of variables. Here, analogously, much useful analysis of
register-machine-language expressions can be performed without knowing the
actual contents of machine registers. For example, we can replace references
to registers by pointers to the register objects, and we can replace references
to labels by pointers to the place in the instruction sequence that the label
designates.
Before it can generate the instruction execution procedures, the assembler must
know what all the labels refer to, so it begins by scanning the controller text
to separate the labels from the instructions. As it scans the text, it
constructs both a list of instructions and a table that associates each label
with a pointer into that list. Then the assembler augments the instruction
list by inserting the execution procedure for each instruction.
The assemble procedure is the main entry to the assembler. It takes the
controller text and the machine model as arguments and returns the instruction
sequence to be stored in the model. Assemble calls
extract-labels to build the initial instruction list and label table
from the supplied controller text. The second argument to
extract-labels is a procedure to be called to process these results:
This procedure uses update-insts! to generate the instruction execution
procedures and insert them into the instruction list, and returns the modified
list.
Extract-labels takes as arguments a list text (the sequence of
controller instruction expressions) and a receive procedure.
Receive will be called with two values: (1) a list insts of
instruction data structures, each containing an instruction from text ;
and (2) a table called labels , which associates each label from
text with the position in the list insts that the label
designates.
Extract-labels works by sequentially scanning the elements of the
text and accumulating the insts and the labels . If an
element is a symbol (and thus a label) an appropriate entry is added to the
labels table. Otherwise the element is accumulated onto the
insts list.
Using the receive procedure here is a way to
get extract-labels to effectively return two values--- labels and
insts ---without explicitly making a compound data structure to hold
them. An alternative implementation, which returns an explicit pair of values,
is
You can consider our use of receive as demonstrating an elegant way to
return multiple values, or simply an excuse to show off a programming trick.
An argument like receive that is the next procedure to be invoked is
called a ``continuation.'' Recall that we also used continuations to implement
the backtracking control structure in the amb evaluator in section
4-3-3.
Update-insts! modifies the instruction list, which initially contains
only the text of the instructions, to include the corresponding execution
procedures:
The machine instruction data structure simply pairs the instruction text with
the corresponding execution procedure. The execution procedure is not yet
available when extract-labels constructs the instruction, and is
inserted later by update-insts! .
The instruction text is not used by our simulator, but it is handy to keep
around for debugging (see Exercise 5-16).
Elements of the label table are pairs:
Exercise 5.8: The following register-machine code
is ambiguous, because the label here is defined more than once:
start
(goto (label here))
here
(assign a (const 3))
(goto (label there))
here
(assign a (const 4))
(goto (label there))
there
With the simulator as written, what will the contents of register a be
when control reaches there ? Modify the extract-labels procedure
so that the assembler will signal an error if the same label name is used to
indicate two different locations.
Generating Execution Procedures for Instructions
The assembler calls make-execution-procedure to generate the execution
procedure for an instruction. Like the analyze procedure in the
evaluator of section 4-1-7, this dispatches on the type of instruction to
generate the appropriate execution procedure.
For each type of instruction in the register-machine language, there is a
generator that builds an appropriate execution procedure. The details of these
procedures determine both the syntax and meaning of the individual instructions
in the register-machine language. We use data abstraction to isolate the
detailed syntax of register-machine expressions from the general execution
mechanism, as we did for evaluators in section 4-1-2, by using syntax
procedures to extract and classify the parts of an instruction.
Assign instructions
The make-assign procedure handles assign instructions:
Make-assign extracts the target register name (the second element of the
instruction) and the value expression (the rest of the list that forms the
instruction) from the assign instruction using the selectors
The register name is looked up with get-register to produce the target
register object. The value expression is passed to make-operation-exp
if the value is the result of an operation, and to make-primitive-exp
otherwise. These procedures (shown below) parse the value expression and
produce an execution procedure for the value. This is a procedure of no
arguments, called value-proc , which will be evaluated during the
simulation to produce the actual value to be assigned to the register. Notice
that the work of looking up the register name and parsing the value expression
is performed just once, at assembly time, not every time the instruction is
simulated. This saving of work is the reason we use execution procedures, and
corresponds directly to the saving in work we obtained by separating program
analysis from execution in the evaluator of section 4-1-7.
The result returned by make-assign is the execution procedure for the
assign instruction. When this procedure is called (by the machine
model's execute procedure), it sets the contents of the target register
to the result obtained by executing value-proc . Then it advances the
pc to the next instruction by running the procedure
(define (advance-pc pc)
(set-contents! pc (cdr (get-contents pc))))
Advance-pc is the normal termination for all instructions except
branch and goto .
Test , branch , and goto instructions
Make-test handles test instructions in a similar way. It
extracts the expression that specifies the condition to be tested and generates
an execution procedure for it. At simulation time, the procedure for the
condition is called, the result is assigned to the flag register, and
the pc is advanced:
The execution procedure for a branch instruction checks the contents of
the flag register and either sets the contents of the pc to the
branch destination (if the branch is taken) or else just advances the pc
(if the branch is not taken). Notice that the indicated destination in a
branch instruction must be a label, and the make-branch procedure
enforces this. Notice also that the label is looked up at assembly time, not
each time the branch instruction is simulated.
A goto instruction is similar to a branch, except that the destination
may be specified either as a label or as a register, and there is no condition
to check---the pc is always set to the new destination.
The final instruction type, handled by make-perform , generates an
execution procedure for the action to be performed. At simulation time, the
action procedure is executed and the pc advanced.
The value of a reg , label , or const expression may be
needed for assignment to a register ( make-assign ) or for input to an
operation ( make-operation-exp , below). The following procedure
generates execution procedures to produce values for these expressions during
the simulation:
Assign , perform , and test instructions may include the
application of a machine operation (specified by an op expression) to
some operands (specified by reg and const expressions). The
following procedure produces an execution procedure for an ``operation
expression''---a list containing the operation and operand expressions from the
instruction:
Observe that the treatment of operation expressions is very much like the
treatment of procedure applications by the analyze-application procedure
in the evaluator of section 4-1-7 in that we generate an execution
procedure for each operand. At simulation time, we call the operand procedures
and apply the Scheme procedure that simulates the operation to the resulting
values. The simulation procedure is found by looking up the operation name in
the operation table for the machine:
(define (lookup-prim symbol operations)
(let ((val (assoc symbol operations)))
(if val
(cadr val)
(error "Unknown operation -- ASSEMBLE" symbol))))
Exercise 5.9: The treatment of machine operations
above permits them to operate on labels as well as on constants and the
contents of registers. Modify the expression-processing procedures to enforce
the condition that operations can be used only with registers and constants.
Exercise 5.10: Design a new syntax for
register-machine instructions and modify the simulator to use your new syntax.
Can you implement your new syntax without changing any part of the simulator
except the syntax procedures in this section?
Exercise 5.11: When we introduced save
and restore in section 5-1-4, we didn't specify what would happen
if you tried to restore a register that was not the last one saved, as in the
sequence
(save y)
(save x)
(restore y)
There are several reasonable possibilities for the meaning of restore :
(restore y) puts into y the last value saved on the stack,
regardless of what register that value came from. This is the way our
simulator behaves. Show how to take advantage of this behavior to eliminate
one instruction from the Fibonacci machine of section 5-1-4 (Figure
5-12).
(restore y) puts into y the last value saved on the stack, but
only if that value was saved from y ; otherwise, it signals an error.
Modify the simulator to behave this way. You will have to change save
to put the register name on the stack along with the value.
(restore y) puts into y the last value saved from y
regardless of what other registers were saved after y and not restored.
Modify the simulator to behave this way. You will have to associate a separate
stack with each register. You should make the initialize-stack
operation initialize all the register stacks.
Exercise 5.12: The simulator can be used to help
determine the data paths required for implementing a machine with a given
controller. Extend the assembler to store the following information in the
machine model:
ize
a list of all instructions, with duplicates removed, sorted by instruction type
( assign , goto , and so on);
a list (without duplicates) of the registers used to hold entry points (these
are the registers referenced by goto instructions);
a list (without duplicates) of the registers that are save d
or restore d;
for each register, a list (without duplicates) of the sources from which it is
assigned (for example, the sources for register val in the factorial
machine of Figure 5-11 are (const 1) and ((op *) (reg n)
(reg val)) ).
Extend the message-passing interface to the machine to provide access to this
new information. To test your analyzer, define the Fibonacci machine from
Figure 5-12 and examine the lists you constructed.
Exercise 5.13: Modify the simulator so that it
uses the controller sequence to determine what registers the machine has rather
than requiring a list of registers as an argument to make-machine .
Instead of pre-allocating the registers in make-machine , you can
allocate them one at a time when they are first seen during assembly of the
instructions.
Monitoring Machine Performance
Simulation is useful not only for verifying the correctness of a proposed
machine design but also for measuring the machine's performance. For example,
we can install in our simulation program a ``meter'' that measures the number
of stack operations used in a computation. To do this, we modify our simulated
stack to keep track of the number of times registers are saved on the stack and
the maximum depth reached by the stack, and add a message to the stack's
interface that prints the statistics, as shown below. We also add an operation
to the basic machine model to print the stack statistics, by initializing
the-ops in make-new-machine to
Exercise 5-15 through Exercise 5-19 describe other useful
monitoring and debugging features that can be added to the register-machine
simulator.
Exercise 5.14: Measure the number of pushes and
the maximum stack depth required to compute n! for various small values of
n using the factorial machine shown in Figure 5-11. From your data
determine formulas in terms of n for the total number of push operations
and the maximum stack depth used in computing n! for any n > 1. Note
that each of these is a linear function of n and is thus determined by two
constants. In order to get the statistics printed, you will have to augment
the factorial machine with instructions to initialize the stack and print the
statistics. You may want to also modify the machine so that it repeatedly
reads a value for n, computes the factorial, and prints the result (as we
did for the @acronym{GCD} machine in Figure 5-4), so that you will not
have to repeatedly invoke get-register-contents ,
set-register-contents! , and start .
Exercise 5.15: Add instruction
counting
to the register machine simulation. That is, have the machine model
keep track of the number of instructions executed. Extend the machine model's
interface to accept a new message that prints the value of the instruction
count and resets the count to zero.
Exercise 5.16: Augment the simulator to provide
for instruction tracing
. That is, before each instruction is
executed, the simulator should print the text of the instruction. Make the
machine model accept trace-on and trace-off messages to turn
tracing on and off.
Exercise 5.17: Extend the instruction tracing of
Exercise 5-16 so that before printing an instruction, the simulator
prints any labels that immediately precede that instruction in the controller
sequence. Be careful to do this in a way that does not interfere with
instruction counting (Exercise 5-15). You will have to make the
simulator retain the necessary label information.
Exercise 5.18: Modify the make-register
procedure of section 5-2-1 so that registers can be traced. Registers
should accept messages that turn tracing on and off. When a register is
traced, assigning a value to the register should print the name of the
register, the old contents of the register, and the new contents being
assigned. Extend the interface to the machine model to permit you to turn
tracing on and off for designated machine registers.
Exercise 5.19: Alyssa P. Hacker wants a
breakpoint
feature in the simulator to help her debug her machine
designs. You have been hired to install this feature for her. She wants to be
able to specify a place in the controller sequence where the simulator will
stop and allow her to examine the state of the machine. You are to implement a
procedure
(set-breakpoint
that sets a breakpoint just before the nth instruction after the given
label. For example,
(set-breakpoint gcd-machine 'test-b 4)
installs a breakpoint in gcd-machine just before the assignment to
register a . When the simulator reaches the breakpoint it should print
the label and the offset of the breakpoint and stop executing instructions.
Alyssa can then use get-register-contents and
set-register-contents! to manipulate the state of the simulated machine.
She should then be able to continue execution by saying
(proceed-machine )
She should also be able to remove a specific breakpoint by means of
(cancel-breakpoint
or to remove all breakpoints by means of
(cancel-all-breakpoints )
Storage Allocation and Garbage Collection
In section 5-4, we will show how to implement a Scheme evaluator as a
register machine. In order to simplify the discussion, we will assume that our
register machines can be equipped with a list-structured memory
, in
which the basic operations for manipulating list-structured data are primitive.
Postulating the existence of such a memory is a useful abstraction when one is
focusing on the mechanisms of control in a Scheme interpreter, but this does
not reflect a realistic view of the actual primitive data operations of
contemporary computers. To obtain a more complete picture of how a Lisp system
operates, we must investigate how list structure can be represented in a way
that is compatible with conventional computer memories.
There are two considerations in implementing list structure. The first is
purely an issue of representation: how to represent the ``box-and-pointer''
structure of Lisp pairs, using only the storage and addressing capabilities of
typical computer memories. The second issue concerns the management of memory
as a computation proceeds. The operation of a Lisp system depends crucially on
the ability to continually create new data objects. These include objects that
are explicitly created by the Lisp procedures being interpreted as well as
structures created by the interpreter itself, such as environments and argument
lists. Although the constant creation of new data objects would pose no
problem on a computer with an infinite amount of rapidly addressable memory,
computer memories are available only in finite sizes (more's the pity). Lisp
systems thus provide an automatic storage allocation
facility to
support the illusion of an infinite memory. When a data object is no longer
needed, the memory allocated to it is automatically recycled and used to
construct new data objects. There are various techniques for providing such
automatic storage allocation. The method we shall discuss in this section is
called garbage collection
.
@menu
* 5-3-1:: Memory as Vectors
* 5-3-2:: Maintaining the Illusion of Infinite Memory
@end menu
Memory as Vectors
A conventional computer memory can be thought of as an array of cubbyholes,
each of which can contain a piece of information. Each cubbyhole has a unique
name, called its address
or location
. Typical memory
systems provide two primitive operations: one that fetches the data stored in a
specified location and one that assigns new data to a specified location.
Memory addresses can be incremented to support sequential access to some set of
the cubbyholes. More generally, many important data operations require that
memory addresses be treated as data, which can be stored in memory locations
and manipulated in machine registers. The representation of list structure is
one application of such address arithmetic
.
To model computer memory, we use a new kind of data structure called a
vector
. Abstractly, a vector is a compound data object whose
individual elements can be accessed by means of an integer index in an amount
of time that is independent of the index.
We could represent memory as
lists of items. However, the access time would then not be independent of the
index, since accessing the nth element of a list requires n - 1
cdr operations.
In order to describe memory operations, we use two
primitive Scheme procedures for manipulating vectors:
(vector-ref > <@var{n>)} returns the nth
element of the vector.
(vector-set! > <@var{n> )}
sets the nth element of the vector to the designated value.
For example, if v is a vector, then (vector-ref v 5) gets the
fifth entry in the vector v and (vector-set! v 5 7) changes the
value of the fifth entry of the vector v to 7.
For
completeness, we should specify a make-vector operation that constructs
vectors. However, in the present application we will use vectors only to model
fixed divisions of the computer memory.
For computer memory, this access can
be implemented through the use of address arithmetic to combine a base
address
that specifies the beginning location of a vector in memory with an
index
that specifies the offset of a particular element of the
vector.
Representing Lisp data
We can use vectors to implement the basic pair structures required for a
list-structured memory. Let us imagine that computer memory is divided into
two vectors: the-cars and the-cdrs . We will represent list
structure as follows: A pointer to a pair is an index into the two vectors.
The car of the pair is the entry in the-cars with the designated
index, and the cdr of the pair is the entry in the-cdrs with the
designated index. We also need a representation for objects other than pairs
(such as numbers and symbols) and a way to distinguish one kind of data from
another. There are many methods of accomplishing this, but they all reduce to
using typed pointers
, that is, to extending the notion of ``pointer''
to include information on data type.
This is precisely the same
``tagged data'' idea we introduced in Chapter 2 for dealing with generic
operations. Here, however, the data types are included at the primitive
machine level rather than constructed through the use of lists.
The data type
enables the system to distinguish a pointer to a pair (which consists of the
``pair'' data type and an index into the memory vectors) from pointers to other
kinds of data (which consist of some other data type and whatever is being used
to represent data of that type). Two data objects are considered to be the
same ( eq? ) if their pointers are identical.
Type information
may be encoded in a variety of ways, depending on the details of the machine on
which the Lisp system is to be implemented. The execution efficiency of Lisp
programs will be strongly dependent on how cleverly this choice is made, but it
is difficult to formulate general design rules for good choices. The most
straightforward way to implement typed pointers is to allocate a fixed set of
bits in each pointer to be a type field
that encodes the data type.
Important questions to be addressed in designing such a representation include
the following: How many type bits are required? How large must the vector
indices be? How efficiently can the primitive machine instructions be used to
manipulate the type fields of pointers? Machines that include special hardware
for the efficient handling of type fields are said to have tagged
architectures
.
Figure 5-14 illustrates the use of this method to
represent the list ((1 2) 3 4) , whose box-and-pointer diagram is also
shown. We use letter prefixes to denote the data-type information. Thus, a
pointer to the pair with index 5 is denoted p5 , the empty list is
denoted by the pointer e0 , and a pointer to the number 4 is denoted
n4 . In the box-and-pointer diagram, we have indicated at the lower left
of each pair the vector index that specifies where the car and
cdr of the pair are stored. The blank locations in the-cars and
the-cdrs may contain parts of other list structures (not of interest
here).
Figure 5.14: Box-and-pointer and memory-vector
representations of the list ((1 2) 3 4) .
A pointer to a number, such as n4 , might consist of a type indicating
numeric data together with the actual representation of the number
4.
This decision on the representation of numbers determines whether
eq? , which tests equality of pointers, can be used to test for equality
of numbers. If the pointer contains the number itself, then equal numbers will
have the same pointer. But if the pointer contains the index of a location
where the number is stored, equal numbers will be guaranteed to have equal
pointers only if we are careful never to store the same number in more than one
location.
To deal with numbers that are too large to be represented in the
fixed amount of space allocated for a single pointer, we could use a distinct
bignum
data type, for which the pointer designates a list in which
the parts of the number are stored.
This is just like writing a number
as a sequence of digits, except that each ``digit'' is a number between 0 and
the largest number that can be stored in a single pointer.
A symbol might be represented as a typed pointer that designates a sequence of
the characters that form the symbol's printed representation. This sequence is
constructed by the Lisp reader when the character string is initially
encountered in input. Since we want two instances of a symbol to be recognized
as the ``same'' symbol by eq? and we want eq? to be a simple test
for equality of pointers, we must ensure that if the reader sees the same
character string twice, it will use the same pointer (to the same sequence of
characters) to represent both occurrences. To accomplish this, the reader
maintains a table, traditionally called the obarray
, of all the
symbols it has ever encountered. When the reader encounters a character string
and is about to construct a symbol, it checks the obarray to see if it has ever
before seen the same character string. If it has not, it uses the characters
to construct a new symbol (a typed pointer to a new character sequence) and
enters this pointer in the obarray. If the reader has seen the string before,
it returns the symbol pointer stored in the obarray. This process of replacing
character strings by unique pointers is called interning
symbols.
Implementing the primitive list operations
Given the above representation scheme, we can replace each ``primitive'' list
operation of a register machine with one or more primitive vector operations.
We will use two registers, the-cars and the-cdrs , to identify the
memory vectors, and will assume that vector-ref and vector-set!
are available as primitive operations. We also assume that numeric operations
on pointers (such as incrementing a pointer, using a pair pointer to index a
vector, or adding two numbers) use only the index portion of the typed pointer.
For example, we can make a register machine support the instructions
Cons is performed by allocating an unused index and storing the
arguments to cons in the-cars and the-cdrs at that indexed
vector position. We presume that there is a special register, free ,
that always holds a pair pointer containing the next available index, and that
we can increment the index part of that pointer to find the next free
location.
There are other ways of finding free storage. For example,
we could link together all the unused pairs into a free list
. Our
free locations are consecutive (and hence can be accessed by incrementing a
pointer) because we are using a compacting garbage collector, as we will see in
section 5-3-2.
For example, the instruction
(assign (op cons) (reg ) (reg ))
is implemented as the following sequence of vector operations:
This is
essentially the implementation of cons in terms of set-car! and
set-cdr! , as described in section 3-3-1. The operation
get-new-pair used in that implementation is realized here by the
free pointer.
simply tests the equality of all fields in the registers, and predicates such
as pair? , null? , symbol? , and number? need only
check the type field.
Implementing stacks
Although our register machines use stacks, we need do nothing special here,
since stacks can be modeled in terms of lists. The stack can be a list of the
saved values, pointed to by a special register the-stack . Thus,
(save >) can be implemented as
and (perform (op initialize-stack)) can be implemented as
(assign the-stack (const ()))
These operations can be further expanded in terms of the vector operations
given above. In conventional computer architectures, however, it is usually
advantageous to allocate the stack as a separate vector. Then pushing and
popping the stack can be accomplished by incrementing or decrementing an index
into that vector.
Exercise 5.20: Draw the box-and-pointer
representation and the memory-vector representation (as in Figure 5-14)
of the list structure produced by
(define x (cons 1 2))
(define y (list x x))
with the free pointer initially p1 . What is the final value of
free ? What pointers represent the values of x and y ?
Exercise 5.21: Implement register machines for
the following procedures. Assume that the list-structure memory operations are
available as machine primitives.
(define (count-leaves tree)
(define (count-iter tree n)
(cond ((null? tree) n)
((not (pair? tree)) (+ n 1))
(else (count-iter (cdr tree)
(count-iter (car tree) n)))))
(count-iter tree 0))
Exercise 5.22: Exercise 3-12 of section
3-3-1 presented an append procedure that appends two lists to form
a new list and an append! procedure that splices two lists together.
Design a register machine to implement each of these procedures. Assume that
the list-structure memory operations are available as primitive operations.
Maintaining the Illusion of Infinite Memory
The representation method outlined in section 5-3-1 solves the problem of
implementing list structure, provided that we have an infinite amount of
memory. With a real computer we will eventually run out of free space in which
to construct new pairs.
This may not be true eventually, because
memories may get large enough so that it would be impossible to run out of free
memory in the lifetime of the computer. For example, there are about
3*(10^13), microseconds in a year, so if we were to cons once per
microsecond we would need about 10^15 cells of memory to build a machine that
could operate for 30 years without running out of memory. That much memory
seems absurdly large by today's standards, but it is not physically impossible.
On the other hand, processors are getting faster and a future computer may have
large numbers of processors operating in parallel on a single memory, so it may
be possible to use up memory much faster than we have postulated.
However,
most of the pairs generated in a typical computation are used only to hold
intermediate results. After these results are accessed, the pairs are no
longer needed---they are garbage
. For instance, the computation
constructs two lists: the enumeration and the result of filtering the
enumeration. When the accumulation is complete, these lists are no longer
needed, and the allocated memory can be reclaimed. If we can arrange to
collect all the garbage periodically, and if this turns out to recycle memory
at about the same rate at which we construct new pairs, we will have preserved
the illusion that there is an infinite amount of memory.
In order to recycle pairs, we must have a way to determine which allocated
pairs are not needed (in the sense that their contents can no longer influence
the future of the computation). The method we shall examine for accomplishing
this is known as garbage collection
. Garbage collection is based on
the observation that, at any moment in a Lisp interpretation, the only objects
that can affect the future of the computation are those that can be reached by
some succession of car and cdr operations starting from the
pointers that are currently in the machine registers.
We assume here
that the stack is represented as a list as described in section 5-3-1, so
that items on the stack are accessible via the pointer in the stack register.
Any memory cell that is not so accessible may be recycled.
 The method we shall examine
here is called stop-and-copy
. The basic idea is to divide memory
into two halves: ``working memory'' and ``free memory.'' When cons
constructs pairs, it allocates these in working memory. When working memory is
full, we perform garbage collection by locating all the useful pairs in working
memory and copying these into consecutive locations in free memory. (The
useful pairs are located by tracing all the car and cdr pointers,
starting with the machine registers.) Since we do not copy the garbage, there
will presumably be additional free memory that we can use to allocate new
pairs. In addition, nothing in the working memory is needed, since all the
useful pairs in it have been copied. Thus, if we interchange the roles of
working memory and free memory, we can continue processing; new pairs will be
allocated in the new working memory (which was the old free memory). When this
is full, we can copy the useful pairs into the new free memory (which was the
old working memory).
This idea was invented and first implemented by
Minsky, as part of the implementation of Lisp for the PDP-1 at the
@acronym{MIT
Research Laboratory of Electronics. It was further developed by
Fenichel and Yochelson (1969) for use in the Lisp implementation for the
Multics time-sharing system. Later, Baker (1978) developed a ``real-time''
version of the method, which does not require the computation to stop during
garbage collection. Baker's idea was extended by Hewitt, Lieberman, and Moon
(see Lieberman and Hewitt 1983) to take advantage of the fact that some
structure is more volatile and other structure is more permanent.
An alternative commonly used garbage-collection technique is the
mark-sweep
method. This consists of tracing all the structure
accessible from the machine registers and marking each pair we reach. We then
scan all of memory, and any location that is unmarked is ``swept up'' as
garbage and made available for reuse. A full discussion of the mark-sweep
method can be found in Allen 1978.
The Minsky-Fenichel-Yochelson algorithm is the dominant algorithm in use for
large-memory systems because it examines only the useful part of memory. This
is in contrast to mark-sweep, in which the sweep phase must check all of
memory.  That is, at the end of the
garbage-collection phase the useful data will have been moved to consecutive
memory locations, with all garbage pairs compressed out. This can be an
extremely important performance consideration in machines with virtual memory,
in which accesses to widely separated memory addresses may require extra paging
operations.}
Implementation of a stop-and-copy garbage collector
We now use our register-machine language to describe the stop-and-copy
algorithm in more detail. We will assume that there is a register called
root that contains a pointer to a structure that eventually points at
all accessible data. This can be arranged by storing the contents of all the
machine registers in a pre-allocated list pointed at by root just before
starting garbage collection.
This list of registers does not include
the registers used by the storage-allocation system--- root ,
the-cars , the-cdrs , and the other registers that will be
introduced in this section.
We also assume that, in addition to the current