algebra.tex 16.2 KB
Newer Older
1
\section{Algebraic Structures}
2

3
\subsection{OFE}
4

5
The model of Iris lives in the category of \emph{Ordered Families of Equivalences} (OFEs).
6
This definition varies slightly from the original one in~\cite{catlogic}.
7

8
\begin{defn}
9
  An \emph{ordered family of equivalences} (OFE) is a tuple $(\ofe, ({\nequiv{n}} \subseteq \ofe \times \ofe)_{n \in \nat})$ satisfying
10
  \begin{align*}
11 12 13
    \All n. (\nequiv{n}) ~& \text{is an equivalence relation} \tagH{ofe-equiv} \\
    \All n, m.& n \geq m \Ra (\nequiv{n}) \subseteq (\nequiv{m}) \tagH{ofe-mono} \\
    \All x, y.& x = y \Lra (\All n. x \nequiv{n} y) \tagH{ofe-limit}
14 15 16
  \end{align*}
\end{defn}

17 18
The key intuition behind OFEs is that elements $x$ and $y$ are $n$-equivalent, notation $x \nequiv{n} y$, if they are \emph{equivalent for $n$ steps of computation}, \ie if they cannot be distinguished by a program running for no more than $n$ steps.
In other words, as $n$ increases, $\nequiv{n}$ becomes more and more refined (\ruleref{ofe-mono})---and in the limit, it agrees with plain equality (\ruleref{ofe-limit}).
19

20 21
Notice that OFEs are just a different presentation of bisected 1-bounded ultrametric spaces, where the family of equivalence relations gives rise to the distance function (two elements that are equal for $n$ steps are no more than $2^{-n}$ apart).

22
\begin{defn}
23 24 25 26
  An element $x \in \ofe$ of an OFE is called \emph{discrete} if
  \[ \All y \in \ofe. x \nequiv{0} y \Ra x = y\]
  An OFE $A$ is called \emph{discrete} if all its elements are discrete.
  For a set $X$, we write $\Delta X$ for the discrete OFE with $x \nequiv{n} x' \eqdef x = x'$
27 28 29
\end{defn}

\begin{defn}
30 31
  A function $f : \ofe \to \ofeB$ between two OFEs is \emph{non-expansive} (written $f : \ofe \nfn \ofeB$) if
  \[\All n, x \in \ofe, y \in \ofe. x \nequiv{n} y \Ra f(x) \nequiv{n} f(y) \]
32
  It is \emph{contractive} if
33
  \[ \All n, x \in \ofe, y \in \ofe. (\All m < n. x \nequiv{m} y) \Ra f(x) \nequiv{n} f(y) \]
34
\end{defn}
35 36
Intuitively, applying a non-expansive function to some data will not suddenly introduce differences between seemingly equal data.
Elements that cannot be distinguished by programs within $n$ steps remain indistinguishable after applying $f$.
37 38

\begin{defn}
39
  The category $\OFEs$ consists of OFEs as objects, and non-expansive functions as arrows.
40
\end{defn}
Ralf Jung's avatar
Ralf Jung committed
41

Ralf Jung's avatar
Ralf Jung committed
42 43
Note that $\OFEs$ is bicartesian closed, \ie it has all sums, products and exponentials as well as an initial and a terminal object.
In particular:
Ralf Jung's avatar
Ralf Jung committed
44
\begin{defn}
45
  Given two OFEs $\ofe$ and $\ofeB$, the set of non-expansive functions $\set{f : \ofe \nfn \ofeB}$ is itself an OFE with
Ralf Jung's avatar
Ralf Jung committed
46
  \begin{align*}
47
    f \nequiv{n} g \eqdef{}& \All x \in \ofe. f(x) \nequiv{n} g(x)
Ralf Jung's avatar
Ralf Jung committed
48 49
  \end{align*}
\end{defn}
50 51

\begin{defn}
52
  A (bi)functor $F : \OFEs \to \OFEs$ is called \emph{locally non-expansive} if its action $F_1$ on arrows is itself a non-expansive map.
53 54
  Similarly, $F$ is called \emph{locally contractive} if $F_1$ is a contractive map.
\end{defn}
Ralf Jung's avatar
Ralf Jung committed
55
The function space $(-) \nfn (-)$ is a locally non-expansive bifunctor.
Ralf Jung's avatar
Ralf Jung committed
56
Note that the composition of non-expansive (bi)functors is non-expansive, and the composition of a non-expansive and a contractive (bi)functor is contractive.
57

58 59 60 61 62 63 64 65 66 67
One very important OFE is the OFE of \emph{step-indexed propositions}:
For every step-index, such a proposition either holds or does not hold.
Moreover, if a propositions holds for some $n$, it also has to hold for all smaller step-indices.
\begin{align*}
  \SProp \eqdef{}& \psetdown{\nat} \\
    \eqdef{}& \setComp{X \in \pset{\nat}}{ \All n, m. n \geq m \Ra n \in X \Ra m \in X } \\
  X \nequiv{n} Y \eqdef{}& \All m \leq n. m \in X \Lra m \in Y \\
  X \nincl{n} Y \eqdef{}& \All m \leq n. m \in X \Ra m \in Y
\end{align*}

68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
\subsection{COFE}

COFEs are \emph{complete OFEs}, which means that we can take limits of arbitrary chains.

\begin{defn}[Chain]
  Given some set $\cofe$ and an indexed family $({\nequiv{n}} \subseteq \cofe \times \cofe)_{n \in \nat}$ of equivalence relations, a \emph{chain} is a function $c : \nat \to \cofe$ such that $\All n, m. n \leq m \Ra c (m) \nequiv{n} c (n)$.
\end{defn}

\begin{defn}
  A \emph{complete ordered family of equivalences} (COFE) is a tuple $(\cofe : \OFEs,  \lim : \chain(\cofe) \to \cofe)$ satisfying
  \begin{align*}
    \All n, c.& \lim(c) \nequiv{n} c(n) \tagH{cofe-compl}
  \end{align*}
\end{defn}

\begin{defn}
  The category $\COFEs$ consists of COFEs as objects, and non-expansive functions as arrows.
\end{defn}

The function space $\ofe \nfn \cofeB$ is a COFE if $\cofeB$ is a COFE (\ie the domain $\ofe$ can actually be just an OFE).
88
$\SProp$ as defined above is complete, \ie it is a COFE.
89 90 91

Completeness is necessary to take fixed-points.

92 93 94
\begin{thm}[Banach's fixed-point]
\label{thm:banach}
Given an inhabited COFE $\ofe$ and a contractive function $f : \ofe \to \ofe$, there exists a unique fixed-point $\fixp_T f$ such that $f(\fixp_T f) = \fixp_T f$.
95
Moreover, this theorem also holds if $f$ is just non-expansive, and $f^k$ is contractive for an arbitrary $k$.
96 97 98 99 100 101 102 103
\end{thm}

\begin{thm}[America and Rutten~\cite{America-Rutten:JCSS89,birkedal:metric-space}]
\label{thm:america_rutten}
Let $1$ be the discrete COFE on the unit type: $1 \eqdef \Delta \{ () \}$.
Given a locally contractive bifunctor $G : \COFEs^{\textrm{op}} \times \COFEs \to \COFEs$, and provided that \(G(1, 1)\) is inhabited,
then there exists a unique\footnote{Uniqueness is not proven in Coq.} COFE $\ofe$ such that $G(\ofe^{\textrm{op}}, \ofe) \cong \ofe$ (\ie the two are isomorphic in $\COFEs$).
\end{thm}
104 105 106

\subsection{RA}

Ralf Jung's avatar
Ralf Jung committed
107 108
\begin{defn}
  A \emph{resource algebra} (RA) is a tuple \\
109
  $(\monoid, \mvalFull :  \monoid \to \mProp, \mcore{{-}}:
110
  \monoid \to \maybe\monoid, (\mtimes) : \monoid \times \monoid \to \monoid)$ satisfying:
Ralf Jung's avatar
Ralf Jung committed
111 112 113
  \begin{align*}
    \All \melt, \meltB, \meltC.& (\melt \mtimes \meltB) \mtimes \meltC = \melt \mtimes (\meltB \mtimes \meltC) \tagH{ra-assoc} \\
    \All \melt, \meltB.& \melt \mtimes \meltB = \meltB \mtimes \melt \tagH{ra-comm} \\
114 115 116
    \All \melt.& \mcore\melt \in \monoid \Ra \mcore\melt \mtimes \melt = \melt \tagH{ra-core-id} \\
    \All \melt.& \mcore\melt \in \monoid \Ra \mcore{\mcore\melt} = \mcore\melt \tagH{ra-core-idem} \\
    \All \melt, \meltB.& \mcore\melt \in \monoid \land \melt \mincl \meltB \Ra \mcore\meltB \in \monoid \land \mcore\melt \mincl \mcore\meltB \tagH{ra-core-mono} \\
117
    \All \melt, \meltB.& \mvalFull(\melt \mtimes \meltB)  \Ra \mvalFull(\melt)  \tagH{ra-valid-op} \\
Ralf Jung's avatar
Ralf Jung committed
118
    \text{where}\qquad %\qquad\\
119
    \maybe\monoid \eqdef{}& \monoid \uplus \set{\mnocore} \qquad\qquad\qquad \melt^? \mtimes \mnocore \eqdef \mnocore \mtimes \melt^? \eqdef \melt^? \\
120
    \melt \mincl \meltB \eqdef{}& \Exists \meltC \in \monoid. \meltB = \melt \mtimes \meltC \tagH{ra-incl}
Ralf Jung's avatar
Ralf Jung committed
121 122
  \end{align*}
\end{defn}
123 124 125
Here, $\mProp$ is the set of (meta-level) propositions.
Think of \texttt{Prop} in Coq or $\mathbb{B}$ in classical mathematics.

126 127
RAs are closely related to \emph{Partial Commutative Monoids} (PCMs), with two key differences:
\begin{enumerate}
128 129
\item The composition operation on RAs is total (as opposed to the partial composition operation of a PCM), but there is a specific subset of \emph{valid} elements that is compatible with the composition operation (\ruleref{ra-valid-op}).
These valid elements are identified by the \emph{validity predicate} $\mvalFull$.
130

131
This take on partiality is necessary when defining the structure of \emph{higher-order} ghost state, \emph{cameras}, in the next subsection.
132 133 134 135 136

\item Instead of a single unit that is an identity to every element, we allow
for an arbitrary number of units, via a function $\mcore{{-}}$ assigning to an element $\melt$ its \emph{(duplicable) core} $\mcore\melt$, as demanded by \ruleref{ra-core-id}.
  We further demand that $\mcore{{-}}$ is idempotent (\ruleref{ra-core-idem}) and monotone (\ruleref{ra-core-mono}) with respect to the \emph{extension order}, defined similarly to that for PCMs (\ruleref{ra-incl}).

137
  Notice that the domain of the core is $\maybe\monoid$, a set that adds a dummy element $\mnocore$ to $\monoid$.
138 139 140 141 142 143 144
%  (This corresponds to the option type.)
  Thus, the core can be \emph{partial}: not all elements need to have a unit.
  We use the metavariable $\maybe\melt$ to indicate elements of  $\maybe\monoid$.
  We also lift the composition $(\mtimes)$ to $\maybe\monoid$.
  Partial cores help us to build interesting composite RAs from smaller primitives.

Notice also that the core of an RA is a strict generalization of the unit that any PCM must provide, since $\mcore{{-}}$ can always be picked as a constant function.
145 146
\end{enumerate}

Ralf Jung's avatar
Ralf Jung committed
147 148 149

\begin{defn}
  It is possible to do a \emph{frame-preserving update} from $\melt \in \monoid$ to $\meltsB \subseteq \monoid$, written $\melt \mupd \meltsB$, if
Ralf Jung's avatar
Ralf Jung committed
150
  \[ \All \maybe{\melt_\f} \in \maybe\monoid. \mvalFull(\melt \mtimes \maybe{\melt_\f}) \Ra \Exists \meltB \in \meltsB. \mvalFull(\meltB \mtimes \maybe{\melt_\f}) \]
Ralf Jung's avatar
Ralf Jung committed
151 152 153

  We further define $\melt \mupd \meltB \eqdef \melt \mupd \set\meltB$.
\end{defn}
154
The proposition $\melt \mupd \meltsB$ says that every element $\maybe{\melt_\f}$ compatible with $\melt$ (we also call such elements \emph{frames}), must also be compatible with some $\meltB \in \meltsB$.
155
Notice that $\maybe{\melt_\f}$ could be $\mnocore$, so the frame-preserving update can also be applied to elements that have \emph{no} frame.
156 157
Intuitively, this means that whatever assumptions the rest of the program is making about the state of $\gname$, if these assumptions are compatible with $\melt$, then updating to $\meltB$ will not invalidate any of these assumptions.
Since Iris ensures that the global ghost state is valid, this means that we can soundly update the ghost state from $\melt$ to a non-deterministically picked $\meltB \in \meltsB$.
Ralf Jung's avatar
Ralf Jung committed
158

159
\subsection{Cameras}
160 161

\begin{defn}
162
  A \emph{camera} is a tuple $(\monoid : \OFEs, \mval : \monoid \nfn \SProp, \mcore{{-}}: \monoid \nfn \maybe\monoid,\\ (\mtimes) : \monoid \times \monoid \nfn \monoid)$ satisfying:
163
  \begin{align*}
164 165 166 167 168 169
    \All \melt, \meltB, \meltC.& (\melt \mtimes \meltB) \mtimes \meltC = \melt \mtimes (\meltB \mtimes \meltC) \tagH{camera-assoc} \\
    \All \melt, \meltB.& \melt \mtimes \meltB = \meltB \mtimes \melt \tagH{camera-comm} \\
    \All \melt.& \mcore\melt \in \monoid \Ra \mcore\melt \mtimes \melt = \melt \tagH{camera-core-id} \\
    \All \melt.& \mcore\melt \in \monoid \Ra \mcore{\mcore\melt} = \mcore\melt \tagH{camera-core-idem} \\
    \All \melt, \meltB.& \mcore\melt \in \monoid \land \melt \mincl \meltB \Ra \mcore\meltB \in \monoid \land \mcore\melt \mincl \mcore\meltB \tagH{camera-core-mono} \\
    \All \melt, \meltB.& \mval(\melt \mtimes \meltB) \subseteq \mval(\melt)  \tagH{camera-valid-op} \\
170
    \All n, \melt, \meltB_1, \meltB_2.& \omit\rlap{$n \in \mval(\melt) \land \melt \nequiv{n} \meltB_1 \mtimes \meltB_2 \Ra {}$} \\
171
    &\Exists \meltC_1, \meltC_2. \melt = \meltC_1 \mtimes \meltC_2 \land \meltC_1 \nequiv{n} \meltB_1 \land \meltC_2 \nequiv{n} \meltB_2 \tagH{camera-extend} \\
172
    \text{where}\qquad\qquad\\
173 174
    \melt \mincl \meltB \eqdef{}& \Exists \meltC. \meltB = \melt \mtimes \meltC \tagH{camera-incl} \\
    \melt \mincl[n] \meltB \eqdef{}& \Exists \meltC. \meltB \nequiv{n} \melt \mtimes \meltC \tagH{camera-inclN}
175 176 177
  \end{align*}
\end{defn}

178 179 180 181 182
This is a natural generalization of RAs over OFEs\footnote{The reader may wonder why on earth we call them ``cameras''.
The reason, which may not be entirely convincing, is that ``camera'' was originally just used as a comfortable pronunciation of ``CMRA'', the name used in earlier Iris papers.
CMRA was originally supposed to be an acronym for ``complete metric resource algebras'' (or something like that), but we were never very satisfied with it and thus ended up never spelling it out.
To make matters worse, the ``complete'' part of CMRA is now downright misleading, for whereas previously the carrier of a CMRA was required to be a COFE (complete OFE), we have relaxed that restriction and permit it to be an (incomplete) OFE.
For these reasons, we have decided to stick with the name ``camera'', for purposes of continuity, but to drop any pretense that it stands for something.}.
Ralf Jung's avatar
Ralf Jung committed
183
All operations have to be non-expansive, and the validity predicate $\mval$ can now also depend on the step-index.
184 185
We define the plain $\mvalFull$ as the ``limit'' of the step-indexed approximation:
\[ \mvalFull(\melt) \eqdef \All n. n \in \mval(\melt) \]
186

187
\paragraph{The extension axiom (\ruleref{camera-extend}).}
188 189 190
Notice that the existential quantification in this axiom is \emph{constructive}, \ie it is a sigma type in Coq.
The purpose of this axiom is to compute $\melt_1$, $\melt_2$ completing the following square:

Ralf Jung's avatar
Ralf Jung committed
191
% RJ FIXME: Needs some magic to fix the baseline of the $\nequiv{n}$, or so
192 193 194 195 196 197 198 199 200 201 202 203 204 205
\begin{center}
\begin{tikzpicture}[every edge/.style={draw=none}]
  \node (a) at (0, 0) {$\melt$};
  \node (b) at (1.7, 0) {$\meltB$};
  \node (b12) at (1.7, -1) {$\meltB_1 \mtimes \meltB_2$};
  \node (a12) at (0, -1) {$\melt_1 \mtimes \melt_2$};

  \path (a) edge node {$\nequiv{n}$} (b);
  \path (a12) edge node {$\nequiv{n}$} (b12);
  \path (a) edge node [rotate=90] {$=$} (a12);
  \path (b) edge node [rotate=90] {$=$} (b12);
\end{tikzpicture}\end{center}
where the $n$-equivalence at the bottom is meant to apply to the pairs of elements, \ie we demand $\melt_1 \nequiv{n} \meltB_1$ and $\melt_2 \nequiv{n} \meltB_2$.
In other words, extension carries the decomposition of $\meltB$ into $\meltB_1$ and $\meltB_2$ over the $n$-equivalence of $\melt$ and $\meltB$, and yields a corresponding decomposition of $\melt$ into $\melt_1$ and $\melt_2$.
206
This operation is needed to prove that $\later$ commutes with separating conjunction:
207
\begin{mathpar}
208
  \axiom{\later (\prop * \propB) \Lra \later\prop * \later\propB}
209 210
\end{mathpar}

211
\begin{defn}
212
  An element $\munit$ of a camera $\monoid$ is called the \emph{unit} of $\monoid$ if it satisfies the following conditions:
213
  \begin{enumerate}[itemsep=0pt]
214
  \item $\munit$ is valid: \\ $\All n. n \in \mval(\munit)$
Ralf Jung's avatar
Ralf Jung committed
215
  \item $\munit$ is a left-identity of the operation: \\
216
    $\All \melt \in M. \munit \mtimes \melt = \melt$
217
  \item $\munit$ is its own core: \\ $\mcore\munit = \munit$
218 219 220
  \end{enumerate}
\end{defn}

221
\begin{lem}\label{lem:camera-unit-total-core}
222 223 224
  If $\monoid$ has a unit $\munit$, then the core $\mcore{{-}}$ is total, \ie $\All\melt. \mcore\melt \in \monoid$.
\end{lem}

225 226
\begin{defn}
  It is possible to do a \emph{frame-preserving update} from $\melt \in \monoid$ to $\meltsB \subseteq \monoid$, written $\melt \mupd \meltsB$, if
Ralf Jung's avatar
Ralf Jung committed
227
  \[ \All n, \maybe{\melt_\f}. n \in \mval(\melt \mtimes \maybe{\melt_\f}) \Ra \Exists \meltB \in \meltsB. n \in\mval(\meltB \mtimes \maybe{\melt_\f}) \]
228 229 230 231 232

  We further define $\melt \mupd \meltB \eqdef \melt \mupd \set\meltB$.
\end{defn}
Note that for RAs, this and the RA-based definition of a frame-preserving update coincide.

Ralf Jung's avatar
Ralf Jung committed
233
\begin{defn}
234
  A camera $\monoid$ is \emph{discrete} if it satisfies the following conditions:
Ralf Jung's avatar
Ralf Jung committed
235 236
  \begin{enumerate}[itemsep=0pt]
  \item $\monoid$ is a discrete COFE
Ralf Jung's avatar
Ralf Jung committed
237
  \item $\mval$ ignores the step-index: \\
238
    $\All \melt \in \monoid. 0 \in \mval(\melt) \Ra \All n. n \in \mval(\melt)$
Ralf Jung's avatar
Ralf Jung committed
239 240
  \end{enumerate}
\end{defn}
241 242
Note that every RA is a discrete camera, by picking the discrete COFE for the equivalence relation.
Furthermore, discrete cameras can be turned into RAs by ignoring their COFE structure, as well as the step-index of $\mval$.
243

244 245
\begin{defn}[Camera homomorphism]
  A function $f : \monoid_1 \to \monoid_2$ between two cameras is \emph{a camera homomorphism} if it satisfies the following conditions:
246
  \begin{enumerate}[itemsep=0pt]
247
  \item $f$ is non-expansive
248 249 250 251
  \item $f$ commutes with composition:\\
    $\All \melt_1 \in \monoid_1, \melt_2 \in \monoid_1. f(\melt_1) \mtimes f(\melt_2) = f(\melt_1 \mtimes \melt_2)$
  \item $f$ commutes with the core:\\
    $\All \melt \in \monoid_1. \mcore{f(\melt)} = f(\mcore{\melt})$
252
  \item $f$ preserves validity: \\
253
    $\All n, \melt \in \monoid_1. n \in \mval(\melt) \Ra n \in \mval(f(\melt))$
254 255 256 257
  \end{enumerate}
\end{defn}

\begin{defn}
Ralf Jung's avatar
Ralf Jung committed
258
  The category $\CMRAs$ consists of cameras as objects, and camera homomorphisms as arrows.
259
\end{defn}
260
Note that every object/arrow in $\CMRAs$ is also an object/arrow of $\OFEs$.
Ralf Jung's avatar
Ralf Jung committed
261
The notion of a locally non-expansive (or contractive) bifunctor naturally generalizes to bifunctors between these categories.
Ralf Jung's avatar
Ralf Jung committed
262
%TODO: Discuss how we probably have a commuting square of functors between Set, RA, CMRA, COFE.
263

264 265 266 267
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "iris"
%%% End: