第六章：函數(shù)

理解函數(shù)是理解 Lisp 的關(guān)鍵之一。概念上來說，函數(shù)是 Lisp 的核心所在。實(shí)際上呢，函數(shù)是你手邊最有用的工具之一。

6.1 全局函數(shù) (Global Functions)

謂詞?fboundp?告訴我們，是否有個(gè)函數(shù)的名字與給定的符號(hào)綁定。如果一個(gè)符號(hào)是函數(shù)的名字，則?symbol-function?會(huì)返回它：

> (fboundp '+)
T
> (symbol-function '+)
#<Compiled-function + 17BA4E>

可通過?symbol-function?給函數(shù)配置某個(gè)名字：

(setf (symbol-function 'add2)
  #'(lambda (x) (+ x 2)))

新的全局函數(shù)可以這樣定義，用起來和?defun?所定義的函數(shù)一樣：

> (add2 1)
3

實(shí)際上?defun?做了稍微多的工作，將某些像是

(defun add2 (x) (+ x 2))

翻譯成上述的?setf?表達(dá)式。使用?defun?讓程序看起來更美觀，并或多或少幫助了編譯器，但嚴(yán)格來說，沒有?defun?也能寫程序。

通過把?defun?的第一個(gè)實(shí)參變成這種形式的列表?(setf?f)?，你定義了當(dāng)?setf?第一個(gè)實(shí)參是?f?的函數(shù)調(diào)用時(shí)，所會(huì)發(fā)生的事情。下面這對(duì)函數(shù)把?primo?定義成?car?的同義詞：

(defun primo (lst) (car lst))

(defun (setf primo) (val lst)
  (setf (car lst) val))

在函數(shù)名是這種形式?(setf?f)?的函數(shù)定義中，第一個(gè)實(shí)參代表新的數(shù)值，而剩余的實(shí)參代表了傳給?f?的參數(shù)。

現(xiàn)在任何?primo?的?setf?，會(huì)是上面后者的函數(shù)調(diào)用：

> (let ((x (list 'a 'b 'c)))
    (setf (primo x) 480)
    x)
(480 b c)

不需要為了定義?(setf?primo)?而定義?primo?，但這樣的定義通常是成對(duì)的。

由于字符串是 Lisp 表達(dá)式，沒有理由它們不能出現(xiàn)在代碼的主體。字符串本身是沒有副作用的，除非它是最后一個(gè)表達(dá)式，否則不會(huì)造成任何差別。如果讓字符串成為?defun?定義的函數(shù)主體的第一個(gè)表達(dá)式，

(defun foo (x)
  "Implements an enhanced paradigm of diversity"
  x)

那么這個(gè)字符串會(huì)變成函數(shù)的文檔字符串（documentation string）。要取得函數(shù)的文檔字符串，可以通過調(diào)用?documentation?來取得：

> (documentation 'foo 'function)
"Implements an enhanced paradigm of diversity"

6.2 局部函數(shù) (Local Functions)

通過?defun?或?symbol-function?搭配?setf?定義的函數(shù)是全局函數(shù)。你可以像存取全局變量那樣，在任何地方存取它們。定義局部函數(shù)也是有可能的，局部函數(shù)和局部變量一樣，只在某些上下文內(nèi)可以訪問。

局部函數(shù)可以使用?labels?來定義，它是一種像是給函數(shù)使用的?let?。它的第一個(gè)實(shí)參是一個(gè)新局部函數(shù)的定義列表，而不是一個(gè)變量規(guī)格說明的列表。列表中的元素為如下形式：

(name parameters . body)

而?labels?表達(dá)式剩余的部份，調(diào)用?name?就等于調(diào)用?(lambda?parameters?.?body)?。

> (labels ((add10 (x) (+ x 10))
           (consa  (x) (cons 'a x)))
    (consa (add10 3)))
(A . 13)

labels?與?let?的類比在一個(gè)方面上被打破了。由?labels?表達(dá)式所定義的局部函數(shù)，可以被其他任何在此定義的函數(shù)引用，包括自己。所以這樣定義一個(gè)遞歸的局部函數(shù)是可能的：

> (labels ((len (lst)
             (if (null lst)
                 0
                 (+ (len (cdr lst)) 1))))
    (len '(a b c)))
3

5.2 節(jié)展示了?let?表達(dá)式如何被理解成函數(shù)調(diào)用。?do?表達(dá)式同樣可以被解釋成調(diào)用遞歸函數(shù)。這樣形式的?do?:

(do ((x a (b x))
     (y c (d y)))
    ((test x y) (z x y))
  (f x y))

等同于

(labels ((rec (x y)
           (cond ((test x y)
                  (z x y))
                 (t
                  (f x y)
                  (rec (b x) (d y))))))
  (rec a c))

這個(gè)模型可以用來解決，任何你對(duì)于?do?行為仍有疑惑的問題。

6.3 參數(shù)列表 (Parameter Lists)

2.1 節(jié)我們演示過，有了前序表達(dá)式，?+?可以接受任何數(shù)量的參數(shù)。從那時(shí)開始，我們看過許多接受不定數(shù)量參數(shù)的函數(shù)。要寫出這樣的函數(shù)，我們需要使用一個(gè)叫做剩余（?rest?）參數(shù)的東西。

如果我們?cè)诤瘮?shù)的形參列表里的最后一個(gè)變量前，插入?&rest?符號(hào)，那么當(dāng)這個(gè)函數(shù)被調(diào)用時(shí)，這個(gè)變量會(huì)被設(shè)成一個(gè)帶有剩余參數(shù)的列表?，F(xiàn)在我們可以明白?funcall?是如何根據(jù)?apply?寫成的。它或許可以定義成：

(defun our-funcall (fn &rest args)
  (apply fn args))

我們也看過操作符中，有的參數(shù)可以被忽略，并可以缺省設(shè)成特定的值。這樣的參數(shù)稱為選擇性參數(shù)（optional parameters）。（相比之下，普通的參數(shù)有時(shí)稱為必要參數(shù)「required parameters」) 如果符號(hào)?&optional?出現(xiàn)在一個(gè)函數(shù)的形參列表時(shí)，

(defun philosoph (thing &optional property)
  (list thing 'is property))

那么在?&optional?之后的參數(shù)都是選擇性的，缺省為?nil?:

> (philosoph 'death)
(DEATH IS NIL)

我們可以明確指定缺省值，通過將缺省值附在列表里給入。這版的?philosoph

(defun philosoph (thing &optional (property 'fun))
  (list thing 'is property))

有著更鼓舞人心的缺省值：

> (philosoph 'death)
(DEATH IS FUN)

選擇性參數(shù)的缺省值可以不是常量?？梢允侨魏蔚?Lisp 表達(dá)式。若這個(gè)表達(dá)式不是常量，它會(huì)在每次需要用到缺省值時(shí)被重新求值。

一個(gè)關(guān)鍵字參數(shù)（keyword parameter）是一種更靈活的選擇性參數(shù)。如果你把符號(hào)?&key?放在一個(gè)形參列表，那在?&key?之后的形參都是選擇性的。此外，當(dāng)函數(shù)被調(diào)用時(shí)，這些參數(shù)會(huì)被識(shí)別出來，參數(shù)的位置在哪不重要，而是用符號(hào)標(biāo)簽（譯注:?:?）識(shí)別出來：

> (defun keylist (a &key x y z)
    (list a x y z))
KEYLIST

> (keylist 1 :y 2)
(1 NIL 2 NIL)

> (keylist 1 :y 3 :x 2)
(1 2 3 NIL)

和普通的選擇性參數(shù)一樣，關(guān)鍵字參數(shù)缺省值為?nil?，但可以在形參列表中明確地指定缺省值。

關(guān)鍵字與其相關(guān)的參數(shù)可以被剩余參數(shù)收集起來，并傳遞給其他期望收到這些參數(shù)的函數(shù)。舉例來說，我們可以這樣定義?adjoin?：

(defun our-adjoin (obj lst &rest args)
  (if (apply #'member obj lst args)
      lst
      (cons obj lst)))

由于?adjoin?與?member?接受一樣的關(guān)鍵字，我們可以用剩余參數(shù)收集它們，再傳給?member?函數(shù)。

5.2 節(jié)介紹過?destructuring-bind?宏。在通常情況下，每個(gè)模式（pattern）中作為第一個(gè)參數(shù)的子樹，可以與函數(shù)的參數(shù)列表一樣復(fù)雜：

(destructuring-bind ((&key w x) &rest y) '((:w 3) a)
  (list w x y))
(3 NIL (A))

6.4 示例：實(shí)用函數(shù) (Example: Utilities)

2.6 節(jié)提到過，Lisp 大部分是由 Lisp 函數(shù)組成，這些函數(shù)與你可以自己定義的函數(shù)一樣。這是程序語言中一個(gè)有用的特色：你不需要改變你的想法來配合語言，因?yàn)槟憧梢愿淖冋Z言來配合你的想法。如果你想要 Common Lisp 有某個(gè)特定的函數(shù)，自己寫一個(gè)，而這個(gè)函數(shù)會(huì)成為語言的一部分，就跟內(nèi)置的?+?或?eql?一樣。

有經(jīng)驗(yàn)的 Lisp 程序員，由上而下（top-down）也由下而上 (bottom-up)地工作。當(dāng)他們朝著語言撰寫程序的同時(shí)，也打造了一個(gè)更適合他們程序的語言。通過這種方式，語言與程序結(jié)合的更好，也更好用。

寫來擴(kuò)展 Lisp 的操作符稱為實(shí)用函數(shù)（utilities）。當(dāng)你寫了更多 Lisp 程序時(shí)，會(huì)發(fā)現(xiàn)你開發(fā)了一系列的程序，而在一個(gè)項(xiàng)目寫過許多的實(shí)用函數(shù)，下個(gè)項(xiàng)目里也會(huì)派上用場(chǎng)。

專業(yè)的程序員常發(fā)現(xiàn)，手邊正在寫的程序，與過去所寫的程序有很大的關(guān)聯(lián)。這就是軟件重用讓人聽起來很吸引人的原因。但重用已經(jīng)被聯(lián)想成面向?qū)ο蟪绦蛟O(shè)計(jì)。但軟件不需要是面向?qū)ο蟮牟拍苤赜?── 這是很明顯的，我們看看程序語言（換言之，編譯器），是重用性最高的軟件。

要獲得可重用軟件的方法是，由下而上地寫程序，而程序不需要是面向?qū)ο蟮牟拍軌蛴上露系貙懗?。?shí)際上，函數(shù)式風(fēng)格相比之下，更適合寫出重用軟件。想想看?sort?。在 Common Lisp 你幾乎不需要自己寫排序程序；?sort?是如此的快與普遍，以致于它不值得我們煩惱。這才是可重用軟件。

(defun single? (lst)
  (and (consp lst) (null (cdr lst))))

(defun append1 (lst obj)
  (append lst (list obj)))

(defun map-int (fn n)
  (let ((acc nil))
    (dotimes (i n)
      (push (funcall fn i) acc))
    (nreverse acc)))

(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
        (if val (push val acc))))
    (nreverse acc)))

(defun most (fn lst)
  (if (null lst)
      (values nil nil)
      (let* ((wins (car lst))
             (max (funcall fn wins)))
        (dolist (obj (cdr lst))
          (let ((score (funcall fn obj)))
            (when (> score max)
              (setf wins obj
                    max  score))))
        (values wins max))))

圖 6.1 實(shí)用函數(shù)

你可以通過撰寫實(shí)用函數(shù)，在程序里做到同樣的事情。圖 6.1 挑選了一組實(shí)用的函數(shù)。前兩個(gè)?single??與?append1?函數(shù)，放在這的原因是要演示，即便是小程序也很有用。前一個(gè)函數(shù)?single??，當(dāng)實(shí)參是只有一個(gè)元素的列表時(shí)，返回真。

> (single? '(a))
T

而后一個(gè)函數(shù)?append1?和?cons?很像，但在列表后面新增一個(gè)元素，而不是在前面:

> (append1 '(a b c) 'd)
(A B C D)

下個(gè)實(shí)用函數(shù)是?map-int?，接受一個(gè)函數(shù)與整數(shù)?n?，并返回將函數(shù)應(yīng)用至整數(shù)?0?到?n-1?的結(jié)果的列表。

這在測(cè)試的時(shí)候非常好用（一個(gè) Lisp 的優(yōu)點(diǎn)之一是，互動(dòng)環(huán)境讓你可以輕松地寫出測(cè)試）。如果我們只想要一個(gè)?0?到?9?的列表，我們可以：

> (map-int #'identity 10)
(0 1 2 3 4 5 6 7 8 9)

然而要是我們想要一個(gè)具有 10 個(gè)隨機(jī)數(shù)的列表，每個(gè)數(shù)介于 0 至 99 之間（包含 99），我們可以忽略參數(shù)并只要:

> (map-int #'(lambda (x) (random 100))
           10)
(85 50 73 64 28 21 40 67 5 32)

map-int?的定義說明了 Lisp 構(gòu)造列表的標(biāo)準(zhǔn)做法（idiom）之一。我們創(chuàng)建一個(gè)累積器?acc?，初始化是?nil?，并將之后的對(duì)象累積起來。當(dāng)累積完畢時(shí)，反轉(zhuǎn)累積器。?[1]

我們?cè)?filter?中看到同樣的做法。?filter?接受一個(gè)函數(shù)與一個(gè)列表，將函數(shù)應(yīng)用至列表元素上時(shí)，返回所有非?nil?元素:

> (filter #'(lambda (x)
              (and (evenp x) (+ x 10)))
          '(1 2 3 4 5 6 7))
(12 14 16)

另一種思考?filter?的方式是用通用版本的?remove-if?。

圖 6.1 的最后一個(gè)函數(shù)，?most?，根據(jù)某個(gè)評(píng)分函數(shù)（scoring function），返回列表中最高分的元素。它返回兩個(gè)值，獲勝的元素以及它的分?jǐn)?shù):

> (most #'length '((a b) (a b c) (a)))
(A B C)
3

如果平手的話，返回先馳得點(diǎn)的元素。

注意圖 6.1 的最后三個(gè)函數(shù)，它們?nèi)邮芎瘮?shù)作為參數(shù)。 Lisp 使得將函數(shù)作為參數(shù)傳遞變得便捷，而這也是為什么，Lisp 適合由下而上程序設(shè)計(jì)的原因之一。成功的實(shí)用函數(shù)必須是通用的，當(dāng)你可以將細(xì)節(jié)作為函數(shù)參數(shù)傳遞時(shí)，要將通用的部份抽象起來就變得容易許多。

本節(jié)給出的函數(shù)是通用的實(shí)用函數(shù)?？梢杂迷谌魏畏N類的程序。但也可以替特定種類的程序撰寫實(shí)用函數(shù)。確實(shí)，當(dāng)我們談到宏時(shí)，你可以凌駕于 Lisp 之上，寫出自己的特定語言，如果你想這么做的話。如果你想要寫可重用軟件，看起來這是最靠譜的方式。

6.5 閉包 (Closures)

函數(shù)可以如表達(dá)式的值，或是其它對(duì)象那樣被返回。以下是接受一個(gè)實(shí)參，并依其類型返回特定的結(jié)合函數(shù)：

(defun combiner (x)
  (typecase x
    (number #'+)
    (list #'append)
    (t #'list)))

在這之上，我們可以創(chuàng)建一個(gè)通用的結(jié)合函數(shù):

(defun combine (&rest args)
  (apply (combiner (car args))
         args))

它接受任何類型的參數(shù)，并以適合它們類型的方式結(jié)合。（為了簡(jiǎn)化這個(gè)例子，我們假定所有的實(shí)參，都有著一樣的類型。）

> (combine 2 3)
5
> (combine '(a b) '(c d))
(A B C D)

2.10 小節(jié)提過詞法變量（lexical variables）只在被定義的上下文內(nèi)有效。伴隨這個(gè)限制而來的是，只要那個(gè)上下文還有在使用，它們就保證會(huì)是有效的。

如果函數(shù)在詞法變量的作用域里被定義時(shí)，函數(shù)仍可引用到那個(gè)變量，即便函數(shù)被作為一個(gè)值返回了，返回至詞法變量被創(chuàng)建的上下文之外。下面我們創(chuàng)建了一個(gè)把實(shí)參加上?3?的函數(shù)：

> (setf fn (let ((i 3))
             #'(lambda (x) (+ x i))))
#<Interpreted-Function C0A51E>
> (funcall fn 2)
5

當(dāng)函數(shù)引用到外部定義的變量時(shí)，這外部定義的變量稱為自由變量（free variable）。函數(shù)引用到自由的詞法變量時(shí)，稱之為閉包（closure）。?[2]?只要函數(shù)還存在，變量就必須一起存在。

閉包結(jié)合了函數(shù)與環(huán)境（environment）；無論何時(shí)，當(dāng)一個(gè)函數(shù)引用到周圍詞法環(huán)境的某個(gè)東西時(shí)，閉包就被隱式地創(chuàng)建出來了。這悄悄地發(fā)生在像是下面這個(gè)函數(shù)，是一樣的概念:

(defun add-to-list (num lst)
  (mapcar #'(lambda (x)
              (+ x num))
          lst))

這函數(shù)接受一個(gè)數(shù)字及列表，并返回一個(gè)列表，列表元素是元素與傳入數(shù)字的和。在 lambda 表達(dá)式里的變量?num?是自由的，所以像是這樣的情況，我們傳遞了一個(gè)閉包給?mapcar?。

一個(gè)更顯著的例子會(huì)是函數(shù)在被調(diào)用時(shí)，每次都返回不同的閉包。下面這個(gè)函數(shù)返回一個(gè)加法器（adder）:

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

它接受一個(gè)數(shù)字，并返回一個(gè)將該數(shù)字與其參數(shù)相加的閉包（函數(shù)）。

> (setf add3 (make-adder 3))
#<Interpreted-Function COEBF6>
> (funcall add3 2)
5
> (setf add27 (make-adder 27))
#<Interpreted-Function C0EE4E>
> (funcall add27 2)
29

我們可以產(chǎn)生共享變量的數(shù)個(gè)閉包。下面我們定義共享一個(gè)計(jì)數(shù)器的兩個(gè)函數(shù):

(let ((counter 0))
  (defun reset ()
    (setf counter 0))
  (defun stamp ()
    (setf counter (+ counter 1))))

這樣的一對(duì)函數(shù)或許可以用來創(chuàng)建時(shí)間戳章（time-stamps）。每次我們調(diào)用?stamp?時(shí)，我們獲得一個(gè)比之前高的數(shù)字，而調(diào)用reset?我們可以將計(jì)數(shù)器歸零:

> (list (stamp) (stamp) (reset) (stamp))
(1 2 0 1)

你可以使用全局計(jì)數(shù)器來做到同樣的事情，但這樣子使用計(jì)數(shù)器，可以保護(hù)計(jì)數(shù)器被非預(yù)期的引用。

Common Lisp 有一個(gè)內(nèi)置的函數(shù)?complement?函數(shù)，接受一個(gè)謂詞，并返回謂詞的補(bǔ)數(shù)（complement）。比如：

> (mapcar (complement #'oddp)
          '(1 2 3 4 5 6))
(NIL T NIL T NIL T)

有了閉包以后，很容易就可以寫出這樣的函數(shù)：

(defun our-complement (f)
  #'(lambda (&rest args)
      (not (apply f args))))

如果你停下來好好想想，會(huì)發(fā)現(xiàn)這是個(gè)非凡的小例子；而這僅是冰山一角。閉包是 Lisp 特有的美妙事物之一。閉包開創(chuàng)了一種在別的語言當(dāng)中，像是不可思議的程序設(shè)計(jì)方法。

6.6 示例：函數(shù)構(gòu)造器 (Example: Function Builders)

Dylan 是 Common Lisp 與 Scheme 的混合物，有著 Pascal 一般的語法。它有著大量返回函數(shù)的函數(shù)：除了上一節(jié)我們所看過的complement?，Dylan 包含:?compose?、?disjoin?、?conjoin?、?curry?、?rcurry?以及?always?。圖 6.2 有這些函數(shù)的 Common Lisp 實(shí)現(xiàn)，而圖 6.3 演示了一些從定義延伸出的等價(jià)函數(shù)。

(defun compose (&rest fns)
  (destructuring-bind (fn1 . rest) (reverse fns)
    #'(lambda (&rest args)
        (reduce #'(lambda (v f) (funcall f v))
                rest
                :initial-value (apply fn1 args)))))

(defun disjoin (fn &rest fns)
  (if (null fns)
      fn
      (let ((disj (apply #'disjoin fns)))
        #'(lambda (&rest args)
            (or (apply fn args) (apply disj args))))))

(defun conjoin (fn &rest fns)
  (if (null fns)
      fn
      (let ((conj (apply #'conjoin fns)))
        #'(lambda (&rest args)
            (and (apply fn args) (apply conj args))))))

(defun curry (fn &rest args)
  #'(lambda (&rest args2)
      (apply fn (append args args2))))

(defun rcurry (fn &rest args)
  #'(lambda (&rest args2)
      (apply fn (append args2 args))))

(defun always (x) #'(lambda (&rest args) x))

圖 6.2 Dylan 函數(shù)建構(gòu)器

首先，?compose?接受一個(gè)或多個(gè)函數(shù)，并返回一個(gè)依序?qū)⑵鋮?shù)應(yīng)用的新函數(shù)，即，

(compose #'a #'b #'c)

返回一個(gè)函數(shù)等同于

#'(lambda (&rest args) (a (b (apply #'c args))))

這代表著?compose?的最后一個(gè)實(shí)參，可以是任意長(zhǎng)度，但其它函數(shù)只能接受一個(gè)實(shí)參。

下面我們建構(gòu)了一個(gè)函數(shù)，先給取參數(shù)的平方根，取整后再放回列表里，接著返回:

> (mapcar (compose #'list #'round #'sqrt)
          '(4 9 16 25))
((2) (3) (4) (5))

接下來的兩個(gè)函數(shù)，?disjoin?及?conjoin?同接受一個(gè)或多個(gè)謂詞作為參數(shù)：?disjoin?當(dāng)任一謂詞返回真時(shí)，返回真，而?conjoin?當(dāng)所有謂詞返回真時(shí)，返回真。

> (mapcar (disjoin #'integerp #'symbolp)
          '(a "a" 2 3))
(T NIL T T)

> (mapcar (conjoin #'integerp #'symbolp)
          '(a "a" 2 3))
(NIL NIL NIL T)

若考慮將謂詞定義成集合，?disjoin?返回傳入?yún)?shù)的聯(lián)集（union），而?conjoin?則是返回傳入?yún)?shù)的交集（intersection）。

      cddr = (compose #'cdr #'cdr)
      nth  = (compose #'car #'nthcdr)
      atom = (compose #'not #'consp)
           = (rcurry #'typep 'atom)
        <= = (disjoin #'< #'=)
     listp = (disjoin #'< #'=)
           = (rcurry #'typep 'list)
        1+ = (curry #'+ 1)
           = (rcurry #'+ 1)
        1- = (rcurry #'- 1)
    mapcan = (compose (curry #'apply #'nconc) #'mapcar
complement = (curry #'compose #'not)

圖 6.3 某些等價(jià)函數(shù)

函數(shù)?curry?與?rcurry?（“right curry”）精神上與前一小節(jié)的?make-adder?相同。兩者皆接受一個(gè)函數(shù)及某些參數(shù)，并返回一個(gè)期望剩余參數(shù)的新函數(shù)。下列任一個(gè)函數(shù)等同于?(make-adder?3)?:

(curry #'+ 3)
(rcurry #'+ 3)

當(dāng)函數(shù)的參數(shù)順序重要時(shí)，很明顯可以看出?curry?與?rcurry?的差別。如果我們?curry?#'-?，我們得到一個(gè)用其參數(shù)減去某特定數(shù)的函數(shù)，

(funcall (curry #'- 3) 2)
1

而當(dāng)我們?rcurry?#'-?時(shí)，我們得到一個(gè)用某特定數(shù)減去其參數(shù)的函數(shù):

(funcall (rcurry #'- 3) 2)
-1

最后，?always?函數(shù)是 Common Lisp 函數(shù)?constantly?。接受一個(gè)參數(shù)并原封不動(dòng)返回此參數(shù)的函數(shù)。和?identity?一樣，在很多需要傳入函數(shù)參數(shù)的情況下很有用。

6.7 動(dòng)態(tài)作用域 (Dynamic Sc??ope)

2.11 小節(jié)解釋過局部與全局變量的差別。實(shí)際的差別是詞法作用域（lexical scope）的詞法變量（lexical variable），與動(dòng)態(tài)作用域（dynamic scope）的特別變量（special variable）的區(qū)別。但這倆幾乎是沒有區(qū)別，因?yàn)榫植孔兞繋缀蹩偸鞘窃~法變量，而全局變量總是是特別變量。

在詞法作用域下，一個(gè)符號(hào)引用到上下文中符號(hào)名字出現(xiàn)的地方。局部變量缺省有著詞法作用域。所以如果我們?cè)谝粋€(gè)環(huán)境里定義一個(gè)函數(shù)，其中有一個(gè)變量叫做?x?，

(let ((x 10))
  (defun foo ()
    x))

則無論?foo?被調(diào)用時(shí)有存在其它的?x?，主體內(nèi)的?x?都會(huì)引用到那個(gè)變量:

> (let ((x 20)) (foo))
10

而動(dòng)態(tài)作用域，我們?cè)诃h(huán)境中函數(shù)被調(diào)用的地方尋找變量。要使一個(gè)變量是動(dòng)態(tài)作用域的，我們需要在任何它出現(xiàn)的上下文中聲明它是?special?。如果我們這樣定義?foo?：

(let ((x 10))
  (defun foo ()
    (declare (special x))
    x))

則函數(shù)內(nèi)的?x?就不再引用到函數(shù)定義里的那個(gè)詞法變量，但會(huì)引用到函數(shù)被調(diào)用時(shí)，當(dāng)下所存在的任何特別變量?x?:

> (let ((x 20))
    (declare (special x))
    (foo))
20

新的變量被創(chuàng)建出來之后， 一個(gè)?declare?調(diào)用可以在代碼的任何地方出現(xiàn)。?special?聲明是獨(dú)一無二的，因?yàn)樗梢愿淖兂绦虻男袨椤?13 章將討論其它種類的聲明。所有其它的聲明，只是給編譯器的建議；或許可以使程序運(yùn)行的更快，但不會(huì)改變程序的行為。

通過在頂層調(diào)用?setf?來配置全局變量，是隱式地將變量聲明為特殊變量:

> (setf x 30)
30
> (foo)
30

在一個(gè)文件里的代碼，如果你不想依賴隱式的特殊聲明，可以使用?defparameter?取代，讓程序看起來更簡(jiǎn)潔。

動(dòng)態(tài)作用域什么時(shí)候會(huì)派上用場(chǎng)呢？通常用來暫時(shí)給某個(gè)全局變量賦新值。舉例來說，有 11 個(gè)變量來控制對(duì)象印出的方式，包括了*print-base*?，缺省是?10?。如果你想要用 16 進(jìn)制顯示數(shù)字，你可以重新綁定?*print-base*?:

> (let ((*print-base* 16))
    (princ 32))
20
32

這里顯示了兩件事情，由?princ?產(chǎn)生的輸出，以及它所返回的值。他們代表著同樣的數(shù)字，第一次在被印出時(shí)，用 16 進(jìn)制顯示，而第二次，因?yàn)樵?let?表達(dá)式外部，所以是用十進(jìn)制顯示，因?yàn)?*print-base*?回到之前的數(shù)值，?10?。

6.8 編譯 (Compilation)

Common Lisp 函數(shù)可以獨(dú)立被編譯或挨個(gè)文件編譯。如果你只是在頂層輸入一個(gè)?defun?表達(dá)式：

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

許多實(shí)現(xiàn)會(huì)創(chuàng)建一個(gè)直譯的函數(shù)（interpreted function）。你可以將函數(shù)傳給?compiled-function-p?來檢查一個(gè)函數(shù)是否有被編譯:

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

若你將?foo?函數(shù)名傳給?compile?:

> (compile 'foo)
FOO

則這個(gè)函數(shù)會(huì)被編譯，而直譯的定義會(huì)被編譯出來的取代。編譯與直譯函數(shù)的行為一樣，只不過對(duì)?compiled-function-p?來說不一樣。

你可以把列表作為參數(shù)傳給?compile?。這種?compile?的用法在 161 頁 (譯注: 10.1 小節(jié))。

有一種函數(shù)你不能作為參數(shù)傳給?compile?：一個(gè)像是?stamp?或是?reset?這種，在頂層明確使用詞法上下文輸入的函數(shù) (即?let?)?[3]在一個(gè)文件里面定義這些函數(shù)，接著編譯然后載入文件是可以的。這么限制直譯的代碼的是實(shí)作的原因，而不是因?yàn)樵谠~法上下文里明確定義函數(shù)有什么問題。

通常要編譯 Lisp 代碼不是挨個(gè)函數(shù)編譯，而是使用?compile-file?編譯整個(gè)文件。這個(gè)函數(shù)接受一個(gè)文件名，并創(chuàng)建一個(gè)原始碼的編譯版本 ── 通常會(huì)有同樣的名稱，但不同的擴(kuò)展名。當(dāng)編譯過的文件被載入時(shí)，?compiled-function-p?應(yīng)給所有定義在文件內(nèi)的函數(shù)返回真。

當(dāng)一個(gè)函數(shù)包含在另一個(gè)函數(shù)內(nèi)時(shí)，包含它的函數(shù)會(huì)被編譯，而且內(nèi)部的函數(shù)也會(huì)被編譯。所以?make-adder?(108 頁)被編譯時(shí)，它會(huì)返回編譯的函數(shù):

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

6.9 使用遞歸 (Using Recursion)

比起多數(shù)別的語言，遞歸在 Lisp 中扮演了一個(gè)重要的角色。這主要有三個(gè)原因：

1. 函數(shù)式程序設(shè)計(jì)。遞歸演算法有副作用的可能性較低。
2. 遞歸數(shù)據(jù)結(jié)構(gòu)。 Lisp 隱式地使用了指標(biāo)，使得遞歸地定義數(shù)據(jù)結(jié)構(gòu)變簡(jiǎn)單了。最常見的是用在列表：一個(gè)列表的遞歸定義，列表為空表，或是一個(gè)?cons?，其中?cdr?也是個(gè)列表。
3. 優(yōu)雅性。Lisp 程序員非常關(guān)心它們的程序是否美麗，而遞歸演算法通常比迭代演算法來得優(yōu)雅。

學(xué)生們起初會(huì)覺得遞歸很難理解。但 3.9 節(jié)指出了，如果你想要知道是否正確，不需要去想遞歸函數(shù)所有的調(diào)用過程。

同樣的如果你想寫一個(gè)遞歸函數(shù)。如果你可以描述問題是怎么遞歸解決的，通常很容易將解法轉(zhuǎn)成代碼。要使用遞歸來解決一個(gè)問題，你需要做兩件事：

1. 你必須要示范如何解決問題的一般情況，通過將問題切分成有限小并更小的子問題。
2. 你必須要示范如何通過 ── 有限的步驟，來解決最小的問題 ── 基本用例。

如果這兩件事完成了，那問題就解決了。因?yàn)檫f歸每次都將問題變得更小，而一個(gè)有限的問題終究會(huì)被解決的，而最小的問題僅需幾個(gè)有限的步驟就能解決。

舉例來說，下面這個(gè)找到一個(gè)正規(guī)列表（proper list）長(zhǎng)度的遞歸算法，我們每次遞歸時(shí)，都可以找到更小列表的長(zhǎng)度：

1. 在一般情況下，一個(gè)正規(guī)列表的長(zhǎng)度是它的?cdr?加一。
2. 基本用例，空列表長(zhǎng)度為?0?。

當(dāng)這個(gè)描述翻譯成代碼時(shí)，先處理基本用例；但公式化遞歸演算法時(shí)，我們通常從一般情況下手。

前述的演算法，明確地描述了一種找到正規(guī)列表長(zhǎng)度的方法。當(dāng)你定義一個(gè)遞歸函數(shù)時(shí)，你必須要確定你在分解問題時(shí)，問題實(shí)際上越變?cè)叫　Ｈ〉靡粋€(gè)正規(guī)列表的?cdr?會(huì)給出?length?更小的子問題，但取得環(huán)狀列表（circular list）的?cdr?不會(huì)。

這里有兩個(gè)遞歸算法的示例。假定參數(shù)是有限的。注意第二個(gè)示例，我們每次遞歸時(shí)，將問題分成兩個(gè)更小的問題：

第一個(gè)例子，?member?函數(shù)，我們說某物是列表的成員，需滿足：如果它是第一個(gè)元素的成員或是?member?的?cdr?的成員。但空列表沒有任何成員。

第二個(gè)例子，?copy-tree?一個(gè)?cons?的?copy-tree?，是一個(gè)由?cons?的?car?的?copy-tree?與?cdr?的?copy-tree?所組成的。一個(gè)原子的?copy-tree?是它自己。

一旦你可以這樣描述算法，要寫出遞歸函數(shù)只差一步之遙。

某些算法通常是這樣表達(dá)最自然，而某些算法不是。你可能需要翻回前面，試試不使用遞歸來定義?our-copy-tree?(41 頁，譯注: 3.8 小節(jié))。另一方面來說，23 頁 (譯注: 2.13 節(jié)) 迭代版本的?show-squares?可能更容易比 24 頁的遞歸版本要容易理解。某些時(shí)候是很難看出哪個(gè)形式比較自然，直到你試著去寫出程序來。

如果你關(guān)心效率，有兩個(gè)你需要考慮的議題。第一，尾遞歸（tail-recursive），會(huì)在 13.2 節(jié)討論。一個(gè)好的編譯器，使用循環(huán)或是尾遞歸的速度，應(yīng)該是沒有或是區(qū)別很小的。然而如果你需要使函數(shù)變成尾遞歸的形式時(shí)，或許直接用迭代會(huì)更好。

另一個(gè)需要銘記在心的議題是，最顯而易見的遞歸算法，不一定是最有效的。經(jīng)典的例子是費(fèi)氏函數(shù)。它是這樣遞歸地被定義的，

1. Fib(0) = Fib(1) = 1
2. Fib(n) = Fib(n-1)+Fib(n-2)

直接翻譯這個(gè)定義，

(defun fib (n)
  (if (<= n 1)
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

這樣是效率極差的。一次又一次的重復(fù)計(jì)算。如果你要找?(fib?10)?，這個(gè)函數(shù)計(jì)算?(fib?9)?與?(fib?8)?。但要計(jì)算出?(fib?9)，它需要再次計(jì)算?(fib?8)?，等等。

下面是一個(gè)算出同樣結(jié)果的迭代版本:

(defun fib (n)
  (do ((i n (- i 1))
       (f1 1 (+ f1 f2))
       (f2 1 f1))
      ((<= i 1) f1)))

迭代的版本不如遞歸版本來得直觀，但是效率遠(yuǎn)遠(yuǎn)高出許多。這樣的事情在實(shí)踐中常發(fā)生嗎？非常少 ── 這也是為什么所有的教科書都使用一樣的例子 ── 但這是需要注意的事。

Chapter 6 總結(jié) (Summary)

1. 命名函數(shù)是一個(gè)存在符號(hào)的?symbol-function?部分的函數(shù)。?defun?宏隱藏了這樣的細(xì)節(jié)。它也允許你定義文檔字符串（documentation string），并指定?setf?要怎么處理函數(shù)調(diào)用。
2. 定義局部函數(shù)是有可能的，與定義局部變量有相似的精神。
3. 函數(shù)可以有選擇性參數(shù)（optional）、剩余（rest）以及關(guān)鍵字（keyword）參數(shù)。
4. 實(shí)用函數(shù)是 Lisp 的擴(kuò)展。他們是由下而上編程的小規(guī)模示例。
5. 只要有某物引用到詞法變量時(shí)，它們會(huì)一直存在。閉包是引用到自由變量的函數(shù)。你可以寫出返回閉包的函數(shù)。
6. Dylan 提供了構(gòu)造函數(shù)的函數(shù)。很簡(jiǎn)單就可以使用閉包，然后在 Common Lisp 中實(shí)現(xiàn)它們。
7. 特別變量（special variable）有動(dòng)態(tài)作用域 (dynamic scope)。
8. Lisp 函數(shù)可以單獨(dú)編譯，或（更常見）編譯整個(gè)文件。
9. 一個(gè)遞歸演算法通過將問題細(xì)分成更小丶更小的子問題來解決問題。

Chapter 6 練習(xí) (Exercises)

1. 定義一個(gè)?tokens?版本 (67 頁)，接受?:test?與?:start?參數(shù)，缺省分別是?#'constituent?與?0?。(譯注: 67 頁在 4.5 小節(jié))
2. 定義一個(gè)?bin-search?(60 頁)的版本，接受?:key?,?:test?,?start?與?end?參數(shù)，有著一般的意義與缺省值。(譯注: 60 頁在 4.1 小節(jié))
3. 定義一個(gè)函數(shù)，接受任何數(shù)目的參數(shù)，并返回傳入的參數(shù)。
4. 修改?most?函數(shù) (105 頁)，使其返回 2 個(gè)數(shù)值，一個(gè)列表中最高分的兩個(gè)元素。(譯注: 105 頁在 6.4 小節(jié))
5. 用?filter?(105 頁) 來定義?remove-if?（沒有關(guān)鍵字）。(譯注: 105 頁在 6.4 小節(jié))
6. 定義一個(gè)函數(shù)，接受一個(gè)參數(shù)丶一個(gè)數(shù)字，并返回目前傳入?yún)?shù)中最大的那個(gè)。
7. 定義一個(gè)函數(shù)，接受一個(gè)參數(shù)丶一個(gè)數(shù)字，若傳入?yún)?shù)比上個(gè)參數(shù)大時(shí)，返回真。函數(shù)第一次調(diào)用時(shí)應(yīng)返回?nil?。
8. 假設(shè)?expensive?是一個(gè)接受一個(gè)參數(shù)的函數(shù)，一個(gè)介于 0 至 100 的整數(shù)（包含 100)，返回一個(gè)耗時(shí)的計(jì)算結(jié)果。定義一個(gè)函數(shù)frugal?來返回同樣的答案，但僅在沒見過傳入?yún)?shù)時(shí)調(diào)用?expensive?。
9. 定義一個(gè)像是?apply?的函數(shù)，但在任何數(shù)字印出前，缺省用 8 進(jìn)制印出。

腳注

[1] | 在這個(gè)情況下，?nreverse?(在 222 頁描述)和?reverse?做一樣的事情，但更有效率。

[2] | “閉包”這個(gè)名字是早期的 Lisp 方言流傳而來。它是從閉包需要在動(dòng)態(tài)作用域里實(shí)現(xiàn)的方式衍生而來。

[3] | 以前的 ANSI Common Lisp，?compile?的第一個(gè)參數(shù)也不能是一個(gè)已經(jīng)編譯好的函數(shù)。