Context Navigation

-                      r58732d1
+                      r7db48364
 With more specificity, the cost is a lexicographically-ordered tuple, where each element corresponds to a particular kind of conversion.
 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}.
+Degree of safe conversion is calculated as path weight in a directed graph of safe conversions between types; Bilson's version and the current version of this graph are in Figures~\ref{bilson-conv-fig} and~\ref{extended-conv-fig}, respectively.
 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:
 …
 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 two declarations above).
 These costs are summed over the parameters 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.
+\begin{figure}
+        \centering
+        \begin{subfigure}[h]{3in}
+                \includegraphics{figures/bilson-conv-graph}
+                \caption{Bilson} \label{bilson-conv-fig}
+        \end{subfigure}~\begin{subfigure}[h]{3in}
+                \includegraphics{figures/extended-conv-graph}
+                \caption{Extended} \label{extended-conv-fig}
+        \end{subfigure}
+        % \includegraphics{figures/safe-conv-graph}
+        \caption[Safe conversion graphs.]{Safe conversion graphs. 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} (highlighted in red in \ref{bilson-conv-fig}) is deliberately omitted in \ref{extended-conv-fig}, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}
+        \label{safe-conv-fig}
+\end{figure}
 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.
 …
 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}.
+Bilson's \CFACC{} uses conversion costs based off Figure~\ref{bilson-conv-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 $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).
-\begin{figure}
-        \centering
-        \includegraphics{figures/safe-conv-graph}
-        \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}
 With these modifications, the current \CFA{} cost tuple is as follows:

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 7db48364

Legend:

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

Download in other formats: