I remember Edsger Dijkstra (1930 – 2002)

In 1966 I became a PhD student of A. van Wijngaarden at the Computational Department of the Mathematical Centre in Amsterdam. Whatever my topic was going to be, it was clear that my job would be to program. There used to be one computer, the Electrologica X1. Shortly before my arrival a much faster and bigger successor was added: the X8 from the same manufacturer. The language was Algol 60.

Most organizations have a strong attachment to a single programming language. At the Mathematical Centre this attachment was even stronger than usual. My new colleagues proudly pointed to the cover of the Revised Report on the algorithmic language Algol 60, which showed van Wijngaarden among the members of the committee that had defined the language. Moreover, they told me, as soon as the report was finalized early 1960, a race was on between Peter Naur and his team at Regnecentralen in Copenhagen and Dijkstra at the Mathematical Centre; upon which Dijkstra vowed not to shave until the project was finished; upon which Dijkstra finished the compiler by himself in six weeks, in assembler, on the fly inventing new compilation techniques (such as required for Call By Name), handily beating the Regnecentralen team.

Thus was the story that had gotten better in the telling ever since Dijkstra left the Mathematical Centre in 1962 to become a professor at THE, the engineering school in Eindhoven in the Netherlands. In 2000 I returned to what used to be the Mathematical Centre. During the year I was there, a visit by Dijkstra was announced. As I was curious about the origins of the Mathematical Centre’s early Algol 60 compiler, I e-mailed Dijkstra in advance the above story with the request to meet him to hear his side. I got a reply by e-mail, which is just as well because the brief return of the prodigal son to the Netherlands turned out to be a tightly orchestrated whirlwind media event.

Here is Dijkstra’s reply (my translation from the Dutch original):

Allow me to make a few corrections.

(i) I have never competed with Peter Naur. (I was raised somewhat puritanically: we had to try our hardest and give the most, but we were not allowed to compete. I am still grateful to my parents for this education.) When we had decided on the structure of the object program, the three of us (that is, Aad van Wijngaarden, Jaap Zonneveld and myself) went to Copenhagen to check our plans with Peter, just to make sure, before we started coding. Of course Peter’s group was the only one with which such a discussion was possible. I remember being surprised later (and somewhat disappointed) that Peter’s group only finished in the summer of 1961. By the way, Peter made this compiler, I think, not for the GIER [the machine built by Regnecentralen], but for a larger machine of Swedish origin. I thought that Peter’s compiler for the GIER was his second.

(ii) We were to implement with five of us: Aad van Wijngaarden, Jaap Zonneveld, Joke Feringa, Freek Barning, and myself. Feringa and Barning left quite soon. Van Wijngaarden did not contribute — on the contrary! — but pretended otherwise to the outside world. I had been warned by Bram Loopstra and Carel Scholten [hardware designers formerly at the Mathematical Centre] that the little chief was not adverse to showing off other peoples’ work as his own. I was not in the mood to let that happen to me. At that time Jaap, van W. and I were clean-shaven; Jaap had a moustache. To make clear that the two of us were doing the work, Jaap and I decided not to shave until the implementation worked, being convinced that van W. would not follow us in this. In this way we made it clear who was responsible for the Algol compiler. Thus it happened; that was around Pentecost [a European holiday six weeks after Easter]. In August the system worked. Jaap got rid of his moustache and beard soon after; I retained them.

(iii) The Algol compiler was, by the way, the occasion for me to bang my fist on the table in van Wijngaarden’s office. (I have not done so ever again.) Van W. wanted us to model the compiler on what Harry D. Huskey had shown us that fall. That was such a chaotic mess that I told van W. that if he wanted such a compiler, he would have to do it himself and that I refused to have anything to do with such a project. He backed down. (I think Niklaus Wirth in his Turing lecture made a remark about Huskey’s programming style; Huskey was his thesis adviser.)

With my cordial regards and my best wishes,
as ever yours Edsger

At least the myth that I picked up soon after my arrival at the Mathematical Centre, while mythical, turned out to be a fruitful one. In the fulness of time, it elicited an even more interesting story. I was pained to hear about van Wijngaarden’s role in this. As my thesis adviser he cared for me beyond the call of duty. He had been Dijkstra’s thesis adviser before that. In a handsome tribute to van Wijngaarden in his 1972 Turing lecture, Dijkstra acknowledges his debt.

Concurrently with his work on the compiler, Dijkstra wrote a paper about the new technique he used in the Algol-60 compiler. The paper was published as “Recursive Programming” by E.W. Dijkstra in Numerische Mathematik volume 2, pp. 312-318, in 1960. I mention this so that you can compare the e-mail with his acknowledgments at the end of the publication.

The author is especially indebted to Professor A. van Wijngaarden and J.A. Zonneveld, co-members of the team that is engaged in the construction of a compiler for ALGOL 60 at the moment of writing. During the course of this work many aspects, which he had tentatively written down at an earlier stage, became clearer, and their consequences became apparent under the pressure of the circumstances.
Furthermore, the author had the great privilege of having some inspiring conversations on this subject with Professor H.D. Huskey, when he was the guest of the Mathematical Centre, Amsterdam, in the summer of 1959.

Dijkstra has often been criticized for lack of politeness. Here he couldn’t have been more polite.

I only remember having seen Dijkstra at the Mathematical Centre on one occasion during my stay there between 1966 and 1971. In 1968 he gave a lecture on the subject of the goto statement. It was summer and the lecture was scheduled in the evening; only half a dozen showed up. Next morning T.J. Dekker (known for the first implementation of semaphores) and I, puzzled, were trying to figure out how one could do my quicksort variant (ACM Algorithm 402) without goto’s.

In those years the most visible activity at the Computational Department of the Mathematical Centre was Algol 67, which segued into Algol 68. When the work did not make the implied deadline, they decided not to change the name another time. The success of Algol 60 made the official (sponsored by IFIP) successor a big deal. Dijkstra’s success with the Algol 60 compiler made him a key member of the committee appointed to define the successor. However, irreconcilable differences with van Wijngaarden caused Dijkstra to resign. I am told that the addition of semaphores to Algol 68 was a gesture to placate Dijkstra. Also, in 1968 when Dijkstra officially inaugurated the THE multiprogramming system, van Wijngaarden made a pilgrimage to Eindhoven, with as many of us in tow as he could muster. I think Dijkstra never realized how much he meant to the big “little chief”.

By 1973 I was in Edinburgh, learning logic programming from Kowalski. Enthused with the new religion, I planned a lecture tour through the Netherlands. I wrote to everyone I knew offering a talk on logic programming. Dijkstra said OK, provided it would be on Tuesday afternoon. To my surprise, the great man nearly fell off his chair nodding in agreement at several points in my talk. Afterwards he took me excitedly to his office to show his guarded-command formalism featuring the same type of nondeterminism he had noticed in the logic programs I had just presented.

In the train on my way to the next stop I tried to reproduce an example of program derivation that Dijkstra had shown to me.

It is required to ensure that m is the maximum of x and y. The natural formulation is

(m = x or m = y) and m >= x and m >= y

The crucial move is to apply distributivity to get

(m = x and m >= y) or (m = y and m >= x)

Then equality and commutativity to get

(x >= y and m = x) or (y >= x and m = y)

which transcribes to Prolog or guarded commands:

if x >= y -> m = x | y >= x -> m = y fi

On this, or a visit not long after, I ate with Edsger’s family seated at a big round dining table with a Lazy Susan in the middle loaded with the typically Dutch huge assortment of jars with stuff to smear or sprinkle on slices of bread, including jams, chocolate paste, and several varieties of “muisjes”, a cost- and time-effective way to still appetites of hungry teenagers. The backyard, flowerless, optimized for kids and dogs. Upstairs, the office. Edsger told me how pleased he was to be at the university only on Tuesdays, consulting with Burroughs for the rest of the time. He pointed proudly to the two telephones on his desk, one of which he could use to call anywhere in the world, with the bills going direct to Burroughs. To most people in the 1970s in the Netherlands this was a mind-boggling concept. It was hard enough to get one phone from the PTT state monopoly.

To the German general public, “der alte Fritz” means king Frederick the Great of Prussia. To the computer science community it meant prof. dr. F.L. Bauer, the pope of German computer science. Bauer was the professor in Munich and organized a long series of NATO Summer Schools. He loved the Bavarian country side and located the summer schools in Marktoberdorf, a small town away from Munich. These events were dominated by three stars: Dijkstra, Hoare, and Wirth; the rest of the lectures were filled in by protege’s of Bauer’s from Munich. It was all extremely European, something one couldn’t say of computer science as a whole.

In 1973, to get some variation, Alan Perlis was invited. He couldn’t be more different, and stole the show. The summer school was held in a boarding school. Breakfast consisted of excellent coffee (black in my case), exquisitely fresh crispy rolls, butter, and jam. For several of the American participants this caused considerable agony, one (who didn’t look particularly healthy) arguing that anything less than two ounces of protein for breakfast is detrimental to health. Lunch was also at the boarding school. For dinner we got vouchers at the local tavern. At opposite ends Dijkstra and Perlis were holding forth to the faithful, trying to ignore some of us shuttling back and forth.

Apart from the two telephones, another notable feature of the office in Dijkstra’s home was an elegant portable Olivetti typewriter. At the time, a proper professor would write with a fountain pen, possibly a Mont Blanc, which was at the time one of several ordinary brands. Only secretaries touched a keyboard. But Edsger typed his EWD memo’s himself, somewhere acknowledging the unversity for purchasing for his sole use the one typewriter with the one font that could do justice to his thoughts. This way he did a lot of typing: the big one, “Notes on Structured Programming” (EWD249), runs to 88 pages.

Fast forward to my visit to Edsger in the 1980s in Austin, Texas, when all profs did their writing on keyboards and Edsger refused to touch one. I have since been told that one way of swearing allegiance to Edsgerismus is to purchase a Mont Blanc and to find that it facilitates the proofs of your programs (which are only to be contemplated, not executed). In his office Edsger had a pencil dangling from a string with a sign pointing to it saying “Word Processor”.

Not only were word processors anathema to Edsger as superfluous mechanical devices, but they also gave offense by coming with fat manuals. Edsger told me indignantly that some manual for Wordperfect ran to six hundred and fifty pages. He reminded me of the fact that Georg Joos only needed six hundred for his great work “Textbook of Theoretical Physics”. It was blasphemy to Edsger that a manual for buggy software for a perverse purpose used more space than a comprehensive compilation of the most sublime knowledge. If you already have a Mont Blanc, consider for your next purchase this book of Joos’s. Of course, it’s long been out of print. But it can be ordered from several antiquarian bookstores via the Web. For true Edsgerismus, get it as “Lehrbuch der Theoretischen Physik”.

At the time of his 2001 visit to the Netherlands, Edsger was already being treated for what turned out to be his fatal illness. The next year he moved to his old home near Eindhoven where I had first visited him in 1973. He died there in 2002.