Changeset 17f27d40


Ignore:
Timestamp:
Apr 15, 2017, 11:45:40 AM (5 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
160af1e
Parents:
79b8dc3
Message:

work on conclusion and add references

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/cfa.bib

    r79b8dc3 r17f27d40  
    433433    keywords    = {Parametric polymorphism, alphard, iterators, nested types},
    434434    contributer = {gjditchfield@plg},
     435    key         = {Alphard},
    435436    editor      = {Mary Shaw},
    436437    title       = {{ALPHARD}: Form and Content},
     
    861862
    862863@techreport{C11,
    863     type = {International Standard},
     864    type        = {International Standard},
    864865    keywords    = {ISO/IEC C 11},
    865866    contributer = {pabuhr@plg},
     
    872873
    873874@techreport{C++Concepts,
    874     type = {International Standard},
     875    type        = {International Standard},
    875876    keywords    = {ISO/IEC TS 19217:2015},
    876877    contributer = {a3moss@uwaterloo.ca},
     
    53175318    title       = {Programming with Sets: An Introduction to {SETL}},
    53185319    publisher   = {Springer},
     5320    address     = {New York, NY, USA},
    53195321    year        = 1986,
    53205322}
     
    63126314}
    63136315
    6314 @article{Sutter15,
     6316@online{Sutter15,
    63156317    contributer = {pabuhr@plg},
    63166318    author      = {Herb Sutter and Bjarne Stroustrup and Gabriel Dos Reis},
     
    67646766    number      = 6,
    67656767    month       = jun,
     6768    publisher   = {ACM},
     6769    address     = {New York, NY, USA},
    67666770    year        = 1990,
    67676771    pages       = {127-136},
  • doc/generic_types/generic_types.tex

    r79b8dc3 r17f27d40  
    194194The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
    195195
     196
    196197\subsection{Polymorphic Functions}
    197198\label{sec:poly-fns}
    198199
    199200\CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}.
    200 The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name):
     201The 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):
    201202\begin{lstlisting}
    202203`forall( otype T )` T identity( T val ) { return val; }
     
    211212An 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.
    212213
    213 Since 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.
     214Since 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.
    214215For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    215216\begin{lstlisting}
     
    291292\smallskip\par\noindent
    292293\lstMakeShortInline@%
    293 Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
     294Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    294295As 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.
    295296In addition, several operations are defined in terms values @0@ and @1@, \eg:
     
    298299if (x) x++                                                                      $\C{// if (x != 0) x += 1;}$
    299300\end{lstlisting}
    300 Every 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.
     301Every 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.
    301302Due 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.
    302303The 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.
     
    319320\end{lstlisting}
    320321
    321 In 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:
     322In 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:
    322323\begin{lstlisting}
    323324trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
     
    515516[ int, int ] div( int num, int den );           $\C{// return two integers}$
    516517[ double, double ] div( double num, double den ); $\C{// return two doubles}$
    517 int q, r;                                                                       $\C{// overload variable names}$
     518int q, r;                                                                       $\C{// overloaded variable names}$
    518519double q, r;
    519520[ q, r ] = div( 13, 5 );                                        $\C{// select appropriate div and q, r}$
    520 [ q, r ] = div( 13.5, 5.2 );
     521[ q, r ] = div( 13.5, 5.2 );                            $\C{// assign into tuple}$
    521522\end{lstlisting}
    522523Clearly, this approach is straightforward to understand and use;
    523524therefore, why do few programming languages support this obvious feature or provide it awkwardly?
    524525The answer is that there are complex consequences that cascade through multiple aspects of the language, especially the type-system.
    525 This section show these consequences and how \CFA deals with them.
     526This section show these consequences and how \CFA handles them.
    526527
    527528
     
    536537printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
    537538\end{lstlisting}
    538 Here, the values returned by @div@ are composed with the call to @printf@.
     539Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments.
    539540However, the \CFA type-system must support significantly more complex composition:
    540541\begin{lstlisting}
     
    552553
    553554An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF.
    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.
    555 As a consequence, \CFA allows declaration of \emph{tuple variables} that can be initialized from an MRVF, \eg:
     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:
    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.
    668 x.2]
     667[int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]
    669668\end{lstlisting}
    670669\end{tabular}
     
    954953Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
    955954Figure~\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}.
    956 The tests are similar for C and \CC.
    957 The 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.
    958 The last experiment creates a file and prints $N=40M$ elements of type @int@ and @pair( _Bool, char)@ using a variadic print.
    959 
    960 The 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.
     955The benchmark tests are similar for C and \CC.
     956The 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
     958The 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.
    961959The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    962960hence runtime checks are necessary to safely down-cast objects.
     
    964962For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    965963Preliminary tests show the difference has little runtime effect.
    966 Finally, the C @rand@ function is used generate random numbers.
     964%Finally, the C @rand@ function is used generate random numbers.
    967965
    968966\begin{figure}
    969967\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt,numbers=left,numberstyle=\tt\small,numberblanklines=false]
    970968int main( int argc, char *argv[] ) {
    971         int max = 0;
    972         stack(int) s, t;
    973         REPEAT_TIMED( "push_int", push( &s, 42 ); )
    974         TIMED( "copy_int", t = s; )
    975         TIMED( "clear_int", clear( &s ); )
    976         REPEAT_TIMED( "pop_int", max = max( max, pop( &t ) ); )
    977 
    978         stack(pair(_Bool, char)) s1, t1;
    979         pair(_Bool, char) max = { (_Bool)0, '\0' };
    980         REPEAT_TIMED( "push_pair", push( &s1, (pair(_Bool, char)){ (_Bool)0, 'a' } ); )
    981         TIMED( "copy_pair", t1 = s1; )
    982         TIMED( "clear_pair", clear( &s1 ); )
    983         REPEAT_TIMED( "pop_pair", max = max( max, pop( &t1 ) ); )
    984 
    985969        FILE * out = fopen( "cfa-out.txt", "w" );
    986         REPEAT_TIMED( "print_int", print( out, 42, ":", 42, "\n" ); )
    987         REPEAT_TIMED( "print_pair", print( out, (pair(_Bool, char)){ (_Bool)0, 'a' }, ":",
    988                                                          (pair(_Bool, char)){ (_Bool)0, 'a' }, "\n" ); )
     970        int max = 0, vali = 42;
     971        stack(int) si, ti;
     972
     973        REPEAT_TIMED( "push_int", push( &si, vali ); )
     974        TIMED( "copy_int", ti = si; )
     975        TIMED( "clear_int", clear( &si ); )
     976        REPEAT_TIMED( "pop_int", max = max( max, pop( &ti ) ); )
     977        REPEAT_TIMED( "print_int", print( out, vali, ":", vali, "\n" ); )
     978
     979        pair(_Bool, char) maxp  = { (_Bool)0, '\0' }, valp = { (_Bool)0, 'a' };
     980        stack(pair(_Bool, char)) sp, tp;
     981
     982        REPEAT_TIMED( "push_pair", push( &sp, valp ); )
     983        TIMED( "copy_pair", tp = sp; )
     984        TIMED( "clear_pair", clear( &sp ); )
     985        REPEAT_TIMED( "pop_pair", maxp = max( maxp, pop( &tp ) ); )
     986        REPEAT_TIMED( "print_pair", print( out, valp, ":", valp, "\n" ); )
    989987        fclose(out);
    990988}
    991989\end{lstlisting}
    992 \caption{Micro-Benchmark}
     990\caption{\CFA Micro-Benchmark}
    993991\label{fig:MicroBenchmark}
    994992\end{figure}
     
    10061004\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    10071005\begin{tabular}{r|rrrr}
    1008                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
    1009 maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
    1010 source code size (lines)        & 301           & 224           & 188           &       437                     \\
    1011 redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
    1012 binary size (KB)                        & 18            & 234           & 18            &       42                      \\
     1006                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
     1007maximum memory usage (MB)                       & 10001         & 2501          & 2503          & 11253                 \\
     1008source code size (lines)                        & 301           & 224           & 188           & 437                   \\
     1009redundant type annotations (lines)      & 46            & 3                     & 2                     & 15                    \\
     1010binary size (KB)                                        & 18            & 234           & 18            & 42                    \\
    10131011\end{tabular}
    10141012\end{table}
     
    10991097\section{Conclusion \& Future Work}
    11001098
     1099The \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.
     1100While 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.
     1101The 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.
     1102The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions.
     1103The work is a challenging design, engineering, and implementation exercise.
     1104On the surface, the project may appear as a rehash of similar mechanisms in \CC.
     1105However, 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.
     1106All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
     1107Finally, we demonstrate that \CFA performance for some idiomtic cases is better than C and close to \CC, showing the design is competitive.
     1108
    11011109There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
    11021110In addition to this work, there are some interesting future directions the polymorphism design could take.
     
    11071115These 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.
    11081116
    1109 In 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.
    1110 We 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.
    1111 
    11121117
    11131118\begin{acks}
Note: See TracChangeset for help on using the changeset viewer.