Most of the thought about how a task should be broken down is done in the design stage. Regardless of the complexity of a design, implementation should remain a fairly straightforward translation process.
Abstraction is the omission of detail for the sake of looking at the big picture. For example, an abstract is an overview of a book or paper that summarizes the whole story with very little detail.
Abstraction can have many levels. The highest level of abstraction covers the whole picture, and has the least detail.
When we go to lower levels of abstraction, we generally focus on only part of the picture. For example, we may have a more detailed abstract for each chapter of a book, and even more detailed abstracts for each section.
A table of contents is another form of abstraction, as is a review article, or an outline.
A top-down design is a multilevel view of something showing a highly abstract level, with very little concern for detail, as well as additional levels with increasing detail for smaller portions of the problem.
Stepwise refinement is the process of creating a top-down design, breaking down a large design into layers of increasing detail.
Consider a house as A simple example. At the most abstract level, as house can be viewed as a set of rooms. At the next level, each room consists of walls, a ceiling, and a floor. A floor typically consists of joists, subflooring, and a floor covering such as carpet or tile.
More detailed views of the house focus on smaller portions of the house, omitting more and more other components. This is necessary
This is the approach we use to deal with anything that is too large and complex to comprehend, whether it be a house, a field of study, or an engineering problem. We choose a balance between breadth and detail, taking more of one and less of the other, depending on the needs of the moment.
The most intuitive way to visualize a top-down design is using a Tree structure view:
 |
The problem with such a tree view is that it generally becomes too wide to represent on paper after 2 or three levels of refinement. The same structure can be rotated 90 degrees and represented as text using indentation to denote the level in the tree. This structure is more convenient to represent in documents, since it mostly grows vertically.
Earth
Africa
Asia
Antarctica
Australia
N. America
Canada
Mexico
USA
S. America
Europe
Top-down designs can be used to represent anything that can be broken down. A design can reveal the organization of physical objects to as much detail as we want, even down to subatomic particles.
Top-down designs can also show the structure of ideas and processes, which is how they are generally used in computer science. In this case, the tree or text diagram indicates a sequence of steps. On the tree, the sequence goes from left to right, and in the text it goes from the top down.
Example 21.1. Ordering Pizza
Order pizza
Decide on toppings
Talk to pizza eaters
Talk to mom
Talk to dad
Talk to brother
Wave at brother so he takes off headphones
Talk to sister
Wave at sister so she gets off the phone
Write down toppings
Decide on a pizza place
Talk to pizza eaters
Same details as above
Decide on pick-up or delivery
Talk to pizza eaters
Same details as above
Get phone number
Check Internet
Check phone book
Call pizza place
Dial number
Wait for answer
Talk to pizza guy
One thing you may notice in the pizza example is that some of the modules we created when breaking down the process are used repeatedly. This is another benefit of breaking down a problem into layers and modules. In addition to simply making the problem manageable, if it turns out that some modules can be reused, the next step of implementing the solution is easier since you only have to implement a module once no matter how many times it is used.
Identifying and separating out modules that can be used in multiple places is called factoring the design (or the code). It is akin to reducing an expression such as xy + xz to x(y + z). It's the same expression, but the latter only represents x once. By factoring a program design, you ensure that each module of code will only be implemented once, which results in a smaller program.
Now let's consider a problem for which we can easily implement a solution on a computer.
Example 21.2. Sorting
Sort list of numbers
Get list
Get number
If not end of list, repeat
Sort list
Find smallest number in list
Assume first is smallest
Compare to next number
If next is smaller, remember location
Repeat compare until end of list
Swap with first
Copy first to temporary location
Copy second to first
Copy temporary location to second
Repeat for remaining numbers
Repeat until only one number remains
Output sorted list
Output number
If not end of list, repeat
Note
The key to stepwise refinement is avoiding the temptation to go into too much detail too quickly. At each step, we only break things down into a few, slightly smaller and less abstract units. We then tackle each of these smaller units in the same way, one at a time, until we have refined all the units at that level.First level of refinement:
Sort list of numbers Get list Sort list Output sorted list
Second level of refinement:
Get list Get number Repeat until end of listSort list Find smallest Swap with first Repeat previous two steps for remaining numbers Repeat previous three steps until only one number remainsOutput list Output a number Repeat until end of list