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