Modular Design

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 and Layers

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.

    N. America
    S. America

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 20.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 20.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


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:

  1. Sort list of numbers
        Get list
        Sort list
        Output sorted list

Second level of refinement:

  1. Get list
        Get number
        Repeat until end of list
  2. Sort list
        Find smallest
        Swap with first
        Repeat previous two steps for remaining numbers
        Repeat previous three steps until only one number remains
  3. Output list
        Output a number
        Repeat until end of list


An important part of using top-down design and implementation is to stay focused on one layer and finish it before starting the next. If you don't, you will find yourself redoing an entire subtree when you alter the design at a higher level.