Edsger Wybe Dijkstra

　　1 提出“goto有害論”;

　　2 提出信號量和PV原語;

　　3 解決了有趣的“哲學(xué)家聚餐”問題;

　　4 最短路徑算法(SPF)和銀行家算法的創(chuàng)造者;

　　5 第一個Algol 60編譯器的設(shè)計者和實現(xiàn)者;

　　6 THE操作系統(tǒng)的設(shè)計者和開發(fā)者;

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

　　在與癌癥進行了多年的斗爭之后，偉大的荷蘭計算機科學(xué)家Edsger Wybe Dijkstra已經(jīng)于2002年8月6日在荷蘭Nuenen自己的家中與世長辭！享年72歲。

　　他是計算機先驅(qū)之一，他開發(fā)了程序設(shè)計的框架結(jié)構(gòu)。 Edsger Wybe Dijkstra于1930年5月11日生于Rotterdam，，他的父親，Douwe Wybe Dijkstra是一位化學(xué)家，他的母親，Brechtje Cornelia Kruyper是一位數(shù)學(xué)家，這種充滿科學(xué)氣息的家庭背景對于他的職業(yè)生涯乃至他的整個人生都有著深刻的影響。Edsger Wybe Dijkstra在當(dāng)?shù)氐腉ymnasium Erasmianum讀高中，1948年，他考入了Leyden大學(xué)。他在聯(lián)合國從事法律方面的工作時卻在懷念在Erasmianum的日子，現(xiàn)在，他選擇了數(shù)學(xué)和物理。

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

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

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

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

　　Dijkstra被西方學(xué)術(shù)界稱為“結(jié)構(gòu)程序設(shè)計之父”和“先知先覺”（Oracle），他一生致力于把程序設(shè)計發(fā)展成一門科學(xué)�？茖W(xué)研究的帥才最重要的素質(zhì)是洞察力（Vision和Insight），能夠發(fā)現(xiàn)有前景的新領(lǐng)域或在新領(lǐng)域內(nèi)發(fā)現(xiàn)和解決最關(guān)鍵的問題。下面僅舉幾例說明Dijkstra的洞察力。

　　解決編譯系統(tǒng)中的關(guān)鍵問題

　　FORTRAN是最早得到一定程度推廣的高級語言，但FORTRAN的編譯系統(tǒng)并未科學(xué)地解決一些主要的難題。最早提出用堆棧（stack）來編譯復(fù)雜公式的是德國的Bauer和Samelson，他們的著名論文“順序公式的翻譯”（Sequential Formula Translation）是編譯方面的經(jīng)典論文。最近有些報道說Dijkstra是堆棧的發(fā)明人，這恐怕不符事實。Dijkstra發(fā)展了堆棧的概念，使之用于整個編譯，以及目標(biāo)代碼運行時的動態(tài)存儲分配，并在此基礎(chǔ)上和Jenson完成了世界上第一個ALGOL60編譯系統(tǒng)，采用了他首創(chuàng)的優(yōu)先數(shù)編譯算法。其中遞歸調(diào)用子程序時的環(huán)境維護是Dijkstra的重要貢獻，Display這一術(shù)語就是當(dāng)時他發(fā)明的，這是用來維護動態(tài)環(huán)境的一組寄存器（軟件），其結(jié)構(gòu)清晰并能適應(yīng)任何復(fù)雜情況。我于20世紀(jì)60年代初看完他的文章后馬上想到，假如計算機硬件中有對應(yīng)的設(shè)備將極大地提高軟件的運行效率。

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

　　同步進程的協(xié)調(diào)和操作系統(tǒng)的結(jié)構(gòu)

　　Dijkstra在1950～1952年期間曾當(dāng)過三年程序員，在從事硬件中斷處理程序的研制中，他發(fā)現(xiàn)一些程序錯誤在多個中斷同時出現(xiàn)的情況下無法再現(xiàn)，很容易被當(dāng)作硬件的瞬間故障，這一現(xiàn)象使Dijkstra毛骨悚然，促使他后來鉆研用科學(xué)方法從事軟件研制。操作系統(tǒng)是當(dāng)時最復(fù)雜的軟件，1965年Dijkstra在ACM通訊上發(fā)表了僅一頁長的短文“并行程序的控制”，這是他在操作系統(tǒng)領(lǐng)域的第一個重要貢獻。該文提出了并行程序互鎖問題的一個解決方案�！八梨i”（Deadly embrace）這一術(shù)語是Dijkstra發(fā)明的。1967年在首屆操作系統(tǒng)原理研討會上，Dijkstra介紹了他和幾個博士生研制的THE多道程序系統(tǒng)。THE系統(tǒng)的目的是驗證Dijkstra關(guān)于操作系統(tǒng)原理、結(jié)構(gòu)、同步進程通信機制等方面的一系列新想法。今天已經(jīng)普遍采用的系統(tǒng)的多層結(jié)構(gòu)、抽象、上層不需了解下層的詳細(xì)細(xì)節(jié)等科學(xué)原則就是當(dāng)時Dijkstra提出的，引起了強烈反響；同步進程通信的信號量Semaphore這一術(shù)語也是Dijkstra當(dāng)時創(chuàng)造的。

　　同步進程協(xié)調(diào)方面的程序錯誤是很難發(fā)現(xiàn)的，為此我曾吃過大苦頭。1979年我開始設(shè)計Ⅱ型照排系統(tǒng)，用了兩臺雙極型高速微處理器平行工作實現(xiàn)輪廓字形的復(fù)原和控制激光掃描，兩臺微處理器通過信號量彼此協(xié)調(diào)。設(shè)計和編程均無錯誤，但在把微程序翻譯成二進制代碼時錯了一位，結(jié)果造成了無法再現(xiàn)的隨機故障：激光打印機輸出的漢字有時拖尾巴。這一故障持續(xù)了一年多，引起用戶不滿，后由濰坊計算機公司的一位協(xié)作人員挖空心思地發(fā)現(xiàn)了錯誤的原因，即二進制碼錯誤，問題才得以解決。

　　上世紀(jì)六十年代操作系統(tǒng)的研制經(jīng)受了一系列重大挫折，典型的例子是OS 360。而Dijkstra為首的一批科學(xué)家的努力，使操作系統(tǒng)走上了健康發(fā)展的道路。

　　Go To語句有害和結(jié)構(gòu)程序設(shè)計

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

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

　　1． 紐約時報信息庫管理系統(tǒng)，含8.3萬行源代碼，只化了11人年，第一年使用過程中，只發(fā)生過一次使系統(tǒng)失效的軟件故障；

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

　　上個世紀(jì)六十年代末到七十年代初，上述這兩個系統(tǒng)可以算得上是大型軟件了。

　　結(jié)構(gòu)程序設(shè)計概念影響了后來的高級語言，也影響了一代程序員的風(fēng)格和習(xí)慣。

　　堅持真理，不惜反對恩師

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

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

　　Dijkstra的名言今天仍有現(xiàn)實意義

　　Dijkstra的主要貢獻是在上個世紀(jì)五十年代末到七十年代初，也就是他二十多歲到四十歲出頭這段時間完成的�；貞涍@些過去的成就是想強調(diào)：洞察力對一個科學(xué)家是何等的重要! Dijkstra獲圖靈獎以后，軟件領(lǐng)域又涌現(xiàn)出圖形用戶界面、面向?qū)ο蠹夹g(shù)等一系列新的里程碑，因特網(wǎng)更是帶來一個全新的時代。但是三十年前Dijkstra關(guān)于程序可靠性的一些名言至今仍有意義：

　　“有效的程序員不應(yīng)該浪費很多時間用于程序調(diào)試，他們應(yīng)該一開始就不要把故障引入�！�

　　“程序測試是表明存在故障的非常有效的方法，但對于證明沒有故障，調(diào)試是很無能為力的�！�

　　Dijkstra大力鼓吹程序正確性證明，但這一方法離實用還有相當(dāng)距離，因為一段源程序的正確性證明的文字往往比源代碼還要長，所以充分的軟件測試今天仍不可或缺。但是程序員的科學(xué)訓(xùn)練是十分重要的，有人曾做過一個試驗：一個題目由一批印度程序員編程，其結(jié)果驚人地相似；而由一批中國程序員來做，編出的程序五花八門。中國的軟件人員有時把創(chuàng)造性放在不恰當(dāng)?shù)牡胤健Ｖ挥幸?guī)范的科學(xué)的編程，一個大項目才能得到有效的管理，其質(zhì)量才有保證。