漫谈计算机大师 Dijkstra 的事情

4,346次阅读

共计 3874 个字符，预计需要花费 10 分钟才能阅读完成。

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 第一次美国之行给他留下了深刻印象。在 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 报告」。他的算法和文章大都让人感受到简洁、经济、优雅。他对简洁的热爱来自于早年母亲的指导。他曾经问他的母亲数学是不是一个很难的学科，她回答说「如果你需要超过五行文字来证明什么，那你的方向多半错了」。

最后，作为结语，送给大家一句 EWD 1213 里的名言：