計算機科學 1960

符號表達式的遞迴函數及其機器計算，第一部分

約翰·麥卡錫

程式與資料是同一種串列——而一個小小的 eval，便能執行牠們全部。

Choose your version

In depth · the introduction

如果一個程式，竟與它所處理的資料是同一種材料造的——以至於它讀取、構造、執行別的程式，就像你把兩個數相加那樣輕鬆，會怎樣？

把這個想法拆開看

麥卡錫的 LISP，幾乎是從「無」中搭起來的。萬物——資料也好，程式也好——都是 S-表達式：要麼是一個樸素的符號，比如 A，要麼是兩個表達式合成的序對，寫作 (e1 · e2)。有了兩個把序對拆開的運算（car 取左半，cdr 取右半）、一個把序對建起來的運算（cons），再加上兩個問句——「這是單個符號嗎？」「這兩個符號一樣嗎？」——你就能拼出任意形狀的串列。

妙處在於：一個 LISP 程式，自己也不過是這樣一張串列。於是麥卡錫能寫下一個簡短的函數 eval，它接收任意「化作串列的程式」並執行之——一臺用它所解釋的語言寫成的直譯器。把「如何拆開、如何拼合、如何在情形間抉擇、如何再次呼叫自己」都定義好，你便有了一臺完整的、通用的電腦。

它從哪裡來

1958 年，時在麻省理工的麥卡錫，提出了「Advice Taker（建議接受者）」——一個能用日常事實來推理的程式。要造出它，他需要一門處理符號與表達式、而不只是數字的語言；正是從這個目標裡，在 IBM 704 上長出了 LISP——「LISt Processor（串列處理器）」的縮寫。他於 1960 年把這套設計發表在《ACM 通訊》上。他原是把 eval 當作一段理論寫下的；學生史蒂夫·羅素卻意識到，它可以徑直敲進機器裡，於是第一個 LISP 直譯器驟然現身——這讓麥卡錫頗感意外。

它為何重要

LISP 把整個計算世界如今習以為常的一些想法，作為可執行的部件引入：if-then-else 的抉擇；讓一個函數呼叫自身來定義自己（遞迴）；作為通用容器的串列；以及——悄無聲息地——自動的記憶體清理，麥卡錫後來給它起名「垃圾回收」。它做了三十年人工智慧的語言，也是仍在使用的、僅次於 FORTRAN 的第二古老的高階語言。

一個類比

想想樂高。一個原子，是一塊單獨的積木；一個序對，是兩樣東西扣在一起。car 與 cdr 就是「取左邊那塊」和「取右邊那塊」；cons 則是「把兩塊扣到一起」。再設想：某個模型的拼裝說明書，本身也能用樂高積木拼出來。那麼，你就能把一份它自己的說明書遞給這個模型，讓它把自己搭起來。這種自我指涉——程式與資料由同一種積木造成——正是 LISP 的全部訣竅。在下方的工具裡，親手把表達式拆開試試。

它身處何處

LISP 是阿隆佐·丘奇的 λ-演算（1936）與艾倫·圖靈的機器（1936）——「什麼是可計算的」之抽象答案——的實踐孿生，被化作了一門你真能執行的語言。約翰·巴克斯的 FORTRAN（1957）讓數值計算變快，而麥卡錫，讓符號計算成為可能。它的血脈經由 Scheme 與 Clojure 一直流到今天，而它所開創的垃圾回收，如今就活在 Java、Python 和 JavaScript 之中。

The original document

Original source text

J. McCarthy · Communications of the ACM, Vol. 3, No. 4, pp. 184–195 · April 1960

1 · Introduction

A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T.

The system was built to support the "Advice Taker," McCarthy's 1958 proposal for a program that could reason with declarative and imperative sentences. Numbers were not enough; the project needed a way to manipulate symbolic expressions, and so the paper begins not with the machine but with a class of expressions and the functions over them.

2 · Functions and Function Definitions

the notion of conditional expression is believed to be new, and the use of conditional expressions permits functions to be defined recursively in a new and convenient way.

A conditional expression (p1 → e1, ⋯, pn → en) is evaluated left to right. With it, a function may be defined by a formula that mentions itself without circularity — for example n! and the example function ff. Forms are turned into functions by Church's λ-notation; recursive functions are named with label. (The if … then … else that ALGOL 60 adopted, suggested by John Backus, descends from McCarthy's proposal.)

3 · Recursive Functions of Symbolic Expressions

1. Atomic symbols are S-expressions. 2. If e1 and e2 are S-expressions, so is (e1 · e2).

A list (m1, ⋯, mn) abbreviates the nested pairs (m1 · (m2 · (⋯ (mn · NIL) ⋯))). Five elementary functions act on S-expressions: the predicates atom and eq, and the constructors and selectors car, cdr, cons.

car [cons [x; y]] = x · cdr [cons [x; y]] = y · cons [car [x]; cdr [x]] = x, provided that x is not atomic.

car and cdr are undefined on atoms. Their names come from the IBM 704: "car" is a mnemonic for "contents of the address part of register," "cdr" for "contents of the decrement part of register," and "cons" is an abbreviation for "construct." From these five primitives, plus composition, conditionals, and recursion, McCarthy builds all computable functions of symbolic expressions.

The universal function

the universal S-function apply which plays the theoretical role of a universal Turing machine and the practical role of an interpreter.

Because S-functions can themselves be written as S-expressions, a single function eval (called through apply) takes the representation of any function together with its arguments and returns the value — an interpreter for the language written in the language itself.

4 · The LISP Programming System

S-expressions are stored on the IBM 704 as list structure: linked machine words whose address and decrement parts hold car and cdr. Free memory is kept on a free-storage list, from which cons takes a word.

Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts.

The reclamation marks every register reachable from the base registers by car–cdr chains and returns the rest to the free-storage list — the automatic storage management McCarthy would later name garbage collection.

[ … ]

M.I.T. · Communications of the ACM · April 1960