Changeset 4859ae9

Timestamp:

Aug 12, 2016, 4:06:50 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, 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:

• doc/aaron_comp_II/comp_II.tex (modified) (3 diffs)

doc/aaron_comp_II/comp_II.tex

@@ -463 +463 @@
 Deciding 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. 
 
-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. 
-Persch \etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass. 
-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.
+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. 
+Persch~\etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass. 
+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.
 
 \subsubsection{Common Subexpression Caching}
@@ -471 +471 @@
 
 \subsection{Implicit Conversion Application}
-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.
-Integrating implicit conversion handling into their algorithms provides some choice of implementation approach. 
+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. 
+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 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.}.
+Integrating implicit conversion handling into the presented argument-parameter matching algorithms provides some choice of implementation approach. 
 
 \subsubsection{On Parameters}
@@ -488 +489 @@
 
 \subsection{Candidate Set Generation}
-Cormack, Baker and Bilson all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression. 
+All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression. 
 However, 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.
 Under 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.
 
 \subsubsection{Eager}
-Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore. 
+Within the eager approach taken by the existing top-down and bottom-up algorithms, there are still variants to explore. 
 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 minimal-cost interpretations. 
 Sorting 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.