Edsger Wybe Dijkstra

　　1 提出“goto有害論”;

　　2 提出信號(hào)量和PV原語;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　堅(jiān)持真理，不惜反對(duì)恩師

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

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

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

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

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

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

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