Laboratory Notebook

Chapter 7 - Debugging

Geof Pawlicki

Your name: | |

Your email address: | |

Your student ID number: |

Once this form has been customized for your
institution, you can use this button

We would like to thank Dr. Leslie Foster for contributing the "Pascal Triangle" debugging exercise.

To gain experience with

- designing stubs for testing components of your programs in isolation
- the principles of test case selection and evaluation
- using assertions to document program assumptions
- the debugger
- strategies for effective debugging

Testing a function for run time errors in context of an ongoing project is always difficult. The source of an error may well be obscured by other functions, there could be more than one error, it might arise under unusual circumstances or even appear to go away. Testing a new function in isolation, before adding it to a project gives you an excellent opportunity to locate errors before they become lost in a broken project.

Testing in isolation is called *unit testing*. It requires a *test
stub*, that is, a function `main()` that calls your new
function with parameters obtained from 1) user input, 2) a file or 3) a
function that generates parameter values.

Write two test stubs for the following function. The first test stub takes test values from prompted user input. The second test stub generates test cases randomly.

public class FindFirst { /** * Search a string for a substring * @param s the string to look in * @param sub the string to look for * @return if found, the integer position of sub in s else, -1 */ public static int findFirst(String s, String sub) { int i = 0; while (sub.length() + i <= s.length()) { if(s.substring(i, i + sub.length()) == sub) return i; else i++; } return -1; } public static void main(String[] args) { String searchFor; String searchIn; boolean done = false; while (!done) { /* Your work goes here (get test cases consisting of two strings for findFirst()) */ } } }

- Test stub having user input test cases.

/* paste program here */ - Test stub having randomly generated test cases.

When generating test cases randomly, be sure to include both positive and negative tests. That is, use 1) a random substring taken from the teststring and 2) some other random string.

Hint: We have no function to generate a completely random string, but you can write one! Make a string of the 26 lowercase letters, then extract single-character length substrings from it at positions generated by

`Numeric.randomInt(0, 25)`and concatenate them./* paste program here */

It is of couse tedious to type in lots of test data every time you find a bug in your code. How can you reduce that workload ?

Did you think of boundary cases? What would be boundary cases in this example?

Now run the following function through two test procedures (manual and automatic test case generation)

/** * Searches for last occurrence of one string in another * @param s the string to look in * @param sub the string to look for * @return if found, the integer position of sub in s else, -1 */ public static int findLast(String s, String sub) { int n = s.length; while (sub.length() <= s.length()) { if(s.substring(s.length() - 2 - sub.length(), s.length() - 2) == sub) return n - s.length(); else s = s.substr(0, s.length() - 2); } return -1; }

What is the error?

Did one of your test cases catch it? Which?

Test cases should provide *complete coverage* of each instruction
branch in your function. Every branch, for example both statement blocks
in an `if - else` pairing, should succeed and fail at least once
each.

/* Simplified calculator to perform two variable arithmetic */ public static void main(String[] args) { System.out.println("Enter an arithmetic expression (e.g. 2 + 3):"); double left = Console.in.readInt(); String op = Console.in.readWord(); double right = Console.in.readInt(); double answer = 0; if (op.equals("+")) { answer = left + right; } else if (op.equals("-")) { answer = left - right; } else if (op.equals("*")) { answer = left * right; } else if (op.equals("/") { if (right != 0) { answer = left / right; } else { System.out.println("Divide by 0"); return; } } else { System.out.println(op + " is an unknown operation."); return; } System.out.println(left + " " + op + " " + right + " = " + answer);; }

Give a set of test cases for `left, op`, and `right`
that provide complete coverage of all branches.

Compile and run the program, then enter the test cases that you supplied. Does each branch work as expected ?

Having tested the input to a function, how can the output be validated? You can :

- Pick inputs that have known results
- Use an inverse function to undo a result in order to compare it with the input
- Compare result with an answer obtained another way

Let's test the `power()` function from page 273

/** * Compute an integral power of a number * @param a the number to be raised to an integral power * @param n the power to which it is to be raised * @return a to the nth power */ public static double power(double a, int n) { double r = 1; double b = a; int i = n; while (i > 0) { if(i % 2 == 0) /* n is even */ { b = b * b; i = i /2; } else /* n is odd */ { r = r * b; i--; } } return r; }

- Write a program that uses the reciprocal
`Math.sqrt`to test whether`Math.sqrt(power(x,2)) == x` - If the test succeeds, how much confidence do you have that
`power`is correct ? - Use the fact that x
^{y}= e^{y.log(x)}. Write a program that computes the`power`function in another way, and compares the two values. - (Extra credit) Which way is actually faster,
`power(double a, int n)`or x^{y}= e^{y.log(x)}?

Use the `fib` function in ch12/fibloop.cpp as an oracle to test
whether the following function is correct:

/** * Compute a Fibonacci number * @param n an integer * @return the nth Fibonacci number */ public static long fibonacci(int n) { return (long)(Math.pow((1 + Math.sqrt(5)) / 2, n) / Math.sqrt(5) + 0.5); } public static void main(String[] args) { System.out.print("Enter the number of the Fibonacci number to be computed: "); int fibNumber = Console.in.readInt(); /* your work goes here */ }

Throw an `IllegalArgumentException` in the following example to
signal that an improper input has occurred and to prevent the bad
parameters from being utilized by the function.

import ccj.*; public class PrecondExercise { /** * Compute seconds from midnight * @param hours hour of a clock time (between 0 and 23) * @param min minutes of a clock time (between 0 and 59) * @return the number of seconds between midnight and the clock time */ public static int convertToSec(int hours, int min) { /* your work here -- assert that hours and min are within input range */ return hours * 3600 + min * 60; } /** * Compute the number of seconds between two clock times * @param hfrom the hours of the earlier time * @param mfrom the minutes of the earlier time * @param hto the hours of the later time * @param mto the minutes of the later time * @return the number of seconds between them */ public static int secondsBetween(int hfrom, int mfrom, int hto, int mto) { int secs = convertToSec(hto, mto) - convertToSec(hfrom, mfrom); /* your work here -- assert that the from time is before the to time */ return secs; } public static void main(String[] args) { System.out.print("Input start time: (hh mm): "); int startHr = Console.in.readInt(); int startMin = Console.in.readInt(); System.out.print("Input end time: (hh mm): "); int endHr = Console.in.readInt(); int endMin = Console.in.readInt(); System.out.println(secondsBetween(startHr, startMin, endHr, endMin) + " seconds elapsed"); } }

How does your program handle

- input error, ie.
`start > end`?

`hours > 23`or`minutes < 0`

A program trace is the result of print statements at known points in a
program. It shows that the program has executed commands up to a certain
point. For example, the following `main()` function documents the
parameters to `power(int a, int n)`.

public static void main(String[] args) { double answer = 0; System.out.print("Enter the number to be raised to a power: "); double a = Console.in.readDouble(); System.out.print("Enter the power to which " + a + " is to be raised: "); int n = Console.in.readInt();System.out.println("Before call to power(a,n), a= " + a + " n= " + n + " and answer = " + answer);answer = power(a, n);System.out.println("After call to power(a,n), a= " + a + " n= " + n + " and answer = " + answer);}

Add print statements to the preceeding `power(int a, int n)`
function to document all changes to variables `r, a` and `n`.
Show the resulting trace when `power` is called with `a = 3`
and `n = 11`.

The following portion of the lab is designed to have you practice some of the basics of debugging. Copy the following program listing into a new file called pastri.cpp on your hard drive.

import ccj.*; public class Pastri { /** * skip n spaces on a line * @param n - the number of spaces to skip */ public static void skip(int n) { int i; /* a counter */ for (i = 0; i <= n; i++ ) System.out.print(" "); } /** * calculate n factorial * @param n calculate the factorial of n * @return n! */ public static int factorial(int n) { int product; /* accumulator for the running product */ int i; /* a counter */ product = 1; for (i = 1; i <= n; i++) { product = product + i ; } return product; } /** * calculate the number of combinations of n things taken * k at a time (n choose k) * @param n the number of items to choose from * @param k the number of items choosen * @return n choose k */ public static int combination(int n, int k) { int comb = factorial(n) / factorial(k) * factorial(n-k); return comb; } public static void main(String[] args) { int nrows; /* the number of rows to print */ int n; /* a counter for the current row */ int k; /* a counter for the current column */ int comb; /* the number of combinations */ int spacesToSkip = 36; /* spaces to skip at the beginning of each row */ System.out.print("Enter the number of rows (<=13) in Pascal's triangle: "); nrows = Console.in.readInt(); System.out.print("\n\n\n"); /* print the title * / System.out.println("THE FIRST " + nrows + "ROWS OF PASCAL'S TRIANGLE"); / * start a loop over the number of rows */ for (n = 0; n < nrows; n++) { skip(spacesToSkip); /* space to make a triangle */ spacesToSkip = spacesToSkip - 2; for (k = 0; k <= n; k++) { comb = combination(n,k) ; Console.out.printf("%4d",comb); } System.out.println(); n++; } } }

The program's purpose is to display Pascal's Triangle, a sequence of integers that arises in numerous areas of math and computer science, especially combinatorics and probability. When completed, the program's output should be:

Enter the number of rows (<= 13) in Pascal's Triangle. 5 THE FIRST 5 ROWS OF PASCAL's TRIANGLE: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Entries in Pascal's triangle are indexed by integers. `n` is the
number of the row and `k` is the position from the leftmost member
of the row. The indexes in both directions start at zero (0), so in the
fifth row listed above, C(4,0) = 1, C(4,1) = 4, and so on.

The values themselves are computed by the formula `C(n, k) = n! / (
k! (n-k)!)`, which is called a *combination*. `n!`
denotes a *factorial*, that is, the product `n(n-1)(n-2)...(2)(1)`.
The combinations can be interpreted as the number of ways to choose `k`
elements from a collection containing `n` elements. When
described, it is customary to say "n choose k", for instance '4
choose 3 is 4' ".

If 4 objects are numbered 1 through 4, how many ways can you select 2 of them ? Show all the possible pairings here. Then compute C(4, 2) by using the formula.. Does it match the number of selections?

As you will discover with the help of your debugger, the program to compute Pascal's triangle has some mistakes. Each provides an opportunity to learn a debugging concept in context of it's use.

- Load the file Pastri.java into your compiler.
- Select the
*Run*command from the debugger menu. - and enter
`5`for input (the number of rows for the program to display)

What output is displayed?

- Use the
*Reset*command to reset your debugger - Then use the
*Step Into*command to restart the program from the very beginning. - Now use the
*Step Over*command several times, until the active line isnrows = Console.in.readInt();

- Select
*Step Over*again - The program is now expecting keyboard input because the
`Console.in.readInt()`method is being executed. - Type
`5`(followed by the Enter key) for the input.

On what line is the cursor positioned now ?

- Select your compiler's
*Inspect*command. - Inspect the value of
`nrows`

What is the value for `nrows` shown in the dialog box?

- Select
*Step Over*twice - Look at the output for Pascal's triangle.

Does the output have the title: ` TABLE 1: THE FIRST 5 ROWS OF
PASCAL'S TRIANGLE `?

That is strange. The program is supposed to print three newlines, then the title. Let's find out why the title doesn't appear.

- Select
*Reset*the to start the debugger once again. - Select
*Step Into* - Then select
*Step Over*until you reach the line prompting for input.. - Enter
`5`for`nrows` - Select
*Step Over*one more time. This should skip over the line`System.out.print("\n\n\n");` - Select
*Step Over*one more time.

What line are you on now?

- Notice that you skipped over the line

`System.out.println("THE FIRST " + nrows + "ROWS OF PASCAL'S TRIANGLE");`

The reason is that two delimiters for comments had extra spaces in them. - Change the line

`/* print a title * /`into

`/* print a title */`

and the line

`/ * start a loop over the number of rows */`into

`/* start a loop over the number of rows */`

When you changed the positioning of the comment delimiters, did any changes occur to the commented text? This depends on your development environment--describe what happened, if anything.

- Recompile your program to incorporate your changes.
- Select
*Reset* - Then select
*Run*to run the program. - Enter
`5`for the number of rows. (Use`5`for input for all the runs until part 11, below).

Does the title now show up on the screen?

How many rows of Pascal's triangle are displayed?

- To find out why there are not five rows, return to the source code by pressing enter.
- Select
*Add watch* - Add
`n`to the watch list. You will likely get a message such as`n: Undefined symbol`. The variable`n`is undefined because you haven't yet started the program. - Select
*Add watch*again - Add
`k`to the watch list.

How many lines are now in the watch window?

*Reset*and*Step Into*.- Select
*Step Over*until you reach the line`skip(spacesToSkip); /* space to make a triangle */`

What values of `n` and `k` are in the watch window? (If
the watch window isn't present select *View Watch*.)

- Keep selecting
*Step Over*until you are again at the line`skip(spacesToSkip); /* space to make a triangle */`.

What are the values of `n` and `k`?

- Keep selecting
*Step Over*until you exit the`for`loops and arrive at the line`System.out.println();`

Now what are the values of `n` and `k`?

- View the program output. Notice that there are only three rows in the
triangle. This is because the
`n`values listed above went from 0 to 2 to 4 to 6. That is, the loop index*i*should have been increased by one each time, not two. - Change the line of code:
`for (n = 0; n < nrows - 1; n = n + 2)`to be`for (n = 1; n <= nrows; n++)` - Recompile
- Select
*Run*and input`5`to the program where prompted. You should now have five rows in the triangle.

- The entries in the triangle are still incorrect. To see one reason
why,
*Reset*and*Step Into*the program, then press*Step Over*quite a few times, until the watch window first displays:n: 2 k: 0

You should be at line`comb = combination(n, k);` - Press
*Step Into*, to get to the line`int combination = factorial(n) / factorial(k) * factorial(n-k);`Notice that*Step Into*goes into each function as it is executed. That is why we've been using it to start the`main()`program from the very beginning. Using*Step Over*always steps over the next function to the next line of ode in the current procedure. - Press
*Step Into*again. You should be at the line`int product = 1; /* accumulated product */`in the function`factorial(n)` - From the menu select
*Inspect*and type in`product`. An inspect window should show up containing`product` - Now press
*Step Into*until you are at the line`return product;`

What value does `n` have in the window? (Note that `k`
is undefined in the watch window since `k` is not active in the
function factorial.

What value does `product` have in the inspect window?

- The reason that
`product`in the inspect window is incorrect is that the lineproduct = product + i;

should beproduct = product * i;

- Close the Evaluate and the Inspect windows.
- Make the above change in your editor.
- Recompile
*Reset*and*Run*the program again with input of`5`. Oh no! the triangle is still wrong!

It is tedious to have to keep stepping to get inside a program. A more efficient way is to set a breakpoint at a line of interest. Then the program runs at full speed until a breakpoint is reached.

*Reset*and make sure that`n`and`k`are still in the watch window (or add them again).- Select the line
`comb = combination(n,k) ;` - Select
*Add Breakpoint*. - Select
*Run*until the program stops at the breakpoint. - Repeat selecting
*Run*until the watch window displaysn: 3 k: 1

- Then
*Step Into*once - and then
*Step Over*until you are at the line:`return comb;` - Select
*Inspect* - and enter
`comb`for the expression in the dialogue box.

What is the value listed for `comb`?

- The true value for the combination of 3 things taken 1 at a time is
3! / 1!·2! = 6 / 2 = 3. So, the above value of
`comb`is wrong. - Something must be wrong with our combination calculation. In fact,
the programmer has ommitted parentheses in the denominator for the line:
comb = factorial(n) / factorial(k) * factorial(n-k) ;

- Change the line to be:
comb = factorial(n) / (factorial(k) * factorial(n-k)) ;

- Recompile and select
*Reset*and*Run*

Is your Pascal's Triangle correct (for `nrows = 5`)?

- Select the line
`comb = combination(n,k) ;` - Select
*Toggle Breakpoint*. - Select
*Run*

Do the results look OK when you input 13 for the number of rows?

They should now. Exit, saving any files you might wish to keep.

Fill in the commands that your debugger uses for the following activities:

Don't forget to send your answers when you're finished.