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_4_skeleton [2007/03/22 20:26] vkuncak |
sav07_lecture_4_skeleton [2007/03/22 20:45] vkuncak |
||
---|---|---|---|
Line 8: | Line 8: | ||
We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | We use weakest preconditions, although you could also use strongest postconditions or any other variants of the conversion from programs to formulas. | ||
+ | |||
===== More on wp ===== | ===== More on wp ===== | ||
Line 64: | Line 65: | ||
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. | ||
+ | |||
+ | |||
+ | ==== References about weakest precondition (in construction) ==== | ||
+ | * (some online references will come here) | ||
+ | * Back, Wright: Refinement Calculus | ||
+ | * Edsger W. Dijkstra: A Discipline of Programming | ||
+ | * C. A. R. Hoare, He Jifeng: Unifying Theories of Programming | ||
===== Modeling data structures ===== | ===== Modeling data structures ===== | ||
Line 76: | Line 84: | ||
Array bounds checking. | Array bounds checking. | ||
+ | |||
==== Semantics of references ==== | ==== Semantics of references ==== | ||
Objects as references, null as an object. | Objects as references, null as an object. | ||
+ | |||
+ | Program with class declaration | ||
+ | |||
+ | <code java> | ||
+ | class Node { | ||
+ | Node left, right; | ||
+ | } | ||
+ | </code> | ||
+ | |||
+ | How can we represent fields? | ||
+ | |||
+ | Possible mathematical model: fields as functions from objects to objects. | ||
+ | |||
+ | left : Node => Node | ||
+ | right : Node => Node | ||
+ | |||
+ | What is the meaning of assignment? | ||
+ | |||
+ | x.f = y | ||
+ | |||
+ | <latex> | ||
+ | f[x \mapsto y](z) = \left\{ \begin{array}{lr} | ||
+ | y, & z=x \\ | ||
+ | f(z), & z \neq x | ||
+ | \end{array}\right. | ||
+ | </latex> | ||
+ | |||
+ | left, right - uninterpreted functions (can have any value, depending on the program, unlike arithmetic functions such as +,-,* that have fixed interpretation). | ||
Null checks. | Null checks. | ||
Line 96: | Line 133: | ||
Again, the second part! More technical. But, often you can use these things as a black box. | Again, the second part! More technical. But, often you can use these things as a black box. | ||
+ | |||
==== Congruence closure algorithm ==== | ==== Congruence closure algorithm ==== | ||
Line 106: | Line 144: | ||
More information on congruence closure algorithm: | More information on congruence closure algorithm: | ||
- | * Gallier, Chapter 10.6 | + | * [[Gallier Logic Book]], Chapter 10.6 |
- | * The paper by Nelson and Oppen | + | * {{nelsonoppen80decisionprocedurescongruenceclosure.pdf|the original paper by Nelson and Oppen}} |