We use a special printing procedure, user-print , to avoid printing the
environment part of a compound procedure, which may be a very long list (or may
even contain cycles).
Now all we need to do to run the evaluator is to initialize the global
environment and start the driver loop. Here is a sample interaction:
(define the-global-environment (setup-environment))
(driver-loop)
;;; M-Eval input:
(define (append x y)
(if (null? x)
y
(cons (car x)
(append (cdr x) y))))
;;; M-Eval value:
ok
;;; M-Eval input:
(append '(a b c) '(d e f))
;;; M-Eval value:
(a b c d e f)
Exercise 4.14: Eva Lu Ator and Louis Reasoner
are each experimenting with the metacircular evaluator. Eva types in the
definition of map , and runs some test programs that use it. They work
fine. Louis, in contrast, has installed the system version of map as a
primitive for the metacircular evaluator. When he tries it, things go terribly
wrong. Explain why Louis's map fails even though Eva's works.
Data as Programs
In thinking about a Lisp program that evaluates Lisp expressions, an analogy
might be helpful. One operational view of the meaning of a program is that a
program is a description of an abstract (perhaps infinitely large) machine.
For example, consider the familiar program to compute factorials:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
We may regard this program as the description of a machine containing parts
that decrement, multiply, and test for equality, together with a two-position
switch and another factorial machine. (The factorial machine is infinite
because it contains another factorial machine within it.) Figure 4-2 is
a flow diagram for the factorial machine, showing how the parts are wired
together.
Figure 4.2: The factorial program, viewed as an
abstract machine.
In a similar way, we can regard the evaluator as a very special machine that
takes as input a description of a machine. Given this input, the evaluator
configures itself to emulate the machine described. For example, if we feed
our evaluator the definition of factorial , as shown in Figure 4-3,
the evaluator will be able to compute factorials.
Figure 4.3: The evaluator emulating a factorial
machine.
From this perspective, our evaluator is seen to be a universal
machine
. It mimics other machines when these are described as Lisp
programs.
The fact that the machines are described in Lisp is
inessential. If we give our evaluator a Lisp program that behaves as an
evaluator for some other language, say C, the Lisp evaluator will emulate the C
evaluator, which in turn can emulate any machine described as a C program.
Similarly, writing a Lisp evaluator in C produces a C program that can execute
any Lisp program. The deep idea here is that any evaluator can emulate any
other. Thus, the notion of ``what can in principle be computed'' (ignoring
practicalities of time and memory required) is independent of the language or
the computer, and instead reflects an underlying notion of
computability
. This was first demonstrated in a clear way by Alan
M. Turing (1912-1954), whose 1936 paper laid the foundations for theoretical
computer science. In the paper, Turing presented a simple computational
model---now known as a Turing machine
---and argued that any
``effective process'' can be formulated as a program for such a machine. (This
argument is known as the Church-Turing thesis
.) Turing then
implemented a universal machine, i.e., a Turing machine that behaves as an
evaluator for Turing-machine programs. He used this framework to demonstrate
that there are well-posed problems that cannot be computed by Turing machines
(see Exercise 4-15), and so by implication cannot be formulated as
``effective processes.'' Turing went on to make fundamental contributions to
practical computer science as well. For example, he invented the idea of
structuring programs using general-purpose subroutines. See Hodges 1983 for a
biography of Turing.
This is striking. Try to imagine an analogous evaluator
for electrical circuits. This would be a circuit that takes as input a signal
encoding the plans for some other circuit, such as a filter. Given this input,
the circuit evaluator would then behave like a filter with the same
description. Such a universal electrical circuit is almost unimaginably
complex. It is remarkable that the program evaluator is a rather simple
program.
Some people find it counterintuitive that an evaluator, which
is implemented by a relatively simple procedure, can emulate programs that are
more complex than the evaluator itself. The existence of a universal evaluator
machine is a deep and wonderful property of computation. Recursion
theory
, a branch of mathematical logic, is concerned with logical limits of
computation. Douglas Hofstadter's beautiful book @cite{G@"odel, Escher, Bach
(1979) explores some of these ideas.}
Another striking aspect of the evaluator is that it acts as a bridge between
the data objects that are manipulated by our programming language and the
programming language itself. Imagine that the evaluator program (implemented
in Lisp) is running, and that a user is typing expressions to the evaluator and
observing the results. From the perspective of the user, an input expression
such as (* x x) is an expression in the programming language, which the
evaluator should execute. From the perspective of the evaluator, however, the
expression is simply a list (in this case, a list of three symbols: * ,
x , and x ) that is to be manipulated according to a well-defined
set of rules.
That the user's programs are the evaluator's data need not be a source of
confusion. In fact, it is sometimes convenient to ignore this distinction, and
to give the user the ability to explicitly evaluate a data object as a Lisp
expression, by making eval available for use in programs. Many Lisp
dialects provide a primitive eval procedure that takes as arguments an
expression and an environment and evaluates the expression relative to the
environment.
Warning: This eval primitive is not identical to
the eval procedure we implemented in section 4-1-1, because it
uses actual Scheme environments rather than the sample environment
structures we built in section 4-1-3. These actual environments cannot
be manipulated by the user as ordinary lists; they must be accessed via
eval or other special operations. Similarly, the apply primitive
we saw earlier is not identical to the metacircular apply , because it
uses actual Scheme procedures rather than the procedure objects we constructed
in sections 4-1-3 and 4-1-4.
implementation of Scheme
includes eval , as well as a symbol user-initial-environment that
is bound to the initial environment in which the user's input expressions are
evaluated.}
Exercise 4.15: Given a one-argument procedure
p and an object a , p is said to ``halt'' on a if
evaluating the expression (p a) returns a value (as opposed to
terminating with an error message or running forever). Show that it is
impossible to write a procedure halts? that correctly determines whether
p halts on a for any procedure p and object a . Use
the following reasoning: If you had such a procedure halts? , you could
implement the following program:
Now consider evaluating the expression (try try) and show that any
possible outcome (either halting or running forever) violates the intended
behavior of halts? .
Although we stipulated that halts?
is given a procedure object, notice that this reasoning still applies even if
halts? can gain access to the procedure's text and its environment.
This is Turing's celebrated Halting Theorem
, which gave the first
clear example of a non-computable
problem, i.e., a well-posed task
that cannot be carried out as a computational procedure.
Internal Definitions
Our environment model of evaluation and our metacircular evaluator execute
definitions in sequence, extending the environment frame one definition at a
time. This is particularly convenient for interactive program development, in
which the programmer needs to freely mix the application of procedures with the
definition of new procedures. However, if we think carefully about the
internal definitions used to implement block structure (introduced in section
1-1-8), we will find that name-by-name extension of the environment may
not be the best way to define local variables.
Consider a procedure with internal definitions, such as
(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
f >)
Our intention here is that the name odd? in the body of the procedure
even? should refer to the procedure odd? that is defined after
even? . The scope of the name odd? is the entire body of
f , not just the portion of the body of f starting at the point
where the define for odd? occurs. Indeed, when we consider that
odd? is itself defined in terms of even? ---so that even?
and odd? are mutually recursive procedures---we see that the only
satisfactory interpretation of the two define s is to regard them as if
the names even? and odd? were being added to the environment
simultaneously. More generally, in block structure, the scope of a local name
is the entire procedure body in which the define is evaluated.
As it happens, our interpreter will evaluate calls to f correctly, but
for an ``accidental'' reason: Since the definitions of the internal procedures
come first, no calls to these procedures will be evaluated until all of them
have been defined. Hence, odd? will have been defined by the time
even? is executed. In fact, our sequential evaluation mechanism will
give the same result as a mechanism that directly implements simultaneous
definition for any procedure in which the internal definitions come first in a
body and evaluation of the value expressions for the defined variables doesn't
actually use any of the defined variables. (For an example of a procedure that
doesn't obey these restrictions, so that sequential definition isn't equivalent
to simultaneous definition, see Exercise 4-19.)
Wanting programs
to not depend on this evaluation mechanism is the reason for the ``management
is not responsible'' remark in Footnote 28 of Chapter 1. By
insisting that internal definitions come first and do not use each other while
the definitions are being evaluated, the @acronym{IEEE
standard for Scheme
leaves implementors some choice in the mechanism used to evaluate these
definitions. The choice of one evaluation rule rather than another here may
seem like a small issue, affecting only the interpretation of ``badly formed''
programs. However, we will see in section 5-5-6 that moving to a model
of simultaneous scoping for internal definitions avoids some nasty difficulties
that would otherwise arise in implementing a compiler.}
There is, however, a simple way to treat definitions so that internally defined
names have truly simultaneous scope---just create all local variables that will
be in the current environment before evaluating any of the value expressions.
One way to do this is by a syntax transformation on lambda expressions.
Before evaluating the body of a lambda expression, we ``scan out'' and
eliminate all the internal definitions in the body. The internally defined
variables will be created with a let and then set to their values by
assignment. For example, the procedure
(lambda
(define u )
(define v )
)
would be transformed into
(lambda
(let ((u '*unassigned*)
(v '*unassigned*))
(set! u )
(set! v )
))
where *unassigned* is a special symbol that causes looking up a variable
to signal an error if an attempt is made to use the value of the
not-yet-assigned variable.
An alternative strategy for scanning out internal definitions is shown in
Exercise 4-18. Unlike the transformation shown above, this enforces the
restriction that the defined variables' values can be evaluated without using
any of the variables' values.
The @acronym{IEEE
standard for Scheme
allows for different implementation strategies by specifying that it is up to
the programmer to obey this restriction, not up to the implementation to
enforce it. Some Scheme implementations, including @acronym{MIT} Scheme, use
the transformation shown above. Thus, some programs that don't obey this
restriction will in fact run in such implementations.}
Exercise 4.16: In this exercise we implement the
method just described for interpreting internal definitions. We assume that
the evaluator supports let (see Exercise 4-6).
Change lookup-variable-value (section 4-1-3) to signal an error if
the value it finds is the symbol *unassigned* .
Write a procedure scan-out-defines that takes a procedure body and
returns an equivalent one that has no internal definitions, by making the
transformation described above.
Install scan-out-defines in the interpreter, either in
make-procedure or in procedure-body (see section 4-1-3).
Which place is better? Why?
Exercise 4.17: Draw diagrams of the environment
in effect when evaluating the expression in the procedure in the
text, comparing how this will be structured when definitions are interpreted
sequentially with how it will be structured if definitions are scanned out as
described. Why is there an extra frame in the transformed program? Explain
why this difference in environment structure can never make a difference in the
behavior of a correct program. Design a way to make the interpreter implement
the ``simultaneous'' scope rule for internal definitions without constructing
the extra frame.
Exercise 4.18: Consider an alternative strategy
for scanning out definitions that translates the example in the text to
(lambda
(let ((u '*unassigned*)
(v '*unassigned*))
(let ((a )
(b ))
(set! u a)
(set! v b))
))
Here a and b are meant to represent new variable names, created
by the interpreter, that do not appear in the user's program. Consider the
solve procedure from section 3-5-4:
(define (solve f y0 dt)
(define y (integral (delay dy) y0 dt))
(define dy (stream-map f y))
y)
Will this procedure work if internal definitions are scanned out as shown in
this exercise? What if they are scanned out as shown in the text? Explain.
Exercise 4.19: Ben Bitdiddle, Alyssa P. Hacker,
and Eva Lu Ator are arguing about the desired result of evaluating the
expression
(let ((a 1))
(define (f x)
(define b (+ a x))
(define a 5)
(+ a b))
(f 10))
Ben asserts that the result should be obtained using the sequential rule for
define : b is defined to be 11, then a is defined to be 5,
so the result is 16. Alyssa objects that mutual recursion requires the
simultaneous scope rule for internal procedure definitions, and that it is
unreasonable to treat procedure names differently from other names. Thus, she
argues for the mechanism implemented in Exercise 4-16. This would lead
to a being unassigned at the time that the value for b is to be
computed. Hence, in Alyssa's view the procedure should produce an error. Eva
has a third opinion. She says that if the definitions of a and b
are truly meant to be simultaneous, then the value 5 for a should be
used in evaluating b . Hence, in Eva's view a should be 5,
b should be 15, and the result should be 20. Which (if any) of these
viewpoints do you support? Can you devise a way to implement internal
definitions so that they behave as Eva prefers?
The @acronym{MIT
implementors of Scheme support Alyssa on the following grounds: Eva is in
principle correct -- the definitions should be regarded as simultaneous. But
it seems difficult to implement a general, efficient mechanism that does what
Eva requires. In the absence of such a mechanism, it is better to generate an
error in the difficult cases of simultaneous definitions (Alyssa's notion) than
to produce an incorrect answer (as Ben would have it).}
Exercise 4.20: Because internal definitions look
sequential but are actually simultaneous, some people prefer to avoid them
entirely, and use the special form letrec instead. Letrec looks
like let , so it is not surprising that the variables it binds are bound
simultaneously and have the same scope as each other. The sample procedure
f above can be written without internal definitions, but with exactly
the same meaning, as
(define (f x)
(letrec ((even?
(lambda (n)
(if (= n 0)
true
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (= n 0)
false
(even? (- n 1))))))
f >))
Letrec expressions, which have the form
(letrec (() ... ())
)
are a variation on let in which the expressions
that provide the initial values for the
variables are evaluated in an environment
that includes all the letrec bindings. This permits recursion in the
bindings, such as the mutual recursion of even? and odd? in the
example above, or the evaluation of 10 factorial with
(letrec ((fact
(lambda (n)
(if (= n 1)
1
(* n (fact (- n 1)))))))
(fact 10))
Implement letrec as a derived expression, by transforming a
letrec expression into a let expression as shown in the text
above or in Exercise 4-18. That is, the letrec variables should
be created with a let and then be assigned their values with
set! .
Louis Reasoner is confused by all this fuss about internal definitions. The
way he sees it, if you don't like to use define inside a procedure, you
can just use let . Illustrate what is loose about his reasoning by
drawing an environment diagram that shows the environment in which the
f > is evaluated during evaluation of the
expression (f 5) , with f defined as in this exercise. Draw an
environment diagram for the same evaluation, but with let in place of
letrec in the definition of f .
Exercise 4.21: Amazingly, Louis's intuition in
Exercise 4-20 is correct. It is indeed possible to specify recursive
procedures without using letrec (or even define ), although the
method for accomplishing this is much more subtle than Louis imagined. The
following expression computes 10 factorial by applying a recursive factorial
procedure:
This example illustrates a programming trick for
formulating recursive procedures without using define . The most general
trick of this sort is the Y operator
, which can be used to give a
``pure [lambda]-calculus'' implementation of recursion. (See Stoy 1977 for
details on the [lambda] calculus, and Gabriel 1988 for an exposition of the
Y operator in Scheme.)
((lambda (n)
((lambda (fact)
(fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)
Check (by evaluating the expression) that this really does compute factorials.
Devise an analogous expression for computing Fibonacci numbers.
Consider the following procedure, which includes mutually recursive internal
definitions:
(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
(even? x))
Fill in the missing expressions to complete an alternative definition of
f , which uses neither internal definitions nor letrec :
The evaluator implemented above is simple, but it is very inefficient, because
the syntactic analysis of expressions is interleaved with their execution.
Thus if a program is executed many times, its syntax is analyzed many times.
Consider, for example, evaluating (factorial 4) using the following
definition of factorial :
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
Each time factorial is called, the evaluator must determine that the
body is an if expression and extract the predicate. Only then can it
evaluate the predicate and dispatch on its value. Each time it evaluates the
expression (* (factorial (- n 1)) n) , or the subexpressions
(factorial (- n 1)) and (- n 1) , the evaluator must perform the
case analysis in eval to determine that the expression is an
application, and must extract its operator and operands. This analysis is
expensive. Performing it repeatedly is wasteful.
We can transform the evaluator to be significantly more efficient by arranging
things so that syntactic analysis is performed only once.
This
technique is an integral part of the compilation process, which we shall
discuss in Chapter 5. Jonathan Rees wrote a Scheme interpreter like this
in about 1982 for the T project (Rees and Adams 1982). Marc Feeley (1986) (see
also Feeley and Lapalme 1987) independently invented this technique in his
master's thesis.
We split eval , which takes an expression and an
environment, into two parts. The procedure analyze takes only the
expression. It performs the syntactic analysis and returns a new procedure,
the execution procedure
, that encapsulates the work to be done in
executing the analyzed expression. The execution procedure takes an
environment as its argument and completes the evaluation. This saves work
because analyze will be called only once on an expression, while the
execution procedure may be called many times.
With the separation into analysis and execution, eval now becomes
(define (eval exp env)
((analyze exp) env))
The result of calling analyze is the execution procedure to be applied
to the environment. The analyze procedure is the same case analysis as
performed by the original eval of section 4-1-1, except that the
procedures to which we dispatch perform only analysis, not full evaluation:
Here is the simplest syntactic analysis procedure, which handles
self-evaluating expressions. It returns an execution procedure that ignores
its environment argument and just returns the expression:
For a quoted expression, we can gain a little efficiency by extracting the text
of the quotation only once, in the analysis phase, rather than in the execution
phase.
Looking up a variable value must still be done in the execution phase, since
this depends upon knowing the environment.
There is, however, an
important part of the variable search that can be done as part of the
syntactic analysis. As we will show in section 5-5-6, one can determine
the position in the environment structure where the value of the variable will
be found, thus obviating the need to scan the environment for the entry that
matches the variable.
Analyze-assignment also must defer actually setting the variable until
the execution, when the environment has been supplied. However, the fact that
the assignment-value expression can be analyzed (recursively) during
analysis is a major gain in efficiency, because the assignment-value
expression will now be analyzed only once. The same holds true for
definitions.
Analyzing a lambda expression also achieves a major gain in efficiency:
We analyze the lambda body only once, even though procedures resulting
from evaluation of the lambda may be applied many times.
Analysis of a sequence of expressions (as in a begin or the body of a
lambda expression) is more involved.
See Exercise 4-23
for some insight into the processing of sequences.
Each expression in the
sequence is analyzed, yielding an execution procedure. These execution
procedures are combined to produce an execution procedure that takes an
environment as argument and sequentially calls each individual execution
procedure with the environment as argument.
To analyze an application, we analyze the operator and operands and construct
an execution procedure that calls the operator execution procedure (to obtain
the actual procedure to be applied) and the operand execution procedures (to
obtain the actual arguments). We then pass these to
execute-application , which is the analog of apply in section
4-1-1. Execute-application differs from apply in that the
procedure body for a compound procedure has already been analyzed, so there is
no need to do further analysis. Instead, we just call the execution procedure
for the body on the extended environment.
Our new evaluator uses the same data structures, syntax procedures, and
run-time support procedures as in sections 4-1-2, 4-1-3, and
4-1-4.
Exercise 4.22: Extend the evaluator in this
section to support the special form let . (See Exercise 4-6.)
Exercise 4.23: Alyssa P. Hacker doesn't
understand why analyze-sequence needs to be so complicated. All the
other analysis procedures are straightforward transformations of the
corresponding evaluation procedures (or eval clauses) in section
4-1-1. She expected analyze-sequence to look like this:
Eva Lu Ator explains to Alyssa that the version in the text does more of the
work of evaluating a sequence at analysis time. Alyssa's sequence-execution
procedure, rather than having the calls to the individual execution procedures
built in, loops through the procedures in order to call them: In effect,
although the individual expressions in the sequence have been analyzed, the
sequence itself has not been.
Compare the two versions of analyze-sequence . For example, consider the
common case (typical of procedure bodies) where the sequence has just one
expression. What work will the execution procedure produced by Alyssa's
program do? What about the execution procedure produced by the program in the
text above? How do the two versions compare for a sequence with two
expressions?
Exercise 4.24: Design and carry out some
experiments to compare the speed of the original metacircular evaluator with
the version in this section. Use your results to estimate the fraction of time
that is spent in analysis versus execution for various procedures.
Variations on a Scheme -- Lazy Evaluation
Now that we have an evaluator expressed as a Lisp program, we can experiment
with alternative choices in language design simply by modifying the evaluator.
Indeed, new languages are often invented by first writing an evaluator that
embeds the new language within an existing high-level language. For example,
if we wish to discuss some aspect of a proposed modification to Lisp with
another member of the Lisp community, we can supply an evaluator that embodies
the change. The recipient can then experiment with the new evaluator and send
back comments as further modifications. Not only does the high-level
implementation base make it easier to test and debug the evaluator; in
addition, the embedding enables the designer to snarf
Snarf: ``To
grab, especially a large document or file for the purpose of using it either
with or without the owner's permission.'' Snarf down: ``To snarf, sometimes
with the connotation of absorbing, processing, or understanding.'' (These
definitions were snarfed from Steele et al. 1983. See also Raymond 1993.)
features from the underlying language, just as our embedded Lisp evaluator uses
primitives and control structure from the underlying Lisp. Only later (if
ever) need the designer go to the trouble of building a complete implementation
in a low-level language or in hardware. In this section and the next we
explore some variations on Scheme that provide significant additional
expressive power.
@menu
* 4-2-1:: Normal Order and Applicative Order
* 4-2-2:: An Interpreter with Lazy Evaluation
* 4-2-3:: Streams as Lazy Lists
@end menu
Normal Order and Applicative Order
In section 1-1, where we began our discussion of models of evaluation, we
noted that Scheme is an applicative-order
language, namely, that all
the arguments to Scheme procedures are evaluated when the procedure is applied.
In contrast, normal-order
languages delay evaluation of procedure
arguments until the actual argument values are needed. Delaying evaluation of
procedure arguments until the last possible moment (e.g., until they are
required by a primitive operation) is called lazy
evaluation
.
The difference between the ``lazy'' terminology and the
``normal-order'' terminology is somewhat fuzzy. Generally, ``lazy'' refers to
the mechanisms of particular evaluators, while ``normal-order'' refers to the
semantics of languages, independent of any particular evaluation strategy. But
this is not a hard-and-fast distinction, and the two terminologies are often
used interchangeably.
Consider the procedure
(define (try a b)
(if (= a 0) 1 b))
Evaluating (try 0 (/ 1 0)) generates an error in Scheme. With lazy
evaluation, there would be no error. Evaluating the expression would return 1,
because the argument (/ 1 0) would never be evaluated.
An example that exploits lazy evaluation is the definition of a procedure
unless
(unless (= b 0)
(/ a b)
(begin (display "exception: returning 0")
0))
This won't work in an applicative-order language because both the usual value
and the exceptional value will be evaluated before unless is called
(compare Exercise 1-6). An advantage of lazy evaluation is that some
procedures, such as unless , can do useful computation even if evaluation
of some of their arguments would produce errors or would not terminate.
If the body of a procedure is entered before an argument has been evaluated we
say that the procedure is non-strict
in that argument. If the
argument is evaluated before the body of the procedure is entered we say that
the procedure is strict
in that argument.
The ``strict''
versus ``non-strict'' terminology means essentially the same thing as
``applicative-order'' versus ``normal-order,'' except that it refers to
individual procedures and arguments rather than to the language as a whole. At
a conference on programming languages you might hear someone say, ``The
normal-order language Hassle has certain strict primitives. Other procedures
take their arguments by lazy evaluation.''
In a purely applicative-order
language, all procedures are strict in each argument. In a purely normal-order
language, all compound procedures are non-strict in each argument, and
primitive procedures may be either strict or non-strict. There are also
languages (see Exercise 4-31) that give programmers detailed control over
the strictness of the procedures they define.
A striking example of a procedure that can usefully be made non-strict is
cons (or, in general, almost any constructor for data structures). One
can do useful computation, combining elements to form data structures and
operating on the resulting data structures, even if the values of the elements
are not known. It makes perfect sense, for instance, to compute the length of
a list without knowing the values of the individual elements in the list. We
will exploit this idea in section 4-2-3 to implement the streams of
Chapter 3 as lists formed of non-strict cons pairs.
Exercise 4.25: Suppose that (in ordinary
applicative-order Scheme) we define unless as shown above and then
define factorial in terms of unless as
(define (factorial n)
(unless (= n 1)
(* n (factorial (- n 1)))
1))
What happens if we attempt to evaluate (factorial 5) ? Will our
definitions work in a normal-order language?
Exercise 4.26: Ben Bitdiddle and Alyssa
P. Hacker disagree over the importance of lazy evaluation for implementing
things such as unless . Ben points out that it's possible to implement
unless in applicative order as a special form. Alyssa counters that, if
one did that, unless would be merely syntax, not a procedure that could
be used in conjunction with higher-order procedures. Fill in the details on
both sides of the argument. Show how to implement unless as a derived
expression (like cond or let ), and give an example of a situation
where it might be useful to have unless available as a procedure, rather
than as a special form.
An Interpreter with Lazy Evaluation
In this section we will implement a normal-order language that is the same as
Scheme except that compound procedures are non-strict in each argument.
Primitive procedures will still be strict. It is not difficult to modify the
evaluator of section 4-1-1 so that the language it interprets behaves
this way. Almost all the required changes center around procedure application.
The basic idea is that, when applying a procedure, the interpreter must
determine which arguments are to be evaluated and which are to be delayed. The
delayed arguments are not evaluated; instead, they are transformed into objects
called thunks
.
The word thunk
was invented by an
informal working group that was discussing the implementation of call-by-name
in Algol 60. They observed that most of the analysis of (``thinking about'')
the expression could be done at compile time; thus, at run time, the expression
would already have been ``thunk'' about (Ingerman et al. 1960).
The thunk must
contain the information required to produce the value of the argument when it
is needed, as if it had been evaluated at the time of the application. Thus,
the thunk must contain the argument expression and the environment in which the
procedure application is being evaluated.
The process of evaluating the expression in a thunk is called
forcing
.
This is analogous to the use of force on the
delayed objects that were introduced in Chapter 3 to represent streams.
The critical difference between what we are doing here and what we did in
Chapter 3 is that we are building delaying and forcing into the
evaluator, and thus making this uniform and automatic throughout the language.
In general, a thunk will be forced only when its value is needed: when it is
passed to a primitive procedure that will use the value of the thunk; when it
is the value of a predicate of a conditional; and when it is the value of an
operator that is about to be applied as a procedure. One design choice we have
available is whether or not to memoize
thunks, as we did with delayed
objects in section 3-5-1. With memoization, the first time a thunk is
forced, it stores the value that is computed. Subsequent forcings simply
return the stored value without repeating the computation. We'll make our
interpreter memoize, because this is more efficient for many applications.
There are tricky considerations here, however.
Lazy evaluation
combined with memoization is sometimes referred to as call-by-need
argument passing, in contrast to call-by-name
argument passing.
(Call-by-name, introduced in Algol 60, is similar to non-memoized lazy
evaluation.) As language designers, we can build our evaluator to memoize, not
to memoize, or leave this an option for programmers (Exercise 4-31). As
you might expect from Chapter 3, these choices raise issues that become
both subtle and confusing in the presence of assignments. (See Exercise
4-27 and Exercise 4-29.) An excellent article by Clinger (1982)
attempts to clarify the multiple dimensions of confusion that arise here.
Modifying the evaluator
The main difference between the lazy evaluator and the one in section 4-1
is in the handling of procedure applications in eval and apply .
The application? clause of eval becomes
This is almost the same as the application? clause of eval in
section 4-1-1. For lazy evaluation, however, we call apply with
the operand expressions, rather than the arguments produced by evaluating them.
Since we will need the environment to construct thunks if the arguments are to
be delayed, we must pass this as well. We still evaluate the operator, because
apply needs the actual procedure to be applied in order to dispatch on
its type (primitive versus compound) and apply it.
Whenever we need the actual value of an expression, we use
instead of just eval , so that if the expression's value is a thunk, it
will be forced.
Our new version of apply is also almost the same as the version in
section 4-1-1. The difference is that eval has passed in
unevaluated operand expressions: For primitive procedures (which are strict),
we evaluate all the arguments before applying the primitive; for compound
procedures (which are non-strict) we delay all the arguments before applying
the procedure.
The procedures that process the arguments are just like list-of-values
from section 4-1-1, except that list-of-delayed-args delays the
arguments instead of evaluating them, and list-of-arg-values uses
actual-value instead of eval :
The other place we must change the evaluator is in the handling of if ,
where we must use actual-value instead of eval to get the value
of the predicate expression before testing whether it is true or false:
Finally, we must change the driver-loop procedure (section 4-1-4)
to use actual-value instead of eval , so that if a delayed value
is propagated back to the read-eval-print loop, it will be forced before being
printed. We also change the prompts to indicate that this is the lazy
evaluator:
With these changes made, we can start the evaluator and test it. The
successful evaluation of the try expression discussed in section
4-2-1 indicates that the interpreter is performing lazy evaluation:
(define the-global-environment (setup-environment))
(driver-loop)
;;; L-Eval input:
(define (try a b)
(if (= a 0) 1 b))
;;; L-Eval value:
ok
;;; L-Eval input:
(try 0 (/ 1 0))
;;; L-Eval value:
1
Representing thunks
Our evaluator must arrange to create thunks when procedures are applied to
arguments and to force these thunks later. A thunk must package an expression
together with the environment, so that the argument can be produced later. To
force the thunk, we simply extract the expression and environment from the
thunk and evaluate the expression in the environment. We use
actual-value rather than eval so that in case the value of the
expression is itself a thunk, we will force that, and so on, until we reach
something that is not a thunk:
One easy way to package an expression with an environment is to make a list
containing the expression and the environment. Thus, we create a thunk as
follows:
Actually, what we want for our interpreter is not quite this, but rather thunks
that have been memoized. When a thunk is forced, we will turn it into an
evaluated thunk by replacing the stored expression with its value and changing
the thunk tag so that it can be recognized as already
evaluated.
Notice that we also erase the env from the thunk
once the expression's value has been computed. This makes no difference in the
values returned by the interpreter. It does help save space, however, because
removing the reference from the thunk to the env once it is no longer
needed allows this structure to be garbage-collected
and its space
recycled, as we will discuss in section 5-3.
Similarly, we could have allowed unneeded environments in the memoized delayed
objects of section 3-5-1 to be garbage-collected, by having
memo-proc do something like (set! proc '()) to discard the
procedure proc (which includes the environment in which the delay
was evaluated) after storing its value.
Give the missing values in the following sequence of interactions, and explain
your answers.
This exercise demonstrates that the interaction between
lazy evaluation and side effects can be very confusing. This is just what you
might expect from the discussion in Chapter 3.
(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
;;; L-Eval input:
w
;;; L-Eval value:
;;; L-Eval input:
count
;;; L-Eval value:
Exercise 4.28: Eval uses
actual-value rather than eval to evaluate the operator before
passing it to apply , in order to force the value of the operator. Give
an example that demonstrates the need for this forcing.
Exercise 4.29: Exhibit a program that you would
expect to run much more slowly without memoization than with memoization.
Also, consider the following interaction, where the id procedure is
defined as in Exercise 4-27 and count starts at 0:
Give the responses both when the evaluator memoizes and when it does not.
Exercise 4.30: Cy D. Fect, a reformed C
programmer, is worried that some side effects may never take place, because the
lazy evaluator doesn't force the expressions in a sequence. Since the value of
an expression in a sequence other than the last one is not used (the expression
is there only for its effect, such as assigning to a variable or printing),
there can be no subsequent use of this value (e.g., as an argument to a
primitive procedure) that will cause it to be forced. Cy thus thinks that when
evaluating sequences, we must force all expressions in the sequence except the
final one. He proposes to modify eval-sequence from section 4-1-1
to use actual-value rather than eval :
Ben Bitdiddle thinks Cy is wrong. He shows Cy the for-each procedure
described in Exercise 2-23, which gives an important example of a
sequence with side effects:
Explain why Ben is right about the behavior of for-each .
Cy agrees that Ben is right about the for-each example, but says that
that's not the kind of program he was thinking about when he proposed his
change to eval-sequence . He defines the following two procedures in the
lazy evaluator:
(define (p1 x)
(set! x (cons x '(2)))
x)
(define (p2 x)
(define (p e)
e
x)
(p (set! x (cons x '(2)))))
What are the values of (p1 1) and (p2 1) with the original
eval-sequence ? What would the values be with Cy's proposed change to
eval-sequence ?
Cy also points out that changing eval-sequence as he proposes does not
affect the behavior of the example in part a. Explain why this is true.
How do you think sequences ought to be treated in the lazy evaluator? Do you
like Cy's approach, the approach in the text, or some other approach?
Exercise 4.31: The approach taken in this
section is somewhat unpleasant, because it makes an incompatible change to
Scheme. It might be nicer to implement lazy evaluation as an
upward-compatible extension
, that is, so that ordinary Scheme
programs will work as before. We can do this by extending the syntax of
procedure declarations to let the user control whether or not arguments are to
be delayed. While we're at it, we may as well also give the user the choice
between delaying with and without memoization. For example, the definition
(define (f a (b lazy) c (d lazy-memo))
...)
would define f to be a procedure of four arguments, where the first and
third arguments are evaluated when the procedure is called, the second argument
is delayed, and the fourth argument is both delayed and memoized. Thus,
ordinary procedure definitions will produce the same behavior as ordinary
Scheme, while adding the lazy-memo declaration to each parameter of
every compound procedure will produce the behavior of the lazy evaluator
defined in this section. Design and implement the changes required to produce
such an extension to Scheme. You will have to implement new syntax procedures
to handle the new syntax for define . You must also arrange for
eval or apply to determine when arguments are to be delayed, and
to force or delay arguments accordingly, and you must arrange for forcing to
memoize or not, as appropriate.
Streams as Lazy Lists
In section 3-5-1, we showed how to implement streams as delayed lists.
We introduced special forms delay and cons-stream , which allowed
us to construct a ``promise'' to compute the cdr of a stream, without
actually fulfilling that promise until later. We could use this general
technique of introducing special forms whenever we need more control over the
evaluation process, but this is awkward. For one thing, a special form is not
a first-class object like a procedure, so we cannot use it together with
higher-order procedures.
This is precisely the issue with the
unless procedure, as in Exercise 4-26.
Additionally, we were
forced to create streams as a new kind of data object similar but not identical
to lists, and this required us to reimplement many ordinary list operations
( map , append , and so on) for use with streams.
With lazy evaluation, streams and lists can be identical, so there is no need
for special forms or for separate list and stream operations. All we need to
do is to arrange matters so that cons is non-strict. One way to
accomplish this is to extend the lazy evaluator to allow for non-strict
primitives, and to implement cons as one of these. An easier way is to
recall (section 2-1-3) that there is no fundamental need to implement
cons as a primitive at all. Instead, we can represent pairs as
procedures:
This is the procedural representation described in
Exercise 2-4. Essentially any procedural representation (e.g., a
message-passing implementation) would do as well. Notice that we can install
these definitions in the lazy evaluator simply by typing them at the driver
loop. If we had originally included cons , car , and cdr as
primitives in the global environment, they will be redefined. (Also see
Exercise 4-33 and Exercise 4-34.)
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
In terms of these basic operations, the standard definitions of the list
operations will work with infinite lists (streams) as well as finite ones, and
the stream operations can be implemented as list operations. Here are some
examples:
Note that these lazy lists are even lazier than the streams of Chapter 3:
The car of the list, as well as the cdr , is
delayed.
This permits us to create delayed versions of more general
kinds of list structures, not just sequences. Hughes 1990 discusses some
applications of ``lazy trees.''
In fact, even accessing the car or
cdr of a lazy pair need not force the value of a list element. The
value will be forced only when it is really needed -- e.g., for use as the
argument of a primitive, or to be printed as an answer.
Lazy pairs also help with the problem that arose with streams in section
3-5-4, where we found that formulating stream models of systems with
loops may require us to sprinkle our programs with explicit delay
operations, beyond the ones supplied by cons-stream . With lazy
evaluation, all arguments to procedures are delayed uniformly. For instance,
we can implement procedures to integrate lists and solve differential equations
as we originally intended in section 3-5-4:
(define (integral integrand initial-value dt)
(define int
(cons initial-value
(add-lists (scale-list integrand dt)
int)))
int)
(define (solve f y0 dt)
(define y (integral dy y0 dt))
(define dy (map f y))
y)
;;; L-Eval input:
(list-ref (solve (lambda (x) x) 1 0.001) 1000)
;;; L-Eval value:
2.716924
Exercise 4.32: Give some examples that
illustrate the difference between the streams of Chapter 3 and the
``lazier'' lazy lists described in this section. How can you take advantage of
this extra laziness?
Exercise 4.33: Ben Bitdiddle tests the lazy list
implementation given above by evaluating the expression
(car '(a b c))
To his surprise, this produces an error. After some thought, he realizes that
the ``lists'' obtained by reading in quoted expressions are different from the
lists manipulated by the new definitions of cons , car , and
cdr . Modify the evaluator's treatment of quoted expressions so that
quoted lists typed at the driver loop will produce true lazy lists.
Exercise 4.34: Modify the driver loop for the
evaluator so that lazy pairs and lists will print in some reasonable way.
(What are you going to do about infinite lists?) You may also need to modify
the representation of lazy pairs so that the evaluator can identify them in
order to print them.
Variations on a Scheme -- Nondeterministic Computing
In this section, we extend the Scheme evaluator to support a programming
paradigm called nondeterministic computing
by building into the
evaluator a facility to support automatic search. This is a much more profound
change to the language than the introduction of lazy evaluation in section
4-2.
Nondeterministic computing, like stream processing, is useful for ``generate
and test'' applications. Consider the task of starting with two lists of
positive integers and finding a pair of integers---one from the first list and
one from the second list---whose sum is prime. We saw how to handle this with
finite sequence operations in section 2-2-3 and with infinite streams in
section 3-5-3. Our approach was to generate the sequence of all possible
pairs and filter these to select the pairs whose sum is prime. Whether we
actually generate the entire sequence of pairs first as in Chapter 2, or
interleave the generating and filtering as in Chapter 3, is immaterial to
the essential image of how the computation is organized.
The nondeterministic approach evokes a different image. Imagine simply that we
choose (in some way) a number from the first list and a number from the second
list and require (using some mechanism) that their sum be prime. This is
expressed by following procedure:
(define (prime-sum-pair list1 list2)
(let ((a (an-element-of list1))
(b (an-element-of list2)))
(require (prime? (+ a b)))
(list a b)))
It might seem as if this procedure merely restates the problem, rather than
specifying a way to solve it. Nevertheless, this is a legitimate
nondeterministic program.
We assume that we have previously defined a
procedure prime? that tests whether numbers are prime. Even with
prime? defined, the prime-sum-pair procedure may look
suspiciously like the unhelpful ``pseudo-Lisp'' attempt to define the
square-root function, which we described at the beginning of section
1-1-7. In fact, a square-root procedure along those lines can actually
be formulated as a nondeterministic program. By incorporating a search
mechanism into the evaluator, we are eroding the distinction between purely
declarative descriptions and imperative specifications of how to compute
answers. We'll go even farther in this direction in section 4-4.
The key idea here is that expressions in a nondeterministic language can have
more than one possible value. For instance, an-element-of might return
any element of the given list. Our nondeterministic program evaluator will
work by automatically choosing a possible value and keeping track of the
choice. If a subsequent requirement is not met, the evaluator will try a
different choice, and it will keep trying new choices until the evaluation
succeeds, or until we run out of choices. Just as the lazy evaluator freed the
programmer from the details of how values are delayed and forced, the
nondeterministic program evaluator will free the programmer from the details of
how choices are made.
It is instructive to contrast the different images of time evoked by
nondeterministic evaluation and stream processing. Stream processing uses lazy
evaluation to decouple the time when the stream of possible answers is
assembled from the time when the actual stream elements are produced. The
evaluator supports the illusion that all the possible answers are laid out
before us in a timeless sequence. With nondeterministic evaluation, an
expression represents the exploration of a set of possible worlds, each
determined by a set of choices. Some of the possible worlds lead to dead ends,
while others have useful values. The nondeterministic program evaluator
supports the illusion that time branches, and that our programs have different
possible execution histories. When we reach a dead end, we can revisit a
previous choice point and proceed along a different branch.
The nondeterministic program evaluator implemented below is called the
amb evaluator because it is based on a new special form called
amb . We can type the above definition of prime-sum-pair at the
amb evaluator driver loop (along with definitions of prime? ,
an-element-of , and require ) and run the procedure as follows:
;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; Starting a new problem
;;; Amb-Eval value:
(3 20)
The value returned was obtained after the evaluator repeatedly chose elements
from each of the lists, until a successful choice was made.
Section 4-3-1 introduces amb and explains how it supports
nondeterminism through the evaluator's automatic search mechanism. Section
4-3-2 presents examples of nondeterministic programs, and section
4-3-3 gives the details of how to implement the amb evaluator by
modifying the ordinary Scheme evaluator.
@menu
* 4-3-1:: Amb and Search
* 4-3-2:: Examples of Nondeterministic Programs
* 4-3-3:: Implementing the Amb Evaluator
@end menu
Amb and Search
To extend Scheme to support nondeterminism, we introduce a new special form
called amb .
The idea of amb for nondeterministic
programming was first described in 1961 by John McCarthy (see McCarthy 1967).
The expression
(amb ... )
returns the value of one of the n expressions
``ambiguously.'' For example, the expression
(list (amb 1 2 3) (amb 'a 'b))
can have six possible values:
(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)
Amb with a single choice produces an ordinary (single) value.
 Operationally, we can think of (amb) as an
expression that when evaluated causes the computation to ``fail'': The
computation aborts and no value is produced. Using this idea, we can express
the requirement that a particular predicate expression p must be true as
follows:
(define (require p)
(if (not p) (amb)))
With amb and require , we can implement the an-element-of
procedure used above:
An-element-of fails if the list is empty. Otherwise it ambiguously
returns either the first element of the list or an element chosen from the rest
of the list.
We can also express infinite ranges of choices. The following procedure
potentially returns any integer greater than or equal to some given n:
(define (an-integer-starting-from n)
(amb n (an-integer-starting-from (+ n 1))))
This is like the stream procedure integers-starting-from described in
section 3-5-2, but with an important difference: The stream procedure
returns an object that represents the sequence of all integers beginning with
n, whereas the amb procedure returns a single integer.
In
actuality, the distinction between nondeterministically returning a single
choice and returning all choices depends somewhat on our point of view. From
the perspective of the code that uses the value, the nondeterministic choice
returns a single value. From the perspective of the programmer designing the
code, the nondeterministic choice potentially returns all possible values, and
the computation branches so that each value is investigated separately.
Abstractly, we can imagine that evaluating an amb expression causes time
to split into branches, where the computation continues on each branch with one
of the possible values of the expression. We say that amb represents a
nondeterministic choice point
. If we had a machine with a sufficient
number of processors that could be dynamically allocated, we could implement
the search in a straightforward way. Execution would proceed as in a
sequential machine, until an amb expression is encountered. At this
point, more processors would be allocated and initialized to continue all of
the parallel executions implied by the choice. Each processor would proceed
sequentially as if it were the only choice, until it either terminates by
encountering a failure, or it further subdivides, or it finishes.
One
might object that this is a hopelessly inefficient mechanism. It might require
millions of processors to solve some easily stated problem this way, and most
of the time most of those processors would be idle. This objection should be
taken in the context of history. Memory used to be considered just such an
expensive commodity. In 1964 a megabyte of RAM cost about $400,000. Now every
personal computer has many megabytes of RAM, and most of the time most of that
RAM is unused. It is hard to underestimate the cost of mass-produced
electronics.
On the other hand, if we have a machine that can execute only one process (or a
few concurrent processes), we must consider the alternatives sequentially. One
could imagine modifying an evaluator to pick at random a branch to follow
whenever it encounters a choice point. Random choice, however, can easily lead
to failing values. We might try running the evaluator over and over, making
random choices and hoping to find a non-failing value, but it is better to
systematically search
all possible execution paths. The amb
evaluator that we will develop and work with in this section implements a
systematic search as follows: When the evaluator encounters an application of
amb , it initially selects the first alternative. This selection may
itself lead to a further choice. The evaluator will always initially choose
the first alternative at each choice point. If a choice results in a failure,
then the evaluator automagically
Automagically: ``Automatically, but
in a way which, for some reason (typically because it is too complicated, or
too ugly, or perhaps even too trivial), the speaker doesn't feel like
explaining.'' (Steele 1983, Raymond 1993)
backtracks
to the most
recent choice point and tries the next alternative. If it runs out of
alternatives at any choice point, the evaluator will back up to the previous
choice point and resume from there. This process leads to a search strategy
known as depth-first search
or chronological
backtracking
.
[Footnote 4.47] The integration
of automatic search strategies into programming languages has had a long and
checkered history. The first suggestions that nondeterministic algorithms
might be elegantly encoded in a programming language with search and automatic
backtracking came from Robert Floyd (1967). Carl Hewitt (1969) invented a
programming language called Planner that explicitly supported automatic
chronological backtracking, providing for a built-in depth-first search
strategy. Sussman, Winograd, and Charniak (1971) implemented a subset of this
language, called MicroPlanner, which was used to support work in problem
solving and robot planning. Similar ideas, arising from logic and theorem
proving, led to the genesis in Edinburgh and Marseille of the elegant language
Prolog (which we will discuss in section 4-4). After sufficient
frustration with automatic search, McDermott and Sussman (1972) developed a
language called Conniver, which included mechanisms for placing the search
strategy under programmer control. This proved unwieldy, however, and Sussman
and Stallman (1975) found a more tractable approach while investigating methods
of symbolic analysis for electrical circuits. They developed a
non-chronological backtracking scheme that was based on tracing out the logical
dependencies connecting facts, a technique that has come to be known as
dependency-directed backtracking
. Although their method was complex,
it produced reasonably efficient programs because it did little redundant
search. Doyle (1979) and McAllester (1978, 1980) generalized and clarified the
methods of Stallman and Sussman, developing a new paradigm for formulating
search that is now called truth maintenance
. Modern problem-solving
systems all use some form of truth-maintenance system as a substrate. See
Forbus and deKleer 1993 for a discussion of elegant ways to build
truth-maintenance systems and applications using truth maintenance. Zabih,
McAllester, and Chapman 1987 describes a nondeterministic extension to Scheme
that is based on amb ; it is similar to the interpreter described in this
section, but more sophisticated, because it uses dependency-directed
backtracking rather than chronological backtracking. Winston 1992 gives an
introduction to both kinds of backtracking.
Driver loop
The driver loop for the amb evaluator has some unusual properties. It
reads an expression and prints the value of the first non-failing execution, as
in the prime-sum-pair example shown above. If we want to see the value
of the next successful execution, we can ask the interpreter to backtrack and
attempt to generate a second non-failing execution. This is signaled by typing
the symbol try-again . If any expression except try-again is
given, the interpreter will start a new problem, discarding the unexplored
alternatives in the previous problem. Here is a sample interaction:
;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; Starting a new problem
;;; Amb-Eval value:
(3 20)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 110)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(8 35)
;;; Amb-Eval input:
try-again
;;; There are no more values of
(prime-sum-pair (quote (1 3 5 8)) (quote (20 35 110)))
;;; Amb-Eval input:
(prime-sum-pair '(19 27 30) '(11 36 58))
;;; Starting a new problem
;;; Amb-Eval value:
(30 11)
Exercise 4.35: Write a procedure
an-integer-between that returns an integer between two given bounds.
This can be used to implement a procedure that finds Pythagorean triples, i.e.,
triples of integers (i,j,k) between the given bounds such that
i <= j and i^2 + j^2 = k^2, as follows:
(define (a-pythagorean-triple-between low high)
(let ((i (an-integer-between low high)))
(let ((j (an-integer-between i high)))
(let ((k (an-integer-between j high)))
(require (= (+ (* i i) (* j j)) (* k k)))
(list i j k)))))
Exercise 4.36: Exercise 3-69 discussed how
to generate the stream of all Pythagorean triples, with no upper bound
on the size of the integers to be searched. Explain why simply replacing
an-integer-between by an-integer-starting-from in the procedure
in Exercise 4-35 is not an adequate way to generate arbitrary Pythagorean
triples. Write a procedure that actually will accomplish this. (That is,
write a procedure for which repeatedly typing try-again would in
principle eventually generate all Pythagorean triples.)
Exercise 4.37: Ben Bitdiddle claims that the
following method for generating Pythagorean triples is more efficient than the
one in Exercise 4-35. Is he correct? (Hint: Consider the number of
possibilities that must be explored.)
Section 4-3-3 describes the implementation of the amb evaluator.
First, however, we give some examples of how it can be used. The advantage of
nondeterministic programming is that we can suppress the details of how search
is carried out, thereby expressing our programs at a higher level of
abstraction.
Logic Puzzles
The following puzzle (taken from Dinesman 1968) is typical of a large class of
simple logic puzzles:
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an
apartment house that contains only five floors. Baker does not live on the top
floor. Cooper does not live on the bottom floor. Fletcher does not live on
either the top or the bottom floor. Miller lives on a higher floor than does
Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does
not live on a floor adjacent to Cooper's. Where does everyone live?
We can determine who lives on each floor in a straightforward way by
enumerating all the possibilities and imposing the given
restrictions:
Our program uses the following procedure to determine if
the elements of a list are distinct:
Although this simple procedure works, it is very slow. Exercise 4-39 and
Exercise 4-40 discuss some possible improvements.
Exercise 4.38: Modify the multiple-dwelling
procedure to omit the requirement that Smith and Fletcher do not live on
adjacent floors. How many solutions are there to this modified puzzle?
Exercise 4.39: Does the order of the
restrictions in the multiple-dwelling procedure affect the answer? Does it
affect the time to find an answer? If you think it matters, demonstrate a
faster program obtained from the given one by reordering the restrictions. If
you think it does not matter, argue your case.
Exercise 4.40: In the multiple dwelling problem,
how many sets of assignments are there of people to floors, both before and
after the requirement that floor assignments be distinct? It is very
inefficient to generate all possible assignments of people to floors and then
leave it to backtracking to eliminate them. For example, most of the
restrictions depend on only one or two of the person-floor variables, and can
thus be imposed before floors have been selected for all the people. Write and
demonstrate a much more efficient nondeterministic procedure that solves this
problem based upon generating only those possibilities that are not already
ruled out by previous restrictions. (Hint: This will require a nest of
let expressions.)
Exercise 4.41: Write an ordinary Scheme program
to solve the multiple dwelling puzzle.
Exercise 4.42: Solve the following ``Liars''
puzzle (from Phillips 1934):
Five schoolgirls sat for an examination. Their parents---so they
thought---showed an undue degree of interest in the result. They therefore
agreed that, in writing home about the examination, each girl should make one
true statement and one untrue one. The following are the relevant passages
from their letters:
Betty: ``Kitty was second in the examination. I was only third.''
Ethel: ``You'll be glad to hear that I was on top. Joan was second.''
Joan: ``I was third, and poor old Ethel was bottom.''
Kitty: ``I came out second. Mary was only fourth.''
Mary: ``I was fourth. Top place was taken by Betty.''
What in fact was the order in which the five girls were placed?
Exercise 4.43: Use the amb evaluator to
solve the following puzzle:
This is taken from a booklet called
``Problematical Recreations,'' published in the 1960s by Litton Industries,
where it is attributed to the @cite{Kansas State Engineer
.}
Mary Ann Moore's father has a yacht and so has each of his four friends:
Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr. Parker. Each of the
five also has one daughter and each has named his yacht after a daughter of one
of the others. Sir Barnacle's yacht is the Gabrielle, Mr. Moore owns the
Lorna; Mr. Hall the Rosalind. The Melissa, owned by Colonel Downing, is named
after Sir Barnacle's daughter. Gabrielle's father owns the yacht that is named
after Dr. Parker's daughter. Who is Lorna's father?
Try to write the program so that it runs efficiently (see Exercise 4-40).
Also determine how many solutions there are if we are not told that Mary Ann's
last name is Moore.
Exercise 4.44: Exercise 2-42 described the
``eight-queens puzzle'' of placing queens on a chessboard so that no two attack
each other. Write a nondeterministic program to solve this puzzle.
Parsing natural language
Programs designed to accept natural language as input usually start by
attempting to parse
the input, that is, to match the input against
some grammatical structure. For example, we might try to recognize simple
sentences consisting of an article followed by a noun followed by a verb, such
as ``The cat eats.'' To accomplish such an analysis, we must be able to
identify the parts of speech of individual words. We could start with some
lists that classify various words:
Here we use the convention that the
first element of each list designates the part of speech for the rest of the
words in the list.
(define nouns '(noun student professor cat class))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(article the a))
We also need a grammar
, that is, a set of rules describing how
grammatical elements are composed from simpler elements. A very simple grammar
might stipulate that a sentence always consists of two pieces---a noun phrase
followed by a verb---and that a noun phrase consists of an article followed by
a noun. With this grammar, the sentence ``The cat eats'' is parsed as follows:
We can generate such a parse with a simple program that has separate procedures
for each of the grammatical rules. To parse a sentence, we identify its two
constituent pieces and return a list of these two elements, tagged with the
symbol sentence :
At the lowest level, parsing boils down to repeatedly checking that the next
unparsed word is a member of the list of words for the required part of speech.
To implement this, we maintain a global variable *unparsed* , which is
the input that has not yet been parsed. Each time we check a word, we require
that *unparsed* must be non-empty and that it should begin with a word
from the designated list. If so, we remove that word from *unparsed*
and return the word together with its part of speech (which is found at the
head of the list):
Notice that parse-word uses set! to
modify the unparsed input list. For this to work, our amb evaluator
must undo the effects of set! operations when it backtracks.
We can now try the parser and verify that it works for our simple test
sentence:
;;; Amb-Eval input:
(parse '(the cat eats))
;;; Starting a new problem
;;; Amb-Eval value:
(sentence (noun-phrase (article the) (noun cat)) (verb eats))
The amb evaluator is useful here because it is convenient to express the
parsing constraints with the aid of require . Automatic search and
backtracking really pay off, however, when we consider more complex grammars
where there are choices for how the units can be decomposed.
Let's add to our grammar a list of prepositions:
(define prepositions '(prep for to in by with))
and define a prepositional phrase (e.g., ``for the cat'') to be a preposition
followed by a noun phrase:
Now we can define a sentence to be a noun phrase followed by a verb phrase,
where a verb phrase can be either a verb or a verb phrase extended by a
prepositional phrase:
Observe that this definition is recursive---a
verb may be followed by any number of prepositional phrases.
While we're at it, we can also elaborate the definition of noun phrases to
permit such things as ``a cat in the class.'' What we used to call a noun
phrase, we'll now call a simple noun phrase, and a noun phrase will now be
either a simple noun phrase or a noun phrase extended by a prepositional
phrase:
Observe that a given input may have more than one legal parse. In the sentence
``The professor lectures to the student with the cat,'' it may be that the
professor is lecturing with the cat, or that the student has the cat. Our
nondeterministic program finds both possibilities:
(parse '(the professor lectures to the student with the cat))
Exercise 4.45: With the grammar given above, the
following sentence can be parsed in five different ways: ``The professor
lectures to the student in the class with the cat.'' Give the five parses and
explain the differences in shades of meaning among them.
Exercise 4.46: The evaluators in sections
4-1 and 4-2 do not determine what order operands are evaluated in.
We will see that the amb evaluator evaluates them from left to right.
Explain why our parsing program wouldn't work if the operands were evaluated in
some other order.
Exercise 4.47: Louis Reasoner suggests that,
since a verb phrase is either a verb or a verb phrase followed by a
prepositional phrase, it would be much more straightforward to define the
procedure parse-verb-phrase as follows (and similarly for noun phrases):
Does this work? Does the program's behavior change if we interchange the order
of expressions in the amb
Exercise 4.48: Extend the grammar given above to
handle more complex sentences. For example, you could extend noun phrases and
verb phrases to include adjectives and adverbs, or you could handle compound
sentences.
This kind of grammar can become arbitrarily complex, but it
is only a toy as far as real language understanding is concerned. Real
natural-language understanding by computer requires an elaborate mixture of
syntactic analysis and interpretation of meaning. On the other hand, even toy
parsers can be useful in supporting flexible command languages for programs
such as information-retrieval systems. Winston 1992 discusses computational
approaches to real language understanding and also the applications of simple
grammars to command languages.
Exercise 4.49: Alyssa P. Hacker is more
interested in generating interesting sentences than in parsing them. She
reasons that by simply changing the procedure parse-word so that it
ignores the ``input sentence'' and instead always succeeds and generates an
appropriate word, we can use the programs we had built for parsing to do
generation instead. Implement Alyssa's idea, and show the first half-dozen or
so sentences generated.
Although Alyssa's idea works just fine (and is
surprisingly simple), the sentences that it generates are a bit boring---they
don't sample the possible sentences of this language in a very interesting way.
In fact, the grammar is highly recursive in many places, and Alyssa's technique
``falls into'' one of these recursions and gets stuck. See Exercise 4-50
for a way to deal with this.
Implementing the Amb Evaluator
The evaluation of an ordinary Scheme expression may return a value, may never
terminate, or may signal an error. In nondeterministic Scheme the evaluation
of an expression may in addition result in the discovery of a dead end, in
which case evaluation must backtrack to a previous choice point. The
interpretation of nondeterministic Scheme is complicated by this extra case.
We will construct the amb evaluator for nondeterministic Scheme by
modifying the analyzing evaluator of section 4-1-7.
We chose to
implement the lazy evaluator in section 4-2 as a modification of the
ordinary metacircular evaluator of section 4-1-1. In contrast, we will
base the amb evaluator on the analyzing evaluator of section
4-1-7, because the execution procedures in that evaluator provide a
convenient framework for implementing backtracking.
As in the analyzing
evaluator, evaluation of an expression is accomplished by calling an execution
procedure produced by analysis of that expression. The difference between the
interpretation of ordinary Scheme and the interpretation of nondeterministic
Scheme will be entirely in the execution procedures.
Execution procedures and continuations
Recall that the execution procedures for the ordinary evaluator take one
argument: the environment of execution. In contrast, the execution procedures
in the amb evaluator take three arguments: the environment, and two
procedures called continuation procedures
. The evaluation of an
expression will finish by calling one of these two continuations: If the
evaluation results in a value, the success continuation
is called
with that value; if the evaluation results in the discovery of a dead end, the
failure continuation
is called. Constructing and calling appropriate
continuations is the mechanism by which the nondeterministic evaluator
implements backtracking.
It is the job of the success continuation to receive a value and proceed with
the computation. Along with that value, the success continuation is passed
another failure continuation, which is to be called subsequently if the use of
that value leads to a dead end.
It is the job of the failure continuation to try another branch of the
nondeterministic process. The essence of the nondeterministic language is in
the fact that expressions may represent choices among alternatives. The
evaluation of such an expression must proceed with one of the indicated
alternative choices, even though it is not known in advance which choices will
lead to acceptable results. To deal with this, the evaluator picks one of the
alternatives and passes this value to the success continuation. Together with
this value, the evaluator constructs and passes along a failure continuation
that can be called later to choose a different alternative.
A failure is triggered during evaluation (that is, a failure continuation is
called) when a user program explicitly rejects the current line of attack (for
example, a call to require may result in execution of (amb) , an
expression that always fails---see section 4-3-1). The failure
continuation in hand at that point will cause the most recent choice point to
choose another alternative. If there are no more alternatives to be considered
at that choice point, a failure at an earlier choice point is triggered, and so
on. Failure continuations are also invoked by the driver loop in response to a
try-again request, to find another value of the expression.
In addition, if a side-effect operation (such as assignment to a variable)
occurs on a branch of the process resulting from a choice, it may be necessary,
when the process finds a dead end, to undo the side effect before making a new
choice. This is accomplished by having the side-effect operation produce a
failure continuation that undoes the side effect and propagates the failure.
In summary, failure continuations are constructed by
amb expressions---to provide a mechanism to make alternative choices if
the current choice made by the amb expression leads to a dead end;
the top-level driver---to provide a mechanism to report failure when the
choices are exhausted;
assignments---to intercept failures and undo assignments during backtracking.
Failures are initiated only when a dead end is encountered. This occurs
if the user program executes (amb) ;
if the user types try-again at the top-level driver.
Failure continuations are also called during processing of a failure:
When the failure continuation created by an assignment finishes undoing a side
effect, it calls the failure continuation it intercepted, in order to propagate
the failure back to the choice point that led to this assignment or to the top
level.
When the failure continuation for an amb runs out of choices, it calls
the failure continuation that was originally given to the amb , in order
to propagate the failure back to the previous choice point or to the top level.
Structure of the evaluator
The syntax- and data-representation procedures for the amb evaluator,
and also the basic analyze procedure, are identical to those in the
evaluator of section 4-1-7, except for the fact that we need additional
syntax procedures to recognize the amb special form:
We assume
that the evaluator supports let (see Exercise 4-22), which we have
used in our nondeterministic programs.
We must also add to the dispatch in analyze a clause that will recognize
this special form and generate an appropriate execution procedure:
((amb? exp) (analyze-amb exp))
The top-level procedure ambeval (similar to the version of eval
given in section 4-1-7) analyzes the given expression and applies the
resulting execution procedure to the given environment, together with two given
continuations:
A success continuation is a procedure of two arguments: the value just obtained
and another failure continuation to be used if that value leads to a subsequent
failure. A failure continuation is a procedure of no arguments. So the general
form of an execution procedure is
(lambda (env succeed fail)
;; succeed is (lambda (value fail) ...)
;; fail is (lambda () ...)
...)
will attempt to evaluate the given expression and will return either the
expression's value (if the evaluation succeeds) or the symbol failed (if
the evaluation fails). The call to ambeval in the driver loop shown
below uses much more complicated continuation procedures, which continue the
loop and support the try-again request.
Most of the complexity of the amb evaluator results from the mechanics
of passing the continuations around as the execution procedures call each
other. In going through the following code, you should compare each of the
execution procedures with the corresponding procedure for the ordinary
evaluator given in section 4-1-7.
Simple expressions
The execution procedures for the simplest kinds of expressions are essentially
the same as those for the ordinary evaluator, except for the need to manage the
continuations. The execution procedures simply succeed with the value of the
expression, passing along the failure continuation that was passed to them.
Notice that looking up a variable always ``succeeds.'' If
lookup-variable-value fails to find the variable, it signals an error,
as usual. Such a ``failure'' indicates a program bug---a reference to an
unbound variable; it is not an indication that we should try another
nondeterministic choice instead of the one that is currently being tried.
Conditionals and sequences
Conditionals are also handled in a similar way as in the ordinary evaluator.
The execution procedure generated by analyze-if invokes the predicate
execution procedure pproc with a success continuation that checks
whether the predicate value is true and goes on to execute either the
consequent or the alternative. If the execution of pproc fails, the
original failure continuation for the if expression is called.
Sequences are also handled in the same way as in the previous evaluator, except
for the machinations in the subprocedure sequentially that are required
for passing the continuations. Namely, to sequentially execute a and
then b , we call a with a success continuation that calls
b .
(define (analyze-sequence exps)
(define (sequentially a b)
(lambda (env succeed fail)
(a env
;; success continuation for calling a
(lambda (a-value fail2)
(b env succeed fail2))
;; failure continuation for calling a
fail)))
(define (loop first-proc rest-procs)
(if (null? rest-procs)
first-proc
(loop (sequentially first-proc (car rest-procs))
(cdr rest-procs))))
(let ((procs (map analyze exps)))
(if (null? procs)
(error "Empty sequence -- ANALYZE"))
(loop (car procs) (cdr procs))))
Definitions and assignments
Definitions are another case where we must go to some trouble to manage the
continuations, because it is necessary to evaluate the definition-value
expression before actually defining the new variable. To accomplish this, the
definition-value execution procedure vproc is called with the
environment, a success continuation, and the failure continuation. If the
execution of vproc succeeds, obtaining a value val for the
defined variable, the variable is defined and the success is propagated:
Assignments are more interesting. This is the first place where we really use
the continuations, rather than just passing them around. The execution
procedure for assignments starts out like the one for definitions. It first
attempts to obtain the new value to be assigned to the variable. If this
evaluation of vproc fails, the assignment fails.
If vproc succeeds, however, and we go on to make the assignment, we must
consider the possibility that this branch of the computation might later fail,
which will require us to backtrack out of the assignment. Thus, we must
arrange to undo the assignment as part of the backtracking process.
We
didn't worry about undoing definitions, since we can assume that internal
definitions are scanned out (section 4-1-6).
This is accomplished by giving vproc a success continuation (marked with
the comment ``*1*'' below) that saves the old value of the variable before
assigning the new value to the variable and proceeding from the assignment.
The failure continuation that is passed along with the value of the assignment
(marked with the comment ``*2*'' below) restores the old value of the variable
before continuing the failure. That is, a successful assignment provides a
failure continuation that will intercept a subsequent failure; whatever failure
would otherwise have called fail2 calls this procedure instead, to undo
the assignment before actually calling fail2 .
The execution procedure for applications contains no new ideas except for the
technical complexity of managing the continuations. This complexity arises in
analyze-application , due to the need to keep track of the success and
failure continuations as we evaluate the operands. We use a procedure
get-args to evaluate the list of operands, rather than a simple
map as in the ordinary evaluator.
In get-args , notice how cdr ing down the list of aproc
execution procedures and cons ing up the resulting list of args is
accomplished by calling each aproc in the list with a success
continuation that recursively calls get-args . Each of these recursive
calls to get-args has a success continuation whose value is the
cons of the newly obtained argument onto the list of accumulated
arguments:
The actual procedure application, which is performed by
execute-application , is accomplished in the same way as for the ordinary
evaluator, except for the need to manage the continuations.
The amb special form is the key element in the nondeterministic
language. Here we see the essence of the interpretation process and the reason
for keeping track of the continuations. The execution procedure for amb
defines a loop try-next that cycles through the execution procedures for
all the possible values of the amb expression. Each execution procedure
is called with a failure continuation that will try the next one. When there
are no more alternatives to try, the entire amb expression fails.
The driver loop for the amb evaluator is complex, due to the mechanism
that permits the user to try again in evaluating an expression. The driver
uses a procedure called internal-loop , which takes as argument a
procedure try-again . The intent is that calling try-again should
go on to the next untried alternative in the nondeterministic evaluation.
Internal-loop either calls try-again in response to the user
typing try-again at the driver loop, or else starts a new evaluation by
calling ambeval .
The failure continuation for this call to ambeval informs the user that
there are no more values and re-invokes the driver loop.
The success continuation for the call to ambeval is more subtle. We
print the obtained value and then invoke the internal loop again with a
try-again procedure that will be able to try the next alternative. This
next-alternative procedure is the second argument that was passed to the
success continuation. Ordinarily, we think of this second argument as a
failure continuation to be used if the current evaluation branch later fails.
In this case, however, we have completed a successful evaluation, so we can
invoke the ``failure'' alternative branch in order to search for additional
successful evaluations.
(define input-prompt ";;; Amb-Eval input:")
(define output-prompt ";;; Amb-Eval value:")
(define (driver-loop)
(define (internal-loop try-again)
(prompt-for-input input-prompt)
(let ((input (read)))
(if (eq? input 'try-again)
(try-again)
(begin
(newline)
(display ";;; Starting a new problem ")
(ambeval input
the-global-environment
;; ambeval success
(lambda (val next-alternative)
(announce-output output-prompt)
(user-print val)
(internal-loop next-alternative))
;; ambeval failure
(lambda ()
(announce-output
";;; There are no more values of")
(user-print input)
(driver-loop)))))))
(internal-loop
(lambda ()
(newline)
(display ";;; There is no current problem")
(driver-loop))))
The initial call to internal-loop uses a try-again procedure that
complains that there is no current problem and restarts the driver loop. This
is the behavior that will happen if the user types try-again when there
is no evaluation in progress.
Exercise 4.50: Implement a new special form
ramb that is like amb except that it searches alternatives in a
random order, rather than from left to right. Show how this can help with
Alyssa's problem in Exercise 4-49.
Exercise 4.51: Implement a new kind of
assignment called permanent-set! that is not undone upon failure. For
example, we can choose two distinct elements from a list and count the number
of trials required to make a successful choice as follows:
(define count 0)
(let ((x (an-element-of '(a b c)))
(y (an-element-of '(a b c))))
(permanent-set! count (+ count 1))
(require (not (eq? x y)))
(list x y count))
;;; Starting a new problem
;;; Amb-Eval value:
(a b 2)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a c 3)
What values would have been displayed if we had used set! here
rather than permanent-set! ?
Exercise 4.52: Implement a new construct called
if-fail that permits the user to catch the failure of an expression.
If-fail takes two expressions. It evaluates the first expression as
usual and returns as usual if the evaluation succeeds. If the evaluation
fails, however, the value of the second expression is returned, as in the
following example:
;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5))))
(require (even? x))
x)
'all-odd)
;;; Starting a new problem
;;; Amb-Eval value:
all-odd
;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5 8))))
(require (even? x))
x)
'all-odd)
;;; Starting a new problem
;;; Amb-Eval value:
8
Exercise 4.53: With permanent-set! as
described in Exercise 4-51 and if-fail as in Exercise 4-52,
what will be the result of evaluating
Exercise 4.54: If we had not realized that
require could be implemented as an ordinary procedure that uses
amb , to be defined by the user as part of a nondeterministic program, we
would have had to implement it as a special form. This would require syntax
procedures
In Chapter 1 we stressed that computer science deals with imperative (how
to) knowledge, whereas mathematics deals with declarative (what is) knowledge.
Indeed, programming languages require that the programmer express knowledge in
a form that indicates the step-by-step methods for solving particular problems.
On the other hand, high-level languages provide, as part of the language
implementation, a substantial amount of methodological knowledge that frees the
user from concern with numerous details of how a specified computation will
progress.
Most programming languages, including Lisp, are organized around computing the
values of mathematical functions. Expression-oriented languages (such as Lisp,
Fortran, and Algol) capitalize on the ``pun'' that an expression that describes
the value of a function may also be interpreted as a means of computing that
value. Because of this, most programming languages are strongly biased toward
unidirectional computations (computations with well-defined inputs and
outputs). There are, however, radically different programming languages that
relax this bias. We saw one such example in section 3-3-5, where the
objects of computation were arithmetic constraints. In a constraint system the
direction and the order of computation are not so well specified; in carrying
out a computation the system must therefore provide more detailed ``how to''
knowledge than would be the case with an ordinary arithmetic computation. This
does not mean, however, that the user is released altogether from the
responsibility of providing imperative knowledge. There are many constraint
networks that implement the same set of constraints, and the user must choose
from the set of mathematically equivalent networks a suitable network to
specify a particular computation.
The nondeterministic program evaluator of section 4-3 also moves away
from the view that programming is about constructing algorithms for computing
unidirectional functions. In a nondeterministic language, expressions can have
more than one value, and, as a result, the computation is dealing with
relations rather than with single-valued functions. Logic programming extends
this idea by combining a relational vision of programming with a powerful kind
of symbolic pattern matching called unification
.
Logic
programming has grown out of a long history of research in automatic theorem
proving. Early theorem-proving programs could accomplish very little, because
they exhaustively searched the space of possible proofs. The major
breakthrough that made such a search plausible was the discovery in the early
1960s of the unification algorithm
and the resolution
principle
(Robinson 1965). Resolution was used, for example, by Green and
Raphael (1968) (see also Green 1969) as the basis for a deductive
question-answering system. During most of this period, researchers
concentrated on algorithms that are guaranteed to find a proof if one exists.
Such algorithms were difficult to control and to direct toward a proof. Hewitt
(1969) recognized the possibility of merging the control structure of a
programming language with the operations of a logic-manipulation system,
leading to the work in automatic search mentioned in section 4-3-1
(footnote Footnote 4-47). At the same time that this was being done,
Colmerauer, in Marseille, was developing rule-based systems for manipulating
natural language (see Colmerauer et al. 1973). He invented a programming
language called Prolog for representing those rules. Kowalski (1973; 1979), in
Edinburgh, recognized that execution of a Prolog program could be interpreted
as proving theorems (using a proof technique called linear Horn-clause
resolution). The merging of the last two strands led to the logic-programming
movement. Thus, in assigning credit for the development of logic programming,
the French can point to Prolog's genesis at the University of Marseille, while
the British can highlight the work at the University of Edinburgh. According
to people at @acronym{MIT
, logic programming was developed by these groups in
an attempt to figure out what Hewitt was talking about in his brilliant but
impenetrable Ph.D. thesis. For a history of logic programming, see Robinson
1983.}
This approach, when it works, can be a very powerful way to write programs.
Part of the power comes from the fact that a single ``what is'' fact can be
used to solve a number of different problems that would have different ``how
to'' components. As an example, consider the append operation, which
takes two lists as arguments and combines their elements to form a single list.
In a procedural language such as Lisp, we could define append in terms
of the basic list constructor cons , as we did in section 2-2-1:
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
This procedure can be regarded as a translation into Lisp of the following two
rules, the first of which covers the case where the first list is empty and the
second of which handles the case of a nonempty list, which is a cons of
two parts:
For any list y , the empty list and y append to form
y .
For any u , v , y , and z , (cons u v) and
y append to form (cons u z) if v and y append to form z .
To see the correspondence between the
rules and the procedure, let x in the procedure (where x is
nonempty) correspond to (cons u v) in the rule. Then z in the
rule corresponds to the append of (cdr x) and y .
Using the append procedure, we can answer questions such as
Find the append of (a b) and (c d) .
But the same two rules are also sufficient for answering the following sorts of
questions, which the procedure can't answer:
Find a list y that append s with (a b) to produce (a
b c d) .
Find all x and y that append to form (a b c d) .
In a logic programming language, the programmer writes an append
``procedure'' by stating the two rules about append given above. ``How
to'' knowledge is provided automatically by the interpreter to allow this
single pair of rules to be used to answer all three types of questions about
append .
This certainly does not relieve the user of the entire
problem of how to compute the answer. There are many different mathematically
equivalent sets of rules for formulating the append relation, only some
of which can be turned into effective devices for computing in any direction.
In addition, sometimes ``what is'' information gives no clue ``how to'' compute
an answer. For example, consider the problem of computing the y such that
y^2 = x.
Contemporary logic programming languages (including the one we implement here)
have substantial deficiencies, in that their general ``how to'' methods can
lead them into spurious infinite loops or other undesirable behavior. Logic
programming is an active field of research in computer
science.
Interest in logic programming peaked during the early 80s
when the Japanese government began an ambitious project aimed at building
superfast computers optimized to run logic programming languages. The speed of
such computers was to be measured in LIPS (Logical Inferences Per Second)
rather than the usual FLOPS (FLoating-point Operations Per Second). Although
the project succeeded in developing hardware and software as originally
planned, the international computer industry moved in a different direction.
See Feigenbaum and Shrobe 1993 for an overview evaluation of the Japanese
project. The logic programming community has also moved on to consider
relational programming based on techniques other than simple pattern matching,
such as the ability to deal with numerical constraints such as the ones
illustrated in the constraint-propagation system of section 3-3-5.
Earlier in this chapter we explored the technology of implementing interpreters
and described the elements that are essential to an interpreter for a Lisp-like
language (indeed, to an interpreter for any conventional language). Now we
will apply these ideas to discuss an interpreter for a logic programming
language. We call this language the query language
, because it is
very useful for retrieving information from data bases by formulating
queries
, or questions, expressed in the language. Even though the
query language is very different from Lisp, we will find it convenient to
describe the language in terms of the same general framework we have been using
all along: as a collection of primitive elements, together with means of
combination that enable us to combine simple elements to create more complex
elements and means of abstraction that enable us to regard complex elements as
single conceptual units. An interpreter for a logic programming language is
considerably more complex than an interpreter for a language like Lisp.
Nevertheless, we will see that our query-language interpreter contains many of
the same elements found in the interpreter of section 4-1. In
particular, there will be an ``eval'' part that classifies expressions
according to type and an ``apply'' part that implements the language's
abstraction mechanism (procedures in the case of Lisp, and rules
in
the case of logic programming). Also, a central role is played in the
implementation by a frame data structure, which determines the correspondence
between symbols and their associated values. One additional interesting aspect
of our query-language implementation is that we make substantial use of
streams, which were introduced in Chapter 3.
@menu
* 4-4-1:: Deductive Information Retrieval
* 4-4-2:: How the Query System Works
* 4-4-3:: Is Logic Programming Mathematical Logic?
* 4-4-4:: Implementing the Query System
@end menu
Deductive Information Retrieval
Logic programming excels in providing interfaces to data bases for information
retrieval. The query language we shall implement in this chapter is designed
to be used in this way.
In order to illustrate what the query system does, we will show how it can be
used to manage the data base of personnel records for Microshaft, a thriving
high-technology company in the Boston area. The language provides
pattern-directed access to personnel information and can also take advantage of
general rules in order to make logical deductions.
A sample data base
The personnel data base for Microshaft contains assertions
about
company personnel. Here is the information about Ben Bitdiddle, the resident
computer wizard:
Each assertion is a list (in this case a triple) whose elements can themselves
be lists.
As resident wizard, Ben is in charge of the company's computer division, and he
supervises two programmers and one technician. Here is the information about
them:
All of these people are in the computer division, as indicated by the word
computer as the first item in their job descriptions.
Ben is a high-level employee. His supervisor is the company's big wheel
himself:
The data base also contains assertions about which kinds of jobs can be done by
people holding other kinds of jobs. For instance, a computer wizard can do the
jobs of both a computer programmer and a computer technician:
(can-do-job (administration secretary)
(administration big wheel))
Simple queries
The query language allows users to retrieve information from the data base by
posing queries in response to the system's prompt. For example, to find all
computer programmers one can say
The input query specifies that we are looking for entries in the data base that
match a certain pattern
. In this example, the pattern specifies
entries consisting of three items, of which the first is the literal symbol
job , the second can be anything, and the third is the literal list
(computer programmer) . The ``anything'' that can be the second item in
the matching list is specified by a pattern variable
, ?x . The
general form of a pattern variable is a symbol, taken to be the name of the
variable, preceded by a question mark. We will see below why it is useful to
specify names for pattern variables rather than just putting ? into
patterns to represent ``anything.'' The system responds to a simple query by
showing all entries in the data base that match the specified pattern.
A pattern can have more than one variable. For example, the query
(address ?x ?y)
will list all the employees' addresses.
A pattern can have no variables, in which case the query simply determines
whether that pattern is an entry in the data base. If so, there will be one
match; if not, there will be no matches.
The same pattern variable can appear more than once in a query, specifying that
the same ``anything'' must appear in each position. This is why variables have
names. For example,
(supervisor ?x ?x)
finds all people who supervise themselves (though there are no such assertions
in our sample data base).
The query
(job ?x (computer ?type))
matches all job entries whose third item is a two-element list whose first item
is computer :
because the third item in the entry is a list of three elements, and the
pattern's third item specifies that there should be two elements. If we wanted
to change the pattern so that the third item could be any list beginning with
computer , we could specify
This uses the dotted-tail notation
introduced in Exercise 2-20.
(job ?x (computer . ?type))
For example,
(computer . ?type)
matches the data
(computer programmer trainee)
with ?type as the list (programmer trainee) . It also
matches the data
(computer programmer)
with ?type as the list (programmer) , and matches the data
(computer)
with ?type as the empty list () .
We can describe the query language's processing of simple queries as follows:
The system finds all assignments to variables in the query pattern that
satisfy
the pattern---that is, all sets of values for the variables
such that if the pattern variables are instantiated with
(replaced
by) the values, the result is in the data base.
The system responds to the query by listing all instantiations of the query
pattern with the variable assignments that satisfy it.
Note that if the pattern has no variables, the query reduces to a determination
of whether that pattern is in the data base. If so, the empty assignment,
which assigns no values to variables, satisfies that pattern for that data
base.
Exercise 4.55: Give simple queries that retrieve
the following information from the data base:
@enumerate
all people supervised by Ben Bitdiddle;
the names and jobs of all people in the accounting division;
the names and addresses of all people who live in Slumerville.
Compound queries
Simple queries form the primitive operations of the query language. In order
to form compound operations, the query language provides means of combination.
One thing that makes the query language a logic programming language is that
the means of combination mirror the means of combination used in forming
logical expressions: and , or , and not . (Here and ,
or , and not are not the Lisp primitives, but rather operations
built into the query language.)
We can use and as follows to find the addresses of all the computer
programmers:
is satisfied by all sets of values for the pattern variables that
simultaneously satisfy ... .
As for simple queries, the system processes a compound query by finding all
assignments to the pattern variables that satisfy the query, then displaying
instantiations of the query with those values.
Another means of constructing compound queries is through or . For
example,
is satisfied by all sets of values for the pattern variables that satisfy at
least one of ... .
Compound queries can also be formed with not . For example,
finds all people supervised by Ben Bitdiddle who are not computer programmers.
In general,
(not )
is satisfied by all assignments to the pattern variables that do not satisfy
.
Actually, this description of not is valid
only for simple cases. The real behavior of not is more complex. We
will examine not 's peculiarities in sections 4-4-2 and
4-4-3.
The final combining form is called lisp-value . When lisp-value
is the first element of a pattern, it specifies that the next element is a Lisp
predicate to be applied to the rest of the (instantiated) elements as
arguments. In general,
(lisp-value ... )
will be satisfied by assignments to the pattern variables for which the
applied to the instantiated ...
is true. For example, to find all people whose salary is
greater than $30,000 we could write
Lisp-value should be used
only to perform an operation not provided in the query language. In
particular, it should not be used to test equality (since that is what the
matching in the query language is designed to do) or inequality (since that can
be done with the same rule shown below).
specifies that two people live near each other if they live in the same town.
The final not clause prevents the rule from saying that all people live
near themselves. The same relation is defined by a very simple
rule:
Notice that we do not need same in order to make two
things be the same: We just use the same pattern variable for each---in effect,
we have one thing instead of two things in the first place. For example, see
?town in the lives-near rule and ?middle-manager in the
wheel rule below. Same is useful when we want to force two
things to be different, such as ?person-1 and ?person-2 in the
lives-near rule. Although using the same pattern variable in two parts
of a query forces the same value to appear in both places, using different
pattern variables does not force different values to appear. (The values
assigned to different pattern variables may be the same or different.)
(rule (same ?x ?x))
The following rule declares that a person is a ``wheel'' in an organization if
he supervises someone who is in turn a supervisor:
We will also allow rules without bodies, as in same , and
we will interpret such a rule to mean that the rule conclusion is satisfied by
any values of the variables.
We can think of a rule as representing a large
(even infinite) set of assertions, namely all instantiations of the rule
conclusion with variable assignments that satisfy the rule body. When we
described simple queries (patterns), we said that an assignment to variables
satisfies a pattern if the instantiated pattern is in the data base. But the
pattern needn't be explicitly in the data base as an assertion. It can be an
implicit assertion implied by a rule. For example, the query
As in the case of compound procedures, rules can be used as parts of other
rules (as we saw with the lives-near rule above) or even be defined
recursively. For instance, the rule
says that a staff person is outranked by a boss in the organization if the boss
is the person's supervisor or (recursively) if the person's supervisor is
outranked by the boss.
Exercise 4.57: Define a rule that says that
person 1 can replace person 2 if either person 1 does the same job as person 2
or someone who does person 1's job can also do person 2's job, and if person 1
and person 2 are not the same person. Using your rule, give queries that find
the following:
all people who can replace Cy D. Fect;
all people who can replace someone who is being paid more than they are,
together with the two salaries.
Exercise 4.58: Define a rule that says that a
person is a ``big shot'' in a division if the person works in the division but
does not have a supervisor who works in the division.
Exercise 4.59: Ben Bitdiddle has missed one
meeting too many. Fearing that his habit of forgetting meetings could cost him
his job, Ben decides to do something about it. He adds all the weekly meetings
of the firm to the Microshaft data base by asserting the following:
Each of the above assertions is for a meeting of an entire division. Ben also
adds an entry for the company-wide meeting that spans all the divisions. All
of the company's employees attend this meeting.
(meeting whole-company (Wednesday 4pm))
On Friday morning, Ben wants to query the data base for all the meetings that
occur that day. What query should he use?
Alyssa P. Hacker is unimpressed. She thinks it would be much more useful to be
able to ask for her meetings by specifying her name. So she designs a rule
that says that a person's meetings include all whole-company meetings
plus all meetings of that person's division. Fill in the body of Alyssa's
rule.
(rule (meeting-time ?person ?day-and-time)
)
Alyssa arrives at work on Wednesday morning and wonders what meetings she has
to attend that day. Having defined the above rule, what query should she make
to find this out?
Exercise 4.60: By giving the query
(lives-near ?person (Hacker Alyssa P))
Alyssa P. Hacker is able to find people who live near her, with whom she can
ride to work. On the other hand, when she tries to find all pairs of people
who live near each other by querying
(lives-near ?person-1 ?person-2)
she notices that each pair of people who live near each other is listed twice;
for example,
Why does this happen? Is there a way to find a list of people who live near
each other, in which each pair appears only once? Explain.
Logic as programs
We can regard a rule as a kind of logical implication: If an assignment
of values to pattern variables satisfies the body, then it satisfies the
conclusion. Consequently, we can regard the query language as having the
ability to perform logical deductions
based upon the rules. As an
example, consider the append operation described at the beginning of
section 4-4. As we said, append can be characterized by the
following two rules:
For any list y , the empty list and y append to form
y .
For any u , v , y , and z , (cons u v) and
y append to form (cons u z) if v and y append to form z .
To express this in our query language, we define two rules for a relation
(append-to-form x y z)
which we can interpret to mean `` x and y append to form
z '':
The first rule has no body, which means that the conclusion holds for any value
of ?y . Note how the second rule makes use of dotted-tail notation to
name the car and cdr of a list.
Given these two rules, we can formulate queries that compute the append
of two lists:
;;; Query input:
(append-to-form (a b) (c d) ?z)
;;; Query results:
(append-to-form (a b) (c d) (a b c d))
What is more striking, we can use the same rules to ask the question ``Which
list, when append ed to (a b) , yields (a b c d) ?'' This is
done as follows:
;;; Query input:
(append-to-form (a b) ?y (a b c d))
;;; Query results:
(append-to-form (a b) (c d) (a b c d))
We can also ask for all pairs of lists that append to form (a b c
d) :
;;; Query input:
(append-to-form ?x ?y (a b c d))
;;; Query results:
(append-to-form () (a b c d) (a b c d))
(append-to-form (a) (b c d) (a b c d))
(append-to-form (a b) (c d) (a b c d))
(append-to-form (a b c) (d) (a b c d))
(append-to-form (a b c d) () (a b c d))
The query system may seem to exhibit quite a bit of intelligence in using the
rules to deduce the answers to the queries above. Actually, as we will see in
the next section, the system is following a well-determined algorithm in
unraveling the rules. Unfortunately, although the system works impressively in
the append case, the general methods may break down in more complex
cases, as we will see in section 4-4-3.
Exercise 4.61: The following rules implement a
next-to relation that finds adjacent elements of a list:
(rule (?x next-to ?y in (?x ?y . ?u)))
(rule (?x next-to ?y in (?v . ?z))
(?x next-to ?y in ?z))
What will the response be to the following queries?
(?x next-to ?y in (1 (2 3) 4))
(?x next-to 1 in (2 1 3 1))
Exercise 4.62: Define rules to implement the
last-pair operation of Exercise 2-17, which returns a list
containing the last element of a nonempty list. Check your rules on queries
such as (last-pair (3) ?x) , (last-pair (1 2 3) ?x) , and
(last-pair (2 ?x) (3)) . Do your rules work correctly on queries such as
(last-pair ?x (3)) ?
Exercise 4.63: The following data base (see
Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way
of Cain:
(son Adam Cain)
(son Cain Enoch)
(son Enoch Irad)
(son Irad Mehujael)
(son Mehujael Methushael)
(son Methushael Lamech)
(wife Lamech Ada)
(son Ada Jabal)
(son Ada Jubal)
Formulate rules such as ``If S is the son of f, and f is the son of
G, then S is the grandson of G'' and ``If W is the wife of
M, and S is the son of W, then S is the son of M'' (which
was supposedly more true in biblical times than today) that will enable the
query system to find the grandson of Cain; the sons of Lamech; the grandsons of
Methushael. (See Exercise 4-69 for some rules to deduce more complicated
relationships.)
How the Query System Works
In section 4-4-4 we will present an implementation of the query
interpreter as a collection of procedures. In this section we give an overview
that explains the general structure of the system independent of low-level
implementation details. After describing the implementation of the
interpreter, we will be in a position to understand some of its limitations and
some of the subtle ways in which the query language's logical operations differ
from the operations of mathematical logic.
It should be apparent that the query evaluator must perform some kind of search
in order to match queries against facts and rules in the data base. One way to
do this would be to implement the query system as a nondeterministic program,
using the amb evaluator of section 4-3 (see Exercise 4-78).
Another possibility is to manage the search with the aid of streams. Our
implementation follows this second approach.
The query system is organized around two central operations called
pattern matching
and unification
. We first describe
pattern matching and explain how this operation, together with the organization
of information in terms of streams of frames, enables us to implement both
simple and compound queries. We next discuss unification, a generalization of
pattern matching needed to implement rules. Finally, we show how the entire
query interpreter fits together through a procedure that classifies expressions
in a manner analogous to the way eval classifies expressions for the
interpreter described in section 4-1.
Pattern matching
A pattern matcher
is a program that tests whether some datum fits a
specified pattern. For example, the data list ((a b) c (a b)) matches
the pattern (?x c ?x) with the pattern variable ?x bound to
(a b) . The same data list matches the pattern (?x ?y ?z) with
?x and ?z both bound to (a b) and ?y bound to
c . It also matches the pattern ((?x ?y) c (?x ?y)) with
?x bound to a and ?y bound to b . However, it does
not match the pattern (?x a ?y) , since that pattern specifies a list
whose second element is the symbol a .
The pattern matcher used by the query system takes as inputs a pattern, a
datum, and a frame
that specifies bindings for various pattern
variables. It checks whether the datum matches the pattern in a way that is
consistent with the bindings already in the frame. If so, it returns the given
frame augmented by any bindings that may have been determined by the match.
Otherwise, it indicates that the match has failed.
For example, using the pattern (?x ?y ?x) to match (a b a) given
an empty frame will return a frame specifying that ?x is bound to
a and ?y is bound to b . Trying the match with the same
pattern, the same datum, and a frame specifying that ?y is bound to
a will fail. Trying the match with the same pattern, the same datum,
and a frame in which ?y is bound to b and ?x is unbound
will return the given frame augmented by a binding of ?x to a .
The pattern matcher is all the mechanism that is needed to process simple
queries that don't involve rules. For instance, to process the query
(job ?x (computer programmer))
we scan through all assertions in the data base and select those that match the
pattern with respect to an initially empty frame. For each match we find, we
use the frame returned by the match to instantiate the pattern with a value for
?x .
Streams of frames
The testing of patterns against frames is organized through the use of streams.
Given a single frame, the matching process runs through the data-base entries
one by one. For each data-base entry, the matcher generates either a special
symbol indicating that the match has failed or an extension to the frame. The
results for all the data-base entries are collected into a stream, which is
passed through a filter to weed out the failures. The result is a stream of
all the frames that extend the given frame via a match to some assertion in the
data base.
Because matching is generally very expensive, we would like
to avoid applying the full matcher to every element of the data base. This is
usually arranged by breaking up the process into a fast, coarse match and the
final match. The coarse match filters the data base to produce a small set of
candidates for the final match. With care, we can arrange our data base so
that some of the work of coarse matching can be done when the data base is
constructed rather then when we want to select the candidates. This is called
indexing
the data base. There is a vast technology built around
data-base-indexing schemes. Our implementation, described in section
4-4-4, contains a simple-minded form of such an optimization.
In our system, a query takes an input stream of frames and performs the above
matching operation for every frame in the stream, as indicated in Figure
4-4. That is, for each frame in the input stream, the query generates a new
stream consisting of all extensions to that frame by matches to assertions in
the data base. All these streams are then combined to form one huge stream,
which contains all possible extensions of every frame in the input stream.
This stream is the output of the query.
Figure 4.4: A query processes a stream of frames.
output stream
input stream +-------------+ of frames,
of frames | query | filtered and extended
---------------->| +------------------------->
| (job ?x ?y) |
+-------------+
^
|
stream of assertions
from data base
To answer a simple query, we use the query with an input stream consisting of a
single empty frame. The resulting output stream contains all extensions to the
empty frame (that is, all answers to our query). This stream of frames is then
used to generate a stream of copies of the original query pattern with the
variables instantiated by the values in each frame, and this is the stream that
is finally printed.
Compound queries
The real elegance of the stream-of-frames implementation is evident when we
deal with compound queries. The processing of compound queries makes use of
the ability of our matcher to demand that a match be consistent with a
specified frame. For example, to handle the and of two queries, such as
(informally, ``Find all people who can do the job of a computer programmer
trainee''), we first find all entries that match the pattern
(can-do-job ?x (computer programmer trainee))
This produces a stream of frames, each of which contains a binding for
?x . Then for each frame in the stream we find all entries that match
(job ?person ?x)
in a way that is consistent with the given binding for ?x . Each such
match will produce a frame containing bindings for ?x and
?person . The and of two queries can be viewed as a series
combination of the two component queries, as shown in Figure 4-5. The
frames that pass through the first query filter are filtered and further
extended by the second query.
Figure 4.5: The and combination of two
queries is produced by operating on the stream of frames in series.
+----------------------+
| (and A B) |
input stream | | output stream
of frames | +---+ +---+ | of frames
------------------->| A +------>| B +-------------------->
| +---+ +---+ |
| ^ ^ |
| | | |
| +-----*-----+ |
+-----------|----------+
|
data base
Figure 4-6 shows the analogous method for computing the or of two
queries as a parallel combination of the two component queries. The input
stream of frames is extended separately by each query. The two resulting
streams are then merged to produce the final output stream.
Figure 4.6: The or combination of two
queries is produced by operating on the stream of frames in parallel and
merging the results.
+---------------------------+
| (or A B) |
| +---+ |
input | +->| A |------------+ | output
stream of | | +---+ V | stream of
frames | | ^ +-------+ | frames
-------------* | | merge +--------------->
| | | +-------+ |
| | | ^ |
| | | +---+ | |
| +------->| B +------+ |
| | +---+ |
| | ^ |
| | | |
| +--*--+ |
+---------|-----------------+
|
data base
Even from this high-level description, it is apparent that the processing of
compound queries can be slow. For example, since a query may produce more than
one output frame for each input frame, and each query in an and gets its
input frames from the previous query, an and query could, in the worst
case, have to perform a number of matches that is exponential in the number of
queries (see Exercise 4-76).
But this kind of exponential
explosion is not common in and queries because the added conditions tend
to reduce rather than expand the number of frames produced.
Though systems for
handling only simple queries are quite practical, dealing with complex queries
is extremely difficult.
There is a large literature on
data-base-management systems that is concerned with how to handle complex
queries efficiently.
From the stream-of-frames viewpoint, the not of some query acts as a
filter that removes all frames for which the query can be satisfied. For
instance, given the pattern
(not (job ?x (computer programmer)))
we attempt, for each frame in the input stream, to produce extension frames
that satisfy (job ?x (computer programmer)) . We remove from the input
stream all frames for which such extensions exist. The result is a stream
consisting of only those frames in which the binding for ?x does not
satisfy (job ?x (computer programmer)) . For example, in processing the
query
the first clause will generate frames with bindings for ?x and
?y . The not clause will then filter these by removing all frames
in which the binding for ?x satisfies the restriction that ?x is
a computer programmer.
There is a subtle difference between this
filter implementation of not and the usual meaning of not in
mathematical logic. See section 4-4-3.
The lisp-value special form is implemented as a similar filter on frame
streams. We use each frame in the stream to instantiate any variables in the
pattern, then apply the Lisp predicate. We remove from the input stream all
frames for which the predicate fails.
Unification
In order to handle rules in the query language, we must be able to find the
rules whose conclusions match a given query pattern. Rule conclusions are like
assertions except that they can contain variables, so we will need a
generalization of pattern matching---called unification
---in which
both the ``pattern'' and the ``datum'' may contain variables.
A unifier takes two patterns, each containing constants and variables, and
determines whether it is possible to assign values to the variables that will
make the two patterns equal. If so, it returns a frame containing these
bindings. For example, unifying (?x a ?y) and (?y ?z a) will
specify a frame in which ?x , ?y , and ?z must all be bound
to a . On the other hand, unifying (?x ?y a) and (?x b ?y)
will fail, because there is no value for ?y that can make the two
patterns equal. (For the second elements of the patterns to be equal,
?y would have to be b ; however, for the third elements to be
equal, ?y would have to be a .) The unifier used in the query
system, like the pattern matcher, takes a frame as input and performs
unifications that are consistent with this frame.
The unification algorithm is the most technically difficult part of the query
system. With complex patterns, performing unification may seem to require
deduction. To unify (?x ?x) and ((a ?y c) (a b ?z)) , for
example, the algorithm must infer that ?x should be (a b c) ,
?y should be b , and ?z should be c . We may think
of this process as solving a set of equations among the pattern components. In
general, these are simultaneous equations, which may require substantial
manipulation to solve.
In one-sided pattern matching, all the
equations that contain pattern variables are explicit and already solved for
the unknown (the pattern variable).
For example, unifying (?x ?x) and
((a ?y c) (a b ?z)) may be thought of as specifying the simultaneous
equations
?x = (a ?y c)
?x = (a b ?z)
These equations imply that
(a ?y c) = (a b ?z)
which in turn implies that
a = a, ?y = b, c = ?z,
and hence that
?x = (a b c)
In a successful pattern match, all pattern variables become bound, and the
values to which they are bound contain only constants. This is also true of
all the examples of unification we have seen so far. In general, however, a
successful unification may not completely determine the variable values; some
variables may remain unbound and others may be bound to values that contain
variables.
Consider the unification of (?x a) and ((b ?y) ?z) . We can
deduce that ?x = (b ?y) and a = ?z , but we cannot further solve
for ?x or ?y . The unification doesn't fail, since it is
certainly possible to make the two patterns equal by assigning values to
?x and ?y . Since this match in no way restricts the values
?y can take on, no binding for ?y is put into the result frame.
The match does, however, restrict the value of ?x . Whatever value
?y has, ?x must be (b ?y) . A binding of ?x to the
pattern (b ?y) is thus put into the frame. If a value for ?y is
later determined and added to the frame (by a pattern match or unification that
is required to be consistent with this frame), the previously bound ?x
will refer to this value.
Another way to think of unification is that
it generates the most general pattern that is a specialization of the two input
patterns. That is, the unification of (?x a) and ((b ?y) ?z) is
((b ?y) a) , and the unification of (?x a ?y) and (?y ?z
a) , discussed above, is (a a a) . For our implementation, it is more
convenient to think of the result of unification as a frame rather than a
pattern.
Applying rules
Unification is the key to the component of the query system that makes
inferences from rules. To see how this is accomplished, consider processing a
query that involves applying a rule, such as
(lives-near ?x (Hacker Alyssa P))
To process this query, we first use the ordinary pattern-match procedure
described above to see if there are any assertions in the data base that match
this pattern. (There will not be any in this case, since our data base
includes no direct assertions about who lives near whom.) The next step is to
attempt to unify the query pattern with the conclusion of each rule. We find
that the pattern unifies with the conclusion of the rule
resulting in a frame specifying that ?person-2 is bound to (Hacker
Alyssa P) and that ?x should be bound to (have the same value as)
?person-1 . Now, relative to this frame, we evaluate the compound query
given by the body of the rule. Successful matches will extend this frame by
providing a binding for ?person-1 , and consequently a value for
?x , which we can use to instantiate the original query pattern.
In general, the query evaluator uses the following method to apply a rule when
trying to establish a query pattern in a frame that specifies bindings for some
of the pattern variables:
Unify the query with the conclusion of the rule to form, if successful, an
extension of the original frame.
Relative to the extended frame, evaluate the query formed by the body of the
rule.
Notice how similar this is to the method for applying a procedure in the
eval / apply evaluator for Lisp:
Bind the procedure's parameters to its arguments to form a frame that extends
the original procedure environment.
Relative to the extended environment, evaluate the expression formed by the
body of the procedure.
The similarity between the two evaluators should come as no surprise. Just as
procedure definitions are the means of abstraction in Lisp, rule definitions
are the means of abstraction in the query language. In each case, we unwind
the abstraction by creating appropriate bindings and evaluating the rule or
procedure body relative to these.
Simple queries