Step-Wise Composition: Confusing Terminology?

Dated: 

June 1972

To clarify his step-wise program composition, Dijkstra used terms like “program layers” and “levels of abstraction” in his `Notes on Structured Programming' [1, Chapter 1]. These terms were not well defined as Dijkstra conceded later. As a result, Dijkstra's exposition — although extremely rich in content — was difficult to understand completely. See e.g. Denning's clarifying article on Structured Programming [3] or my interview with Liskov who mentions Parnas in this regard [2].

In my previous post I re-introduced some of Dijkstra's descriptions of his prime-number example. The first two, Description 0 and Description 1, are presented again below.

Description 0:
begin  “print first thousand prime numbers”  end

Description 1:
begin  variable “table p”;
 “fill table p with first thousand prime numbers”;
 “print table p”  end

Dijkstra used several terms to denote the same thing. The word “description”, for instance, was used as a synonym for “program layer”. Description 0 is thus Program Layer 0 and Description 1 is Program Layer 1.

Each line below is a list of synonyms:

  • “refinements” — “decompositions” 
  • “description” — “program layer” — “level of abstraction” 
  • “abstract program” — “virtual machine”

Only the very last description obtained by step-wise composition corresponds to the final executable program. All other descriptions, such as Description 0 and Description 1, are abstract programs. Hence, for these abstract cases, the following terms can be used as synonyms as well:

  • “description” — “program layer” — “level of abstraction” — “abstract program” — “virtual machine”

Dijkstra also distinguished a more concrete program from an abstract program by means of the words “children” and “ancestor”. The latter word occurs in the following passage:

when a program has been built up to an intermediate stage of refinement, what has then been written down is in fact a suitable “common ancestor” for all possible programs produced by further refinements. [1,p.40]

More interesting is Dijkstra's usage of the words “program layer” in the following quote:

If we succeed in building up our program along the lines just given, we have arranged our program in layers. Each program layer is to be understood all by itself, under the assumption of a suitable machine to execute it, while the function of each layer is to simulate the machine that is assumed to be available on the level immediately above it. [1,p.49]

The resemblance with Dijkstra's THE system is apparent because THE is essentially a layered system of abstract machines. Note, however, that the layers constituting the THE system are part of the end product, while the program layers in a step-wise program composition do not constitute the final program. In a step-wise program composition, only the very last program layer is expressed in executable code and it is the final program.

Having said that, I hasten to remark that the complete step-wise program composition is reflected in the final program structure. That is, the series of decision choices that the programmer makes is reflected in the structure of his final executable program. Description 1, presented above, already resembles much of the structure of the final description; that is, of the final executable program. Description 2, presented in my previous post, resembles more structure of the final description. Description 3 is even closer to the final executable program, and so on.

As the previous and also the following passage illustrate, Dijkstra associated a “program layer” with a “machine”.

All the time I design programs for non-existing machines and add: “if we now had a machine comprising the primitives here assumed, then the job is done”. [...]  Again we are left with a primitive that admits further refinement without commitments regarding the other primitives. [...]  we create the machine [...]  [1,p.55]

Here we again see Dijkstra continue with what he had started to do in Amsterdam during the 1950s: programming non-existing machines on paper. (See my previous post for some preliminary comments on Dijkstra's work during the early 1950s.)

Dijkstra's hierarchy of machines also shows some resemblance to Van Wijngaarden's 1962 work on `Generalized Algol' [4]. Dijkstra and Van Wijngaarden had been working and thinking alike in Amsterdam during the 1950s.

A Bit Confusing

Unfortunately, Dijkstra's excessive use of synonyms made his exposition a bit confusing. Consider, for instance, the following list of words used by Dijkstra:

  1. “layered hierarchy of machines”
  2. “a layer contains “a bunch of programs” to be executed by some conceptual machine”
  3. “a picture of program structure as a layered hierarchy of machines” [1, p.50]

The words in the first line refer, for instance, to the descriptions in the prime-number example: Description 0 — Description 1 — Description 2. Each description corresponds to a machine. The “layer” in the second line refers to a specific description, such as Description 1. So far so good. But the words in the third line are confusing: “program structure” here refers, again, to the layered descriptions in the prime-number example and not to the structure of the final executable program. Dijkstra's “program” refers to all descriptions together, not solely to the final executable program.

Dijkstra also used the words “levels of abstraction” in an attempt to get his intuitive ideas across.

Our experience [...]  strongly suggests that the arrangement of various layers, corresponding to different levels of abstraction, is an attractive vehicle for program composition. [...] It is not vain to hope that many a program modification can now be presented as replacement of one (virtual) machine by a compatible one. [1, p.49]

Strictly speaking, the words “virtual machine” in this context refer to a step (i.e. a program layer) in a step-wise program composition, not to a structural entity of the final program such as a layer in the THE system. Having said that, recall that the step-wise composition and the structure of the final program are closely related. It is no coincidence that the THE system itself can easily be modified (by changing one of its layers) because its layered structure reflects the decision choices that were (supposedly) made during its step-wise creation.

 

[1] O.-J. Dahl, E.W. Dijkstra, and C.A.R. Hoare. Structured Programming. Academic Press, London - New York - San Francisco, 1972.

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

[3] P.J. Denning. A hard look at structured programming. In Structured Programming: Analysis, p. 183-202. Infotech State of the Art Report, Maidenhead, England, 1976.

[4] A. van Wijngaarden. Generalized ALGOL. In R. Goodman, editor, Annual Review Automatic Programming, volume 3, p. 17-26. Pergamon Press, 1963.

Tags: