## 第 2 章 函數 函數不僅是 Lisp 程序的根基，它同時也是 Lisp 語言的基石。在多數語言里，'+' (加法) 操作符都和用戶自定義的函數多少有些不一樣。但 Lisp 采用了函數應用作為其統一模型，來描述程序能完成的所有計算。 在Lisp 里，'+' 和你自己定義的函數一樣，也是個函數。 事實上，除了少數稱為*特殊形式*（special form）的操作符之外， Lisp 的核心就是一個函數的集合。有什么可以阻止你給這個集合添磚加瓦呢？答案是: > 沒有 如果你覺得某件事 Lisp 應該能做，那你完全可以把它寫出來，然后你的新函數可以享有和內置函數同等的待遇。 這對程序員產生了深遠的影響。它意味著，或可以把任何一個新加入的函數都看作是對Lisp 語言的擴充，也可以把它當成特定應用的一部分。典型情況是，有經驗的Lisp 程序員兩邊都寫一些，并不斷調整語言和應用之間的界限，直到它們彼此完美地配合在一起。本書要講述的正是如何在語言和應用之間達到最佳的結合點。由于我們向這一最終目標邁進的每一步都依賴于函數，所以自然應該先從函數開始。 ### 2.1 作為數據的函數 有兩點讓 Lisp 函數與眾不同。一是前面提到的: > Lisp 本身就是函數的集合。 這意味著我們可以自己給 Lisp 增加新的操作符。另一個關于函數的重要問題，是要了解： > 函數也是 Lisp 的對象。 Lisp 提供了其他語言擁有的大多數數據類型。我們有整數和浮點數、字符串、數組、結構體等等。但 Lisp 還支持一種乍看之下讓人奇怪的數據類型：函數。幾乎所有編程語言都提供某種形式的函數或過程。那么，說 "Lisp 把函數作為一種數據類型提供出來" 又是什么意思呢？這意味著在 Lisp 里我們可以像對待其他熟悉的數據類型那樣來對待函數，就像整數那樣：在運行期創建一個新函數，把函數保存在變量和結構體里面，把它作為參數傳給其他函數，還有把它作為函數的返回值。 這種在運行期創建和返回函數的能力特別有用。這個優點可能初看起來還讓人心存疑慮，就好像那些可以在某些計算機上運行的可以修改自身的機器語言程序一樣。但對于 Lisp 來說，在運行期創建新函數的技術簡直就是家常便飯。 ### 2.2 定義函數 多數人的學習會從 "用 defun 創建函數" 開始。下面的表達式定義了一個叫 double 的函數，其返回值是傳入參數的兩倍。 ~~~ > (defun double (x) (* x 2)) DOUBLE ~~~ 如果把上述定義送入 Lisp ，我們就可以在其他函數里調用 double ，或者從最頂層(toplevel) 調用： ~~~ > (double 1) 2 ~~~ Lisp 的源代碼文件通常主要由類似這樣的函數定義組成，這有幾分類似 C 或者 Pascal 這些語言中的過程定義。但接下來就大不一樣了。這些 defun 并不只是過程定義，它們還是 Lisp 調用。在我們了解了 defun 背后的運作機制后，這種區別會更明顯。 同時，函數本身也是對象。defun 實際所做的就是構造這樣的對象，然后把它保存在第一個參數名下。因此我們既可以調用 double ，也可以持有這個名字對應的函數對象。要得到這個對象，通常的做法是使用 #' (井號 + 單引號) 操作符。這個操作符的作用可以理解成：它能將名字映射到實際的函數對象。把它放到double 的前面： ~~~ > #'double #<Interpreted-Function C66ACE> ~~~ 我們就有了上面定義所創建的實際對象。盡管它的輸出形式在不同的Lisp 實現中各不相同，但 Common Lisp 的函數是第一類(first-class) 對象，它和整數和字符串這些更熟悉的對象享有完全相同的權利。所以，我們既可以把這個函數作為參數傳遞，也可以把它作為返回值返回，還能把它存在數據結構里，等等： ~~~ > (eq #'double (car (list #'double))) T ~~~ 甚至可以不用 defun 來定義函數。和大多數 Lisp 對象一樣，我們也可以通過其文字表達的形式來引用它。 就像當我們提到一個整數時，只要使用這個數字本身那樣。而表示字符串時，用括在兩個雙引號之間的一 系列字符。如果要表達的是一個函數，我們可以使用一種稱為–表達式(lambda-expression) 的東西。–表達式是一個由三個部分組成的列表：lambda 符號、參數列表，以及包含零個以上表達式的主體。下面這個–表達式相當于一個和double 等價的函數： ~~~ (lambda (x) (* x 2)) ~~~ 它描述了一個函數，函數的參數是 ，并且返回 。–表達式也可以看作是函數的名字。如果說double 是個正規的名字，就像 "米開朗琪羅"，那么 (lambda (x) (* x 2)) 就相當于具體的描述，比如 "完成西斯庭大教堂穹頂壁畫的人" 。通過把一個井號和引號 "#" 放在表達式的前面，我們就得到了相應的函數： ~~~ > #'(lambda (x) (* x 2)) #<Interpreted-Function C674CE> ~~~ 這個函數和 double 的表現相同，但它們是兩個不同的對象。 在函數調用中，函數名出現在前面，接下來是參數： ~~~ > (double 3) 6 ~~~ 由于–表達式同時也是函數的名字，因而它也可以出現在函數調用的最前面： ~~~ > ((lambda (x) (* x 2)) 3) 6 ~~~ 在 Common Lisp 里，我們可以同時擁有名為double 的函數和變量。 ~~~ > (setq double 2) 2 > (double double) 4 ~~~ 當名字出現在函數調用的首位，或者前置 #' 的時候，它被認為是函數。其他場合下它被當成變量名。 因此我們說 Common Lisp 擁有獨立的函數和變量名字空間 (name-space)。我們可以同時有一個叫 foo 的變量以及一個叫 foo 的函數，而且它們不必相同。這種情形可能會讓人不解，并且可能在一定程度上影響代碼的可讀性，但這是 Common Lisp 程序員必須面對的問題。 Common Lisp 還提供了兩個函數用于將符號映射到它所代表的函數或者變量，以備不時之需。symbol-value 函數以一個符號為參數，返回對應變量的值： 譯者注：擁有分開的變量和函數命名空間的 Lisp 稱為 Lisp-2，在另一類 Lisp-1 下，變量和函數定義在同一命名空間里，最著名的 這種 Lisp 方言是 Scheme。關于 Lisp-1 vs. Lisp-2 在網上有很多討論，一般觀點認為 Lisp-1 對于編譯器來說更難實現。 ~~~ > (symbol-value 'double) 2 ~~~ 而 symbol-function 則用來得到一個全局定義的函數： ~~~ > (symbol-function 'double) #<Interpreted-Function C66ACE> ~~~ 注意到，由于函數也是普通的對象，所以變量也可以把函數作為它的值： ~~~ > (setq x #'append) #<Compiled-Function 46B4BE> > (eq (symbol-value 'x) (symbol-function 'append)) T ~~~ 深入分析的話，defun 實際上是把它第一個參數的 symbol-function 設置成了用它其余部分構造的函數。 下面兩個表達式完成的功能基本相同： ~~~ (defun double (x) (* x 2)) (setf (symbol-function 'double) #'(lambda (x) (* x 2))) ~~~ 所以，defun 和其它語言的過程定義的效果相同， 把一個名字和一段代碼關聯起來。但是內部機制完全不一樣。我們可以不用defun 來創建函數，函數也不一定要保存在某個符號的值里面。和任何語言里定義過程的方法一樣，defun 的內部實現使用的也是一種更通用的機制：構造一個函數，然后把它和某個名字關聯起來，這兩步其實是兩個獨立的操作。當我們不需要利用Lisp 中所謂函數所有的通用性時，用 defun 來生成函數就和在其他限制更多的語言里定義函數一樣的簡單。 ### 2.3 函數型參數 函數同為數據對象，就意味著我們可以像對待其他對象那樣把它傳遞給其他函數。這種性質對于Lisp 這種自底向上程序設計至關重要。 如果一門語言把函數作為數據對象，那么它必然也會提供某種方式讓我們能調用它們。在Lisp 里，這個函數就是apply。一般而言，我們用兩個參數來調用apply ：函數和它的參數列表。下列四個表達式的效果是一樣的： ~~~ (+ 1 2) (apply #'+ '(1 2)) (apply (symbol-function '+) '(1 2)) (apply #'(lambda (x y) (+ x y)) '(1 2)) ~~~ 在Common Lisp 里，apply 可以帶任意數量的參數。其中，最前面給出的函數將被應用到一個列表，該列表由其余參數cons 到最后一個參數產生，而最后的參數也是個列表。所以表達式 ~~~ (apply #'+ 1 '(2)) ~~~ 和前面四個表達式等價。如果不方便以列表的形式提供參數，可以使用funcall ，它和apply 唯一的區別也在于此。表達式 ~~~ (funcall #'+ 1 2) ~~~ 和上面的那些表達式效果相同。 很多內置的Common Lisp 函數都可以把函數作為參數。這些內置函數中，最常用的是映射類的函數。例如 mapcar 帶有兩個以上參數 一個函數加上一個以上的列表(每個列表都分別是函數的參數)，然后它可以將參數里的函數依次作用在每個列表的元素上： ~~~ > (mapcar #'(lambda (x) (+ x 10)) '(1 2 3)) (11 12 13) > (mapcar #'+ '(1 2 3) '(10 100 1000)) (11 102 1003) ~~~ Lisp 程序經常需要對列表中的每一項都做一些操作，然后再把結果同樣以列表的形式返回。上面的第一個例子介紹的步驟，就是用來完成這個工作的常用辦法：生成一個你所需功能的函數，然后用 mapcar 把它映射到列表上。 我們已經了解到，"把函數當作數據來使用" 的能力給編程帶來了極大的便利。在許多語言里，即便我們可以像 mapcar 那樣把函數作為參數傳遞進去，那也只能是事先在代碼中定義好的函數。如果只有一小段代碼需要把列表中的每項都加上10，我們就只得專門定義一個叫plus_ten 或者類似名字的函數，而這個函數只是在這段代碼中才會用到。有了–表達式，就可以直接表達函數了。 Common Lisp 和它以前方言之間一個最大的區別就是它擁有大量使用函數型參數的內置函數。其中，除了隨處可見的mapcar ，還有兩個最常用的函數就是sort 和 remove-if 。前者是通用的排序函數。它接受一個列表和一個謂詞，然后使用這個謂詞，對原列表中的元素兩兩進行比較，并返回所得排序后的列表。 ~~~ > (sort '(1 4 2 5 6 7 3) #'<) (1 2 3 4 5 6 7) ~~~ 有種辦法可以幫助記憶sort 函數工作方式，如果你用 排序一個沒有重復元素的列表，那么當你把 應用到結果列表的時候，它將會返回真。 假使Common Lisp 里沒有remove-if 函數的話，那它就應該是你寫的第一個工具。它接受一個函數和列表，并且返回這個列表中所有調用那個函數返回假的元素。 ~~~ > (remove-if #'evenp '(1 2 3 4 5 6 7)) (1 3 5 7) ~~~ 作為把函數作為參數的函數示例，這里給出一個remove-if 的受限版本： ~~~ (defun our-remove-if (fn lst) (if (null lst) nil (if (funcall fn (car lst)) (our-remove-if fn (cdr lst)) (cons (car lst) (our-remove-if fn (cdr lst)))))) ~~~ 注意到在這個定義里fn 并沒有前綴#' 。因為函數就是數據對象，變量可以將一個函數作為它的正規值。 這就是事情的來龍去脈。#' 僅用來引用那些以符號命名的函數 通常是用defun 全局定義的。 正如第4 章將要展示的那樣，編寫那種接受函數作為參數的新工具是自下而上程序設計的重要環節。 Common Lisp 自帶了大量的工具函數，很多你想要的可能已經有了。但無論是使用內置的工具，比如sort ， 還是編寫你的實用工具，基本原則是一樣的：與其把功能寫死，不如傳進去一個函數參數。 ### 2.4 作為屬性的函數 函數作為Lisp 對象這一事實也創造了條件，讓我們能夠編寫出那種可以隨時擴展以滿足新需求的程序。 假設我們需要寫一個以動物種類作為參數并產生相應行為的函數。在大多數語言中，會使用case 語句達到這個目的，Lisp 里也可以用同樣的辦法： ~~~ (defun behave (animal) (case animal ~~~ 譯者注：即 (apply #'< '(1 2 3 4 5 6 7)) T 。 ~~~ (dog (wag-tail) (bark)) (rat (scurry) (squeak)) (cat (rub-legs) (scratch-carpet)))) ~~~ 如果要增加一種新動物該怎么辦呢？如果計劃增加新的動物，那么把behave 定義成下面的樣子可能會更好一些： ~~~ (defun behave (animal) (funcall (get animal 'behavior))) ~~~ 同時把每種個體動物的行為以單獨的函數形式保存，例如，存放在以它們名字命名的屬性列表里： ~~~ (setf (get 'dog 'behavior) #'(lambda () (wag-tail) (bark))) ~~~ 用這種方式處理的話，要增加一種新動物，所有你需要做的事情就是定義一個新的屬性。一個函數都不用重寫。 上述第二種方法盡管更靈活，但看上去要慢些。實際上也是如此。如果速度很關鍵，我們可以把屬性表換成結構體，而且特別要用編譯過的函數代替解釋性的函數。(第2.9 節解釋了怎樣做到這些。) 使用了結構體和編譯函數，上面的代碼就會靈活，而且其速度可以達到甚至超過那些使用case 語句的實現。 這樣使用函數相當于面向對象編程中的方法概念。總的來說，方法是作為對象屬性的一種函數，這也正是 我們手里有的。如果把繼承引入這個模型，你就得到了面向對象編程的全部要素。第25 章將用少得驚人的代碼來說明這一點。 面向對象編程的一大亮點是它能讓程序可擴展。這一點在Lisp 界激起的反響要小很多，因為在這里，人們早已把可擴展性當成理所當然的事情了。如果我們要的可擴展性不是很依賴繼承，那么純Lisp 可能就已經足夠應付了。 ### 2.5 作用域 Common Lisp 是一種詞法作用域(lexically scope) 的Lisp。Scheme 是最早的有詞法作用域的方言；在它之前，動態作用域(dynamicscope) 被視為Lisp 的本質屬性之一。 詞法作用域和動態作用域的區別在于語言處理自由變量的方式不同。當一個符號被用來表達變量時，我們稱這個符號在表達式中是被綁定的(bound)，這里的變量可以是參數，也可以是來自像let 和do 這樣的變量綁定操作符。如果符號不受到約束，就認為它是自由的。下面的例子具體說明了作用域： ~~~ (let ((y 7)) (defun scope-test (x) (list x y))) ~~~ 在函數表達式里，x 是受約束的，而y 是自由的。自由變量有意思的地方就在于，這種變量應有的值并不那么顯而易見。一個約束變量的值是確信無疑的 當調用scope-test 時，x 的值就是通過參數傳給它的值。但y 的值應該是什么呢？這要看具體方言的作用域規則。 在動態作用域的Lisp 里，要想找出當scope-test 執行時自由變量的值，我們要往回逐個檢查函數的調用鏈。當發現y 被綁定時，這個被綁定的值即被用在scope-test 中。如果沒有發現，那就取y 的全局值。這樣，在用動態作用域的Lisp 里，在調用的時候y 將會產生這樣的值： ~~~ > (let ((y 5)) (scope-test 3)) (3 5) ~~~ 如果是動態作用域，那么在定義 scope-test 時，把y 綁定到7 就沒有任何意義了。調用 scope-test 時，y 只有一個值，就是 5。 在詞法作用域的 Lisp 里，我們不再往回逐個檢查函數的調用鏈，而是逐層檢查定義這個函數時，它所處的各層外部環境。在一個詞法作用域Lisp 里，我們的示例將捕捉到定義scope-test 時，變量y 的綁定。所以可以在 Common Lisp 里觀察到下面的現象： ~~~ > (let ((y 5)) (scope-test 3)) (3 7) ~~~ 這里將y 綁定到5。這樣做對函數調用的返回值不會有絲毫影響。 盡管你仍然可以通過將變量聲明為special 來得到動態作用域，但是詞法作用域是Common Lisp 的默認行為。總的來說，Lisp 社區對昨日黃花的動態作用域幾乎沒什么留戀。因為它經常會導致痛苦而又難以捉摸的bug。而詞法作用域不僅僅是一種避免錯誤的手段。在下一章我們會看到，它同時也帶來了一些嶄新的編程技術。 ### 2.6 閉包 由于Common Lisp 是詞法作用域的，所以如果定義含有自由變量的函數，系統就必須在函數定義時保存那些變量的綁定。這種函數和一組變量綁定的組合稱為閉包。我們發現，閉包在各種場合都能大顯身手。 閉包在 Common Lisp 程序中如此無所不在，以至于你可能已經用了它卻渾然不知。每當你傳給 mapcar 一 個包含自由變量的前綴#' 的–表達式時，你就在使用閉包。例如，假設我們想寫一個函數，它接受一個數列并且給每個數加上相同的數字。這個list+ 函數 ~~~ (defun list+ (lst n) (mapcar #'(lambda (x) (+ x n)) lst)) ~~~ 將做到我們想要的： ~~~ > (list+ '(1 2 3) 10) (11 12 13) ~~~ 如果仔細觀察list+ 里傳給mapcar 的那個函數，就可以發現它實際上是個閉包。那個n 是自由的，其綁定來自周圍的環境。在詞法作用域下，每一次這樣使用映射函數都將導致一個閉包的創建。 閉包在 Abelson 和 Sussman 的經典教材《計算機程序的構造和解釋》一書中扮演了更加重要的角色。閉包是帶有局部狀態的函數。使用這種狀態最簡單的方式是如下的情況： ~~~ (let ((counter 0)) (defun new-id () (incf counter)) (defun reset-id () (setq counter 0))) ~~~ 這兩個函數共享一個計數器變量。前者返回計數器的下一個值，后者把計數器重置到0。這種方式避免了對計數器變量非預期的引用，盡管同樣的功能也可以用一個全局的計數器變量完成。 如果返回的函數能帶有局部狀態，那么也會很有幫助。例如這個make-adder 函數 ~~~ (defun make-adder (n) #'(lambda (x) (+ x n))) ~~~ 接受一個數值參數，然后返回一個閉包，當調用后者時，能夠把之前那個數加到它的參數上。我們可以根據需要生成任意數量的這種加法器： 在動態作用域(作為默認作用域) 的情況下，這種表達方式也會一樣工作，雖然其原理不同 前提是mapcar 沒有一個參數的名字是 "n" 。 ~~~ > (setq add2 (make-adder 2) add10 (make-adder 10)) #<Interpreted-Function BF162E> > (funcall add2 5) 7 > (funcall add10 3) 13 ~~~ 在 make-adder 返回的那些閉包里，內部狀態都是固定的，但其實也可以生成那種能應要求改變自己狀態的閉包。 ~~~ (defun make-adderb (n) #'(lambda (x &optional change) (if change (setq n x) (+ x n)))) ~~~ 這個新版本的 make-adder 函數返回一個閉包，如果調用它時只傳入一個參數，那么其行為和舊版本是一樣的。 ~~~ > (setq addx (make-adderb 1)) #<Interpreted-Function BF1C66> > (funcall addx 3) 4 ~~~ 但是，如果這個新加法器的第二個參數不為空的話，在它內部，n 的拷貝將被設置成第一個參數的值： ~~~ > (funcall addx 100 t) 100 > (funcall addx 3) 103 ~~~ 甚至有可能返回共享同一數據對象的一組閉包。圖2.1 中的函數被用來創建原始數據庫。它接受一個關聯表(db)，并相應返回一個由查詢、追加和刪除這三個閉包所組成的列表。 ~~~ (defun make-dbms (db) (list #'(lambda (key) (cdr (assoc key db))) #'(lambda (key val) (push (cons key val) db) key) #'(lambda (key) (setf db (delete key db :key #'car)) key))) ~~~ 圖2.1： 一個列表里的三個閉包 每次調用make-dbms 都會創建新的數據庫 這個新數據庫就是一組新函數，它們把自己的共享拷貝封存在一張關聯表(assoc-list) 里面。 ~~~ > (setq cities (make-dbms '((boston . us) (paris .france)))) (#<Interpreted-Function 8022E7> #<Interpreted-Function 802317> #<Interpreted-Function 802347>) ~~~ 數據庫里實際的關聯表是對外界不可見的，我們甚至不知道它是個關聯表 但是可以通過構成 cities 的那些函數訪問到它： ~~~ > (funcall (car cities) 'boston) US > (funcall (second cities) 'london 'england) LONDON > (funcall (car cities) 'london) ENGLAND ~~~ 調用列表的 car 多少有些難看。實際的程序中，函數訪問的入口可能隱藏在結構體里。當然也可以設法更簡潔地使用它們 數據庫可以通過這樣的函數間接訪問： ~~~ (defun lookup (key db) (funcall (car db) key)) ~~~ 無論怎樣，這種改進都不會影響到閉包的基本行為。 實際程序中的閉包和數據結構往往比我們在make-adder 和make-dbms 里看到的更加精巧。這里用到的單個共享變量也可以發展成任意數量的變量，每個都可以約束到任意的數據結構上。 閉包是 Lisp 的眾多獨特和實實在在的優勢之一。如果下些工夫的話，還可能把有的 Lisp 程序翻譯成能力稍弱的語言，但只要試著去翻譯上面那些使用了閉包的程序，你就會明白這種抽象幫我們省去了多少工作。 后續章節將進一步探討閉包的更多細節。第5 章展示了如何用它們構造復合函數，接著在第6 章里會繼續介紹如何用它們替代傳統的數據結構。 ### 2.7 局部函數 在用–表達式定義函數時，我們就會面對一個使用 defun 時所沒有的限制：使用–表達式定義的函數由于它沒有名字，因此也就沒有辦法引用自己。這意味著在 Common Lisp 里，不能用 lambda 定義遞歸函數。 如果我們想要應用某些函數到一個列表的所有元素上，可以使用最熟悉的Lisp 語句： ~~~ > (mapcar #'(lambda (x) (+ 2 x)) '(2 5 7 3)) (4 7 9 5) ~~~ 要是想把遞歸函數作為第一個參數送給mapcar 呢？如果函數已經用defun 定義了，我們就可以通過名字簡單地引用它： ~~~ > (mapcar #'copy-tree '((a b) (c d e))) ((A B) (C D E)) ~~~ 但現在假設這個函數必須是一個閉包，它從mapcar 所處的環境獲得綁定。在我們的list+ 例子里， ~~~ (defun list+ (lst n) (mapcar #'(lambda (x) (+ x n)) lst)) ~~~ mapcar 的第一個參數是 #'(lambda (x) (+ x n)) ，它必須要在list+ 里定義，原因是它需要捕捉n 的綁定。到目前為止都還一切正常，但如果要給mapcar 傳遞一個函數，而這個函數在需要局部綁定的同時也是遞歸的呢？我們不能使用一個在其他地方通過defun 定義的函數，因為這需要局部環境的綁定。并且我們也不能使用lambda 來定義一個遞歸函數，因為這個函數將無法引用其自身。 Common Lisp 提供了labels 幫助我們跳出這個兩難的困境。除了在一個重要方面有所保留外，labels 基本可以看作是let 的函數版本。labels 表達式里的每個綁定規范都必須符合如下形式： ~~~ (<name> <parameters> . <body>) ~~~ 在labels 表達式里，?name? 將指向與下面表達式等價的函數： ~~~ #'(lambda <parameters> . <body>) ~~~ 例如， ~~~ > (labels ((inc (x) (1+ x))) (inc 3)) > 4 ~~~ 盡管如此，在let 與labels 之間有一個重要的區別。在let 表達式里，變量的值不能依賴于同一個let 里生成的另一個變量 就是說，你不能說 ~~~ (let ((x 10) (y x)) y) ~~~ 然后認為這個新的 能反映出那個新 的值。相反，在labels 里定義的函數 的函數體里就可以引用那里定義的其他函數，包括 本身，這就使定義遞歸函數成為可能。 使用labels ，我們就可以寫出類似list+ 這樣的函數了，但這里 mapcar 的第一個參數是遞歸函數： ~~~ (defun count-instances (obj lsts) (labels ((instances-in (lst) (if (consp lst) (+ (if (eq (car lst) obj) 1 0) (instances-in (cdr lst))) 0))) (mapcar #'instances-in lsts))) ~~~ 該函數接受一個對象和一個列表，然后分別統計出該對象在列表的每個元素(作為列表) 中出現的次數，把這些次數組成列表，并返回它： ~~~ > (count-instances 'a '((a b c) (d a r p a) (d a r) (a a))) (1 2 1 2) ~~~ ### 2.8 尾遞歸 遞歸函數自己調用自己。如果函數調用自己之后不做其他工作，這種調用就稱為尾遞歸(tail-recursive)。 下面這個函數不是尾遞歸的 ~~~ (defun our-length (lst) (if (null lst) 0 (1+ (out-length (cdr lst))))) ~~~ 因為在從遞歸調用返回之后，我們又把結果傳給了1+。而下面這個函數就是尾遞歸的? ~~~ (defun our-find-if (fn lst) (if (funcall fn (car lst)) (car lst) (our-find-if fn (cdr lst)))) ~~~ 因為通過遞歸調用得到的值被立即返回了。 尾遞歸是一種令人青睞的特性，因為許多Common Lisp 編譯器都可以把尾遞歸轉化成循環。若使用這種編譯器，你就可以在源代碼里書寫優雅的遞歸，而不必擔心函數調用在運行期產生的系統開銷。 如果一個函數不是尾遞歸的話，常常可以把一個使用累積器(accumulator) 的局部函數嵌入到其中，用這種方法把它轉換成尾遞歸的形式。在這里，累積器指的是一個參數，它代表著到目前為止計算得到的值。例如our-length 可以轉換成 ~~~ (defun our-length (lst) (labels ((rec (lst acc) (if (null lst) ~~~ ?原書勘誤：如果沒有找到期望的元素，our-find-if 函數將無限遞歸下去。 ~~~ acc (rec (cdr lst) (1+ acc))))) (rec lst 0))) ~~~ 上面定義的函數里，到現在為止，所有見到的列表元素的總數都被放在了另一個參數acc 里。當遞歸運行到達列表的結尾，acc 的值就是總的長度，只要直接返回它就可以了。通過在調用樹從上往下走的過程中累計這個值，而不是從下往上地在返回的時候再計算它，我們就可以將rec 尾遞歸化。 許多 Common Lisp 編譯器都能做尾遞歸優化，但這并不是所有編譯器的默認行為。所以在編寫尾遞歸函數時，你應該把 ~~~ (proclaim '(optimize speed)) ~~~ 寫在文件的最前面，確保編譯器不會辜負你的苦心，進行期望的優化。? 如果提供尾遞歸和類型聲明，現有的Common Lisp 編譯器就能生成運行速度能與C 程序相媲美，甚至超過? 它的代碼。RichardGabriel 以下面的函數作為例證，它從1 累加到n ： ~~~ (defun triangle (n) (labels ((tri (c n) (declare (type fixnum n c)) (if (zerop n) c (tri (the fixnum (+ n c)) (the fixnum (- n 1)))))) (tri 0 n))) ~~~ 這就是快速的Common Lisp 代碼的典范。一開始就用這樣寫程序可能會覺得不太自然。可能更好的辦法 是先用自己最習慣的方式編寫函數，然后在必要時把它轉化成尾遞歸的等價形式。 ### 2.9 編譯 Lisp 函數可以單獨編譯或者按文件編譯。如果你只是在toplevel 下輸入一個defun 表達式， ~~~ > (defun foo (x) (1+ x)) FOO ~~~ 多數實現會創建相應的解釋函數(interpretedfunction)。你可以使用compiled-function-p 來檢查函數是 否被編譯過： ~~~ > (compiled-function-p #'foo) NIL ~~~ 我們可以把函數名傳給compile ，用這種辦法來編譯foo ~~~ > (compile 'foo) FOO ~~~ 這樣可以編譯foo 的定義，并把之前的解釋版本換成編譯版本。 ~~~ > (compiled-function-p #'foo) T ~~~ 編譯和解釋函數都是Lisp 對象，兩者的行為表現是相同的，只是對 compiled-function-p 的反應不一樣。 直接給出的函數也可以編譯：compile 希望它的第一個參數是個名字，但如果你給它的是nil ，它就會編譯第二個參數給出的–表達式。 ~~~ > (compile nil '(lambda (x) (+ x 2))) #<Compiled-Function BF55BE> ~~~ ?(optimize speed) 的聲明應該是(optimize (speed 3)) 的簡寫。但是有一種 Common Lisp 實現，若使用前一種聲明，則會進行尾遞歸優化，而后一種聲明則不會產生這種優化。 如果你同時給出名字和函數參數，compile 的效果就相當于編譯一個defun ： ~~~ > (progn (compile 'bar '(lambda (x) (* x 3))) (compiled-function-p #'bar)) T ~~~ 把compile 集成進語言里意味著程序可以隨時構造和編譯新函數。不過，顯式調用compile 和調用eval 一樣，都屬于非常規的手段，同樣要多加小心。? 當第2.1 節里說在運行時創建新函數屬常用編程技術時， 它指的是從類似 make-adder 那樣的函數中生成的閉包，并非指從原始列表里調用compile 得到的新函數。調用 compile 并不屬于常用的編程技術，相反，它極少會用到。所以要注意，若非必要，盡量避免使用它。除非你在Lisp 之上實現另一種語言，但即使如此，用宏也有可能達到同樣的目的。 有兩類函數不能被作為參數送給compile。根據 ???2(667 頁)，你不能編譯"在非空詞法環境中解釋性地定義出的" 函數。那就是說，在 toplevel 下，如果你定義一個帶有let 的foo ~~~ > (let ((y 2)) (defun foo (x) (+ x y))) ~~~ 那么，(compile 'foo) 是不能保證正常工作的。你也不能對已經編譯過的函數調用compile ，CLTL2 隱晦地暗示 "結果 ...是不確定的"。 通常編譯Lisp 代碼的方法，不是用compile 逐個地編譯函數，而是用compile-file 編譯整個文件。該函數接受一個文件名，然后創建源代碼的編譯版本 一般情況下，編譯出的文件和源文件有相同的基本文件名，但擴展名不一樣。編譯過的文件被加載后，compiled-function-p 對文件里定義的所有函數，返回值都是真。 后面的章節還有賴編譯帶來的另一種效果：如果當某個函數出現在另一函數中，并且外面的函數已經編譯的話，那么里面的函數也會隨之被編譯。 ???2 里并沒有明確這一行為，但所有正規的實現都支持它。 對于那些返回函數的函數來說，內層函數的編譯行為是很清楚的。當make-adder (第12 頁) 被編譯時，它將返回一個編譯過的函數： ~~~ > (compile 'make-adder) MAKE-ADDER > (compiled-function-p (make-adder 2)) T ~~~ 后面的章節將說明，這一事實對于實現嵌入式語言來說尤為重要。如果一種新語言是通過轉換實現的，而 且轉換出來的代碼是編譯過的，那么它也會產生編譯后的輸出 這個轉換過程也就成為了新語言事實上的編譯器。(在第53 頁有一個簡單的例子。) 要是有特別小的函數，就可能會有內聯編譯它的需要。否則調用這個函數的開銷可能會超出執行函數本身的開銷。如果我們定義了一個函數： ~~~ (defun 50th (lst) (nth 49 lst)) ~~~ 并且聲明： ~~~ (proclaim '(inline 50th)) ~~~ 所以只要函數一編譯過，它在引用50th 的時候就無需進行真正的函數調用了。如果我們定義并且編譯一個調用了 50th 的函數， ~~~ (defun foo (lst) (+ (50th lst) 1)) ~~~ 那么編譯foo 的同時，50th 的代碼應該被編譯進它里面。就好像我們原來寫的就是 ?第190頁解釋了顯式調用eval 有害的理由。 ?把這段代碼寫在文件里然后再編譯是沒問題的。這一限制是由于具體實現的原因，被強加在了解釋型函數上，而絕不是因為在清楚明白的詞法環境中定義函數有什么不對。 ~~~ (defun foo (lst) (+ (nth 49 lst) 1)) ~~~ 一樣。缺點是，如果我們改動了50th 的定義的話，那么就必須重新編譯foo ，否則它用的還是原來的定義。 內聯函數的限制基本上和宏差不多(見第7.9 節)。 ### 2.10 來自列表的函數 一些早期的 Lisp 方言用列表來表示函數。這賦予了程序員非同一般的編寫和執行其Lisp 程序的能力。 在Common Lisp 中，函數不再由列表構詞 優良的實現把它們編譯成本地代碼。但你仍然可以寫出那種編寫程序的程序，因為列表是編譯器的輸入。 再怎么強調 "Lisp 程序可以編寫 Lisp 程序" 都不為過，尤其是當這一事實經常被忽視時。即使有經驗的 Lisp 程序員也很少意識到他們因這種語言特性而得到的種種好處。例如，正是這個特性使得Lisp 宏如此強大。 本書里描述的大部分技術都依賴于這個能力，即編寫處理 Lisp 表達式的程序的能力。