1958 LISP：S 表達式、eval/apply 與垃圾回收#
案發現場#
1956 年，John McCarthy 在 IBM 參與夏季研究計畫時思考一個問題：能否讓電腦做「符號推理」而非僅是數值計算？ 數值計算方面 FORTRAN（見 1957-FORTRAN.md）即將交卷，但下棋、定理證明、邏輯推演這類 AI 問題（人工智慧一詞正是 McCarthy 於 1956 年 Dartmouth 會議提出）需要不同的工具。
當時的謎題：
- 遞迴之謎：FORTRAN 不支援遞迴（因為所有變數配置在靜態記憶體）。而處理樹狀符號結構（如棋盤局勢、句法樹）天然需要遞迴。
- 程式即資料之謎：AI 研究需要程式能操作、修改甚至生成其他程式。FORTRAN 中程式編譯後就與資料世界隔絕。
- 記憶體之謎：符號處理會產生大量小物件（符號節點），手動管理必死，需要自動回收。
1958 年，McCarthy 到 MIT，與研究團隊一起著手破解。
偵查過程#
McCarthy 的推理是一連串漂亮的數學步驟：
第一步：選擇數學基礎——Lambda 演算。 Church 的 \(\lambda\) 演算（見 1960-Lambda計算.md）提供了遞迴與函數抽象的理論基礎。McCarthy 採用其核心思想：函數是一等公民。
第二步：設計表達式表示法。 為了「程式即資料」，McCarthy 把一切（程式與資料）都表示為鏈結串列，最初設計兩種語法：
- M 表達式（人類可讀）：
car[cons[A;B]] - S 表達式（機器形式）：
(car (cons A B))
關鍵轉折：團隊成員 Steve Russell 看了 McCarthy 論文草稿中的 eval 數學定義後說：「這個 eval 可以直接用機器碼實作！」於是 S 表達式直接成為語言本身，eval 成為語言的核心函數——數學定義直接變成可執行程式，這在程式語言史上是第一次。
第三步：寫下萬能函數。 LISP 的核心是 7 個基本函數（car, cdr, cons, atom, eq, cond, quote）加上萬能的 eval/apply 二元組：
用 Python 寫出的 meta-circular evaluator（後文）只需數十行——因為語言的語意就濃縮在這個遞迴方程中。
第四步：破解記憶體之謎。 McCarthy 與團隊發明垃圾回收（GC）：當空間耗盡時，從根部（目前作用域）遍歷所有可達節點，標記後其餘全部回收：
1959 年 Collins 實作了第一個 mark-sweep GC。這是「程式設計師不必管理記憶體」思想的誕生，後來影響 Java、Python、Go 一切現代語言。
結案報告#
LISP 一舉破解三謎：遞迴（函數可呼叫自身）、程式即資料（quote + eval）、自動記憶體（GC）。1960 年 McCarthy 發表《Recursive Functions of Symbolic Expressions》，LISP 成為 AI 研究的專屬語言三十年。
遺產清單：
- 函數式範式：一等函數、閉包、高階函數經 Scheme（1975）傳承，影響 Haskell（見 1990-Haskell.md）、JavaScript（見 1995-JavaScript.md）、Python 的 lambda。
- GC 普及：現代所有 managed 語言的 GC（Java JVM、CPython、Go runtime）皆源於此。
- REPL 與互動式開發：S 表達式 + eval 天然形成「讀取-求值-印出」循環，今日 Python/Jupyter 的互動介面即其後裔。
- 巨集系統：因程式即資料，LISP 的
defmacro能用語言本身擴展語言——其他語言至今難以複製。 - AI 語言：從早期西洋棋程式到 1970s 的專家系統，LISP 是五代機以前 AI 的通用語。
McCarthy 後來說：「LISP 的設計一半是理論、一半是意外。」——那個意外（Russell 實作 eval）決定了此後六十年的語言史。
證據與工具#
用 Python 實作一個迷你 meta-circular evaluator——這就是 1958 年 LISP 的核心：
def tokenize(s):
return s.replace('(', ' ( ').replace(')', ' ) ').split()
def parse(tokens):
t = tokens.pop(0)
if t == '(':
lst = []
while tokens[0] != ')':
lst.append(parse(tokens))
tokens.pop(0)
return lst
return t
def env_find(env, var):
return env.get(var)
def eval_lisp(x, env):
if isinstance(x, str): # 原子
return env_find(env, x)
if not isinstance(x, list): # 數字
return x
op = x[0]
if op == 'quote': return x[1]
if op == 'car': return eval_lisp(x[1], env)[0]
if op == 'cdr': return eval_lisp(x[1], env)[1:]
if op == 'cons': return [eval_lisp(x[1], env)] + eval_lisp(x[2], env)
if op == 'eq': return eval_lisp(x[1], env) == eval_lisp(x[2], env)
if op == 'cond': # 條件表達式
for (test, expr) in x[1:]:
if eval_lisp(test, env): return eval_lisp(expr, env)
return None
if op == 'lambda': # 函數抽象 (lambda (x) body)
params, body = x[1], x[2]
return ('closure', params, body, env)
# 應用：apply 語意
f = eval_lisp(op, env)
args = [eval_lisp(a, env) for a in x[1:]]
if isinstance(f, tuple):
_, params, body, fenv = f
newenv = dict(fenv); newenv.update(zip(params, args))
return eval_lisp(body, newenv)
return f(*args) # 內建算術
env = {'nil': [], 't': True, '+': lambda a, b: a + b, '-': lambda a, b: a - b}
print(eval_lisp(parse(tokenize('(car (cons 1 (quote (2 3))))')), env)) # => 1
print(eval_lisp(parse(tokenize('(cond (nil 0) (t 42))')), env)) # => 42
# 遞迴：定義階乘（用 cond 遞迴呼叫）
fact = "(def fact (lambda (n) (cond ((eq n 0) 1) (t (* n (fact (- n 1)))))))"
env['def'] = 'DEF'
env['*'] = lambda a, b: a * b
# 展示 S 表達式即資料：程式本身是串列
prog = parse(tokenize('(cons (quote fact) (quote (42 nil)))'))
print(prog) # ['fact', '42', []]
這約 50 行的 Python 正是 McCarthy 1960 年論文中 eval 函數的化身——語言的語意小到能放進偵探的口袋，卻足以容納整個 AI 時代。