Functional Programming for Java Developers 讀書摘要

這是我之前念 Functional Programming for Java Developers 一書的摘要記錄。這本書很薄只有90頁,是一本蠻不錯的 Functional Programming 概念入門勸敗書。

近來 Functional Programming (函數式編程,以下簡稱FP) 的重要性提昇就是為了因應 Concurrency 的需求。CPU 朝向多核架構發展,OOP的程式開發方式物件充滿可變狀態,造成撰寫 Concurrency 程式時陷阱多多。

當然,要寫FP不代表一定要用FP語言,還是可以用現成的OO語言去寫。但就像用沒有OO支援的C去寫OO風格,用專門的FP語言還是比較方便。

為何要FP?

作者說雖然是因為 Concurrency 而學 FP,但是後來卻很享受這種 Paradigm Shift (典範轉移)。OO 被發明因為 GUI,後來人們發現可以用來應用在各種領域上。OO 和 FP 都是工具,各有優缺點,但是現在人們碰到所有問題都用 OO 去解,就像你手上有著搥子,在你眼中什麼都看起來像釘子

FP 不代表比 OO 優越,畢竟 OO 的好處已經被證實且廣泛應用。而是目前時代不同了,OO 的缺點在某些領域已經到了不可忽視的地步,有些挑戰性的問題用 FP 解更為適合,例如:

1. Concurrent

以往我們總是讓最聰明的人去解 Concurrent 問題,小心地注意 Synchronized access to shared。因此絕大部分的開發者不需要煩惱。但是今日CPU多核,Concurrent 需求大增,FP 可以給你正確方式和更高階的 Concurrency 抽象機制來讓這件事更容易。

2. Big data (大部分的程式只是資料處理問題)

當你需要處理 terabytes 等級的資料時,你絕對承受不了 Object 的 overhead,你需要更有效率有最少 overhead 的資料結構跟演算法。ORM 在這問題上是無用的,任何轉換 Relational data 的抽象機制是無用的。FP 可以给你最少的 overhead 來操作這些原始資料,又可以做到 DRY 跟 Reuse 性。用 FP 直接處理原始資料,你不需要 OO 的 overhead。

3. Modular

OO 當初的願景包括 Reusable components,可以直接放到你的 app 中。但是成功的 Library, Framework 案例都是你必須 follow 他們的規則來走,很多 code 還是必須重寫。OO 不算是非常成功在 “Component assembly”
OO 無限制的彈性破壞了 Reuse,因為如何跟一個物件互動的方式太多了。一個系統有好的限制反而比較 Modular,就像 PC 的成功在於 IBM 設計出 PC 架構。Web 的成功在於 HTTP 的簡單協定。

FP 用標準的 List, map, set 來組織資料,FP 的 functions 避免 side effect。去除 dependencies 讓 function 可以在不同 contexts 都可以直接 resue。

4. Work Faster and Faster

今日對於可以快速 deliver 比精確地模型 domain 還重要,因為我們更看重快速修正的能力,一天可以 deployment 好幾次。OO 強調的 object model 能力似乎可以再三考慮了,FP 可以幫助我們有彈性變化的能力。

5. Simplicity

很多OO的複雜性和middleware都是不必要的。FP 返樸歸真更為簡潔。

什麼是FP?

不是有 function 的程式語言就叫做 functional programming language 唷?

最早的 FP 是 Lisp,也是目前第二老的高階程式語言了(Fortran最老),ML family 包括 Caml, OCaml, F#。最 purity 則是 Haskell,近期有 Clojure, Scala 在 JVM 上。

基本原則:

1. 避免 Mutable State

Mutable value 讓 multithreaded programming 變困難。如果可以 immutable,那就不需要 synchronization 了。

另外,程式也更 correctness 正確,特別是在一個大型系統中一個非 locally 的 mutations,要找 bugs 時特別辛苦。

Java 有提供 final,但是這保險卻不夠。因為 final 的 object 還是可以修改!! 例如容器中的元素。沒有 mutable value 之後,FP 提供了其他有效率的方式來操作容器。

不過,還是有部分的 mutability 是無法避免的,例如IO。但是 FP 鼓勵我們思考 Mutable 的必要,將 Mutable 的部份包裝起來,程式其他部分就是 Immutable 安全的。這些需要 Mutable 的部份可以用 STM 或 Actor 來解決 Concurrency 問題。

2. Function 是一級資料, Lambdas 和 Closures, Higher-Order Functions

First-class value 表示可以當成變數(或參數)直接傳遞,方法也不能回傳一個 function,在 Java 中甚至連 class 都不是 first-class。在 Ruby 中 function 和 class 都是。

(method 和 function 的語意有一點差別,前者多半指物件中的方法,後者則比較廣義,不一定綁在物件或類別上。)

Callback method 的情景是最常需要傳遞 function 的地方,Java 用 anonymous inner class 來解決這個問題。不是不行,只是不同 library 的類別(或介面)和要覆寫的 method 命名都不同,每次都要查。如果程式語言支援統一用 function wrapper 就簡潔多了。這種 anonymous function 又叫作 lambda。closure 指的是可以在 function 指涉到外面的變數。在 Java 有限度支援,inner class 中只可以用外面被 final 的變數。

Function 可以回傳 Function 的能力叫做 Higher-Order Functions,在 Java 中只能用 function wrapper 來做了。

3. Side-Effect-Free Function 沒有副作用

不像OO,FP的 function 不論在什麼 context,執行結果都相同。只要參數列相同,不論什麼情況結果都相同(叫做 referential transparency)。

4. Recursion 遞迴

因為要避免 State (loop counter 就是 mutable 變數),所以用遞迴處理迴圈。不過,深度遞迴會造成 stack 過深的效能問題,因此 FP 語言多會支援 tail-call recursion 的能力能將運算自動轉成迴圈。可惜的是 Java 沒有這個能力。

5. Lazy Evaluation

要表示無窮數列,不可能全算出來,lazy evaluation 可以在要的時候再計算。lazy evaluation 可以幫助我們需要時才執行昂貴的操作。完全的 lazy evaluation 需要 referential transparency 才辦的到,也就是需要 side-effect-free function 和 immutable value。(只有最 Pure Functional 的 Haskell 預設所有 expressions 都是 lazy)

6. Declarative 風格,而不是 Imperative

OO 基本上也是 Imperative 風格,一行行告訴電腦特定的步驟。

# Declarative
def factorial
  if (n==1) return 1
  else return n * factorial(n-1)
end

# Imperative 有許多 mutation step
def factorial
  result = 1
  for (i = 2; i<=n; i++) {
    result *= i 
  }
  return result
end

Declarative 風格也跟 lazy evaluation 很合。跟 mutability 和 side-effect function 則不相容。

無論偏好 static 或 dynamic typing, FP 對於 type design 也有一套看法,除了下一章提到的核心容器 type,還有一件事值得學習:

immutable 表示變數初始一定要有值,也就表示不應該允許 null,null 也常常是 bug 源頭,例如忘記去 check null 的存在。在 Java 中 Null type 就是任何 type 的 subtype。會需要 null 的存在,顯然是因為我們需要一個變數來表示 “Optionally” 可有可無,那麼何不明顯建立一個 type 處理,例如一個抽象介面 Option 以及它的實體化 subtype (final) Some 和 (final) None 表示一個有一個無。因此在需要 null 的場合,使用 Some 和 None 來包裝。Java 的 type-safe 會保證你不會忘記一定要處理 Option,看是 Some 或 None,這種作法保證了程式的可靠性。

像 Option 介面只允許 Some 和 None 這兩個 final 不能再 subtype 的 type,叫做 Algebraic data type,可以從一種 type 安全變換成另一種 type (下一章會有例子)。跟一般我們設計介面的 abstract data type 不限制 subtype,強調 polymorphic behavior 的用法概念不同。

資料結構和演算法

FP 偏好使用核心提供的容器 Lists、Maps、Trees、Sets,不像 OO 愛用物件包裹。根據上一章的FP原則,來實際看一些資料結構和演算法。FP提供了常見的資料結構和對應的 Combinator 操作。

Linked list 也是一種 Algebraic Data Type,只有兩種 subtype: empty 和 non-empty。這跟 Java 的 List type 不一樣,Map 也是 abstract data type。作者用 Java 實作了 functional-style 的 List, Map

Combinator functions: 處理容器的基本三招: 1. filter 2. map 3.fold 很多其他操作都是基於此。這三招又叫作 Combinators,是最厲害的 reusable 建構演算法可以組合出複雜的運算。這三招也讓你不必一直用遞迴。

因為是 immutable,所以變數需要改變時,就要不斷的 Copy 出新值才行。如果碰到大資料,對效能就有問題了。好在 FP 內部實作利用了 Structure sharing 的方式,用 tree 結構避免 full-copy 來有效率的處理。這種資料結構叫做 Persistent Data Structure。

利用 DSL (DSL可以用OO也可以用FP實作) 來包裝 FP 操作,只使用核心資料結構和 Combinators。不需要每樣東西都物件化,OO 操作是錯誤的抽象化層級。

Function Concurrency

很喜歡作者的這句話 “Multithreaded programming, requiring synchronized access to shared, mutable state, is the assembly language of concurrency”,每次看 OO 程式語言的 threading 章節都覺得 multithreaded 是神人才能寫的東西,實在太難了。

雖然 immutable 特性已經讓很多 synchronization 不需要了。但是 mutate state 還是有不可避免的時候,這時候可以利用更高抽象層級的 Actors 和 STM 來確保 thread-safe。

Actors 透過 Actor 來做訊息傳遞,每個 Actor 有自己的 queue。實作最好的大概是 Erlang 了。
有趣的是,最早的 Smalltalk 想法還比較像 Actor Model,關鍵是 messaging。

1.只有一個 actor 負責改變狀態,所以其他 code 想改變時,都必須通知唯一的 actor,從而避免 synchronization 問題。
2. 允許多個 actors 修改,會有一個特別的 semaphore message 代表安全。

Actors 風險是如果 scope 太大,會造成 bottleneck。

Java 上目前有兩個好的實作:AkkaFunctional Java。Actors 模型有許多地方都受 Erlang 成功的啟發,包括 Akka 用了 Bridge design pattern 來增加 robustness 和 error recovery 能力。

STM 提供記憶體層級的 ACI (記憶體所以做不到 During,所以不是ACID)。STM 背後的原理是 value 本身還是 immutable 的,如果有改變值,則透過改變 references,加上 Persistent Data Structures 機制增加效率。STM 目前做最好的語言大概是 Clojure。Akka 也有 STM 的實作。

關於 Actor 和 STM 的使用時機比喻,RubyConf 2011 的這場 Scaling Ruby with Actors, or How I Learned to Stop Worrying and Love Threads 演講我覺得還不錯。

更好的OO

OO 編程基本上是 Imperative,而 FP 是 declarative。Imperative 看起來很忙又很多 mutation,容易出錯。
mutable 物件不 thread-safe 而且不易掌控修改。讓物件 immutable,盡量 declarative。雖然有限制,但是保持所有 public 抽象層的 Pure,即使內在不 Pure。

以 LSV 為例,在 OO 中因為繼承的自由跟彈性,很難保證符合,於是透過測試或設計模式來做。例如 Template patterns,但是 FP 的 higher-order functions 就可以做到了,細節在 function argument 再定義即可。

有些人覺得 FP 是不是讓 OO 世界的設計模式無用,其實這是搞混了模式的精神跟實作。某些 GOF 的 pattern 其實根本就是 FP 內建的功能(Singleton, Composite, Command, Iterator等),有些則可以被取代(Template Method –> higher-order functions)。

FP 也有自己的模式,例如 Fold 用法和 Pattern matching。Monad 被用在 sequence expressions。Vistor pattern 的用途(go inside the object)則被 Pattern matching 取代。

Pattern matching 蠻像 switch 的加強版,是一種好用的 modularity 工具,可以根據 type 做 data extraction,使用 Pattern matching 來實作新功能而不會污染本來的 type

什麼是好 type 設計? OO modeling 沒錯,但是不精準的 OO code 時卻不無法保證 LSV 的 type 正確性。這就是 OO programming 的問題,domain concept 都在變,不如化作 key-value pairs。當然也有好的 domain concept 是不會變,例如錢,zip codes 等等

作者認為任何放在 collection 裡的都不應該有專屬的 type,讓 filter, map, fold 主導。type wrapper 不值得花費開發。

ORM 跟其他 OO middleware 都是無謂的複雜,用 filter, map, fold 轉換資料形式即可。Domain object 雖然容易了解,但是好處卻不總是值得。越少 code 就越 Agile (Play framework 的 Scala Anorm API 是個好例子)。

願景

從 Groovy, JRuby, Jython 等 Scripting 語言開始學FP是最簡單的一步,雖然不是FP語言,但是有許多FP的功能。FP 中,Scala 是作者的最愛,你可以同時有OO,然後慢慢學FP。當然,避免一直待在 OO 舒適圈。Clojure 即使你不愛 Lisp 但也值得一學,Lisp 可是歷久不衰的語言。

如果考慮JVM以外,Haskell可以一試,這是所有FP語言的搖籃。Windows 使用者則可以考慮F#。The Structure and Interpretation of Computer Programs 是經典教科書,作者還推薦讀 Neal Ford’s Functional ThinkingWhy Functional Programming Matters

Java 的 Functional 工具有 Functional JavaTotally LazyAkka。作者期望 Akka 會是接下來幾年 Java 界的明日之星。

參與討論

2 則留言

  1. 版主好,我是一個 Haskell 的學習者,有些資訊/意見想分享給您參考

    1. STM 在 Haskell 的 GHC 編譯器工具集也有提供。Haskell 線上雜誌 Monad.Reader #15[1] 與 Beautiful Code 收錄的 Beautiful Concurrency [2] 中都有提到。Haskell 這邊的特色在於,其 STM Monad型別系統限制了任何會在平行中出錯的程式碼在編譯期就會被揪出來。簡單而言就是只有 read/write 這兩個動作可以被允許於 STM 中存取共用變數,其他任何動作都必須等這一串讀寫共用變數動作結束後,unwrap 回 IO Monad 才可執行。

    [1] themonadreader.files.wordpress.com/2010/01/issue15.pdf
    [2] research.microsoft.com/pubs/74063/beautiful.pdf

    2. 在 Haskell 中,平行 Parallel 與並行 Concurrency 是兩個不同的概念。前者指 evaluation 時貨真價實的利用多核心支援去做平行求值。平行範例例如

    fib :: Int -> Int
    fib 1 = 1
    fib 0 = 1
    fib n = fib (n – 1) + fib (n – 2)

    fib2 :: Int -> Int
    fib2 n = a `par` (b `pseq` (a+b))
    where a = fib n
    b = fib n + 1

    fib2 中使用了 `par` 與 `pseq` 去做平行求值運算。這是個很有名的例子。另外並行則是使用 `forkIO` 等 interleaving 函式,於 IO Monad 中做交互執行(不一定真的同時執行)的動作。可以注意到前者用在 pure 函式中,後者用在 Monad Actions 中。這在 Real World Haskell 一書,以其我上述提到的 [2] 中有解說。

    3. 對 FP 而言,尤其是對 Haskell 而言,沒有 Monad/Arrowlet 機制的 FP 可能只提了一半的現實。主要因為 pure 語言要如何與「現實世界」接軌一直都被提起。更有人會認為 FP 不實際就是因為他們看不到 FP 可以透過 Monad/Arrowlet 在全 pure 的情況下執行「實際的」運算。版主好像在前一篇說 Monad 還不是很熟,我想版主如果有時間,Monad.Reader#13 的著名文章 Typeclassopedia [3] 可以讓版主熟悉整個相關架構體系。當然其語言是 Haskell 可能稍微偏頗,但我想注意其抽象精神即可

    [3] www.haskell.org/haskellwiki/Typeclassopedia

    4. 其他語言我不太清楚。但在 Haskell 中,所有錯誤都是某種型別錯誤。因此型別系統對其 FP 精神而言非常重要。對程式設計師而言,這句話如果完全實現的威力在於,型別錯誤就等於編譯期錯誤,也就是 runtime error 這可怕的東西出現的機會將大大減低。像剛剛講的 STM Monad ,若如我們一般的作法讓共享資料的動作擴展到讀寫以外的場合,錯誤可能會藏在每個角落 ( data race ) 。但因為 Haskell 用型別系統防止這種事情發生,因此我們可以斷定只要編譯不出錯,runtime 絕對不會有 data race 的問題會發生。現在有些程式設計師覺得型別完全不重要或是認為語言應該拋棄型別,我覺得會連 compiling time debugging 的效率優點一起揚棄掉。不過我覺得這與麻煩到死的無/少推斷型別系統有關,例如

    SomeThing i_know_its_SomeThing = new SomeThing()

    不能

    i_know_its_SomeThing = new SomeThing()

    順便說一句:在 Real World Haskell 一書中,作者認為Haskell 與 Ruby 的做法相反。Ruby 在最後有需要時才做型別檢查,Haskell 則是認為先把型別全部做完,這樣 runtime 就不會有 overhead 。

    5. Java 因為缺少 first class function 的概念,隨便做個 FP 的模擬都會麻煩到死。我之前嘗試著使用 Java 去實作類似 jQuery 的 fluent api call ,用來模擬 Arrowlet ,結果發現首先要實作 Functor 作為 first class function ,然後Java 的 generic 型別系統只做了 C++ 的 template 大概半套(JVM 是不認 generic 的),讓很多地方都必須強制轉型。接著因為沒有 first class function ,必須大量使用非常醜陋的 anonymous class 去做類似的事情。更麻煩的是因為其 operator 不能 overloading ,所以像 monad 的 bind 、arrow 的 (+++) 等運算子都不能輕易表現。 Functional Java 從人類讀寫層面來看也幾乎一樣醜。我想一門適合某些領域的程式語言,先決條件就是要在該領域表現出一種文法層次的合宜,甚至優雅。在這方面,Java 在不動用到 Compiler 改造語言的情況下我覺得完全不適合 FP 。

    6. 我在學 FP 之前也花了一些時間學習 OOP 很多 pattern 。現在回頭來看,我覺得 pattern 存在多少都是因為 OOP 的模組介接與運算組合不能像 FP 那樣容易。例如 map 這種函式可以輕易透過組合組出新函式( Curry 機制更是 ) 。在像 Java 或 C++ 那樣的語言中,你要大量透過組合製作出新的函式只能走上我之前的路,先去實作 Functor 。又如果是透過 Composite/Strategy/… 等 pattern 去做運算的組合,對 FP 而言幾乎像呼吸一樣自然 , OOP 要先實作整個 pattern 體系。

    —-

    最後是很高興有像版主這種比較在「圈子中」的人開始推 FP 。我自己開始學 FP 也是看到一些中文網誌的介紹,然後持續的學 Haskell 。這段時間每每嘆羨於 FP 的概念與實作是如此強大。當然可能 FP 有不少缺點,但我感到難過的是有些人不明白其重點就開始批評( 最常見的:「pure 不實際」 — 不知道 Monad/Arrowlet )。天幸最近多核與 Big Data 的興起讓各種 FP 語言有比較公平的舞台去一展身手。

    最後推薦一篇文章:The Downfall of Imperative Programming – by Bartosz Milewski [4]。其中講了作者決定離開 Imperative Programming Languages ,例如 C++ 與其共同參與設計的 D 語言。原因是作者覺得在多核的硬體趨勢下,Imperative Languages 無可避免的會遇到 data races 問題。

    重點兩個:

    Imperative programs will always be vulnerable to data races because they contain mutable variables.

    而於此同時, Functional Languages

    There are no data races in purely functional languages because they don’t have mutable variables.

    [4] fpcomplete.com/the-downfall-of-imperative-programming/

發佈留言

發表迴響