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 | ||
|
sav08:sign_analysis_of_expressions_and_programs [2008/05/07 00:14] vkuncak |
sav08:sign_analysis_of_expressions_and_programs [2008/05/07 00:45] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Sign Analysis of Expressions and Programs ====== | ====== Sign Analysis of Expressions and Programs ====== | ||
| + | |||
| + | ===== Sign Analysis of Expressions ===== | ||
| Suppose we want to test quickly whether the result of an expression is positive, negative or zero. | Suppose we want to test quickly whether the result of an expression is positive, negative or zero. | ||
| Line 28: | Line 30: | ||
| Concrete operations: ${+}, {\times} : \mathbb{Z}^2 \to \mathbb{Z}$ | Concrete operations: ${+}, {\times} : \mathbb{Z}^2 \to \mathbb{Z}$ | ||
| - | Abstract domain: $A = \{ pos, neg, \top \}$ | + | Abstract domain: $A = \{ neg, nul, pos, \top \}$ |
| + | |||
| + | Abstract operations: $\oplus, \otimes : A^2 \to A$ defined by tables: | ||
| + | |||
| + | ===== Sign Analysis of Programs ===== | ||
| + | |||
| + | Prove that this program never reports error: | ||
| - | Abstract operations: $\oplus, \otimes : A^2 \to A$ | + | <code> |
| + | i = 20; | ||
| + | x = 2; | ||
| + | while (i > 0) { | ||
| + | x = x + 4; | ||
| + | i = i - 1; | ||
| + | } | ||
| + | if (x==0) { | ||
| + | error; | ||
| + | } else { | ||
| + | y = 1000/x; | ||
| + | } | ||
| + | </code> | ||