Dr. Edsger Dijkstra, pioneer in Computer Science, died August 6 in his home in Nuenen, the Netherlands.
Dijkstra launched the first salvo in the battle for structured programming with his March 1968 letter to The Communications of the ACM entitled “Go To Statement Considered Harmful”. He is the inventor of “Dijkstra’s algorithm”, an efficient way to find the shortest path in a graph. He is credited with inventing the operating system concept of semaphores (and the Dining Philosophers problem, used to illustrate the need for semaphores or some other mutual exclusion mechanism).
To my mind, his most important contribution is: (from this obituary):
Most of his writings have been archived at the University of Texas. They are wondrous to read if you are interested in the science of computation in any way.
He was cranky, cantankerous, strongly opinionated, and nearly always right. He will be sorely missed in the field.
My area or research significantly intersected his. So at conferences people sat around and told Dijkstra stories.
He was a strange, strange person. I did not know a single person how knew him and had anything particularly nice to say.
I know you’re not supposed to speak ill of the dead and all, but he really held the field back. He’s one of the dinosaurs that Kuhn talked about that have to literally die off so that the next generation of new, better, ideas can be heard.
I don’t know of a single research result of his that would earn him any permanence viewed objectively. (A lot that he is credited with had been done earlier by less publicity seeking individuals.)
The closest contact I had with him was his referee report for “that 2 page paper that made me famous”. Beautiful calligraphic handwriting but of no use whatsoever.
Speaking of which, what can you say about a person that deliberately tried to ruin peoples’ careers over their handwriting?
With his uncompromising insistence that computer programming is more akin to proving mathematical theorems than guessing lottery numbers? With his bizarre belief that programs should always be both elegant and correct? How did someone as progressive as Dijkstra “hold the field back”?
What are the new, better ideas? Shoddy, buggy, slow, bloated, late-to-market software? That’s the current state-of-the-art–Dijkstra railed (shrill as he often was) against exactly the factors that led to that situation. He wasn’t afraid to tell us the truths that might hurt (the title of one of his most famous pieces was: “How do we tell truths that might hurt?”).
As a professional working in programming language design, I have always believed he was exactly right when he said (in “How do we tell truths that might hurt?”):
Sadly, you may be right. This field is too eager to discard its history. The same will probably be said about Knuth, McCarthy, Backus, Hoare, and Wirth.
This is the man who discovered the shortest spanning tree algorithm. He invented semaphores. He helped invent monitors (along with Per Brinch Hansen–I have Brinch Hansen’s The Achitecture of Concurrent Programs here, and he gives Dijkstra much of the credit). As the designer and implementor of the first Algol 60 compiler he invented much of the modern compiler architecture. He discovered the three-color marking algorithm used in incremental and real-time garbage collection.
Here’s how I’ll be remembering him:
Of course, if you’re a big fan of “quick and dirty” or you just want your GOTOs back, then you can finally celebrate.
I agree with Newton meter for the most part. Dijkstra was important and generally correct. I do disagree with Dijkstra on the GOTO issue, in that I feel that all tools have a place and you don’t get rid of nails simply because you now have screws. GOTO’s are good things when used properly. That said, he was more often right than wrong.
Speaking of Knuth, I remember back when I was in college, and hated Knuths insistance on superior commentation in programming. Then I had to maintain someone elses code as part of my job as a test engineer…I now comment religiously. I and am sad to see that in programming courses that intelligent commenting is giving way to short // comments in the code, rather than requirements of explainations as to what is being done. I look at Knuth in a new light now.
I don’t know what Algorithm book you have, but the ones I teach out of give it as “Prim’s Algorithm”, with a citation almost a decade earlier than Dijkstra. The same algorithm has been cited by Tarjan and others going back even more decades.
Semaphores (and correctness). Well, everybody knew about locks. With locks you can protect counters. The only reason semaphores are so well known is because of the weird Ice Age effect in OS books since the 70s. Nothing original and poorly specified. Lamport directly inquired about the exact specification for a paper he was writing a couple years ago and did not get a satisfactory response. For all of Dijkstra’s wailing about precision he did not practice what he preached. If you have read his research papers, you will be appalled that this same person is touted as a paragon of Mathematical precision. In regards to that referee report he did for my paper, he did a half-backed “improved” proof for only part of the problem. A lot of “and similarly” was sprinkled throughout.
Monitors. Brinch-Hansen became famous for sending out letters to people who mistakenly gave credit to others for Monitors. (Despite Tony Hoare’s explicit kudos to B-H in his Monitors paper.) Dijkstra and Monitors? Plueeze.
You will find many people with a vastly different take on Dijkstra and compilers. Many people. The consensus would range from “no effect” to “what are you on?”
3-color GC. It took me 15 minutes as a grad student to figure out how to do this much simpler with just 2 colors. A lot of other people did likewise. A lot. Note also that it was a multi-author paper. Several bright people contributed to fix an initially buggy algorithm. A classic example of Dijkstra not doing things well.
And that’s just scratching the surface. There are a lot of horrible things done out there because people don’t know that there are simpler, better ways. Just read an 2002 OS book and compare it to a 1975 OS book. Long overdue for change.
I laugh that you would think that an intelligent person might therefore dismiss Knuth. After all, it was Knuth that wrote the most famous and influential response to Dijkstra’s paper. Most anti-Dijkstra people are therefore pro-Knuth on that issue.
We are still waiting for Programming Languages to properly incorperate the features necessary for simple structered programming that Knuth discussed. (The Java “throw/catch” shows how, years later, such things can still be badly done.)
I bow to your judgement. I had initially considered MPSIMS, but I didn’t feel that it was either mundane or pointless. I think ftg shows that there is a difference of opinion, though I suspect things will quickly get pretty mundane and pointless (starting with this post).
ftg, interesting views on the history of computer science; I find your recollections and opinions valuable. I would caution you against allowing your personal opinion of Dijkstra to excessively cloud your assessment of his technical achievements; those ought to be judged more or less as anyone else’s would. Your posts lead me to believe that if Dijkstra invented or discovered something that was later improved on by others, you would say “there’s an example of Dijkstra screwing up”; and if Dijkstra himself improved upon the work of others, you would say “there’s an example of Dijkstra passing off other’s work as his own”. It seems as if you expect him to be simultaneously a pioneer and (nearly) perfect. That’s a pretty tall order, but I would claim that he was often one or the other, and perhaps, at rare times, both.
A disclaimer: I never had the opportunity to meet or have other contact with the man. My opinion of him is based solely on his writings, and mostly his opinion pieces. And to be honest, I must say that I tend to agree with his opinions. I certainly recognize that this isn’t universal–for instance, you seem to disagree very much with some of his opinions.
Since we’re officially mundane and pointless now, I would rather explore his technical achievements, upon which we can hopefully find some common ground. I would be quite interested if you were able to correct any of my misapprehensions or fill in any gaps.
Dijkstra’s Algorithm?. I found a few references online that dated it to 1956 (here, here, and here for instance), but it appears to have been first published in 1959 (“A note on two problems in connection with graphs.” Numerische Mathematik 1 p269-271, 1959). Dijkstra used two variations on the same algorithm in order to solve both the shortest path and the minimum spanning tree problems. Prim only treated minimum spanning tree (which was first published in his “Shortest connection networks and some generalizations”, Bell System Technical Journal 36:1389-1401, 1957).
According to Introduction to Algorithms by Cormen, Leiserson, and Rivest, first edition (they call the MST version “Prim’s algorith” and the shortest path version “Dijkstra’s algorithm”):
I do not have a copy of the original Dijkstra paper, so I can’t tell whether he was aware of Prim’s (and Jarník’s) work on MSTs or not. In either case, it appears that the shortest path algorithm, at least, is due to Dijkstra.
Semaphores. It does seem to be true that “everybody knew about locks”, but with locks you can still encounter race conditions (which can be fixed by the addition af a wakeup waiting bit–see, e.g.Modern Operating Systems, by Tanenbaum, but only for two processes). According to J. Anderson, “Lamport on Mutual Exclusion: 27 Years of Planting Seeds”, in Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing, pp. 3-12, August 2001 (available here):
The Dijkstra algorithm was published in E. Dijkstra, Solution of a problem in concurrent programming control. Communications of the ACM, 8(9):1965. The Knuth algorithm was published in D. Knuth, Additional comments on a problem in concurrent programming control. Communications of the ACM, 9(5):321-322, 1966. Both articles are available from the ACM digital library, which requires a subscription.
Semaphores were first described in Dijkstra’s Cooperating Sequential Processes, which I would claim is technically quite influential. It can be found as EWD 123 here. I am interesting in more about your Lamport/semaphore specification anecdote. What exactly is did Lamport find poorly specified about semaphores–the original treatment is pretty clear:
It’s not clear to me why Leslie Lamport (of all people!) would find semaphores underspecified, and why he would expect Dijkstra to provide him with a specification rather than carrying out this research on his own.
So, semaphores were invented by Dijkstra, giving the first solution to an important problem. Influential? I think so.
Monitors. “Dijkstra and Monitors? Plueeze.” Huh? Brinch Hanson writes, in the preface to The Architecture of Concurrent Programs:
The Dijkstra paper cited is available here as EWD 310: “Hierarchical ordering of sequential processes”. Perhaps Dijkstra invented two major synchronization mechanisms?
Compilers. ‘The consensus would range from “no effect” to “what are you on?”’ That’s way too harsh. Dijkstra arguably implemented the first Algol-60 compiler (though I would be one who might argue with it–I would consider Neliac, JOVIAL, and MAD to all be “Algol 60”). The implementation is described in “An Algol 60 Translator for the X1”, available here as MR35/61. He seems to have made the first discovery of the idea that lexical scope can be implemented in the control stack (that’s why I ebulliently claimed he “invented much of the modern compiler architecture”). McCarthy’s LISP had local (“automatic”) variables implemented in the control stack as early as 1958 (thus permitting recursion in a useful way, unlike early FORTRAN), but it had dynamic scope (yuck!). This is all described in E. W. Dijkstra, “Recursive programming”, Numerische Mathematik, 2 (1960) 312-318. (This paper is frequently cited, I believe I can even dig out a copy reprinted in a 1967 collection). And no less than Aho, Sethi, and Ullman credit him with inventing displays (and thus indirectly and of interest to my own research, display closures). So, he invented stack allocation, which can be seen to lead directly to such things as closure conversion and register allocation. From Compilers: Principles, Techniques, and Tools (the Dragon book):
From a really neat 1993 paper by John Reynolds entitled “The Discoveries of Continuations”:
The Dijkstra quote is from “Recursive Programming” (1960).
A related aside: Peter Naur’s “The European Side of the Last Phase of the Development of Algol 60”, from the first ACM History of Programming Languages conference (available with subscription from the ACM digital library) cites Dijkstra numerous times in connection with the design of Algol 60. Many of these are in conjunction with recommendations made by a 1959 UNESCO conference in Paris consisting of Edsger Dijkstra, Alan Perlis, Willy Heise, and Klaus Samelson. It would be surprising if Dijkstra were just a fly on the wall at this meeting with Perlis, Heise, and Semelson doing all the design work (I say surprising based on how opinionated Dijkstra turned out to be post-1959). A reading of the Naur article leads to the conclusion that Dijkstra had an effect on the design of Algol 60, which was an influential development in Computer Science indeed.
3-color marking. It’s been a while for garbage collection and me. You mean to say that incremental garbage collection (where the collector and mutator run as coroutines) can be achieved with two-color marking (essentially, vanilla mark-sweep)? That’s interesting–do you have a cite (I say this not as a challenge, but because I’m interested in filling gaps in my own knowledge). Here’s a case where Dijkstra is in trouble with you, because he needs to collaborate with Lamport, Martin, Scholten, and Steffens? I need more convincing to believe that the idea of 3-color marking (which certainly appears to be due to Dijkstra) is not influential.
GOTO and other sundries. Ahhh. Did Knuth disagree with Dijkstra about this? I think you’re talking about his “Structured Programming with go to Statements”, Computing Surveys 6, 4 (Dec 1974) 261-301. (available from the ACM digital library, with subscription). I always read that as essentially agreeing with Dijkstra in philosophy. Note that Knuth’s design methodology (structured refinement–first get it correct but simple, then optimize) is also championed by Dijkstra (e.g. in EWD 703: A tutorial on the split binary semaphore, available here).
A reading of “GOTO considered harmful” (the title was written and placed on the letter by a CACM editor) shows that Dijkstra is not exactly the screaming fanatic about the issue that some think. And he himself was not under any illusion that he had made a new discovery (he credits, among others, Peter Landin and Christopher Strachey, who I would place among the giants of the field). An interesting recollection by Douglas McIlroy is contained in Reynolds’ “The Discoveries of Continuations”:
In addition (and I almost forgot), I would classify Dijkstra’s treatment of levels of abstraction and abstract data types (e.g. E. W. Dijkstra, “The Structure of the ‘THE’-multiprogramming System”, Communications of the ACM, 11:5, May 1968, 341-346.) as “influential”, even if not entirely “new”.
