Changeset a7976d79
 Timestamp:
 Oct 5, 2016, 11:47:52 AM (8 years ago)
 Branches:
 ADT, aaronthesis, armeh, astexperimental, cleanupdtors, deferred_resn, demangler, enum, forallpointerdecay, jacob/cs343translation, jenkinssandbox, master, newast, newastuniqueexpr, newenv, no_list, persistentindexer, pthreademulation, qualifiedEnum, resolvnew, with_gc
 Children:
 d58a39a0, d95f565
 Parents:
 c69adb7 (diff), 19b5d6b (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.  File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/aaron_comp_II/comp_II.tex
rc69adb7 ra7976d79 400 400 401 401 \section{Expression Resolution} 402 \subsection{Analysis} 402 403 The 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 zeroargument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions). 403 404 Assuming 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 argumentparameter matches can be chosen independently of each other. … … 409 410 The 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 typesystem completeness. 410 411 412 \subsection{Expression Costs} 413 The expression resolution problem involves minimization of a cost function; loosely defined, this cost function is the number of implicit conversions in the toplevel expression interpretation. 414 With more specificity, the \emph{cost} of a particular expression interpretation is a lexicographicallyordered tuple, where each element of the tuple corresponds to a particular kind of conversion. 415 In \CFA today, cost is a threetuple including the number of unsafe conversions, the number of polymorphic parameter bindings, and the number of safe conversions. 416 These 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} 419 void f(char, long); // $f_1$  cost (2, 0, 1) 420 forall(otype T) void f(T, long); // $f_2$  cost (0, 1, 1) 421 void f(long, long); // $f_{3a}$  cost (0, 0, 2) 422 void f(int, float); // $f_{3b}$  cost (0, 0, 2) 423 void f(int, long); // $f_4$  cost (0, 0, 1) 424 425 f(7, 11); 426 \end{lstlisting} 427 428 In 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©). 430 Neither $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. 431 If the declaration of $f_4$ was missing, the expression would be ambiguous, because the two singlestep ©int©to©long© conversions in $f_{3a}$ cost the same as the one doublestep ©int©to©float© conversion in $f_{3b}$. 432 433 In 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} 411 436 The 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. 412 437 The first area of investigation is efficient argumentparameter 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.