Changeset 4859ae9
 Timestamp:
 Aug 12, 2016, 4:06:50 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:
 afd4cde
 Parents:
 e73a793
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/aaron_comp_II/comp_II.tex
re73a793 r4859ae9 463 463 Deciding when to switch between bottomup and topdown resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for which subexpressions to swich matching strategies on is an open question, one reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use topdown resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottomup resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions. 464 464 465 Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello 466 Persch 467 These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and also in that they apply both filtering heuristics to all expression nodes , an optimization defeated by \CFA's polymorphic functions and implicit conversions.465 Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello~\etal~\cite{Pennello80}) that uses a topdown filtering pass followed by a bottomup filtering pass to reduce the number of candidate interpretations; they prove that for the Ada programming language a small number of such iterations is sufficient to converge to a solution for the expression resolution problem. 466 Persch~\etal~\cite{PW:overload} developed a similar twopass approach where the bottomup pass is followed by the topdown pass. 467 These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and also in that they apply both filtering heuristics to all expression nodes; \CFA's polymorphic functions and implicit conversions make the approach of filtering out invalid types taken by all of these algorithms infeasible. 468 468 469 469 \subsubsection{Common Subexpression Caching} … … 471 471 472 472 \subsection{Implicit Conversion Application} 473 Baker's and Cormack's algorithms do not account for implicit conversions\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; both assume that there is at most one valid interpretation of a given expression for each distinct type. 474 Integrating implicit conversion handling into their algorithms provides some choice of implementation approach. 473 With the exception of Bilson, the authors mentioned above do not account for implicit conversions in their algorithms\footnote{Baker does briefly comment on an approach for handling implicit conversions, but does not provide an implementable algorithm.}; all assume that there is at most one valid interpretation of a given expression for each distinct type. 474 Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with implicit parameter binding and type inference; their presentation of implicit parameter binding and type inference is largely similar to \CFA's implicit polymorphic type binding, though their algorithm does not account for other implicit conversions and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argumentparameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}. 475 Integrating implicit conversion handling into the presented argumentparameter matching algorithms provides some choice of implementation approach. 475 476 476 477 \subsubsection{On Parameters} … … 488 489 489 490 \subsection{Candidate Set Generation} 490 Cormack, Baker and Bilson allgenerate the complete set of candidate argument interpretations before attempting to match the containing function call expression.491 All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression. 491 492 However, given that the toplevel expression interpretation that is ultimately chosen is the minimalcost valid interpretation, any consideration of nonminimalcost interpretations is in some sense wasted work. 492 493 Under the assumption that that programmers generally write function calls with relatively lowcost interpretations, a possible worksaving heuristic is to generate only the lowestcost argument interpretations first, attempt to find a valid toplevel interpretation using them, and only if that fails generate the next highercost argument interpretations. 493 494 494 495 \subsubsection{Eager} 495 Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore.496 Within the eager approach taken by the existing topdown and bottomup algorithms, there are still variants to explore. 496 497 Cormack and Baker do not account for implict conversions, and thus do not account for the possibility of multiple valid interpretations with distinct costs; Bilson, on the other hand, sorts the list of interpretations to aid in finding minimalcost interpretations. 497 498 Sorting the lists of argument or function call interpretations by cost at some point during resolution may provide useful opportunities to shortcircuit expression evaluation when a minimalcost interpretation is found, though it is unclear if this shortcircuiting behaviour justifies the cost of the sort.
Note: See TracChangeset
for help on using the changeset viewer.