高德納已經(jīng)五十八歲了。 他打算再花二十年的時(shí)間繼續他的著(zhù)作，The Art of Computer Programming. 大家知道 Donald E. Knuth 是資訊科學(xué)界公認的大宗師， 知道他以他的重量級著(zhù)作 The Art of Computer Programming(以下簡(jiǎn)稱(chēng)TAOCP)[2,3,4] 聞名于世，原計劃要出七冊，但目前只完成了三冊。但也許并沒(méi)有很多人知道他還有個(gè)中文名字：“高德納”。
TAOCP 這套書(shū)的名氣這么大，敢去碰它的人反倒不多。寒假我因為一些原因，讀了高德納的另一本書(shū) "The Stanford GraphBase"[1]。大師的書(shū)到底是什么樣子呢？
高德納在序言里說(shuō)了寫(xiě)這本書(shū)的原因：在寫(xiě) TAOCP 的第四冊前， 他想要用一個(gè)叫做 ladders 的游戲當作貫穿全書(shū)的例子。 于是寫(xiě)了不少相關(guān)的程式和龐大的測試資料，最后集結成了一個(gè)程式／資料庫。 他想這套 GraphBase 可以作為大家測試 graph 演算法的基礎，讓那些 “街上混的程式員們 (programmers-on-the-street)” 知道電腦科學(xué)家們也會(huì )做實(shí)際的事。另外，這套程式庫全部用他鼓吹的 literate programming 方式寫(xiě)成，也可以當成一個(gè)活生生的例子。最后一個(gè)，但卻是最重要的原因是，"to have fun".“的確，快樂(lè )是這一路上最主要的原因，但我不敢承認。電腦科學(xué)家們總是得裝出一副咬牙工作的樣子，讓別人心甘情愿付給他們高薪水。但遲早這個(gè)社會(huì )得承認， 有些工作仍然值得尊敬 --- 即使它們比任何事情都要來(lái)
得有趣。”
我不禁笑了。高德納在辦正事的途中岔出去做別的事情，一做就是好幾年已經(jīng)不是第一次。TeX 這個(gè)現在大家都在用的排版系統不就是他嫌 TAOCP 被排得不好看， 因此自己卷起袖子研究電腦排版的產(chǎn)物嗎？Tex 耗去了他十年的光陰，而這本 Stanford GraphBase 則可以追溯到二十年前。高德納好像永遠不怕老？
Ladders 這個(gè)游戲是這樣的：挑兩個(gè)五個(gè)字母的英文單字，試試看一次一個(gè)字母，把一個(gè)字變成另外一個(gè)。但是在過(guò)程中它必須仍然是一個(gè)英文單字。比如說(shuō)把 black 變成 white 的方法是這樣的：
black -> brack -> brace -> trace -> trice -> trite -> write -> white
大家看得出來(lái)，如果把每個(gè)單字當作一個(gè) node, 兩個(gè)單字如果只差一個(gè)字母，就連一條 edge, 那么這個(gè)游戲可以想成在兩個(gè) node 中找一條 path 。
但 GraphBase 有趣的地方卻是資料。 高德納收集了一個(gè)含 5757 個(gè)單字的資料庫。他參考了 1971 年以前 Beeler 為了這個(gè)游戲專(zhuān)門(mén)編的一部字典，刪去老的字，加入新的單字。高德納花了很大篇幅解說(shuō)他選字的標準：姓名不選，所以 Knuth 就沒(méi)有了；但是 gauss 已經(jīng)是一個(gè)電磁學(xué)單位，所以受錄了進(jìn)去。他很耐心的等到 e-mail 終于被大家寫(xiě)成 email, 以便把他收集到資料庫中。
接下來(lái)就開(kāi)始玩這個(gè)資料庫啰。高德納發(fā)現 5757 個(gè)單字中，有 774個(gè) degree 是 1 的（只有一根接出去的 edge），位居第一。Degree= 2 的也有 727 個(gè)。株連最廣的單字是 "bares" 和 "cores" ， degree = 25，而 "cores" 的 25 個(gè)鄰居都是 degree 大于 9 的。 Degree = 1 的單字中有 103 組根本就是孤零零的兩兩成對，如 alpha-aloha, gonad-monad. 跑一個(gè)找 connected component 的演算法，發(fā)現大部分的單字都在同一個(gè)有 4493 個(gè)單字的大 component 里面。
高德納自己定了一個(gè)方法橫量單字在文章中的出現頻率。 在這 5757個(gè)單字中，"which" 是最常出現的， 其次是 "there" 和 "their"。"often" 果然常出現，比出現("occur") 還要常出現。
看來(lái)高德納真的是玩得不亦樂(lè )乎呢。"to have fun", 于是我們可以想像高德納出這本書(shū)的真正原因，是他自己建了這些資料后，發(fā)現越玩越有趣，終于忍不住想出書(shū)了。
玩過(guò)了單字，想知道美國大學(xué)足球隊誰(shuí)比較強嗎？高德納已經(jīng)把 120支隊伍的 638 場(chǎng)比賽建成 graph 了。 他又參考資料， 找出美國的128 個(gè)城市之間的最短距離，并且在發(fā)現前人的資料明顯錯誤后自己寫(xiě)程式來(lái)修正。把蒙娜麗莎的微笑掃描起來(lái)后，高德納示范了如何運用 bipartite graph matching 的技巧，用骨牌重新拼出這幅名畫(huà)。
高德納的文筆親切而幽默。CWeb 是他大力推廣的 literate programming 系統，他認為每個(gè)人都應該有一套。 “但是今天已經(jīng)沒(méi)什么人能永遠跟上新軟體的發(fā)行，所以如果你沒(méi)有 CWeb,也不用覺(jué)得太有罪惡感。” 接下來(lái)他解釋如何安裝 Stanford GraphBase, 這一段的makefile 可以給想學(xué) make 的同學(xué)們做很好的參考。 如果裝不起來(lái)呢？高德納問(wèn)，你有沒(méi)有好好祈禱呀？最后，他希望大家能像他一樣，多用這些程式庫和資料檔做些實(shí)驗，“也許有天你也會(huì )迫不及待地想出本這樣的書(shū)呢！”
瀏覽了全書(shū)，我想：高德納到底是太閑，還是有用不完的精力？將近六十歲的他，仍舊充滿(mǎn)著(zhù)旺盛的活力和赤子般的好奇心，而這一切又以他深厚的功力做為基礎。
四月號的 Dr. Dobb‘s Journal 做了一篇高德納的專(zhuān)訪(fǎng)[5]。 為什么寫(xiě)書(shū)寫(xiě)到一半， 卻花了十年的時(shí)間在 Tex 上？ 他說(shuō)， Niklaus Wirth （Pascal, Modular-2 和 Oberon 的設計者）一直想設計飛機，但他發(fā)現他需要夠好的工具，于是他設計了一個(gè)個(gè)的電腦語(yǔ)言，造了自己的電腦。高德納也希望他的書(shū)能夠不因科技的進(jìn)步而被淘汰，希望即使制書(shū)的科技進(jìn)步，他的書(shū)仍舊是用領(lǐng)先的方式制作的。
談到另一位大師 Edsgar Dijkstra, 他說(shuō) Dijkstra 的力量來(lái)自于他不妥協(xié)的拗脾氣。“光是想像用 C++ 寫(xiě)程式就會(huì )讓他病倒！”Dijkstra 的拿手技巧是鉅細靡遺地用 formal 方法推導、檢驗程式， 這和工業(yè)界不斷產(chǎn)生數以 mega 計的軟體， 但使用者卻無(wú)時(shí)不負擔著(zhù) bug 的風(fēng)險的實(shí)際情況顯然有段差距。高德納則認為自己位于兩種極端的中間。一方面他贊同 formal 方法提供的可靠性，但他也知道在大系統中這種方式的極限。他盡力維持他的軟體的品質(zhì)，因此他愿意提供賞金給在 TeX 中找到新 bug 的人。
由于高德納已經(jīng)不用 email 了，他有一個(gè) Web page[6]，http://www-cs-faculty.Stanford.EDU/~knuth/ 里頭還有個(gè) FAQ, 可以看到他中文名字的圖章。大家劈頭要問(wèn)的當然是：第四冊什么時(shí)候出來(lái)呀？
他說(shuō)，TAOCP的第四冊將會(huì )分成三部份，4A : Enumeration and Backtracking, 4B : Graph and Network Algorithms 和 4C : Optimization and Recursion. 從 1997 年開(kāi)始，他會(huì )以大約每 128 頁(yè)為一個(gè)單位（高德納好像很喜歡用 2 的乘冪做單位，他付給找出 TAOCP中錯誤的賞金也是 $65536 分）把第四冊的部份散發(fā)給大家，聽(tīng)取各方的意見(jiàn)。如果一切順利，第四冊將在2003 年正式完成。第五冊的完成時(shí)間則定在 2009 年。第五冊告一段落后，他會(huì )重新整理 TAOCP的一到三冊，更新內容。再下一步，他將把一到五冊的重要內容全部濃縮在一本書(shū)里。之后才著(zhù)手進(jìn)行六和七冊。所以，高德納至少得活到 2020 年啰....
為了完成 TAOCP, 高德納已經(jīng)退休，過(guò)著(zhù)半隱士的生活。 他不用 e-mail, 不怎么會(huì )見(jiàn)訪(fǎng)客， 取消大部分的演講和旅行。 他說(shuō)，他得用 batch 方式工作，而不能把事情 swap 來(lái) swap 去的。他托人在家里造了一座管風(fēng)琴，空閑的時(shí)間里，他就會(huì )彈彈琴自?shī)?。如果你?huì )彈琴，他很愿意和你見(jiàn)個(gè)面，來(lái)個(gè)四手聯(lián)彈。
為什么那么賣(mài)力呢？ 在DDJ的專(zhuān)訪(fǎng)里， 當被問(wèn)到他是否能從 Tex 和 Metafont 圖利時(shí)， 他說(shuō)，一旦一個(gè)人能夠喂飽自己，能夠有個(gè)安身之所，剩下的就是他能為別人做些什么，如何能為群體做出一些貢獻了。
因此他很希望程式創(chuàng )作者們不要把演算法當作自己的私產(chǎn)。程式應該容易閱讀和了解，因為越多人能夠了解它，它才能夠發(fā)揮越大的影響力。
也許他也是基于這個(gè)想法繼續 TAOCP 的寫(xiě)作吧？ 在他的 web page 中，對于他的這件“此生的大事”，他下了這樣的注腳：“我嘗試著(zhù)盡我所能的去學(xué)習電腦科學(xué)里的一些領(lǐng)域，然后把這些知識摘要成大家比較容易了解的方式，讓沒(méi)有那么多時(shí)間做這種學(xué)習的人也能夠吸收他們”。
為了這個(gè)目的，他必須閱讀超過(guò)二十萬(wàn)頁(yè)的文件，然后把它們濃縮到兩千頁(yè)里頭。他寫(xiě)的東西并不是最流行的，但他希望他能從日新月異的新技術(shù)中，萃取出值得存活到下個(gè)世紀的東西。
不禁想起前陣子同學(xué)討論到的話(huà)題：專(zhuān)家是訓練有素的狗嗎？我們該不該成為專(zhuān)家？高德納毫無(wú)疑問(wèn)地是個(gè)專(zhuān)家，但他的大師學(xué)養和風(fēng)范也許能給我們不少啟發(fā)。
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 也有一篇小小的訪(fǎng)問(wèn)。高德納最喜歡的
語(yǔ)言是 CWeb, 最喜歡的運動(dòng)是棒球，認為有許多人是他值得崇敬的。
高德納將在最近將他的論文以更淺顯的方式整理過(guò)后，重新集結出版。
這套書(shū)的預定讀者并不是電腦科學(xué)的專(zhuān)家，似乎很值得一讀。這套書(shū)
將有八本，前兩冊已經(jīng)出版：
[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
聯(lián)系客服
