跳轉到

1962：LISP 1.5——GC 與巨集正式化#

事件#

1962年，MIT 出版 《LISP 1.5 Programmer's Manual》（McCarthy、Abrahams、Edwards、Levin、Levin 著），這是第一個正式且廣泛使用的 LISP 版本，被安裝在數十台電腦上。LISP 1.5 將垃圾回收（GC）、巨集系統、一級函數與高階函數正式化，奠定了 LISP 家族的標準形態。

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

1. 垃圾回收（Garbage Collection）#

  • 理論原因：列表是動態配置的遞迴結構，函數式風格大量產生中間列表；若無法自動回收，純函數式運算在記憶體上不可行。
  • 實用原因：McCarthy 在 1960 年的論文中已提出想法，1962 年 LISP 1.5 手冊正式化 標記-清除（mark-sweep） 演算法——從根集合標記所有可達的 cons cell，再清除未標記者。 GC 的核心概念：CONS 不斷產生新 cell，用不到的舊 cell 由標記-清除自動回收——程式設計師完全不必（也不能）插手：
;; 標記-清除（mark-sweep）概念示意
;; 假設記憶體是一排 cons cell：
  [a|•]→[b|/]   [c|•]→[d|/]   [e|/]
   ↑根集合可達        ↑沒有任何變數指向 c、d、e

;; 1. 標記階段：從根集合（如變數 x 的值）出發，標記所有可達 cell
;;    → a、b 被標記
;; 2. 清除階段：掃過整個記憶體，把未標記的 c、d、e 放回自由串列
;;    → c、d、e 的空間自動回收，可供之後的 CONS 重複使用

;; 程式面：中間列表用完即丟，GC 在背後默默善後
(setq x (mapcar (function (lambda (n) (* n n))) '(1 2 3 4)))
;; 運算過程產生的 4 個中間 cell 與臨時結構，
;; 全都不需手動釋放——這是史上第一個自動記憶體管理

對照組：在沒有 GC 的語言（如 C）裡，同樣的結構要手動配置與釋放，漏掉 free 就是記憶體洩漏：

/* C（1972，為對照而引用）：手動記憶體管理 */
struct node *p = malloc(sizeof(struct node));
/* ...使用 p... */
free(p);          /* 忘了這行 → 記憶體洩漏；提早這行 → 懸吊指標 */

2. 巨集（Macro）系統#

  • 理論原因：程式即資料（S-表達式同構性）意味著程式可以被程式轉換——巨集就是「編譯期對程式做 β-歸約式的改寫」。
  • 實用原因：LISP 1.5 提供巨集機制讓使用者以 LISP 本身擴充語言，新增控制結構與語法糖，而不需修改直譯器。
  • 彌補缺陷：傳統語言的語法是固定的，使用者無法新增語言結構；巨集讓語言成為「可自我擴充的語言」，這是 LISP 至今的招牌特性。
(defmacro when (test &rest body)
  `(cond (,test ,@body)))

巨集在編譯期對程式做改寫：呼叫 (when ...) 時，巨集函數先算出展開式，再求值展開後的程式——語言就這樣被使用者擴充：

;; unless 巨集：與 when 相反的測試
(defmacro unless (test &rest body)
  `(cond ((not ,test) ,@body)))

;; 展開過程（macroexpand 所見）：
;; (unless (= x 0) (print 'not-zero))
;;   ⇒ (cond ((not (= x 0)) (print 'not-zero)))
;;   ——本來不存在的語法，被使用者「發明」出來

(when (> x 0) (print 'positive))
(unless (null l) (print (car l)))

LISP 1.5 時代巨集甚至可以自己動手組 S-表達式（不用反引號語法，當年正是這樣寫的）：

;; LISP 1.5 風格：手動用 list/cons 組出展開式
(defmacro while (test &rest body)
  (list 'cond
        (list (list 'not test) nil)
        (cons 'progn (append body
                             (list (cons 'while (cons test body)))))))
;; 展開成遞迴呼叫自身，模擬出迴圈——控制結構由函式庫供應

3. 函數作為一級值與高階函數#

  • 理論原因：λ 演算中函數本來就是一級公民——可以傳遞、傳回、組合。LISP 1.5 讓這點真正落地。
  • 實用原因：列表處理天然需要「把函數套用到每個元素」——mapcar 等高階函數成為標準庫的一部分。
  • 彌補缺陷：FORTRAN 的副程式不能作為資料傳遞；一級函數讓控制抽象（如 map、filter）成為可能。
;; 高階函數：把函數當資料傳遞
(mapcar (function (lambda (x) (* x x))) '(1 2 3 4))
; => (1 4 9 16)

;; filter 風格：選出偶數
(defun evens (l)
  (cond ((null l) nil)
        ((= (rem (car l) 2) 0) (cons (car l) (evens (cdr l))))
        (t (evens (cdr l)))))
(evens '(1 2 3 4 5 6))   ; => (2 4 6)

;; 函數作為引數傳入另一個高階函數
(defun apply-twice (f x)
  (funcall f (funcall f x)))
(apply-twice (function (lambda (n) (* 10 n))) 3)   ; => 300

對照組：FORTRAN 的副程式是固定的位址，無法作為值傳遞——「把平方函數套到每個元素」只能為每種運算各寫一個迴圈：

C     FORTRAN：每種運算都要一個專屬副程式與迴圈
      SUBROUTINE SQUARE (A, N)
      DIMENSION A(100)
      DO 10 I = 1, N
      A(I) = A(I) * A(I)
   10 CONTINUE
      RETURN
      END

(mapcar (function (lambda (x) (* x x))) '(1 2 3 4))
; => (1 4 9 16)

4. FUNARG 問題——作用域之爭的起點#

  • 理論原因：λ 演算採詞法作用域（變數的意義由定義處決定），但 LISP 1.5 的實作採動態作用域（由呼叫處決定），兩者理論上不一致。
  • 實用原因：當函數可作為傳回值（funarg），動態作用域會使自由變數指向呼叫時的環境而非定義時的環境，產生難以預測的行為。
  • 彌補缺陷：FUNARG 問題暴露了動態作用域的缺陷，直接引發了長達二十年的詞法 vs 動態作用域之爭，直到 1975 年 Scheme 才徹底解決。

動態作用域的陷阱實例：同一個函數、不同的呼叫環境，自由變數的意義竟不相同——函數的行為無法脫離呼叫處預測：

;; LISP 1.5 動態作用域：自由變數 z 在「呼叫時」才綁定
(defun add-z (x) (+ x z))     ; z 是自由變數

;; 呼叫環境一：恰好有 z
(setq z 100)
(add-z 1)                     ; => 101  （z 來自呼叫處）

;; 呼叫環境二：換了呼叫者，行為就變了
(defun caller-without-z (f) (funcall f 1))
(caller-without-z (function add-z))  ; z 未定義 → 錯誤或得到不可預測的值

對照組：λ 演算（及後來的 Scheme）採詞法作用域，同一個閉包不管從哪裡呼叫，結果都一樣：

;; Scheme 詞法作用域：z 在定義處綁定
(define z 100)
(define (add-z x) (+ x z))
(add-z 1)                     ; => 101
((lambda (f) (f 1)) add-z)    ; => 101  行為永遠可預測

彌補了什麼缺陷#

LISP 1.5 彌補了三個實用化缺口：GC 解決了函數式風格的記憶體管理問題、巨集解決了語言無法擴充的問題、一級函數與高階函數讓 λ 演算的表達力真正可用。同時 FUNARG 問題誠實地暴露了實作與理論的落差，為後繼者（Scheme）留下了明確的待解難題。

相關條目#