计算机领域的诺贝尔奖。事实上，如果没有他们作出的贡献，现代计算机很难像 今天这样深入平常百姓家。在本书中，他们解释了自己对科学产生兴趣的缘由， 回顾了成长环境和其他科学家对他们产生的影响，闸述了各自进行基础探索和发 现的途径，同时也分享了对未来的看法和主张。 在说明这些思想及其重要性时，本书尽量避开了科学术语，因此读者不需要 任何专业知识，只要对计算机的发展演变，以及这一领域的科学家们的思维方式 感兴趣即可。 设想回到1690年去拜访艾萨克·牛顿。你也许会问他对于惯性力的看法，而 他也可能会讲述自己早年间在伍尔索普的农场生活”。能与计算机学科的艾萨 克·牛顿们当面交流，是我们莫大的荣幸，这也鼓舞我们写出了本书。 关于写作风格与表现形式 本书立足于现场访谈的第一手记录，因为我们相信，这些科学家们的言传身 教更能帮助读者透彻地了解他们的个性和方法，这比经过我们的转述和修饰要好 得多。我们负贵勾画出相应的历史背景，并解释相关的科学和数学原理，但关于 这些科学家是如何提出自己的发现，当时他们都在想些什么，最好还是听他们自 己来说。 考虑到行家里手通常会对技术细节感兴趣，我们把相关部分用补充内容的形 式展现出来。也许读者把书读完一遍之后还会要回头再看看这些部分。我们也为 刚刚接触这个领域的读者们提供了一份基本术语的词汇表。此外我们还在每部分 开篇几页按时间顺序列出了本领域及诸位科学家生平的大事，帮助读者在时间上 进行定位。本书的最后两章“后记”和“结语”，则探索了两个问题：伟大的计算 机科学家在他们的人生和思想上是否存在者家族相似性？25年后，类似本书这 样的著作又将会探讨哪些新的发现？ 第一部分语言大师：如何与机器对话 1 1约翰·巴科斯不断进取的发明家 4 品
2约翰·麦卡锡不走寻常路的常识逻辑学家 16 3艾伦·C.凯清晰的浪漫主义梦想28 第二部分算法大师：如何快速地解决问题 39 4艾兹赫尔·W,戴克斯彻可怕的说明文和最短路径 42 5迈克尔·0.拉宾机会的可能性51 6高德纳（唐纳德·E.克努斯）逐新趣异一线牵 66 7罗伯特·E.陶尔扬寻找优秀的结构 76 8莱斯利·兰伯特时间、空间和计算 89 9史提芬·古克和利奥尼德·列文良解难觅101 第三部分架构大师：如何构建更好的机器115 10弗雷德里克·P.布鲁克斯成功带来的愉悦 117 11伯顿·J.史密斯与光速赛跑 127 12W.丹尼尔·希利斯与生物学的连结 136 第四部分机器智能的雕塑大师：如何让机器更聪明 147 13爱德华·A费根鲍姆知识的力量149 14道格拉斯·B.莱纳特一场二十年的豪赌159 后记：下一个25年173 .巴ocin.C0m 参考文献189 第一部分 语言大师：如何与机器对话 假设现在第二次世界大战刚结束不久，而你是一位总工程师，负贵一项计算 机制造计划。你收集了一堆电线和开关，任务是构建出一台机器，以便预测飞机
在空中的飞行模式。鉴于当时的技术水平，你只能使用一些不可靠的部件，而且 构建的机器要便于装配。这台机器消耗的电力足以供应一个小型工厂。此外你还 为它配各了一个足以容纳几千个字符的存储器、加法器、乘法器，以及一套用于 计算的指令集。 指令是最不需要操心的问题，它们只需表达清楚，能够完成任务即可。 为了提高效率，你需要让各种指令尽可能与工程设计的细节相适应。这台机 器的存储器具有不同的运行速度和能耗，因此你需要设定一个指令组用于在慢速 存储器和快速存储器之间传递数据，设定另一个指令组用于在快速存储器中对数 据进行四则算术运算或其他操作。这种分组方式无疑不利于编写预测飞行模式的 程序，如果将存储器视为一种不分类的资源来进行指令分组，应该会容易不少， 但你并不为此担心。在当时，一毛钱就能雇来一打学数学的编程人员，而相比之 下，机器本身却非常精致、昂贵且罕见。 五年之后，情况发生了根本性的变化。你吃惊地发现，随者对程序的需求高 张以及硬件成本的降低，程序设计的费用要远高于硬件的购买和维护成本。（这种 态势一直延续了下来。到了20世纪90年代中期，在大多数企业的软件开发环节 中，程序设计的开支已经达到了硬件开支的50倍左右.)因此你为自己制定了两 个新的目标：缩短程序第一个版本发布所需要的时间，以及让程序更易于改进， 以适应客户需求的变化。 V你决定修致编程人员与机器沟通所使用的语言。新的语言应当反映出所要解 决问题的结构，而不再是反映存储器的快慢层级和算术运算。每一种行业都会根 据自身的目的而发明某种语言，例如电影导演会用“开拍”(action)这个简单的 术语来表示“摄像师开始拍摄，演员开始表演，其他人员各就各位”。由于在20 世纪50年代中期，计算机主要应用于纯科学和数据处理，因此你更关注的是创造 一种数学语言，包括运算公式、求和以及向量数组。为了开拓思路，你拜访了许 多研究人员，也了解了许多项目，它们允许程序员输入类似(W+门/Z这样的数 学表达式，然后计算机就能自行编译并且进行相应的运算。 到了1958年，有一门科学编程语言脱颖而出，它就是约翰·巴科斯和他在 IBWM公司的同事合作设计的Fortran(取自formula translation的缩写，即公式 n Warner Back 19242007)被称为Forran爵言之父，197年获得图灵奖。本书第1章详
翻译)。这门语言至今仍然是自然科学界使用最为广泛的编程语言。 与此同时，一个研究团队在1956年开辟了计算机的一个崭新领域：人工智能 (artificial intelligence)。这门学科的一个目标是创造出具备人类推理能力 的计算机。由于人类大部分的推理过程都需要进行抽象（例如积木的相对位置、 句子的语法、不同洗衣皂的优缺点)，偏重数学运算的Fortran语言对此并不适用。 卡内基-梅隆大学的艾伦·纽厄尔“和赫伯特·西蒙“建议用符号表(1isto symbols)来表现抽象概念，并且把推理过程视为一种“符号操作”(symbol manipulation). 假设有一块红色积木、一块蓝色积木和一块黄色积木。一个5岁大的小孩也 可以告诉我们，如果红色积木在蓝色积木之上，而黄色积木又在红色积木之上， 那么黄色积木必然也在蓝色积木之上。将前两个事实用符号表来表示，我们可能 会写：(above redblock blueblock)以及(above yellowblock blueblock)。之后 引用符号操作规则，我们便能得出：如果(above x y)和(above z x),则(above z y)。 年轻的约翰·麦卡锡对这一想法印象深刻，但他认为纽厄尔和西蒙的设计过 于复杂。他简化了设计，加入了两个强大的功能，也就是我们所知的递归 (recursion)和求值(eval),并且创造了一门称为Lisp的语言（取自“Iist processing”的缩写，即表处理).isp不仅是人工智能方面的首选语言，且自 1958年诞生起，和Fortran一起不断为计算机语言的设计提供灵感。 这一年的夏天，一个国际计算机科学家小组在苏黎世成立，开始设计纳入 Lisp元素的Fortran语言的继任者.他们的精诚合作产生了里程碑式的A1gol60, 它直接催生了Pascal、C和Ada这些语言，同时也是从PostSeript到Excel等各 种语言的直系祖先。 然而到了20世纪70年代早期，一些研究人员逐渐发现由Fortran、A1gol 和Li即所衍生出来的上百种语言都存在着一个共同的弱点：写出来的程序让人很 难读懂。在实际工作中，人们发现如果想修改程序的行为，往往都需要整个重写。 “赫伯特·西蒙(Herbert lexand Simon,中文名为司马贺，191620O1)是现代一些重要学术领域，如人工智能 的人之一并且获得了很多荣，如1975年 :的堂的20是人工背能方面的务机。191年铁得图现关。参见本书第2苹
拥有生物学背景的艾伦·凯认为应该把程序构建成像活的生物那样：由独立 自主的“细 胞”构成，彼此通过讯息传递进行合作。他认为通过自主的单元来构建程序，将 会使这些单元能够融入新的上下文情境。对于这种“细胞”，他使用了“对象 (object))一词来称呼，并且将这种方式称为“面向对象”(objectrientation). 对象的行为取决于它得到的州忌。 第一部分语言大师：如何与机器对话 比如说，在与图片有关的程序中，可以用“旋转30度”、“开始打印”这样的 讯息或命令来描述常用行为。而如果是操控登月机器人的程序，则可能是“收集 岩石样本”或者“找到高度超过1米的石块”。20世纪70年代中期，艾伦·凯带 领他在施乐公司的团队设计出了首个面向对象 的语言Smalltalk。大批年轻人在数年间加入了它的用户群。由此开始，Smalltalk 深刻地影响了C+等日趋成熟的编程语言，其自身也衍生了一批专业的追随者。 过去四十年间，世界上诞生了成百上千种编程语言，约有60种在今天仍然被 广泛使用，其中包括文字处理、电子表格、图形设计和动画设计等领域的专用语 言。就像工具帮助木匠解决问题一样，一门好的编程语言也能帮助我们解决计算 机的问题。而且编程人员也正如木匠习惯于自己的工具那样习惯于自己钟爱的语 言。 1语言学家本杰明·沃尔夫"曾经说过：“语言塑造了我们思考的方式，决定 了我们思考的内容。”他这番话是针对人类语言所言，而计算机语言则进一步印 证了这一主张，尤其是那些灵感来源于巴科斯、麦卡锡和凯的成果的计算机语言。 制的若人类的思哈模武