非确定性计算

1961年，Lisp语言的发明者John McCarthy提出了非确定性程序设计的思想。设想一下，如果我们有一个算子称为amb(iguous)，它的行为如下：

1. 有参数的时候不确定地返回其中一个参数；
2. 没有参数的时候对它的求值则将导致失败；
3. 如果其子表达式有一个可达，则表达式必须有返回值。

所以：

1. 求值(amb 1 2) 将返回1或者2；
2. 求值(amb)将导致失败；
3. 求值(amb 1 (amb))必然返回1。

这里有对amb的解释、示例和一个在scheme语言中的简单实现。有了amb后，我们可以思考下面一个简单的数学问题：如果 2 <= x, y, z <=9，有哪些x, y, z可以使得x的平方是y和z的平方和？

(define (require p)
(if (not p) (amb)))

(define in-range
(lambda (a b)
  (require (< a b))
  (amb a (in-range (+ a 1) b))))

(let ((x (in-range 2 9))
    (y (in-range 2 9))
    (z (in-range 2 9)))
(require (= (* x x)
            (+ (* y y) (* z z))))
(list x y z))

对上面的表达是求值，将会得到（5 3 4)，再求值(amb)将得到(5 4 3) ，再次求值则会得到错误报告：(error "amb tree exhausted")。这两组数正是我们需要的结果。