Why Functional Programming Matters 函數(shù)式程序設(shè)計為什么至關(guān)重要
作者： John Hughes 原文地址：http://wiht.link/functional-prog

此論文作于1984年，作為查麥茲大學(xué)的備忘錄流傳了多年居触，經(jīng)過小幅度修訂的版本出現(xiàn)于1989年與1990年，即［Hug89］與［Hug90］尸疆。此版本基于原查麥茲大學(xué)備忘錄的nroff源碼臼膏，為LaTeX做了改動,使其更接近于印刷版本并糾正了少許錯誤硼被。

本文由CloudiDust在 http://blog.csdn.net/ddwn/article/details/984390 最初翻譯，并由BYVoid根據(jù)原文重新校對渗磅、整理和排版嚷硫。

摘要

軟件正在變得越來越復(fù)雜，因此良好的軟件構(gòu)架也越來越重要始鱼。結(jié)構(gòu)良好的軟件易于編寫仔掸，易于除錯，同時提供可復(fù)用組件庫以降低未來開發(fā)的成本医清。傳統(tǒng)型語言在程序模塊化方面具有理念上的局限性起暮，而函數(shù)式語言超越了局限。在本文中我們指出会烙，函數(shù)式語言的兩大特性鞋怀，高階函數(shù)與惰性求值，能夠極大地促進模塊化持搜。作為例證密似，我們處理了列表和樹，編寫了一些數(shù)值算法葫盼，并實現(xiàn)了alpha-beta啟發(fā)式搜索（一個人工智能算法残腌，用于游戲系統(tǒng)中）。既然模塊化是程序設(shè)計成功的關(guān)鍵贫导，那么函數(shù)式語言對現(xiàn)實世界而言便極其重要了抛猫。

1.引言

本論文試圖證明，對“現(xiàn)實世界”而言孩灯，函數(shù)式程序設(shè)計是極其重要的闺金。同時，本文也試圖明確指出函數(shù)式語言的長處峰档，以幫助使用函數(shù)式語言的程序員們將這些長處發(fā)揮到極致败匹。

函數(shù)式語言之所以被如此稱呼，是因為程序完全是由函數(shù)組成的讥巡。主程序本身也是一個函數(shù)掀亩，以程序的輸入為參數(shù)，并返回其輸出欢顷。典型地槽棍，主函數(shù)通過其他函數(shù)定義，而這些函數(shù)又同樣以更多的其他函數(shù)來定義，直到最低層的語言原生函數(shù)為止炼七。這些函數(shù)與數(shù)學(xué)中的函數(shù)很相像缆巧，因此在本文中將以普通等式來定義它們。本文使用了Turner的程序語言Miranda中的表示方法豌拙，但對于之前沒有函數(shù)式語言相關(guān)知識的讀者陕悬，本文仍然是可讀的。（Miranda是Research Software Ltd.的商標(biāo)姆蘸。）

函數(shù)式程序設(shè)計的特性與優(yōu)點通扯漳總結(jié)為類似這樣：函數(shù)式程序不包含任何賦值語句芙委，因此變量一旦被賦予一個值逞敷，就不再改變。更一般地說灌侣，函數(shù)式程序不包含任何副作用：一個函數(shù)除了計算它本身的值以外推捐，不產(chǎn)生任何作用。這一特性消滅了“Bug”的一個主要來源侧啼，同時也使執(zhí)行順序不再重要——沒有副作用能夠改變一個表達式的值牛柒，故它可以在任何時刻被求值。這一特性將程序員從決定控制流的重?fù)?dān)之下拯救出來痊乾。由于表達式可以在任何時刻被求值皮壁，程序員便可以隨心所欲地使用變量的值來代替變量，反之亦然——也就是說哪审，程序是“引用透明”的蛾魄。這一自由使得函數(shù)式程序與它們傳統(tǒng)的對應(yīng)物相比，更容易數(shù)學(xué)化地控制湿滓。

這樣的“優(yōu)點”列表很不錯滴须，但如果說外行人不把它當(dāng)回事，這也并不會令人驚訝叽奥。它列出了很多內(nèi)容關(guān)于函數(shù)式程序設(shè)計“沒有”什么（它沒有賦值扔水，沒有副作用，沒有控制流）但卻沒多說它“有”什么朝氓。函數(shù)式程序員聽起來很像是中世紀(jì)的僧侶似的魔市，他們禁絕了塵世中的種種樂趣并且期望這能使自己變得高潔。對于那些更關(guān)心物質(zhì)利益的人而言赵哲，這些“優(yōu)點”并沒有多大的說服力嘹狞。

函數(shù)式程序員們爭辯說，函數(shù)式程序設(shè)計確實有巨大的物質(zhì)利益——一個函數(shù)式程序員擁有比他傳統(tǒng)型的同行高得多的生產(chǎn)力誓竿，因為函數(shù)式程序短得多磅网。但這有什么道理嗎？在這些“優(yōu)點”的基礎(chǔ)之上筷屡，唯一的很靠不住的借口就是涧偷，傳統(tǒng)的程序中有90％是賦值語句簸喂，而在函數(shù)式程序中這些全都可以省略！這真是太荒唐了燎潮，如果省略賦值語句可以帶來如此巨大的好處喻鳄，那么FORTRAN程序員們早該這樣干了二十年了。通過省略特性來使語言更加強大在邏輯上是不可能的确封，不論這種特性是多么糟糕除呵。

甚至函數(shù)式程序員都應(yīng)該對這些所謂的“優(yōu)點”表示不滿意，因為它們對于發(fā)掘函數(shù)式語言的威力毫無幫助爪喘。不可能寫出一個特別地（particularly）缺少了賦值語句或者特別地引用透明的程序颜曾。這些不是什么衡量程序質(zhì)量的尺度，因此盯緊了它們（以此證明函數(shù)式語言的強大）也不理想秉剑。

很明顯泛豪，對函數(shù)式程序設(shè)計的特性的描述是不完備的。我們必須找出一些東西來填補——它們不但要解釋函數(shù)式程序設(shè)計的威力侦鹏，更要給函數(shù)式程序員們一個明確的追求目標(biāo)诡曙。

2.與結(jié)構(gòu)化程序設(shè)計的相似性

指出函數(shù)式與結(jié)構(gòu)化程序設(shè)計之間的相似性是很有幫助的。過去略水，結(jié)構(gòu)化程序設(shè)計的特性與優(yōu)點被總結(jié)為類似這樣：結(jié)構(gòu)化程序不包含goto語句价卤；結(jié)構(gòu)化程序中的語句塊沒有多入口與多出口；結(jié)構(gòu)化程序與它們傳統(tǒng)的對應(yīng)物相比渊涝，更容易數(shù)學(xué)化地控制慎璧。這些結(jié)構(gòu)化程序設(shè)計的“優(yōu)點”與我們之前所談到的函數(shù)式程序設(shè)計的“優(yōu)點”在本質(zhì)上很相似。這些敘述本質(zhì)上都是否定式的驶赏，從而導(dǎo)致了諸如“不可或缺的goto”之類一大堆徒勞的爭論炸卑。

事后諸葛亮式地說，很明顯地煤傍，結(jié)構(gòu)化程序設(shè)計的這些特性盖文，盡管很有用，但沒有觸及問題的核心蚯姆。結(jié)構(gòu)化程序與非結(jié)構(gòu)化程序之間最重要的區(qū)別就是五续，結(jié)構(gòu)化程序是用模塊化的方法設(shè)計的。模塊化設(shè)計帶來了生產(chǎn)力的巨大提升：首先龄恋，小模塊可以很快很容易地編寫疙驾；其次，通用模塊可以被重用郭毕，使以后的程序可以更快地開發(fā)它碎；再次，程序的模塊可以被獨立測試，減少了除錯的時間扳肛。

“不使用goto”等等這一類特性傻挂，對于這一提升沒什么作用。這些特性促進了“程序設(shè)計的小改良”挖息，然而模塊化設(shè)計卻促進了“程序設(shè)計的大進化”金拒。因此，程序員在FORTRAN或匯編語言中都可以享受結(jié)構(gòu)化程序設(shè)計帶來的好處套腹，哪怕那需要一點額外的工作绪抛。

模塊化設(shè)計是成功的程序設(shè)計的關(guān)鍵，這一觀點現(xiàn)在已經(jīng)被普遍地接受了电禀，而諸如Modula-II[Wir82]幢码，Ada[oD80]以及Standard ML[MTH90]之類的程序語言都內(nèi)置了語言特性以促進模塊化。然而鞭呕，有一點非常重要蛤育，卻常常被忽略宛官。當(dāng)編寫一個模塊化程序以解決問題的時候葫松，程序員首先把這個問題分解為子問題，而后解決這些子問題并把解決方案合并底洗。程序員能夠以什么方式分解問題腋么，直接取決于他能以什么方式把解決方案粘起來。因此亥揖，為了能在觀念上提升程序員將問題模塊化的能力珊擂，必須在程序語言提供中提供各種新的黏合劑。復(fù)雜的作用域規(guī)則與對分塊編譯的支持只對文本層面的細(xì)節(jié)有幫助费变，它們沒有提供能表達新觀念的工具以分解問題摧扇。

通過與木匠行業(yè)的類比可以認(rèn)識到黏合劑的重要性。先制作椅子的各部分——坐墊挚歧，椅子腿扛稽，靠背，等等——而后用正確的方法釘起來滑负，那么制作一把椅子是很容易的在张。但這取決于將木板與插接口結(jié)合起來的能力。如果缺乏這種能力矮慕，那么制作椅子的唯一方式帮匾，就是將它從一大塊木頭里整個地切割出來，這是一項艱巨得多的任務(wù)痴鳄。這個例子同時表明了模塊化的非凡威力與擁有合適的黏合劑的重要性瘟斜。

現(xiàn)在讓我們回到函數(shù)式程序設(shè)計上來。在這篇論文余下的部分里，我們將指出螺句，函數(shù)式語言提供了兩種新的明未、非常重要的黏合劑。我們將給出許多可以使用新方法模塊化的示例程序壹蔓，它們因此變得很簡潔趟妥。這就是函數(shù)式程序設(shè)計威力的關(guān)鍵——它允許了大幅改進的模塊化設(shè)計。這也正是函數(shù)式程序員必須追求的目標(biāo)——更小佣蓉、更簡潔披摄、更通用的模塊，用我們將要描述的新黏合劑黏合起來勇凭。

3.把函數(shù)粘起來

兩種黏合劑中的第一種疚膊，使簡單的函數(shù)可以聚合起來形成復(fù)雜的函數(shù)。以一個簡單的處理問題來說明：將列表中的元素累加起來虾标。我們用下面的語句定義列表：

 listof X :: = nil | cons X (listof X)

這說明寓盗，一個元素類型為X的列表（不論X是什么），或是nil璧函，代表一個沒有元素的空列表傀蚌，或是一個X與另一個X的列表的cons。cons代表一個列表蘸吓，其首元素為X善炫，而第二個以及后續(xù)元素即是另一個X的列表的元素。此處的X可以代表任何類型——例如库继，如果X是一個Integer（整數(shù)類型）箩艺，那么這個定義就是說，一個整數(shù)列表宪萄，或者是空的艺谆，或者是一個整數(shù)與另一個整數(shù)列表的cons。依照通常的實踐拜英，我們寫列表時静汤，只是簡單地將其元素包含在方括號里，而不是將cons和nil顯式地寫出來聊记。方便起見撒妈，這是一個簡單的速記法。例如：

[] 表示 nil
[1] 表示 cons 1 nil
[1 2 3] 表示 cons 1 ( cons 2 ( cons 3 nil ))

列表中的元素可以通過一個遞歸函數(shù)sum進行累加排监。sum必須為兩類參數(shù)進行定義：一個空列表（nil）狰右，以及一個cons。由于沒有數(shù)字存在時舆床，累加結(jié)果是0棋蚌，因此我們定義：

sum nil = 0

又因為cons的累加和可以通過將列表的第一個元素加到其余元素的累加和上的方式進行計算嫁佳，所以可以定義：

sum (cons num list) = num + sum list

檢查定義可以發(fā)現(xiàn)計算sum時，只有下面用紅色粗體標(biāo)出的部分是特化的：

sum nil = 0
sum (cons num list) = num + sum list

這說明sum的計算可以通過一個通用的遞歸模式和特化的部分來模塊化谷暮。這個通用的遞歸模式習(xí)慣上被稱為“遞減”（reduce）蒿往，因此sum可以表達為：

sum = reduce add 0

方便起見，reduce傳遞了一個二元函數(shù)add湿弦。add是這樣定義的：

add x y = x + y

只要將sum的定義參數(shù)化瓤漏，我們便可以得到reduce的定義，即：

(reduce f x) nil = x(reduce f x)(cons num list) = f num ((reduce f x) list)

這里我們寫出了(reduce f x)兩邊的括號以強調(diào)它代替了sum颊埃。習(xí)慣上括號是省略的蔬充，因此 ((reduce f x) list)寫作(reduce f x list)。一個三元函數(shù)如reduce班利，當(dāng)只提供兩個參數(shù)時饥漫，將成為關(guān)于那個余下參數(shù)的一元函數(shù)。一般地罗标，對一個N元函數(shù)庸队，提供了M(< N)個參數(shù)后，該函數(shù)便成為了關(guān)于余下的N-M個參數(shù)的函數(shù)闯割。我們在下文中將遵守這一約定彻消。

用這種方式將sum模塊化之后，我們就可以通過對這部分的重用來收獲福利了纽谒。最有趣的部分就是证膨，reduce可以（直接）用于編寫一個函數(shù)來計算列表中元素的累乘積如输，而不需要更多的編程步驟：

product = reduce multiply 1

它也可以用來測試一個布爾值的列表中是否至少有一個元素為真：

anytrue = reduce or false

或者它們是否都為真：

alltrue = reduce and true

理解(reduce f a)的一種方式是鼓黔，將其看作一個將列表中的所有cons替換為f，將所有nil替換為a的函數(shù)不见。以列表[1,2,3]為例澳化，既然它表示：

cons 1 (cons 2 (cons 3 nil))

那么(reduce add 0)將其轉(zhuǎn)換為：

add 1 (add 2 (add 3 0)) = 6

而(reduce multiply 1)將其轉(zhuǎn)換為：

multiply 1 (mulitiply 2 (mulitiply 3 1)) = 6

于是，很明顯地稳吮，(reduce cons nil)將復(fù)制列表本身缎谷。既然將一個列表追加到另一個列表上的方式是將前一個列表的元素cons到后一個列表前部，我們便得到：

append a b = reduce cons b a

例如：

append [1,2] [3,4] = reduce cons [3,4] [1,2]
= (reduce cons [3,4]) (cons 1 ( cons 2 nil ))
= cons 1 ( cons 2 [3,4]))= [1,2,3,4] （將cons替換為cons灶似，將nil替換為[3,4]）

一個用于將列表中全部元素翻倍的函數(shù)可以寫作：

doubleall = reduce doubleandcons nil
doubleandcons num list = cons ( 2*num ) list

doubleandcons可以進一步模塊化列林，首先分解為：

doubleandcons = fandcons double
double n = 2*n
fandcons f elem list = cons (f elem) list

繼續(xù)分解：

fandcons f = cons . f

其中“.”（函數(shù)復(fù)合，一個標(biāo)準(zhǔn)運算符）定義為：

(f . g) h = f(g h)

為證明fandcons的定義是正確的酪惭，我們代入一些參數(shù)：

fandcons f elem= (cons . f) elem= cons (f elem)

因此

fandcons f elem list = cons (f elem) list

最終得到的版本是：

doubleall = reduce (cons . double) nil

繼續(xù)模塊化希痴，我們得到：

doubleall = map doublemap f = reduce (cons . f) nil

其中map使任意的函數(shù)作用于列表的全部元素之上。map是另一個很通用的函數(shù)春感。

我們甚至可以寫出一個函數(shù)累加矩陣中的所有元素砌创，該矩陣用列表的列表表示虏缸。這個函數(shù)是：

summatrix = sum . map sum

map sum使用函數(shù)sum分別計算所有行的元素之和，而后最左邊的sum將每一行的元素之和累加起來嫩实，從而得到整個矩陣的累加和刽辙。

這些例子應(yīng)該已經(jīng)足以使讀者確信，一點模塊化的努力可以產(chǎn)生很大的效果甲献。通過將一個簡單的函數(shù)（sum）模塊化為一個“高階函數(shù)”與一些簡單參數(shù)的聚合宰缤，我們得到了一個部件（reduce），它可以用于編寫與列表有關(guān)的許多函數(shù)晃洒，而又不再需要（更多的）編程努力撵溃。不止是對有關(guān)列表的函數(shù)可以這么干，舉另外一個例子锥累，考慮數(shù)據(jù)類型“有序標(biāo)記樹”缘挑，其定義是：

treeof X ::= node X (listof (treeof X))

這個定義表明，一棵X的樹桶略，由一個標(biāo)記類型為X的結(jié)點（node）语淘，以及一個子樹列表組成，而這些子樹也是X的樹际歼。例如惶翻，樹：

      1 o
       /\
      /  \ 
     /    \
   2 o    o 3 
           | 
           |
           |
          o 4

可以被表示成：

node 1(cons 
  (node 2 nil) 
  (cons (node 3 
    (cons (node 4 nil) nil) 
  )
nil))

我們不再給出一個函數(shù)例子并將它抽象為高階函數(shù)，取而代之的是鹅心，直接給出一個類似于reduce的函數(shù)redtree吕粗。回憶一下旭愧，reduce有兩個參數(shù)颅筋，一個用于取代cons，另一個用于取代nil输枯。既然樹由node议泵，cons和nil組成，那么redtree必須有三個參數(shù)——用于分別取代上述三者桃熄。由于樹和列表不是同一種類型先口，我們得定義兩個函數(shù)分別處理它們。因此我們定義：

redtree f g a (node label subtrees) = f label (redtree' f g a subtrees )
redtree' f g a (cons subtree rest) = g (redtree f g a subtree) (redtree' f g a rest)
redtree' f g a nil = a

［這相當(dāng)于f取代node瞳收，g取代cons碉京，a取代nil。］

很多有趣的函數(shù)都可以通過把redtree和其他函數(shù)粘起來的方法來定義螟深。例如谐宙，要把一棵數(shù)字樹上的所有標(biāo)記累加起來，可以使用：

sumtree = redtree add add 0

以我們剛才表述的那棵樹為例血崭，sumtree展開成：

add 1
(add (add 2 0)
(add (add 3
(add (add 4 0) 0))
0))
= 10

要生成一個包含樹中全部標(biāo)記的列表卧惜，可以用：

labels = redtree cons append nil

仍然是那個例子厘灼，得到：

cons 1
(append (cons 2 nil)
(append (cons 3
(append (cons 4 nil) nil))
nil))
= [1,2,3,4]

最后，可以定義一個類似于map的函數(shù)咽瓷，此函數(shù)使函數(shù)f作用于樹中的全部標(biāo)記上：

maptree f = redtree (node . f) cons nil

以上這些操作之所以可行设凹，是因為函數(shù)式語言允許將傳統(tǒng)型語言中不可分解的函數(shù)表達為一些部件的聚合，也就是一個泛化的高階函數(shù)與一些特化函數(shù)的聚合茅姜。這樣的高階函數(shù)一旦定義闪朱，便使得很多操作都可以很容易地編寫出來。不論何時钻洒，只要一個新的數(shù)據(jù)類型被定義奋姿，就應(yīng)當(dāng)同時定義用于處理這種數(shù)據(jù)的高階函數(shù)。這樣就簡化了對數(shù)據(jù)類型的處理素标，同時也將與它的表示細(xì)節(jié)相關(guān)的知識局部化了称诗。與函數(shù)式語言最相像的傳統(tǒng)程序語言是可擴展語言，只要有需求，這種程序語言就好像隨時都可以擴展出新的控制結(jié)構(gòu)一樣。

4.把程序粘起來

函數(shù)式語言提供的另一種黏合劑使得所有程序都可以粘在一起胸梆。回憶一下袜香，一個完整的函數(shù)式程序只不過是一個從輸入映射到輸出的函數(shù)。如果f和g是這樣的程序鲫惶，那么對程序(g.f)當(dāng)提供了輸入?yún)?shù)input之后蜈首，得到：

g (f input)

程序f計算自身的輸出，此輸出被用作程序g的輸入欠母。傳統(tǒng)上欢策，這是通過將f的輸出儲存在臨時文件中實現(xiàn)的。這種方法的毛病是艺蝴，臨時文件可能會占用太大的空間猬腰，以至于將程序黏合起來變得很不現(xiàn)實。函數(shù)式語言提供了一種解決方案猜敢。程序f和g嚴(yán)格地同步運行，只有當(dāng)g試圖讀取輸入時盒延，f才啟動缩擂，并且只運行足夠的時間，恰好可以提供g需要讀取的輸出數(shù)據(jù)添寺。而后f將被掛起胯盯，g將繼續(xù)執(zhí)行，直到它試圖讀取另一個輸入计露。一個額外的好處是博脑，如果g沒有讀取完f的全部輸出就終止了憎乙，那么f也將被終止。f甚至可以是一個不會自行終止的程序叉趣，它可以產(chǎn)生無窮多的輸出泞边，因為當(dāng)g運行結(jié)束時，f也將被強行終止疗杉。這就使得終止條件可以與循環(huán)體分離——一種強大的模塊化形式阵谚。

這種求值方式使得f盡可能地少運行，因此被稱為“惰性求值（lazy evaluation）”烟具。它使得將程序模塊化為一個產(chǎn)生大量可能解的生成器與一個選取恰當(dāng)解的選擇器的方案變得可行梢什。有些其他的系統(tǒng)也允許程序以這種方式運行，但只有函數(shù)式語言對每一個函數(shù)調(diào)用都一律使用惰性求值朝聋，使得程序的每個部分都可以用這種方式模塊化嗡午。惰性求值也許是函數(shù)式程序員的拿手利器中威力最大的模塊化工具。

4.1.牛頓－拉夫森求根法

我們將編寫一些數(shù)值算法以展現(xiàn)惰性求值的威力冀痕。首先翼馆，考慮用于求解平方根的牛頓－拉夫森算法。該算法從一個初始的近似值a0開始計算數(shù)N的平方根金度，為了求得更好的解应媚，它使用下述規(guī)則：

a(n+1) = (a(n) + N/a(n)) / 2

如果近似值序列趨近于某一個極限a，那么

a = (a + N/a) / 22a = a + N/aa = N/aa*a = Na = squareroot(N)

事實上猜极，這個近似值序列確實迅速地趨近于一個極限中姜。平方根算法取一個允許誤差eps為參數(shù)，當(dāng)兩個相鄰的近似值之差的絕對值小于eps時跟伏，算法便終止了丢胚。

這個算法通常被編寫為類似下面這樣：

C N IS CALLED ZN HERE SO THAT IT HAS THE RIGHT TYPE
X = A0
Y = A0 + 2.*EPS
C THE VALUE OF Y DOES NOT MATTER SO LONG AS ABS(X-Y).GT.EPS
100 IF (ABS(X-Y).LE.EPS) GOTO 200
Y = X
X = (X + ZN/X) / 2
200 CONTINUE
C THE SQUARE ROOT OF ZN IS NOW IN X

［這是一段FORTRAN的程序，C代表注釋行受扳。.LE.是“Less than or Equal to”（小于或等于）的縮寫携龟，同理.GT.是“大于”的意思。]

在傳統(tǒng)型語言中勘高，這個程序是不可分解的峡蟋。我們將利用惰性求值將其化為更加模塊化的形式，而后演示所生成部件的一些其他用途华望。

由于牛頓－拉夫森算法計算的是一個近似值的序列蕊蝗，故將它寫作一個使用近似值列表的程序就再自然不過了。每個近似值都可以通過下面的函數(shù)從前一個值計算得到：

next N x = (x + N/x) / 2

因此(next N)是從一個近似值映射到下一個值的函數(shù)赖舟。調(diào)用函數(shù)f蓬戚，得到近似值序列：

[a0, f a0, f(f a0), f(f(f a0)), ...]

我們可以定義一個函數(shù)來計算：

repeat f a = cons a (repeat f (f a))

因此近似值序列可以這樣計算：

repeat (next N) a0

repeat是一個具有“無窮”輸出的函數(shù)的例子——但這沒關(guān)系，因為超出程序其余部分需求的近似值并不會被計算宾抓。無窮性只是潛在的：它只說明子漩，只要有需求豫喧，就可以計算出任意數(shù)量的近似值，repeat本身不會強加任何限制幢泼。

求根函數(shù)的剩余部分是函數(shù)within紧显，它取一個允許誤差與一個近似值列表作為參數(shù)，并在列表中查找差值不超過允許誤差的一對相鄰的近似值旭绒。這個函數(shù)可以定義為：

within eps (cons a (cons b rest)) = {
= b, 如果 abs(a-b) <= eps
= within eps (cons b rest), 其他情況
}

將這兩個部件結(jié)合起來鸟妙，

sqrt a0 eps N = within eps (repeat (next N) a0)

現(xiàn)在我們得到了求根函數(shù)的兩大部件，便可以嘗試用不同的方式組合它們挥吵。將要進行的修改之一重父，是將判斷條件改為“相鄰近似值的比趨近1”而不是“差趨近0”。這對于非常小的數(shù)字而言更加合適（當(dāng)初始的相鄰近似值之間的差值很小時）忽匈，對非常大的數(shù)字也是如此（當(dāng)舍尾產(chǎn)生的誤差比允許誤差大很多時）房午。我們只需要定義一個函數(shù)來替換within，而并不需要改寫生成近似值的部件：

relative eps (cons a (cons b rest)) =
= b, 如果 abs(a-b) <= eps*abs b
= relative eps (cons b rest), 其他情況

［注意：relative里的eps與within里的eps定義是不同的丹允！前者是絕對誤差后者是相對誤差９帷］

4.2.數(shù)值微分

我們已經(jīng)重用了平方根近似值序列，當(dāng)然雕蔽，對函數(shù)within和relative的重用也是可能的折柠，它們能夠與任何一個生成近似值序列的數(shù)值算法配合。我們將這樣來編寫數(shù)值微分算法批狐。

函數(shù)在某一點的微分扇售，便是其圖象在該點的斜率。通過分別計算函數(shù)在該點與一個臨近點處的取值嚣艇，而后計算兩點連線斜率的方法承冰，可以很容易地估計出微分的值。這基于一個假定：如果這兩點靠得足夠近食零，那么函數(shù)圖象在兩點之間不會彎曲得很厲害困乒。于是有下述定義：

easydiff f x h = (f(x+h)-f x) / h

為了得到良好的近似值，h應(yīng)該很小贰谣。不幸的是娜搂，如果h太小，那么f(x+h)與f(x)會相當(dāng)接近冈爹，因此在相減過程中產(chǎn)生的舍尾誤差可能會掩蓋了計算結(jié)果涌攻。如何為h選取恰當(dāng)?shù)闹的兀拷鉀Q這個矛盾一種合理的方案是：從一個較大取值開始频伤，不斷減小h的值，并求出一個近似值序列芝此。這個序列將趨近于該點的導(dǎo)數(shù)憋肖，但最終會由于舍尾誤差的存在而不可救藥地變得不精確因痛。如果我們用(within eps)來選取第一個足夠精確的近似值，那么舍尾誤差影響結(jié)果的風(fēng)險將會大大降低岸更。我們需要一個函數(shù)來計算這個序列：

differentiate h0 f x = map (easydiff f x) (repeat halve h0)
halve x = x/2

此處h0是h的初值鸵膏，而后繼取值是通過不斷減半得到的。通過這個函數(shù)怎炊，任意點處的導(dǎo)數(shù)可以這樣計算：

within eps (differentiate h0 f x)

但是谭企，甚至這個方案也不是那么令人滿意的，因為近似值序列收斂得相當(dāng)慢评肆。解決這個問題需要一點數(shù)學(xué)知識债查，序列中的元素可以記為：

微分的精確值 ＋ 一個關(guān)于h的誤差項

理論表明，該誤差項與h的某一次冪大致成正比瓜挽，因此當(dāng)h減小時盹廷，誤差也會減小。設(shè)精確值為A久橙，而誤差項為B*h**n [**是求冪運算符］俄占。由于計算每個近似值時所用的h取值是下一個的兩倍，故任意兩個連續(xù)的近似值可以表示成：

a(i) = A + B*(2**n)*(h**n)a(i+1) = A + B*(h**n)

現(xiàn)在就可以消去誤差項了淆衷，我們得到：

A=(a(i+1)*(2**n) - a(i))/(2**n - 1)

當(dāng)然缸榄，誤差項只不過“大致”與h的某一次冪（成正比），因此這個結(jié)論也是近似的祝拯。但這是一個好得多的近似甚带。這一改進可以通過下述函數(shù)作用于所有相鄰的近似值對之上：

elimerror n (cons a (cons b rest)) =
= cons ((b*(2**n)-a)/(2**n-1)) (elimerror n (cons b rest))

從一個近似值序列中消除誤差項的操作產(chǎn)生了另一個收斂速度快得多的序列。

使用elimerror之前還有一個問題需要解決——我們必須知道n的正確值鹿驼。通常這個值很難預(yù)測欲低，但卻很容易衡量。不難驗證畜晰，下述函數(shù)能夠正確地消除誤差項砾莱，但在此我們并不給出證明。

order (cons a (cons b (cons c rest))) =
= round(log2( (a-c)/(b-c) - 1 ))
round x = 最接近x的整數(shù)
log2 x = x以2為底的對數(shù)

現(xiàn)在凄鼻，一個通用的近似值序列優(yōu)化函數(shù)可以定義為：

improve s = elimerror (order s) s

使用improve能夠更加高效地計算函數(shù)f的導(dǎo)數(shù)腊瑟，如下：

within eps (improve (differentiate h0 f x))

improve只對利用一個不斷減半的參數(shù)h計算得到的近似值序列適用。但是块蚌，如果improve作用于這樣的序列闰非，那么其結(jié)果也是一個這樣的序列！這意味著一個近似值序列可以優(yōu)化不止一次峭范。每一次優(yōu)化的過程中财松，都有一個不同的誤差項被消除，因此優(yōu)化產(chǎn)生的序列收斂得越來越快。因此辆毡，可以非常高效地計算導(dǎo)數(shù)：

within eps (improve (improve (improve (differentiate h0 f x))

從數(shù)值分析的角度講菜秦，這似乎是一個“第四階方法”(fourth order method)，可以迅速地給出準(zhǔn)確的結(jié)果舶掖。甚至可以定義：

super s = map second (repeat improve s)
second (cons a (cons b rest)) = b

super函數(shù)使用repeat improve來生成一個不斷被優(yōu)化的近似值的序列的序列球昨。［就是說，生成一個序列眨攘，其中每一個元素是一個近似值序列主慰，而這個元素是用前一個元素優(yōu)化得到的。］同時鲫售，super提取出每個近似值序列中的第二個元素共螺，構(gòu)造出一個新的序列（已經(jīng)確認(rèn)，第二元素是最佳選擇——它比首元更精確龟虎，而且不需要額外的計算）璃谨。這個算法的確非常復(fù)雜——更多的近似值被計算的同時，它使用了不斷優(yōu)化的數(shù)值方法鲤妥〖淹蹋可以用下面的程序非常非常高效地計算導(dǎo)數(shù)：

within eps (super (differentiate h0 f x))

這個案例可能就像是用大錘敲碎堅果一樣（大材小用），但關(guān)鍵是棉安，甚至一個像super一樣復(fù)雜的函數(shù)底扳，當(dāng)被惰性求值的方法模塊化時，也會變得很容易表達贡耽。

4.3.數(shù)值積分

在這一部分我們將討論的最后一個例子是數(shù)值積分衷模。問題的描述很簡單：給出一個返回實數(shù)，并有一元實數(shù)參數(shù)的函數(shù)蒲赂，以及兩個端點a和b阱冶，估算兩點之間曲線f下方的面積。估算面積的最簡單方法是假定f趨近于直線滥嘴，此時面積就是：

easyintegrate f a b = (f a + f b)*(b-a)/2

不幸的是木蹬，除非a與b足夠接近，否則這個估算似乎非常不精確若皱。更好的估算方法是镊叁，將a與b之間的區(qū)間分為兩段，分別估算子區(qū)間上的面積走触，再將結(jié)果加起來晦譬。我們可以定義一個不斷趨近于準(zhǔn)確值的積分近似值序列，首先使用上述方程進行第一次近似互广，而后將分別趨近于兩個子區(qū)間上的子積分準(zhǔn)確值的（兩個）近似值累加起來以得到新的（積分總體的）近似值敛腌。計算這個序列可以使用函數(shù)：

intergrate f a b = cons (easyintergrate f a b)
(map addpair (zip (intergrate f a mid)
(intergrate f mid b)))
式中 mid = (a+b)/2

zip是另一個標(biāo)準(zhǔn)的表處理函數(shù)。它讀取兩個列表，并返回一個有序?qū)Φ牧斜碛疲總€有序?qū)τ蓛蓚€輸入列表中對應(yīng)的元素組成夸溶。從而第一對由列表一和列表二的首元組成逸吵，第二對由列表一和列表二的第二個元素組成凶硅，以此類推。zip可以定義為：

zip (cons a s) (cons b t) = cons (pair a b) (zip s t)

在函數(shù)intergrate中扫皱，zip用于生成由兩個子區(qū)間上相對應(yīng)的積分近似值對組成的列表足绅，而map addpair用于將有序?qū)χ械脑叵嗉樱瑥亩梢粋€原積分的近似值列表韩脑。

實際上氢妈，這個版本的intergrate函數(shù)相當(dāng)?shù)托В驗樗掷m(xù)不斷地重復(fù)計算f的值段多。就像所寫的一樣首量，easyintergrate計算了f在a和b兩處的值，而對intergrate的遞歸調(diào)用將重復(fù)計算它們进苍。同樣的加缘，(f mid)也在遞歸調(diào)用中重復(fù)計算了。因此觉啊，更可取的是下述從不重復(fù)計算f的版本：

intergrate f a b = interg f a b (f a) (f b)
integ f a b fa fb = cons ((fa+fb)*(b-a)/2)
(map addpair (zip (interg f a m fa fm)
(interg f m b fm fb)))
式中 m = (a+b)/2fm = f m

integrate給出了一個不斷趨近準(zhǔn)確值的積分近似值列表拣宏，正如differentiate在上一小節(jié)中所做的一樣。因此可以寫出計算式以求出所需任意精度的積分值杠人，如下：

within eps (intergrate f a b)relative eps (integrate f a b)

這個積分算法與上一小節(jié)中的第一個微分算法有著同樣的缺點——它收斂得相當(dāng)慢勋乾。序列中的第一個近似值僅僅用了兩個相距(a-b)的點來計算（通過easyintergrate）。第二個近似值也（除了a嗡善、b之外）用到了中點辑莫，因此相鄰兩點之間的間距僅為(b-a)/2。第三個近似值在兩個子區(qū)間上作同樣的處理罩引，因此間距僅為(b-a)/4各吨。很清楚，每個近似值對應(yīng)的相鄰兩點之間的間距在計算下一個值時被減半了蜒程。將這一間距看作h绅你，那么這個序列就可以成為上一小節(jié)中定義的improve函數(shù)的優(yōu)化對象了。因此我們可以寫出（函數(shù)來計算）快速收斂的積分近似值序列昭躺，例如：

super (intergrate sin 0 4)improve (intergrate f 0 1)式中 f x = 1/(1+x*x)

（后一個序列是用于計算pi/4的“第八階方法”忌锯。其中的第二個近似值只需要計算5次f的取值，但卻具有5位準(zhǔn)確數(shù)字领炫。）

在本節(jié)中我們選取了一些數(shù)值算法并將它們函數(shù)化地編寫出來偶垮，把惰性求值當(dāng)做了黏合部件的黏合劑。由于惰性求值的存在，使得我們可以用很多新的方式來模塊化這些算法似舵，從而產(chǎn)生用途廣泛的函數(shù)脚猾，例如within，relative
和improve砚哗。通過這些部件的不同組合龙助，我們簡單而明了地編寫出了一些相當(dāng)不錯的數(shù)值算法。

5.人工智能中的例子

我們已經(jīng)指出蛛芥，函數(shù)式語言威力強大主要是因為它們提供了兩種新的黏合劑：高階函數(shù)和惰性求值提鸟。在本節(jié)中，我們將討論人工智能中一個大一點的實例仅淑，并演示如何使用這兩種黏合劑來十分簡單地編寫它称勋。

我們選取的實例是alpha-beta“啟發(fā)式搜索”，一個用于估計游戲者所處形勢好壞的算法涯竟。該算法預(yù)測游戲局勢的可能發(fā)展赡鲜，但會避免對無意義局勢的進一步探究。
令游戲局勢使用position類型的對象來表示庐船。這個類型依據(jù)游戲的不同而不同银酬，我們不對此作任何假定。必然有一種方法可以知曉對某一個局勢能夠采取的行動：假定有一個函數(shù)：

moves: position -> listof position

該函數(shù)以一個游戲局勢為參數(shù)醉鳖，并返回一個可以由自變量出發(fā)捡硅，通過一步行動而形成的position
的列表。以noughts and crosses游戲（tic-tac-toe）為例：

fp1

利用函數(shù)moves，第一步是構(gòu)造一棵博弈樹瞭恰。這棵樹的結(jié)點都用局勢來標(biāo)記屯曹，而一個結(jié)點的子結(jié)點用從該結(jié)點一步便可到達的局勢標(biāo)記。也就是說惊畏，如果一個結(jié)點標(biāo)記為局勢p恶耽，那么它的子結(jié)點將使用(moves p)中的局勢來標(biāo)記。一棵博弈樹完全有可能是無窮的颜启，如果這個游戲可以在雙方都不勝的情形下永遠(yuǎn)進行下去的話偷俭。博弈樹與第2節(jié)中討論的樹完全類似——每個結(jié)點都有一個標(biāo)記（它所代表的局勢）與一個子結(jié)點列表。因此我們可以使用相同的數(shù)據(jù)類型來表示它們缰盏。

博弈樹是通過反復(fù)運用moves而構(gòu)造出來的涌萤。構(gòu)造從根局勢開始淹遵，moves用于生成根結(jié)點處子樹的標(biāo)記，而后moves被用于生成子樹的子樹负溪，依此類推透揣。這一遞歸模式可以用一個高階函數(shù)表示：

reptree f a = node a (map (reptree f) (f a))

使用這個函數(shù)可以定義另一個函數(shù)，該函數(shù)從一個特定的局勢開始生成博弈樹：

gametree p = reptree moves p

例如圖1所示川抡。此處使用的高階函數(shù)reptree與上一節(jié)中用于構(gòu)造無窮列表的函數(shù)repeat是類似的辐真。

fp2

alpha-beta算法從一個給定的局勢出發(fā)，就游戲的發(fā)展將會是有利還是不利作出判斷猖腕。然而拆祈，要做到這一點，它必須能夠在不考慮下一步的情況下粗略地估計某一個局勢的“價值”倘感。在后繼局勢不可預(yù)測時必須使用這一函數(shù)，它也可以用來對算法進行先期引導(dǎo)咙咽。靜態(tài)估價的結(jié)果是從計算機的角度考慮的老玛，是對該局勢的前途的度量（假設(shè)在游戲中計算機與人對抗）。結(jié)果越大钧敞，局勢對計算機而言越好蜡豹。結(jié)果越小，局勢越糟溉苛。最簡單的此類函數(shù)將會镜廉，比如說，對計算機確定勝利的局勢返回+1愚战，對計算機確定失敗的局勢返回-1娇唯，而對其它的局勢返回0。在現(xiàn)實中寂玲，靜態(tài)估價函數(shù)會衡量各種使局勢“看上去不錯”的因素塔插。例如，具體的好處拓哟，以及象棋中對中心的控制想许。假定有這樣一個函數(shù)：

static: position -> number

既然一棵博弈樹是一個(treeof position)，那么它就可以被函數(shù)(maptree static)轉(zhuǎn)換為一個(treeof number)断序，該函數(shù)對樹中所有的（也許是無窮多個）局勢進行靜態(tài)估價流纹。此處使用了第2節(jié)中定義的函數(shù)maptree。

給出一棵靜態(tài)估價樹之后违诗，其中各個局勢的真值究竟是多大漱凝？特別地，對根局勢應(yīng)該賦予什么值较雕？不是它的靜態(tài)值碉哑，因為那只是一個粗略的猜測挚币。一個結(jié)點被賦予的值，必須由其子結(jié)點的真值決定扣典。這一過程的完成妆毕，基于每個游戲者都會選擇對自己最有利的行動的假定≈猓回憶一下笛粘，高值意味著計算機的有利形勢。很明顯湿硝，當(dāng)計算機從任意的局勢開始下一步行動時薪前，它將選擇通往真值最高的子結(jié)點的行動。類似地关斜，對手將會選擇通往真值最低的子結(jié)點的行動示括。假定計算機與其對手輪流行動，那么當(dāng)輪到計算機行動時痢畜，節(jié)點的真值用函數(shù)maximise計算垛膝，反之用minimise計算。

［所謂“真值”（true value）丁稀，可能是我翻譯得不好吼拥，此處理解為類似“真正的價值”的意思吧，是一個量度线衫，不是邏輯學(xué)里的0和1哦凿可。］

maximise (node n sub) = max (map minimise sub)
minimise (node n sub) = min (map maximise sub)

此處max和min是關(guān)于列表的函數(shù)，分別返回列表中元素的最大值與最小值授账。上述定義是不完整的枯跑，因為它們將永遠(yuǎn)遞歸下去——沒有給出邊界情形。我們必須定義沒有后繼的結(jié)點的值（其標(biāo)記）矗积。因此靜態(tài)估價用于任一游戲者勝利或者后繼局勢不可預(yù)測的情況下全肮。maximise與minimise的完整定義是：

maximise (node n nil) = n
maximise (node n sub) = max (map minimise sub)
maximise (node n nil) = n
maximise (node n sub) = min (map minimise sub)

在這個階段，幾乎已經(jīng)可以寫出一個取一個局勢作為參數(shù)并返回其真值的函數(shù)了棘捣」枷伲可能是：

evaluate = maximise . maptree static . gametree

這個定義有兩個問題。首先乍恐，它不適用于無窮樹评疗。maximise不斷地遞歸直到找到一個沒有子樹的結(jié)點——樹的端點。如果沒有端點那么maximise就不會返回結(jié)果茵烈。第二個問題與第一個有關(guān)——甚至有窮的博弈樹（如noughts and crosses里的那棵）事實上也可能相當(dāng)大百匆。估價整棵博弈樹是不現(xiàn)實的——搜索必須被限定在接下去的幾步之內(nèi)。為此可以將樹剪至一個固定的深度：

prune 0 (node a x) = node a nilprune n (node a x) = node a (map (prune (n-1)) x)

(prune n)取一棵樹作為參數(shù)并“剪去”與根結(jié)點的距離超過n的所有結(jié)點呜投。如果一棵博弈樹被剪枝加匈，那么將強制maximise對深度為n的結(jié)點執(zhí)行靜態(tài)估價而不是進一步遞歸存璃。因此evaluate可以被定義為：

evaluate = maximise . maptree static . prune 5 . gametree

這將考慮其后（比如說）5步的形勢。

在此開發(fā)過程中我們已經(jīng)使用了高階函數(shù)與惰性求值雕拼。高階函數(shù)reptree和maptree使得我們能夠很容易地構(gòu)造與處理博弈樹纵东。更重要的是，惰性求值確保了我們可以使用這種方式模塊化evaluate啥寇。由于博弈樹具有潛在的無窮結(jié)果偎球，在沒有惰性求值的情況下，程序?qū)⒂肋h(yuǎn)不會終止辑甜。我們將不能寫：

prune 5 . gametree

而不得不將這兩個函數(shù)整合成一個只構(gòu)造樹的前五層的函數(shù)衰絮。更糟糕的是，甚至那前五層都可能已經(jīng)太大以至于無法在同一時間內(nèi)存儲于內(nèi)存中磷醋。而在我們所寫的程序中猫牡，函數(shù)

maptree static . prune 5 . gametree

只是構(gòu)造出了樹中maximise所需的部分。由于每一部分都可以在被maximise處理完之后丟棄（被垃圾收集器回收）子檀，故完整的樹從來沒有存儲于內(nèi)存中镊掖。只有樹的一小部分在某一段時間內(nèi)被儲存著。因此這個惰性程序很有效率褂痰。這一效率取決于maximise（組合鏈上的最后一個函數(shù)）與gametree（第一個函數(shù)）的相互作用，因此在沒有惰性求值的情況下症虑，要完成任務(wù)缩歪，只能將組合鏈上的所有函數(shù)整合成一個大函數(shù)。這是對模塊化的強烈破壞谍憔，但也是通常的做法匪蝙。通過單獨修補每個部件，我們就可以優(yōu)化估價算法——這相對簡單习贫。而一個傳統(tǒng)型程序員必須把整個程序作為一個單元來修改逛球，這就困難多了。
到目前為止苫昌，我們只是描述了簡單的對最大最小值的處理（minimaxing）颤绕。但alpha-beta算法的核心是“計算maximise與minimise的值時常常不需要考慮整棵樹”這一觀察結(jié)果∷钌恚考慮樹：

          max 
          / \ 
         /   \
        /     \ 
       /       \ 
     min       min 
     / \       / \
    /   \     /   \
   1     2   0     ?

相當(dāng)奇怪地奥务，為了估價這棵樹，并不需要知道問號處的值袜硫。左子樹的最小值是1氯葬，但右子樹的最小值顯然是一個小于或等于0的值。因此這兩個最小值的最大值必然是1婉陷。這一觀察結(jié)果可以被泛化并內(nèi)建到maximise和minimise之中帚称。

第一步是將maximise拆分成max對一個數(shù)字列表的作用官研。也就是，將maximise分解為：

maximise = max . maximise'

（minimise可以用類似的方法分解闯睹。由于maximise和minimise是完全對稱的戏羽，故我們將只討論maximise，而假定minimise也照此處理瞻坝。）一旦這樣分解之后蛛壳，maximise可以使用minimise'來發(fā)現(xiàn)minimise將對哪些數(shù)字求最小值，并且不再使用minimise本身所刀。而后便可以在不查看某些數(shù)字的情況下便將它們丟棄衙荐。由于惰性求值的存在，如果maxmise并不會查看所有的數(shù)字列表浮创，那么一部分列表將不會被計算忧吟，這是對計算機時間的潛在節(jié)約。

將max從maximise中“約分出來”是很簡單的斩披，得到：

maximise' (node n nil) = cons n nil
maximise' (node n l) = map minimise l
= map (min . minimise') l
= map min (map minimise' l)
= mapmin (map minimise' l)
式中 mapmin = map min

由于minimise'返回一個數(shù)字列表溜族，而這個列表的最小值是minimise的結(jié)果，故(map minimise' l)返回一個數(shù)字列表的列表。Maximise'應(yīng)該返回這些列表中每個列表的最小值組成的列表，但只有其中［Maximise的返回值中］的最大值才有用问窃。我們應(yīng)該定義一個mapmin的新版本以忽略那些最小值不重要的列表［在(map minimise' l)的返回值中］的最小值沦泌。

mapmin (cons nums rest) =
= cons (min nums) (omit (min nums) rest)

函數(shù)omit傳遞一個“潛在的最大值”——當(dāng)前所發(fā)現(xiàn)的最小值中最大的一個——并忽略任何比該值小的最小值。

omit pot nil = nil
omit pot (cons nums rest) =
= omit pot rest, if minleq nums pot
= cons (min nums) (omit (min nums) rest), otherwise

minleq以一個數(shù)字列表和一個潛在最大值為參數(shù)，如果列表的最小值小于或等于潛在最大值就返回真。要完成這一工作，它并不需要掃描整個列表况既！如果列表中有任意一個元素小于或等于潛在最大值，那么列表的最小值肯定也是如此组民。該特別元素之后的所有元素都是無關(guān)緊要的——它們就像是上面例子中的問號一樣棒仍。因此minleq可以被定義為：

minleq nil pot = false
minleq (cons num rest) port = true, if numn2

此處sort是多用途排序函數(shù)。現(xiàn)在估價函數(shù)定義為：

evaluate = max . maximise' . highfirst . maptree static . prune 8 . gametree

也可能認(rèn)為臭胜，為了限制搜索莫其，只要考慮計算機或者對手的前三個最佳行動也已經(jīng)足夠了。要編寫這樣的程序庇楞，只需要把highfirst換成(taketree 3 . highfirst)榜配，其中：

taketree n = redtree (nodett n) cons nil
nodett n label sub = node label (take n sub)

taketree將樹上所有的結(jié)點替換為最多有n個子結(jié)點的結(jié)點，它使用了函數(shù)(take n)吕晌，而該函數(shù)返回列表的前n個元素（如果列表比n短蛋褥，那么返回的元素就少一些）。

另一種優(yōu)化是對剪枝的改良睛驳。上述程序甚至在局勢非常dynamic的情形下也會向前搜索固定的深度——（但是烙心，）例如在國際象棋中膜廊，一旦皇后被威脅，也許就可以決定不再搜索了淫茵。通匙希可以定義某些“dynamic”的形勢，并在遇到這樣的結(jié)點之一時匙瘪，不再繼續(xù)搜索而停止铆铆。假定有函數(shù)“dyramic”用以確定這樣的形勢，那么只需要為prune追加一個定義等式：

prune 0 (node pos sub) = node pos (map (prune 0) sub), if dynamic pos

在像這個程序一樣模塊化的程序里丹喻，作出這樣的改動是很簡單的薄货。如前所述，這個程序的效率碍论，關(guān)鍵是由鏈中的最后一個函數(shù)maximise與第一個函數(shù)gametree的相互作用決定的谅猾，因此若沒有惰性求值，就只能寫成一個單一的程序鳍悠。這樣的程序難于編寫税娜，難于修改，而且藏研，非常難于理解敬矩。

6.結(jié)論

在本文中，我們指出模塊化是成功的程序設(shè)計的關(guān)鍵蠢挡。以提高生產(chǎn)力為目標(biāo)的程序語言谤绳，必須良好地支持模塊化程序設(shè)計。但是袒哥，新的作用域規(guī)則和分塊編譯的技巧是不夠的——“模塊化”不僅僅意味著“模塊”。我們分解程序的能力直接取決于將解決方案粘在一起的能力消略。為了協(xié)助模塊化程序設(shè)計堡称，程序語言必須提供優(yōu)良的黏合劑。函數(shù)式程序語言提供了兩種新的黏合劑——高階函數(shù)與惰性求值艺演。利用這些黏合劑可以將程序用新的却紧、令人激動的方式模塊化，對此我們舉出了很多實例胎撤。越小晓殊、越通用的模塊越可能被廣泛地重用，使后續(xù)的程序設(shè)計工作變得簡單伤提。這解釋了為什么函數(shù)式程序與傳統(tǒng)型程序比較巫俺，要小得多，也容易編寫得多肿男。它也為函數(shù)式程序員提供了一個追求目標(biāo)介汹。如果程序的任何部分是雜亂或者復(fù)雜的却嗡，那么程序員就應(yīng)當(dāng)嘗試將其模塊化并泛化其部件。他應(yīng)當(dāng)期望把高階函數(shù)和惰性求值用作他做此事的工具嘹承。

當(dāng)然窗价，我們并不是指出高階函數(shù)與惰性求值的力與美的第一人。例如叹卷，Turner展示了這兩者如何在一個生成化學(xué)結(jié)構(gòu)的程序里大顯身手［Tur81］撼港。Abelson和Sussman強調(diào)“流”（惰性列表）是構(gòu)架程序的強大工具［AS86］。Henderson使用了流來構(gòu)架函數(shù)式操作系統(tǒng)［P.H82］骤竹。本論文的主要貢獻是帝牡，斷言了模塊化自身，便是函數(shù)式語言強大威力的關(guān)鍵瘤载。

這與當(dāng)前有關(guān)惰性求值的論戰(zhàn)也有關(guān)聯(lián)否灾。有些人認(rèn)為函數(shù)式語言應(yīng)當(dāng)是惰性的，而其他人認(rèn)為不是這樣鸣奔。有些人走折衷路線墨技，只提供惰性列表以及用于構(gòu)造它們的特殊語法（例如，在SCHEME中［AS86］）挎狸。本論文提供了更進一步的證據(jù)扣汪，證明惰性求值非常重要以至于不能被降為二等公民。這也許是函數(shù)式程序員所擁有的最強大的黏合劑锨匆。人們不應(yīng)當(dāng)阻礙對這樣一個極為重要的工具的使用崭别。

致謝

在牛津程序設(shè)計研究組與Phil Wadler和Richard Bird的多次交談對本論文的寫作幫助甚大。約特堡查麥茲大學(xué)的Magnus Bondesson指出了一個數(shù)值算法的早期版本中的嚴(yán)重錯誤恐锣，同時也協(xié)助了很多其他算法的開發(fā)茅主。本論文在英國科學(xué)與工程研究評議會提供的研究基金贊助下發(fā)表。

參考文獻

[AS86] H.Abelson,G.J.Sussman. 計算機程序的構(gòu)造與解釋. 麻省理工學(xué)院出版社,波士頓,1986
[Hug89] J.Hughes. 函數(shù)式程序設(shè)計為什么至關(guān)重要. 計算機月刊,32(2),1989
[Hug90] John Hughes. 函數(shù)式程序設(shè)計為什么至關(guān)重要. D.Turner主編,函數(shù)式編程的研究主題. Addison Wesley,1990
[MTH90] R.Milner,M.Tofte,R.Harper. Standard ML的定義. 麻省理工學(xué)院出版社,1990
[oD80] 美利堅合眾國國防部. 程序語言Ada參考手冊. Springer-Verlag,1980
[P.H82] P.Henderson. 純函數(shù)式操作系統(tǒng). 1982
[Tur81] D.A.Turner. 應(yīng)用語言在語義上的優(yōu)雅性. 1981年度函數(shù)式語言與計算機架構(gòu)會議會報,海邊溫特渥,普茨茅斯,新漢普夏郡,1981
[Tur85] D.A.Turner. Miranda: 擁有多態(tài)類型的非嚴(yán)格語言. 1985年度函數(shù)式語言與計算機架構(gòu)會議會報,1-16頁,南錫,法國,1985
[Wir82] N.Wirth. Modula-II程序設(shè)計. Springer-Verlag,1982