4.3 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

4.2.

本节通过在求值器中内建自动搜索机制，将 Scheme 求值器扩展为支持一种称为非确定性计算 (nondeterministic computing) 的程序设计范式。与 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 2.2.3 and with infinite streams in

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.

非确定性计算与流处理一样，适用于“生成并检验”类应用。考虑这样一个任务：给定两个正整数表，从第一个表中取一个整数、从第二个表中取一个整数，找出和为素数的整数对。我们在 2.2.3 节用有限序列操作处理过这个问题，在 3.5.3 节又用无限流加以处理。当时的思路是生成所有可能的整数对序列，再对其筛选，保留和为素数的整数对。至于是像第 2 章那样先生成完整的序对序列，还是像第 3 章那样将生成与筛选交织进行，对于计算组织方式的本质图景而言并无差别。

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:

非确定性方法唤起了一幅截然不同的图景。试想我们只是（以某种方式）从第一个表中选一个数、从第二个表中选一个数，然后（借助某种机制）要求它们的和为素数。这可以用下面的过程来表达：

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.

这个过程看起来不过是重新陈述了问题，而非给出求解方法。然而，它确实是一个合法的非确定性程序。

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.

这里的核心思想在于：非确定性语言中的表达式可以拥有多个可能的值。例如，`an-element-of` 可以返回给定表中的任意元素。我们的非确定性程序求值器会自动选择一个可能的值并记录该选择。若随后的某个约束条件不被满足，求值器便尝试另一个选择，如此反复，直到求值成功或穷尽所有选择为止。正如惰性求值器将程序员从值的延迟与强迫的细节中解放出来，非确定性程序求值器也将程序员从如何进行选择的细节中解放出来。

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 求值器，因为它基于一种名为 `amb` 的新特殊形式。我们可以在 amb 求值器的驱动循环中输入上述 `prime-sum-pair` 的定义（连同 `prime?`、`an-element-of` 和 `require` 的定义），并按如下方式运行该过程：

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.

4.3.2 presents examples of nondeterministic programs, and

4.3.3 gives the details of how to implement the amb evaluator by

modifying the ordinary Scheme evaluator.

4.3.1 节介绍 `amb` 并阐释它如何通过求值器的自动搜索机制支持非确定性；4.3.2 节给出非确定性程序的示例；4.3.3 节详细说明如何通过修改普通 Scheme 求值器来实现 amb 求值器。