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:44] vkuncak |
sav07_lecture_3_skeleton [2007/03/20 17:19] vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Lecture 3 (Skeleton) ====== | ====== Lecture 3 (Skeleton) ====== | ||
+ | |||
+ | ===== Converting programs (with simple values) to formulas ===== | ||
+ | |||
+ | |||
==== Context ==== | ==== Context ==== | ||
Line 6: | Line 10: | ||
* represent programs using guarded command language, e.g. desugaring of 'if' into non-deterministic choice and assume | * represent programs using guarded command language, e.g. desugaring of 'if' into non-deterministic choice and assume | ||
* give meaning to guarded command language statements as relations | * give meaning to guarded command language statements as relations | ||
- | * we can represent relations using set comprehensions; if our program r has two state components, we can represent its meaning R(r) as | + | * we can represent relations using set comprehensions; if our program c has two state components, we can represent its meaning R( c ) as |
<latex> | <latex> | ||
\{((x_0,y_0),(x,y)) \mid F \} | \{((x_0,y_0),(x,y)) \mid F \} | ||
</latex> | </latex> | ||
- | where F is some formula that has x,y,x_0,y_0 as free variables. | + | where F is some formula that has x,y,x_0,y_0 as free variables. |
- | Our goal is to find rules for computing R(r) that are | + | * this is what I mean by ''simple values'': later we will talk about modeling pointers and arrays, but we will still use this as a starting point. |
+ | |||
+ | Our goal is to find rules for computing R( c ) that are | ||
* correct | * correct | ||
* efficient | * efficient | ||
- | * create formulas that we can prove later | + | * create formulas that we can effectively prove later |
+ | |||
+ | What exactly do we prove about the formula R( c ) ? | ||
+ | |||
+ | We prove that this formula is **valid** | ||
+ | |||
+ | R( c ) -> error=false | ||
Line 59: | Line 71: | ||
when c is a basic command. | when c is a basic command. | ||
+ | |||
+ | |||
Line 74: | Line 88: | ||
But if a variable is equal to another, it can be substituted using the substitution rules | But if a variable is equal to another, it can be substituted using the substitution rules | ||
- | (exists x_1. x_1 = t & F(x_1)) <-> F(t) | + | (exists x_1. x_1=t & F(x_1)) <-> F(t) |
- | (forall x_1. x_1 = t -> F(x_1) <-> F(t) | + | (forall x_1. x_1=t -> F(x_1) <-> F(t) |
We can apply these rules to reduce the size of formulas. | We can apply these rules to reduce the size of formulas. | ||
+ | |||
+ | ==== Symbolic execution ==== | ||
+ | |||
+ | Symbolic execution converts programs into formulas by going forward. It is therefore somewhat analogous to the way an [[interpreter]] for the language would work. It is based on the notion of strongest postcondition. | ||
+ | |||
+ | ==== Weakest preconditions ==== | ||
+ | |||
+ | While symbolic execution computes formula by going forward along the program syntax tree, weakest precondition computes formula by going backward. | ||
==== Papers ==== | ==== Papers ==== |