Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav07_lecture_4 [2007/03/27 16:35] leander.eyer |
sav07_lecture_4 [2007/03/28 18:14] vkuncak |
||
---|---|---|---|
Line 8: | Line 8: | ||
We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | ||
+ | |||
+ | |||
Line 41: | Line 43: | ||
havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | ||
- | FIXME | + | This is the relation that links all states where all variables but x remain unchanged. Intuitively, it makes sense that proving Q holds after visiting the havoc(x) relation is the same than proving Q for all values of x. |
+ | |||
+ | wp(Q,havoc(x)) = {(x1,y1) | ∀(x2,y2). ((x1,y1),(x2,y2)) ∈ havoc(x) -> (x2,y2) ∈ Q} | ||
+ | = {(x1,y1) | ∀(x2,y2). y1 = y2 -> (x2,y2) ∈ Q} | ||
+ | = {(x1,y1) | ∀x2. Q[y2:=y1]} | ||
+ | = ∀x. Q | ||
+ | |||
+ | Note that instead of using states s<sub>1</sub> and s<sub>2</sub>, pairs (x<sub>1</sub>,y<sub>1</sub>) and (x<sub>2</sub>,y<sub>2</sub>) are used. y stands for all unchanged variables. | ||
* By wp semantics of havoc and assume | * By wp semantics of havoc and assume | ||
Line 90: | Line 99: | ||
Benefit: if there is x_{n+1} that is not changed, we do not need to write its properties in the loop invariant. This can make loop invariant shorter. | Benefit: if there is x_{n+1} that is not changed, we do not need to write its properties in the loop invariant. This can make loop invariant shorter. | ||
+ | |||
==== References about weakest precondition (under construction) ==== | ==== References about weakest precondition (under construction) ==== | ||
- | * (some online references will come here) | + | * [[http://www.soe.ucsc.edu/%7Ecormac/papers/popl01.ps|Avoiding Exponential Explosion: Generating Compact Verification Conditions]] |
* Back, Wright: Refinement Calculus | * Back, Wright: Refinement Calculus | ||
* Edsger W. Dijkstra: A Discipline of Programming | * Edsger W. Dijkstra: A Discipline of Programming | ||
* C. A. R. Hoare, He Jifeng: Unifying Theories of Programming | * C. A. R. Hoare, He Jifeng: Unifying Theories of Programming | ||
- | |||
- | |||
- | |||
- | |||
===== Modeling data structures ===== | ===== Modeling data structures ===== | ||
Line 270: | Line 276: | ||
assume(x ∉ alloc); | assume(x ∉ alloc); | ||
alloc = alloc ∪ {x} | alloc = alloc ∪ {x} | ||
+ | |||
Line 275: | Line 282: | ||
==== Dynamically allocated arrays ==== | ==== Dynamically allocated arrays ==== | ||
- | When we allow dynamically allocated arrays, we introduce an additional parameter to the array function which identifies the array in question. | + | When we allow dynamically allocated arrays, we introduce a new global function **array** which maps a pair (arrayID, index) to values. |
x[i] = v; | x[i] = v; | ||
Line 289: | Line 296: | ||
===== Proving formulas with uninterpreted functions ===== | ===== Proving formulas with uninterpreted functions ===== | ||
+ | ==== Congruence closure algorithm ==== | ||
+ | The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula. | ||
+ | Recall the following properties of the relation **equivalence**: | ||
+ | - x = x (everything is equal to itself) (reflexivity) | ||
+ | - x = y -> y = x (symmetry) | ||
+ | - x = y ∧ y = z -> x = z (transitivity) | ||
+ | A congruence is an equivalence relationship with the additional property | ||
+ | * (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2) | ||
+ | a ≡ b (mod n) is a congruence in respect to addition. Indeed: | ||
- | + | a ≡ b (mod n) ∧ c ≡ d (mod n) -> a + c ≡ b + d (mod n) | |
- | + | ||
- | + | ||
- | + | ||
- | ==== Congruence closure algorithm ==== | + | |
- | + | ||
- | The congruence closure algorithm can be used to proove the correctness of quantifier free formulas by examining congruence closures of the statements in the formula. | + | |
- | + | ||
- | Recall the following properties of relations: | + | |
- | - x = x (everything is equal to itself) | + | |
- | - x = y -> y = x (reflexivity) | + | |
- | - x = y ∧ y = z -> x = z (transitivity) | + | |
- | - (x1 = x2 ∧ y1 = y2) -> f(x1, y1) = f(x2, y2) (equivalence in functions) | + | |
Equality is a congruence with respect to all function symbols. | Equality is a congruence with respect to all function symbols. |