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

对普通 Scheme 表达式求值，可能返回一个值、可能永不终止、也可能发出一个错误信号。在非确定性 Scheme 中，对表达式求值还可能导致发现一条死路，此时求值必须回溯到先前的某个选择点。这一额外情形使非确定性 Scheme 的解释变得更加复杂。

We will construct the amb evaluator for nondeterministic Scheme by

modifying the analyzing evaluator of 4.1.7. 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.

Subheading: Execution procedures and continuations

我们将通过修改 4.1.7 节的分析式求值器来构造适用于非确定性 Scheme 的 amb 求值器。与分析式求值器一样，对表达式的求值通过调用由该表达式的分析所产生的执行过程来完成。普通 Scheme 的解释与非确定性 Scheme 的解释之间的区别将完全体现在执行过程上。

小节标题：执行过程与续延

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

回顾一下，普通求值器的执行过程接受一个参数：执行时所处的环境。与此相对，amb 求值器的执行过程接受三个参数：环境，以及两个被称为续延过程 (continuation procedures) 的过程。对一个表达式的求值将通过调用这两个续延之一来结束：若求值得到一个值，则以该值调用成功续延 (success continuation)；若求值导致发现一条死路，则

failure continuation is called. Constructing and calling appropriate

continuations is the mechanism by which the nondeterministic evaluator

implements backtracking.

调用失败续延 (failure continuation)。构造并调用适当的续延，正是非确定性求值器实现回溯的机制。

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

失败在求值过程中被触发（即失败续延被调用），发生在用户程序显式拒绝当前攻坚路线时（例如，对 require 的调用可能导致执行 `(amb)`，这是一个始终失败的表达式——参见 4.3.1 节）。此时持有的失败续延将促使最近的选择点选取另一个备选项。若该选择点已无更多备选项可供考虑，则触发更早选择点处的失败，依此类推。驱动循环也会在响应 try-again 请求时调用失败续延，以寻找该表达式的另一个值。

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;

amb 表达式——提供一种机制，以便在当前由 amb 表达式所做的选择导致死路时能够做出备选选择；

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);

用户程序执行 `(amb)` 时；

if the user types try-again at the top-level driver.

Failure continuations are also called during processing of a failure:

用户在顶层驱动输入 try-again 时。

在处理失败的过程中，失败续延也会被调用：

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.

Subheading: Structure of the evaluator

当某个 amb 的失败续延耗尽了所有选择时，它会调用最初传递给该 amb 的失败续延，以便将失败传播回前一个选择点或顶层。

小节标题：求值器的结构

The syntax- and data-representation procedures for the amb evaluator,

and also the basic analyze procedure, are identical to those in the

evaluator of 4.1.7, except for the fact that we need additional

syntax procedures to recognize the amb special form:

amb 求值器的语法和数据表示过程，以及基本的 analyze 过程，与 4.1.7 节求值器中的对应内容完全相同，唯一的区别在于我们需要额外的语法过程来识别 amb 特殊形式：

We must also add to the dispatch in analyze a clause that will recognize

this special form and generate an appropriate execution procedure:

我们还必须在 analyze 的分派中添加一个子句，用于识别这一特殊形式并生成相应的执行过程：

The top-level procedure ambeval (similar to the version of eval

given in 4.1.7) analyzes the given expression and applies the

resulting execution procedure to the given environment, together with two given

continuations:

顶层过程 ambeval（类似于 4.1.7 节给出的 eval 版本）对给定表达式进行分析，并将得到的执行过程应用于给定的环境以及两个给定的续延：

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

成功续延是一个接受两个参数的过程：刚刚获得的值，以及另一个在该值导致后续失败时使用的失败续延。失败续延是一个不接受参数的过程。因此，执行过程的一般形式为

For example, executing

例如，执行

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.

将尝试对给定表达式求值，并返回该表达式的值（若求值成功）或符号 failed（若求值失败）。下面所示的驱动循环中对 ambeval 的调用使用了复杂得多的续延过程，这些过程负责延续循环并支持 try-again 请求。

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

Subheading: Simple expressions

amb 求值器的大部分复杂性来自于在各执行过程相互调用时传递续延的种种机制。在阅读下面的代码时，应将每个执行过程与 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.

最简单的几类表达式的执行过程与普通求值器中的对应过程本质上相同，区别仅在于需要管理续延。这些执行过程直接以表达式的值作为成功结果，并将传递给它们的失败续延原样转交下去。

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.

Subheading: Conditionals and sequences

请注意，查找变量总是"成功"的。如果 lookup-variable-value 找不到该变量，它会像往常一样发出一个错误信号。这样的"失败"表明程序存在错误——引用了一个未绑定的变量；它并非意味着我们应该转而尝试另一个非确定性的选择，以代替当前正在尝试的选择。

小节标题：条件式与序列

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.

条件式的处理方式与普通求值器中相似。由 analyze-if 生成的执行过程以一个成功续延调用谓词执行过程 pproc，该成功续延检查谓词值是否为真，并据此继续执行后件或替代件。若 pproc 的执行失败，则调用 if 表达式原有的失败续延。

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.

序列的处理方式与前一个求值器相同，只是子过程 sequentially 中为传递续延而做的种种安排有所不同。具体而言，为了依次执行 a 然后执行 b，我们以一个成功续延调用 a，该续延再调用 b。

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

定义是另一种需要费心处理续延的情况，因为在实际定义新变量之前，必须先对定义值表达式求值。为此，定义值的执行过程 vproc 以环境、成功续延和失败续延为参数被调用。若 vproc 的执行成功，得到被定义变量的值 val，则该变量被定义，成功状态随之传播：

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.

赋值更为有趣。这是我们真正用到续延而非仅仅传递它的第一处。赋值的执行过程与定义的执行过程开头相同：它首先尝试获取要赋给变量的新值。若对 vproc 的求值失败，则赋值失败。

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.

然而，若 vproc 成功，我们继续执行赋值，就必须考虑到这条计算分支后来可能失败的情况，届时需要回溯并撤销赋值。因此，必须安排在回溯过程中撤销该赋值。

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.

具体做法是：给 vproc 提供一个成功续延（下方以注释 "*1*" 标注），该续延在将新值赋给变量并从赋值处继续之前，先保存变量的旧值。随赋值结果一同传递的失败续延（下方以注释 "*2*" 标注）在继续处理失败之前，先恢复变量的旧值。也就是说，一次成功的赋值会提供一个失败续延，用以拦截后续发生的失败；原本应调用 fail2 的任何失败都将转而调用这个过程，从而在真正调用 fail2 之前撤销赋值。

Subheading: Procedure applications

小节：过程应用

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.

过程应用的执行过程中没有新思想，有的只是管理续延的技术复杂性。这一复杂性出现在 analyze-application 中，源于在对运算对象求值时需要持续追踪成功续延和失败续延。我们使用过程 get-args 来对运算对象的表求值，而非像普通求值器那样简单地使用 map。

In get-args, notice how cdr-ing down the list of aproc

execution procedures and consing 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:

在 get-args 中，请注意：沿 aproc 执行过程的表逐步取 cdr、并将所得参数逐步 cons 成结果表，是通过以成功续延调用表中的每个 aproc 来完成的，该成功续延会递归地调用 get-args。每次递归调用 get-args 所用的成功续延，其值是将新获得的参数 cons 到已积累的参数表之首：

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.

实际的过程应用由 execute-application 执行，其方式与普通求值器相同，只是需要额外管理续延。

Subheading: Evaluating amb expressions

小节：对 amb 表达式求值

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.

amb 特殊形式是非确定性语言的核心要素。在这里，我们看到了解释过程的本质，以及持续追踪续延的原因。amb 的执行过程定义了一个循环 try-next，它遍历 amb 表达式所有可能值的执行过程。每个执行过程被调用时，都附带一个失败续延，该续延会尝试下一个选择。当没有更多可选项时，整个 amb 表达式即告失败。

Subheading: Driver loop

小节：驱动循环

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.

amb 求值器的驱动循环较为复杂，原因在于它提供了一种机制，允许用户在对表达式求值时再次尝试。驱动循环使用名为 internal-loop 的过程，该过程接受一个名为 try-again 的过程作为参数。其意图是：调用 try-again 应在非确定性求值中转向下一个未尝试过的选择。internal-loop 要么在用户于驱动循环中键入 try-again 时调用 try-again，要么通过调用 ambeval 开始一次新的求值。

The failure continuation for this call to ambeval informs the user that

there are no more values and re-invokes the driver loop.

此次调用 ambeval 的失败续延会通知用户已没有更多值，并重新调用驱动循环。

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.

对 ambeval 调用的成功续延更为微妙。它打印所获得的值，然后以一个能够尝试下一个备选项的 try-again 过程再次调用内部循环。这个"下一备选项"过程是传递给成功续延的第二个参数。通常我们将这第二个参数视为在当前求值分支后续失败时使用的失败续延。然而在本情形下，我们已完成了一次成功求值，因而可以调用这个"失败"备选分支，以便搜寻更多成功的求值结果。

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.

对 internal-loop 的初次调用使用了一个 try-again 过程，该过程会报告当前没有正在进行的问题，并重启驱动循环。这就是当用户在没有任何求值进行中时输入 try-again 所触发的行为。