Next Gear

This rewriting approach to debugging is a lot like programming, but applied to finding errors by seeing if what you have written is what you write again. It is at the next level that things shift into a new gear. Some programmers do this automatically without realizing that they have done it. Other programmers just don't know how to move up to the next level and so waste a lot of time uselessly rewriting the code in their heads to find a discrepancy but repeatedly making the same mistake over and over again.

If rewriting the code doesn't find the bug, then the problem most likely is as much in your head as it is in the code. You may know the process you are trying to capture and you may be happy about the transcription from process to text, but what you are doing is wrong in some way. Either the process you have in your head is flawed or you are repeatedly making the same error in rendering it into text. So what to do next? The answer is that you have to bring the "experimental method" to the problem.

Yes, the experimental method as used in all of science. This is the reason that scientists often make good debuggers. What you have to do next is to use the code to make a prediction of what should happen when you run the program. Then you run the program and see if your prediction is correct. If it is correct, you have achieved nothing and need to repeat the process. If it is incorrect then you have found the bug. You may not understand the bug or be able to fix it yet, but you now have its location and nature pinned down and, with some extra exploration of the same kind, you should be able to understand where you are going wrong.

In this approach you take your existing code and use it to make a prediction. This is like taking a theory that you believe to be true and making a prediction. You then construct an experiment in the hope of invalidating the prediction. In other words, you are trying to prove your theory wrong. This is standard scientific method and it is really important. You are not trying to create an experiment to prove your prediction correct. In debugging, proving that you know what the program is doing doesn't help one little bit, apart from to make you feel unreasonably good about it. What matters is finding a discrepancy between your understanding and what actually happens. Once you have this you can build a new theory of what is going on and test this in the same way.

A good human debugger will select a part of the program and construct a test that is most likely to find a difference between predicted and actual behavior. A good debugger will also construct tests that are specific in their rejection of the current theory. If you build a test that shows that your theory is flawed in a number of possible ways then this is good, but a test that pins that flaw down to just one aspect is so much better. It is the ability to see what tests and results narrow down the cause of the problem that makes a good debugger truly great.

So debugging is an activity that is different to programming. It takes your current understanding of a program as a theory that you have to disprove. From your understanding you have to construct an experiment and predict its outcome with the objective of being proved wrong. This is classical experimental method applied to software.

Tests

The whole point of the scientific method is that any theory has to be disprovable. That is, we are not trying to prove that a theory is correct but to prove that it is incorrect. At first this seems like nonsense, but it really is the only rational way to proceed. The reason is that there are many many tests you could preform that show that the theory is valid or at least that the outcome has no effect on the theory. We could go on testing the theory in this way forever. What we need is a test that will disprove the theory because once disproved we can move on to formulate a new theory knowing that the old one was false.

This is what we have to do when we are debugging. The theory that is currently held is that the program, as written, is correct. Of course, this cannot be because we have observed some behavior that the correct program wouldn’t produce. What we want is a test that will prove that our program isn’t doing what we think it is and deliver some information on what it is doing. For example, in the previous chapter we created a program that implemented a binary search:

Function BinarySearch(Start, End, Target)
	While Start <= End
		Middle = CEIL((End-Start+1)/2)
		If shelf(Middle) == target Then 
                                        Return Middle
		If shelf(Middle) < target Then 
			Start = Middle+1
		Else
			End = Middle-1
	Return Not Found

Suppose it isn’t working in some way. You might start off by trying to rewrite it. If this doesn’t work then debugging proper has to begin. If the program is working as you expect then each time through the loop the Start and End should divide the range to the left or the right. To check that this is the case you could add some debugging instructions to display the values:

Function BinarySearch(Start, End, Target)
	While Start <= End
		Middle = CEIL((End-Start+1)/2)
		If shelf(Middle) == target Then 
                                           Return Middle
		If shelf(Middle) < target Then 
			Start = Middle+1
		Else
			End = Middle-1
		Print Start, End
	Return Not Found

Starting with a known short list of books you would follow through watching the way Start and End divides up the books. If the program doesn’t do it the way it should, you have your proof that the program is incorrect and you need to investigate further.

What does “investigate further” mean? It means find a test that will reveal the way the Start and End values are being created. In this case this suggests examining the value of Middle and adding instructions to check its value.

This is obviously a very simple program and there aren’t many opportunities for things to go wrong, but when it comes to a bigger program the possibilities for appropriate tests proliferate very quickly and selecting one that is likely to give you the information you need is difficult.