1958-LISP誕生#

案件摘要#

1958 年秋天，John McCarthy 在 MIT 面對一台 IBM 704，著手調查一樁「程式語言失蹤案」：符號運算（微分、定理證明）需要一種能動態生長的資料結構，但當時的 Fortran 與組合語言都無法勝任。McCarthy 從 1956 年 Dartmouth 會議上聽來的 list processing 概念出發，偵造出一種全新的語言——LISP。破案時刻發生在他寫下 universal function eval 的那一刻：LISP 竟然可以用自己定義自己，如同 universal Turing machine 自我模擬。這樁案件不僅偵破，還開啟了人工智慧黃金時代的「母語」傳統。

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

• 1956 年 Dartmouth 會議：McCarthy 聽到 Newell、Shaw 與 Simon 展示 IPL（Information Processing Language）的 list processing 能力，意識到符號計算需要鏈結串列。
• 符號運算的需求：符號微分、定理證明產生的表示式大小無法預測，需要動態資料結構而非固定長度的陣列。
• Fortran 的缺陷：Fortran（1957）為數值計算設計，只有固定大小的陣列，無法表達遞迴與符號資料。
• 組合語言的痛苦：直接用 IBM 704 組合語言撰寫符號程式，工程量巨大且難以修改。
• McCarthy 需要一種「可證明性」的語言：他想對語言本身做數學推理，而這需要簡潔的語義。

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

線索一：S-expression 與 M-expression#

McCarthy 定義了兩層語法。S-expression（symbolic expression）是資料層：

M-expression（meta expression）是程式層，例如 car[cons[A;B]]。最終 S-expression 取得壓倒性勝利——因為 eval 直接以 S-expression 為輸入，程式即資料（homoiconicity）就此誕生。

線索二：car/cdr/cons 的硬體密碼#

IBM 704 的每個字組有位址（address）與遞減（decrement）兩個暫存器：

• car = Contents of Address part of Register
• cdr = Contents of Decrement part of Register
• cons = 構造（construct）一個新的 pair

三個基本操作構成 pair 的代數：

線索三：universal function eval/apply#

McCarthy 最關鍵的推理：寫下一個函數 eval[e, a]，它接收 S-expression 形式的程式與環境，並求值之。核心結構是 eval 與 apply 互相遞迴呼叫。這使 LISP 成為自己的直譯器，如同 universal Turing machine 模擬任意圖靈機。

破案時刻：用 Python 實作 mini-LISP#

import re

def parse(s):
    tokens = re.findall(r'\(|\)|[^\s()]+', s)
    def read(i):
        if tokens[i] == '(':
            lst, i = [], i + 1
            while tokens[i] != ')':
                x, i = read(i)
                lst.append(x)
            return lst, i + 1
        return tokens[i], i + 1
    return read(0)[0]

def evaluate(e, env):
    if isinstance(e, str):
        if e in env: return env[e]
        if e.lstrip('-').isdigit(): return int(e)  # 數值字面量
        return {'atom': e}
    op = e[0]
    if op == 'quote':  return e[1]
    if op == 'if':     return evaluate(e[2] if truth(evaluate(e[1], env)) else e[3], env)
    if op == 'define':
        if isinstance(e[1], list):  # (define (f p...) body) 語法糖
            env[e[1][0]] = evaluate(['lambda', e[1][1:], e[2]], env)
        else:
            env[e[1]] = evaluate(e[2], env)
        return None
    if op == 'lambda': return ('closure', e[1], e[2], env)
    if op in ('car',): return evaluate(e[1], env)[0]
    if op == 'cdr':    return evaluate(e[1], env)[1]
    if op == 'cons':   return [evaluate(e[1], env), evaluate(e[2], env)]
    if op in ('+', '-', '*'):
        a, b = evaluate(e[1], env), evaluate(e[2], env)
        return {'+': a + b, '-': a - b, '*': a * b}[op]
    if op == '=':      return evaluate(e[1], env) == evaluate(e[2], env)
    f = evaluate(op, env)
    args = [evaluate(x, env) for x in e[1:]]
    return apply(f, args)

def truth(v): return v not in (False, [], None)

def apply(f, args):
    _, params, body, env = f
    return evaluate(body, dict(env, **dict(zip(params, args))))

env = {}
evaluate(parse('(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))'), env)
print(evaluate(parse('(fact 5)'), env))  # 120

這段程式重現了 1960 年論文中的 eval：LISP 用不到百行就能自我定義。

補充線索#

• lambda 記法直接取自 Church 的 λ-Calculus；LISP 1.5 手冊加入 FUNCTION 標記以區分函數值（lexical closure 的前身）。
• 遞迴是一等公民：fact 直接以遞迴定義，這在 Fortran 中不可能。
• 條件表達式（conditional expression）：McCarthy 對 Algol 委員會的貢獻，(if c a b) 讓遞迴定義可以落地。
• 垃圾回收：cons 不斷配置新 cell，無人手動釋放——這個懸案成為 1960 年的另一件案子（詳見下一篇）。

結案 -- 後果與影響#

• LISP 1（1958）、LISP 1.5（1962，MIT Press 手冊）確立語言規格，成為 AI 研究的標準工具。
• AI 黃金時代的母語：SHRDLU（Winograd, 1970）、ELIZA（Weizenbaum, 1966）皆以 LISP 撰寫。
• 「程式即資料」（homoiconicity）概念影響巨集系統、REPL 文化與後繼語言。
• 語言譜系：Scheme（1975）、Common Lisp（1984）、Clojure（2007）、Racket 皆為其後裔。
• 函數式編程核心概念——遞迴、一級函數、條件表達式——經由 LISP 進入主流。

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

• John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", Communications of the ACM, 3(4), 1960, pp. 184–195.
• John McCarthy et al., LISP 1.5 Programmer's Manual, MIT Press, 1962.
• John McCarthy, "Programs with Common Sense", Proceedings of the Symposium on Mechanization of Thought Processes, 1958（Dartmouth 時代的思想背景）.
• Paul Graham, "The Roots of Lisp", 2002（對 1960 年論文的現代重述）.
• Herbert Stoyan, "Early LISP History (1954–1959)", ACM SIGPLAN Symposium on LISP and Functional Programming, 1984.