计算机科学 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