跳轉到

1977：Backus 函數式風格宣言#

事件#

1977年8月，John Backus（FORTRAN 與 BNF 的發明人）在 ACM 圖靈獎演講中發表 「Can Programming Be Liberated from the von Neumann Style?」（1978 年刊於《Communications of the ACM》）。這位馮紐曼風格的開創者親自批判馮紐曼風格，提出 FP 系統：一種無變數、以組合子為本的函數級程式設計（function-level programming）語言。這場演講被視為函數式程式設計的宣言，啟發了 Miranda（1985）與 Haskell（1990）一整個學派。

語法/特性加入的理論與實用原因#

1. 批評馮紐曼瓶頸（von Neumann Bottleneck）#

  • 理論原因：馮紐曼架構中 CPU 與記憶體之間的通道是瓶頸；傳統語言（含 FORTRAN、C）的語義就是「逐字改變記憶體狀態」，程式設計師被迫逐字「餵食」這個瓶頸。
  • 實用原因：Backus 觀察到傳統語言的「單字」（變數、指定敘述）切斷了程式的邏輯結構——程式無法用代數方式推導與組合。
  • 彌補缺陷：傳統語言的程式是「關於狀態的逐步指令」，無法整體推理；函數式風格讓程式成為可代數變換的數學物件。

同一個「交換兩個變數」的小任務，馮紐曼風格必須逐字改動狀態（還需要暫存變數）：

/* 馮紐曼風格（C 語言，為對照而引用）：逐字改變記憶體狀態 */
temp = x;      /* 每一行都是一次「單字」的狀態改動 */
x = y;
y = temp;      /* temp 這個變數只為了伺候狀態機而存在 */

馮紐曼風格的每一行都「餵食」CPU–記憶體瓶頸，而且程式被變數切得支離破碎——無法整體推理，也無法代數化簡。

2. 函數級程式設計（無變數）#

  • 理論原因：直接對應 Curry 組合邏輯與 λ 演算的 η-轉換——λx.(f x) 等於 f，變數可以完全消除。程式只由函數組合而成，不需命名中間值。
  • 實用原因：無變數的程式沒有「某變數此刻的值」這種問題，程式即等式，可被系統自動化簡與驗證。
  • 彌補缺陷：傳統語言需要為每個中間結果命名變數，名稱管理本身成為錯誤來源。

「算平均」的兩種風格對照——同一個問題，馮紐曼風格靠變數與迴圈，FP 風格只有函數組合：

/* 馮紐曼風格：三個變數 + 一個迴圈 + 一個分支 */
float avg(float a[], int n) {
    float sum = 0;               /* 中間值要命名：sum */
    for (int i = 0; i < n; i++)  /* 迴圈變數要命名：i */
        sum += a[i];             /* 逐字改動狀態 */
    return sum / n;              /* 還要處理 n=0 的邊界 */
}

;; FP 風格（Backus, 1977）：沒有任何變數
定義 平均 := (/ ÷) ∘ [長度, (/ +)]
;; 解讀：[長度, (/ +)] 把輸入同時算出「長度」與「總和」成一對，
;; 再用 (插入 /) 把這一對相除。
;; 整個程式是一條函數的代數式，可被系統直接化簡與驗證。

用組合子代數推導程式的正確性——這是馮紐曼風格做不到的：

;; 代數律：α f ∘ 配對 = <f ∘ 1', f ∘ 2'>  （映射可與配對交換）
;; FP 程式可以像數學式一樣逐條化簡、驗證等價；
;; 命令式程式裡 sum += a[i] 這種「狀態改動」沒有代數律可用。


定義 內積 := (插入 /) ∘ (α ×) ∘ 分配右 ∘ 配對
（FP 的內積定義：沒有任何變數，只用組合子 ∘、α、/、× 表達整個演算法。）

FP 組合子的逐步執行示意——每個組合子都是「對整個結構一次性運算」：

;; FP 組合子的語義
;; ∘  結合：f ∘ g 先套 g，再套 f
;; α  映射：α f [x1, x2, x3] = [f x1, f x2, f x3]
;; /  插入：/ + [1, 2, 3] = 1 + (2 + 3)   對序列遞迴插入二元運算
;; 配對：<f, g> x = [f x, g x]     兩個函數同時套用

;; 執行 內積 <[1,2,3], [4,5,6]>：
配對       → <[1,2,3], [4,5,6]>       ; 先把兩個引數配對
分配右     → [[1,4],[2,5],[3,6]]      ; 逐位置配成元素對
α ×        → [4, 10, 18]              ; 每對相乘
(插入 /)   → 32                       ; 全部加總：4 + (10 + 18)

3. 組合子（Combinators）#

  • 理論原因：組合邏輯（Curry, 1920s–1930）證明少數幾個組合子（S、K）即可表達一切可計算函數；FP 提供結合（∘）、映射（α）、插入（/）、配對等組合子作為程式的唯一黏合劑。
  • 實用原因：組合子讓演算法以「函數的代數式」呈現——整個程式可以像數學式一樣被化簡。
  • 彌補缺陷：傳統語言的函式呼叫需要顯式傳遞參數，函數無法像資料一樣組合；組合子讓「函數的組合」成為語言的一級操作。

組合子把演算法黏合成一條函數式——新增一個運算只需再「組」一個組合子，不必改寫迴圈：

;; 用同一組組合子定義一族相關函數（無變數、無迴圈）：
定義 總和   := (插入 +)
定義 乘積   := (插入 ×)
定義 平方和 := (插入 +) ∘ (α ×) ∘ (α 自身)      ; 先平方再總和
定義 範數   := (開方) ∘ 平方和                  ; 再組一層即可

;; 執行 平方和 [1, 2, 3]：
α × ∘ α 自身 → [1, 4, 9]
(插入 +)     → 14

對照組：命令式語言每新增一種彙總運算，就要複製一份迴圈：

/* 命令式風格：每種彙總都要一份新的迴圈 */
int sum(int a[], int n)    { int s = 0; for (...) s += a[i]; return s; }
int product(int a[], int n){ int s = 1; for (...) s *= a[i]; return s; }
int sumsq(int a[], int n)  { int s = 0; for (...) s += a[i]*a[i]; return s; }

4. APL 的影響#

  • 理論原因：Iverson 的 APL（1962）以陣列整體操作（非逐元素）為中心，證明「對整個結構一次性運算」的表達力。Backus 的 FP 繼承了這種「整體式」思維。
  • 實用原因：APL 的簡潔（一行可表達複雜演算法）啟發了 FP 的組合子設計，儘管 Backus 棄其符號、取其精神。

APL 以一行陣列整體運算聞名——同樣「算平均」，APL 與 FP 皆是整體式，對照 FORTRAN 的逐元素迴圈：

;; APL（1962）：一行，對整個陣列一次性運算（← 為指定，÷ 為除法）
      AVG ← (+/X) ÷ ⍴X
;; +/X 對 X 插入加法得總和，⍴X 得長度——沒有迴圈、沒有下標

;; FP（Backus, 1977）：繼承同樣的整體式思維，但改用具名組合子
定義 平均 := (/ ÷) ∘ [長度, (/ +)]
;; Backus 棄 APL 的神祕符號、取其「對整個結構一次性運算」的精神

彌補了什麼缺陷#

Backus 的宣言彌補的最大缺陷是：傳統馮紐曼風格語言「程式無法整體推理、無法代數推導」的問題。FP 雖然本身未廣泛商用，但它的論證——無副作用、一級函數、組合子、整體式運算——成為 1980 年代以後函數式語言復興的理論藍圖：Miranda、Haskell、Clean 一脈相承，連物件導向語言的 lambda 支援也受其感召。圖靈獎得主親手批判自己創造的典範，讓「函數式風格」從學院角落躍上主流議程。

相關條目#