Differences

This shows you the differences between two versions of the page.

--- sav07_lecture_4 [2007/03/28 09:49]
iulian.dragos
+++ 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.
@@ Line 41: / Line 43: @@
   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
@@ 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.
 ==== 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
   * Edsger W. Dijkstra: A Discipline of Programming
   * C. A. R. Hoare, He Jifeng: Unifying Theories of Programming
 ===== Modeling data structures =====