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 14:53] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Lecture 3 (Skeleton) ====== | ====== Lecture 3 (Skeleton) ====== | ||
| + | |||
| + | ===== Converting programs (with simple values) to formulas ===== | ||
| ==== Context ==== | ==== Context ==== | ||
| Line 11: | Line 13: | ||
| </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. | ||
| + | |||
| + | * 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(r) that are | Our goal is to find rules for computing R(r) that are | ||
| Line 60: | Line 64: | ||
| when c is a basic command. | when c is a basic command. | ||
| - | ==== Accumulation of equalities ==== | + | |
| + | |||
| + | ==== Avoiding accumulation of equalities ==== | ||
| This approach generates many variables and many frame conditions. | This approach generates many variables and many frame conditions. | ||
| Line 73: | Line 79: | ||
| 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. | ||