Changeset c57d1935 for doc


Ignore:
Timestamp:
Apr 16, 2017, 8:25:27 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, resolv-new, with_gc
Children:
4635c79
Parents:
a381b46
Message:

pass over evaluation section, add more citations

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/cfa.bib

    ra381b46 rc57d1935  
    99%    Predefined journal names:
    1010%  acmcs: Computing Surveys             acta: Acta Infomatica
     11@string{acta="Acta Infomatica"}
    1112%  cacm: Communications of the ACM
    1213%  ibmjrd: IBM J. Research & Development ibmsj: IBM Systems Journal
     
    877878    contributer = {a3moss@uwaterloo.ca},
    878879    key         = {{ISO/IEC} {TS} 19217},
     880    author      = {Concepts},
    879881    title       = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts},
    880882    institution = {International Standard Organization},
     
    27232725
    27242726@online{GCCExtensions,
    2725     contributer = {a3moss@uwaterloo.ca},
    2726     key = {{GNU}},
    2727     title = {Extensions to the {C} Language Family},
    2728     year = 2014,
    2729     url = {https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/C-Extensions.html},
    2730     urldate = {2017-04-02}
     2727    contributer = {a3moss@uwaterloo.ca},
     2728    key         = {{GNU}},
     2729    author      = {{C Extensions}},
     2730    title       = {Extensions to the {C} Language Family},
     2731    year        = 2014,
     2732    note        = {\href{https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/C-Extensions.html}{https://\-gcc.gnu.org/\-onlinedocs/\-gcc-4.7.2/\-gcc/\-C\-Extensions.html}},
     2733    urldate     = {2017-04-02}
    27312734}
    27322735
     
    28242827    key         = {Fortran95},
    28252828    title       = {Fortran 95 Standard, ISO/IEC 1539},
    2826     organization = {Unicomp, Inc.},
     2829    organization= {Unicomp, Inc.},
    28272830    address     = {7660 E. Broadway, Tucson, Arizona, U.S.A, 85710},
    28282831    month       = jan,
     
    30613064
    30623065@online{GObject,
    3063     keywords = {GObject},
    3064     contributor = {a3moss@uwaterloo.ca},
    3065     author = {{The GNOME Project}},
    3066     title = {{GObject} Reference Manual},
    3067     year = 2014,
    3068     url = {https://developer.gnome.org/gobject/stable/},
    3069     urldate = {2017-04-04}
     3066    keywords    = {GObject},
     3067    contributor = {a3moss@uwaterloo.ca},
     3068    author      = {{GObject}},
     3069    organization= {The GNOME Project},
     3070    title       = {{GObject} Reference Manual},
     3071    year        = 2014,
     3072    url         = {https://developer.gnome.org/gobject/stable/},
     3073    urldate     = {2017-04-04}
    30703074}
    30713075
     
    36473651    author      = {James Gosling and Bill Joy and Guy Steele and Gilad Bracha and Alex Buckley},
    36483652    title       = {{Java} Language Specification},
     3653    organization= {Oracle},
    36493654    publisher   = {Oracle},
    36503655    year        = 2015,
     
    45674572    keywords    = {objective-c},
    45684573    contributor = {a3moss@uwaterloo.ca},
    4569     author      = {{Apple Computer}},
     4574    author      = {{Objective-C}},
    45704575    title       = {The {Objective-C} Programming Language},
    45714576    organization= {Apple Computer Inc.},
     
    45774582    keywords    = {objective-c},
    45784583    contributor = {a3moss@uwaterloo.ca},
    4579     author      = {{Apple Computer Inc.}},
     4584    author      = {{Xcode}},
    45804585    title       = {{Xcode} 7 Release Notes},
    45814586    year        = 2015,
     
    58825887    keywords    = {Rust programming language},
    58835888    contributer = {pabuhr@plg},
    5884     author      = {{Rust Programming Language}},
     5889    author      = {{Rust}},
    58855890    title       = {The {Rust} Programming Language},
    58865891    organization= {The Rust Project Developers},
     
    69206925
    69216926@online{Vala,
    6922     keywords = {GObject, Vala},
    6923     contributor = {a3moss@uwaterloo.ca},
    6924     author = {{The GNOME Project}},
    6925     title = {Vala Reference Manual},
    6926     year = 2017,
    6927     url = {https://wiki.gnome.org/Projects/Vala/Manual},
    6928     urldate = {2017-04-04}
     6927    keywords    = {GObject, Vala},
     6928    contributor = {a3moss@uwaterloo.ca},
     6929    author      = {{Vala}},
     6930    organization= {The GNOME Project},
     6931    title       = {Vala Reference Manual},
     6932    year        = 2017,
     6933    url         = {https://wiki.gnome.org/Projects/Vala/Manual},
     6934    urldate     = {2017-04-04}
    69296935}
    69306936
  • doc/generic_types/generic_types.tex

    ra381b46 rc57d1935  
    8282% replace/adjust listing characters that look bad in sanserif
    8383literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    84         {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     84        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1%{_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    8585        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2,
    8686moredelim=**[is][\color{red}]{`}{`},
     
    185185(4) Extensions introduced by \CFA must be translated in the most efficient way possible.
    186186These goals ensure existing C code-bases can be converted to \CFA incrementally with minimal effort, and C programmers can productively generate \CFA code without training beyond the features being used.
    187 \CC is often used similarly, but has the paired 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.
     187\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.
    188188
    189189\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).
     
    199199
    200200\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):
     201The signature feature of \CFA is parametric-polymorphic functions~\citep{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name):
    202202\begin{lstlisting}
    203203`forall( otype T )` T identity( T val ) { return val; }
     
    209209If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@).
    210210
    211 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual-function calls.
    212 An 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.
     211In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions;
     212the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual-function calls.
     213A design advantage is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
    213214
    214215Since bare polymorphic-types provide a restricted 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.
    215216For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
     217\newpage
    216218\begin{lstlisting}
    217219forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$
     
    220222which works for any type @T@ with a matching addition operator.
    221223The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@.
    222 There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type, as in~\cite{Ada}, in its type analysis.
     224There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada}, in its type analysis.
    223225The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@.
    224226\CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition.
     
    367369
    368370One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
    369 Broadly speaking, there are three approaches to implement abstract data structures in C.
     371Broadly speaking, there are three approaches to implement abstract data-structures in C.
    370372One approach is to write bespoke data structures for each context in which they are needed.
    371373While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
     
    377379\CC, Java, and other languages use \emph{generic types} to produce type-safe abstract data-types.
    378380\CFA also implements generic types that integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.
    379 However, for known concrete parameters, the generic type definition can be inlined, like \CC templates.
     381However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates.
    380382
    381383A 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:
     
    457459Whether a type is concrete, dtype-static, or dynamic is decided solely on the type parameters and @forall@ clause on a declaration.
    458460This design allows opaque forward declarations of generic types, \eg @forall(otype T) struct Box@ -- like in C, all uses of @Box(T)@ can be separately compiled, and callers from other translation units know the proper calling conventions to use.
    459 If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T) struct unique_ptr { T* p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off.
     461If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T) struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off.
    460462
    461463
     
    843845forall( otype R, otype S ) void ?{}( pair(R, S) *, R, S );  // (1)
    844846forall( dtype T, ttype Params | sized(T) | { void ?{}( T *, Params ); } ) T * new( Params p ) {
    845         return ((T*)malloc( sizeof(T) )){ p }; // construct into result of malloc
     847        return ((T *)malloc( sizeof(T) )){ p }; // construct into result of malloc
    846848}
    847849pair( int, char ) * x = new( 42, '!' );
     
    948950\label{sec:eval}
    949951
    950 Though \CFA provides significant added functionality over C, these added features have a low runtime penalty.
     952Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    951953In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    952 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see source code in Appendix~\ref{sec:BenchMarks}).
    953 Since all these languages share a subset comprising most of standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
    954 Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
    955 Figure~\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 benchmark tests are similar for C and \CC.
    957 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.
     954This 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}).
     955Since 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.
     956A more illustrative benchmark is to show the costs of idiomatic use of each language's features covering common usage.
     957Figure~\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}.
     958The benchmark test is similar for C and \CC.
     959The 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.
    958960
    959961The 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.
     
    961963hence runtime checks are necessary to safely down-cast objects.
    962964The 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.
    963 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has little runtime impact.
     965For 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.
     966Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    964967
    965968\begin{figure}
    966 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt,numbers=left,numberstyle=\tt\small,numberblanklines=false]
     969\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    967970int main( int argc, char *argv[] ) {
    968971        FILE * out = fopen( "cfa-out.txt", "w" );
     
    987990}
    988991\end{lstlisting}
    989 \caption{\CFA Micro-Benchmark}
    990 \label{fig:MicroBenchmark}
     992\caption{\CFA Benchmark Test}
     993\label{fig:BenchmarkTest}
    991994\end{figure}
    992995
     
    10021005\label{tab:eval}
    10031006\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    1004 \begin{tabular}{r|rrrr}
     1007\begin{tabular}{rrrrr}
    10051008                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    10061009maximum memory usage (MB)                       & 10001         & 2501          & 2503          & 11253                 \\
     
    10111014\end{table}
    10121015
    1013 Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:MicroBenchmark} and its C, \CC, and \CCV equivalents.
    1014 The data shown is the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
    1015 All code was compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen.
    1016 The benchmarks were run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency.
    1017 The C and \CCV variants are generally the slowest and most memory-hungry, due to their less-efficient memory layout and the pointer-indirection necessary to implement generic types in these languages; this problem is exacerbated by the second level of generic types in the pair-based benchmarks.
    1018 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of boolean and char tests, which makes sense given that an integer is actually larger than the pair in both languages.
    1019 \CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented here using the \CC @dynamic_cast@ mechanism); our C benchmark uses unchecked casts due to the lack of a language mechanism to perform such checks, while \CFA and \CC can enforce type-safety statically at compilation.
     1016Figure~\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.
     1017The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
     1018All code is compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen.
     1019The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency.
     1020
     1021The C and \CCV variants are generally the slowest with the largest memory footprint, because to their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
     1022this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
     1023By 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.
     1024\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
     1025There are two outliers in the graph for \CFA: all prints and pop of @pair@.
     1026Both 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.
     1027A compiler for \CFA could easily perform these optimizations.
     1028Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    10201029
    10211030\CC performs best because it uses header-only inlined libraries (\ie no separate compilation).
    1022 \CFA and \CC have the advantage of a pre-written generic @pair@ 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 in its standard distribution and \CCV does not use the \CC standard template library by construction.
    1023 The definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count for \CCV, which somewhat inflates its line count, as an actual object-oriented language would include these in the standard library; with their omission the \CCV line count is similar to C.
    1024 We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or boilerplate-filled wrapper types, which may be similarly verbose.
     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.
     1032For \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;
     1033with their omission the \CCV line count is similar to C.
     1034We 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.
    10251035
    10261036Raw line-count, however, is a fairly rough measure of code complexity;
    10271037another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    1028 Such un-checked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@). To 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. The \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. 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). 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.
     1038Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@).
     1039To 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.
     1040The \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.
     1041The 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).
     1042These 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.
     1043
    10291044
    10301045\section{Related Work}
     
    10411056In 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.
    10421057The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed properties for a type.
    1043 Until \CC concepts~\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;
     1058Until \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;
    10441059furthermore, \CC concepts are restricted to template polymorphism.
    10451060
     
    10501065While 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.
    10511066
    1052 Objective-C~\citep{obj-c-book} is an industrially successful extension to C.
     1067\citep{obj-c-book} is an industrially successful extension to C.
    10531068However, Objective-C is a radical departure from C, using an object-oriented model with message-passing.
    10541069Objective-C did not support type-checked generics until recently~\citep{xcode7}, historically using less-efficient and more error-prone runtime checking of object types.
    1055 The GObject framework~\citep{GObject} also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C;
     1070The~\citep{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C;
    10561071these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference-counting.
    1057 Vala~\citep{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.
     1072\citep{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.
    10581073Java~\citep{Java8} included generic types in Java~5;
    10591074Java's generic types are type-checked at compilation and type-erased at runtime, similar to \CFA's.
     
    10611076Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
    10621077
    1063 D~\citep{D}, Go~\citep{Go}, and Rust~\citep{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust.
     1078D~\citep{D}, Go~\citep{Go}, and~\citep{Rust} are modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go and \emph{traits} in Rust.
    10641079However, each language represents a significant departure from C in terms of language model, and none has the same level of compatibility with C as \CFA.
    10651080D and Go are garbage-collected languages, imposing the associated runtime overhead.
     
    10771092SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types.
    10781093Tuples in SETL allow subscripting, dynamic expansion, and multiple assignment.
    1079 C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types, so the mechanism is not type-safe.
     1094C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types, so the mechanism is type unsafe.
    10801095KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL.
    10811096The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field access.
     
    10891104Go does not have tuples but supports MRVF.
    10901105Java's variadic functions appear similar to C's but are type-safe using homogeneous arrays, which are less useful than \CFA's heterogeneously-typed variadic functions.
    1091 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and Scala~\cite{Scala}, which decompose tuples using pattern matching.
     1106Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and~\cite{Scala}, which decompose tuples using pattern matching.
    10921107
    10931108
     
    11011116On the surface, the project may appear as a rehash of similar mechanisms in \CC.
    11021117However, 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.
    1103 All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
     1118All of these new features are being used by the \CFA development-team to build the \CFA runtime-system.
    11041119Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    11051120
    1106 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
     1121There 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.)
    11071123In addition, there are interesting future directions for the polymorphism design.
    11081124Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions.
    11091125\CFA polymorphic functions, by contrast, uses a dynamic virtual dispatch.
    11101126The 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.
    1111 Two 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 to some set of types.
    1112 These approaches are not mutually exclusive, and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    1113 In general, we believe separate compilation producing smaller code works well with loaded hardware-caches, which may offset the benefit of larger inlined code.
     1127Two 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.
     1128These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
     1129In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code.
    11141130
    11151131
    11161132\begin{acks}
    1117 The authors would like to recognize the design assitance 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.
     1133The 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.
    11181134
    11191135This 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.
     
    11241140\bibliography{cfa}
    11251141
     1142
    11261143\appendix
    11271144
    1128 \section{Benchmark Source Code}
    1129 \label{sec:BenchMarks}
    1130 
     1145\section{Benchmark Interfaces}
     1146\label{sec:BenchmarkInterfaces}
     1147
     1148\lstset{basicstyle=\linespread{0.9}\sf\small}
     1149
     1150\CFA
     1151\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1152forall(otype T) struct stack_node;
     1153forall(otype T) struct stack { stack_node(T) * head; };
     1154forall(otype T) void ?{}(stack(T) * s);
     1155forall(otype T) void ?{}(stack(T) * s, stack(T) t);
     1156forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t);
     1157forall(otype T) void ^?{}(stack(T) * s);
     1158forall(otype T) _Bool empty(const stack(T) * s);
     1159forall(otype T) void push(stack(T) * s, T value);
     1160forall(otype T) T pop(stack(T) * s);
     1161forall(otype T) void clear(stack(T) * s);
     1162
     1163void print( FILE * out, const char * x );
     1164void print( FILE * out, _Bool x );
     1165void print( FILE * out, char x );
     1166void print( FILE * out, int x );
     1167forall(otype T, ttype Params | { void print( FILE *, T ); void print( FILE *, Params ); })
     1168        void print( FILE * out, T arg, Params rest );
     1169forall(otype R, otype S | { void print( FILE *, R ); void print( FILE *, S ); })
     1170        void print( FILE * out, pair(R, S) x );
     1171\end{lstlisting}
     1172
     1173\medskip\noindent
     1174\CC
     1175\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1176std::pair
     1177std::forward_list wrapped in std::stack interface
     1178
     1179template<typename T> void print(ostream& out, const T& x) { out << x; }
     1180template<> void print<bool>(ostream& out, const bool& x) { out << (x ? "true" : "false"); }
     1181template<> void print<char>(ostream& out, const char& x ) { out << "'" << x << "'"; }
     1182template<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 << "]"; }
     1184template<typename T, typename... Args> void print(ostream& out, const T& arg, const Args&... rest) {
     1185        out << arg;     print(out, rest...); }
     1186\end{lstlisting}
     1187
     1188\medskip\noindent
     1189C
     1190\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1191struct pair { void * first, second; };
     1192struct pair * new_pair( void * first, void * second );
     1193struct pair * copy_pair( const struct pair * src,
     1194        void * (*copy_first)( const void * ), void * (*copy_second)( const void * ) );
     1195void free_pair( struct pair * p, void (*free_first)( void * ), void (*free_second)( void * ) );
     1196int 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
     1199struct stack_node;
     1200struct stack { struct stack_node * head; };
     1201struct stack new_stack();
     1202void copy_stack( struct stack * dst, const struct stack * src, void * (*copy)( const void * ) );
     1203void clear_stack( struct stack * s, void (*free_el)( void * ) );
     1204_Bool stack_empty( const struct stack * s );
     1205void push_stack( struct stack * s, void * value );
     1206void * pop_stack( struct stack * s );
     1207
     1208void print_string( FILE * out, const char * x );
     1209void print_bool( FILE * out, _Bool x );
     1210void print_char( FILE * out, char x );
     1211void print_int( FILE * out, int x );
     1212void print( FILE * out, const char * fmt, ... );
     1213\end{lstlisting}
     1214
     1215
     1216\begin{comment}
    11311217Throughout, @/***/@ designates a counted redundant type annotation.
    11321218
     
    12231309
    12241310\lstinputlisting[language=c++]{evaluation/cpp-vbench.cpp}
     1311\end{comment}
    12251312
    12261313\end{document}
Note: See TracChangeset for help on using the changeset viewer.