During his life he shaped the field of computer science like no other scientist. His ground-breaking contributions ranged from the engineering to the theoretical side of computer science. They covered areas such as compiler construction, operating systems, distributed systems, sequential and concurrent programming, software engineering, and graph algorithms. Many of Dijkstra’s papers, often just a few pages long, are the source of new research areas. Indeed, several concepts that are now standard in computer science were first identified by Dijkstra and bear names coined by him.
Dijkstra did not end up becoming a theoretical physicist, thanks to a discussion with Adriaan van Wijngaarden, at that time director of the Mathematisch Centrum’s Computation Department. After working as a programmer at the centre for three years, he knocked on Van Wijngaarden’s door, full of doubt, as he was finding it difficult to combine his role as a programmer and his study in theoretical physics at the Leiden University. ‘When I left his office hours later,’ Dijkstra said in his 1972 ACM Turing Lecture, ‘I was another person.’ Indeed, though programming was not an established discipline yet, Van Wijngaarden managed to convince Dijkstra that ‘it was here to stay’ and that he could play a part in putting the discipline on the map.
Cornerstone of fame: Dijkstra’s algorithm
And put it on the map he did. Dijkstra worked at the Mathematisch Centrum from 1952 to 1962, where he came up with what has become, in his words, ‘one of the cornerstones of my fame’. That cornerstone is the algorithm for the shortest path, also known as Dijkstra’s algorithm. According to Dijkstra, ‘it was a twenty-minute invention’ that he conceived while having a cup of coffee on a café terrace with his fiancée Ria, who he had met at Mathematisch Centrum. He initially used the algorithm in 1956 to showcase the potential of a new computer called ARMAC. But he understood all too well that a demonstration for laypeople had to have a problem and answer that they could understand.
His solution was to design an algorithm that would find the shortest route between two cities in the Netherlands using a simplified map. ‘What’s the shortest way to travel from Rotterdam to Groningen?’ Dijkstra asked rhetorically in an interview with Communications of the ACM. ‘It is the algorithm for the shortest path.’ Though he used the algorithm for the official presentation of the ARMAC in 1956, it wasn’t published until 1959 in his three-page article A Note on Two Problems in Connexion with Graphs. Its impact is best summarised in 1999 by Danish computer scientist Mikkel Thorup: ‘Since 1959, all theoretical developments in SSSP [Single-Source Shortest Paths] for general directed and undirected graphs have been based on Dijkstra’s algorithm.’
ALGOL 60 programming
Another key achievement during Dijkstra’s time at Mathematisch Centrum was his contribution to the development and popularisation of the programming language ALGOL 60. In 1958-1959, Dijkstra was involved in a number of meetings that culminated in the publication of the report defining the ALGOL 60 language. Ironically, Dijkstra’s name does not appear in the list of 13 authors of the final report: it seems he left the committee prematurely because he could not agree with the majority opinions. But it was during his tenure as a programmer at Mathematisch Centrum that he and his colleague Jaap Zonneveld wrote the first ALGOL 60 compiler, which among others used a new method for implementing recursion. His short book, A Primer of Algol 60 Programming, originally published in 1962, was the standard reference for the programming language for several years.
Tuesday Afternoon Club
In 1962 Dijkstra started working as a professor in the Mathematics Department at Eindhoven’s Technological University. Two years later, he and his wife Ria moved into a newly built house in Nuenen, a small village on the outskirts of Eindhoven. Nuenen was added to the world map of computer science in 1973 when Dijkstra started to circulate his reports signed ‘Burroughs Research Fellow’ with his home address. Many thought that Burroughs, a company known at that time for the production of computers based on an innovative hardware architecture, was based in Nuenen.
In fact, Dijkstra was the only research fellow of Burroughs Corporation and worked for it from home, occasionally travelling to its branches in the USA. As a result he reduced his appointment at the university to one day a week. That day, Tuesday, soon became known as the day of the famous ‘Tuesday Afternoon Club’, a seminar during which he and his colleagues discussed scientific articles, scrutinising all aspects – notation, organisation, presentation, language, and content. When he moved to the University of Texas at Austin in 1984, it did not take long for a new ‘branch’ of the Tuesday Afternoon Club to open.
The birth of concurrent programming
In 1968, Dijkstra published his famous paper, Cooperating Sequential Processes, which provided the foundation for all subsequent designs of the operating systems and also gave birth to the field of concurrent programming. Many of Dijkstra’s ideas from this period had been germinating for some time. Indeed, Cooperating Sequential Processes had been completed in 1965 as manuscript, denoted by hem as EWD 123. Dijkstra consecutively numbered his largely handwritten manuscripts, using his Mont Blanc fountain pen, which are known in the world of computer science as EWDs. This paper proposes the first synchronisation mechanism for concurrent processes, the semaphore with its two operations, commonly known as P and V.
Deadlock problem and proofs
In a 1971 paper, Dijkstra illustrated the so-called deadlock problem by means of the so-called dining philosophers problem: five philosophers seated around a table are supposed to eat spaghetti sharing only five forks. The problem, however, is that each of them uses two forks to eat. This example became a classic benchmark for explaining new synchronisation primitives. The paper also led to an intense search for high-level synchronisation mechanisms, leading eventually to the concept of a monitor, pioneered by computer scientists Per Brinch Hansen and Tony Hoare.
In the late 1970s, Dijkstra became interested in the development and presentation of proofs. Some of these proofs were surprising applications of his programming methodology to geometry or algebra. He criticised the use of implication and instead favoured proofs presented as chains of equivalences with each step justified as an interlaced comment, and he liked to stress the fact that the equivalence is associative, a fact that logicians knew but apparently never used.
Move to Austin
Dijkstra accepted a position at the University of Texas at Austin in 1984. Austin was like a second home to Dijkstra, and he spent his vacations discovering America’s national parks together with his wife in their Volkswagen bus, dubbed the Touring Machine. The classes he taught in Austin actually had little to do with computer science. Instead they dealt with his interest in the presentation of mathematical proofs. He would ask students to write up proofs of the elementary mathematical problems he discussed in class, which he would return with incisive but humorous comments such as ‘Many sins of omissions’.
His lectures were highly entertaining because of his sharp comments, striking turns of phrase and curious quotations that he used to put on the blackboard before starting his lecture. He never asked his students to quiet down in the classroom. Instead, he would lower his own voice to the point of being hardly audible. This trick was amazingly effective.
Colourful and opinionated
Dijkstra was a colourful – if sometimes difficult and opinionated – and well-respected man. Many researchers were captivated by his strong personality combined with remarkable working habits, forthright honesty and definite opinions on how to conduct research. Dijkstra seemed to believe that everyone should think, and even behave, the way he did. This made him a natural prophet and accounted for many of his idiosyncrasies.
Dijkstra attracted a relatively small but stable group of disciples, which included both PhD students and highly renowned computer scientists. They adopted his writing style and notation, his manners, use of a fountain pen, and occasionally even his type of sandals.
Plain prose
The elegance of his writing was unmatched. He could write about formal issues in essay format containing barely any formulas. His paper Cooperating Sequential Processes is perhaps the best example. Similarly, he was able to discuss intricate algorithms in distributed computing in a seemingly informal way, in plain prose, with just a few simple formulas. He wrote his articles in a unique style characterised by conciseness, economy of argument, and clarity of exposition. Each sentence was carefully chiselled. Each paragraph was striking.
The elegance of his writing was matched by his handwriting. In fact, it was so distinct and perfect that in the late 1980s Luca Cardelli, then from the DEC Systems Research Center in California, designed a ‘Dijkstra’ font for desktop computers. Soon after, Dijkstra received a letter typeset in this font and thought it was handwritten until news reached him about the creation of this font. Some of Dijkstra’s colleagues occasionally used this font in their slide presentations during the departmental meetings in Austin.
Light in the darkness
Dijkstra’s key achievements were recognised early in his career. In 1972, he was presented with computing science’s highest honour, the ACM Turing Award. He was a Foreign Honorary Member of the American Academy of Arts and Sciences, a member of the Royal Netherlands Academy of Arts and Sciences (KNAW), and held the doctor honoris causa titles from Queen’s University Belfast in Northern Ireland and the Athens University of Economics & Business in Greece. In addition, over a period of 30 years, he received numerous other awards and distinctions, some just a couple of weeks before his death on 6 August 2002.
Not surprisingly, his obituary appeared in a number of newspapers, including The New York Times, The Washington Post, and The Guardian. As J Strother Moore, the chairman of the Computing Science Department at Austin, said during Dijkstra’s funeral: ‘He was like a man with a light in the darkness. He illuminated virtually every issue he discussed.’
References
Krzysztof Apt. Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius. Formal Aspects of Computing (2002) 14: 92–98.
Krzysztof Apt. The Man Who Carried Computer Science on His Shoulders. Interference (2020) vol. 5, issue 3.
Edsger W. Dijkstra. The Humble Programmer. Communications of the ACM (1972) 15:859-866.
E. W. Dijkstra Archive, The University of Texas at Austin.
In April 2001, one year before his death, the Dutch public broadcasting organisation VPRO aired a documentary about Dijkstra, titled Denken als discipline (Thinking as a discipline).
