Changeset 9fd06ae


Ignore:
Timestamp:
Feb 19, 2018, 10:44:05 AM (6 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:
b060aba
Parents:
1280f95
Message:

more wordsmithing

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/general/Paper.tex

    r1280f95 r9fd06ae  
    158158
    159159
    160 \title{Generic and Tuple Types with Efficient Dynamic Layout in \protect\CFA}
     160\title{\protect\CFA : Adding Modern Programming Language Features to C}
    161161
    162162\author{Aaron Moss, Robert Schluntz, Peter Buhr}
     
    184184The 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.
    185185This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    186 Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     186Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     187
    187188The 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.
    188189Prior 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.
    189 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.
    190 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.
     190Specifically, \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 programmers.
     191This paper presents a quick tour of \CFA features showing how their design avoids shortcomings of similar features in C and other C-like languages.
     192Finally, experimental results are presented to validate several of the new features.
    191193\end{abstract}
    192194
     
    222224\CC is used similarly, but has the disadvantages of multiple legacy design-choices that cannot be updated and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
    223225
    224 \CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)--(3).
     226\CFA is currently implemented as a source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3).
    225227Ultimately, a compiler is necessary for advanced features and optimal performance.
    226228
     
    268270
    269271The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name):
    270 \begin{lstlisting}
     272\begin{cfa}
    271273`forall( otype T )` T identity( T val ) { return val; }
    272274int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
    273 \end{lstlisting}
     275\end{cfa}
    274276The @identity@ function above can be applied to any complete \newterm{object type} (or @otype@).
    275277The 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.
     
    283285Since bare polymorphic-types provide a restricted set of available operations, \CFA provides a \newterm{type assertion}~\cite[pp.~37-44]{Alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
    284286For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    285 \begin{lstlisting}
     287\begin{cfa}
    286288forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$
    287289int val = twice( twice( 3.7 ) );
    288 \end{lstlisting}
     290\end{cfa}
    289291which works for any type @T@ with a matching addition operator.
    290292The 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@.
     
    296298Like \CC, \CFA inherits a massive compatible library-base, where other programming languages must rewrite or provide fragile inter-language communication with C.
    297299A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array:
    298 \begin{lstlisting}
     300\begin{cfa}
    299301void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
    300302                                int (* compar)( const void *, const void * ));
     
    305307double key = 5.0, vals[10] = { /* 10 sorted float values */ };
    306308double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    307 \end{lstlisting}
     309\end{cfa}
    308310which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrappers:
    309 \begin{lstlisting}
     311\begin{cfa}
    310312forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
    311313        int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ }
     
    318320double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
    319321int posn = bsearch( 5.0, vals, 10 );
    320 \end{lstlisting}
     322\end{cfa}
    321323The nested function @comp@ provides the hidden interface from typed \CFA to untyped (@void *@) C, plus the cast of the result.
    322324Providing a hidden @comp@ function in \CC is awkward as lambdas do not use C calling-conventions and template declarations cannot appear at block scope.
     
    326328\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}).
    327329For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@:
    328 \begin{lstlisting}
     330\begin{cfa}
    329331forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); }
    330332int * ip = malloc();                                            $\C{// select type and size from left-hand side}$
    331333double * dp = malloc();
    332334struct S {...} * sp = malloc();
    333 \end{lstlisting}
     335\end{cfa}
    334336where the return type supplies the type/size of the allocation, which is impossible in most type systems.
    335337
     
    337339For example, the \CFA @qsort@ only sorts in ascending order using @<@.
    338340However, it is trivial to locally change this behaviour:
    339 \begin{lstlisting}
     341\begin{cfa}
    340342forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ }
    341343{       int ?<?( double x, double y ) { return x `>` y; }       $\C{// locally override behaviour}$
    342344        qsort( vals, size );                                    $\C{// descending sort}$
    343345}
    344 \end{lstlisting}
     346\end{cfa}
    345347Within the block, the nested version of @?<?@ performs @?>?@ and this local version overrides the built-in @?<?@ so it is passed to @qsort@.
    346348Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    347349
    348 %% Redundant with Section~\ref{sec:libraries} %%
    349 
    350 % Finally, \CFA allows variable overloading:
    351 % \begin{lstlisting}
    352 % short int MAX = ...;   int MAX = ...;  double MAX = ...;
    353 % short int s = MAX;    int i = MAX;    double d = MAX;   $\C{// select correct MAX}$
    354 % \end{lstlisting}
    355 % Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    356350
    357351\subsection{Traits}
    358352
    359353\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration:
    360 \begin{lstlisting}
     354\begin{cfa}
    361355trait `summable`( otype T ) {
    362356        void ?{}( T *, zero_t );                                $\C{// constructor from 0 literal}$
     
    370364        for ( unsigned int i = 0; i < size; i += 1 ) total `+=` a[i]; $\C{// select appropriate +}$
    371365        return total; }
    372 \end{lstlisting}
     366\end{cfa}
    373367
    374368In fact, the set of @summable@ trait operators is incomplete, as it is missing assignment for type @T@, but @otype@ is syntactic sugar for the following implicit trait:
    375 \begin{lstlisting}
     369\begin{cfa}
    376370trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
    377371        void ?{}( T * );                                                $\C{// default constructor}$
     
    379373        void ?=?( T *, T );                                             $\C{// assignment operator}$
    380374        void ^?{}( T * ); };                                    $\C{// destructor}$
    381 \end{lstlisting}
     375\end{cfa}
    382376Given 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.
    383377
     
    392386
    393387% Nominal inheritance can be simulated with traits using marker variables or functions:
    394 % \begin{lstlisting}
     388% \begin{cfa}
    395389% trait nominal(otype T) {
    396390%     T is_nominal;
    397391% };
    398392% int is_nominal;                                                               $\C{// int now satisfies the nominal trait}$
    399 % \end{lstlisting}
     393% \end{cfa}
    400394%
    401395% Traits, however, are significantly more powerful than nominal-inheritance interfaces; most notably, traits may be used to declare a relationship \emph{among} multiple types, a property that may be difficult or impossible to represent in nominal-inheritance type systems:
    402 % \begin{lstlisting}
     396% \begin{cfa}
    403397% trait pointer_like(otype Ptr, otype El) {
    404398%     lvalue El *?(Ptr);                                                $\C{// Ptr can be dereferenced into a modifiable value of type El}$
     
    411405%
    412406% lvalue int *?( list_iterator it ) { return it->value; }
    413 % \end{lstlisting}
     407% \end{cfa}
    414408% In the example above, @(list_iterator, int)@ satisfies @pointer_like@ by the user-defined dereference function, and @(list_iterator, list)@ also satisfies @pointer_like@ by the built-in dereference operator for pointers. Given a declaration @list_iterator it@, @*it@ can be either an @int@ or a @list@, with the meaning disambiguated by context (\eg @int x = *it;@ interprets @*it@ as an @int@, while @(*it).value = 42;@ interprets @*it@ as a @list@).
    415409% While a nominal-inheritance system with associated types could model one of those two relationships by making @El@ an associated type of @Ptr@ in the @pointer_like@ implementation, few such systems could model both relationships simultaneously.
     
    432426
    433427A 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:
    434 \begin{lstlisting}
     428\begin{cfa}
    435429forall( otype R, otype S ) struct pair {
    436430        R first;
     
    447441pair( double *, double * ) r = { &d, &d };
    448442d = value_p( r );
    449 \end{lstlisting}
     443\end{cfa}
    450444
    451445\CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}.
     
    456450\CFA generic types also allow checked argument-constraints.
    457451For example, the following declaration of a sorted set-type ensures the set key supports equality and relational comparison:
    458 \begin{lstlisting}
     452\begin{cfa}
    459453forall( otype Key | { _Bool ?==?(Key, Key); _Bool ?<?(Key, Key); } ) struct sorted_set;
    460 \end{lstlisting}
     454\end{cfa}
    461455
    462456
     
    467461A function declaration that accepts or returns a concrete generic-type produces a declaration for the instantiated structure in the same scope, which all callers may reuse.
    468462For example, the concrete instantiation for @pair( const char *, int )@ is:
    469 \begin{lstlisting}
     463\begin{cfa}
    470464struct _pair_conc1 {
    471465        const char * first;
    472466        int second;
    473467};
    474 \end{lstlisting}
     468\end{cfa}
    475469
    476470A concrete generic-type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
    477471In 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:
    478 \begin{lstlisting}
     472\begin{cfa}
    479473struct _pair_conc0 {
    480474        void * first;
    481475        void * second;
    482476};
    483 \end{lstlisting}
     477\end{cfa}
    484478
    485479
     
    518512The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
    519513The 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@:
    520 \begin{lstlisting}
     514\begin{cfa}
    521515forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
    522516        return cmp( a->first, b->first ) ? : cmp( a->second, b->second );
    523517}
    524 \end{lstlisting}
     518\end{cfa}
    525519Since @pair(T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the fields of both pairs and the arguments to the comparison function match in type.
    526520
    527521Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    528522Sometimes information is only used for type-checking and can be omitted at runtime, \eg:
    529 \begin{lstlisting}
     523\begin{cfa}
    530524forall(dtype Unit) struct scalar { unsigned long value; };
    531525struct metres {};
     
    540534scalar(litres) two_pools = swimming_pool + swimming_pool;
    541535marathon + swimming_pool;                                       $\C{// compilation ERROR}$
    542 \end{lstlisting}
     536\end{cfa}
    543537@scalar@ is a dtype-static type, so all uses have a single structure definition, containing @unsigned long@, and can share the same implementations of common functions like @?+?@.
    544538These implementations may even be separately compiled, unlike \CC template functions.
     
    552546however, many operations have multiple outcomes, some exceptional.
    553547Consider C's @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and float values, respectively.
    554 \begin{lstlisting}
     548\begin{cfa}
    555549typedef struct { int quo, rem; } div_t;         $\C{// from include stdlib.h}$
    556550div_t div( int num, int den );
     
    559553int q;
    560554double r = remquo( 13.5, 5.2, &q );                     $\C{// return remainder, alias quotient}$
    561 \end{lstlisting}
     555\end{cfa}
    562556@div@ aggregates the quotient/remainder in a structure, while @remquo@ aliases a parameter to an argument.
    563557Both approaches are awkward.
    564558Alternatively, a programming language can directly support returning multiple values, \eg in \CFA:
    565 \begin{lstlisting}
     559\begin{cfa}
    566560[ int, int ] div( int num, int den );           $\C{// return two integers}$
    567561[ double, double ] div( double num, double den ); $\C{// return two doubles}$
     
    570564[ q, r ] = div( 13, 5 );                                        $\C{// select appropriate div and q, r}$
    571565[ q, r ] = div( 13.5, 5.2 );                            $\C{// assign into tuple}$
    572 \end{lstlisting}
     566\end{cfa}
    573567Clearly, this approach is straightforward to understand and use;
    574568therefore, why do few programming languages support this obvious feature or provide it awkwardly?
     
    584578
    585579However, functions also use \newterm{composition} (nested calls), with the direct consequence that MRVFs must also support composition to be orthogonal with single-returning-value functions (SRVF), \eg:
    586 \begin{lstlisting}
     580\begin{cfa}
    587581printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
    588 \end{lstlisting}
     582\end{cfa}
    589583Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments.
    590584However, the \CFA type-system must support significantly more complex composition:
    591 \begin{lstlisting}
     585\begin{cfa}
    592586[ int, int ] foo$\(_1\)$( int );                        $\C{// overloaded foo functions}$
    593587[ double ] foo$\(_2\)$( int );
    594588void bar( int, double, double );
    595589bar( foo( 3 ), foo( 3 ) );
    596 \end{lstlisting}
     590\end{cfa}
    597591The type-resolver only has the tuple return-types to resolve the call to @bar@ as the @foo@ parameters are identical, which involves unifying the possible @foo@ functions with @bar@'s parameter list.
    598592No combination of @foo@s are an exact match with @bar@'s parameters, so the resolver applies C conversions.
     
    604598An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF.
    605599\CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types, \eg:
    606 \begin{lstlisting}
     600\begin{cfa}
    607601[ int, int ] qr = div( 13, 5 );                         $\C{// tuple-variable declaration and initialization}$
    608602[ double, double ] qr = div( 13.5, 5.2 );
    609 \end{lstlisting}
     603\end{cfa}
    610604where the tuple variable-name serves the same purpose as the parameter name(s).
    611605Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C.
    612606
    613607One way to access the tuple-variable components is with assignment or composition:
    614 \begin{lstlisting}
     608\begin{cfa}
    615609[ q, r ] = qr;                                                          $\C{// access tuple-variable components}$
    616610printf( "%d %d\n", qr );
    617 \end{lstlisting}
     611\end{cfa}
    618612\CFA also supports \newterm{tuple indexing} to access single components of a tuple expression:
    619 \begin{lstlisting}
     613\begin{cfa}
    620614[int, int] * p = &qr;                                           $\C{// tuple pointer}$
    621615int rem = qr`.1`;                                                       $\C{// access remainder}$
     
    624618bar( qr`.1`, qr );                                                      $\C{// pass remainder and quotient/remainder}$
    625619rem = [div( 13, 5 ), 42]`.0.1`;                         $\C{// access 2nd component of 1st component of tuple expression}$
    626 \end{lstlisting}
     620\end{cfa}
    627621
    628622
     
    635629%\par\smallskip
    636630%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    637 \begin{lstlisting}
     631\begin{cfa}
    638632int f( int, int );
    639633int g( [int, int] );
     
    644638g( y, 10 );             $\C{// structure}$
    645639h( x, y );              $\C{// flatten and structure}$
    646 \end{lstlisting}
    647 %\end{lstlisting}
     640\end{cfa}
     641%\end{cfa}
    648642%&
    649 %\begin{lstlisting}
     643%\begin{cfa}
    650644%\end{tabular}
    651645%\smallskip\par\noindent
     
    664658%\par\smallskip
    665659%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    666 \begin{lstlisting}
     660\begin{cfa}
    667661int x = 10;
    668662double y = 3.5;
     
    672666z = 10;                                                                         $\C{// mass assignment}$
    673667[y, x] = 3.14;                                                          $\C{// mass assignment}$
    674 \end{lstlisting}
    675 %\end{lstlisting}
     668\end{cfa}
     669%\end{cfa}
    676670%&
    677 %\begin{lstlisting}
     671%\begin{cfa}
    678672%\end{tabular}
    679673%\smallskip\par\noindent
     
    686680Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C.
    687681This example shows mass, multiple, and cascading assignment used in one expression:
    688 \begin{lstlisting}
     682\begin{cfa}
    689683void f( [int, int] );
    690684f( [x, y] = z = 1.5 );                                          $\C{// assignments in parameter list}$
    691 \end{lstlisting}
     685\end{cfa}
    692686
    693687
     
    696690It is also possible to access multiple fields from a single expression using a \newterm{member-access}.
    697691The result is a single tuple-valued expression whose type is the tuple of the types of the members, \eg:
    698 \begin{lstlisting}
     692\begin{cfa}
    699693struct S { int x; double y; char * z; } s;
    700694s.[x, y, z] = 0;
    701 \end{lstlisting}
     695\end{cfa}
    702696Here, the mass assignment sets all members of @s@ to zero.
    703697Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (\eg rearrange, drop, and duplicate components).
     
    705699%\par\smallskip
    706700%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    707 \begin{lstlisting}
     701\begin{cfa}
    708702[int, int, long, double] x;
    709703void f( double, long );
     
    711705f( x.[0, 3] );                                                          $\C{// drop: f(x.0, x.3)}$
    712706[int, int, int] y = x.[2, 0, 2];                        $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
    713 \end{lstlisting}
    714 %\end{lstlisting}
     707\end{cfa}
     708%\end{cfa}
    715709%&
    716 %\begin{lstlisting}
     710%\begin{cfa}
    717711%\end{tabular}
    718712%\smallskip\par\noindent
    719713%\lstMakeShortInline@%
    720714It is also possible for a member access to contain other member accesses, \eg:
    721 \begin{lstlisting}
     715\begin{cfa}
    722716struct A { double i; int j; };
    723717struct B { int * k; short l; };
    724718struct C { int x; A y; B z; } v;
    725719v.[x, y.[i, j], z.k];                                           $\C{// [v.x, [v.y.i, v.y.j], v.z.k]}$
    726 \end{lstlisting}
     720\end{cfa}
    727721
    728722
     
    733727In \CFA, the cast operator has a secondary use as type ascription.
    734728That 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:
    735 \begin{lstlisting}
     729\begin{cfa}
    736730int f();     // (1)
    737731double f();  // (2)
     
    739733f();       // ambiguous - (1),(2) both equally viable
    740734(int)f();  // choose (2)
    741 \end{lstlisting}
     735\end{cfa}
    742736
    743737Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
    744738Taking a look at standard C provides some guidance with respect to the way casts should work with tuples:
    745 \begin{lstlisting}
     739\begin{cfa}
    746740int f();
    747741void g();
     
    749743(void)f();  // (1)
    750744(int)g();  // (2)
    751 \end{lstlisting}
     745\end{cfa}
    752746In C, (1) is a valid cast, which calls @f@ and discards its result.
    753747On the other hand, (2) is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
     
    759753
    760754For example, in
    761 \begin{lstlisting}
     755\begin{cfa}
    762756[int, int, int] f();
    763757[int, [int, int], int] g();
     
    768762([int, int, int, int])g();    $\C{// (4)}$
    769763([int, [int, int, int]])g();  $\C{// (5)}$
    770 \end{lstlisting}
     764\end{cfa}
    771765
    772766(1) discards the last element of the return value and converts the second element to @double@.
     
    786780Tuples also integrate with \CFA polymorphism as a kind of generic type.
    787781Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non-tuple types, \eg:
    788 \begin{lstlisting}
     782\begin{cfa}
    789783forall(otype T, dtype U) void f( T x, U * y );
    790784f( [5, "hello"] );
    791 \end{lstlisting}
     785\end{cfa}
    792786where @[5, "hello"]@ is flattened, giving argument list @5, "hello"@, and @T@ binds to @int@ and @U@ binds to @const char@.
    793787Tuples, however, may contain polymorphic components.
    794788For example, a plus operator can be written to add two triples together.
    795 \begin{lstlisting}
     789\begin{cfa}
    796790forall(otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
    797791        return [x.0 + y.0, x.1 + y.1, x.2 + y.2];
     
    800794int i1, i2, i3;
    801795[i1, i2, i3] = x + ([10, 20, 30]);
    802 \end{lstlisting}
     796\end{cfa}
    803797
    804798Flattening and restructuring conversions are also applied to tuple types in polymorphic type assertions.
    805 \begin{lstlisting}
     799\begin{cfa}
    806800int f( [int, double], double );
    807801forall(otype T, otype U | { T f( T, U, U ); }) void g( T, U );
    808802g( 5, 10.21 );
    809 \end{lstlisting}
     803\end{cfa}
    810804Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
    811805This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}.
    812806Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
    813 \begin{lstlisting}
     807\begin{cfa}
    814808int _thunk( int _p0, double _p1, double _p2 ) { return f( [_p0, _p1], _p2 ); }
    815 \end{lstlisting}
     809\end{cfa}
    816810so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    817 These thunks take advantage of GCC C nested-functions to produce closures that have the usual function-pointer signature.
     811These thunks take advantage of gcc C nested-functions to produce closures that have the usual function-pointer signature.
    818812
    819813
     
    830824Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
    831825For example, a generalized @sum@ function written using @ttype@:
    832 \begin{lstlisting}
     826\begin{cfa}
    833827int sum$\(_0\)$() { return 0; }
    834828forall(ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
     
    836830}
    837831sum( 10, 20, 30 );
    838 \end{lstlisting}
     832\end{cfa}
    839833Since @sum@\(_0\) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
    840834In order to call @sum@\(_1\), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list and @Params@ is bound to @[20, 30]@.
     
    843837
    844838It is reasonable to take the @sum@ function a step further to enforce a minimum number of arguments:
    845 \begin{lstlisting}
     839\begin{cfa}
    846840int sum( int x, int y ) { return x + y; }
    847841forall(ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
    848842        return sum( x + y, rest );
    849843}
    850 \end{lstlisting}
     844\end{cfa}
    851845One more step permits the summation of any summable type with all arguments of the same type:
    852 \begin{lstlisting}
     846\begin{cfa}
    853847trait summable(otype T) {
    854848        T ?+?( T, T );
     
    860854        return sum( x + y, rest );
    861855}
    862 \end{lstlisting}
     856\end{cfa}
    863857Unlike C variadic functions, it is unnecessary to hard code the number and expected types.
    864858Furthermore, this code is extendable for any user-defined type with a @?+?@ operator.
     
    866860
    867861It is also possible to write a type-safe variadic print function to replace @printf@:
    868 \begin{lstlisting}
     862\begin{cfa}
    869863struct S { int x, y; };
    870864forall(otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {
     
    875869void print( S s ) { print( "{ ", s.x, ",", s.y, " }" ); }
    876870print( "s = ", (S){ 1, 2 }, "\n" );
    877 \end{lstlisting}
     871\end{cfa}
    878872This example showcases a variadic-template-like decomposition of the provided argument list.
    879873The individual @print@ functions allow printing a single element of a type.
     
    883877Finally, it is possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
    884878For example, it is possible to write @new@ as a library function:
    885 \begin{lstlisting}
     879\begin{cfa}
    886880forall( otype R, otype S ) void ?{}( pair(R, S) *, R, S );
    887881forall( dtype T, ttype Params | sized(T) | { void ?{}( T *, Params ); } ) T * new( Params p ) {
     
    889883}
    890884pair( int, char ) * x = new( 42, '!' );
    891 \end{lstlisting}
     885\end{cfa}
    892886The @new@ function provides the combination of type-safe @malloc@ with a \CFA constructor call, making it impossible to forget constructing dynamically allocated objects.
    893887This function provides the type-safety of @new@ in \CC, without the need to specify the allocated type again, thanks to return-type inference.
     
    898892Tuples are implemented in the \CFA translator via a transformation into \newterm{generic types}.
    899893For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg:
    900 \begin{lstlisting}
     894\begin{cfa}
    901895[int, int] f() {
    902896        [double, double] x;
    903897        [int, double, int] y;
    904898}
    905 \end{lstlisting}
     899\end{cfa}
    906900is transformed into:
    907 \begin{lstlisting}
     901\begin{cfa}
    908902forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
    909903        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
     
    919913        _tuple3(int, double, int) y;
    920914}
    921 \end{lstlisting}
     915\end{cfa}
    922916\begin{sloppypar}
    923917Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
     
    926920\begin{comment}
    927921Since tuples are essentially structures, tuple indexing expressions are just field accesses:
    928 \begin{lstlisting}
     922\begin{cfa}
    929923void f(int, [double, char]);
    930924[int, double] x;
     
    933927printf("%d %g\n", x);
    934928f(x, 'z');
    935 \end{lstlisting}
     929\end{cfa}
    936930Is transformed into:
    937 \begin{lstlisting}
     931\begin{cfa}
    938932void f(int, _tuple2(double, char));
    939933_tuple2(int, double) x;
     
    942936printf("%d %g\n", x.field_0, x.field_1);
    943937f(x.field_0, (_tuple2){ x.field_1, 'z' });
    944 \end{lstlisting}
     938\end{cfa}
    945939Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
    946940In the call to @f@, the second and third argument components are structured into a tuple argument.
     
    949943Expressions that may contain side effects are made into \newterm{unique expressions} before being expanded by the flattening conversion.
    950944Each unique expression is assigned an identifier and is guaranteed to be executed exactly once:
    951 \begin{lstlisting}
     945\begin{cfa}
    952946void g(int, double);
    953947[int, double] h();
    954948g(h());
    955 \end{lstlisting}
     949\end{cfa}
    956950Internally, this expression is converted to two variables and an expression:
    957 \begin{lstlisting}
     951\begin{cfa}
    958952void g(int, double);
    959953[int, double] h();
     
    965959        (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
    966960);
    967 \end{lstlisting}
     961\end{cfa}
    968962Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order.
    969963The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true.
     
    13591353
    13601354
    1361 % \subsection{Exception Handling ???}
     1355\subsection{Exception Handling}
     1356
     1357\CFA provides two forms of exception handling: \newterm{resumption} (fix-up) and \newterm{recovery}.
     1358Both mechanisms provide dynamic call to a handler using dynamic name-lookup, where fix-up has dynamic return and recovery has static return from the handler.
     1359\begin{cquote}
     1360\lstDeleteShortInline@%
     1361\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     1362\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Resumption}}       & \multicolumn{1}{c}{\textbf{Recovery}} \\
     1363\begin{cfa}
     1364_Exception E { int fix; };
     1365void f() {
     1366        ... _Resume E;
     1367        // control returns here after handler
     1368try {
     1369        f();
     1370} catchResume( E e ) {
     1371        ... e.fix = ...; // return correction to raise
     1372} // dynamic return to _Resume
     1373\end{cfa}
     1374&
     1375\begin{cfa}
     1376_Exception E {};
     1377void f() {
     1378        ... _Throw E;
     1379        // control does NOT return here after handler
     1380try {
     1381        f();
     1382} catch( E e ) {
     1383        ... // recover and continue
     1384} // static return to next statement
     1385\end{cfa}
     1386\end{tabular}
     1387\lstMakeShortInline@%
     1388\end{cquote}
    13621389
    13631390
     
    13671394An important part of this subjective feel is maintaining C's procedural paradigm, as opposed to the object-oriented paradigm of other systems languages such as \CC and Rust.
    13681395Maintaining this procedural paradigm means that C coding-patterns remain not only functional but idiomatic in \CFA, reducing the mental burden of retraining C programmers and switching between C and \CFA development.
    1369 Nonetheless, some features of object-oriented languages are undeniably convienient but are independent of object-oriented programming;
     1396Nonetheless, some features of object-oriented languages are undeniably convenient but are independent of object-oriented programming;
    13701397\CFA adapts these features to a procedural paradigm.
    13711398
     
    15351562as well, parameter names are optional, \eg:
    15361563\begin{cfa}
    1537 [ int x ] f ();                                                 $\C{// returning int with no parameters}$
     1564[ int x ] f ( /* void */ );                             $\C{// returning int with no parameters}$
    15381565[ int x ] f (...);                                              $\C{// returning int with unknown parameters}$
    15391566[ * int ] g ( int y );                                  $\C{// returning pointer to int with int parameter}$
    1540 [ ] h ( int, char );                                    $\C{// returning no result with int and char parameters}$
     1567[ void ] h ( int, char );                               $\C{// returning no result with int and char parameters}$
    15411568[ * int, int ] j ( int );                               $\C{// returning pointer to int and int, with int parameter}$
    15421569\end{cfa}
     
    16931720\subsection{Constructors and Destructors}
    16941721
    1695 One of the strengths (and weaknesses) of C is control over memory management, allowing resource release to be more consistent and precisely timed than possible with garbage-collected memory-management.
    1696 However, this manual approach is often verbose, furthermore it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.
     1722One of the strengths (and weaknesses) of C is memory-management control, allowing resource release to be precisely specified versus unknown release with garbage-collected memory-management.
     1723However, this manual approach is often verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.
    16971724\CC addresses these issues using Resource Aquisition Is Initialization (RAII), implemented by means of \newterm{constructor} and \newterm{destructor} functions;
    16981725\CFA adopts constructors and destructors (and @finally@) to facilitate RAII.
    1699 While constructors and destructors are a common feature of object-oriented programming-languages, they are independent capabilities allowing \CFA to retain a procedural paradigm.
     1726While constructors and destructors are a common feature of object-oriented programming-languages, they are an independent capability allowing \CFA to adopt them while retaining a procedural paradigm.
    17001727Specifically, \CFA constructors and destructors are denotes by name and first parameter-type versus name and nesting in an aggregate type.
    1701 
    1702 In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@;
    1703 like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @x{ ... };@ or @^x{...};@.
     1728Constructor calls seamlessly integrate with existing C initialization syntax, providing a simple and familiar syntax to C programmers and allowing constructor calls to be inserted into legacy C code with minimal code changes.
     1729
     1730In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@.
    17041731The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@.
     1732The symbol \lstinline+^+ is used because it was the last remaining binary operator that could be used in a unary context.
     1733Like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @?{}(x, ...)@ or @^{}(x, ...)@.
    17051734The constructor and destructor have return type @void@ and a first parameter of reference to the object type to be constructed or destructs.
    17061735While the first parameter is informally called the @this@ parameter, as in object-oriented languages, any variable name may be used.
    1707 Both constructors and destructors allow additional parametes after the @this@ parameter for specifying values for initialization/de-initialization\footnote{Destruction parameters are useful for specifying storage-management actions, such as de-initialize but not de-allocate.}.
     1736Both constructors and destructors allow additional parametes after the @this@ parameter for specifying values for initialization/de-initialization\footnote{
     1737Destruction parameters are useful for specifying storage-management actions, such as de-initialize but not deallocate.}.
    17081738\begin{cfa}
    17091739struct VLA {
    17101740        int len, * data;
    17111741};
    1712 void ?{}( VLA& vla ) with ( vla ) {                     $\C{// default constructor}$
    1713         len = 10;  data = calloc( len );
    1714 }
    1715 void ^?{}( VLA& vla ) {                                         $\C{// destructor}$
    1716         free( vla.data );
    1717 }
    1718 {       VLA x; `?{}(x);`                                                $\C{// compiler generated constructor call}$
    1719         // ... use x
    1720 `^?{}(x);` }                                                            $\C{// compiler generated desturctor call}$
    1721 \end{cfa}
    1722 @VLA@ is an example of a \newterm{managed type}\footnote{A managed type affects the runtime environment versus being self-contained.} in \CFA: a type requiring a non-trivial constructor or destructor, or with a field of a managed type.
    1723 A managed types is implicitly constructed upon allocation, and destructed upon deallocation to ensure proper interaction of runtime resources, in this case the @data@ array in the heap.
    1724 The exact details of the placement of these implicit constructor and destructor calls are omitted here for brevity, the interested reader should consult \cite{Schluntz17}.
    1725 
    1726 Constructor calls seamlessly integrate with existing C initialization syntax, providing a simple and familiar syntax to C programmers and allowing constructor calls to be inserted into legacy C code with minimal code changes.
    1727 As such, \CFA also provides syntax for \newterm{initialization} and \newterm{copy}:
    1728 \begin{cfa}
    1729 void ?{}( VLA & vla, int size, int fill );      $\C{// initialization}$
    1730 void ?{}( VLA & vla, VLA other );                       $\C{// copy}$
    1731 VLA y = { 20, 0xdeadbeef },  // initialization
    1732            z = y; // copy
    1733 \end{cfa}
    1734 
    1735 Copy constructors have exactly two parameters, the second of which has the same type as the base type of the @this@ parameter; appropriate care is taken in the implementation to avoid recursive calls to the copy constructor when initializing this second parameter.
    1736 Other constructor calls look just like C initializers, except rather than using field-by-field initialization (as in C), an initialization which matches a defined constructor will call the constructor instead.
    1737 
    1738 In addition to initialization syntax, \CFA provides two ways to explicitly call constructors and destructors.
    1739 Explicit calls to constructors double as a placement syntax, useful for construction of member fields in user-defined constructors and reuse of large storage allocations.
    1740 While the existing function-call syntax works for explicit calls to constructors and destructors, \CFA also provides a more concise \newterm{operator syntax} for both:
    1741 
    1742 \begin{cfa}
    1743 VLA a, b;
    1744 a{};                            $\C{// default construct}$
    1745 b{ a };                         $\C{// copy construct}$
    1746 ^a{};                           $\C{// destruct}$
    1747 a{ 5, 0xFFFFFFFF };     $\C{// explicit constructor call}$
     1742void ?{}( VLA & vla ) with ( vla ) {            $\C{// default constructor}$
     1743        len = 10;  data = alloc( len );
     1744}
     1745void ^?{}( VLA & vla ) with ( vla ) {           $\C{// destructor}$
     1746        free( data );
     1747}
     1748{
     1749        VLA x;                                                                  $\C{// implicit:  ?\{\}( x );}$
     1750}                                                                                       $\C{// implicit:  ?\^{}\{\}( x );}$
     1751\end{cfa}
     1752@VLA@ is a \newterm{managed type}\footnote{
     1753A managed type affects the runtime environment versus a self-contained type.}: a type requiring a non-trivial constructor or destructor, or with a field of a managed type.
     1754A managed types is implicitly constructed upon allocation and destructed upon deallocation to ensure proper interaction with runtime resources, in this case the @data@ array in the heap.
     1755For details of the placement of implicit constructor and destructor calls among complex executable statements see~\cite[\S~2.2]{Schluntz17}.
     1756
     1757\CFA also provides syntax for \newterm{initialization} and \newterm{copy}:
     1758\begin{cfa}
     1759void ?{}( VLA & vla, int size, char fill ) with ( vla ) {       $\C{// initialization}$
     1760        len = size;  data = alloc( len, fill );
     1761}
     1762void ?{}( VLA & vla, VLA other ) {                      $\C{// copy}$
     1763        vla.len = other.len;  vla.data = other.data;
     1764}
     1765\end{cfa}
     1766An initialization constructor-call has the same syntax as a C initializer, except the initialization values are passed as arguments to a matching constructor (number and type of paremeters).
     1767\begin{cfa}
     1768VLA va = `{` 20, 0 `}`,  * arr = alloc()`{` 5, 0 `}`;
     1769\end{cfa}
     1770Note, the use of a \newterm{constructor expression} to initialize the storage from the dynamic storage-allocation.
     1771Like \CC, the copy constructor has two parameters, the second of which is a value parameter with the same type as the first parameter;
     1772appropriate care is taken to not recursively call the copy constructor when initializing the second parameter.
     1773
     1774\CFA constructors may be explicitly call, like Java, and destructors may be explicitly called, like \CC.
     1775Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of member fields in user-defined constructors and reuse of existing storage allocations.
     1776While existing call syntax works for explicit calls to constructors and destructors, \CFA also provides a more concise \newterm{operator syntax} for both:
     1777\begin{cfa}
     1778{
     1779        VLA x,  y = { 20, 0x01 },  z = y;
     1780        // implicit:  ?{}( x );  ?{}( y, 20, 0x01 );  ?{}( z, y ); z points to y
     1781        ^x{};                                                                   $\C{// deallocate x}$
     1782        x{};                                                                    $\C{// reallocate x}$
     1783        z{ 5, 0xff };                                                   $\C{// reallocate z, not pointing to y}$
     1784        ^y{};                                                                   $\C{// deallocate y}$
     1785        y{ x };                                                                 $\C{// reallocate y, points to x}$
     1786        x{};                                                                    $\C{// reallocate x, not pointing to y}$
     1787        // implicit:  ^?{}(z);  ^?{}(y);  ^?{}(x);
     1788}
    17481789\end{cfa}
    17491790
    17501791To provide a uniform type interface for @otype@ polymorphism, the \CFA compiler automatically generates a default constructor, copy constructor, assignment operator, and destructor for all types.
    1751 These default functions can be overridden by user-generated versions of them.
    1752 For compatibility with the standard behaviour of C, the default constructor and destructor for all basic, pointer, and reference types do nothing, while the copy constructor and assignment operator are bitwise copies; if default zero-initialization is desired, the default constructors can be overridden.
     1792These default functions can be overridden by user-generated versions.
     1793For compatibility with the standard behaviour of C, the default constructor and destructor for all basic, pointer, and reference types do nothing, while the copy constructor and assignment operator are bitwise copies;
     1794if default zero-initialization is desired, the default constructors can be overridden.
    17531795For user-generated types, the four functions are also automatically generated.
    17541796@enum@ types are handled the same as their underlying integral type, and unions are also bitwise copied and no-op initialized and destructed.
     
    17561798For @struct@ types, each of the four functions are implicitly defined to call their corresponding functions on each member of the struct.
    17571799To better simulate the behaviour of C initializers, a set of \newterm{field constructors} is also generated for structures.
    1758 A constructor is generated for each non-empty prefix of a structure's member-list which copy-constructs the members passed as parameters and default-constructs the remaining members.
    1759 To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all field constructors for that type are hidden from expression resolution; similarly, the generated default constructor is hidden upon declaration of any constructor.
     1800A constructor is generated for each non-empty prefix of a structure's member-list to copy-construct the members passed as parameters and default-construct the remaining members.
     1801To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all field constructors for that type are hidden from expression resolution;
     1802similarly, the generated default constructor is hidden upon declaration of any constructor.
    17601803These semantics closely mirror the rule for implicit declaration of constructors in \CC\cite[p.~186]{ANSI98:C++}.
    17611804
    1762 In rare situations user programmers may not wish to have constructors and destructors called; in these cases, \CFA provides an ``escape hatch'' to not call them.
    1763 If a variable is initialized using the syntax \lstinline|S x @= {}| it will be an \newterm{unmanaged object}, and will not have constructors or destructors called.
    1764 Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg  \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics.
    1765 In addition to the expressive power, \lstinline|@=| provides a simple path for migrating legacy C code to \CFA, by providing a mechanism to incrementally convert initializers; the \CFA design team decided to introduce a new syntax for this escape hatch because we believe that our RAII implementation will handle the vast majority of code in a desirable way, and we wished to maintain familiar syntax for this common case.
     1805In some circumstance programmers may not wish to have constructor and destructor calls.
     1806In these cases, \CFA provides the initialization syntax \lstinline|S x @= {}|, and the object becomes unmanaged, so constructors and destructors calls are not generated.
     1807Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics.
     1808The point of \lstinline|@=| is to provide a migration path from legacy C code to \CFA, by providing a mechanism to incrementally convert to implicit initialization.
    17661809
    17671810
     
    18401883
    18411884
    1842 \subsection{Default Parameters}
     1885% \subsection{Default Parameters}
    18431886
    18441887
     
    22182261A separator does not appear before a C string starting with the characters: \lstinline[mathescape=off,basicstyle=\tt]@([{=$@
    22192262\item
    2220 A seperator does not appear after a C string ending with the characters: \lstinline[basicstyle=\tt]@,.;!?)]}%@
     2263A separator does not appear after a C string ending with the characters: \lstinline[basicstyle=\tt]@,.;!?)]}%@
    22212264\item
    22222265{\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
    2223 A seperator does not appear before or after a C string begining/ending with the quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
     2266A separator does not appear before or after a C string beginning/ending with the quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
    22242267}%
    22252268\item
     
    22842327
    22852328\begin{figure}
    2286 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2329\begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    22872330int main( int argc, char * argv[] ) {
    22882331        FILE * out = fopen( "cfa-out.txt", "w" );
     
    23082351        fclose(out);
    23092352}
    2310 \end{lstlisting}
     2353\end{cfa}
    23112354\caption{\protect\CFA Benchmark Test}
    23122355\label{fig:BenchmarkTest}
     
    23222365Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:BenchmarkTest} and its C, \CC, and \CCV equivalents.
    23232366The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
    2324 All code is compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen.
     2367All code is compiled at \texttt{-O2} by gcc or g++ 6.2.0, with all \CC code compiled as \CCfourteen.
    23252368The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency.
    23262369
     
    23512394\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    23522395There are two outliers in the graph for \CFA: all prints and pop of @pair@.
    2353 Both of these cases result from the complexity of the C-generated polymorphic code, so that the GCC compiler is unable to optimize some dead code and condense nested calls.
     2396Both of these cases result from the complexity of the C-generated polymorphic code, so that the gcc compiler is unable to optimize some dead code and condense nested calls.
    23542397A compiler designed for \CFA could easily perform these optimizations.
    23552398Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
     
    24792522\smallskip\noindent
    24802523\CFA
    2481 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2524\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    24822525forall(otype T) struct stack_node {
    24832526        T value;
     
    25212564        s->head = 0;
    25222565}
    2523 \end{lstlisting}
     2566\end{cfa}
    25242567
    25252568\medskip\noindent
    25262569\CC
    2527 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2570\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    25282571template<typename T> class stack {
    25292572        struct node {
     
    25762619        }
    25772620};
    2578 \end{lstlisting}
     2621\end{cfa}
    25792622
    25802623\medskip\noindent
    25812624C
    2582 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2625\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    25832626struct stack_node {
    25842627        void * value;
     
    26172660        s->head = NULL;
    26182661}
    2619 \end{lstlisting}
     2662\end{cfa}
    26202663
    26212664\medskip\noindent
    26222665\CCV
    2623 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2666\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    26242667stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
    26252668void stack::copy(const stack & o) {
     
    26642707        head = nullptr;
    26652708}
    2666 \end{lstlisting}
     2709\end{cfa}
    26672710
    26682711
Note: See TracChangeset for help on using the changeset viewer.