讲故事并不是我擅长的事情，不过事情总有一个开始，诸位看官莫嫌我絮烦，只是希望可以讲述的更有条理一些。某日正读一本关于Erlang的书，书中出了一个关于八皇后的题目，这是计算机科学中经典的问题，当年上学时曾绞尽脑汁仍然云山雾罩，不得其解。如今再次相遇，岂能再坐壁上观？！更何况手边已有趁手的兵器。试看Erlang的实现：
-module(queens).
-export([queens/1]).
queens(0) -> [[]];
queens(N) ->
[[Row | Columns] || Columns <- queens(N - 1),
Row <- lists:seq(1, 8) -- Columns,
safe(Row, Columns, 1)].
safe(_Row, [], _N) -> true;
safe(Row, [Column | Columns], N) ->
(Row /= Column + N) andalso (Row /= Column - N) andalso safe(Row, Columns, (N + 1)).
从头至尾10行代码，如果不是为了使代码美观，6行足矣（这还包括了**-module** 和**-export** 两行声明语法，与算法本身无关的代码）。如此简短尽然可以清晰地实现复杂的八皇后 问题，如果采用命令式程序语言得写多少行？本文的重点不在于比较这个，Erlang是一门非常强大的语言，对于我来说Erlang好比探春，但是Scheme才是林黛玉呀，所以毫不迟疑用Scheme来实现：
(define (accumulate op initial sequence)
(if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))
)
(define (enumerate-interval low high)
(if (> low high) '() (cons low (enumerate-interval (+ low 1) high)))
)
(define (flatmap proc seq)
(accumulate append '() (map proc seq))
)
(define empty-board '())
(define (safe? k position)
(let loop ([new-queen (car position)] [rest-queens (cdr position)] [i 1])
(if (null? rest-queens) #t
(let ([rest-current-queen (car rest-queens)])
(if
(or
(= new-queen rest-current-queen)
(= new-queen (+ rest-current-queen i))
(= new-queen (- rest-current-queen i))
) #f
(loop new-queen (cdr rest-queens) (+ i 1))
)
)
)
)
)
(define (adjoin-position new-row k rest-of-queens)
(cons new-row rest-of-queens)
)
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (position) (safe? k position)) ;过滤无效的解
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row) ;扩充（k-1）个皇后的每一个解，给每个解都增加第k个皇后
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)
)
)
(queen-cols (- k 1)) ;前（k-1）个有效的皇后，虽然是太虚幻境，但可以认为是事实
)
)
)
)
(queen-cols board-size)
)
Scheme版本比Erlang版本代码增加了不少，原因在于其没有模式匹配 和列表推导 这两大利器，不过我更喜欢Scheme强大的表现力，可以随心所欲地构造我需要的一切，而且S-表达式看起来十分优美自然。Scheme版本实际上解决了n-皇后，更进一步了。
事情到这里并没有结束，原因在于我刚开始实现Scheme版本的八皇后时，选择翻译Erlang代码，最终失败了！一番挣扎之后，意识到该问题属于非确定性计算，猛然想起《SICP》中有一节专门介绍了此种计算，也即本文的主角——amb
非确定性计算
amb这个名字源于ambiguous ,其含义并不是很好理解。一番披肝沥胆之后，终于窥到了一些门径，趁机厘清很多知识点。我将尽力平铺直述，简要的介绍这种强大且十分有用的武器。
首先，我们来观察一个问题：
假设有两个数组，数组中都是一些正整数，比如l1 = [1 2 3 4 5], l2 = [3 4 6 7 8]，我们分别从l1和l2中各取一个数字，相加之后，如果是素数，则满足要求。怎么办呢？
对于这个简单的问题，相信难不倒大家，采用回溯算法轻易就解决了，这里只是想引出“非确定性计算”的概念。非确定性计算和流处理类似，对于“生成和检测式”的应用特别有价值，它往往只描述问题，但没有描述问题的解决方法，这句话很有意思，如果暂时没有理解不用着急，继续往下看。
对于非确定性计算，首先需要明确的一点是，表达式是允许存在多个值的，比如上面的问题的解至少有(1 4),(2 3)两个解吧。
有一件很有教益的事情，那就是非确定性计算和流处理对于时间的不同看法。流处理利用了惰性求值，这会给我们一种错觉，仿佛所有可能的结果的出现没有时间顺序；对于非确定性的求值，一个表达式是对一个可能的世界的探索，每一个值都由一次选择所确定，某些选择会走入死胡同，而另一些会得到有用的值，所以非确定性计算给我们的感觉是，时间是有分支的。程序当中会保存所有可能的不同执行历史，在遇到一个死胡同时，总是可以回到以前的选择点，并沿着另一个分支继续下去。
下面将要实现的非确定性求值器称为——amb求值器
amb求值器
假设目前已经扩充了Scheme以支持非确定性计算，引入了一种新的称为amb的新形式，表达式 $(amb <e_1> <e_2> … <e_n>)$ 会“有歧义地”返回n个表达式之一的值，比如：
(list (amb 1 2 3) (amb 'a 'b))
可以有如下6个可能的值： (1 a) (1 b) (2 a) (2 b) (3 a) (3 b)
对于没有选项的amb，即(amb) ——视为没有可接收值的表达式，这将导致求值“fail”。
amb求值器在每个选择点，总是选择第一个可能性，如果选择的结果失败，那么求值器自动地回溯到最近的选择点，去尝试下一个可能性。如果它用完了所以的可能性，则自动退回到上一个选择点，并从那里继续（这个“继续”很有意思，后文会看到，“继续”不但是结论，还是其实现的方式，一语双关）下去。从这个过程可以看出，这是一种深度优先 算法。
逻辑谜题
在讨论amb求值器的实现之前，先看一道逻辑谜题：
曹操、孙权、刘备、袁绍、马超5人住在一栋5层的楼房里面，每人住一层。曹操不住顶层，孙权不住底层，刘备不住顶层也不住底层，袁绍比刘备高一层，马超与刘备不在相邻的楼层，刘备与孙权也不在相邻的楼层，请问他们各住在哪一层？
在没有amb时，代码怎么写呢？恐怕不容易吧。但是现在有了amb求值器，瞬间美好了：
(define (multiple-dwelling)
(let (
[caocao (amb 1 2 3 4 5)]
[sunquan (amb 1 2 3 4 5)]
[liubei (amb 1 2 3 4 5)]
[yuanshao (amb 1 2 3 4 5)]
[machao (amb 1 2 3 4 5)]
)
(require (distinct? (list caocao sunquan liubei yuanshao machao)))
(require (not (= caocao 5)))
(require (not (= sunquan 1)))
(require (not (= liubei 5)))
(require (not (= liubei 1)))
(require (> yuanshao liubei))
(require (not (= (abs (- machao liubei)) 1))
(require (not (= (abs (- sunquan liubei)) 1))
(list (list 'caocao caocao) (list 'sunquan sunquan) (list 'liubei liubei)
(list 'yuanshao yuanshao) (list 'machao machao))
)
)
上述代码只是描述问题的关系，即各个require部分（先不考虑性能问题。还记得上文提到的“描述问题，但没有描述问题的解决方法”吗？），并没有添加什么“处理逻辑”，但是会产生下面结果：
((caocao 3) (sunquan 2) (liubei 4) (yuanshao 5) (machao 1))
居然得到了谜题的解，这是什么魔法？？？
amb轻而易举地解决了这种需要大量回溯的问题。
实现
现在该谈一谈神奇的amb如何实现了吧。前文已经多次提到过，amb求值的过程可能会不断的回溯，这势必导致程序流程的跳转，程序跳转该怎么办呢？函数式语言可没有break,continue之类的语法，因为根本不需要，那么函数式语言有啥？答案是continuation(翻译成继续，或者延续都可以。还记得“一语双关”吗？)
Scheme内置了这个强大的控制抽象，过程名为：call-with-current-continuation， 名字略长，不过一般都是用其缩写：call/cc。囿于篇幅，本文不打算介绍continuation，如果想详细了解它，请自行搜索。
常规求值器的执行过程有一个参数：执行环境env。amb求值器的执行过程有三个参数，除了执行环境env之外，还有两个continuation过程（一个成功延续、一个失败延续）。对一个表达式进行求值，结束后会调用这两个continuation过程之一：如果此次求值得到了一个结果，则调用成功延续；如果结果是遇到了死胡同，则调用失败延续。
成功延续的工作是：接受一个值，并将计算进行去下，与这个值一起，成功延续过程还将得到一个另一个失败延续，如果使用该值时遇到了死胡同，则需要调用这个失败延续。
失败延续的工作是：试探非确定性过程的另一个分支。非确定性计算的最关键的特征，在于表达式可以表示于不同可能性之间的选择。
我承认有点烧脑，但还算清晰，让递归在脑海中奔涌吧。
利用宏来简化amb的构造，代码参考这里：
(define amb-fail '*)
(define initialize-amb-fail
(lambda ()
(set! amb-fail
(lambda ()
(error "amb tree exhausted")))))
(initialize-amb-fail)
(define-syntax amb
(syntax-rules ()
((amb alt ...)
(let ((prev-amb-fail amb-fail)) ;保存前一个选择点
(call/cc
(lambda (sk) ;对于整个amb表达式构造一个sk的contnuation
(call/cc
(lambda (fk) ;对于每一个amb的选项构造一个fk的continuation
(set! amb-fail ;先把amb-fail设置为一个函数，该函数可将amb-fail恢复到进入amb前的值
(lambda ()
(set! amb-fail prev-amb-fail)
(fk 'fail))
)
(sk alt) ;立即返回自己的分支的值,从而引起amb表达式中途返回。注意，每一个分支执行时都会引起 amb 立即返回。后面的分支都还没有执行！
)
) ...
(prev-amb-fail)
)
)
)
)
)
)
第一个选项（也可以叫分支）会被立即返回，后面的暂时不执行。假设该值被认为是“无效的（比如应用该值后，执行到(amb)了）”，则执行(prev-amb-fail)，而prev-amb-fail在进入amb的时候被绑定到了amb-fail， 不过amb-fail已被设置成了一个函数：
(lambda ()
(set! amb-fail prev-amb-fail)
(fk 'fail))
它先把amb-fail设置成prev-amb-fail,也就是进入（amb alt …）之前的值， 然后用(fk ‘fail)返回’fail到分支的continuation，即可以执行下一个分支（下一个选项）了。
十分精巧的程序！！！
上述的amb每次只能返回一个结果，如果需要返回所有有效的结果，可以用下面定义的宏：
(define-syntax bag-of
(syntax-rules ()
((bag-of e)
(let ((prev-amb-fail amb-fail) (results '()))
(if (call/cc
(lambda (k)
(set! amb-fail (lambda () (k #f))) ;<-----+
(let ((v e)) ;amb-fail will be modified by e |
(set! results (cons v results)) ;|
(k #t)))) ;|
(amb-fail)) ;so this amb-fail may not be ---+
(set! amb-fail prev-amb-fail)
(reverse! results)))))
(bag-of (let ([a (amb 1 2 3)] [b (amb 0 -1 2)])
(if (= (+ a b) 1) (list a b) (amb))
)) ;结果为：((1 0) (2 -1))
回到n-皇后问题
到目前为止，我已手握amb这把利器，是时候重构一下n-皇后问题了。
(define number-between
(lambda (lo hi)
(let loop ((i lo))
(if (> i hi) (amb)
(amb i (loop (+ i 1))))))) ; (amb 1 (amb 2 (amb 3 ... )))
(define (n-queens n)
(call/cc
(lambda (return)
(let add-queen ([i 0] [result '()])
(when (< i n) ;最多摆几个皇后
(let ([new-queen (number-between 1 n)])
(if
(safe? n (append (list new-queen) result)) ;新加入的皇后必须是有效的
(add-queen (+ i 1) (append (list new-queen) result))
(amb))
)
)
(return result)
)
)
)
)
(bag-of (n-queens 8)) ;8个皇后的所有解
该版本比之前的Scheme版本的实现改进了很多，现在只需要描述一下我的问题的关系即可，程序会自动选择所有正确的值，无需关心计算机内部到底发生了什么。在面对很多逻辑问题时，我们可以很轻松地解决了。
也许有人会问，如果采用命令式语言来处理的话，可能几个嵌套的循环也能达到相同的结果，如此大费周章的介绍这个叫amb的技术，到底有什么价值呢？ 那就来聊一聊。
有什么意义？
在谈论意义之前，容许我提一个问题
为什么SQL语言要设计成这样？与命令式语言如此的不同？
首先需要明确的一点是，计算机科学处理的是命令式（怎样做）的知识，而数学处理的是说明式（是什么）的知识。 事实上，人类不可能只面临其中一种问题，程序设计中一个重要的分支就是逻辑程序设计，有很多问题或者数据之间存在着关联关系，难以观测到结论，描述它们的关系很简单，但是直接告诉计算机如何去做却不那么容易，或许我们可以为若干此类问题编写命令式代码，但是不可能对所有这样的问题都编写代码，显然信息之间的关系是多种多样的，那么代码就需要相应的变化，往往修改这样的代码是很困难的， 甚至需要重新设计并编码。另一方面，如果程序设计可以处理说明式的知识，岂不是大大减轻了程序员的工作了呢？函数式语言的设计是基于lambda理论，围绕着数学函数值的计算组织起来的，依靠其强大的表现力，在处理逻辑问题上更加得心应手，可以化繁为简。
说到这里，是不是觉得，保存在数据库中的数据之间存在着种种联系呢？SQL正是描述了这种关系，我们只需要告诉数据库我们需要什么数据（select）, 数据在什么位置（from）, 哪些是有意义的（where）就行了，并不需要告诉数据库该如何具体操作，数据库可以根据我们的描述（SQL）就能够准确的返回结果，这真是关于非确定性计算的一个极好的例子，此时我们总该明白为什么数据库叫做关系型数据库 了吧。我们不妨设想一下，如果不采用描述的方式来查询数据，程序员们该怎么做？还能够轻易的查找到需要的数据吗？
刚才我提出的问题，想必此刻应该有答案了。
