1958 - McCarthy 發明 LISP#

案件摘要#

1958 年，John McCarthy 在 MIT 以 λ 演算為內核，發明 LISP—— 史上第二古老的高階程式語言。他把「函數即資料」的推理帶入實作，誕生了垃圾回收、遞迴函數、條件表達式與 eval/apply—— λ 演算從紙上理論首次成為可執行的程式語言。

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

1956 年 Dartmouth 會議上 McCarthy 首次提出「人工智慧」一詞，他的目標是讓電腦處理符號推理，需要一門「符號處理語言」。
當時主流是 Fortran（1957），為數值計算設計，處理鏈結串列、符號表達式極為笨拙。
McCarthy 曾閱讀 Church 的《The Calculi of Lambda-Conversion》（1941），並受 Curry 的組合邏輯影響，深知「函數即一級公民」的威力。
線索：Church 數字證明函數可用 λ 項表示——那麼資料也可以用函數表示，程式與資料可以合而為一。

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

McCarthy 如何接觸 λ 演算#

McCarthy 在普林斯頓數學系讀博士（1951 年），期間研讀 Church 與 Curry 的著作。
他最初嘗試以「函數表示法」設計語言，發現 λ 演算的記號可直接借用，但他偏好更易讀的寫法：把 \(\lambda x.\ M\) 寫成 (lambda (x) M)。
1958 年秋，McCarthy 的學生 Steve Russell 建議：eval 函數可以用機器碼實作——LISP interpreter 就此誕生。

S-表達式：資料即程式#

LISP 的核心概念是 S-表達式（symbolic expression）：

expr ::= atom | (expr expr ...)

λ 抽象寫成：

(lambda (x) (* x x))     ; 即 λx. x * x

呼叫：

((lambda (x) (* x x)) 5)  ; 求值為 25

資料與程式同構：

'(a b (c d))   ; quote 使 S-表達式成為資料
(car '(a b c)) ; 求值為 a

eval/apply：λ 演算的實作核心#

McCarthy 定義兩個相互遞迴的函數：

eval(e, a)：求表達式 \(e\) 在環境 \(a\) 中的值
apply(f, x)：將函數 \(f\) 作用於參數 \(x\)

eval/apply 的數學骨架就是 λ 演算的兩條規則：

\[ \text{eval}((\lambda x.\, M)\ N, a) = \text{eval}(M, a[x \mapsto \text{eval}(N, a)]) \]

\[ \text{eval}(x, a) = a(x) \]

CAR / CDR / CONS：鏈結串列的三劍客#

函數	意義	數學對應
`(car x)`	取串列首元素	\(x = (h, t) \Rightarrow h\)
`(cdr x)`	取串列尾	\(x = (h, t) \Rightarrow t\)
`(cons h t)`	建構配對	\(h : t\) （cons cell）

對應 λ 演算中的 Church 配對：

\[ \mathrm{pair} = \lambda h.\lambda t.\lambda f.\, f\ h\ t \]

\[ \mathrm{car} = \lambda p.\, p\ (\lambda h.\lambda t.\, h), \quad \mathrm{cdr} = \lambda p.\, p\ (\lambda h.\lambda t.\, t) \]

垃圾回收（Garbage Collection）#

LISP 首創 GC：cons cell 動態配置於 heap，當不再被引用時自動回收。 McCarthy 與團隊實作了「標記-清除（mark-and-sweep）」演算法：

1. Mark：從 roots（暫存器、堆疊）出發，標記所有可達 cell
2. Sweep：掃描整個 heap，回收未標記的 cell

這是現代 Java、Python、Go 等語言 GC 的共同祖先。

遞迴函數#

LISP 原生支援遞迴（當時罕見）：

(defun factorial (n)
  (cond ((= n 0) 1)
        (t (* n (factorial (- n 1))))))

對應數學定義：

\[ n! = \begin{cases} 1 & n = 0 \\ n \cdot (n-1)! & n > 0 \end{cases} \]

Y 組合子模擬匿名遞迴：

((lambda (f) ((lambda (x) (f (x x)))
              (lambda (x) (f (x x)))))
 (lambda (fact) (lambda (n)
   (if (= n 0) 1 (* n (fact (- n 1)))))))

一個簡單的 Python 版 LISP interpreter#

import math

def tokenize(s):
    return s.replace('(', ' ( ').replace(')', ' ) ').split()

def parse(tokens):
    t = tokens.pop(0)
    if t == '(':
        return [parse(tokens) for _ in range(int(tokens.count(')')))]
    try:
        return float(t) if '.' in t else int(t)
    except ValueError:
        return t

def parse_all(s):
    toks = tokenize(s)
    result = []
    while toks:
        result.append(parse(toks))
    return result

env = {'*': lambda a: math.prod(a),
       '+': lambda a: sum(a),
       '-': lambda a: a[0] - sum(a[1:]),
       'car': lambda a: a[0][0],
       'cdr': lambda a: a[0][1:],
       'cons': lambda a: [a[0]] + a[1],
       '=': lambda a: a[0] == a[1],
       'quote': lambda a: a[0]}

def eval(x, e=env):
    if isinstance(x, str):
        return e[x]
    if isinstance(x, (int, float)):
        return x
    op, *args = x
    if op == 'lambda':
        params, body = args[0], args[1]
        return lambda a: eval(body, {**e, **dict(zip(params, a))})
    if op == 'if':
        return eval(args[1] if eval(args[0], e) else args[2], e)
    if op == 'defun':
        e[args[1]] = eval(['lambda', args[2], args[3]], e)
        return args[1]
    f = eval(op, e)
    return f([eval(a, e) for a in args])

print(eval(parse_all('((lambda (x) (* x x)) 5)')[0]))        # 25.0
print(eval(parse_all("(car (cons 1 (cons 2 ())))")[0]))       # 1
print(eval(parse_all("(defun fact (n) (if (= n 0) 1 (* n (fact (- n 1))))) (fact 5)")[1]))  # 120

結案 -- 後果與影響#

LISP 成為 AI 研究的標準語言（直到 1990 年代），催生了 Scheme（1975）、 Common Lisp（1984）。
垃圾回收成為現代語言的標配（Java、C#、Python、Go、JavaScript）。
遞迴、一級函數、閉包進入主流：JavaScript、Python、Ruby 皆受影響。
eval/apply 模型成為所有 interpreter 的教科書架構。
LISP 的 S-表達式啟發了後世的 homoiconicity（同像性）與巨集系統。
McCarthy 後續提出 conditional expression（1960），補足了 Church 演算缺乏的條件式，成為現代 if-then-else 的起源。

關鍵人物與文獻#

John McCarthy（1927–2011）：LISP 發明人，「人工智慧」一詞創造者。
Steve Russell：第一個 LISP interpreter 的實作者。
McCarthy, J. (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Comm. ACM 3(4), 184–195.
McCarthy, J. et al. (1962). LISP 1.5 Programmer's Manual. MIT Press.