埃德斯加·狄克斯特拉

1、埃德斯加狄克斯特拉王选：从Dijkstra谈帅才的洞察力编者按：9月5日，本期报纸即将截稿付印之际，方正集团转来了王选老师特别写给计算机世界的这篇文章。在文中，王选院士缅怀计算机科学先驱Dijkstra的历史功绩，在技术的时空中浓缩大师的魅力、勾勒计算机科学发展的轨迹。但在缅怀的背后，更值得读者重视的，是王选老师对中国软件产业缺乏既懂管理又懂技术的师才的忧虑。计算机世界最近报道了计算机科学先驱Dijkstra于8月上旬逝世的消息。Dijkstra被西方学术界称为结构程序设计之父和先知先觉(Oracle)，他一生致力于把程序设计发展成一门科学。科学研究的帅才最重要的素质是洞察力(Vision和Insight)，能够发现有前景的新领域或在新领域内发现和解决最关键的问题。下面仅举几例说明Dijkstra的洞察力。解决编译系统中的关键问题FORTRAN是最早得到一定程度推广的高级语言，但FORTRAN的编译系统并未科学地解决一些主要的难题。最早提出用堆栈(stack)来编译复杂公式的是德国的Bauer和Samelson，他们的著名论文顺序公式的翻译(Sequential Formula Tra

2、nslation)是编译方面的经典论文。最近有些报道说Dijkstra是堆栈的发明人，这恐怕不符事实。Dijkstra发展了堆栈的概念，使之用于整个编译，以及目标代码运行时的动态存储分配，并在此基础上和Jenson完成了世界上第一个ALGOL60编译系统，采用了他首创的优先数编译算法。其中递归调用子程序时的环境维护是Dijkstra的重要贡献，Display这一术语就是当时他发明的，这是用来维护动态环境的一组寄存器(软件)，其结构清晰并能适应任何复杂情况。我于20世纪60年代初看完他的文章后马上想到，假如计算机硬件中有对应的设备将极大地提高软件的运行效率。Dijkstra是ALGOL 60报告的主要起草者之一，1972年Dijkstra在他获得ACM图灵奖的讲演中，仍对这一报告给予高度评价：只有极少极少几个像ALGOL60报告这样短的文件能给计算机界带来如此深远的影响。同步进程的协调和操作系统的结构Dijkstra在19501952年期间曾当过三年程序员，在从事硬件中断处理程序的研制中，他发现一些程序错误在多个中断同时出现的情况下无法再现，很容易被当作硬件的瞬间故障，这一现象使Dijk

3、stra毛骨悚然，促使他后来钻研用科学方法从事软件研制。操作系统是当时最复杂的软件，1965年Dijkstra在ACM通讯上发表了仅一页长的短文并行程序的控制，这是他在操作系统领域的第一个重要贡献。该文提出了并行程序互锁问题的一个解决方案。死锁(Deadly embrace)这一术语是Dijkstra发明的。1967年在首届操作系统原理研讨会上，Dijkstra介绍了他和几个博士生研制的THE多道程序系统。THE系统的目的是验证Dijkstra关于操作系统原理、结构、同步进程通信机制等方面的一系列新想法。今天已经普遍采用的系统的多层结构、抽象、上层不需了解下层的详细细节等科学原则就是当时Dijkstra提出的，引起了强烈反响；同步进程通信的信号量Semaphore这一术语也是Dijkstra当时创造的。同步进程协调方面的程序错误是很难发现的，为此我曾吃过大苦头。1979年我开始设计型照排系统，用了两台双极型高速微处理器平行工作实现轮廓字形的复原和控制激光扫描，两台微处理器通过信号量彼此协调。设计和编程均无错误，但在把微程序翻译成二进制代码时错了一位，结果造成了无法再现的随机故障：激光打

4、印机输出的汉字有时拖尾巴。这一故障持续了一年多，引起用户不满，后由潍坊计算机公司的一位协作人员挖空心思地发现了错误的原因，即二进制码错误，问题才得以解决。上世纪六十年代操作系统的研制经受了一系列重大挫折，典型的例子是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语句太容易把程序弄乱，应从一切高级语言中去掉；只用三种基本控制结构就可以写各种程序，

5、而这样的程序可以由上而下阅读而不会返回。这封信引起了激烈的讨论。人们逐渐认识到：不是一个简单地去掉Go To的问题，而是促进一种新的程序设计观念、方法和风格，以期显著提高软件生产率和降低软件维护代价。当时采用结构程序设计方法的两个最著名项目是：1.纽约时报信息库管理系统，含8.3万行源代码，只化了11人年，第一年使用过程中，只发生过一次使系统失效的软件故障；2.美国宇航局空间实验室操作的模拟系统，含40万行源代码，只用两年时间就全部完成。上个世纪六十年代末到七十年代初，上述这两个系统可以算得上是大型软件了。结构程序设计概念影响了后来的高级语言，也影响了一代程序员的风格和习惯。坚持真理，不惜反对恩师ALGOL 68语言是Van Wijingaarden为主设计的，得到了IFIP下属的工作小组的多数票通过。Wirth、Dijkstra和Hoare等工作小组成员发表了少数派报告，强烈反对这一语言及其表达方式。ALGOL 68的表达方式独特而严格,但不易理解，是Wijingaarden的发明。事实证明，少数派是正确的，ALGOL 68很快就夭折了。要知道，Wijingaarden是Dijkst

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

7、在上个世纪五十年代末到七十年代初，也就是他二十多岁到四十岁出头这段时间完成的。回忆这些过去的成就是想强调：洞察力对一个科学家是何等的重要！Dijkstra获图灵奖以后，软件领域又涌现出图形用户界面、面向对象技术等一系列新的里程碑，因特网更是带来一个全新的时代。但是三十年前Dijkstra关于程序可靠性的一些名言至今仍有意义：有效的程序员不应该浪费很多时间用于程序调试，他们应该一开始就不要把故障引入。程序测试是表明存在故障的非常有效的方法，但对于证明没有故障，调试是很无能为力的。Dijkstra大力鼓吹程序正确性证明，但这一方法离实用还有相当距离，因为一段源程序的正确性证明的文字往往比源代码还要长，所以充分的软件测试今天仍不可或缺。但是程序员的科学训练是十分重要的，有人曾做过一个试验：一个题目由一批印度程序员编程，其结果惊人地相似；而由一批中国程序员来做，编出的程序五花八门。中国的软件人员有时把创造性放在不恰当的地方。只有规范的科学的编程，一个大项目才能得到有效的管理，其质量才有保证。中国软件产业的发展需要有洞察力的帅才，也需要一大批训练有素的程序设计人员和既懂技术又懂管理的项目领导人。

8、PS埃德斯加狄克斯特拉-最先察觉goto有害的计算机科学大师1972年的图灵奖授予荷兰的计算机科学家埃德斯加狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因最早指出goto是有害的以及首创结构化程序设计而闻名于世。事实上，他对计算机科学的贡献并不仅仅限于程序设计技术。在算法和算法理论、编译器、操作系统诸多方面，狄克斯特拉都有许多创造，作出了杰出贡献。1983年，ACM为纪念Communications of ACM创刊25周年，评选出从1958-1982的四分之一个世纪中在该杂志上发表的25篇有里程碑意义的论文，每年一篇，狄克斯特拉一人就有两篇人选，是仅有的这样的两位学者之一(另一位是英国学者霍尔：C.A.R.Hoare，1980年图灵奖获得者)。狄克斯特拉1930年5月11日生于鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。狄克斯特拉的少年时代是在德国法西斯占领军的铁蹄下度过的。由于食物短缺，他被送到乡下他父亲的一个朋友那里去。纳粹德国投降后，1945年7月，十分虚弱的狄克斯特拉才和家

9、人重新团聚。狄克斯特拉原打算学法律，毕业后到联合国工作，为维护世界和平服务。但他中学毕业时，数理化成绩都特别好，因此他父亲说服了他，1948年进莱顿大学学习数学与物理。在学习理论物理的过程中，狄克斯特拉发现这个领域中的许多问题都需要进行大量复杂的计算，于是决定学习计算机编程。1951年，他自费赴英参加了剑桥大学举办的一个程序设计培训班，学习在EDSAC(Electronic Delay Storage Automatic Calculator，这是由1967年图灵奖获得者威尔克斯主持设计与开发的世界上第一台存储程序式电子计算机)上的编程方法，这使他成为世界上第一批程序员之一。第二年，阿姆斯特丹数学中心了解到这一情况，拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫，因为世界上当时还没有程序员这一职业。数学中心的计算部主任、Algol语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A.van Wijingaarden，1916-1987，因在设计A 120168时，为解决上下文有关性这一难题而提出了一种具有很强描述能力的新的文法，叫二级文法又称W文法而闻名。他也曾对1984年图灵奖获得者N.Wirth的研究产生过影响)对他说，目前程序设计虽然还没有成为学科，不被重视，但既然计算机已经有了，正处于开创阶段，你未来就有可能使程序设计成为一个受人尊敬的学科。这段话说动了狄克斯特拉，使他接受了这个职位，而且越干越有兴趣，这样，他在第二年就结束了在莱顿大学的学业，成为数学中心全日制的工作人员，从此进入计算机领域，并且正如维京格尔藤所预言的那样，逐渐成为该领域的知名专家，创造出了许许多多的第一。1956年，他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为狄克斯特拉算法，解决了机器入学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用。1959年，在数学中心将他们原先的ARMAC计算机进行升级的过程中，狄克斯特拉设计了一种处理程序，成功地解决了实时中断(real-time interrupt)问题。狄克斯特拉的博士论文就是以此为课题完成的，并在阿姆斯特丹大学通过论文答辩而获得博士学位。19

《埃德斯加·狄克斯特拉》由会员飞***分享，可在线阅读，更多相关《埃德斯加·狄克斯特拉》请在金锄头文库上搜索。