表面的简洁
?
本文刊發在《程序員》雜志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
總結
- 上一篇: 软件开发质量控制-CMMI读后疑问
- 下一篇: (转)测试用例的设计方法(全)之二 错