Changeset 7c6eb64 for doc/theses/aaron_moss_PhD

Timestamp:

Feb 14, 2019, 11:40:17 PM (6 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:

4c41b17

Parents:

96bf5781

Message:

thesis: incorporate feedback on cost model section

Location:

doc/theses/aaron_moss_PhD/phd

Files:

• experiments.tex (modified) (1 diff)
• figures/safe-conv-graph.eps (modified) (previous)
• figures/safe-conv-graph.odg (modified) (previous)
• resolution-heuristics.tex (modified) (5 diffs)

doc/theses/aaron_moss_PhD/phd/experiments.tex

@@ -156 +156 @@
 \section{Instance Difficulty}
 
+% TODO: look at overloads
+% TODO: histogram of hard cases
+
 \section{\CFA{} Results}
 

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

@@ -28 +28 @@
 \begin{itemize}
 \item If either operand is a floating-point type, the common type is the size of the largest floating-point type. If either operand is !_Complex!, the common type is also !_Complex!.
-\item If both operands are of integral type, the common type has the same size\footnote{Technically, the C standard defines a notion of \emph{rank}, a distinct value for each \lstinline{signed} and \lstinline{unsigned} pair; integral types of the same size thus may have distinct ranks. For instance, if \lstinline{int} and \lstinline{long} are the same size, \lstinline{long} will have greater rank. The standard-defined types are declared to have greater rank than any types of the same size added as compiler extensions.} as the larger type.
+\item If both operands are of integral type, the common type has the same size\footnote{Technically, the C standard defines a notion of \emph{rank} in \cite[\S{}6.3.1.1]{C11}, a distinct value for each \lstinline{signed} and \lstinline{unsigned} pair; integral types of the same size thus may have distinct ranks. For instance, if \lstinline{int} and \lstinline{long} are the same size, \lstinline{long} will have greater rank. The standard-defined types are declared to have greater rank than any types of the same size added as compiler extensions.} as the larger type.
 \item If the operands have opposite signedness, the common type is !signed! if the !signed! operand is strictly larger, or !unsigned! otherwise. If the operands have the same signedness, the common type shares it.
 \end{itemize}
 
-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. 
+Beginning with the work of Bilson\cite{Bilson03}, \CFA{} defines 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 Bilson's \CFA{} design, conversion cost is a 3-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. 
-Degree of safe conversion is calculated as path weight in a weighted directed graph of safe conversions between types; the current version of this graph is in Figure~\ref{safe-conv-graph-fig}. 
-The safe conversion graph designed such that the common type $c$ of two types $u$ and $v$ is compatible with the C standard definitions from \cite[\S{}6.3.1.8]{C11} and can be calculated as the unique type minimizing the sum of the path weights of $\overrightarrow{uc}$ and $\overrightarrow{vc}$.
+In Bilson's design, conversion cost is a 3-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. 
+Degree of safe conversion is calculated as path weight in a directed graph of safe conversions between types; both Bilson's version and the current version of this graph are in Figure~\ref{safe-conv-graph-fig}. 
+The safe conversion graph is designed such that the common type $c$ of two types $u$ and $v$ is compatible with the C standard definitions from \cite[\S{}6.3.1.8]{C11} and can be calculated as the unique type minimizing the sum of the path weights of $\overrightarrow{uc}$ and $\overrightarrow{vc}$.
 The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters:
 
 \begin{cfa}
 void f(char, long); $\C{// (1,0,1)}$
+void f(short, long); $\C{// (1,0,1)}$
 forall(otype T) void f(T, long); $\C{// (0,1,1)}$
 void f(long, long); $\C{// (0,0,2)}$
@@ -48 +49 @@
 \end{cfa}
 
-Note that safe and unsafe conversions are handled differently; \CFA{} counts distance of safe conversions (\eg{} !int! to !long! is cheaper than !int! to !unsigned long!), while only counting the number of unsafe conversions (\eg{} !int! to !char! and !int! to !short! both have unsafe cost 1).
+Note that safe and unsafe conversions are handled differently; \CFA{} counts distance of safe conversions (\eg{} !int! to !long! is cheaper than !int! to !unsigned long!), while only counting the number of unsafe conversions (\eg{} !int! to !char! and !int! to !short! both have unsafe cost 1, as in the first fwo declarations above). 
+These costs are summed over the paramters in a call; in the example above, the cost of the two !int! to !long! conversions for the fourth declaration sum equal to the one !int! to !unsigned long! conversion in the fifth.
 
 As part of adding reference types to \CFA{} (see Section~\ref{type-features-sec}), Schluntz added a new $reference$ element to the cost tuple, which counts the number of implicit reference-to-rvalue conversions performed so that candidate interpretations can be distinguished by how closely they match the nesting of reference types; since references are meant to act almost indistinguishably from lvalues, this $reference$ element is the least significant in the lexicographic comparison of cost tuples.
 
 I have also refined the \CFA{} cost model as part of this thesis work. 
-Bilson's \CFA{} cost model includes the cost of polymorphic type bindings from a function's type assertions in the $poly$ element of the cost tuple; this has the effect of making more-constrained functions more expensive than less-constrained functions. 
+Bilson's \CFA{} cost model includes the cost of polymorphic type bindings from a function's type assertions in the $poly$ element of the cost tuple; this has the effect of making more-constrained functions more expensive than less-constrained functions, as in the following example:
+
+\begin{cfa}
+forall(dtype T | { T& ++?(T&); }) T& advance(T&, int);
+forall(dtype T | { T& ++?(T&); T& ?+=?(T&, int)}) T& advance(T&, int);
+\end{cfa}
+
+In resolving a call to !advance!, the binding to the !T&! parameter in the assertions is added to the $poly$ cost in Bilson's model.
 However, type assertions actually make a function \emph{less} polymorphic, and as such functions with more type assertions should be preferred in type resolution. 
-As an example, some iterator-based algorithms can work on a forward iterator that only provides an increment operator, but are more efficient on a random-access iterator that can be incremented by an arbitrary number of steps in a single operation. 
-The random-access iterator has more type constraints, but should be chosen whenever those constraints can be satisfied. 
-As such, I have added a $specialization$ element to the \CFA{} cost tuple, the values of which are always negative. 
-Each type assertion subtracts 1 from $specialization$, so that more-constrained functions will cost less and thus be chosen over less-constrained functions, all else being equal.
+In the example above, the more-constrained second function can be implemented more efficiently, and as such should be chosen whenever its added constraint can be satisfied.
+As such, a $specialization$ element is now included in the \CFA{} cost tuple, the values of which are always negative. 
+Each type assertion subtracts 1 from $specialization$, so that more-constrained functions cost less, and thus are chosen over less-constrained functions, all else being equal.
 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 a strict superset of assertions,  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.
 
-I have also incorporated an unimplemented aspect of Ditchfield's earlier cost model.
+I also incorporated an unimplemented aspect of Ditchfield's earlier cost model.
 In the example below, adapted from \cite[p.89]{Ditchfield92}, 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:
 
@@ -71 +79 @@
 \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. 
+The new cost model accounts 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 new 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. 
+In the modified model, each level of constraint on a polymorphic type in the parameter list results in a decrement of the $specialization$ cost element, which is shared with the count of assertions due to their common nature as constraints on polymorphic type bindings. 
+Thus, all else equal, if both a binding to !T! and a binding to !T*! are available, the model chooses the more specific !T*! binding with $specialization = -1$.
+This process is recursive, such that !T**! has $specialization = -2$. 
+This calculation 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.
+Specialization cost is not counted on the return type list; since $specialization$ is a property of the function declaration, a lower specialization cost prioritizes one declaration over another. 
+User programmers can choose between functions with varying parameter lists by adjusting the arguments, but the same is not true of varying return types, so the return types are omitted from the $specialization$ element.
 Since both $vars$ and $specialization$ are properties of the declaration rather than any particular interpretation, they are prioritized less than the interpretation-specific conversion costs from Bilson's original 3-tuple. 
 
-A final refinement I have made to the \CFA{} cost model is with regard to choosing between arithmetic conversions. 
-The C standard states that the common type of !int! and !unsigned int! is !unsigned int! and that the common type of !int! and !long! is !long!, but does not provide guidance for making a choice between those two conversions. 
-Bilson's \CFACC{} used conversion costs based off a graph similar to that in Figure~\ref{safe-conv-graph-fig}, but with arcs selectively removed to disambiguate the costs of such conversions. 
-However, the arc removal in Bilson's design resulted in inconsistent and somewhat surprising costs, with conversion to the next-larger same-sign type generally (but not always) double the cost of conversion to the !unsigned! type of the same size.
-In my redesign, for consistency with the approach of the usual arithmetic conversions,which select a common type primarily based on size, but secondarily on sign, the costs of arcs in the new graph are defined to be $1$ to go to a larger size, but $1 + \varepsilon$ to change the sign. 
+A final refinement I have made to the \CFA{} cost model is with regard to choosing among arithmetic conversions. 
+The C standard \cite[\S{}6.3.1.8]{C11} states that the common type of !int! and !unsigned int! is !unsigned int! and that the common type of !int! and !long! is !long!, but does not provide guidance for making a choice among conversions. 
+Bilson's \CFACC{} uses conversion costs based off the left graph in Figure~\ref{safe-conv-graph-fig}. 
+However, Bilson's design results in inconsistent and somewhat surprising costs, with conversion to the next-larger same-sign type generally (but not always) double the cost of conversion to the !unsigned! type of the same size.
+In the redesign, for consistency with the approach of the usual arithmetic conversions, which select a common type primarily based on size, but secondarily on sign, arcs in the new graph are annotated with whether they represent a sign change, and such sign changes are summed in a new $sign$ cost element that lexicographically succeeds than $safe$. 
 This means that sign conversions are approximately the same cost as widening conversions, but slightly more expensive (as opposed to less expensive in Bilson's graph). 
-The $\varepsilon$ portion of the arc cost is implemented by adding a new $sign$ cost lexicographically after $safe$ which counts sign conversions.
 
 \begin{figure}
         \centering
         \includegraphics{figures/safe-conv-graph}
-        \caption[Safe conversion graph.]{Safe conversion graph; plain arcs have cost $1$ while dashed sign-conversion arcs have cost $1+ \varepsilon$. The arc from \lstinline{unsigned long} to \lstinline{long long} is deliberately omitted, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}
+        \caption[Safe conversion graphs.]{Safe conversion graphs; Bilson's on the left, the extended graph on the right. In both graphs, plain arcs have cost $safe = 1, sign = 0$ while dashed sign-conversion arcs have cost $safe = 1, sign = 1$. As per \cite[\S{}6.3.1.8]{C11}, types promote to types of the same signedness with greater rank, from \lstinline{signed} to \lstinline{unsigned} with the same rank, and from \lstinline{unsigned} to \lstinline{signed} with greater size. The arc from \lstinline{unsigned long} to \lstinline{long long} is deliberately omitted in the modified graph, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}
         \label{safe-conv-graph-fig}
 \end{figure}
@@ -105 +113 @@
 \end{equation*}
 
-\subsection{Expression Cost}
+\subsection{Expression Cost} \label{expr-cost-sec}
 
 The mapping from \CFA{} expressions to cost tuples is described by Bilson in \cite{Bilson03}, and remains effectively unchanged modulo the refinements to the cost tuple described above. 
@@ -364 +372 @@
 
 % Mention relevance of work to C++20 concepts
+
+% Mention more compact representations of the (growing) cost tuple