Hoare logic
|
|
Hoare logic is a formal system developed by the British computer scientist C. A. R. Hoare, and subsequently refined by Hoare and other researchers. It was published in Hoare's 1969 paper "An axiomatic basis for computer programming". The purpose of the system is to provide a set of logical rules in order to reason about the correctness of computer programs with the rigour of mathematical logic.
Hoare acknowledges earlier contributions from Robert Floyd, who had published a similar system for flowcharts.
The central feature of Hoare logic is the Hoare triple. A triple describes how the execution of a piece of code changes the state of the computation. A Hoare triple is of the form
- <math>\{P\}\;C\;\{Q\}<math>
where P and Q are assertions and C is a command. P is called the precondition and Q the postcondition. Assertions are formulas in predicate logic. The intuitive reading of such a triple is: Whenever P holds of the state before the execution of C, then Q will hold afterwards. Note that if C does not terminate, then there is no "after", so Q can be any statement at all. Indeed, one can choose Q to be false to express that C does not terminate.
This is called "partial correctness". If C terminates and at termination Q is true, the expression exhibits "total correctness". Termination would have to be proved separately.
Hoare logic has axioms and inference rules for all the constructs of a simple imperative programming language. In addition to the rules for the simple language in Hoare's original paper, rules for other language constructs have been developed since then by Hoare and many other researchers. There are rules for concurrency, procedures, jumps, and pointers.
The assignment axiom states that after the assignment any predicate holds for the variable that was previously true for the right-hand side of the assignment:
- <math> \frac{}{\{P[E/x]\}\ x:=E \ \{P\} } <math>
An example of a valid triple is:
- <math>\{ x = 42\} \ y:=x + 1\ \{y =43 \wedge x= 42\}<math>
- Sequencing rule
- <math> \frac {\{P\}\ S\ \{Q\}\ , \ \{Q\}\ T\ \{R\} } {\{P\}\ S;T\ \{R\}} <math>
For example, consider the following two instances of the assignment axiom:
- <math>\{ x + 1 = 43\} \ y:=x + 1\ \{y =43 \}<math>
and
- <math>\{ y = 43\} \ z:=y\ \{z =43 \}<math>
By the sequencing rule, one concludes:
- <math>\{ x + 1 = 43\} \ y:=x + 1; z:= y\ \{z =43 \}<math>
- Conditional rule
- <math>\frac { \{B \wedge P\}\ S\ \{Q\}\ ,\ \{\neg B \wedge P \}\ T\ \{Q\} }
{ \{P\}\ if\ B\ then\ S\ else\ T\ \{Q\} } <math>
- While rule
- <math>\frac { \{P \wedge B \}\ S\ \{P\} }
{ \{P \}\ while\ B\ do\ S\ od\ \{\neg B \wedge\ P\} }
<math>
P is the loop invariant.
- Rule of consequence
- <math>
\frac { P^\prime \rightarrow\ P\ ,\ \lbrace P \rbrace\ S\ \lbrace Q \rbrace\ ,\ Q \rightarrow\ Q^\prime } { \lbrace P^\prime\ \rbrace\ S\ \lbrace Q^\prime\rbrace } <math>
Total correctness
The rules above only prove partial correctness. Total correctness can be proved with an extended version of the While rule.
- While Rule for total correctness:
- <math>
\frac { \{P \wedge B \wedge z = t \}\ S\ \{P \wedge z > t \},P \rightarrow t \geq 0}
{ \{P \}\ while\ B\ do\ S\ od\} \{\neg B \wedge\ P\} }
<math>
In this rule, in addition to maintaining the loop invariant, one also proves termination by way of a term whose value decreases during each iteration.
See also
References
- C. A. R. Hoare. "An axiomatic basis for computer programming". Communications of the ACM, 12(10):576-585, October 1969. [1] (http://doi.acm.org/10.1145/363235.363259)
- Robert D. Tennent: "Specifying Software" (a recent textbook that includes an introduction to Hoare logic) ISBN 0-521-00401-2 [2] (http://www.cs.queensu.ca/home/specsoft/)de:Hoarekalkül