Changeset 2240ec4


Ignore:
Timestamp:
Jan 18, 2019, 5:22:21 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
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
Added
Removed
  • doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex

    r28c120b r2240ec4  
    77To 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.
    88
    9 \section{Conversion Cost}
     9\section{Expression Resolution}
    1010
    11 \TODO{Open with discussion of C's ``usual arithmetic conversions''}
     11\subsection{Conversion Cost}
    1212
     13C 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.
     14Beginning 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.
    1315Loosely defined, the conversion cost counts the implicit conversions utilized by an interpretation.
    1416With more specificity, the cost is a lexicographically-ordered tuple, where each element corresponds to a particular kind of conversion.
    15 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.
     17In 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.
    1618The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters:
    1719
     
    3638A 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.
    3739
    38 \TODO{Discuss $var$ element, bring in Ditchfield 4.4.4 (p.89), add discussion of type specialization}
     40I have also incorporated an unimplemented aspect of Ditchfield's earlier cost model.
     41In 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:
    3942
    40 % Discuss changes to cost model, as promised in Ch. 2
     43\begin{cfa}
     44forall(otype T, otype U) void f(T, U);  $\C{// polymorphic}$
     45forall(otype T) void f(T, T);  $\C{// less polymorphic}$
     46forall(otype T) void f(T, int);  $\C{// even less polymorphic}$
     47forall(otype T) void f(T*, int); $\C{// least polymorphic}$
     48\end{cfa}
     49
     50I 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.
     51In the example above, the first !f! has $var = 2$, while the remainder have $var = 1$.
     52My 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.
     53The 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.
     54
     55In my modified model, each level of constraint on a polymorphic type in the parameter list results in a decrement of the $specialization$ cost element.
     56Thus, all else equal, if both a binding to !T! and a binding to !T*! are available, \CFA{} will pick the more specific !T*! binding.
     57This process is recursive, such that !T**! produces a -2 specialization cost, as opposed to the -1 cost for $T*$.
     58This 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!).
     59Since the user programmer provides parameters, but cannot provide guidance on return type, specialization cost is not counted for the return type list.
     60The final \CFA{} cost tuple is thus as follows:
     61
     62\begin{equation*}
     63        (unsafe, poly, safe, vars, specialization, reference)
     64\end{equation*}
     65
     66\subsection{Expression Cost}
     67
     68Having defined the cost model ...
     69
     70% mention cast expression as "eager"
    4171
    4272% Mention relevance of work to C++20 concepts
Note: See TracChangeset for help on using the changeset viewer.