Changeset b44a7c5 for doc/aaron_comp_II/comp_II.tex
 Timestamp:
 Jul 26, 2016, 10:06:53 AM (6 years ago)
 Branches:
 aaronthesis, armeh, cleanupdtors, ctor, deferred_resn, demangler, jacob/cs343translation, jenkinssandbox, master, memory, newast, newastuniqueexpr, newenv, no_list, persistentindexer, resolvnew, with_gc
 Children:
 c967ef9
 Parents:
 ef3b335
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/aaron_comp_II/comp_II.tex
ref3b335 rb44a7c5 245 245 246 246 \section{Expression Resolution} 247 % TODO cite Baker, Cormack, etc. 247 248 \subsection{ArgumentDirected} 249 250 251 \subsection{ParameterDirected} 252 \textbf{TODO: Richard's algorithm isn't Baker (Cormack?), disentangle from this section \ldots}. 253 The expression resolution algorithm used by the existing iteration of {CFACC} is based on Baker's\cite{Baker82} algorithm for overload resolution in Ada. 254 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. 255 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 zeroargument functions. 256 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. 257 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). 258 259 \textbf{TODO: Figure} 260 261 Baker's algorithm was designed to account for name overloading; Richard Bilson\cite{Bilson03} extended this algorithm to also handle polymorphic functions, implicit conversions \& multiple return types when designing the original \CFA compiler. 262 The core of the algorithm is a function which Baker refers to as $gen\_calls$. 263 $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. 264 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$. 265 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. 266 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. 267 If a subexpression interpretation is ambiguous, than any expression interpretation containing it will also be ambiguous. 268 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{minimalcost} interpretation of the expression as type $T$, as cheaper expressions are always chosen in preference to more expensive ones. 269 270 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). 271 If no such element can be found, there is no valid interpretation of the expression using $f_i$, while if more than one such (minimalcost) element is found than an ambiguous interpretation with the result type of $f_i$ is produced. 272 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. 273 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. 274 $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 (minimalcost) result, or if this single result is ambiguous, and valid otherwise. 275 276 In this implementation, resolution of a single toplevel 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} 277 278 \textbf{TODO: Basic Lit Review} \textit{Look at 2.4 in Richard's thesis for any possible morerecent 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} 279 \textit{CormackWright90 seems to describe a solution for the same problem, mostly focused on how to find the implicit parameters} 280 281 \section{Proposal} 248 282 249 283 \section{Completion Timeline}
Note: See TracChangeset
for help on using the changeset viewer.