Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav07_lecture_3_skeleton [2007/03/20 14:27] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 14:35] vkuncak |
||
---|---|---|---|
Line 24: | Line 24: | ||
R(x=t) = (x=t & y=y_0 & error=error_0) | R(x=t) = (x=t & y=y_0 & error=error_0) | ||
- | ***Note***: all our statements will have the property that if error_0 = true, then error=true. That is, you can never recover from an error state. This is convenient: if we prove no errors at the end, then there were never errors in between. | + | **Note**: all our statements will have the property that if error_0 = true, then error=true. That is, you can never recover from an error state. This is convenient: if we prove no errors at the end, then there were never errors in between. |
- | ***Note***: the condition y=y_0 & error=error_0 is called <b>frame condition</b>. There are as many conjuncts as there are components of the state. This can be annoying to write, so let us use shorthand frame(x) for it. The shorthand frame(x) denotes a conjunction of v=v_0 for all v that are distinct from x (in this case y and error). We can have zero or more variables as arguments of frame, so frame() means that nothing changes. | + | **Note**: the condition y=y_0 & error=error_0 is called <b>frame condition</b>. There are as many conjuncts as there are components of the state. This can be annoying to write, so let us use shorthand frame(x) for it. The shorthand frame(x) denotes a conjunction of v=v_0 for all v that are distinct from x (in this case y and error). We can have zero or more variables as arguments of frame, so frame() means that nothing changes. |
R(havoc x) = frame(x) | R(havoc x) = frame(x) | ||
Line 32: | Line 32: | ||
R(assert F) = (F -> frame) | R(assert F) = (F -> frame) | ||
- | Note: | + | **Note**: |
x=t is same as havoc(x);assume(x=t) | x=t is same as havoc(x);assume(x=t) | ||
assert false = crash (stops with error) | assert false = crash (stops with error) | ||
+ | |||
assume true = skip (does nothing) | assume true = skip (does nothing) | ||
+ | |||
+ | |||
+ | ==== Composing formulas using relation composition ==== | ||
+ | |||
+ | This is perhaps the most direct way of transforming programs to formulas. It creates formulas that are linear in the size of the program. | ||
+ | |||
+ | Non-deterministic choice is union of relations, that is, disjunction of formulas: | ||
+ | |||
+ | CR(c1 [] c2) = CR(c1) | CR(c2) | ||
+ | |||
+ | In sequential composition we follow the rule for composition of relations. We want to get again formula with free variables x_0,y_0,x,y. So we need to do renaming. Let x_1,y_1,error_1 be fresh variables. | ||
+ | |||
+ | CR(c1 ; c2) = exists x_1,y_1,error_1. CR(c1)[x:=x_1,y:=y_1,error:=error_1] & CR(c2)[x:=x_1,y:=y_1,error:=error_1] | ||
+ | |||
==== Papers ==== | ==== Papers ==== |