第三章 函數式編程

前一章解釋了 Lisp 和 Lisp 程序兩者是如何由單一的原材料函數，建造起來的。和任何建筑材料一樣，它的特質既影響了我們所建造事物的種類，也影響著我們建造它們的方式。

本章描述 Lisp 世界里較常用的一類編程方法。這些方法十分精妙，讓我們能夠嘗試編寫更有挑戰(zhàn)的程序。

下一章將介紹一種尤其重要的編程方法，是 Lisp 讓我們得以運用這種方法：即通過進化的方式開發(fā)程序，而非遵循先計劃再實現的老辦法。

3.1 函數式設計

事物的特征會受其原材料的影響。例如，一座木結構建筑和石結構建筑看起來就會感覺不一樣。甚至當離得很遠，看不清原材料究竟是木頭還是石頭，你也可以大體說出它是用什么造的。與之相似，Lisp 函數的特征也影響著 Lisp 程序的結構。

函數式編程意味著利用返回值而不是副作用來寫程序。副作用包括破壞性修改對象(例如通過rplaca) 以及變量賦值(例如通過 setq)。如果副作用很少并且局部化，程序就會容易閱讀，測試和調試。Lisp 并非從一開始就是這種風格的，但隨著時間的推移，Lisp 和函數式編程之間的關系變得越來越密不可分。

這里有個例子，它可以說明函數式編程和你在用其他語言編程時的做法到底有什么不一樣。假設由于某種原因我們想把列表里的元素順序顛倒一下。這次的函數不再顛倒參數列表中的元素順序，而是接受一個列表作為參數，返回列表中的元素與之相同但是排列次序相反。

圖3.1 中的函數能對列表求逆。它把列表看作數組，按位置取反；其返回值是無意義的：

 > (setq lst '(a b c))
 (A B C)
 > (bad-reverse lst)
 NIL
 > lst
 (C B A)

函數如其名，bad-reverse 與好的 Lisp 風格相去甚遠。更糟糕的是，它還有其它丑陋之處：

因為其正常工作有賴于副作用，所以它使調用者離函數式編程的理想漸行漸遠。

 (defun bad-reverse (lst)
 (let* ((len (length lst))
        (ilimit (truncate (/ len 2))))
   (do ((i 0 (1+ i))
        (j (1- len) (1- j)))
     ((>= i ilimit))
    (rotatef (nth i lst) (nth j lst)))))

圖3.1： 一個對列表求逆的函數

盡管是個反派角色， bad-reverse 仍有其可取之處：

它展示了 Common Lisp 交換兩個值的習慣用法。

rotatef 宏可以輪轉任何普通變量的值。所謂普通變量是指那些可以作為setf 第一個參數的變量。當它只應用于兩個參數時，效果就是交換它們。

與之相對，圖 3.2 中的函數能返回順序相反的列表。通過使用 good-reverse ，我們得到的返回值是顛倒順序后的列表，而原始列表原封不動：

   ;; 代碼 3.2： 一個返回相反順序列表的函數
   > (setq lst '(a b c)
   (A B C)
   > (good-reverse lst)
   (C B A)
   > lst
   (A B C)

   (defun good-reverse (lst)
     (labels ((rev (lst acc)
      (if (null lst)
          acc
          (rev (cdr lst) (cons (car lst) acc)))))
             (rev lst nil)))

過去常認為可以根據外貌來判斷一個人的性格。不管這個說法對于人來說是否靈驗，但是對于 Lisp 來說， 這一般是可行的。函數式程序有著和命令式程序不同的外形。函數式程序的結構完全是由表達式里參數的組合表現出來的，并且由于參數是縮進的，函數式代碼看起來在縮進方面顯得更為靈動。函數式代碼看起來如同紙面上的行云流水； 命令式代碼則看起來堅固駑鈍，Basic 語言就是一例。

即使遠遠的看上去，從bad- 和good-reverse 兩個函數的形狀也能分清孰優(yōu)孰劣。另外，good-reverse 不僅短些，也更加高效： 而不是因為 Common Lisp 已經有了內置的 reverse ，所以我們可以不用自己實現它。不過還是有必要簡單了解一下這個函數，因為它經常能暴露出一些函數式編程中的錯誤觀念。和 good-reverse 一樣，內置的 reverse 通過返回值工作，而沒有修改它的參數。但學習 Lisp 的人們可能會誤以為它像 bad-reverse 那樣依賴于 副作用。如果這些學習者想在程序里的某個地方顛倒一個列表的順序，他們可能會寫

 (reverse lst)

結果還很奇怪為什么函數調用沒有效果。事實上，如果我們希望利用那種函數提供的效果，就必須在調用代碼里自己處理。也就是需要把程序改成這樣

  (setq lst (reverse lst))

調用 reverse 這類操作符的本意就是取返回值，而非利用其副作用。你自己的程序也應該用這種風格編寫， 不僅因為它固有的好處，而是因為，如果你不這樣寫，就等于在跟語言過不去。

在比較 bad-reverse 和 good-reverse 時我們還忽略了一點，那就是 bad-reverse 里沒有 cons 。它對原始列表進行操作，但卻不構造新的列表。這樣是比較危險的，因為有可能在程序的其他地方還會用到原始列表，但為了效率，有時可能必須這樣做。為滿足這種需要，Common Lisp 還提供了一個稱為 nreverse 的求逆函數的破壞性版本。

所謂破壞性函數，是指那類能改變傳給它的參數的函數。即便如此，破壞性函數通常也通過取返回值的方式工作：你必須假定 nreverse 將會回收利用你作為參數傳給它的列表，但不能認為它幫你在原地把原來的列表掉了個。和以前一樣，逆序后的列表只能通過返回值拿到。你仍然不能把

  (nreverse lst)

寫在函數中間，然后假定從那以后lst 的順序就是相反的了。在大多數實現里可以看到下面的現象：

  > (setq lst '(a b c))
  (A B C)

第 164 頁有一個很典型的例子。

  > (nreverse lst)
  (C B A)
  > lst
  (A)

要想真正求逆一個列表，你就不得不把 lst 賦給返回值，這和使用原來的 reverse 是一樣的。

如果我們知道某個函數有破壞性，這并不是說：調用它就是為了利用其副作用。危險之處在于，有的破壞性函數給人留下了破壞性的印象。例如：

  (nconc x y)

幾乎總是和：

  (setq x (nconc x y))

效果相同。如果你寫的代碼依賴于前一個用法，有時它可以正常工作。然而當 x 為 nil 時，結果就會出人意料。

只有少數 Lisp 操作符的本意就是為了副作用。一般而言，內置操作符本來是為了調用后取返回值的。不要被sort，remove 或者 substitute 這樣的名字所誤導。如果你需要副作用，那就對返回值使用setq。

這個規(guī)則主張某些副作用其實是難免的。堅持函數式的編程思想并沒有提倡杜絕副作用。而是說除非必要最好不要有。

養(yǎng)成這個習慣可能要花些時間。不妨開始時先盡量少用下列的操作符：

  set setq setf psetf psetq incf decf push
  pop pushnew rplaca rplacd rotatef shiftf
  remf remprop remhash

還包括 let* ，命令式程序經常藏匿其中。在這里要求有節(jié)制地使用這些操作符的目的只是希望倡導良好的Lisp 風格，而不是想制定清規(guī)戒律。然而，僅此一項就可讓你受益匪淺了。

在其他語言里，導致副作用的最普遍原因就是讓一個函數返回多個值的需求。如果函數只能返回一個值，那它就不得不通過改變參數來 "返回" 其余的值。幸運的是，在 Common Lisp 里不必這樣做，因為任何函數都可以返回多值。

舉例來說，內置函數 truncate 返回兩個值，被截斷的整數，以及原來數字的小數部分。在典型的實現中，在最外層調用這個函數時兩個值都會返回：

  > (truncate 26.21875)
  26
  0.21875

當調用方只需要一個值時，被使用的就是第一個值：

  > (= (truncate 26.21875) 26)
  T

通過使用 multiple-value-bind ，調用方代碼可以捕捉到兩個值。該操作符接受一個變量列表、一個調用，以及一段程序體。變量將被綁定到函數調用的對應返回值，而這段程序體會依照綁定后的變量求值：

  > (multiple-value-bind (int frac) (truncate 26.21875)
  (list int frac))
  (26 0.21875)

最后，為了返回多值，我們使用 values 操作符：

  > (defun powers (x)
        (values x (sqrt x) (expt x 2)))
  POWERS
  > (multiple-value-bind (base root square) (powers 4)
         (list base root square))
             (4 2.0 16)

一般來說，函數式編程不失為上策。對于 Lisp 來說尤其如此，因為 Lisp 在演化過程中已經支持了這種編程方式。諸如 reverse 和 nreverse 這樣的內置操作符的本意就是以這種方式被使用的。其他操作符，例如 values 和 multiple-value-bind，是為了便于進行函數式編程而專門提供的。

3.2 內外顛倒的命令式

函數式程序代碼的用意和那些更常見的方法，即命令式程序相比可能顯得更加明確一些。函數式程序告訴你它想要什么；而命令式程序告訴你它要做什么。函數式程序說 "返回一個由 a 和 x 的第一個元素的平方所組成的列表："

  (defun fun (x)
  (list 'a (expt (car x) 2)))

而命令式程序則會說 "取得 x 的第一個元素，把它平方，然后返回由 a 及其平方組成的列表"：

  (defun imp (x)
    (let (y sqr)
    (setq y (car x))
     (setq sqr (expt y 2))
     (list 'a sqr)))

Lisp 程序員有幸可以同時用這兩種方式來寫程序。某些語言只適合于命令式編程 尤其是 Basic，以及大多數機器語言。事實上，imp 的定義和多數 Lisp 編譯器從 fun 生成的機器語言代碼在形式上很相似。

既然編譯器能為你做，為什么還要自己寫這樣的代碼呢？對于許多程序員來說，他們甚至從沒想過這個問題。語言給我們的思想打上烙?。阂恍┝晳T于命令式語言編程的人或許已經開始用命令式的術語思考問題，而且會覺得寫命令式程序比寫函數式程序更容易。如果有一種語言可以助你一臂之力，這種思維定勢是值得克服的。

對于其他語言的同行來說，剛開始使用 Lisp 可能像初次踏入溜冰場那樣。事實上在冰上比在干地面上更容易行走 如果使用溜冰鞋的話。然后你對這項運動的看法就會徹底改觀。

溜冰鞋對于冰的意義，和函數式編程對 Lisp 的意義是一樣的。這兩樣東西在一起讓你更優(yōu)雅地移動，事半功倍。但如果你已經習慣于另一種行走模式，那么開始的時候你就無法體會到這一點。把 Lisp 作為第二語言學習的一個障礙就是學會如何用函數式的風格來編程。

幸運的是，有一種把命令式程序轉換成函數式程序的訣竅。開始時你可以把這一訣竅用到寫好的代碼里。

不久以后你就可以預想到這個過程，一邊寫代碼，一邊做轉換了。而在這之后一段時間，你就有能力從一開始就用函數式的思想構思你的程序。

這個訣竅就是認識到命令式程序其實是一個從里到外翻過來的函數式程序。要想找出藏在命令式程序中的函數式程序，也只要把它從外到里翻一下。讓我們在 imp 上實踐一下這個技術。

我們首先注意到的是初始 let 里 y 和 sqr 的創(chuàng)建。這預示著接下來會出問題。就像運行期的 eval ，需要未初始化變量的情況很罕見，它們因而被看作程序染病的癥狀。這些變量就像插在程序上，用來固定的圖釘，它們被用來防止程序自己卷回到原形。

不過我們暫時先不考慮它們，直接看函數的結尾。命令式程序里最后發(fā)生的事情，也就是函數式程序在最外層發(fā)生的事情。所以第一步是抓住最后對 list 的調用，然后把程序的其余部分塞進去就好像把一件襯衫從里到外翻過來。我們繼續(xù)重復做相同的轉換，就好像我們先翻襯衫的袖子，然后再翻袖口那樣。

從結尾處開始，我們將 sqr 替換成 (expt y 2)，得到：

  (list 'a (expt y 2))

然后我們將y 替換成 (car x)：

  (list 'a (expt (car x) 2))

現在我們可以把其余代碼扔掉了，因為之前已經把所有內容都填到了最后一個表達式里。在這個過程中我們擺脫了對變量 y 和 sqr 的依賴，因而也得以把 let 一起扔進垃圾堆。

最終的結果比開始的時候要短小，而且更好懂。在原先的代碼里，我們面對最終的表達式 (list 'a sqr)， 卻無法一眼看出 sqr 的值的出處?，F在，返回值的來歷則像交通指示圖一樣一覽無余。

本章的這個例子很短，但這里的技術是可以推廣的。事實上，它對于大型函數應該更有價值。即使存在一些有副作用的函數，也可以把其中沒有副作用的那部分清理得干凈一些。

3.3 函數式接口

某些副作用比其他的更糟糕。例如，盡管下面的函數調用了 nconc

  (defun qualify (expr)
  (nconc (copy-list expr) (list 'maybe)))

但它沒有破壞引用透明。如果你每次都傳給它一個確定的參數，那它的返回值將總是相同(equal) 的。

從調用者的角度來看，qualify 就和純函數型代碼一樣。但我們不能對bad-reverse (第19頁) 下同樣的評語，這個函數事實上修改了它的參數。

如果不把所有副作用的有害程度都劃上等號，而是有方法能把這些情況分出個高下，那樣將會對我們有很大的幫助?？梢苑钦降卣f，如果一個函數修改的是其他函數都不擁有的東西，那么它就是無害的。例如， qualify 里的 nconc 就是無害的，因為作為第一個參數的列表是新生成的。它不屬于任何其他函數。

通常，在我們提到擁有者關系時，不能說變量的擁有者是某某函數，而應該說其擁有者是函數的某個調用。

盡管這里并沒有其他函數擁有變量 x ：

  (let ((x 0))
  (defun total (y)
  (incf x y)))

但一次調用的效果會在接下來的調用中看到。所以規(guī)則應當是：一個給定的調用 (invocation) 可以安全地修改它唯一擁有的東西。

究竟誰是參數和返回值的擁有者 依照Lisp 的習慣，是函數的調用擁有那些作為返回值得到的對象，但它并不擁有那些作為參數傳給它的對象。凡是修改參數的函數都應該打上"破壞性" 的標簽，以示區(qū)別，但如果函數修改的只是返回給它們的對象，那我們沒有準備什么特別的稱號給這些函數。

譬如，下面的函數就聽從了這個提議：

  (defun ok (x)
  (nconc (list 'a x) (list 'c)))

但它調用的nconc 卻置若罔聞。由于nconc 拼出來的列表總是重新生成的，而沒有使用原來傳給ok 作為參數的那個列表，所以ok 總的來說是ok 的。

如果稍微改一點兒，例如：

    (defun not-ok (x)
    (nconc (list 'a) x (list 'c)))

那么對nconc 的調用就會修改傳給not-ok 的參數了。

許多Lisp 程序沒有遵守這個慣例，至少在局部上是這樣。盡管如此，正如我們從 ok 那里看到的，局部的違背并不會讓主調函數變質。而且那些與上述情況相符的函數仍會保留很多純函數式代碼的優(yōu)點。

要想寫出真正意義上的函數式代碼，還要再加個條件。函數不能和不遵守這些規(guī)則的代碼共享對象。例如，盡管這個函數沒有副作用：

    (defun anything (x)
    (+ x *anything*))

但它的返回值依賴于全局變量?anything。因此，如果任何其他函數可以改變這個變量的值，那么anything 就可能返回任意值。

關于引用透明的定義見135頁。

要是把代碼寫成讓每次調用都只修改它自己擁有的東西的話，那這樣的代碼就基本上就可以和純函數式代碼媲美了。從外界看來，一個滿足上述所有條件的函數至少會擁有有函數式的接口：如果用同一參數調用它兩次，你應當會得到同樣的結果。正如下一章所展示的那樣，這也是自底向上程序設計最重要的組成部分。

破壞性的操作符還有個問題，就是它和全局變量一樣會破壞程序的局部性。當你寫函數式代碼時，可以集中精力：只要考慮調用正在編寫的函數的調用方，或者被調用方就行了。要是你想要破壞性地修改某些數據，這個好處就不復存在了。你修改的數據可能在任何一個地方用到。

上面的條件不能保證你能得到和純粹的函數式代碼一樣的局部性，盡管它們確實在某種程度上有所改進。

例如，假設f 調用了g ，如下：

    (defun f (x)
    (let ((val (g x)))
     ; safe to modify val here?
    ))

在f 里把某些東西nconc 到val 上面安全嗎 如果g 是identity 的話就不安全：這樣我們就修改了某些原本作為參數傳給 f 本身的東西。

所以，就算要修改那些按照這個規(guī)定寫就的程序，還是不得不看看f 之外的東西。雖然要多操心一些，但也用不著看得太多：現在我們不用復查程序的所有代碼，只消考慮從f 開始的那棵子樹就行了。

推論之一是函數不該返回任何不能安全修改的東西。如此說來，就應當避免寫那些返回包含引用對象的函數。如果我們這樣定義exclaim ，讓它的返回值包含一個引用列表，

    (defun exclaim (expression)
    (append expression '(oh my)))

那么任何后續(xù)的對返回值的破壞性修改

    > (exclaim '(lions and tigers and bears))
    (LIONS AND TIGERS AND BEARS OH MY)
    > (nconc * '(goodness))
    (LIONS AND TIGERS AND BEARS OH MY GOODNESS)

將替換函數里的列表：

    > (exclaim '(fixnums and bignums and floats))
    (FIXNUMS AND BIGNUMS AND FLOATS OH MY GOODNESS)

為了避免exclaim 的這個問題，它應該寫成：

    (defun exclaim (expression)
    (append expression (list 'oh 'my)))

雖說函數不應返回引用列表，但是這個常理也有例外，即生成宏展開的函數。宏展開器可以安全地在它們的展開式里包含引用列表，只要這些展開式是直接送到編譯器那里的。

其他時候，還是應該審慎地對待引用列表。除了上面的例外情況，如果發(fā)現用到了引用列表，很多情況，這些代碼是完全可以用類似in (103頁) 這樣的宏來完成的。

3.4 交互式編程

前一章說明了函數式的編程風格是一種組織程序的好辦法。但它的好處還不止于此。Lisp 程序員并非完全是從美感出發(fā)才采納函數式風格的。他們采用這種風格是因為它讓工作更輕松。在 Lisp 的動態(tài)環(huán)境里， 函數式程序能以非同尋常的速度寫就，與此同時，寫出的程序也非同尋常的可靠。

在 Lisp 里調試程序相對簡單。很多信息在運行期是可見的，可以幫助追查錯誤的根源。但更重要的是你

可以輕易地測試程序。你不需要編譯一個程序然后一次性測試所有東西。你可以在toplevel 循環(huán)里通過逐個地調用每個函數來測試它們。

增量測試非常有用，為了更好地利用它，Lisp 風格也隨之改進。用函數式風格寫出的程序可以逐個函數地

理解它，從讀者的觀點來看，這是它的主要優(yōu)點。此外，函數式風格也極其適合增量測試：以這種風格寫出的程序可以逐個函數地進行測試。當一個函數既不檢查也不改變外部狀態(tài)時，任何bug 都會立即現形。這樣，函數影響外面世界的唯一渠道是它的返回值。只要返回值是你期望的，你就完全可以信任返回它的代碼。

事實上有經驗的Lisp 程序員會盡量讓他們的程序易于測試：

1. 他們試圖把副作用分離到個別函數里，以便程序中更多的部分可以寫成純函數式風格。

2. 如果一個函數必須產生副作用，他們至少會想辦法給它設計一個函數式的接口。

3. 他們給每個函數賦予一個單一的，定義良好的功能。

一旦函數按照這種辦法寫成，程序員們就可以用一組有代表性的情況對它測試，測試好了，就使用另一組情況測試。如果每一塊磚都各司其職，那么圍墻就會屹立不倒。

在Lisp 里，一樣可以更好地設計圍墻。先假想一下，如果談話的時候，和對方距離很遠，聲音的延遲甚至有一分鐘，會有什么樣的一番感受。要是換成和隔壁房間的人說話，會有怎樣的改觀。這樣，將進行的對話不僅僅是速度比原來快，而是一個完全不同的對話。在Lisp 中，開發(fā)軟件就像是面對面的交流。你可以邊寫代碼邊做測試。和對話相似，即時的回應對于開發(fā)來說一樣有戲劇化的效果。你不只是把原先的程序寫得更快，而是會寫出另一種程序。

這是什么道理 當測試更便捷時，你就可以更頻繁地進行測試。對于Lisp，和其他語言一樣，開發(fā)是由編碼和測試構成的循環(huán)往復的周期性過程。但在Lisp 的周期更短：單個函數，甚至函數的一部分都可以成為一個開發(fā)周期。并且如果一邊寫代碼一邊測試的話，當錯誤發(fā)生時你就知道該檢查哪里：應該看看最后寫的那部分。正如聽起來那樣簡單，這一原則極大地提高了自底向上編程的可行性。它帶來了額外的信賴感， 使得Lisp 程序員至少在一定程度上從舊式的計劃–實現的軟件開發(fā)風格中解脫了出來。

第 1.1 節(jié)強調了自底向上的設計是一個進化的過程。在這個過程中，你在寫程序的同時也就是在構造一門語言。這一方法只有當你信賴底層代碼時才可行。如果你真的想把這一層作為語言使用，你就必須假設， 如同使用其他語言時那樣，任何遇到的bug 都是你程序里的bug，而不是語言本身的。

難道你的新抽象有能力承擔這一重任，同時還能按照新的需求隨機應變？沒錯，在Lisp 里你可以兩不誤。

當以函數式風格編寫程序，并且進行增量測試時，你可以得到隨心所欲的靈活性，加上人們認為只有仔細計劃才能確保的可靠性。