Changeset 6295081


Ignore:
Timestamp:
Oct 4, 2016, 11:24:57 AM (7 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
19b5d6b
Parents:
db46512
Message:

Add cost section to Comp II

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    rdb46512 r6295081  
    400400
    401401\section{Expression Resolution}
     402\subsection{Analysis}
    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.
    410411
     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.
     417
     418\begin{lstlisting}
     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)
     424
     425f(7, 11);
     426\end{lstlisting}
     427
     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}$.
     432
     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.
     434
     435\subsection{Objectives}
    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.