-
樓主 / webdriver
- 時間: 2014-10-17 13:14
-
-
- 時間: 2014-10-17 13:43傻瓜函數式編程
2006年6月19日，星期一
開篇
我們這些碼農做事都是很拖拉的。每天例行報到後，先來點咖啡，看看郵件還有RSS訂閱的文章。然後翻翻新聞還有那些技術網站上的更新，再過一遍編程論壇口水區裡那些無聊的論戰。最後從頭把這些再看一次以免錯過什麼精彩的內容。然後就可以吃午飯了。飯飽過後，回來盯著IDE發一會呆，再看看郵箱，再去搞杯咖啡。光陰似箭，可以回家了……
（在被眾人鄙視之前）我唯一想說的是，在這些拖拉的日子裡總會時不時讀到一些不明覺厲的文章。如果沒有打開不應該打開的網站，每隔幾天你都可以看到至少一篇這樣的東西。它們的共性：難懂，耗時，於是這些文章就慢慢的堆積成山了。很快你就會發現自己已經累積了一堆的收藏鏈接還有數不清的PDF文件，此時你只希望隱入一個杳無人煙的深山老林裡什麼也不做，用一年半載好好的消化這些私藏寶貝。當然，我是說最好每天還是能有人來給送吃的順帶幫忙打掃衛生倒垃圾，哇哈哈。
--- 太形象了 （讀者評）
我不知道你都收藏了些什麼，我的閱讀清單裡面相當大部分都是函數式編程相關的東東：基本上是最難啃的。這些文章充斥著無比枯燥的教科書語言，我想就連那些在華爾街浸淫10年以上的大牛都無法搞懂這些函數式編程（簡稱FP）文章到底在說什麼。你可以去花旗集團或者德意志銀行找個項目經理來問問1：你們為什麼要選JMS而不用Erlang？答案基本上是：我認為這個學術用的語言還無法勝任實際應用。可是，現有的一些系統不僅非常復雜還需要滿足十分嚴苛的需求，它們就都是用函數式編程的方法來實現的。這，就說不過去了。
關於FP的文章確實比較難懂，但我不認為一定要搞得那麼晦澀。有一些歷史原因造成了這種知識斷層，可是FP概念本身並不難理解。我希望這篇文章可以成為一個“FP入門指南”，幫助你從指令式編程走向函數式編程。先來點咖啡，然後繼續讀下去。很快你對FP的理解就會讓同事們刮目相看了。
什麼是函數式編程（Functional Programming，FP）？它從何而來？可以吃嗎？倘若它真的像那些鼓吹FP的人說的那麼好，為什麼實際應用中那麼少見？為什麼只有那些在讀博士的家伙想要用它？而最重要的是，它母親的怎麼就那麼難學？那些所謂的closure、continuation，currying，lazy evaluation還有no side effects都是什麼東東（譯者：本著保留專用術語的原則，此處及下文類似情形均不譯）？如果沒有那些大學教授的幫忙怎樣把它應用到實際工程裡去？為什麼它和我們熟悉的萬能而神聖的指令式編程那麼的不一樣？
我們很快就會解開這些謎團。剛才我說過實際工程和學術界之間的知識斷層是有其歷史原因的，那麼就先讓我來解釋一下這個問題。答案，就在接下來的一次公園漫步中： -
-
- 時間: 2014-10-17 13:43公園漫步
時間機器啟動……我們來到公元前380年，也就是2000多年前的雅典城外。這是一個陽光明媚的久違的春天，柏拉圖和一個帥氣的小男仆走在一片橄欖樹蔭下。他們正准備前往一個學院。天氣很好，吃得很飽，漸漸的，兩人的談話轉向了哲學。
“你看那兩個學生，哪一個更高一些？”，柏拉圖小心的選擇用字，以便讓這個問題更好的引導眼前的這個小男孩。
小男仆望向水池旁邊的兩個男生，“他們差不多一樣高。”。
“‘差不多一樣高’是什麼意思？”柏拉圖問。
“嗯……從這裡看來他們是一樣高的，但是如果走近一點我肯定能看出差別來。”
柏拉圖笑了。他知道這個小孩已經朝他引導的方向走了。“這麼說來你的意思是世界上沒有什麼東西是完全相同的咯？”
思考了一會，小男孩回答：“是的。萬物之間都至少有一丁點差別，哪怕我們無法分辨出來。”
說到點子上了！“那你說，如果世界上沒有什麼東西是完全相等的，你怎麼理解‘完全相等’這個概念？”
小男仆看起來很困惑。“這我就不知道了。”
這是人類第一次試圖了解數學的本質。柏拉圖認為我們所在的世界中，萬事萬物都是完美模型的一個近似。他同時意識到雖然我們不能感受到完美的模型，但這絲毫不會阻止我們了解完美模型的概念。柏拉圖進而得出結論：完美的數學模型只存在於另外一個世界，而因為某種原因我們卻可以通過聯系著這兩個世界的一個紐帶來認識這些模型。一個簡單的例子就是完美的 圓形。沒有人見過這樣的一個圓，但是我們知道怎樣的圓是完美的圓，而且可以用公式把它描述出來。
如此說來，什麼是數學呢？為什麼可以用數學法則來描述我們的這個宇宙？我們所處的這個世界中萬事萬物都可以用數學來描述嗎？2 數理哲學是一門很復雜的學科。它和其他多數哲學一樣，更著重於提出問題而不是給出答案。數學就像拼圖一樣，很多結論都是這樣推導出來的：先是確立一些互不沖突的基礎原理，以及一些操作這些原理的規則，然後就可以把這些原理以及規則拼湊起來形成新的更加復雜的規則或是定理了。數學家把這種方法稱為“形式系統”或是“演算”。如果你想做的話，可以用形式系統描述俄羅斯方塊這個游戲。而事實上，俄羅斯方塊這個游戲的實現，只要它正確運行，就是一個形式系統。只不過它以一種不常見的形式表現出來罷了。
如果半人馬阿爾法上有文明存在的話，那裡的生物可能無法解讀我們的俄羅斯方塊形式系統甚至是簡單的 圓形的形式系統，因為它們感知世界的唯一器官可能只有鼻子（譯者：偶的媽你咋知道？）也許它們是無法得知俄羅斯方塊的形式系統了，但是它們很有可能知道圓形。它們的圓形我們可能沒法解讀，因為我們的鼻子沒有它們那麼靈敏（譯者：那狗可以麼？）可是只要越過形式系統的表示方式（比如通過使用“超級鼻子”之類的工具來感知這些用味道表示的形式系統，然後使用標准的解碼技術把它們翻譯成人類能理解的語言），那麼任何有足夠智力的文明都可以理解這些形式系統的本質。
有意思的是，哪怕宇宙中完全不存在任何文明，類似俄羅斯方塊還有圓形這樣的形式系統依舊是成立的：只不過沒有智慧生物去發現它們而已。這個時候如果忽然一個文明誕生了，那麼這些具有智慧的生物就很有可能發現各種各樣的形式系統，並且用它們發現的系統去描述各種宇宙法則。不過它們可能不會發現俄羅斯方塊這樣的形式系統，因為在它們的世界裡沒有俄羅斯方塊這種東西嘛。有很多像俄羅斯方塊這樣的形式系統是與客觀世界無關的，比如說自然數，很難說所有的自然數都與客觀世界有關，隨便舉一個超級大的數，這個數可能就和世界上任何事物無關，因為這個世界可能不是無窮大的。 -
- 時間: 2014-10-17 13:43歷史回眸3
再次啟動時間機……這次到達的是20世紀30年代，離今天近了很多。無論新舊大陸，經濟大蕭條都造成了巨大的破壞。社會各階層幾乎每一個家庭都深受其害。只有極其少數的幾個地方能讓人們免於遭受窮困之苦。幾乎沒有人能夠幸運的在這些避難所裡度過危機，注意，我說的是幾乎沒有，還真的有這麼些幸運兒，比如說當時普林斯頓大學的數學家們。
新建成的哥特式辦公樓給普林斯頓大學帶來一種天堂般的安全感。來自世界各地的邏輯學者應邀來到普林斯頓，他們將組建一個新的學部。正當大部分美國人還在為找不到一片面包做晚餐而發愁的時候，在普林斯頓卻是這樣一番景象：高高的天花板和木雕包覆的牆，每天品茶論道，漫步叢林。 一個名叫阿隆佐·邱奇(Alonzo Church)的年輕數學家就過著這樣優越的生活。阿隆佐本科畢業於普林斯頓後被留在研究院。他覺得這樣的生活完全沒有必要，於是他鮮少出現在那些數學茶會中也不喜歡到樹林裡散心。阿隆佐更喜歡獨處：自己一個人的時候他的工作效率更高。盡管如此他還是和普林斯頓學者保持著聯系，這些人當中有艾倫·圖靈、約翰·馮·諾伊曼、庫爾特·哥德爾。
這四個人都對形式系統感興趣。相對於現實世界，他們更關心如何解決抽象的數學問題。而他們的問題都有這麼一個共同點：都在嘗試解答關於計算的問題。諸如：如果有一台擁有無窮計算能力的超級機器，可以用來解決什麼問題？它可以自動的解決這些問題嗎？是不是還是有些問題解決不了，如果有的話，是為什麼？如果這樣的機器采用不同的設計，它們的計算能力相同嗎？
在與這些人的合作下，阿隆佐設計了一個名為lambda演算的形式系統。這個系統實質上是為其中一個超級機器設計的編程語言。在這種語言裡面，函數的參數是函數，返回值也是函數。這種函數用希臘字母lambda（λ），這種系統因此得名4。有了這種形式系統，阿隆佐終於可以分析前面的那些問題並且能夠給出答案了。
除了阿隆佐·邱奇，艾倫·圖靈也在進行類似的研究。他設計了一種完全不同的系統（後來被稱為圖靈機），並用這種系統得出了和阿隆佐相似的答案。到了後來人們證明了圖靈機和lambda演算的能力是一樣的。
如果二戰沒有發生，這個故事到這裡就應該結束了，我的這篇小文沒什麼好說的了，你們也可以去看看有什麼其他好看的文章。可是二戰還是爆發了，整個世界陷於火海之中。那時的美軍空前的大量使用炮兵。為了提高轟炸的精度，軍方聘請了大批數學家夜以繼日的求解各種差分方程用於計算各種火炮發射數據表。後來他們發現單純手工計算這些方程太耗時了，為了解決這個問題，各種各樣的計算設備應運而生。IBM制造的Mark一號就是用來計算這些發射數據表的第一台機器。Mark一號重5噸，由75萬個零部件構成，每一秒可以完成3次運算。
戰後，人們為提高計算能力而做出的努力並沒有停止。1949年第一台電子離散變量自動計算機誕生並取得了巨大的成功。它是馮·諾伊曼設計架構的第一個實例，也是一台現實世界中實現的圖靈機。相比他的這些同事，那個時候阿隆佐的運氣就沒那麼好了。
到了50年代末，一個叫John McCarthy的MIT教授（他也是普林斯頓的碩士）對阿隆佐的成果產生了興趣。1958年他發明了一種列表處理語言（Lisp），這種語言是一種阿隆佐lambda演算在現實世界的實現，而且它能在馮·諾伊曼計算機上運行！很多計算機科學家都認識到了Lisp強大的能力。1973年在MIT人工智能實驗室的一些程序員研發出一種機器，並把它叫做Lisp機。於是阿隆佐的lambda演算也有自己的硬件實現了！ -
- 時間: 2014-10-17 13:43函數式編程
函數式編程是阿隆佐思想的在現實世界中的實現。不過不是全部的lambda演算思想都可以運用到實際中，因lambda演算在設計的時候就不是為了在各種現實世界中的限制下工作的。所以，就像面向對象的編程思想一樣，函數式編程只是一系列想法，而不是一套嚴苛的規定。有很多支持函數式編程的程序語言，它們之間的具體設計都不完全一樣。在這裡我將用Java寫的例子介紹那些被廣泛應用的h函數式編程思想（沒錯，如果你是受虐狂你可以用Java寫出函數式程序）。在下面的章節中我會在Java語言的基礎上，做一些修改讓它變成實際可用的函數式編程語言。那麼現在就開始吧。
Lambda演算在最初設計的時候就是為了研究計算相關的問題。所以函數式編程主要解決的也是計算問題，而出乎意料的是，是用函數來解決的！（譯者：請理解原作者的苦心，我想他是希望加入一點調皮的風格以免讀者在中途睡著或是轉台……）。函數就是函數式編程中的基礎元素，可以完成幾乎所有的操作，哪怕最簡單的計算，也是用函數完成的。我們通常理解的變量在函數式編程中也被函數代替了：在函數式編程中變量僅僅代表某個表達式（這樣我們就不用把所有的代碼都寫在同一行裡了）。所以我們這裡所說的‘變量’是不能被修改的。所有的變只能被附一次初值。在Java中就意味著每一個變量都將被聲明為final（如果你用C++，就是const）。在FP中，沒有非final的變量。
final int i = 5;
final int j = i + 3;
既然FP中所有的變量都是final的，可以引出兩個規定：一是變量前面就沒有必要再加上final這個關鍵字了，二是變量就不能再叫做‘變量’了……於是現在開始對Java做兩個改動：所有Java中聲明的變量默認為final，而且我們把所謂的‘變量’稱為‘符號’。
到現在可能會有人有疑問：這個新創造出來的語言可以用來寫什麼有用的復雜一些的程序嗎？畢竟，如果每個符號的值都是不能修改的，那麼我們就什麼東西都不能改變了！別緊張，這樣的說法不完全正確。阿隆佐在設計lambda演算的時候他並不想要保留狀態的值以便稍後修改這些值。他更關心的是基於數據之上的操作（也就是更容易理解的“計算”）。而且，lambda演算和圖靈機已經被證明了是具有同樣能力的系統，因此指令式編程能做到的函數式編程也同樣可以做到。那麼，怎樣才能做到呢？
事實上函數式程序是可以保存狀態的，只不過它們用的不是變量，而是函數。狀態保存在函數的參數中，也就是說在棧上。如果你需要保存一個狀態一段時間並且時不時的修改它，那麼你可以編寫一個遞歸函數。舉個例子，試著寫一個函數，用來反轉一個Java的字符串。記住咯，這個程序裡的變量都是默認為final的5。
String reverse(String arg) {
if(arg.length == 0) {
return arg;
}
else {
return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1);
}
}
這個方程運行起來會相對慢一些，因為它重復調用自己6。同時它也會大量的消耗內存，因為它會不斷的分配創建內存對象。無論如何，它是用函數式編程思想寫出來的。這時候可能有人要問了，為什麼要用這種奇怪的方式編寫程序呢？嘿，我正准備告訴你。 -
- 時間: 2014-10-17 13:44
-
- 時間: 2014-10-17 13:44單元測試
因為FP中的每個符號都是final的，於是沒有什麼函數會有副作用。誰也不能在運行時修改任何東西，也沒有函數可以修改在它的作用域之外修改什麼值給其他函數繼續使用（在指令式編程中可以用類成員或是全局變量做到）。這意味著決定函數執行結果的唯一因素就是它的返回值，而影響其返回值的唯一因素就是它的參數。
這正是單元測試工程師夢寐以求的啊。現在測試程序中的函數時只需要關注它的參數就可以了。完全不需要擔心函數調用的順序，也不用費心設置外部某些狀態值。唯一需要做的就是傳遞一些可以代表邊界條件的參數給這些函數。相對於指令式編程，如果FP程序中的每一個函數都能通過單元測試，那麼我們對這個軟件的質量必將信心百倍。反觀Java或者C++，僅僅檢查函數的返回值是不夠的：代碼可能修改外部狀態值，因此我們還需要驗證這些外部的狀態值的正確性。在FP語言中呢，就完全不需要。 -
- 時間: 2014-10-17 13:44調試查錯
如果一段FP程序沒有按照預期設計那樣運行，調試的工作幾乎不費吹灰之力。這些錯誤是百分之一百可以重現的，因為FP程序中的錯誤不依賴於之前運行過的不相關的代碼。而在一個指令式程序中，一個bug可能有時能重現而有些時候又不能。因為這些函數的運行依賴於某些外部狀態， 而這些外部狀態又需要由某些與這個bug完全不相關的代碼通過某個特別的執行流程才能修改。在FP中這種情況完全不存在：如果一個函數的返回值出錯了，它一直都會出錯，無論你之前運行了什麼代碼。
一旦問題可以重現，解決它就變得非常簡單，幾乎就是一段愉悅的旅程。中斷程序的運行，檢查一下棧，就可以看到每一個函數調用時使用的每一個參數，這一點和指令式代碼一樣。不同的是指令式程序中這些數據還不足夠，因為函數的運行還可能依賴於成員變量，全局變量，還有其他類的狀態（而這些狀態又依賴於類似的變量）。FP中的函數只依賴於傳給它的參數，而這些參數就在眼前！還有，對指令式程序中函數返回值的檢查並不能保證這個函數是正確運行的。還要逐一檢查若幹作用域以外的對象以確保這個函數沒有對這些牽連的對象做出什麼越軌的行為（譯者：好吧，翻譯到這裡我自己已經有點激動了）。對於一個FP程序，你要做的僅僅是看一下函數的返回值。
把棧上的數據過一遍就可以得知有哪些參數傳給了什麼函數，這些函數又返回了什麼值。當一個返回值看起來不對頭的那一刻，跳進這個函數看看裡面發生了什麼。一直重復跟進下去就可以找到bug的源頭！ -
- 時間: 2014-10-17 13:45並發執行
不需要任何改動，所有FP程序都是可以並發執行的。由於根本不需要采用鎖機制，因此完全不需要擔心死鎖或是並發競爭的發生。在FP程序中沒有哪個線程可以修改任何數據，更不用說多線程之間了。這使得我們可以輕松的添加線程，至於那些禍害並發程序的老問題，想都不用想！
既然是這樣，為什麼沒有人在那些高度並行的那些應用程序中采用FP編程呢？事實上，這樣的例子並不少見。愛立信開發了一種FP語言，名叫Erlang，並應用在他們的電信交換機上，而這些交換機不僅容錯度高而且拓展性強。許多人看到了Erlang的這些優勢也紛紛開始使用這一語言。在這裡提到的電信交換控制系統遠遠要比華爾街上使用的系統具有更好的擴展性也更可靠。事實上，用Erlang搭建的系統並不具備可擴展性和可靠性，而Java可以提供這些特性。Erlang只是像岩石一樣結實不容易出錯而已。
FP關於並行的優勢不僅於此。就算某個FP程序本身只是單線程的，編譯器也可以將其優化成可以在多CPU上運行的並發程序。以下面的程序為例：
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
如果是函數式程序，編譯器就可以對代碼進行分析，然後可能分析出生成字符串s1和s2的兩個函數可能會比較耗時，進而安排它們並行運行。這在指令式編程中是無法做到的，因為每一個函數都有可能修改其外部狀態，然後接下來的函數又可能依賴於這些狀態的值。在函數式編程中，自動分析代碼並找到適合並行執行的函數十分簡單，和分析C的內聯函數沒什麼兩樣。從這個角度來說用FP風格編寫的程序是“永不過時”的（雖然我一般不喜歡說大話空話，不過這次就算個例外吧）。硬件廠商已經沒辦法讓CPU運行得再快了。他們只能靠增加CPU核的數量然後用並行來提高運算的速度。這些廠商故意忽略一個事實：只有可以並行的軟件才能讓你花大價錢買來的這些硬件物有所值。指令式的軟件中只有很小一部分能做到跨核運行，而所有的函數式軟件都能實現這一目標，因為FP的程序從一開始就是可以並行運行的。 -
- 時間: 2014-10-17 13:45熱部署
在Windows早期，如果要更新系統那可是要重啟電腦的，而且還要重啟很多次。哪怕只是安裝一個新版本的播放器。到了XP的時代這種情況得到比較大的改善，盡管還是不理想（我工作的時候用的就是Windows，就在現在，我的系統托盤上就有個討厭的圖標，我不重啟機子就不消失）。這一方面Unix好一些，曾經。只需要暫停一些相關的部件而不是整個操作系統，就可以安裝更新了。雖然是要好一些了，對很多服務器應用來說這也還是不能接受的。電信系統要求的是100%的在線率，如果一個救急電話因為系統升級而無法撥通，成千上萬的人就會因此喪命。同樣的，華爾街的那些公司怎麼也不能說要安裝軟件而在整個周末停止他們系統的服務。
最理想的情況是更新相關的代碼而不用暫停系統的其他部件。對指令性程序來說是不可能的。想想看，試著在系統運行時卸載掉一個Java的類然後再載入這個類的新的實現，這樣做的話系統中所有該類的實例都會立刻不能運行，因為該類的相關狀態已經丟失了。這種情況下可能需絞盡腦汁設計復雜的版本控制代碼，需要將所有這種類正在運行的實例序列化，逐一銷毀它們，然後創建新類的實例，將現有數據也序列化後裝載到這些新的實例中，最後希望負責裝載的程序可以正確的把這些數據移植到新實例中並正常的工作。這種事很麻煩，每次有新的改動都需要手工編寫裝載程序來完成更新，而且這些裝載程序還要很小心，以免破壞了現有對象之間的聯系。理論上是沒問題，可是實際上完全行不通。
FP的程序中所有狀態就是傳給函數的參數，而參數都是儲存在棧上的。這一特性讓軟件的熱部署變得十分簡單。只要比較一下正在運行的代碼以及新的代碼獲得一個diff，然後用這個diff更新現有的代碼，新代碼的熱部署就完成了。其它的事情有FP的語言工具自動完成！如果還有人認為這只存在於科幻小說中，他需要再想想：多年來Erlang工程師已經使用這種技術對它們的系統進行升級而完全不用暫停運行了。
ZT: 傻瓜函數式編程
