Edsger Dijkstra--把计算机科学扛在肩上的人

Krzysztof apt是阿姆斯特丹数学和计算机科学中心的研究员，也是阿姆斯特丹大学的荣誉退休教授。

我从奈梅亨坐到埃因霍温的火车晚点了。更糟糕的是，我当时在大学大楼里找不到合适的办公室。当我最终到达预约地点时，我比原定计划晚了半个多小时。教授完全无视我再三道歉，开始花整整一个小时开会。这是我第一次见到埃德斯格·怀贝·迪克斯特拉(Edsger Wybe Dijkstra)。

1975年我们见面时，迪克斯特拉45岁。三年前，计算机科学界最负盛名的奖项--ACM图灵奖(ACM Turing Award)授予了他。我比他小近20岁，对这一领域知之甚少--我只是在几周前才知道什么是流程图。我是一名刚从共产主义波兰来到这里的博士后，有数理逻辑的背景，并计划留在西方。我带着两个图书推荐和一份Dijkstra最近写的研究文章离开了会议。他还建议我学习编程语言帕斯卡。

迪克斯特拉于2002年去世。在20世纪70年代和80年代，在他职业生涯的巅峰时期，他可能是他所在领域内讨论最多的科学家。他是一位开拓者和天才，他的工作和思想塑造了新兴的计算机科学领域，几乎没有人能与他相提并论。正是在他的职业生涯中，计算机科学成为了一门受人尊敬的、成熟的学科。

计算机科学的工程观侧重于构建软件系统和硬件组件，而数学观和逻辑观旨在为编程等领域提供严格的基础，两者之间存在持久的紧张关系。迪克斯特拉试图调和这两种观点。因此，他在许多基本方面为分歧的双方做出了贡献。

迪克斯特拉也是一个最引人注目和不同寻常的人。他既受到钦佩，也受到批评，几乎所有他接触到的人都对他发表了评论。然而，尽管Dijkstra取得了成就，但在计算机科学之外，他在很大程度上仍然鲜为人知。在他去世18年后，几乎没有人听说过他，即使在他自己的国家也是如此。

E于1930年出生于鹿特丹。他形容曾任荷兰化学学会主席的父亲是“一位优秀的化学家”，母亲是“一位才华横溢的没有工作的数学家”。1948年，迪克斯特拉在鹿特丹著名的伊拉斯米安体育馆完成中学学业，取得了显著的成绩。他的学校文凭显示，他在十三门科目中至少有六门取得了可能的最高分。然后他进入莱顿大学学习物理。

1951年9月，迪克斯特拉的父亲建议他去剑桥参加一个为期三周的编程课程。事实证明，这是一个影响深远的想法。正是在剑桥，迪克斯特拉遇到了数学家和计算机科学家阿德里安·范·维恩加登(Adriaan Van Wijngaarden)，后者随后给他提供了一份在阿姆斯特丹数学中心(数学中心)的工作，他于次年加入了该中心。迪克斯特拉用他自己的话说，成为“第一个在工资单上拥有‘程序员’资格的荷兰人。”2 1956年，他在莱顿完成了学业。三年后，他为自己的博士论文“与自动计算机通信”辩护。他的上级是范·维恩加登。

迪克斯特拉在数学中心工作，直到1962年，他搬到埃因霍温，担任埃因霍温理工大学数学系教授。1973年，他将工作减少到每周一天，剩下的四天在当时一家创新的美国计算机制造商Burroughs Corporation担任研究员。他对Burroughs的唯一职责是进行研究，每年几次前往美国访问公司总部。

在Dijkstra的报告中，他列出了荷兰Nuenen 4565号Plataanstraat 5号的地址。这使得一些人认为Burroughs公司已经开设了一个新的办事处。实际上，地址就是迪克斯特拉的家，那是一座简陋的房子，位于埃因霍温郊区附近的一个村庄里。他的办公室由二楼的一个小房间组成，房间里配备了一台“优雅的便携式奥利维蒂打字机”和“两部电话…”。其中一个他可以用来给世界上任何地方打电话，账单直接寄给巴罗斯。“。

1984年，对Burroughs Corporation的方向改变和他所在的大学对计算机科学缺乏支持感到失望的Dijkstra离开了荷兰，在德克萨斯大学奥斯汀分校(University Of Texas At Austin)担任了一个享有盛誉的计算机科学教授。他后来写道：“而伯罗斯的学术视野在缩小，而我自己的视野在拓宽。”4他于1999年退休。

2002年初，Dijkstra得知自己身患绝症，并与妻子Ria一起搬回了纽宁。他在8月份去世，就在回来几个月后。十年后，RIA去世了。这对夫妇身后留下了三个孩子：Femke，Marcus和Rutger。

在他的职业生涯中，Dijkstra写了大约40份期刊出版物和30份会议出版物。他被列为几乎所有这些作品的唯一作者。他的几篇期刊论文只有几页长，而他的大多数会议出版物都是未经审阅的手稿，这些手稿是他在一年一度的国际马尔托伯多夫暑期学校(International Marktoberdorf Summer School)上提交的，并在学校议事程序中发表。他还写了几章书和几本书。

从这个角度来看，Dijkstra的研究成果似乎是值得尊敬的，但以目前的标准来看，其他方面并不引人注目。在这种情况下，外表确实是具有欺骗性的。用这种方式评判他的作品是完全错误的。事实上，迪克斯特拉是一位非常多产的作家，尽管是以一种不同寻常的方式。

我开始写一系列私人报告。它们连续编号，并以他的首字母为前缀，成为人们所熟知的EWD。四十多年来，他一直在写这些报告。最终的EWD编号为1,318，日期为2002年4月14日。EWDS总共有7700多页。每一份报告都由迪克斯特拉本人复印并邮寄给其他计算机科学家。接受者根据主题的不同而不同。以这种方式分发了大约20份每份EWD。

EWD最初是用荷兰语用打字机写的。1972年，迪克斯特拉改用全英文写作，1979年，他开始主要用手写。EWDS包括研究论文、新的或现有定理的证明、对他人科学工作的评论或意见(通常是批判性的，偶尔的标题是“给…的一封有点公开信”)。、立场文件、演讲稿、关于如何进行研究的建议(“只做你能做的事”)、关于教育和大学作用的意见(“大学的任务不是提供社会要求的东西，而是提供社会需要的东西”6)，以及对难题的原创性解决方案。后来的报道还包括偶尔对迪克斯特拉的生活和工作进行描述。许多电子出版物的标题是“旅行报告”，详细描述了他参加会议(“我设法不被拖到克里姆林宫就去了莫斯科”7)、暑期学校或度假目的地的旅行。这些报告是关于Dijkstra的习惯、观点、思维和(手写)写作的丰富信息来源。只有一小部分与研究有关的EWD曾经出现在科学期刊或书籍上。

事实上，这种报道研究的方式在18世纪很常见。在二十世纪，这是一个令人信服的时代错误。尽管如此，它还是奏效了。在日期为1987年1月11日的EWD1000中，Dijkstra讲述了读者告诉他们，他们拥有第六代或第七代EWD249。8个。

无论是用钢笔还是打字机书写，迪克斯特拉的技术报告都是以每分钟约3个字的速度撰写的。“剩下的时间，”他说，“都是用来思考的。”9对迪克斯特拉来说，写作和思考融为一体。在准备新的EWD时，他总是从一开始就寻求制作最终版本。

1999年左右，Dijkstra在奥斯汀的前同事汉密尔顿·理查兹(Hamilton Richards)创建了一个网站，以保存所有可用的EWD及其书目条目。10该网站名为E.W.Dijkstra Archive，也提供了大量关于Dijkstra的额外材料，包括他早期技术报告、采访、视频、讣告、文章和博客的扫描链接。

尽管在全球范围内进行了搜索，但一些1968年前的EWD从未被发现。根据Dijkstra自己的承认，编号方案中其他缺失的条目是“被我未能完成的文件占据”。

D是他所在领域的真正先锋。这偶尔会给他的日常生活带来问题。在他的图灵奖演讲中，他回忆道：

1957年，我结婚了，荷兰的结婚仪式要求你说明你的职业，我说我是一名程序员。但阿姆斯特丹镇的市政当局不接受它，理由是没有这样的职业。12个。

在20世纪50年代中期，Dijkstra构思了一种优雅的最短路径算法。当时几乎没有计算机科学期刊，要找到地方发表他长达三页的报告绝非易事。最终，三年后，他选择了新成立的Numerische Mahematik。13“A Note on Two Problems in Connexion with Graphs”仍然是计算机科学中被引用最多的论文之一，而Dijkstra的算法已经成为GPS导航系统中计算两个位置之间的最短路径所不可或缺的算法。

从1959年12月开始，在8个月的时间里，Dijkstra用Jaap Zonneveld编写了一个ALGOL 60编译器。他们的是这种新的高度创新的编程语言的第一个编译器。这是一项了不起的成就。为了编写编译器，必须克服几个挑战。这两个人面临的最明显的问题是，被指定运行该软件的机器，即荷兰电工X1计算机，只有4096个单词的内存。相比之下，现在的笔记本电脑的内存要大一百万倍。

编程语言本身也不是没有挑战。ALGOL 60包含一系列新颖的特性，例如递归，其支持方式比逻辑学家所设想的复杂得多。15 Dijkstra提出的一个称为显示的想法解决了递归过程的实现问题，并已成为编译器编写的标准技术。16个。

ALGOL 60是由一个国际委员会设计的。虽然Dijkstra在设计过程中参加了几次会议，但他的名字并没有出现在最终报告的13名编辑中。显然，他不同意多数人的意见，退出了委员会。这可能是他极力主张独立的第一个公开迹象。

在他供职于埃因霍温理工大学期间，Dijkstra和他的团队为X1的继任者ELELOGICA X8编写了一个操作系统。他们创建的系统被称为多道程序设计系统(The是Technische Hogeschool Eindhoven的缩写)，具有创新的分层功能结构，其中较高的层仅依赖于较低的层。18岁。

正是在他研究这个系统期间，Dijkstra的兴趣开始转向并行程序，这是一个早期的例子。这些程序由一组组件组成，每个组件都是并行执行的传统程序。众所周知，这类程序很难编写和分析，因为无论其组件的执行速度如何，它们都需要正确工作。并行程序还需要同步它们的操作，以确保独占访问资源。如果共享计算机网络的用户同时分派多个打印作业，这应该不会导致来自不同打印作业的页面散布。增加复杂性的是，并行程序的组件不应该变得死锁，不应该无限期地等待另一个组件。

在20世纪60年代早期，这些问题还没有得到适当的检查或分析，也没有开发出任何技术来验证潜在的解决方案。Dijkstra发现了一个关键的同步问题，他将其命名为互斥问题，并在一页纸的论文中发表了他的解决方案。19本文摘自EWD123，这是一份长达87页的报告，标题为“协作顺序进程”。在同一份报告中，他介绍了第一个已知的同步原语，他称之为信号量，这导致了互斥问题的一个简单得多的解决方案。20他还发现了僵局问题，他将其命名为致命拥抱，并提出了一个优雅的解决方案，即银行家算法。21互斥问题，以及死锁检测和预防，现在是操作系统和并行编程课程的必修主题。

1968年，Dijkstra发表了一封写给ACM通讯编辑的两页信，在信中他批评了Goto编程声明。22日，这封题为“声明被认为有害”的信受到了广泛批评，并引发了相当大的争论。最终，迪克斯特拉的观点占了上风。每个程序员现在都知道使用goto语句会导致所谓的意大利面代码。Java是目前使用最广泛的编程语言之一，最初发布于1996年，没有GOTO语句。“被认为有害的”一词在计算机科学中仍然经常使用，并与Dijkstra有着千丝万缕的联系。

1968年，迪克斯特拉遭受了长时间的深度抑郁，持续了近半年。他后来提到在这段时间里住院。23迪克斯特拉苦恼的一个原因是，他所在的系认为计算机科学并不重要，于是解散了他的团队。他还必须决定下一步要做什么。Dijkstra的主要软件项目，ALGOL 60编译器和多道程序设计系统，给了他一种感觉，编程是一项有自己规则的活动。然后，他试图发现这些规则，并以一种有意义的方式呈现它们。最重要的是，他努力将编程转变为一门数学学科，这一努力让他在接下来的几年里一直忙于工作。当时，这些水域完全是未知水域。似乎没有其他人把注意力放在这些事情上。

一年后，87页的EWD249“结构化编程笔记”的出现，标志着Dijkstra抑郁的结束。24 EWD的主题如此新颖，写作如此引人入胜，新术语“结构化编程”如此令人信服，以至于报告取得了巨大的成功。但是，在迪克斯特拉看来，“ibm…。偷走了术语“结构化编程”和…。25对于那些知道Dijkstra对IBM计算机和软件长期持有的、基本上是负面的看法的人来说，这一说法并不令人惊讶。如今，类似的情况并不少见。

1972年，Dijkstra获得了ACM图灵奖，该奖项被广泛认为是计算机科学界最重要的奖项。他被认为是。

对编程的基本贡献是一项高智力的挑战；雄辩地坚持和实践证明程序应该被正确地组合，而不仅仅是调试成正确的；用于阐明对程序设计基础上的问题的看法。26岁。

随之而来的是更多的根本性贡献。1974年，Dijkstra发表了一篇两页的文章，其中他介绍了一个新概念：自我稳定。27在这篇论文中，他提出了一个问题，即当一台机器出现暂时故障时，通信机器系统如何进行自我修复。他提出了新的协议，以保证系统的正确功能最终将得到恢复。“自我稳定，”他说，“…。可能在从全球网络(强调)到公共总线控制的范围内具有相关性。“。考虑到万维网是在短短15年后发展起来的，这是一个惊人的观察结果。事实证明，这份文件一直被完全忽视，直到1983年，莱斯利·兰波特在一次特邀演讲中强调了它的重要性。随着时间的推移，Dijkstra概述的想法将导致分布式计算领域出现一个全新的领域，并拥有自己的年度研讨会和会议。2002年，这篇论文获得了一个奖项，该奖项在死后被重新命名为分布式计算埃茨格·W·迪克斯特拉奖(Edsger W.Dijkstra Award)。

一些事件不能确定性预测的观念，通常被称为非决定论，几个世纪以来一直困扰着哲学家和后来的物理学家。计算机科学家最近加入了这个故事，以非决定论的名义研究这一想法-应该指出的是，这不是对事件的任何概率解释的参考。1963年，约翰·麦卡锡(John McCarthy)在编程语言的背景下引入了非决定论。几年后，罗伯特·弗洛伊德(Robert Floyd)展示了这个概念(现在被称为天使非决定论)是如何大幅简化需要搜索的编程任务的。28当有选择时，会有一些计算来提供所需的结果-尽管不确定是哪一个。

Dijkstra的非确定性观点很可能受到他在博士论文中开发的实时中断处理程序固有的不确定性行为的影响。在1975年的一篇论文中，他介绍了一种他称之为守卫命令的小型编程语言；它封装了现在被称为恶魔非决定论的东西。事实上，这就是我第一次见到他时他递给我的那张纸。与天使变种不同的是，所有的计算都必须提供所需的结果。这种对非决定论(Dijkstra称之为非决定论)的更苛刻的观点有时会产生更简单的程序，但原因不是天使般的非决定论。程序员可以自由地不指定某些决定。

Dijkstra引入的编程符号偶尔会产生优雅的程序。他通过重新考虑欧几里德2300年前计算两个自然数的最大公约数的算法来说明这一点。该算法可以表述为：只要两个数字不同，就从较大的数字中不断减去较小的数字。在Dijkstra的语言中，这个算法可以用一种简单的方式编写，与用英语描述的方式相差不远。30他的语言还引入了守卫这一关键概念，自那以后，这一概念已成为各种编程形式主义中的一个自然概念。同样，最弱的前置条件语义(Dijkstra引入来描述程序语义的概念)标志着进入程序验证领域的时间较晚，但意义重大。几年后，Tony Hoare推广了该语言，创建了一个非常有影响力的分布式计算编程语言提案，他将其命名为CSP。31。

Dijkstra的里程碑式著作“编程纪律”于1976年出版。32它介绍了一种新的编程方法，Dijkstra将最弱的前置条件语义与一些启发式方法相结合，开发了几个计算机程序，并同时给出了它们的正确性证明。与EWD249“结构化编程说明”不同的是，他现在争论的是程序的正确性。

.