PHOTOGRAPHS
BIRTH:
11 May 1930, Rotterdam, The Netherlands
DEATH:
6 August 2002, Nuenen, The Netherlands.
EDUCATION:
Gymnasium Erasmianum in Rotterdam (1948); undergraduate degree, physics, University of Leyden, (1956); PhD computer science, University of Amsterdam (1959). Honorary Degrees: Queen’s University Belfast, Athens University of Economics and Business.
EXPERIENCE:
Programmer, Computation Department of the Mathematical Centre in Amsterdam (1952–1962); Professor of Mathematics, Eindhoven University of Technology (1962–1973); Research Fellow, Burroughs Corporation (1973–1984); Schlumberger Centennial Chair in the Computer Science Department at the University of Texas at Austin (1984–2000).
HONORS AND AWARDS:
Member of the Royal Netherlands Academy of Arts and Sciences (1971); Distinguished Fellow of the British Computer Society (1971); AFIPS Harry Goode Memorial Award (1974); Foreign Honorary member of the American Academy of Arts and Sciences (1975); IEEE Computer Society Computer Pioneer Award (1982); ACM/SIGCSE Award for outstanding contributions to computer science education (1989); ACM Fellow (1994); ACM Influential Paper Award for: “Self-stabilizing systems in spite of distributed control” Communications of the ACM 17, Vol. 11 (1974), pp. 643–644, 2002 (in 2003 this annual award was renamed the Dijkstra Prize).
EDSGER WYBE DIJKSTRA DL Author Profile link
Netherlands – 1972
CITATION
For fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the foundations of program design.
SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
Edsger W. Dijkstra was born in 1930 in Rotterdam, The Netherlands. His father, a high-school chemistry teacher, served as president of the Dutch Chemical Society. His mother, who never held a formal job, had a lasting influence on his approach to mathematics and his emphasis on elegance.
Graduating from high school in 1948 and intending to become a theoretical physicist, Dijkstra thought the ability to use an electronic computer might be advantageous. Three years of programming at the Mathematical Center in Amsterdam convinced him that the intellectual challenge of programming exceeded that of theoretical physics, but where was the sound body of knowledge that could support programming as an intellectually respectable discipline? His boss, A. van Wijngaarden, persuaded him that in the years to come he could be one of the people to make programming a respectable discipline. Completing his study of physics as quickly as he could, Dijkstra forsook physics for programming.
At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities? The best known algorithms had running times which grew as the cube of the network’s size; the running time of Dijkstra’s algorithm grew only as the square. Developed in 20 minutes while Dijkstra was relaxing on a café terrace with his fiancée, Maria (Ria) C. Debets, his Shortest Path algorithm is still used in such applications as packet-switching software for computer communications.
Around the same time, Dijkstra invented another very efficient network algorithm for use in designing the X1 computer. Known as the Minimum Spanning Tree algorithm, it finds the shortest length of wire needed to connect a given set of points on a wiring panel. He published both network algorithms in a single paper in 1959.[3]
When Dijkstra and Maria Debets married in 1957, the marriage rites required him to state his profession. When he stated that he was a programmer, the authorities objected that there was no such profession, and the marriage certificate instead identifies him as a theoretical physicist.
While at the Mathematical Center, Dijkstra worked on the very important “real-time interrupt” problem, which became the topic of his Ph.D. thesis [2]. Several computer manufacturers of the day were facing the same problem, but they had not approached the problem with the rigor that Dijkstra applied to it.
At the Mathematical Center, Dijkstra and J.A.Zonneveld developed the first compiler for Algol-60, a high-level programming language designed by an international committee. Completed in August 1960, their compiler predates the second Algol-60 compiler by more than a year. One of Algol-60’s great innovations, for which Dijkstra was instrumental, was the explicit introduction of recursion. He was probably the first to introduce the notion of a “stack” for translating recursive programs, reporting this seminal work in a short article [4]. In the Oxford English Dictionary, the terms “vector” and “stack” in a computing context are attributed to Dijkstra.
In 1962 Dijkstra was appointed Professor of Mathematics at the Eindhoven University of Technology. There he built the THE operating system (named for the university, then known as Technische Hogeschool te Eindhoven), which has influenced the design of many subsequent operating systems. It introduced a number of design principles which have become part of the working vocabulary of every professional programmer. Introducing the reprint of Dijkstra’s article on the THE operating system in the 25th Anniversary issue of Communications of the ACM, the Editor-in-Chief wrote, “This project initiated a long line of research in multilevel systems architecture—a line that continues to the present day because hierarchical modularity is a powerful approach to organizing large systems.”
In 1968, Dijkstra published a brief letter to the editor in Communications of ACM, titled “Go To statement considered harmful”[5], arguing that the GO TO statement, found in many high-level programming languages, is a major source of errors, and should therefore be eliminated. There ensued a giant commotion in the computing community, with combatants taking positions on all sides of the issue. The debate has long since subsided; programming languages now provide alternatives to the GO TO. Few programmers today use it liberally, and most never use it at all.
Around this time, Dijkstra was beginning to formulate some of his early ideas about programming as a mathematical discipline. He pointed out that software productivity and reliability is closely related to rigor in design, which eliminates software flaws at an early stage. He was particularly impressed by the immensity of the so-called “software crisis” when he attended the famous 1968 NATO Conference on Software Engineering, the first conference devoted to the growing epidemic of software delivered late, over budget, and full of flaws. Convinced that programming methodology should become a scientific discipline, he decided to study how to avoid complexity in software designs.
Dijkstra’s “Notes on Structured Programming,” circulated to a few friends for their comments and soon became a sensation, and major corporations initiated programs based on his ideas to integrate rigorous practices into their programming projects. Subsequently published [1] and still in print after nearly 40 years, this work has had far-reaching impact on all areas of computer science, from the teaching of the first courses in programming to the design of complex software. Mathematical analyses of program design and specifications have become central activities in computer science research.
Dijkstra’s acceptance speech for the 1972 ACM Turing Award, titled “The humble programmer”[6], includes a vast number of observations on the evolution of programming as a discipline and prescriptions for its continued growth. It is required reading for any aspiring computer scientist.
In August 1973 Dijkstra joined Burroughs Corporation as a Research Fellow. His duties consisted of consulting at some of the company’s research centers a few times a year and pursuing his own research. Among his significant contributions from this period is the development of a theory of nondeterminacy [7], a concept outside traditional mathematics. Dijkstra was the first to observe not only that nondeterminacy is central in computations whose components interact asynchronously, but also that even when no asynchrony is involved, nondeterminacy is an effective tool for reasoning about programs and simplifying program design.
His other major contribution during this period was the development of “predicate transformers” as a basis for defining program semantics and as a tool for deriving programs. His ideas refined the earlier ideas of C. A. R. Hoare for an axiomatic basis of computer programming. He expounded these ideas along with nondeterminacy in A Discipline of Programming [8], which has been identified by the Science Citation Index as a “Citations Classic”.
The Burroughs years were Dijkstra’s most prolific in terms of research articles. He wrote nearly 500 documents in the EWD series, most of them technical reports, for private circulation within a select group.
As a frequent visitor to the Burroughs Research Center in Austin, Texas starting in the late 1970s, Dijkstra had become familiar with the Department of Computer Science of the University of Texas at Austin. In 1984 Dijkstra accepted an appointment as the Department’s Schlumberger Centennial Chair.
During his eighteen years in Austin, Dijkstra continued as a prolific researcher. Having earlier embarked on a long-term project for “Streamlining Mathematical Arguments”, in Austin he co-authored a book on predicate calculus [9] advocating a “calculational proof style” for mathematical arguments. He continued to apply his method in a number of diverse areas: coordinate geometry, linear algebra, graph theory, designs of sequential and distributed programs, and many others.
The years in Austin saw Dijkstra at his best as a teacher and mentor for a generation of undergraduate and graduate students. From his days in the Eindhoven University of Technology he had thought deeply about how computer science should be taught, and Austin provided him the opportunity for trying out his ideas [10]. He enjoyed the experience, appreciating “... brilliant students who made it a challenge and a privilege to lecture for them” [11]. He urged universities not to shrink from the challenge of teaching radical novelties.
On the occasion of Dijkstra’s 60th birthday in 1990, the Department of Computer Sciences organized a two-day seminar in his honor. Speakers came from all over the US and Europe, and a group of computer scientists contributed research articles which were edited into a book [12].
Dijkstra retired from active teaching in November 1999. To mark the occasion and to celebrate his forty-plus years of seminal contributions to computing science, the Department of Computer Sciences organized a symposium, which took place on his 70th birthday in May 2000. The symposium was attended by a large number of prominent computer scientists as well as current and former students.
Returning to The Netherlands in February 2002, Dijkstra died in Nuenen on 6 August 2002.
Dijkstra’s Aphorisms and Epigrams
Dijkstra was famous for his wit and eloquence, such as in his remark:
The question of whether computers can think is like the question of whether submarines can swim;
or his advice to a promising researcher, who asked how to select a topic for research:
Do only what only you can do;
and his remark in his Turing Award acceptance speech:
In their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind.
Compiled below are a few more of Dijkstra’s other memorable epigrams.
The tools we use have a profound and devious influence on our thinking habits, and therefore on our thinking abilities.
Brainpower is by far our scarcest resource.
Program testing can at best show the presence of errors but never their absence.
The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague.
So-called natural language is wonderful for the purposes it was created for, such as to be rude in, to tell jokes in, to cheat or to make love in (and Theorists of Literary Criticism can even be content-free in it), but it is hopelessly inadequate when we have to deal unambiguously with situations of great intricacy, situations which unavoidably arise in such activities as legislation, arbitration, mathematics or programming. (foreword to Teaching and Learning Formal Methods, edited by C. N. Dean and M. G. Hinchey, Academic Press, 1996)
Computer Science is no more about computers than astronomy is about telescopes.
Being abstract is something profoundly different from being vague.
Nothing is as expensive as making mistakes.
In the practice of computing, where we have so much latitude for making a mess of it, mathematical elegance is not a dispensable luxury, but a matter of life and death.
If 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself, Dijkstra would not have liked this, well that would be enough immortality for me.
Acknowledgment: This profile borrows much from the Memorial Resolution solicited by the Faculty Council of The University of Texas at Austin.
荣誉和奖项。
荷兰皇家艺术与科学院院士（1971年）；英国计算机学会杰出院士（1971年）；AFIPS哈里-古德纪念奖（1974年）；美国艺术与科学院外籍荣誉会员（1975年）；IEEE计算机学会计算机先锋奖（1982年）；ACM/SIGCSE计算机科学教育杰出贡献奖（1989年）；ACM研究员（1994年）；ACM有影响力论文奖。"Self-stabilizing systems in spite of distributed control" Communications of the ACM 17, Vol. 11 (1974), pp.643-644, 2002（2003年这个年度奖改名为Dijkstra奖）。
1948年高中毕业，打算成为一名理论物理学家，Dijkstra认为使用电子计算机的能力可能是有利的。在阿姆斯特丹数学中心的三年编程经历使他确信，编程的智力挑战超过了理论物理学，但哪里有健全的知识体系可以支持编程成为一门智力上值得尊敬的学科呢？他的老板A. van Wijngaarden说服他，在未来的几年里，他可以成为使编程成为一门值得尊敬的学科的人之一。迪克斯特拉以最快的速度完成了他的物理学研究，他放弃了物理学而选择了编程。
在数学中心，一个主要项目是建立ARMAC计算机。在1956年的正式启用仪式上，Dijkstra设计了一个程序来解决一个对非技术观众来说很有趣的问题。给定一个连接城市的道路网络，两个指定城市之间最短的路线是什么？最著名的算法的运行时间随着网络规模的立方而增长；Dijkstra的算法的运行时间只随着平方而增长。当Dijkstra与他的未婚妻Maria (Ria) C. Debets在咖啡馆的阳台上放松时，他的最短路径算法在20分钟内开发出来，现在仍然被用于计算机通信的分组交换软件等应用中。
1962年，Dijkstra被任命为埃因霍温科技大学的数学教授。在那里，他建立了THE操作系统（以大学命名，当时称为Technische Hogeschool te Eindhoven），该系统影响了许多后续操作系统的设计。它引入了一些设计原则，这些原则已经成为每个专业程序员工作词汇的一部分。在《ACM通讯》25周年纪念刊上，主编在介绍Dijkstra关于THE操作系统的文章时写道："这个项目开启了多级系统架构的长线研究--这条路线一直延续到今天，因为分层模块化是组织大型系统的强大方法。"
所谓的自然语言对于它被创造出来的目的来说是非常好的，比如说用它来粗鲁，用它来讲笑话，用它来欺骗或做爱（文学批评理论家甚至可以用它来表达内容），但是当我们必须明确地处理非常复杂的情况时，它就无可救药地不够了，这些情况在立法、仲裁、数学或编程等活动中不可避免地出现。(C. N. Dean和M. G. Hinchey编辑的《形式化方法的教与学》前言，学术出版社，1996年)
