Turing award lecture — an analogy with physics


early 1972

Dijkstra contributed greatly to introducing hierarchical systems into computing. Already in his very first report of 1953 as employee of the Mathematical Centre in Amsterdam, Dijkstra introduced what he would later call separate levels of concern [1]. In 1959–60, he acquired fame after reformulating the problem of ALGOL translation as an hierarchical problem. His intermediate machine-independent stack-based language was, in hindsight, a precursor to the now widely used virtual machine; see chapter 3 in my book The Dawn of Software Engineering [2]. Dijkstra extended his layered software approach during the 1960s. His hierarchical THE operating system is most notable in this regard. Interested readers can download McKeag's account of the THE system here.

But where did Dijkstra's appeal for hierarchy come from? He definitely was only one of few to reason hierarchically during the 1950s and 1960s. Another important name in this regard is Barbara Liskov with her VENUS operating system which she discussed with me; see chapter 6 in my book [2].

Paraphrasing the comments made to me by two former colleagues of Dijkstra — De Bruijn and Van der Poel — in recent interviews: "Dijkstra was neither a mathematician nor an engineer, he was a physicist". According to them, Dijkstra had a peculiar and highly original way of viewing a programming problem — irrespective of the differences these men had with Dijkstra on more than one occasion.

Educated as a theoretical physicist from Leiden University, Dijkstra repeatedly made analogies with physics when solving programming problems during the 1950s and 1960s. The following words from his 1972 Turing award lecture illustrate the analogy with regard to his notion of hierarchical system:

We understand walls in terms of bricks, bricks in terms of crystals, crystals in terms of molecules etc. [EWD 340]

Hierarchical systems seem to have the property that something considered as an undivided entity on one level, is considered as a composite object on the next lower level of greater detail; as a result the natural gain of space or time that is applicable at each level decreases by an order of magnitude when we shift our attention from one level to the next lower one. [EWD 340]

Dijkstra elaborated on this analogy in EWD 317.

[1] E.G. Daylight. A compilation of Dutch computing styles, 1950s – 1970s. Accepted for HAPOP (History and Philosophy of Programming), Birmingham, July 2 – 6, 2012.

[2] E.G. Daylight. The Dawn of Software Engineering: from Turing to Dijkstra. Lonely Scholar, April 2012.