4.3 Variations on a Scheme: Nondeterministic Computing - CloneableX/SICP-learning GitHub Wiki
在本节，我们将继续扩展 Scheme 求值器，使它支持 非确定性计算（nondeterministic computing） 范式，并在此基础上构建支持自动搜索的系统。此次修改相比惰性求值而言更加精深。
非确定性计算与流相似，在生成及检测方面极其有用。假设存在两个正整数列表并需要分别从两个列表中各取一个整数构成一个整数序对，并且序对中两个整数的和是素数。按之前章节讲述的知识来看，可以通过流或序列收集所有整数序对，再通过筛选排除两数之和不是素数的序对。无论最终是使用序列还是流实现，都是生成数据然后检测筛选，所以数据实现的形式对计算组织的根本情形无关紧要。
不过非确定性计算能够提供另一种组织计算的方式。试想象，我们从第一个列表中选取了一个数字，然后从第二列表中也选取了一个数字，并通过某种机制要求两数之和必须为素数。表达为如下程式。
(define (prime-sum-pair list1 list2)
(let ((a (an-element-of list1))
(b (an-element-of list2)))
(require (prime? (+ a b)))
(list a b)))上述程式看起来只是将问题再次描述了一遍，对于问题的解决并没有任何推进。其实不然，这是一个合法的非确定性计算程序。
其中的关键概念是非确定性计算语言中的表达式会存在多种可能的结果。例如，an-element-of 会返回指定列表中的任意一个元素。我们的非确定性程序求值器能够自动选择数值并保持选择操作的痕迹。如果当前选择结果不符合要求，求值器将尝试选择另一个数值，或者已经完成所有尝试。与惰性求值器向程序员敞开了延迟计算和触发计算的细节一样，非确定性程序求值器会向程序员敞开选择操作的细节。
对比非确定性求值与流计算的时间图景上的差异具有重要的指导意义。流计算通过惰性求值将流的可能性结果收集的时间与实际的流元素计算时间进行了解耦，所以求值器给我们造成了在非时间序列中它的所有可能性结果都已经计算完成的错觉。在非确定性计算中，一个表达式表示通过一系列选择造就的一系列可能情况的探索。某些可能性会走向死胡同，而另一些可能性中却有我们需要的结果。所以非确定性程序求值器会造成时间分支，并且程序拥有不同可能性执行历史的错觉。当我们走进死胡同时，需要回溯前一个选择节点并再次选择另一种可能性分支。
非确定性程序求值器由称为 amb 的求值器实现，它由于基于特殊形式 amb 实现而得名。如果在 amb 求值器的环境中执行 prime-sum-pair 将得到如下效果。
;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))
;;; Starting a new proble
;;; Amb-Eval value:
(3 20)计算结果由求值器在两个列表中不断获得元素，直到产生符合条件的结果的分支产生。
本章节会先介绍 amb 以及解释它如何通过求值器的自动查询机制实现非确定性计算。接着展示一些非确定性程序的例子，最后再讲解如何通过修改原始的 Scheme 求值器实现 amb 求值器。
为了扩展 Scheme 使其支持非确定性求值，需要先了解一个新的特殊形式 amb，语法为 (amb <e1> <e2> ... <en))，返回结果为 n 个表达式中的任意一个。例如，表达式 (list (amb 1 2 3) (amb 'a 'b)) 可能会产生 (1 a) (1 b) (2 a) (2 b) (3 a) (3 b) 这六种情况，所以 amb 就是对结果的一次选择。
如果 amb 中如果没有任何选择（也就是没有传递任何表达式作为参数）它就是一个没有可访问值的表达式。从操作上来说，当求值时出现计算错误（可能是放弃计算或没有值产生），我们便可以将 (amb) 视作一个表达式。利用这个概念，可以通过 (define (require p) (if (not p) (amb))) 表示要求谓词 p 必须为 true。
在 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))))上述程式与流程式 integers-starting-from 极为相似，不过它们之间有一个较大的差异，流程式返回结果为一个以 n 开头包含所有整数的序列对象，而 amb 程式返回的只是一个单独的整数。
更抽象地理解，我们可以认为 amb 表达式计算时会导致时间被分割为不同的分支，当计算中选择某个分支时将产生相应的结果，所以我们认为 amb 表示一个非确定性的选择节点。如果我们拥有一台能够提供充足动态分配的处理器的机器，便可以直接实现类似的搜索。一开始表达式在序列机中执行，当 amb 表达式出现时，需要将其分配给多个处理器，并初始化按不同的选择继续对之前的计算并行执行。每个处理器会按自身的选择执行，直到执行失败或进行下一步选择拆分或完成运算为止。
但如果我们只有一台能够执行一个进程（或较少的并发进程）的机器时，必须考虑其他的顺序执行方案。一种解决方案是当选择节点出现时求值器随机选择一个分支继续计算，但随机选择容易导致错误结果。于是便需要不断通过求值器的随机选择并期望能找到符合条件的结果，但如果能系统性地搜索所有可能的分支将会更好。所以本章要实现的 amb 求值器需要系统性搜索的功能，当求值器遇到 amb 时，起始应选择尚未选择过的可能性中的第一个。这个选择可能将其导向其他的选择，不过求值器在每个选择节点都是同样的选择策略。如果选择产生的结果是失败的，则求值器将自动回溯到最近的选择节点，然后尝试其他的可能性。如果某个选择节点的所有可能性都被穷尽，求值器将返回前一个选择节点并继续同样的计算步骤。这种搜索策略称为 深度优先（depth-first） 搜索或 时间回溯（chronological backtracking）。
amb求值器的驱动循环拥有一些与众不同的属性。它读取表达式并打印首个未失败的执行结果，就像前面的 prime-sum-pair 一样。如果打算查看下一个成功的执行结果，只能命令解释器进行回溯，并尝试生成第二个成功的执行结果，可以通过标识 try-again 发起此命令。如果输入的是 try-again 之外的其他表达式，解释器将开始计算新表达式，并且也不再对之前的表达式的其他可能性进行探索。下面是一些简单的交互。
;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 100))
;;; Starting a new problem
;;; Amb-Eval value:
(3 20)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(3 100)
;;; 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)在下一节会讲解 amb 求值器的具体实现，不过在此之前，我们会先展示使用 amb 求值器的例子。非确定性编程的优势在于我们能够隐藏搜索结果的细节，因此能够在更高维度的抽象中表达程序。
下列谜题是一个谜题大类中的典型。
Baker、Cooper、Fletcher、Miller 和 Smith 住在一个五层公寓的不同楼层。其中 Backer 不住在顶楼，Coopper 不住在一楼，Fletcher 即不住在顶楼也不住在一楼。Miller 住的楼层比 Cooper 的高，Smith 不住在 Fletcher 的相邻楼层，Fletcher 不住在 Cooper 的相邻楼层。请回答他们每个人所居住的楼层。
通过题目中的限制条件我们能够直接枚举每个人可居住楼层的所有可能结果。
(define (multiple-dwelling)
(let ((backer (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 'backer backer) (list 'cooper cooper)
(list 'fletcher fletcher) (list 'millter miller)
(list 'smith smith))))运行 (multiple-dwelling) 表达式的计算结果为 ((backer 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))。尽管程式能够运行但它计算十分慢。
有些程序用于接收并解析自然语言的语法结构。例如，当传入「The cat eats」这个由名词和动词组成的简单句式，程序应该识别句子中的每个词语。所以，首先我们需要提供不同种类词语的列表。
(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* 中的单词移除，并将此单词与它所属的语法分类一起返回。
(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 input:
(parse '(the cat eats))
;;; Starting a new problem
;;; Amb-Eval value:
(sentence (noun-phrase (article the) (noun cat)) (verb eats))解析自然语言中使用 amb 求值器的原因是由于通过它的 require 程式便于表示语法转化的限制条件。不过自动搜索和时间回溯需要在处理更加复杂的语法转化时才会用上，比如对不同短语组合的选择。
接着再添加介词语法列表。
(define preposition '(prep for to in by with))并且定义由介词加名词短语的形式的组合为介词短语。
(define (parse-prepositional-phrase)
(list 'prep-phrase
(parse-word prepositions)
(parse-noun-phrase)))现在我们不仅能够解析名词短语，同时还可以解析带有介词短语的动词短语。
(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 profesor 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 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)))))))原始的 Scheme 求值器只会返回结果、无限循环或因为错误终止。而在非确定性 Scheme 求值器中，表达式的计算结果还有无效结果的可能，这种计算结果导致求值器需要回到前一个选择节点。非确定性 Scheme 解释器也正是因为这种情况变得更加复杂。
我们会基于之前构建的 Scheme 求值器创建 amb 求值器，原先的 Scheme 求值器会对表达式进行分析然后执行。与之相比，非确定性求值器会完全执行整个程式。
原先的求值器执行程式时需要基于执行环境运行。与之不同的是，amb 求值器需要基于环境和两个称为 延续程式（continuation procedures） 程式执行表达式。在计算表达式时调用了任意延续程式都将终止对表达式的计算，如果当前已经产生表达式计算结果则调用 成功延续（success continuation） 程式并将计算结果作为参数传递；反之，则调用 失败延续（failure continuation） 程式。通过调用合适的延续程式是非确定性求值器实现回溯算法的基础。
成功延续程式的功能是接收表达式计算结果，并延续整个计算过程。如果通过表达式计算结果继续进行计算时进入了死胡同，则会将当前的成功延续状态传递给失败延续程式。
失败延续程式的功能是尝试非确定性计算过程中的其他可能性分支。非确定性计算语言的本质就是通过表达式能够表示对多个可能性进行选择的情况。即使尚未知晓哪个选择会导向期望的结果，但每次计算表达式都必须选择其中一种可能性继续推进。为了按描述的步骤进行，首先求值器会选择一种可能性传递给成功延续程式。根据接收数值不同推进计算，如果计算失败将会调用失败延续程式并在稍后选择另一个可能性继续计算。
在计算期间（也就是失败延续被调用期间），如果用户程序明确排除了当前可能性的演算路径（例如，通过 require 计算 (amb)，表达式会呈现失败的情况），则将触发失败情况。失败延续持有最近一次选择节点，并回到最近一次选择节点进行另一种可能性的选择。如果当前选择节点已经没有其他可能性可供选择，则前一个选择节点将触发失败，依照此方式不断推进。失败延续会被驱动循环中输入的 try-again 请求触发，从而计算表达式的另一个可能性结果。
并且，如果一个副作用操作（例如赋值操作）出现在某个选择计算的进程中，当此次计算过程发现无法得到预期结果时，在进行新的选择前需要回滚此次副作用操作。所以副作用操作产生的失败延续必须在回滚副作用操作后再传递失败情况。
总而言之，失败延续通过下列几个要素构成
-
amb表达式：如果当前由amb表达式产生的选择导致非预期结果的产生，则由它提供进行另一个选择的机制 -
顶级驱动：当选择可能性被耗尽时由它提供的机制报告失败情况
-
赋值：在回溯期间由它拦截失败情况并回滚赋值操作
只有在非预期结果出现时失败情况才会被初始化。非预期结果包括下列几种情况。
- 当用户程序执行
(amb)时 - 当用户在顶级驱动中输入
try-again时
失败延续在失败进程中也会被调用。
- 当由赋值对副作用操作回滚后产生失败延续时，调用的失败延续将对失败情况进行拦截，并会将失败传播回引起赋值的选择节点或顶级驱动器。
- 如果失败延续是由
amb耗尽选择可能性产生，则它将调用最初提供给amb的失败延续，并将失败情况传递回前一个选择节点或顶级驱动。
amb 求值器中语法和数据表示程式都以原先的 Scheme 求值器 analyze 程式为基础，除此之外还需要新的语法程式处理 amb 特殊形式。
(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))接着要在 analyze 中添加关于 amb 的处理逻辑。
((amb? exp) (analyze-amb exp))顶级程式 ambeval 会分析指定表达式，并在指定环境和给定的两个延续程式中应用产生的表达式。
(define (ambeval exp env succeed fail)
((analyze exp) env succeed fail))成功延续程式需要两个参数，一个为表达式计算产生的数值，另一个为出现失败情况时调用的失败延续程式。失败延续程式没有参数。所以执行程式的一般形式如下。
(lambda (env succeed fail)
;; succeed is (lambda (value fail) ...)
;; fail is (lambda () ...)
...)例如，按下列方式运行，如果表达式成功将返回表达式的结果，否则将返回标识 failed。当在驱动循环中调用 ambeval 时会对延续程式进行更复杂的使用，我们会在后面展示。
(ambeval <exp>
the-global-environment
(lambda (value fail) value)
(lambda () 'failed))amb 求值器最复杂的情况在于执行程式间互相调用时要不断传递延续情况。为了能够通畅阅读后面的代码，你需要将其与原先的求值器的相应程式对比。
对于较简单的表达式执行 amb 求值器与原始求值器是类似的，不同的部分在于 amb 求值器需要将信息传递给延续程式。一般情况下，都是将表达式结果传递给成功延续程式执行，并将执行时的失败延续程式也传递给成功延续程式。
(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 没有找到对应变量的值，它会抛出错误。但这种失败情况是由于程序缺陷（也就是变量未绑定）造成，并不能说明通过非确定性计算进行另一种选择便能够得到正确结果。
条件表达式的处理方式与原始求值器的处理方式一致。analyze-if 将调用谓词程式（其实是成功延续程式），并检测其结果是否为真，按检测情况调用不同的表达式。如果谓词表达式调用的过程中失败了，则调用 if 表达式的失败延续程式。
(define (analyze-if exp)
(let ((pproc (analyze (if-predicte exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env succeed fail)
(pproc env
;; success continuation for evaluating the predicte
;; to obtain pred-value
(lambda (pred-value fail2)
(if (true? pred-value)
(cproc env succeed fail2)
(aproc env succeed fail2)))
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))))由于需要处理延续程式所以定义变量语法需要采用别的处理方式，因为在实际定义新变量前必须计算定义值的表达式。为了完成定义值的计算需要通过执行环境、成功延续程式和失败延续程式调用，如果定义值计算成功则将计算结果作为定义变量，在变量定义完成后成功将继续传播。
(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))))赋值的处理会比较有趣。在处理赋值时会首次真正使用延续程式，而之前都只是进行传递。赋值逻辑处理的开始阶段与定义变量的处理类似，首先需要计算赋予变量的变量值，如果变量值计算失败则赋值失败。
如果变量值计算成功，则需要考虑后续计算失败的可能性，因为如果当前可能性分支上出现失败情况则需要回溯赋值操作，所以需要将回滚赋值作为回溯过程的一个步骤处理。
为了实现上述功能，提供给计算变量值的成功延续操作上需要在赋新值之前对旧变量值进行保存，然后再继续赋值操作。失败延续程式在继续推进失败进程前需要将存储的旧变量值恢复。并且，成功赋值时会提供一个用于拦截失败情况的失败延续程式；只要发生任何失败情况 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)
(let ((old-value
(lookup-variable-value var env)))
(set-variable-value! var val env)
(succeed 'ok
(lambda ()
(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 处理后续的 aprocs。并通过 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 过程的本质以及追踪延续程式的原因。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 使用非确定性求值器继续尝试未选择过的可能性。在驱动循环中输入 try-again 时internal-loop 将调用 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 导致。