Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav08:review_of_fixpoints_in_semantics [2008/04/30 10:43] vkuncak |
sav08:review_of_fixpoints_in_semantics [2015/04/21 17:30] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Review of Fixpoints in Semantics ====== | ====== Review of Fixpoints in Semantics ====== | ||
- | |||
- | **Definition:** Given a set $A$ and a function $f : A \to A$ we say that $x \in A$ is a fixed point (fixpoint) of $f$ if $f(x)=x$. | ||
- | |||
- | **Definition:** Let $(A,\le)$ be a partial order, let $f : A \to A$ be a monotonic function on $(A,\le)$, and let the set of its fixpoints be $S = \{ x \mid f(x)=x \}$. If the least element of $S$ exists, it is called the **least fixpoint**, if the greatest element of $S$ exists, it is called the **greatest fixpoint**. | ||
- | |||
- | Note: | ||
- | * a function can have various number of fixpoints. Take $f : {\cal Z} \to {\cal Z}$, | ||
- | * $f(x)=x$ the set of fixedpoints is | ||
- | * $f(x)=x^2$ the set of fixedpoints is | ||
- | * $f(x)=3x-6$ has exactly one fixpoint | ||
- | * a function can have at most one least and at most one greatest fixpoint | ||
- | |||
- | We can use fixpoints to give meaning to recursive and iterative definitions | ||
- | * key to describing arbitrary long executions in programs | ||
===== Transitive Closure as Least Fixedpoint ===== | ===== Transitive Closure as Least Fixedpoint ===== | ||
Recall the definition of transitive closure for $r \subseteq D \times D$ a binary relation | Recall the definition of transitive closure for $r \subseteq D \times D$ a binary relation | ||
- | \[ | + | \begin{equation*} |
r^* = \bigcup_{n \ge 0} r^n | r^* = \bigcup_{n \ge 0} r^n | ||
- | \] | + | \end{equation*} |
where $r^0 = \Delta_D$. | where $r^0 = \Delta_D$. | ||
Line 37: | Line 23: | ||
This can be written as | This can be written as | ||
- | \[ | + | \begin{equation*} |
p = F(p) | p = F(p) | ||
- | \] | + | \end{equation*} |
where | where | ||
F(p) = if (c) then (s;p) else skip | F(p) = if (c) then (s;p) else skip | ||
Line 49: | Line 35: | ||
If $r_s$ is meaning of $s$ and $\Delta_c$ is meaning of //assume( c )//, the meaning is the fixpoint of function | If $r_s$ is meaning of $s$ and $\Delta_c$ is meaning of //assume( c )//, the meaning is the fixpoint of function | ||
- | \[ | + | \begin{equation*} |
f(r) = (\Delta_c \circ r_s \circ r) \cup \Delta_{\lnot c} | f(r) = (\Delta_c \circ r_s \circ r) \cup \Delta_{\lnot c} | ||
- | \] | + | \end{equation*} |
Any program can be reduced to a loop: | Any program can be reduced to a loop: | ||
Line 74: | Line 60: | ||
Program points are CFG nodes. Statements are labels on CFG edges. | Program points are CFG nodes. Statements are labels on CFG edges. | ||
- | We look at a particular way of representing and computing sets of reachable, splitting states by program counter (control-flow graph node): **collecting semantics**. | + | We look at a particular way of representing and computing sets of reachable states, splitting states by program counter (control-flow graph node): **collecting semantics**. |
$PS$ - the set of values of program variables (not including program counter). | $PS$ - the set of values of program variables (not including program counter). | ||
Line 84: | Line 70: | ||
Let $p_0$ be initial program counter and $I$ the set of values of program variables in $p_0$. | Let $p_0$ be initial program counter and $I$ the set of values of program variables in $p_0$. | ||
- | The set of reachable states is defined as the least solution of: | + | The set of reachable states is defined as the least solution of constraints: |
+ | \begin{equation*} | ||
+ | I \subseteq C(p_0) | ||
+ | \end{equation*} | ||
+ | \begin{equation*} | ||
+ | \bigwedge_{(p_1,p_2) \in E} sp(C(p),r(c(p_1,p_2)))) \subseteq C(p_2) | ||
+ | \end{equation*} | ||
+ | where $c(p_1,p_2)$ is command associated with edge $(p_1,p_2)$, and $r(c(p_1,p_2))$ is the relation giving semantics for this command. | ||