Submitted by egdaylight on
“I still remember it well, the day my future husband entered my life”, Ria Debets-Dijkstra recalls. “He was a good-looking man, 20 years of age. He entered our Computing Department with a cane!” . The Computing Department was part of the newly founded Mathematical Centre in Amsterdam. Ria Debets-Dijkstra had already been working there for two years before she saw Edsger Dijkstra on that eventful day in 1951. Dijkstra officially joined the Computing Department in March of the following year. Until 1956, he would work two days a week in Amsterdam and spend the rest of his time studying theoretical physics in Leiden.
During the first ten years of his career, Dijkstra worked as a programmer in Van Wijngaarden's team at the Mathematical Centre in Amsterdam. In 1962 he was appointed professor at the Technische Hogeschool of Eindhoven. And only ten years later, he already received computing's most prestigious prize, the Turing Award. By 1982, he had changed his focus from programming methodology to mathematical methodology and would continue to work on the latter for the next 20 years of his life. He died in August 2002.
In this post I compare and contrast three snapshots of Dijkstra's career, snapshots taken in the years 1960, 1976, and 1982.
1960 — In search for a general language
As he demonstrated in his 1952 inaugural lecture, Van Wijngaarden was very keen on connecting natural languages with programming languages when Dijkstra joined the Mathematical Centre. With hindsight, it is no surprise to see ideas similar to Van Wijngaarden's expressed in some of Dijkstra's early writings (see e.g. MR 34: `On the Design of Machine Independent Programming Languages').
Around 1960, Dijkstra and Van Wijngaarden viewed ALGOL60 as a programming language containing unneeded restrictions. They wanted to discard those restrictions and devise a general language instead. Van Wijngaarden's persistence in this regard eventually led to the definition of ALGOL68.
An example of an unneeded restriction — that fortunately was not part of ALGOL60 thanks to Van Wijngaarden's and Dijkstra's prior efforts — was a procedure that can call another procedure but not itself. By discarding that restriction, one obtains a more general and hence simpler language; i.e. a language that can handle recursive procedures. For further details, see my two previous posts: `An analogy between mathematics and programming' and `Dijkstra's Unification versus the Case Distinctions of Irons & Feurzeig'.
1976 — In search for intellectual manageability
Like so many others, Dijkstra was a computer programmer who had no training in mathematical logic. Only in the early 1970s did Dijkstra become a supporter of Hoare's logical approach to programming language semantics. [2, p.346].
According to Dijkstra, it was Hoare who showed the computing community that intellectual manageability of programs critically depends on the specific choice of linguistic constructions. On the one hand, the programming language should offer combinatorial freedom. On the other hand, if too much freedom is provided, then the language may be intellectually unmanageable (and, as a possible result, difficult to implement). For example, a language containing procedure calls, and hence also recursive procedure calls, is intellectually unmanageable.
So Dijkstra's support for Van Wijngaarden's linguistic ideals faded. Dijkstra learned from Hoare that a computing scientist should, on the one hand, try to generalize the task he has to solve but, on the other hand, avoid introducing generalizations that are intellectually difficult to manage in the first place. [3, p.10-11] Too much combinatorial freedom can be detrimental.
[Dijkstra] advocated many restrictions on programming language constructs, but always with the problems of program correctness in mind, of showing the correctness of a program. In 1976, in A Discipline of Programming, he even dropped the recursive procedure altogether [...]
This comment is from an anonymous reviewer for Chapter 3 in my book The Dawn of Software Engineering: from Turing to Dijkstra. The comment characterizes Dijkstra's thinking of the 1970s and stands in sharp contrast to the way Dijkstra thought about programming, and recursion in particular, during the early 1960s. What Dijkstra considered to be simple (and elegant) in 1960 was not necessarily simple in 1976.
1982 — A program text represents a predicate
During the 1980s, calculational reasoning became Dijkstra's main occupation. Instead of viewing a program text as an operational description of an abstract machine as he had done during the 1960s, Dijkstra viewed a program text as a formula in a formal system. The formula represents a predicate. In his words:
Each program text [... represents ...] a predicate on the Cartesian product of the so-called initial state space and the final state space. [4, p.1]
Furthermore, the activity of formally deriving a program from its specification is a constructive form of predicate calculus — constructive because the predicate has to allow for the interpretation of automatically executable code.
Mathematical logic entered the arena of computing science in various guises but primarily by researchers who were not mathematical logicians (— a central theme in my book The Dawn of Software Engineering). It is precisely this historical interplay between ideas from mathematical logic and their counterparts in computing science which, I believe, can serve well in grasping the basics of our field.
 Paraphrased words from an interview with Ria Debets-Dijkstra in December 2011.
 E.W. Dijkstra. “EWD 1308: What led to Notes on Structured Programming”. In: Software pioneers: contributions to software engineering. Ed. by M. Broy and E. Denert. Springer, 2002, pp. 341–346.
 E.W. Dijkstra. "EWD 325: Poging tot plaatsbepaling van de informatica", pp. 0-14.
 E.W. Dijkstra. "EWD 819: Mathematical Induction and Computing Science", 4 April 1982, pp. 0-7.
Recursion not elegant?
Submitted by Srinivas Nayak (not verified) on
I couldn't stop myself writing on this.
It was a eye opener for me to know such a thing. I had gone through Dijkstra's papers on recursion and discipline of programming, but never thought of anything such.
Anyway, your posts gives true insight into Dijkstra's thinking.