第 6 章 函數(shù)作為表達(dá)方式

第 6 章 函數(shù)作為表達(dá)方式

通常說來，數(shù)據(jù)結(jié)構(gòu)被用來描述事物?？梢杂脭?shù)組描述坐標(biāo)變換，用樹結(jié)構(gòu)表示命令的層次結(jié)構(gòu)，而用圖來表示鐵路網(wǎng)。在 Lisp 里，我們常會使用閉包作為表現(xiàn)形式。在閉包里，變量綁定可以保存信息，也能扮演在復(fù)雜數(shù)據(jù)結(jié)構(gòu)中指針的角色。如果讓一組閉包之間共享綁定，或者讓它們之間能相互引用，那么我們就可以創(chuàng)建混合型的對象類型，它同時繼承了數(shù)據(jù)結(jié)構(gòu)和程序邏輯兩者的優(yōu)點。

其實在表象之下，共享綁定就是指針。閉包只是讓我們能在更高的抽象層面上操作指針。通過用閉包來表示我們以往用靜態(tài)數(shù)據(jù)結(jié)構(gòu)表示的對象，就往往可能得到更為優(yōu)雅，效率更好的程序。

6.1 網(wǎng)絡(luò)

閉包有三個有用的特性：它是動態(tài)的，擁有局部狀態(tài)，而且我們可以創(chuàng)建閉包的多個實例。那么帶有局部狀態(tài)的動態(tài)對象的多個拷貝能在什么地方一展身手呢？答案是：和網(wǎng)絡(luò)有關(guān)的程序。許多情況下，我們可以把網(wǎng)絡(luò)中的節(jié)點表示成閉包。閉包在擁有其局部狀態(tài)的同時，它還能引用其它閉包。因而，一個表示網(wǎng)絡(luò)中節(jié)點的閉包是能夠知道作為它發(fā)送數(shù)據(jù)目的地的其他幾個節(jié)點（閉包） 的。換句話說，我們有能力把網(wǎng)絡(luò)結(jié)構(gòu)直接翻譯成代碼。

在本節(jié)和下一節(jié)里，我們會分別了解兩種遍歷網(wǎng)絡(luò)的方法。首先我們會按照傳統(tǒng)的辦法，即把節(jié)點定義成結(jié)構(gòu)體，并用與之分離的代碼來遍歷網(wǎng)絡(luò)。接著，在下一節(jié)我們將會用一個統(tǒng)一的抽象模型來構(gòu)造通用功能的程序。

;; [示例代碼6.1]
;; 一輪 twenty questions 游戲
> (run-node 'people)
Is the person a man?
>> yes
Is he living?
>> no
Was he American?
>> yes
Is he on a coin?
>> yes
Is the coin a penny?
>> yes
LINCOLN

我們將選擇一個最簡單的應(yīng)用作為例子：一個能運行 twenty questions 的程序。我們的網(wǎng)絡(luò)將會是一棵二叉樹。每個非葉子節(jié)點都會含有一個是非題，并且根據(jù)對這個問題的回答，遍歷過程會在左子樹或者右子樹兩者中擇一，繼續(xù)往下進行。葉子節(jié)點將會含有所有的返回值。當(dāng)遍歷過程遇到葉子節(jié)點時，葉子節(jié)點的值會被作為遍歷過程的返回值返回。如 [示例代碼 6.1] 所示，是程序運行一輪 twenty questions 的樣子。

從習(xí)慣的辦法著手，可能就是先定義某種數(shù)據(jù)結(jié)構(gòu)來表示節(jié)點。節(jié)點應(yīng)該包含這幾樣信息：它是否是葉子節(jié)點；如果是的話，那返回值是什么，倘若不是，要問什么問題；還有與答案對應(yīng)的下個節(jié)點是什么樣的。

譯者注：twenty questions 曾是一檔國外很流行的電視智力節(jié)目，同時也是人工智能的重要題材。

;; [示例代碼 6.2]
;; 節(jié)點的表示方法及其定義
(defstruct node contents yes no)

(defvar *nodes* (make-hash-table))

(defun defnode (name conts &optional yes no)
    (setf (gethash name *nodes*)
        (make-node :contents conts
        :yes yes
        :no no)))

[示例代碼 6.2] 里定義了一個信息足夠詳盡的數(shù)據(jù)結(jié)構(gòu)。它的設(shè)計目標(biāo)是讓數(shù)據(jù)所占的空間最小化。contents 字段中要么是問題要么是返回值。如果該節(jié)點不是葉子節(jié)點，那么yes 和no 字段會告訴我們與問題的答案對應(yīng)的去向；如果節(jié)點是個葉子節(jié)點，我們自然會知道這一點，因為這些字段會是空的。全局的nodes

是一個哈希表，在表中，我們會用節(jié)點的名字來索引節(jié)點。最后，defnode 會新建一個節(jié)點（兩種節(jié)點都可以），并把它保存到nodes?中。有了這些原材料，我們就可以定義樹的第一個節(jié)點了：

(defnode 'people "Is the person a man?"
    'male 'female)

[示例代碼 6.3] 中所示的網(wǎng)絡(luò)正好足夠我們運行6.1 中所示的一輪游戲。

;; [示例代碼 6.3]
;; 作為樣例的網(wǎng)絡(luò)
(defnode 'people "Is the person a man?" 'male 'female)
(defnode 'male "Is he living?" 'liveman 'deadman)
(defnode 'deadman "Was he American?" 'us 'them)
(defnode 'us "Is he on a coin?" 'coin 'cidence)
(defnode 'coin "Is the coin a penny?" 'penny 'coins)
(defnode 'penny 'lincoln)

;; [示例代碼 6.4]
;; 用來遍歷網(wǎng)絡(luò)的函數(shù)
(defun run-node (name)
    (let ((n (gethash name *nodes*)))
        (cond ((node-yes n)
                (format t "~A~%>> " (node-contents n))
            (case (read)
                (yes (run-node (node-yes n)))
                (t (run-node (node-no n)))))
        (t (node-contents n)))))

現(xiàn)在，我們要做的就是寫一個能遍歷這個網(wǎng)絡(luò)的函數(shù)了，這個函數(shù)應(yīng)該打印出問題，并順著答案所指示的路徑走下去。函數(shù)的名字是 run-node ，如 [示例代碼 6.4] 所示。給出一個名字，我們就根據(jù)名字找到對應(yīng)的節(jié)點。如果該節(jié)點不是葉子節(jié)點，就把 contents 作為問題打印出來，按照答案不同，我們繼續(xù)順著兩條可能的途徑之一繼續(xù)遍歷。如果該節(jié)點是葉子節(jié)點，run-node 會徑直返回 contents。使用 [示例代碼 6.3] 中定義的網(wǎng)絡(luò)，這個函數(shù)就能生成 [示例代碼 6.1] 中的輸出信息。

6.2 編譯后的網(wǎng)絡(luò)

在上一節(jié)，我們編寫了一個使用網(wǎng)絡(luò)的程序，也許使用任何一種語言都能寫出這樣的程序。的確，這個程序太簡單了，看上去似乎很難把它寫成另一個模樣。但是事實上，我們可以把程序打理得更簡潔一些。

;; [示例代碼 6.5]
;; 編譯成閉包形式的網(wǎng)絡(luò)
(defun *nodes* (make-hash-table))

(defun defnode (name conts &optional yes no)
(setf (gethash name *nodes*)
(if yes
#'(lambda ()
(format t "~A~%>> " conts)
(case (read)
(yes (funcall (gethash yes *nodes*)))
(t (funcall (gethash no *nodes*)))))
#'(lambda () conts))))

[示例代碼 6.5] 就是明證。這是讓我們的網(wǎng)絡(luò)運行起來所需要的所有代碼。在這里，不再把節(jié)點定義成一個結(jié)構(gòu)，

也沒有用一個單獨的函數(shù)來遍歷這些節(jié)點，而是把節(jié)點表示成閉包。原來保存在數(shù)據(jù)結(jié)構(gòu)里的數(shù)據(jù)現(xiàn)在棲身于閉包里的變量綁定中。沒有必要運行 run-node 了，它已經(jīng)隱含在了節(jié)點自身里面。要啟動遍歷過程， 只消 funcall 一下起始的那個節(jié)點就行了：

(funcall (gethash 'people *nodes*))
Is the person a man
>>

自此，接下來的人機對話就和上個版本的實現(xiàn)一樣了。

借助把節(jié)點都表示成閉包的方式，我們得以將 twenty questions 網(wǎng)絡(luò)完全轉(zhuǎn)化成代碼（而非數(shù)據(jù)）。正如我們所看到的，程序代碼必須在運行時按照名字來查找節(jié)點函數(shù)。然而，如果我們確信網(wǎng)絡(luò)在運行的時候不會重新定義，那就可以更進一步：讓節(jié)點函數(shù)直接調(diào)用它們的下一站目標(biāo)函數(shù)，而不必再動用哈希表了。

如 [示例代碼 6.6] 所示，是新版的程序代碼?，F(xiàn)在，node 從哈希表改成了一個列表。像以前一樣，所有的節(jié)點還

是用defnode 定義的，不過定義時并不會生成閉包。在定義好所有的節(jié)點之后，我們就調(diào)用 compile-net 來一次性地編譯整個網(wǎng)絡(luò)。這個函數(shù)遞歸地進行處理，一直往下，直至樹的葉子節(jié)點，在遞歸過程層層返回時，每一步都返回了兩個目標(biāo)函數(shù)對應(yīng)的節(jié)點（或稱函數(shù)），而不僅僅是給出它們的名字。 當(dāng)最外面的 compile-net 調(diào)用返回時，它給出的函數(shù)將表示一個我們所需的那部分網(wǎng)絡(luò)。

> (setq n (compile-net 'people))
#<Compiled-Function BF3C06>
> (funcall n)
Is the person a man?
>>

注意到，compile-net 進行的編譯有兩層含義。按照通常編譯的含義，它把網(wǎng)絡(luò)的抽象表示翻譯成了代碼。

更進一層，如果compile-net 自身被編譯的話，那它就會返回編譯后的函數(shù)。（見第17頁）

在編譯好網(wǎng)絡(luò)之后，由defnode 構(gòu)造的列表就沒用了。如果切斷列表與程序的聯(lián)系（例如將nodes 設(shè)為nil），垃圾收集器就會回收它。

這個版本的程序假定程序中的網(wǎng)絡(luò)是一種樹結(jié)構(gòu)，這個前提對這個應(yīng)用來說肯定是成立的。

;; [示例代碼 6.6]
;; 使用靜態(tài)引用的編譯過程
(defvar *nodes* nil)

(defun defnode (&rest args)
(push args *nodes*)
args)

(defun compile-net (root)
(let ((node (assoc root *nodes*)))
(if (null node)
nil
(let ((conts (second node))
(yes (third node))
(no (fourth node)))
(if yes
(let ((yes-fn (compile-net yes))
(no-fn (compile-net no)))
#'(lambda ()
(format t "~A~%>> " conts)
(funcall (if (eq (read) 'yes)
yes-fn
no-fn))))
#'(lambda () conts))))))

6.3 展望

有許多涉及網(wǎng)絡(luò)的程序都能通過把節(jié)點編譯成閉包的形式來實現(xiàn)。閉包作為數(shù)據(jù)對象，和各種數(shù)據(jù)結(jié)構(gòu)一樣能用來表現(xiàn)事物的屬性。這樣做需要一些和習(xí)慣相左的思考方式，但是作為回報的是更為迅速，更為優(yōu)雅的程序。

宏在相當(dāng)程度上將有助于我們把閉包用作一種表達(dá)方式。"用閉包來表示" 是 "編譯" 的另外一種說法。而且由于宏是在編譯時完成它們的工作的，因而它們理所應(yīng)當(dāng)?shù)鼐褪沁@種技術(shù)的最佳載體。在介紹了宏技術(shù)之后，第 23 章和第 24 章里會呈上更大規(guī)模的程序，這些程序?qū)褂眠@里曾用過的方法寫成。