History of Lisp，中文翻译

Programming
1

目录

本文为 LISP 发明人 John McCarthy 于 1979 年 2 月 12 日 发表的论文 的中文翻译。这篇论文讲述了 1956 年至 1962 年间 LISP 的历史——1962 年后 LISP 开枝散叶，不同思想无法一一描述。

话说四十多年前是不是常用长难句？原文第一节第三段居然只有俩句号。不过在我的领域，每句话（逗号分隔）都不会超过 25 个字的。

1. 引言

这份草稿对许多帮助实现 Lisp 和贡献想法的人提及不足。特别欢迎在这些方向的改进建议。尤其需要 FUNARG 历史和 uplevel 寻址细节的信息。

本文着重于基本思想的开发，并区分了两个时期——1956 年夏季至 1958 年夏季，期间大部分关键思想得以形成（其中一些实现于 FORTRAN 的 FLPL 上）；以及 1958 年秋季至 1962 年，期间该编程语言被实现并应用于人工智能问题。1962 年后，LISP 的开发变得多线并行，不同地方追求着不同的思想。

如果本文没有指出某个想法应该归功于谁，那么应该把它视作我的成果，或者之前某个想法的产物。然而，过去我曾在这方面犯过错误，并且几乎没有收到注解本文草稿的请求。我们认为显然的功能，说不定是别人好不容易想出来的呢？随着本文写作接近尾声，我逐渐意识到还有更多信息来源不够准确，还有更多领域无法确定。

LISP 这门编程语言的特点如下：用符号表达式而非数字进行计算；符号表达式和其它数据结构在计算机内存中表示为链表；在外部媒介中则通常用嵌套列表表示，少数情况下也会用所谓 “S-表达式” 表示。“S-表达式” 是一小簇操作的集合，包含：

  1. 选择器和构造器，都用函数表示。
  2. 函数的组合，用来制造更复杂的函数。
  3. 条件表达式，用来实现分支结构。
  4. 在递归里使用条件表达式，从而表示所有可计算函数。
  5. λ 表达式，用来实现具名函数1。
  6. 把 LISP 程序表达为 LISP 数据的能力。
  7. 用条件表达式解释逻辑连词。
  8. LISP 函数 eval ，既是语言的形式化定义，也是该语言的解释器。
  9. 最后是垃圾回收，管理内存的一种手段。

在分时操作系统上，LISP 语句也可以用作命令行语言。

这些想法中有些来自其他编程语言，但大多是原创的。在初始阶段接近尾声时，我们逐渐意识到这一系列想法不仅构成了优雅的数学系统，而且还形成了实用的编程语言。随后，数学上的简洁性成为目标，因此我们从语言核心中删减了一些特性。这既受到审美考虑的驱动，也源于一种信念：如果语义紧凑且没有例外情况，那么证明程序正确性的技术会更容易。经过了 (Cartwright 1976) 和 (Cartwright 和 McCarthy 1978) 两篇论文的研究，我们发现 LISP 程序可以解释为一阶逻辑的句子（sentences）和模式（schemata），这些成果为最初的直觉——逻辑简洁会带来回报——提供了新的证据。

2. LISP 史前史——1956 年夏至 1958 年夏

1956 年夏，达特茅斯人工智能暑期研究项目（Dartmouth Summer Research Project on Artificial Intelligence）正在进行，这是首次有组织的人工智能研究。期间，我初次产生了对代数式列表处理语言的需求，这种编程语言需要在 IBM 704 计算机上进行人工智能工作。在这个会议上，Newell、Shaw 和 Simon 描述了 IPL 2，用于 Rand 公司 JOHNNIAC 计算机的列表处理语言。他们在这个语言实现了他们的 Logic Theorist 程序。然而复制 IPL 的诱惑并没有多少，因为 IPL 的形式基于他们刚好可用的 JOHNNIAC 加载器，而且 FORTRAN 用代数方式编写程序的想法很有吸引力。人们很快意识到，只要组合直接子式的提取函数，立即就可以得到符号表达式的任意子式的提取函数，这似乎足以证明转向代数语言是合理的。

在 IBM 704 上开发语言有两个动机。第一，IBM 在麻省理工学院建了个新英格兰计算中心，用在达特茅斯学院中。够有钱的。第二，IBM 正在开发一个证明平面几何定理的程序（基于 Marvin Minsky 的想法），而我将担任该项目的顾问。当时看来，IBM 是追求人工智能研究的良好选择，甚至连进一步的项目预期都有。当时还不清楚 IBM 的 FORTRAN 项目会不会引出子语言，以进行方便的列表处理，如果不然则需要从头开始构造一种新的语言。然而，许多考虑因素与结果无关。

除了几何证明程序之外，我自己的人工智能研究正沿着导致 1958 年 Advice Taker 提案的路线进行（McCarthy，1959 年）。我们需要一种合适的形式语言，其中的句子可以表示关于世界的信息，然后需要用逻辑确定行为的推理程序。当时看来，用列表结构表示句子还挺合适——现在也是——而且列表处理语言也适合编程推理中涉及的运算——现在也是。

这种符号信息的内部表示放弃了熟悉的中缀记法，转而采用一种简化编程实质性计算任务（例如逻辑推理或代数化简、微分或积分）的记法。非要用常规记法的话，就必须编写翻译程序。因此，大多数 LISP 程序使用前缀记法来表达代数表达式，因为它们通常必须在决定下一步该做什么之前确定动词。在这方面，LISP 与其他几乎所有的符号计算系统都不同。COMIT、FORMAC 和 Formula Algol 程序都认为 “计算” 是符号表达式的某种打印形式上的操作。SNOBOL 操作字符串，但对字符串如何表示符号表达式持中立态度。这一特点很可能解释了 LISP 在与这些语言竞争中的成功，尤其是在需要编写大型程序时。这种优势类似于二进制计算机相对于十进制计算机的优势——但更为显著。

（20 世纪 50 年代末，通常没人觉得整洁的输出和方便的输入符号很重要。当时可用的内存甚至连当今常见的输入输出程序都装不下。而且，带有足够字符集的键控穿孔机和打印机当时还不存在。）

第一个问题是如何在 IBM 704 上实现列表结构。这台计算机字长 36 比特，每个字中有两个 15 位字段，名叫 “地址” 和 “减量”，通过特殊的指令可以移动入 15 位的变址寄存器，也可以从变址寄存器中获取。机器的地址长 15 比特，因此很明显列表结构应该使用 15 位指针。自然每个字应该分成 4 个字段，即地址字段、减量字段、前缀（prefix）字段和标签（tag）字段。最后两个字段各为 3 位，因为位于减量字段两边，所以不好合并成一个 6 位的部分。

这时我们还没有确定基本操作符应该是什么。基本操作符涉及到 “用掩码提取字的一部分” 和 “提取内存某一个字” 这两种操作，它们各自是否应视作关于地址的函数？我们认为这两个回答之间并没有太大的关系。以当时的视角来看，将后者叫做函数有点怪，因为其值取决于操作执行时内存的内容，不像真正的、数学里的函数。但是，如果语法上把它当作函数，那样就能像函数一样组合，这个优点无法忽略。

因此，最初提出的函数集包括 cwr，代表 “指定位置内存存储的字（Contents of the Word in Register number）”，以及提取机器字的指定字段、或者将它们移到机器字右侧标准位置的四个函数。还提出了一个三参数的额外函数，用来提取任意的比特序列。

很快我们注意到，提取子表达式需要组合地址字段的提取函数与 cwr，而沿列表向后处理则需要组合减量字段的提取函数与 cwr。因此，我们定义了 “指定位置内存的地址字段内容（Contents of the Address part of Register number）”的复合操作 car。类似地，我们还定义了 cdr、cpr 和 ctr。因为 IBM 704 有（与索引相关的）指令，我们想单独实现 car 和 cdr。显然还需要一个构造操作，从空闲内存列表（free storage list）中拿走一个字，然后用给定内容填充它。某个时刻 cons(a, d, p, t) 出现了，但它是子例程，而不是可以返回值的函数。这项工作是在达特茅斯完成的，但没有实现在计算机上，因为新英格兰计算中心预计一年以内都收不到 IBM 704。

在 IBM 的平面几何项目相关工作中，Nathaniel Rochester 和 Herbert Gelernter（在 McCarthy 的建议下）决定在 FORTRAN 中实现一种列表处理语言。当时看来在 FORTRAN 里实现是最简单的方式，因为我们当时认为开发新语言的编译器至少需要许多年的人力。这项工作由 IBM 的 Herbert Gelernter 和 Carl Gerberich 进行，并导致了 FLPL 的诞生，即 FORTRAN 列表处理语言（Fortran Lisp Processing Language）。Gelernter 和 Gerberich 注意到 cons 应该是函数，而不仅仅是子例程，并且它的返回值应该是从空闲内存列表中获取的机器字的地址。通过这个改进，我们可以通过 cons 的组合来用子表达式构建新的表达式。

在 FLPL 中，表达式可以很容易地处理，并且它成功用于几何程序，但它既没有条件表达式也没有递归，并且列表结构的删除需要程序显式处理。

条件表达式的发明要从 1957-58 年，我在 MIT 工作时的 FORTRAN 程序说起。那时我在 IBM 704 上编写了一组国际象棋合法移动的例程。这个程序没有用到列表处理。FORTRAN 1 和 FORTRAN 2 中提供的 IF 语句2用起来非常不方便，因此自然地发明了一个函数 XIF(M, N1, N2)，其根据表达式 M 是否为零而返回 N1 或 N2。这个函数缩短了许多程序，也大大降低了理解难度，但必须谨慎使用，因为所有三个参数都必须在进入 XIF 之前被求值，因为尽管 XIF 是用机器语言编写的，但它作为普通的 FORTRAN 函数被调用。这导致了真正的条件表达式的发明，它根据 M 是真还是假而只求值 N1 和 N2 中的一个。进一步，我渴望一种允许使用条件表达式的编程语言。

我写了篇论文来定义条件表达式，并且提议了在 ALGOL 中的用法。但是这篇论文寄往 CACM 时居然给降级成编辑来信了，因为它非常短。

1958 年的夏天，我应 Nathaniel Rochester 的邀请在 IBM 信息研究部门度过。我选择了求导代数表达式作为样例问题。这导致了以下超越 FLPL 的革新：

  1. 用条件表达式定义递归函数。

    求导的思路显然是递归的，而条件表达式允许将各种情况合并为一个公式。

  2. maplist 函数，它把一个函数应用于列表的每个元素，形成一个新的列表。这显然是为了求导任意多个项的和，稍作修改后，它也可以用于区分乘积。（最初的版本现在被称为 mapcar ）。

  3. 要将函数作为参数使用，就需要一个函数的表示法，自然想到丘奇（1941）的 λ 表示法。我没看懂他论文的其余部分，因此没有尝试实现他更通用的函数定义机制。丘奇使用高阶函数而不是条件表达式，但是条件表达式在计算机上更容易实现。

  4. 求导显然可以用递归定义出，但是其过程中会产生废弃的列表结构，释放它们所占用内存的方法并不那么显然。显式释放内存不够吸引人，它会把优雅的求导弄得一团糟。不用说，这个练习的重点不是求导程序本身（其中已经有一些程序被编写出来），而是澄清符号计算中涉及的运算。

事实上，那个夏天并没有实现求导程序，因为 FLPL 既不支持条件表达式，也不支持子例程的递归调用。我们需要新的语言，因为无论技术上还是政治上修改 Fortran 都非常困难，而且条件表达式和递归都无法用机器语言 Fortran 函数实现——哪怕用上可以修改调用自己的代码的 “函数” 也无法实现。此外据我观察， IBM 小组对现有的 FLPL 似乎很满意，并不想允许条件表达式和递归所需的模糊却又剧烈的改变。我记得他们争论说这些东西没必要。

3. LISP 的实现

1958 年秋，我当上了麻省理工学院通信科学系的助理教授（隶属于电子工程系），并与 Marvin Minsky（当时是数学系的助理教授）启动麻省理工人工智能项目。该项目由麻省理工电子研究实验室支持，后者与武装部队签了合同，这份合同给了主任——Jerome Wiesner 教授——极大的自由度。他有权启动他自己看来有科研意义的新项目，连书面提案都不用写。Wiesner 问我和 Minsky 这个项目有没有什么需要的，我们要了一个房间、两个程序员、一个书记还有一台键控打孔机。电子研究实验室承诺了六位数学研究生的技术支持，所以他还让我们顺便照看一下其中的几位。

LISP 的实现始于 1958 年秋季。最初的设想是开发一个编译器，但后来认为这项认为过于庞大，我们需要进行一些实验来制定出关于子程序链接、栈处理和内存释放的良好规范。因此，我们首先手工将各种函数编译成汇编语言，并编写子程序来提供一个 LISP “环境”。这些程序里有一个用来读取和打印列表结构。 LISP 数据在外部用括号列表表示，但是我已经记不清是这时做出的决定，还是讨论求导的时候就已经使用了。

需要手工编译的程序用所谓 “M-表达式” 编写，这是一种非正式的符号，旨在尽可能类似于 FORTRAN。除了 FORTRAN 式的赋值语句和 GOTO 语句外，该符号还允许条件表达式和 LISP 的基本函数。递归函数不需要 FORTRAN I 中新的函数定义符号——只是限制的移除而已——根据我的记忆，FORTRAN 手册中并未明确说明——禁止递归定义。M-表达式还使用方括号而不是圆括号来包围函数的参数，以便保留圆括号用于列表结构常量。本来的目的是把 M-表达式的某种近似形式编译成目标语言，但是后来解释器先一步出现，那时用 LISP 列表表示 LISP 函数已成为主流语法，因此 M-表达式从未被完全定义。机器可读的 M-表达式需要重新定义，因为手工 M-表达式使用的字符在 IBM 026 键盘穿孔机上是不可用的。

READ 和 PRINT 程序实际上建立了一种符号信息的标准外部表示法，例如用 (PLUS X (TIMES 3 Y) Z) 表示 x + 3y + z，用 (ALL (X) (OR (P X) (Q X Y))) 表示 (∀x)(P(x) ∨ Q(x, y)) 。其他表示法同样需要特殊编程，因为标准的数学表示法中不同的运算符的句法也不同。这种表示法后来被称为 “剑桥前缀表示法”，因为它类似于 Lukasiewicz 的前缀表示法，而且我们注意到 Quine 也使用了一种括号前缀表示法。

内存释放问题也需要考虑，像 IPL 那样的显式释放内存显然不好看。有两种替代方案。第一种是在更新程序变量时释放其旧内容所占用的内存。由于 car 和 cdr 操作不会复制结构，因此列表结构是可以共用的，进而释放内存需要一个引用计数系统。因为每个字里只剩下六比特能用了，并且这些比特分散在字的各个部分，如果没有对列表结构的表示方式进行重大改变，引用计数似乎是不可能实现的。（后来 Collins（1960）在 48 位的 CDC 计算机上使用引用计数的内存管理方案。）

第二种选择是垃圾回收，这种方案中，用过的内存会被丢弃，直到空闲内存列表耗尽，这时标记所有可以从程序变量和堆栈中访问的内存，然后把未标记的内存转化为新的空闲存储列表。如果我们决定采用垃圾回收，那么实际实现就可以推迟，因为当时还只做了一些玩具示例，只会产生 “垃圾” 而不需要真的执行 “回收”。

当时还决定使用 SAVE 和 UNSAVE 例程，它们使用一个公共栈（表示为数组）来保存递归子例程中变量的值和子例程返回地址。IPL 用列表表示栈，并且栈必须显式指出。另外我们还决定放弃每个字的前缀和标记字段，放弃 cwr ，并将 cons 定义为两个参数的函数。因此我们只剩下一种类型——15 比特的地址——所以这种语言不需要类型声明。

描述可计算函数的方式一般有两种，图灵机和递归函数理论中常用的通用递归定义。上文的简化使 LISP 比它们都要简洁。图灵机是一种笨拙的编程语言，但递归函数理论家们完全不会在乎，因为他们几乎没有任何理由去编写特定的递归定义，他们关注的是递归函数的通用性质。他们常常会尝试证明具有特定性质的递归函数存在，但这可以通过非正式的论证来完成，不需要明确写下来。计算理论发展初期，有些人开发了基于图灵机的编程语言；也许这种方式更科学。总之，我决定撰写一篇论文来描述 LISP：它既是一种编程语言，也是递归函数理论的一个框架。这篇论文是《符号表达式的递归函数及其机器计算，第一部分》（中文翻译）（McCarthy 1960）。第二部分我没写过，不过原本是想写一点代数表达式计算的实际运用。这篇论文没有影响到递归函数理论家，因为没有涉及他们感兴趣的问题。

有一点数学角度的考虑影响了 LISP，那就是用从变量和常量开始，用函数的应用构建表达式，以此表示程序。我认为 LISP 中最重要的决定是，这些表达式遵守通常的数学法则，也就是可以把表达式替换成具有相同值的其它表达式，这样就可以用普通的数学方法来证明程序的性质了。这只有在避免副作用的情况下才有可能实现。不幸的是，注重性能时副作用往往是一种极大的便利，所以带副作用的 “函数” 在 LISP 中是存在的。所谓 “纯 LISP” 没有副作用， (Cartwright 1976) 和 (Cartwright 与 McCarthy 1978) 两篇论文展示了如何用一阶逻辑中的句子（sentence）和模式（schemata）来表示纯 LISP 程序，并证明它们的性质。这是追求数学美妙的又一动机，因为现在更容易证明纯 LISP 程序满足其规范，而不是其他广泛使用的编程语言。（比方说，编写程序来拼接链表，然后证明该操作满足结合律，这对其他编程语言爱好者是重大挑战。）

证明 LISP 比图灵机更简洁不止这种方法。我们可以编写一个泛用 LISP 函数，从而易见它比通用图灵机的描述更简短、更容易理解。这个 LISP 函数就是 eval[e, a] ，它计算 LISP 表达式 e 的值——第二个参数 a 是各个变量的值组成的列表（ eval 的递归需要用到这个变量）。编写 eval 需要发明一种把 LISP 函数表示为 LISP 数据的方式，所以我给它所在的论文设计了一种这样的方式，没想到后来实践中用来表达 LISP 程序。为了逻辑完备性，定义函数的语法需要扩展以支持递归函数，LABEL 符号就是 Nathaniel Rochester 为此发明的。D.M.R. Park 指出，LABEL 在逻辑上是不必要的，因为结果可以通过仅使用 LAMBDA 来实现——通过构造类似丘奇的 Y 组合子，尽管方式更复杂。

S.R. Russell 注意到 eval 可以作为 LISP 的解释器，迅速手工编写了它，现在我们有了一种带解释器的编程语言。

意外出现的解释器往往会冻结语言的形式，恰好上面提到的论文《递归函数……》中做出了一些轻率的决定，更不幸的是后来才发现这些决策的错误。比方说用于表示条件表达式 COND，这会导致不必要的括号深度，以及使用数字零来同时表示空列表 NIL 和布尔值假。除了鼓励下流（pornographic）编程之外，将地址 0 赋予特殊解释，给所有后续实现都带来了困难。

LISP 内部形式虽然令人尴尬，但最初仍能被接受还有另一个原因：我们仍然期望能够转而编写 M-表达式。定义 M-表达式精确含义并编译它们，至少也要翻译成 S-表达式，然而这一项目既未确定也未放弃，它只是延后到无限的未来之中，而新一代程序员出现了，他们更倾向于内部记号，而不是能够设计的类似 FORTRAN 或 ALGOL 的记号。

4. 从 LISP 1 到 LISP 1.5

4.1 属性表（Property list）

为每个符号提供属性表的想法在最初的汇编语言实现中就已存在。这也是 Advice Taker 理论中的一个核心概念。虽然按 Advice Taker (McCarthy 1959) 的要求，任意表达式，不止符号，只要它所持有的信息不依赖于结构，就应该有属性表。READ 和 PRINT 需要访问符号的打印名称。一旦函数定义成为可能，就必须能够区分一个函数是用机器代码写的 SUBR，还是由列表结构表示的 EXPR。顺便提供了一些处理属性表的函数，供大量依赖属性表的应用程序使用。

4.2 插入和删除列表元素

在人工智能领域，列表处理最初宣传的优点之一是插入和删除元素。可惜这种功能与共享列表结构不兼容。此外，插入和删除操作无法用简洁的函数表示。LISP 可以用伪函数 rplaca 和 rplacd 表示它们，但沾了这俩函数基本就跟逻辑无缘了，因为相等（equal）的参数应用于它们会产生不一样的结果。

4.3 数字

大多数计算既需要数字也需要符号表达式。在 LISP I 中，数字实现为元素是原子的列表。事实证明除了最简单的计算，这种方式都太慢了。性能比较合理的方式在 LISP 1.5 中出现，它把数字视作 S-表达式里的原子，但是几乎在所有早期 LISP 中，数字运算相比 FORTRAN 要多耗十来倍甚至一百倍的时间。

4.4 自由变量

James R. Slagle 毫无恶意地写下了这个函数，然后抱怨为什么没有正常的行为：

testr[x, p, f, u] ← 如果 p[​x] 那么 f[​x]
                    否则如果 atom[​x] 那么 u[]
                    否则 testr[cdr[​x], p, f, λ: testr[car[​x], p, f, u]]

该函数的目的是，找到 x 的一个子表达式，满足 p[​x] 成立，然后返回 f[​x] 。如果搜索失败，则调用无参数的续延（continuation）函数 u[] ，然后返回它的返回值。难点在于，递归调用 testr 时， car[​x] 所需的 x 是递归外部的值，但实际使用的是递归内部的值。用现代术语来讲，我们想要的是词法作用域，实际上得到的却是动态作用域。

不得不承认，我曾误将这个困难视作 bug，因此相信 Steve Russell 很快就能修好。他确实修复了这个问题，但是发明了所谓的 “FUNARG”，将词法环境与函数参数一起传递。后来在 Algol 60 中也出现了类似的困难，事实证明 Russell 的解决方案比 Algol 60 要更加全面。虽然 Russell 的方法在解释执行时没什么问题，但在编译代码中，全面和性能似乎是对立的，这导致了接连不断的妥协。可惜时间问题，我不能写附录来介绍问题的历史，有兴趣的读者可以参考 (Moses 1970) 作为起点。（David Park 告诉我，Patrick Fischer 也在开发 FUNARG 方面出了力）。

4.5 “程序特色（program feature）”3

除了函数组合和条件表达式，LISP 还可以用赋值语句和 goto 语句来编写顺序程序。与递归函数所构成的优雅 “数学特色”，“程序特色” 看起来像是仓促的补充。这并不完全正确；LISP 中顺序程序的概念早于递归函数的概念。不过符号 PROG 确实是后来才补充的，而且远非最优。

4.6 解释器4

只要我们把解释器 eval 写出来了，它就可供程序员使用，并且特别容易使用，因为它解释以 LISP 数据表达的 LISP 程序。特别是，eval 使得 F-表达式（FEXPR）和 F-子例程（FSUBR）5成为可能，它们是 “函数”，但是并不直接给出参数，而是给出求值为参数的表达式，有需要时用 eval 求值。这种工具的主要用处在于，有些函数并不总是求值所有参数；它们先求值其中一些参数，然后决定求值哪些其他参数。这种功能类似于 Algol 中按名传递（call-by-name）的参数，但更加灵活，因为 eval 可以由程序员决定用不用。现在似乎可以处理 “外延性” F-表达式和 F-子例程的一阶逻辑。

4.7 可变数量的参数

由于 LISP 处理列表，所以我们可以使用参数数量可变的函数，只需要向函数提供参数列表而不是单独的参数即可。

不幸的是，上述特征都没有在 LISP（其他编程语言也没有）的基础上得到全面而清晰的数学语义。关于 LISP 的最佳尝试是 Michael Gordon（1973）的工作，但它过于复杂。

4.8 编译器

Robert Brayton 最早尝试实现编译器，但失败了。第一个成功的 LISP 编译器是由 Timothy Hart 和 Michael Levin 编写的。它用 LISP 编写，并声称所有的编程语言中，这是第一个用自己编写的编译器。

许多人在 LISP 的初始开发中做出了贡献，惭愧的是我没能记住所有他们的贡献，因此本文只能给出姓名清单。我能记住的有 Paul Abrahams、Robert Brayton、 Daniel Edwards、Patrick Fischer、Phyllis Fox、Saul Goldberg、Timothy Hart、Louis Hodes、Michael Levin、David Luckham、Klim Maling、Marvin Minsky、David Park、IBM 的 Nathaniel Rochester 和 Steve Russell。

除了对 LISP 系统的研究之外，我们还编写了许多应用程序，这些经验也影响了系统本身。我能记住的主要应用程序有：Rochester 和 Goldberg 的一个符号计算程序，这个程序与阻抗之类电网相关的函数有关；以及由 Minsky 指导， J.R. Slagle 编写的关于符号积分的论文；还有 Paul Abrahams 关于证明检查的论文。

5. 超越 LISP 1.5

作为一门编程语言，LISP 存在许多局限性。在 1960 年代初，最明显的问题是数值计算极其缓慢、无法使用内存块表示对象然后垃圾回收整个内存块，以及无法使用传统中缀表达式来输入输出符号表达式。所有这些问题和其他问题都将在 LISP 2 中得到解决。然而我们只能停留在 M.I.T.开发的 LISP 1.5，它仅修正了最明显的缺陷。

LISP 2 是 Systems Development 公司和 Information International 公司的合作项目，最初计划用于 Q32 计算机，该计算机由 IBM 为军事目的建造，字长 48 比特，地址长 18 比特，因此比 IBM 7090 更适合于雄心勃勃的项目。不幸的是，Systems Development 公司的 Q32 从未配备超过 48K 字的内存。等到我们意识到 Q32 的内存太少时，已经决定在新的 IBM 360/67 和 Digital Equipment 公司的 PDP-6 上开发语言——Systems Development 公司正在获取前者，而 Information International 公司、麻省理工学院和斯坦福大学更倾向于后者。事后才发现该项目比预期更昂贵，合作比预期更困难，因此 LISP 2 项目被放弃。从 20 世纪 70 年代的角度来看，这是令人遗憾的，因为此后花费了更多金钱来开发功能更少的 LISP。然而，当时人们并不知道人工智能研究的主流机器将是 PDP-10，它是 PDP-6 的继任者。人工智能社区的一部分，例如 BBN 和 SRI，在 SDS 940 计算机上进行人工智能工作，事实证明这是架构性偏离的决定。

解释器的存在和类型声明的缺失使得 LISP 特别适合在分时环境中使用。无需离开 LISP 解释器就能方便地定义函数、测试函数、重新编辑函数。1960 年（或 1961 年），在 IBM 704 的原型分时环境中展示了 LISP 的应用（见附录）。 1963 年，L. Peter Deutsch 在 PDP-1 计算机上实现了第一个交互式 LISP，但 PDP-1 的内存太小，无法进行严肃的符号计算。

LISP 最重要的实现位于 PDP-6 及其后继者 PDP-10 上，这些计算机由马萨诸塞州梅纳德市的 Digital Equipment 公司制造。事实上，这些机器的半字指令和堆栈指令都是为了 LISP 而开发的。麻省理工学院在这些机器上开发了 LISP，后来又开发了 INTERLISP（原 BBN LISP）和 MACLISP，这进一步促使这些机器成为人工智能研究的首选设备。IBM 704 LISP 扩展到 IBM 7090 上，后来又发展出了适用于 IBM 360 和 370 的 LISP。

麻省理工学院电子研究实验室的季度进展报告是关于 LISP 的最早出版物。 McCarthy 于 1960 年发表的论文（中文翻译）是第一篇期刊出版物。Phyllis Fox 写的手册由电子研究实验室于 1960 年出版，McCarthy、Levin 等编写的 LISP 1.5 Programmer’s Manual 于 1962 年由麻省理工学院出版社出版。在这篇手册出版后，许多计算机上都出现了 LISP 的实现。然而，与大多数广泛使用的编程语言的情况不同，没有任何组织尝试推广 LISP，也从未有过标准化协议的尝试，尽管最近 A.C.Hearn 开发了一个 “标准 LISP”（Marti、Hearn、 Griss 和 Griss6 1978 年），该标准 LISP 可以在多台计算机上运行，以支持 REDUCE 系统进行代数表达式计算。

6. 结论

LISP 是目前广泛使用的第二古老的编程语言（仅次于 FORTRAN，不计 APT，因为后者本质上并非用于编程）。它的长寿归功于两个事实。首先，就像物理学的静摩擦一样，纯粹的符号变化会被阻碍，因此 LISP 的核心在编程语言空间中占据某种局部最优。条件表达式的递归使用、在外部用列表表示符号信息、在内部用链表结构表示符号信息，以及以相同方式表示程序，这些特点很可能具有非常长的寿命。

其次，LISP 仍然具有其他语言无法匹敌的操作特性，从而仍是符号计算和人工智能高级系统的便捷载体。比如运行时系统，能够良好地访问主机机器和操作系统的特性；内部语言是列表结构，因此 LISP 是更高级语言编译的良好目标；与其它编程语言系统协作时，LISP 和它们生成的二进制或汇编程序有良好的兼容性；LISP 的解释器可以用作驱动其他程序的命令语言。（甚至可以推测，LISP 之所以能够生存，正是因为它的程序是列表，而这一点，包括我在内，大家都认为是一个缺点。例如 POP-2（Burstall 1968, 1971）等提议替代 LISP 的语言，为了采用类似 Algol 的语法而放弃了这一特性，导致更高级系统无法将其当作目标语言。）

如果有人创建了一种更全面的语言，不仅影响了 LISP，并且为更全面的特性提供清晰的数学语义时，那么 LISP 会变得过时。

7. 参考文献

Abrahams, Paul W. (1963), Machine verification of mathematical proof, M.I.T. 数学博士毕业论文。

Abrahams, Paul W., Barnett, J. 等, (1966), “The LISP 2 Programming Language and System”, Proceedings of the Fall Joint Computer Conference, 第 661-676 页。

Abrahams, Paul W. (1967), LISP 2 Specifications, Systems Development 公司技术报告 TM-3417/200/00, 圣莫尼卡, 加利福尼亚州。

Allen, John (1978), Anatomy of LISP, 麦格劳-希尔出版社。

Berkeley, Edmund C 著。Daniel Bobrow 编. (1964), The Programming Language LISP, its Operation and Applications, Information International 公司, 马萨诸塞州剑桥。(已绝版)。

Burstall, R.M., J.S. Collins 和 R.J. Popplestone (1968), POP-2 Papers, 爱丁堡大学出版社，苏格兰爱丁堡。

Burstall, R.M., J.S. Collins 和 R.J. Popplestone (1971), Programming in POP-2. 爱丁堡大学出版社，苏格兰爱丁堡。

Cartwright, Robert (1976), A practical formal semantic definition and verification system for typed LISP , 斯坦福人工智能实验室技术报告 AIM-296，斯坦福，加利福尼亚。

Cartwright, Robert 和 John McCarthy (1978) “Representation of Recursive Programs in First Order Logic” (待出版). （草稿见 ARPAnet 上 SU-AI 中名为 FIRST.NEW[W77,JMC] 的文件）

Collins, G.E. (1960) “A method for overlapping and erasure of lists”, Communications of the ACM, 第三卷, 第 655-657 页。

阿隆索·丘奇 (1941), Calculi of Lambda conversion, Princeton University Press, 普林斯顿大学出版社，新泽西州普林斯顿。

Fox, Phyllis (1960), LISP I Programmers Manual, 内部文件，麻省理工学院，马萨诸塞州剑桥。

Gordon, Michael (1973) Models of Pure LISP, 实验编程报告：第 31 号，爱丁堡大学，爱丁堡。

Gelernter, H., J. R. Hansen, 和 C. L. Gerberich (1960), “A FORTRAN-Compiled List Processing Language”, ACM 期刊, 第七卷, 第二篇论文, 第 87-101 页。

Hearn, Anthony (1967), REDUCE, a User-oriented Interactive System for Algebraic Simplification, 斯坦福人工智能实验室技术报告 AIM-57，斯坦福，加利福尼亚。

Hewitt, Carl (1971), Description and theoretical analysis (using schemata) of PLANNER: a language for proving theorems and manipulating models in a robot, 博士论文，MIT，马萨诸塞州剑桥。

McCarthy, John (1958) “Programs with common sense”, Proceedings of the Symposium on the Mechanization of Thought Processes, 英国泰德林顿国家生理实验室。

McCarthy, J., Minsky, M. 等, (1959a), 第 52 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, J., Minsky, M. 等, (1959b), 第 55 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, John (1959c), Letter to the Editor, CACM, 第二卷第 8 篇。

McCarthy, J., Minsky, M. 等, (1960a), 第 56 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, John (1960b), “Recursive Functions of Symbolic Expressions and their Computation by Machine, part I”, CACM, 第三卷, 第四篇, 第 184-195 页。（中文翻译）

McCarthy, J., Minsky, M. 等, (1962a), 季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, J., Minsky, M. 等, (1962b), 第 64 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, John (1962c), LISP 1.5 Programmer’s Manual, (和 Abrahams, Edwards, Hart, 以及 Levin 合著), MIT 出版社，马萨诸塞州剑桥。

McCarthy, J., Minsky, M. 等, (1963a), 第 68 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, J., Minsky, M. 等, (1963b), 第 69 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, John (1963c) “A Basis for a Mathematical Theory of Computation”, 收录于 P. Braffort 和 D. Hirschberg 编辑的《计算机编程与形式系统》，第 33-70 页。北荷兰出版公司，阿姆斯特丹。

McCarthy, John (1963d) “Towards a Mathematical Science of Computation”, Proceedings of IFIP Congress, Munich 1962, 1962 年慕尼黑，阿姆斯特丹：北荷兰出版社，第 21-28 页。

McCarthy, J., Minsky, M. 等, (1965), 第 76 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, J., Minsky, M. 等, (1966), 第 80 号季度进展报告，MIT 电子研究实验室，马萨诸塞州剑桥。

McCarthy, John 和 Carolyn Talcott (1979) LISP with Proofs, 待出版。已经有大部分章节的版本可以在斯坦福人工智能实验室获取。

Marti, J. B., Hearn, A. C., Griss, M. L. 和 Griss, C. (1978) Standard LISP Report, 犹他大学符号计算小组报告第 60 号，普罗沃，犹他州。

Mathlab 小组 (1977), MACSYMA Reference Manual, 麻省理工学院计算机科学实验室版本 9，剑桥，马萨诸塞州。

Mitchell, R.W. (1964) LISP 2 Specifications Proposal, 斯坦福人工智能实验室备忘录第 21 号，斯坦福，加利福尼亚州。

Moon, David A. (1974), MACLISP Reference Manual, MAC 项目技术报告, MIT, 剑桥, 马萨诸塞州。

Moses, Joel (1970) The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem, M.I.T. 麻省理工学院人工智能备忘录 199，马萨诸塞州剑桥。

Newell, A., 和 J.C. Shaw (1957) “Programming the Logic Theory Machine”, Proceedings of the 1957 Western Joint Computer Conference, IRE.

Rulifson, J. 等 (1968), “QA4 - A Language for Writing Problem-Solving Programs”, Proceeding IFIP 1968 Congress, TA-2, 第 111-115 页。

Stoyan, Herbert. 来自东德德累斯顿的 Herbert Stoyan 完成了关于 LISP 历史的几章。

Sussman, G. Winograd, T., 和 Charniak, E. (1970), Microplanner Reference Manual, AI 备忘录 203, AIL MIT, 马萨诸塞州剑桥。

Teitelman, Warren (1975), INTERLISP: Interlisp Reference Manual, Xerox PARC Technical Report, Palo Alto, Calif.

Weisman, Clark (1967), LISP 1.5 Primer, 迪肯森出版社。

还有麻省理工学院和斯坦福大学人工智能实验室的许多报告和备忘录，它们涉及了 LISP 的各个方面以及基于 LISP 构建的高级系统。

附录 - 幽默轶事

LISP 的第一次在线演示，也是分时系统先驱，我们称之为 “time-stealing” 分时系统的第一次演示。麻省理工学院工业联系研讨会（Industrial Liaison Symposia）的部分参与者也来观看了，给他们留下好印象非常重要。我们把一台 Flexowriter 连接到了 IBM 704，然后修改了操作系统，可以用中断信号指示字符存在，然后操作系统会从 Flexowriter 收集字符到缓冲区中。出现回车时，当前编辑的一行就会交给 LISP 进行处理。该演示依赖于一个事实：计算机的内存刚刚从 8192 字增加到 32768 字，因此每次垃圾回收时只会收集较小的一批内存。

这次演示也是首批使用闭路电视的演示之一，目的是让观众免于用博物馆脚步（museum feet）围在终端旁等待发生什么。因此他们位于四楼，而我则在一楼计算机室练习 LISP，对着麦克风说话。我们决定演示的问题是，判断给定一阶微分方程（形如 Mdx + Ndy ）是否为恰当方程，方法是检测 \frac{∂M}{∂y} = \frac{∂N}{∂x} 是否成立，这也涉及一些基本的代数简化。

一切进展顺利，虽然有点慢。但是突然 Flexowriter 开始以每秒十个字符的速度打字：

“THE GARBAGE COLLECTOR HAS BEEN CALLED. SOME INTERESTING STATISTICS ARE AS FOLLOWS:”

（垃圾回收器启动了。下面给出一些有价值的统计信息：）

并且不断输出。当时垃圾回收还很新，我们相当自豪，也很好奇，而且我们通常是输出在行式打印机上，所以每次调用时它会打印一整页，显示标记了多少个字、回收了多少个字、列表空间的大小等等。在之前的彩排中，垃圾收集器没有被调用，但我们没有刷新 LISP 核心映像，所以在演示过程中我们用完了空闲内存。

之前从未提及过垃圾回收，我只能想象观众的反应。我们已经在紧张的日程中落后了，很明显，打印垃圾收集器的信息将占用演示所剩的全部时间，而讲稿人和观众都被笑声弄得无法继续。我想有些人认为我们是某个恶作剧的受害者。

约翰·麦卡锡 人工智能实验室 计算机科学系 斯坦福大学 加利福尼亚州斯坦福 94305

LISP[F77,JMC] 的这份草稿在本文开头的日期发布。

脚注

1 译注：原文为 “for naming functions”，真的是具名函数，虽然我也不知道它 “具” 的 “名” 是什么。

2 译注：早期 FORTRAN 的 IF 语句形如

IF(N) 10,20,30

它表示，如果变量 N 是负数，那么跳转至标记为 10 的那一行（FORTRAN 可以给每行指定一个标记，这就是前面那六个空格的作用）；如果 N = 0，那么跳转至 20；如果 N 是正数，那么跳转至 30。如你所见这种 IF 不是很好用。

3 译注：我在之前的 McCarthy 1960 年论文的翻译 中误将 “program feature” 译作 “特色程序”，因为我觉得这个词表示 “ALGOL、FORTRAN 等其它语言的特色”，但是现在才发现它应该与 “数学特色” 相对立。

4 译注：原文这一节没有标题，这个标题以及 §4.7 节和 §4.8 节的标题是我自己加的。

5 译注：F-表达式指使用 LISP 定义的 F-函数，F-子例程指使用机器代码定义的 F-函数。§4.1 提到了这一点。

6 译注：Griss 出现了两次，因为他们分别是 Griss M. L. 和 Griss. C.，见 §7 参考文献。

8 个赞