How To Debug Your CSC430 Programs
1 Debugging is really hard
2 Hypothesis-based debugging
3 Debugging functional programs
3.1 Functional Programming?
3.2 Don’t Use a Debugger
3.3 Test Case Minimization
3.4 Finding the broken code
3.5 Ask Questions!
3.6 ta da
8.0.0.11

How To Debug Your CSC430 Programs

Here are some thoughts on debugging, and the process of debugging in CSC 430. The goal here is to make your life better: to help you learn more effectively, and have more time in your life to do whatever it is you want to do with your life!

1 Debugging is really hard

The number one most important thing to understand about debugging is this: It can be ludicrously time-consuming.

The standard saying about debugging is this: you will spend 90% of your programming time debugging. The other 10% is spent introducing bugs.

Ha ha.

But seriously.

The first part is not a joke: debugging is enormously time consuming. Correspondingly:

If you cannot debug your programs in a reasonable amount of time, you cannot complete your programming tasks.

Debugging is not the whole story when programming: a poor program design can probably hurt you even more than an ineffective debugging process. Indeed, difficulty in debugging can often be linked to poor program design. But for now, I just want to stay very simple, and try to give you a process that will help you get through this course (CSC430).

One important complication here is that it’s easy to think of debugging as something like cleaning a window; we look for the spots, and wipe them away. Debugging programs is nothing like that. The problems are not superficial blotches on top of a correct structure; instead, they are generally structural problems. They could be minor structural problems, or they could be major structural problems.

A minor structural problem: "Oh, I thought that the result of ANDing together an empty list of booleans would be false, because the list is empty, but I see now that it should be true."

A major structural problem: "Oh, I see now that I completely misunderstood how programs in my host languge are evaluated."

The challenge is that understanding these problems—especially the major ones—requires questioning and undoing some relatively basic assumptions about your own program. Imagine spending an hour under your car trying to figure out why the rear wheels aren’t getting power, only to discover that it’s a front-wheel drive car. We constantly make assumptions at a broad range of levels, and debugging requires us to question these assumptions serially, without dismantling the other parts of our understanding.

2 Hypothesis-based debugging

The single most important thing I can tell you about debugging is this: do not start debugging without a hypothesis. This is akin to writing test cases before you start coding. You must have some idea of what you think the problem might be before you start debugging.

Debugging without a hypothesis is like walking out of the door and hunting a heffalump, a la Winnie the Pooh. Winnie the Pooh (for those of you not familiar with A. A. Milne) is very sweet, and very clueless, and spends a lot of time walking in circles looking for a nonexistent beast, and being startled by his own footprints.

It’s a good story, but not a good process, especially when it’s late and you’re tired and sleepy and you have other homework to do.

Instead, start your debugging process by using your head. What are you observing? What should you be observing instead? What could be causing it? That’s the important one, let me repeat it: What could be causing it?

Make a hypothesis. Now let’s talk about testing that hypothesis.

3 Debugging functional programs

The programming in this course will be done in a largely functional style. This will make many things enormously easier to debug, but it’s important to understand how and why, and what tools you should not bother working with.

3.1 Functional Programming?

At the beginning of this course, the term "functional programming" may not mean anything to you. In some ways, much of the course is an explanation of what that term means.

The simplest way to say it is this: functional programs do not have side-effects, most notably mutation. That is: functional programs do not include statements like

x = x + 1;

...that change what x is bound to.

This change causes a cascading sequence of updates. For instance, functional programs generally don’t need the idea of "statements" at all!

Why does functional programming leave out side effects? In a nutshell, so that functions in a functional program behave like functions in math. That is: they act as mappings from inputs to outputs. Calling a function with the same inputs will always produce the same output.

3.2 Don’t Use a Debugger

This decision has a dramatic effect on the process of debugging.

Specifically, most debugging tools are designed to allow you to halt a program while it’s running, to inspect its state. This is vital, because it may be that the first and second and thirty-ninth time you call the function f with 9 it behaves as expected, but somewhere between the thirty-ninth and forty-fourth time it triggers a Null Pointer Exception, and it only happens when it’s called from this other particular method and when this tree happens to contain a reference to this other data structure. Yikes!

With a purely functional program, this can’t happen. As we stated before, a function in a functional language is a mapping from inputs to outputs. If it mapped 9 to "loganberry" the first time it was called, it will continue to do so every time it is called.

What this means is that traditional "step through the program" debuggers are generally not very useful in functional programming languges. You can build them, and they work fine, but there’s just not much point in using them; if you want to check whether f works correctly on a particular input, just write a test case to ensure that it works correctly on that input! Not only do you then know that the problem must be somewhere else, you also have a test case that will continue to run automatically and guarantee that you don’t accidentally break the program.

3.3 Test Case Minimization

Let’s take a step back. It’s all very well and good to say that f always produces the same value, but how do you get started on a large failing test case? We call top-interp with some big program, and it’s producing the wrong result. How do we begin?

The goal of debugging is to identify the problem with your program. When you start debugging, you have no idea where the problem is. (The problem could even be in your test case!) The goal of debugging is to narrow down the space of possible problems, until you find the particular problem that you have.

Often, large test cases identify problems that simple test cases don’t. It’s often the case that when you put enough pieces together, you wind up discovering weak points in the design. On the other hand, large test cases exercise many different parts of your program, and require you to inspect a whole lot of code.

When you’re looking at a big failing test case, then, the very first thing you should try to do is to ... make it smaller! The process of test case minimization involves cutting pieces out of the test case in order to discover the smallest test case that triggers the problem.

This is absolutely vital when working with larger languages and systems; it will often be the case that you discover a problem with a particular thirty-thousand line program. At this point, diving into the languge implementation headfirst is insanity. What you need is to find a VERY SMALL program that reliably triggers the problem.

It’s also very important not to leave your brain at the door when you’re performing test case minimization; it’s easy to get lost in the mindless process of performing a binary search, trimming out first this part and then that part of the program. Keep in mind that your goal should always be to have that "aha!" moment when you realize why the problem is occurring.

3.4 Finding the broken code

So: we have a test case that’s failing. We’ve done our best to shrink it to a manageable size. We need to repair the program so that it behaves correctly for this input.

For a functional program, this generally means that we’re looking at a function body that assembles the results of other function calls into a final answer. The basic question that we need to answer is this: are we making the right function calls? If so, are those function calls returning the right results?

In general, the major difficulty here is that there’s more than one right way to write any given program, so there may be multiple ways to answer these questions. Fortunately, in this course (csc 430), there’s nearly always a single "recommended" path to the answer, and my sincere hope is that your classmates and instructor (could be me...) can help guide you toward that answer. Much of the exploration will be on your own, though, so you need to be able to focus in on asking the right question.

The best way to ask yourself questions (am I calling this function with the right argument? is it returning the right thing?) ... is to write a test case. For example: "I think that my substitution function isn’t properly performing substitution for the arguments after the first." That’s a perfect time to write a test case, to either confirm or reject your hypothesis. If you confirm your hypothesis, you’re one step closer to fixing the problem! If your test case passes, you can be confident that that wasn’t the problem. And in a functional languge, you know that that function will *always* behave correctly on that input.

3.5 Ask Questions!

Finally, remember that the goal here is to learn, and that one of the principal benefits of learning in a course as part of a school rather than studying alone in a hut in Nunavut is that you have other students and an instructor to support and assist you. They’re there to answer your questions. In the case of the instructor (me), that’s THE ONLY reason I’m here. The entire point of this aspect of my existence is to help students learn. In the case of your fellow students, answering your questions is a fantastic way for them to develop their own knowledge. Explaining something to someone else is the best way to strengthen and repair their own conceptual mistakes.

Indeed, asking questions can help you in a much more direct way. Writing a question carefully, and explaining why you have this question, and what you tried and why it doesnt work, is a FANTASTIC way to help you discover your own errors. I can’t count the number of times I’ve sat down to write a long e-mail about how something is terribly broken, only to realize that the problem is mine, and that I was misunderstanding something important.

3.6 ta da

So: Good Luck! Learn lots! Ask Questions!