Changeset ce76eb9 for doc/aaron_comp_II
 Timestamp:
 Aug 8, 2016, 5:16:03 PM (5 years ago)
 Branches:
 aaronthesis, armeh, cleanupdtors, ctor, deferred_resn, demangler, jacob/cs343translation, jenkinssandbox, master, memory, newast, newastuniqueexpr, newenv, no_list, persistentindexer, resolvnew, with_gc
 Children:
 f18a711
 Parents:
 3bb195c
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/aaron_comp_II/comp_II.tex
r3bb195c rce76eb9 62 62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 63 63 64 \newcommand{\bigO}[1]{O\left( #1 \right)} 65 64 66 \begin{document} 65 67 \pagestyle{headings} … … 386 388 387 389 \section{Expression Resolution} 388 The expression resolution problem is essentially to determine an optimal matching 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). 389 Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $O(p^k)$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $O(i)$ valid interpretations for each subexpression, there will be $O(i)$ candidate functions and $O(i^p)$ possible argument combinations for each expression, so a single recursive call to expression resolution will take $O(i^{p+1} \cdot p^k)$ time if it compares all combinations. 390 Given this bound, resolution of a single toplevel expression tree of depth $d$ takes $O(i^{p+1} \cdot p^{k \cdot d})$ time\footnote{The call tree will have leaves at depth $O(d)$, and each internal node will have $O(p)$ fanout, producing $O(p^d)$ total recursive calls.}. 391 Expression resolution is somewhat unavoidably exponential in $p$, the number of function parameters, and $d$, the depth of the expression tree, but these values are fixed by the user programmer, and generally bounded by reasonably small constants. 392 $k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ term is linear in the input size of the source code for the expression, otherwise the resolution algorithm will exibit sublinear performance scaling on code containing moredeeply nested expressions. 390 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). 391 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. 392 Given these bounds, resolution of a single toplevel expression tree of depth $d$ takes $\bigO{i^{p+1} \cdot p^{k \cdot d}}$ time under fullcombination matching, or $\bigO{i(p+1) \cdot p^{k \cdot d}}$ time for independentparameter matching\footnote{A call tree has leaves at depth $\bigO{d}$, and each internal node has $\bigO{p}$ fanout, producing $\bigO{p^d}$ total recursive calls.}. 393 394 Expression resolution is somewhat unavoidably exponential in $d$, the depth of the expression tree, and if arguments cannot be matched to parameters independently of each other, expression resolution is also exponential in $p$. 395 However, both $d$ and $p$ are fixed by the user programmer, and generally bounded by reasonably small constants. 396 $k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ factor is linear in the input size of the source code for the expression, otherwise the resolution algorithm exibits sublinear performance scaling on code containing moredeeply nested expressions. 393 397 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. 394 398 395 The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests t woprimary areas of investigation to accomplish that end.396 The first is efficient argumentparameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.399 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. 400 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. 397 401 %TODO: look up and lit review 398 The second, and likely more fruitful, area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; given the large ($p+1$) exponent on number of interpretations considered in the runtime analysis, even small reductions here could have a significant effect on overall resolver runtime. 402 The second area of investigation is minimizing dependencies between argumentparameter matches; the current CFA compiler attempts to match entire argument combinations against functions at once, potentially attempting to match the same argument against the same parameter multiple times. 403 Whether the feature set of \CFA admits an expression resolution algorithm where arguments can be matched to parameters independently of other arguments in the same function application is an area of open research; polymorphic type paramters produce enough of a crossargument dependency that the problem is not trivial. 404 If crossargument resolution dependencies cannot be completely eliminated, effective caching strategies to reduce duplicated work between equivalent argumentparameter matches in different combinations may mitigate the asymptotic defecits of the wholecombination matching approach. 405 The final area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; if argumentparameter matches cannot be made independent, even small reductions in $i$ should yield significant reductions in the $i^{p+1}$ resolver runtime factor. 399 406 The discussion below presents a number of largely orthagonal axes for expression resolution algorithm design to be investigated, noting prior work where applicable. 400 407
Note: See TracChangeset
for help on using the changeset viewer.