Changeset 2240ec4 for doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex

Timestamp:

Jan 18, 2019, 5:22:21 PM (5 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

9a38436c

Parents:

28c120b

Message:

Thesis: further elaboration of cost model

File:

• doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (modified) (2 diffs)

doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex

@@ -7 +7 @@
 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 +38 @@
 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