Changeset b1bd5d38

Jul 28, 2016, 12:21:04 PM (8 years ago)
Aaron Moss <a3moss@…>
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

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

1 edited


  • doc/aaron_comp_II/comp_II.tex

    ra2565a2 rb1bd5d38  
    304304\subsection{Candidate Set Generation}
     305Cormack\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.
     306However, 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.
     307If 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.
     310Within the eager approach taken by Cormack, Baker \& Bilson, there are still variants to explore.
     311Cormack \& 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.
     312Sorting 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.
     315In the presence of implicit conversions, many argument interpretations may match a given parameter by application of an appropriate implicit conversion.
     316However, 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.
     317The 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.
     318Assuming 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.
     319Note 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.
     320Ideally, 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.
    310322\subsubsection{Stepwise Lazy}
     323As 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.
     324Under this approach the \CFA resolver could, for instance, try expression interpretations in the following order:
     326\item All interpretations with no polymorphic type binding or implicit conversions.
     327\item Interpretations containing no polymorphic type binding and at least one safe implicit conversion.
     328\item Interpretations containing polymorphic type binding, but only safe implicit conversions.
     329\item Interpretations containing at least one unsafe implicit conversion.
     331If 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.
     332This may save significant amounts of work, especially given that the first steps avoid potentially expensive handling of implicit conversions and type assertion satisfaction entirely.
Note: See TracChangeset for help on using the changeset viewer.