Changeset 6943a987 for doc/aaron_comp_II


Ignore:
Timestamp:
Aug 29, 2016, 10:33:05 AM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
5e644d3e
Parents:
79841be (diff), 413ad05 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    r79841be r6943a987  
    9191\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.
    9292\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.
    93 The 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.
     93The new features make \CFA more powerful and expressive than C, but impose a compile-time cost, particularly in the expression resolver, which must evaluate the typing rules of a significantly more complex type-system.
    9494
    9595The 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.
     
    104104
    105105It is important to note that \CFA is not an object-oriented language.
    106 \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.
     106\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.
    107107Particularly, \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.
    108108The 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.
     
    120120\end{lstlisting}
    121121The ©identity© function above can be applied to any complete object type (or ``©otype©'').
    122 The type variable ©T© is transformed into a set of additional implicit parameters to ©identity© which encode sufficient information about ©T© to create and return a variable of that type.
     122The type variable ©T© is transformed into a set of additional implicit parameters to ©identity©, which encode sufficient information about ©T© to create and return a variable of that type.
    123123The 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.
    124124Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC virtual function calls.
    125125Determining if packaging all polymorphic arguments to a function into a virtual function table would reduce the runtime overhead of polymorphic calls is an open research question.
    126126
    127 Since 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:
     127Since bare polymorphic types do not provide a great range of available operations, \CFA provides a \emph{type assertion} mechanism to provide further information about a type:
    128128\begin{lstlisting}
    129129forall(otype T ®| { T twice(T); }®)
     
    137137\end{lstlisting}
    138138These type assertions may be either variable or function declarations that depend on a polymorphic type variable.
    139 ©four_times© can only be called with an argument for which there exists a function named ©twice© that can take that argument and return another value of the same type; a pointer to the appropriate ©twice© function is passed as an additional implicit parameter to the call to ©four_times©.
     139©four_times© can only be called with an argument for which there exists a function named ©twice© that can take that argument and return another value of the same type; a pointer to the appropriate ©twice© function is passed as an additional implicit parameter to the call of ©four_times©.
    140140
    141141Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
     
    148148The compiler accomplishes this by creating a wrapper function calling ©twice // (2)© with ©S© bound to ©double©, then providing this wrapper function to ©four_times©\footnote{©twice // (2)© could also have had a type parameter named ©T©; \CFA specifies renaming of the type parameters, which would avoid the name conflict with the type variable ©T© of ©four_times©.}.
    149149
    150 Finding 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.
     150Finding 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 \emph{in the current scope}.
    151151If 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 is examined as a candidate for its own type assertion unboundedly repeatedly.
    152152To 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 that cannot be resolved by CFA.
     
    170170forall(otype M | has_magnitude(M))
    171171M max_magnitude( M a, M b ) {
    172     M aa = abs(a), ab = abs(b);
    173     return aa < ab ? b : a;
     172    return abs(a) < abs(b) ? b : a;
    174173}
    175174\end{lstlisting}
    176175
    177176Semantically, traits are simply a named lists of type assertions, but they may be used for many of the same purposes that interfaces in Java or abstract base classes in \CC are used for.
    178 Unlike Java interfaces or \CC base classes, \CFA types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to interface implementation in Go, as opposed to the nominal inheritance model of Java and \CC.
     177Unlike Java interfaces or \CC base classes, \CFA types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to implementation of an interface in Go, as opposed to the nominal inheritance model of Java and \CC.
    179178Nominal inheritance can be simulated with traits using marker variables or functions:
    180179\begin{lstlisting}
     
    190189\end{lstlisting}
    191190
    192 Traits, however, are significantly more powerful than nominal-inheritance interfaces; firstly, due to the scoping rules of the declarations which satisfy a trait's type assertions, a type may not satisfy a trait everywhere that the type is declared, as with ©char© and the ©nominal© trait above.
    193 Secondly, traits may be used to declare a relationship between multiple types, a property which may be difficult or impossible to represent in nominal-inheritance type systems:
     191Traits, however, are significantly more powerful than nominal-inheritance interfaces; firstly, due to the scoping rules of the declarations that satisfy a trait's type assertions, a type may not satisfy a trait everywhere that the type is declared, as with ©char© and the ©nominal© trait above.
     192Secondly, traits may be used to declare a relationship among multiple types, a property that may be difficult or impossible to represent in nominal-inheritance type systems:
    194193\begin{lstlisting}
    195194trait pointer_like(®otype Ptr, otype El®) {
     
    202201};
    203202
    204 typedef list* list_iterator;
     203typedef list *list_iterator;
    205204
    206205lvalue int *?( list_iterator it ) {
     
    209208\end{lstlisting}
    210209
    211 In the example above, ©(list_iterator, int)© satisfies ©pointer_like© by the given function, and ©(list_iterator, list)© also satisfies ©pointer_like© by the built-in pointer dereference operator.
     210In the example above, ©(list_iterator, int)© satisfies ©pointer_like© by the user-defined dereference function, and ©(list_iterator, list)© also satisfies ©pointer_like© by the built-in dereference operator for pointers.
     211Given a declaration ©list_iterator it©, ©*it© can be either an ©int© or a ©list©, with the meaning disambiguated by context (\eg ©int x = *it;© interprets ©*it© as an ©int©, while ©(*it).value = 42;© interprets ©*it© as a ©list©).
    212212While a nominal-inheritance system with associated types could model one of those two relationships by making ©El© an associated type of ©Ptr© in the ©pointer_like© implementation, few such systems could model both relationships simultaneously.
    213213
    214 The flexibility of \CFA's implicit trait satisfaction mechanism provides programmers with a great deal of power, but also blocks some optimization approaches for expression resolution.
    215 The ability of types to begin to or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters could lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships.
     214The flexibility of \CFA's implicit trait-satisfaction mechanism provides programmers with a great deal of power, but also blocks some optimization approaches for expression resolution.
     215The ability of types to begin to or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters can lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships.
    216216On the other hand, the addition of a nominal inheritance mechanism to \CFA's type system or replacement of \CFA's trait satisfaction system with a more object-oriented inheritance model and investigation of possible expression resolution optimizations for such a system may be an interesting avenue of further research.
    217217
    218218\subsection{Name Overloading}
    219219In C, no more than one variable or function in the same scope may share the same name\footnote{Technically, C has multiple separated namespaces, one holding ©struct©, ©union©, and ©enum© tags, one holding labels, one holding typedef names, variable, function, and enumerator identifiers, and one for each ©struct© or ©union© type holding the field names.}, and variable or function declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration.
    220 This makes finding the proper declaration to match to a variable expression or function application a simple matter of symbol table lookup, which can be easily and efficiently implemented.
     220This restriction makes finding the proper declaration to match to a variable expression or function application a simple matter of symbol-table lookup, which can be easily and efficiently implemented.
    221221\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 variable and function names for different types common in the C standard library, as in the following example:
    222222\begin{lstlisting}
     
    229229double max = DBL_MAX;  // (4)
    230230
    231 max(7, -max);   // uses (1) and (3), by matching int type of 7
    232 max(max, 3.14); // uses (2) and (4), by matching double type of 3.14
     231max(7, -max);   // uses (1) and (3), by matching int type of the constant 7
     232max(max, 3.14); // uses (2) and (4), by matching double type of the constant 3.14
    233233
    234234max(max, -max);  // ERROR: ambiguous
    235 int m = max(max, -max); // uses (1) and (3) twice, by return type
     235int m = max(max, -max); // uses (1) once and (3) twice, by matching return type
    236236\end{lstlisting}
    237237
     
    239239
    240240\subsection{Implicit Conversions}
    241 In 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.
    242 C 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.
    243 \CFA adds to the usual arithmetic conversions rules for determining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, \eg ©int© to ©double©.
    244 
    245 The 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.
     241In addition to the multiple interpretations of an expression produced by name overloading, \CFA must support all of the implicit conversions present in C for backward compatibility, producing further candidate interpretations for expressions.
     242C does not have a 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.
     243\CFA adds to the usual arithmetic conversions rules defining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, \eg ©int© to ©double©.
     244
     245The 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.
    246246Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate.
    247 For instance, in the example in the previous subsection, ©max(max, -max)© cannot be unambiguously resolved, but ©int m = max(max, -max);© has a single minimal-cost resolution.
    248 ©int m = (int)max((double)max, -(double)max)© is also be a valid interpretation, but is not minimal-cost due to the unsafe cast from the ©double© result of ©max© to ©int© (the two ©double© casts function as type ascriptions selecting ©double max© rather than casts from ©int max© to ©double©, and as such are zero-cost).
     247For instance, in the example in the previous subsection, ©max(max, -max)© cannot be unambiguously resolved, but ©int m = max(max, -max)© has a single minimal-cost resolution.
     248While the interpretation ©int m = (int)max((double)max, -(double)max)© is also a valid interpretation, it is not minimal-cost due to the unsafe cast from the ©double© result of ©max© to ©int© (the two ©double© casts function as type ascriptions selecting ©double max© rather than casts from ©int max© to ©double©, and as such are zero-cost).
    249249
    250250\subsubsection{User-generated Implicit Conversions}
     
    252252Such a conversion system should be simple for 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.
    253253
    254 Ditchfield~\cite{Ditchfield:conversions} has laid out a framework for using polymorphic-conversion-constructor functions to create a directed acyclic graph (DAG) of conversions.
     254Ditchfield~\cite{Ditchfield:conversions} laid out a framework for using polymorphic-conversion-constructor functions to create a directed acyclic graph (DAG) of conversions.
    255255A 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.
    256 With 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.
     256With these two types of conversion arcs, separate DAGs can be created for the safe and the unsafe conversions, and conversion cost can be represented the length of the shortest path through the DAG from one type to another.
    257257\begin{figure}[h]
    258258\centering
    259259\includegraphics{conversion_dag}
    260 \caption{A portion of the implicit conversion DAG for built-in types.}
     260\caption{A portion of the implicit conversion DAG for built-in types.}\label{fig:conv_dag}
    261261\end{figure}
    262 As can be seen in the example DAG above, there are either safe or unsafe paths between each of the arithmetic types listed; the ``final'' arcs are important both to avoid creating cycles in the signed-unsigned conversions, and to disambiguate potential diamond conversions (\eg, if the ©int© to ©unsigned int© conversion was not marked final there would be two length-two paths from ©int© to ©unsigned long©, and it would be impossible to choose which one; however, since the ©unsigned int© to ©unsigned long© arc can not be traversed after the final ©int© to ©unsigned int© arc, there is a single unambiguous conversion path from ©int© to ©unsigned long©).
     262As can be seen in Figure~\ref{fig:conv_dag}, there are either safe or unsafe paths between each of the arithmetic types listed; the ``final'' arcs are important both to avoid creating cycles in the signed-unsigned conversions, and to disambiguate potential diamond conversions (\eg, if the ©int© to ©unsigned int© conversion was not marked final there would be two length-two paths from ©int© to ©unsigned long©, making it impossible to choose which one; however, since the ©unsigned int© to ©unsigned long© arc can not be traversed after the final ©int© to ©unsigned int© arc, there is a single unambiguous conversion path from ©int© to ©unsigned long©).
    263263
    264264Open research questions on this topic include:
    265265\begin{itemize}
    266266\item Can a conversion graph 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?
    267 \item Can such a graph representation can be usefully augmented to include user-defined types as well as built-in types?
    268 \item Can the graph can be efficiently represented and used in the expression resolver?
     267\item Can such a graph representation be usefully augmented to include user-defined types as well as built-in types?
     268\item Can the graph be efficiently represented and used in the expression resolver?
    269269\end{itemize}
    270270
    271271\subsection{Constructors and Destructors}
    272272Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
    273 Each 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©.
    274 This 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.
     273Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor.
     274For ©struct© types these functions each call their equivalents on each field of the ©struct©.
     275This feature 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.
    275276The following example shows the implicitly-generated code in green:
    276277\begin{lstlisting}
     
    280281};
    281282
    282 ¢void ?{}(kv *this) {
    283     ?{}(&this->key);
    284     ?{}(&this->value);
    285 }
    286 void ?{}(kv *this, kv that) {
    287     ?{}(&this->key, that.key);
    288     ?{}(&this->value, that.value);
    289 }
    290 kv ?=?(kv *this, kv that) {
    291     ?=?(&this->key, that.key);
    292     ?=?(&this->value, that.value);
     283¢void ?{}(kv *this) {  // default constructor
     284    ?{}(&(this->key));  // call recursively on members
     285    ?{}(&(this->value));
     286}
     287void ?{}(kv *this, kv that) {  // copy constructor
     288    ?{}(&(this->key), that.key);
     289    ?{}(&(this->value), that.value);
     290}
     291kv ?=?(kv *this, kv that) {  // assignment operator
     292    ?=?(&(this->key), that.key);
     293    ?=?(&(this->value), that.value);
    293294    return *this;
    294295}
    295 void ^?{}(kv *this) {
    296     ^?{}(&this->key);
    297     ^?{}(&this->value);
     296void ^?{}(kv *this) {  // destructor
     297    ^?{}(&(this->key));
     298    ^?{}(&(this->value));
    298299
    299300
     
    335336\begin{itemize}
    336337\item Since there is an implicit conversion from ©void*© to any pointer type, the highlighted expression can be interpreted as either a ©void*©, matching ©f // (1)©, or a ©box(S)*© for some type ©S©, matching ©f // (2)©.
    337 \item To determine the cost of the ©box(S)© interpretation, a type must be found for ©S© which satisfies the ©otype© implicit type assertions (assignment operator, default and copy constructors, and destructor); one option is ©box(S2)© for some type ©S2©.
     338\item To determine the cost of the ©box(S)© interpretation, a type must be found for ©S© that satisfies the ©otype© implicit type assertions (assignment operator, default and copy constructors, and destructor); one option is ©box(S2)© for some type ©S2©.
    338339\item The assignment operator, default and copy constructors, and destructor of ©box(T)© are also polymorphic functions, each of which require the type parameter ©T© to have an assignment operator, default and copy constructors, and destructor. When choosing an interpretation for ©S2©, one option is ©box(S3)©, for some type ©S3©.
    339340\item The previous step repeats until stopped, with four times as much work performed at each step.
    340341\end{itemize}
    341 This problem can occur in any resolution context where a polymorphic function that can satisfy its own type assertions is required for a possible interpretation of an expression with no constraints on its type, and is thus not limited to combinations of generic types with ©void*© conversions, though constructors for generic types often satisfy their own assertions and a polymorphic conversion such as the ©void*© conversion to a polymorphic variable can create an expression with no constraints on its type.
     342This problem can occur in any resolution context where a polymorphic function can satisfy its own type assertions is required for a possible interpretation of an expression with no constraints on its type, and is thus not limited to combinations of generic types with ©void*© conversions.
     343However, constructors for generic types often satisfy their own assertions and a polymorphic conversion such as the ©void*© conversion to a polymorphic variable is a common way to create an expression with no constraints on its type.
    342344As discussed above, the \CFA expression resolver must handle this possible infinite recursion somehow, and it occurs fairly naturally in code like the above that uses generic types.
    343345
     
    345347\CFA adds \emph{tuple types} to C, a syntactic facility for referring to lists of values anonymously or with a single identifier.
    346348An identifier may name a tuple, and a function may return one.
    347 Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap© below:
    348 \begin{lstlisting}
    349 [char, char] x = [ '!', '?' ];
    350 int x = 42;
    351 
    352 forall(otype T) [T, T] swap( T a, T b ) { return [b, a]; }
     349Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap©:
     350\begin{lstlisting}
     351[char, char] x = [ '!', '?' ];  // (1)
     352int x = 42;  // (2)
     353
     354forall(otype T) [T, T] swap( T a, T b ) { return [b, a]; }  // (3)
    353355
    354356x = swap( x ); // destructure [char, char] x into two elements of parameter list
    355357// cannot use int x for parameter, not enough arguments to swap
    356 \end{lstlisting}
    357 Tuple 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.
     358
     359void swap( int, char, char ); // (4)
     360
     361swap( x, x ); // resolved as (4) on (2) and (1)
     362// (3) on (2) and (2) is close, but the polymorphic binding makes it not minimal-cost
     363\end{lstlisting}
     364Tuple 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.
     365In the second example, the second ©x© argument can be resolved starting at the second or third parameter of ©swap©, depending which interpretation of ©x© was chosen for the first argument.
    358366
    359367\subsection{Reference Types}
    360368I have been designing \emph{reference types} for \CFA, in collaboration with the rest of the \CFA research team.
    361369Given 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.
    362 References 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.
    363 These 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, as below:
     370References preserve C's existing qualifier-dropping lvalue-to-rvalue conversion (\eg a ©const volatile int&© can be implicitly converted to a bare ©int©).
     371The 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.
     372These 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, as in:
    364373\begin{lstlisting}
    365374const int magic = 42;
     
    369378print_inc( magic ); // legal; implicitly generated code in green below:
    370379
    371 ¢int tmp = magic;¢ // copies to safely strip const-qualifier
     380¢int tmp = magic;¢ // to safely strip const-qualifier
    372381¢print_inc( tmp );¢ // tmp is incremented, magic is unchanged
    373382\end{lstlisting}
    374 These reference conversions may also chain with the other implicit type conversions.
    375 The 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.
     383These reference conversions may also chain with the other implicit type-conversions.
     384The main implication of the reference conversions for expression resolution is the multiplication of available implicit conversions, though given the restricted context reference conversions may be able to be treated efficiently as a special case of implicit conversions.
    376385
    377386\subsection{Special Literal Types}
    378387Another proposal currently under consideration for the \CFA type-system is assigning special types to the literal values ©0© and ©1©.
    379 Implicit conversions from these types 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.
     388Implicit conversions from these types 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 precisely.
    380389This approach 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.
    381390The main implication for expression resolution is that the frequently encountered expressions ©0© and ©1© may have a large number of valid interpretations.
     
    386395int somefn(char) = delete;
    387396\end{lstlisting}
    388 This feature is typically used in \CCeleven to make a type non-copyable by deleting its copy constructor and assignment operator, or forbidding some interpretations of a polymorphic function by specifically deleting the forbidden overloads.
    389 To 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.
     397This feature is typically used in \CCeleven to make a type non-copyable by deleting its copy constructor and assignment operator\footnote{In previous versions of \CC a type could be made non-copyable by declaring a private copy constructor and assignment operator, but not defining either. This idiom is well-known, but depends on some rather subtle and \CC-specific rules about private members and implicitly-generated functions; the deleted-function form is both clearer and less verbose.}, or forbidding some interpretations of a polymorphic function by specifically deleting the forbidden overloads\footnote{Specific polymorphic function overloads can also be forbidden in previous \CC versions through use of template metaprogramming techniques, though this advanced usage is beyond the skills of many programmers. A similar effect can be produced on an ad-hoc basis at the appropriate call sites through use of casts to determine the function type. In both cases, the deleted-function form is clearer and more concise.}.
     398To add a similar feature to \CFA involves including the deleted function declarations in expression resolution along with the normal declarations, but producing a compiler error if the deleted function is the best resolution.
    390399How 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.
    391400
     
    404413%TODO: look up and lit review
    405414The second area of investigation is minimizing dependencies between argument-parameter matches; the current CFA compiler attempts to match entire argument combinations against functions at once, potentially attempting to match the same argument against the same parameter multiple times.
    406 Whether the feature set of \CFA admits an expression resolution algorithm where arguments can be matched to parameters independently of other arguments in the same function application is an area of open research; polymorphic type paramters produce enough of a cross-argument dependency that the problem is not trivial.
     415Whether the feature set of \CFA admits an expression resolution algorithm where arguments can be matched to parameters independently of other arguments in the same function application is an area of open research; polymorphic type paramters produce enough cross-argument dependencies that the problem is not trivial.
    407416If cross-argument resolution dependencies cannot be completely eliminated, effective caching strategies to reduce duplicated work between equivalent argument-parameter matches in different combinations may mitigate the asymptotic defecits of the whole-combination matching approach.
    408417The final area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; if argument-parameter matches cannot be made independent, even small reductions in $i$ should yield significant reductions in the $i^{p+1}$ resolver runtime factor.
     
    412421
    413422\subsection{Argument-Parameter Matching}
    414 The 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.
     423The first axis for consideration is the 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.
    415424For programming languages without implicit conversions, argument-parameter matching is essentially the entirety of the expression resolution problem, and is generally referred to as ``overload resolution'' in the literature.
    416 All 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:
     425All 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 in Figure~\ref{fig:res_dag}:
    417426\begin{figure}[h]
    418427\centering
     
    433442\end{figure}
    434443
    435 Note 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.
     444Note that some interpretations may be part of more than one super-interpretation, as with the second $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 superexpression.
    436445
    437446\subsubsection{Argument-directed (Bottom-up)}
     
    451460A reasonable hybrid approach might take a top-down approach when the expression to be matched has a fixed type, and a bottom-up approach in untyped contexts.
    452461This approach may involve switching from one type to another at different levels of the expression tree.
    453 For instance:
     462For instance, in:
    454463\begin{lstlisting}
    455464forall(otype T)
     
    460469int x = f( f( '!' ) );
    461470\end{lstlisting}
    462 The outer call to ©f© must have a return type that is (implicitly convertable to) ©int©, so a top-down approach is used to select \textit{(1)} as the proper interpretation of ©f©. \textit{(1)}'s parameter ©x©, however, is an unbound type variable, and can thus take a value of any complete type, providing no guidance for the choice of candidate for the inner call to ©f©. The leaf expression ©'!'©, however, determines a zero-cost interpretation of the inner ©f© as \textit{(2)}, providing a minimal-cost expression resolution where ©T© is bound to ©void*©.
    463 
    464 Deciding when to switch between bottom-up and top-down resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and though finding good heuristics for which subexpressions to swich matching strategies on is an open question, one reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions.
     471the outer call to ©f© must have a return type that is (implicitly convertable to) ©int©, so a top-down approach is used to select \textit{(1)} as the proper interpretation of ©f©. \textit{(1)}'s parameter ©x©, however, is an unbound type variable, and can thus take a value of any complete type, providing no guidance for the choice of candidate for the inner call to ©f©. The leaf expression ©'!'©, however, determines a zero-cost interpretation of the inner ©f© as \textit{(2)}, providing a minimal-cost expression resolution where ©T© is bound to ©void*©.
     472
     473Deciding when to switch between bottom-up and top-down resolution to minimize wasted work in a hybrid algorithm is a necessarily heuristic process, and finding good heuristics for which subexpressions to swich matching strategies on is an open question.
     474One reasonable approach might be to set a threshold $t$ for the number of candidate functions, and to use top-down resolution for any subexpression with fewer than $t$ candidate functions, to minimize the number of unmatchable argument interpretations computed, but to use bottom-up resolution for any subexpression with at least $t$ candidate functions, to reduce duplication in argument interpretation computation between the different candidate functions.
    465475
    466476Ganzinger and Ripken~\cite{Ganzinger80} propose an approach (later refined by Pennello~\etal~\cite{Pennello80}) that uses a top-down filtering pass followed by a bottom-up filtering pass to reduce the number of candidate interpretations; they prove that for the Ada programming language a small number of such iterations is sufficient to converge to a solution for the expression resolution problem.
    467477Persch~\etal~\cite{PW:overload} developed a similar two-pass approach where the bottom-up pass is followed by the top-down pass.
    468 These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and also in that they apply both filtering heuristics to all expression nodes; \CFA's polymorphic functions and implicit conversions make the approach of filtering out invalid types taken by all of these algorithms infeasible.
     478These algorithms differ from the hybrid approach under investigation in that they take multiple passes over the expression tree to yield a solution, and that they also apply both filtering heuristics to all expression nodes; \CFA's polymorphic functions and implicit conversions make the approach of filtering out invalid types taken by all of these algorithms infeasible.
    469479
    470480\subsubsection{Common Subexpression Caching}
     
    480490\CC~\cite{ANSI98:C++} includes both name overloading and implicit conversions in its expression resolution specification, though unlike \CFA it does complete type-checking on a generated monomorphization of template functions, where \CFA simply checks a list of type constraints.
    481491The upcoming Concepts standard~\cite{C++concepts} defines a system of type constraints similar in principle to \CFA's.
    482 Cormack and Wright~\cite{Cormack90} present an algorithm which integrates overload resolution with a polymorphic type inference approach very similar to \CFA's.
     492Cormack and Wright~\cite{Cormack90} present an algorithm that integrates overload resolution with a polymorphic type inference approach very similar to \CFA's.
    483493However, their algorithm does not account for implicit conversions other than polymorphic type binding and their discussion of their overload resolution algorithm is not sufficiently detailed to classify it with the other argument-parameter matching approaches\footnote{Their overload resolution algorithm is possibly a variant of Ganzinger and Ripken~\cite{Ganzinger80} or Pennello~\etal~\cite{Pennello80}, modified to allow for polymorphic type binding.}.
    484494
     
    486496Bilson does account for implicit conversions in his algorithm, but it is unclear if the approach is optimal.
    487497His 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.
    488 This 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 does not generate implicit conversions that are not useful to match the containing function.
    489 Calculating implicit conversions on parameters pairs naturally with a top-down approach to expression resolution, though it can also be used in a bottom-up approach, as Bilson demonstrates.
     498This 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; however, this approach does not generate implicit conversions that are not useful to match the containing function.
    490499
    491500\subsubsection{On Arguments}
    492501Another approach is to generate a set of possible implicit conversions for each set of interpretations of a given argument.
    493502This approach has the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, never finds more than one interpretation of the argument with a given type, and re-uses calculation of implicit conversions between function candidates.
    494 On the other hand, this approach may unncessarily generate argument interpretations that never match any parameter, wasting work.
    495 Further, 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.
    496 Calculating implicit conversions on arguments is a viable approach for bottom-up expression resolution, though it may be difficult to apply in a top-down approach due to the presence of a target type for the expression interpretation.
     503On the other hand, this approach may unnecessarily generate argument interpretations that never match any parameter, wasting work.
     504Furthermore, 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.
    497505
    498506\subsection{Candidate Set Generation}
    499 All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
    500 However, given that the top-level expression interpretation that is ultimately chosen is the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work.
    501 Under the assumption that that programmers 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 next higher-cost argument interpretations.
     507All the algorithms discussed to this point generate the complete set of candidate argument interpretations before attempting to match the containing function-call expression.
     508However, given that the top-level expression interpretation that is ultimately chosen is the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is wasted work.
     509Under the assumption that programmers 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 next higher-cost argument interpretations.
    502510
    503511\subsubsection{Eager}
     
    563571This comparison closes Baker's open research question, as well as potentially improving Bilson's \CFA compiler.
    564572
    565 Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype is being developed which acts on a simplified input language encapsulating the essential details of the \CFA type-system\footnote{Note this simplified input language is not a usable programming language.}.
     573Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype is being developed that acts on a simplified input language encapsulating the essential details of the \CFA type-system\footnote{Note this simplified input language is not a usable programming language.}.
    566574Multiple variants of this resolver prototype will be implemented, each encapsulating a different expression resolution variant, sharing as much code as feasible.
    567575These 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.
     
    571579As an example, there are currently multiple open proposals for how implicit conversions should interact with polymorphic type binding in \CFA, each with distinct levels of expressive power; if the resolver prototype is modified to support each proposal, the optimal algorithm for each proposal can be compared, providing an empirical demonstration of the trade-off between expressive power and compiler runtime.
    572580
    573 This 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.
     581This proposed project should provide valuable data on how to implement a performant compiler for programming languages such as \CFA with powerful static type-systems, specifically targeting the feature interaction between name overloading and implicit conversions.
    574582This work is not limited in applicability to \CFA, but may also be useful for supporting efficient compilation of the upcoming Concepts standard~\cite{C++concepts} for \CC template constraints, for instance.
    575583
Note: See TracChangeset for help on using the changeset viewer.