Functional Programming for Java Developers 讀書摘要

标签: Functional Java | 发表时间:2012-04-16 22:38 | 作者:ihower
出处:http://ihower.tw/blog

這是我之前念 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。

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 界的明日之星。

相关 [functional programming for] 推荐:

Functional Programming for Java Developers 讀書摘要

- - ihower { blogging }
這是我之前念 Functional Programming for Java Developers 一書的摘要記錄. 這本書很薄只有90頁,是一本蠻不錯的 Functional Programming 概念入門勸敗書. 近來 Functional Programming (函數式編程,以下簡稱FP) 的重要性提昇就是為了因應 Concurrency 的需求.

Programming Collective Intelligence 读书总结

- 透明 - 崔添翼 § 翼若垂天之云
assign every item to the nearest centroid, and move the centroid to the average location of all items assigned to them. checking pairs of nodes that have a common parent to see if merging them would increase the entropy by less than a specified threshold.