|
2002 年 9 月 09 日
這是本系列中的第二篇文章。在上一篇文章中，可以說我們從高空鳥瞰了 O‘Caml程序設(shè)計語言中的一些顯著特征。包括 O‘Caml 的跨平臺特性，它在程序語言家族的族譜中的位置，它的 geeky factor，以及它所提倡的 Functional 程序設(shè)計方式。在本篇文章中，我們將要靠近一些，更加仔細的看一看 O‘Caml 中這個重要的程序設(shè)計方式，F(xiàn)unctional 程序設(shè)計。
1 前言
讓我們引用著名的計算機科學家 Alan J. Perlis 為美國麻省理工學院 的程序設(shè)計入門課程的經(jīng)典教材《計算機程序的結(jié)構(gòu)及其解釋》一書所著的序言，來開始我們今天對 O‘Caml 以及 Functional 程序設(shè)計方式的介紹。
"我認為有一件事對于我們這些從事計算機科學的人特別的重要，那就是我們應(yīng)該讓計算始終保持有趣。在剛開始的時候，計算是非常有趣的。當然，這讓那些付了錢的顧客不時的感到不太滿意。終于沒過多久，我們就開始正經(jīng)八百的對待他們的抱怨了。我們漸漸開始覺得我們應(yīng)該對這些機器成功、無錯的運行負起責任，我們應(yīng)該好好的使用它們。我不認為我們應(yīng)該如此。我認為我們應(yīng)該折騰這些機器，帶它們進入新的領(lǐng)域，讓屋子里始終環(huán)繞著有趣的氛圍。我希望計算機科學這個領(lǐng)域永遠不要失去它尋找樂趣的本領(lǐng)。無論如何，我希望我們不要變成傳教士。不要弄得好象你是在推銷紅寶書。這個世界上這種人已經(jīng)太多了。關(guān)于計算方面，你所知道的，別人會學會的。不要覺得好象通往成功計算的大門鑰匙掌握在你的手里。在你手里的，我想，我也這樣希望，是智慧：比你第一次被領(lǐng)來看到這些機器時，更深入的了解它們，而且你還可以讓這個認識更加的深入。"
這篇文章的目的就是帶大家進入 Functional 程序設(shè)計這一有趣的領(lǐng)域。
2 作為第一等公民的函數(shù)數(shù)據(jù)類型
Functional 程序設(shè)計的最吸引人注意的地方在于，"函數(shù)"現(xiàn)在可以被當作像整數(shù)（int）和浮點數(shù)（float）一樣的數(shù)據(jù)類型。這就是說，我們可以把函數(shù) func 賦值給一個變量；可以從子程序返回一個函數(shù)，就跟返回一個浮點數(shù)一樣的容易；兩個函數(shù)可以進行復(fù)合運算，就像兩個整數(shù)可以進行加減乘除運算一樣。我們將看到，在 Functional 程序設(shè)計里面，"函數(shù)"被提升為程序設(shè)計語言中的第一等（First Class）的公民，使用"函數(shù)"可以像使用整數(shù)和浮點數(shù)或者是字符串一樣的隨心所欲；不再象過去，函數(shù)只能被調(diào)用，沒有其它的花樣。
"函數(shù)"被提升成第一等的公民以后，引起了一連串的連鎖反應(yīng)。我們可以觀察到，過去，調(diào)用一個子程序，子程序必須完成一定的計算效果，然后把計算的效果通過一定的辦法返回給調(diào)用者。這個返回計算效果的辦法，通常就是設(shè)置一個全局變量，或者是一個大局部的變量。而現(xiàn)在，由于可以把子程序的計算效果通過返回一個"函數(shù)"傳遞回調(diào)用者，我們可以不用設(shè)置全局變量了。那么，設(shè)置全局變量，和不設(shè)置全局變量而傳遞一個函數(shù)，這兩種返回子程序計算效果的辦法，這個區(qū)別是不是很重要？還是只是一個玩意兒而已呢？由于設(shè)置了全局變量（或者是一個大局部的變量），調(diào)用子程序之后再往下的計算過程，要根據(jù)全局變量的值做不同的反應(yīng)，而全局變量往往離發(fā)生效果的代碼段"距離"很遠。這就帶來這樣一個難過的事情，由于任何一個程序員的注意力都不可避免的是局部的，這樣的話，程序中的一段代碼，每次運行都會根據(jù)"遙遠"的全局變量，執(zhí)行出難以預(yù)料的不同結(jié)果。這就使得調(diào)試這樣的程序變得相當?shù)馁M力。
反過來看 Functional 的程序設(shè)計方法，它把一個子程序的計算效果累積在一個函數(shù)里面，然后把這個函數(shù)返回給調(diào)用者，可以做到不用設(shè)置全局變量。這樣使得調(diào)用者在繼續(xù)往下計算的時候，它的計算只和傳遞回來的這個"函數(shù)"有關(guān)，而不會受到代碼中"遙遠"的其它地方的變量值的影響。影響 Functional 程序中代碼執(zhí)行效果的因素，一是程序代碼本身，二是輸入數(shù)據(jù)。而且這兩個因素都是局部的，在程序員的注意力范圍之內(nèi)。當從代碼段中不同的地方，用同樣的輸入數(shù)據(jù)調(diào)用同一段代碼的時候，得到的輸出是一模一樣的。這就是所謂的"Referential Transparency"，它的主要好處是，讓代碼調(diào)試變得相對簡單了。
如果一門程序設(shè)計語言，只允許上面說的 Functional 的調(diào)用子程序的方法，也就是說，它不允許你設(shè)置各種各樣的全局或者是局部的變量，也就是說，如果它不允許邊界效應(yīng)（side effects），那么這門編程語言就叫做是 Pure 的、純粹的 Functional 編程語言。我們所要關(guān)心的 O‘Caml 并不是 Pure 的，所以在 O‘Caml 里面可以混合這兩種編程方式。讀者朋友們不免要問，如果上面說的 Functional 的方式好，那怎么還要抓住"不好"的方式不放呢？這個問題是很難回答的，像 Pure 的 Functional 編程語言，有 Haskell 和 Clean 等，不那么 Pure 的有 Lisp 和 O‘Caml 等。上面說的 Pure 的好處是真的，但是編程的時候要考慮許多事情，Referential Transparency 只是一個方面，比如我要編寫一個有限狀態(tài)自動機的程序，用 Pure Functional 的程序設(shè)計方式就有些難過了，因為，畢竟給變量設(shè)置不同的值，這是編寫一個有限狀態(tài)自動機的很自然的方式。如果不允許設(shè)置邊界效應(yīng)，只允許數(shù)據(jù)在沒有邊界效應(yīng)的管子（子程序）里流進流出，這樣要表達出自動機的狀態(tài)，就比較難過了。
3 模式與 Functional 編程，一個例子
上面講了 Functional 程序設(shè)計中，"函數(shù)"可以被當作程序設(shè)計語言中第一等的公民來對待，就像 int 和 float 一樣。下面，我們將通過一個例子，來看看這個概念是否真的是程序設(shè)計中的一個利器，還是說，這個概念只是說著玩玩，讓人徒傷腦筋而已。
1: $ ledit ocaml
2: Objective Caml version 3.06
3: # let rec sum lst =
4: match lst with
5: [] -> 0
6: | head :: tail -> head + sum tail ;;
7: val sum : int list -> int = <fun>
8: # sum [ 1; 2; 3 ] ;;
9: - : int = 6
|
上面是一個在 BASH Shell 下面交互式的執(zhí)行 O‘Caml 的一個屏幕快照。第一行的"$"是 BASH Shell 命令提示符；ledit 是 O‘Caml 的一個行編輯程序，用 ledit 來執(zhí)行 ocaml 就可以獲得行編輯的一些功能，這是運行交互式的 ocaml 的時候，必不可少的一個工具。下面幾行中的"#"是 O‘Caml 的命令提示符，提示你輸入新的 O‘Caml 語句。上面的第二行打印出 O‘Caml 的一個簡單的 Banner，可以看到 O‘Caml 的全稱是 Objective Caml，這個 3.06 版本是這個月剛剛推出的，就在本系列文章的第一篇和這個第二篇之間，O‘Caml 已經(jīng)連續(xù)推出了 3.05 和 3.06 兩個版本。上面的第三行，let rec sum lst 定義了一個函數(shù)，名為 sum，接受一個參數(shù)，記為 lst。在上面的 let 關(guān)鍵字后面的 rec 關(guān)鍵字，意思是 recursive，表示我們定義的這個 sum 函數(shù)，將要采用一個遞歸的定義，也就是說，在 sum 的定義中，我們將要調(diào)用 sum 本身。這里的 sum 函數(shù)是一個簡單的求和的函數(shù)，它把一個 list 類型的變量，我們這里記為 lst，其中的各個項加起來，求和。
上面的第四行，match lst with，這里面 match 和 with 是關(guān)鍵字。這是 Functional 編程的一個有趣的風格，即大量的采用模式匹配的方法來寫程序。（不過，本節(jié)標題中所說的模式并不是指這個，我們下面將會看到。）這個模式匹配的編程風格，很像 C 語言里面的 switch 和 case。這里的 match lst with，可以想象成就是 C 語言里面的 switch (lst)。第五行的 [] ->0，其中的 [] 表示一個空的 list。翻譯成類似 C 語言的語法，就是 case [] : 0; break; 意思是，如果 lst 是一個空的 list 的話，這個 sum 函數(shù)就返回 0。第六行的 | head :: tail ->head + sum tail ;; 開頭的豎杠是或者的意思，也就是另開一個 case。這個 case 是什么樣的呢？我們要先看看 list 這個數(shù)據(jù)類型是怎么回事。
一個 list 就好像是一個鏈表，在 O‘Caml 里面，list 中的每個元素都必須是同一種類型。比如：
# let lst = [ 1; 2; 3 ] ;;
val lst : int list = [1; 2; 3]
|
這里就定義了一個元素為 int 類型的 list 數(shù)據(jù)，名為 lst，它的第一個元素是 1，然后是 2 和 3。
# 0 :: lst ;;
- : int list = [0; 1; 2; 3]
|
上面的 :: 是一個構(gòu)造 list 的操作符，0::lst 把一個新的元素 0 加到一個 list 類型的數(shù)據(jù) lst 前面，于是就返回一個新的 list 類型的數(shù)據(jù)。這個新的 list 類型的領(lǐng)頭的元素現(xiàn)在是 0 了，它后面跟了一個 list 是 [ 1; 2; 3 ]，而這個 [ 1; 2; 3 ] 又是怎么個一回事呢？
# 0 :: 1 :: 2 :: 3 :: [] ;;
- : int list = [0; 1; 2; 3]
|
這里，我們就看到 list 數(shù)據(jù)類型的本質(zhì)了。我們用 list 構(gòu)造操作符 ::，從 0，1，2，3 四個元素和一個空的 list 構(gòu)造出了跟上面的一個一模一樣的 list。原來 O‘Caml 里面的一個 list 又有點像 C 語言里面的單向鏈表，又有點像 C 語言里面的以 NULL 字符作為結(jié)尾標記的字符串。結(jié)合上面的幾段文字的分析，我們看到，這里的這個 list [0; 1; 2; 3] 它的領(lǐng)頭的元素是 0，后面跟著一個 list [1; 2; 3]，而這個 [1; 2; 3] 它的領(lǐng)頭元素是 1，后面跟著 list [ 2;3 ]，這又是領(lǐng)頭的元素 2 后面跟著 [3] 這個單元素的 list，而這個單元素的 list 其實是領(lǐng)頭的 3 后面跟著一個空的 list []，這個空的 list 才表示這整個 list 的結(jié)尾。我們在對 list 數(shù)據(jù)類型有了這樣的一個了解之后，接下來繼續(xù)回到我們的 sum 函數(shù)。
我們看到第六行的 | head :: tail ->head + sum tail ;; 在豎杠后面的 head :: tail 這個模式匹配了我們關(guān)心的 sum 函數(shù)的變量 lst 不是一個空的 list 的情況。我們知道，變量 lst 或者為空，那么第五行的 [] ->0 給出了 sum 函數(shù)的返回值；或者 lst 不為空，那么它的構(gòu)成必然是這樣的：一個領(lǐng)頭的元素，后面跟著一個 list 類型的數(shù)據(jù)。這里，我們就把這個領(lǐng)頭的元素匹配成，或者說叫做命名成 head，而把后面跟著的 list 匹配成 tail。也就是說，如果 sum 函數(shù)的變量 lst 不是一個空的 list 的話，sum lst 其實就是 head 加上 sum tail。這樣，我們就定義完成了我們的 sum 求和函數(shù)。上面程序的第八行做了一個簡單的測試，果真得到了預(yù)期的結(jié)果。
這個小函數(shù)的定義，我們首先看到"遞歸"是一個強有力的工具，似乎還沒有開始編程序，程序就已經(jīng)編好了。我們還看到，模式匹配 match something with 是 Functional 程序設(shè)計里面使用很廣泛的一種風格。這個模式匹配要遠遠超出 C 語言里面的 switch () 語句。但是這里的這個模式匹配，并不是本節(jié)的小標題所要說的模式，我們下面就來看看本節(jié)真正的想要說的模式是怎樣的。
我們?nèi)绻毿挠^察，就會發(fā)現(xiàn)，上面定義的這個求和函數(shù)，它把一個 list 拿過來，為 list 為空的情況定義一個返回值；然后，在 list 不為空的情況下怎么辦呢？它使用了一個二元操作符，就是加法來處理。這就是我們所要說的模式。這個模式雖然簡單，但顯然是很有用的。如果這個 list 是一個字符串的 list 的話，我們可以用這個模式把 list 里面的各個字符串元素串在一起，連成一個大字符串。如果我們不求和，而要求乘積，這真是手到擒來。如果我們可以定義復(fù)雜的二元操作符，那么顯然這個模式可以幫助我們完成復(fù)雜的 list 操作。但是，我們是不是每次要用到這個模式的時候，都要寫上像前面的 sum 函數(shù)的定義一樣那一大堆東西呢？如果是那樣的話，即使我們注意到了這個模式，事實上也沒有什么大的幫助。好在 Functional 程序設(shè)計可以把函數(shù)提到第一等公民的地位上來，我們來觀察一下，看看有沒有什么辦法。
我們首先觀察到，這個模式的有效輸入，其實只有兩個東西，一是在 list 為空的情況下的返回值，二就是在 list 不為空的情況下，使用哪一個二元操作符。事實上，如果把我們的模式定名為 pat 的話，我們希望把 sum 求和函數(shù)用一句話就寫出來，就是 let sum = pat add 0 ;; 這樣的話，我們關(guān)于這個模式的知識，就濃縮在 pat 這個函數(shù)的定義里面了。由于 Functional 程序設(shè)計里面函數(shù)被提高到最高的地位上，所以上面的這個 pat 才可以實現(xiàn)。它可以接受一個函數(shù)（add）作為參數(shù)，而它的返回值也可以是一個函數(shù)（sum）?？磥?，F(xiàn)unctional 程序設(shè)計還是有點特別嘛！下面，我們就來看看如何定義這個 pat 函數(shù)。
# let rec pat func value lst =
match lst with
[] -> value
| head :: tail -> func head (pat func value tail) ;;
val pat : (‘a(chǎn) -> ‘b -> ‘b) -> ‘b -> ‘a(chǎn) list -> ‘b = <fun>
|
上面定義了 pat 這個函數(shù)。這個函數(shù)的定義過程很簡單，就是把上面的 sum 函數(shù)的定義照葫蘆畫瓢一番，凡是遇到 sum 的地方，就換成 pat func value 就成了。這樣一來，我們就把我們從 sum 的函數(shù)定義中觀察到的一個簡單的設(shè)計模式，濃縮到了 pat 這個函數(shù)的定義里面來了。如果現(xiàn)在再要我們來定義一個求和函數(shù)的，我們只需要提供一個加法的二元操作符，再提供一個初始值就可以了。這個初始值是 0；而這個二元操作符的定義如下：
# let add a b = a + b ;;
val add : int -> int -> int = <fun>
|
下面，我們使用這個二元操作符，以及我們的 pat 函數(shù)，來重新定義一個求和函數(shù)。
# let patsum = pat add 0 ;;
val patsum : int list -> int = <fun>
# patsum [ 1; 2; 3 ] ;;
: int = 6
|
測試的結(jié)果正如我們的所料。下面再來看另一個例子。先定義一個二元操作符：
# let dup a b = a * 2 :: b ;;
val dup : int -> int list -> int list = <fun>
|
然后用初始值 [] 和上面定義的二元操作符 dup 來定義我們的翻倍函數(shù)：
# let patdup = pat dup [] ;;
val patdup : int list -> int list = <fun>
|
測試：
# patdup [ 1; 2; 3 ] ;;
- : int list = [2; 4; 6]
|
這個例子定義了一個新的函數(shù)，它把 [1;2;3] 中的每個元素翻倍變成了 [2;4;6]。我們注意到，這也是一個有用的模式，但是像上面那樣使用前面定義的 pat 函數(shù)來完成，顯然并不漂亮，上面的那個二元操作符的定義也很不自然。我們希望，像前面定義的 pat 一樣，把這個新發(fā)現(xiàn)的模式也用一個函數(shù)來濃縮起來。
# let pat2 func lst =
let op1 a b = func a :: b in
let op2 = pat op1 [] in
op2 lst ;;
val pat2 : (‘a(chǎn) -> ‘b) -> ‘a(chǎn) list -> ‘b list = <fun>
|
這個第二個模式，它接受的參數(shù)只有兩個，第一個是一個一元函數(shù)，第二個是一個 list。這第二個模式干的事情，就是把這個一元函數(shù)用到 list 里面的每個元素的身上，然后返回一個新的 list。下面我們來看看如何使用這個模式。先定義一個一元函數(shù)：
# let duplicate a = a * 2 ;;
val duplicate : int -> int = <fun>
|
然后，把這個一元函數(shù)用到模式二的頭上，來重新得到我們前面的把 [1;2;3] 變成 [2;4;6] 的函數(shù)：
# pat2 duplicate [1; 2; 3] ;;
- : int list = [2; 4; 6]
|
上面的兩個模式，在 functional 程序設(shè)計里面，被濃縮成了兩個函數(shù)。而之所以能夠做到這一步，這是因為在 functional 程序設(shè)計里面，函數(shù)被提升成了程序設(shè)計語言里面第一等的公民，可以被傳遞，可以被賦值。我們看到，程序設(shè)計語言里面一個粗看起來不明所以的特征，經(jīng)過一些探究，竟帶給我們一些意想不到有趣效果。
4 小結(jié)
學習一門新的編程語言，重要的學會這門程序語言帶來的新的程序設(shè)計方式。當你真正的學會了這些新的程序設(shè)計方式的時候，你可以丟開這門剛剛學會的程序語言，換回你原先熟悉的一門編程語言。在這門你早已經(jīng)學會的程序語言里面試一試你剛剛學會的這些新的程序設(shè)計方式。這樣你就會了解這門新的編程語言提供的這些抽象到底是怎么一個玩意兒。這門新的編程語言在后臺默默的為你做了哪些事情。你也就會了解它為你做的這些事情在什么時候會是你真正需要的，在另外一些場合又有可能你會不太需要它為你做的這些事情。直到你可以把程序設(shè)計方式從編程語言里面剝離出來以后，你才算真正的理解了這門新的編程語言。請讀者朋友們記住，僅僅知道一門編程語言的語法可是萬萬不夠的。
在學會了一門新的程序語言之后，如何判斷付出的努力是否值得呢？你可以想一想這門新的程序語言是否為你帶來了看待計算過程的一個新的角度。我們可以說，程序語言就是對計算過程的一個抽象，不同的程序語言表達的是不同的抽象。你可以嘗試著判斷一下這個新的剛剛獲得的抽象是否足夠有力，是否可以在足夠多的場合應(yīng)用這個抽象。如果學習一門新的編程語言沒有為你帶來任何新的見解，那樣的話，這門新的編程語言對你來說有多大的使用價值，這實在是要打上一個大大的問號的。這種情況的話，十有八九，你原先掌握的編程語言對你來說要更好一些。而另一方面，如果你的確獲得了新的見解，那么這門新的編程語言對你來說就肯定蘊含了有價值的、有趣的技術(shù)。這樣的話，即使你以后一時沒有機會或者沒有可能使用這門新的編程語言，你還可以在被迫使用不合適的程序語言的時候，仍舊使用上合適的抽象、合適的技術(shù)。
在下一篇文章里，我們將要介紹用 O‘Caml 在 Linux 系統(tǒng)上進行編程的一些實際的例子，并看到用 O‘Caml 進行跨平臺開發(fā)的威力。我們的實例將輕易的可以在 Linux 和 Windows 兩個系統(tǒng)平臺上運行。那么，下次再見！
參考資料
- O‘Caml 編程語言的主頁， http://www.
- Harold Abelson and Gerald Jay Sussman,《計算機程序的結(jié)構(gòu)及其解釋》，即著名的 SICP。 http://mitpress./sicp/full-text/book/book.html
- O‘Caml 的參考手冊， http://caml./ocaml/htmlman/index.html
- Haskell 編程語言主頁。Haskell 是紀念邏輯學家 Haskell Curry 的。本系列文章的第一篇里面提到 過 Curry 這個技術(shù)，這個 Curry 也是紀念這位邏輯學家而起的名字。Haskell 同 O‘Caml 不同，是一 門Pure 的 Functional 程序設(shè)計語言。 http://www./
- Clean 編程語言，這也是一門 Pure 的 Functional 編程語言。 http://www.cs./~clean/
- 關(guān)于 Scheme 編程語言，在 http://www./可以找到大量的有用的信息。Scheme 是 Lisp 這一族編程語言中的一種。在 SICP（見上）這本書中，就是使用的 Scheme 編程語言來做的解說。
- Why Functional Programming Matters，水平高的朋友們可以看看這篇 John Hughes 的文章， http://www.math./~rjmh/Papers/whyfp.ps這是本文作者在自學 Functional Programming 的過程中，讀到的最有啟發(fā)的一篇文章。
關(guān)于作者
 |
|
|
|
趙蔚，自由職業(yè)者。歡迎大家通過我的電子郵件 zhaoway@public1.ptt.js.cn和我進行交流，我的興趣包括 Lisp，C++，O‘Caml，Concurrent Clean，Haskell 還有其它的好多編程語言。在編程語言之外，我對 Linux Kernel，OpenGL 和 Quake III 也都頗有興趣。我的網(wǎng)絡(luò)日記位于 http://www./person/zhaoway/。上面列有我在網(wǎng)絡(luò)上發(fā)表的其它的文章。歡迎讀者朋友們批評指教。
|
|
