怎样与机器对话?
假如你是二次世界大战以后的一个计算机制造计划的总工程师。你收集了一堆电线和开关，任务是制造一台机器用于预测飞机穿过大气的飞行模式。由于当时技术所限，你只能使用不太可靠的部件，并且要求能够方便地装配起来。这台机器将消耗足以供应一个小型工厂的电量。你赋予它一个足以容纳几千个字符的存储器，一个加法器，一个乘法器，和一个用于计算的指令集。
指令倒不用担心什么，它们只需要表达得能够进行工作就行了。
为效率起见，你确定好能够反映许多工程设计细节的指令。你的机器有着速度和价格不同的存储器。因此你发明了一组在慢速存储器和快速存储器之间转移数据的指令，以及另一组用于加减乘除和在快速存储器中处理数据的指令。这种分组方式使得编写预测飞行模式的程序比那种不把存储器区别对待的分组方式更加困难，但你不用操心这些。那时的数学家程序员遍地都是。这台机器精密、昂贵且独一无二。
Lois Haibt5年后，形势完全改变了。令你吃惊的是，你发现对程序不断上升的需求和硬件价格的下跌使得编写程序比购买和维护硬件更加昂贵。（这种现象一直持续着。到90年代中期，在大多数软件开发中，软件费用约为硬件费用的50倍。）于是，你为自己制订了两个新的目标：缩短程序第一版编写的时间，并在客户要求变化时能够更方便地改进程序。
你决定改变程序员和机器交流的语言。这种语言不是反映存储器的快慢分组和机器的算术运算，而是反映所需解决的问题的结构。你知道，每种职业都为自己的用途发明语言。比如，影片导演使用“开始”这一术语用于简单表示“摄影师开始拍摄，演员表演当前的剧情，其他人员各就各位”。50年代中期，计算机主要应用于科学和数据处理，所以你集中精力编写一种数学语言：算术公式、总和及向量。为了得到一些想法，你去拜访各种研究人员，看见有的方案让程序员可以写出像（X＋Y）/Z那样的数学表达式，而让计算机执行适当的运算。
1958年，在科学程序设计语言中出现了一个佼佼者：Fortran（Formula Translation的缩写，表示公式翻译），由约翰·巴库斯（John Backus）和他在IBM的几个同事设计而成。这种语言现在仍然是自然科学中应用最广泛的程序设计语言。
与此同时，一个研究小组于1959年开辟了计算机科学中的一个新领域：人工智能。这个学科的目标就是制造具有人的推理能力的计算机。由于人的推理中许多情况下都必须处理抽象概念，比如砖块的相对位置、句子的语法、问题的正反两面等等，而Fortran偏重算术的特性并不适合这个目标。卡耐基·梅隆大学(Carnegie Mellon)的艾伦·纽威尔(Allen Newell)和赫伯特·西蒙(Herbert Simon，其中文名为司马贺)提出用符号表表示抽象概念，把推理模拟为“符号操作”。
假设一个游戏室中有一块红砖、一块蓝砖和一块黄砖。一个5岁的小孩都能告诉你，如果红砖在蓝砖上，黄砖在红砖上，那么黄砖便在蓝砖上。前两个事件用符号表表示为：（上 红砖 蓝砖）和（上 黄砖 蓝砖）。然后可以引入这样一个符号操作规则：如果（上X Y）和（上Z X），那么（上Z Y）。
这种意见给年轻的约翰·麦卡锡很深的印象，但他认为纽威尔－西蒙设计太复杂了。他将该设计简化，并加入了两个功能强大的特性“递归”和“求值”，并发明了一种语言Lisp（表示List Processing表处理）。Lisp除成为人工智能的首选语言外，从1956年它发表开始还与Fortran一起激起了许多人设计计算机语言的兴趣。
那年夏天，一群国际计算机科学家在苏黎世召开会议，准备设计一种包含有Lisp成分的Fortran的后继语言。他们的合作导致了Algol 60语言的产生，这是Pascal、C和Ada等语言的父语言，也是从Postscript到Excel等语言的祖语言。
到70年代初，一小群研究人员开始认识到，从Fortran、Algol和Lisp演化出来的成百上千种语言有一个共同的缺陷：程序写完后几乎不可能读懂。程序员们发现为了改变程序的特性常常不得不重写它。
有着生物学方面背景的艾伦·凯(Alan C. Kay)得出结论，认为程序必须构造成像生物那样：通过自主的“细胞”互相传递信息进行协作。他认为通过自主单元构造程序的方式可以使这些单元在新的背景下也能使用。他用“对象”(object)指代这种“细胞”(cell)，并称这种方式为“面向对象”(object··orientation)。对象的特性根据它所作出反应的消息定义。
比如，与图象有关的应用程序中，可以用“转30度”和“打印自身”等消息或命令描述图象的共同特性。而控制机器人月球行走的程序可定义机器人对“收集岩石样品”和“定位高于一米的石头”等消息作出反应。70年代中期，凯和他在施乐公司的小组设计了第一个面向对象语言：Smalltalk。随后几年，它的第一批用户中有许多是十几岁的青少年。从那以后，Smalltalk深刻地影响了像C++那样成熟的语言，也有一些自己的后续语言。
在过去的40年里，曾有成千上万种语言设计出来；大约60种仍在广泛使用，包括用于文字处理、电子表格、图形和动画片等方面的专用语言。一种好的语言，像一件工具帮助木匠解决问题一样，可以解决计算机问题。而程序员就像木匠习惯于自己的工具一样习惯于自己喜欢的语言。
语言学家本杰明·沃夫(Benjamin Whorf)曾经写道：“语言塑造我们的思维，决定我们思考的内容。”这些话是对人类语言而言的，但计算机语言，特别是巴库斯、麦卡锡和凯所作的工作，时时刻刻都在证实这些话。
第二章
我们并不知道我们想要什么和怎样去做。这只是顺其自然的事情。第一个挑战就是这种语言看上去会像什么。然后便是怎样分析表达式?D?D这是一个很大的问题，现在看来，当时我们做的是极其笨拙的……
约翰·巴库斯论Fortran的发明
怎样与机器对话?
有句谚语说：需要是发明之母。但有些发明家却不是由于需要的驱使，而更多的是由于对不精确或效率低下的不满。约翰·巴库斯就是这样一位发明家。他在三个重大的创造中扮演了主要的角色：Fortran，第一个高级程序设计语言；巴库斯－诺尔范式，为高级语言提供描述语法规则的方法；和一种叫FP的函数程序设计语言。今天，这几个发明推动着全世界的研究和商业进展。但对于巴库斯自己来说，这个发明却是起因于对他能找到的概念上的工具的不耐烦。
好象整个家庭看起来都对效率低下感到不满。第一次世界大战前，巴库斯父亲在阿特拉斯火药公司从普通员工升到了首席化学家的职位，这是一家生产用于炸药的硝化甘油的制造商。很好的理由导致了他的提升。
他们的工厂常常发生爆炸，或者产量极低，他们并不知道这是为什么。这种产品对温度极其敏感。我父亲发现他们使用的德国产的昂贵的温度计并不准确。于是，他去了德国，学习温度计制造，并得到了一些好温度计，这样他们的工厂便不再发生那么多爆炸了。
第一次世界大战期间，老巴库斯居于军火官员的高位。但他并没有得到许诺的战后在杜邦公司的工作，于是他改做证券经纪人。到1924年约翰·巴库斯在费城出生时，他父亲已经在战后的繁荣中发了财。巴库斯在特拉华州的威尔明顿度过了他的童年，然后就学于宾夕法尼亚州波茨敦市很有名望的希尔学校。
我年年不及格，从未学习过。我讨厌学习。我只是到处走来走去打发时间。结果每年我都去新罕布什尔州的暑期学校，夏日里可以去划船，度过美好的时光，这真令我高兴。
1942年巴库斯在希尔学校迟迟地毕业后，去了弗吉尼亚大学，他父亲希望他在那儿学化学。巴库斯喜欢理论知识，但讨厌实验室。他把大多数时间花在舞会上，等着被征入伍。到第二学期末，他每周只上一堂课?D?D一堂轻松的音乐欣赏课。最后，校方处罚了他，他在弗吉尼亚大学的学业便结束了。1943年，他参了军。
巴库斯成了一名下士，在乔治亚州的斯图沃特堡率领一个防空小队，但他在一次能力测试中的成绩使得陆军决定送他参加匹兹堡大学的工程预科学习。后来的一次医科能力测试可能救了他的命。
我的战友们都送到了突围战役二战期间美军和德军之间最重要的战役之一。?D?D译者注的战场上，而我去哈弗富德(Haverford)学院学习医学预科。
作为医学预科学习的一部分，巴库斯到大西洋城医院的神经外科病房护理重伤员。一次偶然的机会，巴库斯被诊断出脑袋上有骨瘤，然后安装了一块金属板进去。不久，他参加了第五大街医院（现在的纽约医学院）的医科学习，但只学了9个月。
我讨厌那儿。医科学校的人不喜欢思考。他们只会背书?D?D那是他们需要你做的全部。你不需要思考。
巴库斯发现他脑袋里的金属板装得不对，便到附近的一家有专业平板技术的斯塔屯岛医院更换了一下。他找到技术员并自己设计了一个。那以后，巴库斯便没再作过医学方面的工作。他在纽约城租了一套每月18美元的小公寓。
我的确不知道我到底想要做什么。我觉得自己想要的是一套高保真的音响，因为我喜欢音乐。那时候并没有那种东西，于是我到一所无线电技术学校学习。我有了一位非常好的老师，这是我遇到的第一位好老师，他让我与他合作为一家杂志计算一些电路的特性。
我记得作了一些相对简单的计算，得出放大电路曲线中的几个点。这是一件费力、乏味又烦人的工作，但它使我对数学感起了兴趣。它有所应用使我感兴趣。
巴库斯到哥伦比亚大学基础学院注册学习了一些数学课程。他不喜欢微积分，但喜欢代数。1949年春，25岁的巴库斯差几个月就要毕业拿到数学学士学位了，但他仍然不知道自己想要做什么。
那年春天的一个晚上，他参观了IBM公司曼迪逊大街上的计算中心。他被带领参观了选择顺序电子计算器(SSEC计算器)，这是IBM公司早期的电子（真空管）机器之一。
这台庞大的SSEC计算器占满了一间大屋子，遍布着管子和电线。参观过程中，巴库斯曾对导游提起他正要找工作，导游告诉他去找主管。
我说算了，没法儿去。我看上去又散又乱。但她仍然坚持，我便去了。作了一次测试并通过了。
巴库斯受聘在SSEC计算器上工作。这台机器从现代意义上来说实际上不是计算机。它没有存储软件的存储器，程序必须通过穿孔纸带输入。SSEC计算器有着成千上万个电子机械部件，运行并不可靠。
在这台机器上工作非常有趣。一切都由你自己掌握。你必须时时待在那儿，因为这台机器每3分钟便会停止运行和出错。你必须设法让它重新运行。
这种程序设计是非常原始的。
你只是读参考手册，得到一系列指令，这就是关于程序设计你所知道的全部。每个人必须想出办法怎样去完成什么东西，当然有无数种不同的方法，人们会用无数种方法去做它。
巴库斯在SSEC计算器上工作了3年。他接手的第一个较大的项目是计算月历?D?D任一给定时刻月球的位置。那时候，IBM公司便能负担一个纯粹科学部门的昂贵开支，该部门和哥伦比亚大学有一个联合项目，是为了在科学研究中找到使用穿孔卡和纸带机的方法。这个联合体的支柱便是商业和政府用的穿孔卡片机产品。极其庞大的SSEC计算器给了公众深刻的印象，但它却只是一台不能存储数据的计算器，IBM最终还是抛弃了这种技术。无论公司的动机如何，巴库斯在SSEC计算器的工作中学到了很多东西，也为科学计算作出了他的第一个贡献?D?D快速编码，这起因于在小机器上无法计算大数。
快速编码: 在小“字”中计算大数
计算机中，“字”是指计算机能够进行加减乘运算的数的长度。这些字有固定的长度，通常是8到32位二进制数，依不同的硬件而不同。长度的限制使得表示从埃（毫米的千万分之一）那么小到光年那么大的值必须进行特殊的处理。
科学计算领域的先驱之一就是著名的数学家约翰·冯·诺依曼(John von Neumann，1903－1957)。冯·诺依曼在匈牙利还是孩子时就是一个数学神童，还在中学时他就完成了第一篇数学论文。他还有超常的记忆力。他曾开玩笑地把整个《剑桥古代世界史》背了下来。他的研究成果包括古典数学和量子力学的基本结论，还发明了博弈论。冯·诺依曼1933年移民美国，到了普林斯顿的高等研究所，在二次大战的曼哈顿计划中担任领导。
冯·诺依曼认识到设计原子弹将需要计算非常大和非常小的数。宾夕法尼亚大学摩尔工程学院的一个电子计算器项目引起了他的兴趣。1944年他加入了这个项目，开始作为观察员，后来作为参与者，并提出了制造一台不仅存储数据而且存储指令的机器的想法?D?D这也是现代所有计算设备实际使用的方法。提出想法和发明并不一样。冯·诺依曼把发明归功于艾伦·图灵，他理论中的“机器”也存储指令。制造电子存储器归功于摩尔学院的约翰·埃卡特(John Eckert)，他用水银振动管存储数据。
战后，冯·诺依曼设计了自己的计算机（一般称为Johniac）和一些最早的程序，用于解答核物理中不能手工计算的问题。冯·诺依曼在科学计算方面的兴趣促使他建议使用“比例因子”用于在计算机中存储和操作非常大和非常小的数。
这种想法比较简单。假设一个计算机字只能存储三个数字。当表示数517时，把517写入该计算机字，并设定比例因子为0；表示51.7时，把517写入该字，并设定因子为-1；表示5170时，把517写入该字，并设定因子为1；表示5,170,000时，把517写入该字，并设定因子为4；等等。正的比例因子表示跟在数后的0的个数，而负的比例因子表示小数点右边数字的个数。
在设计计算过程中，程序员并不知道每个计算结果的精确值，但应该知道（或者冯·诺依曼相信如此）其比例因子。是的，这个想法足够简单?D?D如果你是一个伟大的数学家的话。巴库斯却有着程序员的眼力。
你必须对问题非常了解，因为什么样的比例因子都有，你必须防止数溢出或由于取整误差太大发生错误。因此，由于机器的特性，程序设计是非常复杂的。
在IBM公司，巴库斯和哈伦·荷里克(Harlan Herrick)一起，编写了一个叫快速编码的程序用于支持浮点数运算。浮点数带有自己的比例因子，因此使程序员省却了设定比例因子的麻烦。巴库斯设计快速编码的经验为以后更大的挑战作好了准备。
每个人都看见了程序设计有多昂贵。租借机器要花去好几百万，而程序设计的费用却只会多不会少。程序设计之所以如此昂贵，是因为必须雇佣很多程序员用“汇编”或第二代语言编程，这比0和1的二进制或机器码只进了一步。汇编语言消耗大量时间；为一台特定的机器编写命令然后调试大量出现的错误是一件非常费力的工作。程序常常蒙混过关，实现不了最终目标。
Fortran：第一个高级计算机语言
1953年12月，巴库斯给他在IBM公司的老板卡斯伯特·赫德(Cuthbert Hurd)写了一个备忘录，建议为IBM 704机设计一种程序设计语言(IBM 704已经可以进行浮点数计算)。这就是后来的公式翻译语言?D?DFortran。其目标非常明了。
它仅仅意味着使程序设计得更快一些。我并没有打算让它在别的机器上使用。当时几乎也没有别的机器。
但巴库斯首先必须克服冯·诺依曼的强烈的反对，当时他是IBM公司的顾问。
他并不认为程序设计是个大问题。我想他主要的反对意见之一是不知道用浮点数会有什么样的麻烦，对于定点数至少有麻烦时知道麻烦在哪儿。但他对于程序设计的费用并不了解，他的确认为Fortran是个浪费。
不管怎样，赫德还是批准了这个计划，冯·诺依曼也不再反对。巴库斯随便找了几个有经验的程序员和刚从学校毕业的年轻数学家。到1945年秋，他的程序设计小组已经清楚地认识到：要为IBM 704机设计一种使程序设计更加方便的语言。
正如他们所认识到的，设计语言是比较简单的。而将其翻译成机器能够直接理解的语言才是真正的挑战。进行这项翻译任务的程序叫编译器。巴库斯和他的小组没有现在可以让一个大学本科生在一个学期里设计和实现一种新的语言编译器的算法。特别是没有设计编译器的核心部分句法分析器的好方法。
句法分析是计算机中相当于图解语句的一项工作，这是我们中的大多数人一离开学校便很高兴地忘记的一件事。在图解语句时，要分析出语句的不同部分之间的关系：限定词、名词、动词、形容词、副词，然后用树形结构表示出来。（见图1-1。）
在语言编译器中，句法分析器画出这棵树，然后把高级语言（便于人们理解的语言）翻译成机器语言。机器语言是由一系列直接输入计算机电路中的指令组成。（不同的计算机型常常使用不同的指令?D?D这就是一个苹果机程序无法在IBM兼容机上运行的原因。）
图1-1分析一个英语句子
机器语言程序的效率取决于程序设计者利用快而短时的存储器的效率。大多数现代计算机至少有16个寄存器，有的有上千个。不过比起较慢的随机存储器（RAM）中成百万字节的信息来说这只是一个小数目。但大多数运算却是在寄存器中进行的。
比如，算术表达式（A＋B）/C翻译成如下的序列：
把A复制到寄存器1
把B复制到寄存器2
把C复制到寄存器3
把寄存器1与2相加，其和放入寄存器1
把寄存器1除以寄存器3，其商放入寄存器1
在这个例子中，算术运算要求把数据放入寄存器中。（有些机器不需要把数据放入寄存器中，但这样运算会慢得多。）如果下一步运算要用到变量D和E，语言翻译器就要决定是把D和E放入寄存器4和5中，还是再次使用1、2或3。这个决策取决于A、B、C何时将再次使用以及其他许多因素。这是一个复杂的问题，直到现在仍未解决。巴库斯和他的小组是尝试对这个问题得到一个合理解答的第一批人之一。
但最大的挑战还是Fortran的一个新特点：DO循环语句。这种语句是程序员用来简便地进行重复运算的。比如，指令序列：
DO 13 J=1,100
C［J］=A［J］+B［J］
13 CONTINUE
把A的第一个元素加上B的第一个元素得到C的第一个元素，然后把A的第二个元素加上B的第二个元素得到C的第二个元素，等等。
有效地编译DO语句需要用到一个特殊的寄存器?D?D“变址寄存器”。在Fortran最初设计使用的IBM 704机中只有3个变址寄存器，这是一个宝贵的资源。
哈伦·荷里克发明了DO语句，我们知道在这儿我们会遇到问题?D?D怎样实现它。我们只有3个变址寄存器，却有这么多脚标(在这个例子中是J，复杂的程序可能有20个以上的脚标)。
在程序中算出哪些信息使用哪个变址寄存器是极其困难的。如果你想用一般的方法做这件事，你得到的编码会极其糟糕。我们知道必须分析代码出现的频率和各种东西。
巴库斯小组中的所有成员都和他一样关心效率。Fortran的设计者们明白如果他们的新的高级语言生成的机器语言比一个优秀程序员手工做的效率更低，那么程序员们是不会使用这种高级语言的。由于这个原因，他们几乎一半的工作都是为了生成效率更高的机器码。结果，Fortran以其良好的性能而著称。
IBM 704机大约只有80个用户，包括通用电气、联合航空公司、洛克希德(Lockheed)公司和其他一些飞机制造工业的用户。西屋电气公司(Westinghouse)1957年4月幸运地成了Fortran的第一个商业用户，巴库斯的小组给了他们一套存储着语言编译器的穿孔卡片。
循环的贵族发明家
巴库斯和20世纪50年代的任何其他参与实践的计算机科学家并不知道，循环是在100多年前发明的。1833年，拜伦拜伦(Lord Byron，即George Gordon Byron)，18世纪英国著名浪漫主义诗人和讽刺作家。?D?D译者注的女儿奥戈斯塔·安达(Augusta Ada)遇见了查理·巴比奇(Charles Babbage)，他正在设计一个叫分析机的机械计算机器。8岁时就是数学天才的安达是当时仅有的几个理解巴比奇眼光的人，他们开始了整个一生的维多利亚式的合作，这足以使她成为世界一流的程序员。在为分析机设计程序时，她发现了引入循环甚至是子程序的必要性。
她整理了一篇描述分析机的文章，但拒绝以自己的名义发表，因为她觉得妇女被认为不能写科学论文。后来在巴比奇和她丈夫洛夫莱斯伯爵(Earl of Lovelace)的敦促下她最终同意以A．A．L的名字缩写发表。安达的生活在悲剧中结束。她成了一个赌徒、酒鬼和可卡因吸食者，36岁时死于癌症，正是拜伦笔下悲惨的结局。
他们以为这是全套Fortran，没用任何指令便运行了它。他们在进行流体力学的计算?D?D计算机翼等类似结构承受的压力用于设计飞机。他们本来应该先用桌面计算器和风洞为研究风力对于飞机等的影响而建造的隧道，风速由人控制。?D?D译者注。
Fortran的第一个应用程序运行正常，但西屋公司的科学家和其他一些人不久便发现了Fortran编译器中大量的错误。巴库斯小组在随后的6个月里改好了它们。
虽然巴库斯领导了他那个杰出的小组4年，尝试了一次极耗精力的复杂的努力，但仍然对参与该项目一直很谦虚。
我替那么多人(罗伯特·纳尔逊(Robert Nelson)、哈伦·荷里克、洛伊丝·海贝特(Lois Haibt)、罗伊·纳特(Roy Nutt)、艾文·齐洛尔(Irving Ziller)、谢尔登·贝斯特(Sheldon Best)、大卫·赛尔(David Sayre)、理查德·戈德堡(Richard Goldberg)、彼得·谢里登(Peter Sheridan))获得如此多的荣誉看起来很不公平，是他们创造了大量的东西。管理这样一个小组并不需要很多精力。每个人都过得很愉快，我的主要职能只是中止午餐后开始的象棋比赛，让大家下午两点继续工作。
从Fortran发表近40年后，它仍然是科学计算所选择的语言。它一直在得到改进便是其重要性的一个证据。比如1992年，一个国际标准委员会给Fortran加入了一个新的特性，允许程序员告诉编译器多台计算机可以共享单个DO循环语句，如果需要的话。我们将在以后讨论这个问题。
巴库斯50年代末才停止Fortran的工作。但他对程序设计的贡献却刚刚开始。
1958年5月，一个国际商业和学术计算机科学家委员会在苏黎世召开大会。他们的目标是改进Fortran，并设计一种单一的标准化的计算机语言。他们设计的国际代数语言后来称为Algol语言。
Algol比Fortran有两个明显的优点。第一，这种新语言引入了局部变量的概念。每个程序给不同的数据元素定义不同的名称。在上面的一个Fortran例子中，我们定义了元素A、B和C。通常，在一个程序中总是有很多数据元素，以至程序员总要冒重复使用名称的风险。也就是说，程序员有可能在同一个程序中把一个已经存在的名称给了一个新的元素，这样会导致一些很不愉快的错误。有着常见名字的人都能很自然地理解这种问题：账单寄错了地址，信用因为错误的原因而被拒绝，大晚上的电话是找别人的。程序设计中，在整个程序中意义不变的名称叫“全局变量”，弄混对象的情况叫“名称冲突”。
消除“名称冲突”的一种方法是让名称的使用环境局部化。比如，在约克城提起“公爵”一般指约克城的公爵，而在新港爵士音乐会上提起“公爵”很可能是指艾林顿公爵艾林顿公爵(Duke Ellington，即Edward Kennedy Ellington)，20世纪美国著名作曲家。?D?D译者注。同样，局部变量指其名称只在一定的有限环境中有效的计算机内存单元。在这个环境之外，同样的名称可以指向不同的内存单元。
Fortran只允许全局命名，而Algol却可以局部命名。除了方便以外，局部命名还使约翰·麦卡锡近来引入计算机科学中的递归这种程序设计形式成为可能。
计算机的递归函数是部分按照自身定义的。举一个日常生活中递归定义的例子。一个女子如此定义自己的母方祖先：我母亲是我的母方祖先，而我母亲的任何母方祖先都是我的母方祖先。这个定义初看起来好象是循环的，不过让我们仔细地看一看。
假设安是巴巴拉的母亲，巴巴拉是卡罗尔的母亲，卡罗尔是多娜的母亲。（还可以继续定义尤妮斯、弗洛伦斯等。）按照我们的定义，巴巴拉是卡罗尔的母方祖先，因为她是卡罗尔的母亲。安也是卡罗尔的母方祖先，因为她是巴巴拉的母方祖先（她是巴巴拉的母亲）。我们已经知道安是卡罗尔的母方祖先，我们会看到安也一定是多娜的母方祖先。
递归使得程序员可以把一个问题拆成许多小问题，然后把各个小问题的解答黏合在一起。比如，若要把一大堆纸按顺序排好，可以先把其中的一半排好，然后排剩下的一半，最后再把两部分合起来。
从严格的理论意义上来说，递归和局部命名并没有使这种新的语言功能比Fortran更强，但却提供了一种新的思考方式，产生了后来像深度优先搜索那样的算法，我们将在陶尔扬一章中讨论这种算法。
巴库斯喜欢Algol中蕴含的那些思想，但却对清晰地表示它们感到很困难。
他们只是用英语描述什么东西。这是陈述?D?D而这是例子。你对这些Algol委员会非常苦恼(尽是关于术语的徒然的讨论)，意识到需要做点什么。你得学会怎样做到精确。
为了解决这个问题，巴库斯使用了一种叫上下文无关文法的形式体系，刚刚由语言学家诺姆·乔姆斯基(Noam Chomsky)发明（见第26页框图“上下文无关文法和巴库斯－诺尔范式”）。乔姆斯基的工作来源于埃米尔·波斯特重写语法的理论工作。
巴库斯到底是如何想到这种综合方法的，这肯定能让历史学家忙一阵子。
这是一个奇怪而混乱的问题。我发誓研究语法的想法来自埃米尔·波斯特，因为我曾在莱姆·埃斯塔特(Lamb Estate，IBM公司设在哈德逊的思想库)上过马丁·戴维斯的课。……因此，我认为如果想要描述什么东西的话，只要像波斯特那样做就行了。但马丁·戴维斯告诉我他很久以后才教过这门课(根据戴维斯的记录是在1960～1961年)。我便不知道如何解释了。对于乔姆斯基我一无所知。我是一个孤陋寡闻的人。据马丁·戴维斯推测，一个受过哈佛训练的逻辑学家，也是Fortran小组成员之一的理查德·戈德堡可能曾与巴库斯讨论过波斯特和乔姆斯基的工作。
由于一系列的偶然事件，巴库斯的发明最后成为著名的巴库斯-诺尔范式，开始是1959年6月巴库斯在联合国教科文组织在巴黎召开的关于Algol的大会上试图解释他关于精确语法的思想。
当然，这篇论文我写得太晚了，没有收录在大会的报告集中。我手拿着这篇论文去了大会。因此没有很好地分发它。但彼得·诺尔(Peter Naur)读到了它并作了许多修改。
诺尔是一名丹麦数学家，他改进了巴库斯的记号法，并用来描述整个Algol语言。程序设计语言界开始试用Algol的时候，诺尔的参考手册证明是当时描述语言语法的最好的参考书。
从他自己的发明中把程序设计解放出来
巴库斯发明了世界上最早的和最流行的程序设计语言之一，并发展了一种可以描述许多语言的符号系统。许多人，甚至许多杰出的科学家，都可能曾沿着这些成就前进。但巴库斯没有。对于是否喜欢自己所作的东西，他并没有把握。
当你写好一个Fortran程序后，你无法判断程序到底会怎样进行。Fortran程序读取两个数，然后把它们相乘，然后存储起来，然后去做别的事，然后再作判断，等等。试图确定实际上在计算什么并不容易。试图用不同的方法计算(也很困难)，因为你基本上不知道程序在干什么。
巴库斯的目标是使得程序员能够知道自己想要做什么，而并不需要知道怎样做。1977年巴库斯在图灵奖受奖演说“程序设计能从冯·诺依曼风格中解放出来吗”中，向计算机科学界介绍了这个概念。
上下文无关文法和巴库斯－诺尔范式
我们考虑以下一些英语短语的描述，以便了解巴库斯－诺尔范式。术语“名词短语”和“动词短语”借自现代语言学。
句子→ 名词短语动词短语
名词短语→冠词形容词名词|冠词名词
动词短语→动词名词短语
形容词→红 | 蓝 | 黄 | 大 | 小 | 聪明的
名词→房屋 | 女孩 | 男孩
动词→喜欢 | 打
冠词→the | a
竖线“|”表示可选择。比如，冠词可以是“the”也可以是“a”。语法告诉我们“女孩喜欢男孩”是一个正确的句子，因为“女孩”构成一个名词短语，而“喜欢男孩”构成
一个动词短语。从语法上来说，“聪明的房屋喜欢男孩”也是正确的，尽管这个句子在意义上是不合常理的。
在程序设计语言中，巴库斯－诺尔范式也具有这种性质。只要遵从其规则，就会得到语法上正确的程序，编译器就能成功地将其翻译成机器语言，并保留所写的高级语言程序的原有含义。当然，原来那个程序仍然可能没有意义。编译器只保证翻译正确，而不管原程序是否正确。
提起冯·诺依曼与他早年反对这位杰出的数学家开发Fortran并没有关系。巴库斯所指的是冯·诺依曼所阐述的计算机的特征：即处理器与内存连接，程序和数据都存储在内存中。按照巴库斯的看法，这种特征意味着这样一个基本循环过程：处理器从内存中输入数据，对其执行一些操作，然后把结果返回内存。巴库斯认为遵循这种范式的程序设计语言缺乏透明度。在约翰·麦卡锡的Lisp语言（主要用于人工智能）和肯尼斯·艾华逊(Kenneth Iverson)的APL语言的基础上，巴库斯提出了一种叫FP的语言。其主要目标是通过数学函数构造程序。
一般（冯·诺依曼式的）语言和像FP那样的函数语言的主要差别在于，一般语言直接修改计算机内存，而函数语言却依靠“函数构造”。巴库斯在他的图灵奖受奖演说中用两个数组的内积的例子介绍了他的FP语言，这是一种物理中常用的运算。标准冯·诺依曼风格的语言大体上以如下的形式写这个运算：
c:=0
for i:=1 step 1 until n do
c:=c+a［i］*b［i］
巴库斯从几个方面批评了这种形式，特别是以下两个方面。第一，c被重复修改，这样理解该程序的唯一方式是理解每一次修改是用于把又一个乘积加到一个运行着的总和上的。因此，人们为了理解它就必须能够在心里执行这些代码。第二，这种形式定义了向量（a和b）及其长度（n）。对于一般的向量，这些都需要作为“参数”进行传递?D?D在大多数语言中这都是一件需要诀窍的事。而在FP语言中，内积运算则如下定义：
Def Innerproduct=(Insert+)(ApplyToAll*)(Transpose)这个式子须从右往左读。Transpose把两个向量的对应元素排成对。在上面的例子中，a［1］和b［1］成对，a［2］和b［2］成对，等等。“(ApplyToAll*)”以每对元素之积取代它们。“(Insert+)”求这些积之和。
巴库斯认为，这主要有三个优点。第一，没有隐藏的状态（例如上面程序中的变量c）。第二，它对任意两个长度相等的向量都有效，因为它没有定义变量（因此不需要传递参数）。第三，不需要重复计算。每一步，或者每个“函数”（Transpose, ApplyToAll和Insert)在一个叫做“构造”的过程中只对前一步运算的结果操作了一次。
具讽刺意味的是，函数语言包括FP语言，并没有流行起来，其原因正是Fortran的成功之处：函数语言程序难于编译成有效的形式。随着处理器和内存速度的增加，权威们预测将不用再对程序的效率那么关心，但这些预测至今仍未实现。
并且，FP语言对许多现实中的程序设计任务并不合适，特别对那些主要是读取数据、修改数据并将其返回数据库的任务。像修改平衡帐户那样的任务自然是适合于冯·诺依曼范式的。
设计一种函数语言然后将其与实际工作结合起来是很难的。对此谁都会有疑问。
如果说巴库斯没有解决这个问题的话，他却漂亮地提出了这个问题。而其他计算机科学家将从此循着他的建议前进。巴库斯1991年退休以后，彻底地从计算机科学界退了出来，同时也从科学中退了出来。他只是冥想和读一些克里希纳穆尔蒂(Krishnamurti)和叶娃·彼拉克斯(Eva Pierrakos)写的反省的书籍。
大多数科学家是因为惧怕生活而成为科学家的。在科学中有所成就是非常诱人的，因为不必与人发生冲突，不必忍受人际关系的痛苦，不必在世界上艰苦前进就可以成就这些东西。脱离尘世是多么的诱人?D?D这个有几分清净的世界，你可以全力施展你的才华，而没有任何痛苦。解决问题的痛苦和生活中的痛苦比起来是微不足道的。
内省不是一种科学活动：它不可重复，没有关于怎样内省和你要追求什么的好理论。通过对自己的反省可以欣赏到宇宙的神秘，这是很奇怪的。你并不需要试图去发现物理定律。
第三章
如果希望计算机有一般的智能，那么外在结构就必须基于一般的常识和推理。
约翰·麦卡锡
怎样与机器对话?
一个5岁的小女孩玩着一辆塑料玩具车，把它推来推去，按着喇叭。她知道不能在餐桌上玩它，也不能用它打弟弟的脑袋。上学以前，她把小车放在弟弟够不着的地方。放学后，她认为在原来放小车的地方可以找到它。
引导她的行为和想法的推理非常简单，任何她那个年龄的小孩都懂。但大多数计算机则不懂。计算机的问题一部分在于它缺乏一个5岁的小孩就已经从父母那儿学到的日常社会环境的知识，比如不要损坏家具，不要伤着小弟弟。另一部分问题在于计算机没有我们日常的推理能力，我们使用了一种与常规逻辑不同，因此也与一般计算机程序员的思维不同的基于经验的推测常识体系。常规逻辑使用的是一种叫“演绎推理”的推理形式。演绎推理使得我们可以从“所有失业的演员都是待业者”和“赛贝是一名失业的演员”这样的陈述推出新的陈述“赛贝是待业者”。演绎推理的优点在于其可靠性?D?D如果前提成立，那么结论也成立。它还是单调的（一个数学术语，其基本含义是“不变的”），即如果获悉新的与前提没有矛盾的事实，那么结论仍然成立。
但尽管大多数人在学校中学过演绎推理，却很少在实践中使用它。这个5岁的小女孩相信她的玩具车仍在原处，因为她把它放在了弟弟够不着的地方，但如果某天她上学前看见弟弟爬上了凳子，她可能就不会那么有把握了。5岁小孩就会的常识推理依赖于基于经验的推测，这可能会由于新事实的出现而不得不作出非单调的修改。在这一点上，这个5岁的小孩并不特别。
甚至公认的演绎推理大师夏洛克·福尔摩斯也并不是常常运用演绎推理。关于一匹受伤的赛马“银驹”(Silver Blaze)的历险故事中，极具天才的福尔摩斯从看门狗没有叫这件事得出结论?D?D它认识罪犯。这很聪明，似乎是有道理的，在这个故事中也证明是正确的，但这却不是演绎推理?D?D狗可能被麻醉了，或者戴了口套，或者跑出去追兔子了。
程序员知道怎样让计算机进行演绎推理，因为其中的数学很容易理解。但如果想让计算机进行这种人类所赖以生存的推测性的而又常常正确的常识推理的话，就得发明一种全新的数理逻辑。这是约翰·麦卡锡为自己确立的目标之一。
有一些其他原因使麦卡锡成名。他发明了Lisp（List Processing，表处理）语言，人工智能中的主要语言，它从一开始就带来了丰富的语言设计思想。作为一名难题设计者和教师，他在从密码技术到平面性检验的众多新领域激发了其他计算机科学家的灵感，正如我们将在拉宾和陶尔扬的章节中看到的一样。
麦卡锡1927年生于波士顿一个共产党活动家的家庭，这是一个经常搬迁的家庭。他父亲是爱尔兰天主教徒，职业是木匠、渔民和社团组织者，他家不停地从波士顿迁到纽约再到洛杉矶。他母亲是立陶宛犹太人，在联邦出版社的通讯社当新闻记者，后来就职于一家共产主义报刊，最后成为一名社会工作者。麦卡锡把他早年对科学的兴趣和家庭的政治观点联系起来了。
对于技术有利于人类有着一种普遍的信心。我记得我还是孩子时就读过一本书叫《十万个为什么》?D?D一本流行的苏联科普书籍，伊林(M.Ilin)写于30年代初。我记得没见过任何像那样的美国书籍。十几年前，我曾非常有兴趣地读到过一个特别早熟的中国小孩的故事，他很小就读《十万个为什么》，真了不起。
麦卡锡记忆中自己十几岁时是个普通的人，但有证据表明并非如此。他在上初中时，曾得到一份加州理工学院的课程目录，并翻了翻大学低年级的数学微积分课本。他买来这些书，完成了所有的练习。这使他1944年进入加州理工学院时可以免修头两年的大学数学。
1948年，麦卡锡开始上数学专业的研究生。那年9月，他参加了在加州理工学院举行的希克松脑行为机制专题讨论会。伟大的数学家及计算机设计者约翰·冯·诺依曼发表了一篇关于自复制自动机?D?D可以复制自身的机器的论文。虽然在大会上没有人明确地把机器智能和人类智能联系起来，但冯·诺依曼的讲话却激起了麦卡锡的好奇心。
1949年，已经开始在普林斯顿大学上数学专业博士研究生的麦卡锡第一次尝试了在机器上模拟人类智能。
我把有智慧的东西看成有限自动机，它与同样是有限自动机的环境相联系。我和约翰·冯·诺依曼见了面，他非常赞成。他说：“把它整理出来，整理出来。”但我没有整理出来，因为我觉得它并不太好。
自动机是一种随着时间从一个状态转入另一个状态的机器模型。比如，标准的汽车启动过程中，司机点火后汽车从“熄火”状态转入“空挡但启动”状态。司机挂挡发动时，汽车转入“启动且挂一挡”状态。交互式自动机从某个状态转入另一状态是取决于其自身的状态以及它所观察到的其他自动机的状态。有的自动机是有智能的（可假定司机是），但智能并不是必需的组成部分。交互式自动机则试图统一两者。
麦卡锡否决了自己使用自动机模拟人类智能的第一次尝试，但状态和状态转换的思想在十几年后重又出现在他情景演算的工作中。
在这整段时间里，麦卡锡想要制造一台像人一样有智慧的机器的兴趣一直持续着。1952年夏，普林斯顿的一位研究生杰里·雷纳(Jerry Rayna)建议麦卡锡找一些对机器智能有兴趣的人去收集这方面的文章。麦卡锡最早接触的人之一就是克洛德·香农(Claude Shannon)，他发明了自己所称的通信数学理论。其他人将其简称为信息理论。香农的理论最初用于电信，后来用于语言学、数学和计算机科学等诸学科。
香农不喜欢浮华的术语。他把这卷书命名为《自动机研究》。但这些文章到我手里的时候我却失望了。其中关于智能的东西并不多。
因此1955年我开始组织达特茅斯计划时，为了让参与者们清楚我们要讨论的是什么，我使用了“人工智能”这个术语。
1956年的达特茅斯夏季人工智能研究计划证明是计算机科学史上的一个里程碑。这个雄心勃勃的10个人两个月的研究计划的目标是（用建议中的话来说）：“在认为学习的每个方面或智能的任何其他特性都可以准确地加以描述，可以制造机器对其进行模拟这样一个猜想的基础上前进。”
4名组织者麦卡锡、马文·明斯基(Marvin Minsky)（当时在哈佛）、纳撒内尔·罗切斯特(Nathaniel Rochester)（一位杰出的IBM计算机设计师）和香农向洛克菲勒基金会申请了一笔今天看来是非常少的赞助：每位研究人员1200美元，加上“外地人员的火车票费用”?D?D总共7500美元。
在建议中，麦卡锡写道，他将研究语言和智能的关系，希望设计一种计算机能够“较好地博弈和完成其他任务”。几乎40年后回忆起这次会议时，麦卡锡非常坦率地形容了自己当时的愿望。
对于这次会议我的目标是完全不现实的。我以为一个夏天的讨论便可以实现主要的计划。实际上这种模型我从未参与过，而只是在一次夏季防空军事会议上听说过。
当这次会议无论如何解决不了发明一台具有真正智能的机器这一极其困难的问题时，他们确立了一些目标和方法，使得人工智能作为计算机科学中一个独立的、最终也相当有潜力的领域这一地位得到了承认。虽然许多与会者没有继续从事该领域的研究，但还是有几个人取得了有深远影响的成就。
卡耐基·梅隆大学的艾伦·纽威尔、肖(J．C．Shaw)和赫伯特·西蒙描述了他们的第二代信息处理语言（IPL 2）。IPL 2是这三位科学家致力于构造一个叫逻辑理论机的用于证明初等逻辑和博弈论中定理的程序的结果。为了做到这一点，他们需要一种程序设计语言能够操作表示象棋棋子和逻辑变量真值等对象的符号。因为这不同于对数进行算术运算，他们建议使用他们所说的“表结构”。
为了说明用于符号处理的表的用法，让我们冒昧一下梦游仙境的爱丽斯。出自英国作家Lewis Carroll的文学作品《爱丽斯漫游奇境记》，爱丽斯、猫和哈特是文中的三个主人公。?D?D译者注假设猫告诉爱丽斯：“不是我疯了，就是哈特疯了。”我们用C，H，A分别表示断言猫、哈特或爱丽斯疯了。我们可以用表格式把猫的陈述表示为(或 C H)。然后猫又告诉爱丽斯：“不是你疯了，就是哈特疯了。”聪明的爱丽斯可以把这两个陈述一起表示为(与 (或C H) (或A H) )。最后猫说：“我们三个中只有一个疯了。”就是说，至少有两个没有疯。爱丽斯可以将其表示为(与(或C H) (或A H) (或 (与 (非A) (非C) ) (与 (非A) (非H)) (与 (非C) (非H) ) ) )。
把这些陈述表示成表格式后，我们就可以定义一些表操作规则，比如(与 (或 X Y) (或 Z Y) ) = (或 (与 X Z) Y)。也就是说，如果不是X就是Y和不是Z就是Y成立，那么，不是X和Z就是Y成立。使用一些这样的规则我们就可以得出结论(与H (非C) (非A) )。那么，根据猫所说，只有哈特疯了。
使用表进行逻辑推理的优点在于，随着推理的进行表可以扩展、收缩和重组。此外，可以用同样的形式表示规则和数据。大多数与会者都认为表操作显然是一个成功。达特茅斯会议的另一个成就是马文·明斯基提出的构造一个几何定理证明器的建议。明斯基书面试验了几个例子，认为证明几何定理是纽威尔和西蒙所提议的基于规则方法的一种较好的应用。IBM公司的赫伯特·格勒尔特(Herbert Gelernter)和纳撒内尔·罗切斯特决定去实现这个程序。格勒尔特后来开发了一个帮助有机化学家合成新的化合物的工具。他儿子大卫是一位在并行程序设计和医用人工智能领域有名的研究人员和设计师。麦卡锡担任这个定理证明项目的顾问，这给了他设计智能行为程序的机会。
格勒尔特和他的助手卡尔·格贝里希(Carl Gerberich)采纳了我的建议，从Fortran开始，设计他们所谓的FLPL?D?DFortran表处理语言。他们还加入了自己的一些想法。
1956年，约翰·巴库斯和他IBM的小组发表了第一个高级程序设计语言Fortran。Fortran把从事数字计算的程序员从为每种机器分别编写汇编语言的麻烦中解放出来。直到现在，它仍然是科学和工程计算中的通用语言。FLPL第一次尝试了扩展Fortran，使其具有符号操作功能。1958年夏天，麦卡锡在IBM工作时，试图用FLPL语言给他在中学时就熟知的代数式的差分问题写表程序。但这需要递归条件表达式比如，y2的微分等于2y乘以y的微分；因为表达式的微分是依照其组成部分的微分定义的，所以这是递归的。，Fortran却不支持递归。
如果Fortran支持递归的话，我肯定会用FLPL做下去。我甚至考虑了怎样在Fortran中加入递归的问题。但这样就太杂凑了。
结果，IBM公司不久便失去了对人工智能的兴趣。有些顾客害怕有智能的机器会威胁他们的就业，60年代初IBM公司的市场信息表明计算机应该只是哑巴数字捣弄机，让它们做什么就做什么?D?D既不多也不少。
麦卡锡不再去修补Fortran，而发明了Lisp。纽威尔，肖和西蒙后来把IPL形容为一种随时间渐渐复杂的语言，而麦卡锡把Lisp形容为一种随时间渐渐简单的语言。
“Lisp”是表处理语言(list processing)的缩写，正如所预期的那样，Lisp中所有的数据都用表表示。这些表限制在圆括号中。比如，（罗伯特 教 丹尼斯）就是表示句子“罗伯特教丹尼斯”的一个表。在这种情况下，顺序是很重要的，因为顺序表明了谁教谁。
可以用表（白菜 莴苣 草莓）表示一个商品列表。这种情况下，顺序就不重要了?D?D因为这三种商品可以按任意次序购买。在这两个例子中，表都是包含“原子”作为其元素。原子不像表那样，它没有组成部分。表却可以包含（并且常常包含）其他表作为组成部分。比如，（罗伯特 打（卡罗尔 和 丹尼斯））反映了句子的语法结构，其中的圆括号表明卡罗尔和丹尼斯都是被打的对象。再举一个例子，（乘6（加x y））表示6×（x＋y）。在这儿顺序是很重要的，圆括号表明x和y是一起的。
这样，表就能表示科学和工程中的任何标准的数学结构和语言中的句子结构。
从一开始麦卡锡就有了一个热心的合作小组。
1958年秋我回到麻省理工学院的时候，我和明斯基有了一个大工作室，一台键控穿孔机，一名秘书，两个程序员和六名数学专业研究生。早在春天时我们就向杰里·威斯纳(Jerry Wiesner)申请了这些，准备实施一个人工智能计划。
尽管我们还没有准备好书面的提议，我们的要求就得到了满足。幸运的是，麻省理工学院的电子研究实验室刚刚从美军得到一个没有限制的联合服务合同，并且还没有分派各种资源。我想这是美国比别的国家更早研究人工智能的原因之一。纽威尔－西蒙的工作也可能是因为美国空军提供给兰德(Rand)公司的灵活的支持才得以成功。
随着工作的进展，麦卡锡试图改进这种语言的表达能力。1959年，当他试图展示这种语言可以明确地表达任何可计算函数时，他加入了一种叫“求值”的特性。
求值允许程序定义新的函数或过程，然后作为程序的一部分予以执行。大多数语言在执行新函数以前会强行中止程序，并且“重新编译”。由于求值函数可以执行任何函数，所以它扮演的是一个“万能图灵机”的角色，是其他计算机的通用模拟器。
求值概念具有非常实际的意义。比如，经纪人事务所由于国际资本市场活动的原因，所以每天24小时每周7天都提供计算服务。假如有人编写了一个用新的方法分析路透社股票数据的程序。各经纪人希望马上能使用这个程序，但只有不损失他们的机器使用的情况下他们才会这样做。求值使这成为可能。
表处理语言Lisp
Lisp中的基本操作
典型的Lisp函数和过程或者把一个表拆开，或者把几个表合并成一个新表。比如，“追加”函数对两个表通过将其中一个附加于另一个末尾的方式生成一个新表。这在用名词和动词短语构造句子时是有效的。让我们看看鲍勃和艾丽斯两个人的关系：（追加（鲍勃 吻）（艾丽斯））生成表（鲍勃 吻 艾丽斯）。
另一个有用的函数“倒置”把一个表中的元素从尾到头颠倒过来。这样（倒置（追加（鲍勃 吻）（艾丽斯）））将生成（倒置（鲍勃 吻 艾丽斯）），然后生成（艾丽斯 吻 鲍勃）。而另一方面，（追加（倒置（鲍勃 吻））（艾丽斯））将生成（追加（吻 鲍勃）艾丽斯），然后生成（吻 鲍勃 艾丽斯）。
无论如何，鲍勃和艾丽斯的关系总可以明确。我们可以看到Lisp程序可由处理表和产生新表的函数构造而成。这就是巴库斯发明FP时吸引他的东西。
Lisp中的递归和求值
麦卡锡把递归作为Lisp处理策略中的核心部分。递归是一种按照自身定义操作的方法。程序员通过定义较简单问题的实例绕过了循环定义的禁忌。
比如，如果表中只包含一个元素，可以定义其倒置为表本身。而表中有几个元素时，可如下定义其倒置：把表中除第一个以外的所有元素的倒置和包含第一个元素的表追加在一起。如果这听起来很拗口的话，试试就行了。表L的第一个元素称为L的头，表示为（头 L），而剩下的元素称为尾，表示为（尾 L）。这样我们便可以按Lisp的精神（虽然不是Lisp的语法）把该程序写为：
定义（倒置L）为
如果L只有一个元素，则（倒置L）等于L
否则等于（追加（倒置（尾L））（表（头L）））
举一个具体的例子试一下，艾丽斯、鲍勃和卡罗尔三个人：（倒置（艾丽斯 鲍勃 卡罗尔））＝（追加（（倒置（鲍勃 卡罗尔））（艾丽斯）））=（追加（（卡罗尔 鲍勃）（艾丽斯）））=（卡罗尔 鲍勃 艾丽斯）。
因为函数和过程本身也是定义为表的，所以它们也可以通过其他的函数和过程来构造。这样求值函数就可以执行这种函数或过程了。
Lisp中蕴含的思想吸引了负责设计Algol语言（巴库斯和诺尔为其发明了巴库斯－诺尔范式）的国际委员会。1960年在巴黎召开的针对这种语言的委员会会议上，麦卡锡提出了递归和条件表达式的建议。经过一番对记号法的争论后，该委员会接受了这种思想。
Algol是第一个采纳Lisp创新的语言，但当然不是最后一个。Algol的后继语言Pascal、C、Ada和大多数其他的现代程序设计语言都支持递归和条件表达式。但直到目前，主流语言都不支持求值，很大一部分原因在于语言设计者们担心给程序员往运行着的程序中加入新特征的能力是危险的。但现在许多程序必须整日整夜连续运行好多天，求值这种特性越来越显得必要，所以大多数试验中的新语言都包括像求值那样的东西。
Lisp成为人工智能的标准语言已经有大约40年了。麦卡锡并没有料到它有这么长的使用寿命，他甚至曾建议将其修改成类似Algol那样。但人工智能程序员们更喜欢Lisp最初的语法，麦卡锡像以前的巴库斯和以后的凯一样，失去了对这种语言的控制。
构造常识逻辑
麦卡锡总是把Lisp看成是达到自己以前的也是现在的主要目标?D?D“制造一台像人一样有智慧的机器”的手段。
他在一篇发表于1959年的论文《具有常识的程序》中详细地阐述了这个目标。这篇论文标志着他开始了把数学的严密应用于称为常识的那种难以捉摸的推理形式的一生的追求。
为了使他的目标具体一些，他把具有常识的程序定义为可以“独立地推出任何它被告知或它已经知道的事物的直接结果”。他举了一个例子，描述一个人从坐在自己的办公桌前到驱车去机场的推理过程。
在介绍完论文随后的讨论中，著名的逻辑学家和语言学家耶霍舒亚·巴尔-希勒尔(Yehoshua Bar-Hillel)指出麦卡锡的方法是“半成熟的”和“伪哲学的”，说麦卡锡提议的推理不能叫“演绎推理”，因为其结论不总是成立的。希勒尔说道：“坐出租车去机场不是更便宜吗·难道不能取消旅行去做许多别的事吗·”
在对批评的回答中，麦卡锡同意论文的基础建立在“不明确的哲学假定上。……任何时候，我们设计程序让计算机从经验中学习，我们都把某种认识论编进了程序中。”从那以后，解决认识论问题成了麦卡锡和其他少数人工智能理论家研究的中心。
在你了解这些工作以前，也许你想知道为什么他们首先要把常识纳入到计算机程序中来。这对科学和社会有什么好处呢·麦卡锡提供了一种答案。
所有的科学，包括所有的专业理论，都包含着常识。当你想要改进这些理论时，你总要回到常识推理，它指引着你的试验。
因此，如果有人想要设计一个更好的象棋程序，他就得试验他得到的这种程序，让它对局进行分析。所有关于进行何种试验的推理都是与常识相关的。
在许多科学家的著作中都可以找到类似的观点。比如，理查德·费曼(Richard Feynman)在他著名的讲座中，讨论对称时说道：
我们所有的物理思想在其应用中都需要一定的常识；它们不是纯粹的数学或抽象的思想。我们把设备移到新的位置说现象相同时，必须明白我们的意思。我们的意思是说我们移动了所有我们认为相关的东西；如果现象不同，我们便会想到有些相关的东西没有同时移动，而我们就要去把它找出来。Richard P.Feynman, Robert B．Leighton, and Matthew Sands, The Feynman Lectures on Physics（New York：Addison··Wesley,1977）vol. 1，p. 11-1。
常识推理的主要优点之一在于其弹性。当它面对环境中出现的新情况时，能够很好地适应。麦卡锡举了这样一个例子。
假设一位旅客想从格拉斯哥转由伦敦飞往莫斯科。现在假定他了解一些关于需要购买机票和从一个地方飞到另一个地方的结果的事实。
可以编写许多程序进行如下推理：如果他从格拉斯哥飞往伦敦并由伦敦飞往莫斯科，那么他就在莫斯科。但如果他在伦敦丢了机票会发生什么呢·你就不会再认为事情会按原计划进行。而再买一张机票的计划倒是可能的。现有的任何应用程序都不会如此细致地考虑这种环境条件的变化。
1964年， 当时已是斯坦福人工智能实验室负责人的麦卡锡提出了一种叫情景演算的逻辑，情景代表世界的一个状态。当主体行为时便导致新的情景。主体将采取何种行为取决于他对情景的了解。
在麦卡锡举的乘飞机的例子中，没有意识到自己丢了机票的旅客会直接去机场，而意识到自己丢了机票的旅客会去旅行社找（假定是有智慧的）旅行代理人。
情景演算和有限自动机理论中都有状态转换的概念。但情景演算中的推理不仅取决于情景，而且取决于主体对情景的了解。他或她了解的或可以了解到的越多，所作的决定就越正确?D?D而这正是他或她所希望的。情景演算吸引了众多的研究人员，他们用很多方法应用了它或它的变体，但这种理论也带来了许多新的问题。
在一个许多主体互相联系的世界中，和一个主体有关的情景可能随着其他主体的行为而改变。但在我们的常识世界中，我们知道大多数其他主体的行为实际上并不影响我们的决策。
比如，丢了机票的旅客（主体A）的行为不会因为美国总统（主体B）早晨在华盛顿特区慢跑时买了一个小麦松饼而改变。逻辑不会告诉我们这两个行为无关，而是我们的直觉让我们得出这样的结论（除非我们相信不太可能的阴谋）。
在和爱丁堡大学的帕特里克·海斯(Patrick Hayes)一起写的一本书中，麦卡锡把简洁地表示不受特定行为影响的众多事实的一般问题称为“框架问题”。
简单说，当特定行为发生时，框架问题并不需要涉及所有并未变化的事物。
大多数成功的破案都依赖于对框架问题的洞察。当侦探英雄找到答案时，他总是辨别出了多数人可能摒弃或忽视的行为和主体之间的联系。比如在《银驹》中，福尔摩斯发现了罪犯是看门狗的主人，因为这条狗没有叫。很少有人，包括他可敬的伙伴华生博士也没有想到这一点。
“对这件案子，思维推理的艺术，应当用来仔细查明事实细节，而不是去寻找新的证据。这件惨案极不平凡，如此费解，并且与那么多人有切身利害关系，使我们颇费推测、猜想和假设。困难在于，需要把那些确凿的事实?D?D无可争辩的事实与那些理论家、记者虚构粉饰之词区别开来。”《夏洛克·福尔摩斯全集》，第335页。
对于一台需要在任何时刻都可能出现新的令人惊讶的事实的环境中解决框架问题的计算机来说，它必须像夏洛克·福尔摩斯那样有一种新的推理方法。1974年马文·明斯基发表了《表征知识的框架问题》（麻省理工学院出版社）一书，书中他辩论道，人工智能不应该使用逻辑，因为逻辑天性就是保守的。
为了理解他的意见，考虑一下当你听说一个朋友有一只叫班乔的鸟时会发生什么。你想象的情景中可能包括班乔会飞。但如果现在你朋友告诉你班乔是只企鹅，或剪了翅膀或腿被绑着或怕飞的鸟，你就不会再认为班乔会飞了。虽然没有违背班乔是鸟的事实，但新的信息却让你改变了最初的结论。
明斯基称这种推理形式为非单调的。常规的演绎推理总是单调的?D?D如果新的信息和旧的不相矛盾的话，则新的信息不会改变原有的结论。日常推理中充满了非单调性。我们相信总统在华盛顿特区吞下小松饼不会影响伦敦希思罗机场的旅客，但如果我们了解到他吃小松饼是开始希思罗的萨克斯音乐会的信号时我们就会改变主意了。
麦卡锡认为非单调性是解决框架问题的一种途径。从直觉上来说，有智慧的主体进行推理时先假定疏远的行为是无关的，但当发现那些行为事实上有关时则须重新推理。麦卡锡不像明斯基那样，他认为逻辑是解决这个问题的唯一可靠的基础。为了做到这些，逻辑需要一种推测的形式化基础。
麦卡锡提出了“限定”方式，这是一种允许主体进行如下推测的规则：“我已经知道了所有可能具有性质P的对象。因此，如果我又遇到一个新的对象，则假定其不具有性质P。”
比如在班乔的例子中，假定班乔会飞。也就是说，对于鸟排除不会飞的性质。相反，对于大象则排除会飞的性质，即在没有相反证据的情况下，假定大象不会飞?D?D它不具备会飞的性质。因此，限定是一种对事物进行基于经验的猜测的方法。在了解到更多事实的情况下可能会证明它是错误的，但同时它也使我们可以构造出一些有用的假设。
在某个情景中想要知道排除哪些性质时，就必须知道关于世界的事实。在班乔和大象的例子中，就必须知道一般的鸟会飞，而一般的大象不会。人们几乎不用想就可以应用这样的知识，但这却给计算机提出了极大的挑战。
比如，百科全书告诉你拿破仑死于1821年，而威灵顿威灵顿公爵一世，即Arthur Wellesley，曾在滑铁卢战役中击败拿破仑。?D?D译者注死于1852年，拿破仑死时是英国政府囚禁在圣赫勒拿岛上的囚徒。
但百科全书告诉你威灵顿听说了拿破仑的死讯的可能性非常小?D?D你必须对百科全书上的知识应用常识才会知道这一点。
你可能进行如下推理：威灵顿可能听说了拿破仑的死讯，因为他大半的职业生涯都为拿破仑所困扰。因此你可以排除“未听说困扰自己的人的死讯”。而更简单的问题，拿破仑听说了威灵顿的死讯吗·当然没有，因为“听说比自己晚死的人的死讯”是不可能的。
基本问题在于怎样利用情景的背景知识作出自然的推测，正如将军们了解对手的情况一样。麦卡锡开始发展一种操作和利用背景知识的新的逻辑形式。
部分的目标只是理解人们所说的话。如果人工智能系统无法利用背景知识，那么它便无法解释人们的语言。
为了了解这个问题的难度，我们可以考虑这样一个事实，即正确地应用背景知识不仅对机器来说是困难的，人们自己有时也会有麻烦。前任众议院发言人托马斯·奥尼尔(Thomas P．(Tip) O··Neill)曾讲过一个欢迎新任总统罗纳德·里根(Ronald Reagan)就职的故事。奥尼尔告诉里根他有胡佛·克利夫兰(Grover Cleveland)的办公桌。里根笑着说他曾在电影中扮演克利夫兰。里根说的是棒球手胡佛·克利夫兰·