天天看點

你不知道的關于計算機大師Dijkstra的事情

Dijkstra 的全名叫 Edsger Wybe Dijkstra(艾茲赫爾·韋伯·戴克斯特拉)。大部分中國程式員如果能記住這個名字是因為學過計算最短路徑的「Dijkstra 算法」,然而大部分人都難以記住正确的拼寫,因為他是荷蘭人,名字不符合英語的發音規則。

他是幾位影響力最大的計算科學的創始者之一,也是少數同時從工程和理論的角度塑造這個新學科的人。他的根本性貢獻覆寫了很多領域,包括:編譯器、作業系統、分布式系統、程式設計、程式設計語言、程式驗證、軟體工程、圖論等等。他的很多論文為後人開拓了整個新的研究領域。我們現在熟悉的一些标準概念,比如互斥、死鎖、信号量等,都是 Dijkstra 發明和定義的。1994 年時有人對約 1000 名計算機科學家進行了問卷調查,選出了 38 篇這個領域最有影響力的論文,其中有五篇是 Dijkstra 寫的。

Dijkstra 在鹿特丹長大。在高中畢業前他想在法學界發展,并且希望将來能在聯合國做荷蘭的代表。然而因為他畢業時數學、實體、化學、生物都是滿分,老師和父母都勸他選擇科學的道路,後來他選擇學習理論實體。在大學期間,世界上最早的電子計算機出現了,他父親讓他到劍橋大學參加一個程式設計的課程。從這裡開始,他的程式設計生涯開始了。一段時間以後他決定轉向計算機程式設計,因為他認為相對于理論實體,程式設計對智力是更大的挑戰。程式設計是最無情的,每一個一和零都容不得差錯。

後來他在阿姆斯特丹的數學中心成為了一個兼職的程式員。他的工作是為一些正在被設計制造的計算機編寫程式,也就是說他要用紙和筆把程式寫出來,驗證它們的正确性,和負責硬體的同僚确認需要的指令是可以被實作的,并寫出計算機的規範說明。他為并不存在的機器寫了五年程式,是以他很習慣于不測試自己寫的程式,因為無法測試。這意味着他必須通過推理說服自己程式是正确的,這種習慣可能是他後來經常強調通過程式結構保證正确性易于推理的原因。他曾經被後來出現的實時中斷困擾了一陣子,因為中斷随時可能發生,讓證明程式的正确性變得複雜了很多。他的博士論文就是關于一個他寫的實時中斷處理程式。

在他決定成為一個程式員後,他盡快完成了學業,因為以他的話說,他在大學裡不再受歡迎了:實體學家們覺得他是逃兵,而數學家們也看不起他和他做的事,因為在當時的數學文化裡,你的課題必須和 ∞ 有關才會受尊重。那個時候程式設計沒有成為一個職業,沒有人能說出這個行業的基礎知識體系是什麼,而這些都會被 Dijkstra 改變。1957 年,他結婚的時候在申請的職業一欄寫上了「程式員」,結果被政府拒絕,因為當時荷蘭沒有這個職業。

在一台新的叫 ARMAC 的計算機釋出之前,Dijkstra 需要想出一個可以讓不懂數學的媒體和公衆了解的問題,以便向他們展示。有一天他和未婚妻在阿姆斯特丹購物,他們停下來在一家咖啡店的陽台上喝咖啡休息,他開始思考這個問題。他覺得可以讓計算機示範如何計算荷蘭兩個城市間的最短路徑,這樣問題和答案都容易被人了解。于是他在 20 分鐘内想出了高效計算最短路徑的方法。Dijkstra 自己也沒有想到這個 20 分鐘的發明會成為他最著名的成就之一,并且會被以他的名字命名為 Djikstra 算法。三年以後這個算法才首次釋出,但當時的數學家們都不認為這能成為一個數學問題:兩點之間的路徑數量是有限的,其中必然有一條最短的,這算什麼問題呢?在之後的幾十年裡,直到今天,這個算法被廣泛應用在各個行業。Djikstra 的眼科醫生一直不知道他是做什麼的,有一天突然問他:「是你發明了 GPS 導航的算法嗎?」。一問之下,原來他讀了 2000 年 11 月的科學美國人雜志,講 GPS 的文章裡說到了 Djikstra。

你不知道的關于計算機大師Dijkstra的事情

求解最短路徑的 Dijkstra 算法

Dijkstra 後來在采訪中說,他的最短路徑算法之是以能如此簡潔,是因為當時在咖啡店裡沒有紙和筆,這強迫他在思考時避免複雜度,盡可能追求簡單。 在他的訪談和文章中,經常能發現一個主題,就是資源的匮乏往往最能激發創造性。

Dijkstra 第一次美國之行給他留下了深刻印象。在 1963 年時他已經小有名氣,ACM 邀請他參加了一次在普林斯頓的會議,這也是他第一次和 Donald Knuth 會面。第一個演講者是一個來自 IBM 的人,Dijkstra 發現他完全聽不懂這個人講的内容,也不了解寫滿了整個黑闆的公式,而很多其他聽衆都積極提出問題并參與讨論。在茶歇的時候他對其他人表達了擔憂,認為自己可能不适合參加這個會議,美國的參會者告訴他「哦,不必擔心。其實大家都聽不懂他說什麼。但是這次會議是 IBM 贊助的,是以得讓他們先上台,而且不能冷場。」Dijkstra 後來似乎一直對 IBM 不太感冒。IBM 的 System/360 大型機釋出後,他花了一些時間閱讀 360 的手冊,他把這段時間描述為「我職業生涯中最黑暗的一周」。後來蘇聯決定建造和 360 完全相容的計算機,Dijkstra 在一次會議上說「這是美國在冷戰中最大的勝利」。

之後 Dijkstra 進入了學術上最活躍的時期,他解決了多個圖論算法問題,他發表的關于并發程式控制的論文開創了分布式計算和并發計算的領域,他也首先定義了互斥和死鎖并提出了解法。他和  Jaap Zonneveld 一起寫了第一個 ALGOL 60 的編譯器,這是最早支援遞歸的編譯器。他們約定項目結束前都不許刮胡子,Zonneveld 在結束後很快剃掉了胡子,而 Dijkstra 從此終身留着胡子。

1960 年代後期,由于計算機變得越來越強大,程式設計和維護的方式跟不上軟體複雜度的快速上升,世界進入了「軟體危機」。Dijkstra 在 ACM 的月刊上發表了一篇名為 GOTO Statement Considered Harmful 的文章為全世界的程式員們指明了方向,這就是結構化程式設計運動的開始。他和 Hoare、Dahl 合著的《結構化程式設計》成為了這次軟體史上第一次變革的綱領,影響了此後大部分程式設計語言,包括 70、80 後程式員熟悉的 C 和 Pascal。很多大學的第一門程式設計課就是以這本書的名字作為課程名。

在分布式計算方面,除了定義前面提到的互斥、死鎖等并發控制的基礎概念和問題,他還開創了自穩定系統這個子領域,并且是最早對容錯系統進行研究的人。我自己的 Ph.D. 論文就屬于對自穩定系統的研究。分布式計算最權威的會議是 PODC,而 Leslie Lamport 曾經評價到,PODC 之是以存在就是因為 Dijkstra。「PODC 影響力論文獎」是分布式計算領域最高的榮譽,它認可的是經過時間考驗的重要成就。我自己的導師 Michael Fischer 和 Nancy Lynch、Michael Paterson 一起在 2001 年獲獎。2002 年,Dijkstra 去世,這一年的 PODC 獎頒給了他,獲獎論文是他 1974 年關于自穩定系統的論文。為了紀念他,PODC 決定從 2003 年把這個獎項改名為 Dijkstra 獎。是以 Dijkstra 是少數獲得過以自己的名字命名的獎項的人之一。

Dijkstra 在學術界有一些很知名的個性。讀過碩士或者博士的人大多對論文的應用次數、影響因子之類的東西很敏感,中國學術界尤其如此。而 Dijkstra 在他的書和文章裡幾乎從來不提供參考文獻清單,很多人對此很不滿,而他認為這樣增強了他工作的獨立性。他在德州大學奧斯丁分校的教學風格也很獨特。在每個學期開始的時候,他會給每個學生拍一張照片以便記住他們的名字(這是在智能手機還沒發明,使用老式相機的時代)。他的課程幾乎都沒有指定教科書,少數有教科書的時候也是他自己寫的書。我上大學的時候,有很多教授也有隻用自己寫的教科書的習慣,但可能原因不一樣吧。他通常用口試的方式進行期末考試,花一周的時間讓學生逐個到他辦公室或家裡考試,每個人要用兩三個小時。

盡管計算機軟體技術有很大一部分是 Dijkstra 發明的,但他卻很少使用計算機,或許這和他作為程式員時很大一部分時間是在為還沒造出來的計算機開發程式有關系。後來在德州大學的同僚壓力下他購買了一台 Macintosh 電腦,但隻用來回複電子郵件和浏覽網頁。和 Donald Knuth、Leslie Lamport 這樣關注于論文的數字排版并發明了 TeX 和 LaTeX 來做這件事的計算機科學家不一樣,Dijkstra 從不用計算機寫論文。他認為應該不需要草稿和編輯就能寫出一篇文章,是以他通常在腦中把整篇文章構思好才把文字落到紙上。在早期他用打字機,後來他一直隻使用 Montblanc 的 Meisterstück 鋼筆。這在計算機學界是很有名的習慣,很多人都收到過 Dijkstra 用 Montblanc 寫的信。Montblanc 應該請他做代言。

Dijkstra 通常會用鋼筆寫好一篇文章,然後影印一些在同僚中小範圍散發,而這些同僚又會影印更多,釋出到更廣的範圍。他一生中寫了 1300 多篇文章,他用自己姓名的首字母 EWD 給他們編号:EWD 1, EWD 2, … EWD 1318。在計算機科學中,這些文章被統稱為「EWD 報告」。他的算法和文章大都讓人感受到簡潔、經濟、優雅。他對簡潔的熱愛來自于早年母親的指導。他曾經問他的母親數學是不是一個很難的學科,她回答說「如果你需要超過五行文字來證明什麼,那你的方向多半錯了」。

你不知道的關于計算機大師Dijkstra的事情

最後,作為結語,送給大家一句 EWD 1213 裡的名言:

如果十年以後,你以快而髒的方式做什麼事的時候,能想象我在你的肩後看着,然後對自己說:「Dijkstra 不會希望這樣的。」那麼對我來說,這就和永生一樣了。

— Edsger Wybe Dijkstra