To extend Scheme to support nondeterminism, we introduce a new special form
called amb.
The expression
为了将 Scheme 扩展以支持非确定性 (nondeterminism)，我们引入一种称为 `amb` 的新特殊形式。表达式
returns the value of one of the n expressions ⟨
返回 n 个表达式 ⟨
e
i
⟩
“ambiguously.” For example, the expression
⟩
中某一个的值，以“模棱两可 (ambiguously)”的方式进行选择。例如，表达式
can have six possible values:
共有六个可能的值：
Amb with a single choice produces an ordinary (single) value.
只有单个选择的 `amb` 产生普通的（单一）值。
Amb with no choices—the expression (amb)—is an expression
with no acceptable values. 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:
没有任何选择的 `amb`——即表达式 `(amb)`——是一个没有可接受值的表达式。从操作层面来看，可以将 `(amb)` 视为这样一种表达式：对它求值会使计算“失败 (fail)”——计算中止，不产生任何值。利用这一思想，我们可以如下表达某个谓词表达式 `p` 必须为真的要求：
With amb and require, we can implement the an-element-of
procedure used above:
借助 `amb` 和 `require`，我们可以实现上面用到的 `an-element-of` 过程：
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.
`An-element-of` 在表为空时失败。否则，它以非确定性的方式返回表的第一个元素，或从表的其余元素中选取一个元素。
We can also express infinite ranges of choices. The following procedure
potentially returns any integer greater than or equal to some given n:
我们也可以表达无限范围的选择。下面这个过程可能返回任何大于或等于给定 `n` 的整数：
This is like the stream procedure integers-starting-from described in
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.
这类似于 3.5.2 节中描述的流过程 `integers-starting-from`，但有一个重要区别：流过程返回的是一个表示从 `n` 开始的所有整数序列的对象，而 `amb` 过程返回的是单个整数。
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
从抽象层面看，我们可以想象，对一个 amb 表达式求值会导致时间分裂成若干分支，计算在每条分支上分别以该表达式的某个可能值继续推进。我们说 amb 代表一个
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.
非确定性选择点 (nondeterministic choice point)。如果我们拥有一台配备足够多可动态分配处理器的机器，便可以直接实现这种搜索。执行过程就像在顺序机器上一样推进，直到遇到一个 amb 表达式。此时，系统分配并初始化更多处理器，以继续由该选择所隐含的所有并行执行路径。每个处理器都像自己是唯一的选择一样顺序推进，直到它因遇到失败而终止、或进一步细分、或执行完毕。
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
系统地搜索所有可能的执行路径。我们将在本节开发并使用的 amb 求值器实现了如下系统化搜索：当求值器遇到一个 amb 的应用时，它首先选取第一个备选项。这一选择本身可能又导致进一步的选择。求值器在每个选择点上总是优先选取第一个备选项。若某次选择导致失败，求值器便会自动地 (automagically)
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.
Subheading: Driver loop
回溯到最近的选择点，并尝试下一个备选项。如果在某个选择点上所有备选项都已耗尽，求值器就退回到上一个选择点并从那里继续。这一过程形成了一种被称为深度优先搜索 (depth-first search) 或按时序回溯 (chronological backtracking) 的搜索策略。
小节标题：驱动循环
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 求值器的驱动循环具有一些不寻常的特性。它读入一个表达式并打印第一次无失败执行的值，正如上面所示的 prime-sum-pair 示例那样。如果想查看下一次成功执行的值，可以要求解释器回溯并尝试产生第二次无失败执行。这通过输入符号 try-again 来触发。若给出 try-again 之外的任何表达式，解释器就会开始处理一个新问题，并丢弃前一个问题中尚未探索的备选项。下面是一段交互示例：
(amb ⟨e₁⟩ ⟨e₂⟩ … ⟨eₙ⟩)(list (amb 1 2 3) (amb 'a 'b))(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)(define (require p)
(if (not p) (amb)))(define (an-element-of items)
(require (not (null? items)))
(amb (car items)
(an-element-of (cdr items))))(define (an-integer-starting-from n)
(amb n (an-integer-starting-from (+ n 1))));;; 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)