《计算机程序设计的艺术》唐纳德·克努特

唐纳德·克努特 ——经典巨著《计算机程序设计的艺术》的年轻作者 :9001/jisuanjifazhanshi/xianqu/23.htm 洋洋数百万言的多卷本《计算机程序设计的艺术》(The Art of Computer Programming)堪称计算机科学理论与技术的经典巨著，有评论认为其作用与地位可与数学史上欧几里得的《几何学原理》相比。本书作者唐纳德·克努特(Donald Ervin Knuth)因而荣获首届计算机先驱奖。 克努特1938年1月10日生于美国威斯康辛州密歇根湖畔的密尔沃基(Milwaukee)。这是一个山灵水秀、人才辈出的地方，“人工智能之父”、诺贝尔奖获得者西蒙(H．A．Simon)也是在这里出生的，而且是1975年图灵奖的得主。但克努特比西蒙小整整22岁，是一个“小字辈”。克努特的父亲是一个多才多艺的人，有研究生学历，当过小学和中学教师，星期天在教堂演奏风琴，还在自家地下室办了一个小印刷厂。从克努特咿啊学语开始，他父母就给他念儿童故事，给他看卡通读物，使他从小就培养了对学习的兴趣。4岁的时候，他成为密尔沃基公共图书馆一个名为“书迷俱乐部”(Book Worm Club)的最年轻的成员(也许也是全世界最年轻的书迷)。5岁的时候，一次他独自坐电车去图书馆看书，天快黑了也不见回家，他父母打电话到图书馆去，值班员在一个书架前找到克努特时，他正坐在地上津津有味地看书，丝毫没有发觉图书馆已经闭馆，读者已经走光了。克努特上8年级时，当地的Ziegler糖果厂为了促销其称为Giant Bar的一种棒棒糖，在学校中搞了一个比赛，看谁能用Ziegler’s Giant Bar中的字母排列组合出最多的单词。克努特假装胃疼，在家里呆了两个星期，利用一部大字典，得出了4500个单词，比裁判掌握的2 000个单词多出一倍多，一举为他所在的班夺得冠军，赢得一台电视机和每人—块Giant Bar而克努特本人则赢得一付雪撬。 在数学上，克努特也很早就表现出天才。高中一年级时，他发明了一种方法，利用这种方法，对任意画出的2条相交直线，他能立即给出相应的方程。 1956年，克努特以各科平均97．5的创记录的高分从密尔沃基路德兰高级中学毕业，进入俄亥俄州克利夫兰的开思理工学院(Case Institute of Technology)攻读物理。这一年，他在中学时就创作的一篇出色的科学幻想小说“普茨比度量衡体系”(The Potrzebie System of Weights and Measures)在美国著名的《疯狂》(Mad)杂志上发表，克努特获得了他的第一笔稿费25美元，并因而获得西屋科学天才的提名奖。在这篇小说中，克努特风趣而富于幻想地提出了替代公制的一种新的计量制度，比如以一本流行杂志的厚度为长度单位，虽然滑稽可笑，却设计得严密周到，天衣无缝，其中甚至还包括一种新的历法。文章刊出后大受欢迎，多次重印，1991年还重印过一次，其时作者克努特即将退休。 大学一年级结束以后的暑假，克努特在学校打工，负责把统计数字画成图表。碰巧他工作室的隔壁就是计算机房，新到了一台IBM 650。当时的计算机体积都很庞大，有供输入和调试的控制台，上面排列着一排排的开关和指示灯，计算机工作时指示灯快速闪烁变化出不同的图案，这引起克努特极大的好奇与兴趣，他接连好几天彻夜不眠地呆在机房，观察它的工作，钻研使用手册，探究计算机的奥秘。一年以后，他终于改学数学，与计算机结缘。这段经历对于克努特是如此重要和关键，以致他在《计算机程序设计的艺术》第一卷的；卷首，不像别的作者那样一般写上“献给自己的父母”或“献给自己的妻子”，而是写着“献给曾经安装在开思理工学院的650型计算机，以纪念那些愉快的夜晚”。他的第一个计算机应用程序也是在650计算机上实现的：他为他所在的校篮球队(克努特人高马大，也喜爱运动)设计了一个复杂的公式，根据球员在每场比赛中的得分、助攻、抢断、篮板球、盖帽等多项统计数字对球员进行综合评估。球队教练根据克努特的程序挑选和使用球员，使开思理工学院在1960年赢得了联赛冠军，克努特的“神奇的公式和程序”也被当地报纸和广播传为美谈。1960年，克努特在开思理工学院毕业，不但被授予学士学位，还被破例同时授予硕士学位。之后他进入加州理工学院研究生院，1963年获得博士学位，留校工作至1968年，然后转入斯坦福大学任教，其间1972—1973年曾经在奥斯陆大学当客座教授。 克努特至今进行了两大工程，一个已经完成，一个尚未完成。第一个大工程就是《计算机程序设计的艺术》系列，开始于他念博士期间，出七卷，第一卷《基本算法》于1968年出版，第二卷《半数字化算法》于1969年出版，第三卷《排序与搜索》于1973年出版，第四卷《组合算法》尚在写作之中。这个工程为什么前紧后松，长期停顿呢?原来，前三卷书出版以后，克努特根据自己在校对清样时的感受，决心对排版技术进行彻底改造，因此中止了第一个工程，而开始其第二个工程。这个工程花费了克努特整整9年的时间和精力，结果就是对整个西文印刷行业带来了革命性变革的TEX排版软件和METAFONT字型设计软件。这两个软件为克努特赢得了ACM的另一个奖项：1986年度的软件系统奖(Software System Award)。但是这两个软件并没有为克努特和斯坦福大学赚过一分钱：克努特把它们作为自由软件无偿提供给用户。这比理查德·斯托尔曼(Richard Stallman，1990年ACM Hopper奖获得者)在1984年发动自由软件运动早了约5-6年。克努特说：“我写这两个程序是出于对书籍的热爱，也想给这个领域以必要的推动。我已经有些名气了，我的书卖得也不错。所以我不需要为我出于热爱而做的事保留专卖权。此外，数学家通常是不为他们发现的定理获取报酬的”。1979年，克努特还创建了TEX用户集团，这个集团10年前的成员数就超过3 000。细心的读者也许会注意到，许多西文书版权页的下部注明“本书用TEX系统排版”。 克努特的两大工程(虽然其中之一尚未最后完成)都是取得很大成功的。《计算机程序设计的艺术》一书以其的丰富和深刻喻为经典，有人甚至称之为“计算机的圣经”，被译为俄、日、西、葡、匈牙利、罗马尼亚等多种文字在世界各国广泛流传，其发行量创造了计算机类图书的最高记录，直至20世纪80年代中期，都一直保持着月销售量每卷达2 000册的势头，成为Addison-Wesley出版社成立以来销路最好的图书。在我国也有译本(可惜书名译为《计算机程序设计技巧》，这是不符合克努特的本意的)。此外，克努特还有许多“小创造”。计算机科学技术中两个最基本的概念：“算法”(Algorithm)和“数据结构”(Data Structure)就是克努特于29岁时提出来的。1973年他首创双向链表。在编译器设计方面，著名的LR(A)文法也是克努特在对自左至右、自底向上的移进一归约进行了深刻剖析的基础上，经过高度概括和集中以后发明的，它表示具有从左(L)到右(R)的分析而向前看A个符号，以确定所要进行的归约和应用何种语法解释。LR(A)文法的识别效率高，在从左至右扫描输入串时，就能发现其中的语法错误，并能准确地指出出错位置，因此被广泛应用。此外，利用LR(A)文法还能正确区分像Flying planes is fun和Flying planes can crash这类(前一个句子“开飞机很有趣”中Flying是动名词，而后一个句子“飞行中的飞机可能出事”中Flying是现在分词当形容词)。以著名的巴克斯—诺尔范式为基础的“属性文法”(attribute grammar)也是克努特首先提出来的。属性文法在普通的上下文无关文法(context-free grammar)的基础上，对每一个终结点或非终结点加上一些属性，和对这些属性进行估值的语义集，从而形成一种新的、有更强表达与描述能力的文法。其中属性是由<属性名，属性值>的有序偶对组成的。属性的内容则可包括模式标识符表等。 在算法方面，有他和他的学生共同设计的诸如Knuth-Bendix算法和Knuth—Morris-Pratt算法，前者是为了考察数学公理及其推论是否“完全”而构造标准重写规则集(rewriting rule set)的算法，曾成功地用它解决了群论中的等式的证明问题，是定理机器证明的一个范例。后者是在文本中查找字符串的简单而高效的算法。此外，克努特还设计与实现过最早的随机数发生器(random number generator)。 20世纪70年代中期，克努特和其他一些计算机科学家曾经设想在未来10年中将产生一种比现有程序设计语言更加强大、更加优美的新型语言，并预先命名它为“乌托邦84”(Utopia 84)语言。乌托邦原是托马斯所著Utopia一书中所描述的人间理想王国，克努特悄用过来代表一种未来的理想语言，希望它有更好的数据结构和控制结构，更符合结构化程序设计的思想，等等。克努特提出Utopia 84已经过去20多年了，虽然程序设计语言在不断地发展与完善之中，但“理想语言”并未出现，可能永远也不会出现。但新一代人会不断进取。克努特在20世纪80年代所倡导的“作文式程序设计”(1iterate programming，国内有人将它译为“文化程序设计”)就是这一努力的又一体现和成果。我们从上小学起不就学做作文吗?作文首先要构思好故事，把事情的来龙去脉交代清楚，这相当于编程时先要把程序逻辑弄好。其次要围绕故事情节尽可能把有关的人物、环境等细节描写得清清楚楚，生动活泼，这相当于在程序中加入必要的注释和说明，以便阅读和理解。所谓作文式程序设计就是要像写作文那样进行编程，从完成的“源程序”中既可提炼出可执行的程序代码，又可生成程序文档，“毕其功于一役”。作文还有一个要点是分段，一篇作文要分成若干段落，以便层次分明，铺陈有序。作文式程序设计也是这样，一个复杂的程序是由若干较简单的片段构成的，较大的片段还可分为更简单的一些小片段。1983年，克努特推出了第一个这样的程序设计系统WEB。WEB包括两个子系统，一个子系统从WEB程序中自动地抽出描述算法的部分，并且加工成PASCAL编译器所能接受的形式，然后据此得到可在计算机上执行的代码。另一个子系统则把WEB程序加工为TEX系统所能接受的形式，并据此得到具有高度可读性的完整的程序文档。显然，WEB就是一个完成“PASCAL作文”的工具。继WEB之后，提姆勃莱比(H．W．Thimbleby)开发出CWEB，和WEB类似，但是一个完成“C作文”的工具。WEB和CWEB都是自由软件，可从因特网上下载。 为了说明作文式程序设计的特色，下面给出采用这种方法编写的源程序的一个片段。 @* Insertion sort This is the standard insertion sort algorithm. Assumes a sentinel at $a[0]$. @p for i:=2 to N do begin V:=a[I];j:=i; @ end @ @= while a[j-1]> v do a[j]:=v 这个片段是采用标准的插入排序算法对一个数组中的元素进行排序。片段中的@符号是系统约定，用以引入作文式程序设计中的各种特征。符号$则通知系统交叉引用某段文本作为代码而非注解。片段中有一个“宏”(macro)，就是{Insert $ v $ in the array)。宏允许缩写，上述宏就可缩写为{Insert．．．)，因此是很方便和精炼的。上述片段经过处理以后获得的程序代码如下所示。 for i：=2 tO N do begin v：=a[i]；j：=i； while a[j-1]> v do begin a[j]：=a[j-1]； j:=j-1 end； a[j]：=v 而处理以后获得的可供印刷的文档则如下所示。 31．Insertion sort．This is the standard inseaion son algorithm．Assumes a sentinel at O[0]． for i=2 tO N dO begin v：=a[I];j:=i； end 32． while a[j-1]> v do begin a[j]：=a[j-1]；j:=j-1 edn