Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    raa5fdac rc8ad5d9  
    7474\setlength{\gcolumnposn}{3.5in}
    7575\setlength{\columnposn}{\gcolumnposn}
    76 
    7776\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
    7877\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
    … …  
    192191This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    193192Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     193
    194194The 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.
    195195Prior 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.
    … …  
    209209
    210210\section{Introduction}
     211
    211212The 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.
    212213This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    … …  
    237238\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.
    238239
    239 \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).
     240\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).
    240241Ultimately, a compiler is necessary for advanced features and optimal performance.
    241242All features discussed in this paper are working, unless otherwise stated as under construction.
    … …  
    265266Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads.
    266267As an example:
    267 \begin{cfa}
    268 int max = 2147483647;                                           $\C[4in]{// (1)}$
    269 double max = 1.7976931348623157E+308;           $\C{// (2)}$
     268
     269\begin{cfa}
     270int max = 2147483647;                                   $\C[4in]{// (1)}$
     271double max = 1.7976931348623157E+308;   $\C{// (2)}$
    270272int max( int a, int b ) { return a < b ? b : a; }  $\C{// (3)}$
    271273double max( double a, double b ) { return a < b ? b : a; }  $\C{// (4)}\CRT$
    … …  
    327329A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array:
    328330\begin{cfa}
    329 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
    330                                 int (* compar)( const void *, const void * ));
     331void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (* compar)( const void *, const void * ));
    331332int comp( const void * t1, const void * t2 ) {
    332333         return *(double *)t1 < *(double *)t2 ? -1 : *(double *)t2 < *(double *)t1 ? 1 : 0;
    … …  
    376377Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    377378
    378 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}).
    379 \begin{cfa}
    380 forall( otype `T` ) {                                                   $\C{// distribution block, add forall qualifier to declarations}$
     379Under construction is a mechanism to distribute @forall@ over routines/types, where each block declaration is prefixed with the initial @forall@ clause significantly reducing duplication (see @stack@ examples in Section~\ref{sec:eval}):
     380\begin{cfa}
     381forall( otype `T` ) {                                                   $\C{// forall block}$
    381382        struct stack { stack_node(`T`) * head; };       $\C{// generic type}$
    382         inline {                                                                        $\C{// nested distribution block, add forall/inline to declarations}$
    383                 void push( stack(`T`) & s, `T` value ) ...      $\C{// generic operations}$
    384                 T pop( stack(`T`) & s ) ...
    385         }
     383        void push( stack(`T`) & s, `T` value ) ...      $\C{// generic operations}$
     384        T pop( stack(`T`) & s ) ...
    386385}
    387386\end{cfa}
    … …  
    391390
    392391\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:
    393 \begin{cquote}
    394 \lstDeleteShortInline@%
    395 \begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
    396 \begin{cfa}
    397 trait `sumable`( otype T ) {
    398         void `?{}`( T &, zero_t ); // 0 literal constructor
    399         T ?+?( T, T );                   // assortment of additions
    400         T `?+=?`( T &, T );
    401         T ++?( T & );
    402         T ?++( T & );
     392\begin{cfa}
     393trait `summable`( otype T ) {
     394        void ?{}( T *, zero_t );                                $\C{// constructor from 0 literal}$
     395        T ?+?( T, T );                                                  $\C{// assortment of additions}$
     396        T ?+=?( T *, T );
     397        T ++?( T * );
     398        T ?++( T * );
    403399};
    404 \end{cfa}
    405 &
    406 \begin{cfa}
    407 forall( otype T `| sumable( T )` ) // use trait
    408 T sum( T a[$\,$], size_t size ) {
    409         `T` total = { `0` };  // initialize by 0 constructor
    410         for ( size_t i = 0; i < size; i += 1 )
    411                 total `+=` a[i]; // select appropriate +
     400forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) {$\C{// use trait}$
     401        `T` total = { `0` };                                    $\C{// instantiate T from 0 by calling its constructor}$
     402        for ( unsigned int i = 0; i < size; i += 1 ) total `+=` a[i]; $\C{// select appropriate +}$
    412403        return total;
    413404}
    414405\end{cfa}
    415 \end{tabular}
    416 \lstMakeShortInline@%
    417 \end{cquote}
    418406
    419407In 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:
    … …  
    478466
    479467A 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:
    480 \begin{cquote}
    481 \lstDeleteShortInline@%
    482 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    483468\begin{cfa}
    484469forall( otype R, otype S ) struct pair {
    485         R first;        S second;
     470        R first;
     471        S second;
    486472};
    487 `forall( otype T )` // dynamic
    488 T value( pair(const char *, T) p ) { return p.second; }
    489 `forall( dtype F, otype T )` // dtype-static (concrete)
    490 T value( pair(F *, T * ) p) { return *p.second; }
    491 \end{cfa}
    492 &
    493 \begin{cfa}
    494 pair(const char *, int) p = {"magic", 42}; // concrete
     473forall( otype T ) T value( pair( const char *, T ) p ) { return p.second; } $\C{// dynamic}$
     474forall( dtype F, otype T ) T value( pair( F *, T * ) p ) { return *p.second; } $\C{// dtype-static (concrete)}$
     475
     476pair( const char *, int ) p = { "magic", 42 }; $\C{// concrete}$
    495477int i = value( p );
    496 pair(void *, int *) q = { 0, &p.second }; // concrete
     478pair( void *, int * ) q = { 0, &p.second }; $\C{// concrete}$
    497479i = value( q );
    498480double d = 1.0;
    499 pair(double *, double *) r = { &d, &d }; // concrete
     481pair( double *, double * ) r = { &d, &d }; $\C{// concrete}$
    500482d = value( r );
    501483\end{cfa}
    502 \end{tabular}
    503 \lstMakeShortInline@%
    504 \end{cquote}
    505484
    506485\CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}.
    … …  
    589568Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    590569Sometimes information is only used for type-checking and can be omitted at runtime, \eg:
    591 \begin{cquote}
    592 \lstDeleteShortInline@%
    593 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    594570\begin{cfa}
    595571forall( dtype Unit ) struct scalar { unsigned long value; };
    596572struct metres {};
    597573struct litres {};
     574
    598575forall( dtype U ) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
    599576        return (scalar(U)){ a.value + b.value };
    600577}
    601 \end{cfa}
    602 &
    603 \begin{cfa}
    604 scalar(metres) half_marathon = { 21_098 };
    605 scalar(litres) pool = { 2_500_000 };
    606 scalar(metres) marathon = half_marathon +
    607                                                         half_marathon;
    608 scalar(litres) two_pools = pool + pool;
    609 `marathon + pool;`      // compilation ERROR
    610 \end{cfa}
    611 \end{tabular}
    612 \lstMakeShortInline@%
    613 \end{cquote}
     578scalar(metres) half_marathon = { 21_093 };
     579scalar(litres) swimming_pool = { 2_500_000 };
     580scalar(metres) marathon = half_marathon + half_marathon;
     581scalar(litres) two_pools = swimming_pool + swimming_pool;
     582marathon + swimming_pool;                                       $\C{// compilation ERROR}$
     583\end{cfa}
    614584@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 @?+?@.
    615585These implementations may even be separately compiled, unlike \CC template functions.
    … …  
    12191189                `LIF:` if ( ... ) {
    12201190                        `LF:` for ( ... ) {
    1221                                 ... break `LC`; ...
    1222                                 ... break `LS`; ...
    1223                                 ... break `LIF`; ...
    1224                                 ... continue `LF;` ...
    1225                                 ... break `LF`; ...
     1191                                `LW:` while ( ... ) {
     1192                                        ... break `LC`; ...
     1193                                        ... break `LS`; ...
     1194                                        ... break `LIF`; ...
     1195                                        ... continue `LF;` ...
     1196                                        ... break `LF`; ...
     1197                                        ... continue `LW`; ...
     1198                                        ... break `LW`; ...
     1199                                } // while
    12261200                        } // for
    12271201                } else {
    … …  
    12391213                if ( ... ) {
    12401214                        for ( ... ) {
    1241                                 ... goto `LC`; ...
    1242                                 ... goto `LS`; ...
    1243                                 ... goto `LIF`; ...
    1244                                 ... goto `LFC`; ...
    1245                                 ... goto `LFB`; ...
     1215                                while ( ... ) {
     1216                                        ... goto `LC`; ...
     1217                                        ... goto `LS`; ...
     1218                                        ... goto `LIF`; ...
     1219                                        ... goto `LFC`; ...
     1220                                        ... goto `LFB`; ...
     1221                                        ... goto `LWC`; ...
     1222                                        ... goto `LWB`; ...
     1223                                  `LWC`: ; } `LWB:` ;
    12461224                          `LFC:` ; } `LFB:` ;
    12471225                } else {
    … …  
    12651243// continue loop
    12661244// terminate loop
     1245// continue loop
     1246// terminate loop
    12671247
    12681248
    12691249
    12701250// terminate if
     1251
     1252
    12711253
    12721254\end{cfa}
    … …  
    14291411\label{s:WithStatement}
    14301412
    1431 Heterogeneous data is often aggregated into a structure/union.
    1432 To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate field-qualification by opening a scope containing the field identifiers.
    1433 \begin{cquote}
    1434 \vspace*{-\baselineskip}%???
    1435 \lstDeleteShortInline@%
    1436 \begin{cfa}
    1437 struct S { char c; int i; double d; };
     1413Grouping heterogeneous data into \newterm{aggregate}s (structure/union) is a common programming practice, and an aggregate can be further organized into more complex structures, such as arrays and containers:
     1414\begin{cfa}
     1415struct S {                                                                      $\C{// aggregate}$
     1416        char c;                                                                 $\C{// fields}$
     1417        int i;
     1418        double d;
     1419};
     1420S s, as[10];
     1421\end{cfa}
     1422However, functions manipulating aggregates must repeat the aggregate name to access its containing fields:
     1423\begin{cfa}
     1424void f( S s ) {
     1425        `s.`c; `s.`i; `s.`d;                                    $\C{// access containing fields}$
     1426}
     1427\end{cfa}
     1428which extends to multiple levels of qualification for nested aggregates.
     1429A similar situation occurs in object-oriented programming, \eg \CC:
     1430\begin{C++}
     1431struct S {
     1432        char c;                                                                 $\C{// fields}$
     1433        int i;
     1434        double d;
     1435        void f() {                                                              $\C{// implicit ``this'' aggregate}$
     1436                `this->`c; `this->`i; `this->`d;        $\C{// access containing fields}$
     1437        }
     1438}
     1439\end{C++}
     1440Object-oriented nesting of member functions in a \lstinline[language=C++]@class/struct@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping.
     1441However, for other aggregate parameters, qualification is necessary:
     1442\begin{cfa}
    14381443struct T { double m, n; };
    1439 // multiple aggregate parameters
    1440 \end{cfa}
    1441 \begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
    1442 \begin{cfa}
    1443 void f( S & s, T & t ) {
    1444         `s.`c; `s.`i; `s.`d;
    1445         `t.`m; `t.`n;
    1446 }
    1447 \end{cfa}
    1448 &
    1449 \begin{cfa}
    1450 void f( S & s, T & t ) `with ( s, t )` {
    1451         c; i; d;                // no qualification
    1452         m; n;
    1453 }
    1454 \end{cfa}
    1455 \end{tabular}
    1456 \lstMakeShortInline@%
    1457 \end{cquote}
    1458 Object-oriented programming languages only provide implicit qualification for the receiver.
     1444int S::f( T & t ) {                                                     $\C{// multiple aggregate parameters}$
     1445        c; i; d;                                                                $\C{\color{red}// this--{\textgreater}.c, this--{\textgreater}.i, this--{\textgreater}.d}$
     1446        `t.`m; `t.`n;                                                   $\C{// must qualify}$
     1447}
     1448\end{cfa}
     1449
     1450To simplify the programmer experience, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate qualification to fields by opening a scope containing the field identifiers.
     1451Hence, the qualified fields become variables with the side-effect that it is easier to optimizing field references in a block.
     1452\begin{cfa}
     1453void f( S & this ) `with ( this )` {            $\C{// with statement}$
     1454        c; i; d;                                                                $\C{\color{red}// this.c, this.i, this.d}$
     1455}
     1456\end{cfa}
     1457with the generality of opening multiple aggregate-parameters:
     1458\begin{cfa}
     1459void f( S & s, T & t ) `with ( s, t )` {                $\C{// multiple aggregate parameters}$
     1460        c; i; d;                                                                $\C{\color{red}// s.c, s.i, s.d}$
     1461        m; n;                                                                   $\C{\color{red}// t.m, t.n}$
     1462}
     1463\end{cfa}
    14591464
    14601465In detail, the @with@ statement has the form:
    … …  
    14691474The object is the implicit qualifier for the open structure-fields.
    14701475
    1471 All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right.
     1476All expressions in the expression list are open in parallel within the compound statement.
     1477This semantic is different from Pascal, which nests the openings from left to right.
    14721478The difference between parallel and nesting occurs for fields with the same name and type:
    14731479\begin{cfa}
    … …  
    22552261\begin{cfa}
    22562262MIN
    2257 
    22582263MAX
    2259 
    22602264PI
    22612265E
    … …  
    22632267&
    22642268\begin{cfa}
    2265 SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN,
    2266         LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
    2267 SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX,
    2268         LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
     2269SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
     2270SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
    22692271M_PI, M_PIl
    22702272M_E, M_El
    … …  
    24392441ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
    24402442ip = (int *)realloc( ip, 2 * dim * sizeof( int ) );
    2441 ip = (int *)realloc( ip, 4 * dim * sizeof( int ) );
    2442                         memset( ip, fill, 4 * dim * sizeof( int ) );
     2443ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) );
     2444
    24432445ip = memalign( 16, sizeof( int ) );
    24442446ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) );
    … …  
    26052607Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    26062608In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    2607 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}).
     2609This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
    26082610Since 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.
    26092611A more illustrative comparison measures the costs of idiomatic usage of each language's features.
    … …  
    28222824\appendix
    28232825
    2824 \section{Benchmark Stack Implementations}
    2825 \label{sec:BenchmarkStackImplementations}
    2826 
    2827 Throughout, @/***/@ designates a counted redundant type annotation; code reformatted slightly for brevity.
    2828 
    2829 
    2830 \subsection{C}
    2831 
    2832 \begin{flushleft}
    2833 \lstDeleteShortInline@%
    2834 \begin{tabular}{@{}l@{\hspace{1.8\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
    2835 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
    2836 typedef struct node {
     2826\section{Benchmark Stack Implementation}
     2827\label{sec:BenchmarkStackImplementation}
     2828
     2829Throughout, @/***/@ designates a counted redundant type annotation; code reformatted for brevity.
     2830
     2831\smallskip\noindent
     2832C
     2833\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2834struct stack_node {
    28372835        void * value;
    2838         struct node * next;
    2839 } node;
    2840 typedef struct stack {
    2841         struct node * head;
    2842 } stack;
    2843 void copy_stack( stack * s, const stack * t,
    2844                                 void * (*copy)( const void * ) ) {
    2845         node ** cr = &s->head;
    2846         for (node * nx = t->head; nx; nx = nx->next) {
    2847                 *cr = malloc( sizeof(node) ); /***/
    2848                 (*cr)->value = copy( nx->value );
    2849                 cr = &(*cr)->next;
    2850         }
    2851         *cr = NULL;
    2852 }
    2853 void clear_stack( stack * s, void (* free_el)( void * ) ) {
    2854         for ( node * nx = s->head; nx; ) {
    2855                 node * cr = nx;
    2856                 nx = cr->next;
    2857                 free_el( cr->value );
    2858                 free( cr );
     2836        struct stack_node * next;
     2837};
     2838struct stack { struct stack_node* head; };
     2839void clear_stack( struct stack * s, void (*free_el)( void * ) ) {
     2840        for ( struct stack_node * next = s->head; next; ) {
     2841                struct stack_node * crnt = next;
     2842                next = crnt->next;
     2843                free_el( crnt->value );
     2844                free( crnt );
    28592845        }
    28602846        s->head = NULL;
    28612847}
    2862 \end{cfa}
    2863 &
    2864 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
    2865 stack new_stack() {
    2866         return (stack){ NULL }; /***/
    2867 }
    2868 stack * assign_stack( stack * s, const stack * t,
    2869                                 void * (*copy_el)( const void * ),
    2870                                 void (*free_el)( void * ) ) {
     2848struct stack new_stack() { return (struct stack){ NULL }; /***/ }
     2849void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) {
     2850        struct stack_node ** crnt = &s->head;
     2851        for ( struct stack_node * next = t->head; next; next = next->next ) {
     2852                *crnt = malloc( sizeof(struct stack_node) ); /***/
     2853                (*crnt)->value = copy( next->value );
     2854                crnt = &(*crnt)->next;
     2855        }
     2856        *crnt = NULL;
     2857}
     2858struct stack * assign_stack( struct stack * s, const struct stack * t,
     2859                void * (*copy_el)( const void * ), void (*free_el)( void * ) ) {
    28712860        if ( s->head == t->head ) return s;
    28722861        clear_stack( s, free_el ); /***/
    … …  
    28742863        return s;
    28752864}
    2876 _Bool stack_empty( const stack * s ) {
    2877          return s->head == NULL;
    2878 }
    2879 void push_stack( stack * s, void * v ) {
    2880         node * n = malloc(sizeof(node)); /***/
    2881         *n = (node){ v, s->head }; /***/
     2865_Bool stack_empty( const struct stack * s ) { return s->head == NULL; }
     2866void push_stack( struct stack * s, void * v ) {
     2867        struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/
     2868        *n = (struct stack_node){ v, s->head }; /***/
    28822869        s->head = n;
    28832870}
    2884 void * pop_stack( stack * s ) {
    2885         node * n = s->head;
     2871void * pop_stack( struct stack * s ) {
     2872        struct stack_node * n = s->head;
    28862873        s->head = n->next;
    28872874        void * v = n->value;
    … …  
    28902877}
    28912878\end{cfa}
    2892 \end{tabular}
    2893 \lstMakeShortInline@%
    2894 \end{flushleft}
    2895 
    2896 
    2897 \subsection{\CFA}
    2898 \label{s:CforallStack}
    2899 
    2900 \begin{flushleft}
    2901 \lstDeleteShortInline@%
    2902 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
    2903 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     2879
     2880\medskip\noindent
     2881\CFA
     2882\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     2883forall( otype T ) struct stack_node {
     2884        T value;
     2885        stack_node(T) * next;
     2886};
     2887forall( otype T ) struct stack { stack_node(T) * head; };
     2888forall( otype T ) void clear( stack(T) & s ) with( s ) {
     2889        for ( stack_node(T) * next = head; next; ) {
     2890                stack_node(T) * crnt = next;
     2891                next = crnt->next;
     2892                ^(*crnt){};
     2893                free(crnt);
     2894        }
     2895        head = 0;
     2896}
     2897forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2898forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) {
     2899        stack_node(T) ** crnt = &s.head;
     2900        for ( stack_node(T) * next = t.head; next; next = next->next ) {
     2901                *crnt = alloc();
     2902                ((*crnt)->value){ next->value };
     2903                crnt = &(*crnt)->next;
     2904        }
     2905        *crnt = 0;
     2906}
     2907forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2908        if ( s.head == t.head ) return s;
     2909        clear( s );
     2910        s{ t };
     2911        return s;
     2912}
     2913forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
     2914forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2915forall( otype T ) void push( stack(T) & s, T value ) with( s ) {
     2916        stack_node(T) * n = alloc();
     2917        (*n){ value, head };
     2918        head = n;
     2919}
     2920forall( otype T ) T pop( stack(T) & s ) with( s ) {
     2921        stack_node(T) * n = head;
     2922        head = n->next;
     2923        T v = n->value;
     2924        ^(*n){};
     2925        free( n );
     2926        return v;
     2927}
     2928\end{cfa}
     2929
     2930\begin{comment}
    29042931forall( otype T ) {
    2905         struct node {
     2932        struct stack_node {
    29062933                T value;
    2907                 node(T) * next;
     2934                stack_node(T) * next;
    29082935        };
    2909         struct stack { node(T) * head; };
    2910         void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    2911         void ?{}( stack(T) & s, stack(T) t ) {
    2912                 node(T) ** cr = &s.head;
    2913                 for ( node(T) * nx = t.head; nx; nx = nx->next ) {
    2914                         *cr = alloc();
    2915                         ((*cr)->value){ nx->value };
    2916                         cr = &(*cr)->next;
    2917                 }
    2918                 *cr = 0;
    2919         }
     2936        struct stack { stack_node(T) * head; };
    29202937        void clear( stack(T) & s ) with( s ) {
    2921                 for ( node(T) * nx = head; nx; ) {
    2922                         node(T) * cr = nx;
    2923                         nx = cr->next;
    2924                         ^(*cr){};
    2925                         free(cr);
     2938                for ( stack_node(T) * next = head; next; ) {
     2939                        stack_node(T) * crnt = next;
     2940                        next = crnt->next;
     2941                        ^(*crnt){};
     2942                        free(crnt);
    29262943                }
    29272944                head = 0;
    29282945        }
    2929 \end{cfa}
    2930 &
    2931 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
    2932         void ^?{}( stack(T) & s) { clear( s ); }
     2946        void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2947        void ?{}( stack(T) & s, stack(T) t ) {
     2948                stack_node(T) ** crnt = &s.head;
     2949                for ( stack_node(T) * next = t.head; next; next = next->next ) {
     2950                        *crnt = alloc();
     2951                        ((*crnt)->value){ next->value };
     2952                        crnt = &(*crnt)->next;
     2953                }
     2954                *crnt = 0;
     2955        }
    29332956        stack(T) ?=?( stack(T) & s, stack(T) t ) {
    29342957                if ( s.head == t.head ) return s;
    … …  
    29372960                return s;
    29382961        }
    2939         _Bool empty( const stack(T) & s ) {
    2940                 return s.head == 0;
    2941         }
     2962        void ^?{}( stack(T) & s) { clear( s ); }
     2963        _Bool empty( const stack(T) & s ) { return s.head == 0; }
    29422964        void push( stack(T) & s, T value ) with( s ) {
    2943                 node(T) * n = alloc();
     2965                stack_node(T) * n = alloc();
    29442966                (*n){ value, head };
    29452967                head = n;
    29462968        }
    29472969        T pop( stack(T) & s ) with( s ) {
    2948                 node(T) * n = head;
     2970                stack_node(T) * n = head;
    29492971                head = n->next;
    29502972                T v = n->value;
    … …  
    29542976        }
    29552977}
    2956 
    2957 \end{cfa}
    2958 \end{tabular}
    2959 \lstMakeShortInline@%
    2960 \end{flushleft}
    2961 
    2962 
    2963 \subsection{\CC}
    2964 
    2965 \begin{flushleft}
    2966 \lstDeleteShortInline@%
    2967 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
    2968 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     2978\end{comment}
     2979
     2980\medskip\noindent
     2981\CC
     2982\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    29692983template<typename T> struct stack {
    29702984        struct node {
    29712985                T value;
    29722986                node * next;
    2973                 node( const T & v, node * n = nullptr ) :
    2974                         value( v ), next( n ) {}
     2987                node( const T & v, node * n = nullptr ) : value( v ), next( n ) {}
    29752988        };
    29762989        node * head;
    2977         void copy( const stack<T> & o ) {
    2978                 node ** cr = &head;
    2979                 for ( node * nx = o.head; nx; nx = nx->next ) {
    2980                         *cr = new node{ nx->value }; /***/
    2981                         cr = &(*cr)->next;
    2982                 }
    2983                 *cr = nullptr;
    2984         }
     2990        stack() : head( nullptr ) {}
     2991        stack( const stack<T> & o ) { copy( o ); }
    29852992        void clear() {
    2986                 for ( node * nx = head; nx; ) {
    2987                         node * cr = nx;
    2988                         nx = cr->next;
    2989                         delete cr;
     2993                for ( node * next = head; next; ) {
     2994                        node * crnt = next;
     2995                        next = crnt->next;
     2996                        delete crnt;
    29902997                }
    29912998                head = nullptr;
    29922999        }
    2993 \end{cfa}
    2994 &
    2995 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
    2996         stack() : head( nullptr ) {}
    2997         stack( const stack<T> & o ) { copy( o ); }
     3000        void copy( const stack<T> & o ) {
     3001                node ** crnt = &head;
     3002                for ( node * next = o.head; next; next = next->next ) {
     3003                        *crnt = new node{ next->value }; /***/
     3004                        crnt = &(*crnt)->next;
     3005                }
     3006                *crnt = nullptr;
     3007        }
    29983008        ~stack() { clear(); }
    2999         stack & operator=( const stack<T> & o ) {
     3009        stack & operator= ( const stack<T> & o ) {
    30003010                if ( this == &o ) return *this;
    30013011                clear();
    … …  
    30043014        }
    30053015        bool empty() const { return head == nullptr; }
    3006         void push( const T & value ) {
    3007                 head = new node{ value, head };  /***/
    3008         }
     3016        void push( const T & value ) { head = new node{ value, head };  /***/ }
    30093017        T pop() {
    30103018                node * n = head;
    … …  
    30153023        }
    30163024};
    3017 
    3018 
    3019 
    3020 \end{cfa}
    3021 \end{tabular}
    3022 \lstMakeShortInline@%
    3023 \end{flushleft}
    3024 
    3025 
    3026 \subsection{\CCV}
    3027 
    3028 \begin{flushleft}
    3029 \lstDeleteShortInline@%
    3030 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
    3031 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     3025\end{cfa}
     3026
     3027\medskip\noindent
     3028\CCV
     3029\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    30323030struct stack {
    30333031        struct node {
    30343032                ptr<object> value;
    30353033                node * next;
    3036                 node( const object & v, node * n = nullptr ) :
    3037                                 value( v.new_copy() ), next( n ) {}
     3034                node( const object & v, node * n = nullptr ) : value( v.new_copy() ), next( n ) {}
    30383035        };
    30393036        node * head;
    3040         void copy( const stack & o ) {
    3041                 node ** cr = &head;
    3042                 for ( node * nx = o.head; nx; nx = nx->next ) {
    3043                         *cr = new node{ *nx->value }; /***/
    3044                         cr = &(*cr)->next;
    3045                 }
    3046                 *cr = nullptr;
    3047         }
    30483037        void clear() {
    3049                 for ( node * nx = head; nx; ) {
    3050                         node * cr = nx;
    3051                         nx = cr->next;
    3052                         delete cr;
     3038                for ( node * next = head; next; ) {
     3039                        node * crnt = next;
     3040                        next = crnt->next;
     3041                        delete crnt;
    30533042                }
    30543043                head = nullptr;
    30553044        }
    3056 \end{cfa}
    3057 &
    3058 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     3045        void copy( const stack & o ) {
     3046                node ** crnt = &head;
     3047                for ( node * next = o.head; next; next = next->next ) {
     3048                        *crnt = new node{ *next->value }; /***/
     3049                        crnt = &(*crnt)->next;
     3050                }
     3051                *crnt = nullptr;
     3052        }
    30593053        stack() : head( nullptr ) {}
    30603054        stack( const stack & o ) { copy( o ); }
    30613055        ~stack() { clear(); }
    3062         stack & operator=( const stack & o ) {
     3056        stack & operator= ( const stack & o ) {
    30633057                if ( this == &o ) return *this;
    30643058                clear();
    … …  
    30673061        }
    30683062        bool empty() const { return head == nullptr; }
    3069         void push( const object & value ) {
    3070                 head = new node{ value, head }; /***/
    3071         }
     3063        void push( const object & value ) { head = new node{ value, head }; /***/ }
    30723064        ptr<object> pop() {
    30733065                node * n = head;
    … …  
    30783070        }
    30793071};
    3080 
    3081 
    3082 
    3083 \end{cfa}
    3084 \end{tabular}
    3085 \lstMakeShortInline@%
    3086 \end{flushleft}
     3072\end{cfa}
    30873073
    30883074
Note: See TracChangeset for help on using the changeset viewer.