Debugging

Writing software means you’re writing bugs!

The Fundamental Theorem of Debugging

If the output of a function is incorrect, at least one of the following is true:

• at least one of the inputs is incorrect,
• the function itself is incorrect, or
• your understanding is incorrect.

Corrolary: The Debugging Algorithm

This rule gives a simple debugging algorithm, which is a binary search on the flow of your program until you you’ve narrowed down the location of the error sufficiently small that you can notice the error and fix it.

• Select a point A in your code where your understanding and reality match up. (Default: beginning of the program.)
• Select a point B in your code where your understanding and reality don’t match up. (Default: the end of your program.)
• While you’re not sure what’s wrong:
  • Select a point in between A and B, and call it C. Determine whether the reality of the code (the values that are actually getting processed and passed around) matches your expectations. This means adding in print statements, using a debugger, making plots, etc.
  • If reality does match your expectations, update A to refer to point C.
  • If reality does not match your expectations, update B to refer to point C.
  • If you can’t select a point in the code, if you can’t tell what the reality of your code is and how to find it, or you can’t tell what you should expect, use your resources (documentation, Google, Stack Overflow, TAs, instructors, friends).
  • Repeat.

Let’s Talk About Debugging

A “bug” is a mismatch between the expected and actual behavior of a program. This is caused by some code where there is a mismatch between what you expected the code to do and what the code actually does.

To find that point where the code “breaks” (i.e., does what you don’t expect it to do), you perform a binary search. On one end of the search is the last known point at which the information you’re keeping track of looks correct. On the other end of the search is the first known point at which the information you’re keeping track of looks incorrect. Selecting some part of the code in between these two points will reduce your search space, causing you to either look ahead of your split point if you do see a mismatch at the point you selected, or look after the split point if you don’t see a mismatch. Now you have a smaller window for an error to appear. Recurse.

What This Debugging Algorithm Assumes You Can Do

This approach presumes several skills or resources to build upon. First, it assumes you know what the flow of the program is like so that you can reason for “before” and “after” a certain point, as well as selecting a point that’s reasonably halfway between your endpoints.

Second, it assumes you have the ability to see the state of the program and the information you’re looking to keep track of. This is where print statements and debuggers come in handy. Test data is also often helpful here, too.

Third, and most importantly, it assumes you have a clear expectation of what the code should be doing in the given step. When programmers familiar with the debugging process come to me with questions, this is almost always the root cause of the problem they’re seeing - and if they took a few more binary search steps, the problem would be a lot clearer.

If I Sent This To You In An Email

I believe anyone beyond an Introduction to Programming class should be confident using this strategy for debugging. However, as Dan Luu recounts, for some people the Feynman method (thinking really hard) works for some time beyond that. If I send you a link to this page in response to some question, it means I’m asking you to follow this debugging process. The question you asked (apologies if I misunderstood it) is something that can be addressed by another iteration of binary search. Repeat this process until you hit one of the three assumptions (where to look, how to look, what to look for) and write up that question.

But, if all else fails, email me again.