免費(fèi)AI編程助手
第 22 章 非確定性
第 22 章 非確定性
程序設(shè)計(jì)語言讓我們得以從煩冗的細(xì)節(jié)中脫身而出。Lisp 是一門優(yōu)秀的語言，其原因在于它本身就幫我們處理如此之多的細(xì)枝末節(jié)，同時程序員對復(fù)雜問題的容忍是有限度的，而 Lisp 讓程序員能從他們有限的耐受度中發(fā)掘出最大的潛力。
本章將會解說宏是怎么樣幫助 Lisp 解決另一類重要的細(xì)節(jié)問題的：即，將非確定性算法轉(zhuǎn)換為確定性算法的問題。
本章共分為五個部分。
第一部分 闡述了什么是非確定性。
第二部分 介紹了非確定性 choose 和 fail 的一個 Scheme 實(shí)現(xiàn)，這個實(shí)現(xiàn)使用了續(xù)延。
第三部分 呈現(xiàn)了 choose 和 fail 的 Common Lisp 實(shí)現(xiàn)，這個版本的實(shí)現(xiàn)基于第 20 章提到的 continuation-passing 宏。
第四部分 展示了如何在脫離 Prolog 的情況下，來理解 cut 操作符。
最后一部分 提出了一些改進(jìn)最初版本的非確定性操作符的建議。
在本章定義的非確定性選擇操作符，將會在第 23 章里，被用來編寫一個 ATN 編譯器，而在第 24 章里，這些操作符會被用在一個嵌入式的 Prolog 實(shí)現(xiàn)里面。
22.1 概念
非確定性算法的運(yùn)行有賴于某種超自然的預(yù)見能力。那么，既然我們沒有辦法用到那種有超能力的電腦，為什么還要討論這種算法呢？因?yàn)榉谴_定性算法可以用確定性的算法來模擬。對于純函數(shù)式程序，即那種沒有副作用的程序，要模擬非確定性簡直就是小菜一碟。在純函數(shù)式程序里面，非確定性可以用帶回溯（backtracking） 的搜索過程來實(shí)現(xiàn)。
本章會展示在函數(shù)式程序里模擬非確定性的方法。如果我們有了一個能模擬非確定性的模擬器，那么只要是真正的非確定機(jī)器能夠處理的問題，照理說這個模擬器應(yīng)該也能得出答案。很多時候，寫一個有超自然的洞察力助陣的程序，肯定會比寫缺乏這種能力的程序要輕松。所以如果手里能有這樣一個模擬器，寫起程序來一定會如虎添翼。
在本節(jié)中，我們將會界定非確定性將賦予我們什么樣的能力。下一節(jié)里，會用一些示例程序展示這些能力的用處。本章開始的這兩節(jié)中的例子將會使用 Scheme 編寫。( Scheme 和 Common Lisp 之間的區(qū)別已經(jīng)在第 20.1 節(jié)總結(jié)過了。)
非確定性算法和確定性算法之所以不一樣，其原因在于前者能使用兩種特殊的操作符 choose 和 fail 。Choose 是一個函數(shù)，它能接受一個有限的集合，并返回其中一個元素。要解釋清楚 choose 是如何做選擇的，我們必須首先介紹一下計(jì)算過程中所謂的未來的概念。
這里，我們令 choose 為一個函數(shù) choose ，它接受一個列表，并返回一個元素。對每個元素來說，如果這個元素被選中，那么這個計(jì)算過程就會因?yàn)樗鴮?dǎo)致有一組可能的未來情況與之對應(yīng)。在下列表達(dá)式中
(let ((x (choose '(1 2 3))))
(if (odd? x)
(+ x 1)
x))接下來，當(dāng)這個運(yùn)算過程運(yùn)行到 choose 這里時，將會有三個可能的結(jié)果：
-
如果 choose 返回 1，那么這個運(yùn)算過程將會經(jīng)過 if 的 then 語句，然后返回 2。
-
如果 choose 返回 2 ，那么這個運(yùn)算過程將會經(jīng)過 if 的 else 語句，然后返回 2。
- 如果 choose 返回 3 ，那么這個運(yùn)算過程將會經(jīng)過 if 的 then 語句，然后返回 4 。
本例中，一旦知道 choose 的返回值，我們就能非常清楚這個運(yùn)算過程下一步將會是什么樣子。在普遍情況下，每個選擇都會和一組將來的情形相關(guān)聯(lián)，因?yàn)樵谖磥淼哪承┣闆r下，會出現(xiàn)更多的選擇。舉個例子，如下：
(let ((x (choose '(2 3))))
(if (odd? x)
(choose '(a b))
x))在這里，在運(yùn)行到第一個 choose 的時候，接下來會有兩個可能性：
-
如果 choose 返回 2 ，那么這個運(yùn)算過程將會經(jīng)過 if 的 else 語句，然后返回 2。
- 如果 choose 返回 3 ，那么這個運(yùn)算過程將會經(jīng)過 if 的 then 語句。走到這里，運(yùn)算過程到了一個岔路口，面臨著兩種可能，一個是返回 a ，另一個則返回 b 。
第一個集合有一個可能性，而第二個集合有兩個。因而這個計(jì)算過程總共有三個可能的去向。
這里要記住的是，如果 choose 有幾個選項(xiàng)可供選擇，那么每個選項(xiàng)都會牽涉到一組可能的去向（可能性）。
Choose 會返回哪一項(xiàng)呢？我們可以像下面那樣假設(shè) choose 的工作方式：
-
如果將來的可能性中存在有情況，在這種情況下沒有調(diào)用 fail ，那么 choose 將只會返回一個選擇。
- 如果要在零個選項(xiàng)里作選擇，那么這個 choose 就等價于 fail 。
下面用個例子來解釋，
(let ((x (choose '(1 2))))
(if (odd? x)
(fail)
x))在上面的例子里面，每個可能的選項(xiàng)都有其確定的將來。既然選擇 1 的那個選項(xiàng)的將來調(diào)用了fail ，那么只有 2 能被選擇。所以，總的來說，這個表達(dá)式是確定性的：它總是返回 2。
不過，接下來的表達(dá)式就不是確定性的了：
(let ((x (choose '(1 2))))
(if (odd? x)
(let ((y (choose '(a b))))
(if (eq? y 'a)
(fail)
y))
x))第一個 choose 那里，有兩個可能的將來與 1 這個選擇對應(yīng)，與 2 對應(yīng)的有一個。對于前者，這個將來是確定的，因?yàn)槿绻x a 的話，會導(dǎo)致調(diào)用 fail。因此，這個表達(dá)式總的來說，要么返回 b ，要么返回 2 。最后一個例子，下面的表達(dá)式只有一個可能的值:
(let ((x (choose '(1 2))))
(if (odd? x)
(choose '())
x))因?yàn)?，如果被選擇的是 1，那么接下來會走到一個沒有待選項(xiàng)的 choose。這個例子因而也就和上個以及另一個例子等價。
也許從上面舉的幾個例子，我們還不是很清楚非確定性到底意味著什么，但是我們已經(jīng)開始感受到了這種動人心魄的力量。在非確定性算法中，我們得以這樣表述 "選擇一個元素，使得無論我們接下來做什么決定，都不會導(dǎo)致對 fail 調(diào)用。" 下面的例子是一個非常典型的非確定性算法，它能弄清楚你祖上是不是有人名叫 Igor：
function Ig(n)
if name(n) = 'Igor'
then return n
else if parrents(n)
then return Ig(choose(parents(n))
else failfail 操作符被用來對 choose 的返回值施加影響。如果我們碰到一個 fail ，那么可以推斷 choose 在此之前肯定做了錯誤的選擇。按照定義，choose 的猜測總是正確的。所以，如果我們希望確保計(jì)算過程永遠(yuǎn)不會走到一條特定的路徑，那么我們所要做的就是把一個 fail 放到這條路徑上的某個地方，那樣的話，我們就不會誤入歧途。所以，由于這個算法一代一代地遞歸檢查，函數(shù) Ig 就能夠在路徑上的每一步上作出選擇，或者順著父親這條線索，或者順著母親這條線索，最終讓這條路通向 Igor。
這個過程就好像，一個程序能夠這樣要求：它讓 choose 從一組選項(xiàng)中找出某個元素，只要需要的話，就使用 choose 的返回值作為判斷的依據(jù)，只要 fail 出現(xiàn)，就一票否決，用這個機(jī)制倒推出程序希望 choose 在此之前作出的選擇。接著，一眨眼功夫，choose 的返回值就是我們想要的結(jié)果。在這個模型中，choose 體現(xiàn)出了它預(yù)知未來的能力。
實(shí)際上，choose 并沒有什么超自然的神力。choose 的任意一個實(shí)現(xiàn)都必須能通過在發(fā)現(xiàn)錯誤的時候進(jìn)行回溯，來模擬準(zhǔn)確無誤的猜測，這個過程就像小老鼠能在迷宮里找到出路一樣。但是回溯可以不動聲色地發(fā)生于無形之間。一旦你有某種形式的 choose 和 fail ，就可以寫出像上面例子那樣的算法了，感覺就像這個算法真的知道應(yīng)該選擇哪一個祖先一樣。借助 choose，只要寫一個遍歷問題空間的算法，就能搜索這個問題空間了。
22.2 搜索
有許多經(jīng)典的問題都可以歸結(jié)為搜索問題，對于這類問題，非確定性常常被證明是一種行之有效的抽象方式。假設(shè) nodes 被綁定到一棵樹上節(jié)點(diǎn)組成的列表，而 (kids n) 是一個能返回節(jié)點(diǎn) n 的子節(jié)點(diǎn)的函數(shù)，如果 n 沒有子節(jié)點(diǎn)的話，就返回 #f 。我們打算寫一個函數(shù)，即 (descent n1 n2)，讓它返回從節(jié)點(diǎn) n1 到其子孫節(jié)點(diǎn) n2 (如果有的話) 所經(jīng)過的某條路徑上所有節(jié)點(diǎn)構(gòu)成的列表。[示例代碼 22.1] 中就是這個函數(shù)的一個確定性版本。
[示例代碼 22.1] 確定性的樹搜索
(define (descent n1 n2)
(if (eq? n1 n2)
(list n2)
(let ((p (try-paths (kids n1) n2)))
(if p (cons n1 p) #f))))
(define (try-paths ns n2)
(if (null? ns)
#f
(or (descent (car ns) n2)
(try-paths (cdr ns) n2))))非確定性讓程序員不用再操心路徑尋找的細(xì)節(jié)。而只要告訴 choose ，讓它找到一個節(jié)點(diǎn) n ，使得從 n 到我們的目標(biāo)節(jié)點(diǎn)存在一條路徑。用非確定性的辦法，我們可以寫出更簡單的 descent 版本，如 [示例代碼 22.2] 所示。
[示例代碼 22.2] 中的版本并沒有顯式地去搜索正確的路徑所在的節(jié)點(diǎn)。能這樣寫，是基于這樣的假設(shè)：即 choose 已經(jīng)找到了一個具有期望特性的 n 。如果我們習(xí)慣于閱讀確定性的程序，可能就很難認(rèn)識到這一點(diǎn)，即：choose 毫無疑問是能完成工作的，就好像它能猜出來到底是哪個 n 能讓自己指引整個計(jì)算過程一帆風(fēng)順、正確無誤（fail）地走到終點(diǎn)。
[示例代碼 22.2] 非確定性的樹搜索
(define (descent n1 n2)
(cond ((eq? n1 n2) (list n2))
((null? (kids n1)) (fail))
(else (cons n1 (descent (choose (kids n1)) n2)))))對于choose 的能力，大概更有說服力的實(shí)例要算：即使在函數(shù)調(diào)用的時候，它的預(yù)見力也能奏效。[示例代碼 22.3] 里有一對函數(shù)，它們能猜出兩個數(shù)字，讓兩個數(shù)字之和等于調(diào)用者給出的數(shù)字。在第一個函數(shù)two-numbers 里面，非確定性幫助選擇出兩個數(shù)字，并把它們作為一個列表返回。當(dāng)我們調(diào)用parlor-trick 的時候，它會通過調(diào)用two-numbers 來得到這兩個數(shù)字。請注意，在two-numbers 在做決定的時候，它根本就無從得知用戶給出的那個數(shù)字到底是多少。
;; [示例代碼 22.3] 在子函數(shù)里的選擇非確定性的樹搜索
(define (two-numbers)
(list (choose '(0 1 2 3 4 5))
(choose '(0 1 2 3 4 5))))
(define (parlor-trick sum)
(let ((nums (two-numbers)))
(if (= (apply + nums) sum)
'(the sum of ,@nums)
(fail))))要是choose 猜的兩個數(shù)字加起來不等于用戶輸入的數(shù)字，那么這個計(jì)算過程會以失敗告終。由于我們可以信賴choose ，相信只要存在路徑不通向失敗的話，choose 選擇的路徑上就不會有失敗存在。因此我們才能假定一旦調(diào)用方給出的數(shù)字在合適的區(qū)間內(nèi)，choose 就肯定會作出正確的猜測，實(shí)際上它就是能做到這一點(diǎn)：
> (parlor-trick 7)
(THE SUM OF 2 5)在簡單的搜索問題中，Common Lisp 內(nèi)置的find-if 函數(shù)一樣能完成任務(wù)。那么非確定性選擇到底有什么優(yōu)越性呢？為什么不在待選項(xiàng)的列表里面一個一個找過來，搜索那些具有期望特性的元素呢？choose 和傳統(tǒng)的迭代搜索最根本的區(qū)別在于：choose 對于失敗到底能看到多遠(yuǎn)是沒有止境的。非確定性choose 可以知道未來任意遠(yuǎn)的事情。如果將來在某一點(diǎn)會發(fā)生導(dǎo)致choose 做出無效選擇的事件，我們可以確信choose 自己知道如何避免作出這樣猜測。正如我們在parlor-trick 一例中所見到的，甚至在我們從choose 發(fā)生的函數(shù)中返回之后，fail 操作符仍然能正常工作。
舉例來說，這種失敗機(jī)制常發(fā)生在Prolog 進(jìn)行的搜索中，非確定性之所以在Prolog 里能大顯神通的原因在于，這門語言的一個核心特性是它能每次只返回所有查詢結(jié)果中的一個。倘若使用非確定性的方法，而不是一次返回所有的有效結(jié)果，Prolog 就有能力處理遞歸的規(guī)則和條件，否則它就會得出一個大小為無窮大的結(jié)果集合。
看到descent 的第一反應(yīng)，可能就和看到歸并排序算法的第一反應(yīng)差不多：它到底是在哪里完成的工作的呢？就像歸并排序一樣，工作是在不知不覺中完成的，但是的確是完成了。第22.3 節(jié)會介紹一個choose 實(shí)現(xiàn)，迄今為止在這個實(shí)現(xiàn)里，所有的代碼示例都是實(shí)際使用的程序。
這些例子體現(xiàn)了非確定性作為一種抽象手段的價值所在。最優(yōu)秀的編程語言抽象手段不僅僅是讓你省下由于Scheme 沒有指定參數(shù)求值的順序(正相反，Common Lisp 要求求值的順序?yàn)閺淖笾劣?，這次調(diào)用也可能會返回(THE SUM OF 5 2)。
了打字的時間，更重要的是讓你更省心。在自動機(jī)理論里面，要是沒有非確定性的話，有些證明簡直就難以想象，無法完成。一門允許非確定性的語言也能給程序員創(chuàng)造類似的有利條件。
22.3 Scheme 實(shí)現(xiàn)
這一節(jié)將會解釋續(xù)延(continuation) 是如何模擬非確定性的。[示例代碼 22.4] 是choose 和fail 的Scheme 實(shí)現(xiàn)。在表象之下，choose 和fail 利用回溯來模擬非確定性。然而，一個使用回溯的搜索程序必須保留足夠的信息才能在先前選中的選擇失敗后，繼續(xù)使用其他的選項(xiàng)搜索。這些信息就以續(xù)延的形式保存在全局變量paths?里面。
;; [示例代碼 22.4] choose 和fail 的Scheme 實(shí)現(xiàn)
(define *paths* ())
(define failsym '@)
(define (choose choices)
(if (null? choices)
(fail)
(call-with-current-continuation
(lambda (cc)
(set! *paths*
(cons (lambda ()
(cc (choose (cdr choices))))
*paths*))
(car choices)))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))傳給函數(shù)choose 的是一個名為choices 的列表，它由一系列選項(xiàng)構(gòu)成。如果choice 是空的，那么choose 就會調(diào)用fail ，后者會把計(jì)算過程打回之前的choose。如果choices 是 ( . ) 的形式，那么choose 會首先把它調(diào)用 時的續(xù)延壓入paths?，然后再返回。
相比之下，函數(shù)fail 就簡單一些。它直接從paths?彈出一個續(xù)延，然后調(diào)用它。如果之前保存的路徑都被用完了，fail 就返回符號@。不過，它不會簡簡單單地像普通的函數(shù)返回值那樣返回這個符號，也不會把它作為最近的一次choose 的返回值來返回。我們真正想要做的是把@ 直接返回到toplevel 。這個目的
是這樣達(dá)到的：通過把cc 綁定到定義fail 時所處的那個續(xù)延，而定義fail 的地方可以被認(rèn)為是toplevel。
通過調(diào)用cc ，fail 可以直接返回到那里。
[示例代碼 22.4] 的實(shí)現(xiàn)把paths?當(dāng)成棧來用。在這個實(shí)現(xiàn)里面，每當(dāng)失敗的時候就會轉(zhuǎn)而從最新近的抉擇點(diǎn)重新開始。這種策略被稱為按時間回溯(chrnonologicalbacktracking)，其結(jié)果就是在問題空間中的深度優(yōu)先搜索。"非確定性" 這個詞常會被濫用，就好像它是深度優(yōu)先實(shí)現(xiàn)的代名詞。Floyd 關(guān)于非確定性算法的那篇經(jīng)典的論文中提到的術(shù)語"非確定性"，取的就是這個意思，而且我們看到的一些非確定性解析器(parser)
和Prolog 里面，非確定性算法的實(shí)現(xiàn)都是用的深度優(yōu)先搜索。不過，也要注意到，[示例代碼 22.4] 并非唯一的實(shí)現(xiàn)，
甚至算不上一個正確的實(shí)現(xiàn)。照道理來說，choose 應(yīng)該能根據(jù)任意可計(jì)算的指標(biāo)來選擇對象。但是，如果一個圖里面有環(huán)的話，程序使用這些版本的choose 和fail 來搜索這個圖就無法終止了。
在實(shí)際應(yīng)用中，非確定性常常意味著使用和[示例代碼 22.4] 中等價的的深度優(yōu)先實(shí)現(xiàn)，同時把避免在搜索空間里面繞圈子的問題留給用戶去解決。不過，對這一主題有興趣的讀者，在本章的最后一節(jié)將會解釋如何實(shí)現(xiàn)真正的choose 和fail 。
22.4 Common Lisp 實(shí)現(xiàn)
這一節(jié)將闡述如何用 Common Lisp 來實(shí)現(xiàn) choose 和 fail 一種表現(xiàn)形式。正如我們在上節(jié)所看到的，call/cc 使得在 Scheme 里面能輕而易舉地實(shí)現(xiàn)非確定性機(jī)制。之前，我們對計(jì)算過程的未來定義了一個理論中的概念，續(xù)延把它給具體化了。在 Common Lisp 中，我們可以用在第20 章中給出的 continuation-passing 宏來實(shí)現(xiàn)它。借助這些宏，我們就能給出僅僅比上一節(jié)中的 Scheme 版本稍微難看一些的 choose，但是它們在實(shí)際使用中的效果是一樣的。
;; [示例代碼 22.5] 非確定性操作符的Common Lisp 實(shí)現(xiàn)
(defparameter *paths* nil)
(defconstant failsym '@)
(defmacro choose (&rest choices)
(if choices
'(progn
,@(mapcar #'(lambda (c)
'(push #'(lambda () ,c) *paths*))
(reverse (cdr choices)))
,(car choices))
'(fail)))
(defmacro choose-bind (var choices &body body)
'(cb #'(lambda (,var) ,@body) ,choices))
(defun cb (fn choices)
(if choices
(progn
(if (cdr choices)
(push #'(lambda () (cb fn (cdr choices)))
*paths*))
(funcall fn (car choices)))
(fail)))
(defun fail ()
(if *paths*
(funcall (pop *paths*))
failsym))[示例代碼 22.5] 中是一個fail 的Common Lisp 實(shí)現(xiàn)，以及兩個版本的choose。其中一個choose 的Common Lisp 版本
和它的Scheme 版本有些微小的區(qū)別。Scheme 的choose 接受一個參數(shù)，即：一個待選項(xiàng)的列表，以備選擇作為返回值。而Common Lisp 版本采用了progn 的語法。它后面可以跟任意多個表達(dá)式，choose 會從里面選出一個進(jìn)行求值：
> (defun do2 (x)
(choose (+ x 2) (* x 2) (expt x 2)))
DO2
> (do2 3)
5
> (fail)
6在toplevel，我們可以把回溯算法看得更清楚一些，它運(yùn)行在非確定性搜索的幕后。變量paths?被用來保存還沒有走過的路徑。當(dāng)計(jì)算過程到達(dá)一個有多個可選項(xiàng)的choose 表達(dá)式的時候，第一個可選項(xiàng)會被求值，而其它幾個選項(xiàng)則會被保存在paths?里。如果程序在這之后碰到了fail ，那么最后一個被保存的選項(xiàng)會從paths?彈出來，然后重新開始計(jì)算。要是沒有更多的路徑可供重啟計(jì)算的話，fail 會返回一個特殊的值：
> (fail)
9
> (fail)
@在[示例代碼 22.5] 中，用來表示失敗的常量failsym ，被定義成了符號@。如果你希望把@ 作為一個普通的返回值，那么可以把failsym 改成用gensym。
另一個非確定性的選擇操作符choose-bind 的實(shí)現(xiàn)用了一個稍微不一樣的形式。它接受的是一個符號、一個待選項(xiàng)的列表，還有一個代碼體。choose-bind 會對這個待選項(xiàng)的列表運(yùn)行choose，然后把被選中的值綁定到符號上，最后對代碼體求值：
> (choose-bind x '(marrakesh strasbourg vegas)
(format nil "Let's go to ~A." x))
"Let's go to MARRAKESH."
> (fail)
"Let's go to STRASBOURG."Common Lisp 的實(shí)現(xiàn)中提供兩個選擇操作符的原因只是為了方便。你可以用choose-bind 達(dá)到和choose 一樣的效果，只要把：
(choose (foo) (bar))翻譯成
(choose-bind x '(1 2)
(case x
(1 (foo))
(2 (bar))))就可以了。但是如果在這個情況下我們有一個單獨(dú)的操作符的話，程序的可讀性就會更好些。
Common Lisp 的選擇操作符通過閉包和變量捕捉保存了幾個相關(guān)變量的綁定。choose 和choose-bind 作為宏，在它們所在的表達(dá)式的詞法環(huán)境中展開。注意到，這兩個宏加入paths?的是一個閉包，在這個閉包保存了將要用到的待選項(xiàng)，還有被引用到的詞法變量的所有綁定。舉例來說，在下面的表達(dá)式里
(let ((x 2))
(choose
(+ x 1)
(+ x 100)))當(dāng)啟用之前保存的選項(xiàng)重新開始計(jì)算時，就會用到x 。這就是為什么讓choose 把它的參數(shù)包裝在一個lambda 表達(dá)式的原因所在。上面的表達(dá)式展開后的結(jié)果如下：
(let ((x 2))
(progn
(push #'(lambda () (+ x 100))
*paths*)
(+ x 1)))如果需要的話，對外的接口可以只提供單獨(dú)一個操作符，因?yàn)?(fail) 和 (choose)是等價的。
保存在path?上的對象是一個含有指向x 指針的閉包。這是由于要閉包里存放變量的需要使然，可以從這一點(diǎn)看出Scheme 和Common Lisp 兩者的選擇操作符在語義上的不同之處。
倘若我們把choose 和fail 和第20 章的continuation-passing 宏一起用，那么指向我們的續(xù)延變量cont?的一個指針也會一樣被保存下來。如果用=defun 來定義函數(shù)，同時用=bind 來調(diào)用它們，而且用=values 來獲取函數(shù)的返回值，我們就可以在任意一個Common Lisp 程序里使用這套非確定性的機(jī)制了。
;; [示例代碼 22.6]： Common Lisp 版的 "在子函數(shù)里作選擇"
(=defun two-numbers ()
(choose-bind n1 '(0 1 2 3 4 5)
(choose-bind n2 '(0 1 2 3 4 5)
(=values n1 n2))))
(=defun parlor-trick (sum)
(=bind (n1 n2) (two-numbers)
(if (= (+ n1 n2) sum)
'(the sum of ,n1 ,n2)
(fail))))在這些宏的幫助下，我們可以毫無問題地運(yùn)行那個非確定性的選擇發(fā)生在子函數(shù)里的那個例子了。[示例代碼 22.6] 中展示了Common Lisp 版本的parlor-trick ，就像之前它在Scheme 里一樣，它運(yùn)行正常：
> (parlor-trick 7)
(THE SUM OF 2 5)這個函數(shù)之所以能正常工作，是因?yàn)楸磉_(dá)式
(=values n1 n2)在兩個choose-bind 中被展開成了
(funcall *cont* n1 n2)而每個choose-bind 則都被展開成了一個閉包，每個閉包都保存有指向body 中引用過的變量的指針，這些變量中包括?cont。
在使用choose、choose-bind 和fail 過程中存在的種種限制和[示例代碼 20.5] 中所展示的限制是一樣的，后者代碼中所使用的技術(shù)是continuation-passing 宏。只要是選擇表達(dá)式，它就一定是最后一個被求值的。所以如果我們想要在Common Lisp 里做一系列的選擇的話，這些選擇就必須以嵌套的形式出現(xiàn)：
> (choose-bind first-name '(henry william)
(choose-bind last-name '(james higgins)
(=values (list first-name last-name))))
(HENRY JAMES)
> (fail)
(HENRY HIGGINS)
> (fail)
(WILLIAM JAMES)和平時一樣，這樣做的結(jié)果就是深度優(yōu)先搜索。
在第20 章定義的操作符能讓表達(dá)式享有最后求值的權(quán)利。這個權(quán)利由新的宏抽象層接管了，一個=values 表達(dá)式必須出現(xiàn)在choose 表達(dá)式里面，反過來就行不通。也就是說
(choose (=values 1) (=values 2))是可以的，但是
(=values (choose 1 2)) ; wrong卻不行。(在后面的例子中，choose 的展開式是無法在=values 的展開式里捕獲cont?的變量實(shí)例的。)
只要我們注意不要超越這里列出的以及[示例代碼 20.5] 所示的那些限制，Common Lisp 的非確定選擇機(jī)制就將會和它在Scheme 中一樣，正常工作。與[示例代碼 22.2] 中的Scheme 版的非確定性樹搜索算法相對應(yīng)，[示例代碼 22.7] 中所示的是它的Common Lisp 版本。Common Lisp 版的descent 是從它的Scheme 版本直譯過來的，盡管它顯得有點(diǎn)羅嗦，同時也沒那么漂亮。
;; [示例代碼 22.7]： 在Common Lisp 里做非確定性搜索
> (=defun descent (n1 n2)
(cond ((eq n1 n2) (=values (list n2)))
((kids n1) (choose-bind n (kids n1)
(=bind (p) (descent n n2)
(=values (cons n1 p)))))
(t (fail))))
DESCENT
> (defun kids (n)
(case n
(a '(b c))
(b '(d e))
(c '(d f))
(f '(g))))
KIDS
> (descent 'a 'g)
(A C F G)
> (fail)
@
> (descent 'a 'd)
(A B D)
> (fail)
(A C D)
> (fail)
@
> (descent 'a 'h)
@現(xiàn)在有了Common Lisp 版的實(shí)用工具，就能做非確定性的搜索，而不用顯式地去做回溯了。雖然勞心費(fèi)力寫了這些代碼，但可以從此把本會寫得冗長拖沓、一團(tuán)亂麻的代碼用寥寥幾行就說得清楚明白，這個回報還是值得的。在現(xiàn)有的宏基礎(chǔ)上再構(gòu)造另一層宏，我們就能夠用一頁紙的篇幅寫出一個ATN 編譯器(第23 章)，或是在兩頁紙上初步實(shí)現(xiàn)Prolog(第24 章)。
使用了choose 的Common Lisp 程序在編譯的時候必須打開尾遞歸優(yōu)化，這不只是為了加快程序的運(yùn)行速度，更重要的是為了避免發(fā)生棧溢出。雖然程序是通過調(diào)用續(xù)延函數(shù)來"返回" 值的，但是它真正的返回卻是等碰到了最后的fail 才發(fā)生的。要是不進(jìn)行尾遞歸優(yōu)化，程序占用的?？臻g只會越來越大。
22.5 減枝
本節(jié)將會告訴我們?nèi)绾卧谶M(jìn)行非確定性選擇的Scheme 程序里使用減枝(cut)。雖然cut 一詞來自于Prolog，
但是對非確定性來說，它所代表的概念卻是普適的。你可以在任意一個作非確定性選擇的程序里使用減枝技術(shù)。
如果不把Prolog 牽扯進(jìn)來，可以更容易地理解減枝。讓我們先設(shè)想一個現(xiàn)實(shí)生活中的例子。假設(shè)花生糖的生產(chǎn)廠商決定進(jìn)行一次促銷活動。出廠時，一小部分的花生糖盒子里會裝有可以用來領(lǐng)獎的兌獎幣。為了確保公平，發(fā)貨的時候不會同時把兩個有獎品的盒子送往一個城市。
譯者注：原文為"Chocoblob"，是一種巧克力糖。但為了更通順，譯者自作主張把它改為"花生糖"。
促銷開始后，糖廠發(fā)現(xiàn)由于兌獎幣太小了，很容易被小孩誤吞下去。這個發(fā)現(xiàn)讓糖廠的律師預(yù)見到了由此導(dǎo)致的索賠和訴訟，別無他法，他們只得發(fā)起緊急搜索，想要召回全部有獎的盒子。每個城市都有多家門店銷售花生糖，而每個店都會有不止一個盒子。但是律師們用不著打開每一個包裝盒，因?yàn)橹灰麄円坏┰谀硞€城市發(fā)現(xiàn)有硬幣的盒子，就不用再在這個城市里檢查其他盒子了，因?yàn)槊總€城市最多只有一個有獎的盒子。要實(shí)現(xiàn)這個算法，可以做個減枝操作。
減枝指的是排除搜索樹里的一部分。對于花生糖問題來說，搜索樹是實(shí)實(shí)在在存在的：根節(jié)點(diǎn)是公司的總部，這個節(jié)點(diǎn)的子節(jié)點(diǎn)是獎盒所發(fā)往的城市，而這些子節(jié)點(diǎn)的子節(jié)點(diǎn)則是每個城市里面的門店，每個門店的子節(jié)點(diǎn)則代表了相應(yīng)門店里的包裝盒。當(dāng)律師們搜索這棵樹時，如果找到了有硬幣的盒子時，他們會裁減掉當(dāng)前城市下，還未檢查過的分支。
減枝操作實(shí)際上含有兩個步驟：當(dāng)你知道那一部分的搜索樹已經(jīng)沒有價值了，你就可以進(jìn)行一次減枝，但是首先你必須在樹上你認(rèn)為可以減枝的地方作上標(biāo)記。在花生糖的例子里，我們從常識可以推知，我們一搜索到城市的時候，這棵樹的標(biāo)記就做好了。很難用抽象的術(shù)語說清楚Prolog 的cut 是干什么的，因?yàn)檫@種標(biāo)記是隱式的。不過用顯式的標(biāo)記操作符的話，減枝的意思就比較容易理解了。
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(display 'c))
(fail)))))
(define (coin? x)
(member x '((la 1 2) (ny 1 1) (bos 2 2))))[示例代碼 22.8]： 窮盡的花生糖搜索
[示例代碼 22.8] 中的程序用非確定性的方法搜索了一個規(guī)模更小的花生糖樹。每當(dāng)一個盒子被打開，程序就會顯示一個( ) 的列表。如果盒子里面有硬幣的話，在其后會再打印一個c ：
> (find-boxes)
(LA 1 1)(LA 1 2)C(LA 2 1)(LA 2 2)
(NY 1 1)C(NY 1 2)(NY 2 1)(NY 2 2)
(BOS 1 1)(BOS 1 2)(BOS 2 1)(BOS 2 2)C
@要實(shí)現(xiàn)花生糖的律師們想出的優(yōu)化搜索算法，我們需要兩個新的操作符：mark 和cut。[示例代碼 22.9] 展示了一種定義它們的方法。雖然非確定性本身和特定的實(shí)現(xiàn)沒什么關(guān)系，我們可以通過任意一個實(shí)現(xiàn)來理解它，但是搜索樹的剪枝作為一種優(yōu)化技術(shù)卻高度依賴 choose 的實(shí)現(xiàn)細(xì)節(jié)。[示例代碼 22.9] 中所示的mark 和cut 適用于深度優(yōu)先搜索類型choose 實(shí)現(xiàn)([示例代碼 22.4])。
要做mark ，通常的思路是把標(biāo)記存到paths?里，后者是個列表，被用來保存還沒有檢查過的選擇點(diǎn)。調(diào)用cut 會讓paths?一直退棧，直到彈出最新近壓入的標(biāo)記。但是，我們應(yīng)該把什么作為標(biāo)記呢？我們有幾個選擇，比如說，也許我們可以用符號m ，但是這樣的話，我們就需要重寫fail ，讓它在碰到m 的時候忽略它。幸虧函數(shù)也是一種對象，至少還有一種標(biāo)記讓我們能用fail ，它就是：函數(shù)fail 本身。這樣的話，如果在一個標(biāo)記上發(fā)生了fail ，讓它調(diào)用自己就可以了。
[示例代碼 22.10] 中顯示了如何使用這些操作符來對花生糖的例子中的搜索樹進(jìn)行剪枝。(被修改過代碼所在的行被用分號注明) 每當(dāng)選擇一個城市的時候，我們都會調(diào)用mark 。在那時，paths?里有一個續(xù)延，它保存著對剩余城市的搜索狀態(tài)。
;; [示例代碼 22.9]： 對搜索樹進(jìn)行標(biāo)記和剪枝
(define (mark) (set! *paths* (cons fail *paths*)))
(define (cut)
(cond ((null? *paths*))
((eq? (car *paths*) fail)
(set! *paths* (cdr *paths*)))
(else
(set! *paths* (cdr *paths*))
(cut))));; [示例代碼 22.10]： 剪枝的花生糖搜索
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(mark) ;
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(begin (cut) (display 'c))) ;
(fail)))))如果我們找到一個有硬幣的盒子，就調(diào)用cut ，它會讓path?恢復(fù)到之前做標(biāo)記的狀態(tài)。執(zhí)行減枝的效果直到下次調(diào)用fail 的時候才能看出來。但是到了那個時候，在display 之后，下一個fail 會把搜索過程
直接帶到最外層的choose 那里，就算在搜索樹中更下層的地方還有一些沒有碰過的選擇點(diǎn)，也是這樣。結(jié)果就是：一旦找到了有硬幣的盒子，我們就會從下一個城市繼續(xù)我們的搜索，如下：
> (find-boxes)
(LA 1 1)(LA 1 2)C
(NY 1 1)C
(BOS 1 1)(BOS 1 2)(BOS 2 1)(BOS 2 2)C
@在本例中，我們只檢查了七個盒子，而不是十二個。
22.6 真正的非確定性
確定性的圖搜索程序應(yīng)該采取專門的措施，以免在循環(huán)路徑上無法脫身。[示例代碼 22.11] 中所示是一個包含環(huán)路的有向圖。當(dāng)程序在一條從節(jié)點(diǎn)a 通向節(jié)點(diǎn)e 的路徑上搜索時，就有可能陷入由?a，b，c? 構(gòu)成的環(huán)狀路徑。
除非這個確定性搜索使用了隨機(jī)算法，廣度優(yōu)先搜索，或者顯式地檢測循環(huán)路徑，否則是無法避免死循環(huán)的。如[示例代碼 22.12] 所示，是path 的實(shí)現(xiàn)，其中使用了廣度優(yōu)先搜索，避免了環(huán)路。
從理論上說，非確定性應(yīng)該可以讓我們不用考慮環(huán)路帶來的問題。22.3 中給出的 choose 和 fail 的深度優(yōu)先實(shí)現(xiàn)是無法解決環(huán)路問題的，但倘若我們當(dāng)初要求更嚴(yán)格一些的話，那么應(yīng)該會要求非確定性的 choose 能夠依據(jù)任意可計(jì)算的指標(biāo)來選擇對象，所以這次的例子照道理也應(yīng)該不在話下。如果能用上正確版本的choose 的話，我們就能像[示例代碼 22.13] 中那樣，寫出更簡短、更清晰的path 。
本節(jié)會給出一個環(huán)路安全的choose 和fail 的實(shí)現(xiàn)。[示例代碼 22.14] 中真正的非確定性choose 和fail 的Scheme 實(shí)現(xiàn)
;; [示例代碼 22.11]： 帶環(huán)的有向圖
a c e
b d;; [示例代碼 22.12]： 確定性搜索
(define (path node1 node2)
(bf-path node2 (list (list node1))))
(define (bf-path dest queue)
(if (null? queue)
'@
(let* ((path (car queue))
(node (car path)))
(if (eq? node dest)
(cdr (reverse path))
(bf-path dest
(append (cdr queue)
(map (lambda (n)
(cons n path))
(neighbors node))))))));; [示例代碼 22.13]： 非確定性搜索
(define (path node1 node2)
(cond ((null? (neighbors node1)) (fail))
((memq node2 (neighbors node1)) (list node2))
(else (let ((n (true-choose (neighbors node1))))
(cons n (path n node2))))))對于環(huán)路也能正常工作。只要是等價的非確定性算法能處理的問題,使用了這個版本的choose 和fail 的程序也一定能找到答案,不過這一點(diǎn)還會受到硬件的限制。[示例代碼 22.14] 中定義的true-choose 把用來保存路徑的列表當(dāng)成一個隊(duì)列來操作。因此，使用true-choose 的程序?qū)顟B(tài)空間進(jìn)行的搜索將是廣度優(yōu)先的。每當(dāng)程序到達(dá)選擇點(diǎn)的時候，與每一個選擇相對應(yīng)的續(xù)延都會被加入到用來保存路徑的列表后面。(Scheme 的map 的返回值和Common Lisp 的mapcar 的返回值是一樣的。) 然后，和之前一樣，還是調(diào)用fail。
如果用了這個版本的choose，[示例代碼 22.13] 里定義的path 就能找到一條路徑了，事實(shí)上，它找到的是最短路徑，即[示例代碼 22.11] 中所示的從a 到e 的那條路徑。
雖然為了內(nèi)容的完整性，本章給出了正確版本的choose 和fail ，其實(shí)最初的版本就夠用了。我們不能僅僅因?yàn)槠鋵?shí)現(xiàn)不是形式上正確的，就低估編程語言所提供抽象機(jī)制的價值。在用一些語言編程的時候，感覺上似乎我們能使用任意一個整數(shù)，其實(shí)能操作的最大一個整數(shù)可能只是32767。其實(shí)只要清楚幻象的限度，那么它所帶來的危險就微不足道了，至少我們的抽象是有保證的。下兩章中程序的簡潔明了，很大程度上就歸功于它們對非確定性choose 和fail 的善用。
;; [示例代碼 22.14] choose 的 Scheme 版正確實(shí)現(xiàn)
(define *paths* ())
(define failsym '@)
(define (true-choose choices)
(call-with-current-continuation
(lambda (cc)
(set! *paths* (append *paths*
(map (lambda (choice)
(lambda () (cc choice)))
choices)))
(fail))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))
更多建議：