Changeset d58a39a0

Oct 5, 2016, 2:29:19 PM (5 years ago)
Peter A. Buhr <pabuhr@…>
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
7756647, ab84e8a
faddbd8 (diff), a7976d79 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Merge branch 'master' of plg2:software/cfa/cfa-cc

4 added
1 edited


  • doc/aaron_comp_II/comp_II.tex

    rfaddbd8 rd58a39a0  
    401401\section{Expression Resolution}
    402403The expression resolution problem is determining an optimal match between some combination of argument interpretations and the parameter list of some overloaded instance of a function; the argument interpretations are produced by recursive invocations of expression resolution, where the base case is zero-argument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions).
    403404Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $\bigO{p^k}$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $\bigO{i}$ valid interpretations for each subexpression, there will be $\bigO{i}$ candidate functions and $\bigO{i^p}$ possible argument combinations for each expression, so for a single recursive call expression resolution takes $\bigO{i^{p+1} \cdot p^k}$ time if it must compare all combinations, or $\bigO{i(p+1) \cdot p^k}$ time if argument-parameter matches can be chosen independently of each other.
    409410The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type-system completeness.
     412\subsection{Expression Costs}
     413The expression resolution problem involves minimization of a cost function; loosely defined, this cost function is the number of implicit conversions in the top-level expression interpretation.
     414With more specificity, the \emph{cost} of a particular expression interpretation is a lexicographically-ordered tuple, where each element of the tuple corresponds to a particular kind of conversion.
     415In \CFA today, cost is a three-tuple including the number of unsafe conversions, the number of polymorphic parameter bindings, and the number of safe conversions.
     416These counts include conversions used in subexpression interpretations, as well as those necessary to satisfy the type assertions of any polymorphic functions included in the interpretation.
     419void f(char, long);  // $f_1$ - cost (2, 0, 1)
     420forall(otype T) void f(T, long); // $f_2$ - cost (0, 1, 1)
     421void f(long, long); // $f_{3a}$ - cost (0, 0, 2)
     422void f(int, float); // $f_{3b}$ - cost (0, 0, 2)
     423void f(int, long);  // $f_4$ - cost (0, 0, 1)
     425f(7, 11);
     428In the example above, the expression resolves to $f_4$.
     429$f_1$ has an unsafe conversion (from ©int© to ©char©), and is thus the highest cost, followed by $f_2$, which has a polymorphic binding (from ©int© to ©T©).
     430Neither $f_{3a}$, $f_{3b}$, or $f_4$ match exactly with the type of the call expression (©void (*)(int, int)©), each involving safe conversions, but in this case $f_4$ is cheaper than $f_{3a}$, because it converts fewer arguments, and is also cheaper than $f_{3b}$, because ©long© is a closer match for ©int© than ©float© is.
     431If the declaration of $f_4$ was missing, the expression would be ambiguous, because the two single-step ©int©-to-©long© conversions in $f_{3a}$ cost the same as the one double-step ©int©-to-©float© conversion in $f_{3b}$.
     433In the course of this project I may modify the cost tuple,\footnote{I have considered adding an element to distinguish between cast expressions used as conversions and those used as type ascriptions, and another element to differentiate interpretations based on closer qualifier matches. The existing costing of polymorphic functions could also be made more precice than a bare count of parameter bindings.} but the essential nature of the cost calculation should remain the same.
    411436The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests three primary areas of investigation to accomplish that end.
    412437The first area of investigation is efficient argument-parameter matching; Bilson~\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.
Note: See TracChangeset for help on using the changeset viewer.