Edsger W. Dijkstra - Life and Work

Life and Work

Born in Rotterdam, Dijkstra studied theoretical physics at Leiden University, but quickly realized he was more interested in computer science. Originally employed by the Mathematisch Centrum in Amsterdam, he held a professorship at the Eindhoven University of Technology, worked as a research fellow for Burroughs Corporation in the early 1980s, and later held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin, in the United States. He retired in 2000.

Among his contributions to computer science are the shortest path algorithm, also known as Dijkstra's algorithm; Reverse Polish Notation and related Shunting yard algorithm; the THE multiprogramming system, an important early example of structuring a system as a set of layers; Banker's algorithm; and the semaphore construct for coordinating multiple processors and programs. Another concept due to Dijkstra in the field of distributed computing is that of self-stabilization – an alternative way to ensure the reliability of the system. Dijkstra's algorithm is used in SPF, Shortest Path First, which is used in the routing protocols OSPF and IS-IS.

While he had programmed extensively in machine code in the 1950s, he was known for his low opinion of the GOTO statement in computer programming, writing a paper in 1965, and culminating in the 1968 article "A Case against the GO TO Statement", regarded as a major step towards the widespread deprecation of the GOTO statement and its effective replacement by structured control constructs, such as the while loop. This article was retitled by editor Niklaus Wirth to "Go To Statement Considered Harmful", which introduced the phrase "considered harmful" in computing. This methodology was also called structured programming, the title of his 1972 book, coauthored with C.A.R. Hoare and Ole-Johan Dahl. Dijkstra also strongly opposed the teaching of BASIC.

Dijkstra was known to be a fan of ALGOL 60, and worked on the team that implemented the first compiler for that language. Dijkstra and Jaap Zonneveld, who collaborated on the compiler, agreed not to shave until the project was completed. It was one of the first compilers supporting recursion.

Dijkstra wrote two important papers in 1968, devoted to the structure of a multiprogramming operating system called THE, and to Co-operating Sequential Processes.

From the 1970s, Dijkstra's chief interest was formal verification. The prevailing opinion at the time was that one should first write a program and then provide a mathematical proof of correctness. Dijkstra objected noting that the resulting proofs are long and cumbersome, and that the proof gives no insight on how the program was developed. An alternative method is program derivation, to "develop proof and program hand in hand". One starts with a mathematical specification of what a program is supposed to do and applies mathematical transformations to the specification until it is turned into a program that can be executed. The resulting program is then known to be correct by construction. Much of Dijkstra's later work concerns ways to streamline mathematical argument. In a 2001 interview, he stated a desire for "elegance", whereby the correct approach would be to process thoughts mentally, rather than attempt to render them until they are complete. The analogy he made was to contrast the compositional approaches of Mozart and Beethoven.

Dijkstra was one of the early pioneers in the field of distributed computing. In particular, his paper "Self-stabilizing Systems in Spite of Distributed Control" started the sub-field of self-stabilization.

Many of his opinions on computer science and programming have become widespread. For example, he coined the programming phrase "two or more, use a for," alluding to the rule of thumb that when you find yourself processing more than one instance of a data structure, it is time to consider encapsulating that logic inside a loop. He was the first to make the claim that programming is so inherently complex that, in order to manage it successfully, programmers need to harness every trick and abstraction possible. When expressing the abstract nature of computer science, he wrote

The job was actually beyond the electronic technology of the day, and, as a result, the question of how to get and keep the physical equipment more or less in working condition became in the early days the all-overriding concern. As a result, the topic became —primarily in the USA— prematurely known as "computer science" —which, actually is like referring to surgery as "knife science"— and it was firmly implanted in people's minds that computing science is about machines and their peripheral equipment. Quod non .

He died in Nuenen on August 6, 2002 after a long struggle with cancer. The following year, the ACM (Association for Computing Machinery) PODC Influential Paper Award in distributed computing was renamed the Dijkstra Prize in his honor.