Index: doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex
===================================================================
--- doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 266f36db4f5b143e0d0daccf69e320d688c5c0d1)
+++ doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 2240ec4c1cdd8417e108c5083af7be244434f409)
@@ -7,11 +7,13 @@
To choose between feasible interpretations, \CFA{} defines a \emph{conversion cost} to rank interpretations; the expression resolution problem is thus to find the unique minimal-cost interpretation for an expression, reporting an error if no such interpretation exists.
-\section{Conversion Cost}
+\section{Expression Resolution}
-\TODO{Open with discussion of C's ``usual arithmetic conversions''}
+\subsection{Conversion Cost}
+C does not have an explicit cost model for implicit conversions, but the ``usual arithmetic conversions''\cit{} used to decide which arithmetic operators to use define one implicitly.
+Beginning with the work of Bilson\cite{Bilson03}, \CFA{} has defined a \emph{conversion cost} for each function call in a way that generalizes C's conversion rules.
Loosely defined, the conversion cost counts the implicit conversions utilized by an interpretation.
With more specificity, the cost is a lexicographically-ordered tuple, where each element corresponds to a particular kind of conversion.
-In the original \CFA{} design by Bilson~\cite{Bilson03}, conversion cost is a three-tuple, $(unsafe, poly, safe)$, where $unsafe$ is the count of unsafe (narrowing) conversions, $poly$ is the count of polymorphic type bindings, and $safe$ is the sum of the degree of safe (widening) conversions.
+In Bilson's \CFA{} design, conversion cost is a three-tuple, $(unsafe, poly, safe)$, where $unsafe$ is the count of unsafe (narrowing) conversions, $poly$ is the count of polymorphic type bindings, and $safe$ is the sum of the degree of safe (widening) conversions.
The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters:
@@ -36,7 +38,35 @@
A more sophisticated design would define a partial order over sets of type assertions by set inclusion (\ie{} one function would only cost less than another if it had all of the same assertions, plus more, rather than just more total assertions), but I did not judge the added complexity of computing and testing this order to be worth the gain in specificity.
-\TODO{Discuss $var$ element, bring in Ditchfield 4.4.4 (p.89), add discussion of type specialization}
+I have also incorporated an unimplemented aspect of Ditchfield's earlier cost model.
+In the example below, adapted from \cite[89]{Ditchfield}, Bilson's cost model only distinguished between the first two cases by accounting extra cost for the extra set of !otype! parameters, which, as discussed above, is not a desirable solution:
-% Discuss changes to cost model, as promised in Ch. 2
+\begin{cfa}
+forall(otype T, otype U) void f(T, U); $\C{// polymorphic}$
+forall(otype T) void f(T, T); $\C{// less polymorphic}$
+forall(otype T) void f(T, int); $\C{// even less polymorphic}$
+forall(otype T) void f(T*, int); $\C{// least polymorphic}$
+\end{cfa}
+
+I account for the fact that functions with more polymorphic variables are less constrained by introducing a $var$ cost element that counts the number of type variables on a candidate function.
+In the example above, the first !f! has $var = 2$, while the remainder have $var = 1$.
+My new \CFA{} cost model also accounts for a nuance un-handled by Ditchfield or Bilson, in that it makes the more specific fourth function above cheaper than the more generic third function.
+The fourth function is presumably somewhat optimized for handling pointers, but the prior \CFA{} cost model could not account for the more specific binding, as it simply counted the number of polymorphic unifications.
+
+In my modified model, each level of constraint on a polymorphic type in the parameter list results in a decrement of the $specialization$ cost element.
+Thus, all else equal, if both a binding to !T! and a binding to !T*! are available, \CFA{} will pick the more specific !T*! binding.
+This process is recursive, such that !T**! produces a -2 specialization cost, as opposed to the -1 cost for $T*$.
+This works similarly for generic types, \eg{} !box(T)! also has specialization cost -1; for multi-argument generic types, the least-specialized polymorphic parameter sets the specialization cost, \eg{} the specialization cost of !pair(T, S*)! is -1 (from !T!) rather than -2 (from !S!).
+Since the user programmer provides parameters, but cannot provide guidance on return type, specialization cost is not counted for the return type list.
+The final \CFA{} cost tuple is thus as follows:
+
+\begin{equation*}
+ (unsafe, poly, safe, vars, specialization, reference)
+\end{equation*}
+
+\subsection{Expression Cost}
+
+Having defined the cost model ...
+
+% mention cast expression as "eager"
% Mention relevance of work to C++20 concepts