Reasoning About Assignment Statements

Most programmers say a program is correct when it works. That phrase hides a question: works relative to what? A program can run without crashing, print sensible-looking output, and still fail the task it was written for. To talk precisely about correctness, we need a yardstick that exists outside the program itself. That yardstick is the specification.

The source states the central idea directly: a program is correct when it produces the correct result as specified, so correctness is always measured against a specification. Keep that sentence in mind. Every claim in this article about proofs, states, and statements is in service of checking a program against its specification.

Notice that the specification sits outside the program. You can write a program that is perfectly faithful to its own steps and still be wrong, if the specification it was checked against describes the wrong goal. The source puts it plainly: a proof of correctness is only as trustworthy as the specification it relies on.

In the diagram, the specification is the standard the check uses, and the actual final state is what the run really produced. A correctness check compares the two. If the observed final state satisfies what the specification demands, the run agrees with the specification. The diagram is an illustration built for this article; the source supplies the idea that correctness is measured against a specification.

Think of state as a snapshot. At any instant, the program has a set of variables, each holding some value. That collection is the state. As statements run, the snapshot changes. The full run of the program is the chain of these snapshots, one after another. That chain is the process.

One way to picture a single snapshot is as a mapping from variable names to their current values. The diagram below shows a generated example with three variables after three statements have run. It is a single moment in the process, not the whole process.

In this snapshot, z is the variable whose value was most recently set, so it is marked as changed. The state at this moment contains all three variables and their values. The state immediately before the last statement ran would have contained only x and y, with z not yet holding a value.

The meaning of a statement can be expressed as its effect on the computer's state. This is the key move that makes proofs possible. Instead of asking what a statement means in the abstract, we ask what it does to the snapshot. For an assignment such as x := x + 1, the effect is that the variable x ends up holding the old value of x plus one, while the other variables are unchanged.

The reasoning behind correctness proofs is a single chain. The specification says what the correct result must be. The program's execution is a process made of successive states. Each statement's effect on state is a fact you can rely on. A proof strings those facts together to show that the final state of every run matches what the specification demands. Removing any link weakens the whole argument.

A program is provably correct when it can be demonstrated mathematically that the sequence of computations it describes will always produce the correct result. The important word is always. The proof reasons about every possible run of the program, not just the few runs someone happened to try. This is what makes a proof stronger than testing alone. A test shows behavior on the inputs you chose; a proof addresses all inputs the specification covers.

Rigorous proof is genuinely hard. In practice, full mathematical proofs of correctness are typically limited to fairly small programs. This does not make the ideas useless for larger work. Even in everyday programming, the techniques used in correctness proofs can guide how you reason about code, even when you never write a formal proof.

A second question is harder to see. Many beginners assume that once a program has been shown to be correct, the job is finished and the program can be trusted to do what its users need. This quietly mixes two questions. The first 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. A correct program can still be useless if its specification is wrong.