Changeset aa5fdac


Ignore:
Timestamp:
Apr 28, 2018, 9:18:47 AM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, with_gc
Children:
ac4dad2
Parents:
a87c86f
Message:

shorten sections, add small amount of new material, redo stack code at end

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    ra87c86f raa5fdac  
    7474\setlength{\gcolumnposn}{3.5in}
    7575\setlength{\columnposn}{\gcolumnposn}
     76
    7677\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}}}}
    7778\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
    … …  
    191192This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    192193Nevertheless, 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 
    212211The 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.
    213212This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    … …  
    238237\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.
    239238
    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).
     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).
    241240Ultimately, a compiler is necessary for advanced features and optimal performance.
    242241All features discussed in this paper are working, unless otherwise stated as under construction.
    … …  
    266265Code 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.
    267266As an example:
    268 
    269 \begin{cfa}
    270 int max = 2147483647;                                   $\C[4in]{// (1)}$
    271 double max = 1.7976931348623157E+308;   $\C{// (2)}$
     267\begin{cfa}
     268int max = 2147483647;                                           $\C[4in]{// (1)}$
     269double max = 1.7976931348623157E+308;           $\C{// (2)}$
    272270int max( int a, int b ) { return a < b ? b : a; }  $\C{// (3)}$
    273271double max( double a, double b ) { return a < b ? b : a; }  $\C{// (4)}\CRT$
    … …  
    329327A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array:
    330328\begin{cfa}
    331 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, int (* compar)( const void *, const void * ));
     329void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
     330                                int (* compar)( const void *, const void * ));
    332331int comp( const void * t1, const void * t2 ) {
    333332         return *(double *)t1 < *(double *)t2 ? -1 : *(double *)t2 < *(double *)t1 ? 1 : 0;
    … …  
    377376Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    378377
    379 Under 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}
    381 forall( otype `T` ) {                                                   $\C{// forall block}$
     378To 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}
     380forall( otype `T` ) {                                                   $\C{// distribution block, add forall qualifier to declarations}$
    382381        struct stack { stack_node(`T`) * head; };       $\C{// generic type}$
    383         void push( stack(`T`) & s, `T` value ) ...      $\C{// generic operations}$
    384         T pop( stack(`T`) & s ) ...
     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        }
    385386}
    386387\end{cfa}
    … …  
    390391
    391392\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:
    392 \begin{cfa}
    393 trait `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 * );
     393\begin{cquote}
     394\lstDeleteShortInline@%
     395\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
     396\begin{cfa}
     397trait `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 & );
    399403};
    400 forall( 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 +}$
     404\end{cfa}
     405&
     406\begin{cfa}
     407forall( otype T `| sumable( T )` ) // use trait
     408T 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 +
    403412        return total;
    404413}
    405414\end{cfa}
     415\end{tabular}
     416\lstMakeShortInline@%
     417\end{cquote}
    406418
    407419In 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:
    … …  
    466478
    467479A 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@{}}
    468483\begin{cfa}
    469484forall( otype R, otype S ) struct pair {
    470         R first;
    471         S second;
     485        R first;        S second;
    472486};
    473 forall( otype T ) T value( pair( const char *, T ) p ) { return p.second; } $\C{// dynamic}$
    474 forall( dtype F, otype T ) T value( pair( F *, T * ) p ) { return *p.second; } $\C{// dtype-static (concrete)}$
    475 
    476 pair( const char *, int ) p = { "magic", 42 }; $\C{// concrete}$
     487`forall( otype T )` // dynamic
     488T value( pair(const char *, T) p ) { return p.second; }
     489`forall( dtype F, otype T )` // dtype-static (concrete)
     490T value( pair(F *, T * ) p) { return *p.second; }
     491\end{cfa}
     492&
     493\begin{cfa}
     494pair(const char *, int) p = {"magic", 42}; // concrete
    477495int i = value( p );
    478 pair( void *, int * ) q = { 0, &p.second }; $\C{// concrete}$
     496pair(void *, int *) q = { 0, &p.second }; // concrete
    479497i = value( q );
    480498double d = 1.0;
    481 pair( double *, double * ) r = { &d, &d }; $\C{// concrete}$
     499pair(double *, double *) r = { &d, &d }; // concrete
    482500d = value( r );
    483501\end{cfa}
     502\end{tabular}
     503\lstMakeShortInline@%
     504\end{cquote}
    484505
    485506\CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}.
    … …  
    568589Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    569590Sometimes 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@{}}
    570594\begin{cfa}
    571595forall( dtype Unit ) struct scalar { unsigned long value; };
    572596struct metres {};
    573597struct litres {};
    574 
    575598forall( dtype U ) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
    576599        return (scalar(U)){ a.value + b.value };
    577600}
    578 scalar(metres) half_marathon = { 21_093 };
    579 scalar(litres) swimming_pool = { 2_500_000 };
    580 scalar(metres) marathon = half_marathon + half_marathon;
    581 scalar(litres) two_pools = swimming_pool + swimming_pool;
    582 marathon + swimming_pool;                                       $\C{// compilation ERROR}$
    583 \end{cfa}
     601\end{cfa}
     602&
     603\begin{cfa}
     604scalar(metres) half_marathon = { 21_098 };
     605scalar(litres) pool = { 2_500_000 };
     606scalar(metres) marathon = half_marathon +
     607                                                        half_marathon;
     608scalar(litres) two_pools = pool + pool;
     609`marathon + pool;`      // compilation ERROR
     610\end{cfa}
     611\end{tabular}
     612\lstMakeShortInline@%
     613\end{cquote}
    584614@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 @?+?@.
    585615These implementations may even be separately compiled, unlike \CC template functions.
    … …  
    11891219                `LIF:` if ( ... ) {
    11901220                        `LF:` for ( ... ) {
    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
     1221                                ... break `LC`; ...
     1222                                ... break `LS`; ...
     1223                                ... break `LIF`; ...
     1224                                ... continue `LF;` ...
     1225                                ... break `LF`; ...
    12001226                        } // for
    12011227                } else {
    … …  
    12131239                if ( ... ) {
    12141240                        for ( ... ) {
    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:` ;
     1241                                ... goto `LC`; ...
     1242                                ... goto `LS`; ...
     1243                                ... goto `LIF`; ...
     1244                                ... goto `LFC`; ...
     1245                                ... goto `LFB`; ...
    12241246                          `LFC:` ; } `LFB:` ;
    12251247                } else {
    … …  
    12431265// continue loop
    12441266// terminate loop
    1245 // continue loop
    1246 // terminate loop
    12471267
    12481268
    12491269
    12501270// terminate if
    1251 
    1252 
    12531271
    12541272\end{cfa}
    … …  
    14111429\label{s:WithStatement}
    14121430
    1413 Grouping 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}
    1415 struct S {                                                                      $\C{// aggregate}$
    1416         char c;                                                                 $\C{// fields}$
    1417         int i;
    1418         double d;
    1419 };
    1420 S s, as[10];
    1421 \end{cfa}
    1422 However, functions manipulating aggregates must repeat the aggregate name to access its containing fields:
    1423 \begin{cfa}
    1424 void f( S s ) {
    1425         `s.`c; `s.`i; `s.`d;                                    $\C{// access containing fields}$
    1426 }
    1427 \end{cfa}
    1428 which extends to multiple levels of qualification for nested aggregates.
    1429 A similar situation occurs in object-oriented programming, \eg \CC:
    1430 \begin{C++}
    1431 struct 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++}
    1440 Object-oriented nesting of member functions in a \lstinline[language=C++]@class/struct@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping.
    1441 However, for other aggregate parameters, qualification is necessary:
    1442 \begin{cfa}
     1431Heterogeneous data is often aggregated into a structure/union.
     1432To 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}
     1437struct S { char c; int i; double d; };
    14431438struct T { double m, n; };
    1444 int 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 
    1450 To 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.
    1451 Hence, the qualified fields become variables with the side-effect that it is easier to optimizing field references in a block.
    1452 \begin{cfa}
    1453 void 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}
    1457 with the generality of opening multiple aggregate-parameters:
    1458 \begin{cfa}
    1459 void 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}
     1439// multiple aggregate parameters
     1440\end{cfa}
     1441\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
     1442\begin{cfa}
     1443void 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}
     1450void 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}
     1458Object-oriented programming languages only provide implicit qualification for the receiver.
    14641459
    14651460In detail, the @with@ statement has the form:
    … …  
    14741469The object is the implicit qualifier for the open structure-fields.
    14751470
    1476 All expressions in the expression list are open in parallel within the compound statement.
    1477 This semantic is different from Pascal, which nests the openings from left to right.
     1471All 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.
    14781472The difference between parallel and nesting occurs for fields with the same name and type:
    14791473\begin{cfa}
    … …  
    22612255\begin{cfa}
    22622256MIN
     2257
    22632258MAX
     2259
    22642260PI
    22652261E
    … …  
    22672263&
    22682264\begin{cfa}
    2269 SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
    2270 SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
     2265SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN,
     2266        LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
     2267SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX,
     2268        LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
    22712269M_PI, M_PIl
    22722270M_E, M_El
    … …  
    24412439ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
    24422440ip = (int *)realloc( ip, 2 * dim * sizeof( int ) );
    2443 ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) );
    2444 
     2441ip = (int *)realloc( ip, 4 * dim * sizeof( int ) );
     2442                        memset( ip, fill, 4 * dim * sizeof( int ) );
    24452443ip = memalign( 16, sizeof( int ) );
    24462444ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) );
    … …  
    26072605Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    26082606In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    2609 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:BenchmarkStackImplementation}).
     2607This 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}).
    26102608Since 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.
    26112609A more illustrative comparison measures the costs of idiomatic usage of each language's features.
    … …  
    28242822\appendix
    28252823
    2826 \section{Benchmark Stack Implementation}
    2827 \label{sec:BenchmarkStackImplementation}
    2828 
    2829 Throughout, @/***/@ designates a counted redundant type annotation; code reformatted for brevity.
    2830 
    2831 \smallskip\noindent
    2832 C
    2833 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2834 struct stack_node {
     2824\section{Benchmark Stack Implementations}
     2825\label{sec:BenchmarkStackImplementations}
     2826
     2827Throughout, @/***/@ 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]
     2836typedef struct node {
    28352837        void * value;
    2836         struct stack_node * next;
    2837 };
    2838 struct stack { struct stack_node* head; };
    2839 void 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 );
     2838        struct node * next;
     2839} node;
     2840typedef struct stack {
     2841        struct node * head;
     2842} stack;
     2843void 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}
     2853void 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 );
    28452859        }
    28462860        s->head = NULL;
    28472861}
    2848 struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    2849 void 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 }
    2858 struct stack * assign_stack( struct stack * s, const struct stack * t,
    2859                 void * (*copy_el)( const void * ), void (*free_el)( void * ) ) {
     2862\end{cfa}
     2863&
     2864\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     2865stack new_stack() {
     2866        return (stack){ NULL }; /***/
     2867}
     2868stack * assign_stack( stack * s, const stack * t,
     2869                                void * (*copy_el)( const void * ),
     2870                                void (*free_el)( void * ) ) {
    28602871        if ( s->head == t->head ) return s;
    28612872        clear_stack( s, free_el ); /***/
    … …  
    28632874        return s;
    28642875}
    2865 _Bool stack_empty( const struct stack * s ) { return s->head == NULL; }
    2866 void 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 }; /***/
     2876_Bool stack_empty( const stack * s ) {
     2877         return s->head == NULL;
     2878}
     2879void push_stack( stack * s, void * v ) {
     2880        node * n = malloc(sizeof(node)); /***/
     2881        *n = (node){ v, s->head }; /***/
    28692882        s->head = n;
    28702883}
    2871 void * pop_stack( struct stack * s ) {
    2872         struct stack_node * n = s->head;
     2884void * pop_stack( stack * s ) {
     2885        node * n = s->head;
    28732886        s->head = n->next;
    28742887        void * v = n->value;
    … …  
    28772890}
    28782891\end{cfa}
    2879 
    2880 \medskip\noindent
    2881 \CFA
    2882 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2883 forall( otype T ) struct stack_node {
    2884         T value;
    2885         stack_node(T) * next;
    2886 };
    2887 forall( otype T ) struct stack { stack_node(T) * head; };
    2888 forall( 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);
     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]
     2904forall( otype T ) {
     2905        struct node {
     2906                T value;
     2907                node(T) * next;
     2908        };
     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;
    28942919        }
    2895         head = 0;
    2896 }
    2897 forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    2898 forall( 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 }
    2907 forall( 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 }
    2913 forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
    2914 forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
    2915 forall( 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 }
    2920 forall( 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}
    2931 forall( otype T ) {
    2932         struct stack_node {
    2933                 T value;
    2934                 stack_node(T) * next;
    2935         };
    2936         struct stack { stack_node(T) * head; };
    29372920        void clear( stack(T) & s ) with( s ) {
    2938                 for ( stack_node(T) * next = head; next; ) {
    2939                         stack_node(T) * crnt = next;
    2940                         next = crnt->next;
    2941                         ^(*crnt){};
    2942                         free(crnt);
     2921                for ( node(T) * nx = head; nx; ) {
     2922                        node(T) * cr = nx;
     2923                        nx = cr->next;
     2924                        ^(*cr){};
     2925                        free(cr);
    29432926                }
    29442927                head = 0;
    29452928        }
    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         }
     2929\end{cfa}
     2930&
     2931\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
     2932        void ^?{}( stack(T) & s) { clear( s ); }
    29562933        stack(T) ?=?( stack(T) & s, stack(T) t ) {
    29572934                if ( s.head == t.head ) return s;
    … …  
    29602937                return s;
    29612938        }
    2962         void ^?{}( stack(T) & s) { clear( s ); }
    2963         _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2939        _Bool empty( const stack(T) & s ) {
     2940                return s.head == 0;
     2941        }
    29642942        void push( stack(T) & s, T value ) with( s ) {
    2965                 stack_node(T) * n = alloc();
     2943                node(T) * n = alloc();
    29662944                (*n){ value, head };
    29672945                head = n;
    29682946        }
    29692947        T pop( stack(T) & s ) with( s ) {
    2970                 stack_node(T) * n = head;
     2948                node(T) * n = head;
    29712949                head = n->next;
    29722950                T v = n->value;
    … …  
    29762954        }
    29772955}
    2978 \end{comment}
    2979 
    2980 \medskip\noindent
    2981 \CC
    2982 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     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]
    29832969template<typename T> struct stack {
    29842970        struct node {
    29852971                T value;
    29862972                node * next;
    2987                 node( const T & v, node * n = nullptr ) : value( v ), next( n ) {}
     2973                node( const T & v, node * n = nullptr ) :
     2974                        value( v ), next( n ) {}
    29882975        };
    29892976        node * head;
    2990         stack() : head( nullptr ) {}
    2991         stack( const stack<T> & o ) { copy( o ); }
     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        }
    29922985        void clear() {
    2993                 for ( node * next = head; next; ) {
    2994                         node * crnt = next;
    2995                         next = crnt->next;
    2996                         delete crnt;
     2986                for ( node * nx = head; nx; ) {
     2987                        node * cr = nx;
     2988                        nx = cr->next;
     2989                        delete cr;
    29972990                }
    29982991                head = nullptr;
    29992992        }
    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         }
     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 ); }
    30082998        ~stack() { clear(); }
    3009         stack & operator= ( const stack<T> & o ) {
     2999        stack & operator=( const stack<T> & o ) {
    30103000                if ( this == &o ) return *this;
    30113001                clear();
    … …  
    30143004        }
    30153005        bool empty() const { return head == nullptr; }
    3016         void push( const T & value ) { head = new node{ value, head };  /***/ }
     3006        void push( const T & value ) {
     3007                head = new node{ value, head };  /***/
     3008        }
    30173009        T pop() {
    30183010                node * n = head;
    … …  
    30233015        }
    30243016};
    3025 \end{cfa}
    3026 
    3027 \medskip\noindent
    3028 \CCV
    3029 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     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]
    30303032struct stack {
    30313033        struct node {
    30323034                ptr<object> value;
    30333035                node * next;
    3034                 node( const object & v, node * n = nullptr ) : value( v.new_copy() ), next( n ) {}
     3036                node( const object & v, node * n = nullptr ) :
     3037                                value( v.new_copy() ), next( n ) {}
    30353038        };
    30363039        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        }
    30373048        void clear() {
    3038                 for ( node * next = head; next; ) {
    3039                         node * crnt = next;
    3040                         next = crnt->next;
    3041                         delete crnt;
     3049                for ( node * nx = head; nx; ) {
     3050                        node * cr = nx;
     3051                        nx = cr->next;
     3052                        delete cr;
    30423053                }
    30433054                head = nullptr;
    30443055        }
    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         }
     3056\end{cfa}
     3057&
     3058\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
    30533059        stack() : head( nullptr ) {}
    30543060        stack( const stack & o ) { copy( o ); }
    30553061        ~stack() { clear(); }
    3056         stack & operator= ( const stack & o ) {
     3062        stack & operator=( const stack & o ) {
    30573063                if ( this == &o ) return *this;
    30583064                clear();
    … …  
    30613067        }
    30623068        bool empty() const { return head == nullptr; }
    3063         void push( const object & value ) { head = new node{ value, head }; /***/ }
     3069        void push( const object & value ) {
     3070                head = new node{ value, head }; /***/
     3071        }
    30643072        ptr<object> pop() {
    30653073                node * n = head;
    … …  
    30703078        }
    30713079};
    3072 \end{cfa}
     3080
     3081
     3082
     3083\end{cfa}
     3084\end{tabular}
     3085\lstMakeShortInline@%
     3086\end{flushleft}
    30733087
    30743088
Note: See TracChangeset for help on using the changeset viewer.