Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    rd52a55b r3d60c08  
    5959%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
    6060\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
     61
     62\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work
     63%\renewcommand*{\thefootnote}{\fnsymbol{footnote}}
    6164
    6265\makeatletter
    … …  
    174177\lstMakeShortInline@%
    175178
     179\let\OLDthebibliography\thebibliography
     180\renewcommand\thebibliography[1]{
     181  \OLDthebibliography{#1}
     182  \setlength{\parskip}{0pt}
     183  \setlength{\itemsep}{4pt plus 0.3ex}
     184}
    176185
    177186\title{\texorpdfstring{\protect\CFA : Adding Modern Programming Language Features to C}{Cforall : Adding Modern Programming Language Features to C}}
    … …  
    191200The 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.
    192201This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    193 Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
    194 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.
     202Nevertheless, C, first standardized almost forty years ago, lacks many features that make programming in more modern languages safer and more productive.
     203
     204The goal of the \CFA project (pronounced ``C-for-all'') 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.
    195205Prior 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.
    196206Specifically, \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.
    … …  
    226236Love it or hate it, C is extremely popular, highly used, and one of the few systems languages.
    227237In many cases, \CC is often used solely as a better C.
    228 Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     238Nevertheless, C, first standardized almost forty years ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive.
    229239
    230240\CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that adds modern language-features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers.
    … …  
    239249All languages features discussed in this paper are working, except some advanced exception-handling features.
    240250Not discussed in this paper are the integrated concurrency-constructs and user-level threading-library~\cite{Delisle18}.
    241 \CFA is an \emph{open-source} project implemented as an 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).
     251\CFA is an \emph{open-source} project 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).
    242252Ultimately, a compiler is necessary for advanced features and optimal performance.
    243253% @plg2[9]% cd cfa-cc/src; cloc ArgTweak CodeGen CodeTools Common Concurrency ControlStruct Designators GenPoly InitTweak MakeLibCfa.cc MakeLibCfa.h Parser ResolvExpr SymTab SynTree Tuples driver prelude main.cc
    … …  
    292302The \CFA tests are 290+ files and 27,000+ lines of code.
    293303The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks.
    294 The tests check for correctness and are used for daily regression testing of commits (3800+).
     304The tests check for correctness and are used for daily regression testing of 3800+ commits.
    295305
    296306Finally, it is impossible to describe a programming language without usages before definitions.
    … …  
    313323There are only two hard things in Computer Science: cache invalidation and \emph{naming things} -- Phil Karlton
    314324\end{quote}
    315 \vspace{-10pt}
     325\vspace{-9pt}
    316326C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax.
    317327\CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable;
    … …  
    324334int max( int a, int b ) { return a < b ? b : a; }  $\C{// (3)}$
    325335double max( double a, double b ) { return a < b ? b : a; }  $\C{// (4)}\CRT$
    326 max( 7, -max );                                         $\C[2.75in]{// uses (3) and (1), by matching int from constant 7}$
     336max( 7, -max );                                         $\C{// uses (3) and (1), by matching int from constant 7}$
    327337max( max, 3.14 );                                       $\C{// uses (4) and (2), by matching double from constant 3.14}$
    328 max( max, -max );                                       $\C{// ERROR: ambiguous}$
    329 int m = max( max, -max );                       $\C{// uses (3) and (1) twice, by matching return type}\CRT$
     338max( max, -max );                                       $\C{// ERROR, ambiguous}$
     339int m = max( max, -max );                       $\C{// uses (3) and (1) twice, by matching return type}$
    330340\end{cfa}
    331341
    … …  
    336346As is shown later, there are a number of situations where \CFA takes advantage of available type information to disambiguate, where other programming languages generate ambiguities.
    337347
    338 \Celeven added @_Generic@ expressions, which is used in preprocessor macros to provide a form of ad-hoc polymorphism;
     348\Celeven added @_Generic@ expressions~\cite[\S~6.5.1.1]{C11}, which is used with preprocessor macros to provide ad-hoc polymorphism;
    339349however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading.
    340350The macro wrapping the generic expression imposes some limitations;
    341351\eg, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@.
    342352Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the dispatch functions, which must all have distinct names.
    343 For backwards compatibility, \CFA supports @_Generic@ expressions, but it is an unnecessary mechanism. \TODO{actually implement that}
     353\CFA supports @_Generic@ expressions for backwards compatibility, but it is an unnecessary mechanism. \TODO{actually implement that}
    344354
    345355% http://fanf.livejournal.com/144696.html
    … …  
    369379\begin{cfa}
    370380forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; }  $\C{// ? denotes operands}$
    371 int val = twice( twice( 3.7 ) );
     381int val = twice( twice( 3.7 ) );  $\C{// val == 14}$
    372382\end{cfa}
    373383which works for any type @T@ with a matching addition operator.
    374384The 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@.
    375385There 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~\cite{Cormack81,Baker82,Ada} in its type analysis.
    376 The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@.
     386The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an early conversion to @int@.
    377387\CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition.
    378388
    … …  
    420430\begin{cfa}
    421431forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ }
    422 {
     432int main() {
    423433        int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behaviour}$
    424         qsort( vals, size );                                    $\C{// descending sort}$
     434        qsort( vals, 10 );                                                      $\C{// descending sort}$
    425435}
    426436\end{cfa}
    … …  
    428438Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    429439
    430 To reducing duplication, it is possible to distribute a group of @forall@ (and storage-class qualifiers) over functions/types, so each block declaration is prefixed by the group (see example in Appendix~\ref{s:CforallStack}).
     440To reduce duplication, it is possible to distribute a group of @forall@ (and storage-class qualifiers) over functions/types, so each block declaration is prefixed by the group (see example in Appendix~\ref{s:CforallStack}).
    431441\begin{cfa}
    432442forall( otype `T` ) {                                                   $\C{// distribution block, add forall qualifier to declarations}$
    … …  
    470480\end{cquote}
    471481
    472 In 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:
     482Note, the @sumable@ trait does not include a copy constructor needed for the right side of @?+=?@ and return;
     483it is provided by @otype@, which is syntactic sugar for the following trait:
    473484\begin{cfa}
    474485trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
    … …  
    488499Instead, each polymorphic function (or generic type) defines the structural type needed for its execution (polymorphic type-key), and this key is fulfilled at each call site from the lexical environment, which is similar to Go~\cite{Go} interfaces.
    489500Hence, new lexical scopes and nested functions are used extensively to create local subtypes, as in the @qsort@ example, without having to manage a nominal-inheritance hierarchy.
    490 (Nominal inheritance can be approximated with traits using marker variables or functions, as is done in Go.)
     501% (Nominal inheritance can be approximated with traits using marker variables or functions, as is done in Go.)
    491502
    492503% Nominal inheritance can be simulated with traits using marker variables or functions:
    … …  
    515526
    516527
    517 \vspace*{-2pt}
    518528\section{Generic Types}
    519529
    … …  
    534544\begin{cquote}
    535545\lstDeleteShortInline@%
    536 \begin{tabular}{@{}l|@{\hspace{2\parindentlnth}}l@{}}
    537 \begin{cfa}
    538 forall( otype R, otype S ) struct pair {
     546\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
     547\begin{cfa}
     548`forall( otype R, otype S )` struct pair {
    539549        R first;        S second;
    540550};
    … …  
    561571Concrete types have a fixed memory layout regardless of type parameters, while dynamic types vary in memory layout depending on their type parameters.
    562572A \newterm{dtype-static} type has polymorphic parameters but is still concrete.
    563 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.
     573Polymorphic pointers are an example of dtype-static types;
     574given some type variable @T@, @T@ is a polymorphic type, as is @T *@, but @T *@ has a fixed size and can therefore be represented by @void *@ in code generation.
    564575
    565576\CFA generic types also allow checked argument-constraints.
    … …  
    578589\begin{cfa}
    579590struct _pair_conc0 {
    580         const char * first;
    581         int second;
     591        const char * first;  int second;
    582592};
    583593\end{cfa}
    … …  
    587597\begin{cfa}
    588598struct _pair_conc1 {
    589         void * first;
    590         void * second;
     599        void * first, * second;
    591600};
    592601\end{cfa}
    … …  
    645654\begin{cquote}
    646655\lstDeleteShortInline@%
    647 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
     656\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
    648657\begin{cfa}
    649658forall( dtype Unit ) struct scalar { unsigned long value; };
    … …  
    661670                                                        half_marathon;
    662671scalar(litres) two_pools = pool + pool;
    663 `marathon + pool;`      // compilation ERROR
     672`marathon + pool;`      // ERROR, mismatched types
    664673\end{cfa}
    665674\end{tabular}
    … …  
    947956}
    948957\end{cfa}
    949 One more step permits the summation of any summable type with all arguments of the same type:
    950 \begin{cfa}
    951 trait summable( otype T ) {
     958One more step permits the summation of any sumable type with all arguments of the same type:
     959\begin{cfa}
     960trait sumable( otype T ) {
    952961        T ?+?( T, T );
    953962};
    954 forall( otype R | summable( R ) ) R sum( R x, R y ) {
     963forall( otype R | sumable( R ) ) R sum( R x, R y ) {
    955964        return x + y;
    956965}
    957 forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
     966forall( otype R, ttype Params | sumable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
    958967        return sum( x + y, rest );
    959968}
    … …  
    10061015\begin{cfa}
    10071016forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
    1008         T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    1009         T1 field_1;
     1017        T0 field_0;  T1 field_1;                                        $\C{// generated before the first 2-tuple}$
    10101018};
    10111019_tuple2(int, int) f() {
    10121020        _tuple2(double, double) x;
    10131021        forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 {
    1014                 T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    1015                 T1 field_1;
    1016                 T2 field_2;
     1022                T0 field_0;  T1 field_1;  T2 field_2;   $\C{// generated before the first 3-tuple}$
    10171023        };
    10181024        _tuple3(int, double, int) y;
    10191025}
    10201026\end{cfa}
    1021 {\sloppy
    1022 Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
    1023 \par}%
     1027Tuple expressions are then converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char,@ @double)){ 5, 'x', 1.24 }@.
    10241028
    10251029\begin{comment}
    … …  
    11061110\lstDeleteShortInline@%
    11071111\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1108 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1112\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    11091113\begin{cfa}
    11101114case 2, 10, 34, 42:
    … …  
    11211125\lstDeleteShortInline@%
    11221126\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1123 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1127\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    11241128\begin{cfa}
    11251129case 2~42:
    … …  
    11741178\centering
    11751179\lstDeleteShortInline@%
    1176 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1177 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1180\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
     1181\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    11781182\begin{cfa}
    11791183`choose` ( day ) {
    11801184  case Mon~Thu:  // program
    11811185
    1182   case Fri:  // program
     1186  case Fri:    // program
    11831187        wallet += pay;
    11841188        `fallthrough;`
    1185   case Sat:  // party
     1189  case Sat:   // party
    11861190        wallet -= party;
    11871191
    11881192  case Sun:  // rest
    11891193
    1190   default:  // error
     1194  default:    // print error
    11911195}
    11921196\end{cfa}
    … …  
    11961200  case Mon: case Tue: case Wed: case Thu:  // program
    11971201        `break;`
    1198   case Fri:  // program
     1202  case Fri:    // program
    11991203        wallet += pay;
    12001204
    1201   case Sat:  // party
     1205  case Sat:   // party
    12021206        wallet -= party;
    12031207        `break;`
    12041208  case Sun:  // rest
    12051209        `break;`
    1206   default:  // error
     1210  default:    // print error
    12071211}
    12081212\end{cfa}
    … …  
    12201224\centering
    12211225\lstDeleteShortInline@%
    1222 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1223 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{non-terminator}}  & \multicolumn{1}{c}{\textbf{target label}}     \\
     1226\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
     1227\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{non-terminator}}       & \multicolumn{1}{c@{}}{\textbf{target label}}  \\
    12241228\begin{cfa}
    12251229choose ( ... ) {
    … …  
    12641268\begin{figure}
    12651269\lstDeleteShortInline@%
    1266 \begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
    1267 \multicolumn{1}{@{\hspace{\parindentlnth}}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}   & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}}      \\
     1270\begin{tabular}{@{\hspace{\parindentlnth}}l|@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     1271\multicolumn{1}{@{\hspace{\parindentlnth}}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{@{\hspace{\parindentlnth}}c@{}}{\textbf{C}}   \\
    12681272\begin{cfa}
    12691273`LC:` {
    … …  
    13491353\subsection{Exception Handling}
    13501354
    1351 The following framework for \CFA exception handling is in place, excluding some runtime type-information and virtual functions.
     1355The following framework for \CFA exception-handling is in place, excluding some runtime type-information and virtual functions.
    13521356\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
    13531357Both 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.
    … …  
    13601364\begin{cquote}
    13611365\lstDeleteShortInline@%
    1362 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1363 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Resumption}}      & \multicolumn{1}{c}{\textbf{Termination}}      \\
     1366\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
     1367\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{Resumption}}   & \multicolumn{1}{c@{}}{\textbf{Termination}}   \\
    13641368\begin{cfa}
    13651369`exception R { int fix; };`
    … …  
    14771481If an exception is raised and caught, the handler is run before the finally clause.
    14781482Like a destructor (see Section~\ref{s:ConstructorsDestructors}), a finally clause can raise an exception but not if there is an exception being propagated.
    1479 Mimicking the @finally@ clause with mechanisms like RAII is non-trivially when there are multiple types and local accesses.
     1483Mimicking the @finally@ clause with mechanisms like RAII is non-trivial when there are multiple types and local accesses.
    14801484
    14811485
    … …  
    15301534with ( s, t ) {
    15311535        j + k;                                                                  $\C{// unambiguous, s.j + t.k}$
    1532         m = 5.0;                                                                $\C{// unambiguous, t.m = 5.0}$
    1533         m = 1;                                                                  $\C{// unambiguous, s.m = 1}$
    1534         int a = m;                                                              $\C{// unambiguous, a = s.i }$
    1535         double b = m;                                                   $\C{// unambiguous, b = t.m}$
     1536        m = 5.0;                                                                $\C{// unambiguous, s.m = 5.0}$
     1537        m = 1;                                                                  $\C{// unambiguous, t.m = 1}$
     1538        int a = m;                                                              $\C{// unambiguous, a = t.m }$
     1539        double b = m;                                                   $\C{// unambiguous, b = s.m}$
    15361540        int c = s.i + t.i;                                              $\C{// unambiguous, qualification}$
    1537         (double)m;                                                              $\C{// unambiguous, cast}$
     1541        (double)m;                                                              $\C{// unambiguous, cast s.m}$
    15381542}
    15391543\end{cfa}
    … …  
    15591563and implicitly opened \emph{after} a function-body open, to give them higher priority:
    15601564\begin{cfa}
    1561 void ?{}( S & s, int `i` ) with ( s ) `with( $\emph{\color{red}params}$ )` {
     1565void ?{}( S & s, int `i` ) with ( s ) `{` `with( $\emph{\color{red}params}$ )` {
    15621566        s.i = `i`; j = 3; m = 5.5;
    1563 }
     1567} `}`
    15641568\end{cfa}
    15651569Finally, a cast may be used to disambiguate among overload variables in a @with@ expression:
    … …  
    16291633\lstDeleteShortInline@%
    16301634\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
    1631 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1635\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    16321636\begin{cfa}
    16331637`[5] *` int x1;
    … …  
    16571661\lstDeleteShortInline@%
    16581662\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1659 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1663\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    16601664\begin{cfa}
    16611665`*` int x, y;
    1662 int y;
    1663 \end{cfa}
    1664 &
    1665 \begin{cfa}
    1666 int `*`x, `*`y;
     1666int z;
     1667\end{cfa}
     1668&
     1669\begin{cfa}
     1670int `*`x, `*`y, z;
    16671671
    16681672\end{cfa}
    … …  
    16701674\lstMakeShortInline@%
    16711675\end{cquote}
    1672 The downside of the \CFA semantics is the need to separate regular and pointer declarations.
     1676% The downside of the \CFA semantics is the need to separate regular and pointer declarations.
     1677The separation of regular and pointer declarations by \CFA declarations enforces greater clarity with only slightly more syntax.
    16731678
    16741679\begin{comment}
    … …  
    16771682\lstDeleteShortInline@%
    16781683\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
    1679 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
     1684\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
    16801685\begin{cfa}
    16811686[ 5 ] int z;
    … …  
    17191724\lstDeleteShortInline@%
    17201725\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
    1721 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
     1726\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
    17221727\begin{cfa}
    17231728extern const * const int x;
    … …  
    17441749\lstDeleteShortInline@%
    17451750\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1746 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1751\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    17471752\begin{cfa}
    17481753y = (* int)x;
    … …  
    17721777\lstDeleteShortInline@%
    17731778\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    1774 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     1779\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    17751780\begin{cfa}
    17761781[double] foo(), foo( int ), foo( double ) {...}
    … …  
    17901795* [ * int ] ( int y ) gp;               $\C{// pointer to function returning pointer to int with int parameter}$
    17911796* [ ] ( int, char ) hp;                 $\C{// pointer to function returning no result with int and char parameters}$
    1792 * [ * int, int ] ( int ) jp;    $\C{// pointer to function returning pointer to int and int with int parameter}$
    1793 \end{cfa}
    1794 Note, a function name cannot be specified:
    1795 \begin{cfa}
    1796 * [ int x ] f () fp;                    $\C{// function name "f" is disallowed}\CRT$
    1797 \end{cfa}
     1797* [ * int, int ] ( int ) jp;    $\C{// pointer to function returning pointer to int and int with int parameter}\CRT$
     1798\end{cfa}
     1799Note, the name of the function pointer is specified last, as for other variable declarations.
    17981800
    17991801Finally, new \CFA declarations may appear together with C declarations in the same program block, but cannot be mixed within a specific declaration.
    … …  
    18521854This provides a much more orthogonal design for library implementors, obviating the need for workarounds such as @std::reference_wrapper@.
    18531855Secondly, \CFA references are rebindable, whereas \CC references have a fixed address.
    1854 \newsavebox{\LstBox}
    1855 \begin{lrbox}{\LstBox}
    1856 \lstset{basicstyle=\footnotesize\linespread{0.9}\sf}
    1857 \begin{cfa}
    1858 int & r = *new( int );
    1859 ...                                                                                     $\C{// non-null reference}$
    1860 delete &r;                                                                      $\C{// unmanaged (programmer) memory-management}$
    1861 r += 1;                                                                         $\C{// undefined reference}$
    1862 \end{cfa}
    1863 \end{lrbox}
    18641856Rebinding allows \CFA references to be default-initialized (\eg to a null pointer\footnote{
    1865 While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any non-managed languages (C/\CC), given that it only handles one of many different error situations:
    1866 \begin{cquote}
    1867 \usebox{\LstBox}
    1868 \end{cquote}
    1869 }%
    1870 ) and point to different addresses throughout their lifetime, like pointers.
     1857While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any non-managed languages (C/\CC), given that it only handles one of many different error situations, \eg using a pointer after its storage is deleted.}) and point to different addresses throughout their lifetime, like pointers.
    18711858Rebinding is accomplished by extending the existing syntax and semantics of the address-of operator in C.
    18721859
    … …  
    18801867\begin{itemize}
    18811868\item
    1882 if @R@ is an rvalue of type {@T &@$_1 \cdots$@ &@$_r$} where $r \ge 1$ references (@&@ symbols) than @&R@ has type {@T `*`&@$_{\color{red}2} \cdots$@ &@$_{\color{red}r}$}, \\ \ie @T@ pointer with $r-1$ references (@&@ symbols).
     1869if @R@ is an rvalue of type {@T &@$_1 \cdots$@ &@$_r$} where $r \ge 1$ references (@&@ symbols) then @&R@ has type {@T `*`&@$_{\color{red}2} \cdots$@ &@$_{\color{red}r}$}, \\ \ie @T@ pointer with $r-1$ references (@&@ symbols).
    18831870       
    18841871\item
    … …  
    19141901\end{cfa}
    19151902This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of explicit definition of a temporary variable or the runtime cost of pass-by-value.
    1916 \CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const hell} problem, in which addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers.
     1903\CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const poisoning} problem~\cite{Taylor10}, in which addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers.
    19171904
    19181905
    … …  
    19281915\begin{tabular}{@{}l@{\hspace{3em}}l|l@{}}
    19291916\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}}      & \multicolumn{1}{c|}{\textbf{C Implicit Hoisting}}     & \multicolumn{1}{c}{\textbf{\CFA}}     \\
    1930 \hline
    19311917\begin{cfa}
    19321918struct S {
    … …  
    20081994The symbol \lstinline+^+ is used for the destructor name because it was the last binary operator that could be used in a unary context.}.
    20091995The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@.
    2010 Like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @?{}(x, ...)@ or @^{}(x, ...)@.
     1996Like other \CFA operators, these names represent the syntax used to explicitly call the constructor or destructor, \eg @s{...}@ or @^s{...}@.
    20111997The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed.
    20121998While the first parameter is informally called the @this@ parameter, as in object-oriented languages, any variable name may be used.
    2013 Both constructors and destructors allow additional parametes after the @this@ parameter for specifying values for initialization/de-initialization\footnote{
     1999Both constructors and destructors allow additional parameters after the @this@ parameter for specifying values for initialization/de-initialization\footnote{
    20142000Destruction parameters are useful for specifying storage-management actions, such as de-initialize but not deallocate.}.
    20152001\begin{cfa}
    … …  
    20182004void ^?{}( VLA & vla ) with ( vla ) { free( data ); } $\C{// destructor}$
    20192005{
    2020         VLA x;                                                                  $\C{// implicit:  ?\{\}( x );}$
    2021 }                                                                                       $\C{// implicit:  ?\^{}\{\}( x );}$
     2006        VLA x;                                                                  $\C{// implicit:\ \ x\{\};}$
     2007}                                                                                       $\C{// implicit:\ \textasciicircum{}x\{\};}$
    20222008\end{cfa}
    20232009@VLA@ is a \newterm{managed type}\footnote{
    … …  
    20442030appropriate care is taken to not recursively call the copy constructor when initializing the second parameter.
    20452031
    2046 \CFA constructors may be explicitly call, like Java, and destructors may be explicitly called, like \CC.
     2032\CFA constructors may be explicitly called, like Java, and destructors may be explicitly called, like \CC.
    20472033Explicit 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.
    2048 While existing call syntax works for explicit calls to constructors and destructors, \CFA also provides a more concise \newterm{operator syntax} for both:
     2034Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls:
    20492035\begin{cfa}
    20502036{
    20512037        VLA  x,            y = { 20, 0x01 },     z = y; $\C{// z points to y}$
    2052         //      ?{}( x );   ?{}( y, 20, 0x01 );   ?{}( z, y );
     2038        //    x{};         y{ 20, 0x01 };          z{ z, y };
    20532039        ^x{};                                                                   $\C{// deallocate x}$
    20542040        x{};                                                                    $\C{// reallocate x}$
    … …  
    20572043        y{ x };                                                                 $\C{// reallocate y, points to x}$
    20582044        x{};                                                                    $\C{// reallocate x, not pointing to y}$
    2059         // ^?{}(z);  ^?{}(y);  ^?{}(x);
     2045        //  ^z{};  ^y{};  ^x{};
    20602046}
    20612047\end{cfa}
    … …  
    20782064In these cases, \CFA provides the initialization syntax \lstinline|S x `@=` {}|, and the object becomes unmanaged, so implicit constructor and destructor calls are not generated.
    20792065Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics.
    2080 The same syntax can be used in a compound literal, \eg \lstinline|a = VLA`@`{ 0, 0x0 }|, to create a C-style literal.
     2066The same syntax can be used in a compound literal, \eg \lstinline|a = (VLA)`@`{ 0, 0x0 }|, to create a C-style literal.
    20812067The 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.
    20822068
    … …  
    21342120
    21352121In C, @0@ has the special property that it is the only ``false'' value;
    2136 from the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true.
     2122by the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true.
    21372123As such, an expression @x@ in any boolean context (such as the condition of an @if@ or @while@ statement, or the arguments to @&&@, @||@, or @?:@\,) can be rewritten as @x != 0@ without changing its semantics.
    21382124Operator overloading in \CFA provides a natural means to implement this truth-value comparison for arbitrary types, but the C type system is not precise enough to distinguish an equality comparison with @0@ from an equality comparison with an arbitrary integer or pointer.
    … …  
    21692155\lstDeleteShortInline@%
    21702156\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
    2171 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}}        & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}}      & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}}   & \multicolumn{1}{c}{\textbf{postfix pointer}}  \\
     2157\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}}     & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}}      & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}}   & \multicolumn{1}{c@{}}{\textbf{postfix pointer}}       \\
    21722158\begin{cfa}
    21732159int |?`h|( int s );
    … …  
    22142200\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
    22152201\lstDeleteShortInline@%
    2216 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2217 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{\CC}}      \\
     2202\begin{tabular}{@{}l@{\hspace{1.25\parindentlnth}}l@{}}
     2203\multicolumn{1}{@{}c@{\hspace{1.25\parindentlnth}}}{\textbf{\CFA}}      & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
    22182204\begin{cfa}
    22192205struct W {
    … …  
    22592245        W w, heavy = { 20 };
    22602246        w = 155|_lb|;
    2261         w = 0b1111|_lb|;       // error, binary unsupported
     2247        // binary unsupported
    22622248        w = 0${\color{red}\LstBasicStyle{'}}$233|_lb|;          // quote separator
    22632249        w = 0x9b|_kg|;
    … …  
    22892275\lstDeleteShortInline@%
    22902276\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2291 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}      & \multicolumn{1}{c}{\textbf{Usage}}    \\
     2277\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
    22922278\begin{cfa}
    22932279const short int `MIN` = -32768;
    … …  
    23072293\begin{cquote}
    23082294\lstDeleteShortInline@%
    2309 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2310 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     2295\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     2296\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    23112297\begin{cfa}
    23122298MIN
    2313 
    23142299MAX
    2315 
    23162300PI
    23172301E
    … …  
    23192303&
    23202304\begin{cfa}
    2321 SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN,
    2322         LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
    2323 SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX,
    2324         LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
     2305CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
     2306UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
    23252307M_PI, M_PIl
    23262308M_E, M_El
    … …  
    23382320\lstDeleteShortInline@%
    23392321\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2340 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}      & \multicolumn{1}{c}{\textbf{Usage}}    \\
     2322\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
    23412323\begin{cfa}
    23422324float `log`( float x );
    … …  
    23572339\lstDeleteShortInline@%
    23582340\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2359 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     2341\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    23602342\begin{cfa}
    23612343log
    … …  
    23852367\lstDeleteShortInline@%
    23862368\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2387 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}      & \multicolumn{1}{c}{\textbf{Usage}}    \\
     2369\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
    23882370\begin{cfa}
    23892371unsigned int `abs`( int );
    … …  
    24042386\lstDeleteShortInline@%
    24052387\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2406 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
     2388\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    24072389\begin{cfa}
    24082390abs
    … …  
    24272409an allocation with a specified character.
    24282410\item[resize]
    2429 an existing allocation to decreased or increased its size.
     2411an existing allocation to decrease or increase its size.
    24302412In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation is copied.
    24312413For an increase in storage size, new storage after the copied data may be filled.
    … …  
    24412423
    24422424\begin{table}
     2425\caption{Storage-Management Operations}
     2426\label{t:StorageManagementOperations}
    24432427\centering
    24442428\lstDeleteShortInline@%
    … …  
    24602444\lstDeleteShortInline~%
    24612445\lstMakeShortInline@%
    2462 \caption{Storage-Management Operations}
    2463 \label{t:StorageManagementOperations}
    24642446\end{table}
    24652447
    24662448\begin{figure}
    24672449\centering
    2468 \begin{cquote}
    2469 \begin{cfa}[aboveskip=0pt]
     2450\begin{cfa}[aboveskip=0pt,xleftmargin=0pt]
    24702451size_t  dim = 10;                                                       $\C{// array dimension}$
    24712452char fill = '\xff';                                                     $\C{// initialization fill value}$
    … …  
    24732454\end{cfa}
    24742455\lstDeleteShortInline@%
    2475 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2476 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{C}}        \\
    2477 \begin{cfa}
     2456\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
     2457\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{c@{}}{\textbf{C}}     \\
     2458\begin{cfa}[xleftmargin=-10pt]
    24782459ip = alloc();
    24792460ip = alloc( fill );
    … …  
    24902471&
    24912472\begin{cfa}
    2492 ip = (int *)malloc( sizeof( int ) );
    2493 ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, sizeof( int ) );
    2494 ip = (int *)malloc( dim * sizeof( int ) );
    2495 ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
    2496 ip = (int *)realloc( ip, 2 * dim * sizeof( int ) );
    2497 ip = (int *)realloc( ip, 4 * dim * sizeof( int ) );
    2498                         memset( ip, fill, 4 * dim * sizeof( int ) );
    2499 ip = memalign( 16, sizeof( int ) );
    2500 ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) );
    2501 ip = memalign( 16, dim * sizeof( int ) );
    2502 ip = memalign( 16, dim * sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
    2503 \end{cfa}
    2504 \end{tabular}
    2505 \lstMakeShortInline@%
    2506 \end{cquote}
     2473ip = (int *)malloc( sizeof(int) );
     2474ip = (int *)malloc( sizeof(int) ); memset( ip, fill, sizeof(int) );
     2475ip = (int *)malloc( dim * sizeof(int) );
     2476ip = (int *)malloc( sizeof(int) ); memset( ip, fill, dim * sizeof(int) );
     2477ip = (int *)realloc( ip, 2 * dim * sizeof(int) );
     2478ip = (int *)realloc( ip, 4 * dim * sizeof(int) ); memset( ip, fill, 4 * dim * sizeof(int));
     2479
     2480ip = memalign( 16, sizeof(int) );
     2481ip = memalign( 16, sizeof(int) ); memset( ip, fill, sizeof(int) );
     2482ip = memalign( 16, dim * sizeof(int) );
     2483ip = memalign( 16, dim * sizeof(int) ); memset( ip, fill, dim * sizeof(int) );
     2484\end{cfa}
     2485\end{tabular}
     2486\lstMakeShortInline@%
    25072487\caption{\CFA versus C Storage-Allocation}
    25082488\label{f:StorageAllocation}
    … …  
    25172497S * as = anew( dim, 2, 3 );                                     $\C{// each array element initialized to 2, 3}$
    25182498\end{cfa}
    2519 Note, \CC can only initialization array elements via the default constructor.
     2499Note, \CC can only initialize array elements via the default constructor.
    25202500
    25212501Finally, the \CFA memory-allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap.
    … …  
    25342514\lstDeleteShortInline@%
    25352515\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    2536 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{c}{\textbf{\CC}}      \\
     2516\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
    25372517\begin{cfa}
    25382518int x = 1, y = 2, z = 3;
    … …  
    25892569\end{cquote}
    25902570There is a weak similarity between the \CFA logical-or operator and the Shell pipe-operator for moving data, where data flows in the correct direction for input but the opposite direction for output.
    2591 
     2571\begin{comment}
    25922572The implicit separator character (space/blank) is a separator not a terminator.
    25932573The rules for implicitly adding the separator are:
    … …  
    26082588}%
    26092589\end{itemize}
     2590\end{comment}
    26102591There are functions to set and get the separator string, and manipulators to toggle separation on and off in the middle of output.
    26112592
    … …  
    26222603\centering
    26232604\lstDeleteShortInline@%
    2624 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}@{\hspace{2\parindentlnth}}l@{}}
    2625 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{@{\hspace{2\parindentlnth}}c}{\textbf{C}}     \\
     2605\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
     2606\multicolumn{1}{@{}c@{\hspace{3\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
    26262607\begin{cfa}
    26272608#include <gmp>
    … …  
    26562637
    26572638
    2658 \section{Evaluation}
     2639\section{Polymorphism Evaluation}
    26592640\label{sec:eval}
    26602641
    2661 Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    2662 In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    2663 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementations}).
     2642\CFA adds parametric polymorphism to C.
     2643A runtime evaluation is performed to compare the cost of alternative styles of polymorphism.
     2644The goal is to compare just the underlying mechanism for implementing different kinds of polymorphism.
     2645% Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
     2646% In fact, it is shown that \CFA's generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
     2647The experiment is a set of generic-stack micro-benchmarks~\cite{CFAStackEvaluation} in C, \CFA, and \CC (see implementations in Appendix~\ref{sec:BenchmarkStackImplementations}).
    26642648Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code.
    26652649A more illustrative comparison measures the costs of idiomatic usage of each language's features.
    … …  
    26922676\end{figure}
    26932677
    2694 The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
     2678The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with parametric polymorphism, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
    26952679The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    26962680hence runtime checks are necessary to safely down-cast objects.
    26972681The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
    2698 Note that the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
     2682Note, the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    26992683
    27002684Figure~\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.
    … …  
    27112695
    27122696\begin{table}
    2713 \centering
    27142697\caption{Properties of benchmark code}
    27152698\label{tab:eval}
     2699\centering
    27162700\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    27172701\begin{tabular}{rrrrr}
    … …  
    27262710The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
    27272711this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
    2728 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @short@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
     2712By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair because of equivalent storage layout, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
    27292713\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    2730 The outlier in the graph for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code.
    2731 The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA could easily perform these optimizations.
     2714The outlier for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code.
     2715The gcc compiler is unable to optimize some dead code and condense nested calls;
     2716a compiler designed for \CFA could easily perform these optimizations.
    27322717Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    27332718
    … …  
    27412726Line-count is a fairly rough measure of code complexity;
    27422727another important factor is how much type information the programmer must specify manually, especially where that information is not compiler-checked.
    2743 Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of untype-checked downcasts, \eg @object@ to @integer@ when popping a stack.
     2728Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts, \eg @object@ to @integer@ when popping a stack.
    27442729To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
    27452730The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
    27462731The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
    27472732
     2733We conjecture these results scale across most generic data-types as the underlying polymorphism implement is constant.
     2734
    27482735
    27492736\section{Related Work}
    … …  
    27512738
    27522739\subsection{Polymorphism}
     2740
     2741ML~\cite{ML} was the first language to support parametric polymorphism.
     2742Like \CFA, it supports universal type parameters, but not the use of assertions and traits to constrain type arguments.
     2743Haskell~\cite{Haskell10} combines ML-style polymorphism, polymorphic data types, and type inference with the notion of type classes, collections of overloadable methods that correspond in intent to traits in \CFA.
     2744Unlike \CFA, Haskell requires an explicit association between types and their classes that specifies the implementation of operations.
     2745These associations determine the functions that are assertion arguments for particular combinations of class and type, in contrast to \CFA where the assertion arguments are selected at function call sites based upon the set of operations in scope at that point.
     2746Haskell also severely restricts the use of overloading: an overloaded name can only be associated with a single class, and methods with overloaded names can only be defined as part of instance declarations.
    27532747
    27542748\CC provides three disjoint polymorphic extensions to C: overloading, inheritance, and templates.
    … …  
    28042798Go does not have tuples but supports MRVF.
    28052799Java'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.
    2806 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and~\cite{Scala}, which decompose tuples using pattern matching.
     2800Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml}, Haskell, and Scala~\cite{Scala}, which decompose tuples using pattern matching.
    28072801
    28082802
    … …  
    28352829Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    28362830
    2837 There is ongoing work on a wide range of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules.
    2838 While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these extensions.
    2839 There are also interesting future directions for the polymorphism design.
    2840 Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions.
    2841 \CFA polymorphic functions use dynamic virtual-dispatch;
    2842 the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code.
     2831While all examples in the paper compile and run, a public beta-release of \CFA will take 6--8 months to reduce compilation time, provide better debugging, and add a few more libraries.
     2832There is also new work on a number of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, and modules.
     2833While \CFA polymorphic functions use dynamic virtual-dispatch with low runtime overhead (see Section~\ref{sec:eval}), it is not as low as \CC template-inlining.
     2834Hence it may be beneficial to provide a mechanism for performance-sensitive code.
    28432835Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization).
    28442836These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    … …  
    28492841
    28502842The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, Andrew Beach and Brice Dobry on the features described in this paper, and thank Magnus Madsen for feedback on the writing.
    2851 This work is supported by a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada.
    2852 
    2853 
     2843Funding for this project has been provided by Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada.
     2844
     2845{%
     2846\fontsize{9bp}{12bp}\selectfont%
    28542847\bibliography{pl}
    2855 
     2848}%
    28562849
    28572850\appendix
Note: See TracChangeset for help on using the changeset viewer.