1972年图灵奖获得者：埃德斯加.狄克斯特拉(Dijkstra)
2008-05-11 14:44阅读：
(P.S.
这个埃德斯加.狄克斯特拉，就是那个提出“goto有害论”的Dijkstra，就是那个提出信号量和PV操作的Dijkstra，那个Dijkstra最短路径算法的创造者，第一个Algol60编译器的设计者和实现者，THE操作系统的设计者和开发者，那个与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人。
在摘抄下这篇图灵奖获得者的介绍的时候，我从内心感到崇敬和激动，而且非常之强烈。当我开始学习BASIC的时候，就知道有个叫Dijkstra的人劝告大家不要滥用goto，而在那之前，goto在我看来就是编程的全部奥秘所在。之后我在大学里学习算法、数据结构、操作系统等课程的时候，Dijkstra这个名字一次又一次从书里跳出来，我对于这个名字的崇敬也越来越深。一代大师，我们至今还能从计算机的多个领域中见到他的身影！)
1972年的图灵奖授予荷兰的计算机科学家埃德斯加.狄克斯特拉 (Edsgar Wybe
Dijkstra)。狄克斯特拉因最早指出“goto是有害的”以及首创结构化程序设计而闻名于世。
事实上，他对计算机科学的贡献并不仅仅限于程序设计技术。在算法和算法理论、编译器、操作系统诸多方面，狄克斯特拉都有许多创造，作出了杰出贡献。1983年，ACM为纪念Communications
of ACM
创刊25周年，评选出从1958-1982的四分之一个世纪中在该杂志上发表的25篇有里程碑意义的论文，每年一篇，狄克斯特拉一人就有两篇入选，是仅有的这样的两位学者之一（另一位是英国学者霍尔：C.
A. R. Hoare，1980年图灵奖获得者）。
狄克斯特拉1930年5月11日生于鹿特丹的一个知识分子家庭，在兄弟姐妹4人中排列第三。
他的父亲是一名化学家和发明家ᦁ
2;曾担任荷兰化学会主席。 他母亲则是一位数学家。
狄克斯特拉的少年时代是在德国法西斯占领军的铁蹄下度过的。由于食物短缺，他被送到乡下他父亲的一个朋友那里去。 纳粹德国投降后，
1945年7月，十分虚弱的狄克斯特拉才和家人重新团聚。
狄克斯特拉原打算学法律，毕业后到联合国工作，为维护世界和平服务。但他中学毕业时，数理化成绩都特别好，因此他父亲说服了他，1948年进莱顿大学学习数学与物理。在学习理论物理的过程中，狄克斯特拉发现这个领域中的许多问题都需要进行大量复杂的计算，于是决定学习计算机编程。1951年，他自费赴英参加了剑桥大学举办的一个程序设计培训班，学习在EDSAC（Electronic
Delay StorageAutomatic
Calculator,这是由1967年图灵奖获得者威尔克斯主持设计与开发的世界上第一中存储程序式电子计算机）上的编程方法，这使他成为世界上第一批程序员之一。第二年，阿姆斯特丹数学中心了解到这一情况，拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫，因为世界上当时还没有“程序员”这一职业。数学中心的计算部主任、Algol
语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A. van Wijingaarden,1916-1987，因在设计Algol
68时，为解决上下文有关性这一难题而提出了一种具有很强描述能力的新的文法，叫二级文法又称W文法而闻名。他也曾对1984年图灵奖获得者N.
Wirth的研究产生过影响)对他说，目前程序设计虽然还没有成为学科，不被重视，但既然计算机已经有了，正处于开创阶段，你未来就有可能使程序设计成为一个受人尊敬的学科。这段话说动了狄克斯特拉，使他接受了这个职位，而且越干越有兴趣，这样，他在第二年就结束了在莱顿大学的学业，成为数学中心全日制的工作人员，从此进入计算机领域，并且正如维京格尔藤所预言的那样，
逐渐成为该领域的知名专家，创造出了许许多多的“第一”。
1956年，他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“Dijkstra算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用。
（P.S.
这就是大家熟知的著名的Dijkstra单源最短路经算法）
1959年，在数学中心将他们原先的ARMAC计算机进行升级的过程中，狄克斯特拉设计了一种处理程序，成功地解决了“实时中断”（real-time
interrupt）问题。狄克斯特拉的博士论文就是以此为课题完成的，并在阿姆斯特丹大学通过论文答辩而获得博士学位。
1960年8月，Algol 60文本推出刚刚半年多，狄克斯特拉和他在数学中心的同事仲纳凡尔特(J. A.
Zonneveld)一起就
率先实现了Algol
60编译器。这一成就引起各国计算机学者的惊叹，并因此奠定了狄克斯特拉作为世界一流计算机学者在科学界的地位。
1962年，狄克斯特拉离开数学中心进入位于荷兰南部的埃因霍温技术大学(Eindhoven Technical
University)任数学教授。在这里，他参加了X8计算机的开发，设计与实现了具有多道程序运行能力的操作系统——THE
Multiprogramming System。THE是埃因霍温技术大学的荷兰文Tchnische Hoogeschool
Eindhoven的词头缩写。狄克斯特拉在THE这个系统中所提出的一系统方法和技术奠定了计算机现代操作系统的基础，尤其是关于多层体系结构，顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。为了在单处理机的情况下确定进程(process)能否占有处理机，狄克斯特拉将
每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态。当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞”状态，待造成其退出运行的条件解除，再进入“就绪”状态。而对系统中所有同时运行的进程，在一个进程访问共享数据时，另一个进程不访问该数据）和互斥（mutually-
exclusive，指两个进程不能同时在一个临界区中使用同一个可重复使用的资源，诸如读写缓冲区）两个关系，狄克斯特拉巧妙地利用火车运行控制系统中的
“信号灯”(semaphore，或叫”信号量”)概念加以解决。所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程，为了防止这两个进程并发时产生错误，狄克斯特拉
设计了一种同步机制叫“PV操作”，P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P（S）时信号量S的值减1，若结果不为负则P（S）执行完毕，否则执行P操作的进程暂停以等待释放。执行V操作V（S）时，S的值加1，若结果不大于0则释放一个因执行P（S）而等待的进程。对P1和P2可定义两个信号量S1和S2，初值分别为1和0。进程P1在向缓冲B送入数据前执行P操作P（S1），在送入数据后执行V操作V（S2）。进程P2在从缓冲B读取数据前先执行P操作P（S2），在读出数据后执行V操作V（S1）。当P1往缓冲B送入一数据后信号量S1之值变为0，在该数据读出后S1之值才又变为1，因此在前一数未读出前后一数不会送入，从而保证了P1和P2之间的同步。
我国读者常常不明白这一同步机制为什么叫PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫vrijgeven，PV操作因此得名。这是在计算机术语中不是用英语表达的极少数的例子之一。
THE还有许多特色和创新，如：
1．对短程序予以特殊处理，以减少其周转时间，从而提高整个系统的效率；
2．在使用外围设备方面采取了一系列特殊手段，使之更加经济；
3．对与CPU相联的后援存储器能进行自动控制；
4．设计中既考虑了方便程序员使用，也考虑了方便操作员使用和维护计算机系统。
THE是在程序设计中最先引入并发概念的系统，开创了并发程序设计的先河。因此，当1967年，狄克斯特拉在ACM召开的第一届操作系统原理讨论会上提交的论文“THE多道程序系统的结构”一文中介绍了该系统后，引起与会者的极大兴趣和重视。该文后来刊载于1968年5月的Communications
of ACM上， 就是被评为有里程碑意义的25篇论文之一。
狄克斯特拉的另一篇有里程碑意义的论文是“并发程序控制中的一个问题的解决”(Solution of a Problem
inConcurrent Programming Control)，是1965年9月发表的。
1968年3月，Communications of
ACM登出了狄克斯特拉的那封影响深远的信，在信中他根据自己编程的实际经验和大量观察，得出如下结论：一个程序的易读性和易理解性同其中所包含的无条件转移控制的个数成反比关系，也就是说，转向语句的个数愈多，程序就愈难读、难懂。因此他认为
“GOTO是有害的”，并从而启发了结构化程序设计的思想。1972年，他与当时在爱尔兰昆士大学任教的英国计算机科学家、1980年图灵奖获得者霍尔(C.
A. R. Hoare)合著了《结构化程序设计》一书（Structured Programming，Academic
Pr.），进一步发展与完善了这一思想，并且提出了
另一个著名的论断：“程序测试只能用来证明有错，决不能证明无错！”(Program
testing can be used to show thepresence of bugs，but never to show
theirabsence!)。
1973年8月，狄克斯特拉离开埃因霍温，应聘担任著名的美国宝来公司(Burroughs)的高级研究员，但宝来并不要求他到密歇根州的底特律总部或世界各地的任一分支机构去上班，而是给予他最大的自由：留在荷兰家里做自己感兴趣的任何事情，或到世界各地旅行、考察、参加会议……唯一的要求是他经常把自己的行踪、见闻、观感、心得和看法以书面形式向公司报告。狄克斯特拉于是当了约10年的“自由”研究员，这期间他去过德国、英国、安哥拉、瑞士、加拿大、波兰、苏联、日本、法国、澳大利亚等许多学术会议、讨论会或培训班，当然也继续做研究工作。他向宝来公司发去的信件有500多篇，内容十分丰富。在这期间，狄克斯特拉对计算机科学作出的最重要的贡献，就是1975年他提出了公理化语义描述的一种方法，叫“最弱前置条件方法”(weakest
pre-conditionmethod)，这种方法是在霍尔所提出的前后断言(assertion)
的基础上形成的。其基本思想是：将程序设计看作是“面向目标”的活动，编程就是从预先给定的“后断言”出发，逆向地逐步推导出满足它的程序，同时计算出所需的最弱前置条件。它是一个谓词公式，用wp（S，R）表示，其中R是语句S执行后所期望的的结果，也就是后断言或称结果断言。例如，赋值语句(assignment
statement)的语义可如下表示：
wp（x：= e，R）≡ R [x/e]
其意义是将R中x的所有自由出现同时代换成e 。
假定将x * x赋给x后，x
4= 10，则可表示成：
wp(“x：= x * x”，x
4= 10) ≡((x * x)
4=10)
≡(x
8=10)
为了证明循环的终止性，狄克斯特拉引入了循环不变式和界函数。一般说来，一个循环呈如下形式：
{invariant：P}——进入循环前，不变式P真，
{bound：t} ——并且B真时t>0,t是循环次数的上界
doB→Decrease t,S true od
———当B真时，使t 递减并执行S，S执行过程真
保持P
{P∧B} ———则循环必然终止且终止时P真B假
若Q是S的执行能在有限时间内中止并满足R的任一前提条件，则必有Q→wp(S,R)。因此，证明前后断言Q{S}R只需先求出最弱前置断言wp（S，R），再证明Q→wp(S,R)。
当给定了Q和R，根据Q，R的结构，通过推导wp(S,R)，可推出S的结构，从而将程序设计的过程变成数学推导的过程。例如，要设计一个循环DO，使得当满足前置断言Q和结果断言R，则P，t和B应满足Q→
P∧bound：t,t≦0 →B 及P∧B→R。这实际上给出了循环语句设计的原则。
狄克斯特拉所提出的最弱前置条件的概念及相应的程序设计演算，使得程序的设计和程序的验证可同时进行，具有十分重要的理论意义和实际价值，极大地促进了程序设计作为科学的进程。
狄克斯特拉于1984年结束了宝来公司自由研究员的生活，应邀出任位于奥斯汀的得克萨斯大学计算机科学系名誉主任。
狄克斯特拉论著极多，主要有：
《Algol 60程序设计入门》(A Primer of Algol 60 Programming, Academic
Pr.，1962)
《程序设计的训练方法》(ADiscipline of Programming, Prentice-Hall，1976)
《程序设计的教学就是思维方法的教学》(TheTeaching of Programming i. e. the Teaching of
Thinking，Springer，1976)
《关于计算的论著选集：个人的观点》(SelectedWriting on Computing：A Personal
Perspective，Springer，1982。本书是从他发给宝来公司的大量通信中选出最重要、最有意义的60余件通信材料编纂而成的，集中反映了他那个时期的观点和研究成果)
《程序设计方法》(A Method ofProgramming，Addison- Wesley，1988)
《程序与证明的形式开发》(FormalDevelopment of Programs and
Proofs，Addison-Wesley，1990)
《谓词演算与程序语义》(PredicateCalculus and Program
Semantics，Springer，1990)
除了获得图灵奖外，狄克斯特拉还在1974年获得AFIPS的HarryGoode奖。
狄克斯特拉是在1972年8月14日于波士顿召开的ACM年会上接受图灵奖的。他发表了题为“智力低下的程序员”(The Humble
Programmer)的图灵奖演说，刊于Communications of ACM
，1973年10月，859-866页。也可见《前20年的ACM图灵奖演说集》(ACM Turing Award
Lectutes——TheFirst 20 Years：1966-1985，ACM Pr.
),17-32页。演说中他肯定了Fortran ,Algol,
LISP等语言，而对于PL/I，他认为是失败的。演说的重点是如何建立可靠的软件，如何在编程时就尽力避免引入错误，而不是以后再去消除错误，这不单具有技术上的意义，而且在经济上是十分重要的。狄克斯特拉的上述观点赢得了愈来愈多的人的理解与支持。
1989年，为了庆祝狄克斯特拉60寿辰，由著名计算机学者、狄克斯特拉的长期合作者费京 (W. H. J.
Feijin)等联合编纂了一本纪念性文集，书名引用了狄克斯特拉的另一句名言：《完美是我们的追求》（Beauty is Our
Business，Springer，1990）。书中包括他的同事、朋友、学生们写的53篇文章，其中有4位图灵奖获得者，即霍尔(C.
A. R. Hoare，1980)、克努特（D. Knuth，1974）、沃思（N. Wirth，1984）和伯努利（A.
Pnueli，1996）。有趣的是，克努特在1966年曾经对狄克斯特拉“并发程序控制中一个问题的解决”一文中所提出的方案进行批评，认为该方案有可能使特定进程“饿死”，即永远被阻塞而无法获得所需资源。他提出了一种“不会饿死”的方案。但有评论指出，克努特的方案比狄克斯特拉的方案更加复杂而未见得更加可靠。显然，学术上的争论并不妨碍这两位大师级的计算机科学家成为好朋友。
在与癌症进行了多年的斗争之后，狄克斯特拉于2002年8月6日在荷兰Nuenen自己的家中逝世。
P.S. 大家可以看看王选老师对Dijkstra的评价
王选：从Dijkstra谈帅才的洞察力
