Why Functional Programming Matters ZZ

發信人: bitapf (北京理工程式設計愛好者協會), 信區: FuncProgram

标  題: Why Functional Programming Matters

發信站: BBS 水木清華站 (Sun Nov 23 15:11:17 2003)

後面的沒翻譯完，原文的名字就是這個，大家自己搜一下吧，ps格式的不好給。

想要繼續我的翻譯的我給你投遞原文，或者覺得我翻譯得太爛（的确很爛，汗）

，也給你投遞。留個mail就行。雖然此文已經是将近20年前的東西了，回顧一下

也是好的。

Why Functional Programming Matters

摘要

随着軟體變得越來越複雜，使它結構良好變得越來越重要，結構良好的軟體易寫易調試，

并提供了許多可以降低未來開發代價的可重用子產品。傳統的語言在把問題子產品化的道路上

有概念上的限制，functional語言把這些限制給去掉了。在本文中，我們特别地展示了fu

nctional語言的兩個能夠極大推動子產品化的特色，high-order函數與lazy evaluation。作

為例子，我們操縱list和tree，編寫幾個數值算法，并實作alphabeta heuristic（一個用

于遊戲程式中的人工智能算法）。因為子產品化是成功程式設計的關鍵，functional語言對real

 world很有意義。

1 導論

本文嘗試向“real world”展示Functional Programming重要性，并通過講清楚它的優點

幫助functional程式員最大限度地利用這些好處。

Functional Programming之是以稱之為Functional Programming是因為程式完全由函數組

成。主程式本身被寫成以參數形式接收程式輸入和結果為産生程式輸出的函數。典型的主

函數是由其他函數定義的，而這些函數反過頭來又是由其他更多的函數定義的，直到語言

内建的那些函數為止。這些函數與數學中的函數很像，而且在本文中将由普通的等式定義

。我們的記号遵循Turner的Miranda語言的文法，但應該能夠在事先不了解functional語言

的前提下讀懂。（Miranda式Research軟體有限公司的商标）

Functional Programming的特質與優點經常或多或少地歸結于一下幾條。Functional程式

不包含指派語句，因而也沒有變量，一旦給了一個值永遠不能改變。更一般地說，functi

onal程式一點side-effect都沒有，一個函數調用沒有計算結果之外的影響。這消除了bug

的一個主要來源，并使得執行的順序不是彼此相關的——因為沒有改變表達式的side-eff

ect，它就能在任何時刻被求值。這把程式員從規定程式流程的重擔中釋放出來，因為表達

式可以在任何時候被求值，可以自由地用變量的值代換變量，反之亦然——也就是說程式

是“referentially透明的"。這種自由使得functional程式在數學意義上比傳統程式更易

駕馭。

對好處的這麼一個歸納總體上來說是不錯的，但不要對外界對它不以為意感到奇怪。它說

得更多的是functional programming不是什麼（它沒有指派，沒有side-effect，沒有流程

控制），而不是它是什麼。functional程式員聽起來很像中世紀的僧侶，抛棄自己生活中

的樂趣以獲得使自己變成聖德的希望。對于哪些更關心實實在在的利益的人，這些好處不

是十分地有說服力。

functional程式員争辯地說确實有很多實在的好處——因為functional程式非常精簡，一

個functional程式員比傳統的程式員有大得多的生産力。而這是為什麼呢？唯一的似是而

非的理由暗示了這些“優點”的基礎是傳統程式包含的90％代碼是指派語句，而在functi

onal程式中這些被省略了！這顯而易見是荒唐的。如果僅僅省略指派語句就可以帶來如此

多的好處，那麼FORTRAN程式員可能已經享用20餘年了。通過省略語言特性（不管他們是多

麼糟糕）的辦法使得其變得更有威力從邏輯上講都是不可能的。

甚至一個functional程式員都會被這些所謂的優勢感到不滿足，因為這無益于他們挖掘fu

nctional語言的威力。一個人不能寫尤其特别地缺少指派語句或者特别地referentially透

明的程式。這兒沒有一個衡量軟體品質的準繩，因而沒有要努力達到的目标。

顯然這樣的對functional programming的描述是不恰當的。我們必須找出一些到位的東西

——一些不僅僅解釋了functional programming威力而且該處了一個functional 程式員應

該朝之努力的明确指引。

2 同結構化程式設計的類比

在functional和structured programming之間作一個類比是有好處的。在過去，結構化編

程的好處或多或少的總結出這麼幾條。結構化程式設計沒有goto語句，在結構化程式中的代碼

塊沒有多個入口或者出口。結構化的比非結構化的同樣的程式要在數學意義上更易處理。

結構化程式設計的這些“優點”和我們前面講的functional programming的“優點”的精神上

是很相似的。他們本質上是negative statements，并導緻了許多沒有結果的關于“重要的

goto”的争論，等等。

結構化程式的這些好處是清楚的，如後見之明一樣雖然有幫助，但并沒有切入問題的核心

。結構化和非結構化程式的最重要的差別是結構化程式以子產品化的方式設計。子產品化設計

給它帶來了生産力上的很大提高。首先，消息的子產品可以更快更容易地被編寫。其次，通

用的子產品能夠被重用，導緻了後來的程式的更快速的開發。第三，程式的子產品可以獨立地

被測試，有助于減少花費在調試上的時間。

goto的濫用，等等，對這些問題來說無關緊要。他對“小軟體的程式設計”有幫助，但是子產品

化設計對“大尺度的程式設計”有幫助。因而可以在FORTRAN或者彙編語言中享受結構化程式設計的

好處，甚至要作多一些的工作也無所謂。

大家基本上已經接收了子產品化設計是成功程式設計的關鍵，而且像Modula-II[Wir82], Ada[oD

80] 和 Standard ML [MTH90]這些語言中特别包含了改善子產品性的設計。然而，有一點很

關鍵的地方經常被忽略。在編寫子產品化程式來解決問題的時候，首先要把問題劃分為子問

題，然後逐個解決小問題，最後把這些解決方案粘合起來。分解原有問題的手段直接依賴

于最終粘合解決方案的辦法。因而，要從概念上增強子產品化的能力，必在程式設計語言中提供

新的粘合劑。複雜的作用域規則和提供單獨編譯隻能幫助具體的細節；他們沒有提供新的

分解問題的概念上的工具。

你可以從木匠的比喻中認識到粘合劑的重要性。一個椅子能夠通過用正确方法把位子，腿

，靠背這些部分粘合起來而很容易的制造出來。但這依賴于接頭和木膠的作用。缺少了這

些東西，作一個椅子的唯一辦法就是從一塊硬實的木頭中刻出來，一件困難得多的任務。

這個例子顯示了子產品化的巨大威力和擁有合适粘合劑的重要性。

現在讓我們回到functional programming來。我們在本文的餘下部分讨論functional語言

提供的兩種新的，非常重要的粘合劑。我将提供許多可以用新的手段，因而加大地被簡化

樂得，子產品化的例子。這是functional programming的關鍵能力，它為被極大改進的子產品

化設計提供了可能。這也是functional程式員必須朝之努力的目标——更小更簡單更通用

的子產品，通過我們将要描述的新的粘合劑粘合起來。

3 把函數粘合起來

這兩種新的粘合劑的第一個使得簡單的函數可以粘合在一起成為更複雜的東西。這由簡單

的list處理問題示範——把list中的元素加起來。我們這樣定義list

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

這意味着X（不管X是什麼）的list要麼是nil，代表沒有元素的list，要麼是一個X和另一

個X的list的cons。一個cons代表一個list，它的第一個元素是X，而接下來的元素是另一

個X的list的元素。這兒的X可能代表任何一種型别——例如，如果X是“整數”，那麼定義

說的是整數的list要麼是空的要麼是一個整數要麼是整數和另一個整數的list的cons。遵

循一般的實踐經驗，我們将簡單地通過把它們的元素用方括号擴住的辦法寫下list，而不

是顯式地寫出cons和nil。這隻是符号習慣上的速記。例如，

[] means nil

[1] means cons 1 nil

[1,2,3] means cons 1 (cons 2 (cons 3 nil))

因為list的元素可以通過循環調用函數sum加起來。sum必須為兩種參數做出定義：空的li

st（nil），和一個cons。因為0個數的和是0，我們定義

sum nil = 0

而且因為一個cons的和可以通過計算list的第一個元素和其他元素的和的和得出，我們定

義

sum (cons num list) = num + sum list

檢查這個定義，我們可以看到隻有下面加框的部分是特定于計算和的。

          +---+

sum nil = | 0 |

          +---+

                          +---+

sum (cons num list) = num | + | sum list

                          +---+

這意味着和的計算可以通過把通用的遞歸模式粘合加框的部分被子產品化。這個遞歸模式習

慣上稱為reduce，是以sum可以這樣表示

sum = reduce add 0

其中為了友善，傳遞給reduce的是帶兩個參數的函數而不是一個操作符。Add被如下定義

add x y = x + y

reduce的遞歸定義可以通過參數化sum的定義被繼承，例如

(reduce f x) nil = x

(reduce f x) (cons a l) = f a ((reduce f x) l)

這兒我們在(reduce f x)外加上括号是像讓它代替sum的意思清楚一些。習慣上，這個括号

是被省略的，因而((reduce f x) l)被寫作(reduce f x l)。一個像reduce這樣傳遞3個參

數但隻應用2個的函數，被認為是剩下的一個參數的函數。一般的說，一個傳遞了n個參數

但隻應用m(

通過這樣子產品化sum，我們可以重用這些部分獲得好處。最有意思的是reduce，它能夠讓不

用再程式設計就能寫出把list中的元素乘起來的函數：

product = reduce multiply 1

它還能被用于測試是否布爾值的list是否為真

anytrue = reduce or false

或者它們是否都是真

alltrue = reduce and true

一個了解(reduce f a)的辦法是把它認為是用f替換list中所有cons，用a替換nil的函數。

拿list [1,2,3]作為例子，它的意思是

cons 1 (cons 2 (cons 3 nil))

然後 (reduce add 0)被轉換為

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

而 (reducee multiply 1) 轉換為

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

是以明顯的， (reduce cons nil) 僅僅把一個list複制了一遍。因為一個list能夠通過c

ons另外一個list的元素于其前面被附加到它的後面。我們發現

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]))

                        (replacing cons by cons and nil by [3,4])

                   = [1,2,3,4]

一個把list中所有元素翻倍的元素能夠寫成

      doubleall = reduce doubleandcons nil

where doubleandcons num list = cons (2*num) list

Doubleandcons能夠進一步的子產品化，首先是

      doubleandcons = fandcons double

where double n = 2*n

      fandcons f el list = cons (f el) list

然後由

fandcons f = cons . f

其中“.”（composition函數，一個标準操作符）被定義為

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

我們可以通過應用一些參數，看到fandcons的新的定義是正确的：

   fandcons f el = (cons . f) el

                 = cons (f el)

so fandcons f el list = cons (f el) list

最終的版本是

doubleall = reduce (cons . double) nil

利用我們剛得出的更深入的子產品

doubleall = map double

map f = reduce (cons . f) nil

其中map把任意函數f作用于list的所有元素。map是另一個通常很有用的函數。

我們甚至可以寫出一個求由list的list代表的矩陣所有元素和的函數，它是

summatrix = sum . map sum

map sum使用sum來相加所有的行，然後最左邊的元素加到行的總和來獲得整個矩陣的和。

這些例子應當足以使讀者信服一個小小的子產品化設計能夠起到很大作用。通過子產品化簡單

函數（sum）為“higher order函數”和一些簡單參數的組合，我們得出了一個能夠用于不

用更多程式設計努力就能寫出很多其他操作list的函數的部件（reduce）。我們沒必要隻停留

在關于list的函數上。另一個例子，考慮有序标記的tree這種資料結構，定義為

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

這個定義告訴X的tree是一個有一個标簽X的節點，以及一個subtree的list，subtree又是

其它X的tree。例如，這個tree

    1 o

     / /

    /   /

   /     /

2 o       o 3

          |

          |

          |

          o 4

将由這個代表

node 1

    (cons (node 2 nil)

          (cons (node 3

                     (cons (node 4 nil) nil))

               nil))

不再考慮一個例子然後從中抽象一個higher order函數，我們直接得出一個類似reduce的

redtree函數。回憶reduce帶兩個參數，一個代替cons，一個代替nil。因為trree是用節點

，cons和nil建構的，redtree必須有代替這些東西的參數。既然tree和list是不同的類型

，我們必須定義兩個函數，分别操作自己的類型。是以我們定義

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

通過粘合redtree和其他函數能夠定義出許多有意思的函數。例如，所有數中的數字标簽能

夠通過這個加起來

sumtree = redtree add add 0

拿前面我們寫下的tree作為例子，sumtree給出

add 1

   (add (add 2 0)

        (add (add 3

                 (add (add 4 0) 0))

            0))

= 10

tree中所有label的list能夠用這個計算

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的函數來把函數f應用于tree中的所有label：

maptree f = redtree (node . f) cons nil

所有這些能夠做到，是因為functional語言允許在傳統程式設計語言中不可再分的函數用部件

的組合的形式表示——higher order函數和一些特制的函數。一旦定義了，這樣的higher

 order函數使得許多操作能夠很容易的編制出來。無論何時定義了一個新的資料類型，就

應當寫higher order函數來處理它。這使得容易操作資料類型，而且隐藏了它的實作細節

。和傳統程式設計的最好類比是可擴充語言——它是一種能夠在需要的任何時候用新的控制結

構擴充的程式設計語言。