source: doc/theses/aaron_moss/phd/background.tex @ 7ff01ff

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 7ff01ff was 7ff01ff, checked in by Aaron Moss <a3moss@…>, 6 years ago

Minor tweaks to thesis

  • Property mode set to 100644
File size: 20.1 KB
Line 
1\chapter{\CFA{}}
2
3\CFA{} adds a number of features to C, some of them providing significant increases to the expressive power of the language, but all designed to maintain the existing procedural programming paradigm of C and to be as orthogonal as possible to each other.
4To provide background for the contributions in subsequent chapters, this chapter provides a summary of the features of \CFA{} at the time this work was conducted.
5
6The core design of \CFA{} is laid out in Glen Ditchfield's 1992 PhD thesis, \emph{Contextual Polymorphism}\cite{Ditchfield92}; in that thesis, Ditchfield presents the theoretical underpinnings of the \CFA{} polymorphism model.
7Building on Ditchfield's design for contextual polymorphism as well as KW-C\cite{Buhr94a}, an earlier set of (largely syntactic) extensions to C, Richard Bilson\cite{Bilson03} built the first version of the \CFA{} compiler, \CFACC{}, in the early 2000's.
8This early \CFACC{} provided basic functionality, but incorporated a number of poor algorithmic choices due to a rushed implementation time frame, and as such lacked the runtime performance required for practical use; this thesis is substantially concerned with rectifying those deficits.
9
10The \CFA{} project was revived in 2015 with the intention of building a production-ready language and compiler; at the time of this writing, both \CFA{} and \CFACC{} have been under active development continuously since.
11As this development has been proceeding concurrently with the work described in this thesis, the state of \CFA{} has been somewhat of a moving target; however, Moss~\etal\cite{Moss18} provides a reasonable summary of the current design.
12Notable features added during this period include generic types (Chapter~\ref{generic-chap}), constructors and destructors\cite{Schluntz17}, improved support for tuples\cite{Schluntz17}, reference types\cite{Moss18}, first-class concurrent and parallel programming support\cite{Delisle18}, as well as numerous pieces of syntactic sugar and the start of an idiomatic standard library\cite{Moss18}.
13
14\section{\CFA{} Features}
15
16The selection of features presented in this chapter are chosen to elucidate the design constraints of the work presented in this thesis.
17In some cases the interactions of multiple features make this design 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.
18
19\subsection{Procedural Paradigm}
20
21It is important to note that \CFA{} is not an object-oriented language.
22This is a deliberate choice intended to maintain the applicability of the mental model and language idioms already possessed by C programmers.
23This choice is in marked contrast to \CC{}, which, though it has backward-compatibility with C on the source code level, is a much larger and more complex language, and requires extensive developer re-training before they can write idiomatic, efficient code in \CC{}'s object-oriented paradigm.
24
25\CFA{} does have a system of implicit type conversions derived from C's ``usual arithmetic 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.
26Particularly, \CFA{} has no concept of \emph{subclass}, and thus no need to integrate an inheritance-based form of polymorphism with its parametric and overloading-based polymorphism.
27The graph structure of the \CFA{} type conversions is also markedly different than an inheritance hierarchy; it has neither a top nor a bottom type, and does not satisfy the lattice properties typical of inheritance hierarchies.
28
29Another aspect of \CFA{}'s procedural paradigm is that it retains C's translation-unit-based encapsulation model, rather than class-based encapsulation such as in \CC{}.
30This choice implies that that separate compilation must be maintained to allow headers to act as an encapsulation boundary, rather than the header-only libraries used by \CC{} templates.
31
32\subsection{Name Overloading} \label{overloading-sec}
33
34In 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 \lstinline{struct}, \lstinline{union}, and \lstinline{enum} tags, one holding labels, one holding \lstinline{typedef} names, variable, function, and enumerator identifiers, and one for each \lstinline{struct} and \lstinline{union} type holding the field names\cit{}.}, and variable or function declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration.
35This 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.
36\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:
37
38\begin{cfa}
39#include <limits.h>
40
41const int max = INT_MAX;  $\C[1.75in]{// (1)}$
42const double max = DBL_MAX;  $\C[1.75in]{// (2)}$
43int max(int a, int b) { return a < b ? b : a; }  $\C[1.75in]{// (3)}$
44double max(double a, double b) { return a < b ? b : a; }  $\C[1.75in]{// (4)}$
45
46max( 7, -max );  $\C[3.75in]{// uses (3) and (1), by matching int from 7}$
47max( max, 3.14 );  $\C[3.75in]{// uses (4) and (2), by matching double from 3.14}$
48max( max, -max );  $\C[3.75in]{// ERROR, ambiguous}$
49int m = max( max, -max );  $\C[3.75in]{// uses (3) and (1) twice, by matching return type}$
50\end{cfa}
51
52While the wisdom of giving both the maximum value of a type and the function to take the maximum of two values the same name is debatable, \eg{} some developers may prefer !MAX! for the former, the guiding philosophy of \CFA{} is ``describe, don't prescribe'' --- we prefer to trust programmers with powerful tools, and there is no technical reason to restrict overloading between variables and functions.
53However, the expressivity of \CFA{}'s name overloading has the consequence that simple table lookup is insufficient to match identifiers to declarations, and a type-matching algorithm must be part of expression resolution.
54
55\subsubsection{Operator Overloading}
56
57C does allow name overloading in one context: operator overloading.
58From the perspective of the type system, there is nothing special about operators as opposed to other functions, nor is it desirable to restrict the clear and readable syntax of operators to only the built-in types.
59For these reasons, \CFA{} also allows overloading of operators by writing specially-named functions where !?! stands in for the operands\footnote{This example uses \CFA{}'s reference types, described in Section~\ref{type-features-sec}}:
60
61\begin{cfa}
62struct counter { int x; };
63
64counter& `++?`(counter& c) { ++c.x; return c; }  $\C{// pre-increment}$
65counter `?++`(counter& c) {  $\C{// post-increment}$
66        counter tmp = c; ++c; return tmp;
67}
68bool `?<?`(const counter& a, const counter& b) {  $\C{// comparison}$
69        return a.x < b.x;
70}
71\end{cfa}
72
73Together, \CFA{}'s backward-compatibility with C and the inclusion of this operator overloading feature imply that \CFA{} must select among function overloads using a method compatible with C's ``usual arithmetic conversions''\cit{}, so as to present user programmers with only a single set of overloading rules.
74
75\subsection{Polymorphic Functions}
76
77The most significant feature \CFA{} adds is parametric-polymorphic functions.
78Such functions are written using a !forall! clause (which gives the language its name):
79
80\begin{cfa}
81`forall(otype T)`
82T identity(T x) { return x; }
83\end{cfa}
84
85The !identity! function above can be applied to any complete object type (or ``!otype!'').
86The 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.
87\CFA{} passes the size and alignment of the type represented by an !otype! parameter, as well as a default constructor, copy constructor, assignment operator, and destructor.
88Types which do not have one or more of these operators visible cannot be bound to !otype! parameters.
89In this design, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; experiments have shown this overhead to be similar to \CC{} virtual function calls. \TODO{rerun experiments, possibly look at vtable variant}
90
91One benefit of this design is that it allows polymorphic functions to be separately compiled.
92The forward declaration !forall(otype T) T identity(T);! uniquely defines a single callable function, which may be implemented in a different file.
93The fact that there is only one implementation of each polymorphic function also reduces compile times relative to the template-expansion approach taken by \CC{}, as well as reducing binary sizes and runtime pressure on instruction cache at by re-using a single version of each function.
94
95\subsubsection{Type Assertions}
96
97Since 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:
98
99\begin{cfa}
100forall(otype T `| { T twice(T); }`)
101T four_times(T x) { return twice( twice(x) ); }
102double twice(double d) { return d * 2.0; }  $\C[2.75in]{// (1)}$
103
104double ans = four_times( 10.5 );  $\C[2.75in]{// T bound to double, ans == 42.0}$
105\end{cfa}
106
107These type assertions may be either variable or function declarations that depend on a polymorphic type variable.
108!four_times! may 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 function is passed as an additional implicit parameter of the call to !four_times!.
109
110Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
111For instance, !twice! could have been defined like this:
112
113\begin{cfa}
114forall(otype S | { S ?+?(S, S); })
115S twice(S x) { return x + x; }  $\C[2.75in]{// (2)}
116\end{cfa}
117
118This version of !twice! works for any type !S! that has an addition operator defined for it, and it could be used to satisfy the type assertion on !four_times!.
119\CFACC{} accomplishes this by creating a wrapper function calling !twice // (2)! with !S! bound to !double!, then providing this wrapper function to !four_times!\footnote{\lstinline{twice // (2)} could also have had a type parameter named \lstinline{T}; \CFA{} specifies renaming of the type parameters, which would avoid the name conflict with the type variable \lstinline{T} of \lstinline{four_times}}.
120
121Finding 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}.
122If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that that function is examined as a candidate for its own type assertion unboundedly repeatedly.
123To avoid such infinite loops, \CFACC{} 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 \CFACC{}.
124\TODO{Update this with final state} One contribution made in the course of this thesis was modifying \CFACC{} to use the more flexible expression resolution algorithm for assertion matching, rather than the previous simpler approach of unification on the types of the functions.
125
126\subsubsection{Deleted Declarations}
127
128Particular type combinations can be exempted from matching a given polymorphic function through use of a \emph{deleted function declaration}:
129
130\begin{cfa}
131int somefn(char) = void;
132\end{cfa}
133
134This feature is based on a \CCeleven{} feature typically used 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.}.
135Deleted function declarations are implemented in \CFACC{} by adding them to the symbol table as usual, but with a flag set that indicates that the function is deleted.
136If this deleted declaration is selected as the unique minimal-cost interpretation of an expression than an error is produced. \TODO{Check this is implemented at print.}
137
138\subsubsection{Traits}
139
140\CFA{} provides \emph{traits} as a means to name a group of type assertions, as in the example below\footnote{This example uses \CFA{}'s reference types, constructors, and zero type, described in Section~\ref{type-features-sec}.}:
141
142\begin{cfa}
143`trait has_magnitude(otype T)` {
144        bool ?<?(T, T)$\C[4in]{// comparison operator}$
145        T -?(T)$\C[4in]{// negation operator}$
146        void ?{}(T&, zero_t)$\C[4in]{// constructor from 0}$
147};
148
149forall(otype M | `has_magnitude(M)`)
150M abs(M m) { return m < (M){0} ? -m : m; }
151
152forall(otype M | `has_magnitude(M)`)
153M max_magnitude(M a, M b) { return abs(a) < abs(b) ? b : a; }
154\end{cfa}
155
156Semantically, traits are simply a named list 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.
157Unlike 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 a structural inheritance, similar to interface implementation in Go, as opposed to the nominal inheritance model of Java and \CC{}.
158Nominal inheritance can be simulated in \CFA{} using marker variables in traits:
159
160\begin{cfa}
161trait nominal(otype T) {
162        `T is_nominal;`
163};
164
165int is_nominal;  $\C{// int now satisfies nominal}$
166{
167        char is_nominal;  $\C{// char only satisfies nominal in this scope}$
168}
169\end{cfa}
170
171Traits, 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 that type is declared, as with !char! and the !nominal! trait above.
172Secondly, because \CFA{} is not object-oriented and types do not have a closed set of methods, existing C library types can be extended to implement a trait simply by writing the requisite functions.
173Finally, 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\footnote{This example uses \CFA{}'s reference types, described in Section~\ref{type-features-sec}.}:
174
175\begin{cfa}
176trait pointer_like(`otype Ptr, otype El`) {
177        El& *?(Ptr)$\C{Ptr can be dereferenced to El}$
178};
179
180struct list {
181        int value;
182        list* next; $\C{may omit struct on type names}$
183};
184
185typedef list* list_iterator;
186
187int& *?(list_iterator it) {
188        return it->value;
189}
190\end{cfa}
191
192In 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.
193Given 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 !int!, while !(*it).value = 42;! interprets !*it! as !list!).
194While 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.
195
196The 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.
197The ability of types to begin 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.
198
199\subsection{Implicit Conversions}
200
201In addition to the multiple interpretations of an expression produced by name overloading and polymorphic functions, for backward compatibility \CFA{} must support all of the implicit conversions present in C, producing further candidate interpretations for expressions.
202As mentioned above, C does not have an inheritance hierarchy of types, but the C standard's rules for the ``usual arithmetic conversions''\cit{} define which of the built-in tyhpes are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type.
203\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!.
204One contribution of this thesis, discussed in Section \TODO{add to resolution chapter}, is a number of refinements to this cost model to more efficiently resolve polymorphic function calls.
205
206The expression resolution problem which is the focus of Chapter~\ref{resolution-chap} 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.
207While semantically valid \CFA{} code always has such a unique minimal-cost interpretation, \CFACC{} must also be able to detect and report as errors expressions which have either no interpretation or multiple ambiguous minimal-cost interpretations.
208Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate.
209For instance, in the example in Section~\ref{overloading-sec}, !max(max, -max)! cannot be unambiguously resolved, but !int m = max(max, -max)! has a single minimal-cost resolution.
210While 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 the !int!\footnote{The two \lstinline{double} casts function as type ascriptions selecting \lstinline{double max} rather than casts from \lstinline{int max} to \lstinline{double}, and as such are zero-cost.}.
211These contextual effects make the expression resolution problem for \CFA{} both theoretically and practically difficult, but the observation driving the work in Chapter~\ref{resolution-chap} is that of the many top-level expressions in a given program, most will likely be straightforward and idiomatic so that programmers writing and maintaining the code can easily understand them; it follows that effective heuristics for common cases can bring down compiler runtime enough that a small proportion of harder-to-resolve expressions should not increase compiler runtime or memory usage inordinately.
212
213\subsection{Type Features} \label{type-features-sec}
214
215\subsubsection{Reference Types}
216
217% TODO mention contribution on reference rebind
218
219\subsubsection{Lifetime Management}
220
221\subsubsection{0 and 1 Literals}
Note: See TracBrowser for help on using the repository browser.