Four Snapshots of Dijkstra's Career

Dated: 

1953

Three snapshots of Dijkstra's career are described in my previous blog (1963, 1976, 1982). Below I elaborate on Dijkstra's views in 1953 — a year after he had started his career in computing by joining the Computing Department at the Mathematical Centre of Amsterdam.

Dijkstra joined the Computing Department while studying theoretical physics in Leiden. He was not an engineer by education while his colleagues Van Wijngaarden, Loopstra, Scholten, and Blaauw were engineers. Because he was not in a position to grasp all of the physical intricacies of a computing machine, Dijkstra tried to abstract the what from the how as soon as possible. Translated from his Dutch words from 1953:

“[T]his machine will be described as far as is relevant for the person that uses the machine: we shall describe what the machine does, and not how the machine works.” [1, Dijkstra's emphasis]

Dijkstra used analogies to transition from how a computer's memory works to what it can do. Translated from the same source, Dijkstra wrote:

“Implementing a memory (which stores numbers) like marbles in a bag would be impractical. Instead, the memory is analogous to numbered cells written on a blackboard. With chalk in one hand and a sponge in the other hand, the sponge is used only when the contents of a cell have to be changed. Erasing with the sponge happens automatically; that is, `forgetting' is not a distinct operation.” [1]

So Dijkstra used analogies — like marbles in a bag and a teacher holding a piece of chalk and a sponge — in order to capture the functionality of a computer's memory. He extracted the essentials of a computer by discarding its physical details.

Complementary to the above, Dijkstra also reasoned from the general mathematical problem to the specific machine. Translated from his Dutch words, he wrote:

"1. mathematically formulate the problem

2. mathematically solve the problem

3. select/construct the numerical process (in accordance with 2.)

4. programming: detailed construction of the processes in 3. ...

5. coding: write out the program in machine code ...” [1]

Dijkstra furthermore emphasized that the programming in 4. is applicable to several machines, not only to the ARRA. Coding in 5., in turn, is machine specific. On the one hand, Dijkstra was thus already reasoning abstractly to a noticeable extent during his first year as a programmer.

On the other hand, his abstractions were not as extensive as in later years (cf. his separation of concerns and structured programming). Indeed, in his 1953 report, Dijkstra was still making trade-offs and this was much in line with the work of his fellow engineers. He enumerated the conflicting ideals of the programmer as follows:

"1. maximum speed, to execute the program

2. minimum memory, to store the program

3. maximum safety

4. maximum accuracy

5. maximum flexibility

6. a maximum bird's eye view (of the program)" [1]

Dijkstra immediately noted that “The first two ideals are already to some extent conflicting ideals” and he later also discussed several existing conflicts among the other ideals in the above list.

To demonstrate the conflict between the first two ideals, Dijkstra discussed the difference between a “Stretched program” and a “Cycle program”. To obtain the former, a programmer writes all operations repeatedly; that is, as many times as is needed. To obtain the latter, the programmer writes the operations once and puts them in a subroutine which determines how many times to carry through the cycle. Dijkstra subsequently noted that more memory is needed to implement the “Stretched program” than the “Cycle program”, but that the “Stretched program” executes faster than the “Cycle program”. This typical engineering trade-off has machine-specific implications, Dijkstra noted. When dealing with a slow machine with a large memory, the programmer will opt for the “Stretched program”. When dealing with a fast machine with a small memory, the programmer will choose the “Cycle program” instead. This machine-specific reasoning (specialization) stands in sharp contrast to Dijkstra's later work on ALGOL in the late 1950s and early 1960s [2].

[1] E.W. Dijkstra, "Functionele Beschrijving van de ARRA", MR 12 technical report, Mathematisch Centrum Amsterdam, 1953.

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

Tags: