Changes in / [f891424d:1c38f5b]


Ignore:
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/cfa.bib

    rf891424d r1c38f5b  
    433433    keywords    = {Parametric polymorphism, alphard, iterators, nested types},
    434434    contributer = {gjditchfield@plg},
    435     key         = {Alphard},
    436435    editor      = {Mary Shaw},
    437436    title       = {{ALPHARD}: Form and Content},
    … …  
    862861
    863862@techreport{C11,
    864     type        = {International Standard},
     863    type = {International Standard},
    865864    keywords    = {ISO/IEC C 11},
    866865    contributer = {pabuhr@plg},
    … …  
    873872
    874873@techreport{C++Concepts,
    875     type        = {International Standard},
     874    type = {International Standard},
    876875    keywords    = {ISO/IEC TS 19217:2015},
    877876    contributer = {a3moss@uwaterloo.ca},
    … …  
    53185317    title       = {Programming with Sets: An Introduction to {SETL}},
    53195318    publisher   = {Springer},
    5320     address     = {New York, NY, USA},
    53215319    year        = 1986,
    53225320}
    … …  
    63146312}
    63156313
    6316 @online{Sutter15,
     6314@article{Sutter15,
    63176315    contributer = {pabuhr@plg},
    63186316    author      = {Herb Sutter and Bjarne Stroustrup and Gabriel Dos Reis},
    … …  
    67666764    number      = 6,
    67676765    month       = jun,
    6768     publisher   = {ACM},
    6769     address     = {New York, NY, USA},
    67706766    year        = 1990,
    67716767    pages       = {127-136},

  • doc/generic_types/generic_types.tex

    rf891424d r1c38f5b  
    194194The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
    195195
    196 
    197196\subsection{Polymorphic Functions}
    198197\label{sec:poly-fns}
    199198
    200199\CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}.
    201 The signature feature of \CFA is parametric-polymorphic functions~\citep{forceone:impl,Cormack90} where functions are generalized using a @forall@ clause (giving the language its name):
     200The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name):
    202201\begin{lstlisting}
    203202`forall( otype T )` T identity( T val ) { return val; }
    … …  
    212211An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
    213212
    214 Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion}~\cite{alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
     213Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
    215214For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    216215\begin{lstlisting}
    … …  
    292291\smallskip\par\noindent
    293292\lstMakeShortInline@%
    294 Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
     293Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    295294As well, restricted constant overloading is allowed for the values @0@ and @1@, which have special status in C, \eg the value @0@ is both an integer and a pointer literal, so its meaning depends on context.
    296295In addition, several operations are defined in terms values @0@ and @1@, \eg:
    … …  
    299298if (x) x++                                                                      $\C{// if (x != 0) x += 1;}$
    300299\end{lstlisting}
    301 Every if and iteration statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
     300Every if statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result.
    302301Due to these rewrite rules, the values @0@ and @1@ have the types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly connect to all special @0@ and @1@ contexts.
    303302The types @zero_t@ and @one_t@ have special built in implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work as normal.
    … …  
    320319\end{lstlisting}
    321320
    322 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:
     321In fact, the set of trait operators is incomplete, as there is no assignment requirement for type @T@, but @otype@ is syntactic sugar for the following implicit trait:
    323322\begin{lstlisting}
    324323trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
    … …  
    516515[ int, int ] div( int num, int den );           $\C{// return two integers}$
    517516[ double, double ] div( double num, double den ); $\C{// return two doubles}$
    518 int q, r;                                                                       $\C{// overloaded variable names}$
     517int q, r;                                                                       $\C{// overload variable names}$
    519518double q, r;
    520519[ q, r ] = div( 13, 5 );                                        $\C{// select appropriate div and q, r}$
    521 [ q, r ] = div( 13.5, 5.2 );                            $\C{// assign into tuple}$
     520[ q, r ] = div( 13.5, 5.2 );
    522521\end{lstlisting}
    523522Clearly, this approach is straightforward to understand and use;
    524523therefore, why do few programming languages support this obvious feature or provide it awkwardly?
    525524The answer is that there are complex consequences that cascade through multiple aspects of the language, especially the type-system.
    526 This section show these consequences and how \CFA handles them.
     525This section show these consequences and how \CFA deals with them.
    527526
    528527
    … …  
    537536printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
    538537\end{lstlisting}
    539 Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments.
     538Here, the values returned by @div@ are composed with the call to @printf@.
    540539However, the \CFA type-system must support significantly more complex composition:
    541540\begin{lstlisting}
    … …  
    553552
    554553An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF.
    555 \CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types, \eg:
     554\CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types.
     555As a consequence, \CFA allows declaration of \emph{tuple variables} that can be initialized from an MRVF, \eg:
    556556\begin{lstlisting}
    557557[ int, int ] qr = div( 13, 5 );                         $\C{// tuple-variable declaration and initialization}$
    … …  
    665665x.[0, 1] = x.[1, 0];    $\C[1in]{// rearrange: [x.0, x.1] = [x.1, x.0]}$
    666666f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}\CRT{}$
    667 [int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]
     667[int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.
     668x.2]
    668669\end{lstlisting}
    669670\end{tabular}
    … …  
    953954Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
    954955Figure~\ref{fig:MicroBenchmark} shows the \CFA benchmark tests for a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ routine similar to that in Section~\ref{sec:variadic-tuples}.
    955 The benchmark tests are similar for C and \CC.
    956 The experiment uses element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, find the maximum value in the other stack, and print $N$ constant values.
    957 
    958 The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
     956The tests are similar for C and \CC.
     957The first two experiments use element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, and find the maximum value in the other stack.
     958The last experiment creates a file and prints $N=40M$ elements of type @int@ and @pair( _Bool, char)@ using a variadic print.
     959
     960The structure of each implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
    959961The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    960962hence runtime checks are necessary to safely down-cast objects.
    … …  
    963965For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    964966Preliminary tests show the difference has little runtime effect.
    965 %Finally, the C @rand@ function is used generate random numbers.
     967Finally, the C @rand@ function is used generate random numbers.
    966968
    967969\begin{figure}
    968970\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt,numbers=left,numberstyle=\tt\small,numberblanklines=false]
    969971int main( int argc, char *argv[] ) {
     972        int max = 0;
     973        stack(int) s, t;
     974        REPEAT_TIMED( "push_int", push( &s, 42 ); )
     975        TIMED( "copy_int", t = s; )
     976        TIMED( "clear_int", clear( &s ); )
     977        REPEAT_TIMED( "pop_int", max = max( max, pop( &t ) ); )
     978
     979        stack(pair(_Bool, char)) s1, t1;
     980        pair(_Bool, char) max = { (_Bool)0, '\0' };
     981        REPEAT_TIMED( "push_pair", push( &s1, (pair(_Bool, char)){ (_Bool)0, 'a' } ); )
     982        TIMED( "copy_pair", t1 = s1; )
     983        TIMED( "clear_pair", clear( &s1 ); )
     984        REPEAT_TIMED( "pop_pair", max = max( max, pop( &t1 ) ); )
     985
    970986        FILE * out = fopen( "cfa-out.txt", "w" );
    971         int max = 0, vali = 42;
    972         stack(int) si, ti;
    973 
    974         REPEAT_TIMED( "push_int", push( &si, vali ); )
    975         TIMED( "copy_int", ti = si; )
    976         TIMED( "clear_int", clear( &si ); )
    977         REPEAT_TIMED( "pop_int", max = max( max, pop( &ti ) ); )
    978         REPEAT_TIMED( "print_int", print( out, vali, ":", vali, "\n" ); )
    979 
    980         pair(_Bool, char) maxp  = { (_Bool)0, '\0' }, valp = { (_Bool)0, 'a' };
    981         stack(pair(_Bool, char)) sp, tp;
    982 
    983         REPEAT_TIMED( "push_pair", push( &sp, valp ); )
    984         TIMED( "copy_pair", tp = sp; )
    985         TIMED( "clear_pair", clear( &sp ); )
    986         REPEAT_TIMED( "pop_pair", maxp = max( maxp, pop( &tp ) ); )
    987         REPEAT_TIMED( "print_pair", print( out, valp, ":", valp, "\n" ); )
     987        REPEAT_TIMED( "print_int", print( out, 42, ":", 42, "\n" ); )
     988        REPEAT_TIMED( "print_pair", print( out, (pair(_Bool, char)){ (_Bool)0, 'a' }, ":",
     989                                                         (pair(_Bool, char)){ (_Bool)0, 'a' }, "\n" ); )
    988990        fclose(out);
    989991}
    990992\end{lstlisting}
    991 \caption{\CFA Micro-Benchmark}
     993\caption{Micro-Benchmark}
    992994\label{fig:MicroBenchmark}
    993995\end{figure}
    … …  
    10051007\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    10061008\begin{tabular}{r|rrrr}
    1007                                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    1008 maximum memory usage (MB)                       & 10001         & 2501          & 2503          & 11253                 \\
    1009 source code size (lines)                        & 301           & 224           & 188           & 437                   \\
    1010 redundant type annotations (lines)      & 46            & 3                     & 2                     & 15                    \\
    1011 binary size (KB)                                        & 18            & 234           & 18            & 42                    \\
     1009                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
     1010maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
     1011source code size (lines)        & 301           & 224           & 188           &       437                     \\
     1012redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
     1013binary size (KB)                        & 18            & 234           & 18            &       42                      \\
    10121014\end{tabular}
    10131015\end{table}
    … …  
    10981100\section{Conclusion \& Future Work}
    10991101
    1100 The \CFA goal is to provide an evolutionary pathway for large C development-environments to be more productive and safer, while respecting the talent and skill of C programmers.
    1101 While other programming languages purport to be a better C, they are in fact new and interesting languages in their own right, but not C extensions.
    1102 The purpose of this paper is to introduce \CFA, and showcase two language features that illustrate the \CFA type-system and approaches taken to achieve the evolutionary goal.
    1103 The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions.
    1104 The work is a challenging design, engineering, and implementation exercise.
    1105 On the surface, the project may appear as a rehash of similar mechanisms in \CC.
    1106 However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation.
    1107 All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
    1108 Finally, we demonstrate that \CFA performance for some idiomtic cases is better than C and close to \CC, showing the design is competitive.
    1109 
    11101102There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
    11111103In addition to this work, there are some interesting future directions the polymorphism design could take.
    … …  
    11161108These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unnecessary.
    11171109
     1110In conclusion, the authors' design for generic types and tuples, unlike those available in existing work, is both reusable and type-checked, while still supporting a full range of C features, including separately-compiled modules.
     1111We have experimentally validated the performance of our design against both \CC and standard C, showing it is comparable to both, and in some cases better.
     1112
    11181113
    11191114\begin{acks}

  • src/Parser/ParseNode.h

    rf891424d r1c38f5b  
    107107  public:
    108108        ExpressionNode( Expression * expr = nullptr ) : expr( expr ) {}
     109        ExpressionNode( const ExpressionNode &other );
    109110        virtual ~ExpressionNode() {}
    110         virtual ExpressionNode * clone() const override { return expr ? static_cast<ExpressionNode*>((new ExpressionNode( expr->clone() ))->set_next( maybeClone( get_next() ) )) : nullptr; }
     111        virtual ExpressionNode * clone() const override { return expr ? new ExpressionNode( expr->clone() ) : nullptr; }
    111112
    112113        bool get_extension() const { return extension; }
Note: See TracChangeset for help on using the changeset viewer.