第 4 章 實用函數(shù)

第 4 章 實用函數(shù)

Common Lisp 操作符分為三類：可自定義的函數(shù)和宏，以及不能自定義的特殊形式（specialform）。本章將講述用函數(shù)來擴(kuò)展 Lisp 的技術(shù)。但這里的 "技術(shù)" 和通常的含義不太一樣。關(guān)于這些函數(shù)，重要的不是知道怎樣寫，而是要知道它們從何而來。編寫 Lisp 擴(kuò)展所使用的技術(shù)和你編寫其他任何 Lisp 函數(shù)所使用的技術(shù)大同小異。編寫 Lisp 擴(kuò)展的難點并不在于代碼怎么寫，而在于決定寫什么。

4.1 實用工具的誕生

自底向上程序設(shè)計，簡單說，就是程序員滿腹牢騷，"到底是誰把我的 Lisp 設(shè)計成這個模樣"。你一邊在編寫程序，同時也在為 Lisp 增加那些可以讓你程序更容易編寫的新操作符。這些新操作符被稱為實用工具。

"實用工具" 這一術(shù)語并無明確的定義。有那么一段代碼，如果把它看成獨立的程序，感覺小了點，要是把它作為特定程序的一部分的話，這段代碼又太通用了，這時就可以稱之為實用工具。舉例來說，數(shù)據(jù)庫不能稱為實用工具，但是對列表進(jìn)行單一操作的函數(shù)就可以。大多數(shù)實用工具和 Lisp 已有的函數(shù)和宏很相似。事實上，許多 Common Lisp 內(nèi)置的操作符就源自實用工具。用于收集列表中所有滿足條件元素的 remove-if-not 函數(shù)，在它成為 Common Lisp 的一部分以前，就被程序員們私下里各自定義了多年。

學(xué)習(xí)編寫實用工具與其說是學(xué)習(xí)編寫的技術(shù)，不如說是養(yǎng)成編寫實用工具的習(xí)慣。自底向上程序設(shè)計意味著在編寫程序的同時，也在設(shè)計一門編程語言。為了做好這一點，你必須培養(yǎng)出一種能看出程序中缺少何種操作符的洞察力。你必須能夠在看到一個程序時說， "啊，其實你真正的意思是這個。"

舉個例子，假設(shè) nicknames 是這樣一個函數(shù)， 它接受一個名字，然后構(gòu)造出一個列表，列表由這個名字的所有昵稱組成。有了這個函數(shù)，我們怎樣收集一個名字列表對應(yīng)的所有昵稱呢? Lisp 的初學(xué)者可能會寫出類似的函數(shù)：

(defun all-nicknames (names)
 (if (null names)
  nil
  (nconc (nicknames (car names))
   (all-nicknames (cdr names)))))

而更有經(jīng)驗的 Lisp 程序員可能一看到這樣的函數(shù)就會說 "啊，其實你真正想要的是 mapcan"。 然后，不再被迫定義并調(diào)用一個新函數(shù)來找出一組人的所有昵稱，現(xiàn)在只要一個表達(dá)式就夠了：

(mapcan #'nicknames people)

定義 all-nicknames 完全是在重復(fù)地發(fā)明輪子。它的問題還不只于此： 它同時也葬送了一個機(jī)會： 本可以用通用操作符來直接完成某件事，卻使用了專用的函數(shù)來實現(xiàn)它。

對這個例子來說，操作符 mapcan 是現(xiàn)成的。任何知道 mapcan 的人在看到 all-nicknames 時都會覺得有點不太舒服。要想在自底向上程序設(shè)計方面做得好，就要在缺少的操作符還沒有寫出來的時候，同樣覺得不舒服。你必須能夠在說出 "你真正想要的是 x" 的同時，知道 x 應(yīng)該是什么。

Lisp 編程的要求之一，就是一旦有需要，就應(yīng)該構(gòu)思出新的實用工具。本章的目的就是揭示這些工具是如何從無到有的。假設(shè) towns 是一個附近城鎮(zhèn)的列表,按從近到遠(yuǎn)排序，bookshops 函數(shù)返回一個城市中所有書店的列表。如果想要查找最近的一個有書店的城市，以及該城市里的書店,我們可能一開始會這樣做：

(let ((town (find-if #'bookshops towns)))
 (values town (bookshops town)))

但是這樣有點不大合適： 當(dāng) find-if 找到一個 bookshops ，返回非空元素時， 這個值被直接丟掉了，然后馬上又要重新算一次。如果 bookshops 是一個耗時的函數(shù)調(diào)用， 那么這個用法將是既丑陋又低效的。為了避免做無用功，我們用下面的函數(shù)代替它：

(defun find-books (towns)
 (if (null towns)
  nil
  (let ((shops (bookshops (car towns))))
   (if shops
(values (car towns) shops)
(find-books (cdr towns))))))

這樣，調(diào)用 (find-books towns) 至少能得到我們想要的結(jié)果，并且免去了不必要的計算。但是別急，我們會不會在以后再做一次類似的搜索呢？這里我們真正想要的是一個實用工具， 它集成了 find-if 和 some 的功能，并且能返回符合要求的元素和判斷函數(shù)的返回值。這樣的一個實用工具可能被定義成：

(defun find2 (fn lst)
 (if (null lst)
  nil
  (let ((val (funcall fn (car lst))))
   (if val
(values (car lst) val)
(find2 fn (cdr lst))))))

注意到 find-books 和find2 之間的相似程度。的確， 后者可以看作前者提煉后的結(jié)果?，F(xiàn)在，借助這個新的實用工具，我們就可以用單個表達(dá)式達(dá)到最初的目標(biāo)了：

(find2 #'bookshops towns)

Lisp 編程有一個獨一無二的特征，就是函數(shù)在作為參數(shù)時扮演了一個重要的角色。這也是 Lisp 被廣泛采納用于自底向上程序設(shè)計的部分原因。當(dāng)你能把一個函數(shù)的形骸作為函數(shù)型參數(shù)傳進(jìn)函數(shù)時，你就可以更輕易地從這個函數(shù)中抽象出它的神髓。

程序設(shè)計的入門課程從一開始就教授如何通過這種抽象來減少重復(fù)勞動。前幾課的內(nèi)容之一就是： 切忌把程序的行為寫死在代碼里面。與其定義兩個函數(shù)，它們幾乎完成相同的工作，但其中只有一兩個常量不一樣，不如定義成一個函數(shù)然后把那些常量以參數(shù)的形式傳給它。在 Lisp 里可以走得更遠(yuǎn)一些，因為我們可以把整個函數(shù)都作為參數(shù)傳遞。在前兩個例子里，我們都從一個專用的函數(shù)走向了帶有函數(shù)型參數(shù)的更為通用的函數(shù)。雖然在第一個例子里我們用的是預(yù)定義的 mapcan ，第二個例子里則寫了一個新的實用工具 find2 ，但它們遵循的基本原則是一樣的： 與其將通用的和專用的混在一起，不如定義一個通用的然后把專用的部分作為參數(shù)。

如果慎重使用這個原則，就會得到顯然更優(yōu)雅的程序。它不是驅(qū)動自底向上程序設(shè)計的唯一方法，但卻是主要的一個。本章定義的32 個實用工具里，有18個帶有函數(shù)型參數(shù)。

4.2 投資抽象

如果說簡潔是智慧的靈魂，那么它和效率也同是優(yōu)秀軟件的本質(zhì)特征。編寫和維護(hù)一個程序的開銷與其長 度成正比。同等條件下，程序越短越好。

從這一角度來看，編寫實用工具可以被視為一種投資。通過把 find-books 替換成 find2 這個實用工具， 最后得到的程序行數(shù)仍然是那么多。但從某種角度來看我們確實縮短了程序， 因為實用工具的長度可以不用算在當(dāng)前這個程序的帳上。

把對 Lisp 的擴(kuò)展看作資本支出并不只是會計上的手段。實用工具可以放在單獨的文件里；它們既不會在我們編寫程序時分散我們的精力，也不會在事后我們修改遺留代碼時被牽連進(jìn)去。

然而，作為一項投資，實用工具還是需要額外的關(guān)照。尤其要緊的是它們的質(zhì)量必須過關(guān)。由于它們要被多次使用，所以任何不正確或者低效率之處都將會成倍地償還。除此之外，還要注意它們的設(shè)計： 一個新的實用工具必須為通用場合而作，而不是僅僅著眼于手頭的問題。最后，和任何其他資本支出一樣， 我們不能急于求成。如果你考慮創(chuàng)造一些新操作符作為程序開發(fā)的副產(chǎn)品，但又不敢確定以后在其他場合還能用到它們， 那就先做出來，但只是把它和使用到它的特定程序放在一起。等以后如果在其他程序里也用到這些操作符的時候， 就可以把它們從子程序提升到實用工具的層面，然后將它們通用化。

find2 這個實用工具看來是一次不錯的投資。投入7 行代碼的本錢，我們立即得到了7 行收益。這一實用工具在首次使用時就已收回成本了。Guy Steele 寫道，編程語言應(yīng)該 "順應(yīng)我們追求簡潔的自然傾向：" ……我們傾向于相信一種編程構(gòu)造產(chǎn)生的開銷與它所導(dǎo)致的編程者的不適程度成正比 （我這里所說的"相信" 指的是下意識的傾向而非有意的好惡）。確實，對于語言設(shè)計者來說，理應(yīng)把這個心理學(xué)原則熟記于心。我們認(rèn)為加法的成本較低，部分原因是由于我們只要用一個字符 "+" ?

就可以表示它。即使一種編程構(gòu)造開銷較大，如果我們寫代碼的時候能比其他更便宜的方法省一半力氣的話，也會更喜歡用它。

在任何語言里，除非允許用新的實用工具來表達(dá)語言本身，否則這種 "對簡潔代碼的傾向性" 將引起麻煩。

最簡短的表達(dá)方式很少是最高效的。如果我們想知道一個列表是否比另一個列表更長，原始的 Lisp 將誘使我們寫出

(> (length x) (length y))

如果我們想把一個函數(shù)映射到幾個列表上，可能同樣會有將這些列表先連接起來的想法：

(mapcar fn (append x y z))

這些例子說明編寫實用工具對于某些情形尤為重要，否則，稍不注意就會誤入低效率的歧途。一門語言，一旦裝備了趁手好用的實用工具，它將會引領(lǐng)我們寫出更抽象的程序。如果這些實用工具的實現(xiàn)精巧合理， 它們更會促使我們寫出更加高效的實用工具。

一組實用工具集無疑會使整個編程工作更容易。但它們還有更重要的作用： 讓你寫出更好的程序。廚師看到對味的食材會忍不住動手烹飪，文人騷客也一樣，他們有了合適的題材就會文思如泉涌。這就是為何藝術(shù)家們喜歡在他們的工作室里放很多工具和材料。他們知道如果手頭有了需要的東西，創(chuàng)作沖動就會更強(qiáng)。同樣的現(xiàn)象也出現(xiàn)在自底向上編寫的程序中。一旦寫好了一個新的實用工具，你可能發(fā)現(xiàn)對它的使用往往超乎預(yù)想。

接下來的章節(jié)將介紹幾類實用函數(shù)。它們遠(yuǎn)不能涵蓋你可以加入到 Lisp 的全部函數(shù)類型。然而，這里作為示例給出的所有實用工具都已經(jīng)在實踐中充分地證明了它們的存在價值。

4.3 列表上的操作

列表最初曾是 Lisp 主要的數(shù)據(jù)結(jié)構(gòu)。事實上，"Lisp" 這個名字就來自 "LIStProcessing（列表處理）"。不過， 請不要被這個故事誤導(dǎo)了。 Lisp 跟列表處理之間的關(guān)系并不比 Polo 襯衣和馬球（polo）之間的關(guān)系更親近。

一個高度優(yōu)化的 Common Lisp 程序里可能根本就沒有列表的蹤影。

盡管如此，至少在編譯期它們還是列表。最專業(yè)的程序，在運行期很少使用列表， 相反可能會在編譯期生成宏展開式時大量使用列表。所以盡管列表的角色在現(xiàn)代 Lisp 方言里被淡化了，但是針對列表的各種操作仍然是 Lisp 程序的重要組成部分。

代碼 4.1 和 4.2 里包括了一些構(gòu)造和檢查列表的函數(shù)。那些在圖4.1 中給出的都是些值得定義的最小實用工具。為了滿足效率的需要，應(yīng)該把它們?nèi)柯暶鞒?inline。（見17頁）

第一個函數(shù)是 last1，它返回列表的最后一個元素。內(nèi)置的 last 函數(shù)其實返回的是列表的最后一個cons， 而非最后一個元素。多數(shù)時候，人們都是通過 （car （last ...）） 的方式來得到其最后一個元素的。是否有必要為這種情況寫一個新的實用工具呢 是的， 如果它可以有效地替代一個內(nèi)置操作符，那么答案就是肯定的。

注意到 last1 沒有任何錯誤檢查。一般而言，本書中定義的代碼都將不做任何錯誤檢查。部分原因只是為了使這些示例代碼更加清晰。但是在相對短小的實用工具里不做任何錯誤檢查也合情合理。如果我們試一下這個：

;; 代碼 4.1： 操作列表的一些小函數(shù)
(proclaim '(inline last1 single append1 conc1 mklist))

(defun last1 (lst)
 (car (last lst)))

(defun single (lst)
 (and (consp lst) (not (cdr lst))))

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

(defun conc1 (lst obj)
 (nconc lst (list obj)))

(defun mklist (obj)
 (if (listp obj) obj (list obj)))

;; 代碼 4.2： 操作列表的一些較大函數(shù)
(defun longer (x y)
 (labels ((compare (x y)
       (and (consp x)
        (or (null y)
         (compare (cdr x) (cdr y))))))
  (if (and (listp x) (listp y))
   (compare x y)
   (> (length x) (length y)))))

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

(defun group (source n)
 (if (zerop n) (error "zero length"))
 (labels ((rec (source acc)
   (let ((rest (nthcdr n source)))
    (if (consp rest)
     (rec rest (cons (subseq source 0 n) acc))
     (nreverse (cons source acc))))))
  (if source (rec source nil) nil)))

> (last1 "blub")
>>Error: "blub" is not a list.
Broken at LAST...

這一錯誤將被 last 本身捕捉到。當(dāng)實用工具規(guī)模很小時，它們從開始傳遞的位置開始形成的抽象層很薄。

正如可以看透的薄冰那樣，人們可以一眼看清像 last1 這種實用工具，從而理解從它們底層拋出的錯誤。

single 函數(shù)判斷某個東西是否為單元素的列表。Lisp 程序經(jīng)常需要做這種測試。在一開始實現(xiàn)的時候， 可能會把英語直接翻譯過來：

(= (length lst) 1)

如果寫成這個樣子，測試操作將會極其低效。其實只要一看完列表的第一個元素，就知道所有我們想知道的事情了。

接下來是 append1 和nconc1 。兩個都是在列表結(jié)尾處追加一個新元素，只不過后者是破壞性的。這些函數(shù)雖然小，但是很常用，所以還是應(yīng)該定義的。而且在過去的 Lisp 方言里，確實也預(yù)定義了append1。

然后是 mklist ，它（至少） 在 Interlisp 里是已經(jīng)預(yù)定義了的。其目的是確保某個東西是列表。很多 Lisp 函數(shù)被寫成要么返回一個單一的值，要么返回一個由多個值組成的列表。假設(shè)lookup 就是這樣的函數(shù)，同時，data 是一個列表，我們把這個函數(shù)依次應(yīng)用于data 中的所有元素，每次函數(shù)都會返回相應(yīng)的結(jié)果，最后要把得到的結(jié)果收集在一起?？梢赃@樣寫：

(mapcan #'(lambda (d) (mklist (lookup d)))
  data)

圖4.2 有一些更大的列表實用工具的例子。第一個是longer ，不管是從效率，還是從抽象程度上來看，它都可圈可點。它比較兩個列表，只有在前一個列表更長的時候才返回真。當(dāng)比較兩個列表的長度時，很容易就直接這樣寫：

(> (length x) (length y))

這樣的做法之所以低效，是因為它讓程序從頭到尾遍歷兩個列表。如果一個列表的長度遠(yuǎn)遠(yuǎn)超過另一個， 那么在超出較短列表長度上的進(jìn)行的所有遍歷操作都將是徒勞。像longer 那樣做并且并行地遍歷兩個列表會快一些。

嵌在 longer 里面的是個遞歸函數(shù)，它用于比較兩個列表長度。因為longer 是用來比較長度的，所以只要能用length 判斷長度的對象，它都能處理。但是并行比較長度的辦法只適用于列表，所以這個內(nèi)部函數(shù)只有當(dāng)兩個參數(shù)都是列表時才可以調(diào)用。

下一個函數(shù)是 filter，它和 some 的關(guān)系類似于 remove-if-not 和 find-if 之間的關(guān)系。內(nèi)置的 remove-if-not 的返回值和這樣操作的結(jié)果一樣： 即把給定列表的所有 cdr 依次傳給 find-if ，同時另一個參數(shù)一直用同一個函數(shù)，這樣得到的所有返回值串起來就是 remove-if-not 的返回值。與之相應(yīng)，filter 返回的列表由 some 依次作用在列表 cdr 上的返回值構(gòu)成：

> (filter #'(lambda (x) (if (numberp x) (1+ x)))
  '(a 1 2 b 3 c d 4))
(2 3 4 5)

你傳給 filter 一個函數(shù)和一個列表，如果這個函數(shù)作用在列表元素上返回的值不為空，就把這樣的返回值收集起來，構(gòu)成列表，把它作為 filter 自己的返回值。

注意到 filter 使用了一個累加器，它的工作方式和第 2.8 節(jié)描述的尾遞歸函數(shù)一樣。實際上，編寫尾遞歸函數(shù)的目的就是讓編譯器能夠生成形如filter 那樣的代碼。對于 filter 來說，這種直接的迭代定義比尾遞歸的形式來得簡單。對于列表的聚積操作來說， filter 定義中的 push 和 nreverse 組合是標(biāo)準(zhǔn)的 Lisp 用法。

示例代碼 4.2 中的最后一個函數(shù)用來將列表分組成子列表。你給 group 一個列表 和一個數(shù)字 ，那它將返回一個新列表，由列表 的元素按長度為 的子列表組成。最后剩余的元素放在最后一個子列表里。這樣如果我們給出2 作為第二個參數(shù)，我們就得到一個關(guān)聯(lián)表（asso-list）：

> (group '(a b c d e f g) 2)
((A B) (C D) (E F) (G))

為了把 group 寫成尾遞歸的（見第2.8 節(jié)），這個函數(shù)編得有些拐彎抹角?？焖僭烷_發(fā)的基本原理可以用

在整個程序的開發(fā)上，但它對于單個函數(shù)的編寫也一樣適用。在寫像flatten 這樣的函數(shù)時，從最簡單的可能實現(xiàn)方式開始也許不失為上策。然后，一旦這個最簡版本可用了，如果有必要的話，你就可以用更有效率的迭代或者尾遞歸版本來代替它。如果最早的版本足夠短小，可以把它以注釋的形式留下來用于表述它的復(fù)雜替代者的行為。（group 和圖 4.1， 4.3 中其他函數(shù)的簡化版本可參見書后第268 頁的附注。）

group 定義的與眾不同之處在于它至少檢查了一種錯誤： 如果第二個參數(shù)為 0 ，那么這個函數(shù)就會陷入無休止的遞歸。

從某種意義上說，本書的示例也遵循了通常的 Lisp 實踐經(jīng)驗： 使章節(jié)之間彼此不相互依賴，示例代碼盡可能用原始 Lisp 編寫。但考慮到在定義宏的時候，group 函數(shù)會非常有用，因而它會是個例外，這個函數(shù)將再次出現(xiàn)在后續(xù)章節(jié)的某些地方。

(defun flatten (x)
 (labels ((rec (x acc)
       (cond ((null x) acc)
        ((atom x) (cons x acc))
        (t (rec (car x) (rec (cdr x) acc))))))
  (rec x nil)))

(defun prune (test tree)
 (labels ((rec (tree acc)
       (cond ((null tree) (nreverse acc))
        ((consp (car tree))
         (rec (cdr tree)
          (cons (rec (car tree) nil) acc)))
        (t (rec (cdr tree)
            (if (funcall test (car tree))
             acc
             (cons (car tree) acc)))))))
  (rec tree nil)))

圖4.3： 使用雙遞歸的列表實用工具

圖4.2 中的所有函數(shù)都是作用在列表的最上層（top–level） 結(jié)構(gòu)上。圖 4.3 給出了兩個下降到嵌套列表里的函數(shù)示例。前一個flatten ，也是Interlisp 預(yù)定義的。它返回由一個列表中的所有原子（atom），或者說是元素的元素所組成的列表，即：

> (flatten '(a (b c) ((d e) f)))
(A B C D E F)

圖4.3 中的另一個函數(shù)是 prune ，它對remove-if 的意義就相當(dāng)于copy-tree 之于copy-list。也就是說，它會向下遞歸到子列表里：

> (prune #'evenp '(1 2 (3 (4 5) 6) 7 8 (9)))
(1 (3 (5)) 7 (9))

所有函數(shù)返回值為真的葉子都被刪掉了。

4.4 搜索

本節(jié)給出一些用于搜索列表的函數(shù)示例。盡管 Common Lisp 已經(jīng)提供了豐富的內(nèi)置函數(shù)可以完成同樣的功能， 但對于某些任務(wù)來說光靠這些函數(shù)仍然有些捉襟見肘 或者說它們至少無法高效地完成功能。我們在第 27 頁里虛構(gòu)的案例說明了這一點。圖4.4 中定義的第一個實用工具 find2 ，就是我們?yōu)榱私鉀Q這個問題而做的嘗試。

下個實用工具是 before ，其目的和 find2 類似。它告訴你在一個列表中的對象是否在另一個對象的前面：

> (before 'b 'd '(a b c d))
(B C D)

這個問題非常容易，用原始 Lisp 可以草草寫成：

(< (position 'b '(a b c d)) (position 'd '(a b c d)))
(defun find2 (fn lst)
(if (null lst)
nil
(let ((val (funcall fn (car lst))))
(if val
(values (car lst) val)
(find2 fn (cdr lst))))))

(defun before (x y lst &key (test #'eql))
(and lst
(let ((first (car lst)))
(cond ((funcall test y first) nil)
((funcall test x first) lst)
(t (before x y (cdr lst) :test test))))))

(defun after (x y lst &key (test #'eql))
(let ((rest (before y x lst :test test)))
(and rest (member x rest :test test))))

(defun duplicate (obj lst &key (test #'eql))
(member obj (cdr (member obj lst :test test))
:test test))

(defun split-if (fn lst)
 (let ((acc nil))
  (do ((src lst (cdr src)))
   ((or (null src) (funcall fn (car src)))
(values (nreverse acc) src))
   (push (car src) acc))))

圖4.4： 搜索列表的函數(shù)

但是后面這句話既低效又容易錯： 效率低是因為我們不需要把兩個對象都找到， 只需找到前一個對象即可；

而容易出錯是因為，如果兩個對象中的任何一個不在列表里，那么position 將會返回nil ，而后者會成為< 的參數(shù)。使用before 可以同時解決這兩個問題。

由于before 和測試成員關(guān)系的本質(zhì)很相像，所以在定義它的時候，有意模仿了內(nèi)置的member 函數(shù)。就像member ，它帶有一個可選的test 參數(shù)，其缺省值為eql。同時，它不再簡單地返回一個t ，而是試圖返回可能有用的信息： 以作為第一個參數(shù)給出的對象為首的cdr。

注意到，如果before 在碰到第二個參數(shù)之前，就遇到了第一個參數(shù)，那么這個函數(shù)會直接返回真。這樣的話，倘若列表中根本就不存在第二個參數(shù)，它同樣也會返回真：

> (before 'a 'b '(a))
(A)

通過調(diào)用after 我們可以做更為細(xì)致的測試，要求兩個參數(shù)都出現(xiàn)在列表里：

> (after 'a 'b '(b a d))
(A D)
> (after 'a 'b '(a))
NIL

如果 （member ） 在列表 里找到了 ，它會同時返回列表 中以 開頭的那個cdr。這一返回值可以被用來，例如，找出列表中的重復(fù)元素。如果 在列表 中重復(fù)出現(xiàn)，那么用member 就能在返回列表的cdr 中找到它。這一句法被包含在下一個實用工具中，duplicate：

> (duplicate 'a '(a b c a d))
(A D)

以相同的思路，可以依法炮制其他用來判斷是否重復(fù)的實用工具。

很多挑剔的語言設(shè)計者為 Common Lisp 使用 nil 同時代表邏輯假和空列表感到不可思議。這有時確實會帶來麻煩（見132 頁）， 但對于像duplicate 這樣的函數(shù)來說則非常方便。至于判斷元素是否屬于一個序列（sequence） 的那些函數(shù)，用空序列來表示否定的結(jié)果還是比較合理的。

圖4.4 的最后一個函數(shù)也是 member 的某種泛化。不同之處在于 member 先搜索想要找的元素，然后返回從找到元素開始的列表的 cdr，而 split-if 把原列表的兩個部分都返回了。該實用工具主要用于已經(jīng)按照某種規(guī)則排好序的列表：

> (split-if #'(lambda (x) (> x 4))
'(1 2 3 4 5 6 7 8 9 10))
(1 2 3 4)
(5 6 7 8 9 10)

(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)
(setq wins obj
max score))))
(values wins max))))

(defun best (fn lst)
(if (null lst)
nil
(let ((wins (car lst)))
(dolist (obj (cdr lst))
(if (funcall fn obj wins)
(setq wins obj)))
wins)))

(defun mostn (fn lst)
(if (null lst)
(values nil nil)
(let ((result (list (car lst)))
(max (funcall fn (car lst))))
(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))
(cond ((> score max)
(setq max score
result (list obj)))
((= score max)
(push obj result)))))
(values (nreverse result) max))))

圖4.5： 帶有元素比較的搜索函數(shù)

圖4.5 中是另一種類型的搜索函數(shù)： 它們在列表元素之間進(jìn)行比較。第一個函數(shù)是 most ，它每次查看一個元素。most 接受一個列表和一個用來打分的函數(shù)，其返回值是列表中分?jǐn)?shù)最高的元素。分?jǐn)?shù)相等的時候， 排在前面的元素優(yōu)先。

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

為了方便調(diào)用方，most 也返回了獲勝元素的分?jǐn)?shù)。

best 提供了一種更通用的搜索方式。該實用工具接受一個函數(shù)和一個列表，但這里的函數(shù)必須是個兩參數(shù)謂詞。它返回的元素在該謂詞下勝過所有其他元素。

> (best #'> '(1 2 3 4 5))
5

我們可以認(rèn)為best 等價于sort 的car， 但前者的效率更高些。函數(shù)的調(diào)用者有責(zé)任提供一個能在列表所

有元素上定義全序的謂詞。否則列表中元素的順序?qū)⒂绊懡Y(jié)果； 和之前一樣， 在平手的情況下，先出場的元素獲勝。

最后，mostn 接受一個函數(shù)和一個列表，并返回一個由獲得最高分的所有元素組成的列表（以及這個最高分本身）：

> (mostn #'length '((a b) (a b c) (a) (e f g)))
((A B C) (E F G))
3

4.5 映射

還有一類廣泛使用的 Lisp 函數(shù)是映射函數(shù)，它們將一個函數(shù)應(yīng)用到一個參數(shù)的序列上。圖4.6 展示了一些新的映射函數(shù)示例。開始的三個函數(shù)用來將一個函數(shù)應(yīng)用到一系列整數(shù)，而無需cons 出含有這些數(shù)字的列表。前兩個是map0-n 和map1-n ，它們工作在正整數(shù)區(qū)間上：

> (map0-n #'1+ 5)
(1 2 3 4 5 6)

它們都是用mapa-b 實現(xiàn)的，而mapa-b 更為通用，它能對任意的等差數(shù)列操作：

> (mapa-b #'1+ -2 0 .5)
(-1 -0.5 0.0 0.5 1.0)

mapa-b 之后是更通用的map-> ，它可以用于任意類型的對象序列。序列始于第二個參數(shù)給出的對象，序

列的結(jié)束條件由第三個參數(shù)給出的函數(shù)規(guī)定，而序列的后繼元素則由第四個參數(shù)給出的函數(shù)生成。借助map-> ，不僅能遍歷整數(shù)序列，還可以遍歷任何一種數(shù)據(jù)結(jié)構(gòu)。我們能用map-> 定義mapa-b ，如下：

(defun mapa-b (fn a b &optional (step 1))
(map-> fn
a
#'(lambda (x) (> x b))
#'(lambda (x) (+ x step))))

出于效率考慮，內(nèi)置的mapcan 是破壞性的，它也可用下列代碼表達(dá)：

(defun our-mapcan (fn &rest lsts)
(apply #'nconc (apply #'mapcar fn lsts)))

由于mapcan 用nconc 把列表拼接在一起，第一個參數(shù)返回的列表最好是新創(chuàng)建的，否則等下次看的時候它可能就變樣了。這也是為什么 nicknames （第27 頁） 被定義成一個根據(jù)昵稱"生成列表" 的函數(shù)。如果它直接返回一個存放在其他地方的列表，那么使用 mapcan 會很不安全。替代方案是我們只能用append 把返回的列表拼接在一起。對于這類情況，mappend 提供了一個mapcan 的非破壞性版本。

下一個實用工具是mapcars ，如果你想對多個列表mapcar 某個函數(shù)，那么就可以用上它。假設(shè)有兩個數(shù)列，我們希望得到它們的平方根列表，可以用原始 Lisp 這樣實現(xiàn)：

(mapcar #'sqrt (append list1 list2))

但這里的cons 是沒有必要的。我們把list1 和list2 串在一起后，立即丟棄了結(jié)果。借助mapcars ，可以殊途同歸：

(defun map0-n (fn n)
(mapa-b fn 0 n))

(defun map1-n (fn n)
(mapa-b fn 1 n))

(defun mapa-b (fn a b &optional (step 1))
(do ((i a (+ i step))
(result nil))
((> i b) (nreverse result))
(push (funcall fn i) result)))

(defun map-> (fn start test-fn succ-fn)
(do ((i start (funcall succ-fn i))
(result nil))
((funcall test-fn i) (nreverse result))
(push (funcall fn i) result)))

(defun mappend (fn &rest lsts)
(apply #'append (apply #'mapcar fn lsts)))

(defun mapcars (fn &rest lsts)
(let ((result nil))
(dolist (lst lsts)
(dolist (obj lst)
(push (funcall fn obj) result)))
(nreverse result)))

(defun rmapcar (fn &rest args)
(if (some #'atom args)
(apply fn args)
(apply #'mapcar
#'(lambda (&rest args)
(apply #'rmapcar fn args))
args)))

圖4.6： 映射函數(shù)

(mapcars #'sqrt list1 list2)

而且還避免了多余的cons。

圖4.6 中最后一個函數(shù)是適用于樹的mapcar 版本。它的名字rmapcar 是"recursive mapcar" 的縮寫， 并且所有mapcar 在扁平列表上能完成的功能，它都可以在樹上做到：

> (rmapcar #'princ '(1 2 (3 4 (5) 6) 7 (8 9)))
123456789
(1 2 (3 4 (5) 6) 7 (8 9))

和 mapcar 一樣，它可以接受一個以上的列表作為參數(shù)：

> (rmapcar #'+ '(1 (2 (3) 4)) '(10 (20 (30) 40)))
(11 (22 (33) 44))

后面出現(xiàn)的某些函數(shù)會調(diào)用rmapcar ，包括第225 頁的rep_ 。

在某種程度上，傳統(tǒng)的列表映射函數(shù)可能會被 ???2 中新引入的串行宏（seriesmacro） 所取代。例如，

(mapa-b #'fn a b c)

可以被改寫成：

(collect (map-fn t #'fn (scan-range :from a :upto b :by c)))

盡管如此，映射函數(shù)仍然是有市場的。在某些場合，采用映射函數(shù)可能會更清晰優(yōu)雅。一些map-> 表達(dá)的

結(jié)構(gòu)，改用series 來表達(dá)也許就不那么方便。最后，映射函數(shù)和其他函數(shù)一樣，也可以作為參數(shù)傳遞。

4.6 I/O

(defun readlist (&rest args)
(values (read-from-string
(concatenate 'string "("
(apply #'read-line args)
")"))))
(defun prompt (&rest args)
(apply #'format *query-io* args)
(read *query-io*))

(defun break-loop (fn quit &rest args)
(format *query-io* "Entering break-loop.'~%")
(loop
(let ((in (apply #'prompt args)))
(if (funcall quit in)
(return)
(format *query-io* "~A~%" (funcall fn in))))))

圖4.7： I/O 函數(shù)

圖4.7 給出了三個I/O 實用工具的例子。不同程序?qū)@類實用工具的需要各有不同。圖4.7 中的不過是些

例子。要是你希望用戶在輸入表達(dá)式時可以略去括號，那么可以用第一個函數(shù)。它讀入一行并以列表形式

返回：

> (readlist)
Call me "Ed"
(CALL ME "Ed")

函數(shù)定義中調(diào)用values 是為了只得到一個返回值（read-from-string 本身會返回第二個值，但這個值在這種情況下沒有意義）。

函數(shù)prompt 把打印問題和讀取答案結(jié)合了起來。它帶有跟format 函數(shù)類似的參數(shù)表，除了一開始的流參數(shù)。

> (prompt "Enter a number between ~A and ~A.~%>> " 1 10)
Enter a number between 1 and 10.
>> 3
3

最后，如果你希望模擬 Lisp 的toplevel 環(huán)境，那么break-loop 可以幫上忙。它接受兩個函數(shù)和一個&rest

參數(shù)，后者一次又一次地作為參數(shù)傳給prompt 。當(dāng)輸入使得第二個函數(shù)返回邏輯假的時候，那第一個參數(shù)

將會應(yīng)用在這個輸入上。所以我們可以像這樣來模仿真正的 Lisp toplevel 環(huán)境：

譯者注：原書的寫法是 （collect （#Mfn （scan-range ：from a ：upto b ：by c））），兩種寫法是等價的。CLTL提到：e # macro

charactersyntax #M makesiteasytospecifyusesof map-fn wheretypeis t andthefunctionisanamedfunction。enotation （#Mfunction

...）isanabbreviationfor （map-fn t #'function ...）。由于目前series 宏的標(biāo)準(zhǔn)實現(xiàn)cl-series 包在加載以后的缺省情況下并不定義#M 這個宏，所以這里采用了通俗寫法。

> (break-loop #'eval #'(lambda (x) (eq x :q)) ">> ")
Enter break-loop.
>> (+ 2 3)
5
>> :q
:Q

隨便提一下，這也是Common Lisp 廠商主張對運行期進(jìn)行授權(quán)的原因。如果能在運行期調(diào)用eval ，那么任何 Lisp 程序都可以包含 Lisp 環(huán)境。

4.7 符號和字符串

(defun mkstr (&rest args)
(with-output-to-string (s)
(dolist (a args) (princ a s))))

(defun symb (&rest args)
(values (intern (apply #'mkstr args))))

(defun reread (&rest args)
(values (read-from-string (apply #'mkstr args))))

(defun explode (sym)
(map 'list #'(lambda (c)
(intern (make-string 1
:initial-element c)))
(symbol-name sym)))

圖4.8： 操作符號和字符串的函數(shù)

符號和字符串兩者緊密相關(guān)。通過打印和讀取函數(shù)，我們可以在這兩種表示方式之間相互轉(zhuǎn)換。圖4.8 舉

了幾個實用工具例子，它們都是用來做這種轉(zhuǎn)換工作的。其中，第一個是mkstr ，它接受任意數(shù)量的參數(shù)，

并將它們的打印形式連起來，形成一個字符串：

> (mkstr pi " pieces of " 'pi)
"3.141592653589793 pieces of PI"

我們在mkstr 的基礎(chǔ)上編寫了symb ，大多數(shù)情況下，它被用來構(gòu)造符號。它接受一個或多個參數(shù)，并返回

一個符號（若需要的話，則會新建一個），使其打印名稱等于所有參數(shù)連接在一起的字符串。它可以接受任

何支持可打印表示的對象作為參數(shù)： 符號、字符串、數(shù)字，甚至列表。

> (symb 'ar "Madi" #\L #\L 0)
|ARMadiLL0|

symb 首先調(diào)用mkstr ，把所有參數(shù)連成一個字符串，然后把這個字符串發(fā)給intern。這個函數(shù)是 Lisp 傳統(tǒng)上的符號構(gòu)造器： 它接受一個字符串，然后，如果無法找到一個打印輸出和該字符串相同的符號，就創(chuàng)建一個滿足此條件的新符號。

任何字符串都可以作為符號的打印名稱，甚至是含有小寫字母或者類似括號這樣的宏字符的字符串也不例

外。當(dāng)符號名稱含有這些奇怪的字符時，它將被原樣打印在兩條豎線中間。在源代碼中，這樣的符號應(yīng)該被放在兩條豎線之間，否則就必須用反斜線轉(zhuǎn)義：

> (let ((s (symb '(a b))))
(and (eq s '|(A B)|) (eq s '\(A\ B\))))
T

下一個函數(shù) reread ，是 symb 的通用化版本。它接受一系列對象，然后打印并重讀它們。它可以像symb 那

樣返回符號，但也可以返回其他任何 read 能返回的東西。其間，讀取宏將會被調(diào)用，而不是被當(dāng)成函數(shù)的

一部分，這樣 a：b 將被認(rèn)作包（package） a 中的符號b ，而不是當(dāng)前包中的符號|a：b|。 這個更通用的函數(shù)同時也更加挑剔： 如果reread 的參數(shù)不合 Lisp 語法，它將生成一個錯誤。

圖4.8 中的最后一個函數(shù)在幾種早期方言是預(yù)定義了的： explode 接受一個符號，然后返回一個由該符號名稱里的字符所組成的列表。

> (explode 'bomb)
(B O M B)

毫無疑問，Common Lisp 不會包含這個函數(shù)。如果你發(fā)現(xiàn)自己需要處理符號本身，那你很可能在做某件低效率的事情。盡管如此，在開發(fā)原型的時候，這類實用工具還是有用武之地的，如果是產(chǎn)品級軟件，就另當(dāng)別論了。

4.8 緊湊性

如果你在代碼里用了大量實用工具，有的讀者可能會抱怨這種程序晦澀難懂。那些還沒能自如使用 Lisp 的人只能習(xí)慣閱讀原始的 Lisp 。事實上，他們可能一直就無法認(rèn)同可擴(kuò)展語言的理念。當(dāng)讀到一個嚴(yán)重依賴實用工具的程序時，在他們看來，作者可能是完全出于怪癖而決定用某種私人語言來寫程序。

會有人提出，所有這些新操作符讓程序更難讀了。他認(rèn)為必須首先理解所有的這些新操作符，才能讀懂程序。要想知道為什么這類說法是錯誤的，不妨想想第27 頁的那個例子，在那里我們想要找到最近的書店。如果用 find2 來寫程序，有人可能會抱怨說，在他能夠讀懂這個程序之前，必須先理解這個實用工具的定義。好吧，假設(shè)你沒有用 find2。那么現(xiàn)在可以不用先理解 find2 了，但是讀者將不得不去理解 find-books 的定義，該函數(shù)相當(dāng)于把 find2 和查找書店的特定任務(wù)混在了一起。理解 find2 并不比理解 find-books 更難。另一方面，在這里我們只用了一次這個新的實用工具。實用工具意味著重復(fù)使用。在實際的程序里，它意味著在下列兩種情況中做出選擇，理解 find2 ，或者不得不去理解三到四種特定的搜索例程。顯然前者更容易些。

所以，閱讀自底向上的程序確實需要理解作者定義的所有新操作符。但它的工作量幾乎總是比理解在沒有這些操作符的情況下的所有代碼要少很多。

如果人們抱怨說使用實用工具使得你的代碼難于閱讀了，他們很可能根本沒有意識到，如果你不使用這些實用工具的話代碼看起來將是什么樣子。自底向上程序設(shè)計讓本來規(guī)模很大的程序看起來短小簡單。給人的感覺就是，這程序并沒有做很多事，所以應(yīng)該很好懂。當(dāng)缺乏經(jīng)驗的讀者們更仔細(xì)地閱讀程序，結(jié)果發(fā)現(xiàn)事情并沒有想象的那么簡單，他們就會灰心喪氣。

我們在其他領(lǐng)域觀察到了相同的現(xiàn)象： 設(shè)計合理的機(jī)器可能部件數(shù)量更少，但是看起來會感覺更復(fù)雜，因為這些部件被安置在了更小的空間里。自底向上的程序有種感官上的緊密性。閱讀這種程序可能需要花一些力氣，但如果不是這樣寫的話，你會需要花更多的精力來讀懂它們。

有一種情況下，你應(yīng)該有意地避免使用實用工具，即： 如果你需要寫一個小程序，它將獨立于其余部分的代碼發(fā)布。一個實用工具通常至少要被使用兩到三次才值得引入，但在小程序里， 如果一個實用工具用得太少的話，可能就沒有必要包含它了。

有關(guān)包的介紹，可以參見第 25 章后面的附錄。