第 2 章 函數(shù)

第 2 章 函數(shù)

函數(shù)不僅是 Lisp 程序的根基，它同時也是 Lisp 語言的基石。在多數(shù)語言里，'+' (加法) 操作符都和用戶自定義的函數(shù)多少有些不一樣。但 Lisp 采用了函數(shù)應(yīng)用作為其統(tǒng)一模型，來描述程序能完成的所有計(jì)算。

在Lisp 里，'+' 和你自己定義的函數(shù)一樣，也是個函數(shù)。

事實(shí)上，除了少數(shù)稱為特殊形式（special form）的操作符之外， Lisp 的核心就是一個函數(shù)的集合。有什么可以阻止你給這個集合添磚加瓦呢？答案是:

沒有

如果你覺得某件事 Lisp 應(yīng)該能做，那你完全可以把它寫出來，然后你的新函數(shù)可以享有和內(nèi)置函數(shù)同等的待遇。

這對程序員產(chǎn)生了深遠(yuǎn)的影響。它意味著，或可以把任何一個新加入的函數(shù)都看作是對Lisp 語言的擴(kuò)充，也可以把它當(dāng)成特定應(yīng)用的一部分。典型情況是，有經(jīng)驗(yàn)的Lisp 程序員兩邊都寫一些，并不斷調(diào)整語言和應(yīng)用之間的界限，直到它們彼此完美地配合在一起。本書要講述的正是如何在語言和應(yīng)用之間達(dá)到最佳的結(jié)合點(diǎn)。由于我們向這一最終目標(biāo)邁進(jìn)的每一步都依賴于函數(shù)，所以自然應(yīng)該先從函數(shù)開始。

2.1 作為數(shù)據(jù)的函數(shù)

有兩點(diǎn)讓 Lisp 函數(shù)與眾不同。一是前面提到的:

Lisp 本身就是函數(shù)的集合。

這意味著我們可以自己給 Lisp 增加新的操作符。另一個關(guān)于函數(shù)的重要問題，是要了解：

函數(shù)也是 Lisp 的對象。

Lisp 提供了其他語言擁有的大多數(shù)數(shù)據(jù)類型。我們有整數(shù)和浮點(diǎn)數(shù)、字符串、數(shù)組、結(jié)構(gòu)體等等。但 Lisp 還支持一種乍看之下讓人奇怪的數(shù)據(jù)類型：函數(shù)。幾乎所有編程語言都提供某種形式的函數(shù)或過程。那么，說 "Lisp 把函數(shù)作為一種數(shù)據(jù)類型提供出來" 又是什么意思呢？這意味著在 Lisp 里我們可以像對待其他熟悉的數(shù)據(jù)類型那樣來對待函數(shù)，就像整數(shù)那樣：在運(yùn)行期創(chuàng)建一個新函數(shù)，把函數(shù)保存在變量和結(jié)構(gòu)體里面，把它作為參數(shù)傳給其他函數(shù)，還有把它作為函數(shù)的返回值。

這種在運(yùn)行期創(chuàng)建和返回函數(shù)的能力特別有用。這個優(yōu)點(diǎn)可能初看起來還讓人心存疑慮，就好像那些可以在某些計(jì)算機(jī)上運(yùn)行的可以修改自身的機(jī)器語言程序一樣。但對于 Lisp 來說，在運(yùn)行期創(chuàng)建新函數(shù)的技術(shù)簡直就是家常便飯。

2.2 定義函數(shù)

多數(shù)人的學(xué)習(xí)會從 "用 defun 創(chuàng)建函數(shù)" 開始。下面的表達(dá)式定義了一個叫 double 的函數(shù)，其返回值是傳入?yún)?shù)的兩倍。

  > (defun double (x) (* x 2))
  DOUBLE

如果把上述定義送入 Lisp ，我們就可以在其他函數(shù)里調(diào)用 double ，或者從最頂層(toplevel) 調(diào)用：

  > (double 1)
  2

Lisp 的源代碼文件通常主要由類似這樣的函數(shù)定義組成，這有幾分類似 C 或者 Pascal 這些語言中的過程定義。但接下來就大不一樣了。這些 defun 并不只是過程定義，它們還是 Lisp 調(diào)用。在我們了解了 defun 背后的運(yùn)作機(jī)制后，這種區(qū)別會更明顯。

同時，函數(shù)本身也是對象。defun 實(shí)際所做的就是構(gòu)造這樣的對象，然后把它保存在第一個參數(shù)名下。因此我們既可以調(diào)用 double ，也可以持有這個名字對應(yīng)的函數(shù)對象。要得到這個對象，通常的做法是使用 #' (井號 + 單引號) 操作符。這個操作符的作用可以理解成：它能將名字映射到實(shí)際的函數(shù)對象。把它放到double 的前面：

  > #'double
  #<Interpreted-Function C66ACE>

我們就有了上面定義所創(chuàng)建的實(shí)際對象。盡管它的輸出形式在不同的Lisp 實(shí)現(xiàn)中各不相同，但 Common Lisp 的函數(shù)是第一類(first-class) 對象，它和整數(shù)和字符串這些更熟悉的對象享有完全相同的權(quán)利。所以，我們既可以把這個函數(shù)作為參數(shù)傳遞，也可以把它作為返回值返回，還能把它存在數(shù)據(jù)結(jié)構(gòu)里，等等：

  > (eq #'double (car (list #'double)))
  T

甚至可以不用 defun 來定義函數(shù)。和大多數(shù) Lisp 對象一樣，我們也可以通過其文字表達(dá)的形式來引用它。

就像當(dāng)我們提到一個整數(shù)時，只要使用這個數(shù)字本身那樣。而表示字符串時，用括在兩個雙引號之間的一

系列字符。如果要表達(dá)的是一個函數(shù)，我們可以使用一種稱為–表達(dá)式(lambda-expression) 的東西。–表達(dá)式是一個由三個部分組成的列表：lambda 符號、參數(shù)列表，以及包含零個以上表達(dá)式的主體。下面這個–表達(dá)式相當(dāng)于一個和double 等價的函數(shù)：

  (lambda (x) (* x 2))

它描述了一個函數(shù)，函數(shù)的參數(shù)是 ，并且返回 。–表達(dá)式也可以看作是函數(shù)的名字。如果說double 是個正規(guī)的名字，就像 "米開朗琪羅"，那么 (lambda (x) (* x 2)) 就相當(dāng)于具體的描述，比如 "完成西斯庭大教堂穹頂壁畫的人" 。通過把一個井號和引號 "#" 放在表達(dá)式的前面，我們就得到了相應(yīng)的函數(shù)：

  > #'(lambda (x) (* x 2))
  #<Interpreted-Function C674CE>

這個函數(shù)和 double 的表現(xiàn)相同，但它們是兩個不同的對象。

在函數(shù)調(diào)用中，函數(shù)名出現(xiàn)在前面，接下來是參數(shù)：

  > (double 3)
  6

由于–表達(dá)式同時也是函數(shù)的名字，因而它也可以出現(xiàn)在函數(shù)調(diào)用的最前面：

  > ((lambda (x) (* x 2)) 3)
  6

在 Common Lisp 里，我們可以同時擁有名為double 的函數(shù)和變量。

  > (setq double 2)
  2
  > (double double)
  4

當(dāng)名字出現(xiàn)在函數(shù)調(diào)用的首位，或者前置 #' 的時候，它被認(rèn)為是函數(shù)。其他場合下它被當(dāng)成變量名。

因此我們說 Common Lisp 擁有獨(dú)立的函數(shù)和變量名字空間 (name-space)。我們可以同時有一個叫 foo 的變量以及一個叫 foo 的函數(shù)，而且它們不必相同。這種情形可能會讓人不解，并且可能在一定程度上影響代碼的可讀性，但這是 Common Lisp 程序員必須面對的問題。

Common Lisp 還提供了兩個函數(shù)用于將符號映射到它所代表的函數(shù)或者變量，以備不時之需。symbol-value 函數(shù)以一個符號為參數(shù)，返回對應(yīng)變量的值：

譯者注：擁有分開的變量和函數(shù)命名空間的 Lisp 稱為 Lisp-2，在另一類 Lisp-1 下，變量和函數(shù)定義在同一命名空間里，最著名的

這種 Lisp 方言是 Scheme。關(guān)于 Lisp-1 vs. Lisp-2 在網(wǎng)上有很多討論，一般觀點(diǎn)認(rèn)為 Lisp-1 對于編譯器來說更難實(shí)現(xiàn)。

  > (symbol-value 'double)
  2

而 symbol-function 則用來得到一個全局定義的函數(shù)：

  > (symbol-function 'double)
  #<Interpreted-Function C66ACE>

注意到，由于函數(shù)也是普通的對象，所以變量也可以把函數(shù)作為它的值：

  > (setq x #'append)
  #<Compiled-Function 46B4BE>
  > (eq (symbol-value 'x) (symbol-function 'append))
  T

深入分析的話，defun 實(shí)際上是把它第一個參數(shù)的 symbol-function 設(shè)置成了用它其余部分構(gòu)造的函數(shù)。

下面兩個表達(dá)式完成的功能基本相同：

  (defun double (x) (* x 2))

  (setf (symbol-function 'double)
  #'(lambda (x) (* x 2)))

所以，defun 和其它語言的過程定義的效果相同， 把一個名字和一段代碼關(guān)聯(lián)起來。但是內(nèi)部機(jī)制完全不一樣。我們可以不用defun 來創(chuàng)建函數(shù)，函數(shù)也不一定要保存在某個符號的值里面。和任何語言里定義過程的方法一樣，defun 的內(nèi)部實(shí)現(xiàn)使用的也是一種更通用的機(jī)制：構(gòu)造一個函數(shù)，然后把它和某個名字關(guān)聯(lián)起來，這兩步其實(shí)是兩個獨(dú)立的操作。當(dāng)我們不需要利用Lisp 中所謂函數(shù)所有的通用性時，用 defun 來生成函數(shù)就和在其他限制更多的語言里定義函數(shù)一樣的簡單。

2.3 函數(shù)型參數(shù)

函數(shù)同為數(shù)據(jù)對象，就意味著我們可以像對待其他對象那樣把它傳遞給其他函數(shù)。這種性質(zhì)對于Lisp 這種自底向上程序設(shè)計(jì)至關(guān)重要。

如果一門語言把函數(shù)作為數(shù)據(jù)對象，那么它必然也會提供某種方式讓我們能調(diào)用它們。在Lisp 里，這個函數(shù)就是apply。一般而言，我們用兩個參數(shù)來調(diào)用apply ：函數(shù)和它的參數(shù)列表。下列四個表達(dá)式的效果是一樣的：

  (+ 1 2)

  (apply #'+ '(1 2))

  (apply (symbol-function '+) '(1 2))

  (apply #'(lambda (x y) (+ x y)) '(1 2))

在Common Lisp 里，apply 可以帶任意數(shù)量的參數(shù)。其中，最前面給出的函數(shù)將被應(yīng)用到一個列表，該列表由其余參數(shù)cons 到最后一個參數(shù)產(chǎn)生，而最后的參數(shù)也是個列表。所以表達(dá)式

  (apply #'+ 1 '(2))

和前面四個表達(dá)式等價。如果不方便以列表的形式提供參數(shù)，可以使用funcall ，它和apply 唯一的區(qū)別也在于此。表達(dá)式

  (funcall #'+ 1 2)

和上面的那些表達(dá)式效果相同。

很多內(nèi)置的Common Lisp 函數(shù)都可以把函數(shù)作為參數(shù)。這些內(nèi)置函數(shù)中，最常用的是映射類的函數(shù)。例如 mapcar 帶有兩個以上參數(shù) 一個函數(shù)加上一個以上的列表(每個列表都分別是函數(shù)的參數(shù))，然后它可以將參數(shù)里的函數(shù)依次作用在每個列表的元素上：

  > (mapcar #'(lambda (x) (+ x 10))
  '(1 2 3))
  (11 12 13)
  > (mapcar #'+
  '(1 2 3)
  '(10 100 1000))
  (11 102 1003)

Lisp 程序經(jīng)常需要對列表中的每一項(xiàng)都做一些操作，然后再把結(jié)果同樣以列表的形式返回。上面的第一個例子介紹的步驟，就是用來完成這個工作的常用辦法：生成一個你所需功能的函數(shù)，然后用 mapcar 把它映射到列表上。

我們已經(jīng)了解到，"把函數(shù)當(dāng)作數(shù)據(jù)來使用" 的能力給編程帶來了極大的便利。在許多語言里，即便我們可以像 mapcar 那樣把函數(shù)作為參數(shù)傳遞進(jìn)去，那也只能是事先在代碼中定義好的函數(shù)。如果只有一小段代碼需要把列表中的每項(xiàng)都加上10，我們就只得專門定義一個叫plus_ten 或者類似名字的函數(shù)，而這個函數(shù)只是在這段代碼中才會用到。有了–表達(dá)式，就可以直接表達(dá)函數(shù)了。

Common Lisp 和它以前方言之間一個最大的區(qū)別就是它擁有大量使用函數(shù)型參數(shù)的內(nèi)置函數(shù)。其中，除了隨處可見的mapcar ，還有兩個最常用的函數(shù)就是sort 和 remove-if 。前者是通用的排序函數(shù)。它接受一個列表和一個謂詞，然后使用這個謂詞，對原列表中的元素兩兩進(jìn)行比較，并返回所得排序后的列表。

  > (sort '(1 4 2 5 6 7 3) #'<)
  (1 2 3 4 5 6 7)

有種辦法可以幫助記憶sort 函數(shù)工作方式，如果你用 排序一個沒有重復(fù)元素的列表，那么當(dāng)你把 應(yīng)用到結(jié)果列表的時候，它將會返回真。

假使Common Lisp 里沒有remove-if 函數(shù)的話，那它就應(yīng)該是你寫的第一個工具。它接受一個函數(shù)和列表，并且返回這個列表中所有調(diào)用那個函數(shù)返回假的元素。

  > (remove-if #'evenp '(1 2 3 4 5 6 7))
  (1 3 5 7)

作為把函數(shù)作為參數(shù)的函數(shù)示例，這里給出一個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 并沒有前綴#' 。因?yàn)楹瘮?shù)就是數(shù)據(jù)對象，變量可以將一個函數(shù)作為它的正規(guī)值。

這就是事情的來龍去脈。#' 僅用來引用那些以符號命名的函數(shù) 通常是用defun 全局定義的。

正如第4 章將要展示的那樣，編寫那種接受函數(shù)作為參數(shù)的新工具是自下而上程序設(shè)計(jì)的重要環(huán)節(jié)。

Common Lisp 自帶了大量的工具函數(shù)，很多你想要的可能已經(jīng)有了。但無論是使用內(nèi)置的工具，比如sort ， 還是編寫你的實(shí)用工具，基本原則是一樣的：與其把功能寫死，不如傳進(jìn)去一個函數(shù)參數(shù)。

2.4 作為屬性的函數(shù)

函數(shù)作為Lisp 對象這一事實(shí)也創(chuàng)造了條件，讓我們能夠編寫出那種可以隨時擴(kuò)展以滿足新需求的程序。

假設(shè)我們需要寫一個以動物種類作為參數(shù)并產(chǎn)生相應(yīng)行為的函數(shù)。在大多數(shù)語言中，會使用case 語句達(dá)到這個目的，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))))

如果要增加一種新動物該怎么辦呢？如果計(jì)劃增加新的動物，那么把behave 定義成下面的樣子可能會更好一些：

  (defun behave (animal)
  (funcall (get animal 'behavior)))

同時把每種個體動物的行為以單獨(dú)的函數(shù)形式保存，例如，存放在以它們名字命名的屬性列表里：

  (setf (get 'dog 'behavior)
  #'(lambda ()
  (wag-tail)
  (bark)))

用這種方式處理的話，要增加一種新動物，所有你需要做的事情就是定義一個新的屬性。一個函數(shù)都不用重寫。

上述第二種方法盡管更靈活，但看上去要慢些。實(shí)際上也是如此。如果速度很關(guān)鍵，我們可以把屬性表換成結(jié)構(gòu)體，而且特別要用編譯過的函數(shù)代替解釋性的函數(shù)。(第2.9 節(jié)解釋了怎樣做到這些。) 使用了結(jié)構(gòu)體和編譯函數(shù)，上面的代碼就會靈活，而且其速度可以達(dá)到甚至超過那些使用case 語句的實(shí)現(xiàn)。

這樣使用函數(shù)相當(dāng)于面向?qū)ο缶幊讨械姆椒ǜ拍??？偟膩碚f，方法是作為對象屬性的一種函數(shù)，這也正是

我們手里有的。如果把繼承引入這個模型，你就得到了面向?qū)ο缶幊痰娜恳?。?5 章將用少得驚人的代碼來說明這一點(diǎn)。

面向?qū)ο缶幊痰囊淮罅咙c(diǎn)是它能讓程序可擴(kuò)展。這一點(diǎn)在Lisp 界激起的反響要小很多，因?yàn)樵谶@里，人們早已把可擴(kuò)展性當(dāng)成理所當(dāng)然的事情了。如果我們要的可擴(kuò)展性不是很依賴?yán)^承，那么純Lisp 可能就已經(jīng)足夠應(yīng)付了。

2.5 作用域

Common Lisp 是一種詞法作用域(lexically scope) 的Lisp。Scheme 是最早的有詞法作用域的方言；在它之前，動態(tài)作用域(dynamicscope) 被視為Lisp 的本質(zhì)屬性之一。

詞法作用域和動態(tài)作用域的區(qū)別在于語言處理自由變量的方式不同。當(dāng)一個符號被用來表達(dá)變量時，我們稱這個符號在表達(dá)式中是被綁定的(bound)，這里的變量可以是參數(shù)，也可以是來自像let 和do 這樣的變量綁定操作符。如果符號不受到約束，就認(rèn)為它是自由的。下面的例子具體說明了作用域：

  (let ((y 7))
  (defun scope-test (x)
  (list x y)))

在函數(shù)表達(dá)式里，x 是受約束的，而y 是自由的。自由變量有意思的地方就在于，這種變量應(yīng)有的值并不那么顯而易見。一個約束變量的值是確信無疑的 當(dāng)調(diào)用scope-test 時，x 的值就是通過參數(shù)傳給它的值。但y 的值應(yīng)該是什么呢？這要看具體方言的作用域規(guī)則。

在動態(tài)作用域的Lisp 里，要想找出當(dāng)scope-test 執(zhí)行時自由變量的值，我們要往回逐個檢查函數(shù)的調(diào)用鏈。當(dāng)發(fā)現(xiàn)y 被綁定時，這個被綁定的值即被用在scope-test 中。如果沒有發(fā)現(xiàn)，那就取y 的全局值。這樣，在用動態(tài)作用域的Lisp 里，在調(diào)用的時候y 將會產(chǎn)生這樣的值：

  > (let ((y 5))
  (scope-test 3))
  (3 5)

如果是動態(tài)作用域，那么在定義 scope-test 時，把y 綁定到7 就沒有任何意義了。調(diào)用 scope-test 時，y 只有一個值，就是 5。

在詞法作用域的 Lisp 里，我們不再往回逐個檢查函數(shù)的調(diào)用鏈，而是逐層檢查定義這個函數(shù)時，它所處的各層外部環(huán)境。在一個詞法作用域Lisp 里，我們的示例將捕捉到定義scope-test 時，變量y 的綁定。所以可以在 Common Lisp 里觀察到下面的現(xiàn)象：

  > (let ((y 5))
  (scope-test 3))
  (3 7)

這里將y 綁定到5。這樣做對函數(shù)調(diào)用的返回值不會有絲毫影響。

盡管你仍然可以通過將變量聲明為special 來得到動態(tài)作用域，但是詞法作用域是Common Lisp 的默認(rèn)行為?？偟膩碚f，Lisp 社區(qū)對昨日黃花的動態(tài)作用域幾乎沒什么留戀。因?yàn)樗?jīng)常會導(dǎo)致痛苦而又難以捉摸的bug。而詞法作用域不僅僅是一種避免錯誤的手段。在下一章我們會看到，它同時也帶來了一些嶄新的編程技術(shù)。

2.6 閉包

由于Common Lisp 是詞法作用域的，所以如果定義含有自由變量的函數(shù)，系統(tǒng)就必須在函數(shù)定義時保存那些變量的綁定。這種函數(shù)和一組變量綁定的組合稱為閉包。我們發(fā)現(xiàn)，閉包在各種場合都能大顯身手。

閉包在 Common Lisp 程序中如此無所不在，以至于你可能已經(jīng)用了它卻渾然不知。每當(dāng)你傳給 mapcar 一

個包含自由變量的前綴#' 的–表達(dá)式時，你就在使用閉包。例如，假設(shè)我們想寫一個函數(shù)，它接受一個數(shù)列并且給每個數(shù)加上相同的數(shù)字。這個list+ 函數(shù)

  (defun list+ (lst n)
  (mapcar #'(lambda (x) (+ x n))
  lst))

將做到我們想要的：

  > (list+ '(1 2 3) 10)
  (11 12 13)

如果仔細(xì)觀察list+ 里傳給mapcar 的那個函數(shù)，就可以發(fā)現(xiàn)它實(shí)際上是個閉包。那個n 是自由的，其綁定來自周圍的環(huán)境。在詞法作用域下，每一次這樣使用映射函數(shù)都將導(dǎo)致一個閉包的創(chuàng)建。

閉包在 Abelson 和 Sussman 的經(jīng)典教材《計(jì)算機(jī)程序的構(gòu)造和解釋》一書中扮演了更加重要的角色。閉包是帶有局部狀態(tài)的函數(shù)。使用這種狀態(tài)最簡單的方式是如下的情況：

  (let ((counter 0))
  (defun new-id () (incf counter))
  (defun reset-id () (setq counter 0)))

這兩個函數(shù)共享一個計(jì)數(shù)器變量。前者返回計(jì)數(shù)器的下一個值，后者把計(jì)數(shù)器重置到0。這種方式避免了對計(jì)數(shù)器變量非預(yù)期的引用，盡管同樣的功能也可以用一個全局的計(jì)數(shù)器變量完成。

如果返回的函數(shù)能帶有局部狀態(tài)，那么也會很有幫助。例如這個make-adder 函數(shù)

  (defun make-adder (n)
  #'(lambda (x) (+ x n)))

接受一個數(shù)值參數(shù)，然后返回一個閉包，當(dāng)調(diào)用后者時，能夠把之前那個數(shù)加到它的參數(shù)上。我們可以根據(jù)需要生成任意數(shù)量的這種加法器：

在動態(tài)作用域(作為默認(rèn)作用域) 的情況下，這種表達(dá)方式也會一樣工作，雖然其原理不同 前提是mapcar 沒有一個參數(shù)的名字是 "n" 。

  > (setq add2 (make-adder 2)
  add10 (make-adder 10))
  #<Interpreted-Function BF162E>
  > (funcall add2 5)
  7
  > (funcall add10 3)
  13

在 make-adder 返回的那些閉包里，內(nèi)部狀態(tài)都是固定的，但其實(shí)也可以生成那種能應(yīng)要求改變自己狀態(tài)的閉包。

  (defun make-adderb (n)
  #'(lambda (x &optional change)
  (if change
     (setq n x)
        (+ x n))))

這個新版本的 make-adder 函數(shù)返回一個閉包，如果調(diào)用它時只傳入一個參數(shù)，那么其行為和舊版本是一樣的。

  > (setq addx (make-adderb 1))
  #<Interpreted-Function BF1C66>
  > (funcall addx 3)
  4

但是，如果這個新加法器的第二個參數(shù)不為空的話，在它內(nèi)部，n 的拷貝將被設(shè)置成第一個參數(shù)的值：

  > (funcall addx 100 t)
  100
  > (funcall addx 3)
  103

甚至有可能返回共享同一數(shù)據(jù)對象的一組閉包。圖2.1 中的函數(shù)被用來創(chuàng)建原始數(shù)據(jù)庫。它接受一個關(guān)聯(lián)表(db)，并相應(yīng)返回一個由查詢、追加和刪除這三個閉包所組成的列表。

  (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： 一個列表里的三個閉包

每次調(diào)用make-dbms 都會創(chuàng)建新的數(shù)據(jù)庫 這個新數(shù)據(jù)庫就是一組新函數(shù)，它們把自己的共享拷貝封存在一張關(guān)聯(lián)表(assoc-list) 里面。

  > (setq cities (make-dbms '((boston . us) (paris .france))))
  (#<Interpreted-Function 8022E7>
  #<Interpreted-Function 802317>
  #<Interpreted-Function 802347>)

數(shù)據(jù)庫里實(shí)際的關(guān)聯(lián)表是對外界不可見的，我們甚至不知道它是個關(guān)聯(lián)表 但是可以通過構(gòu)成 cities 的那些函數(shù)訪問到它：

  > (funcall (car cities) 'boston)
  US
  > (funcall (second cities) 'london 'england)
  LONDON
  > (funcall (car cities) 'london)
  ENGLAND

調(diào)用列表的 car 多少有些難看。實(shí)際的程序中，函數(shù)訪問的入口可能隱藏在結(jié)構(gòu)體里。當(dāng)然也可以設(shè)法更簡潔地使用它們 數(shù)據(jù)庫可以通過這樣的函數(shù)間接訪問：

  (defun lookup (key db)
  (funcall (car db) key))

無論怎樣，這種改進(jìn)都不會影響到閉包的基本行為。

實(shí)際程序中的閉包和數(shù)據(jù)結(jié)構(gòu)往往比我們在make-adder 和make-dbms 里看到的更加精巧。這里用到的單個共享變量也可以發(fā)展成任意數(shù)量的變量，每個都可以約束到任意的數(shù)據(jù)結(jié)構(gòu)上。

閉包是 Lisp 的眾多獨(dú)特和實(shí)實(shí)在在的優(yōu)勢之一。如果下些工夫的話，還可能把有的 Lisp 程序翻譯成能力稍弱的語言，但只要試著去翻譯上面那些使用了閉包的程序，你就會明白這種抽象幫我們省去了多少工作。

后續(xù)章節(jié)將進(jìn)一步探討閉包的更多細(xì)節(jié)。第5 章展示了如何用它們構(gòu)造復(fù)合函數(shù)，接著在第6 章里會繼續(xù)介紹如何用它們替代傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)。

2.7 局部函數(shù)

在用–表達(dá)式定義函數(shù)時，我們就會面對一個使用 defun 時所沒有的限制：使用–表達(dá)式定義的函數(shù)由于它沒有名字，因此也就沒有辦法引用自己。這意味著在 Common Lisp 里，不能用 lambda 定義遞歸函數(shù)。

如果我們想要應(yīng)用某些函數(shù)到一個列表的所有元素上，可以使用最熟悉的Lisp 語句：

  > (mapcar #'(lambda (x) (+ 2 x))
  '(2 5 7 3))
  (4 7 9 5)

要是想把遞歸函數(shù)作為第一個參數(shù)送給mapcar 呢？如果函數(shù)已經(jīng)用defun 定義了，我們就可以通過名字簡單地引用它：

  > (mapcar #'copy-tree '((a b) (c d e)))
  ((A B) (C D E))

但現(xiàn)在假設(shè)這個函數(shù)必須是一個閉包，它從mapcar 所處的環(huán)境獲得綁定。在我們的list+ 例子里，

  (defun list+ (lst n)
  (mapcar #'(lambda (x) (+ x n))
  lst))

mapcar 的第一個參數(shù)是 #'(lambda (x) (+ x n)) ，它必須要在list+ 里定義，原因是它需要捕捉n 的綁定。到目前為止都還一切正常，但如果要給mapcar 傳遞一個函數(shù)，而這個函數(shù)在需要局部綁定的同時也是遞歸的呢？我們不能使用一個在其他地方通過defun 定義的函數(shù)，因?yàn)檫@需要局部環(huán)境的綁定。并且我們也不能使用lambda 來定義一個遞歸函數(shù)，因?yàn)檫@個函數(shù)將無法引用其自身。

Common Lisp 提供了labels 幫助我們跳出這個兩難的困境。除了在一個重要方面有所保留外，labels 基本可以看作是let 的函數(shù)版本。labels 表達(dá)式里的每個綁定規(guī)范都必須符合如下形式：

  (<name> <parameters> . <body>)

在labels 表達(dá)式里，?name? 將指向與下面表達(dá)式等價的函數(shù)：

  #'(lambda <parameters> . <body>)

例如，

  > (labels ((inc (x) (1+ x)))
  (inc 3))
  > 4

盡管如此，在let 與labels 之間有一個重要的區(qū)別。在let 表達(dá)式里，變量的值不能依賴于同一個let 里生成的另一個變量 就是說，你不能說

  (let ((x 10) (y x))
  y)

然后認(rèn)為這個新的 能反映出那個新 的值。相反，在labels 里定義的函數(shù) 的函數(shù)體里就可以引用那里定義的其他函數(shù)，包括 本身，這就使定義遞歸函數(shù)成為可能。

使用labels ，我們就可以寫出類似list+ 這樣的函數(shù)了，但這里 mapcar 的第一個參數(shù)是遞歸函數(shù)：

  (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)))

該函數(shù)接受一個對象和一個列表，然后分別統(tǒng)計(jì)出該對象在列表的每個元素(作為列表) 中出現(xiàn)的次數(shù)，把這些次數(shù)組成列表，并返回它：

  > (count-instances 'a '((a b c) (d a r p a) (d a r) (a a)))
  (1 2 1 2)

2.8 尾遞歸

遞歸函數(shù)自己調(diào)用自己。如果函數(shù)調(diào)用自己之后不做其他工作，這種調(diào)用就稱為尾遞歸(tail-recursive)。

下面這個函數(shù)不是尾遞歸的

  (defun our-length (lst)
  (if (null lst)
  0
  (1+ (out-length (cdr lst)))))

因?yàn)樵趶倪f歸調(diào)用返回之后，我們又把結(jié)果傳給了1+。而下面這個函數(shù)就是尾遞歸的?

  (defun our-find-if (fn lst)
  (if (funcall fn (car lst))
  (car lst)
  (our-find-if fn (cdr lst))))

因?yàn)橥ㄟ^遞歸調(diào)用得到的值被立即返回了。

尾遞歸是一種令人青睞的特性，因?yàn)樵S多Common Lisp 編譯器都可以把尾遞歸轉(zhuǎn)化成循環(huán)。若使用這種編譯器，你就可以在源代碼里書寫優(yōu)雅的遞歸，而不必?fù)?dān)心函數(shù)調(diào)用在運(yùn)行期產(chǎn)生的系統(tǒng)開銷。

如果一個函數(shù)不是尾遞歸的話，常常可以把一個使用累積器(accumulator) 的局部函數(shù)嵌入到其中，用這種方法把它轉(zhuǎn)換成尾遞歸的形式。在這里，累積器指的是一個參數(shù)，它代表著到目前為止計(jì)算得到的值。例如our-length 可以轉(zhuǎn)換成

  (defun our-length (lst)
  (labels ((rec (lst acc)
  (if (null lst)

?原書勘誤：如果沒有找到期望的元素，our-find-if 函數(shù)將無限遞歸下去。

  acc
  (rec (cdr lst) (1+ acc)))))
  (rec lst 0)))

上面定義的函數(shù)里，到現(xiàn)在為止，所有見到的列表元素的總數(shù)都被放在了另一個參數(shù)acc 里。當(dāng)遞歸運(yùn)行到達(dá)列表的結(jié)尾，acc 的值就是總的長度，只要直接返回它就可以了。通過在調(diào)用樹從上往下走的過程中累計(jì)這個值，而不是從下往上地在返回的時候再計(jì)算它，我們就可以將rec 尾遞歸化。

許多 Common Lisp 編譯器都能做尾遞歸優(yōu)化，但這并不是所有編譯器的默認(rèn)行為。所以在編寫尾遞歸函數(shù)時，你應(yīng)該把

  (proclaim '(optimize speed))

寫在文件的最前面，確保編譯器不會辜負(fù)你的苦心，進(jìn)行期望的優(yōu)化。?

如果提供尾遞歸和類型聲明，現(xiàn)有的Common Lisp 編譯器就能生成運(yùn)行速度能與C 程序相媲美，甚至超過? 它的代碼。RichardGabriel 以下面的函數(shù)作為例證，它從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 代碼的典范。一開始就用這樣寫程序可能會覺得不太自然?？赡芨玫霓k法

是先用自己最習(xí)慣的方式編寫函數(shù)，然后在必要時把它轉(zhuǎn)化成尾遞歸的等價形式。

2.9 編譯

Lisp 函數(shù)可以單獨(dú)編譯或者按文件編譯。如果你只是在toplevel 下輸入一個defun 表達(dá)式，

  > (defun foo (x) (1+ x))
  FOO

多數(shù)實(shí)現(xiàn)會創(chuàng)建相應(yīng)的解釋函數(shù)(interpretedfunction)。你可以使用compiled-function-p 來檢查函數(shù)是

否被編譯過：

  > (compiled-function-p #'foo)
  NIL

我們可以把函數(shù)名傳給compile ，用這種辦法來編譯foo

  > (compile 'foo)
  FOO

這樣可以編譯foo 的定義，并把之前的解釋版本換成編譯版本。

  > (compiled-function-p #'foo)
  T

編譯和解釋函數(shù)都是Lisp 對象，兩者的行為表現(xiàn)是相同的，只是對 compiled-function-p 的反應(yīng)不一樣。

直接給出的函數(shù)也可以編譯：compile 希望它的第一個參數(shù)是個名字，但如果你給它的是nil ，它就會編譯第二個參數(shù)給出的–表達(dá)式。

  > (compile nil '(lambda (x) (+ x 2)))
  #<Compiled-Function BF55BE>

?(optimize speed) 的聲明應(yīng)該是(optimize (speed 3)) 的簡寫。但是有一種 Common Lisp 實(shí)現(xiàn)，若使用前一種聲明，則會進(jìn)行尾遞歸優(yōu)化，而后一種聲明則不會產(chǎn)生這種優(yōu)化。

如果你同時給出名字和函數(shù)參數(shù)，compile 的效果就相當(dāng)于編譯一個defun ：

  > (progn (compile 'bar '(lambda (x) (* x 3)))
  (compiled-function-p #'bar))
  T

把compile 集成進(jìn)語言里意味著程序可以隨時構(gòu)造和編譯新函數(shù)。不過，顯式調(diào)用compile 和調(diào)用eval 一樣，都屬于非常規(guī)的手段，同樣要多加小心。? 當(dāng)?shù)?.1 節(jié)里說在運(yùn)行時創(chuàng)建新函數(shù)屬常用編程技術(shù)時， 它指的是從類似 make-adder 那樣的函數(shù)中生成的閉包，并非指從原始列表里調(diào)用compile 得到的新函數(shù)。調(diào)用 compile 并不屬于常用的編程技術(shù)，相反，它極少會用到。所以要注意，若非必要，盡量避免使用它。除非你在Lisp 之上實(shí)現(xiàn)另一種語言，但即使如此，用宏也有可能達(dá)到同樣的目的。

有兩類函數(shù)不能被作為參數(shù)送給compile。根據(jù) ???2(667 頁)，你不能編譯"在非空詞法環(huán)境中解釋性地定義出的" 函數(shù)。那就是說，在 toplevel 下，如果你定義一個帶有l(wèi)et 的foo

  > (let ((y 2))
  (defun foo (x) (+ x y)))

那么，(compile 'foo) 是不能保證正常工作的。你也不能對已經(jīng)編譯過的函數(shù)調(diào)用compile ，CLTL2 隱晦地暗示 "結(jié)果 ...是不確定的"。

通常編譯Lisp 代碼的方法，不是用compile 逐個地編譯函數(shù)，而是用compile-file 編譯整個文件。該函數(shù)接受一個文件名，然后創(chuàng)建源代碼的編譯版本 一般情況下，編譯出的文件和源文件有相同的基本文件名，但擴(kuò)展名不一樣。編譯過的文件被加載后，compiled-function-p 對文件里定義的所有函數(shù)，返回值都是真。

后面的章節(jié)還有賴編譯帶來的另一種效果：如果當(dāng)某個函數(shù)出現(xiàn)在另一函數(shù)中，并且外面的函數(shù)已經(jīng)編譯的話，那么里面的函數(shù)也會隨之被編譯。 ???2 里并沒有明確這一行為，但所有正規(guī)的實(shí)現(xiàn)都支持它。

對于那些返回函數(shù)的函數(shù)來說，內(nèi)層函數(shù)的編譯行為是很清楚的。當(dāng)make-adder (第12 頁) 被編譯時，它將返回一個編譯過的函數(shù)：

  > (compile 'make-adder)
  MAKE-ADDER
  > (compiled-function-p (make-adder 2))
  T

后面的章節(jié)將說明，這一事實(shí)對于實(shí)現(xiàn)嵌入式語言來說尤為重要。如果一種新語言是通過轉(zhuǎn)換實(shí)現(xiàn)的，而

且轉(zhuǎn)換出來的代碼是編譯過的，那么它也會產(chǎn)生編譯后的輸出 這個轉(zhuǎn)換過程也就成為了新語言事實(shí)上的編譯器。(在第53 頁有一個簡單的例子。)

要是有特別小的函數(shù)，就可能會有內(nèi)聯(lián)編譯它的需要。否則調(diào)用這個函數(shù)的開銷可能會超出執(zhí)行函數(shù)本身的開銷。如果我們定義了一個函數(shù)：

  (defun 50th (lst) (nth 49 lst))

并且聲明：

  (proclaim '(inline 50th))

所以只要函數(shù)一編譯過，它在引用50th 的時候就無需進(jìn)行真正的函數(shù)調(diào)用了。如果我們定義并且編譯一個調(diào)用了 50th 的函數(shù)，

  (defun foo (lst)
  (+ (50th lst) 1))

那么編譯foo 的同時，50th 的代碼應(yīng)該被編譯進(jìn)它里面。就好像我們原來寫的就是

?第190頁解釋了顯式調(diào)用eval 有害的理由。 ?把這段代碼寫在文件里然后再編譯是沒問題的。這一限制是由于具體實(shí)現(xiàn)的原因，被強(qiáng)加在了解釋型函數(shù)上，而絕不是因?yàn)樵谇宄靼椎脑~法環(huán)境中定義函數(shù)有什么不對。

  (defun foo (lst)
  (+ (nth 49 lst) 1))

一樣。缺點(diǎn)是，如果我們改動了50th 的定義的話，那么就必須重新編譯foo ，否則它用的還是原來的定義。

內(nèi)聯(lián)函數(shù)的限制基本上和宏差不多(見第7.9 節(jié))。

2.10 來自列表的函數(shù)

一些早期的 Lisp 方言用列表來表示函數(shù)。這賦予了程序員非同一般的編寫和執(zhí)行其Lisp 程序的能力。

在Common Lisp 中，函數(shù)不再由列表構(gòu)詞 優(yōu)良的實(shí)現(xiàn)把它們編譯成本地代碼。但你仍然可以寫出那種編寫程序的程序，因?yàn)榱斜硎蔷幾g器的輸入。

再怎么強(qiáng)調(diào) "Lisp 程序可以編寫 Lisp 程序" 都不為過，尤其是當(dāng)這一事實(shí)經(jīng)常被忽視時。即使有經(jīng)驗(yàn)的 Lisp 程序員也很少意識到他們因這種語言特性而得到的種種好處。例如，正是這個特性使得Lisp 宏如此強(qiáng)大。

本書里描述的大部分技術(shù)都依賴于這個能力，即編寫處理 Lisp 表達(dá)式的程序的能力。