1960-ALGOL 60 遞迴與傳名#

案件摘要#

1960 年 1 月，ALGOL 委員會在巴黎集會，由 Peter Naur 編輯的《Report on the Algorithmic Language ALGOL 60》問世，正式將「遞迴程序」（recursive procedures）與「傳名呼叫」（call-by-name）寫進國際標準語言規格。在此之前，遞迴在主流程式語言中是被明文禁止的禁忌——Fortran 與組合語言的世界裡，呼叫堆疊根本不存在。這份報告的幕後，是一場由數學遞迴函數傳統驅動的密謀：Dijkstra 在羅馬會議上力推遞迴程序，van Wijngaarden 則以一個關鍵範例說服眾人接受 call-by-name。本案追查：遞迴如何從禁忌變成標準，以及「每次使用都重新求值」的傳名語義，如何成為日後惰性求值（call-by-need）的直系祖先。

前因 -- 為什麼會有這個案子#

Fortran（1957）與當時的組合語言均無遞迴：函數呼叫位址往往寫死在記憶體中，第二次呼叫會覆蓋自己的返回位址，遞迴等同自殺。
IBM 甚至在文件中把 stack（堆疊）視為明確的禁忌話題，工程上普遍認為「不需要」遞迴。
ALGOL 委員會的成員——Friedrich Bauer、Klaus Samelson、Heinz Rutishauser、Edsger Dijkstra——多出身歐陸數學傳統，熟悉 Gödel、Kleene 的遞迴函數理論，認為「程序應該能呼叫自己」是天經地義。
Bauer 與 Samelson 早在 1957 年就為運算時的堆疊機制申請了專利（"Verfahren zur automatischen Verarbeitung von kodierten Daten"），為遞迴的機器實現鋪好了地基。
1959/1960 年的羅馬（巴黎前） preparatory 會議上，Dijkstra 提案讓程序可以遞迴，遭到激烈反對；van Wijngaarden 以一個需要 call-by-name 的範例反將一軍，辯論白熱化。
委員會的目標是設計一門「演算法的通用語言」，既要能在機器上實現，又要夠數學、夠優雅——這兩種張力正是本案的動機。

線索與推理 -- 數學式、程式、理論#

線索一：call-by-name 的語義 = 不 memoize 的 β 歸約#

λ-Calculus 的 β 歸約是「把實參整個代入函數體，再求值」。call-by-name 正是這條規則的直接翻譯：每次用到參數，就重新求值一次實參表達式。

\[ (\lambda x.\; M)\; N \;\longrightarrow\; M[x := N] \]

若實參 \(N\) 在函數體 \(M\) 中出現 \(k\) 次， \(N\) 就被求值 \(k\) 次——沒有任何記憶。相較之下，call-by-value 先求值 \(N\) 再傳入，只求值 1 次；call-by-need（惰性求值）第一次用到才求值，之後共用結果，也是 1 次。

線索二：複雜度分析——call-by-name 可能指數慢#

傳名的「每次重新求值」看似小毛病，實則可能指數爆炸。設 \(D_n = \lambda x.\,(x\,x)\) （自我複製器），考慮 \(A_n = D_n(D_{n-1}(\cdots D_1\; I))\) ：每展開一層，實參被複製一份，總求值步數呈指數增長：

\[ \text{steps}(A_n) \approx 2^n \qquad \text{而 call-by-need 只需 } O(n) \]

McDonald（Wadsworth 的導師圈常引述的 "amusement"）與 Wadsworth 本人在 1971 年博士論文中正是用這類例子，證明 call-by-name 需要「共享」（sharing）來救——這就是 call-by-need 的誕生現場。

線索三：堆疊框與遞迴的機器實現#

遞迴可行的關鍵是每次呼叫都配置新的「活動記錄」（activation record / stack frame）：返回位址、參數、局部變數都存在 frame 裡，frame 隨呼叫推入堆疊、隨返回彈出。Bauer-Samelson 1957 年的專利正是描述這套用堆疊自動處理巢狀資料的機制。有了它，遞迴只是「呼叫一個恰好是自己的函數」，沒有任何特別之處。

線索四：Jensen's Device——傳名的殺手級應用#

Jørgen Jensen 在委員會中提出的裝置，利用 call-by-name「每次使用重新求值」的特性，寫出一個參數化的求和迴圈：

real procedure SUM(i, lo, hi, u);
    value lo, hi;
    integer i, lo, hi; real u;
begin
    real s;
    s := 0;
    for i := lo step 1 until hi do s := s + u;
    SUM := s
end

呼叫 SUM(i, 1, 10, a[i] * 2) 時，u 是傳名參數：迴圈每迭代一次，就重新求值一次 a[i]*2，且 i 的改動會即時反映在 u 的求值中——一個程序，同時扮演 sum、sum of squares、任何推廣。這個近乎魔術的範例，讓反對者無法否認 call-by-name 的表達力。

程式示範：call-by-value vs call-by-name 的求值次數#

用 Python 的 thunk（零參數函數）模擬 call-by-name「每次重新執行」的行為：

counter = {"n": 0}

def expensive_body():
    counter["n"] += 1
    return 42

def cbv(thunk):
    # call-by-value：先求值一次，之後共用
    v = thunk()
    return v + v + v

def cbn(thunk):
    # call-by-name：每次使用都重新求值
    return thunk() + thunk() + thunk()

print(cbv(expensive_body), counter["n"])  # 126 1  （求值 1 次）
print(cbn(expensive_body), counter["n"])  # 126 4  （又求值 3 次）

三處使用，call-by-value 共 1 次求值，call-by-name 共 4 次。把 v + v + v 換成巢狀展開，就是指數爆炸的縮影。

破案時刻#

1960 年報告第 4.7 節寫下 "recursive procedures" 一詞，附帶一句「程序可以透過自己呼叫自己」。Dijkstra 回憶，當委員會意識到 Bauer-Samelson 的堆疊機制讓遞迴「零成本」時，反對聲浪一夜瓦解——禁忌被邏輯處決。

結案 -- 後果與影響#

遞迴從禁忌變成標準配備；此後的語言若不支援遞迴，反而要特別聲明理由。
call-by-name 的語義直接連到 λ-Calculus 的 β 歸約，成為惰性求值（call-by-need，Wadsworth 1971）的直接前身；Haskell 至今仍以 call-by-need 為核心。
ALGOL 60 的 block structure（區塊結構、詞法作用域）直接影響 Pascal、C 與 Scheme——Scheme 的 let/lambda 作用域就是 ALGOL 血統。
Bauer-Samelson 的堆疊專利影響了日後所有編譯器的 runtime 設計（專利 1981 年到期，堆疊早已是公共財）。
Jensen's Device 成為程式語言課程的經典案例，展示了「控制求值時機」本身就是表達力。
ALGOL 60 被後世稱為「程式語言史上的重大改進」——但它自己從未成為主流商用語言，反倒是它的子孫統治了世界。

關鍵人物與文獻#

Peter Naur (ed.), "Report on the Algorithmic Language ALGOL 60", Communications of the ACM 3(5), 1960, pp. 299–314.
Edsger W. Dijkstra, "Recursive Programming", Numerische Mathematik 2, 1960, pp. 312–322.
Friedrich L. Bauer & Klaus Samelson, "Verfahren zur automatischen Verarbeitung von kodierten Daten"（堆疊專利）, 1957 年申請, US Patent 3,047,761（1962）.
Adriaan van Wijngaarden, 對 call-by-name 的羅馬會議提案，收錄於 ALGOL Bulletin 與 Naur 1960 報告的修訂史.
Christopher Strachey, "Fundamental Concepts in Programming Languages", 1967 年講義, 收錄於 Higher-Order and Symbolic Computation 13, 2000, pp. 11–49（call-by-value / call-by-name 術語的定著點）.
David A. Turner, "Richard Bird and the History of Functional Programming", 及 J. E. Wadsworth, "Semantics and Pragmatics of the Lambda-Calculus", DPhil thesis, Oxford, 1971（call-by-need 的誕生）.