# Changeset 34a6b2e for doc

Ignore:
Timestamp:
Sep 25, 2018, 5:33:02 PM (4 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum
Children:
Parents:
461eed2 (diff), a32346b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg2:software/cfa/cfa-cc

Location:
doc
Files:
6 edited

Unmodified
Removed
• ## doc/proposals/virtual.txt

 r461eed2 first polymorphic parameter). Once a function in a trait has been marked as virtual it defines a new function that takes in that trait's reference and then dynamically calls the underlying type implementation. Hence a trait reference becomes a kind of abstract type, cannot be directly instantiated but can still be used. Instances of a trait are created by wrapping an existing instance of a type that implements that trait. This wrapper includes all the function pointers and other values required to preform the dynamic look-up. These are chosen by the normal look-up rules at the point of abstraction. One of the limitations of this design is that it does not support double is also restricted, initially forbidden, see extension. Ownership of the underlying structure is also a bit of a trick. Considering the use cases for trait object, it is probably best to have the underlying object be heap allocated and owned by the trait object. Extension: Multi-parameter Virtual Traits: context, for instance if the cast occurs on the right hand side of an assignment. Function look-up follows the same rules as relaxed (behavioural) inheritance. Traits can be upcast and down cast without losing information unless the trait is cast down to a structure. Here there are two options. Abstraction Time Binding: The more efficient and consistant with other parts of CFA. Only the trait types use dynamic look-up, if converveted back into a structure the normal static look-up rules find the function at compile time. Casting down to a structure type can then result in the loss of a set of bindings. Construction Time Binding: For more consistant handling of the virtual structs, they are always considered wrapped. Functions are bound to the instance the moment it is constructed and remain unchanged throughout its lifetime, so down casting does not lose information. (We will have to decide between one of these two.) Extension: Multiple Parents We have so far been silent on how the vtable is created, stored and accessed. Creation happens at compile time. Function pointers are found by using the same best match rules as elsewhere (additional rules for defaults from the parent may or may not be required). For strict virtual this must happen at the global scope and forbidding static functions, to ensure that a single unique vtable is created. Similarly, there may have to be stricter matching rules for the functions that go into the vtable, possibly requiring an exact match. Relaxed virtual could relax both restrictions, if we allow different vtable at different conversion (struct to trait reference) sites. If it is allowed local functions being bound to a vtable could cause issues when they go out of scope, however this should follow the lifetime rules most C programs already follow implicitly. Most vtables should be stored statically, the only exception being some of the relaxed vtables that could have local function pointers. These may be able to be stack allocated. All vtables should be immutable and require no manual cleanup. The vtables for the two types might be handled slightly differently and then there is also the hierarchy data for virtual casts. The hierarchy data is simple conceptually. A single (exactly one copy) pointer for each type can act as the identity for it. The value of the pointer is its parent type, with the root pointer being NULL. Additional meta-data can accompany the parent pointer, such as a string name or the vtable fields. They types of each vtable can be constructed from the definitions of the traits (or internal nodes). The stand alone/base vtable is the same for both kinds of inheritance. It may be argumented differently however (include parent /this pointer in hierachal inheritance). Creation of the actual vtable is tricky. For classical single implementation semantics we would assemble the functions and create one vtable at compile time. However, not only does this not give CFA-like behaviour, it is impossible generally because types can satify assertions in different ways at different times and stop satifying them. A special set of harder rules could be used, instead we have decided to try creating multiple vtables for each type. The different vtables will all implement the same type but not always in the same way. Storage has some issues from creation. If the contents of every vtable could be determained at compile time they could all be created and stored statically. However since thunks can be constructed on the stack and become the best match, that isn't always possible. Those will have to be stored in dynamic memory. Which means that all vtables must be stored dynamically or there must be a way to determain which ones to free when the trait object is destroyed. Access has two main options:
• ## doc/theses/aaron_moss_PhD/phd/.gitignore

 r461eed2 templates/ code/a.out thesis.pdf thesis.aux
• ## doc/theses/aaron_moss_PhD/phd/Makefile

 r461eed2 introduction \ background \ generic-types \ type-environment \ resolution-heuristics \

 r461eed2 tabsize=5,                                                                                              % N space tabbing xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation %mathescape=true,                                                                               % LaTeX math escape in CFA code $...$ escapechar=\$, % LaTeX escape in CFA code keepspaces=true, % • ## doc/theses/aaron_moss_PhD/phd/frontpgs.tex  r461eed2 % L I S T O F F I G U R E S % ----------------------------- % \addcontentsline{toc}{chapter}{List of Figures} % \listoffigures % \cleardoublepage % \phantomsection % allows hyperref to link to the correct page \addcontentsline{toc}{chapter}{List of Figures} \listoffigures \cleardoublepage \phantomsection % allows hyperref to link to the correct page % GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) • ## doc/theses/aaron_moss_PhD/phd/generic-types.tex  r461eed2 \label{generic-chap} Talk about generic types. Pull from Moss~\etal\cite{Moss18}. A significant shortcoming in standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms. Broadly speaking, there are three approaches to implement abstract data structures in C. One approach is to write bespoke data structures for each context in which they are needed. While 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. A 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. However, 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 not needed. A 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. Furthermore, writing and using preprocessor macros is unnatural and inflexible. Figure~\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. \begin{figure} \begin{cfa} struct int_list { int value; struct int_list* next; }; void int_list_insert( struct int_list** ls, int x ) { struct int_list* node = malloc(sizeof(struct int_list)); node->value = x; node->next = *ls; *ls = node; } int int_list_head( const struct int_list* ls ) { return ls->value; }$\C[\textwidth]{// all code must be duplicated for every generic instantiation}$struct string_list { const char* value; struct string_list* next; }; void string_list_insert( struct string_list** ls, const char* x ) { struct string_list* node = malloc(sizeof(struct string_list)); node->value = x; node->next = *ls; *ls = node; } const char* string_list_head( const struct string_list* ls ) { return ls->value; }$\C[\textwidth]{// use is efficient and idiomatic}$int main() { struct int_list* il = NULL; int_list_insert( &il, 42 ); printf("%d\n", int_list_head(il)); struct string_list* sl = NULL; string_list_insert( &sl, "hello" ); printf("%s\n", string_list_head(sl)); } \end{cfa} \caption{Bespoke code for linked list implementation.} \label{bespoke-generic-fig} \end{figure} \begin{figure} \begin{cfa} // single code implementation struct list { void* value; struct list* next; };$\C[\textwidth]{// internal memory management requires helper functions}$void list_insert( struct list** ls, void* x, void* (*copy)(void*) ) { struct list* node = malloc(sizeof(struct list)); node->value = copy(x); node->next = *ls; *ls = node; } void* list_head( const struct list* ls ) { return ls->value; }$\C[\textwidth]{// helpers duplicated per type}$void* int_copy(void* x) { int* n = malloc(sizeof(int)); *n = *(int*)x; return n; } void* string_copy(void* x) { return strdup((const char*)x); } int main() { struct list* il = NULL; int i = 42; list_insert( &il, &i, int_copy ); printf("%d\n", *(int*)list_head(il));$\C[2in]{// unsafe type cast}$struct list* sl = NULL; list_insert( &sl, "hello", string_copy ); printf("%s\n", (char*)list_head(sl));$\C[2in]{// unsafe type cast}$} \end{cfa} \caption{\lstinline{void*}-polymorphic code for linked list implementation.} \label{void-generic-fig} \end{figure} \begin{figure} \begin{cfa}$\C[\textwidth]{// code is nested in macros}$#define list(N) N ## _list #define list_insert(N) N ## _list_insert #define list_head(N) N ## _list_head #define define_list(N, T)$\C[0.25in]{ \textbackslash }$struct list(N) { T value; struct list(N)* next; };$\C[0.25in]{ \textbackslash }\C[0.25in]{ \textbackslash }$void list_insert(N)( struct list(N)** ls, T x ) {$\C[0.25in]{ \textbackslash }$struct list(N)* node = malloc(sizeof(struct list(N)));$\C[0.25in]{ \textbackslash }$node->value = x; node->next = *ls;$\C[0.25in]{ \textbackslash }$*ls = node;$\C[0.25in]{ \textbackslash }$}$\C[0.25in]{ \textbackslash }\C[0.25in]{ \textbackslash }$T list_head(N)( const struct list(N)* ls ) { return ls->value; } define_list(int, int);$\C[3in]{// defines int\_list}$define_list(string, const char*);$\C[3in]{// defines string\_list}\C[\textwidth]{// use is efficient, but syntactically idiosyncratic}$int main() { struct list(int)* il = NULL;$\C[3in]{// does not match compiler-visible name}$list_insert(int)( &il, 42 ); printf("%d\n", list_head(int)(il)); struct list(string)* sl = NULL; list_insert(string)( &sl, "hello" ); printf("%s\n", list_head(string)(sl)); } \end{cfa} \caption{Macros for generic linked list implementation.} \label{macro-generic-fig} \end{figure} \CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types. Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18}. \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. A 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. An 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} \TODO{test this code}. \begin{figure} \begin{cfa} forall(otype T) struct list { T value; list(T)* next; };$\C[\textwidth]{// single polymorphic implementation of each function}\C[\textwidth]{// overloading reduces need for namespace prefixes}$forall(otype T) void insert( list(T)** ls, T x ) { list(T)* node = alloc();$\C{// type-inferring alloc}$(*node){ x, *ls };$\C{// concise constructor syntax}$*ls = node; } forall(otype T) T head( const list(T)* ls ) { return ls->value; }$\C[\textwidth]{// use is clear and efficient}$int main() { list(int)* il = 0; insert( &il, 42 );$\C{// inferred polymorphic T}\$ printf("%d\n", head(il)); list(const char*)* sl = 0; insert( &sl, "hello" ); printf("%s\n", head(sl)); } \end{cfa} \caption{\CFA{} generic linked list implementation.} \label{cfa-generic-fig} \end{figure} \section{Design} Though a number of languages have some implementation of generic types, backward compatibility with both C and existing \CFA{} polymorphism presented some unique design constraints for this project. The guiding principle was to maintain an unsurprising language model for C programmers without compromising runtime efficiency. A key insight for this design was that C already possesses a handful of built-in generic types (\emph{compound types} in the language of the standard\cit{}), notably pointer (!T*!) and array (!T[]!), and that user-definable generics should act similarly. \subsection{Related Work} One approach to the design of generic types is that taken by \CC{} templates\cit{}. The 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. Template expansion has the benefit of generating code with near-optimal runtime efficiency, as distinct optimizations can be applied for each instantiation of the template. On the other hand, template expansion can also lead to significant code bloat, exponential in the worst case\cit{}, and the costs of increased instruction cache pressure at runtime and wasted developer time when compiling cannot be discounted. The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms. Because 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. C 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{}. Java\cit{} has another prominent implementation for generic types, based on a significantly different approach than \CC{}. The 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. This 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. To 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. \TODO{Talk about Go, maybe Rust, Swift, etc. as well; specifically mention fat pointer'' polymorphism} \TODO{Talk about Cyclone as well, and why my generics are more powerful} \subsection{\CFA{} Generics} The generic types design in \CFA{} draws inspiration from both \CC{} and Java generics, capturing the better aspects of each. Like \CC{} template types, generic !struct!s and !union!s 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. The 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. As an example, consider the following generic type and function \TODO{test this}: \begin{cfa} forall( otype R, otype S ) struct pair { R first; S second; }; pair(const char*, int) with_len( const char* s ) { return (pair(const char*), int){ s, strlen(s) }; } \end{cfa} In 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!. 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. !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. However, 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{Moss18}) and can be re-used for a wide variety of !pair! instantiations. Since the parameters to this polymorphic constructor call are all statically known, compiler inlining can eliminate any runtime overhead of this polymorphic call. \CFA{} deliberately does not support \CC{}-style partial specializations of generic types. A particularly infamous example in the \CC{} standard library is !vector!, which is represented as a bitstring rather than the array representation of the other !vector! instantiations. Complications 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. Rather than attempting to plug leaks in the template specialization abstraction with a detailed method interface, \CFA{} takes the more principled position that two types with an unrelated data layout are in fact unrelated types, and should be handled with different code. Of course, to the degree that distinct types are similar enough to share an interface, the \CFA{} !trait! system allows one to be defined, and objects of types implementing that !trait! to be operated on in the same polymorphic functions. Since \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. As an example, the !with_len! function above could be an optimization of the following more general function: \begin{cfa} forall(otype T, otype I | { I len(T); }) pair(T, I) with_len( T s ) { return (pair(T,I)){ s, len(s) }; } \end{cfa} \section{Implementation} % forall constraints on struct/union constrain default constructor (TODO check with Rob) % TODO discuss layout function algorithm, application to separate compilation % TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation % TODO mention impetus for zero_t design % TODO mention use in tuple-type implementation % 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) % mention that tuples are implemented on top of a per-arity generic type \section{Performance Experiments} % TODO pull benchmarks from Moss et al. \section{Future Work} % mention future work adding non-type generic parameters, like ints % taking advantage of generic layout functions to provide field assertions in forall qualifiers % mention packed generic layouts (significantly more complex layout function, but possible)
Note: See TracChangeset for help on using the changeset viewer.