Writing Specifications for Programs

Imagine a team that has finished writing a program and has shown, with a proof, that the program is correct. It is tempting to stop there and assume the job is done, and that the program can be trusted to do what its users need. This belief sounds reasonable, but it quietly mixes two different questions. The first question is whether the program does what it was asked to do. The second is whether what it was asked to do was the right thing in the first place. Keeping these two questions apart is the starting point for understanding what a correctness proof can and cannot give you.

Before reading on, take a moment to decide for yourself which of the two questions a proof of correctness answers. Commit to an answer in your own mind. The reasoning you do now is what will make the rest of this article stick.

The specification says what the correct result must be. The program is then judged by whether its actual result matches that stated result. This is why the specification is the yardstick for every correctness claim. If the yardstick is wrong, a program can match it perfectly and still fail the people who depend on it.

Read the diagram as a check. The left column is what the specification demands; the right column is what the program actually does. Correctness is the claim that these agree for every run the program can make.

The reasoning behind correctness proofs rests on two fundamental ideas: process and state. The state of a program is all the information relevant at one moment. A process is the sequence of states the computer passes through as the program executes. Understanding both lets you describe exactly what a program does at every moment, and that description is the raw material any proof needs.

To make this concrete, consider a small invented program with two steps. Step one sets a to 4. Step two sets b to the value of a plus 5. Before any step runs, nothing has been set. After step one, the state holds a equal to 4. After step two, the state holds a equal to 4 and b equal to 9. The whole run is the sequence of those states, and the final state is the one a proof would compare against the specification.

The meaning of a statement can be expressed as its effect on the computer's state. This matters because each statement's effect is a solid fact you can rely on when building a proof. Instead of asking what a statement vaguely means, you ask exactly what it changes in the state and what it leaves alone.

Comparing the state just before and just after a statement makes the effect visible. Only the values the statement touches should differ between the two snapshots. Everything else in the state stays the same.

Here the statement that sets b changes only b, moving it from 0 to 9. The value of a is untouched in both snapshots. A proof that tracks statements this way can chain each effect onto the next until it reaches the final state.

In some cases it is possible to demonstrate, mathematically, that the sequence of computations a program describes will always produce the correct result. This is the sense in which a program can be provably correct. The proof reasons about every possible run of the program, not just the few runs someone happened to try. That is what makes it stronger than testing alone.

The specification, the program's process of states, the effect of each statement, and the final proof are one chain of reasoning. The specification says what the correct result must be. The execution is a process of successive states. Each statement's effect is a reliable fact. The proof strings these facts together to show that the final state of every run matches what the specification demands. Removing any link weakens the whole argument.

Rigorous proof is genuinely hard. In practice, full mathematical proofs of correctness are typically limited to fairly small programs. The effort of tracking every state and every statement's effect grows quickly as a program gets larger, which is why proofs are rare in everyday work.

This does not make the ideas useless for larger work. Even in everyday programming, the ideas and techniques used in correctness proofs can guide how you reason about code, even when you never write a formal proof. Asking what each statement changes, and what result the program must produce, is useful habit even without a written proof.

A program can exactly meet its specification and still be useless to the people who use it. This happens when the specification itself is wrong. The program then does precisely what was asked, but what was asked was not the right thing. The proof succeeds, and the result is still not what anyone needed.