# Changeset 2240ec4

Ignore:
Timestamp:
Jan 18, 2019, 5:22:21 PM (3 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
9a38436
Parents:
28c120b
Message:

Thesis: further elaboration of cost model

File:
1 edited

### Legend:

Unmodified
 r28c120b 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: 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{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