為甚麼是 Functional Programming?

正在 Midlands Graduate School 2010 上課,想到一些東西寫點輕鬆的。

我第一個學的語言,嚴格講起來應該是小學二年級的 GW-Basic,姊姊正在念高職時,借她的課本來看,稍微玩一下。不過並沒有認真學,到最後電腦只是拿來玩電動而已。在那之後過很久,高中電子辭典有些內建 gw-basic,那時候還稍微記得上課會寫些東西打發時間,但就只是玩玩而已。

接下來因緣際會學了 Python 拿來寫些小東西,一路慢慢學到 C 跟 C++ (大一),這時候對程式語言有個想法,反正會寫了 C 之後,大部分的語言都差不多。大三修程式語言時,雖然稍微提過 Scheme(無型別的 Functional Programming),但那時只覺得礙手礙腳,看不出來有什麼必要,老師也只是丟習題下來,沒解釋太多,而該堂課就一直介紹語言設計的原則,還有如 call-by-value, call-by-reference 這些。

令人驚訝的是,大學畢業等當兵的時期,玩一些 C++ template 的泛型程式設計,以及 meta-programming 的東西,漸漸發現這東西好像以前學的 Scheme,沒有 side-effect 副作用,程式展開的基本技巧是數學歸納法,一層一層的 template 實現,玩到 meta-programming 的時候有 type list 等等奇巧淫技,還可以在 template 裡頭再包一層 template,上網搜尋 functional programming (FP) 跟 C++ template 還真有關係,不過這時候也差不多結束去當兵了。

退伍之後進入中研院,穆信成老師實驗室工作,開始學習 Haskell 跟 Agda,邊看些跟 FP 有關的基礎知識,關於 FP 有幾點是 C\C++ 等 imperative language 等沒有的。

第一個是函數是 first-class object,函數在 Haskell 裡頭就跟其他型別如整數,浮點數等一樣,可以當作參數傳來傳去,所以要寫個函數合成的程序,不過就是

comp :: (a -> b) -> (b -> c) -> (a -> c)
comp f g x = g (f x)

看起來就跟數學函數差不多!

再來是 currying 的部份,正如前面說函數是 first-class object,除了傳參數以外,也可以當作回傳值傳回來,前面的例子的型別其實是

(a -> b) -> ( (b -> c) -> (a -> c))

也就是給定一個函數 f 從 a 到 b,回傳一個函數從 (b -> c) 到 (a -> c),函數的定義域與值域是函數空間 b ->c 跟 a -> c!所以我們可以將原本取多個參數的函數如

(a x b) -> c

取「像是」集合的卡氏積為定義域,其值域是 c,這可以轉成

a -> (b -> c)

也是給定一個元素來自 a ,傳回函數 b ->c。在 C++ 這就沒辦法輕鬆作到了。

再來是沒有副作用,一開始把程式語言的函數看作是數學上的函數,這看起來好像沒什麼問題,但是副作用的存在不能保證每次呼叫的時候,傳回來的東西都會一樣,也就是程序本身,並不是獨立於程式語言其他的部份。所以當程式出錯的時候,得把所有碰到的部份走過一遍,才能確定是哪邊出來問題。我不擅於處理太複雜的東西,所以希望簡化整合程式,用各種方式讓他看起來更有結構些,但這點副作用讓我很為難。

FP 函數沒有副作用,即便要使用變數等,也必須用其他方式明確指出這件事情。所以每次呼叫函數的時候,總是可以確定傳回來的值不會變,也因此要寫對程式,也變得比較容易,或許比較難寫些,但相較於 C\C++ 好寫但容易錯比起來,我寧願多花點時間寫正確的程式。

再來一個優點,則是因為沒有副作用,所以可以把計算過的值記起來,以便下次再呼叫的時候直接拿來用,也就是 lazy evaluation 的精神。這使得在 C\C++ 必須自己做的事情,在程式語言方面可以幫你處理。

最後非常吸引人的是,algebraic data type。例如數學上自然數基本上是定義 0 (anyway, 有時候從 1 開始),或者是其他數字的下一個,也就是一個函數 suc 從自然數到自然數。在 Haskell 中要定義這樣的結構,只要寫

data Nat = zero | suc Nat

中間的 | 代表或者,左邊 zero 只有給一個名稱屬於 Nat;右邊是一個函數 suc 取一個 Nat 當作元素,也是屬於 Nat。類似地,要定義一個串列結構只要寫

data List a = empty | cons a (List a)

小寫的 a 是一個變數,可以是任何的型別,而右邊的 cons 長得跟 suc 有點像,不過它取一個元素來自 a 以及令一個 List a 。這同時也說明了,在 Haskell 要作 C++ template 是非常簡單的,這樣的串列不限於任何型別。我們還有稱為 polymorphic type 的型別,可以對任意的型別操作。

其他有趣的特色,例如更豐富的型別系統,可以透過 Curry-Howard isomorphism 將型別當作邏輯述句,程式本身作為推演的證明。以及更深刻的理論將型別理論連結範疇論,作為範疇論的 internal language。或者給予數學結構,發展程式邏輯(program logic),以及如何說明什麼是正確的程式。而 functional programming 也比 imperative language 適合進行程式推導,說明如何利用之中的代數結構,將程式 A 推導成程式 B 等等。

Advertisements

7 thoughts on “為甚麼是 Functional Programming?

  1. 所以你是先學會 python 的呀… 怎麼學到 python 的呢?

    程式語言應該是很有趣的一門課,但很多人都跟我說上課當時沒感覺,少數人後來會想通一些東西,大多數人被習題折磨一學期後就迫不及待地忘掉了… 可能真的很難教吧?

  2. 哎呀,簡單來說,Python 是在聊天室的朋友推薦的。當初那個時候挺流行 IRC 跟網頁聊天室,有些興趣導向的網站都會有,像是 Linux, 還是以前的 Dearhoney 數位音樂工作室。

    當初也忘了為甚麼想學,朋友推薦了之後買了 O’Reilly 的 Learning Python 就開始一章一章的看,一開始是睡覺前看一章,後面的習題就在腦中想像應該是怎樣,那是大學學測前一個禮拜多,剛好書看完就去考試,考完回來才下載 python 開始練習。

    python 對初學者挺好的,用 interpreter 可以馬上看到輸入的述句結果,又有許多工具可以套用,不需要知道 http protocol 就可以套用 httplib 就可以抓網頁的資料,寫起來很有樂趣。

    後來別人問我學什麼語言好,或者怎麼樣學 C\C++ 這類的問題,我都會說先去學 Python 再回來學 C\C++ 這些。因為這類語言最先遇到的問題都不是程式設計的概念,而是一些環境設定啊,作業系統跟底層的東西。

    就像 pointer 如果不對 heap, memory address 這些有概念,我覺得真的很難學,雖然有些抽象的講法,但到底為甚麼要這些東西,就很難講清楚了。

    可是大部分的人都覺得,我只要學 C\C++, Java 為甚麼要叫我再學一個新的東西?到時候還不是要再回來學?或者是這不是標準答案,覺得很困惑。到最後真的去學 Python 的,我身邊好像只有一個。

    這可能扯到自學這件事情。記得還沒上學的時候,其實是很享受看書的。到了小學每次最期待的,就是到圖書館看書的課,但後來國中老師會為了分數打人的時候就有些厭倦。還好父母不會說些什麼,而且國中接觸網際網路,每件事情都很新鮮,到處看些有的沒的,覺得可以自己找資料學到些東西很有趣。

    而唯一去學 Python 的朋友也是以前就很習慣自己看書,自己學想學的東西。而其他人就我知道,似乎除了課本以外的專業書都不大看。

    • 看每個人遇到的問題以及背景吧!

      像是數學系的話,其實學 Python 或是 Matlab 就能夠得到樂趣玩玩學到的理論。我們那個時候教的是 C++,教了指標啊,物件啊這些東西,大概都用不大到。但現在好多了,改教 Matlab 會比較實用,也比較有趣。雖然從 C++ 可以學到很東西,但對於初學者來說,我覺得還是太多太雜了,再加上語法本身很 tricky,光是賦值動作都有回傳值,或著是轉型的部份,讓人很困惑。

  3. 我大學時系上辦給高中生的電腦營,我一個好朋友負責教程式設計課。他很大膽地主張教 python, 所有工作人員只有他聽過這語言。後來我覺得蠻棒的。學生一般反應還不錯,雖然也有人說因為想學 C++ 才來電腦營的,所以很失望…

    我看你寫「因緣際會」便想,不會這麼巧吧.. 後來算算年齡應該是不可能。 XD

    我學 Haskell 好像還是後來的事情。現在我需要寫小的 imperative 程式作實驗時就用 python…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s