Changeset 2240ec4
 Timestamp:
 Jan 18, 2019, 5:22:21 PM (5 years ago)
 Branches:
 ADT, aaronthesis, armeh, astexperimental, cleanupdtors, enum, forallpointerdecay, jacob/cs343translation, jenkinssandbox, master, newast, newastuniqueexpr, pthreademulation, qualifiedEnum
 Children:
 9a38436c
 Parents:
 28c120b
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/theses/aaron_moss_PhD/phd/resolutionheuristics.tex
r28c120b r2240ec4 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 minimalcost interpretation for an expression, reporting an error if no such interpretation exists. 8 8 9 \section{ Conversion Cost}9 \section{Expression Resolution} 10 10 11 \ TODO{Open with discussion of C's ``usual arithmetic conversions''}11 \subsection{Conversion Cost} 12 12 13 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. 14 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. 13 15 Loosely defined, the conversion cost counts the implicit conversions utilized by an interpretation. 14 16 With more specificity, the cost is a lexicographicallyordered 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 threetuple, $(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.17 In Bilson's \CFA{} design, conversion cost is a threetuple, $(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. 16 18 The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters: 17 19 … … 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. 37 39 38 \TODO{Discuss $var$ element, bring in Ditchfield 4.4.4 (p.89), add discussion of type specialization} 40 I have also incorporated an unimplemented aspect of Ditchfield's earlier cost model. 41 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: 39 42 40 % Discuss changes to cost model, as promised in Ch. 2 43 \begin{cfa} 44 forall(otype T, otype U) void f(T, U); $\C{// polymorphic}$ 45 forall(otype T) void f(T, T); $\C{// less polymorphic}$ 46 forall(otype T) void f(T, int); $\C{// even less polymorphic}$ 47 forall(otype T) void f(T*, int); $\C{// least polymorphic}$ 48 \end{cfa} 49 50 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. 51 In the example above, the first !f! has $var = 2$, while the remainder have $var = 1$. 52 My new \CFA{} cost model also accounts for a nuance unhandled by Ditchfield or Bilson, in that it makes the more specific fourth function above cheaper than the more generic third function. 53 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. 54 55 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. 56 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. 57 This process is recursive, such that !T**! produces a 2 specialization cost, as opposed to the 1 cost for $T*$. 58 This works similarly for generic types, \eg{} !box(T)! also has specialization cost 1; for multiargument generic types, the leastspecialized polymorphic parameter sets the specialization cost, \eg{} the specialization cost of !pair(T, S*)! is 1 (from !T!) rather than 2 (from !S!). 59 Since the user programmer provides parameters, but cannot provide guidance on return type, specialization cost is not counted for the return type list. 60 The 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 68 Having defined the cost model ... 69 70 % mention cast expression as "eager" 41 71 42 72 % Mention relevance of work to C++20 concepts
Note: See TracChangeset
for help on using the changeset viewer.