Motivation

Stepwise refinement is a term borrowed from computer programing. Briefly, it refers to the practice of designing software from "the top down" or, more accurately, "from the outside in." It is an implementation of the idea that you have to understand the big picture before you can implement the details.

Stepwise refinement is, for most of us, an unnatural act. We want to jump in and DO something right away, we want to be people of action. But when we jump right in we feel the gnawing anxiety of wondering where what we are doing fits in the larger scheme of things (or, at least, we should feel this). And it turns out that that bit of anxiety along with the fact that once you descend to the level of detail you literally cannot see the larger picture, together, lead to inefficiency, error, and failure to complete tasks.

Example 1

Consider this partial brainstormed list of things involved in getting a chicken dinner ready.

Cook. Clean house. Find table cloth. Set table. Get plates out. Choose recipe. Make shopping list. Shop for ingredients. Go to store. Chop vegetables. Preheat oven to 400. Vacuum dining room. Tidy up living room. Put out glassware. Put out silverware. Napkins. Roast chicken. Put chicken in pan.

As is common, the brainstorm has resulted in ideas (actually, things for our to-do list) that are at different levels of "detail" — some of them are "lower down" than others, or, we might say, some contain others. Let's arrange these hierarchically. In other words, let's identify which steps are a part of another step. One way to do this is to think of each action as a set of action:

(1)
\begin{align} Clean house = \{ Vacuum \hspace{3 pt} dining \hspace{3 pt} room. \hspace{3 pt} Tidy \hspace{3 pt} up \hspace{3 pt} living \hspace{3 pt} room\} \end{align}
(2)
\begin{align} Cook = \{ Choose \hspace{3 pt} recipe. \hspace{3 pt} Shop \hspace{3 pt} for \hspace{3 pt} ingredients. \hspace{3 pt} Roast \hspace{3 pt} Chicken. Do \hspace{3 pt} Veggies \} \end{align}
(3)
\begin{align} Set \hspace{3 pt} table = \{ Find \hspace{3 pt} table \hspace{3 pt} cloth. \hspace{3 pt} Get \hspace{3 pt} plates \hspace{3 pt} out. \hspace{3 pt} Put \hspace{3 pt} out \hspace{3 pt} glassware. \hspace{3 pt} Put \hspace{3 pt} out \hspace{3 pt} silverware. \hspace{3 pt} Napkins. \} \end{align}
(4)
\begin{align} Roast \hspace{3 pt} chicken. = \{ Preheat \hspace{3 pt} oven \hspace{3 pt} to \hspace{3 pt} 400. \hspace{3 pt} Put \hspace{3 pt}chicken \hspace{3 pt} in \hspace{3 pt} pan. \hspace{3 pt}Leave \hspace{3 pt} chicken \hspace{3 pt} in \hspace{3 pt} 400 \hspace{3 pt} oven \hspace{3 pt} for \hspace{3 pt} 90 \hspace{3 pt} minutes.\} \end{align}
(5)
\begin{align} Do \hspace{3 pt} Veggies = \{Chop \hspace{3 pt} vegetables. \hspace{3 pt} Cook \hspace{3 pt} vegetables.\} \end{align}

Level zero is just "Make chicken dinner for guests" (pink in the graphic). Below this, at the first level (green) we have "clean house," "cook," "set table," and "eat drink and be merry." At the next level (purple), things like vacuum dining room, choose recipe, find table cloth and roast chicken. At the third level (orange), we have the steps that go into roasting the chicken: put it in the pan, preheat oven, etc.

levels-of-detail.gif

Our zeroth order flowchart would contain just the green steps — they are the first level of stepwise refinement.

make-dinner-level-0.gif

For our next refinement, we can look more closely at a green step, breaking it down into its purple components.

make-dinner-level-1.gif

And, next, we can take a purple level 1 step and break it down into its orange, level 2 sub-processes.

make-dinner-level-2.gif

Review

So what did we do here? First we brainstormed — just thinking about having folks over for dinner sets off all manner of task-thinking in our heads and so we don't fight it. But then we notice that there is some structure, some levels of generality/detail in these things. In fact, we can say that some of them "contain" others — some are steps within others. And when we group everything into a hierarchy of collections we can start to describe the process at the very top level (here it was 1) clean, 2) cook, 3) table, 4) enjoy).

We then treated each of these as if it were a "black box" — that is, a process that we didn't need to know the inside of — and we could just arranged these in the right sequence even as we knew that there were details to be filled in, we made the decision that the big prep tasks : cleanup, cooking, set up could be thought of as the three main steps.

Then, when it came time to think about cooking, we broke it up into four parts, one of which, "roast chicken," we knew had some other steps in it and so we just treated it as a black box, deferring details until our next step of refinement.

There are two important "skills" here — one is being able to recognize "levels" and the other is being comfortable leaving things in black boxes until it becomes necessary to unpack them.

Practice Problem

Consider your "morning routine" — all the things you need to do to get from being asleep to being in class. Brainstorm and list 20-25 things you do to accomplish this transition. Be deliberately "sloppy" and put things at different levels of detail on the list.

  1. Arrange the items hierarchically. You can use the set technique above, or the circle diagram, or just make an outline.
  2. Draw (on paper) a series of four refinements of a flow chart that represents this process. The first should use three sequential process rectangles. Each successive refinement should "blow up" one step from the previous refinement. You may have to "invent" new sub-processes if your original list doesn't have four levels (note that this is a place where we would use the word analysis — it's original meaning is "to break up into parts").

Example: Get up. Drive to school. Go to class. Start car. Follow usual route. If heavy traffic follow alternative route. Drink OJ. Eat breakfast. Shower. Wash hair. Brush teeth. Make coffee. Fill coffee maker. Perform ablutions.

Stop and Think: (1) Challenges to starting simple and high level, deferring detail? (2) Do you have a consistent level of detail in each version. (3) Where does the information for contingencies — diamonds — come from?

Stepwise Refinement

The thinking process described above can be converted into a deliberate strategy for designing or describing systems. The technique is borrowed from computer science where it was most famously described by Niklaus Wirth in the 1970s1. The technique of stepwise refinement is essentially one of mental discipline that can be expressed this way: "defer details." What we want to do is to think about systems or processes from the top down or outside in. Start with the least focused picture you can — ignore any urges you have to get mired in detail. One strategy is to start with the most generic form a process can have: a beginning, some action(s), and an end:

simple-flow-chart-vertical.gif

The usual convention is to draw a flow chart vertically with "time" running from top to bottom — that is, the process starts at the top and goes to the bottom. But it's just as well to turn the flow chart on its side and have things move from left to right:

simple-flow-chart-horizontal.gif

What we do next is to "unpack" that box that says "action" one step at a time. Let's look at another example.

Example

Suppose that our process is offer hospitality by which we mean to serve beverages — coffee or tea. The simplest flow chart would look like this:

flowchart-beverages.gif

Notice that we are deferring detail here. This might be called a "zeroth order" flowchart. It has an entry/beginning and and exit/end and there is an action step in between. Now let's image we can turn up the magnification one notch and ask what that action step consists of. In plain language: we ask whether our guest would like coffee or tea and then we prepare and serve accordingly.

flowchart-coffee-or-tea.gif

Again, we are deliberately avoiding going into detail here. This is a general principle: defer detail. Don't worry, we are going to produce several iterations of most flow charts and we'll add appropriate levels of detail as we go along.

Any step of a process is subject to further refinement, of being represented in greater detail. What would be the next level of detail for the process of making coffee?

Some candidates: measure coffee, decide on beans to use, brew the coffee, grind beans, prepare dry coffee, boil water, add boiling water, get filter, add milk, add sugar. But these are not at the same level of refinement or detail. Some of them "contain" others. For example:

(6)
\begin{align} brew \hspace{3 pt} coffee = \{ prepare \hspace{3 pt} dry \hspace{3 pt} coffee, \hspace{3 pt} boil \hspace{3 pt} water, \hspace{3 pt} add \hspace{3 pt} boiling \hspace{3 pt} water \} \end{align}
(7)
\begin{align} prepare \hspace{3 pt} dry \hspace{3 pt} coffee = \{decide \hspace{3 pt} on \hspace{3 pt} beans, \hspace{3 pt} grind \hspace{3 pt} beans, \hspace{3 pt} measure \hspace{3 pt} coffee, \hspace{3 pt} get \hspace{3 pt} filter \} \end{align}

If we think only about one level of refinement beyond "make coffee" (remember: defer detail whenever possible) we might list

  • brew coffee
  • pour
  • add sugar
  • add milk
  • serve

But do we always want to add sugar and milk? No, only if the coffee drinker wants them. Therefor our flow chart is going to have to represent these contingencies. Here is the above flow chart with the single step, "make coffee," blown up into its next level of refinement:

flowchart-coffee-detail.gif

TAKEAWAYS

  1. Start from the outside and move in. Top-down. Stepwise refinement. Defer detail.
  2. Strive for consistent "levels"
  3. Every unit/module has single entry and exit point.

Practice Problem

Draw a flow chart representing the task of getting home from work by car : (1) leave; (2) drive; (3) arrive.

It is easy to get lost in the complexity of nuance and micro-considerations when describing a process, the more so when you know a lot about something. The skilled flow charter is able to defer consideration of detail in an orderly manner. She might, for example, draw a first flow chart of the above process that looks like this:

drivinghome-stepwise-refine01a.gif

And then she might think: "What is the NEXT level of detail here?" and think about the fact that getting home consists of three phases. One is getting to the car, putting books and such in the back seat, turning on engine, buckling up, selecting a radio station, and making her way to the campus exit. Then there is the getting home part. This involves selecting a route, perhaps making some stops, being subject to delays and such thrown at her by the rest of the world. And finally there is arriving at home, finding a parking spot, grabbing all of her stuff, locking the car, finding the car keys, etc. She has just articulated all manner of detail but defers thinking about these, instead refining the task into just three major sub-processes:

drivinghome-stepwise-refine01b.gif

And what will be her next refinement. A good practice is to further refine just one thing at a time. Here she selects the "drive home" step because it's the one that has some real variation from day to day. Specifically, it involves listening to the traffic report on the radio and then picking a route home based on where the traffic seems to be worse. She doesn't detail her decision making process yet, but shows where it comes in the sequence of things.

drivinghome-stepwise-refine01c.gif

Finally, she'll refine the "take the best route" sub-process. It involves using the information she gets from listening to the radio to decide between one of two routes. The question or condition she evaluates is: "Is 580 backed up?" Her "protocol" is "take highway 13 if it is, other wise take highway 580."

flow-chart-drivinghome-01.gif

The figure below illustrates these four phases of stepwise refinement. Two things to notice. First, we refined one thing at time. The light blue trapezoids show how a step in a diagram to the left is refined (expanded) in next flow chart to the right.

drivinghome-stepwise-refine01.gif

Second, the new flow chart elements "fit completely inside" the element they are a refinement of. For example, in the third chart, the box "take best route" has a single entry point and a single exit point. At a certain point in the process we "enter" this step and then when it is done we exit. In the third chart, just what happens during the step is not specified; it is a so-called "black box." In the fourth chart this step is expanded, but notice that the "if block" it expands into has a begin circle at the entry point and an end circle at the exit point. These correspond to the single entry and single exit in the previous step.

drivinghome-stepwise-refine01d.gif

Here we want to learn how to read and make flowcharts, understand the concepts of stepwise refinement, top-down design, and "black-boxing," and how to translate verbal (and ethnographic) descriptions into flow charts.

References

  1. Wikipedia articles on Flow Charts
  2. Flow Charts for Simple Tasks: Tutorial with exercises at Univ Plymouth, UK
  3. Flow Charts for Classification: Tutorial with exercises at Univ Plymouth, UK
  4. An overview by HCI consulting in Australia

See Also

Gehani, N. 1981. "Program Development by Stepwise Refinement and Related Topics." Bell System Technical Journal, vol. 60, no. 3.