Structure and Interpretation of Computer Programs (80 page)

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.
  

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:
⁵⁶

(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))

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:

(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))

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 () 
...
)
  
...
)

For example, executing

(ambeval <
exp
>
         the-global-environment
         (lambda (value fail) value)
         (lambda () 'failed))

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
.

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.

(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
    (succeed exp fail)))
(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env succeed fail)
      (succeed qval fail))))
(define (analyze-variable exp)
  (lambda (env succeed fail)
    (succeed (lookup-variable-value exp env)
             fail)))
(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence (lambda-body exp))))
    (lambda (env succeed fail)
      (succeed (make-procedure vars bproc env)
               fail))))

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 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.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env succeed fail)
      (pproc env
             
;; success continuation for evaluating the predicate
             
;; to obtain 
pred-value
             (lambda (pred-value fail2)
               (if (true? pred-value)
                   (cproc env succeed fail2)
                   (aproc env succeed fail2)))
             
;; failure continuation for evaluating the predicate
             fail))))

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 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:

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze (definition-value exp))))
    (lambda (env succeed fail)
      (vproc env                        
             (lambda (val fail2)
               (define-variable! var val env)
               (succeed 'ok fail2))
             fail))))

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.
⁵⁷

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
.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze (assignment-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)        
; *1*
               (let ((old-value
                      (lookup-variable-value var env))) 
                 (set-variable-value! var val env)
                 (succeed 'ok
                          (lambda ()    
; *2*
                            (set-variable-value! var
                                                 old-value
                                                 env)
                            (fail2)))))
             fail))))

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.

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env succeed fail)
      (fproc env
             (lambda (proc fail2)
               (get-args aprocs
                         env
                         (lambda (args fail3)
                           (execute-application
                            proc args succeed fail3))
                         fail2))
             fail))))

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: