< Prev Next >
108
NATO SOFTWARE ENGINEERING CONFERENCE 1968
9. Working Papers

THOUGHTS ON THE SEQUENCE OF WRITING SOFTWARE
by
Stanley Gill
In other papers presented at this conference, Dijkstra stresses the layer structure of software, and Randell refers to the alternative possibilities of constructing the layers from the bottom up (i.e. starting with the primitives) or from the top down (i.e. starting with the target system). Clearly the top-down approach is appropriate when the target system is already closely defined but the hardware or low-level language is initially in doubt. Conversely the bottom-up approach is appropriate when the hardware is given but the target system is only defined in a general way.
The obvious danger in either approach is that certain features will be propagated through the layers and will finally cause trouble by proving undesirable and difficult to remove, when they should have been eliminated in the middle layers. Thus in bottom-up programming, peculiarities of the hardware tend to be reflected in the higher levels (as for example in some high-level languages) when they would be better out of the way, while top-down programming may leave the programmer at the lower levels struggling to implement some feature inherent in the target system, which should have been dealt with higher up. The success of either approach depends upon the designer’s ability to anticipate such problems, and to generate and to recognize solutions that avoid them.
In practice neither approach is ever adopted completely; design proceeds from both top and bottom, to meet somewhere in between, though the height of the meeting point varies with circumstances.
Each program module constitutes a definition, in terms of the primitives available in that layer, of a facility that constitutes a primitive (or primitives) of the layer above. It is thus a ‘downward-facing’ definition. Associated with it is an ‘upward-facing’ definition, which is referred to when the facility provided by the module is used in a higher  layer. Downward-facing definitions are formal, and they are of course the means by which the system is implemented physically. Upward-facing definitions are used by the designer, and are usually informal.
In bottom-up programming the upward-facing definitions, though informal, are complete (or intended to be). Thus for example when a routine has been written in a defined language, the function performed by the routine should be unambiguously defined. In top-down programming this need not be so. In choosing the primitives one layer further down, out of which to construct the facilities required in a given layer, one has only to define them sufficiently closely to determine their role in this construction; the details may be left undefined. A classic example of this is the first step in breaking down a problem, as taught to all student programmers: drawing a flow chart. The blocks in the flow chart are by no means fully defined; their functions are only indicated sufficiently clearly to enable them to be put together correctly. As the lower layers are designed, they gradually complete the definitions of the top layers, and hence the outward functions of the whole system.
Thus in top-down programming one is often working with incompletely defined components. This demands more care and discipline; for example one must ensure that, in completing a definition, one does not introduce side effects that were not foreseen in the upper layers where the definition has been applied, and which could be harmful.
Top-down programming does however have an advantage in that it allows the designer to see which operations are called for frequently in the upper layers, and should therefore be given special treatment below. In bottom-up programming one must try to guess which primitives will prove most useful higher up. This is not easy; almost every programming language is littered with features that are hardly ever used.
In practice, a large software project is rarely a matter of implementing one single target system in terms of one given primitive system. The target is often modified in the course of the project, and the software may later be extended to meet several other targets also. It may be required to implement the whole system again on different hardware. The expectation of such later developments may influence the choice of programming method. Thus, for example, if later implementation on other hardware is likely to be needed, it is unwise to use the bottom-up approach  except from a layer at which one can provide useful common facilities in terms of any of the hardware alternatives. Similarly if (as is often the case) later variations of the target system are likely, it is less attractive to use top-down programming except from a layer at which one can define a useful set of primitives applicable to all the target systems.