Stepwise Refinement

Shame on you all that I had to add this page on 7th March 2003!

The WikiIsNotaDictionary crowd probably prevented it earlier.

StepwiseRefinement is a relatively old technique of SoftwareDesign that has been successfully used in a wide range of StructuredProgramming and ModularProgramming environments and languages. It is the procedural (step-by-step) form of SeparationOfConcerns and has what some may call a fractal nature of task division.

The principle of StepwiseRefinement kind of tries to roll-up YouArentGonnaNeedIt and KeepItSimple in one and most programmers (at least the GoodProgrammers I've encountered) tend to use StepwiseRefinement intuitively.

The software design is approached as being a series of layers of modules of decreasing abstraction with call flows typically forming hierarchies through the modules. You start by identifying the top of the hierarchy (essentially main() or do_stuff()) and then apply TopDown design to work out the next set of modules that need to be built/written.

StepwiseRefinement can (and often is) also applied even down to the function level in languages such as CeeLanguage.

For example, the top level might be the function main(). The SoftwareEngineer decides that main needs to call foo() and bar(), so she writes the function main() to call foo() and bar() but leaves foo() and bar() stubbed out with printf's. She then runs her UnitTests and confirms that foo() and bar() are called correctly i.e. we get printfs coming out where expected, so main() works. She then implements foo() which is straightforward, and runs the UnitTests once more to verify that both main() and foo() operate together correctly. She then goes back to look at bar() but realizes that bar() needs another lower level function, baz() to work. So, she implements bar() to call baz() but again just leaves baz() stubbed out. Once more the UnitTests are run to confirm that the software works correctly. The final stage is then to implement baz() and finished checking the software with the UnitTests.

The advantage of StepwiseRefinement is that it allows for IncrementalDevelopment but on a much finer level of granularity. A little bit like BarryBoehm's SpiralModel. It also uses UnitTests as an integral feature of the development process. The software is also rapidly built as StepwiseRefinement lends itself naturally to producing working (and tested) prototypes of the software as it develops, and it is often possible to build prototypes in remarkably short periods of time as you can apply YAGNI pretty much down to the function level. StepwiseRefinement is highly scalable, as large systems can be developed in a structured and predictable fashion from it.

The downside is that StepwiseRefinement is open to interpretation of precisely what abstraction functions are required at the higher levels. This generates a tendency towards an architecture that has one larger high-level module with several smaller "worker" modules below it. That is, the hierarchy tends to grow across rather than down (which is the intention).

I'd be interested to hear anyone else's thoughts on this. Having been programming CeeLanguage for a few years now (after being a JavaLanguage and ObjectOriented person for 2 years) I have become quite fond of StepwiseRefinement and really do wonder how people program without it, especially when using StructuredProgramming languages.

If you feel the need, PleaseComment.

Example:

Brush Teeth
- find toothbrush
- find toothpaste tube
- open toothpaste tube
  - Put thumb and pointer finger on cap
  - turn fingers counter-clockwise
  - repeat prior step until cap falls off
- squeeze tube onto toothbrush
  - (details omitted)
- clean teeth
  - put brush on teeth
  - move back and fourth vigorously
  - repeat above step 100 times
- clean up
  - rinse brush
    - turn on water
    - put head of brush under running water for 30 seconds
    - turn off water
  - put cap back on toothpaste
  - put all items back in cabinet

Unfortunately, StepwiseRefinement often leads to a solution where each module represents one part of the task in chronological terms, which can lead to multiple modules knowing the details of some data structures. See DavidParnas' wonderful paper OnDecomposingSystems for examples of different ways to decompose a system, some of which are more robust against changes in data representation.

I don't see wrapping data structures and StepwiseRefinement to be mutually exclusive. DavidParnas paper is flawed in some ways.

They aren't, but it takes care to do both at the same time. The point is that it's very easy to think of the "steps" in StepwiseRefinement as being "steps to solve the problem", which tend to be chronological. For example, if the above "brushing your teeth" system were implemented naively, it would be natural to have subroutines for each line, called by the next higher level and calling the ones at the next lower level, all of which have knowledge of the "toothbrush" and "toothpaste" data structures.

Please explain "which have knowledge"? Perhaps this is related to DatabaseNotMoreGlobalThanClasses.

As far as subroutines, yes in practice one often does such. The above illustrates the design dividing process, not the coding and repetition factoring.

Stepwise Refinement and Deviation Management

"Dealing with Deviations from Framework" under HelpersInsteadOfWrappers illustrates how to use the levels to go lower into the StepwiseRefinement tree to "override" behavior for custom exceptions-to-the-rule, but still potentially use some of the existing branches. -t