案例探討: Map-Reduce

何謂 Functional Programming？

Functional Programming (以下簡稱 FP) 是種 programming paradigm (開發典範)，不是 design pattern 也不是 framework，更不是 language。簡單來說，FP 是種以數學函數為中心的「思考方式」與「程式風格」。

〈Why Functional Programming Matters〉撰寫於 1984 年、1990 年做小幅度修改，主要凸顯出 FP 的優點與重要特質。

• 中文翻譯：函數式程式設計為什麼至關重要

一般來說，FP 的幾個特點如下:

• 運算用的 function 大多只包含條件式及遞迴呼叫;
• higher-order functions 主要有兩個特點：
  • function 可當作參數傳入 function 之中
  • function 可以回傳 function
• 沒有隱含 (implicit) 的 Side Effect (副作用)
  • 將程式語言的函式視作看作是數學上的函數，乍看似乎沒問題，但副作用的存在不能保證每次呼叫的時候，傳回來的東西都會一樣，也就是程式本身，並非獨立於程式語言其他的部份。所以當程式出錯的時候，開發者需要走訪所有觸及的程式碼，方可確立問題的來源;
  • 在 Haskell 等純函數語言，副作用是必須「明確」地用型別標示出來，而不是隱含的。副作用本身不必然是 primitive 的操作，可以是由語言的其他構件組成。而如 OCaml 這樣的 FP 語言，甚至提供 (explicit) reference 這樣的型別。所以每次呼叫函數，總可以保證傳回的數值不會變，也因此要寫對程式，也變得比較容易，或者說，較難寫程式但可確保容易寫出對的程式;
• lazy evaluation
  • 當變數被定義時，不會立即 evaluate，而是等待要使用時才 evaluate 並儲存已計算的結果，所以不會重複 evaluate 同一個定義
  • 因為沒有副作用，所以可以把計算過的值記起來，以便下次再呼叫的時候直接拿來用，也就是 lazy evaluation 的精神。

延伸閱讀: Functional Programming: Concept & Example

程式語言引入函式傳遞是縮減複雜度的手法之一，然而，很多時候很難阻止開發者傳遞幾百或幾千行的函式內容。於是，程式語言的設計者則轉向焦點，思索如何規範開發者撰寫出意圖單一、實作單純的簡明函式，這即是不可變(immutable) 特性。當開發者無法任意更動變數內含值或物件狀態，便只能從既有變數值或物件狀態，來產生新的數值或物件狀態，這不啻貫徹數學上的數學函數嗎？換言之，開發者會將大任務切割為若干小任務，於是可察覺小任務的流程重複性，一旦開發者封裝重複的小任務，隨後即可在呼叫它們時，只專注在真正該關心的運算，並以函式傳遞運算。

若函式實作時貫徹不可變特性，該函式就會被稱為純函式 (pure function)，相對地，就會是具有副作用的函式。值得留意的是，即便在 Haskell 一類純函數式語言中，也是有副作用的部份，不然就無法接受外界輸入，也不能進行程式對外的輸出。純函數式程式設計規範的是，副作用函式與純函式有個明確的界線，一邊是完全純粹的世界，不純的世界是另一邊；副作用本身對電腦上執行的程式是必要的特徵，它並非萬惡，真正令開發者畏懼的是，開發者搞不清楚這函式是否有副作用，進一步導致他們在不知道的地方改變什麼。

近年 FP 被重新提出且廣泛應用，是基於以下考量：

1. 單核處理器時脈出現瓶頸，中央處理器的運作時脈已經很難超過 5GHz，因此單執行緒程式速度也面臨瓶頸，但隨著半導體製程進步，單位面積可以塞入更多電晶體，因此處理器可納入更多核 (即 multi-core)。典型 imperative 寫法依賴 side effect，使得多核很難發揮效益，但 FP 沒有 side effect，很容易藉由平行運算，充分運用硬體能力;
2. side effect 寫法很難單元測試，因為不保證每次的結果都ㄧ樣，但 FP 的 pure function 很適合單元測試
3. OOP 的 object composition 需依賴 interface，容易造成 interface 混亂與 over design，但 FP 的 function compostion 不需要額外 interface，只要求你使用 Dataflow 思考，並使用 pure function 避免 side effect 即可

常見 FP 操作

在 FP 中，以下三種常見操作，搭配下圖食物對應:

• map(): 配合給定行為，回傳一個陣列或鏈結串列
• filter(): 用以檢索和篩選
• reduce(): 將素材混合在一塊，得到最終結果

實作

• MapReduce with POSIX Thread
• MapReduce