高 德 納 的 二 十 年 計 畫 (转 载）

高 德 納 的 二 十 年 計 畫                                                                  8123033 穆信成 高德納已經五十八歲了。  他打算再花二十年的時間繼續他的著作， 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)」 知道電腦 科學家們也會做實際的事。另外，這套程式庫全部用他鼓吹的 liter- ate 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" ， de- gree = 25，而 "cores" 的 25 個鄰居都是 degree 大於 9 的。 De- gree = 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 program- ming 系統，他認為每個人都應該有一套。 「但是今天已經沒什麼人 能永遠跟上新軟體的發行，所以如果你沒有 CWeb,也不用覺得太有罪 惡感。」 接下來他解釋如何安裝  Stanford GraphBase,  這一段的 makefile 可以給想學 make 的同學們做很好的參考。 如果裝不起來 呢？高德納問，你有沒有好好祈禱呀？最後，他希望大家能像他一樣， 多用這些程式庫和資料檔做些實驗，「也許有天你也會迫不及待地想 出本這樣的書呢！」 瀏覽了全書，我想：高德納到底是太閒，還是有用不完的精力？將近 六十歲的他，仍舊充滿著旺盛的活力和赤子般的好奇心，而這一切又 以他深厚的功力做為基礎。 * * * 四月號的 Dr. Dobb's Journal 做了一篇高德納的專訪[5]。 為什麼 寫書寫到一半， 卻花了十年的時間在 Tex 上？   他說，  Niklaus Wirth （Pascal, Modular-2 和 Oberon 的設計者）一直想設計飛機， 但他發現他需要夠好的工具，於是他設計了一個個的電腦語言，造了 自己的電腦。高德納也希望他的書能夠不因科技的進步而被淘汰，希 望即使製書的科技進步，他的書仍舊是用領先的方式製作的。 談到另一位大師 Edsgar Dijkstra, 他說 Dijkstra 的力量來自於他 不妥協的拗脾氣。「光是想像用 C++ 寫程式就會讓他病倒！」Dijk- stra 的拿手技巧是鉅細靡遺地用 formal 方法推導、檢驗程式， 這 和工業界不斷產生數以 mega 計的軟體，  但使用者卻無時不負擔著 bug 的風險的實際情況顯然有段差距。高德納則認為自己位於兩種極 端的中間。一方面他贊同 formal 方法提供的可靠性，但他也知道在 大系統中這種方式的極限。他盡力維持他的軟體的品質，因此他願意 提供賞金給在 TeX 中找到新 bug 的人。 * * * 由於高德納已經不用 email 了，他有一個 Web page[6]，     http://www-cs-faculty.Stanford.EDU/~knuth/ 裡頭還有個 FAQ, 可以看到他中文名字的圖章。大家劈頭要問的當然 是：第四冊什麼時候出來呀？ 他說，TAOCP的第四冊將會分成三部份，4A : Enumeration and Back- tracking, 4B : Graph and Network Algorithms 和 4C : Optimiza- tion 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