A design methodology for reliable software systems Liskov 1972
We’ve come to the end of Liskov’s list. The final paper is by Barbara Liskov herself, on the question of how best to go about designing software systems so that we can have some confidence they will work.
The unfortunate fact is that the standard approach to building systems, involving extensive debugging, has not proved successful in producing reliable software, and there is no reason to suppose it ever will.
So we’re going to need some testing, and for high levels of confidence we’ll need good coverage via:
- a complete but minimal set of test cases, and
- a system in which the set of relevant test cases is small, such that it is possible to generate every case
It is the system design which determines how many test cases there are and how easily they can be identified, the problems can be solved most effectively during the design process.”
And with that short introduction, the rest of the paper focuses on the questions of ‘What is a good system design?’ and ‘What process will help to ensure we produce one?’
A good system design is one where complexity is tamed by dividing it into modules (called ‘partitions’ in the paper, because the term module had already become very overloaded). As we’ve looked at previously, just dividing a system into modules isn’t enough though – it matters very much how you make those divisions. In fact,
…the division of a system into modules may introduce additional complexity… if modularity is viewed only as an aid to management, then any ad hoc modularization of the system is acceptable. However, the success of modularity depends directly on how well the modules are chosen.
A good modularity is based on levels of abstraction, and uses structural programming within modules.
Level of abstraction were first defined by Dijktsra. They provide a conceptual framework for achieving a clear and logical design for the system. The entire system is conceived as a hierarchy of levels, the lowest levels being those closest to the machine.
There are two important rules given for levels of abstraction:
- Each level has resources which it owns exclusively and which other levels are not permitted to access.
- Lower levels are not aware of the existence of higher levels and therefore may not refer to them in any way.
With good modularity, the system is broken into a hierarchy of partitions (modules), with each partition representing one level of abstraction and consisting of one or more functions which share common resources. The connections between partitions are limited as follows:
- Control connections are limited by the rules about the hierarchy of levels of abstraction
- Connections in data passed between partitions are limited to the explicit arguments passed from the functions of one partition to the (external) functions of another partition. Implicit interaction on common data may only occur among functions within a partition.
- The combined activity of the functions in a partition support its abstraction and nothing more.
The definition of connections in the above follows Parnas: “The connections between modules are the assumptions which the modules make about each other.”
We know what good modularity looks like when we see it now. But how do you arrive at good modularity in the first place?
The traditional technique for modularization is to analyze the execution-time flow of the system and organize the system structure around each major sequential task. This technique leads to a structure which has very simple connections in control, but the connections in data tend to be complex.
(See Parnas again).
Select modules to support abstractions or concepts which you find helpful in thinking about the system….
Abstraction is a very valuable aid to ordering complexity. Abstractions are introduced in order to make what the system is doing clearer and more understandable; an abstraction is a conceptual simplification because it expresses what is being done without specifying how it is done.
What kinds of abstractions should we be on the lookout for?
- Abstractions of resources – modules that map the characteristics of an abstract resource into the real underlying resource or resources
- Abstractions that hide data storage representations
- Abstractions that limit information:
According to the third requirement for good modularizatio, the functions comprising a partition support only one abstraction and nothing more. Sometimes it is difficult to see that this restriction is being violated, or to recognize that the possibility for identification of another abstraction exists. One technique for simplification is to limit the amount of information which the functions in the partition need to know (or even have access to).
One way to limit information is to introduce modules at a lower level, on which the higher-level module depends, which hide that knowledge.
- Abstractions that generalize a function or group of functions. “Separating such groups is a common technique in system implementation and is also useful for error avoidance, minimization of work, and standardization.”
- Abstractions that encapsulate areas likely to change
The design process proceeds iteratively as follows. First determine an initial set of abstractions which represent the eventual system behaviour in a very general way. Then establish the data and flow of control connections among the partitions.
The second phase occurs concurrently with the first; as abstractions are proposed, their utility and practicality are immediately investigated… A partition has been adequately investigated when its connections with the rest of the system are known and when the designers are confident that they understand exactly what its effect on the system will be. Varying depths of analysis will be necessary to achieve this confidence.
When do you start programming modules? There is a tendency to think of this as the era of the strict waterfall, but that’s not what Liskov proposes:
It is not clear exactly how early structured programming of the system should begin… The best rule is probably to keep trying to write structured programs; failure will indicate that the system abstractions are not yet sufficiently understood and perhaps this exercise will shed some light on where more effort is needed or where other abstractions are required.
Finally, a design can be considered ‘finished’ when the following criteria are met:
- All major abstractions have been identified and partitions defined for them; the system resources have been distributed among the partitions and their positions in the hierararchy established.
- The system exists as a structured program… this consists of several components, but no component is likely to be completely defined. Rather each component is likely to use the names of lower-level components which are not yet defined.
- Sufficient information is available so that a skeleton of a user’s guide to the system could be written. (This was an era of much simpler user interfaces remember).