Structure and Interpretation of Computer Programs (81 page)
Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
(define (get-args aprocs env succeed fail)
(if (null? aprocs)
(succeed '() fail)
((car aprocs) env
;; success continuation for this
aproc
(lambda (arg fail2)
(get-args (cdr aprocs)
env
;; success continuation for recursive
;; call to
get-args
(lambda (args fail3)
(succeed (cons arg args)
fail3))
fail2))
fail)))
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.
(define (execute-application proc args succeed fail)
(cond ((primitive-procedure? proc)
(succeed (apply-primitive-procedure proc args)
fail))
((compound-procedure? proc)
((procedure-body proc)
(extend-environment (procedure-parameters proc)
args
(procedure-environment proc))
succeed
fail))
(else
(error
"Unknown procedure type -- EXECUTE-APPLICATION"
proc))))
amb
expressions
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.
(define (analyze-amb exp)
(let ((cprocs (map analyze (amb-choices exp))))
(lambda (env succeed fail)
(define (try-next choices)
(if (null? choices)
(fail)
((car choices) env
succeed
(lambda ()
(try-next (cdr choices))))))
(try-next cprocs))))
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
(let ((pairs '()))
(if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110))))
(permanent-set! pairs (cons p pairs))
(amb))
pairs))
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
(define (require? exp) (tagged-list? exp 'require))
(define (require-predicate exp) (cadr exp))
and a new clause in the dispatch in
analyze
((require? exp) (analyze-require exp))
as well the procedure
analyze-require
that handles
require
expressions. Complete the following definition of
analyze-require
.
(define (analyze-require exp)
(let ((pproc (analyze (require-predicate exp))))
(lambda (env succeed fail)
(pproc env
(lambda (pred-value fail2)
(if <
??
>
<
??
>
(succeed 'ok fail2)))
fail))))
42
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
.
43
The idea of
amb
for nondeterministic programming was
first described in 1961 by John McCarthy (see McCarthy 1967).
44
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.
45
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.
46
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)
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.
48
Our program uses the following procedure to determine
if the elements of a list are distinct:
(define (distinct? items)
(cond ((null? items) true)
((null? (cdr items)) true)
((member (car items) (cdr items)) false)
(else (distinct? (cdr items)))))
Member
is like
memq
except that it uses
equal?
instead
of
eq?
to test for equality.
49
This is taken from a booklet called “Problematical
Recreations,” published in the 1960s by Litton Industries, where it
is attributed to the
Kansas State Engineer
.
50
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.
51
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.
52
Observe that this
definition is recursive – a verb may be followed by any number
of prepositional phrases.
53
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.
54
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.
55
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.
56
We assume that the evaluator supports
let
(see exercise
4.22
),
which we have used in our nondeterministic programs.
57
We didn't worry about undoing definitions, since we can
assume that internal definitions are scanned out
(section
4.1.6
).