An Introduction to Imperative Programming

A failure is a witness for an error. In general however, failures do not inform us about the cause of the error, i.e. the part of the program that is erroneous. A failure is therefore a symptom not a diagnosis. Let us consider the following example:

unsigned min(unsigned x, unsigned y) {
    if (x < y)
        return y;
    else
        return x;
}

unsigned sum_first_n(unsigned *arr, unsigned sz, unsigned n) {
    unsigned sum = 0;
    n = min(n, sz);
    for (unsigned i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}

Assume that the specification is given, as usual in practice, in plain English:

“The function sum_first_n shall sum up the first n, however at most sz, elements of the array arr.”

Let us consider the following calls to sum_first_n:

int main() {
     unsigned arr[] = { 1, 2, 3 };
     unsigned r1 = sum_first_n(arr, 3, 2); // (1)
     unsigned r2 = sum_first_n(arr, 3, 3); // (2)
     unsigned r3 = sum_first_n(arr, 3, 4); // (3)

The cause for the failure in (1) and the getting stuck in (3) is an error (also called defect or bug) in the function min: min does not compute the minimum but the maximum.

This examples shows that a failure may tell us little about the cause of the error that failure exposes. In practice, it can be especially hard to localize the error in program code. The first input merely results in a wrong result whereas the third causes undefined behavior which can be hard to observe (see Remark 6.2.2).

Finding errors in programs can be significantly simplified if programs fail as early as possible when they enter an erroneous state. Then, the program won't continue executing with “wrong” values and thereby dislocating the cause from the symptom. A very common way to achieve this is to use assertions in the code to assert invariants, i.e. conditions on the program state at a particular program point that have to hold for every input. These assertions can then be checked at runtime and if they are violated, the program can be aborted immediately.

In C, assertions are typically implemented as macros that are expanded to an if-then-else construct as in Definition 6.2.4. When defining the macro NDEBUG (typically by given the command line switch -DNDEBUG) asserts can be deactivated by defining the macro assert to the empty text. This is typically done for production code that has been “sufficiently” tested.

#include <assert.h>
unsigned min(unsigned x, unsigned y) {
    unsigned m = x < y ? x : y;
    assert(m <= x && m <= y && (m == x || m == y));
    return m;
}

In general, it is advisable to document as much invariants as possible using assertions. They come for free in terms of runtime in the production code because they can just be disabled. They can help to expose bugs and can make it easier to fix them. And they are also helpful for documentation purposes because the denote (at least a part) of the invariant that the programmer had in mind for the particular program point. This holds especially for pre- and postconditions. Note however that the C expression language is often not strong enough to formulate powerful invariants because it does not contain quantifiers like the assertion language we have defined in Definition 6.1.2 (they would of course be very hard to check at runtime). Therefore, often only a part of the invariant can be documented in an assertion.

Let us consider the following example where we can use assertions productively to specify the precondition. Which in this case is that the array is non empty:

unsigned min_arr(unsigned* arr, unsigned n) {
    assert(n > 0);
    unsigned res = arr[0];
    for (unsigned i = 1; i < n; i++)
        res = min(res, arr[i]);
    return res;
}

int min_arr(int* arr, unsigned n) {
    if (n == 0)
        return -1;
    int min = arr[0];
    int idx = 0;
    for (unsigned i = 1; i < n; i++) {
        if (arr[i] < min) {
            min = arr[i];
            idx = i;
        }
    }
    return idx;
}

int min_arr(int* arr, unsigned n) {
    assert (n > 0);
    ...
}