# source:doc/aaron_comp_II/comp_II.tex@e93bc13

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglerjacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since e93bc13 was e93bc13, checked in by Aaron Moss <a3moss@…>, 5 years ago

Merge Peter's suggestions into Comp II draft

• Property mode set to 100644
File size: 41.7 KB
Line
2% red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
3% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
4% green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
5% LaTex escape §...§ (section symbol) emacs: C-q M-'
6% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
7% math escape $...$ (dollar symbol)
8
9\documentclass[twoside,11pt]{article}
10
11%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12
13% Latex packages used in the document (copied from CFA user manual).
14\usepackage[T1]{fontenc}                                % allow Latin1 (extended ASCII) characters
15\usepackage{textcomp}
16\usepackage[latin1]{inputenc}
17\usepackage{fullpage,times,comment}
18\usepackage{epic,eepic}
19\usepackage{upquote}                                                                    % switch curled '" to straight
20\usepackage{calc}
21\usepackage{xspace}
22\usepackage{graphicx}
23\usepackage{varioref}                                                                   % extended references
24\usepackage{listings}                                                                   % format program code
25\usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
26\usepackage{latexsym}                                   % \Box glyph
27\usepackage{mathptmx}                                   % better math font with "times"
28\usepackage[usenames]{color}
29\usepackage[pagewise]{lineno}
30\renewcommand{\linenumberfont}{\scriptsize\sffamily}
31\input{common}                                          % bespoke macros used in the document
33\usepackage{breakurl}
34\renewcommand{\UrlFont}{\small\sf}
35
36\setlength{\topmargin}{-0.45in}                                                 % move running title into header
38
39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
40
41\newsavebox{\LstBox}
42
43%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
44
45\title{
46\Huge \vspace*{1in} Efficient Type Resolution in \CFA \\
47\huge \vspace*{0.25in} PhD Comprehensive II Research Proposal
48\vspace*{1in}
49}
50
51\author{
52\huge Aaron Moss \\
53\Large \vspace*{0.1in} \texttt{a3moss@uwaterloo.ca} \\
54\Large Cheriton School of Computer Science \\
55\Large University of Waterloo
56}
57
58\date{
59\today
60}
61
62%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
63
64\begin{document}
66% changed after setting pagestyle
69\pagenumbering{roman}
70\linenumbers                                            % comment out to turn off line numbering
71
72\maketitle
73\thispagestyle{empty}
74
75\clearpage
76\thispagestyle{plain}
77\pdfbookmark[1]{Contents}{section}
78\tableofcontents
79
80\clearpage
81\thispagestyle{plain}
82\pagenumbering{arabic}
83
84\section{Introduction}
85
86\CFA\footnote{Pronounced C-for-all'', and written \CFA or \CFL.} is an evolutionary modernization of the C programming language currently being designed and built at the University of Waterloo by a team led by Peter Buhr.
87\CFA both fixes existing design problems and adds multiple new features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others.
88The new features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type-system.
89
90The primary goal of this research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into CFA, the \CFA reference compiler.
91Secondary goals of this project include the development of various new language features for \CFA: parametric-polymorphic (generic'') types have already been designed and implemented, and reference types and user-defined conversions are under design consideration.
92An experimental performance-testing architecture for resolution algorithms is under development to determine the relative performance of different expression resolution algorithms, as well as the compile-time cost of adding various new features to the \CFA type-system.
93More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type-systems.
94
95\section{\CFA}
96
97To make the scope of the proposed expression resolution problem more explicit, it is necessary to define the features of both C and \CFA (both current and proposed) that affect this algorithm.
98In some cases the interactions of multiple features make expression resolution a significantly more complex problem than any individual feature would; in other cases a feature that does not by itself add any complexity to expression resolution triggers previously rare edge cases more frequently.
99
100It is important to note that \CFA is not an object-oriented language.
101\CFA does have a system of (possibly implicit) type conversions derived from C's type conversions; while these conversions may be thought of as something like an inheritance hierarchy the underlying semantics are significantly different and such an analogy is loose at best.
102Particularly, \CFA has no concept of subclass'', and thus no need to integrate an inheritance-based form of polymorphism with its parametric and overloading-based polymorphism.
103The graph structure of the \CFA type conversions is also markedly different than an inheritance graph; it has neither a top nor a bottom type, and does not satisfy the lattice properties typical of inheritance graphs.
104
105\subsection{Polymorphic Functions}
106The most significant feature \CFA adds is parametric-polymorphic functions.
107Such functions are written using a ©forall© clause (which gives the language its name):
108\begin{lstlisting}
109®forall(otype T)®
110T identity(T x) {
111    return x;
112}
113
114int forty_two = identity(42); // T is bound to int, forty_two == 42
115\end{lstlisting}
116The ©identity© function above can be applied to any complete object type (or ©otype©'').
118The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor and destructor.
119
120Since bare polymorphic types do not provide a great range of available operations, \CFA also provides a \emph{type assertion} mechanism to provide further information about a type:
121\begin{lstlisting}
122forall(otype T ®| { T twice(T); }®)
123T four_times(T x) {
124    return twice( twice(x) );
125}
126
127double twice(double d) { return d * 2.0; } // (1)
128
129double magic = four_times(10.5); // T is bound to double, uses (1) to satisfy type assertion
130\end{lstlisting}
131These type assertions may be either variable or function declarations which depend on a polymorphic type variable.
133
134Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
136\begin{lstlisting}
137forall(otype S | { S ?+?(S, S); })
138S twice(S x) { return x + x; }  // (2)
139\end{lstlisting}
142
143Finding appropriate functions to satisfy type assertions is essentially a recursive case of expression resolution, as it takes a name (that of the type assertion) and attempts to match it to a suitable declaration in the current scope.
144If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function will be examined as a candidate for its own type assertion unboundedly repeatedly.
145To avoid infinite loops, the current CFA compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \CC compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by CFA.
146One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion will not produce a well-typed expression.
147
148\subsubsection{Traits}
149\CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below:
150\begin{lstlisting}
151trait has_magnitude(otype T) {
152    bool ?<?(T, T);        // comparison operator for T
153    T -?(T);               // negation operator for T
154    void ?{}(T*, zero_t);  // constructor from 0 literal
155};
156
157forall(otype M | has_magnitude(M))
158int sgn( M m ) {
159    M zero = 0;  // uses zero_t constructor from trait
160    if ( m < zero ) return -1;
161    if ( zero < m ) return 1;
162    return 0;
163}
164
165// TODO write another function
166\end{lstlisting}
167
169In C, no more than one function or variable in the same scope may share the same name, and function or variable declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration.
170This makes finding the proper declaration to match to a function application or variable expression a simple matter of symbol table lookup, which can be easily and efficiently implemented.
171\CFA, on the other hand, allows overloading of variable and function names, so long as the overloaded declarations do not have the same type, avoiding the multiplication of function names for different types common in the C standard library, as in the following example:
172\begin{lstlisting}
173int three = 3;
174double three = 3.0;
175
176int thrice(int i) { return i * three; } // uses int three
177double thrice(double d) { return d * three; } // uses double three
178
179// thrice(three); // ERROR: ambiguous
180int nine = thrice(three);    // uses int thrice and three, based on return type
181double nine = thrice(three); // uses double thrice and three, based on return type
182\end{lstlisting}
183
184The presence of name overloading in \CFA means that simple table lookup is not sufficient to match identifiers to declarations, and a type matching algorithm must be part of expression resolution.
185
186\subsection{Implicit Conversions}
187In addition to the multiple interpretations of an expression produced by name overloading, \CFA also supports all of the implicit conversions present in C, producing further candidate interpretations for expressions.
188C does not have a traditionally-defined inheritance hierarchy of types, but the C standard's rules for the usual arithmetic conversions'' define which of the built-in types are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type.
190The expression resolution problem, then, is to find the unique minimal-cost interpretation of each expression in the program, where all identifiers must be matched to a declaration and implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression.
191Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate.
192
193\subsubsection{User-generated Implicit Conversions}
194One possible additional feature to \CFA included in this research proposal is \emph{user-generated implicit conversions}.
195Such a conversion system should be simple for user programmers to utilize, and fit naturally with the existing design of implicit conversions in C; ideally it would also be sufficiently powerful to encode C's usual arithmetic conversions itself, so that \CFA only has one set of rules for conversions.
196
197Ditchfield\cite{Ditchfield:conversions} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions.
198A monomorphic variant of these functions can be used to mark a conversion arc in the DAG as only usable as the final step in a conversion.
199With these two types of conversion arcs, separate DAGs can be created for the safe and the unsafe conversions, and conversion cost can be represented as path length through the DAG.
200Open research questions on this topic include whether a conversion graph can be generated that represents each allowable conversion in C with a unique minimal-length path, such that the path lengths accurately represent the relative costs of the conversions, whether such a graph representation can be usefully augmented to include user-defined types as well as built-in types, and whether the graph can be efficiently represented and included in the expression resolver.
201
202\subsection{Constructors and Destructors}
203Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
204Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for struct types these functions each call their equivalents on each field of the struct.
205This affects expression resolution because an ©otype© type variable ©T© implicitly adds four type assertions, one for each of these four functions, so assertion resolution is pervasive in \CFA polymorphic functions, even those without any explicit type assertions.
206
207\subsection{Generic Types}
208I have already added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
209A generic type can be declared by placing a ©forall© specifier on a struct or union declaration, and instantiated using a parenthesized list of types after the type name:
210\begin{lstlisting}
211forall(otype R, otype S) struct pair {
212    R first;
213    S second;
214};
215
216forall(otype T)
217T value( pair(const char*, T) *p ) { return p->second; }
218
219pair(const char*, int) p = { "magic", 42 };
220int magic = value( &p );
221\end{lstlisting}
222For \emph{concrete} generic types, that is, those where none of the type parameters depend on polymorphic type variables (like ©pair(const char*, int)© above), the struct is essentially template expanded to a new struct type; for \emph{polymorphic} generic types (such as ©pair(const char*, T)© above), member access is handled by a runtime calculation of the field offset, based on the size and alignment information of the polymorphic parameter type.
223The default-generated constructors, destructor and assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
224
225Aside from giving users the ability to create more parameterized types than just the built-in pointer, array and function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where a polymorphic function can match its own assertions much more common, as follows:
226\begin{itemize}
227\item Given an expression in an untyped context, such as a top-level function call with no assignment of return values, apply a polymorphic implicit conversion to the expression that can produce multiple types (the built-in conversion from ©void*© to any other pointer type is one, but not the only).
228\item When attempting to use a generic type with ©otype© parameters (such as ©box© above) for the result type of the expression, the resolver will also need to decide what type to use for the ©otype© parameters on the constructors and related functions, and will have no constraints on what they may be.
229\item Attempting to match some yet-to-be-determined specialization of the generic type to this ©otype© parameter will create a recursive case of the default constructor, \etc matching their own type assertions, creating an unboundedly deep nesting of the generic type inside itself.
230\end{itemize}
231As discussed above, any \CFA expression resolver must handle this possible infinite recursion somehow, but the combination of generic types with other language features makes this particular edge case occur somewhat frequently in user code.
232
233\subsection{Tuple Types}
234\CFA adds \emph{tuple types} to C, a facility for referring to multiple values with a single identifier.
235A variable may name a tuple, and a function may return one.
236Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap© below:
237\begin{lstlisting}
238[char, char] x = [ '!', '?' ];
239int x = 42;
240
241forall(otype T) [T, T] swap( T a, T b ) { return [b, a]; }
242
243x = swap( x ); // destructure [char, char] x into two elements of parameter list
244// can't use int x for parameter, not enough arguments to swap
245\end{lstlisting}
246Tuple destructuring means that the mapping from the position of a subexpression in the argument list to the position of a paramter in the function declaration is not straightforward, as some arguments may be expandable to different numbers of parameters, like ©x© above.
247
248\subsection{Reference Types}
249I have been designing \emph{reference types} for \CFA, in collaboration with the rest of the \CFA research team.
250Given some type ©T©, a ©T&© (reference to ©T©'') is essentially an automatically dereferenced pointer; with these semantics most of the C standard's discussions of lvalues can be expressed in terms of references instead, with the benefit of being able to express the difference between the reference and non-reference version of a type in user code.
251References preserve C's existing qualifier-dropping lvalue-to-rvalue conversion (\eg a ©const volatile int&© can be implicitly converted to a bare ©int©); the reference proposal also adds a rvalue-to-lvalue conversion to \CFA, implemented by storing the value in a new compiler-generated temporary and passing a reference to the temporary.
252These two conversions can chain, producing a qualifier-dropping conversion for references, for instance converting a reference to a ©const int© into a reference to a non-©const int© by copying the originally refered to value into a fresh temporary and taking a reference to this temporary.
253These reference conversions may also chain with the other implicit type conversions.
254The main implication of this for expression resolution is the multiplication of available implicit conversions, though in a restricted context that may be able to be treated efficiently as a special case.
255
256\subsection{Literal Types}
258Implicit conversions from these types would allow ©0© and ©1© to be considered as values of many different types, depending on context, allowing expression desugarings like ©if ( x ) {}© $\Rightarrow$ ©if ( x != 0 ) {}© to be implemented efficiently and precicely.
259This is a generalization of C's existing behaviour of treating ©0© as either an integer zero or a null pointer constant, and treating either of those values as boolean false.
260The main implication for expression resolution is that the frequently encountered expressions ©0© and ©1© may have a significant number of valid interpretations.
261
262\subsection{Deleted Function Declarations}
263One final proposal for \CFA with an impact on the expression resolver is \emph{deleted function declarations}; in \CCeleven, a function declaration can be deleted as below:
264\begin{lstlisting}
265int somefn(char) = delete;
266\end{lstlisting}
267To add a similar feature to \CFA would involve including the deleted function declarations in expression resolution along with the normal declarations, but producing a compiler error if the deleted function was the best resolution.
268How conflicts should be handled between resolution of an expression to both a deleted and a non-deleted function is a small but open research question.
269
270\section{Expression Resolution}
271The expression resolution problem is essentially to determine an optimal matching between some combination of argument interpretations and the parameter list of some overloaded instance of a function; the argument interpretations are produced by recursive invocations of expression resolution, where the base case is zero-argument functions (which are, for purposes of this discussion, semantically equivalent to named variables or constant literal expressions).
272Assuming that the matching between a function's parameter list and a combination of argument interpretations can be done in $O(p^k)$ time, where $p$ is the number of parameters and $k$ is some positive number, if there are $O(i)$ valid interpretations for each subexpression, there will be $O(i)$ candidate functions and $O(i^p)$ possible argument combinations for each expression, so a single recursive call to expression resolution will take $O(i^{p+1} \cdot p^k)$ time if it compares all combinations.
273Given this bound, resolution of a single top-level expression tree of depth $d$ takes $O(i^{p+1} \cdot p^{k \cdot d})$ time\footnote{The call tree will have leaves at depth $O(d)$, and each internal node will have $O(p)$ fan-out, producing $O(p^d)$ total recursive calls.}.
274Expression resolution is somewhat unavoidably exponential in $p$, the number of function parameters, and $d$, the depth of the expression tree, but these values are fixed by the user programmer, and generally bounded by reasonably small constants.
275$k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ term is linear in the input size of the source code for the expression, otherwise the resolution algorithm will exibit sub-linear performance scaling on code containing more-deeply nested expressions.
276The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type-system completeness.
277
278The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests two primary areas of investigation to accomplish that end.
279The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.
280%TODO: look up and lit review
281The second, and likely more fruitful, area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; given the large ($p+1$) exponent on number of interpretations considered in the runtime analysis, even small reductions here could have a significant effect on overall resolver runtime.
282The discussion below presents a number of largely orthagonal axes for expression resolution algorithm design to be investigated, noting prior work where applicable.
283
284\subsection{Argument-Parameter Matching}
285The 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.
286
287\subsubsection{Argument-directed (Bottom-up'')}
288Baker's algorithm for expression resolution\cite{Baker82} pre-computes argument candidates, from the leaves of the expression tree up.
289For each candidate function, Baker attempts to match argument types to parameter types in sequence, failing if any parameter cannot be matched.
290
291Bilson\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.
292This 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.
293It is possible the efficiency losses here relative to Baker could be significantly reduced by application of memoization to the argument-parameter type comparisons.
294
295\subsubsection{Parameter-directed (Top-down'')}
296Unlike 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.
297As 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.
298
299\subsubsection{Hybrid}
300This proposal includes the investigation of hybrid top-down/bottom-up argument-parameter matching.
301A reasonable hybrid approach might be to take a top-down approach when the expression to be matched is known to have a fixed type, and a bottom-up approach in untyped contexts.
302This may include switches from one type to another at different levels of the expression tree, for instance:
303\begin{lstlisting}
304forall(otype T)
305int f(T x);  // (1)
306
307void* f(char y);  // (2)
308
309int x = f( f( '!' ) );
310\end{lstlisting}
312
313Deciding 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.
314
315\subsection{Implicit Conversion Application}
316Baker's\cite{Baker82} and Cormack's\cite{Cormack81} algorithms do not account for implicit conversions\footnote{Baker does briefly comment on an approach for handling implicit conversions.}; both assume that there is at most one valid interpretation of a given expression for each distinct type.
317Integrating implicit conversion handling into their algorithms provides some choice of implementation approach.
318
319\subsubsection{On Parameters}
320Bilson\cite{Bilson03} did account for implicit conversions in his algorithm, but it is not clear his approach is optimal.
321His algorithm integrates checking for valid implicit conversions into the argument-parameter matching step, essentially trading more expensive matching for a smaller number of argument interpretations.
322This approach may result in the same subexpression being checked for a type match with the same type multiple times, though again memoization may mitigate this cost, and this approach will not generate implicit conversions that are not useful to match the containing function.
323
324\subsubsection{On Arguments}
325Another approach would be to generate a set of possible implicit conversions for each set of interpretations of a given argument.
326This would have the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, would also never find more than one interpretation of the argument with a given type, and would re-use calculation of implicit conversions between function candidates.
327On the other hand, this approach may unncessarily generate argument interpretations that will never match a parameter, wasting work.
328Further, in the presence of tuple types this approach may lead to a combinatorial explosion of argument interpretations considered, unless the tuple can be considered as a sequence of elements rather than a unified whole.
329
330\subsection{Candidate Set Generation}
331Cormack\cite{Cormack81}, Baker\cite{Baker82} and Bilson\cite{Bilson03} all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
332However, 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.
333If 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.
334
335\subsubsection{Eager}
336Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore.
337Cormack 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.
338Sorting 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.
339
340\subsubsection{Lazy}
341In the presence of implicit conversions, many argument interpretations may match a given parameter by application of an appropriate implicit conversion.
342However, 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.
343The 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.
344Assuming 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{I have already developed a lazy $n$-way combination generation algorithm to perform this task.}, then generating function call interpretations in the order suggested by this list.
345Note 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.
346Ideally, 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.
347
348\subsubsection{Stepwise Lazy}
349As 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.
350Under this approach the \CFA resolver could, for instance, try expression interpretations in the following order:
351\begin{enumerate}
352\item Interpretations with no polymorphic type binding or implicit conversions.
353\item Interpretations containing no polymorphic type binding and at least one safe implicit conversion.
354\item Interpretations containing polymorphic type binding, but only safe implicit conversions.
355\item Interpretations containing at least one unsafe implicit conversion.
356\end{enumerate}
357If 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.
358This may save significant amounts of work, especially given that the first steps avoid potentially expensive handling of implicit conversions and type assertion satisfaction entirely.
359
360%\subsection{Parameter-Directed}
361%\textbf{TODO: Richard's algorithm isn't Baker (Cormack?), disentangle from this section \ldots}.
362%The expression resolution algorithm used by the existing iteration of CFA is based on Baker's\cite{Baker82} algorithm for overload resolution in Ada.
363%The essential idea of this algorithm is to first find the possible interpretations of the most deeply nested subexpressions, then to use these interpretations to recursively generate valid interpretations of their superexpressions.
364%To simplify matters, the only expressions considered in this discussion of the algorithm are function application and literal expressions; other expression types can generally be considered to be variants of one of these for the purposes of the resolver, \eg variables are essentially zero-argument functions.
365%If we consider expressions as graph nodes with arcs connecting them to their subexpressions, these expressions form a DAG, generated by the algorithm from the bottom up.
366%Literal expressions are represented by leaf nodes, annotated with the type of the expression, while a function application will have a reference to the function declaration chosen, as well as arcs to the interpretation nodes for its argument expressions; functions are annotated with their return type (or types, in the case of multiple return values).
367%
368%\textbf{TODO: Figure}
369%
370%Baker's algorithm was designed to account for name overloading; Richard Bilson\cite{Bilson03} extended this algorithm to also handle polymorphic functions, implicit conversions and multiple return types when designing the original \CFA compiler.
371%The core of the algorithm is a function which Baker refers to as $gen\_calls$.
372%$gen\_calls$ takes as arguments the name of a function $f$ and a list containing the set of possible subexpression interpretations $S_j$ for each argument of the function and returns a set of possible interpretations of calling that function on those arguments.
373%The subexpression interpretations are generally either singleton sets generated by the single valid interpretation of a literal expression, or the results of a previous call to $gen\_calls$.
374%If there are no valid interpretations of an expression, the set returned by $gen\_calls$ will be empty, at which point resolution can cease, since each subexpression must have at least one valid interpretation to produce an interpretation of the whole expression.
375%On the other hand, if for some type $T$ there is more than one valid interpretation of an expression with type $T$, all interpretations of that expression with type $T$ can be collapsed into a single \emph{ambiguous expression} of type $T$, since the only way to disambiguate expressions is by their return types.
376%If a subexpression interpretation is ambiguous, than any expression interpretation containing it will also be ambiguous.
377%In the variant of this algorithm including implicit conversions, the interpretation of an expression as type $T$ is ambiguous only if there is more than one \emph{minimal-cost} interpretation of the expression as type $T$, as cheaper expressions are always chosen in preference to more expensive ones.
378%
379%Given this description of the behaviour of $gen\_calls$, its implementation is quite straightforward: for each function declaration $f_i$ matching the name of the function, consider each of the parameter types $p_j$ of $f_i$, attempting to match the type of an element of $S_j$ to $p_j$ (this may include checking of implicit conversions).
380%If no such element can be found, there is no valid interpretation of the expression using $f_i$, while if more than one such (minimal-cost) element is found than an ambiguous interpretation with the result type of $f_i$ is produced.
381%In the \CFA variant, which includes polymorphic functions, it is possible that a single polymorphic function definition $f_i$ can produce multiple valid interpretations by different choices of type variable bindings; these interpretations are unambiguous so long as the return type of $f_i$ is different for each type binding.
382%If all the parameters $p_j$ of $f_i$ can be uniquely matched to a candidate interpretation, then a valid interpretation based on $f_i$ and those $p_j$ is produced.
383%$gen\_calls$ collects the produced interpretations for each $f_i$ and returns them; a top level expression is invalid if this list is empty, ambiguous if there is more than one (minimal-cost) result, or if this single result is ambiguous, and valid otherwise.
384%
385%In this implementation, resolution of a single top-level expression takes time $O(\ldots)$, where \ldots. \textbf{TODO:} \textit{Look at 2.3.1 in Richard's thesis when working out complexity; I think he does get the Baker algorithm wrong on combinations though, maybe\ldots}
386%
387%\textbf{TODO: Basic Lit Review} \textit{Look at 2.4 in Richard's thesis for any possible more-recent citations of Baker\ldots} \textit{Look back at Baker's related work for other papers that look similar to what you're doing, then check their citations as well\ldots} \textit{Look at Richard's citations in 2.3.2 w.r.t. type data structures\ldots}
388%\textit{CormackWright90 seems to describe a solution for the same problem, mostly focused on how to find the implicit parameters}
389
390\section{Proposal}
391Baker\cite{Baker82} discussed various expression resolution algorithms that could handle name overloading, but left experimental comparison of those algorithms to future work; Bilson\cite{Bilson03} described one extension of Baker's algorithm to handle implicit conversions, but did not fully explore the space of algorithmic approaches to handle both overloaded names and implicit conversions.
392This project is intended to experimentally test a number of expression resolution algorithms which are powerful enough to handle the \CFA type-system, including both name overloading and implicit conversions.
393This comparison will close Baker's open research question, as well as potentially improving on Bilson's \CFA compiler.
394
395Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype will be developed which acts on a simplified input language encapsulating the essential details of the \CFA type-system\footnote{Note that this simplified input language is not required to be a usable programming language.}.
396Multiple variants of this resolver prototype will be implemented, each encapsulating a different expression resolution variant, sharing as much code as feasible.
397These variants will be instrumented to test runtime performance, and run on a variety of input files; the input files may be generated programmatically or from exisiting code in \CFA or similar languages.
398These experimental results will allow the research team to determine the algorithm likely to be most performant in practical use, and replace CFA's existing expression resolver with that code.
399The experimental results will also provide some empirical sense of the compile-time cost of various language features by comparing the results of the most performant resolver variant that supports the feature with the most performant resolver variant that doesn't, a useful capability to guide language design.
400
401This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type-systems, specifically targeting the feature interaction between name overloading and implicit conversions.
402
403\appendix
404\section{Completion Timeline}
405The following is a preliminary estimate of the time necessary to complete the major components of this research project:
406\begin{center}
407\begin{tabular}{ | r @{--} l | p{4in} | }
408\hline       May 2015 & April 2016   & Project familiarization and generic types design and implementation. \\
409\hline       May 2016 & April 2017   & Design and implement resolver prototype and run performance experiments. \\
410\hline       May 2017 & August 2017  & Integrate new language features and best-performing resolver prototype into CFA. \\
411\hline September 2017 & January 2018 & Thesis writing and defense. \\
412\hline
413\end{tabular}
414\end{center}
415
417\bibliographystyle{plain}
418\bibliography{cfa}
419