不走寻常路的编程语言大家 – Lisp之父约翰·麦卡锡

编程语言 lisp lisp之父| 2016-05-09

一个5岁的小女孩在玩一辆塑料玩具卡车，把它推来推去，嘴里模仿着喇叭声。她知道不能在餐桌上玩它，也不能用它去打弟弟的头。去学校之前，她会把卡车放到弟弟够不着的地方。放学回家后，她也知道在原来的地方可以找到自己的玩具车。

引导她的行为和期望的推理非常简单，任何一个同龄的小孩都能理解。但是大多数计算机却不能。计算机的问题一部分在于它缺少一般5岁小孩能从父母那里学到的日常社会知识，例如不能损坏家具，不能伤到自己的弟弟；另一部分在于计算机没有我们的日常推理能力。人类使用的是一种基于经验的常识推测体系，它与常规逻辑不同，因此也与一般计算机程序员的思维不同。常规逻辑使用的是一种被称为“演绎”(deduction)的推理形式。演绎让我们能从“所有失业演员都当了服务生”和“托米是个失业演员”这两个陈述中推断出“托米是个服务生”这一新的陈述。其优点在于它的可靠性——如果前提成立，那么结论一定成立。同时演绎推理也是“单调的”(monotonic，数学术语，其基本含义为“不变的”)。如果你发现了新的事实，但并不与前提相矛盾，那么结论仍然成立。

然而，尽管我们大多数人都在学校学过演绎推理，却很少在实际生活中用到。5岁的小女孩相信自己的卡车还在原来的位置，是因为她把它放在了弟弟够不着的地方。但如果某天她在出门时看到弟弟学会了爬凳子，可能就不会这么有把握了。5岁小孩掌握的常识推理主要依靠基于经验的推测，而这可能会由于新事实的出现而不得不作出非单调的修改。而且并不是只有5岁小孩会如此。

就算是公认的演绎推理大师歇洛克·福尔摩斯，也并不经常用到演绎推理。在关于一匹受伤赛马的冒险故事《银色马》中，福尔摩斯运用其天赋的洞察力得出结论，看门狗没有叫是因为它认识罪犯。我们的侦探确实才智超群，而且推论看来合情合理，最后在故事中也证明是正确的，但他用的却不是演绎推理——狗可能是被麻醉了、戴了口套，或者当时正在野地里追兔子。

48-John-McCarthy-AP

程序员知道如何让计算机进行演绎推理，因为计算机能够理解其中涉及的数学。但如果想让计算机进行人类赖以生存的这种推测性的(而又常常是正确的)常识推理，就得发明一种全新的数理逻辑。而这正是约翰·麦卡锡为自己设立的目标之一。

麦卡锡的成名还有其他原因。他发明了人工智能领域的首要语言Lisp (list processing，表处理)，而且自其诞生之日起，就为编程语言设计提供了丰饶的思想源泉。同时，作为一名教师和难题设计师，他在密码学和平面性检验等亚学科领域激发了众多计算机科学家的灵感。我们将在拉宾和陶尔扬的章节中再行描述。

约翰·麦卡锡1927年出生于波士顿一个共产党积极分子家庭，童年在四处奔波中度过。他的父亲是一名爱尔兰天主教徒，先后做过木匠、渔民和工会组织者，全家一直马不停蹄地奔波，从波士顿搬到纽约，然后又搬到洛杉矶。他的母亲是立陶宛犹太人，最初在联邦通讯社当新闻记者，后来就职于一家共产主义报刊，最后成为了一名社会工作者。麦卡锡早年对科学的兴趣与家庭的政治信仰密不可分。

当时普遍相信技术对人类必将有利无害。我记得还是小孩的时候，曾读过一本书叫做《十万个为什么》，是前苏联作家米·伊林在20世纪30年代早期写的一套通俗科普书。在美国好像没有这样的书。有趣的是，十几年前我在报上看到过报道一个特别早熟的中国孩子，而他也读过《十万个为什么》。

麦卡锡认为自己的青少年时期平淡无奇，但事实证明并非如此。在上高三时，他得到了一份加州理工学院的课程目录，上面列出了该校一年级和二年级的微积分课本。他买了这些书，完成了所有的练习题目。这使得他最终在1944年进入加州理工后得以免修头两年的数学课程。

1948年，麦卡锡开始攻读数学系的硕士学位。同年9月他参加了加州理工主办的希克森脑行为机制研讨会，大数学家、计算机设计大师约翰·冯·诺依曼在会上演讲了一篇关于自复制自动机(self-replicating automata)的论文，这是一种可以对自身进行复制的机器。尽管当时的与会人员并没有明确地将机器智能与人类智能联系起来，但冯·诺依曼的讲话却激发了麦卡锡的好奇心。

1949年在普林斯顿大学数学系作博士论文时，麦卡锡首次开始尝试在机器上模拟人类智能。

我把有智能的东西看做是一个有限自动机，与同样是有限自动机的环境相连。我和约翰·冯·诺依曼见了面，他对此非常赞成，敦促我一定要把这篇论文写出来。但最后我并没有写出来，因为我认为它还不够成熟。

“自动机”模拟的是随着时间从一个状态转入另一个状态的机器。比如说，普通的手动变速箱汽车在驾驶员点火启动之后会从“熄火”状态转入“空挡但启动”状态。如果驾驶员挂挡前进则转入“启动且挂一挡”状态。而“交互式自动机”(interacting automaton)则是根据其自身的状态以及它所观察到的其他自动机的状态决定从某个状态转入另一状态。有些自动机是智能的(可看做是自带驾驶员)，但并不是必须智能。交互式自动机试图在这两种类型之间建立一种连续性的统一体。

麦卡锡放弃了自己对利用自动机模拟人类智能的首次尝试。但在十几年之后，当他从事情境演算(situational calculus)方面的工作时，关于状态和状态转换的思想将重新浮出水面。

在这段时间中，麦卡锡始终没有放弃制造一台像人类那样智能的机器这一想法。1952年夏，普林斯顿大学的一个研究生杰里·雷纳(Jerry Rayna)向麦卡锡建议，可以找一些对机器智能感兴趣的人去收集一些该领域的文章。麦卡锡找的第一批人就有克劳德·香农，“信息论”亦即通信数学理论的发明者。香农的理论最初用于远程通信，后被广泛用于语言学、数学以及计算机科学等领域。

香农不喜欢华而不实的术语堆砌。他整理的卷宗为《自动机研究》(Automata Studies)。而其中收集到的文章让我很失望，里面有关智能的内容并不多。所以在1955年开始筹备达特茅斯计划时，我希望开门见山，使用了“人工智能”这一术语，目的是让参与者们弄清楚我们是在干什么。

1956年在达特茅斯学院举办的夏季人工智能研讨会是计算机科学史上的一座里程碑。这项涉及10人、耗时2个月的雄心勃勃的研究计划，其目标是“基于‘我们能够精确、全面地描述人类智能中的学习等特征，并制造出机器模拟之’这一构想，继续阔步前进”(引自其提案)。

研讨会的四位组织者——麦卡锡、马文·明斯基(当时还在哈佛大学)、纳撒尼尔·罗切斯特(IBM的杰出计算机设计师)和香农——向洛克菲勒基金会申请了一笔资金支持，金额在今天看来几乎少得可怜：主要组织者每人1200美元，再加上“外地与会人员的火车票”，总共7500美元。

麦卡锡在提案中写到，他将研究语言和智能二者间的关系，希望通过程序使计算机能“进行棋类游戏并完成其他任务”。时隔40年后回忆起这次研讨会时，麦卡锡以他特有的直率形容了自己当时的愿景和期望。

我为这次会议设定的目标完全不切实际，以为经过一个夏天的讨论就能搞定整个项目。我之前从未参与过这种模式的会议，只是略有耳闻。实际上，它和那种以研究国防为名义的军事夏令营没什么区别。创造一台真正智能的机器是一个极为困难的过程。尽管这次会议在实质上并未解决任何具体问题，但它确立了一些目标和技术方法，使人工智能获得了计算机科学界的承认，成为一个独立的而且最终充满着活力的新兴科研领域。虽然大多数与会者在会后并未继续从事该领域的研究，但另外那少数人中却产生了一批在该领域影响深远的成就。

来自卡内基梅隆大学的艾伦·纽厄尔、赫伯特·西蒙和J.C.肖(J.C.Shaw)描述了他们的第二代信息处理语言(Information Processing Language，IPL2)。这三位科学家致力于构建一种名为“逻辑理论机”的程序，用于验证基本逻辑和博弈论中的定理。而为了做到这一点，他们设计出IPL2这种程序语言以便于操作对象符号，例如象棋的棋子或者逻辑变量里的真值。由于这种操作与针对数字的算术运算非常不同，他们提议使用一种所谓的“表结构”。

让我们冒昧地借用《爱丽丝梦游仙境》来说明如何利用表来进行符号处理。假设柴郡猫告诉爱丽丝“不是我疯了，就是帽匠疯了”。我们用C、H、A代表三种观点，分别是柴郡猫疯了、帽匠疯了和爱丽丝疯了。猫之前的那句声明可以用表的形式表示为(or C H)。然后猫又告诉爱丽丝“不是你疯了，就是帽匠疯了”。聪明的爱丽丝会把这个声明和之前的那个一起表示为(and(orCH)(orAH))。最后猫又说“我们三个中只有一个疯了”。也就是说，至少有两个没有疯。爱丽丝可以将其表示为(and (or C H) (or A H)(or (and (not A) (not C))(and (not A) (not H))(and (not C) (not H))))。

把这些声明表示成表的形式之后，我们就可以定义一些表操作的规则。

例如(and (or X Y) (or Z Y)) = (or (and X Z) Y)。也就是说，如果不是X成立就是Y成立，而且不是Z成立就是Y成立，那么不是X和Z都成立，就是Y成立。应用这样一些规则，我们就能得出结论(and H (not C) (not A))。那么，根据柴郡猫的说法，只有帽匠疯了。

通过表来进行逻辑推理的优点在于，在推理的过程中表可以扩展、收缩和重组。此外，我们可以用同一种形式表示规则和数据。在研讨会大多数与会者们看来，表操作无疑是这次的赢家。达特茅斯会议的另一项成就是马文·明斯基关于构建几何定理证明机的提案。明斯基在纸上试验了几个例子，认为证明几何定理可能是对纽厄尔和西蒙提出的基于规则的方法的一种很好的应用。IBM公司的赫伯特·格林特(Herbert Gelernter)和纳撒尼尔·罗切斯特决定去实现这个程序。格林特日后又开发了一种帮助有机化学家合成新化合物的工具，他的儿子大卫·格林特(David Gelernter)是并行程序设计和医学人工智能领域著名的研究者及设计者。麦卡锡身为这个定理证明项目的顾问，有机会为智能行为编写程序。

格林特和他的助手卡尔·格贝里希(Carl Gerberich)采纳了我的建议，以Fortran为蓝本设计了FLPL——Fortran表处理语言(FortranList Processing Language)。其中也加入了一些他们自己的想法。

1956年，约翰·巴科斯和他在IBM的团队发布了首个高级编程语言Fortran，将从事数字运算的程序员从为每一台计算机写汇编语言中解放出来。直到今天，Fortran仍然是科学和工程计算中的通用语言。FLPL首次尝试了扩展Fortran的符号操作能力。1958年夏天在IBM工作时，麦卡锡试图用FLPL为自己在高中时常用的代数微分应用写一个表程序，但很快发现需要用到递归条件表达式，而Fortran却不支持递归。如果Fortran支持递归，我就能用FLPL做下去。我甚至也考虑了如何往Fortran中加入递归的问题，但是那样做过于复杂。

事实证明，IBM很快就失去了对人工智能的兴趣。一些客户认为智能机器可能会威胁到他们的工作岗位，因此20世纪60年代初期的IBM市场营销都把计算机说成是非智能的快速运算设备，百依百顺、只按要求行事。

麦卡锡不再纠缠于修补Fortran，而是转头发明了Lisp。纽厄尔、肖和西蒙后来把IPL形容为一种越变越复杂的语言，而麦卡锡则把他的Lisp形容为一种越变越简单的语言。

“Lisp”是“list processing language”(表处理语言)的缩写。确如其名，Lisp中所有的数据都用表来表示。这些表都被包含在圆括号中。比如说，(Robert taught Dennis)可能就是表示“罗伯特教丹尼斯”这个句子的一个表。在这种情况下，顺序是很重要的，因为它指明了是谁在教谁。

而(apple tomato milk)则可能表示一个购物清单。在这种情况下，顺序就不重要了，因为这三种商品可以按任意顺序购买。上述这两个例子中，表都包含了“原子”(atom)作为元素。原子和表不同，是Lisp中最小的符号单位，不包含其他任何组成部分。而表还能够包含(而且一般都会包含)其他表作为组成部分。比如说，(Robert taught (Carol and Dennis))反映了句子的语法结构，其中的圆括号指明卡罗尔和丹尼斯都是动词“教”的对象。再比如，(times 6 (plus x y))表示6 x (x + y)。这里的顺序也很重要，而且圆括号表明x和y是一起的。

通过这种方式，表不仅能够表示构成科学和工程的标准数学结构，还能表示构成语言的语句结构。

从一开始，麦卡锡就拥有一个热情高涨的合作者团队。

当我在1958年秋天回到麻省理工的时候，我和明斯基有了一个大工作室、一台键控打孔机，此外还配备了一名秘书、两个程序员和六个数学专业的研究生。我们是在春天时向杰里·威斯纳(Jerry Wiesner)申请的这些，理由是为我们的人工智能项目做准备。

我们连书面提案都没准备，申请就得到了批准。很幸运，当时麻省理工的电子研究实验室刚刚与美国军方签署了一份无固定目标的双向合作协议，而相应的资源还没有到位。我想这种灵活的资源调配正是美国的人工智能研究起步领先于其他国家的原因之一。纽厄尔-西蒙的研究之所以能进行，也是由于美国空军在当时向兰德公司提供了弹性的支持。

随着工作的深入，麦卡锡希望改进这种语言的表达能力。1959年，为了展示Lisp可以明确地表达任何可计算函数，他加入了一个叫做“求值”(eval)的功能。“求值”允许程序定义新的函数或者过程(procedure)，然后将其作为程序的一部分执行。而大多数语言在执行新函数之前都会强制程序中止运行，并且“重新编译”。由于求值函数可以带动并执行任何函数，它扮演了一种“通用图灵机”的角色，是其他计算机的通用模拟器。

求值概念具有非常实际的意义。比如说，由于国际金融市场时刻都在变化，股票交易所必须每周7天、每天24小时不停地提供计算服务。如果有人写了一个程序，可以用新的方法分析路透社的股票数据，股票经纪人很可能希望马上就使用它，但又绝不想中断自己机器的使用。求值让这一切成为可能。

Lisp中蕴含的思想吸引了负责设计Algol语言(巴科斯和诺尔为其发明了巴科斯-诺尔范式)的国际委员会。1960年，在该委员会于巴黎召开的会议上，麦卡锡正式提出了递归和条件表达式这两个概念。在标记方法上，委员会有了些争H论，但最终仍然接受了他的思想。

Algol是第一个采用Lisp创新的语言，但绝对不是最后一个。Algol的后继语言如Pascal、C、Ada以及其他大多数现代编程语言都支持递归和条件表达式。但直到最近，主流语言都不支持求值，主要原因在于语言设计者们担心程序员往运行中的程序里添加新功能可能会很危险。不过如今的很多程序都必须每周7天、每天24小时地连续运行，人们对求值这种特性的需求越来越迫切，因此大多数实验性语言都包含了求值或类似求值的功能。

近50年来，Lisp一直是人工智能领域的标准语言。麦卡锡并未预料到它会有如此长的寿命，甚至曾建议将其修改成类似Algol那样。然而该领域的编程人员仍然喜欢Lisp最初的语法。麦卡锡和在他之前的巴科斯、之后的艾伦·C·凯一样，最终已无法控制自己发明的语言的发展方向。