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_20 [2007/06/05 11:19] kremena.diatchka |
sav07_lecture_20 [2007/06/05 19:22] vkuncak |
||
|---|---|---|---|
| Line 44: | Line 44: | ||
| - must follow protocol: (open (read+write)* close)* | - must follow protocol: (open (read+write)* close)* | ||
| - must follow protocol: (startLog stopLog)* | - must follow protocol: (startLog stopLog)* | ||
| + | |||
| + | |||
| + | |||
| Line 53: | Line 56: | ||
| Let $S$ be the set of program states and $V$ be the set of vertices in the control flow graph. Then we can describe a point in the program as: | Let $S$ be the set of program states and $V$ be the set of vertices in the control flow graph. Then we can describe a point in the program as: | ||
| - | $(s,c)$ | + | $(c,s)$ |
| - | where $s \in S, c \in V$ | + | where $c \in V, s \in S$ |
| Consider the following example: | Consider the following example: | ||
| - | Picture will go here. | + | {{lect20_big_step.png|}} |
| $p()$ is a procedure which can described by the relation $r$: $\{(x,y), (x',y') | x'=100 \wedge y'=y\}$ | $p()$ is a procedure which can described by the relation $r$: $\{(x,y), (x',y') | x'=100 \wedge y'=y\}$ | ||
| Line 66: | Line 69: | ||
| Then we can formally define the semantics of a big step ($\mapsto$) as: | Then we can formally define the semantics of a big step ($\mapsto$) as: | ||
| - | $(c_{0},s_{1}) \mapsto (c_{3}, s_{2})$ | + | $(c_{1},s_{1}) \mapsto (c_{2}, s_{2})$ |
| where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | ||
| Line 91: | Line 94: | ||
| $(s, l, c, t)$ | $(s, l, c, t)$ | ||
| - | Here $l \in L$, where $L$ is the set of local variables of a procedure. Everything would be popped off from $l$ when the procedure returns control to the callee. | + | Here $l \in L$, where $L$ is the set of mappings of local variables of a procedure to their values. Furthermore, on each procedure call, the program pushes $l$ on the stack along with the program point. Everything would be popped off from $l$ when the procedure returns control to the callee. |
| One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | ||
| Line 154: | Line 157: | ||
| In order to define procedure contracts for ''readContent()'' and ''p1()'' to ensure that this property is satisfied, we introduce an object called ''FileState'' which has a typestate. In typestate systems, the type of an object is allowed to change during its lifetime in the computation. In the paper [[http://lara.epfl.ch/~kuncak/papers/LamETAL05GeneralizedTypestateCheckingDataStructureConsistency.pdf|Generalized typestate checking for data structure consistency]], it says that "unlike standard type systems, typestate systems can enforce safety properties that depend on changing object states". | In order to define procedure contracts for ''readContent()'' and ''p1()'' to ensure that this property is satisfied, we introduce an object called ''FileState'' which has a typestate. In typestate systems, the type of an object is allowed to change during its lifetime in the computation. In the paper [[http://lara.epfl.ch/~kuncak/papers/LamETAL05GeneralizedTypestateCheckingDataStructureConsistency.pdf|Generalized typestate checking for data structure consistency]], it says that "unlike standard type systems, typestate systems can enforce safety properties that depend on changing object states". | ||
| - | Therefore ''FileState'' has type ''file'' and two states, ''open'' and ''closed''. Using this notion, we can write the procedure contracts for the two methods as follows: | + | Therefore ''FileState'' has type ''file'' and two states, ''open'' and ''closed''. |
| + | |||
| + | {{lect20_fsm2.png|}} | ||
| + | |||
| + | Using this notion, we can write the procedure contracts for the two methods as follows: | ||
| readContent() | readContent() | ||