# source:doc/aaron_comp_II/comp_II.tex@0318c7a

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

Added sections on constructors and destructors, generic types to comp II draft

• Property mode set to 100644
File size: 16.0 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{\Huge
46\vspace*{1in}
47Efficient Type Resolution in \CFA \\
48\vspace*{0.25in}
49\huge
50PhD Comprehensive II Research Proposal
51\vspace*{1in}
52}
53
54\author{\huge
55\vspace*{0.1in}
56Aaron Moss \\
57\Large Cheriton School of Computer Science \\
58\Large University of Waterloo
59}
60
61\date{
62\today
63}
64
65%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
66
67\begin{document}
69% changed after setting pagestyle
72\pagenumbering{roman}
73\linenumbers                                            % comment out to turn off line numbering
74
75\maketitle
76\thispagestyle{empty}
77
78\clearpage
79\thispagestyle{plain}
80\pdfbookmark[1]{Contents}{section}
81\tableofcontents
82
83\clearpage
84\thispagestyle{plain}
85\pagenumbering{arabic}
86
87\section{Introduction}
88
89\CFA\footnote{Pronounced C-for-all'', and written \CFA, 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.
90Features added to C by \CFA include name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others.
91These features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost to implement, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type system.
92The primary goal of this proposed research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into \Index*{CFA-CC}, the \CFA reference compiler.
93Secondary 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.
94The experimental performance-testing architecture for resolution algorithms will also be used to determine the compile-time cost of adding such new features to the \CFA type system.
95
96\section{\CFA}
97
98To 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) which affect this algorithm.
99In some cases the interactions of multiple features make expression resolution a significantly more complex problem than any individual feature would; in others a feature which does not by itself add any complexity to expression resolution will trigger previously rare edge cases much more frequently.
100
101\subsection{Polymorphic Functions}
102The most significant feature \CFA adds is parametric-polymorphic functions.
103Such functions are written using a ©forall© clause, the feature that gave the language its name:
104\begin{lstlisting}
105forall(otype T)
106T identity(T x) {
107    return x;
108}
109
110int forty_two = identity(42); // T is bound to int, forty_two == 42
111\end{lstlisting}
112The ©identity© function above can be applied to any complete object type (or ©otype©'').
114The 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 \& destructor.
115
116Since 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:
117\begin{lstlisting}
118forall(otype T | { T twice(T); })
119T four_times(T x) {
120    return twice( twice(x) );
121}
122
123double twice(double d) { return d * 2.0; } // (1)
124
125double magic = four_times(10.5); // T is bound to double, uses (1) to satisfy type assertion
126\end{lstlisting}
127These type assertions may be either variable or function declarations which depend on a polymorphic type variable.
129
130Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
132\begin{lstlisting}
133forall(otype S | { S ?+?(S, S); })
134S twice(S x) { return x + x; }  // (2)
135\end{lstlisting}
138
139Finding 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.
140If 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.
141To avoid infinite loops, the current \Index*{CFA-CC} compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \Index*[C++]{\CC} compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by {CFA-CC}.
142One 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 make a more precise judgement of when further type assertion satisfaction recursion will not produce a well-typed expression.
143
145In 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.
146This 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.
147\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:
148\begin{lstlisting}
149int three = 3;
150double three = 3.0;
151
152int thrice(int i) { return i * three; } // uses int three
153double thrice(double d) { return d * three; } // uses double three
154
155// thrice(three); // ERROR: ambiguous
156int nine = thrice(three);    // uses int thrice and three, based on return type
157double nine = thrice(three); // uses double thrice and three, based on return type
158\end{lstlisting}
159
160The 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.
161
162\subsection{Implicit Conversions}
163In 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.
164C 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.
166The 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.
167
168\subsubsection{User-generated Implicit Conversions}
169One possible additional feature to \CFA included in this research proposal is \emph{user-generated implicit conversions}.
170Such 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.
171
172Glen Ditchfield \textbf{TODO CITE} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions.
173A 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.
174With 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.
175Open 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.
176
177\subsection{Constructors \& Destructors}
178Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
179Each 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.
180This 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.
181
182\subsection{Generic Types}
183The author has added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
184A 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:
185\begin{lstlisting}
186forall(otype R, otype S) struct pair {
187    R first;
188    S second;
189};
190
191forall(otype T)
192T value( pair(const char*, T) *p ) { return p->second; }
193
194pair(const char*, int) p = { "magic", 42 };
195int magic = value( &p );
196\end{lstlisting}
197For \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.
198The default-generated constructors, destructor \& assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
199
200Aside from giving users the ability to create more parameterized types than just the built-in pointer, array \& 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:
201\begin{itemize}
202\item A polymorphic implicit conversion (such as the built-in conversion from ©void*© to any other pointer type) applied to an expression can produce an expression of any type.
203\item If we attempt to use a generic type with ©otype© parameters (such as ©box© above) for this type, the ©otype© parameters on the constructors, \etc will also need to be resolved, and will have no constraints on what they may be.
204\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.
205\end{itemize}
206As 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.
207
208\subsection{Multiple Return Values}
209
210\subsection{Reference Types}
211% TODO discuss rvalue-to-lvalue conversion here
212
213\subsection{Literal Types}
214% TODO talk about zero_t, one_t here, implication that some common expressions will have many outbound implicit conversions
215
216\subsection{Deletable Functions}
217
218\section{Expression Resolution}
219% TODO cite Baker, Cormack, etc.
220
221\subsection{Symbol Table}
222% TODO not sure this is sufficiently novel, but it is an improvement to CFA-CC
223
224\section{Completion Timeline}
225
226\section{Conclusion}
227
228\newpage
229
230\bibliographystyle{plain}
231\bibliography{cfa}
232
233