Changeset 71b5d4d3 for doc/aaron_comp_II

Timestamp:

Aug 12, 2016, 11:24:11 AM (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:

dac593fd

Parents:

e3d1cc1

Message:

Add Pennello et al. citation to Comp II draft

File:

• doc/aaron_comp_II/comp_II.tex (modified) (1 diff)

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 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. 
+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. 
 Their algorithm differs from the hybrid approach under investigation in that it takes multiple passes over the expression tree to yield a solution, but is otherwise similar.