SELECTIVE IGNORANCE

Finding the Signal in the Noise

July 2007

My remarks about assertions and exceptions generated a few comments, so I thought I'd pour some gasoline on the fire.

Many years ago I worked in a university computation center where they had just gotten a PL/I compiler that checked whether programs adhered to the rules of the language during execution.

For example, attempting to access a nonexistent array element in PL/I either does the equivalent of throwing an exception in C++ or has undefined behavior, depending on whether you have told the compiler to check array bounds in the section of code that accesses the nonexistent element. Normally, people who cared about performance would not turn on array range checking. However, if you were using the checking compiler, it would check array ranges for you regardless of whether you had asked it to do so.

We had some kind of utility program that people used fairly often. I have completely forgotten what it did, but it doesn't matter. What matters is that it was written in PL/I, and that people had come to rely on it.

Of course, as soon as the debugging compiler arrived, I tried compiling this program with that compiler. I probably don't need to tell you what happened: The program turned out to have so many run-time errors that I gave up trying to find them all. Nearly all of them were index range errors, but--as it happened--for strings rather than for arrays.

In effect, this was a program that worked only by coincidence, but the coincidence was so reliable that dozens of people had used it for many months without discovering a single problem.

This anecdote is an example of a widespread problem. In effect, the program was not really written in PL/I at all; it was written in an extension of PL/I that included the ways in which the compiler happened to behave when presented with certain kinds of errors. Of course, the author of the program was not aware of taking advantage of such behavior; it was only when the compiler was asked to check for the problem that its existence was even suspected.

Ever since then I have wondered how many programs appear to be working correctly when they're really doing nothing of the kind.

Posted by Andrew Koenig at 10:34 PM  Permalink |

Thinking about how to deal with incorrect input reminded me of a place where I used to work. We were building C++ class libraries to distribute to other developers in the company, and our managers imposed a rule: No code delivered to customers could contain an assert statment.

The reasoning was simple, at least in theory: Our customers might use our code in high-reliability systems. An assert causes the entire program to terminate if the condition asserted is false, and the view was that under no conditions could we ever do anything that might terminate the entire program.

Interestingly, this took place before C++ had exceptions, which meant that there was no way of dealing with "impossible" conditions: All a program could do under such circumstances was return an error indication to its caller--an indication that the caller would probably ignore.

Today, of course, we have exceptions; a fact that gives us the opportunity to decide when we should use an exception and when we should use an assert. There are two important differences between an exception and an assert: (1) It is possible to decide during compilation that assert statements should be ignored, and (2) If an assert is executed (i.e. not ignored) and its condition turns out to be false, the caller of the program that contains the assert can't do anything about it.

So the question comes down to this: Is it ever right to terminate a program unconditionally?

The people in charge of the organization in which I worked at the time said no--total termination was something that we could never afford. But I thought then, and I still think, that this view was naive.

For one thing, if you think you can prevent a C++ program from terminating by removing the assert statements, you are seriously mistaken. It is true that by doing so, you make it less likely that the program will crash; but if a crash is something you can never afford, it is far from clear that making a crash less likely is an advantage. After all, by doing so, what you are really doing is making it easier to pretend that a crash will never happen, thereby making the situation that much worse when it does happen.

Moreover, removing assert statements will not keep a program from crashing if it tries to use an invalid pointer, or index past the end of an array, or (on most machines) divide by zero.

Not only that, but it is sometimes right to use an assert instead of an exception. The most common situation that comes to mind is when a program discovers a situation that the programmer believes is impossible. I'm not talking here about mere invalid input, but about a state of affairs that indicates that the program itself is broken in unanticipated ways.

For example, consider a program that implements a doubly-linked list. Such a list might be represented as a collection of nodes, each of which has pointers to its prececessor and successor. In such a program, one can reasonably expect that if p points to a node, and that node has a successor (i.e. it is not at the end of the list), then the successor will point back at the original node as its predecessor. One might incorporate that belief into one's program as

    assert (p->succ == 0 || p->succ->pred == p);

If this assert ever fails, it means that the data structure has become corrupted, and any attempt to use it further will have undefined consequences. It is true that the program might be able to continue in these circumstances, provided that it never tried to use the errant pointer, but if the program produces correct results after that, it does so only by coincidence.

I believe, therefore, that when a program discovers something that is irrefutably wrong with its internal state, it is better off terminating at once, rather than giving its caller the opportunity to pretend that nothing is wrong.

If you like, I think that exceptions should be reserved for situations in which it is possible to do something sensible after catching the exception. When you discover a condition that you thought was impossible, it's hard to say much about what might happen afterward.

Posted by Andrew Koenig at 04:15 PM  Permalink |

Although I didn't realize it at the time, the fellow who talked to me about binary searching at the Monk's Inn had an important idea: Binary searching is an example of an algorithm that is not only unusually useful but also unusually hard to test.

For example, a fundamental part of the nature of any binary-search algorithm is that it relies on its input being already sorted. However, it is not feasable for a binary-search program to test whether its input is sorted, because doing so would take so long as to defeat the whole purpose of using a binary search in the first place.

So we already have a reliability problem: The program will not work unless the input meets the requirements, but it must not check whether those requirements are actually met.

Suppose now that we are going to test a binary-search program. Will our tests include giving it unsorted input? If so, what does it mean to say that the program is working correctly? In other words, how does our test program distinguish between a search program that works correctly on incorrect input and one that doesn't?

It might be reasonable to require that a binary-search program not crash even when presented with unsorted input. But that notion just begs the question of what the program should do, because it's hard to check whether a program "does not crash." The trouble here is that programs can do things that the language does not define, and such actions might cause the program to crash on one occasion and not on another.

The only conclusion I can see is that if we are going to say that a program "must not crash," then we will have to look inside that program and insert code that verifies that it performs no undefined operations. In the case of a binary search, for example, we will have to instrument the code to verify that whenever we access an element of the array being searched, that element actually exists and is not out of bounds.

This conclusion is a special case of a more general notion: To test a program, it may be necessary to insert code into it that verifies that the program limits itself to well-defined operations.

Posted by Andrew Koenig at 10:34 AM  Permalink |