Changeset 4859ae9 for doc/aaron_comp_II


Ignore:
Timestamp:
Aug 12, 2016, 4:06:50 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
afd4cde
Parents:
e73a793
Message:

Add citation for Persch et al., generalize language in later sections to account for further citations

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    re73a793 r4859ae9  
    463463Deciding when to switch between bottom-up and top-down 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 top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions.
    464464
    465 Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello \etal~\cite{Pennello80}) that uses a top-down filtering pass followed by a bottom-up 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 two-pass approach where the bottom-up pass is followed by the top-down 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, an optimization defeated by \CFA's polymorphic functions and implicit conversions.
     465Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello~\etal~\cite{Pennello80}) that uses a top-down filtering pass followed by a bottom-up 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.
     466Persch~\etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass.
     467These 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.
    468468
    469469\subsubsection{Common Subexpression Caching}
     
    471471
    472472\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.
     473With 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.
     474Cormack 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 argument-parameter 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.}.
     475Integrating implicit conversion handling into the presented argument-parameter matching algorithms provides some choice of implementation approach.
    475476
    476477\subsubsection{On Parameters}
     
    488489
    489490\subsection{Candidate Set Generation}
    490 Cormack, Baker and Bilson all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
     491All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
    491492However, given that the top-level expression interpretation that is ultimately chosen is the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work.
    492493Under the assumption that that programmers generally write function calls with relatively low-cost interpretations, a possible work-saving heuristic is to generate only the lowest-cost argument interpretations first, attempt to find a valid top-level interpretation using them, and only if that fails generate the next higher-cost argument interpretations.
    493494
    494495\subsubsection{Eager}
    495 Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore.
     496Within the eager approach taken by the existing top-down and bottom-up algorithms, there are still variants to explore.
    496497Cormack 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 minimal-cost interpretations.
    497498Sorting the lists of argument or function call interpretations by cost at some point during resolution may provide useful opportunities to short-circuit expression evaluation when a minimal-cost interpretation is found, though it is unclear if this short-circuiting behaviour justifies the cost of the sort.
Note: See TracChangeset for help on using the changeset viewer.