什麼是函式式編程#

問十個程式設計師「函式式編程是什麼」，可能會得到十種不同的答案：

  • 用函式來寫程式
  • 函式是「一等公民」（first class）
  • 程式具備引用透明性（referential transparency）
  • 一種以 λ 演算（lambda calculus）為基礎的風格

這些說法都對，但對日常工作沒有實質指導意義。作者給出的更直白定義是：

函式式編程，就是不使用「賦值述句」（assignment statement）的程式設計。

這個定義乍看令人不安——沒有賦值，怎麼可能寫出程式？接下來幾段範例會回答這個問題。

從 C 程式逐步演進#

考慮這個幾乎所有程式都有的核心迴圈：

int main(int ac, char** av) {
  while(!done())
    doSomething();
}

它實在沒有可見的賦值述句，是不是就是函式式呢？我們把它具體化，計算 1 到 10 的平方和：

int n=1;
int sum=0;
int done() { return n>10; }
void doSomething() { sum+=n*n; ++n; }

void sumFirstTenSquares() {
  while(!done()) doSomething();
}

這版不是函式式：

  • doSomething 內有兩個賦值
  • 還用了兩個全域變數，醜陋難讀

把全域變數改為區域變數、再把區域變數轉成函式參數，最後用遞迴取代迴圈：

int sumFirstTenSquaresHelper(int sum, int i) {
  if (i>10) return sum;
  return sumFirstTenSquaresHelper(sum+i*i, i+1);
}

int sumFirstTenSquares() {
  return sumFirstTenSquaresHelper(0, 1);
}

賦值消失了，這版才是函式式。同時它也是遞迴的——這並非巧合：

想擺脫賦值述句，就必須使用遞迴。遞迴用「函式參數初始化」取代了「區域變數的賦值」。

尾呼叫優化（TCO）#

遞迴會吃堆疊，但有個聰明的小技巧能解決這個問題。

注意上例最後的遞迴呼叫，是該函式中 sum 與 i 的最後一次使用——把它們留在堆疊裡毫無意義。如果不開新堆疊框，而是「跳回函式開頭、用新參數覆蓋舊的」，就能避免堆疊爆掉。

這個技巧叫做尾呼叫優化（Tail Call Optimization, TCO），所有函式式語言都會以某種方式提供它。

Java 虛擬機（JVM）的設計讓 TCO 略為複雜；C 則完全沒有 TCO，因此本書 C 範例的堆疊會持續成長。

賦值的問題#

先界定「賦值」（assignment）的精確意義：

  • 初始化（initialization）：int x=0;——x 此時誕生，並被設為 0
  • 賦值（assignment）：x=1;——x 早已存在，現在被改成 1

在第一種情況下，我們無從得知 x 究竟是變數還是常數；在第二種情況下毫無疑問——x 在變動。

因此，函式式編程的另一種說法就是：沒有變數的編程。函式式程式裡的值不會變動。

時序耦合與競態條件#

為什麼避免賦值會更好？想像這樣的程式：

// Block A
.
x=1;
.
// Block B

Block A 與 Block B 在系統狀態上不同——這意味著它們必須照順序執行，否則程式行為就錯了。

這種「時間上的耦合」稱為 時序耦合（temporal coupling），在程式中無所不在：

  • open 必須在 close 之前
  • new 必須在 delete 之前
  • malloc 必須在 free 之前

這類成對操作就像星際大戰裡的西斯（Sith）一樣，總是「永遠是兩個」。我們有多少次忘了關檔、釋放記憶體、釋放號誌量（semaphore）？又有多少次的疑難雜症最後是靠交換兩個函式呼叫的位置解決的？

更糟的是：

  • 垃圾回收（garbage collection）——這是我們承認自己不擅長處理時序耦合而引進的「拐杖」
  • 競態條件（race condition）——多執行緒爭搶處理器時，順序大致正確 99.99%，偶爾就會出錯造成混亂

這些麻煩都是「使用賦值」自然導致的後果。

沒有賦值，就沒有時序耦合，也就沒有競態條件。沒更新就沒有「同時更新」的問題；函式內若狀態不變，就沒有順序問題。

一行 log 的差別#

考慮非函式式版本：

int sumFirstTenSquaresHelper(int sum, int i) {
  while (i<=10) {
    sum+=i*i;
    i++;
  }
  return sum;
}

如果想加 log("i=%d, sum=%d", i, sum);，會發現有三個位置可選——其中一個會印出錯誤的資料。這就是時序耦合留下的陷阱。

換成函式式版本：

int sumFirstTenSquaresHelper(int sum, int i) {
  return (i>10) ? sum : sumFirstTenSquaresHelper(sum+i*i, i+1);
}

整個函式只有一個地方可以放 log，而且必然是正確的資料。

為什麼叫「函式式」#

數學上的**函式（function）**是把輸入映射到輸出的物件：給定 y = f(x)，每個 x 都對應唯一的 y，而且：

  • 對 f 來說，其他事都不重要
  • 系統的當下狀態與 f 無關
  • 沒有「先後順序」的限制——只要傳 x 進去，永遠拿到相同的 y

這個性質叫做引用透明性（referential transparency）：函式呼叫永遠可以用其回傳值替換。

一步步替換#

以前面那個函式式版本為例：

int sumFirstTenSquares() {
  return sumFirstTenSquaresHelper(0, 1);
}

把第一個呼叫展開：

int sumFirstTenSquares() {
  return (1>10) ? 0 : sumFirstTenSquaresHelper(0+1*1, 1+1);
}

再展開下一層：

int sumFirstTenSquares() {
  return
    (1>10) ? 0 :
      (2>10) ? 0+1*1
             : sumFirstTenSquaresHelper((0+1*1)+(1+1)*(1+1), (1+1)+1);
}

每一次呼叫都能單純被「函式本體 + 參數代入」替換。

對非函式式版本做不到這件事——你可以「展開迴圈」，但那不是同樣的替換動作。

函式式程式由「真正的、引用透明的數學函式」組成——這就是 functional 一詞的由來。

真的不能改變狀態嗎#

如果函式式程式沒有變數，就無法改變狀態。一個無法改變狀態的程式還能有什麼用？

答案是：函式式程式從舊狀態計算出新狀態，而不修改舊狀態。

State system(State s) {
  return isFinal(s) ? s : system(advance(s));
}

這個函式從某個初始狀態出發，逐次推進到終態：

  • 沒有任何狀態變數被修改
  • 每一次迭代產生的是「全新的狀態」
  • 若關掉 TCO 讓堆疊成長，所有歷史狀態都會原封不動地保留在堆疊框裡
  • system 仍是真正的數學函式：給 state1，每次都得到 state2

接受輸入的「函式式」程式#

只要稍作修改，就能讓這個 system 響應外部事件，變成傳統的有限狀態機（finite state machine）：

State system(State state, Event event) {
  return done(state) ? state : system(transition(state, event), getEvent());
}

但 getEvent 每次回傳都不一樣——它不是引用透明的，這意味著嚴格來說這個程式並非「純函式式」（pure functional）。

嚴格來說，任何接受輸入的程式都不可能是純函式式。但本書要談的不是純函式式編程，而是函式式風格。

即使輸入不純，整體程式仍可以採函式式風格寫成——這正是本書關心的事。

不可變性#

把上面所有觀察整合在一起，我們得到一條核心結論：

函式式程式中沒有變數。任何東西都不會「改變狀態」。

狀態的演進，是透過「在每次遞迴呼叫時，把新值傳給下一個函式」來實現——舊狀態從未被覆寫。

  • 若不需要舊狀態，TCO 可以把它們優化掉
  • 但精神上，所有過去的狀態都依然存在於某個被釋放的堆疊框裡，未曾改變
  • 既然沒有變數，所有被命名的值就都是常數
  • 一旦被初始化，這些常數的整段歷史將完整、不變、永久存在——這就是不可變性（immutability）
Backward 函式式基礎 持久性資料 Forward