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/28 14:45] cedric.jeanneret |
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 42: | Line 43: | ||
| havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | havoc(x) = {(s,t) | ∀y "y"≠"x".t("y")=s("y")} | ||
| - | 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, it is the same than proving Q for all values of x. | + | 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} | wp(Q,havoc(x)) = {(x1,y1) | ∀(x2,y2). ((x1,y1),(x2,y2)) ∈ havoc(x) -> (x2,y2) ∈ Q} | ||
| Line 98: | 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 ===== | ||