TAOCP作者的高德納--------有神有關的故事

密爾沃基市，是美國 威斯康辛州最大的城市。1938年1月10日，聖誕剛過不久，密爾沃基市民像往常一樣平靜地生活着。咖啡店裡，有人在議論着 羅斯 福總統的救市新政策，有人在議論着到底該不該限制公民持槍。而更多的人呢，則一邊品嘗着密爾沃基聞名全國的啤酒，一邊聽着廣播裡面的實時戰況：侵華日軍登 陸 青島了。誰也沒有想到，這個平靜的日子将載入這座城市的史冊。這天，密爾沃基 路德教會高中的一名印刷 管理者，高興地迎來了一個健康的兒子。他為兒子取了 一個響亮的名字，這個名字在不久的将來，成為了計算機程式設計藝術的旗幟：Donald Ervin Knuth。 為了友善講述，請各位讀者允許我先劇透一件39年後的事兒。在1977年Knuth造訪 中國前夕，姚期智的夫人為他取了一個中文名字： 高德納。在下面的故事裡，我們就使用這個名字來稱呼他。 高德納天資聰穎，他的超凡智力在8歲時就顯示出來了。當時，一家糖果商在孩子們當中舉辦了一項有趣的比賽，要求用“Ziegler’s Giant Bar”裡面的字母，寫出盡可能多的單詞。裁判事先準備了一份2500個單詞的清單，可他卻遠遠低估了小選手的能力，高德納令人驚訝寫出了4500多個單 詞，毫無疑問地獲得了冠軍。他為學校赢得了一台電視機，還為每個同學赢得了一隻棒棒糖，他的賽後感言是，我還能寫出更多。 高德納的高中就讀于他父親所在的路德教會高中，在這期間，他發表了此生第一篇 學術文章。盡管如此，但這個充滿了才華和個性的年輕小夥，并沒有把心思 放在科學上，他的主業是音樂和作曲。他的老師，甚至包括他自己，十分懷疑他将來進入大學後，是否能夠順利學習數學。這種想法給高德納造成了不小的自卑，盡 管他的平均分是學校曆史上最高的。不過有句話說，真正的天才是1%的靈感加上99%的汗水，這話用在高德納身上毫不誇張，18歲的他，在進入大學之後，絲 毫沒有向數學屈服，而是花費無數的課餘時間，大量練習數學難題，這種努力的勁頭再加上他的天份，使他很快就在數學方面超過了其他同學。其實我們與其關注一 些科學家們不可模仿的機會和天賦，莫不如更關注他們如何面對困難和挫折。高德納告訴我們，沒有什麼過不去的坎兒，方法就是抓緊時間幹活。 高德納就讀的大學是 凱斯理工學院，在這裡他接觸了IBM650計算機，這導緻高德納的 音樂家夢想一去不複返，科學天賦終于重新占領了他的心扉。 1956年，在他第一次使用IBM650之後，他就躇躊滿志地相信，說明書上介紹的程式，一定比不上他自己編寫的。于是高德納開始學習程式設計，他的第一個程 序是因數分解，不久之後，高德納就對程式設計有了許多體會。當時高德納還兼職管理學校的籃球隊，于是他編寫了一個程式，能夠自動評估每名球員的價值，令球隊的 教練非常欣賞。這件事還吸引了CBS電視台的報道，後來高德納、球隊教練和IBM650的一張合影，還被印到了IBM650的宣傳冊上。1960年，高德 納以公認出色的成就，打破了學校的慣例，同時獲得了學士和碩士兩個學位，大家來做個減法吧，算算高德納此時年歲幾何。 随後，高德納從五大湖區，來到了美國西南岸，進入 伯克利攻讀數學博士學位。在此期間，他的程式設計生涯也正式開始了，他對外提供軟體服務，為各種不同機 器設計各種稀奇古怪的編譯器，曾經一個程式賣到5000美元。最值得一提的，就是他對ALGOL60編譯器提出的測試方法。不知道大家是否還記得 ALGOL，這盞批量生産 圖靈獎的阿拉丁神燈。當時我們介紹過，ALGOL60的設計目标要求支援遞歸，而在設計編譯器時，對遞歸的處理是很複雜的，是以 經常會因為編譯器不成熟而出故障。高德納編寫了一段非常簡單的測試程式，江湖人稱“Man or boy test”，俗名“是男人就得-67”。高德納說，隻要用ALGOL60編譯器來編譯我的這段程式，如果運作結果等于-67，就說明這個編譯器是純爺們 兒，否則就隻能算小男孩。 1963年，25歲的高德納順利拿到了博士學位，并留在伯克利任教。在畢業前一年，雖然還是研究所學生，但高德納已經因為設計編譯器而響譽計算機行業。 于是著名的Addison-Wesley出版社與他約稿，請他寫一本關于編譯器和程式設計方面的書。這本來是很平常的一件事，但您看看高德納是何許人也， 不久之後，他簡直把這件事做成了一件計算機科學史上的奇觀。1962年約的稿，高德納一直寫到1966年還沒交，在此期間他又是畢業，又是教書，終于人家 出版社急了。編輯找到高德納，說這都四年了你寫了多少啊，高德納說，才寫3000頁手稿。編輯大囧，忙問都3000頁了你怎麼還不交，高德納答曰，急啥， 我還沒寫到正題呢。編輯徹底雷住了，說那你出個多卷本吧…… 《計算機程式設計藝術》，就這麼誕生了。 把一件平常的事做到人間極緻，這就是高德納。他不是故弄玄虛，他的心裡攢着一股勁兒，要寫出一部與 牛頓的《自然哲學的數學原理》相媲美的傳世巨著。 他一開始計劃了六卷，後來覺得這個數字不怎麼好，又改成了七卷。1968年，《計算機程式設計藝術》（The Art Of Computer Programming，江湖人稱TAOCP）的第一卷正式出版了。這一卷的标題叫《基本算法》，但難度卻并不低。比爾 蓋茨曾經花了幾個月的時間讀完這一 卷，并且做了大量的練習，然後他說，如果你想成為一個優秀的程式員，那就去讀這個《基本算法》吧，確定自己能夠解決裡面的每一個問題。然而，高德納本人的 說法卻比蓋茨犀利多了：要是看不懂，就别當程式員。 就在這同一年，高德納跳槽到斯坦福大學，并當上了教授，一邊帶博士，一邊繼續寫書。一年後，TAOCP第二卷《半數值算法》正式出版，又過了三年， 也就是1973年，第三卷《排序與查找》也相繼付梓。這三卷書立即被計算機界驚為神作，在那幾年之内就賣出去了100多萬套，至今仍然是程式設計書籍中的最高 經典。有一些對我們來說巧妙得不能再巧妙的算法，在這三卷書中順手掂來，比比皆是，這個我們等會再說，現在有件要緊的事兒。按照高德納的計劃，這套書一共 是七卷，但是現在剛剛寫完三卷，就已是震古爍今。震到什麼程度呢，連圖靈獎頒獎委員都坐不住了，他們做了一件前所未有的事。按照慣例，圖靈獎的獲獎者都是 成就等身，要經過時代的檢驗，然而高德納卻是例外，在他的七卷本剛剛寫完三卷時，ACM便決定立即為其頒發圖靈獎： 授予高德納圖靈獎，以表彰其在算法分析、 程式設計語言的設計和程式設計領域的傑出貢獻，特别是其著名的《The Art of Computer Programming》系列叢書。 這是1974年的ACM圖靈獎 頒獎詞，高德納捧走了曆史上第9個圖靈碗。這對高德納來說，無疑是個殊榮，因為這一年他隻有36歲，直到現在，他仍然保持着獲獎年齡最小的紀錄。 我們故事才講到一半，可天才的高德納卻已經得到了圖靈獎。各位讀者可能要問，那下面還講啥，他無非就是接着寫書，接着帶博士，就别廢話啦。您要是這 麼想，那就大錯特錯了，他要是那麼做，他就不是高德納。提前劇透一下，這個看上去順理成章的計劃，很快就被打破了，計劃中的七卷本，直到今天都沒有完成。 高德納計劃要寫一套七卷本的《計算機程式設計藝術》，沒想到剛剛寫完第三卷，就被ACM授予了圖靈獎。這在圖靈獎曆史上是從沒有過的事。我們還記得 巴黎會議上的 諾爾吧，他的圖靈碗比他的獲獎成果遲來了整整45年，他等這個碗時間，比高德納獲獎時的歲數還要長。但是，高德納在獲此殊榮之後，再一次令世界大跌眼鏡：他宣布從此歇筆了，因為 排版工具太差，破壞了這套書的美。 高德納的這一動作讓外界十分震驚，可以想見，他遭到了排山倒海的懷疑。有人說，高德納肯定是江郎才盡，拿了圖靈碗，見好就收；有人說，圖靈獎對前三卷的評價過高了，高德納無力面對這麼大的壓力，隻好找個理由撤退；還有人說，獲獎之後停止寫作，充分展現了他寫書的目的就是為了功利。他們紛紛質疑，這個圖靈碗是徹底發錯了人。 然而，如果我們真正翻開TAOCP讀一讀，就不難了解這是為什麼。我覺得，對于算法的研究，可以分成三層境界。第一層是分析算法的複雜度，這是計算機專業的大學生普遍掌握的技能，達到這個境界，可以說是入了算法的門；第二層境界是改進算法的複雜度，在分析之後繼續思考，想辦法去降低它，這就可以算是懂算法了；第三層境界，就是尋找算法的最優複雜度，不但要改進它，而且要改到什麼程度呢？就是要證明出來，我改完的算法就是最優的，你無論如何都不可能再改進了，再改進就違反宇宙規律。 高德納，就是典型的第三種人。諸位不妨看看，TAOCP裡面給出了多少最優算法，高德納是鐵了心，要當算法世界中的上帝。高德納就是這麼一個極緻地追求極緻的人，他強迫自己把每件事都做得不可逾越。那麼他怎麼能夠容忍，這套被他視為畢生事業的書，被糟糕的排版技術束縛？于是，無論别人怎樣質疑，他最終還是把寫作晾到了一邊，開始全力以赴地研究 字型和排版。高德納讓我們領略了什麼才是真正的個性，個性絕不是打18個耳洞，或在牛仔褲上摳 36個窟窿。個性，就是在所有岔路口都追随自己的心，讓所有影響你追求夢想的障礙統統跪倒。 高德納這一歇筆，就是十年。在這不務正業的十年當中，對極緻的追求像隻看不見的手，推動他創造了三個響亮的成果，其中影響最大的，就是排版系統TEX。如果大家用MS Office Word寫過論文，就會體會到那份求死不得的心：不斷地調整 字号、行距、縮進、分欄，如果這還不算什麼，你再寫幾個數學式子看看？但是在TEX中，這些麻煩幾乎完全不存在，你唯一需要做的，就是把你想寫的内容告訴它。如果說時間就是生命，那就可以認為，TEX每天都在拯求科學家們的生命，說它推動了科學的發展也不為過。TEX是一場出版界的革命，直到現在仍是全球學術排版的不二規範，它所排出的文字之美，特别是數學式子的美，讓人們由衷感歎：啊，一毫米都不能再挪動了。 除了功能上的美之外，TEX作為一個軟體産品，也令人歎為觀止。它的版本号不是自然數列，也不是年份，而是從3開始，不斷地逼近圓周率（3.14，3.141…目前最新版本是 3.1415926）。高德納再一次用行動宣告，我這個東西，不可能再有什麼大的改進了，最多隻能小修小補，使其趨近完美。他還專門設立了獎金：誰發現TEX的一個錯誤，就付他2.56美元，第二個錯誤5.12美元，第三個10.24美元…以此類推。我們都知道，傳說某個國王就因為這種指數遊戲失去了江山，高德納作為算法大師，更清楚指數增長的可怕性。然而他卻敢立此重賞，結果直到今天，他也沒有為此付出多少錢，可見TEX經過了怎樣的千錘百煉。這個耗費十年打造的玩具，讓當初質疑圖靈獎發錯了的人們全部閉嘴了，他們甚至改口說：哦，為了這個TEX，不妨再給高德納一個圖靈碗吧。 第二個成果，就是METAFONT，這是一套用來設計字型的系統。對于它的價值，一句話就能概括：計算機界最懂字型的兩個人，一個是蘋果的 喬布斯，另一個就是高德納。 第三個成果，就是文學化程式設計（Literate Programming），它把程式設計的藝術性展示得淋漓盡緻。高德納說，一段好的程式，不僅僅是要清晰易讀，而且要能夠讀出美感，讀出意境。天呐，意境，一排一排的計算機代碼，要像詩歌一樣充滿意境。高教授，你瘋了？ 高德納說，你才瘋了呢，看我給你們露一手。于是，他在C語言的基礎上，開發了一套CWEB系統，除了用它寫出了TEX程式之外，竟然還用它寫了一本叫作《Stanford Graphbase》的書。高德納微微一笑，我都能用程式設計語言寫書，何況有意境的程式了，我的口号是：程式員也能得普利策獎（這是全球新聞寫作領域的最高獎項）。 文學化程式設計還為高德納報了一個小仇。我們第6章中講過的迪科斯徹，當年提出了一個“結構化程式設計”，提倡不要在程式設計時使用 “goto”語句，高德納偏要唱反調，結果被迪科斯徹稱為“沒結構”。這下可好，高德納狡黠一笑，嘿嘿，如果你不跟我混，你就是“沒文化”咯（literate也有“文化”之意）。 歇筆十年的高德納，手捧這三項成果重出江湖，打消了一切質疑。這時他才對十年前的歇筆事件做了一個輕描淡寫的解釋：一個人要想把事情做得漂亮，就必須要跟上帝保持和諧，現在，上帝終于讓我去寫四卷了。 他的筆，又拿了起來。在寫作第四卷的過程中，為了幫助讀者打好數學基礎，以便面對TAOCP中的數學高峰，他又專門撰寫了一本《Concrete Mathematics》。這本書有中文版，翻譯為《具體數學》，我一直覺得稍有不妥。Concrete到底是什麼意思呢，高德納說，意思就是我不教那些軟綿綿的數學，我要教的是扔到地上能砸個響兒的數學。據說，他在課堂上說完這番話，有好幾個同學扭頭走出了教室——他們是土木工程系的學生，還以為高德納是講混凝土的呢（Concrete在土木領域意為“混凝土”）。說到高德納的教學，還有個趣聞，他批改作業的時候隻抽查第314頁，就能判斷出這份作業的品質。為此，我們這本書的第314頁用來向高德納緻敬。 1992年，高德納為了專心寫作，宣布提前退休，并停用電子郵箱。高德納一共帶了28位博士生，他覺得28這個數字很好，于是便宣布不再收學生了。盡管如此，他仍然為想要師從于他的人們留下了一個盼頭：他開了一門叫做Computer Musing的公開課，每次會提出一個問題，如果誰能快速解出來，高德納就會為他的 博士論文簽名。不知道哪位後起之秀能夠獲得如此殊榮呢，我們拭目以待吧。 2008年，在TAOCP的前三卷面市30年之後，第四卷終于千呼萬喚始出來，而高德納，卻已是白發蒼蒼的古稀老人了。一句話，一輩子，一生情，一杯酒，他對計算機科學的熱愛，使他為這套叢書耗費了一生的心血。在這一章的最後，我想用一個詞，來形容這位天才的計算機科學大師，但是思前想後，我隻能想到唯一的一個詞：God。 我想，盡管高德納是一位虔誠的基督徒（他還專門寫過關于聖經研究的書），但他一定會欣然接受這樣的形容。正如當年Linux的作者Linus說：上帝在夢中告訴我，我做出了最優秀的 作業系統。 高德納回答說：我可沒這麼說過。