Changeset 7069652


Ignore:
Timestamp:
Apr 19, 2017, 8:12:56 AM (8 years ago)
Author:
Rob Schluntz <rschlunt@…>
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, resolv-new, with_gc
Children:
5f642e38
Parents:
e39241b (diff), de4ce0e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

Location:
doc
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/cfa.bib

    re39241b r7069652  
    36503650    contributer = {pabuhr@plg},
    36513651    author      = {James Gosling and Bill Joy and Guy Steele and Gilad Bracha and Alex Buckley},
    3652     title       = {{Java} Language Specification},
     3652    title       = {{Java} Language Spec.},
    36533653    organization= {Oracle},
    36543654    publisher   = {Oracle},
    … …  
    62216221}
    62226222
     6223@article{Smith98,
     6224  keywords = {Polymorphic C},
     6225  contributor = {a3moss@uwaterloo.ca},
     6226  title={A sound polymorphic type system for a dialect of C},
     6227  author={Smith, Geoffrey and Volpano, Dennis},
     6228  journal={Science of computer programming},
     6229  volume={32},
     6230  number={1-3},
     6231  pages={49--72},
     6232  year={1998},
     6233  publisher={Elsevier}
     6234}
     6235
    62236236@book{Campbell74,
    62246237    keywords    = {path expressions},

  • doc/generic_types/evaluation/cfa-bench.c

    re39241b r7069652  
    1 #include <stdlib>
    21#include <stdio.h>
    32#include "bench.h"

  • doc/generic_types/evaluation/timing.dat

    re39241b r7069652  
    11"400 million repetitions"       "C"     "\\CFA{}"       "\\CC{}"        "\\CC{obj}"
    2 "push\nint"     2958    2480    1519    3284
    3 "copy\nint"     2961    2014    1534    3126
    4 "clear\nint"    1350    817     722     1459
    5 "pop\nint"      1386    1174    717     5404
    6 "print\nint"    5702    6615    3077    3191
    7 "push\npair"    4160    2648    940     6566
    8 "copy\npair"    6195    2099    977     7234
    9 "clear\npair"   2834    863     723     3315
    10 "pop\npair"     2956    5591    775     26256
    11 "print\npair"   7498    10804   8750    16638
     2"push\nint"     3002    2459    1520    3305
     3"copy\nint"     2985    2057    1521    3152
     4"clear\nint"    1374    827     718     1469
     5"pop\nint"      1416    1221    717     5467
     6"print\nint"    5656    6758    3120    3121
     7"push\npair"    4214    2752    946     6826
     8"copy\npair"    6127    2105    993     7330
     9"clear\npair"   2881    885     711     3564
     10"pop\npair"     3046    5434    783     26538
     11"print\npair"   7514    10714   8717    16525

  • doc/generic_types/evaluation/timing.gp

    re39241b r7069652  
    11# set terminal pdfcairo linewidth 3 size 6,3
    22# set output "timing.pdf"
    3 set terminal pslatex size 6.25,2.25 color solid
     3set terminal pslatex size 6.25,2.125 color solid
    44set output "timing.tex"
    55

  • doc/generic_types/generic_types.tex

    re39241b r7069652  
    99
    1010\makeatletter
     11% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     12% removes it as a variable-name character so keyworks in variables are highlighted
     13\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
     14
    1115% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for
    1216% use rather than use \parident directly.
    … …  
    1418\setlength{\parindentlnth}{\parindent}
    1519
    16 \newlength{\gcolumnposn}                                % temporary hack because lstlisting does handle tabs correctly
     20\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
    1721\newlength{\columnposn}
    1822\setlength{\gcolumnposn}{2.75in}
    … …  
    2125\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
    2226
    23 \newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included
    24 %\newcommand{\TODO}[1]{} % TODO elided
    2527% Latin abbreviation
    2628\newcommand{\abbrevFont}{\textit}       % set empty for no italics
    … …  
    4345                {\abbrevFont{et al}.\xspace}%
    4446}%
    45 % \newcommand{\eg}{\textit{e}.\textit{g}.,\xspace}
    46 % \newcommand{\ie}{\textit{i}.\textit{e}.,\xspace}
    47 % \newcommand{\etc}{\textit{etc}.,\xspace}
    4847\makeatother
    4948
    … …  
    5655\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
    5756\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj\xspace} % C++ virtual symbolic name
    58 \newcommand{\CS}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace}
     57\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
    5958\newcommand{\Textbf}[1]{{\color{red}\textbf{#1}}}
     59\newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included
     60%\newcommand{\TODO}[1]{} % TODO elided
    6061
    6162% CFA programming language, based on ANSI C (with some gcc additions)
    … …  
    8283belowskip=3pt,
    8384% replace/adjust listing characters that look bad in sanserif
    84 literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    85         {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1%{_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    86         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2,
     85literate={-}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
     86        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     87        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1.4ex][c]{\raisebox{0.5ex}{\rule{1.2ex}{0.1ex}}}\kern-0.3ex\textgreater}2,
    8788moredelim=**[is][\color{red}]{`}{`},
    8889}% lstset
    … …  
    159160The 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.
    160161This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
    161 The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \CS 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
     162The \citet{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
    162163The top 3 rankings over the past 30 years are:
    163164\lstDeleteShortInline@%
    164165\begin{center}
    165166\setlength{\tabcolsep}{10pt}
    166 \begin{tabular}{@{}r|c|c|c|c|c|c|c@{}}
    167                 & 2017  & 2012  & 2007  & 2002  & 1997  & 1992  & 1987          \\
    168 \hline
     167\begin{tabular}{@{}rccccccc@{}}
     168                & 2017  & 2012  & 2007  & 2002  & 1997  & 1992  & 1987          \\ \hline
    169169Java    & 1             & 1             & 1             & 1             & 12    & -             & -                     \\
    170 \hline
    171170\Textbf{C}      & \Textbf{2}& \Textbf{2}& \Textbf{2}& \Textbf{2}& \Textbf{1}& \Textbf{1}& \Textbf{1}    \\
    172 \hline
    173171\CC             & 3             & 3             & 3             & 3             & 2             & 2             & 4                     \\
    174172\end{tabular}
    … …  
    188186\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.
    189187
    190 \CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3).
     188\CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)--(3).
    191189Ultimately, a compiler is necessary for advanced features and optimal performance.
    192190
    … …  
    216214Since bare polymorphic-types provide a restricted set of available operations, \CFA provides a \emph{type assertion}~\cite[pp.~37-44]{Alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
    217215For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    218 \newpage
    219216\begin{lstlisting}
    220217forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$
    … …  
    235232int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    236233                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
    237 double vals[10] = { /* 10 floating-point values */ };
    238 double key = 5.0;
     234double key = 5.0, vals[10] = { /* 10 floating-point values */ };
    239235double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    240236\end{lstlisting}
    … …  
    278274
    279275Finally, \CFA allows variable overloading:
    280 \lstDeleteShortInline@%
    281 \par\smallskip
    282 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    283 \begin{lstlisting}
    284 short int MAX = ...;
    285 int MAX = ...;
    286 double MAX = ...;
    287 \end{lstlisting}
    288 &
    289 \begin{lstlisting}
    290 short int s = MAX;  // select correct MAX
    291 int i = MAX;
    292 double d = MAX;
    293 \end{lstlisting}
    294 \end{tabular}
    295 \smallskip\par\noindent
    296 \lstMakeShortInline@%
     276\begin{lstlisting}
     277short int MAX = ...;   int MAX = ...;  double MAX = ...;
     278short int s = MAX;    int i = MAX;    double d = MAX;   $\C{// select correct MAX}$
     279\end{lstlisting}
    297280Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    298281As 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.
    … …  
    473456}
    474457\end{lstlisting}
    475 %       int c = cmp( a->first, b->first );
    476 %       if ( c == 0 ) c = cmp( a->second, b->second );
    477 %       return c;
    478458Since @pair(T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the fields of both pairs and the arguments to the comparison function match in type.
    479459
    … …  
    585565Tuple flattening recursively expands a tuple into the list of its basic components.
    586566Tuple structuring packages a list of expressions into a value of tuple type, \eg:
    587 \lstDeleteShortInline@%
    588 \par\smallskip
    589 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     567%\lstDeleteShortInline@%
     568%\par\smallskip
     569%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    590570\begin{lstlisting}
    591571int f( int, int );
    … …  
    593573int h( int, [int, int] );
    594574[int, int] x;
    595 \end{lstlisting}
    596 &
    597 \begin{lstlisting}
    598575int y;
    599 f( x );                 $\C[1in]{// flatten}$
     576f( x );                 $\C{// flatten}$
    600577g( y, 10 );             $\C{// structure}$
    601 h( x, y );              $\C{// flatten and structure}\CRT{}$
    602 \end{lstlisting}
    603 \end{tabular}
    604 \smallskip\par\noindent
    605 \lstMakeShortInline@%
     578h( x, y );              $\C{// flatten and structure}$
     579\end{lstlisting}
     580%\end{lstlisting}
     581%&
     582%\begin{lstlisting}
     583%\end{tabular}
     584%\smallskip\par\noindent
     585%\lstMakeShortInline@%
    606586In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as the two arguments.
    607587In the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the parameter type of @g@.
    … …  
    614594An assignment where the left side is a tuple type is called \emph{tuple assignment}.
    615595There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \emph{multiple} and \emph{mass assignment}, respectively.
    616 \lstDeleteShortInline@%
    617 \par\smallskip
    618 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     596%\lstDeleteShortInline@%
     597%\par\smallskip
     598%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    619599\begin{lstlisting}
    620600int x = 10;
    621601double y = 3.5;
    622602[int, double] z;
    623 
    624 \end{lstlisting}
    625 &
    626 \begin{lstlisting}
    627 z = [x, y];             $\C[1in]{// multiple assignment}$
    628 [x, y] = z;             $\C{// multiple assignment}$
    629 z = 10;                 $\C{// mass assignment}$
    630 [y, x] = 3.14;  $\C{// mass assignment}\CRT{}$
    631 \end{lstlisting}
    632 \end{tabular}
    633 \smallskip\par\noindent
    634 \lstMakeShortInline@%
     603z = [x, y];                                                                     $\C{// multiple assignment}$
     604[x, y] = z;                                                                     $\C{// multiple assignment}$
     605z = 10;                                                                         $\C{// mass assignment}$
     606[y, x] = 3.14;                                                          $\C{// mass assignment}$
     607\end{lstlisting}
     608%\end{lstlisting}
     609%&
     610%\begin{lstlisting}
     611%\end{tabular}
     612%\smallskip\par\noindent
     613%\lstMakeShortInline@%
    635614Both kinds of tuple assignment have parallel semantics, so that each value on the left and right side is evaluated before any assignments occur.
    636615As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function, \eg, @[x, y] = [y, x]@.
    … …  
    656635Here, the mass assignment sets all members of @s@ to zero.
    657636Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (\eg rearrange, drop, and duplicate components).
    658 \lstDeleteShortInline@%
    659 \par\smallskip
    660 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     637%\lstDeleteShortInline@%
     638%\par\smallskip
     639%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    661640\begin{lstlisting}
    662641[int, int, long, double] x;
    663642void f( double, long );
    664 
    665 \end{lstlisting}
    666 &
    667 \begin{lstlisting}
    668 x.[0, 1] = x.[1, 0];    $\C[1in]{// rearrange: [x.0, x.1] = [x.1, x.0]}$
    669 f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}\CRT{}$
    670 [int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]
    671 \end{lstlisting}
    672 \end{tabular}
    673 \smallskip\par\noindent
    674 \lstMakeShortInline@%
     643x.[0, 1] = x.[1, 0];                                            $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
     644f( x.[0, 3] );                                                          $\C{// drop: f(x.0, x.3)}$
     645[int, int, int] y = x.[2, 0, 2];                        $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
     646\end{lstlisting}
     647%\end{lstlisting}
     648%&
     649%\begin{lstlisting}
     650%\end{tabular}
     651%\smallskip\par\noindent
     652%\lstMakeShortInline@%
    675653It is also possible for a member access to contain other member accesses, \eg:
    676654\begin{lstlisting}
    … …  
    833811This example showcases a variadic-template-like decomposition of the provided argument list.
    834812The individual @print@ functions allow printing a single element of a type.
    835 The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function.
    836 The individual print functions can be used to build up more complicated @print@ functions, such as for @S@, which is something that cannot be done with @printf@ in C.
     813The polymorphic @print@ allows printing any list of types, where as each individual type has a @print@ function.
     814The individual print functions can be used to build up more complicated @print@ functions, such as @S@, which cannot be done with @printf@ in C.
    837815
    838816Finally, it is possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
    … …  
    861839is transformed into:
    862840\begin{lstlisting}
    863 // generated before the first 2-tuple
    864841forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
    865         T0 field_0;
     842        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    866843        T1 field_1;
    867844};
    868845_tuple2(int, int) f() {
    869846        _tuple2(double, double) x;
    870         // generated before the first 3-tuple
    871847        forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
    872                 T0 field_0;
     848                T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    873849                T1 field_1;
    874850                T2 field_2;
    … …  
    877853}
    878854\end{lstlisting}
    879 Tuple expressions are then simply converted directly into compound literals:
    880 \begin{lstlisting}
    881 [5, 'x', 1.24];
    882 \end{lstlisting}
    883 becomes:
    884 \begin{lstlisting}
    885 (_tuple3(int, char, double)){ 5, 'x', 1.24 };
    886 \end{lstlisting}
     855Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
    887856
    888857\begin{comment}
    … …  
    948917Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    949918In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    950 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see source-code interfaces in Appendix~\ref{sec:BenchmarkInterfaces}).
    951 Since all these languages share a subset comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
    952 A more illustrative benchmark is to show the costs of idiomatic use of each language's features covering common usage.
     919This 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}).
     920Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
     921A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
    953922Figure~\ref{fig:BenchmarkTest} 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}.
    954923The benchmark test is similar for C and \CC.
    955 The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N$ constant values.
     924The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N/2$ (to reduce graph height) constants.
     925
     926\begin{figure}
     927\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
     928int main( int argc, char * argv[] ) {
     929        FILE * out = fopen( "cfa-out.txt", "w" );
     930        int maxi = 0, vali = 42;
     931        stack(int) si, ti;
     932
     933        REPEAT_TIMED( "push_int", N, push( &si, vali ); )
     934        TIMED( "copy_int", ti = si; )
     935        TIMED( "clear_int", clear( &si ); )
     936        REPEAT_TIMED( "pop_int", N,
     937                int xi = pop( &ti ); if ( xi > maxi ) { maxi = xi; } )
     938        REPEAT_TIMED( "print_int", N/2, print( out, vali, ":", vali, "\n" ); )
     939
     940        pair(_Bool, char) maxp = { (_Bool)0, '\0' }, valp = { (_Bool)1, 'a' };
     941        stack(pair(_Bool, char)) sp, tp;
     942
     943        REPEAT_TIMED( "push_pair", N, push( &sp, valp ); )
     944        TIMED( "copy_pair", tp = sp; )
     945        TIMED( "clear_pair", clear( &sp ); )
     946        REPEAT_TIMED( "pop_pair", N,
     947                pair(_Bool, char) xp = pop( &tp ); if ( xp > maxp ) { maxp = xp; } )
     948        REPEAT_TIMED( "print_pair", N/2, print( out, valp, ":", valp, "\n" ); )
     949        fclose(out);
     950}
     951\end{lstlisting}
     952\caption{\CFA Benchmark Test}
     953\label{fig:BenchmarkTest}
     954\end{figure}
    956955
    957956The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
    … …  
    959958hence runtime checks are necessary to safely down-cast objects.
    960959The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
    961 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has little runtime impact.
     960For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has negligible runtime impact.
    962961Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    963 
    964 \begin{figure}
    965 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    966 int main( int argc, char *argv[] ) {
    967         FILE * out = fopen( "cfa-out.txt", "w" );
    968         int maxi = 0, vali = 42;
    969         stack(int) si, ti;
    970 
    971         REPEAT_TIMED( "push_int", N, push( &si, vali ); )
    972         TIMED( "copy_int", ti = si; )
    973         TIMED( "clear_int", clear( &si ); )
    974         REPEAT_TIMED( "pop_int", N,
    975                 int xi = pop( &ti );
    976                 if ( xi > maxi ) { maxi = xi; } )
    977         REPEAT_TIMED( "print_int", N/2, print( out, vali, ":", vali, "\n" ); )
    978 
    979         pair(_Bool, char) maxp = { (_Bool)0, '\0' }, valp = { (_Bool)1, 'a' };
    980         stack(pair(_Bool, char)) sp, tp;
    981 
    982         REPEAT_TIMED( "push_pair", N, push( &sp, valp ); )
    983         TIMED( "copy_pair", tp = sp; )
    984         TIMED( "clear_pair", clear( &sp ); )
    985         REPEAT_TIMED( "pop_pair", N,
    986                 pair(_Bool, char) xp = pop( &tp );
    987                 if ( xp > maxp ) { maxp = xp; } )
    988         REPEAT_TIMED( "print_pair", N/2, print( out, valp, ":", valp, "\n" ); )
    989         fclose(out);
    990 }
    991 \end{lstlisting}
    992 \caption{\CFA Benchmark Test}
    993 \label{fig:BenchmarkTest}
    994 \end{figure}
    995962
    996963Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:BenchmarkTest} and its C, \CC, and \CCV equivalents.
    … …  
    1013980                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    1014981maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
    1015 source code size (lines)                        & 247           & 223           & 165           & 339                   \\
     982source code size (lines)                        & 247           & 222           & 165           & 339                   \\
    1016983redundant type annotations (lines)      & 39            & 2                     & 2                     & 15                    \\
    1017984binary size (KB)                                        & 14            & 229           & 18            & 38                    \\
    … …  
    1021988The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
    1022989this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
    1023 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent.
     990By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
    1024991\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    1025992There are two outliers in the graph for \CFA: all prints and pop of @pair@.
    1026993Both of these cases result from the complexity of the C-generated polymorphic code, so that the GCC compiler is unable to optimize some dead code and condense nested calls.
    1027 A compiler for \CFA could easily perform these optimizations.
     994A compiler designed for \CFA could easily perform these optimizations.
    1028995Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    1029996
    1030 \CC performs best because it uses header-only inlined libraries (\ie no separate compilation).
    1031 \CFA and \CC have the advantage of a pre-written generic @pair@ and @stack@ type to reduce line count, while C and \CCV require it to written by the programmer, as C does not have a generic collections-library and \CCV does not use the \CC standard template library by construction.
    1032 For \CCV, the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count, which inflates its line count, as an actual object-oriented language would include these in the standard library;
     997\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 73 and 54 lines, respectively.
     998On the other hand, C does not have a generic collections-library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers.
     999\CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;
    10331000with their omission the \CCV line count is similar to C.
    10341001We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose.
    … …  
    10391006To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
    10401007The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
    1041 The three instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
    1042 These uses are similar to the @new@ expressions in \CC, though ongoing work on the \CFA compiler's type resolver should shortly render even these type casts superfluous.
     1008The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
     1009These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous.
    10431010
    10441011
    … …  
    10561023In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate-compilation of polymorphic functions and generic (opaque) types, which uniformly leverage the C procedural paradigm.
    10571024The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type.
    1058 Until \CC~\citep{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion;
     1025Until \CC~\citet{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specify the requirements of a generic function in code beyond compilation errors during template expansion;
    10591026furthermore, \CC concepts are restricted to template polymorphism.
    10601027
    … …  
    10641031In \CFA terms, all Cyclone polymorphism must be dtype-static.
    10651032While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model.
     1033\citet{Smith98} present Polymorphic C, an ML dialect with polymorphic functions and C-like syntax and pointer types; it lacks many of C's features, however, most notably structure types, and so is not a practical C replacement.
    10661034
    10671035\citet{obj-c-book} is an industrially successful extension to C.
    10681036However, Objective-C is a radical departure from C, using an object-oriented model with message-passing.
    1069 Objective-C did not support type-checked generics until recently~\citet{xcode7}, historically using less-efficient and more error-prone runtime checking of object types.
     1037Objective-C did not support type-checked generics until recently \citet{xcode7}, historically using less-efficient runtime checking of object types.
    10701038The~\citet{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C;
    10711039these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference-counting.
    1072 \citet{Vala} compiles to GObject-based C, and so adds the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for the existing C code-bases.
    1073 Java~\citep{Java8} included generic types in Java~5;
    1074 Java's generic types are type-checked at compilation and type-erased at runtime, similar to \CFA's.
     1040\citet{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code-bases.
     1041Java~\citep{Java8} included generic types in Java~5, which are type-checked at compilation and type-erased at runtime, similar to \CFA's.
    10751042However, in Java, each object carries its own table of method pointers, while \CFA passes the method pointers separately to maintain a C-compatible layout.
    10761043Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
    … …  
    11201087
    11211088There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, concurrent primitives and modules.
    1122 (While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these addition extensions.)
     1089(While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.)
    11231090In addition, there are interesting future directions for the polymorphism design.
    11241091Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions.
    1125 \CFA polymorphic functions, by contrast, uses a dynamic virtual dispatch.
    1126 The runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code.
     1092\CFA polymorphic functions use dynamic virtual-dispatch;
     1093the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code.
    11271094Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types.
    11281095These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    … …  
    11311098
    11321099\begin{acks}
    1133 The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper. They also thank Magnus Madsen and three anonymous reviewers for valuable editorial feedback.
    1134 
    1135 This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}\ and the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
     1100The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper, and thank Magnus Madsen and the three anonymous reviewers for valuable feedback.
     1101This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}, and Aaron Moss and Peter Buhr are funded by the \grantsponsor{Natural Sciences and Engineering Research Council} of Canada.
     1102% the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
    11361103\end{acks}
    11371104
    … …  
    11431110\appendix
    11441111
    1145 \section{Benchmark Interfaces}
    1146 \label{sec:BenchmarkInterfaces}
     1112\section{Benchmark Stack Implementation}
     1113\label{sec:BenchmarkStackImplementation}
    11471114
    11481115\lstset{basicstyle=\linespread{0.9}\sf\small}
    11491116
     1117Throughout, @/***/@ designates a counted redundant type annotation.
     1118
     1119\medskip\noindent
    11501120\CFA
    11511121\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1152 forall(otype T) struct stack_node;
    1153 forall(otype T) struct stack { stack_node(T) * head; };
    1154 forall(otype T) void ?{}(stack(T) * s);
    1155 forall(otype T) void ?{}(stack(T) * s, stack(T) t);
    1156 forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t);
    1157 forall(otype T) void ^?{}(stack(T) * s);
    1158 forall(otype T) _Bool empty(const stack(T) * s);
    1159 forall(otype T) void push(stack(T) * s, T value);
    1160 forall(otype T) T pop(stack(T) * s);
    1161 forall(otype T) void clear(stack(T) * s);
    1162 
    1163 void print( FILE * out, const char * x );
    1164 void print( FILE * out, _Bool x );
    1165 void print( FILE * out, char x );
    1166 void print( FILE * out, int x );
    1167 forall(otype T, ttype Params | { void print( FILE *, T ); void print( FILE *, Params ); })
    1168         void print( FILE * out, T arg, Params rest );
    1169 forall(otype R, otype S | { void print( FILE *, R ); void print( FILE *, S ); })
    1170         void print( FILE * out, pair(R, S) x );
     1122forall(otype T) struct stack_node {
     1123        T value;
     1124        stack_node(T) * next;
     1125};
     1126forall(otype T) void ?{}(stack(T) * s) { (&s->head){ 0 }; }
     1127forall(otype T) void ?{}(stack(T) * s, stack(T) t) {
     1128        stack_node(T) ** crnt = &s->head;
     1129        for ( stack_node(T) * next = t.head; next; next = next->next ) {
     1130                *crnt = ((stack_node(T) *)malloc()){ next->value }; /***/
     1131                stack_node(T) * acrnt = *crnt;
     1132                crnt = &acrnt->next;
     1133        }
     1134        *crnt = 0;
     1135}
     1136forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t) {
     1137        if ( s->head == t.head ) return *s;
     1138        clear(s);
     1139        s{ t };
     1140        return *s;
     1141}
     1142forall(otype T) void ^?{}(stack(T) * s) { clear(s); }
     1143forall(otype T) _Bool empty(const stack(T) * s) { return s->head == 0; }
     1144forall(otype T) void push(stack(T) * s, T value) {
     1145        s->head = ((stack_node(T) *)malloc()){ value, s->head }; /***/
     1146}
     1147forall(otype T) T pop(stack(T) * s) {
     1148        stack_node(T) * n = s->head;
     1149        s->head = n->next;
     1150        T x = n->value;
     1151        ^n{};
     1152        free(n);
     1153        return x;
     1154}
     1155forall(otype T) void clear(stack(T) * s) {
     1156        for ( stack_node(T) * next = s->head; next; ) {
     1157                stack_node(T) * crnt = next;
     1158                next = crnt->next;
     1159                delete(crnt);
     1160        }
     1161        s->head = 0;
     1162}
    11711163\end{lstlisting}
    11721164
    … …  
    11741166\CC
    11751167\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1176 std::pair
    1177 std::forward_list wrapped in std::stack interface
    1178 
    1179 template<typename T> void print(ostream& out, const T& x) { out << x; }
    1180 template<> void print<bool>(ostream& out, const bool& x) { out << (x ? "true" : "false"); }
    1181 template<> void print<char>(ostream& out, const char& x ) { out << "'" << x << "'"; }
    1182 template<typename R, typename S> ostream& operator<< (ostream& out, const pair<R, S>& x) {
    1183         out << "["; print(out, x.first); out << ", "; print(out, x.second); return out << "]"; }
    1184 template<typename T, typename... Args> void print(ostream& out, const T& arg, const Args&... rest) {
    1185         out << arg;     print(out, rest...); }
     1168template<typename T> class stack {
     1169        struct node {
     1170                T value;
     1171                node * next;
     1172                node( const T & v, node * n = nullptr ) : value(v), next(n) {}
     1173        };
     1174        node * head;
     1175        void copy(const stack<T>& o) {
     1176                node ** crnt = &head;
     1177                for ( node * next = o.head;; next; next = next->next ) {
     1178                        *crnt = new node{ next->value }; /***/
     1179                        crnt = &(*crnt)->next;
     1180                }
     1181                *crnt = nullptr;
     1182        }
     1183  public:
     1184        stack() : head(nullptr) {}
     1185        stack(const stack<T>& o) { copy(o); }
     1186        stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
     1187        ~stack() { clear(); }
     1188        stack & operator= (const stack<T>& o) {
     1189                if ( this == &o ) return *this;
     1190                clear();
     1191                copy(o);
     1192                return *this;
     1193        }
     1194        stack & operator= (stack<T> && o) {
     1195                if ( this == &o ) return *this;
     1196                head = o.head;
     1197                o.head = nullptr;
     1198                return *this;
     1199        }
     1200        bool empty() const { return head == nullptr; }
     1201        void push(const T & value) { head = new node{ value, head };  /***/ }
     1202        T pop() {
     1203                node * n = head;
     1204                head = n->next;
     1205                T x = std::move(n->value);
     1206                delete n;
     1207                return x;
     1208        }
     1209        void clear() {
     1210                for ( node * next = head; next; ) {
     1211                        node * crnt = next;
     1212                        next = crnt->next;
     1213                        delete crnt;
     1214                }
     1215                head = nullptr;
     1216        }
     1217};
    11861218\end{lstlisting}
    11871219
    … …  
    11891221C
    11901222\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1191 struct pair { void * first, second; };
    1192 struct pair * new_pair( void * first, void * second );
    1193 struct pair * copy_pair( const struct pair * src,
    1194         void * (*copy_first)( const void * ), void * (*copy_second)( const void * ) );
    1195 void free_pair( struct pair * p, void (*free_first)( void * ), void (*free_second)( void * ) );
    1196 int cmp_pair( const struct pair * a, const struct pair * b,
    1197         int (*cmp_first)( const void *, const void * ), int (*cmp_second)( const void *, const void * ) );
    1198 
    1199 struct stack_node;
    1200 struct stack { struct stack_node * head; };
    1201 struct stack new_stack();
    1202 void copy_stack( struct stack * dst, const struct stack * src, void * (*copy)( const void * ) );
    1203 void clear_stack( struct stack * s, void (*free_el)( void * ) );
    1204 _Bool stack_empty( const struct stack * s );
    1205 void push_stack( struct stack * s, void * value );
    1206 void * pop_stack( struct stack * s );
    1207 
    1208 void print_string( FILE * out, const char * x );
    1209 void print_bool( FILE * out, _Bool x );
    1210 void print_char( FILE * out, char x );
    1211 void print_int( FILE * out, int x );
    1212 void print( FILE * out, const char * fmt, ... );
     1223struct stack_node {
     1224        void * value;
     1225        struct stack_node * next;
     1226};
     1227struct stack new_stack() { return (struct stack){ NULL }; /***/ }
     1228void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
     1229        struct stack_node ** crnt = &s->head;
     1230        for ( struct stack_node * next = t->head; next; next = next->next ) {
     1231                *crnt = malloc(sizeof(struct stack_node)); /***/
     1232                **crnt = (struct stack_node){ copy(next->value) }; /***/
     1233                crnt = &(*crnt)->next;
     1234        }
     1235        *crnt = 0;
     1236}
     1237_Bool stack_empty(const struct stack * s) { return s->head == NULL; }
     1238void push_stack(struct stack * s, void * value) {
     1239        struct stack_node * n = malloc(sizeof(struct stack_node)); /***/
     1240        *n = (struct stack_node){ value, s->head }; /***/
     1241        s->head = n;
     1242}
     1243void * pop_stack(struct stack * s) {
     1244        struct stack_node * n = s->head;
     1245        s->head = n->next;
     1246        void * x = n->value;
     1247        free(n);
     1248        return x;
     1249}
     1250void clear_stack(struct stack * s, void (*free_el)(void *)) {
     1251        for ( struct stack_node * next = s->head; next; ) {
     1252                struct stack_node * crnt = next;
     1253                next = crnt->next;
     1254                free_el(crnt->value);
     1255                free(crnt);
     1256        }
     1257        s->head = NULL;
     1258}
     1259\end{lstlisting}
     1260
     1261\medskip\noindent
     1262\CCV
     1263\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1264stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
     1265void stack::copy(const stack & o) {
     1266        node ** crnt = &head;
     1267        for ( node * next = o.head; next; next = next->next ) {
     1268                *crnt = new node{ *next->value };
     1269                crnt = &(*crnt)->next;
     1270        }
     1271        *crnt = nullptr;
     1272}
     1273stack::stack() : head(nullptr) {}
     1274stack::stack(const stack & o) { copy(o); }
     1275stack::stack(stack && o) : head(o.head) { o.head = nullptr; }
     1276stack::~stack() { clear(); }
     1277stack & stack::operator= (const stack & o) {
     1278        if ( this == &o ) return *this;
     1279        clear();
     1280        copy(o);
     1281        return *this;
     1282}
     1283stack & stack::operator= (stack && o) {
     1284        if ( this == &o ) return *this;
     1285        head = o.head;
     1286        o.head = nullptr;
     1287        return *this;
     1288}
     1289bool stack::empty() const { return head == nullptr; }
     1290void stack::push(const object & value) { head = new node{ value, head }; /***/ }
     1291ptr<object> stack::pop() {
     1292        node * n = head;
     1293        head = n->next;
     1294        ptr<object> x = std::move(n->value);
     1295        delete n;
     1296        return x;
     1297}
     1298void stack::clear() {
     1299        for ( node * next = head; next; ) {
     1300                node * crnt = next;
     1301                next = crnt->next;
     1302                delete crnt;
     1303        }
     1304        head = nullptr;
     1305}
    12131306\end{lstlisting}
    12141307
    12151308
    12161309\begin{comment}
    1217 Throughout, @/***/@ designates a counted redundant type annotation.
    12181310
    12191311\subsubsection{bench.h}
Note: See TracChangeset for help on using the changeset viewer.