艾兹格·迪科斯彻

艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日),生于荷兰鹿特丹,计算机科学家,毕业就职于荷兰莱顿大学,早年钻研物理数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974年AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。

目录

崭新的计算机语言

1952至1956年间,程序设计经历了一个演变的过程,这部分是由于系统分组的复杂性要求一个更具结构性的操作系统,部分是由于科学、数学上的关于程序设计的态度都提出了一个清楚的关于如何提高工作效率的观点。Dijkstra的Shortest Path Algorithm是在这方面取得的突出进展,因为这种演变是全球性的,所以,在全世界的推动下,一个科学的计算机语言基础:ALGOL,不久就诞生了。1958年,Edsger Dijkstra代表Dutch MC出席了11月在Mainz召开的会议,那是一个定义ALGOL详述的准备会议。1959年12月,Dijkstra给ALGOL60下了这样的定义:“一个奇迹就被这样简单的创造了。”最后,1962年的4月,罗马公约同意了其大部分的详述,同年8月,IFIP,国际程序设计语言联盟复查并批准了该报告。1960年的1月,在ALGOL60被定义之后,数学中心首先在荷兰开设了ALGOL60程序设计语言的课程,接着,1961年在英国的Brighton。这是MC一个新的开端:程序设计教育。

机会与欺骗

Eds1962年,Edsger Dijkstra在TH Eindhoven任全职教授,虽然在国外已经被认为是计算机科学的主席,但Dijkstra强烈反对这个称呼,这主要是由于在专业科学知识上的缺乏。他的位置实际上是一个数学教授,他的学生接受了至少三年彻底的数学教育,经过这样一个时期,他们都能作为信息学方面的专家了。那些数学训练是以应用数学原理为基础的。由此,信息学有了适合其学科本身的数学方法。1967年,Dijkstra陷入了情绪上的危机,他第一个学生的论文被他在Eindhoven数学上的同事拒收了,而这些同事对于计算机科学一直是带有偏见的。对于他和他的妻子来说,那段不景气的日子是他们一生中最困难的时期。但是他很快又恢复了,并开始投入编写:结构化编程笔记。而Dijkstra在Eindhoven的同事对此不是保持沉默,就是完全消极的反应,但Dijkstra选择了正确的还击方式:他给欧洲和美国的同事们复印了20多份稿件。1973年,Dijkstra成为了Burroughs的研究员,他减少了在Eindhoven TH的工作。这个决定使他能够去写科学报告,他为Burroughs写了500多篇,还可以如愿的出国旅行。他成了一个自由人,而且拥有该公司最小的实验室:他的书房。

Austin:新纪元的起点

结构程序设计之父

Dijkstra被西方学术界称为“结构程序设计之父”和“先知先觉”(Oracle),他一生致力于把程序设计发展成一门科学。科学研究的帅才最重要的素质是洞察力(Vision和Insight),能够发现有前景的新领域或在新领域内发现和解决最关键的问题。下面仅举几例说明Dijkstra的洞察力。

解决编译系统中的关键问题

FORTRAN是最早得到一定程度推广的高级语言,但FORTRAN的编译系统并未科学地解决一些主要的难题。最早提出用堆栈(stack)来编译复杂公式的是德国的Bauer和Samelson,他们的著名论文“顺序公式的翻译”(Sequential Formula Translation)是编译方面的经典论文。曾有报道说Dijkstra是堆栈的发明人,这恐怕不符事实。Dijkstra发展了堆栈的概念,使之用于整个编译,以及目标代码运行时的动态存储分配,并在此基础上和Jenson完成了世界上第一个ALGOL60编译系统,采用了他首创的优先数编译算法。其中递归调用子程序时的环境维护是Dijkstra的重要贡献,Display这一术语就是当时他发明的,这是用来维护动态环境的一组寄存器(软件),其结构清晰并能适应任何复杂情况。我于20世纪60年代初看完他的文章后马上想到,假如计算机硬件中有对应的设备将极大地提高软件的运行效率。

Dijkstra是ALGOL 60报告的主要起草者之一,1972年Dijkstra在他获得ACM图灵奖的讲演中,仍对这一报告给予高度评价:“只有极少极少几个像ALGOL60报告这样短的文件能给计算机界带来如此深远的影响。”

同步进程的协调和操作系统的结构

Dijkstra在1950~1952年期间曾当过三年程序员,在从事硬件中断处理程序的研制中,他发现一些程序错误在多个中断同时出现的情况下无法再现,很容易被当作硬件的瞬间故障,这一现象使Dijkstra毛骨悚然,促使他后来钻研用科学方法从事软件研制。操作系统是当时最复杂的软件,1965年Dijkstra在ACM通讯上发表了仅一页长的短文“并行程序的控制”,这是他在操作系统领域的第一个重要贡献。该文提出了并行程序互锁问题的一个解决方案。“死锁”(Deadly embrace)这一术语是Dijkstra发明的。1967年在首届操作系统原理研讨会上,Dijkstra介绍了他和几个博士生研制的THE多道程序系统。THE系统的目的是验证Dijkstra关于操作系统原理、结构、同步进程通信机制等方面的一系列新想法。今天已经普遍采用的系统的多层结构、抽象、上层不需了解下层的详细细节等科学原则就是当时Dijkstra提出的,引起了强烈反响;同步进程通信的信号量Semaphore这一术语也是Dijkstra当时创造的。

上世纪六十年代操作系统的研制经受了一系列重大挫折,典型的例子是OS 360。而Dijkstra为首的一批科学家的努力,使操作系统走上了健康发展的道路。

Go To语句有害和结构程序设计

结构程序设计被称为软件发展中的第三个里程碑(第一、二个里程碑是子程序和高级语言)。早在1965年召开的IFIP会议上,Dijkstra就提出“Go To语句可以从高级语言中取消”,“一个程序的质量与程序中所含的Go To语句的数量成反比”。但是,Dijkstra讲话的影响很小,当时人们正忙于IBM 360系列的使用;而IBM 360的主要语言之一是FORTRAN,Go To语句则是FORTRAN的支柱。

1968年Dijkstra给ACM通讯写了一篇短文,该文后改成信件形式刊登,以便早日发表,这就是具有历史意义的、著名的“Go To Letter”。Dijkstra在信中建议:“Go To语句太容易把程序弄乱,应从一切高级语言中去掉;只用三种基本控制结构就可以写各种程序,而这样的程序可以由上而下阅读而不会返回”。这封信引起了激烈的讨论。人们逐渐认识到:不是一个简单地去掉Go To的问题,而是促进一种新的程序设计观念、方法和风格,以期显著提高软件生产率和降低软件维护代价。当时采用结构程序设计方法的两个最著名项目是:

1.纽约时报信息库管理系统,含8.3万行源代码,只花了1年,第一年使用过程中,只发生过一次使系统失效的软件故障;

2.美国宇航局空间实验室操作的模拟系统,含40万行源代码,只用两年时间就全部完成。

上个世纪六十年代末到七十年代初,上述这两个系统可以算得上是大型软件了。

结构程序设计概念影响了后来的高级语言,也影响了一代程序员的风格和习惯。

坚持真理,不惜反对恩师

ALGOL 68语言是Van Wijingaarden为主设计的,得到了IFIP下属的工作小组的多数票通过。Wirth、Dijkstra和Hoare等工作小组成员发表了“少数派报告”,强烈反对这一语言及其表达方式。ALGOL 68的表达方式独特而严格,但不易理解,是Wijingaarden的发明。事实证明,少数派是正确的,ALGOL 68很快就夭折了。

要知道,Wijingaarden是Dijkstra的恩师。上世纪五十年代初Dijkstra在阿姆斯特丹数学中心编程序时Wijingaarden是他的领导。Dijkstra当时正在攻读理论物理学位,他发现理论物理课程和程序设计在精力上越来越冲突,他又拿不定主意,到底成为一个理论物理学家还是选择程序设计作为自己的职业,而他当时又担心程序设计能否成为被尊敬的学科。充满不安心情的Dijkstra于1952年春的一个早晨敲开了Wijingaarden办公室的门。几个小时的谈话,使Dijkstra变了另外一个人,因为Wijingaarden向他指明了程序设计这门学科正处在起步阶段,因而有重大的机会,Dijkstra可以努力使程序设计变成一个受人尊敬的学科。Dijkstra把这次谈话称为他一生中的转折点,于是决定尽快结束理论物理研究,全身心地投入程序设计。Dijkstra说,为此他应该终生感谢Wijingaarden。但是Dijkstra还是强烈地反对其恩师的得意之作ALGOL 68,少数派报告虽被IFIP压制,但真理终究得到了证明,后来的成功语言都是背离ALGOL 68方向的。

Dijkstra的名言今天仍有现实意义

Dijkstra的主要贡献是在上个世纪五十年代末到七十年代初,也就是他二十多岁到四十岁出头这段时间完成的。回忆这些过去的成就是想强调:洞察力对一个科学家是何等的重要!Dijkstra获图灵奖以后,软件领域又涌现出图形用户界面面向对象技术等一系列新的里程碑,因特网更是带来一个全新的时代。但是三十年前Dijkstra关于程序可靠性的一些名言至今仍有意义:

“有效的程序员不应该浪费很多时间用于程序调试,他们应该一开始就不要把故障引入。”

“程序测试是表明存在故障的非常有效的方法,但对于证明没有故障,调试是很无能为力的。”

Dijkstra大力提倡程序正确性证明,但这一方法离实用还有相当距离,因为一段源程序的正确性证明的文字往往比源代码还要长,所以充分的软件测试今天仍不可或缺。

1 主要成就

1.提出“goto有害论”;

2.提出信号量和PV原语;

3.解决了“哲学家就餐”问题;

4.Dijkstra最短路径算法和银行家算法的创造者;

5.第一个Algol 60编译器的设计者和实现者;

6.THE操作系统的设计者和开发者;

与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人。

特别提示:本站内容仅供初步参考,难免存在疏漏、错误等情况,请您核实后再引用。内容均来源于互联网。