In Memoriam Edsger Wybe Dijkstra (1930-2002)


(written by Mario Szegedy, Aug 10, 2002)

A few days ago the news that Edsger Wybe Dijkstra, the founding father of structured programming and many other inventions had passed away sent a shock wave throughout the computer science world. This last stunt however was no more shocking than all the other things he has done throughout his controversial career that he started as a visiting student in Cambridge in 1951. In this page I would like to convey a little observation I made by skimming through a couple of his technical reports prompted by the sad news that he won't add more to the thousand-something of these. I believe they might illuminate his personality as much as his scientific intentions.

We in computer science, like in a big family all know something about Dijkstra. If nothing else, we have taken to our heart his often quoted doctrine of not to use the goto instruction, else we are supposed to be condemned to eternal debugging in our after-life. Did Dijkstra earn his fame via this doctrine, through his ingenious shortest path algorithm or through developing the structured programming framework? Or did he earn it through other things, eg. spearheading the ALGOL project?

None. The most notable about Dijkstra was that he not only invented doctrines; he also lived by them. Opinions, different than his, met with his greatest disapproval, and he related to them in a famously obnoxious manner. He found his own convictions so compelling he was not even willing to argue for them. A famous one:

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

Dijkstra seemed to believe in the all-mightiness of syntax. Not every syntax of course, just the elegant one. Elegance was a criterion he also held for mathematics:

"The traditional mathematician recognizes and appreciates mathematical elegance when he sees it. I propose to go one step further, and to consider elegance an essential ingredient of mathematics: if it's clumsy, it's not mathematics." (if you want to read more wise-crackers of Dijkstra, go to here)

Here I have arrived at the point I am about to make: Dijkstra seem to have held the view that there is a middle ground, where precise syntax of a document can be coupled with enjoyable style. Precision, comprehensibility, elegance (conciseness) and sharpness are not mutually exclusive. This refers not only to software, but also to books and articles in computer science and math.

Skimming through his tech reports is breadth-taking. The wit and style with which he expresses himself make us forget that he also wants to make his writings syntactic feasts. Three reports of his of the year 1993 ( 1154, 1155, 1155a, ) caught my eyes particularly, because they represent a lesser known side of Dijkstra: him as a mathematician. The style of these articles is at the first sight rather strange to an eye trained on usual mathematics texts. The quoted documents, written in Dijkstra's clean and neat hand-writing, work out a well known fact: every prime of the form 4k+1 can be uniquely decomposed as the sum of two squares. The uniqueness is the subject of 1155 and 1155a.

Why did Dijksra bother to reprove this simple number-theoretic fact? Exactly to make a point about the style. There are some small points I like, and I think they should be included into our every-day mathematical formalism. One of these is quoting the reason of every equation:

(qr)2 + (st)2 + (qs)2 + (rt)2 = {algebra}  (q2 + t2)× (r2 + s2)

You might think that if an article is written with so many painstaking details it is boring. Not at all, when written by Dijksrtra. He emphasizes facts that he thinks are interesting, and they really are! Who else would think of the formula (a+b)2 + (a-b)2 = 2(a2 + b2) as a one-one correspondence in between square decompositions of n and those of 2n? Only Dijkstra. The assessment of his efforts is put in his closing remarks:

"The above argument is reported because it provides a striking example of a proof in which the algebra is totally trivial, while all the subtlety has been invested into the decision what to name."

Interestingly, some time ago I pondered about an idea of developing a standardized language for mathematical proofs and articles. I envisioned an entirely precise language that would relate to predicate calculus in the same way as C (or C++) relates to the machine language. The obvious benefit is automated proof checking. The level of the language would be high enough for humans to use it too. I conveyed these ideas to Pierre Deligne, himself a widely acclaimed mathematician, whos reply in summary was: The publications of the Bourbaki group comes perhaps the closest to realizing this idea. But proofs cannot be expressed in a completely standardized human-like language, because the most novel results, exactly the ones that we want to read the most, require new forms of expression.

Reading his reports, Dijkstra seems to be trying to achieve something along the above lines, but in his efforts of making his write-up "algebraically trivial" he misses the major point an algebraist would never miss: There is a mysterious structure, the so-called Gauss integers, that stands behind all the rules of decomposing numbers into sums of squares. For a person loving algebra any explanation not involving this structure would amount to not touching the essence. This seems to justify Deligne's argument: if we try to gain too much on syntax, we might miss the deeper point. Dijksra, born to mathematician and chemist parents and having a distinguished educational record in both math and computer science of course does not miss the point because of the lack of mathematical sophistication. He simply believes he makes the better choice:

"Constructive proofs have a number of potential attractions: They give more (viz. the witness), they can be simpler by avoiding the detour of the counting, and, finally, their design gives us the opportunity to draw on our experience in program construction. This time, however, that the same experience suggests a non-constructive proof that (0) [(x,y): x2 + y2 = p] can be solved, for a constructive proof would via the witness effectively boil down to a factorization - in the complex plane - of p since x2 + y2 = (x + yi)(x - yi), and all factorization algorithms I know are non-constructive in the sense that they are no more than search algorithms that work equally well if there are no factorizations to be found. So I propose to pursue the demonstrandum in the form < N(x,y) :: x2 + y2 = p> ¬ = 0"

In other words he tries to sell the idea to the reader that the introduction of abstract algebraic structures generates non-constructivity, at least from a computer science point of view. Strongly debatable point. Whether it worths the effort to write a twenty pages report on a simple problem even if as he claims the original proof "commits the sins of omission" and "pulls a number of sizable rabbits out of the hat" is unclear, but the product is a nice piece of writing. To come up with a language which is readable for computers and enjoyable for humans would have been a major breakthrough, and he is close to reaching that goal. But he had written all of this just for fun!

These are not the only reports with mathematical content Dijkstra wrote. There is a large number of them. In some of these reports we see him worried about how many characters the shortest mathematical proof for a problem exactly contains, and about what proofs can be easily checked by computer. He often reproves known theorems and rewrites them into his own style. He does this for instance with the well known theorem of Turan that bounds the number of edges of triangle-free graphs. His efforts to me indicate that he has gone trough a lot of pain to understand what it takes to capture mathematical ideas in writing, and struggled to find the best formalism, which he believed came hand in hand with the mathematical thought itself. I am certain, if Dijkstra had another life in to live this century, he would start a second career in automated theorem proving.

Of course the majority of his reports are on compilers and on issues for which he is well known. With the particular selection I wanted to demonstrate: the legacy of Dijkstra extends much farther than his well known accomplishments, and will keep treasure-hunters busy for a while. His philosophy about how to paint the most elegant and accurate picture of the world shines through all his works. Of the thousand plus reports of him I randomly peeped into none seemed dull or boring. Some of them might contain errors, but these human readers can tolerate more. I do not know whether these are clarified texts: they seem to be written in one impulse, containing very few insertions or deletions. What is certain is that the elegant presentation and the convincing power of virtually all of Dijksra's documents spiced with his unique personal style have much contributed to his world wide recognition.