source: doc/theses/aaron_moss_PhD/phd/generic-types.tex @ cf01d0b

aaron-thesisarm-ehcleanup-dtorsjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since cf01d0b was cf01d0b, checked in by Aaron Moss <a3moss@…>, 3 years ago

thesis: typo-fixing revisions from Werner, Ondrej

  • Property mode set to 100644
File size: 40.2 KB
Line 
1\chapter{Generic Types}
2\label{generic-chap}
3
4A significant shortcoming in standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms.
5Broadly speaking, there are three approaches to implement abstract data structures in C.
6One approach is to write bespoke data structures for each context in which they are needed.
7While this approach is flexible and supports integration with the C type checker and tooling, it is also tedious and error prone, especially for more complex data structures.
8A second approach is to use !void*!-based polymorphism, \eg{} the C standard library functions !bsearch! and !qsort!, which allow for the reuse of common functionality.
9However, basing all polymorphism on !void*! eliminates the type checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is otherwise unnecessary.
10A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type checked, but errors in such code may be difficult to locate and debug.
11Furthermore, writing and using preprocessor macros is unnatural and inflexible.
12Figure~\ref{bespoke-generic-fig} demonstrates the bespoke approach for a simple linked list with !insert! and !head! operations, while Figure~\ref{void-generic-fig} and Figure~\ref{macro-generic-fig} show the same example using !void*! and !#define!-based polymorphism, respectively.
13
14\begin{figure}
15        \begin{cfa}
16                #include <stdlib.h> $\C{// for malloc}$
17                #include <stdio.h>  $\C{// for printf}$
18
19                struct int_list { int value; struct int_list* next; };
20
21                void int_list_insert( struct int_list** ls, int x ) {
22                        struct int_list* node = malloc(sizeof(struct int_list));
23                        node->value = x; node->next = *ls;
24                        *ls = node;
25                }
26
27                int int_list_head( const struct int_list* ls ) { return ls->value; }
28
29                $\C[\textwidth]{// all code must be duplicated for every generic instantiation}$
30
31                struct string_list { const char* value; struct string_list* next; };
32
33                void string_list_insert( struct string_list** ls, const char* x ) {
34                        struct string_list* node = malloc(sizeof(struct string_list));
35                        node->value = x; node->next = *ls;
36                        *ls = node;
37                }
38
39                const char* string_list_head( const struct string_list* ls )
40                        { return ls->value; }
41
42                $\C[\textwidth]{// use is efficient and idiomatic}$
43
44                int main() {
45                        struct int_list* il = NULL;
46                        int_list_insert( &il, 42 );
47                        printf("%d\n", int_list_head(il));
48                       
49                        struct string_list* sl = NULL;
50                        string_list_insert( &sl, "hello" );
51                        printf("%s\n", string_list_head(sl));
52                }
53        \end{cfa}
54
55        \caption{Bespoke code for linked list implementation.} \label{bespoke-generic-fig}
56\end{figure}
57
58\begin{figure}
59        \begin{cfa}
60                #include <stdlib.h> $\C{// for malloc}$
61                #include <stdio.h>  $\C{// for printf}$
62
63                // single code implementation
64
65                struct list { void* value; struct list* next; };
66
67                $\C[\textwidth]{// internal memory management requires helper functions}$
68
69                void list_insert( struct list** ls, void* x, void* (*copy)(void*) ) {
70                        struct list* node = malloc(sizeof(struct list));
71                        node->value = copy(x); node->next = *ls;
72                        *ls = node;
73                }
74
75                void* list_head( const struct list* ls ) { return ls->value; }
76
77                $\C[\textwidth]{// helpers duplicated per type}$
78
79                void* int_copy(void* x) {
80                        int* n = malloc(sizeof(int));
81                        *n = *(int*)x;
82                        return n;
83                }
84
85                void* string_copy(void* x) { return strdup((const char*)x); }
86
87                int main() {
88                        struct list* il = NULL;
89                        int i = 42;
90                        list_insert( &il, &i, int_copy );
91                        printf("%d\n", *(int*)list_head(il));  $\C[2in]{// unsafe type cast}$
92                       
93                        struct list* sl = NULL;
94                        list_insert( &sl, "hello", string_copy );
95                        printf("%s\n", (char*)list_head(sl));  $\C[2in]{// unsafe type cast}$
96                }
97        \end{cfa}
98
99        \caption{\lstinline{void*}-polymorphic code for linked list implementation.} \label{void-generic-fig}
100\end{figure}
101
102\begin{figure}
103        \begin{cfa}
104                #include <stdlib.h> $\C{// for malloc}$
105                #include <stdio.h>  $\C{// for printf}$
106
107                $\C[\textwidth]{// code is nested in macros}$
108
109                #define list(N) N ## _list
110
111                #define list_insert(N) N ## _list_insert
112
113                #define list_head(N) N ## _list_head
114
115                #define define_list(N, T) $\C[0.25in]{ \textbackslash }$
116                        struct list(N) { T value; struct list(N)* next; }; $\C[0.25in]{ \textbackslash }$
117                        $\C[0.25in]{ \textbackslash }$
118                        void list_insert(N)( struct list(N)** ls, T x ) { $\C[0.25in]{ \textbackslash }$
119                                struct list(N)* node = malloc(sizeof(struct list(N))); $\C[0.25in]{ \textbackslash }$
120                                node->value = x; node->next = *ls; $\C[0.25in]{ \textbackslash }$
121                                *ls = node; $\C[0.25in]{ \textbackslash }$
122                        } $\C[0.25in]{ \textbackslash }$
123                        $\C[0.25in]{ \textbackslash }$
124                        T list_head(N)( const struct list(N)* ls ) { return ls->value; }
125
126                define_list(int, int); $\C[3in]{// defines int\_list}$
127                define_list(string, const char*); $\C[3in]{// defines string\_list}$
128
129                $\C[\textwidth]{// use is efficient, but syntactically idiosyncratic}$
130
131                int main() {
132                        struct list(int)* il = NULL; $\C[3in]{// does not match compiler-visible name}$
133                        list_insert(int)( &il, 42 );
134                        printf("%d\n", list_head(int)(il));
135                       
136                        struct list(string)* sl = NULL;
137                        list_insert(string)( &sl, "hello" );
138                        printf("%s\n", list_head(string)(sl));
139                }
140        \end{cfa}
141
142        \caption{Macros for generic linked list implementation.} \label{macro-generic-fig}
143\end{figure}
144
145\CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types.
146Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18} and on which this chapter is closely based.
147\CFA{} generic types integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backward compatibility with C in layout and support for separate compilation.
148A generic type can be declared in \CFA{} by placing a !forall! specifier on a !struct! or !union! declaration, and instantiated using a parenthesized list of types after the generic name.
149An example comparable to the C polymorphism examples in Figures~\ref{bespoke-generic-fig}, \ref{void-generic-fig}, and \ref{macro-generic-fig} can be seen in Figure~\ref{cfa-generic-fig}.
150
151\begin{figure}
152        \begin{cfa}
153                #include <stdlib.hfa> $\C{// for alloc}$
154                #include <stdio.h>  $\C{// for printf}$
155
156                forall(otype T) struct list { T value; list(T)* next; };
157
158                $\C[\textwidth]{// single polymorphic implementation of each function}$
159                $\C[\textwidth]{// overloading reduces need for namespace prefixes}$
160
161                forall(otype T) void insert( list(T)** ls, T x ) {
162                        list(T)* node = alloc();  $\C{// type-inferring alloc}$
163                        (*node){ x, *ls }$\C{// concise constructor syntax}$
164                        *ls = node;
165                }
166
167                forall(otype T) T head( const list(T)* ls ) { return ls->value; }
168
169                $\C[\textwidth]{// use is clear and efficient}$
170
171                int main() {
172                        list(int)* il = 0;
173                        insert( &il, 42 );  $\C{// inferred polymorphic T}$
174                        printf("%d\n", head(il));
175                       
176                        list(const char*)* sl = 0;
177                        insert( &sl, "hello" );
178                        printf("%s\n", head(sl));
179                }
180        \end{cfa}
181
182        \caption{\CFA{} generic linked list implementation.} \label{cfa-generic-fig}
183\end{figure}
184
185\section{Design}
186
187Though a number of languages have some implementation of generic types, backward compatibility with both C and existing \CFA{} polymorphism present some unique design constraints for \CFA{} generics.
188The guiding principle is to maintain an unsurprising language model for C programmers without compromising runtime efficiency.
189A key insight for this design is that C already possesses a handful of built-in generic types (\emph{derived types} in the language of the standard \cite[\S{}6.2.5]{C11}), notably pointer (!T*!) and array (!T[]!), and that user-definable generics should act similarly.
190
191\subsection{Related Work} \label{generic-related-sec}
192
193One approach to the design of generic types is that taken by \CC{} templates \cite{C++}.
194The template approach is closely related to the macro-expansion approach to C polymorphism demonstrated in Figure~\ref{macro-generic-fig}, but where the macro-expansion syntax has been given first-class language support.
195Template expansion has the benefit of generating code with near-optimal runtime efficiency, as distinct optimizations can be applied for each instantiation of the template.
196On the other hand, template expansion can also lead to significant code bloat, exponential in the worst case \cite{Haberman16}, and the costs of increased compilation time and instruction cache pressure cannot be ignored.
197The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms.
198Because a \CC{} template is not actually code, but rather a ``recipe'' to generate code, template code must be visible at its call site to be used.
199Furthermore, \CC{} template code cannot be type-checked without instantiating it, a time consuming process with no hope of improvement until \CC{} concepts \cite{C++Concepts} are standardized in \CCtwenty{}.
200C code, by contrast, only needs a function declaration to call that function or a !struct! declaration to use (by-pointer) values of that type, desirable properties to maintain in \CFA{}.
201
202Java \cite{Java8} has another prominent implementation for generic types, introduced in Java~5 and based on a significantly different approach than \CC{}.
203The Java approach has much more in common with the !void*!-polymorphism shown in Figure~\ref{void-generic-fig}; since in Java nearly all data is stored by reference, the Java approach to polymorphic data is to store pointers to arbitrary data and insert type-checked implicit casts at compile-time.
204This process of \emph{type erasure} has the benefit of allowing a single instantiation of polymorphic code, but relies heavily on Java's object model.
205To use this model, a more C-like language such as \CFA{} would be required to dynamically allocate internal storage for variables, track their lifetime, and properly clean them up afterward.
206
207Cyclone \cite{Grossman06} extends C and also provides capabilities for polymorphic functions and existential types which are similar to \CFA{}'s !forall! functions and generic types.
208Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, which is tedious and error-prone compared to \CFA{}'s implicit assertion satisfaction.
209Furthermore, Cyclone's polymorphic functions and types are restricted to abstraction over types with the same layout and calling convention as !void*!, \ie{} only pointer types and !int!.
210In the \CFA{} terminology discussed in Section~\ref{generic-impl-sec}, all Cyclone polymorphism must be dtype-static.
211While the Cyclone polymorphism design provides the efficiency benefits discussed in Section~\ref{dtype-static-sec} for dtype-static polymorphism, it is more restrictive than the more general model of \CFA{}.
212
213Many other languages include some form of generic types.
214As a brief survey, ML \cite{ML} was the first language to support parametric polymorphism, but unlike \CFA{} does not support the use of assertions and traits to constrain type arguments.
215Haskell \cite{Haskell10} combines ML-style polymorphism with the notion of type classes, similar to \CFA{} traits, but requiring an explicit association with their implementing types, unlike \CFA{}.
216Objective-C \cite{obj-c-book} is an extension to C which has had some industrial success; however, it did not support type-checked generics until recently \cite{xcode7}, and its garbage-collected, message-passing object-oriented model is a radical departure from C.
217Go \cite{Go}, and Rust \cite{Rust} are modern compiled languages with abstraction features similar to \CFA{} traits: \emph{interfaces} in Go and \emph{traits} in Rust.
218Go has implicit interface implementation and uses a ``fat pointer'' construct to pass polymorphic objects to functions, similar in principle to \CFA{}'s implicit forall parameters.
219Go does not, however, allow user code to define generic types, restricting Go programmers to the small set of generic types defined by the compiler.
220Rust has powerful abstractions for generic programming, including explicit implementation of traits and options for both separately-compiled virtual dispatch and template-instantiated static dispatch in functions.
221On the other hand, the safety guarantees of Rust's \emph{lifetime} abstraction and borrow checker impose a distinctly idiosyncratic programming style and steep learning curve; \CFA{}, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source.
222
223\subsection{\CFA{} Generics}
224
225The generic types design in \CFA{} draws inspiration from both \CC{} and Java generics, capturing useful aspects of each.
226Like \CC{} template types, generic !struct! and !union! types in \CFA{} have macro-expanded storage layouts, but, like Java generics, \CFA{} generic types can be used with separately-compiled polymorphic functions without requiring either the type or function definition to be visible to the other.
227The fact that the storage layout of any instantiation of a \CFA{} generic type is identical to that of the monomorphic type produced by simple macro replacement of the generic type parameters is important to provide consistent and predictable runtime performance, and to not impose any undue abstraction penalty on generic code.
228As an example, consider the following generic type and function:
229
230% TODO whatever the bug is with initializer-expressions not working, it affects this
231\begin{cfa}
232forall( otype R, otype S ) struct pair { R first; S second; };
233
234pair(const char*, int) with_len( const char* s ) {
235        return (pair(const char*, int)){ s, strlen(s) };
236}
237\end{cfa}
238
239In this example, !with_len! is defined at the same scope as !pair!, but it could be called from any context that can see the definition of !pair! and a declaration of !with_len!.
240If its return type were !pair(const char*, int)*!, callers of !with_len! would only need the declaration !forall(otype R, otype S) struct pair! to call it, in accordance with the usual C rules for opaque types.
241
242!with_len! is itself a monomorphic function, returning a type that is structurally identical to !struct { const char* first; int second; }!, and as such could be called from C given appropriate re-declarations and demangling flags.
243However, the definition of !with_len! depends on a polymorphic function call to the !pair! constructor, which only needs to be written once (in this case, implicitly by the compiler according to the usual \CFA{} constructor generation \cite{Schluntz17}) and can be re-used for a wide variety of !pair! instantiations.
244Since the parameters to this polymorphic constructor call are all statically known, compiler inlining can in principle eliminate any runtime overhead of this polymorphic call.
245
246\CFA{} deliberately does not support \CC{}-style partial specializations of generic types.
247A particularly infamous example in the \CC{} standard library is !vector<bool>!, which is represented as a bit-string rather than the array representation of the other !vector! instantiations.
248Complications from this inconsistency (chiefly the fact that a single bit is not addressable, unlike an array element) make the \CC{} !vector! unpleasant to use in generic contexts due to the break in its public interface.
249Rather than attempting to plug leaks in the template specialization abstraction with a detailed method interface, \CFA{} takes the more consistent position that two types with an unrelated data layout are in fact unrelated types, and should be handled with different code.
250Of course, to the degree that distinct types are similar enough to share an interface, the \CFA{} !trait! system allows such an interface to be defined, and objects of types implementing that !trait! to be operated on using the same polymorphic functions.
251
252Since \CFA{} polymorphic functions can operate over polymorphic generic types, functions over such types can be partially or completely specialized using the usual overload selection rules.
253As an example, the following generalization of !with_len! is a semantically-equivalent function which works for any type that has a !len! function declared, making use of both the ad-hoc (overloading) and parametric (!forall!) polymorphism features of \CFA{}:
254
255\begin{cfa}
256forall(otype T, otype I | { I len(T); })
257pair(T, I) with_len( T s ) {
258        return (pair(T,I)){ s, len(s) };
259}
260\end{cfa}
261
262\CFA{} generic types also support type constraints, as in !forall! functions.
263For example, the following declaration of a sorted set type ensures that the set key implements equality and relational comparison:
264
265\begin{cfa}
266forall(otype Key | { int ?==?(Key, Key); int ?<?(Key, Key); }) struct sorted_set;
267\end{cfa}
268
269These constraints are enforced by applying equivalent constraints to the compiler-generated constructors for this type.
270
271\section{Implementation} \label{generic-impl-sec}
272
273The ability to use generic types in polymorphic contexts means that the \CFA{} implementation must support a mechanism for accessing fields of generic types dynamically.
274While \CFACC{} could in principle use this same mechanism for accessing fields of generic types in monomorphic contexts as well, such an approach would throw away compiler knowledge of static types and impose an unnecessary runtime cost.
275Instead, my design for generic types in \CFACC{} distinguishes between \emph{concrete} generic types that have a fixed memory layout regardless of type parameters and \emph{dynamic} generic types that may vary in memory layout depending on their type parameters.
276
277A \emph{dtype-static} type has polymorphic parameters but is still concrete.
278Polymorphic pointers are an example of dtype-static types; given some type variable !T!, !T! is a polymorphic type, but !T*! has a fixed size and can therefore be represented by a !void*! in code generation.
279In particular, generic types where all parameters are un-!sized! (\ie{} they do not conform to the built-in !sized! trait, which is satisfied by all types the compiler knows the size and alignment of) are always concrete, as there is no possibility for their layout to vary based on type parameters of unknown size and alignment.
280More precisely, a type is concrete if and only if all of its !sized! type parameters are concrete, and a concrete type is dtype-static if any of its type parameters are (possibly recursively) polymorphic.
281To illustrate, the following code using the !pair! type from above has each use of !pair! commented with its class:
282
283% TODO constructor bugs here too
284\begin{cfa}
285//dynamic, layout varies based on T
286forall(otype T) T value$\(_1\)$( pair(const char*, T) p ) { return p.second; }
287
288// dtype-static, F* and T* are concrete but recursively polymorphic
289forall(dtype F, otype T) T value$\(_2\)$( pair(F*, T*) ) { return *p.second; }
290
291pair(const char*, int) p = {"magic", 42}; $\C[2.5in]{// concrete}$
292int i = value(p);
293pair(void*, int*) q = {0, &i}; $\C[2.5in]{// concrete}$
294i = value(q);
295double d = 1.0;
296pair(double*, double*) r = {&d, &d}; $\C[2.5in]{// concrete}$
297d = value(r);
298\end{cfa}
299
300\subsection{Concrete Generic Types}
301
302The \CFACC{} translator template-expands concrete generic types into new structure types, affording maximal inlining.
303To enable interoperation among equivalent instantiations of a generic type, \CFACC{} saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate.
304In particular, tuple types are implemented as a single compiler-generated generic type definition per tuple arity, and can be instantiated and reused according to the usual rules for generic types.
305A function declaration that accepts or returns a concrete generic type produces a declaration for the instantiated structure in the same scope, which all callers may reuse.
306As an example, the concrete instantiation for !pair(const char*, int)! is\footnote{Field name mangling for overloading purposes is omitted.\label{mangle-foot}}:
307
308\begin{cfa}
309struct _pair_conc0 { const char * first; int second; };
310\end{cfa}
311
312A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
313In the example above, the !pair(F*, T*)! parameter to !value! is such a type; its expansion is below\footref{mangle-foot}, and it is used as the type of the variables !q! and !r! as well, with casts for member access where appropriate:
314
315\begin{cfa}
316struct _pair_conc1 { void* first; void* second; };
317\end{cfa}
318
319\subsection{Dynamic Generic Types}
320
321In addition to this efficient implementation of concrete generic types, \CFA{} also offers flexibility with powerful support for dynamic generic types.
322In the pre-existing compiler design, !otype! (and all !sized!) type parameters come with implicit size and alignment parameters provided by the caller.
323The design for generic types presented here adds an \emph{offset array} containing structure-member offsets for dynamic generic !struct! types.
324A dynamic generic !union! needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
325Access to members of a dynamic structure is provided at runtime via base-displacement addressing of the structure pointer and the member offset (similar to the !offsetof! macro), moving a compile-time offset calculation to runtime.
326
327The offset arrays are statically generated where possible.
328If a dynamic generic type is passed or returned by value from a polymorphic function, \CFACC{} can safely assume that the generic type is complete (\ie{} has a known layout) at any call site, and the offset array is passed from the caller; if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C !offsetof! macro.
329As an example, the body of !value!$_2$ above is implemented as:
330
331\begin{cfa}
332_assign_T( _retval, p + _offsetof_pair[1] ); $\C[2in]{// return *p.second}$
333\end{cfa}
334
335Here, !_assign_T! is passed in as an implicit parameter from !otype T! and takes two !T*! (!void*! in the generated code\footnote{A GCC extension allows arithmetic on \lstinline{void*}, calculated as if \lstinline{sizeof(void) == 1}.}), a destination and a source, and !_retval! is the pointer to a caller-allocated buffer for the return value, the usual \CFA{} method to handle dynamically-sized return types.
336!_offsetof_pair! is the offset array passed into !value!; this array is statically generated at the call site as:
337
338\begin{cfa}
339size_t _offsetof_pair[] = {offsetof(_pair_conc0, first),  offsetof(_pair_conc0, second)};
340\end{cfa}
341
342\subsubsection{Layout Functions}
343
344In some cases, the offset arrays cannot be statically generated.
345For instance, modularity is generally provided in C by including an opaque forward declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately-compiled \texttt{.c} file.
346\CFA{} supports this pattern for generic types, implying that the caller of a polymorphic function may not know the actual layout or size of a dynamic generic type and only holds it by pointer.
347\CFACC{} automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed into a function from that function's caller.
348These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all !sized! parameters to the generic structure.
349Un-!sized! parameters are not passed because they are forbidden from being used in a context that affects layout by C's usual rules about incomplete types.
350Similarly, the layout function can only safely be called from a context where the generic type definition is visible, because otherwise the caller does not know how large to allocate the array of member offsets.
351
352The C standard does not specify a memory layout for structs, but the System V ABI \cite{SysVABI} does; compatibility with this standard is sufficient for \CFA{}'s currently-supported architectures, though future ports may require different layout-function generation algorithms.
353This algorithm, sketched below in pseudo-\CFA{}, is a straightforward mapping of consecutive fields into the first properly-aligned offset in the !struct! layout; layout functions for !union! types omit the offset array and simply calculate the maximum size and alignment over all union variants.
354Since \CFACC{} generates a distinct layout function for each type, constant-folding and loop unrolling are applied.
355
356\begin{cfa}
357forall(dtype T1, dtype T2, ... | sized(T1) | sized(T2) | ...)
358void layout(size_t* size, size_t* align, size_t* offsets) {
359        *size = 0; *align = 1;
360        // set up members
361        for ( int i = 0; i < n_fields; ++i ) {
362                // pad to alignment
363                size_t off_align = *size % alignof(field[i]);
364                if ( off_align != 0 ) { *size += alignof(field[i]) - off_align; }
365                // mark member, increase size, and fix alignment
366                offsets[i] = *size;
367                *size += sizeof(field[i]);
368                if ( *align < alignof(field[i]) ) { *align = alignof(field[i]); }
369        }
370        // final padding to alignment
371        size_t off_align = *size % *align;
372        if ( off_align != 0 ) { *size += *align - off_align; }
373}
374\end{cfa}
375
376Results of layout-function calls are cached so that they are only computed once per type per function.
377Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature, an important implementation-hiding constraint of the design.
378For instance, a function that strips duplicate values from an unsorted !list(T)! likely has a reference to the list as its only explicit parameter, but uses some sort of !set(T)! internally to test for duplicate values.
379This function could acquire the layout for !set(T)! by calling its layout function, providing as an argument the layout of !T! implicitly passed into that function.
380
381Whether a type is concrete, dtype-static, or dynamic is decided solely on the basis of the type arguments and !forall! clause type parameters.
382This design allows opaque forward declarations of generic types, \eg{} !forall(otype T) struct Box;! like in C, all uses of !Box(T)! can be separately compiled, and callers from other translation units know the proper calling conventions.
383In an alternate design, where the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static --- \eg{} !Box! could be defined with a body !{ T* p; }!, and would thus not depend on !T! for its layout.
384However, the existence of an !otype! parameter !T! means that !Box! \emph{could} depend on !T! for its layout if this definition is not visible, and preserving separate compilation (and the associated C compatibility) is a more important design metric.
385
386\subsection{Applications of Dtype-static Types} \label{dtype-static-sec}
387
388The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
389The most important such pattern is using !forall(dtype T) T*! as a type-checked replacement for !void*!, \eg{} creating a lexicographic comparison function for pairs of pointers.
390
391\begin{cfa}
392forall(dtype T)
393int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
394        int c = cmp( a->first, b->first );
395        return c ? c : cmp( a->second, b->second );
396}
397\end{cfa}
398
399Since !pair(T*, T*)! is a concrete type, there are no implicit parameters passed to !lexcmp!; hence, the generated code is identical to a function written in standard C using !void*!, yet the \CFA{} version is type-checked to ensure members of both pairs and arguments to the comparison function match in type.
400
401Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \emph{tag structures}.
402Sometimes, information is only used for type checking and can be omitted at runtime.
403In the example below, !scalar! is a dtype-static type; hence, all uses have a single structure definition containing !unsigned long! and can share the same implementations of common functions, like !?+?!.
404These implementations may even be separately compiled, unlike \CC{} template functions.
405However, the \CFA{} type checker ensures matching types are used by all calls to !?+?!, preventing nonsensical computations like adding a length to a volume.
406
407\begin{cfa}
408forall(dtype Unit) struct scalar { unsigned long value; };
409struct metres {};
410struct litres {};
411
412forall(dtype U) scalar(U) ?+?(scalar(U) a, scalar(U) b) {
413        return (scalar(U)){ a.value + b.value };
414}
415
416scalar(metres) half_marathon = { 21098 };
417scalar(litres) pool = { 2500000 };
418scalar(metres) marathon = half_marathon + half_marathon;
419`marathon + pool;` $\C[4in]{// compiler ERROR, mismatched types}$
420\end{cfa}
421
422\section{Performance Experiments} \label{generic-performance-sec}
423
424To validate the practicality of this generic type design, microbenchmark-based tests were conducted against a number of comparable code designs in C and \CC{}, first published in \cite{Moss18}.
425Since these languages are all C-based and compiled with the same compiler backend, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code.
426A more illustrative comparison measures the costs of idiomatic usage of each language's features.
427The code below shows the \CFA{} benchmark tests for a generic stack based on a singly-linked list; the test suite is equivalent for the other languages, code for which is included in Appendix~\ref{generic-bench-app}.
428The experiment uses element types !int! and !pair(short, char)! and pushes $N = 4M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack.
429
430\begin{cfa}
431#define N 4000000
432int main() {
433        int max = 0, val = 42;
434        stack( int ) si, ti;
435
436        REPEAT_TIMED( "push_int", N, push( si, val ); )
437        TIMED( "copy_int", ti{ si }; )
438        TIMED( "clear_int", clear( si ); )
439        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
440
441        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
442        stack( pair( short, char ) ) sp, tp;
443
444        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
445        TIMED( "copy_pair", tp{ sp }; )
446        TIMED( "clear_pair", clear( sp ); )
447        REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp );
448                if ( x > max ) max = x; )
449}
450\end{cfa}
451
452The four versions of the benchmark implemented are C with !void*!-based polymorphism, \CFA{} with parametric polymorphism, \CC{} with templates, and \CC{} using only class inheritance for polymorphism, denoted \CCV{}.
453The \CCV{} variant illustrates an alternative object-oriented idiom where all objects inherit from a base !object! class, a language design similar to Java 4; in particular, runtime checks are necessary to safely downcast objects.
454The most notable difference among the implementations is the memory layout of generic types: \CFA{} and \CC{} inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV{} lack such capability and, instead, must store generic objects via pointers to separately allocated objects.
455Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA{} and \CC{} provide type safety statically.
456
457Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark.
458The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted.
459All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}.
460The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency.
461I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation.
462
463\begin{figure}
464\centering
465\input{generic-timing}
466\caption[Benchmark timing results]{Benchmark timing results (smaller is better)} \label{generic-eval-fig}
467\end{figure}
468
469\begin{table}
470\caption{Properties of benchmark code} \label{generic-eval-table}
471\centering
472\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
473\begin{tabular}{lrrrr}
474                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\
475maximum memory usage (MB)                       & 10\,001       & 2\,502        & 2\,503        & 11\,253               \\
476source code size (lines)                        & 201           & 191           & 125           & 294                   \\
477redundant type annotations (lines)      & 27            & 0                     & 2                     & 16                    \\
478binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
479\end{tabular}
480\end{table}
481
482The C and \CCV{} variants are generally the slowest and have the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types in those languages; this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
483By contrast, the \CFA{} and \CC{} variants run in noticably less time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie{} no separate compilation) and greater maturity of the \CC{} compiler contributing to its lead.
484\CCV{} is slower than C largely due to the cost of runtime type checking of downcasts (implemented with !dynamic_cast!); the outlier for \CFA{}, pop !pair!, results from the complexity of the generated-C polymorphic code.
485The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA{} could more easily perform these optimizations.
486Finally, the binary size for \CFA{} is larger because of static linking with the \CFA{} prelude library, which includes function definitions for all the built-in operators.
487
488\CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort.
489The line counts in Table~\ref{generic-eval-table} include implementations of !pair! and !stack! types for all four languages for purposes of direct comparison, although it should be noted that \CFA{} and \CC{} have prewritten data structures in their standard libraries that programmers would generally use instead.
490Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA{} and \CC{} code to 39 and 42 lines, respectively.
491The difference between the \CFA{} and \CC{} line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA{} library is similar in length to the \CC{} version.
492On the other hand, due to the language shortcomings mentioned at the beginning of the chapter, C does not have a generic collections library in its standard distribution, resulting in frequent re-implementation of such collection types by C programmers.
493\CCV{} does not use the \CC{} standard template library by construction, and, in fact, includes the definition of !object! and wrapper classes for !char!, !short!, and !int! in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library.
494I justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose.
495
496Line count is a fairly rough measure of code complexity; another important factor is how much type information the programmer must specify manually, especially where that information is not type-checked.
497Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs and is much less common in \CFA{} than C, with its manually specified function pointer arguments and format codes, or \CCV{}, with its extensive use of un-type-checked downcasts, \eg{} !object! to !integer! when popping a stack.
498To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{generic-eval-table} counts the number of lines on which the known type of a variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a !sizeof!, !struct! literal, or !new! expression.
499The \CC{} benchmark uses two redundant type annotations to create new stack nodes, whereas the C and \CCV{} benchmarks have several such annotations spread throughout their code.
500The \CFA{} benchmark is able to eliminate \emph{all} redundant type annotations through use of the return-type polymorphic !alloc! function in the \CFA{} standard library.
501
502\section{Future Work}
503
504The generic types presented here are already sufficiently expressive to implement a variety of useful library types.
505However, some other features based on this design could further improve \CFA{}.
506
507The most pressing addition is the ability to have non-type generic parameters.
508C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters (\ie{} array dimension), and allowing \CFA{} users the capability to build similar types is a requested feature.
509% More exotically, the ability to have these non-type parameters depend on dynamic runtime values rather than static compile-time constants opens up interesting opportunities for type-checking problematic code patterns.
510% For example, if a collection iterator was parameterized over the pointer to the collection it was drawn from, then a sufficiently powerful static analysis pass could ensure that that iterator was only used for that collection, eliminating one source of hard-to-find bugs.
511
512The implementation mechanisms behind generic types can also be used to add new features to \CFA{}.
513One such potential feature is \emph{field assertions}, an addition to the existing function and variable assertions on polymorphic type variables.
514These assertions could be specified using this proposed syntax:
515
516\begin{cfa}
517trait hasXY(dtype T) {
518        int T.x;  $\C{// T has a field x of type int}$
519        int T.y;  $\C{// T has a field y of type int}$
520};
521\end{cfa}
522
523Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types.
524Simulating field access can already be done more flexibly in \CFA{} by declaring a trait containing an accessor function to be called from polymorphic code, but these accessor functions impose some overhead both to write and call, and directly providing field access via an implicit offset parameter would be both more concise and more efficient.
525Of course, there are language design trade-offs to such an approach, notably that providing the two similar features of field and function assertions would impose a burden of choice on programmers writing traits, with field assertions more efficient, but function assertions more general; given this open design question a decision on field assertions is deferred until \CFA{} is more mature.
526
527If field assertions are included in the language, a natural extension would be to provide a structural inheritance mechanism for every !struct! type that simply turns the list of !struct! fields into a list of field assertions, allowing monomorphic functions over that type to be generalized to polymorphic functions over other similar types with added or reordered fields, for example:
528
529\begin{cfa}
530struct point { int x, y; };  $\C{// traitof(point) is equivalent to hasXY above}$
531struct coloured_point { int x, y; enum { RED, BLACK } colour };
532
533// works for both point and coloured_point
534forall(dtype T | traitof(point)(T) )
535double hypot( T& p ) { return sqrt( p.x*p.x + p.y*p.y ); }
536\end{cfa}
537
538\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- nothing in the use of the offset arrays implies that the field offsets need to be monotonically increasing.
539
540With respect to the broader \CFA{} polymorphism design, the experimental results in Section~\ref{generic-performance-sec} demonstrate that though the runtime impact of \CFA{}'s dynamic virtual dispatch is low, it is not as low as the static dispatch of \CC{} template inlining.
541However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, it is better to target performance-sensitive code more precisely.
542Two promising approaches are an !inline! annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing a different !inline! annotation on polymorphic function definitions to instantiate a specialized version of the function for some set of types.
543These approaches are complementary and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
Note: See TracBrowser for help on using the repository browser.