?

本文刊發在《程序員》雜志09年第二期上。是討論函數式語言基本性質和發展方向的一篇文章。

?

一、把大象裝進冰箱 ＝＝＝＝＝在命令式語言（當然我們可以確指為C、Delphi、Java或C#等等）中，初學者的第一 個疑難便是這樣的代碼（*注1）：X=X+1為什么？因為在數學概念中，上述等式是不能成立的。這種表達式是計算機的思維邏 輯：當它運算上述表達式（或語句）時，X被作為暫存單元——例如冰箱。為了讓冰箱產 生變化，比如解決“把大象裝進冰箱”這樣的問題，我們需要如下三步：把冰箱門打開，把大象放進去，把冰箱門關上（圖1：“把大象裝進冰箱”的問題）因為我們有兩只手來分別負責拉住冰箱門和大象，所以整個操作過程看起來很完美， 但接下來我們再加上點需求：我們要“把大象拿出來，把長頸鹿裝進去”，怎么辦？是的， 應該這樣：把冰箱門打開，把大象拿出來，把長頸鹿裝進去，把冰箱門關上可惜長頸鹿有腿有思想，所以問題將會出在我們把大象拿出來的那一時刻：長頸鹿跑 掉了。為此，我們必須做很多的防護措施，例如先鎖住長頸鹿，再鎖住大象，以及在整個 過程中，保證冰箱門不會自動關上或打開……而代碼：X=X+1 的執行過程與此類似：當CPU開始存取X這個位置時，它只能在“當前X”與“下一次X” 之間選擇二者之一。當多個線程（或多個CPU）開始存取X這個位置時，如果我們希望得 到相同的X值，那么我們就得在X操作過程中采取象上面一樣的防護措施：加一個鎖。以 保證要求所有線程都取完了這個“當前X”值，才會被切換到“下一次X”值。由于這個限制，一旦多個線程都排著隊來看看這個X的美妙身形，整個隊列就全都慢 下來了。解決這個問題的辦法其實很簡單：只要X可見，我們就永遠不修改這個X。而這，就 是函數式應對大象問題的方法：如果冰箱里放著大象，就永遠不要試圖放長頸鹿。所以在 函數式語言Erlang中的變量一旦賦值，就不能再修改。云風曾在SD2C 2007大會上說：解決問題的最好方法，就是不解決它。這個觀點深得 函數式的精髓。二、帽子戲法的關鍵，在于至少多一頂帽子 ＝＝＝＝＝雜技中的一種常見帽子戲法，是很多人圍成一圈或排成一排然后飛速地傳送手中的帽 子。這如果是一個人來表演，那么應該是左右手各一頂帽子，而多出的一頂則總在頭上。　　 （圖2：帽子戲法）所以，關鍵在于至少要多出一頂帽子。正因為多出來這個帽子，所以我們看到雜技師 在我們面前構建了一個往復不休的循環。事實上程序設計里的“循環”也存在完全相同的 問題：我們至少需要一個變量來保存迭代中的計數，而且這個變量必須是可以修改的(*注 2)。然而這一要求既是玩轉“帽子戲法”的必要條件，卻又與我們上面講過的“不修改變 量”的原則相違背。函數式如何解決這個問題呢？其實答案還是相同的答案：至少多一頂帽子。只不過，帽子不一定要放在頭上，我們 可以把它放在傳遞的過程中——例如空中——就可以了。要知道，讓雜技師用同樣的方法 來擲蘋果，那多出來的一個就總是在空中了。在函數式中，我們如果要構建一個循環，那么可以使用函數遞歸來實現。這上述控制 循環過程的變量，則可以把它放在函數形式參數表——這種類似“空中”的地方。與“空 中”相同的是，我們在靜態看函數時，那是參數表；而運行中時，它傳入實參。然而帽子戲法的表演者并沒有三只手或更多只手，被循環帽子增加的時候，雜技師除 了加快速度之外，保證一個簡單的原則也是極其重要的：總是從帽子隊列的最末端取到下 一只帽子。這一原則保證了可以容納更多帽子，而又不會少處理任何一個。同樣的，遞歸 是消耗棧的，為了使棧空間不爆炸，解決的方法就是在最后一行代碼上調用遞歸，即尾遞 歸。因為尾遞歸的存在，函數最末的調用就可以被優先為一行不消耗棧的跳轉指令，就像 帽子戲法的雜技師從帽子隊列上直接取走輪轉到手邊的帽子一樣。最后，對于一個函數來說，如果它只返回值而不修改函數外的任何東西，那么這個函 數就是安全的，它等價于它返回的這個值——如前所述的，這個值一旦有效（運算出結果 并傳出），就不再變更。所以函數式中的函數調用，可以等價于一個表達式中運算的值。如同函數調用，函數的遞歸也只返回值，所以也等價于一個表達式中運算的值。再進 一步的推論，遞歸實際上等效于循環求值。復雜的表象下，總會有一個簡單的原則。萬人的與一個人的帽子戲法，其原則是一樣 地：至少多一頂帽子，放在頭上，或是空中。三、計算機其實不認得"hello" ＝＝＝＝＝32位的unicode，以及128位的GUID等等，都直接與我們現在或將來的存儲單位以及 運算的通道大小有關。事實上即使我們有128位機器，我們也只打算在這樣的通路上傳送 一個字符"h"——而不是字符串"hello"。從更為準確的角度來說，事實上計算機也不認得字 符"h"，而只認得數字0x68。同樣的，它也不認得所謂的“真假(true/false)”，而只認得數字 的1/0。（圖3：圖靈機的概念圖）我們編程的本質，其實不過是在求值一些數字而已。只是最終我們在自然語義上把這 些數字的一個連續或非連續的集合認為是布爾值、字符串、數組或對象。當我們認識到運 算求值的結果無非是數值，而表達形式又無非是連續或非連續時，我們就得到了基本的數 據抽象單元：值、值系列。再加上我們前面講到的執行體（函數），我們就得到了整個函數 式語言的鼻祖——LISP——的基本運算模型：(+ Xn)其中，“( )”表明一個值系列（表），而“+”在這里指代某種運算，Xn表明值（或值 系列）。整個的表返回一個值，因此也可以將“整個的表（通常這里稱為表達式）”等義為 一個值。任何的一個運算，最終輸出的仍然只是一個或一系列數字，它被顯示在屏幕上， 便成了文本；放在內存中，便成了數據。當然，現實是這樣的機器最終從科學領域走向了民用，在PC（個人計算機）普及的現 在，我們也需要讓類似LISP這樣的——絕對正確而又絕對非人性的——語言變得親切一 些。于是稍微復雜而有用一點的函數式語言，例如Erlang，通過豐富了上述的基本運算模 型來使我們的視覺愉悅，或是在討論它的代碼時顯得神經（略為）正常一些：（表一：以Erlang為例的、簡單的類型抽象）而我們逆推一份具體的Erlang代碼，其實仍然可以表達為上述的(+ Xn)。例如我們可 以在Erlang代碼在編譯階段使用解析樹（Abstract Form）中看到這樣的抽象代碼（abstract code）： [{abstract_code,{raw_abstract_v1, [{attribute,1,file,{"./simplest.erl",1}}, {attribute,1,module,simplest}, {function,3,test,0,[{clause,3,[],[],[{atom,4|...}]}]},{eof,1}]}}] 無論是從形式，還是從實質來看，這種解析樹（在erlang執行中將會按照解析樹來生 成語法樹并執行）與LISP語言的基本原則都是一致的。四、從“函數等義于值”到“函數是值” ＝＝＝＝＝現在，JavaScript語言被更為深入的挖掘并漸漸了解到它的函數式語言本質，而類似 Erlang這樣的“天生傷害人的視力”的語言也移步前臺。這些語言的努力，使我們終于看 到一個屬于函數式語言的時代的曙光。在黎明之前的黑暗中，函數式以它諸多的、最不可 思議的特性迷惘著程序員的目光。連它最基本的概念說明，也如同玄學家的囈語：如同數 學函數是集合A（稱為定義域）中成員到集合B（稱為值域）中成員的映射，函數式語言 就是通過數學函數的定義、應用的說明和求值完成運算過程的。類似于這種等同于“什么也沒說”的解釋，其實的確是在闡述函數式語言的精髓。為 了減輕你的痛苦（但絕非輕視你的智商），我通常換個說法來陳述它們：如果表達式“1+1=2” 中的“+”被理解為求值函數，那么所謂函數式語言，就是通過連續表達式運算求值的語言； 既然上面的表達式可以算出結果“=2”，那么函數式語言自然也可以通過不停地求值找到問 題的答案。首先，在函數式語言中，函數只表明一個運算過程，并產生一個運算結果。這與表達 式中的運算符具有完全相同的性質——所以事實上一個函數式語言中，表達式的運算符被 實現為一個函數。例如erlang的核心模塊中，可以導出類似這樣的函數：（表二：Erlang中的運算符其實對應于內核函數－部分舉例）所以，函數式語言的本質是表達式/函數的“連續求值”。既然我們的輸出或存儲最終 只是在關心“值”，那么顯然連續求值的結果就可以直接作為他們的輸入。如果把輸出終端 或存儲看成接受輸入的設備，那么他也相當于一個函數；如果一臺計算設備只對外界表達 為一個或一系列輸出，并接受來自其他類似設備的輸入，那么計算設備本身也可以視為一 個函數……我們將這個過程放大，其實網絡可以是函數式的。這個就是著名的語用網，它的理論 基礎是petri網論（Petri nets theory）。而事實上，作為計算模型來理解，它與函數式語言是 相似、等價的（*注3）。圖4：perti網的“庫所變換”函數式語言通過函數實現了三個基本的運算邏輯（順序、分支與循環），因此它與我們 常用的命令式語言是等價的(*注4)。但是由于存在存儲問題，所以命令式語言是時序相關 的——即有存取某個存儲單元的先后問題。而函數式語言由于“把大象裝進冰箱”之后就 再也不可更改，因此變得時序無關。以上述的petri網的例子來講，由于時序無關，所以圖左側的“庫所（圓圈）”中的兩 個“消息（黑點）”分解成右側的兩個庫所來處理時，其轉換的代價為0（無鎖），而這個 過程應用在多核機器或分布式網絡上時，效率卻提高了一倍。更深層次地思考這個問題，由于在計算機系統中函數本身仍然是以數據形式存儲的， 所以函數事實上也是“被運算的對象”和“運算結果”。函數的這種特性被稱為高階函數。 “函數等義于值”是函數式的基礎，而“函數是值”，則是高階函數的基礎。圖5：JavaScript統一語言范型的基本模型（*注5）當“函數是值”時，我們可以把一個函數傳遞到另一個地方去運算，而其運算結果仍 然是值，所以可以把一個等義的結果再傳回來。注意這一過程，就是分布運算的實質，所 以，函數式在本質上、天生地就是支持分布運算的。無論我們是將“一段函數式代碼”所 表達的整個運算過程分解成何種形式，并分布在何種復雜的運算環境或網絡環境中，只要 最終在邏輯上它能得到一個值序列和一個運算，就能夠成為更大范圍的分布網絡中的一個 結點。而這，就是整個計算世界的全部（注6）：(symbol)。 ＝＝＝＝＝＝＝＝＝＝注1：《Erlang程序設計》中，作者以這個例子為起始，來講述Erlang變量的單一賦值。注2：參見《結構程序設計》，討論“如何刻畫計算的進展”時，作者E.W.Dijkstra說： （程序）如果含有循環語句，僅用語法指示器就不能描述計算的進展了……（而應該）引 進一個“動態指示器”毫不含糊地累計相應的現行循環的序數……因為，語法指示器無法 充當這種坐標系統的一個組成成分。注3："Implementing Coloured Petri Nets Using a Functional Programming Language" at http://portal.acm.org/citation.cfm?id=993039，and Functional Nets at http://lamp.epfl.ch/fn/注4：不同范型的計算機語言之間等價問題，可以歸結到圖靈等價這個命題上，這意 味著該運算系統或模型能夠執行任何復雜程度的、圖靈機可完成的數學運算。2007年，Alex Smith證明了Wolfram提出了最小的“2,3圖靈機（兩種顏色，三種狀態）”模型是最小完 備的圖靈等價系統。注5：這個統一過程用到了多項與函數式相關的基本設定：函數是執行體、函數等義 于值、函數是值。注6：與“(+ Xn)”比較，這個表達式認為“運算 +”——也就是某個函數——其實也 是值，因此它也是“值系列”Xn中的一個部分。于是，當由自然語義中的symbol來指代 Xn時，整個表達式就變成了：(symbol)。建議閱讀作者的其它兩篇文章：《從表達式到變量：一行scheme代碼之所見》http://blog.csdn.net/aimingoo/archive/2007/02/12/1508118.aspx 《從表達式到函數：表面的簡潔》http://blog.csdn.net/aimingoo/archive/2007/10/08/1815379.aspx

轉載于:https://www.cnblogs.com/encounter/archive/2009/04/22/2188605.html

總結

以上是生活随笔為你收集整理的表面的简洁的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。