跳轉到

1958：LISP 誕生#

事件#

1958年，John McCarthy 在 MIT 任職（繼 1956 年達特茅斯會議之後），著手設計一種適合符號運算與人工智慧研究的語言，即 LISP（LISt Processor）。同一年，第一個實作在 IBM 704 上完成——Steve Russell 意識到 McCarthy 論文中的 eval 可以直接寫成機器碼，於是實作了史上第一個 LISP 直譯器。LISP 是繼 FORTRAN（1957）之後第二古老的高階語言，也是至今仍存活的最古老高階語言。

語法/特性加入的理論與實用原因#

1. 列表與 S-表達式#

  • 理論原因：AI 研究需要處理符號（符號、邏輯式、語句），而非 FORTRAN 擅長的數值運算。以遞迴定義的列表（element · list）是最自然的符號資料結構。
  • 實用原因：程式與資料同構（homoiconicity）——程式本身就是列表，可以被當成資料操作，這讓「寫程式的程式」成為可能。
  • 彌補缺陷：FORTRAN 與組合語言只能自然表達數值與位址運算，無法表達符號結構，AI 研究者被迫手寫組合語言處理列表。
(+) 1 2 3            ; 前綴記法的列表
'(a b (c d) e)       ; 巢狀符號列表

對照組：要表達「某人的姓名與兩個電話」這種符號結構，LISP 一行即可；在 FORTRAN IV 裡卻必須宣告固定長度的字元陣列，符號的巢狀結構被迫壓平：

C     FORTRAN IV：符號結構必須壓平成固定陣列
      CHARACTER*20 NAME, PH1, PH2
      NAME = 'TURING'
      PH1  = '02-1234'
      PH2  = '02-5678'
C     想再巢狀一層？只能另開陣列，自行記住對應關係

;; 同樣的資料，LISP 自然表達巢狀符號結構
'(person (name turing) (phones "02-1234" "02-5678"))

2. CAR/CDR#

  • 理論原因：操作列表需要「取頭」與「取尾」兩個基本運算，對應列表的遞迴定義。
  • 實用原因：名稱直接來自 IBM 704 硬體——CAR 是 Contents of the Address Register（位址暫存器內容），CDR 是 Contents of the Decrement Register（遞減暫存器內容）。硬體細節就這樣成為語言的一部分，並沿用至今。

CAR/CDR 加上 CONS（建構），就是列表的「解構與建構」兩面，遞迴處理由此展開：

(car '(a b c))            ; => A      取頭
(cdr '(a b c))            ; => (B C)  取尾
(car (cdr '(a b c)))      ; => B      連用可達任何元素
(cadr '(a b c))           ; => B      cadr 即 (car (cdr ...))
(cons 'a '(b c))          ; => (A B C) 把頭接回尾
(cons 1 (cons 2 nil))     ; => (1 2)  列表就是這樣一層層建起來的

3. 條件表達式（COND）#

  • 理論原因：λ 演算本身沒有條件分支；McCarthy 在 1958–1960 年的論文中提出把條件做成「表達式」而非「敘述」，使其有值、可遞迴。
  • 實用原因：遞迴函數需要明確的停止條件；條件表達式讓函數體可以用數學式的方式分支。
  • 彌補缺陷：FORTRAN 的 IF 是敘述且不傳回值，無法寫出自然的遞迴數學定義。
(defun fact (n)
  (cond ((= n 0) 1)
        (t (* n (fact (- n 1))))))

COND 的每個子句是「條件、結果」成對出現，依序測試、命中即求值並傳回——本身就是一個有值的表達式：

;; COND 用途一：分支求值（可出現在表達式中任何位置）
(defun sign (n)
  (cond ((= n 0) 'zero)          ; 命中即傳回符號 ZERO
        ((> n 0) 'positive)
        (t 'negative)))
(sign -5)                          ; => NEGATIVE

;; COND 用途二：遞迴的停止條件
(defun sum-list (l)
  (cond ((null l) 0)               ; 空列表：遞迴底
        (t (+ (car l) (sum-list (cdr l))))))
(sum-list '(1 2 3 4))              ; => 10

對照組：FORTRAN II 的算術 IF 只能依「小於零/等於零/大於零」跳轉三個行號，不傳回值、不能寫遞迴，且每一層遞迴都得靠 GOTO 與手動堆疊模擬：

C     FORTRAN II：條件是敘述，只能跳轉
      IF (N) 10, 20, 30
   10 STOP              ; N < 0
   20 RESULT = 1        ; N = 0
      GOTO 40
   30 ...

4. 遞迴作為主要控制結構#

  • 理論原因：遞迴直接對應數學上的歸納定義，也對應 λ 演算的自我應用（透過 Y 組合子可處理遞迴）。
  • 實用原因：列表是遞迴結構，用遞迴處理列表最為自然。
  • 彌補缺陷：當時主流語言（FORTRAN）幾乎不支援遞迴，控制結構只有迴圈與跳轉。

費氏數列的遞迴定義幾乎是數學式的逐字翻譯：

;; 數學定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (+ (fib (- n 1)) (fib (- n 2))))))

(fib 10)  ; => 55

在 FORTRAN 裡，同樣的邏輯必須用迴圈與變數改寫成迭代（FORTRAN II 根本不能遞迴），而且中間值全靠變數管理：

C     FORTRAN II：只能用迴圈與變數，無遞迴
      IA = 0
      IB = 1
      DO 10 I = 1, 9
      IT = IA + IB
      IA = IB
      IB = IT
   10 CONTINUE
C     答案在 IB；三個變數的角色全靠程式設計師腦內追蹤

5. REPL 的發明#

  • 實用原因：Steve Russell 的直譯器讓使用者可以逐式輸入、立即求值——這就是 Read-Eval-Print Loop（互動式迴圈）的誕生。LISP 也因此成為第一個支援互動式開發的語言，這在當時的批次處理世界是革命性的。

REPL 的互動示意（Read → Eval → Print 不斷循環）：

> (+ 1 2)
3                       ; 讀入、求值、印出，立即回應
> (defun fact (n) (cond ((= n 0) 1) (t (* n (fact (- n 1))))))
FACT                    ; 定義函數，傳回函數名
> (fact 5)
120                     ; 馬上就能測試，不必走完整個編譯流程
> (fact 6)
720                     ; 錯了？改一行再試——互動式開發由此誕生

在 1958 年，FORTRAN 的世界是批次處理：整疊打孔卡片交給電腦，跑完（或編譯錯誤中止）才知道結果，一來一回往往要等數小時。

彌補了什麼缺陷#

LISP 把 1936 年 λ 演算的理論帶進實用：函數可以遞迴、條件可以是表達式、程式可以是資料。它彌補了「高階語言無法表達符號運算與遞迴定義」的缺陷，成為此後數十年 AI 研究的標準載具，也開啟了整個函數式程式設計的實用史。

相關條目#