Column 4: Writing Correct Programs

In the late 1960’s people were talking about the promise of programs that verify the correctness of other programs. Unfortunately, in the intervening decades, with precious few exceptions, there is still little more than talk about automated verification systems. In spite of unrealized expectations, though, research on program verification has given us something far more valuable than a black box that gobbles programs and flashes “good” or “bad” — we now have a fundamental understanding of computer programming.

The purpose of this column is to show how that fundamental understanding can help real programmers write correct programs. One reader characterized the approach that most programmers grow up with as “write your code, throw it over the wall, and have Quality Assurance or Testing deal with the bugs.” This column describes an alternative. Before we get to the subject itself, we must keep it in perspective. Coding skill is just one small part of writing correct programs. The majority of the task is the subject of the three previous columns: problem definition, algorithm design, and data structure selection. If you perform those tasks well, writing correct code is usually easy.

We first met this problem in Section 2.2; we are to determine whether the sorted array x[0..n – 1] contains the target element t.† Precisely, we know that n≥0 and that x[0] ≤ x[1] ≤ x[2] ≤ ... < x[n – 1]; when n = 0 the array is empty. The types of t and the elements of x are the same; the pseudocode should work equally well for integers, floats or strings. The answer is stored in the integer p (for position): when p is – 1 the target t is not in x[0..n – 1], otherwise 0≤p≤n – 1 and t = x[p].

† See Problem and Solution 5.1 if you need help in criticizing these short variable names, the form of the binary search function definition, error handling and other issues of style that are critical to the success of large software projects.

Binary search solves the problem by keeping track of the range within the array that holds t (if t is anywhere in the array). Initially, the range is the entire array. The range is shrunk by comparing its middle element to t and discarding half the range. The process continues until t is discovered in the array or until the range in which it must lie is known to be empty. In a table of n elements, binary search uses roughly log₂ n comparisons.

Most programmers think that with the above description in hand, writing the code is easy. They’re wrong. The only way you’ll believe this is by putting down this column right now and writing the code yourself. Try it.

I’ve assigned this problem in courses for professional programmers. The students had a couple of hours to convert the description above into a program in the language of their choice; a high-level pseudocode was fine. At the end of the specified time, almost all the programmers reported that they had correct code for the task. We would then take thirty minutes to examine their code, which the programmers did with test cases. In several classes and with over a hundred programmers, the results varied little: ninety percent of the programmers found bugs in their programs (and I wasn’t always convinced of the correctness of the code in which no bugs were found).

I was amazed: given ample time, only about ten percent of professional programmers were able to get this small program right. But they aren’t the only ones to find this task difficult: in the history in Section 6.2.1 of his Sorting and Searching, Knuth points out that while the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962.

Click here to view code image

initialize range to 0..n-1
loop
    { invariant: mustbe(range) }
    if range is empty,
        break and report that t is not in the array
    compute m, the middle of the range
    use m as a probe to shrink the range
        if t is found during the shrinking process,
        break and report its position

The crucial part of this program is the loop invariant, which is enclosed in curly braces. This assertion about the program state is called an invariant because it is true at the beginning and end of each iteration of the loop; it formalizes the intuitive notion we had above.

We’ll now refine the program, making sure that all actions respect the invariant. The first issue we must face is the representation of range: we’ll use two indices l and u (for “lower” and “upper”) to represent the range l.u. (A binary search function in Section 9.3 represents a range by its beginning position and its length.) The logical function mustbe(l, u) says that if t is anywhere in the array, it must be in the (closed) range x[l..u].

Our next job is the initialization; what values should l and u have so that mustbe(l, u) is true? The obvious choice is 0 and n – 1: mustbe(0, n – 1) says that if t is anywhere in x, then it is in x[0..n – 1], which is precisely what we know at the beginning of the program. Initialization therefore consists of the assignments l = 0 and u = n – 1.

The next tasks are to check for an empty range and to compute the new midpoint, m. The range l..u is empty if l > u, in which case we store the special value – 1 in p and terminate the loop, which gives

if l > u
    p = –1; break

The break statement terminates the enclosing loop. This statement computes m, the midpoint of the range:

m = (l + u) / 2

The “/” operator implements integer division: 6/2 is 3, as is 7/2. Our expanded program is now

Click here to view code image

l = 0; u = n-1
loop
    { invariant: mustbe(l, u) }
    if l > u
        p = -1; break
    m = (1 + u) / 2
    use m as a probe to shrink the range l..u
        if t is found during the shrinking process,
        break and note its position

Refining the last three lines in the loop body will involve comparing t and x[m] and taking appropriate action to maintain the invariant. Thus the code will have the general form

case
    x[m] <  t:  action a
    x[m] == t:  action b
    x[m] >  t:  action c

For action b, we know that t is in position m, so we set p to m and break the loop. Because the other two cases are symmetric, we’ll focus on the first and trust that the last will follow by symmetry (this is part of the reason we’ll verify the code precisely in the next section).

If x[m] < t, then we know that x[0] <x[1] <...<x[m] < t, so t can’t be anywhere in x[0..m]. Combining this with the knowledge that t is not outside x[l..u], we know that if it is anywhere, then it must be in x[m + 1..u], which we write as mustbe(m + 1, u). We then reestablish the invariant mustbe(l, u) by setting l to m + 1. Putting these cases into the previous code sketch gives the final function.

Click here to view code image

l = 0; u = n-1
loop
    { mustbe(l, u) }
    if l > u
        p = -1; break
    m = (l + u) / 2
    case
        x[m] <  t:  1 = m+1
        x[m] == t:  p = m; break
        x[m] >  t:  u = m-1

It’s a short program: a dozen lines of code and one invariant assertion. The basic techniques of program verification — stating the invariant precisely and keeping an eye towards maintaining the invariant as we wrote each line of code — helped us greatly as we converted the algorithm sketch into pseudocode. This process gives us some confidence in the program, but we are by no means certain of its correctness. Spend a few minutes determining whether the code behaves as specified before reading further.

In this section we’ll study a verification argument for the binary search code at a picky level of detail — in practice I’d do a much less formal analysis. The version of the program on the next page is (far too) heavily annotated with assertions that formalize the intuitive notions that we used as we originally wrote the code.

While the development of the code was top-down (starting with the general idea and refining it to individual lines of code), this analysis of correctness will be bottom-up: we’ll start with the individual lines of code and see how they work together to solve the problem.

We’ll start with lines 1 through 3. The assertion in line 1 that mustbe(0, n – 1) is true by the definition of mustbe: if t is anywhere in the array, then it must be in x[0..n – 1]. The assignments in line 2 of l = 0 and u = n – 1 therefore give the assertion in line 3: mustbe(l, u).

We come now to the hard part: the loop in lines 4 through 27. Our argument for its correctness has three parts, each of which is closely related to the loop invariant:

Initialization. The invariant is true when the loop is executed for the first time.

Preservation. If the invariant holds at the beginning of an iteration and the loop body is executed, then the invariant will remain true after the loop body finishes execution.

Termination. The loop will terminate and the desired result will hold (in this case, the desired result is that p has the correct value). Showing this will use the facts established by the invariant.

For initialization we note that the assertion in line 3 is the same as that in line 5. To establish the other two properties, we’ll reason from line 5 through to line 27. When we discuss lines 9 and 21 (the break statements) we will establish termination properties, and if we make it all the way to line 27, we will have established preservation, because it is the same as line 5.

Click here to view code image

 1.  { mustbe(0, n-1) }
 2.  l = 0; u = n-1
 3.  { mustbe(l, u) }
 4.  loop
 5.      { mustbe(l, u) }
 6.      if l > u
 7.          { l > u && mustbe(l, u) }
 8.          { t is not in the array }
 9.          p = -1; break
10.      { mustbe(l, u) && l <= u }
11.      m = (l + u) / 2
12.      { mustbe(l, u) && l <= m <= u }
13.      case
14.          x[m] <  t:
15.                   { mustbe(l, u) && cantbe(0, m) }
16.                   { mustbe(m+1, u) }
17.                   1 = m+1
18.                   { mustbe(l, u) }
19.          x[m] == t:
20.                   { x[m] == t }
21.                   p = m; break
22.          x[m] >  t:
23.                   { mustbe(l, u) && cantbe(m, n) }
24.                   { mustbe(l, m-1) }
25.                   u = m-1
26.                   { mustbe(l, u) }
27.      { mustbe(l, u) }

A successful test in line 6 yields the assertion of line 7: if t is anywhere in the array then it must be between positions l and u, and l > u. Those facts imply line 8: t is not in the array. We thus correctly terminate the loop in line 9 after setting p to –1.

If the test in line 6 fails, we come to line 10. The invariant still holds (we’ve done nothing to change it), and because the test failed we know that l≤u. Line 11 sets m to the average of l and u, truncated down to the nearest integer. Because the average is always between the two values and truncating can’t move it below l, we have the assertion of line 12.

The analysis of the case statement in lines 13 through 27 considers each of its three possible choices. The easiest choice to analyze is the second alternative, in line 19. Because of the assertion in line 20, we are correct in setting p to m and terminating the loop. This is the second of two places where the loop is terminated, and both end it correctly, so we have established the termination correctness of the loop.

We come next to the two symmetric branches of the case statement; because we concentrated on the first branch as we developed the code, we’ll turn our attention now to lines 22 through 26. Consider the assertion in line 23. The first clause is the invariant, which the loop has not altered. The second clause is true because t < x[m] ≤ x[m + 1] ≤ ... ≤ x[n-1], so we know that t can’t be anywhere in the array above position m – 1; this is expressed with the shorthand cantbe(m, n – 1). Logic tells us that if t must be between l and u and can’t be at or above m, then it must be between l and m – 1 (if it is anywhere in x); hence line 24. Execution of line 25 with line 24 true leaves line 26 true — that is the definition of assignment. This choice of the case statement therefore re-establishes the invariant in line 27.

The argument for lines 14 through 18 has exactly the same form, so we’ve analyzed all three choices of the case statement. One correctly terminates the loop, and the other two maintain the invariant.

This analysis of the code shows that if the loop terminates, then it does so with the correct value in p. It may still, however, have an infinite loop; indeed, that was the most common error in the programs written by the professional programmers.

Our halting proof uses a different aspect of the range l..u. That range is initially a certain finite size (n), and lines 6 through 9 ensure that the loop terminates when the range contains less than one element. To prove termination we therefore have to show that the range shrinks during each iteration of the loop. Line 12 tells us that m is always within the current range. Both looping branches of the case statement (lines 14 and 22) exclude the value at position m from the current range and thereby decrease its size by at least one. The program must therefore halt.

With this background, I feel pretty confident that we are able to move ahead with this function. The next column covers precisely this topic: implementing the function in C, then testing it to ensure that it is correct and efficient.

Assertions. The relations among input, program variables, and output describe the “state” of a program; assertions allow a programmer to enunciate those relations precisely. Their roles throughout a program’s life are discussed in the next section.

Sequential Control Structures. The simplest structure to control a program is of the form “do this statement then that statement”. We understand such structures by placing assertions between them and analyzing each step of the program’s progress individually.

Selection Control Structures. These structures include if and case statements of various forms; during execution, one of many choices is selected. We show the correctness of such a structure by considering each of the several choices individually. The fact that a certain choice is selected allows us to make an assertion in the proof; if we execute the statement following if i > j, for instance, then we can assert that i > j and use that fact to derive the next relevant assertion.

Iteration Control Structures. To prove the correctness of a loop we must establish three properties:

We first argue that the loop invariant is established by initialization, and then show that each iteration preserves its truth. These two steps show by mathematical induction that the invariant is true before and after each iteration of the loop. The third step is to argue that whenever execution of the loop terminates, the desired result is true. Together these establish that if the loop ever halts, then it does so correctly; we must prove that it does terminate by other means (the halting proof of binary search used a typical argument).

Functions. To verify a function, we first state its purpose by two assertions. Its precondition is the state that must be true before it is called, and its postcondition is what the function will guarantee on termination. Thus we might specify a C binary search function as follows:

Click here to view code image

int bsearch(int t, int x[], int n)
 /* precondition: x[0] <= x[1] <= ... <= x[n-1]
    postcondition:
        result == -1    =>   t not present in x
        0 <= result < n =>   x[result] == t
  */

These conditions are more a contract than a statement of fact: they say that if the function is called with the preconditions satisfied, then execution of the function will establish its postcondition. After I prove once that the body of the function has this property, I can use the stated relations between the pre- and postconditions without ever again considering the implementation. This approach to software development is often called “programming by contract”.

Later in this book, especially in Columns 9, 11 and 14, we’ll use verification techniques as we develop subtle programs. We’ll use the language of verification to explain every line of code as it is written; it is particularly helpful to sketch an invariant for each loop. The important explanations end up in the program text as assertions; deciding which assertions to include in real software is an art that comes only with practice.

The language of verification is used often after the code is first written, starting during code walk-throughs. During testing, violations of the assert statements point the way to bugs, and examining the form of a violation shows how to remove one bug without introducing another. When you debug, fix both the code and the false assertion: understand the code at all times, and resist those foul urges to “just change it until it works”. The next column illustrates several roles that assertions can play during testing and debugging. Assertions are crucial during maintenance of a program; when you pick up code that you’ve never seen before, and no one else has looked at for years, assertions about the program state can give invaluable insight.

These techniques are only a small part of writing correct programs; keeping the code simple is usually the key to correctness. On the other hand, several professional programmers familiar with these techniques have related to me an experience that is too common in my own programming: when they construct a program, the “hard” parts work the first time, while the bugs are in the “easy” parts. When they came to a hard part, they hunkered down and successfully used powerful formal techniques. In the easy parts, though, they returned to their old ways of programming, with the old results. I wouldn’t have believed this phenomenon until it happened to me; such embarrassments are good motivation to use the techniques frequently.

2. If the original binary search was too easy for you, try the variant that returns in p the position of the first occurrence of t in the array x (if there are multiple occurrences of t, the original algorithm returns an arbitrary one). Your code should make a logarithmic number of comparisons of array elements; it is possible to do the job in log₂ n such comparisons.

3. Write and verify a recursive binary search program. Which parts of the code and proof stay the same as in the iterative version, and which parts change?

4. Add fictitious “timing variables” to your binary search program to count the number of comparisons it makes, and use program verification techniques to prove that its run time is indeed logarithmic.

5. Prove that this program terminates when its input x is a positive integer.

while x != 1 do
    if even(x)
        x = x/2
    else
        x = 3*x+1

6. [C. Scholten] David Gries calls this the “Coffee Can Problem” in his Science of Programming. You are initially given a coffee can that contains some black beans and some white beans and a large pile of “extra” black beans. You then repeat the following process until there is a single bean left in the can.

Randomly select two beans from the can. If they are the same color, throw them both out and insert an extra black bean. If they are different colors, return the white bean to the can and throw out the black.

Prove that the process terminates. What can you say about the color of the final remaining bean as a function of the numbers of black and white beans originally in the can?

7. A colleague faced the following problem in a program to draw lines on a bitmapped display. An array of n pairs of reals (a_i,b_i) defined the n lines y_i = a_ix + b_i. The lines were ordered in the x-interval [0,1] in the sense that y_i < y_i+1 for all values of i between 0 and n – 2 and all values of x in [0,1]:

Less formally, the lines don’t touch in the vertical slab. Given a point (x,y), where 0≤x≤1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

8. Binary search is fundamentally faster than sequential search: to search an n-element table, it makes roughly log₂ n comparisons while sequential search makes roughly n/2. While it is often fast enough, in a few cases binary search must be made faster yet. Although you can’t reduce the logarithmic number of comparisons made by the algorithm, can you rewrite the binary search code to be faster? For definiteness, assume that you are to search a sorted table of n = 1000 integers.

9. As exercises in program verification, precisely specify the input/output behavior of each of the following program fragments and show that the code meets its specification. The first program implements the vector addition a = b + c.

i = 0
while i < n
    a[i] = b[i] + c[i]
    i = i+1

(This code and the next two fragments expand the “for i = [0, n)” loop to a while loop with an increment at the end.) The next fragment computes the maximum value in the array x.

max = x[0]
i = 1
while i < n do
    if x[i] > max
        max = x[i]
    i = i+1

This sequential search program returns the position of the first occurrence of t in the array x[0..n–1].

i = 0
while i < n && x[i] != t
    i = i+1
if i >= n
    p = -1
else
    p = i

This program computes the n^th power of x in time proportional to the logarithm of n. This recursive program is straightforward to code and to verify; the iterative version is subtle, and is left as an additional problem.

Click here to view code image

function exp(x, n)
        pre  n >= 0
        post result = x^n
    if n = 0
        return 1
    else if even(n)
        return square(exp(x, n/2))
    else
        return x*exp(x, n-1)

10. Introduce errors into the binary search function and see whether (and how) they are caught by attempting to verify the buggy code.

11. Write and prove the correctness of a recursive binary search function in C or C++ with this declaration:

Click here to view code image

int binarysearch(DataType x[], int n)

Use this function alone; do not call any other recursive functions.