1958-LISP#

案件摘要#

1958 年，John McCarthy 在 Dartmouth 會議（AI 一詞誕生地）之後，開始探索「符號計算」——用遞迴函數處理符號而非數字。LISP 原本是純理論建構：S-expression 只是內部表示、M-expression 才是給人看的語法。但當他的學生 Steve Russell 用紙筆把 universal function eval 寫成機器碼後，直譯器誕生了——S-expression 直接成為語法，史上最優雅的語言就此現世。

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

Dartmouth 會議（1956）：McCarthy、Minsky、Shannon、Rochester 主辦，AI 一詞誕生。McCarthy 的問題：AI 需要「符號計算」——處理鏈結串列、符號表達式，而非 FORTRAN 擅長的浮點陣列。
FORTRAN 的不足：FORTRAN 為數值計算設計，無遞迴、無動態資料結構、無函數作為值。McCarthy 需要「把函數當資料、把資料當函數」的語言。
理論的傳承：Church 的 λ 演算（1936）與 Turing 機器提供「函數抽象」與「通用機器」的理論——McCarthy 想造的是「通用函數」：一個能解釋任何 LISP 程式的 LISP 函數。
IBM 704 的方便：704 的指令 car（contents of address register）與 cdr（contents of decrement register）恰好提供了鏈結串列的硬體支援——LISP 的基本運算直接來自硬體。

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

案件的核心：七個基本函數#

McCarthy 用七個基本函數建構整個宇宙：atom, eq, car, cdr, cons, cond, quote。資料表示為 S-expression（symbolic expression）：

\[ s ::= \text{atom} \mid (s_1 \; s_2 \; \dots \; s_n) \]

鏈結串列表示：(a b c) 即 cons(a, cons(b, cons(c, NIL)))，用 Python 模擬：

# LISP 鏈結串列的 Python 模擬
# (a b c) = cons('a', cons('b', cons('c', NIL)))
NIL = None

def cons(a, d):  return (a, d)          # 704 的 cons：兩字組
def car(s):      return s[0]            # 704 的 car 指令
def cdr(s):      return s[1]            # 704 的 cdr 指令
def atom(s):     return not isinstance(s, tuple)
def eq(a, b):    return a == b

L = cons('a', cons('b', cons('c', NIL)))   # (a b c)
print(car(L), cdr(L))   # a ('b', ('c', None))

注意：car/cdr 直接來自 IBM 704 的硬體暫存器名稱——語言的命名是硬體的化石。

案件的兇器：McCarthy 的 universal evaluator#

McCarthy 用 LISP 自己寫出「解釋任何 LISP 程式」的函數 eval——這就是史上第一個直譯器的核心。以下是其完整核心（以 Python 語法重現，邏輯忠於 McCarthy 1960 原文）：

def eval(e, a):
    """e: 運算式 (S-expression), a: 關聯串列 (環境)"""
    if atom(e):
        if eq(e, 't'):  return 't'          # quote(t) 的縮寫
        return lookup(e, a)                  # 變數查環境
    if car(e) == 'quote':  return e[1]
    if car(e) == 'cond':
        for (c, r) in e[1:]:
            if eval(c, a) == 't':  return eval(r, a)
    if car(e) == 'lambda':  return e         # 閉包：函數即資料
    if car(e) == 'label':                    # 遞迴函數定義
        return eval(e[2], [(e[1], e[2])] + a)
    return apply_(car(e), evlist(e[1:], a), a)

def apply_(f, x, a):
    if atom(f):  return eval([f] + x, a)     # 基本函數
    return eval(caddr(f),                    # 函數體
                bind(cadr(f), x) + a)        # 綁定參數

def evlist(es, a): return [eval(e, a) for e in es]
def bind(ps, xs):  return list(zip(ps, xs))
def lookup(v, a):
    for (k, val) in a:
        if k == v:  return val
def caddr(s): return car(cdr(cdr(s)))

# 測試：用 evaluator 執行 (label subst (lambda (x y z)
#        (cond ((atom z) (cond ((eq z y) x) ('t z)))
#              ('t (cons (subst x y (car z))
#                        (subst x y (cdr z)))))))
# 這就是 McCarthy 原文中的 subst——在 S-expression 樹中做替換！

關鍵意義：eval + apply 双函數構成不動點——LISP 用自己解釋自己：

\[ \text{eval} \circ \text{apply} = \text{LISP} \implies \text{LISP} = \text{eval}_{\text{LISP}}(\text{LISP}) \]

當 Steve Russell（McCarthy 的學生）看到這段伪碼，說：「這可以直接寫成機器碼！」——直譯器就這樣意外誕生了。McCarthy 本來只把它當理論建構。

M-expression vs S-expression：語法的意外#

McCarthy 原本設計 M-expression（meta-expression）給人看，如 car[cons[A;B]]；S-expression 只是內部表示。但 Russell 的直譯器直接吃 S-expression——反正 eval 能解釋，何必再寫一層語法？S-expression 從此成為 LISP 的語法——史上最簡單的語法：整個語言只有一條文法規則。

圖靈完備性#

七個基本函數 + 遞迴 = 圖靈完備。McCarthy 證明：用 label 定義遞迴函數，可模擬任何 Turing 機器：

\[ \{atom, eq, car, cdr, cons, cond, quote\} + \mu\text{-recursion} \implies \text{Turing-complete} \]

1962 年的第一個垃圾回收#

McCarthy 在 MIT 實作 LISP 1.5 時遇到記憶體耗盡——鏈結串列不斷被 cons，NIL 卻越積越多。他的解法：垃圾回收（garbage collection）——從「根」出發標記所有可達 cell，其餘回收。這是史上第一個 GC，成為 Java、C#、Go 的祖先。

結案 -- 後果與影響#

AI 的母語：LISP 成為 AI 研究四十年（1958-1990s）的標準語言——Minsky 的 MIT AI Lab、Stanford、CMU 全用 LISP。
函數式程式設計的源頭：閉包、一級函數、尾遞迴、條件表達式——Scheme (1975)、ML、Haskell 的思想都源於 LISP。
GC 的發明：垃圾回收成為現代語言（Java、Python、JavaScript、Go）的標配——McCarthy 1962 年的發明影響至今。
語法的極簡：S-expression 的「code = data」（同像性）催生了 macro 系統——LISP 程式可以寫 LISP 程式。
圖靈獎與歷史定位：McCarthy 1971 年獲圖靈獎，LISP 被公認為繼 FORTRAN 後第二個高階語言——卻是第一個「理論先於實作」的語言。

關鍵人物與文獻#

John McCarthy：Dartmouth 會議發起人，LISP 之父，1971 年圖靈獎。
Steve Russell：把 eval 寫成機器碼，直譯器的實作者。
Timothy Hart / Mike Levin：1962 年 LISP 1.5 的 GC 實作。
文獻：
J. McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I," Comm. ACM 3(4), 184-195 (1960).
J. McCarthy et al., LISP 1.5 Programmer's Manual, MIT Press (1962).
P. Graham, "The Roots of Lisp," (2002) — 對 McCarthy 1960 論文的現代重現。