4.3.1 AMB与搜索
为了扩展scheme来支持非确定性，我们介绍一个新的标识符，叫做amb.
表达式(amb <e1> <e2> <e3> <e4> ....<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是一个表达式没有可接受的值。
可操作性的，我们能认为amb是一个表达式，当它引起计算失败时：
计算放弃，没有值产生。使用这个思想,我们能表达这个需要，一个特定的判断
表达式ｐ，是正确的，如下：
(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程序失败。否则，它随机的
返回列表的第一个元素或者是从列表的其它部分中选择一个元素。
我们也能表达选择的无限的范围。如下的程序潜在的返回大于等于
给定数的任何一个数：
(define (an-integer-starting-from n)
(amb n (an-integer-starting-from (+ n 1)))
)
这像在3.5.2部分中描述的流程序an-integer-starting-from，但
是有一个很重要的不同。流程序返回一个对象，它表示从给定数开始
的所有的数的序列，而ａｍｂ程序返回一个单独的整数。
抽象的说，我们能想像到解释一个ａｍｂ表达式，引起了时间分成了片段，
计算在表达式的每个可能的值的片段上继续。我们说ａｍｂ表示了一个非
确定性的选择点。如果我们有一个机器，它有足够多的能被动态分配的处理器，
我们能以正常的方式实现搜索。执行能运行像一个顺序的机器，直到遇到了一
个ａｍｂ表达式。在这一点上，更多的处理器被分配，初始化，为了继续被选择
应用的多个并发的执行。任何一个处理器被顺序执行，好像仅有一个选择，直到
遇到了失败，或者是进入了下一级分支，或者是完成了。
另一个方面，如果我们有一个机器仅能执行一个进程
（或者是一些并发的进程），我们必须考虑顺序地这些分支。
一个能想象修改一个解释器来随机选择一个分支，进入选择点。
然而随机选择，能很容易地导致失败值。我们可能
试图不断地运行解释器，做随机的选择，希望找到一个非失败的值，
但是系统性的搜索所有的可能的执行路径就更好了。
在这部分中我们将开发与使用的ａｍｂ解释器实现了如下的系统的搜索：
当解释器遇到了一个ａｍｂ，它初始化选择第一个分支。这个选择可能本身
导致一个进一步的选择。在任何一个选择点，解释器将总是初始选择
第一个分支。如果一个选择失败了，那么，解释器自动化地回溯到最近的选择点，
并且试尝下一个分支。如果运行完成了任何一个选择点的所有的分支，解释器
将返回到上一个选择点，并从那继续运行。这个过程导致了一个搜索策略，
叫做深度优先搜索。
＊驱动循环
amb解释器的驱动循环有一些非同寻常的特性．它读一个表达式
并且打印第一个非失败的执行的值，正如如上的所示的
prime-sum-pair例子。如果我们要看到下一个成功的执行的值，
我们能要解释器回溯并且试图生成第二个非失败的执行。这能通过
输入符号try-again来实现。如果是除了try-again的其它表达式，
解释器将开始一个新的问题，丢弃之前问题中未探索的选项。这是例子
的交互：
;;; 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)
练习4.35
写一个程序an-integer-between,返回一个区间内的一个整数。
这个程序能被用来实现找勾股定理数的程序。对于三个数，
i<=j,i*i+j*j=k*k如下：
(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-staring-from
来生成勾股定理数是不充分的方式。写一个程序实际地完成这个任务。
（也就是说，写一个程序，在原则上重复try-again,生成所有的勾股定理数）
练习4.37
苯认为如下的方法来生成勾股定理数是比练习4.3５更有效率的，他是对的吗？
(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)
)
)
)
)
)