Chapter 6
Software Design
Software design is the process of decomposing a software problem into subsystems that interact to form a working whole. A well designed program is flexible, extensible and maintainable, and the key to such design is modularity. A modular design permits di erent parts of the program to be built and debugged in isolation. Thus, large-scale systems may be built without an overwhelming growth of complexity induced by dependencies between subtasks.
The process of software design usually involves a series of steps starting from stating the basic program requirements, and successively adding detail. A typical progression is as follows.
• Requirements and specification. The required program operation is described at a general and then a detailed level.
• Program flow. The flow of steps, decisions, and loops are planned, usually in the form of a diagram. This stage indicates dependencies between di erent subtasks. That is, it defines the sequence of operations, and the requirements for communication of data.
• Data structures. The format of variable types for passing data between functions must be chosen in order to design function interfaces.
• Top-down and/or bottom-up design. The structure and components of the program have to be designed. These two design paradigms facilitate organising overall structure and individual modules, respectively.
• Coding. Having produced a plan of how the program should appear, the problem becomes a matter of implementation. The process of coding often uncovers flaws in the original design, or suggests improvements or additional features. Thus, design and implementation tend to be iterative and not a linear progression.
• Testing and debugging. All non-trivial programs contain errors when first written, and should be subjected to thorough testing before being shipped to customers. Methods for systematic testing and debugging are beyond the scope of this text (for more information see, for example, [KP99, Ben00]).
It is important to realise that there are no hard-and-fast rules for good design. Software design is in part principles and formal methodologies, and in part an artform requiring experience and taste.
6.1 Requirements and Specification
In order to write a program, it is first necessary to know what function the program is to perform. The first stage of design is to state a set of requirements, in general terms, for what the program
is to do. For small projects, this might be su cient and programming can commence immediately. However, for larger projects, these general requirements need to be refined into a more detailed specification.
A program specification is a more formal and detailed description of the program’s operation. It defines particulars like input and output formats, responses to various events (such as user requests), and e ciency requirements. A specification may evolve during the program’s implementation, as di culties and new possibilities come to light. It is important to realise that design is an iterative process of refinement, not a linear progression from concept to code.
6.2 Program Flow and Data Structures
Given a specification of the program’s operation, it is a good idea to draw a diagram of the way the program will progress from initialisation to termination. Various formalisms exist for describing program flow, such as flow diagrams and state-transition diagrams. The key idea is to visualise how the program transitions from one state to another and what dependencies exist between di erent parts of the program.
Having defined dependencies, the variable types used to communicate data between di erent parts of the program should be specified. In addition to the basic types, C permits a programmer to create user-defined types of arbitrary complexity (using structs, for example), and these types are collectively termed data-structures.1 Following the definition of key data-structures, it becomes possible to start designing function interfaces.
6.3 Top-down and Bottom-up Design
The top-down approach to design is to start with a set of high level tasks that will be called from main(), and recursively splitting each task into subtasks until a level of complexity is attained that permits the definition of reasonably simple function modules.
This idea of solving a problem by divide-and-conquer is illustrated in Figure 6.1, which shows a hierarchy where the higher-level functions are implemented in terms of the lower-level functions. Top-down design is useful for defining the overall structure of a program, and the dependencies between functions. Usually, the functions are first implemented as interfaces only, with do-nothing internals (also called “dummy” internals). This allows the program to run, albeit without any real utility, and individual functions can be written and tested within a working skeleton program. Thus, the entire program shell is laid out at the start, and the function internals are subsequently built and debugged one-at-a-time.
A key limitation of top-down design is that the resulting functions tend to be problem-specific (i.e., specific to the program at hand). They tend to be non-reusable, and the top-down design of each new project must start from scratch.
The bottom-up approach to software design is to identify various components that will be required by the program, and to build them in isolation from any design of the overall program structure. Assuming the appropriate argument types are known, the function interfaces can be designed, after which the internal implementations are usually straight-forward.
An advantage of bottom-up design is that the resulting modules are often more generic than those designed in a top-down approach. They tend to be less tied to the program at hand and more amenable to reuse. In the best-case, a bottom-up component can be designed even without knowledge of program dependencies; it is su cient to just assume an interface and build an algorithm
1 Data-structures are discussed further in Chapters 11 and 15.
2 In the event that a bottom-up designed function has an interface that doesn’t quite match the interface required by a particular program, it may be adapted to the task by using an “adapter function” (also called a “wrapper function”). These functions simply accept the interface required by the program and convert their arguments to the form required by the component function and then invoke this function. The adapter function does no work of its
Figure 6.1: The top-down design approach. Starting from the highest level functions called from main(), recursively divide the program into sub-problems until the desired level of complexity is met. For example, the task of function f3() is implemented in part by the functions f3a() and f3b(), which each perform a particular subtask.
components form a library or toolbox of reusable modules that may be carried over from one project to the next. The C standard library is a good example of reusable bottom-up design.
The downside of bottom-up design is that it does not give a clear indication of how the individual program elements should be merged together. It does not present the “big picture”, the overall structure of the program with its dependencies and function-call hierarchy. In addition, because components are developed in isolation, they often require the writing of drivers to permit testing and debugging. These drivers are small test programs that allow one to check the response of a component to various inputs. Writing drivers for a large number of di erent components can be a tedious process.
Top-down and bottom-up design are complementary, and practical design tends to use both strategies, working at both ends until they meet in the middle. Top-down design composes the overall program structure and call hierarchy, and bottom-up design builds key functionality and reusable components.
