Verifying a solution means checking that program segments and functions do their tasks correctly. It is difficult to verify programs, although some formal methods are known. This text will illustrate how a program can be verified informally, but rigorously, for appropriate examples. For most of the small examples, verification is left to the reader.
Although only proper verification can ensure the correctness of a program, debugging can help in locating mistakes. Your goal should be not to run or even code programs until you are sure the algorithm is correct. Even if you are sure of the algorithm, debugging tools should be employed. Then, when your program fails to work correctly (as you know by now it will), you can track down the cause without the help of a Holmes or Watson.
In addition to debugging aids provided by your computer system and compiler, good programming techniques facilitate debugging. For example, it is important to learn to display appropriate error messages and information. The top-down approach includes debugging individual functions or program segments as they are refined, so that debugging proceeds as the program is developed. Verifying, debugging, and documenting all require basic understanding of the program and much the same information. To a large extent, then, they should be done concurrently with program development. During development you have the concepts and information fresh in your mind.
The main program and the other functions may each be debugged independently, just as they may be verified and documented independently. This requires stubs and drivers.
A stub takes the place of a function. It should have the same name and parameters as the function and, when called, should output a message indicating it was called. For example,
A driver plays the role of a function that calls another function, and is used to debug the called function. The driver should set up test values for the parameters used by the function it calls, output those values, call the function, and output the returned values. For example,
Using drivers and stubs allows any individual function to be tested and debugged even though the functions that call it and are called by it have not yet been written. Within the function, program segments that correspond to algorithmic tasks can be isolated. A statement can be inserted before and after each of these segments to output a message indicating that the segment was reached during execution, giving the values of variables it worked on, specifying that it was exited during execution, and giving the modified values of the variables.
In this way, you can see the progress of a program during its execution by studying the output of the drivers, stubs, and function being tested. With this approach, you never find yourself with a program that has not run correctly and for which you have no output, or output that gives no clue as to what went wrong or where. Suppose function M has just been refined and is to be tested and debugged. Its refinement may include calls to other functions not yet written or debugged. To test and debug M you must
1. Write a driver to call M and feed it test data on which to work
2. Replace each function of M's refinement by its own stub
For example, to test and debug remove (Figure 1.3) requires
1. A driver to call remove and feed it test values for n and candidates
2. Replacing nonprimes and delete by their individual stubs
This assumes that primes (which calls remove) and noprimes and delete (which remove calls) have not yet been verified or even written.
Instead, suppose primes has already been debugged. Primes, in conjunction with the driver used to debug it, could then be taken as the basis for remove's driver. Next, this driver plus remove could be used as the basis for delete's driver. This way of proceeding parallels the top-down development of the program. It amounts to inserting one new function at a time into an already debugged program.
To illustrate the proper way to use debugging statements, a complete listing and output is given for an execution of the case study program later in the chapter.
remove (n,c)
/* This is a stub for remove */
int n;
collection c;
{printf ("\n remove was called \n");}
removedriver ()
/* This is a driver for remove */
{collection candidates;
int n;
int sentinel = -1;
printf("\n enter a value for n between 2 and 27 \n");scanf("%2d",&n);while (n != sentinel)
{printf("\n remove has been called with n = %d\n",n);create(n,candidates);
print(n,candidates);
remove(n,candidates);
printf("\n remove returns n = %d ", n);printf("and candidates: \n");print(n,candidates);
printf("\n enter a new value for n or -1 to stop \n");scanf("%2d",&n);}
}