1960-垃圾回收#

案件摘要#

LISP 的 cons 不斷產生新的 pair cell，卻沒有人知道該由誰釋放——這是 1958 年 LISP 誕生後遺留下來的懸案。1960 年，McCarthy 的團隊在 LISP 實作中偵破了此案，發明垃圾回收（garbage collection）：與其追問「誰不再使用它」，不如反過來問「還有誰能從根部到達它」。1963 年 Daniel Edwards 完成第一個高效實作；Knuth 1962 年關於 coroutine 的論文中也埋有 mark-sweep 的雛形。破案時刻在於：可達性（reachability）成為「生命」的定義，程式設計師從此擺脫手動記憶體管理。

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

LISP 的 cons cell 動態配置：每次 cons 都向 free list 借一個 cell，符號程式無法預知生命週期。
手動 free 會破壞抽象：若要求程式設計師手動釋放，將破壞「程式即資料」——quoted list 本身也是 cons cell，手動釋放可能釋放掉正在執行的程式。
IBM 704 記憶體極小：約 36K 字組，LISP 程式動輒耗盡記憶體，回收必須自動且完整。
IPL 的前車之鑑：Newell-Shaw-Simon 的 IPL 採手動記憶體管理，使用者深為 list 遺漏（dangling reference）所苦。
遞迴與共享結構：同一個 cell 可能被多處引用，引用計數無法處理循環引用，需要全域視角。

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

線索一：可達性定義「活的」#

把堆積（heap）看成一張有向圖：節點是物件，邊是指標。定義根集合 \(R\) （暫存器、堆疊、全域變數中的指標），則物件 \(o\) 是「活的」若且唯若：

\[ o \in \text{reach}(R), \quad \text{reach}(R) = R \cup \{ x \mid \exists p \in \text{reach}(R),\; p \to x \} \]

不可達者即垃圾——這是不動點式的定義，也是整個 GC 理論的基石。

線索二：Mark-and-Sweep 演算法#

兩個階段：

標記（mark）：從根集合出發，沿指標深度優先或廣度優先遍歷，標記所有可達節點。
清除（sweep）：線性掃描整個堆積，將未標記者加入 free list，並清除標記位元。

複雜度為 \(O(N + L)\) ，其中 \(N\) 為堆積總大小、 \(L\) 為活物件數；圖遍歷部分為 \(O(\text{物件數})\) 。缺點是遍歷時需暫停程式（stop-the-world），且會造成碎片化。

線索三：後續分支的譜系#

Reference counting（Collins, 1960）：每個物件記錄引用數，歸零即回收；缺點是無法回收循環引用。
Copying GC（Cheney, 1970）：把活物件從半空間複製到另一半空間，順帶壓縮，複雜度只與活物件成正比 \(O(L)\) 。
Generational GC（Lieberman & Hewitt, 1983）：基於「大部分物件早夭」的世代假說，把堆積分成年輕代與老年代，年輕代回收頻繁且便宜。

破案時刻：Python 實作簡化 mark-and-sweep GC#

class Obj:
    def __init__(self, name, *refs):
        self.name = name
        self.refs = list(refs)
        self.marked = False

class GC:
    def __init__(self):
        self.heap = []
        self.roots = []

    def new(self, name, *refs):
        o = Obj(name, *refs)
        self.heap.append(o)
        return o

    def mark(self, o):
        if o.marked: return
        o.marked = True
        for r in o.refs:
            self.mark(r)

    def collect(self):
        for o in self.heap: o.marked = False
        for r in self.roots: self.mark(r)
        survivors, freed = [], []
        for o in self.heap:
            (survivors if o.marked else freed).append(o)
        self.heap = survivors
        return [o.name for o in freed]

gc = GC()
a = gc.new('a')
b = gc.new('b', a)          # b -> a
c = gc.new('c', b)          # c -> b -> a
d = gc.new('d')             # 孤兒，無人引用
cycle1 = gc.new('x')
cycle2 = gc.new('y', cycle1)
cycle1.refs.append(cycle2)  # 循環引用，且不可達

gc.roots = [c]              # 只有 c 從根部可達
print(gc.collect())         # 回收: ['d', 'x', 'y']
print(sorted(o.name for o in gc.heap))  # 存活: ['a', 'b', 'c']

孤兒節點 d 與不可達的循環 x ↔ y 都被標記-清除回收——mark-sweep 對循環引用免疫，這正是引用計數做不到的。

補充線索#

1963 年 Daniel Edwards 在 MIT 為 LISP 1.5 寫出第一個高效 GC，使 LISP 得以在記憶體有限的機器上實用。
Knuth 1962 年 "Coroutines" 手稿（1977 年發表於 Stanford）中已有 mark-sweep 雛形，顯示此概念在當時空氣中流動。
標記階段在遞迴深度過深時會溢出堆疊，實際實作改用指標反轉（pointer reversal，Deutsch-Schorr-Waite, 1967）。

結案 -- 後果與影響#

Java、Python、JavaScript、C#、Go 全部內建 GC，手動記憶體管理退居系統程式領域（C、C++、Rust）。
函數式語言的高階抽象——closure、continuation、惰性求值——在 GC 普及後才真正實用，因為它們的生命週期同樣無法預測。
世代 GC 成為 JVM（HotSpot）與 .NET 的標準配置，young/old generation 分代回收。
記憶體安全的現代標準：GC 與型別安全共同消滅了 dangling pointer 與 double free 兩大經典漏洞。
理論影響：可達性分析延伸至靜態分析、指標分析與現代的逃逸分析（escape analysis）。

關鍵人物與文獻（條列）#

John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", Communications of the ACM, 3(4), 1960（首次描述 LISP 的垃圾回收）.
George E. Collins, "A Method for Overlapping and Erasure of Lists", Communications of the ACM, 3(12), 1960, pp. 655–657（reference counting）.
C. J. Cheney, "A Nonrecursive List Compacting Algorithm", Communications of the ACM, 13(11), 1970, pp. 677–678（copying GC）.
Henry Lieberman & Carl Hewitt, "A Real-Time Garbage Collector Based on the Lifetimes of Objects", Communications of the ACM, 26(6), 1983, pp. 419–429（generational GC）.
Donald E. Knuth, "Additional Remarks on Coroutines", Stanford CS Report, 1977（mark-sweep 雛形）.
Richard Jones, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Wiley, 1996.