Differences

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

--- sav08:normal_form_of_loop-free_programs [2008/03/04 17:32]
vkuncak
+++ sav08:normal_form_of_loop-free_programs [2009/03/04 18:57]
vkuncak
@@ Line 1: / Line 1: @@
-====== Normal form for loop-free programs ======
-Example:
-<code>
-(if (x < 0) x=x+1 else x=x);
-(if (y < 0) y=y+x else y=y);
-</code>
-Without loops, after expressing conditionals using [] we obtain
-  c ::=  x=T | assume(F) |  c [] c  |  c ; c
-Laws:
-\[
-     (r_1 \cup r_2) \circ r_3 = (r_1 \circ r_3) \cup (r_2 \circ r_3)
-\]
-\[
-     r_3 \circ (r_1 \cup r_2) = (r_3 \circ r_1) \cup (r_3 \circ r_2)
-\]
-Normal form:
-\[
-   \bigcup_{i=1}^n p_i
-\]
-Each $p_i$ is of form $b_1 \circ \ldots \circ b_k$ for some $k$, where each $b_i$ is assignment or assume.  Each $p_i$ corresponds to one of the finitely paths from beginning to end of the acyclic control-flow graph for loop-free program.
-Length of normal form with sequences of if-then-else.
 We want to show:
@@ Line 40: / Line 15: @@
    \bigwedge_{i=1}^n (\{P\} p_i \{Q\})
 \]
+Note: the rule also applies to infinite union of paths (e.g. generated by loops).
 ===== Three Approaches to Generate Verification Conditions =====
@@ Line 47: / Line 24: @@
   - compute $sp(P,r)$ as a formula, then check entailment $sp(P,r) \subseteq Q$ (forward symbolic execution)
   - compute $wp(Q,r)$ as a formula, then check $P \subseteq wp(Q,r)$ (backward symbolic execution)