第 2 章 函數(shù)

第 2 章 函數(shù)

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

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

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

沒(méi)有

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

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

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

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

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

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

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

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

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

2.2 定義函數(shù)

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

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

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

  > (double 1)
  2

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

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

  > #'double
  #<Interpreted-Function C66ACE>

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

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

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

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

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

  (lambda (x) (* x 2))

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

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

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

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

  > (double 3)
  6

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

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

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

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

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

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

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

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

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

  > (symbol-value 'double)
  2

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

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

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

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

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

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

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

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

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

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

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

如果一門(mén)語(yǔ)言把函數(shù)作為數(shù)據(jù)對(duì)象，那么它必然也會(huì)提供某種方式讓我們能調(diào)用它們。在Lisp 里，這個(gè)函數(shù)就是apply。一般而言，我們用兩個(gè)參數(shù)來(lái)調(diào)用apply ：函數(shù)和它的參數(shù)列表。下列四個(gè)表達(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)用到一個(gè)列表，該列表由其余參數(shù)cons 到最后一個(gè)參數(shù)產(chǎn)生，而最后的參數(shù)也是個(gè)列表。所以表達(dá)式

  (apply #'+ 1 '(2))

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

  (funcall #'+ 1 2)

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

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

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

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

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

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

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

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

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

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

作為把函數(shù)作為參數(shù)的函數(shù)示例，這里給出一個(gè)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))))))

注意到在這個(gè)定義里fn 并沒(méi)有前綴#' 。因?yàn)楹瘮?shù)就是數(shù)據(jù)對(duì)象，變量可以將一個(gè)函數(shù)作為它的正規(guī)值。

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

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

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

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

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

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

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

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

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

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

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

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

這樣使用函數(shù)相當(dāng)于面向?qū)ο缶幊讨械姆椒ǜ拍?。總的?lái)說(shuō)，方法是作為對(duì)象屬性的一種函數(shù)，這也正是

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

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

2.5 作用域

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

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

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

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

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

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

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

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

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

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

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

2.6 閉包

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

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

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

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

將做到我們想要的：

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

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

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

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

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

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

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

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

在動(dòng)態(tài)作用域(作為默認(rèn)作用域) 的情況下，這種表達(dá)方式也會(huì)一樣工作，雖然其原理不同 前提是mapcar 沒(méi)有一個(gè)參數(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))))

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

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

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

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

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

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

每次調(diào)用make-dbms 都會(huì)創(chuàng)建新的數(shù)據(jù)庫(kù) 這個(gè)新數(shù)據(jù)庫(kù)就是一組新函數(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ù)庫(kù)里實(shí)際的關(guān)聯(lián)表是對(duì)外界不可見(jiàn)的，我們甚至不知道它是個(gè)關(guān)聯(lián)表 但是可以通過(guò)構(gòu)成 cities 的那些函數(shù)訪問(wèn)到它：

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

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

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

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

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

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

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

2.7 局部函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

例如，

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

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

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

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

使用labels ，我們就可以寫(xiě)出類(lèi)似list+ 這樣的函數(shù)了，但這里 mapcar 的第一個(gè)參數(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ù)接受一個(gè)對(duì)象和一個(gè)列表，然后分別統(tǒng)計(jì)出該對(duì)象在列表的每個(gè)元素(作為列表) 中出現(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)用就稱(chēng)為尾遞歸(tail-recursive)。

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

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

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

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

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

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

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

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

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

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

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

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

  (proclaim '(optimize speed))

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

如果提供尾遞歸和類(lèi)型聲明，現(xiàn)有的Common Lisp 編譯器就能生成運(yùn)行速度能與C 程序相媲美，甚至超過(guò)? 它的代碼。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āi)始就用這樣寫(xiě)程序可能會(huì)覺(jué)得不太自然?？赡芨玫霓k法

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

2.9 編譯

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

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

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

否被編譯過(guò)：

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

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

  > (compile 'foo)
  FOO

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

并且聲明：

  (proclaim '(inline 50th))

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

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

那么編譯foo 的同時(shí)，50th 的代碼應(yīng)該被編譯進(jìn)它里面。就好像我們?cè)瓉?lái)寫(xiě)的就是

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

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

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

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

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

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

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

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

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