Changeset 3895b8b5


Ignore:
Timestamp:
Apr 14, 2017, 12:41:06 PM (8 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
3fb7f5e, bbe856c
Parents:
1a16e9d
Message:

initial work on evaluatoin and related polymorphic work

Location:
doc
Files:
1 added
2 deleted
4 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/cfa.bib

    r1a16e9d r3895b8b5  
    45644564
    45654565@manual{obj-c-book,
    4566     keywords = {objective-c},
    4567     contributor = {a3moss@uwaterloo.ca},
    4568     author = {{Apple Computer Inc.}},
    4569     title = {The {Objective-C} Programming Language},
    4570     publisher = {Apple Computer Inc.},
    4571     address = {Cupertino, CA},
    4572     year = 2003
     4566    keywords    = {objective-c},
     4567    contributor = {a3moss@uwaterloo.ca},
     4568    author      = {{Apple Computer}},
     4569    title       = {The {Objective-C} Programming Language},
     4570    organization= {Apple Computer Inc.},
     4571    address     = {Cupertino, CA},
     4572    year        = 2003
    45734573}
    45744574
    … …  
    48944894    year        = 1980,
    48954895    month       = nov, volume = 15, number = 11, pages = {47-56},
    4896     note        = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming
    4897          Language},
     4896    note        = {Proceedings of the ACM-SIGPLAN Symposium on the {Ada} Programming Language},
    48984897    comment     = {
    48994898        The two-pass (bottom-up, then top-down) algorithm, with a proof
    … …  
    58815880    keywords    = {Rust programming language},
    58825881    contributer = {pabuhr@plg},
     5882    author      = {{Rust Programming Language}},
    58835883    title       = {The {Rust} Programming Language},
    58845884    organization= {The Rust Project Developers},

  • doc/generic_types/Makefile

    r1a16e9d r3895b8b5  
    2121
    2222GRAPHS = ${addsuffix .tex, \
     23timing \
    2324}
    2425
    … …  
    4546#${DOCUMENT} : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    4647
    47 ${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    48                 ../LaTeXmacros/common.tex ../LaTeXmacros/indexstyle ../bibliography/cfa.bib
     48${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex ../bibliography/cfa.bib
    4949        # Conditionally create an empty *.idx (index) file for inclusion until makeindex is run.
    5050        if [ ! -r ${basename $@}.idx ] ; then touch ${basename $@}.idx ; fi
    … …  
    6666## Define the default recipes.
    6767
     68${GRAPHS} : evaluation/timing.gp evaluation/timing.csv
     69        gnuplot evaluation/timing.gp
     70
    6871%.tex : %.fig
    6972        fig2dev -L eepic $< > $@

  • doc/generic_types/evaluation/timing.csv

    r1a16e9d r3895b8b5  
    1 "400 million repetitions","C","Cforall","C++","C++obj","units"
     1"400 million repetitions","C","\\CFA{}","\\CC{}","\\CC{obj}","units"
    22"push\nint",3379,2616,1928,3527,"ms"
    33"copy\nint",3036,2268,1564,3182,"ms"

  • doc/generic_types/generic_types.tex

    r1a16e9d r3895b8b5  
    66\usepackage{upquote}                                                                    % switch curled `'" to straight
    77\usepackage{listings}                                                                   % format program code
    8 \usepackage{graphicx}
    98
    109\makeatletter
    … …  
    142141
    143142\begin{abstract}
    144 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the \CFA project is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers. This paper describes two \CFA extensions, generic and tuple types, details how their design avoids shortcomings of similar features in C and other C-like languages, and presents experimental results validating the design.
     143The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects.
     144This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
     145Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     146The goal of the \CFA project is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers.
     147Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers.
     148Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers.
     149This paper describes two \CFA extensions, generic and tuple types, details how their design avoids shortcomings of similar features in C and other C-like languages, and presents experimental results validating the design.
    145150\end{abstract}
    146151
    … …  
    151156\section{Introduction and Background}
    152157
    153 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    154 The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \CS 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail. The top 3 rankings over the past 30 years are:
     158The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects.
     159This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
     160The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \CS 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
     161The top 3 rankings over the past 30 years are:
    155162\lstDeleteShortInline@%
    156163\begin{center}
    … …  
    171178Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
    172179
    173 \CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C while maintaining both source compatibility with C and a familiar programming model for programmers. The four key design goals for \CFA~\citep{Bilson03} are:
     180\CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C while maintaining both source compatibility with C and a familiar programming model for programmers.
     181The four key design goals for \CFA~\citep{Bilson03} are:
    174182(1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler;
    175183(2) Standard C code must be as fast and as small when translated by a \CFA compiler as when translated by a C compiler;
    … …  
    179187Unfortunately, \CC is actively diverging from C, so incremental additions require significant effort and training, coupled with multiple legacy design-choices that cannot be updated.
    180188
    181 \CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3). Ultimately, a compiler is necessary for advanced features and optimal performance.
    182 
    183 This paper identifies shortcomings in existing approaches to generic and variadic data types in C-like languages and presents a design for generic and variadic types avoiding those shortcomings. Specifically, the solution is both reusable and type-checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions. The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
     189\CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3).
     190Ultimately, a compiler is necessary for advanced features and optimal performance.
     191
     192This paper identifies shortcomings in existing approaches to generic and variadic data types in C-like languages and presents a design for generic and variadic types avoiding those shortcomings.
     193Specifically, the solution is both reusable and type-checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions.
     194The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
    184195
    185196
    … …  
    187198\label{sec:poly-fns}
    188199
    189 \CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name):
     200\CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}.
     201The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name):
    190202\begin{lstlisting}
    191203`forall( otype T )` T identity( T val ) { return val; }
    192204int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
    193205\end{lstlisting}
    194 The @identity@ function above can be applied to any complete \emph{object type} (or @otype@). The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type. The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor. If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@).
    195 
    196 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments show this overhead is similar to \CC virtual-function calls. An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
    197 
    198 Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable. For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
     206The @identity@ function above can be applied to any complete \emph{object type} (or @otype@).
     207The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type.
     208The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor.
     209If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@).
     210
     211In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments show this overhead is similar to \CC virtual-function calls.
     212An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
     213
     214Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
     215For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    199216\begin{lstlisting}
    200217forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$
    201218int val = twice( twice( 3.7 ) );
    202219\end{lstlisting}
    203 which works for any type @T@ with a matching addition operator. The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@. There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type, as in~\cite{Ada}, in its type analysis.
    204 The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition.
     220which works for any type @T@ with a matching addition operator.
     221The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@.
     222There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type, as in~\cite{Ada}, in its type analysis.
     223The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@.
     224\CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition.
    205225
    206226Crucial to the design of a new programming language are the libraries to access thousands of external software features.
    … …  
    242262where the return type supplies the type/size of the allocation, which is impossible in most type systems.
    243263
    244 Call-site inferencing and nested functions provide a localized form of inheritance. For example, the \CFA @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour:
     264Call-site inferencing and nested functions provide a localized form of inheritance.
     265For example, the \CFA @qsort@ only sorts in ascending order using @<@.
     266However, it is trivial to locally change this behaviour:
    245267\begin{lstlisting}
    246268forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ }
    … …  
    307329\end{lstlisting}
    308330Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete type: stack-allocatable, default or copy-initialized, assigned, and deleted.
    309 % As an example, the @sum@ function produces generated code something like the following (simplified for clarity and brevity)\TODO{fix example, maybe elide, it's likely too long with the more complicated function}:
    310 % \begin{lstlisting}
    311 % void abs( size_t _sizeof_M, size_t _alignof_M,
    312 %               void (*_ctor_M)(void*), void (*_copy_M)(void*, void*),
    313 %               void (*_assign_M)(void*, void*), void (*_dtor_M)(void*),
    314 %               _Bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*),
    315 %       void (*_ctor_M_zero)(void*, int),
    316 %               void* m, void* _rtn ) {                         $\C{// polymorphic parameter and return passed as void*}$
    317 %                                                                                       $\C{// M zero = { 0 };}$
    318 %       void* zero = alloca(_sizeof_M);                 $\C{// stack allocate zero temporary}$
    319 %       _ctor_M_zero(zero, 0);                                  $\C{// initialize using zero\_t constructor}$
    320 %                                                                                       $\C{// return m < zero ? -m : m;}$
    321 %       void *_tmp = alloca(_sizeof_M);
    322 %       _copy_M( _rtn,                                                  $\C{// copy-initialize return value}$
    323 %               _lt_M( m, zero ) ?                                      $\C{// check condition}$
    324 %                (_neg_M(m, _tmp), _tmp) :                      $\C{// negate m}$
    325 %                m);
    326 %       _dtor_M(_tmp); _dtor_M(zero);                   $\C{// destroy temporaries}$
    327 % }
    328 % \end{lstlisting}
    329331
    330332In summation, the \CFA type-system uses \emph{nominal typing} for concrete types, matching with the C type-system, and \emph{structural typing} for polymorphic types.
    … …  
    364366\section{Generic Types}
    365367
    366 One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms. Broadly speaking, there are three approaches to create 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.
    367 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, and does allow the use of common code for 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 would not otherwise be needed.
    368 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 may be difficult to interpret. Furthermore, writing and using preprocessor macros can be unnatural and inflexible.
    369 
    370 Other languages use \emph{generic types}, \eg \CC and Java, to produce type-safe abstract data-types. \CFA also implements generic types that integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation. However, for known concrete parameters, the generic type can be inlined, like \CC templates.
     368One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
     369Broadly speaking, there are three approaches to create data structures in C.
     370One approach is to write bespoke data structures for each context in which they are needed.
     371While 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.
     372A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, and does allow the use of common code for common functionality.
     373However, 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 would not otherwise be needed.
     374A 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 may be difficult to interpret.
     375Furthermore, writing and using preprocessor macros can be unnatural and inflexible.
     376
     377Other languages use \emph{generic types}, \eg \CC and Java, to produce type-safe abstract data-types.
     378\CFA also implements generic types that integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.
     379However, for known concrete parameters, the generic type can be inlined, like \CC templates.
    371380
    372381A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration, and instantiated using a parenthesized list of types after the type name:
    … …  
    387396\end{lstlisting}
    388397
    389 \CFA classifies generic types as either \emph{concrete} or \emph{dynamic}. Concrete have a fixed memory layout regardless of type parameters, while dynamic vary in memory layout depending on their type parameters. A type may have polymorphic parameters but still be concrete, called \emph{dtype-static}. Polymorphic pointers are an example of dtype-static types, \eg @forall(dtype T) T *@ is a polymorphic type, but for any @T@, @T *@  is a fixed-sized pointer, and therefore, can be represented by a @void *@ in code generation.
    390 
    391 \CFA generic types also allow checked argument-constraints. For example, the following declaration of a sorted set-type ensures the set key supports equality and relational comparison:
     398\CFA classifies generic types as either \emph{concrete} or \emph{dynamic}.
     399Concrete have a fixed memory layout regardless of type parameters, while dynamic vary in memory layout depending on their type parameters.
     400A type may have polymorphic parameters but still be concrete, called \emph{dtype-static}.
     401Polymorphic pointers are an example of dtype-static types, \eg @forall(dtype T) T *@ is a polymorphic type, but for any @T@, @T *@  is a fixed-sized pointer, and therefore, can be represented by a @void *@ in code generation.
     402
     403\CFA generic types also allow checked argument-constraints.
     404For example, the following declaration of a sorted set-type ensures the set key supports equality and relational comparison:
    392405\begin{lstlisting}
    393406forall( otype Key | { _Bool ?==?(Key, Key); _Bool ?<?(Key, Key); } ) struct sorted_set;
    … …  
    397410\subsection{Concrete Generic-Types}
    398411
    399 The \CFA translator template-expands concrete generic-types into new structure types, affording maximal inlining. To enable inter-operation among equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate. For example, a function declaration that accepts or returns a concrete generic-type produces a declaration for the instantiated struct in the same scope, which all callers may reuse. For example, the concrete instantiation for @pair( const char *, int )@ is:
     412The \CFA translator template-expands concrete generic-types into new structure types, affording maximal inlining.
     413To enable inter-operation among equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate.
     414For example, a function declaration that accepts or returns a concrete generic-type produces a declaration for the instantiated struct in the same scope, which all callers may reuse.
     415For example, the concrete instantiation for @pair( const char *, int )@ is:
    400416\begin{lstlisting}
    401417struct _pair_conc1 {
    … …  
    405421\end{lstlisting}
    406422
    407 A concrete generic-type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations. In the above example, the @pair( F *, T * )@ parameter to @value_p@ is such a type; its expansion is below and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
     423A concrete generic-type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
     424In the above example, the @pair( F *, T * )@ parameter to @value_p@ is such a type; its expansion is below and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
    408425\begin{lstlisting}
    409426struct _pair_conc0 {
    … …  
    428445The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) }@.
    429446
    430 In some cases the offset arrays cannot be statically generated. For 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 @.c@ file.
     447In some cases the offset arrays cannot be statically generated.
     448For 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 @.c@ file.
    431449\CFA supports this pattern for generic types, but the caller does not know the actual layout or size of the dynamic generic-type, and only holds it by a pointer.
    432450The \CFA translator 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.
    433451These 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 (un@sized@ parameters are forbidden from being used in a context that affects layout).
    434452Results of these layout functions are cached so that they are only computed once per type per function. %, as in the example below for @pair@.
    435 % \begin{lstlisting}
    436 % static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair,
    437 %               size_t _szeof_R, size_t _alignof_R, size_t _szeof_S, size_t _alignof_S) {
    438 %     *_szeof_pair = 0; // default values
    439 %     *_alignof_pair = 1;
    440 %
    441 %       // add offset, size, and alignment of first field
    442 %     _offsetof_pair[0] = *_szeof_pair;
    443 %     *_szeof_pair += _szeof_R;
    444 %     if ( *_alignof_pair < _alignof_R ) *_alignof_pair = _alignof_R;
    445 %
    446 %       // padding, offset, size, and alignment of second field
    447 %     if ( *_szeof_pair & (_alignof_S - 1) )
    448 %               *_szeof_pair += (_alignof_S - ( *_szeof_pair & (_alignof_S - 1) ) );
    449 %     _offsetof_pair[1] = *_szeof_pair;
    450 %     *_szeof_pair += _szeof_S;
    451 %     if ( *_alignof_pair < _alignof_S ) *_alignof_pair = _alignof_S;
    452 %
    453 %       // pad to struct alignment
    454 %     if ( *_szeof_pair & (*_alignof_pair - 1) )
    455 %               *_szeof_pair += ( *_alignof_pair - ( *_szeof_pair & (*_alignof_pair - 1) ) );
    456 % }
    457 % \end{lstlisting}
    458453Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature.
    459454For instance, a function that strips duplicate values from an unsorted @vector(T)@ would likely have a pointer to the vector as its only explicit parameter, but use some sort of @set(T)@ internally to test for duplicate values.
    … …  
    468463\label{sec:generic-apps}
    469464
    470 The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T *@ as a type-checked replacement for @void *@, \eg creating a lexicographic comparison for pairs of pointers used by @bsearch@ or @qsort@:
     465The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
     466The most important such pattern is using @forall(dtype T) T *@ as a type-checked replacement for @void *@, \eg creating a lexicographic comparison for pairs of pointers used by @bsearch@ or @qsort@:
    471467\begin{lstlisting}
    472468forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
    … …  
    670666x.[0, 1] = x.[1, 0];    $\C[1in]{// rearrange: [x.0, x.1] = [x.1, x.0]}$
    671667f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}\CRT{}$
    672 [int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0. x.2]
     668[int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.
     669x.2]
    673670\end{lstlisting}
    674671\end{tabular}
    … …  
    687684\subsection{Casting}
    688685
    689 In C, the cast operator is used to explicitly convert between types. In \CFA, the cast operator has a secondary use as type ascription. That is, a cast can be used to select the type of an expression when it is ambiguous, as in the call to an overloaded function:
     686In C, the cast operator is used to explicitly convert between types.
     687In \CFA, the cast operator has a secondary use as type ascription.
     688That is, a cast can be used to select the type of an expression when it is ambiguous, as in the call to an overloaded function:
    690689\begin{lstlisting}
    691690int f();     // (1)
    … …  
    696695\end{lstlisting}
    697696
    698 Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples. Taking a look at standard C provides some guidance with respect to the way casts should work with tuples:
     697Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
     698Taking a look at standard C provides some guidance with respect to the way casts should work with tuples:
    699699\begin{lstlisting}
    700700int f();
    … …  
    704704(int)g();  // (2)
    705705\end{lstlisting}
    706 In C, (1) is a valid cast, which calls @f@ and discards its result. On the other hand, (2) is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical. Generalizing these principles, any cast wherein the number of components increases as a result of the cast is invalid, while casts that have the same or fewer number of components may be valid.
    707 
    708 Formally, a cast to tuple type is valid when $T_n \leq S_m$, where $T_n$ is the number of components in the target type and $S_m$ is the number of components in the source type, and for each $i$ in $[0, n)$, $S_i$ can be cast to $T_i$. Excess elements ($S_j$ for all $j$ in $[n, m)$) are evaluated, but their values are discarded so that they are not included in the result expression. This approach follows naturally from the way that a cast to @void@ works in C.
     706In C, (1) is a valid cast, which calls @f@ and discards its result.
     707On the other hand, (2) is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
     708Generalizing these principles, any cast wherein the number of components increases as a result of the cast is invalid, while casts that have the same or fewer number of components may be valid.
     709
     710Formally, a cast to tuple type is valid when $T_n \leq S_m$, where $T_n$ is the number of components in the target type and $S_m$ is the number of components in the source type, and for each $i$ in $[0, n)$, $S_i$ can be cast to $T_i$.
     711Excess elements ($S_j$ for all $j$ in $[n, m)$) are evaluated, but their values are discarded so that they are not included in the result expression.
     712This approach follows naturally from the way that a cast to @void@ works in C.
    709713
    710714For example, in
    … …  
    720724\end{lstlisting}
    721725
    722 (1) discards the last element of the return value and converts the second element to @double@. Since @int@ is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of @g@. If @g@ is free of side effects, this expression is equivalent to @[(int)(g().0), (int)(g().1.0), (int)(g().2)]@.
     726(1) discards the last element of the return value and converts the second element to @double@.
     727Since @int@ is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of @g@.
     728If @g@ is free of side effects, this expression is equivalent to @[(int)(g().0), (int)(g().1.0), (int)(g().2)]@.
    723729Since @void@ is effectively a 0-element tuple, (3) discards the first and third return values, which is effectively equivalent to @[(int)(g().1.0), (int)(g().1.1)]@).
    724730
    725 Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions would require more precise matching of types than allowed for function arguments and parameters.}. As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3. Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid. That is, it is invalid to cast @[int, int]@ to @[int, int, int]@.
     731Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions would require more precise matching of types than allowed for function arguments and parameters.}.
     732As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
     733Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid.
     734That is, it is invalid to cast @[int, int]@ to @[int, int, int]@.
    726735\end{comment}
    727736
    … …  
    843852This function provides the type-safety of @new@ in \CC, without the need to specify the allocated type again, thanks to return-type inference.
    844853
    845 % In the call to @new@, @pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(pair(int, char) *, int, char)@.
    846 
    847854
    848855\subsection{Implementation}
    849856
    850857Tuples are implemented in the \CFA translator via a transformation into generic types.
    851 For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated. \eg:
     858For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg:
    852859\begin{lstlisting}
    853860[int, int] f() {
    … …  
    902909f(x.field_0, (_tuple2){ x.field_1, 'z' });
    903910\end{lstlisting}
    904 Note that due to flattening, @x@ used in the argument position is converted into the list of its fields. In the call to @f@, the second and third argument components are structured into a tuple argument. Similarly, tuple member expressions are recursively expanded into a list of member access expressions.
    905 
    906 Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion. Each unique expression is assigned an identifier and is guaranteed to be executed exactly once:
     911Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
     912In the call to @f@, the second and third argument components are structured into a tuple argument.
     913Similarly, tuple member expressions are recursively expanded into a list of member access expressions.
     914
     915Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
     916Each unique expression is assigned an identifier and is guaranteed to be executed exactly once:
    907917\begin{lstlisting}
    908918void g(int, double);
    … …  
    922932);
    923933\end{lstlisting}
    924 Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order. The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true. Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression. Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
    925 
    926 Currently, the \CFA translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure. This notion could be made more precise for certain intrinsic, auto-generated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions.
    927 
    928 The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions. A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg in a unique expression. The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language. However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new.
     934Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order.
     935The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true.
     936Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
     937Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
     938
     939Currently, the \CFA translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure.
     940This notion could be made more precise for certain intrinsic, auto-generated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions.
     941
     942The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
     943A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg in a unique expression.
     944The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language.
     945However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new.
    929946\end{comment}
    930947
    … …  
    932949\section{Evaluation}
    933950
    934 Though \CFA provides significant added functionality over C, these added features do not impose a significant runtime penalty. In fact, \CFA's features for generic programming can enable runtime execution that is faster than idiomatic @void*@-based C code. We have produced a set of generic-code-based micro-benchmarks to demonstrate these claims, source code for which may be found in \TODO{Appendix A}. These benchmarks test a generic stack based on a singly-linked-list, a generic pair data structure, and a variadic @print@ routine similar to that shown in Section~\ref{sec:variadic-tuples}. Each benchmark has been implemented in C with @void*@-based polymorphism, \CFA with the features discussed in this paper, \CC with templates, and \CC using only class inheritance for polymorphism (``\CCV''). The intention of these benchmarks is to represent the costs of idiomatic use of each language's features, rather than the strict maximal performance obtainable by code written in each language -- as all the languages considered have a shared subset comprising most of standard C, a set of maximal-performance benchmarks would presumably show very little runtime variance, and would differ primarily in length and clarity of source code. Particularly, in the \CCV variant of the benchmark all objects inherit from a base @object@ class, explicitly implement interfaces defined as abstract base classes, and must do runtime checks in generic code to safely down-cast objects; this is not an idiomatic programming pattern for \CC, but is meant to represent the design of a simple object-oriented programming language. The most notable difference between the implementations is  memory layout; the \CFA and \CC variants inline the stack and pair elements into their corresponding list and pair nodes, while the C and \CCV versions are forced by their lack of a generic type capability to store generic objects via pointers to separately-allocated objects. For more idiomatic language use, the C and \CFA variants used \texttt{cstdio.h} for printing, while the \CC and \CCV variants used \texttt{iostream}, though preliminary experiments showed this distinction to make little runtime difference. For consistency in testing, all implementations used the C @rand()@ function for random number generation.
     951Though \CFA provides significant added functionality over C, these added features have a low runtime penalty.
     952In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
     953This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see source code in Appendix~\ref{sec:BenchMarks}).
     954Since all these languages share a subset comprising most of standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
     955Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
     956The benchmarks test a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ routine similar to that in Section~\ref{sec:variadic-tuples}.
     957The structure of each implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
     958The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
     959hence runtime checks are necessary to safely down-cast objects.
     960The most notable difference among the implementations is in optimizations: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while the C and \CCV lack generic-type capability {\color{red}(AWKWARD) to store generic objects via pointers to separately-allocated objects}.
     961For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
     962Preliminary tests show the difference has little runtime effect.
     963Finally, the C @rand@ function is used generate random numbers.
    935964
    936965\begin{figure}
    937966\centering
    938 \includegraphics{evaluation/timing}
    939 \caption{Timing Results for benchmarks}
     967\input{timing}
     968\caption{Benchmark Timing Results (smaller is better)}
    940969\label{fig:eval}
    941970\end{figure}
    … …  
    944973\caption{Properties of benchmark code}
    945974\label{tab:eval}
    946 \begin{tabular}{lrrrr}
    947                                                         &       C               &       \CFA    &       \CC             &       \CCV    \\ \hline
    948 maximum memory usage (MB)       &       10001   &       2501    &       2503    &       11253   \\
    949 source code size (lines)        &       301             &       224             &       188             &       437             \\
    950 binary size (KB)                        &       18.46   &       234.22  &       18.42   &       42.10   \\
     975\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
     976\begin{tabular}{r|rrrr}
     977                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
     978maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
     979source code size (lines)        & 301           & 224           & 188           &       437                     \\
     980binary size (KB)                        & 18            & 234           & 18            &       42                      \\
    951981\end{tabular}
    952982\end{table}
    953983
    954 The results of running the benchmarks can be seen in Figure~\ref{fig:eval} and Table~\ref{tab:eval}; each result records the time taken by a single function call, repeated $N = 40,000,000$ times where appropriate. The five functions are $N$ stack pushes of randomly generated elements, deep copy of an $N$ element stack, clearing all nodes of an $N$ element stack, $N/2$ variadic @print@ calls each containing two constant strings and two stack elements \TODO{right now $N$ fresh elements: FIX}, and $N$ stack pops, keeping a running record of the maximum element to ensure that the object copies are not optimized out. These five functions are run first for a stack of integers, and second for a stack of generic pairs of a boolean and a @char@. \TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted. All code was compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen. The benchmarks were 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. The C and \CCV variants are generally the slowest and most memory-hungry, due to their less-efficient memory layout and the pointer-indirection necessary to implement generic types in these languages; this problem is exacerbated by the second level of generic types in the pair-based benchmarks. By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of boolean and char tests, which makes sense given that an integer is actually larger than the pair in both languages.
    955 
    956 The \CC code is the shortest largely due to its use of header-only libraries, as template code cannot be separately compiled, the \CFA line count would shrink to \TODO{} if it used a header-only approach instead of the more idiomatic separate compilation. \CFA and \CC also have the advantage of a more extensive standard library; as part of the standard library neither language's generic @pair@ type is included in the line count, while this type must be written by the user programmer in both C and \CCV. The definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char*@ are included in the line count for \CCV, which somewhat inflates its line count, as an actual object-oriented language would include these in the standard library and with their omission the \CCV line count is similar to C; we justify the given line count by the fact that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose. Raw line-count, however, is a fairly rough measure of code complexity; another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler. Such un-checked 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 pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@) \TODO{Actually calculate this; I want to put a distinctive comment in the source code and grep for it}.
     984Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the benchmark results.
     985Each data point is the time for 40M function call, repeated times where appropriate.
     986The five functions are $N$ stack pushes of randomly generated elements, deep copy of an $N$ element stack, clearing all nodes of an $N$ element stack, $N/2$ variadic @print@ calls each containing two constant strings and two stack elements \TODO{right now $N$ fresh elements: FIX}, and $N$ stack pops, keeping a running record of the maximum element to ensure that the object copies are not optimized out.
     987These five functions are run first for a stack of integers, and second for a stack of generic pairs of a boolean and a @char@.
     988\TODO{} The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
     989All code was compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen.
     990The benchmarks were 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.
     991The C and \CCV variants are generally the slowest and most memory-hungry, due to their less-efficient memory layout and the pointer-indirection necessary to implement generic types in these languages; this problem is exacerbated by the second level of generic types in the pair-based benchmarks.
     992By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of boolean and char tests, which makes sense given that an integer is actually larger than the pair in both languages.
     993
     994\CC performs best because it uses header-only inlined libraries (i.e., no separate compilation).
     995\CFA and \CC have the advantage of a pre-written generic @pair@ type to reduce line count, while C and \CCV require it to written by the programmer. {\color{red} Why?}
     996The definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count for \CCV, which somewhat inflates its line count, as an actual object-oriented language would include these in the standard library and with their omission the \CCV line count is similar to C;
     997we justify the given line count by the fact that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     998Raw line-count, however, is a fairly rough measure of code complexity;
     999another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
     1000Such un-checked 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 pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@) \TODO{Actually calculate this; I want to put a distinctive comment in the source code and grep for it}.
     1001
    9571002
    9581003\section{Related Work}
    9591004
    9601005
    961 \subsection{Generics}
    962 
    963 \CC is the existing language it is most natural to compare \CFA to, as they are both more modern extensions to C with backwards source compatibility. The most fundamental difference in approach between \CC and \CFA is their approach to this C compatibility. \CC does provide fairly strong source backwards compatibility with C, but is a dramatically more complex language than C, and imposes a steep learning curve to use many of its extension features. For instance, in a break from general C practice, template code is typically written in header files, with a variety of subtle restrictions implied on its use by this choice, while the other polymorphism mechanism made available by \CC, class inheritance, requires programmers to learn an entirely new object-oriented programming paradigm; the interaction between templates and inheritance is also quite complex. \CFA, by contrast, has a single facility for polymorphic code, one which supports separate compilation and the existing procedural paradigm of C code. A major difference between the approaches of \CC and \CFA to polymorphism is that the set of assumed properties for a type is \emph{explicit} in \CFA. One of the major limiting factors of \CC's approach is that templates cannot be separately compiled, and, until concepts~\citep{C++Concepts} are standardized (currently anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors for template expansion failures. By contrast, the explicit nature of assertions in \CFA allows polymorphic functions to be separately compiled, and for their requirements to be checked by the compiler; similarly, \CFA generic types may be opaque, unlike \CC template classes.
    964 
    965 Cyclone also provides capabilities for polymorphic functions and existential types~\citep{Grossman06}, similar in concept to \CFA's @forall@ functions and generic types. Cyclone 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, a tedious and potentially error-prone process. Furthermore, Cyclone's polymorphic functions and types are restricted in that they may only abstract over types with the same layout and calling convention as @void*@, in practice only pointer types and @int@ - in \CFA terms, all Cyclone polymorphism must be dtype-static. This design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, but is more restrictive than \CFA's more general model.
    966 
    967 Apple's Objective-C \citep{obj-c-book} is another industrially successful set of extensions to C. The Objective-C language model is a fairly radical departure from C, adding object-orientation and message-passing. Objective-C implements variadic functions using the C @va_arg@ mechanism, and did not support type-checked generics until recently \citep{xcode7}, historically using less-efficient and more error-prone runtime checking of object types instead. The GObject framework \citep{GObject} also adds object-orientation with runtime type-checking and reference-counting garbage-collection to C; these are much more intrusive feature additions than those provided by \CFA, in addition to the runtime overhead of reference-counting. The Vala programming language \citep{Vala} compiles to GObject-based C, and so adds the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code-bases. Java \citep{Java8} has had generic types and variadic functions since Java~5; Java's generic types are type-checked at compilation and type-erased at runtime, similar to \CFA's, though in Java each object carries its own table of method pointers, while \CFA passes the method pointers separately so as to maintain a C-compatible struct layout. Java variadic functions are simply syntactic sugar for an array of a single type, and therefore less useful than \CFA's heterogeneously-typed variadic functions. Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
    968 
    969 D \citep{D}, Go \citep{Go}, and Rust \citep{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust. However, each language represents dramatic departures from C in terms of language model, and none has the same level of compatibility with C as \CFA. D and Go are garbage-collected languages, imposing the associated runtime overhead. The necessity of accounting for data transfer between the managed Go runtime and the unmanaged C runtime complicates foreign-function interface between Go and C. Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more. D restricts garbage collection to its own heap by default, while Rust is not garbage-collected, and thus has a lighter-weight runtime that is more easily interoperable with C. Rust also possesses much more powerful abstraction capabilities for writing generic code than Go. On the other hand, Rust's borrow-checker, while it does provide strong safety guarantees, is complex and difficult to learn, and imposes a distinctly idiomatic programming style on Rust. \CFA, with its more modest safety features, is significantly easier to port C code to, while maintaining the idiomatic style of the original source.
     1006\subsection{Polymorphism}
     1007
     1008\CC is closest language to \CFA;
     1009both are extensions to C with source and runtime backwards compatibility, and incremental extensions to C.
     1010The fundamental difference is in their engineering approach to C compatibility and programmer expectation.
     1011While \CC provides good backwards compatibility with C, it has a steep learning curve for many of its extensions.
     1012For example, polymorphism is provided via three disjoint mechanisms: overloading, inheritance, and templates.
     1013The overloading is restricted because resolution does not using the return type, inheritance requires learning object-oriented programming and coping with a restricted nominal-inheritance hierarchy, templates cannot be separately compiled resulting in compilation/code bloat and poor error messages, and determining how these mechanisms interact and which to use is confusing.
     1014In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate-compilation of polymorphic functions and generic (opaque) types, which uniformly leveraging the C procedural paradigm.
     1015The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type.
     1016Until \CC concepts~\citep{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion;
     1017furthermore, \CC concepts are restricted to template polymorphism.
     1018
     1019Cyclone~\citep{Grossman06} also provides capabilities for polymorphic functions and existential types, similar to \CFA's @forall@ functions and generic types.
     1020Cyclone 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, a tedious and potentially error-prone process.
     1021Furthermore, 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@.
     1022In \CFA terms, all Cyclone polymorphism must be dtype-static.
     1023While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model.
     1024
     1025Objective-C~\citep{obj-c-book} is an industrially successful extensions to C.
     1026However, Objective-C is a radical departure from C, using an object-oriented model with message-passing.
     1027Objective-C did not support type-checked generics until recently~\citep{xcode7}, historically using less-efficient and more error-prone runtime checking of object types.
     1028The GObject framework~\citep{GObject} also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C;
     1029these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference-counting.
     1030Vala~\citep{Vala} compiles to GObject-based C, and so adds the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for the existing C code-bases.
     1031Java~\citep{Java8} included generic types in Java~5;
     1032Java's generic types are type-checked at compilation and type-erased at runtime, similar to \CFA's.
     1033However, in Java, each object carries its own table of method pointers, while \CFA passes the method pointers separately to maintain a C-compatible layout.
     1034Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
     1035
     1036D~\citep{D}, Go~\citep{Go}, and Rust~\citep{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust.
     1037However, each language represents significant departures from C in terms of language model, and none has the same level of compatibility with C as \CFA.
     1038D and Go are garbage-collected languages, imposing the associated runtime overhead.
     1039The necessity of accounting for data transfer between managed runtimes and the unmanaged C runtime complicates foreign-function interfaces to C.
     1040Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more.
     1041D restricts garbage collection to its own heap by default, while Rust is not garbage-collected, and thus has a lighter-weight runtime more interoperable with C.
     1042Rust also possesses much more powerful abstraction capabilities for writing generic code than Go.
     1043On the other hand, Rust's borrow-checker, provides strong safety guarantees but is complex and difficult to learn, and imposes a distinctly idiomatic programming style.
     1044\CFA, with its more modest safety features, ports directly to C code, while maintaining the idiomatic style of the original source.
    9701045
    9711046
    … …  
    9751050SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types.
    9761051Tuples in SETL allow subscripting, dynamic expansion, and multiple assignment.
     1052C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types.
    9771053KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL.
    9781054The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field access.
    … …  
    9851061Like \CC, D provides tuples through a library variadic-template structure.
    9861062Go does not have tuples but supports MRVF.
    987 Java's variadic functions appear similar to C's but are type-safe using arrays.
     1063Java's variadic functions appear similar to C's but are type-safe using homogeneous arrays, which are less useful than \CFA's heterogeneously-typed variadic functions.
    9881064Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and Scala~\cite{Scala}, which decompose tuples using pattern matching.
    9891065
    … …  
    9911067\section{Conclusion \& Future Work}
    9921068
    993 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives. In addition to this work, there are some interesting future directions the polymorphism design could take. Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. \CFA polymorphic functions, by contrast, use an approach that is essentially dynamic virtual dispatch. The runtime overhead of this approach is low, but not as low as \CC template functions, and it may be beneficial to provide a mechanism for particularly performance-sensitive code to close this gap. Further research is needed, but two promising approaches are to allow an annotation on polymorphic function call sites that tells the translator to create a template-specialization of the function (provided the code is visible in the current translation unit) or placing an annotation on polymorphic function definitions that instantiates a version of the polymorphic function specialized to some set of types. These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unnecessary.
    994 
    995 In conclusion, the authors' design for generic types and tuples, unlike those available in existing work, is both reusable and type-checked, while still supporting a full range of C features, including separately-compiled modules. We have experimentally validated the performance of our design against both \CC and standard C, showing it is \TODO{shiny, cap'n}.
     1069There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
     1070In addition to this work, there are some interesting future directions the polymorphism design could take.
     1071Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions.
     1072\CFA polymorphic functions, by contrast, use an approach that is essentially dynamic virtual dispatch.
     1073The runtime overhead of this approach is low, but not as low as \CC template functions, and it may be beneficial to provide a mechanism for particularly performance-sensitive code to close this gap.
     1074Further research is needed, but two promising approaches are to allow an annotation on polymorphic function call sites that tells the translator to create a template-specialization of the function (provided the code is visible in the current translation unit) or placing an annotation on polymorphic function definitions that instantiates a version of the polymorphic function specialized to some set of types.
     1075These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unnecessary.
     1076
     1077In conclusion, the authors' design for generic types and tuples, unlike those available in existing work, is both reusable and type-checked, while still supporting a full range of C features, including separately-compiled modules.
     1078We have experimentally validated the performance of our design against both \CC and standard C, showing it is \TODO{shiny, cap'n}.
     1079
    9961080
    9971081\begin{acks}
    … …  
    10001084This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}\ and the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
    10011085\end{acks}
     1086
     1087
     1088\appendix
     1089
     1090
     1091\section{BenchMarks}
     1092\label{sec:BenchMarks}
     1093
     1094TODO
     1095
    10021096
    10031097\bibliographystyle{ACM-Reference-Format}
Note: See TracChangeset for help on using the changeset viewer.