在本节中，我们将扩展 Scheme 求值器，通过在求值器中内置支持自动搜索的设施，来支持一种称为非确定性计算的编程范式。这是对语言比第 4.2 节引入惰性求值更为深刻的变革。
非确定性计算与流处理一样，对于"生成并测试"应用非常有用。考虑从两个正整数列表出发，找到一个整数对——第一个列表中取一个，第二个列表中取一个——其和为素数的任务。我们在第 2.2.3 节中看到了如何用有限序列操作来处理这个问题，在第 3.5.3 节中用无穷流来处理。我们的方法是生成所有可能对的序列，然后过滤出和为素数的那些对。无论我们是像第 2 章那样首先生成整个对的序列，还是像第 3 章那样将生成和过滤交织进行，对于计算组织的基本图像来说都不重要。
非确定性方法唤起了一个不同的图像。想象一下，我们简单地（以某种方式）从第一个列表中选一个数，从第二个列表中选一个数，然后（使用某种机制）要求它们的和为素数。这由以下过程表达：
(define (prime-sum-pair list1 list2)
(let ((a (an-element-of list1))
(b (an-element-of list2)))
(require (prime? (+ a b)))
(list a b)))
这个过程似乎只是重述了问题，而不是指定了解决它的方法。然而，这是一个合法的非确定性程序。42
这里的关键思想是，在非确定性语言中，表达式可以有多个可能的值。例如，an-element-of 可能返回给定列表中的任意元素。我们的非确定性程序求值器将自动选择一个可能的值并跟踪这个选择。如果后续的要求不满足，求值器将尝试另一个不同的选择，并且它会持续尝试新的选择，直到求值成功，或者直到我们用完所有选择。正如惰性求值器将程序员从值如何延迟和强制求值的细节中解放出来一样，非确定性程序求值器将程序员从选择如何做出的细节中解放出来。
对比非确定性求值和流处理所唤起的不同时间图像是很有启发性的。流处理使用惰性求值来解耦可能答案的流被组装的时间与实际流元素被产生的时间。求值器支持一种幻觉，即所有可能的答案都像一个永恒的时间序列一样展现在我们面前。对于非确定性求值，一个表达式代表了对一组可能世界的探索，每个世界由一组选择决定。一些可能的世界通向死胡同，而另一些则拥有有用的值。非确定性程序求值器支持一种幻觉，即时间会分支，我们的程序有不同的可能执行历史。当我们到达死胡同时，我们可以回到之前的选择点，并沿着不同的分支继续前进。
下面实现的非确定性程序求值器称为 amb 求值器，因为它基于一种称为 amb 的新特殊形式。我们可以在 amb 求值器驱动循环中输入上述 prime-sum-pair 的定义（以及 prime?、an-element-of 和 require 的定义），并按如下方式运行该过程：
;;; Amb-Eval 输入：
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; 开始一个新问题
;;; Amb-Eval 值：
(3 20)
返回的值是在求值器反复从每个列表中选择元素后得到的，直到做出成功的选择。
Section 4.3.1 介绍 amb 并解释它如何通过求值器的自动搜索机制支持非确定性。第 4.3.2 节展示非确定性程序的例子，第 4.3.3 节给出如何通过修改普通 Scheme 求值器来实现 amb 求值器的细节。
为了扩展 Scheme 以支持非确定性，我们引入一种称为 amb 的新特殊形式。43 表达式 (amb <e1> <e2> ... <en>) ``模糊地''返回 n 个表达式 <ei> 中某一个的值。 例如，表达式
(list (amb 1 2 3) (amb 'a 'b))
可以有六种可能的值：
| (1 a) | (1 b) | (2 a) | (2 b) | (3 a) | (3 b) |
Amb 没有选择——即表达式 (amb) ——是一个没有可接受值的表达式。在操作上，我们可以认为 (amb) 是一个在被求值时导致计算"失败"的表达式：计算中止，不产生任何值。利用这个想法，我们可以表达特定谓词表达式 p 必须为真的要求如下：
(define (require p)
(if (not p) (amb)))
利用 amb 和 require，我们可以实现上面使用的 an-element-of 过程：
(define (an-element-of items)
(require (not (null? items)))
(amb (car items) (an-element-of (cdr items))))
An-element-of 在列表为空时失败。否则它模糊地返回列表的第一个元素，或者从列表的其余部分中选择一个元素。
我们还可以表达无穷范围的选择。以下过程可能返回大于或等于某个给定 n 的任何整数：
(define (an-integer-starting-from n)
(amb n (an-integer-starting-from (+ n 1))))
这类似于第 3.5.2 节中描述的流过程 integers-starting-from，但有一个重要的区别：流过程返回一个代表从 n 开始的所有整数序列的对象，而 amb 过程返回单个整数。44
抽象地说，我们可以想象对 amb 表达式求值会导致时间分裂成多个分支，计算在每个分支上以表达式的一个可能值继续进行。我们说 amb 代表了一个非确定性选择点。如果我们有一台拥有足够多可动态分配处理器的机器，我们就可以直接实现搜索。执行将像在顺序机器上一样进行，直到遇到 amb 表达式。此时，更多的处理器将被分配并初始化，以继续选择所隐含的所有并行执行。每个处理器将像它是唯一的选择一样顺序进行，直到它因遇到失败而终止，或者进一步细分，或者完成。45
另一方面，如果我们只有一台只能执行一个进程（或少量并发进程）的机器，我们必须顺序地考虑这些替代方案。可以想象修改求值器，使其在遇到选择点时随机选择一个分支进行。然而，随机选择很容易导致失败的值。我们可以尝试反复运行求值器，做出随机选择，希望能找到一个不失败的值，但更好的方法是系统地搜索所有可能的执行路径。我们在本节中将要开发和使用的 amb 求值器实现了一种系统搜索，如下所示：当求值器遇到 amb 的应用时，它最初选择第一个替代。这个选择本身可能导致进一步的选择。求值器将在每个选择点始终最初选择第一个替代。如果一个选择导致失败，求值器会自动魔法般地46回溯到最近的选择点并尝试下一个替代。如果在任何选择点用完了替代方案，求值器将回退到前一个选择点并从那里继续。这个过程导致了一种称为深度优先搜索或时间顺序回溯的搜索策略。47
amb 求值器的驱动循环有一些不寻常的特性。它读取一个表达式并打印第一个不失败的执行的值，如上所示的 prime-sum-pair 例子。如果我们想看下一个成功执行的值，我们可以要求解释器回溯并尝试生成第二个不失败的执行。这通过键入符号 try-again 来表示。如果输入的是除 try-again 以外的任何表达式，解释器将开始一个新问题，丢弃前一个问题中未探索的替代方案。下面是一个示例交互：
;;; Amb-Eval 输入：
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; 开始一个新问题
;;; Amb-Eval 值：
(3 20)
;;; Amb-Eval 输入：
try-again
;;; Amb-Eval 值：
(3 110)
;;; Amb-Eval 输入：
try-again
;;; Amb-Eval 值：
(8 35)
;;; Amb-Eval 输入：
try-again
;;; 没有更多的值了：
(prime-sum-pair (quote (1 3 5 8)) (quote (20 35 110)))
;;; Amb-Eval 输入：
(prime-sum-pair '(19 27 30) '(11 36 58))
;;; 开始一个新问题
;;; Amb-Eval 值：
(30 11)
练习 4.35. 编写一个过程 an-integer-between，它返回给定两个界限之间的一个整数。这可以用来实现一个寻找毕达哥拉斯三元组的过程，即给定界限之间的整数三元组 (i,j,k)，满足 i < j 且 i2 + j2 = k2，如下所示：
(define (a-pythagorean-triple-between low high)
(let ((i (an-integer-between low high)))
(let ((j (an-integer-between i high)))
(let ((k (an-integer-between j high)))
(require (= (+ (* i i) (* j j)) (* k k)))
(list i j k)))))
练习 4.36. 练习 3.69 讨论了如何生成所有毕达哥拉斯三元组的流，没有搜索整数大小的上界。解释为什么简单地将练习 4.35 过程中的 an-integer-between 替换为 an-integer-starting-from 并不是生成任意毕达哥拉斯三元组的合适方法。编写一个实际上能达到这个目的的过程。（也就是说，编写一个过程，反复键入 try-again 原则上最终能生成所有毕达哥拉斯三元组。）
练习 4.37. Ben Bitdiddle 声称以下生成毕达哥拉斯三元组的方法比练习 4.35 中的方法更高效。他是正确的吗？（提示：考虑必须探索的可能性数量。）
(define (a-pythagorean-triple-between low high)
(let ((i (an-integer-between low high))
(hsq (* high high)))
(let ((j (an-integer-between i high)))
(let ((ksq (+ (* i i) (* j j))))
(require (>= hsq ksq))
(let ((k (sqrt ksq)))
(require (integer? k))
(list i j k))))))
第 4.3.3 节描述了 amb 求值器的实现。不过，我们首先给出一些如何使用它的例子。非确定性编程的优点在于我们可以隐藏搜索如何执行的细节，从而 在更高的抽象层次上表达我们的程序。
以下谜题（取自 Dinesman 1968）是典型的一大类简单逻辑谜题的代表：
Baker、Cooper、Fletcher、Miller 和 Smith 住在一栋只有五层楼的公寓的不同楼层。Baker 不住在顶层。Cooper 不住在底层。Fletcher 既不住在顶层也不住在底层。Miller 住的楼层比 Cooper 高。Smith 住的楼层不与 Fletcher 相邻。Fletcher 住的楼层不与 Cooper 相邻。每个人住在哪里？
我们可以通过枚举所有可能性并施加给定的约束，以一种直接的方式确定谁住在哪一层：48
(define (multiple-dwelling)
(let ((baker (amb 1 2 3 4 5))
(cooper (amb 1 2 3 4 5))
(fletcher (amb 1 2 3 4 5))
(miller (amb 1 2 3 4 5))
(smith (amb 1 2 3 4 5)))
(require
(distinct? (list baker cooper fletcher miller smith)))
(require (not (= baker 5)))
(require (not (= cooper 1)))
(require (not (= fletcher 5)))
(require (not (= fletcher 1)))
(require (> miller cooper))
(require (not (= (abs (- smith fletcher)) 1)))
(require (not (= (abs (- fletcher cooper)) 1)))
(list (list 'baker baker)
(list 'cooper cooper)
(list 'fletcher fletcher)
(list 'miller miller)
(list 'smith smith))))
求值表达式 (multiple-dwelling) 产生结果
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
虽然这个简单的过程能工作，但它非常慢。练习 4.39 和 4.40 讨论了一些可能的改进。
练习 4.38. 修改 multiple-dwelling 过程，去掉 Smith 和 Fletcher 不住在相邻楼层的要求。这个修改后的谜题有多少个解？
练习 4.39. multiple-dwelling 过程中约束的顺序会影响答案吗？会影响找到答案的时间吗？如果你认为有关系，请通过重新排序约束，演示一个比给定程序更快的程序。如果你认为没关系，请论证你的观点。
练习 4.40. 在多住房问题中，在要求楼层分配互不相同之前和之后，人员到楼层的分配集合各有多少个？先生成所有人员到楼层的可能分配，然后留给回溯去消除它们，这是非常低效的。例如，大多数约束只依赖于一两个人员-楼层变量，因此可以在为所有人选定楼层之前就施加它们。编写并演示一个更高效的非确定性过程，它基于只生成那些尚未被先前约束排除的可能性来解决这个问题。（提示：这需要嵌套 let 表达式。）
练习 4.41. 编写一个普通的 Scheme 程序来求解多住房谜题。
练习 4.42. 求解以下"说谎者"谜题（来自 Phillips 1934）：
五位女学生参加了一场考试。她们的父母——她们这样认为——对结果表现出了过度的关心。因此她们约定，在写回家关于考试的信中，每个女孩应该做一个真实的陈述和一个虚假的陈述。以下是她们信中的相关段落：
- Betty："Kitty 考了第二名。我只得了第三名。"
- Ethel："你会很高兴听到我得了第一名。Joan 得了第二名。"
- Joan："我得了第三名，可怜的 Ethel 得了最后一名。"
- Kitty："我得了第二名。Mary 只得了第四名。"
- Mary："我得了第四名。第一名被 Betty 拿走了。"
实际上这五个女孩的排名顺序是怎样的？
练习 4.43. 使用 amb 求值器解决以下谜题：49
Mary Ann Moore 的父亲有一艘游艇，他的四个朋友也各有一艘：Downing 上校、Hall 先生、Barnacle 爵士和 Parker 博士。这五个人每人也有一个女儿，并且每个人都以自己的游艇以其中另一个人的女儿的名字命名。Barnacle 爵士的游艇是 Gabrielle，Moore 先生拥有 Lorna；Hall 先生拥有 Rosalind。Melissa 号由 Downing 上校拥有，是以 Barnacle 爵士的女儿命名的。Gabrielle 的父亲拥有以 Parker 博士的女儿命名的游艇。谁是 Lorna 的父亲？尝试编写程序使其高效运行（见练习 4.40）。另外，如果我们不知道 Mary Ann 的姓是 Moore，确定有多少个解。
练习 4.44. 练习 2.42 描述了"八皇后谜题"，即将皇后放在棋盘上使得没有两个皇后互相攻击。编写一个非确定性程序来解决这个谜题。
设计用于接受自然语言输入的程序通常首先尝试解析输入，即将输入与某种语法结构进行匹配。例如，我们可能尝试识别由冠词后接名词后接动词组成的简单句子，如"The cat eats."。为了完成这样的分析，我们必须能够识别单个单词的词性。我们可以从一些对各类单词进行分类的列表开始：50
(define nouns '(noun student professor cat class))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(article the a))
我们还需要一个语法，即一组描述语法元素如何由更简单的元素组合而成的规则。一个非常简单的语法可以规定一个句子总是由两部分组成——一个名词短语后接一个动词——而一个名词短语由一个冠词后接一个名词组成。按照这个语法，句子"The cat eats"被解析如下：
(sentence (noun-phrase (article the) (noun cat))
(verb eats))
我们可以用一个简单的程序来生成这样的解析，该程序为每个语法规则设置独立的过程。要解析一个句子，我们识别它的两个组成部分并返回这两个元素的列表，用符号 sentence 标记：
(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-word verbs)))
类似地，名词短语通过找到一个冠词后接一个名词来解析：
(define (parse-noun-phrase)
(list 'noun-phrase
(parse-word articles)
(parse-word nouns)))
在最底层，解析归结为反复检查下一个未解析的单词是否属于所需词性的单词列表。为了实现这一点，我们维护一个全局变量 *unparsed*，它保存尚未解析的输入。每次我们检查一个单词时，我们要求 *unparsed* 必须非空，并且它应该以指定列表中的一个单词开头。如果是这样，我们将该单词从 *unparsed* 中移除，并返回该单词及其词性（位于列表的头部）：51
(define (parse-word word-list)
(require (not (null? *unparsed*)))
(require (memq (car *unparsed*) (cdr word-list)))
(let ((found-word (car *unparsed*)))
(set! *unparsed* (cdr *unparsed*))
(list (car word-list) found-word)))
要开始解析，我们需要做的就是将 *unparsed* 设置为整个输入，尝试解析一个句子，并检查没有剩余内容：
(define *unparsed* '())
(define (parse input)
(set! *unparsed* input)
(let ((sent (parse-sentence)))
(require (null? *unparsed*))
sent))
我们现在可以尝试解析器，并验证它对我们的简单测试句子有效：
;;; Amb-Eval 输入：
(parse '(the cat eats))
;;; 开始一个新问题
;;; Amb-Eval 值：
(sentence (noun-phrase (article the) (noun cat)) (verb eats))
amb 求值器在这里很有用，因为借助 require 来表达解析约束很方便。然而，当我们考虑更复杂的语法（其中单位如何分解存在选择）时，自动搜索和回溯才真正体现其价值。
让我们向语法中添加一个介词列表：
(define prepositions '(prep for to in by with))
并定义一个介词短语（例如"for the cat"）为一个介词后接一个名词短语：
(define (parse-prepositional-phrase)
(list 'prep-phrase
(parse-word prepositions)
(parse-noun-phrase)))
现在我们可以定义句子为一个名词短语后接一个动词短语，其中动词短语可以是单个动词，也可以是由介词短语扩展的动词短语：52
(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-verb-phrase)))
(define (parse-verb-phrase)
(define (maybe-extend verb-phrase)
(amb verb-phrase
(maybe-extend (list 'verb-phrase
verb-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-word verbs)))
与此同时，我们还可以详细说明名词短语的定义，以允许"a cat in the class"这样的结构。我们以前称之为名词短语的，现在称之为简单名词短语，而名词短语现在可以是简单名词短语或由介词短语扩展的名词短语：
(define (parse-simple-noun-phrase)
(list 'simple-noun-phrase
(parse-word articles)
(parse-word nouns)))
(define (parse-noun-phrase)
(define (maybe-extend noun-phrase)
(amb noun-phrase
(maybe-extend (list 'noun-phrase
noun-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-simple-noun-phrase)))
我们的新语法让我们可以解析更复杂的句子。例如
(parse '(the student with the cat sleeps in the class))
产生
(sentence
(noun-phrase
(simple-noun-phrase (article the) (noun student))
(prep-phrase (prep with)
(simple-noun-phrase
(article the) (noun cat))))
(verb-phrase
(verb sleeps)
(prep-phrase (prep in)
(simple-noun-phrase
(article the) (noun class)))))
注意，给定的输入可能有多个合法的解析。在句子"The professor lectures to the student with the cat"中，可能是教授带着猫讲课，也可能是学生有猫。我们的非确定性程序找到了两种可能性：
(parse '(the professor lectures to the student with the cat))
产生
(sentence
(simple-noun-phrase (article the) (noun professor))
(verb-phrase
(verb-phrase
(verb lectures)
(prep-phrase (prep to)
(simple-noun-phrase
(article the) (noun student))))
(prep-phrase (prep with)
(simple-noun-phrase
(article the) (noun cat)))))
要求求值器再试一次得到
(sentence
(simple-noun-phrase (article the) (noun professor))
(verb-phrase
(verb lectures)
(prep-phrase (prep to)
(noun-phrase
(simple-noun-phrase
(article the) (noun student))
(prep-phrase (prep with)
(simple-noun-phrase
(article the) (noun cat)))))))
练习 4.45. 使用上面给出的语法，以下句子可以有五种不同的解析方式： "The professor lectures to the student in the class with the cat." 请给出这五种解析，并解释它们之间在含义上的细微差别。
练习 4.46. 第 4.1 节和 4.2 节的求值器不决定操作数的求值顺序。我们将看到 amb 求值器按从左到右的顺序求值它们。解释为什么如果操作数按其他顺序求值，我们的解析程序将无法工作。
练习 4.47. Louis Reasoner 提出，由于动词短语要么是动词，要么是动词短语后接介词短语，因此更直接的方法是如下定义过程 parse-verb-phrase（名词短语也类似）：
(define (parse-verb-phrase)
(amb (parse-word verbs)
(list 'verb-phrase
(parse-verb-phrase)
(parse-prepositional-phrase))))
这样能工作吗？如果我们交换 amb 中表达式的顺序，程序的行为会改变吗？
练习 4.48. 扩展上面给出的语法以处理更复杂的句子。例如，你可以扩展名词短语和动词短语以包含形容词和副词，或者你可以处理复合句。53
练习 4.49. Alyssa P. Hacker 对生成有趣的句子比解析它们更感兴趣。她认为，只需修改过程 parse-word，使其忽略"输入句子"并总是成功且生成一个适当的词，我们就可以用已经为解析构建的程序来做生成。实现 Alyssa 的想法，并展示生成的前大约六个句子。54
对普通 Scheme 表达式的求值可能返回一个值，可能永不终止，或者可能发出错误信号。在非确定性 Scheme 中，表达式的求值还可能发现死胡同，在这种情况下求值必须回溯到先前的选择点。非确定性 Scheme 的解释由于这种额外的情况而变得复杂。
我们将通过修改第 4.1.7 节的分析求值器，来为非确定性 Scheme 构造 amb 求值器。55 与分析求值器一样，表达式的求值通过调用一个由该表达式分析产生的执行过程来完成。普通 Scheme 的解释与非确定性 Scheme 的解释之间的区别将完全体现在执行过程中。
回想普通求值器的执行过程接受一个参数：执行环境。相比之下，amb 求值器中的执行过程接受三个参数：环境，以及两个称为续延过程的过程。表达式的求值将通过调用这两个续延之一来完成：如果求值产生一个值，则用该值调用成功续延；如果求值导致发现死胡同，则调用失败续延。构造和调用适当的续延是非确定性求值器实现回溯的机制。
成功续延的工作是接收一个值并继续计算。沿着该值，成功续延还传递另一个失败续延，如果该值的使用导致死胡同，稍后将调用它。
失败续延的工作是尝试非确定性过程的另一个分支。非确定性语言的本质在于表达式可以表示多个替代方案之间的选择。这种表达式的求值必须选择其中一个指明的替代方案进行，即使事先不知道哪些选择会产生可接受的结果。为了处理这一点，求值器选取一个替代方案并将此值传递给成功续延。与该值一起，求值器还构造并传递一个失败续延，该续延可以在以后被调用以选择不同的替代方案。
当用户程序显式拒绝当前的尝试路径时，求值过程中会触发失败（即调用失败续延）（例如，调用 require 可能导致执行 (amb)，一个总是失败的表达式——参见第 4.3.1 节）。此时手中的失败续延将导致最近的选择点选择另一个替代方案。如果该选择点没有更多可考虑的替代方案，则会触发更早选择点的失败，依此类推。驱动循环也会调用失败续延以响应 try-again 请求，以找到表达式的另一个值。
此外，如果副作用操作（例如给变量赋值）发生在某个选择导致的过程分支上，那么当过程发现死胡同时，可能需要在做出新选择之前撤销该副作用。这通过让副作用操作产生一个失败续延来实现，该续延会撤销副作用并传播失败。
总结来说，失败续延由以下构造：
只会在遇到死胡同时才发起失败。这发生在
失败续延也在处理失败的过程中被调用：
amb 求值器的语法和数据表示过程，以及基本的 analyze 过程，与第 4.1.7 节中求值器的相应过程完全相同，除了我们需要额外的语法过程来识别 amb 特殊形式：56
(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))
我们还必须在 analyze 的分派中添加一个子句，用于识别这种特殊形式并生成适当的执行过程：
((amb? exp) (analyze-amb exp))
顶层过程 ambeval（类似于第 4.1.7 节中给出的 eval 版本）分析给定的表达式，并将得到的执行过程应用于给定的环境，以及两个给定的续延：
(define (ambeval exp env succeed fail)
((analyze exp) env succeed fail))
成功续延是一个接受两个参数的过程：刚获得的值和另一个失败续延，如果该值导致后续失败则使用它。失败续延是一个不接受参数的过程。因此执行过程的通用形式为
(lambda (env succeed fail)
;; succeed is (lambda (value fail) ...)
;; fail is (lambda () ...)
...)
例如，执行
(ambeval <exp>
the-global-environment
(lambda (value fail) value)
(lambda () 'failed))
将尝试求值给定的表达式，并返回表达式的值（如果求值成功）或符号 failed（如果求值失败）。下面所示的驱动循环中对 ambeval 的调用使用了更复杂的续延过程，这些过程继续循环并支持 try-again 请求。
amb 求值器的大部分复杂性来自于在执行过程相互调用时传递续延的机制。在阅读以下代码时，你应该将每个执行过程与第 4.1.7 节中给出的普通求值器的相应过程进行比较。
最简单类型的表达式的执行过程与普通求值器的执行过程基本相同，除了需要管理续延。执行过程简单地用表达式的值成功，并传递传递给它们的失败续延。
(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))))
注意，查找变量总是"成功"的。如果 lookup-variable-value 找不到该变量，它会像往常一样发出一条错误信号。这种"失败"指示了一个程序 bug——引用未绑定的变量；这并不是我们应该尝试另一个非确定性选择而不是当前正在尝试的选择的指示。
条件表达式也以与普通求值器类似的方式处理。analyze-if 生成的执行过程调用谓词执行过程 pproc，并传入一个成功续延，该续延检查谓词值是否为真，然后继续执行分支或替代分支。如果 pproc 的执行失败，则调用 if 表达式的原始失败续延。
(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))))
序列也以与先前求值器相同的方式处理，除了子过程 sequentially 中为传递续延所需的复杂操作。也就是说，要顺序执行 a 然后 b，我们调用 a 并传入一个成功续延，该续延会调用 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))))
定义是另一个我们必须花些功夫来管理续延的情况，因为有必要在实际定义新变量之前求值定义值表达式。为了实现这一点，定义值执行过程 vproc 被调用时传入环境、一个成功续延和失败续延。如果 vproc 的执行成功，为被定义的变量获得一个值 val，则变量被定义，并且成功被传播：
(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))))
赋值更有趣。这是第一个我们真正使用续延（而不仅仅是传递它们）的地方。赋值的执行过程开始类似于定义。它首先尝试获得要赋给变量的新值。如果这个 vproc 的求值失败，赋值失败。
然而，如果 vproc 成功，我们继续执行赋值，我们必须考虑计算的这个分支之后可能失败的可能性，这将要求我们回溯出该赋值。因此，我们必须安排撤销赋值作为回溯过程的一部分。57
这是通过给予 vproc 一个成功续延（下面用注释"*1*"标记）来实现的，该续延在将新值赋给变量并从赋值继续之前保存变量的旧值。与赋值的值一起传递的失败续延（下面用注释"*2*"标记）在继续失败之前恢复变量的旧值。也就是说，成功的赋值提供了一个将拦截后续失败的失败续延；任何原本会调用 fail2 的失败都会调用这个过程，以便在真正调用 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))))
应用的执行过程除了管理续延的技术复杂性外，不包含新的想法。这种复杂性出现在 analyze-application 中，因为当我们在求值操作数时需要跟踪成功和失败续延。我们使用一个过程 get-args 来求值操作数列表，而不是像普通求值器中那样使用简单的 map。
(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))))
在 get-args 中，注意通过对列表中的每个 aproc 调用一个成功续延（递归调用 get-args）来向下遍历 aproc 执行过程列表并向上构建结果 args 列表。这些对 get-args 的递归调用中的每一个都有一个成功续延，其值是将新获得的参数 cons 到累积参数列表上：
(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)))
实际的过程应用由 execute-application 执行，其完成方式与普通求值器相同，除了需要管理续延。
(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 特殊形式是非确定性语言中的关键元素。这里我们看到了解释过程的本质以及跟踪续延的原因。amb 的执行过程定义了一个循环 try-next，该循环遍历 amb 表达式所有可能值的执行过程。每个执行过程被调用时都带有一个将尝试下一个的失败续延。当没有更多替代方案可尝试时，整个 amb 表达式失败。
(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))))
amb 求值器的驱动循环是复杂的，因为它有允许用户在求值表达式中再试一次的机制。驱动使用一个名为 internal-loop 的过程，它接受一个名为 try-again 的过程作为参数。其意图是调用 try-again 应该继续非确定性求值中的下一个未尝试的替代方案。Internal-loop 要么响应用户在驱动循环中输入 try-again 而调用 try-again，要么通过调用 ambeval 开始新的求值。
对这个 ambeval 调用的失败续延告知用户没有更多值并重新调用驱动循环。
对 ambeval 调用的成功续延更微妙。我们打印获得的值，然后再次调用内部循环，传入一个能够尝试下一个替代方案的 try-again 过程。这个 next-alternative 过程是传递给成功续延的第二个参数。通常，我们将这第二个参数视为失败续延，如果当前求值分支之后失败则使用它。然而在这种情况下，我们已经完成了一次成功的求值，所以我们可以调用"失败"替代分支来搜索额外的成功求值。
(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))))
对 internal-loop 的初始调用使用了一个 try-again 过程，该过程抱怨没有当前问题并重新启动驱动循环。如果用户在没有进行求值时输入 try-again，就会发生这种行为。
练习 4.50. 实现一个新的特殊形式 ramb，它与 amb 类似，但它以随机顺序搜索替代方案，而不是从左到右。展示这如何有助于解决练习 4.49 中 Alyssa 的问题。
练习 4.51. 实现一种称为 permanent-set! 的新赋值，它在失败时不会被撤销。例如，我们可以从一个列表中选择两个不同的元素，并计数成功选择所需的尝试次数如下：
(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))
;;; 开始一个新问题
;;; Amb-Eval 值：
(a b 2)
;;; Amb-Eval 输入：
try-again
;;; Amb-Eval 值：
(a c 3)
如果我们在这里使用 set! 而不是 permanent-set!，会显示什么值？
练习 4.52. 实现一种称为 if-fail 的新构造，它允许用户捕获表达式的失败。If-fail 接受两个表达式。它照常求值第一个表达式，如果求值成功则照常返回。然而，如果求值失败，则返回第二个表达式的值，如以下示例所示：
;;; Amb-Eval 输入：
(if-fail (let ((x (an-element-of '(1 3 5))))
(require (even? x))
x)
'all-odd)
;;; 开始一个新问题
;;; Amb-Eval 值：
all-odd
;;; Amb-Eval 输入：
(if-fail (let ((x (an-element-of '(1 3 5 8))))
(require (even? x))
x)
'all-odd)
;;; 开始一个新问题
;;; Amb-Eval 值：
8
练习 4.53. 使用练习 4.51 中描述的 permanent-set! 和练习 4.52 中的 if-fail，求值以下表达式的结果是什么
(let ((pairs '()))
(if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110))))
(permanent-set! pairs (cons p pairs))
(amb))
pairs))
练习 4.54. 如果我们没有意识到 require 可以作为一个使用 amb 的普通过程来实现（由用户作为非确定性程序的一部分来定义），我们就不得不将其实现为一种特殊形式。这需要语法过程
(define (require? exp) (tagged-list? exp 'require))
(define (require-predicate exp) (cadr exp))
以及在 analyze 的分派中添加一个新子句
((require? exp) (analyze-require exp))
以及处理 require 表达式的过程 analyze-require。完成以下的 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 我们假设我们已经定义了一个检测数字是否为素数的过程 prime?。即使定义了 prime?，prime-sum-pair 过程可能看起来可疑地类似于我们曾在第 1.1.7 节开头描述的无用的"伪 Lisp"定义平方根函数的尝试。事实上，按照这种方式的确可以将平方根过程表述为一个非确定性程序。通过将搜索机制整合到求值器中，我们正在侵蚀纯声明式描述与关于如何计算答案的命令式规范之间的区别。我们将在第 4.4 节中朝这个方向走得更远。
43 用于非确定性编程的 amb 的思想由 John McCarthy 于 1961 年首次描述（见 McCarthy 1967）。
44 实际上，非确定性地返回单个选择与返回所有选择之间的区别在某种程度上取决于我们的观点。从使用该值的代码的角度来看，非确定性选择返回单个值。从设计代码的程序员的角度来看，非确定性选择可能返回所有可能的值，并且计算分支使得每个值被单独考察。
45 有人可能会反对，说这是一种无望的低效机制。它可能需要数百万个处理器才能以这种方式解决一些容易陈述的问题，而且大部分时间这些处理器中大多数将处于空闲状态。这种反对意见应放在历史的背景下来看待。内存曾经被认为正是这样一种昂贵的商品。在 1964 年，一兆字节的 RAM 大约价值 40 万美元。现在每台个人计算机都有许多兆字节的 RAM，而且大部分时间这些 RAM 中的大部分都未被使用。大规模生产的电子产品的成本再怎么低估也不为过。
46 自动化魔法："自动地，但以一种出于某种原因（通常是因为太复杂、太丑陋，或者可能太琐碎）说话者不想解释的方式。"（Steele 1983，Raymond 1993）
47 将自动搜索策略整合到编程语言中有着漫长而曲折的历史。最早提出非确定性算法可以优雅地编码在具有搜索和自动回溯功能的编程语言中的建议来自Robert Floyd（1967）。Carl Hewitt（1969）发明了一种名为 Planner 的编程语言，它显式支持自动时间顺序回溯，提供内置的深度优先搜索策略。Sussman、Winograd 和 Charniak（1971）实现了该语言的一个子集，称为 MicroPlanner，用于支持问题求解和机器人规划方面的工作。源于逻辑和定理证明的类似思想，导致了在爱丁堡和马赛产生了优雅的 Prolog 语言（我们将在第 4.4 节中讨论）。在对自动搜索经历了足够多的挫折之后，McDermott 和 Sussman（1972）开发了一种名为 Conniver 的语言，它包含了将搜索策略置于程序员控制之下的机制。然而，这被证明是笨重的，Sussman 和 Stallman（1975）在研究电路符号分析方法时发现了一种更易处理的方法。他们开发了一种非时间顺序的回溯方案，该方案基于追踪连接事实的逻辑依赖关系，这种技术后来被称为 依赖导向回溯。虽然他们的方法复杂，但产生了相当高效的程序，因为它做了很少的冗余搜索。Doyle（1979）和 McAllester（1978，1980）推广并澄清了 Stallman 和 Sussman 的方法，发展出了一种现在称为 真值维护 的表述搜索的新范式。现代问题求解系统都使用某种形式的真值维护系统作为基础。关于构建真值维护系统的优雅方式及使用真值维护的应用的讨论，见 Forbus 和 deKleer 1993。Zabih、McAllester 和 Chapman 1987 描述了一种基于 amb 的 Scheme 非确定性扩展；它类似于本节描述的解释器，但更复杂，因为它使用依赖导向回溯而非时间顺序回溯。Winston 1992 介绍了这两种回溯。
48 我们的程序使用以下过程来确定列表的元素是否互不相同：
(define (distinct? items)
(cond ((null? items) true)
((null? (cdr items)) true)
((member (car items) (cdr items)) false)
(else (distinct? (cdr items)))))
Member 类似于 memq，不同之处在于它使用 equal? 而不是 eq? 来测试相等性。
49 这取自一本名为《Problematical Recreations》的小册子，由 Litton Industries 在 20 世纪 60 年代出版，其中将其归功于《Kansas State Engineer》。
50 这里我们使用约定，每个列表的第一个元素指定列表中其余单词的词性。
51 注意 parse-word 使用 set! 来修改未解析的输入列表。为了使其工作，我们的 amb 求值器必须在回溯时撤销 set! 操作的效果。
52 注意这个定义是递归的——一个动词后面可以跟任意数量的介词短语。
53 这种语法可以变得任意复杂，但就真正的语言理解而言，它只是一个玩具。计算机真正理解自然语言需要语法分析和意义解释的复杂混合。另一方面，即使是玩具解析器也可以在支持信息检索系统等程序的灵活命令语言方面发挥作用。Winston 1992 讨论了真实语言理解的计算方法，以及简单语法在命令语言中的应用。
54 虽然 Alyssa 的想法工作得很好（并且出奇地简单），但它生成的句子有点无聊——它们没有以非常有趣的方式采样这种语言的可能句子。事实上，语法在许多地方是高度递归的，而 Alyssa 的技术会"落入"这些递归之一并卡住。参见练习 4.50 了解处理此问题的方法。
55 我们选择将第 4.2 节中的惰性求值器实现为对第 4.1.1 节中普通元循环求值器的修改。相比之下，我们将基于第 4.1.7 节的分析求值器来构建 amb 求值器，因为该求值器中的执行过程为实现回溯提供了方便的框架。