Functional programming

[gracekrcx]

大貓 - 那些函數語言 Tutorial 沒教我的事 [OSDC 2013] 那些函數語言Tutorial沒有教我的事

每次看 10 分鐘，並且把講者的內容打了一遍（暴力學習），之後看了別的文章，有些大大的觀點和此篇有出入，但大方向應該是可以收斂的

programming paradigm

『編程範式』或『程式設計法』。 函數式程式設計（functional programming）、物件導向程式設計（Object-oriented programming）、指令式程式設計（Imperative programming）等等為不同的程式設計法。

Functional programming (wiki)

1. In computer science, functional programming is a programming paradigm
2. avoids changing state and mutable data. 避免更改狀態和可變數據
3. In functional code, the output value of a function depends only on its arguments, so calling a function with the same value for an argument always produces the same result. 函數的輸出值僅取決於其參數
4. 倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導複雜的運算，而不是設計一個複雜的執行過程。

6-22

產生一些懷疑，Functional programing 表示沒有副作用，資料結構是不可變的，就不用擔心執行緒之間可變狀態共享互相影響的情形，和 race condition 的問題，世界真的這麼美好嗎？

*Concurrent：Concurrent 主要是一個 CPU 會去做多件事，但是同一個時間點之內只會做一件事

7-22

Outline

• 函數語言的各種特性
• Pure Function & Side Effect
• Immutable Data Structure
• Conclusion

9-22

函數語言的各種特性  追本溯源，函數語言只有一個重要的特性，First-class Function，意思就是function 可以變成一個變數，function 可以變成一個 function 的參數或是回傳值，function 可以和 function 組合起來。

那什麼樣的語言有這樣的特性呢？ Lisp, Scheme...

C++11, C#3.0, Java8...這些靜態，物件導向的語言，也慢慢的引入這些特質，事實證明，有這些特質，可以用更精簡的方法去描述邏輯。 在學習 Functional programming 時如果可以更了解此特性的本質，再回到指令式語言例如 C++, Ruby，去使用此函式編程也會更得心應手。

常常會聽到因為函數語言是 pure function，沒有 side effect，資料結構不可變，適合作平行運算。但事實上，在語言層面，保證『資料結構不可變』的函數語言是比較少的，例如：erlang, haskell，另外要在語言層面就判別一個 function 是不是 『pure function』也是少數，例如：haskell

haskell 為了在語言層面判斷一個 function 是不是 pure function，用了一些數學方法。

*First-class Function : 當函式在那個語言中可以被視為跟其他的變數一樣時，我們稱那樣的程式語言擁有一級函式。

*Functional programming languages, such as Scheme, ML, Haskell, F#, and Scala, all have first-class functions.

10-22

Side Effect 

沒有副作用：就是沒有輸入輸出，也沒有讀取或是寫入廣域變數的狀態

純函數的好處 如果真的沒有副作用的話，就真的不用擔心跟其他的 thread 有交互的影響，不用擔心 race conditoion 和 lock 的問題

給與相同參數，得到相同結果 有 deterministic 性質，對單元測試有幫助

Pure = deterministic + without side effects A pure function is deterministic.

11-22

所有程式都有 side effect 說一個語言沒有 side effect 很奇怪，因為所有程式都有 side effect

為什麼所有程式都有 side effect ? 執行一個程式你一定是期盼他執行某些事情，例如：修改記憶體狀態，在螢幕上顯示資訊，將結果輸出至檔案，如果你執行一個程式完全沒有 side effect 那個程式應該沒有任何用，因為你看不到他的任何效果

重點 不是「避免副作用」，不是整個語言或是 function 都沒有 side effect，而是區分「有副作用」及「沒有副作用」的 function，因為你的程式一定需要 side efect 去完成它的結果，在完成結果的過程之中，有某些 function 是沒有副作用，有些是有副作用

12-22

舉例：Pure Function - C++

如果輸出結果是寫到某一個檔案，那跟讀取這個檔案的 thread 造成影響，如果我的值是寫到某一個全域變數，那其他讀取這個全域變數的 function 產生交互影響。

那這個例子有沒有符合 pure function 的定義？

1. 給相同的輸入，會有相同的輸出
2. 沒有修改廣域變數

所以，使用指令式語言還是可以實作 pure function 的。

以這個例子來看，現在計算的程式是一個 pure function，我們可以單獨對他進行單元測試，main function 是一個 impure function 他可以完成需要的輸出工作

13-22

舉例：Pure Function - Erlang(single assignment)

erlang 有一個特質是 single assignment，single assignment 是說一個變數只要賦值一次，就沒辦法賦值第二次，也就是一個變數賦值之後就不能更改了

erlang 因為 single assignment 的特性，所以變數被指派之後就不可以被改變，所以在語言層面，可以不用擔心廣域變數被改變，造成 side effect。

但這例子是不是就沒有 side effect，不是喔。這裏的 erlang:display() 是一個會產生 side effect 的操作。 所以還是可以有些 function 可以去做一些 side effect 的事情，例如在 console 去印一些資訊，讀檔寫檔，輸出輸入，或是去存取記憶體裡面的值。

當然我們也可以像 c++ 那樣把程式拆開來，定義一個 pure function 把階層算出來，再定義一個 impure function 把結果 print 出來，把 pure function 和 impure function 分開，pure function 的部分就不會和其他的 thread 互相干擾

erlang 這樣的語言，在語言層式面多了一些保證，就是他保證廣域變數不會造成 side effect，但他還是無法保證你的 function call 不會造成 side effect。

14-22

舉例：Pure Function - Haskell(single assignment & IO Monad)

直接講型別宣告 Haskell 有一個特性，就是型別裡面有 IO 他才有 side effect

如果你看型別裡面沒有 IO，例如 Int -> [Int] ，語言就可以保證說，這個 function 傳入一個 Integer，他會輸出一個 Integer list，語言可以保證一定沒為副作用，如果你試著在 pure function 裡面去執行一個 print 的動作，會在 compiler 時得到一個型別錯誤，所以可以藉由這樣的型別定義，把 pure function 和 impure function 切的乾淨

15-22

所以函數語言沒有副作用？ -> 這句話本身有問題，因為所以的程式都有副作用

函數語言中，所有函數都是純函數？ 這樣的講法太概括了。 大多數的函數語言，都無法保證一個 function 是 pure function，包括 (Ex. Lisp, Scheme, Scala…) ，大多數的語言在語言層面都無法有這樣的保證。

少數語言有單一賦值特性，可避免廣域變數造成副作用。 (Ex. Haskell, Erlang…) 但因為語言有單一賦值的特性，所以你必須用完全不同的方法去寫程式，例如原本用變數，必須用高階函式或是尾端遞迴，去寫程式

更少數的語言，可從型別系統區別純函數與非純函數。(Ex. Haskell…)

使用函數語言就不用擔心副作用的問題了(X)，這個說法太概括了

16-22

Immutable Data structure

常常聽一個點，函數語言中，資料結構是不可變的，所以不用擔心 share mutable state 的問題？？ 使用函數語言，就不必擔心平行程式中，共享可變狀態的問題了？？

17-22

舉例：Immutable Data structure - Java

資料在不同的 thread 被共享，所以希望資料是不可變的，使用 final 宣告。 如果你要做一個加法的運算，你不能修改目前的物件，你要 new 一個新的物件去存你相加之後的結果

舉例：Immutable Data structure - Scala

Scala 號稱是物件導向和函數語言的融合，一個變數用 val 宣告就是不可變的，var 就是可變的

在上述物件導向語言裡面，只要在 constructor 之後，宣告變數不可變，那就會是 immutable 的，這些資料結構在 thread 之間共享的時候，就比較不用擔心值被修改

18-22

舉例：Immutable Data structure - Haskell

Haskell 有一個跟 java, scala 不一樣的地方是，他除了變數是單一指派之外，他的資料結構一但 constructor 之後，也不能改變。 像 java 可以選擇是否使用 final，但 haskell 裡面所有的資料結構，都是一但 constructor 之後就沒法改變，所以如果你要改變一個資料結構，唯一的方法就是 constructor 一個新的資料結構，對需要改變的值做改變，舊的資料就等著他自動 被系統機制垃圾回收。其實 erlang 也是，語言可以保證所有的資料結構都是不可變的。

19-22

Immutable Data structure 小結

將特定資料結構宣告為不可變 (Ex. Scala, Java, C++…)

靠 programer 使用語言特性，像 Scala 把變數印成 val，資料結構就會是 immutable 的，但這並不是函數語言的專利，你在 c++, java 這類的 Imperative 語言（命令式程序設計語言）也可以辦得到

約定與紀律

如果你在開發的文件上註明，這個資料結構，在什麼樣的情況之下，不應該被改變，這樣還是可以擁有 immutable 的資料結構

使用函數語言，就不必擔心平行程式中，共享可變狀態的問題了 (X)

這樣講有點浮誇，因為這不是函數語言的專利

學習函數語言的編程典範，能對純函數、不可變 資料等概念有更透徹的理解 (O)

學習 haskell 這樣的程式語言，常會有綁手綁腳的感覺，你在一個 pure function 要印一個 debug message 都會非常困難，寫久了才會比較容易切分，pure 跟 impure 的邏輯

20-22

Conclusion

現今「函數語言」其實是指很多具有不同特性 的語言，很難一言概括分析。

所以當你聽到有人說，函數語言具有怎麼樣的特性，你都要再仔細思考一下

語言特性帶來的優點（及其代價）

例如 Haskell 可以從型別中區分 pure function，但他的代價是你需要去學習一套新的編成典範，也因為嚴謹性的關係，寫起來會有額外的 cost

編程典範帶來的優點

函數語言還是鼓勵你把 function 寫成 pure function，去學習這些概念，可以學習如何切分邏輯在 pure function 與 impure function。

學習 high order function 的簡化邏輯，以及一些 immutable 的手法

22-22

Q&A

1. 常常聽到函數語言可以怎麼樣，通常都太概括了。
2. HasKell 號稱是一個純函數語言，因為他在語言的層面上面，可以把 pure function 和 impure function 分切開來，但其實講者對『函數語言』的充要條件只有一個，那就是 first class function ，那是不是說 pure functional language 才是真正的 functional language，應該說 pure functional language 只是 functional language 的一個分頁而已
3. 當我們再討論哪一個語言是 functional language 哪一個不是，或哪一個架構才是真的 mvc ，不如換一個方向去討論，這些東西帶給開發上的好處是哪些，好的概念是哪些，然後我們把這些好的用在我們的開發上

[gracekrcx]

Abstract Thinking - 從 Functional Programming 看見程式之美

[gracekrcx]

純粹的好，Pure Function 知道