Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
sav08:backward_vcg_with_loops [2008/03/05 01:45] vkuncak |
sav08:backward_vcg_with_loops [2009/03/11 10:58] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Backward VCG with Loops ====== | ====== Backward VCG with Loops ====== | ||
| + | |||
| + | When using wp, we do not need to separately accumulate verification conditions, because we accumulate them all in the precondition formula. | ||
| ===== Desugaring loops with loop invariants ==== | ===== Desugaring loops with loop invariants ==== | ||
| Line 43: | Line 45: | ||
| 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. | 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. | ||
| + | |||
| ===== Avoiding Exponential Explosion ===== | ===== Avoiding Exponential Explosion ===== | ||
| - | Static single assignment form. | + | The tricks to avoid exponential explosion can also be implemented in backwards verification-condition generation, using a variant of static single assignment form. |
| - | * [[http://research.microsoft.com/~leino/papers/krml157.pdf|Weakest preconditions for unstructured programs]] | ||
| * [[http://doi.acm.org/10.1145/360204.360220|Avoiding exponential explosion: generating compact verification conditions]] | * [[http://doi.acm.org/10.1145/360204.360220|Avoiding exponential explosion: generating compact verification conditions]] | ||
| + | * [[http://research.microsoft.com/~leino/papers/krml157.pdf|Weakest preconditions for unstructured programs]] | ||
| + | * [[http://citeseer.ist.psu.edu/697165.html|Efficient weakest preconditions]] | ||