Changeset 47ed726 for doc/theses/aaron_moss_PhD/phd/type-environment.tex
- Timestamp:
- Dec 8, 2018, 4:06:25 PM (6 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum
- Children:
- 29207bf
- Parents:
- df43791
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/aaron_moss_PhD/phd/type-environment.tex
rdf43791 r47ed726 49 49 For instance, unifying !R*! with !S*! for type variables !R! and !S! will result in a call to $unify(T, find($!R!$), find($!S!$))$, while unifying !R*! with !int*! will result in a call to $unifyBound$ on !int! and the bound type of the class containing !R!. 50 50 As such, a call to $unify(T, T_i, T_j)$ may touch every type class in $T$, not just $T_i$ and $T_j$, collapsing the entirety of $T$ into a single type class in extreme cases. 51 For more information on \CFA{} unification, see \cite{Bilson03}. 51 52 The inverse of $unify$ is $split(T, T_i)$, which produces a new environment $T'$ which is the same as $T$ except that $T_i$ has been replaced by two classes corresponding to the arguments to the previous call to $unify$ on $T_i$. 52 53 If there has been no call to $unify$ on $T_i$ (\ie{} $T_i$ is a single-element class) $T_i$ is absent in $T'$. … … 58 59 The invalid state of $T$ on failure is not important, given that a combination failure will result in the resolution algorithm backtracking to a different environment. 59 60 $combine$ proceeds by calls to $insert$, $add$, and $unify$ as needed, and can be roughly thought of as calling $unify$ on every pair of classes in $T$ that have variables $v'_{i,j}$ and $v'_{i,k}$ in the same class $T'_i$ in $T'$. 60 Like in$unify$, $combine$ can always find a mutually-consistent partition of type variables into classes (in the extreme case, all type variables from $T$ and $T'$ in a single type class), but may fail due to inconsistent bounds on merged type classes.61 Like $unify$, $combine$ can always find a mutually-consistent partition of type variables into classes (in the extreme case, all type variables from $T$ and $T'$ in a single type class), but may fail due to inconsistent bounds on merged type classes. 61 62 62 63 Finally, the backtracking access patterns of the compiler can be exploited to reduce memory usage or runtime through use of an appropriately designed data structure. … … 183 184 In this section I present asymptotic analyses of the various approaches to a type environment data structure discussed in the previous section. 184 185 186 \begin{table} 187 \caption[Type environment operation bounds]{Worst-case analysis of type environment operations. $n$ is the number of type classes, $m$ the maximum size of a type class, and $p$ the edit distance between two environments or a single environment and the empty environment; $u(n)$ captures the recursive cost of class unification.} 188 \label{env-bounds-table} 189 \centering 190 \begin{tabular}{rllll} 191 \hline 192 & \textbf{Na\"{\i}ve} & \textbf{Incremental} & \textbf{Union-Find} & \textbf{U-F with Classes} \\ 193 \hline 194 $find$ & $O(n)$ & $O(p)$ & $O(\alpha(m))$ & $O(\log m)$ \\ 195 $report$ & $O(m)$ & $O(m)$ & $O(n \log m)$ & $O(m)$ \\ 196 $bound$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 197 $insert$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 198 $add$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 199 $bind$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 200 $unify$ & $O(m + u(n))$ & $O(m + u(n))$ & $O(\log m + u(n))$ & $O(\log m + u(n))$ \\ 201 $split$ & --- & --- & --- & $O(\log m)$ \\ 202 $combine$ & $O(nm \cdot u(n))$ & $O(pm \cdot u(n))$ & $O(n \log m \cdot u(n))$ & $O(p \log m \cdot u(n))$ \\ 203 $save$ & $O(nm)$ & $O(1)$ & $O(nm)$ & $O(1)$ \\ 204 $backtrack$ & $O(nm)$ & $O(pm)$ & $O(nm)$ & $O(p)$ \\ 205 \hline 206 \end{tabular} 207 \end{table} 208 185 209 % Future work: design multi-threaded version of C&F persistent map --- core idea is some sort of thread-boundary edit node
Note: See TracChangeset
for help on using the changeset viewer.