Changeset b1bd5d38 for doc/aaron_comp_II

Timestamp:

Jul 28, 2016, 12:21:04 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:

95330f5

Parents:

a2565a2

Message:

Added discussion of candidate generation schemes (eager vs lazy) to comp II

File:

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

doc/aaron_comp_II/comp_II.tex

@@ -303 +303 @@
 
 \subsection{Candidate Set Generation}
+Cormack\cite{Cormack81}, Baker\cite{Baker82} \& Bilson\cite{Bilson03} all 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 will be the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work.
+If we assume that user programmers will 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 higher-cost argument interpretations.
 
 \subsubsection{Eager}
+Within the eager approach taken by Cormack, Baker \& Bilson, there are still variants to explore. 
+Cormack \& 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 not clear if this short-circuiting behaviour would justify the cost of the sort.
 
 \subsubsection{Lazy}
+In the presence of implicit conversions, many argument interpretations may match a given parameter by application of an appropriate implicit conversion. 
+However, if user programmers actually use relatively few implicit conversions, then the ``on arguments'' approach to implicit conversions will generate a large number of high-cost interpretations which may never be used. 
+The essence of the lazy approach to candidate set generation is to wrap the matching algorithm into the element generator of a lazy list type, only generating as few elements at a time as possible to ensure that the next-smallest-cost interpretation has been generated. 
+Assuming that argument interpretations are provided to the parameter matching algorithm in sorted order, a sorted list of function call interpretations can be produced by generating combinations of arguments sorted by total cost\footnote{The author has developed a lazy $n$-way combination generation algorithm that can perform this task.}, then generating function call interpretations in the order suggested by this list. 
+Note that the function call interpretation chosen may have costs of its own, for instance polymorphic type binding, so in some cases a number of argument combinations (any combination whose marginal cost does not exceed the cost of the function call interpretation itself) may need to be considered to determine the next-smallest-cost function call interpretation.
+Ideally, this candidate generation approach will lead to very few unused candidates being generated (in the expected case where the user programmer has, in fact, provided a validly-typable program), but this research project will need to determine whether or not the overheads of lazy generation exceed the benefit produced from considering fewer interpretations.
 
 \subsubsection{Stepwise Lazy}
+As a compromise between the trade-offs of the eager and lazy approaches, it would also be interesting to investigate a ``stepwise lazy'' approach, where all the interpretations for some ``step'' are eagerly generated, then the interpretations in the later steps are only generated on demand. 
+Under this approach the \CFA resolver could, for instance, try expression interpretations in the following order:
+\begin{enumerate}
+\item All interpretations with no polymorphic type binding or implicit conversions.
+\item Interpretations containing no polymorphic type binding and at least one safe implicit conversion.
+\item Interpretations containing polymorphic type binding, but only safe implicit conversions.
+\item Interpretations containing at least one unsafe implicit conversion.
+\end{enumerate} 
+If a valid expression interpretation is found in one step, it is guaranteed to be lower-cost than any interpretation in a later step (by the structure of \CFA interpretation costs), so no step after the first one where a valid interpretation can be found need be considered.
+This may save significant amounts of work, especially given that the first steps avoid potentially expensive handling of implicit conversions and type assertion satisfaction entirely.
 
 %\subsection{Parameter-Directed}