5.2.1 Correctness and Refinement

As we remember, the refinement ordering was introduced in Chapter 4 to rank specifications in terms of strength, reflecting how demanding a specification is or how hard a specification is to satisfy. As we recall, this ordering plays a role in determining whether a given specification is complete with respect to a completeness property and whether a given specification is minimal with respect to a minimality property. Surprisingly, or on second thought not surprisingly, the same refinement ordering plays an important role in defining program correctness, as the following propositions provide. For the sake of simplicity, we restrict our attention to deterministic programs (i.e., programs that produce a uniquely determined final state for any given initial state).

Function P refines relation R if and only if it has a larger domain that R and for all elements s in the domain of R, the pair (s,P(s)) is an element of R; this is exactly how we defined (total) correctness in Section 5.1.

Unlike with total correctness, in partial correctness P does not have to satisfy R for all initial states in the domain of R; rather it suffices that it satisfies R for elements of the domain of R for which p terminates normally (whence the term PL). Note that if we take P=Ø (i.e., program p fails to terminate for all initial states), then this condition is satisfied.

Relation RL has the same domain as relation R, but because it assigns all the elements of S to any element of the domain of R, it imposes no condition on the final state; this is exactly what termination is about.

We conclude this section by revisiting the definition of refinement: so far we have interpreted the refinement to mean that a specification is stronger than another, more demanding than another, and so on. There is a simple way to characterize refinement, now that we have defined correctness; it is given in the following proposition.

Isn’t the essence of being a stronger specification to admit fewer correct programs? Any program that is correct with respect to the stronger/more demanding/more refined specification is necessarily correct with respect to the weaker/less demanding/less refined specification. The necessary condition of this Proposition is a mere consequence of the transitivity of the refinement ordering: if a program p is correct with respect to R, then its function P refines R; since R refines R′, then a fortiori P refines R′, hence p is correct with respect to R′.

5.2.2 Set Theoretic Characterizations

Whereas in Section 5.1 we introduced definitions of correctness and in Section 5.2.1 we introduced propositions that formulate correctness in terms of refinement, in this section we introduce propositions that formulate correctness in terms of set theoretic formulae. In practice, these are more tractable than either the definitions or the refinement-based characterizations.

Interpretation of this formula: The set dom(R) is the set of initial states for which program p must behave as R mandates. The set is the set of initial states for which program p does behave as R mandates (see Fig. 5.1 for an illustration). Program p is correct with respect to specification R if and only if these two sets are identical.

Interpretation of this formula: The set is the set of initial states for which program p behaves as R mandates (see Fig. 5.1 for an illustration). The set is the set of states for which program p terminates and specification R has a requirement. Program p is partially correct with respect to specification R if and only if it behaves according to R whenever it terminates.

This condition simply means that dom(R) is a subset of dom(P).

5.2.3 Illustrations

As an illustration of the propositions given in the previous section, we revisit the examples of Section 5.1 and check the formulas of these propositions to ensure that we reach the same conclusions. We consider the specification and the candidate programs of the first example:

The following table shows, for each candidate program P, the values of , dom(R), dom(P), and the correctness property of P: total correctness (TC), partial correctness (PC), termination (T), or none (N).

Candidate				TC	PC	T	N
P1	{0,1,2,3}	{0,1,2,3}	{0,1,2,3}
P2	{0,1,2,3}	{0,1,2,3}	{0,1,2,3,4,5,6}
P3	{0,1,2}	{0,1,2,3}	{0,1,2}
P4	{0,1,2}	{0,1,2,3}	{0,1,2,4,5,6}
P5	{0,1,2}	{0,1,2,3}	{0,1,2,3}
P6	{0,1,2}	{0,1,2,3}	{0,1,2,3,4,5,6}

These are indeed the conclusions we had reached earlier for the first example. For the second example, we list the specification and programs, then we draw the same table.

Candidate			,	TC	PC	T	N
P1		S
P2		S	S
P3	S	S	S

These are indeed the conclusions we had reached earlier for the second example. For the third example, we had a single program and many specifications, which we present below:

p: {while (y<>0) {x=x+1; y=y-1;};}

We remember that the function of program p is , whence the domain of P is ; for each specification R we write, in the table below, the values of , dom(R), and dom(P), then make a judgment about the correctness properties of P with respect to the specification in question.

Specification			,	TC	PC	T	N
R1		S
R2
R3
R4
R5
R6
R7		S

5.3.1 Sample Formulas

As a way to nurture the reader’s understanding of this notation, we give below a number of formulas, which we want to consider as valid (in reference to the definition above); we let x and y be integer variables and we classify the sample formulas by the control structure of the program p.

Assignment statement:

• {x=1} x=x+1; {x=2}
• {x≥1} x=x+1; {x≥2}
• {x≥1} x=x+1; {x≥1}
• {x=1 ∧ y=4} x=x+1; {x=2 ∧ y=4}
• {x=x0} x=x+1 {x=x0+1}, for some constant x0.
• {x=x0 ∧ y=y0} x=x+1 {x=x0+1 ∧ y=y0}, for some constants x0 and y0.
• {x=x0 ∧ y=y0} x=x+1 {x≥x0+1 ∧ y≥y0}, for some constants x0 and y0.

Sequence statement:

• {x=3} x=x+3; y=x*x; {x=6 ∧ y=36}
• {x=3} x=x*x; y=x+9 {x=9 ∧ y=18}
• {x=x0 ∧ y=y0} x=x+3; y=x*x; {x=x0+3 ∧ y=(x0+3)²}, for some constants x0 and y0.
• {x=x0 ∧ y=y0} x=x*x; y=x+9; {x=x0² ∧ y=x0²+9}, for some constants x0 and y0.
• {x=x0 ∧ y=y0} x=x+y; y=x–y; x=x–y; {x=y0 ∧ y=x0}, for some constants x0 and y0.
• {x=x0 ∧ y=y0} x=x+1; y=y–1; {x=x0+1 ∧ y=y0–1}, for some constants x0 and y0.
• {x=x0 ∧ y=y0} x=x+1; y=y–1; {x+y=x0+y0}, for some constants x0 and y0.
• {x+y=A} x=x+1; y=y–1; {x+y=A}, for some constant A.

Conditional statement:

• {true} if (x<0) {x=−x;} {x≥0}.
• {x=x0} if (x<0) {x=–x;} {x=|x0|}.
• {true} if (x<y) {x=x+y; y=x−y; x=x−y;} {x≥y}.
• {x=x0 ∧ y=y0} if (x<y) {x=x+y; y=x–y; x=x–y;} {x=max(x0,y0) ∧ y=min(x0,y0)}, for some constants x0 and y0.

Alternation statement:

• {x=x0 ∧ y=y0 ∧ x>0 ∧ y>0 ∧ x≠y} if (x>y) {x=x–y ;} else {y=y–x ;} {gcd(x,y)=gcd(x0,y0)}, for some constants x0 and y0.
• {gcd(x,y)=A ∧ x>0 ∧ y>0 ∧ x≠y} if (x>y) {x=x–y ;} else {y=y–x ;} {gcd(x,y)=A}, for some constant A.

Iteration:

• {true} while (y≠0) {x=x+1; y=y–1;} {y=0}
• {y≥0} while (y≠0) {x=x+1; y=y–1;} {y=0}
• {y<0} while (y≠0) {x=x+1; y=y–1;} {y=0}
• {x=x0 ∧ y=y0} while (y≠0) {x=x+1; y=y–1;} {x=x0+y0 ∧ y=0}, for some constants x0 and y0.
• {y≥0} while (y>0) {x=x+1; y=y–1;} {y=0}
• {x=x0 ∧ y≥0} while (y>0) {x=x+1; y=y–1;} {x≥x0}
• {y<0} while (y>0) {x=x+1; y=y–1;} {y<0}
• {x=x0 ∧ y=y0 ∧ y≥0} while (y>0) {x=x+1; y=y–1;} {x=x0+y0 ∧ y=0}, for some constants x0 and y0.
• {x=x0 ∧ y=y0 ∧ y<0} while (y>0) {x=x+1; y=y–1;} {x=x0 ∧ y= y0 ∧ y<0}, for some constants x0 and y0.
• {y<0} while (y≠0) {x=x+1; y=y–1;} {y=–1}
• {y<0} while (y≠0) {x=x+1; y=y–1;} {y=1}
• {y<0} while (y≠0) {x=x+1; y=y–1;} {y=2}

We leave it to the reader to ponder, by reference to the definition of this notation, why each one of the formulas above is valid. So far we have established the validity of these formulas by inspection, in reference to the definition. For larger and more complex programs, this may not be practical; in the next section, we introduce a deductive process that aims to establish the validity of complex formulas by induction on the complexity of the program structure.

5.3.2 An Inference System

An inference system is a system for inferring conclusions from hypotheses in a systematic manner. Such a system can be defined by means of the following artifacts:

• A set F of (syntactically defined) formulas.
• A subset A of F, called the set of axioms, which includes formulas that we assume to be valid by hypothesis.
• A set of inference rules, which we denote by R, where each rule is made up of a set of formulas called the premises of the rule, and a formula called the conclusion of the rule. We interpret a rule to mean that whenever the premises of a rule are valid, so is its conclusion; we usually represent a rule by listing its premises above a line and its conclusion below the line.

An inference in an inference system is an ordered sequence of formulas, say v₁, v₂, …, v_n, such each formula in the sequence, say v_i, is either an axiom or the conclusion of a rule whose premises appear prior to v_i, that is, amongst . A theorem of a deductive system is any formula that appears in an inference.

In this section, we propose an inference system that enables us to establish the validity of Hoare formulas by induction on the complexity of the program component of the formulas. To this effect, we present in turn, the formulas, then the axioms, and finally the rules.

• Formulas. Formulas of our inference system include all the formulas of logic, as well as Hoare formulas.
• Axioms. Axioms of this inference system include all the tautologies of logic, as well as the following formulas:
  • {false} p {ψ}, for any program p and any postcondition ψ.
  • {φ} p {true}, for any program p and any precondition φ.
• Rules. We present below a rule for each statement of a simple C-like programming language.

Assignment Statement Rule: We consider an assignment statement that affects a program variable (and implicitly preserving all other variables), and we interpret it as an assignment to the whole program state (changing the selected variable and preserving the other variables), which we denote by s=E(s), where s is the state of the program. We submit the following rule,

Interpretation: If we want ψ to hold after execution of the assignment statement, when s is replaced by E(s), then ψ(E(s)) must hold before execution of the assignment; hence the precondition φ must imply ψ(E(s)).

Sequence Rule: Let p be a sequence of two subprograms, say p1 and p2. We have the following rule,

Interpretation: if we can find an intermediate predicate int that serves as a postcondition to p1 and a precondition to p2, then the conclusion is established.

Conditional Rule: Let p be a conditional statement of the form: if (condition) {statement;}. We have the following rule,

Interpretation: The two premises of this rule correspond to the two execution paths through the flowchart of the conditional statement (Fig. 5.2).

Alternation Rule: Let p be an alternation statement of the form: if (condition) {statement;} else {statement;}. We have the following rule,

Interpretation: The two premises of this rule correspond to the two execution paths through the flowchart of the conditional statement (Fig. 5.3).

Iteration Rule: Let p be an iterative statement of the form: while (condition) {statement;}. We have the following rule,

Interpretation: The first and second premises establish an inductive proof to the effect that predicate inv holds after any number of iterations. The third premise provides that upon termination of the loop, the combination of predicate inv and the negation of the loop condition must logically imply the postcondition. Predicate inv is called an invariant assertion. It must be chosen so as to be sufficiently weak to satisfy the first premise, yet sufficient strong to satisfy the third premise (and the second). See the flowchart below, which highlight the points at which each of the relevant assertions is supposed to hold. Note that inv is placed upstream of the loop condition; hence the loop condition is never part of inv (since upstream of the loop condition we do not know whether t is true or not) (Fig. 5.4).

Consequence Rule: Given a Hoare formula, we can always strengthen the precondition and/or weaken the postcondition. We have the following rule:

Interpretation: This rule stems readily from the definition of these formulas.

Using the proposed axioms and rules, we can now generate theorems of the form {φ} p {ψ}. The question that arises then is: what good does it do us to generate such theorems? What does that tell us about p? The following Proposition provides the answer.

In the following section, we present sample illustrative examples of the inference system presented herein.

5.3.3 Illustrative Examples

We consider the following program on space S defined by variables x and y of type real, and we form a triplet by embedding it between a precondition and a postcondition:

• Program: while (y≠0) {x=x+1; y=y–1;}.
• Precondition: , for some constants x0 and y0.
• Postcondition: .

We form the following formula and we attempt to prove that this formula is a theorem of the proposed inference system:

While (y≠0){x=x+1;y=y−1;}

We apply the iteration rule to v, using the invariant assertion . This yields the following three formulas:

We find that v₀ and v₂ are both tautologies and hence they are axioms of the inference system. We consider v₁, to which we apply the sequence rule, with the intermediate assertion . This yields two formulas:

We apply the assignment statement rule to v₁₀ and v₁₁, which yields the following formulas:

We find that v₁₀₀ and v₁₁₀ are both tautologies and hence they are axioms of the inference system. This concludes our proof to the effect that v is a theorem, since the sequence

is an inference, as the reader may check: each formula in this sequence is either an axiom or the conclusion of a rule whose premises are to the left of the formula. By virtue of the proposition labeled Proving Partial Correctness, we conclude that program p is partially correct with respect to the following specification:

It may be more expressive to view this inference as a tree structure, where leaves are the axioms and internal nodes represent the rules that were invoked in the inference; the root of the tree represents the theorem that is established in the inference (Fig. 5.5).

As a second illustrative example, we let space S be defined by three integer variables n, f, k, such that n is nonnegative, and we let program p be defined as:

{f=1; k=1; while (k≠n+1) {f=f*k; k=k+1;};}.

We choose the following precondition and postcondition:

This produces the following formula:

v : {(n = n0)} f=1; k=1; while (k≠n+1) {f=f*k; k=k+1;} {f = n0!}.

We apply the sequence rule to v, using the intermediate predicate . This yields

while (k≠n+1) {f=f*k; k=k+1;} {f = n0!}.

We apply the sequence rule to v₀, using the intermediate assertion . This yields

We apply the assignment statement rule to v₀₀ and v₀₁. This yields respectively:

We find that v₀₀₀ and v₀₁₀ are both tautologies and hence axioms of the inference system. We now focus on v₁, to which we apply the iteration rule, with the invariant assertion . This yields:

We find that formula v₁₀ is a tautology, since the factorial of 0 is 1, and we find that formula v₁₂ is a tautology, by simple substitution. Hence we now focus on v₁₁, to which we apply the sequence rule, with the intermediate assertion . This yields:

Application of the assignment statement rule to v₁₁₀ and v₁₁₁ yields:

We find that v₁₁₀₀ and v₁₁₁₀ are both tautologies and hence axioms of the inference system. This concludes our proof; we leave it to the reader to verify that the following sequence is an inference in the proposed inference system:

Because v is a theorem, we conclude that program p is partially correct with respect to the following specification (formed from the precondition and postcondition of v):

As a third example, we consider the following GCD program on positive integer variables x and y:

{while (x≠y) {if (x>y) {x=x–y;} else {y=y–x;};},

and we consider the following precondition/postcondition pair:

We form the following formula:

We apply the iteration rule to v with the following invariant assertion: . This yields:

We find that v₀ and v₂ are tautologies and hence axioms of the inference system. We focus on v₁, to which we apply the alternation rule, which yields:

We apply the assignment statement rule to v₁₀ and v₁₁, which yields:

We find that both of these formulas are tautologies and hence axioms of the inference system. This concludes the proof that v is a theorem; hence program p is partially correct with respect to