Hierarchical Program Structures Dahl and Hoare, 1972

We continue to work our way through Liskov’s list. ‘Hierarchical program structures’ is actually a book chapter, and is notable for defining a ‘prefix’ mechanism that looks awfully like a form of class inheritance, paving the way for hierarchical program structures (i.e. Class hierarchies). The main takeaway for me is the idea that architectural layers should correspond to conceptual layers, with every entity in a given layer being at the same level of conceptual abstraction.

A programming language provides us with basic concepts and composition rules for constructing and analysing computing processes… data and operations on data seem to be so closely connected in our minds, that it takes elements of both kinds to make up any concept useful for understanding computing processes.

On top of the concepts provided by a programming language, we build higher level concepts. The necessity for this is simply the limits of our own intellect – precise thinking is possible only in terms of a small number of elements at a time. As a consequence,

… The only efficient way to deal with complicated systems is in a hierarchical fashion. The dynamic system is constructed and understood in terms of high level concepts, which are in turn constructed and understood in terms of low-level concepts, and so forth. This must be reflected in the structure of the program which defines the dynamic system; in some way or other the higher level concepts will correspond to program components.

Coming up with a suitable set of concepts is a creative process, often requiring insights that arise during the later stages of construction. Thus software projects tend to be complicated iterative processes involving construction and revision at each stage. A good decomposition of the system enables each component to be programmed independently, and revised with little or no implications for the rest of the system.

Examples of higher-level concepts are given:

• Procedures can be used to model some concepts, but their reliance on the stack for data storage means that algorithms are the only concepts that can be effectively modelled by them.
• Classes combine variables and procedures and allow modelling of a wider array of concepts (e.g. A frequency histogram).
• Coroutines enable two conceptual pieces of a program to operate at the same level (vs. one calling the other). Consider a two-pass compiler: the first pass outputs a long sequence of messages to be consumed as input by the second pass. But it is possible to arrange for the whole translation to be carried out in a single pass with the sequence of messages transmitted piecewise from the first pass to the next.

This suggests that a single coroutine may profitably be regarded as a complete self-contained program whose input and output instructions have been replaced by calls upon those coroutines to produce and consume the data.

It’s interesting to see coroutines right alongside classes as a basic concept modelling tool. They’ve certainly not had such equal billing for most of the intervening 44 years, though perhaps Go is getting closer with its goroutines.

The next concept to be introduced is that of self-referential classes that can be used to build recursive data structures such as binary trees and linked lists. “This is accomplished by declaring attributes of a class to be references to objects of the very same class.”

And finally we arrive at a concept introduced under the heading “program concatenation:”

In the preceding sections we have seen how the class mechanism is capable of modelling certain simple concepts, by specifying data structures and defining operations over them. In this section we develop a method by which more elaborate concepts can be constructed on the basis of simpler ones. This will establish potential hierarchies of concepts, with complex concepts subordinate to the more simple ones in terms of which they are defined…

How do we do that? In 1972, we do it by concatenation. Take two classes A and B, and merge the attributes of both classes and the composition of their actions. Writing ‘X class Y …’ means to take all of the declarations in X and ‘shove them at the front’ of the declaration of Y. In other words, it’s a primitive form of inheritance.

The concept hierarchies formed by this mechanism help to bridge the gap between the problem domain and the general purpose programming language.

Our difficulty in bridging such gaps is the fact that we have to work sequentially on one simple part problem at a time, not always knowing in advance whether they are the right problems. In order to better overcome such difficulties we may build pyramids. Unlike the Egyptian ones ours are either standing on their heads (bottom-up construction) or hanging in the air (top-down construction). The construction principle involved is best called abstraction.

At each layer of the pyramid we concentrate on features common to many phenomena, and we abstract away features too for removed from the conceptual level at which we are working. Thereby, we have a better chance of formulating concepts which are indeed useful at a later stage.

Whether we work top-down or bottom-up (or even a little bit of both and hope to meet-in-the-middle) system construction consists of adding new layers of pyramids until the conceptual gap has finally been bridged. Each such layer will correspond to a conceptual level of understanding.

At the higher conceptual layers, we have what we would now call a domain language:

A well-formed conceptual level (bottom-up) is a set of well-defined inter-related concepts, which may be combined to make more elaborate concepts. It may serve for further construction in a mental platform, raised above ground towards some application area, i.e. as an “application language.” A reconstructed application language may serve to shorten the conceptual gap that has to be bridged for many problems in the area.