最早认识到“goto有害”   

       

    狄克斯特拉1930年5月11日生于鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。狄克斯特拉的少年时代是在德国法西斯的铁蹄下度过的。由于食物短缺，他被送到乡下他父亲的一个朋友那里去。纳粹德国投降后，1945年7月，十分虚弱的狄克斯特拉才和家人重新团聚。狄克斯特拉原打算学法律，毕业后到联合国工作，为维护世界和平服务。但他中学毕业时，数理化成绩都特别好，因此他父亲说服了他，1948年进莱顿大学学习数学和物理。在学习理论物理的过程中，狄克斯特拉发现了这个领域中的许多问题都需要进行大量复杂的计算，于是决定学习计算机编程。1951年，他自费赴英参加剑桥大学举办的一个程序设计培训班，学习在EDSAC上的编程方法，这使他成为世界上第一批程序员之一。第二年，阿姆斯特丹数学中心了解到这一情况，拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫，因为世界上当时还没有“程序员”这一职业。数学中心的计算部主任、Algol语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A.van. Wijingaarden)对他说，目前程序设计虽然还没有成为学科，不被重视，但既然计算机已经有了，正处于开创阶段，你未来就有可能使程序设计成为一个受尊敬的学科。这段话说动了狄克斯特拉，使他接受了这个职位，而且越干越有兴趣，这样，他在第二年就结束了在莱顿大学的学业，成为数学中心全日制的工作人员，从此进入计算机领域，并且正如维京格尔藤所预言的那样，逐渐成为该领域的知名专家，创造出了许许多多的“第一”。

    1956年，他成功的设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用。

    1959年，在数学中心将他们原先的ARMAC计算机进行升级的过程中，狄克斯特拉设计了一种处理程序，成功的解决了“实时中断”(real-time interrupt)问题。狄克斯特拉的博士论文就是以此为课题完成的，并在阿姆斯特丹大学通过论文答辩而获得博士学位。

    1960年8月，Algol60文本推出刚刚半年多，狄克斯特拉和他在数学中心的同事仲纳凡尔特(J.A.Zonneveld)一起就率先实现了世界上第一个Algol60编译器，比欧美其他各国学者实现Algol60早一年还多。这一成就引起各国计算机学者的惊叹，并因此奠定了狄克斯特拉作为世界一流计算机学者在科学界的地位。

    1962年，狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德霍芬技术大学(Eindhove Technical University)任数学教授。在这里，他参加了X8计算机的开发，设计与实现了具有多道程序运行能力的操作系统--THE Multiprogramming System。THE是艾恩德霍芬技术大学的荷兰文Technische Hoogeschool Eindhoven的词头缩写。狄克斯特拉在THE这个系统中所提出的一系列方法和技术奠定了计算机现代操作系统的基础，尤其是关于多层体系结构，顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中国首先提出并为以后的操作系统如UNIX等所采用的。为了在单处理机的情况下确定进程(process)能否占有处理机，狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态，由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程进入“就绪”状态。当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞”状态，待造成其退出运行的条件解除，在进入“就绪”状态。而对系统中所有同时运行的进程之间所存在的相互制约的同步(Synchronization，指为了避免错误，在一个进程访问共享数据时，另一个进程不访问该数据)和互斥(mutaullu 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月的Communication of ACM上，就是被评为有里程碑意义的25篇论文之一。狄克斯特拉的另一篇有里程碑意义的论文是“并发程序控制中的一个问题的解决”(Solution of a Problem in Concurrent Programming Control)，是1965年9月发表的。

    1968年3月，Communication of ACM登出了狄克斯特拉的那封影响深远的信，在信中他根据自己编程的实际经验和大量观察，得出如下结论：一个程序的易读性和易理解性同其中所包含的无条件转移控制的个数成反比关系，也就是说，转向语句的个数愈多，程序就愈难读、难懂。因此他认为“GOTO是有害的”，并从而启发了结构化程序设计的思想。1972年，他与当时在爱尔兰昆士大学任教的英国计算机科学家、1980年图灵机获得者霍尔合著了《结构化程序设计》一书(Structure Programming, Academic Pr.)，进一步发展与完善了这一思想，并且提出了另一个著名的论断：“程序测试只能用来证明有错，决不能证明无错！”(Program testing can be used to show the presence of bugs, but never to show their absence!)。

    1973年8月，狄克斯特拉离开了艾恩德霍芬，应聘担任著名的美国宝来公司(Burroughs)的高级研究员，但宝来并不要求他到密西根州的底特律总部或世界各地的任一分支机构去上班，而是给予他最大的自由：留在荷兰家里做自己感兴趣的任何事情，或到世界各地旅行、考察、参加会议......唯一的要求是他经常把自己的行踪、见闻、观感、心得和看法以书面形式向公司报告。狄克斯特拉于是当了约10年的“自由”研究员，这期间他去过德国、英国、安哥拉、瑞士、加拿大、波兰、苏联、日本、法国、澳大利亚等许多国家，参加了许多学术会议、讨论会或培训班，当然也继续做许多研究工作。这期间，狄克斯特拉对计算机科学做出的最重要的贡献，就是1975年他提出了公理化语义描述的一种方法，叫“最弱前置条件方法”(weakest pre-condition method)，这种方法是在霍尔所提出的前后断言(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的结构，从而将程序设计过程变成了数学推导的过程。

    狄克斯特拉所提出的最弱前置条件的概念及相应的程序设计演算，使得程序设计和程序验证可同时进行，具有十分重要的理论意义和实际价值，极大地促进了程序设计作为科学的进程。

    狄克斯特拉于1984年结束了宝来公司的自由研究员的生活，应邀出任位于奥斯汀的德克萨斯大学计算机科学系名誉主任。

    狄克斯特拉论著极多，主要有：

    《Algol 60程序设计入门》(A Primer of Algol 60 Programming,Academic Pr., 1962)

    《程序设计的训练方法》(A Discipline of Programming, Prentice-Hall, 1976)

    《程序设计的教学就是思维方法的教学》(The Teaching of Pro-gramming i.e. the Teaching of Thinking, Springer, 1976)

    《关于计算的论著选集：个人的观点》(Selected Writing on Computing: A Personal Perspective， Springer, 1982)

    《程序设计方法》(A Method of Programming, Addison-Wesley,1988)

    《程序与证明的形式开发》(Formal Development of Programs and Proofs, Addison-Wesley, 1990)

    《谓词演算与程序语义》(Predicate Calculus and Program Semantics, Springer, 1990)

    除了图灵奖，狄克斯特拉还在1974年获得AFIPS的Harry Goode奖。

    狄克斯特拉是在1972年8月14日于波士顿召开的ACM年会上接受图灵奖的。他发表了题为“智力低下的程序员”(The Humble Programmer)的图灵奖演说，刊于Communication of ACM，1973年10月，859~866页。也可见于《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures-The First 20 Years:1966-1985, ACM Pr.)17~32页。演说中他肯定了Fortran, Algol, LISP等语言，而对于PL/I，他认为是失败的。演说的重点是如何建立可靠的软件，如何在编程时就尽力避免引入错误，而不是以后再去消除错误，这不单是具有技术上的意义，而且在经济上十分重要。狄克斯特拉的上述观点赢得了愈来愈多的人的理解和支持。

    延伸阅读--http://amturing.acm.org/award_winners/dijkstra_1053701.cfm