Changeset 5553a7b

Timestamp:

Jul 20, 2016, 12:25:50 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

fd603d8

Parents:

0b1376f

Message:

Added name overloading and implicit conversions sections to Comp II

File:

• doc/aaron_comp_II/comp_II.tex (modified) (1 diff)

doc/aaron_comp_II/comp_II.tex

@@ -145 +145 @@
 In 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.  
 This 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. 
-\CFA, on the other hand, allows overloading of variable and function names % TODO talk about uses for this 
+\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:
+\begin{lstlisting}
+int three = 3;
+double three = 3.0;
+
+int thrice(int i) { return i * three; } // uses int three
+double thrice(double d) { return d * three; } // uses double three
+
+// thrice(three); // ERROR: ambiguous
+int nine = thrice(three);    // uses int thrice and three, based on return type
+double nine = thrice(three); // uses double thrice and three, based on return type
+\end{lstlisting}
+
+The 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.
 
 \subsection{Implicit Conversions}
-% TODO also discuss possibility of user-generated implicit conversions here
+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. 
+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. 
+\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, {e.g.} ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, {e.g.} ©int© to ©double©. 
+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, implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression, and which subexpression interpretation is minimal-cost may be disambiguated by context.
+
+\subsubsection{User-generated Implicit Conversions}
+One possible additional feature to \CFA included in this research proposal is \emph{user-generated implicit conversions}. 
+Such 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. 
+
+Glen Ditchfield \textbf{TODO CITE} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions. 
+A 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. 
+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. 
+Open 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.
 
 \subsection{Generic Types}