Changeset be0a9d8 for doc/aaron_comp_II


Ignore:
Timestamp:
Aug 10, 2016, 5:04:10 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:
e394618
Parents:
3078643
Message:

Added example of resolution DAG to Comp II draft

Location:
doc/aaron_comp_II
Files:
4 added
1 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    r3078643 rbe0a9d8  
    3737\setlength{\headsep}{0.25in}
    3838
     39\usepackage{caption}
     40\usepackage{subcaption}
     41
    3942%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    4043
     
    6265%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    6366
    64 \newcommand{\bigO}[1]{O\left( #1 \right)}
     67\newcommand{\bigO}[1]{O\!\left( #1 \right)}
    6568
    6669\begin{document}
     
    407410
    408411\subsection{Argument-Parameter Matching}
    409 The first axis we consider is argument-parameter matching --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
    410 
    411 \subsubsection{Argument-directed (``Bottom-up'')}
    412 Baker's algorithm for expression resolution\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up.
     412The first axis for consideration is argument-parameter matching direction --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
     413All expression resolution algorithms form a DAG of interpretations, some explicitly, some implicitly; in this DAG, arcs point from function-call interpretations to argument interpretations, as below:
     414\begin{figure}[h]
     415\centering
     416\begin{subfigure}[h]{2in}
     417\begin{lstlisting}
     418int *p;  // $p_i$
     419char *p; // $p_c$
     420
     421double *f(int*, int*); // $f_d$
     422char *f(char*, char*); // $f_c$
     423
     424f( f( p, p ), p );
     425\end{lstlisting}
     426\end{subfigure}~\begin{subfigure}[h]{2in}
     427\includegraphics{resolution_dag}
     428\end{subfigure}
     429\caption{Resolution DAG for a simple expression. Functions that do not have a valid argument matching are covered with an \textsf{X}.}\label{fig:res_dag}
     430\end{figure}
     431
     432Note that some interpretations may be part of more than one super-interpretation, as with $p_i$ in the bottom row, while some valid subexpression interpretations, like $f_d$ in the middle row, are not used in any interpretation of their containing expression.
     433
     434\subsubsection{Argument-directed (Bottom-up)}
     435Baker's algorithm for expression resolution~\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up.
    413436For each candidate function, Baker attempts to match argument types to parameter types in sequence, failing if any parameter cannot be matched.
    414437
    415 Bilson\cite{Bilson03} similarly pre-computes argument candidates in the original \CFA compiler, but then explicitly enumerates all possible argument combinations for a multi-parameter function; these argument combinations are matched to the parameter types of the candidate function as a unit rather than individual arguments.
    416 This is less efficient than Baker's approach, as the same argument may be compared to the same parameter many times, but allows a more straightforward handling of polymorphic type binding and multiple return types.
    417 It is possible the efficiency losses here relative to Baker could be significantly reduced by application of memoization to the argument-parameter type comparisons.
    418 
    419 \subsubsection{Parameter-directed (``Top-down'')}
    420 Unlike Baker and Bilson, Cormack's algorithm\cite{Cormack81} requests argument candidates which match the type of each parameter of each candidate function, from the top-level expression down; memoization of these requests is presented as an optimization.
     438Bilson~\cite{Bilson03} similarly pre-computes argument candidates in the original \CFA compiler, but then explicitly enumerates all possible argument combinations for a multi-parameter function; these argument combinations are matched to the parameter types of the candidate function as a unit rather than individual arguments.
     439This approach is less efficient than Baker's approach, as the same argument may be compared to the same parameter many times, but allows a more straightforward handling of polymorphic type-binding and multiple return-types.
     440It is possible the efficiency losses here relative to Baker could be significantly reduced by keeping a memoized cache of argument-parameter type comparisons and reading previously-seen argument-parameter matches from this cache rather than recomputing them.
     441
     442\subsubsection{Parameter-directed (Top-down)}
     443Unlike Baker and Bilson, Cormack's algorithm~\cite{Cormack81} requests argument candidates that match the type of each parameter of each candidate function, from the top-level expression down; memoization of these requests is presented as an optimization.
    421444As presented, this algorithm requires the result of the expression to have a known type, though an algorithm based on Cormack's could reasonably request a candidate set of any return type, though such a set may be quite large.
    422445
     
    436459
    437460Deciding when to switch between bottom-up and top-down resolution in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for it is an open question, one reasonable approach might be to switch from top-down to bottom-up when the number of candidate functions exceeds some threshold.
     461
     462\subsubsection{Common Subexpression Caching}
     463With any of these argument-parameter approaches, it may be a useful optimization to cache the resolution results for common subexpressions; in Figure~\ref{fig:res_dag} this optimization would result in the list of interpretations $[p_c, p_i]$ for ©p© only being calculated once, and re-used for each of the three instances of ©p©.
    438464
    439465\subsection{Implicit Conversion Application}
Note: See TracChangeset for help on using the changeset viewer.