高德纳(Donald E. Knuth)的二十年计划

[收藏注：有谁不知道Donald E. Knuth吗，不知道的话，唔，怎么办呢？去看别的网页吧。这篇文章可能写的比较早，如果看到一些信息与现时不符，请不要张大你的嘴巴。:)]

高德纳已经五十八岁了。他打算再花二十年的时间继续他的著作，The Art of Computer Programming. 大家知道 Donald E. Knuth 是资讯科学界公认的大宗师，知道他以他的重量级著作 The Art of Computer Programming(以下简称TAOCP)[2,3,4] 闻名于世，原计划要出七册，但目前只完成了三册。但也许并没有很多人知道他还有个中文名字：“高德纳”。

TAOCP 这套书的名气这么大，敢去碰它的人反倒不多。寒假我因为一些原因，读了高德纳的另一本书 "The Stanford GraphBase"[1]。大师的书到底是什么样子呢？

高德纳在序言里说了写这本书的原因：在写 TAOCP 的第四册前，他想要用一个叫做 ladders 的游戏当作贯穿全书的例子。于是写了不少相关的程式和庞大的测试资料，最后集结成了一个程式／资料库。他想这套 GraphBase 可以作为大家测试 graph 演算法的基础，让那些 “街上混的程式员们 (programmers-on-the-street)” 知道电脑科学家们也会做实际的事。另外，这套程式库全部用他鼓吹的 literate programming 方式写成，也可以当成一个活生生的例子。最后一个，但却是最重要的原因是，"to have fun".“的确，快乐是这一路上最主要的原因，但我不敢承认。电脑科学家们总是得装出一副咬牙工作的样子，让别人心甘情愿付给他们高薪水。但迟早这个社会得承认，有些工作仍然值得尊敬 --- 即使它们比任何事情都要来得有趣。”

我不禁笑了。高德纳在办正事的途中岔出去做别的事情，一做就是好几年已经不是第一次。TeX 这个现在大家都在用的排版系统不就是他嫌 TAOCP 被排得不好看，因此自己卷起袖子研究电脑排版的产物吗？Tex 耗去了他十年的光阴，而这本 Stanford GraphBase 则可以追溯到二十年前。高德纳好像永远不怕老？

Ladders 这个游戏是这样的：挑两个五个字母的英文单字，试试看一次一个字母，把一个字变成另外一个。但是在过程中它必须仍然是一个英文单字。比如说把 black 变成 white 的方法是这样的：

black -> brack -> brace -> trace -> trice -> trite -> write -> white

大家看得出来，如果把每个单字当作一个 node, 两个单字如果只差一个字母，就连一条 edge, 那么这个游戏可以想成在两个 node 中找一条 path 。

但 GraphBase 有趣的地方却是资料。高德纳收集了一个含 5757 个单字的资料库。他参考了 1971 年以前 Beeler 为了这个游戏专门编的一部字典，删去老的字，加入新的单字。高德纳花了很大篇幅解说他选字的标准：姓名不选，所以 Knuth 就没有了；但是 gauss 已经是一个电磁学单位，所以受录了进去。他很耐心的等到 e-mail 终于被大家写成 email, 以便把他收集到资料库中。

接下来就开始玩这个资料库啰。高德纳发现 5757 个单字中，有 774个 degree 是 1 的（只有一根接出去的 edge），位居第一。Degree= 2 的也有 727 个。株连最广的单字是 "bares" 和 "cores" ， degree = 25，而 "cores" 的 25 个邻居都是 degree 大于 9 的。 Degree = 1 的单字中有 103 组根本就是孤零零的两两成对，如 alpha-aloha, gonad-monad. 跑一个找 connected component 的演算法，发现大部分的单字都在同一个有 4493 个单字的大 component 里面。

高德纳自己定了一个方法横量单字在文章中的出现频率。在这 5757个单字中，"which" 是最常出现的，其次是 "there" 和 "their"。"often" 果然常出现，比出现("occur") 还要常出现。

看来高德纳真的是玩得不亦乐乎呢。"to have fun", 于是我们可以想像高德纳出这本书的真正原因，是他自己建了这些资料后，发现越玩越有趣，终于忍不住想出书了。

玩过了单字，想知道美国大学足球队谁比较强吗？高德纳已经把 120支队伍的 638 场比赛建成 graph 了。他又参考资料，找出美国的128 个城市之间的最短距离，并且在发现前人的资料明显错误后自己写程式来修正。把蒙娜丽莎的微笑扫描起来后，高德纳示范了如何运用 bipartite graph matching 的技巧，用骨牌重新拼出这幅名画。

高德纳的文笔亲切而幽默。CWeb 是他大力推广的 literate programming 系统，他认为每个人都应该有一套。 “但是今天已经没什么人能永远跟上新软体的发行，所以如果你没有 CWeb,也不用觉得太有罪恶感。” 接下来他解释如何安装 Stanford GraphBase, 这一段的makefile 可以给想学 make 的同学们做很好的参考。如果装不起来呢？高德纳问，你有没有好好祈祷呀？最后，他希望大家能像他一样，多用这些程式库和资料档做些实验，“也许有天你也会迫不及待地想出本这样的书呢！”

浏览了全书，我想：高德纳到底是太闲，还是有用不完的精力？将近六十岁的他，仍旧充满著旺盛的活力和赤子般的好奇心，而这一切又以他深厚的功力做为基础。

四月号的 Dr. Dobb's Journal 做了一篇高德纳的专访[5]。为什么写书写到一半，却花了十年的时间在 Tex 上？他说， Niklaus Wirth （Pascal, Modular-2 和 Oberon 的设计者）一直想设计飞机，但他发现他需要够好的工具，于是他设计了一个个的电脑语言，造了自己的电脑。高德纳也希望他的书能够不因科技的进步而被淘汰，希望即使制书的科技进步，他的书仍旧是用领先的方式制作的。

谈到另一位大师 Edsgar Dijkstra, 他说 Dijkstra 的力量来自于他不妥协的拗脾气。“光是想像用 C++ 写程式就会让他病倒！”Dijkstra 的拿手技巧是钜细靡遗地用 formal 方法推导、检验程式，这和工业界不断产生数以 mega 计的软体，但使用者却无时不负担著 bug 的风险的实际情况显然有段差距。高德纳则认为自己位于两种极端的中间。一方面他赞同 formal 方法提供的可靠性，但他也知道在大系统中这种方式的极限。他尽力维持他的软体的品质，因此他愿意提供赏金给在 TeX 中找到新 bug 的人。

由于高德纳已经不用 email 了，他有一个 Web page[6]，http://www-cs-faculty.Stanford.EDU/~knuth/ 里头还有个 FAQ, 可以看到他中文名字的图章。大家劈头要问的当然是：第四册什么时候出来呀？

他说，TAOCP的第四册将会分成三部份，4A : Enumeration and Backtracking, 4B : Graph and Network Algorithms 和 4C : Optimization and Recursion. 从 1997 年开始，他会以大约每 128 页为一个单位（高德纳好像很喜欢用 2 的乘幂做单位，他付给找出 TAOCP中错误的赏金也是 $65536 分）把第四册的部份散发给大家，听取各方的意见。如果一切顺利，第四册将在2003 年正式完成。第五册的完成时间则定在 2009 年。第五册告一段落后，他会重新整理 TAOCP的一到三册，更新内容。再下一步，他将把一到五册的重要内容全部浓缩在一本书里。之后才著手进行六和七册。所以，高德纳至少得活到 2020 年啰....

为了完成 TAOCP, 高德纳已经退休，过著半隐士的生活。他不用 e-mail, 不怎么会见访客，取消大部分的演讲和旅行。他说，他得用 batch 方式工作，而不能把事情 swap 来 swap 去的。他托人在家里造了一座管风琴，空闲的时间里，他就会弹弹琴自娱。如果你会弹琴，他很愿意和你见个面，来个四手联弹。

为什么那么卖力呢？在DDJ的专访里，当被问到他是否能从 Tex 和 Metafont 图利时，他说，一旦一个人能够喂饱自己，能够有个安身之所，剩下的就是他能为别人做些什么，如何能为群体做出一些贡献了。

因此他很希望程式创作者们不要把演算法当作自己的私产。程式应该容易阅读和了解，因为越多人能够了解它，它才能够发挥越大的影响力。

也许他也是基于这个想法继续 TAOCP 的写作吧？在他的 web page 中，对于他的这件“此生的大事”，他下了这样的注脚：“我尝试著尽我所能的去学习电脑科学里的一些领域，然后把这些知识摘要成大家比较容易了解的方式，让没有那么多时间做这种学习的人也能够吸收他们”。

为了这个目的，他必须阅读超过二十万页的文件，然后把它们浓缩到两千页里头。他写的东西并不是最流行的，但他希望他能从日新月异的新技术中，萃取出值得存活到下个世纪的东西。

不禁想起前阵子同学讨论到的话题：专家是训练有素的狗吗？我们该不该成为专家？高德纳毫无疑问地是个专家，但他的大师学养和风范也许能给我们不少启发。

Reference

[1] Donald E. Knuth, The Stanford GraphBase : A Platform for Combinatorial Computing, Addison-Wesley, 1993

[2] Donald E. Knuth, The Art of Computer Programming, Vol 1 : Fundamental Algorithms, Addison-Wesley, 1973

[3] Donald E. Knuth, The Art of Computer Programming, Vol 2 : Seminumerical Algorithms, Addison-Wesley, 1973

[4] Donald E. Knuth, The Art of Computer Programming, Vol 3 : Sorting and searching, Addison-Wesley, 1973

The Art of Computer Programming 有日文，俄文，西班牙文等许多国的版本。

其中，中文版资料如下

Chinese translation by Guan JiWen and Su YunLin, Pei Xue He Cha Zhao,

Beijing: Defense Industry Publishing Co., 1985

[5] Jack Woehr, An interview with Donald Knuth, Dr. Dobb's Journal, April 1996, p16-p22

[6] Donald E Knuth's WWW Page : http://www-cs-faculty.Stanford.EDU/~knuth/

http://www.geekchic.com/repliq6.htm 也有一篇小小的访问。高德纳最喜欢的语言是 CWeb, 最喜欢的运动是棒球，认为有许多人是他值得崇敬的。高德纳将在最近将他的论文以更浅显的方式整理过后，重新集结出版。这套书的预定读者并不是电脑科学的专家，似乎很值得一读。这套书将有八本，前两册已经出版：

[7] Literate Programming, Stanford, California: Center for the Study of Language and Information, 1992

[8] Selected Papers on Computer Science, Stanford's Center for the Study of Linguistics and Information and Cambridge University Press, spring, 1996

[9] Selected Papers on Analysis of Algorithms, to be published

[10] Selected Papers on Computer Languages, to be published

[11] Selected Papers on Design of Algorithms, to be published

[12] Selected Papers on Digital Typography, to be published

[13] Selected Papers on Discrete Mathematics, to be published

[14] Selected Papers on Fun and Games, to be published