Changeset a332d432


Ignore:
Timestamp:
Oct 4, 2018, 3:52:45 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer
Children:
a72b240
Parents:
a32346b
Message:

Added to related work, implementation, and future work for generic types chapter

Location:
doc/theses/aaron_moss_PhD/phd
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/aaron_moss_PhD/phd/generic-types.tex

    ra32346b ra332d432  
    179179\subsection{Related Work}
    180180
    181 One approach to the design of generic types is that taken by \CC{} templates\cit{}.
     181One approach to the design of generic types is that taken by \CC{} templates\cite{C++}.
    182182The 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.
    183183Template expansion has the benefit of generating code with near-optimal runtime efficiency, as distinct optimizations can be applied for each instantiation of the template.
     
    185185The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms.
    186186Because a \CC{} template is not actually code, but rather a sort of ``recipe'' to generate code, template code must be visible at its call site to be used.
     187Furthermore, \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{}.
    187188C code, by contrast, only needs a !struct! or function declaration to call that function or use (by-pointer) values of that type, a desirable property to maintain for \CFA{}.
    188189
    189 Java\cit{} has another prominent implementation for generic types, based on a significantly different approach than \CC{}.
     190Java\cite{Java8} has another prominent implementation for generic types, introduced in Java~5 and based on a significantly different approach than \CC{}.
    190191The 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.
    191192This process of \emph{type erasure} has the benefit of allowing a single instantiation of polymorphic code, but relies heavily on Java's object model and garbage collector.
    192193To 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.
    193194
    194 \TODO{Talk about Go, maybe Rust, Swift, etc. as well; specifically mention ``fat pointer'' polymorphism}
    195 
    196 \TODO{Talk about Cyclone as well, and why my generics are more powerful}
     195Cyclone\cite{Grossman06} is another language extending C, and also provides capabilities for polymorphic functions and existential types, similar to \CFA{}'s !forall! functions and generic types.
     196Cyclone 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.
     197Furthermore, 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!.
     198In the \CFA{} terminology discussed in Section~\ref{generic-impl-sec}, all Cyclone polymorphism must be dtype-static.
     199While 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{}.
     200
     201Many other languages include some form of generic types.
     202As a brief survey, ML\cite{ML} was the first language to support parameteric polymorphism, but unlike \CFA{} does not support the use of assertions and traits to constrain type arguments.
     203Haskell\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{}.
     204Objective-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 it's garbage-collected, message-passing object-oriented model is a radical departure from C.
     205Go\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.
     206Go has implicit interface implementation and uses a ``fat pointer'' construct to pass polymorphic objects to functions, similar in principle to \CFA{}'s implicit forall paramters.
     207Go does not, however, allow user code to define generic types, restricting Go programmers to the small set of generic types defined by the compiler.
     208Rust has powerful abstractions for generic programming, including explicit implemenation of traits and options for both separately-compiled virtual dispatch and template-instantiated static dispatch in functions.
     209On 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.
    197210
    198211\subsection{\CFA{} Generics}
     
    212225
    213226In 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!.
    214 If its return type was !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.
     227If its return type was !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.
    215228
    216229!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 an appropriate redeclaration and demangling flags.
     
    234247\end{cfa}
    235248
    236 \section{Implementation}
    237 
    238 % forall constraints on struct/union constrain default constructor (TODO check with Rob)
    239 
    240 % TODO discuss layout function algorithm, application to separate compilation
    241 % TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation (actually no, you need to be able to see the type for it to be sized)
    242 
    243 % mention that tuples are implemented on top of a per-arity generic type
    244 
    245 \section{Performance Experiments}
    246 
    247 % TODO pull benchmarks from Moss et al.
     249\CFA{} generic types also support the type constraints from !forall! functions.
     250For example, the following declaration of a sorted set type ensures that the set key implements equality and relational comparison:
     251
     252\begin{cfa}
     253forall(otype Key | { int ?==?(Key, Key); int ?<?(Key, Key); }) struct sorted_set;
     254\end{cfa}
     255
     256These constraints are implemented by applying equivalent constraints to the compiler-generated constructors for this type.
     257
     258\section{Implementation} \label{generic-impl-sec}
     259
     260The ability to use generic types in polymorphic contexts means that the \CFA{} implementation in \CFACC{} must support a mechanism for accessing fields of generic types dynamically at runtime.
     261While \CFACC{} could in principle use this same mechanism for accessing fields of all generic types, such an approach would throw away compiler knowledge of static types and impose an unnecessary runtime cost, limiting the utility of the generic type design.
     262Instead, my design for generic type support 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.
     263A \emph{dtype-static} type has polymorphic parameters but is still concrete.
     264Polymorphic 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.
     265In particular, generic types where all parameters are un-!sized! (\ie{} they do not conform to the built-in !sized! trait because the compiler does not know their size and alignment) are always concrete, as there is no possibility for their layout to vary based on type parameters of unknown size and alignment.
     266More 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.
     267To illustrate, the following code using the !pair! type from above \TODO{test this} has each use of !pair! commented with its class:
     268
     269\begin{cfa}
     270//dynamic, layout varies based on T
     271forall(otype T) T value( pair(const char*, T) p ) { return p.second; }
     272
     273// dtype-static, F* and T* are concrete but recursively polymorphic
     274forall(dtype F, otype T) T value( pair(F*, T*) ) { return *p.second; }
     275
     276pair(const char*, int) p = {"magic", 42}; $\C[2.5in]{// concrete}$
     277int i = value(p);
     278pair(void*, int*) q = {0, &p.second}; $\C[2.5in]{// concrete}$
     279i = value(q);
     280double d = 1.0;
     281pair(double*, double*) r = {&d, &d}; $\C[2.5in]{// concrete}$
     282d = value(r);
     283\end{cfa}
     284
     285\subsection{Concrete Generic Types}
     286
     287The \CFACC{} translator template expands concrete generic types into new structure types, affording maximal inlining.
     288To 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.
     289In 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.
     290A 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.
     291As an example, the concrete instantiation for !pair(const char*, int)! is\footnote{This omits the field name mangling performed by \CFACC{} for overloading purposes.\label{mangle-foot}}
     292
     293\begin{cfa}
     294struct _pair_conc0 { const char * first; int second; };
     295\end{cfa}
     296
     297A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
     298In 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.
     299
     300\begin{cfa}
     301struct _pair_conc1 { void* first; void* second; };
     302\end{cfa}
     303
     304\subsection{Dynamic Generic Types}
     305
     306In addition to this efficient implementation of concrete generic types, \CFA{} also offers flexibility with powerful support for dynamic generic types.
     307In the pre-existing compiler design, !otype! (and all !sized!) type parameters come with implicit size and alignment parameters provided by the caller.
     308The design for generic types presented here adds an \emph{offset array} containing structure-member offsets for dynamic generic !struct! types.
     309A dynamic generic !union! needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
     310Access to members of a dynamic structure is provided at runtime via base displacement addressing the structure pointer and the member offset (similar to the !offsetof! macro), moving a compile-time offset calculation to runtime.
     311
     312the offset arrays are statically generated where possible.
     313If 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.
     314As an example, the body of the second !value! function above is implemented as
     315
     316\begin{cfa}
     317_assign_T( _retval, p + _offsetof_pair[1] ); $\C[2in]{// return *p.second}$
     318\end{cfa}
     319
     320Here, !_assign_T! is passed in as an implicit parameter from !otype T! and takes two !T*! (!void*! in the generated code), 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.
     321!_offsetof_pair! is the offset array passed into !value!; this array is generated at the call site as
     322
     323\begin{cfa}
     324size_t _offsetof_pair[] = {offsetof(_pair_conc0, first),  offsetof(_pair_conc0, second)};
     325\end{cfa}
     326
     327\subsubsection{Layout Functions}
     328
     329In some cases, the offset arrays cannot be statically generated.
     330For 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.
     331\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.
     332\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 functions's caller.
     333These 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.
     334Un!sized! parameters not passed because they are forbidden from being used in a context that affects layout by C's usual rules about incomplete types.
     335Similarly, the layout function can only safely be called from a context where the generic type definition is visible, because otherwise the caller will not know how large to allocate the array of member offsets.
     336
     337The C standard does not specify a memory layout for structs, but the POSIX ABI for x86\cit{} does; this memory layout is common for C implementations, but is a platform-specific issue for porting \CFA{}.
     338This 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.
     339Since \CFACC{} generates a distinct layout function for each type, constant-folding and loop unrolling are applied.
     340
     341\begin{cfa}
     342forall(dtype T1, dtype T2, ... | sized(T1) | sized(T2) | ...)
     343void layout(size_t* size, size_t* align, size_t* offsets) {
     344        // initialize values
     345        *size = 0; *align = 1;
     346        // set up members
     347        for ( int i = 0; i < n_fields; ++i ) {
     348                // pad to alignment
     349                size_t off_align = *size % alignof(field[i]);
     350                if ( off_align != 0 ) { *size += alignof(field[i]) - off_align; }
     351                // mark member, increase size, and fix alignment
     352                offsets[i] = *size;
     353                *size += sizeof(field[i]);
     354                if ( *align < alignof(field[i]) ) { *align = alignof(field[i]); }
     355        }
     356        // final padding to alignment
     357        size_t off_align = *size % *align;
     358        if ( off_align != 0 ) { *size += *align - off_align; }
     359}
     360\end{cfa}
     361
     362Results of layout function calls are cached so that they are only computed once per type per function.
     363Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature, an important implemenation-hiding constraint of the design.
     364For 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.
     365This 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.
     366
     367Whether a type is concrete, dtype-static, or dynamic is decided solely on the basis of the type arguments and !forall! clause type paramters.
     368This 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 to use.
     369In 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.
     370However, 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 we judged preserving separate compilation (and the associated C compatibility) in the implemented design to be an acceptable trade-off.
     371
     372\subsection{Applications of Dtype-static Types} \label{dtype-static-sec}
     373
     374The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
     375The 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.
     376
     377\begin{cfa}
     378forall(dtype T)
     379int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
     380        int c = cmp( a->first, b->first );
     381        return c ? c : cmp( a->second, b->second );
     382}
     383\end{cfa}
     384
     385Since !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.
     386
     387Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \emph{tag structures}.
     388Sometimes, information is only used for type checking and can be omitted at runtime.
     389In 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 !?+?!.
     390These implementations may even be separately compiled, unlike \CC{} template functions.
     391However, the \CFA{} type checker ensures matching types are used by all calls to !?+?!, preventing nonsensical computations like adding a length to a volume.
     392
     393\begin{cfa}
     394forall(dtype Unit) struct scalar { unsigned long value; };
     395struct metres {};
     396struct litres {};
     397
     398forall(dtype U) scalar(U) ?+?(scalar(U) a, scalar(U) b) {
     399        return (scalar(U)){ a.value + b.value };
     400}
     401
     402scalar(metres) half_marathon = { 21098 };
     403scalar(litres) pool = { 2500000 };
     404scalar(metres) marathon = half_marathon + half_marathon;
     405`marathon + pool;` $\C[4in]{// compiler ERROR, mismatched types}$
     406\end{cfa}
     407
     408\section{Performance Experiments} \label{generic-performance-sec}
     409
     410\TODO{pull benchmarks from Moss et al.}
    248411
    249412\section{Future Work}
    250413
    251 % mention future work adding non-type generic parameters, like ints
    252 
    253 % taking advantage of generic layout functions to provide field assertions in forall qualifiers
    254 
    255 % mention packed generic layouts (significantly more complex layout function, but possible)
     414The generic types design presented here is already sufficiently expressive to implement a variety of useful library types.
     415However, some other features based on this design could further improve \CFA{}.
     416
     417The most pressing addition is the ability to have non-type generic parameters.
     418C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters, and allowing \CFA{} users the capability to build similar types is a requested feature.
     419More 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.
     420For 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.
     421
     422The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}.
     423One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables.
     424Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types.
     425Simulating 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.
     426Of 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 we have deferred a decision on field assertions until we have more experience using \CFA{}.
     427If 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.
     428\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- the layout function would need to be re-written, but nothing in the use of the offset arrays implies that the field offsets need be monotonically increasing.
     429
     430With 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.
     431However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, we are considering more targeted mechanisms for performance-sensitive code.
     432Two promising approaches are 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.
     433These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
     434In general, the \CFA{} team believes that separate compilation works well with loaded hardware caches by producing smaller code, which may offset the benefit of larger inlined code.
  • doc/theses/aaron_moss_PhD/phd/thesis.tex

    ra32346b ra332d432  
    2222\usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments
    2323\usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver
     24
     25\usepackage{footmisc} % for double refs to the same footnote
    2426
    2527% Hyperlinks make it very easy to navigate an electronic document.
Note: See TracChangeset for help on using the changeset viewer.