Next / Previous / Contents / Shipman's homepage

3. Stepwise refinement

Cleanroom is, among other things, a stepwise refinement approach. For any nontrivial system, you will divide the logic of the program as a whole into smaller and smaller pieces, writing intended functions to describe the semantics of each piece, until every piece of the finished system has a well-defined interface and clearly implements its intended function.

3.1. The HIPO model: nested black boxes

The venerable HIPO model of software design is a way of subdividing large problems into smaller ones.

It is useful to model a system as a black box. In this model, the purpose of a system is to transform a set of one or more inputs into one more outputs.

This particular concept came from circuit design. For example, the half-adder is a standard building block for digital logic. It has two inputs A and B, and two outputs called sum and carry. We might draw the black box like this:

If we are building a larger system out of these, all we need to know is the truth tables for the outputs: sum ≡ A ^ B and carry ≡ A & B, where “^” is Boolean exclusive-or and “&” is Boolean and.

The black-box view is sometimes called the IPO model for Input, Processing, and Output. The outputs of this black box are a function of the inputs, and the P stands for the processing done inside the box to convert the inputs to the outputs.

The H in HIPO stands for “hierarchical”: we divide large, complex functional blocks into networks of smaller functional blocks. The final design is a hierarchy of nested black boxes; the system as a whole is the outermost box, and the design consists of subdividing the functionality in each box until we reach simple, single pieces.

Here is the next level of stepwise refinement of our half-adder circuit.

Here we see how the overall inputs (A and B) are routed inside the top-level box to smaller functional pieces, in this case, an XOR gate and an AND gate.

In a circuit design, we could continue this another level, dividing up the AND gate into smaller pieces (transistors).

So it is with software design by stepwise refinement. You start by describing the entire system in terms of the desired outputs, the inputs required to compute those outputs, and the processing that converts inputs into outputs.

In this abstraction, we take a very broad view of what constitutes an input or output. Inputs might include data files, keystrokes on a keyboard, values from a database, messages from the Internet, or anything else that we can operate on. Outputs might include data files, images on a screen, sounds coming from a speaker, or changes to a database.

Note

Principles of good cohesion (what goes on inside each piece) and coupling (the connections between the pieces) are outside the scope of this essay. For an overview, see Wikipedia.