Program development by stepwise refinement Wirth, CACM 1971
This is the second of Barbara Liskov’s 7 ‘must-read’ CS papers. Wirth’s main point is that we have a tendency to focus far too much on mastering the syntax and style associated with a particular programming language, and nowhere near enough time on the process by which new programs are designed in the first place.
… active programming consists of the design of new programs, rather than contemplation of old programs… Clearly, programming courses should teach methods of design and construction, and the selected examples should be such that a gradual development can be nicely illustrated.
By far the bulk of the paper though, is dedicated to one worked example of this principle, introducing the idea of stepwise refinement. The goal is to write a program to solve the eight-queens problem.
Picture credit: Wikipedia
Wirth starts out with a very high level sketch of a solution, and gradually fills in the details to make both a more concrete and a more efficient implementation over time.
In each step, one or several instruction of the given program are decomposed into more detailed instructions. This successive decomposition or refinement of specifications terminates when all instructions are expressed in terms of an underlying computer or programming language, and must therefore be guided by the facilities available on that computer or language.
It’s not just about refinement of the tasks involved in the program; crucially the data and data representations may also need to be refined. “It is natural to refine program and data specifications in parallel.” It’s interesting to think about the task-based decomposition that naturally arises from this method, and contrast it with Parnas’ advice in “On the criteria to be used in decomposing systems into modules“. The stepwise refinement example in this paper though is ‘in the small,’ and really about the stepwise refinement of an algorithm as much as anything.
Reading through the worked example, I’m glad we have higher-level programming languages to work with these days! (The paper uses Algol 60). There are a few too many global variables and pointers for modern tastes. The thinking process is still valuable though.
A guideline in the process of stepwise refinement should be the principle to decompose decisions as much as possible, to untangle aspects which are only seemingly interdependent, and to defer those decisions which concern details of representation as long as possible.
Here are the steps in Wirth’s refinement:
Up-front thinking…
- Start out with a very simple brute force algorithm that tries all possible placements until it finds one that works.
- Realise that this would be highly inefficient (about 7 hours on the technology of the day), and thus we need to find a shortcut…
- Reduce the number of candidate solutions that must be generated and tried, using a little domain knowledge: in this case, that there must be one queen in every column. This process would find an answer in about 100 seconds on the technology of the day.
- Realise that we can do better by being systematic about the way we generate trial solutions via stepwise construction of trial solutions. That is, we start out by placing a queen in the first column, and then adding a queen in successive columns at each next step. If at any point in this process one or more queens conflict with each other we know there is no point going any further, so instead we can backtrack and try again from there. This version generates 876 partial solutions before finding a complete one, and takes about 0.09 seconds on the technology of the day.
Development of the program…
Only at this point does Wirth think about moving into code. The first version is expressed in terms of a number of high-level procedures, whose details have yet to be filled in:
The next step is to begin to fill-in the details of those procedures, at which point we can no longer defer any decision about data representation.
A common difficulty in program design lies in the unfortunate fact that at the stage where decisions about data representations have to be made, it often is still difficult to foresee the details of the necessary instructions operating on the data, and often quite impossible to estimate the advantages of one possible representation over another. In general, it is therefore advisable to delay decisions about data representation as long as possible…
(Or as Parnas would advise us, to hide information about data representation from the rest of the program).
With a little thought, Wirth rejects the straightforward 8×8 boolean matrix in favour of an array of columns. Analysing the efficiency of the resulting structure, Wirth then introduces auxiliary variables that make it more computationally efficient to determine whether or not a given square is safe to place a queen on.
Upon every introduction of auxiliary data, care has to be taken of their correct initialization…
The final version of the program still displays the structure of the version designed in the first step… “other, equally valid solutions can be suggested and be developed by the same process of stepwise refinement.
Wirth concludes with five remarks about the process:
- Program construction consists of a sequence of refinement steps
- The degree of modularity obtained during the refinement will determine the ease or difficulty with which a program can be adapted to changes or extensions
- During stepwise refinement, a notation natural to the problem in hand should be used as long as possible… “the direction in which the notation develops during the process of refinement is determined by the language in which the program must ultimately be specified.”
- Each refinement implies a number of design decisions based on a set of design criteria.
- Even the small example program in the paper requires quite a lengthy explanation, indicating that careful programming is not a trivial subject!
Among these criteria [for the design decisions] are efficiency, storage economy, clarity, and regularity of structure. Students must be taught to be conscious of the involved decisions and to critically examine and to reject solutions, sometimes even if they are correct as far as the result is concerned; they must learn to weigh the various aspects of design alternatives in the light of these criteria. In particular, they must be taught to revoke earlier decisions and to back up, if necessary, even to the top.