## 第 6 章 函數作為表達方式 通常說來，數據結構被用來描述事物。可以用數組描述坐標變換，用樹結構表示命令的層次結構，而用圖來表示鐵路網。在 Lisp 里，我們常會使用閉包作為表現形式。在閉包里，變量綁定可以保存信息，也能扮演在復雜數據結構中指針的角色。如果讓一組閉包之間共享綁定，或者讓它們之間能相互引用，那么我們就可以創建混合型的對象類型，它同時繼承了數據結構和程序邏輯兩者的優點。 其實在表象之下，共享綁定就是指針。閉包只是讓我們能在更高的抽象層面上操作指針。通過用閉包來表示我們以往用靜態數據結構表示的對象，就往往可能得到更為優雅，效率更好的程序。 ### 6.1 網絡 閉包有三個有用的特性：它是動態的，擁有局部狀態，而且我們可以創建閉包的多個實例。那么帶有局部狀態的動態對象的多個拷貝能在什么地方一展身手呢？答案是：和網絡有關的程序。許多情況下，我們可以把網絡中的節點表示成閉包。閉包在擁有其局部狀態的同時，它還能引用其它閉包。因而，一個表示網絡中節點的閉包是能夠知道作為它發送數據目的地的其他幾個節點（閉包） 的。換句話說，我們有能力把網絡結構直接翻譯成代碼。 在本節和下一節里，我們會分別了解兩種遍歷網絡的方法。首先我們會按照傳統的辦法，即把節點定義成結構體，并用與之分離的代碼來遍歷網絡。接著，在下一節我們將會用一個統一的抽象模型來構造通用功能的程序。 ~~~ ;; [示例代碼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 ~~~ 我們將選擇一個最簡單的應用作為例子：一個能運行 twenty questions 的程序。我們的網絡將會是一棵二叉樹。每個非葉子節點都會含有一個是非題，并且根據對這個問題的回答，遍歷過程會在左子樹或者右子樹兩者中擇一，繼續往下進行。葉子節點將會含有所有的返回值。當遍歷過程遇到葉子節點時，葉子節點的值會被作為遍歷過程的返回值返回。如 [示例代碼 6.1] 所示，是程序運行一輪 twenty questions 的樣子。 從習慣的辦法著手，可能就是先定義某種數據結構來表示節點。節點應該包含這幾樣信息：它是否是葉子節點；如果是的話，那返回值是什么，倘若不是，要問什么問題；還有與答案對應的下個節點是什么樣的。 譯者注：twenty questions 曾是一檔國外很流行的電視智力節目，同時也是人工智能的重要題材。 ~~~ ;; [示例代碼 6.2] ;; 節點的表示方法及其定義 (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] 里定義了一個信息足夠詳盡的數據結構。它的設計目標是讓數據所占的空間最小化。contents 字段中要么是問題要么是返回值。如果該節點不是葉子節點，那么yes 和no 字段會告訴我們與問題的答案對應的去向；如果節點是個葉子節點，我們自然會知道這一點，因為這些字段會是空的。全局的*nodes* 是一個哈希表，在表中，我們會用節點的名字來索引節點。最后，defnode 會新建一個節點（兩種節點都可以），并把它保存到*nodes*?中。有了這些原材料，我們就可以定義樹的第一個節點了： ~~~ (defnode 'people "Is the person a man?" 'male 'female) ~~~ [示例代碼 6.3] 中所示的網絡正好足夠我們運行6.1 中所示的一輪游戲。 ~~~ ;; [示例代碼 6.3] ;; 作為樣例的網絡 (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] ;; 用來遍歷網絡的函數 (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))))) ~~~ 現在，我們要做的就是寫一個能遍歷這個網絡的函數了，這個函數應該打印出問題，并順著答案所指示的路徑走下去。函數的名字是 run-node ，如 [示例代碼 6.4] 所示。給出一個名字，我們就根據名字找到對應的節點。如果該節點不是葉子節點，就把 contents 作為問題打印出來，按照答案不同，我們繼續順著兩條可能的途徑之一繼續遍歷。如果該節點是葉子節點，run-node 會徑直返回 contents。使用 [示例代碼 6.3] 中定義的網絡，這個函數就能生成 [示例代碼 6.1] 中的輸出信息。 ### 6.2 編譯后的網絡 在上一節，我們編寫了一個使用網絡的程序，也許使用任何一種語言都能寫出這樣的程序。的確，這個程序太簡單了，看上去似乎很難把它寫成另一個模樣。但是事實上，我們可以把程序打理得更簡潔一些。 ~~~ ;; [示例代碼 6.5] ;; 編譯成閉包形式的網絡 (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] 就是明證。這是讓我們的網絡運行起來所需要的所有代碼。在這里，不再把節點定義成一個結構， 也沒有用一個單獨的函數來遍歷這些節點，而是把節點表示成閉包。原來保存在數據結構里的數據現在棲身于閉包里的變量綁定中。沒有必要運行 run-node 了，它已經隱含在了節點自身里面。要啟動遍歷過程， 只消 funcall 一下起始的那個節點就行了： ~~~ (funcall (gethash 'people *nodes*)) Is the person a man >> ~~~ 自此，接下來的人機對話就和上個版本的實現一樣了。 借助把節點都表示成閉包的方式，我們得以將 twenty questions 網絡完全轉化成代碼（而非數據）。正如我們所看到的，程序代碼必須在運行時按照名字來查找節點函數。然而，如果我們確信網絡在運行的時候不會重新定義，那就可以更進一步：讓節點函數直接調用它們的下一站目標函數，而不必再動用哈希表了。 如 [示例代碼 6.6] 所示，是新版的程序代碼。現在，*node* 從哈希表改成了一個列表。像以前一樣，所有的節點還 是用defnode 定義的，不過定義時并不會生成閉包。在定義好所有的節點之后，我們就調用 compile-net 來一次性地編譯整個網絡。這個函數遞歸地進行處理，一直往下，直至樹的葉子節點，在遞歸過程層層返回時，每一步都返回了兩個目標函數對應的節點（或稱函數），而不僅僅是給出它們的名字。 當最外面的 compile-net 調用返回時，它給出的函數將表示一個我們所需的那部分網絡。 ~~~ > (setq n (compile-net 'people)) #<Compiled-Function BF3C06> > (funcall n) Is the person a man? >> ~~~ 注意到，compile-net 進行的編譯有兩層含義。按照通常編譯的含義，它把網絡的抽象表示翻譯成了代碼。 更進一層，如果compile-net 自身被編譯的話，那它就會返回編譯后的函數。（見第17頁） 在編譯好網絡之后，由defnode 構造的列表就沒用了。如果切斷列表與程序的聯系（例如將*nodes* 設為nil），垃圾收集器就會回收它。 這個版本的程序假定程序中的網絡是一種樹結構，這個前提對這個應用來說肯定是成立的。 ~~~ ;; [示例代碼 6.6] ;; 使用靜態引用的編譯過程 (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 展望 有許多涉及網絡的程序都能通過把節點編譯成閉包的形式來實現。閉包作為數據對象，和各種數據結構一樣能用來表現事物的屬性。這樣做需要一些和習慣相左的思考方式，但是作為回報的是更為迅速，更為優雅的程序。 宏在相當程度上將有助于我們把閉包用作一種表達方式。"用閉包來表示" 是 "編譯" 的另外一種說法。而且由于宏是在編譯時完成它們的工作的，因而它們理所應當地就是這種技術的最佳載體。在介紹了宏技術之后，第 23 章和第 24 章里會呈上更大規模的程序，這些程序將會使用這里曾用過的方法寫成。