Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav07_lecture_4_skeleton [2007/03/22 20:30] vkuncak |
sav07_lecture_4_skeleton [2007/03/26 14:14] leander.eyer |
||
|---|---|---|---|
| Line 17: | Line 17: | ||
| === wp of havoc === | === wp of havoc === | ||
| - | Can we derive wp(Q,havoc(x)? | + | Can we derive wp(Q,havoc(x))? |
| * By consider havoc(x) as (... [] x=-1 [] x = 0 [] x = 1 [] ...) ? | * By consider havoc(x) as (... [] x=-1 [] x = 0 [] x = 1 [] ...) ? | ||
| * From relational definition? | * From relational definition? | ||
| Line 64: | Line 64: | ||
| 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 (under 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 85: | ||
| 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 109: | Line 147: | ||
| * [[Gallier Logic Book]], Chapter 10.6 | * [[Gallier Logic Book]], Chapter 10.6 | ||
| * {{nelsonoppen80decisionprocedurescongruenceclosure.pdf|the original paper by Nelson and Oppen}} | * {{nelsonoppen80decisionprocedurescongruenceclosure.pdf|the original paper by Nelson and Oppen}} | ||
| - | |||