Edsger Wybe Dijkstra: His Life, Work, and Legacy

by Krzysztof R Apt, Tony Hoare

Edsger Wybe Dijkstra (1930–2002) was one of the most influential researchers in the history of computer science, making fundamental contributions to both the theory and practice of computing. Early in his career, he proposed the single-source shortest path algorithm, now commonly referred to as Dijkstra’s algorithm. He wrote (with Jaap Zonneveld) the first ALGOL 60 compiler, and designed and implemented with his colleagues the influential THE operating system. Dijkstra invented the field of concurrent algorithms, with concepts such as mutual exclusion, deadlock detection, and synchronization. A prolific writer and forceful proponent of the concept of structured programming, he convincingly argued against the use of the Go To statement. In 1972 he was awarded the ACM Turing Award 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.” Subsequently he invented the concept of self-stabilization relevant to fault-tolerant computing. He also devised an elegant language for nondeterministic programming and its weakest precondition semantics, featured in his influential 1976 book A Discipline of Programming in which he advocated the development of programs in concert with their correctness proofs. In the later stages of his life, he devoted much attention to the development and presentation of mathematical proofs, providing further support to his long-held view that the programming process should be viewed as a mathematical activity.

In this unique new book, 31 computer scientists, including five recipients of the Turing Award, present and discuss Dijkstra’s numerous contributions to computing science and assess their impact. Several authors knew Dijkstra as a friend, teacher, lecturer, or colleague. Their biographical essays and tributes provide a fascinating multi-author picture of Dijkstra, from the early days of his career up to the end of his life.

Genres: Biography

534 pages, Kindle Edition

Published July 14, 2022

Reviews

[Behrooz Parhami]

Edsger Wybe Dijkstra [1930-2002] made fundamental contributions to the theory and practice of computing. In this book, computer scientists, including Dijkstra himself, friends, mentors, and colleagues, provide both biographical and technical narratives on the influential computer scientist. For the book's table of contents, see:

https://dl.acm.org/doi/book/10.1145/3...

Dijkstra won the Turing Award in 1972 "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."

He advocated for the development of programs in concert with their correctness proofs. He also developed important ideas in fault-tolerant computing and in the domain of developing and presenting mathematical proofs of computer programs. Dijkstra remains one of the most quotable and most-quoted computer scientists. Here are three of his statements that are my favorites:

- "Computer science is no more about computers than astronomy is about telescopes.

- "The question of whether a computer can think is no more interesting than the question of whether a submarine can swim."

- "Program testing can be used to show the presence of bugs, but never to show their absence!"

He viewed programming as a mathematical activity, recommending that second-rate mathematicians had better limit themselves to pure math, because programming is one of the most-difficult branches of applied mathematics.