Edsger Wybe Dijkstra

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.

Author: Hamilton Richards

---

Turing Lecture: The humble programmer