自傳節選
Donald Knuth自傳的開頭這樣寫道:“Donald Knuth真的只是一個人么?”作為世界頂級計算機科學家之一,Knuth教授已經完成了編譯程式、屬性文法和運算法則的前沿研究,並編著完成了已在程式設計領域中具有權威標準和參考價值的書目的前三卷。在完成該項工作之餘,Knuth還用了十年時間發明了兩個數字排版系統,並編寫了六本著作對其做了詳盡的解釋說明,現在,這兩個系統已經被廣泛地運用於全世界的數學刊物的排版中。隨後,Knuth又發明了檔案程式設計的兩種語言,以及“文章性程式語言”相關的方法論。
到目前為止,Knuth已經出版發行了17部書籍,一百五十餘篇論文,包括了巴比倫算法、聖經、字母“s”的歷史等多方面的內容。作為一名數學家, Knuth曾開創了幾門新的課程,為純計算數學做出了很大貢獻。他所獲得的獎項和榮譽數不勝數,其中最值得注目的有1974年美國計算機協會圖靈獎 (ACM Turing Award),1979年美國前總統卡特授予的科學金獎(Medal of Science)以及1996年11月由於發明先進技術榮獲的極受尊重的京都獎(Kyoto Prize)。在不多的業餘時間裡,Knuth不僅寫小說,還是一個音樂家、作曲家、管風琴設計師。
是Knuth獨特的審美感決定了他興趣廣泛、富有多方面造詣的特點,Knuth傳奇般的生產力也是源於這一點。對於Knuth來說,衡量一個電腦程式是否完整的標準不僅僅在於它是否能夠運行,他認為一個電腦程式應該是雅致的、甚至可以說是美的。電腦程式設計應該是一門藝術,一個算法應該像一段音樂,而一個好的程式應該如一部文學作品一般。
早期經歷
Knuth,1938年1月10日生於美國威斯康星州密爾沃基市。他在模式方面辨別和熟練操作的能力在八年級的時候開始顯現出來。當時,當地的一家糖果製造商舉辦了一項比賽,比賽要求選手用其品牌“Ziegler's Giant Bar”中的字母組成新的單詞,規定時間內組成單詞數量最多者獲勝。Knuth參加了比賽,並以單詞總數4500餘個遠遠超過了裁判的2500個的標準,輕鬆贏得頭獎。賽後,Knuth說道,如果自己當初想到回答時用些省略符號的話,還能寫出更多。這次比賽Knuth為學校贏得了一台電視機,還為每個同學贏得了一根糖果棒。
Knuth多產的出版事業開始於他的高中時代,當時他的科技設計被Westinghouse Science Talent Search 光榮提及。他的“Potzebie System of Weights and Measures ”的基礎章節被登在“Mad”雜誌第26號,“Power”的基礎章節被叫作“whatmeworry”。“Mad”的編輯認識到了年輕的Donald著作的重要性,以25美元買下了他的文章,並刊登在了其1957年6月的期刊上。
高中的時候,Knuth對數學並沒多大興趣,而是把主要精力放在主修的課程:聽音樂和作曲上。他在高中的樂隊里吹薩克斯、大號時,曾把Dragnet、 Howdy Doody Time 和 Brylcream的主題曲聯成一段新的音樂。這位著名的科學家在近期評論自己的早期作品時承認:“對於著作權,我一無所知。”
雖然Knuth的GPA是學校歷史上最高的,但是他和他的指導老師還是對他能否成功學習大學數學持懷疑態度。Knuth說在他高中階段和大學早期一直有一種自卑感,這個問題一度是他的一個障礙。作為一個大學新生,Knuth沒有對於失敗的恐懼,他花了許多時間攻克額外的數學難題,幾個月後,他在這方面的能力已經遠遠超過了其他同學。
高等教育和早期的計算機工作
當Knuth在Case科學院(現在的Case Western Reserve)獲得物理獎學金時,夢想成為一個音樂家的計畫改變了。Knuth回去繼續研究數學是在大二,當時一個愛出難題的教授提出了一個特殊的問題,並說哪個學生能解決這個問題就立刻記成績“A”。Knuth跟大多數同學一樣,也認為那是道解不出來的題目,直到有一天,他錯過了公共汽車,只能步行去看一個演出,Knuth利用路上這點空閒時間決定嘗試一下。那陣子他運氣真的是非常好,不僅問題很快就解開了,得到了“A”,還成功地經常逃課。雖然 Knuth也承認,逃課讓他有負罪感,但是很明顯,他完全有能力補上落下的功課,接下來的一學年,他的離散數學就又得了個“A”,而且還獲得了給自己不能參加的課程評定論文等級的工作機會。
1956年,作為Case的新生,Knuth第一次接觸到了計算機,那是一台IBM 650。Knuth說直到一年後,女孩才進入了他的生活。這又是計算機科學界一直以來虧欠科學家們的一個事例之一。
Knuth熬夜讀IBM 650的說明手冊,自學基本的程式設計。那時,在高等計算機語言發明之前,程式編寫只能用第二代或是彙編語言。這個工作既耗時又困難,因為指令必須根據每台機器特定的構造編寫,而實際上指令只須一步就可從二進制0、1系列轉存到計算機硬碟上。Knuth說,有了第一次使用650的經歷,他便肯定自己能編寫出比說明手冊上介紹的更好的程式。
Knuth很快便開始“閒逛”,編寫可以執行數學函式的程式。他的第一個程式是把數字轉化為素數,第三個是做井字遊戲(或者說是讓計算機在改正每次輸的錯誤的過程來學會玩井字遊戲)。作為學校籃球隊的經理,Knuth編寫了一個根據不同成績標準評定每個運動員對球隊貢獻等級的程式,他的努力贏來了那些認為這樣做有助於球隊贏得同盟冠軍的教練的好評(雖然,無庸質疑,不是每一個運動員都這樣認為)。Knuth的成就成了新聞周刊的標誌,他和教練、計算機的照片也被刊登在IBM650後來的說明手冊上。
1960年,Knuth從Case畢業時享有著最高榮譽,在由全體教員參加的選舉上,他因其公認的出眾成就獲得了碩士學位。1963年,Knuth回到加利福尼亞理工學院攻取了數學博士學位,之後成為了該院的數學教授。在加利福尼亞理工學院任教期間,Knuth作為Burroughs 公司的顧問繼續從事軟體開發工作。1968年,他加入了史丹福大學,九年後坐上了該校計算機科學學科的第一把交椅。1993年,Knuth成為史丹福大學 “the Art of Computer Programming”(電腦程式設計藝術)的榮譽退休教授。
早期成就和電腦程式設計藝術的開端
1962年,Knuth還是個研究生的時候就開始了他電腦程式的工作。那時,他已經開始了個人諮詢,為不同的機器編寫編譯程式。編譯程式是一種翻譯原始或高級語言和對象或二進制機器語言的中間語言。在不知道眾多軟體公司正高額尋求成百上千的編輯者的情況下,Knuth編寫了一個程式,賺得5000美元,他的名字立刻響譽了整個行業。世界上一流的出版社Addison-Wesley找到Knuth,請他寫一本關於編譯程式的書。到1966年,Knuth已經發表了3000頁的手寫設計草圖,並且發明了一種綜合方法,用於分析或決定結構翻譯所客觀需要的文法規則。最近,關於他的那第一部著作,Knuth自己這樣評述:“用三年半的時間寫第一章可並不是件好事。”
當Knuth的出版商計算出他的那3000頁的筆跡列印成文章大約需要2000頁時,大家才發現這實際上是一項多么大的工程。Knuth決定將它詳述,成為一部更大的關於程式設計科學的縱覽,共分為七個部分。一部巨著就這樣——誕生了。《電腦程式設計藝術》,至今仍是各程式類圖書書架上標誌性的書籍。微軟執行長比爾.蓋茨在1995年接受一次採訪時說,“如果你認為你是一名真正優秀的程式設計師,就去讀第一卷,確定可以解決其中所有的問題。”值得注意的是,蓋茨本人讀這本書時用去了幾個月的時間,並同時進行了難以置信的訓練。蓋茨還說:“如果你能讀懂整套書的話,請給我發一份你的簡歷。”
依Knuth本人所講,《電腦程式設計藝術》是他畢生最重要的事業,其目的是“組織和總結所知道的計算機方法的相關知識,並打下堅實的數學、歷史基礎”。Knuth撰寫的前三卷被翻譯成多種語言,到1976年為止,已賣出超過一百萬冊。他目前正全神貫注地編寫第四卷,他期望第四卷的篇幅約為2000 頁,並分為三個獨立的章節。為了完成叢書的其餘部分,Knuth現在進入了一種引退的狀態,全身心地投入這項工作。Knuth說,一般說來,他更喜歡在一段時間內集中精神完成一項工作,正像他自己在書中提出的:按“一批”的模式。
Knuth從他主要的工作計畫中拿出了十年,即從1976年起,致力於對數字排版的研究,設計了著名的檔案準備TeX系統,字型生成程式METAFONT。這項工作帶來的值得注意的副產品是用於結構檔案和“文章性程式語言”附隨方法論的WEB和CWEB語言。
現在,Knuth和他的妻子Jill,兩個孩子John 和Jennifer一起,住在史丹福大學校園裡。他繼續著《電腦程式設計藝術》第四卷的編寫工作。雖然說Knuth是全身心的投入這一項工作,但他還是能擠出時間研究MMIX的設計,那是一台64位RISC(精簡指令集計算機)。而他的業餘愛好仍然是音樂,還一直邀請那些能夠即興演奏四手聯彈鋼琴曲的人們給他留下便條,以便安排一些活動。
成就簡要回顧
編譯程式
編譯程式能夠實現高級語言和二進制機器語言之間的翻譯。二十世紀六十年代初期,Knuth教授致力於這方面的研究,雖然現代的軟體已經可以使其變的簡單一些,但編寫編譯程式仍被認為是一項極為困難的工作。Knuth教授在這方面最著名的成就是LR(k)分析的研究,那是一個能使確定一串字元文法規則的過程更加順暢的值得注目的方法。
屬性文法
在編譯程式的工作之後,Knuth教授走上了形式上定義程式語言意義、語義的研究道路。他建立起一個更加經濟的方法去通譯聯合規則,他把這種方法稱作“屬性規則”。該方法創立的同時,計算機科學的子域被稱作“屬性文法”。
算法
也許Knuth教授在計算機科學領域最原創的貢獻就是他對於算法的分析。算法是編寫一個程式,使之能去完成一項任務的基礎,例如搜尋或分類等。在加利福尼亞理工學院時,Knuth教授在一個畢業生的協作下,開發了用來探究數學公理推論的Knuth-Bendix算法。1968年,Knuth教授在斯坦福,和他的一個學生開發了Knuth-Morris-Pratt算法,該法則使計算機在文章中搜尋一串字元的過程更加連貫。他所著的《電腦程式設計藝術》是一個詳盡的算法實踐和科學的概觀。
數位化排版
“數學書籍和雜誌已經不像從前那樣漂亮了。”Knuth教授在一篇早期關於數學排版的文章中這樣寫道。由於對計算機排版的校樣的低質量感到無法忍受, Knuth教授從他史詩性的七卷集巨著的編寫過程中拿出了十年時間,來開發一個高質量的計算機排版系統。其間,Knuth開發了兩個用於檔案排版和字型生成的軟體系統,這兩個系統現在已被世界大多數出版社運用。它們分別是TeX,用於出版業的科學排版,和“優美文章”的產品;METAFONT,一個字型生成程式。
結構化檔案和文章性程式語言
Knuth教授的排版研究,引領他發明了檔案構造的兩種語言和一個方法論,叫作“文章性程式語言”。語言分別是WEB和CWEB,它們促進了程式編寫向 “文學作品,是用來閱讀的”這個方向發展。這兩種語言的結合,一種是檔案格式化,另一種是程式設計,這就使程式設計師能夠同時創建兩個不同的系統程式,一個面向人,另一個面向機器。當一條過程清楚地描述程式並促進其維護時,另外一個則產生一個機器可執行的程式。這些工作就是Knuth教授在實現其使程式設計為讀者易懂、甚至感覺漂亮的目標的過程中,在計算機領域裡所做出的巨大貢獻。