Tutorial : C - Software Design

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

 

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 sufficient 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 efficiency requirements. A specification may evolve during the program’s implementation, as difficulties 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.

 

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 different parts of the program.

Having defined dependencies, the variable types used to communicate data between different 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. Following the definition of key data-structures, it becomes possible to start designing function interfaces.

 

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, 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 sufficient to just assume an interface and build an algorithm. Such 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 different 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.

 

Pseudocode Design

When designing the implementation of a particular function, it is sometimes helpful to write an outline of the algorithm at an abstract level in pseudocode rather than immediately writing C code. This form of function-level design concentrates on the algorithm structure without getting bogged down in syntactical details.

Pseudocode, also called program design language, is basically an English description of a code segment’s intent. For example, consider the following pseudocode to get values from the user and compute their factorial.

loop number of times
prompt user and get integer value
calculate factorial
print factorial

Given a pseudocode layout, it becomes straightforward to replace the pseudocode with C constructs. In sections where the code intent is not obvious, it is good practice to leave the original pseudocode in place as a comment.

 

Case Study: A Tic-Tac-Toe Game

As an example of modular program design, this section presents the design and implementation of a simple game: Tic-Tac-Toe (also known as Noughts-And-Crosses). This program is simple enough to describe in a reasonable period of time, and complex enough to demonstrate the concepts required for larger-scale programs.

 

Requirements
The aim of this program is to play a game of Tic-Tac-Toe against the computer. To begin, the user is welcomed to the game and asked if he wishes to have first go. The following game is turns-based, alternating between a request for the user’s move, and the computer’s own-move decision. After each turn, the result is printed in ASCII and, if there is a winner or a draw, the user is asked if he wishes to play again.

 

Specification

The program is to print a welcome message to introduce the game and its rules

Welcome to TIC-TAC-TOE.
-----------------------

The object of this game is to get a line of X’s before the computer gets a line of O’s. A line may be across, down, or diagonal.

The board is labelled from 1 to 9 as follows:

1|2|3
-----
4|5|6
-----
7|8|9

This is followed by a request for whether the user wishes to start, with the integer 1 meaning ‘yes’ and 0 for ‘no’.

Do you wish to go first (1-Yes, 0-No) ?
Each time the user is to make a move, a request is made for which location he wishes to choose, designated by a number between 1 and 9.

Your turn (1 - 9):

After the user or the computer has made a decision, the resulting table is printed in ASCII. For example, after 5 turns, the board might look like

X| |
-----
X|O|
-----
 |X|O

The game will terminate with a winner or a draw, and a comment is to be printed on account of the user’s win, loss or draw, respectively.

You win. Congratulations!!
You lose. Better luck next time.
Its a draw. How dull.

Finally, the user is asked if he wishes to play again and, if so, the game returns to the request of whether he wishes to have first go. Otherwise, the program terminates.

Do you wish to play again (1-Yes, 0-No) ?

 

Program Flow and Data Structures

A rough sketch of the flow and dependencies of the program. Such diagrams are very useful for getting an initial impression of modular composition and interaction. For smallscale projects, a simple hand-drawn diagram may be sufficient; for larger or team-built programs, they are typically precursors to more formal design diagrams. there are a series of initialisation operations—a welcome screen and a prompt asking whether the users wants to go first—and then a main game-play loop. The game loop takes each player’s decision in turn, prints the resulting game-board, and determines if the game continues or is over. On game-over, a message is printed based on the result (win, lose, or draw), and the user can choose to play again or quit.

The internals of this program are very simple, but it is necessary to specify the main variable types as they will affect the design of the function interfaces. From the flow diagram, it can be seen that there are three key data structures passed between the various functions. The first is the current state of the game for each of the nine locations on the Tic-Tac-Toe board. Each location may be in one of three states: empty, cross, or nought. It was decided to make the game states an integer array, and the possible states enumerated constants.

#define NUMSTATES 9
enum { NOTHING, CROSS, NOUGHT };
int state[NUMSTATES];

 

The other two data structures are the state of whose current turn it is (user or computer) and the state of the game result (still playing, user won, user lost, or draw). These variables were chosen to be enumerated types, and their possible states given by enumerated constants.

enum Turn { USER, COMPUTER };
enum Result { PLAYING, WIN, LOSE, DRAW };
enum Turn turn;
enum Result result;

 

Bottom-Up Design
 
Looking at the program specifications, there are several functions that can be designed immediately without knowledge of the overall program structure. Consider the following examples. All the input requirements for this program are solitary integers. Therefore it is worthwhile to write a function that extracts an integer from the keyboard input, and does appropriate input validation and error handling. This function would be passed a message string to prompt the user, and would return an integer.

int getint_from_user(char* message);

 

In the case of bad input, an error message would be printed and the prompt message reapplied. Given that the current state of the game is stored in an integer array, a function can be built to print the output in ASCII. This function would have the following interface

void plot_state(int state[]);

 

We assume the number of states (9 for a 3x3 game) is known and defined by a symbolic constant, so it need not be passed as a function argument. Another function dependent only on the current state of the game is the computer’s decision making process. This function encapsulates the algorithm for choosing the computer’s next move.

void get_computer_decision(int state[]);

 

The algorithm might be dumb, such as a random choice from the set of available locations, or smart, such as an exhaustive search of the game decision tree. Because the algorithm implementation is hidden, different algorithms can be trialed and debugged without change to the rest of the program.

Finally, another function well-suited to bottom-up design is the algorithm that determines whether the game is to continue playing, or if it has finished with a winner or a draw. This function requires only the current game state, but may be made more efficient if given the most-recent move as well. In the implementation shown, the current state and the most-recent player (user or computer) are passed.

enum Result compute_result(int state[], enum Turn turn);

 

Top-Down Design
 
The structure of the program is refined by a top-down process, starting from the highest level functions called from main().

int main(void)
{
	enum Turn turn;
	enum Result result;
	int newgame = 1;
	welcome();
	while (newgame) {
		turn = who_goes_first();
		result = play_game(turn);
		gameover_message(result);
		newgame = play_again();
	};
	goodbye();
	return 0;
}

 

The choice of enumerated constants, and function and variable names makes the operation of main() quite clear, even without any comments. The functions all specify high-level operations and no lowlevel details are present to confuse the intent of the program. This approach greatly simplifies implementation changes and extensions. Implementation of these functions begins by writing all the definitions without any internals (except a return value, if required). Then the algorithms for each function are added and tested one-at-a-time.

The top-down heirarchy of this program. All of the top-level functions are quite trivial, except for play_game(), which is split recursively into smaller subtasks. The structure obtained from this design meets with the bottom-up design of the various modules described previously, and turning the overall design into code from this point is straightforward.

 

Benefits of Modular Design

This design encloses each operation within a function. The function interfaces are minimal and decoupled, and completely hide any implementation details. The benefit of this modularity is that the code is flexible; changes and extensions are simple to implement.

Consider the following examples. One, it is possible to change the welcome and goodbye messages easily. Two, all input handling is encapsulated within the function getint_from_user(), which incorporates appropriate error checking. And three, if the game is ported to an environment with a graphical interface, only the input-output functions need to be revised.

By far the most technical part of this program was the computer decision-making function get_computer_decision(). To get the computer to make good choices is not trivial. However, to make the program run does not require an intelligent opponent, and a very simple random selection scheme was sufficient. Once the rest of the program was fully tested, it was straightforward to write cleverer decision-making code. This is a good example of hiding an algorithm behind an interface, allowing various implementations to be tested and compared without change to the rest of the program.