艾茲格·迪科斯徹

艾茲格·W·迪科斯徹(Edsger Wybe Dijkstra)

1 提出“goto有害論”;

2 提出信號量和PV原語;

3 解決了“哲學家聚餐”問題;

4 Dijkstra最短路徑演演算法和銀行家演演算法的創造者;

5 第一個Algol 60編譯器的設計者和實現者;

6 THE操作系統的設計者和開發者;

與D. E. Knuth並稱為我們這個時代最偉大的計算機科學家的人。

與癌症抗爭多年，於2002年8月6日在荷蘭Nuenen自己的家中去世，享年72歲。

他是計算機先驅之一，他開發了程序設計的框架結構。 Edsger Wybe Dijkstra於1930年5月11日生於Rotterdam，他的父親，Douwe Wybe Dijkstra是一位化學家，他的母親，Brechtje Cornelia Kruyper是一位數學家，這種充滿科學氣息的家庭背景對於他的職業生涯乃至他的整個人生都有著深刻的影響。Edsger Wybe Dijkstra在當地的Gymnasium Erasmianum讀高中，1948年，他考入了Leyden大學。他在聯合國從事法律方面的工作時卻在懷念在Erasmianum的日子。但之後，他選擇了數學和物理。

首次體驗程序設計

Edsger Wybe Dijkstra在三年之內取得了學士學位，這令他的父親非常高興，並在1951年9月同意他去英國參加一個夏季的課程，那是一個由劍橋大學開設的，學習電子計算裝置程序設計的課程，講師是著名的威爾克斯（Maurice Vincent Wilkes），Edsger Wybe Dijkstra的導師讓他給Amsterdamr數學中心計算部門的主管Aad van Wijngaarden寫一封信，以確定他的基礎知識是否足夠他去完成該學業。 Van Wijngaarden 1950年曾在劍橋學習過，他很快便回復了，信的內容有兩點，一是肯定Dijkstra現有的知識已經足夠了，二是請他來Amsterdamr作為一名程序設計人員為自己工作。對於Dijkstra來說，當時還是一名學生，而他在1951年夏季Wilkes所授的學業成為了他日後職業生涯的基礎。在數學中心的“自由階段”在沒有任何相關知識的情況下，Dijkstra的程序設計生涯開始於改寫突變程序和輸入Van Wijngaarden已經寫好的程序。Van Wijngaarden允許他這樣做，這些程序是為MC第一台計算機ARRA I開發的，由C.S. Scholten和J. Loopstra設計完成。 MC計算部門夜以繼日的工作，去解決有關那些在Netherland開發的大的方案中為數眾多的難題。例如關於Zeeland州安全問題的DELTA計劃。另外一個較大的工程是Fokker友誼飛機的開發，其機翼振動的計算結果需要MC盡最大的能量。 1953年Gerrit Blaauw加入了MC的隊伍。第一台ARRA II 構造完成，由於這台機器的可靠性，Fokker飛機公司又訂了一台類似的計算機，叫做FERTA。FERTA的速度是ARRA II 的兩倍，而且用一套不同類型的代碼。Dijkstra為這些機器都研製開發了軟體，也包括其後1956年的ARMAC，那也是為MC開發的最後一台計算機。在完成了FERTA之後，Gerrit Blaauw去往美國為IBM工作，在那裡，他從事IBM7030“Stretch”的開發工作，並最終設計和建造了IBM 360系統。新的挑戰：Electrologica 由於巨大、精於計算的機器的開發以走上正軌，Dijkstra, Scholten 和Loopstra又以完成了下一台計算機的準備工作，1956年，MCmanagement和人壽保險公司Nillmij決定成立一個獨立的公司：Electrologica，來經營商業電腦。

嶄新的計算機語言

1952至1956年間，程序設計經歷了一個演變的過程，這部分是由於系統分組的複雜性要求一個更具結構性的操作系統，部分是由於科學、數學上的關於程序設計的態度都提出了一個清楚的關於如何提高工作效率的觀點。Dijkstra的Shortest Path Algorithm是在這方面取得的突出進展，因為這種演變是全球性的，所以，在全世界的推動下，一個科學的計算機語言基礎：ALGOL，不久就誕生了。 1958年，Edsger Dijkstra代表Dutch MC出席了11月在Mainz召開的會議，那是一個定義ALGOL詳述的準備會議。1959年12月，Dijkstra給ALGOL60下了這樣的定義：“一個奇迹就被這樣簡單的創造了。”最後，1962年的4月，羅馬公約同意了其大部分的詳述，同年8月，IFIP，國際程序設計語言聯盟複查並批准了該報告。 1960年的1月，在ALGOL60被定義之後，數學中心首先在荷蘭開設了ALGOL60程序設計語言的課程，接著，1961年在英國的Brighton。這是MC一個新的開端：程序設計教育。

機會與欺騙

Eds1962年，Edsger Dijkstra在TH Eindhoven任全職教授，雖然在國外已經被認為是計算機科學的主席，但Dijkstra強烈反對這個稱呼，這主要是由於在專業科學知識上的缺乏。他的位置實際上是一個數學教授，他的學生接受了至少三年徹底的數學教育，經過這樣一個時期，他們都能作為信息學方面的專家了。那些數學訓練是以應用數學原理為基礎的。由此，信息學有了適合其學科本身的數學方法。 1967年，Dijkstra陷入了情緒上的危機，他第一個學生的論文被他在Eindhoven數學上的同事拒收了，而這些同事對於計算機科學一直是帶有偏見的。對於他和他的妻子來說，那段不景氣的日子是他們一生中最困難的時期。但是他很快又恢復了，並開始投入編寫：結構化編程筆記。而Dijkstra在Eindhoven的同事對此不是保持沉默，就是完全消極的反應，但Dijkstra選擇了正確的還擊方式：他給歐洲和美國的同事們複印了20多份稿件。1973年，Dijkstra成為了Burroughs的研究員，他減少了在Eindhoven TH的工作。這個決定使他能夠去寫科學報告，他為Burroughs寫了500多篇，還可以如願地出國旅行。他成了一個自由人，而且擁有該公司最小的實驗室：他的書房。

Austin:新紀元的起點

Dijkstra在旅行途中多次有機會參觀在Austin的得克薩斯州立大學，在那裡他還做過幾次講座。1984年，他有了一個擔任那裡計算機科學學院的全職教授的機會，他覺得他在那裡會感到像家一樣，於是他和他的妻子搬到美國居住。這便開始了他15年的教學生活：編寫、討論程序設計技術。除此以外，整個美國的好客給他和他的妻子都留下了深刻的印象。得克薩斯州立大學：超型計算機 1999年，Dijkstra在他69歲的時候，結束了作為教授的職業生涯。回顧47年的艱苦工作，為了一個更好、更簡單、更準確的編程方法而不停地努力奮鬥，使“符號、說明清楚”。Dijkstra認為最具價值的是他對學生的教導，而且能夠向人們展示這項工作可以做得比他們所知或所想象的更加出色。能夠做到吸引他人，已經成為了他最有收穫的活動。 “對於我來說，計算機科學上的第一個挑戰是如何把命令維持在有限個內，然而巨大的、分立的宇宙是複雜地纏繞著的。第二個也是同樣重要的挑戰是如何傳授解決那第一個問題的方法：只培養你個人的才智（那會隨你進入墳墓的東西）是不夠的，你必須教會其他人如何去發揮他們的才智。你越關注這兩個挑戰，你越會清楚的看到它們只不過是同一枚硬幣的兩個面：自學是去發現什麼東西是可以被教會的。” （"My hopes to Computer Science") Edsger Wybe Dijkstra因患癌症於2002年8月6日在Nuenen, The Netherlands逝世。

結構程序設計之父

Dijkstra被西方學術界稱為“結構程序設計之父”和“先知先覺”（Oracle），他一生致力於把程序設計發展成一門科學。科學研究的帥才最重要的素質是洞察力（Vision和Insight），能夠發現有前景的新領域或在新領域內發現和解決最關鍵的問題。下面僅舉幾例說明Dijkstra的洞察力。

解決編譯系統中的關鍵問題

FORTRAN是最早得到一定程度推廣的高級語言，但FORTRAN的編譯系統並未科學地解決一些主要的難題。最早提出用堆棧（stack）來編譯複雜公式的是德國的Bauer和Samelson，他們的著名論文“順序公式的翻譯”（Sequential Formula Translation）是編譯方面的經典論文。曾有報道說Dijkstra是堆棧的發明人，這恐怕不符事實。Dijkstra發展了堆棧的概念，使之用於整個編譯，以及目標代碼運行時的動態存儲分配，並在此基礎上和Jenson完成了世界上第一個ALGOL60編譯系統，採用了他首創的優先數編譯演演算法。其中遞歸調用子程序時的環境維護是Dijkstra的重要貢獻，Display這一術語就是當時他發明的，這是用來維護動態環境的一組寄存器（軟體），其結構清晰並能適應任何複雜情況。我於20世紀60年代初看完他的文章后馬上想到，假如計算機硬體中有對應的設備將極大地提高軟體的運行效率。

Dijkstra是ALGOL 60報告的主要起草者之一，1972年Dijkstra在他獲得ACM圖靈獎的講演中，仍對這一報告給予高度評價：“只有極少極少幾個像ALGOL60報告這樣短的文件能給計算機界帶來如此深遠的影響。”

同步進程的協調和操作系統的結構

Dijkstra在1950～1952年期間曾當過三年程序員，在從事硬體中斷處理程序的研製中，他發現一些程序錯誤在多個中斷同時出現的情況下無法再現，很容易被當作硬體的瞬間故障，這一現象使Dijkstra毛骨悚然，促使他後來鑽研用科學方法從事軟體研製。操作系統是當時最複雜的軟體，1965年Dijkstra在ACM通訊上發表了僅一頁長的短文“并行程序的控制”，這是他在操作系統領域的第一個重要貢獻。該文提出了并行程序互鎖問題的一個解決方案。“死鎖”（Deadly embrace）這一術語是Dijkstra發明的。1967年在首屆操作系統原理研討會上，Dijkstra介紹了他和幾個博士生研製的THE多道程序系統。THE系統的目的是驗證Dijkstra關於操作系統原理、結構、同步進程通信機制等方面的一系列新想法。今天已經普遍採用的系統的多層結構、抽象、上層不需了解下層的詳細細節等科學原則就是當時Dijkstra提出的，引起了強烈反響；同步進程通信的信號量Semaphore這一術語也是Dijkstra當時創造的。

上世紀六十年代操作系統的研製經受了一系列重大挫折，典型的例子是OS 360。而Dijkstra為首的一批科學家的努力，使操作系統走上了健康發展的道路。

Go To語句有害和結構程序設計

結構程序設計被稱為軟體發展中的第三個里程碑（第一、二個里程碑是子程序和高級語言）。早在1965年召開的IFIP會議上，Dijkstra就提出“Go To語句可以從高級語言中取消”，“一個程序的質量與程序中所含的Go To語句的數量成反比”。但是，Dijkstra講話的影響很小，當時人們正忙於IBM 360系列的使用；而IBM 360的主要語言之一是FORTRAN，Go To語句則是FORTRAN的支柱。

1968年Dijkstra給ACM通訊寫了一篇短文，該文後改成信件形式刊登，以便早日發表，這就是具有歷史意義的、著名的“Go To Letter”。Dijkstra在信中建議：“Go To語句太容易把程序弄亂，應從一切高級語言中去掉；只用三種基本控制結構就可以寫各種程序，而這樣的程序可以由上而下閱讀而不會返回”。這封信引起了激烈的討論。人們逐漸認識到：不是一個簡單地去掉Go To的問題，而是促進一種新的程序設計觀念、方法和風格，以期顯著提高軟體生產率和降低軟體維護代價。當時採用結構程序設計方法的兩個最著名項目是：

1． 紐約時報信息庫管理系統，含8.3萬行源代碼，只花了1年，第一年使用過程中，只發生過一次使系統失效的軟體故障；

2． 美國宇航局空間實驗室操作的模擬系統，含40萬行源代碼，只用兩年時間就全部完成。

上個世紀六十年代末到七十年代初，上述這兩個系統可以算得上是大型軟體了。

結構程序設計概念影響了後來的高級語言，也影響了一代程序員的風格和習慣。

堅持真理，不惜反對恩師

ALGOL 68語言是Van Wijingaarden為主設計的，得到了IFIP下屬的工作小組的多數票通過。Wirth、Dijkstra和Hoare等工作小組成員發表了“少數派報告”，強烈反對這一語言及其表達方式。ALGOL 68的表達方式獨特而嚴格，但不易理解，是Wijingaarden的發明。事實證明，少數派是正確的，ALGOL 68很快就夭折了。

要知道，Wijingaarden是Dijkstra的恩師。上世紀五十年代初Dijkstra在阿姆斯特丹數學中心編程序時Wijingaarden是他的領導。Dijkstra當時正在攻讀理論物理學位，他發現理論物理課程和程序設計在精力上越來越衝突，他又拿不定主意，到底成為一個理論物理學家還是選擇程序設計作為自己的職業，而他當時又擔心程序設計能否成為被尊敬的學科。充滿不安心情的Dijkstra於1952年春的一個早晨敲開了Wijingaarden辦公室的門。幾個小時的談話，使Dijkstra變了另外一個人，因為Wijingaarden向他指明了程序設計這門學科正處在起步階段，因而有重大的機會，Dijkstra可以努力使程序設計變成一個受人尊敬的學科。Dijkstra把這次談話稱為他一生中的轉折點，於是決定儘快結束理論物理研究，全身心地投入程序設計。Dijkstra說，為此他應該終生感謝Wijingaarden。但是Dijkstra還是強烈地反對其恩師的得意之作ALGOL 68，少數派報告雖被IFIP壓制，但真理終究得到了證明，後來的成功語言都是背離ALGOL 68方向的。

Dijkstra的名言今天仍有現實意義

Dijkstra的主要貢獻是在上個世紀五十年代末到七十年代初，也就是他二十多歲到四十歲出頭這段時間完成的。回憶這些過去的成就是想強調：洞察力對一個科學家是何等的重要! Dijkstra獲圖靈獎以後，軟體領域又湧現出圖形用戶界面、面向對象技術等一系列新的里程碑，網際網路更是帶來一個全新的時代。但是三十年前Dijkstra關於程序可靠性的一些名言至今仍有意義：

“有效的程序員不應該浪費很多時間用於程序調試，他們應該一開始就不要把故障引入。”

“程序測試是表明存在故障的非常有效的方法，但對於證明沒有故障，調試是很無能為力的。”

Dijkstra大力提倡程序正確性證明，但這一方法離實用還有相當距離，因為一段源程序的正確性證明的文字往往比源代碼還要長，所以充分的軟體測試今天仍不可或缺。但是程序員的科學訓練是十分重要的，有人曾做過一個試驗：一個題目由一批印度程序員編程，其結果驚人地相似；而由一批中國程序員來做，編出的程序五花八門。中國的軟體人員有時把創造性放在不恰當的地方。只有規範的科學的編程，一個大項目才能得到有效的管理，其質量才有保證。