Changeset c57d1935
- Timestamp:
- Apr 16, 2017, 8:25:27 AM (7 years ago)
- 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
- Location:
- doc
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/bibliography/cfa.bib
ra381b46 rc57d1935 9 9 % Predefined journal names: 10 10 % acmcs: Computing Surveys acta: Acta Infomatica 11 @string{acta="Acta Infomatica"} 11 12 % cacm: Communications of the ACM 12 13 % ibmjrd: IBM J. Research & Development ibmsj: IBM Systems Journal … … 877 878 contributer = {a3moss@uwaterloo.ca}, 878 879 key = {{ISO/IEC} {TS} 19217}, 880 author = {Concepts}, 879 881 title = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts}, 880 882 institution = {International Standard Organization}, … … 2723 2725 2724 2726 @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} 2731 2734 } 2732 2735 … … 2824 2827 key = {Fortran95}, 2825 2828 title = {Fortran 95 Standard, ISO/IEC 1539}, 2826 organization 2829 organization= {Unicomp, Inc.}, 2827 2830 address = {7660 E. Broadway, Tucson, Arizona, U.S.A, 85710}, 2828 2831 month = jan, … … 3061 3064 3062 3065 @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} 3070 3074 } 3071 3075 … … 3647 3651 author = {James Gosling and Bill Joy and Guy Steele and Gilad Bracha and Alex Buckley}, 3648 3652 title = {{Java} Language Specification}, 3653 organization= {Oracle}, 3649 3654 publisher = {Oracle}, 3650 3655 year = 2015, … … 4567 4572 keywords = {objective-c}, 4568 4573 contributor = {a3moss@uwaterloo.ca}, 4569 author = {{ Apple Computer}},4574 author = {{Objective-C}}, 4570 4575 title = {The {Objective-C} Programming Language}, 4571 4576 organization= {Apple Computer Inc.}, … … 4577 4582 keywords = {objective-c}, 4578 4583 contributor = {a3moss@uwaterloo.ca}, 4579 author = {{ Apple Computer Inc.}},4584 author = {{Xcode}}, 4580 4585 title = {{Xcode} 7 Release Notes}, 4581 4586 year = 2015, … … 5882 5887 keywords = {Rust programming language}, 5883 5888 contributer = {pabuhr@plg}, 5884 author = {{Rust Programming Language}},5889 author = {{Rust}}, 5885 5890 title = {The {Rust} Programming Language}, 5886 5891 organization= {The Rust Project Developers}, … … 6920 6925 6921 6926 @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} 6929 6935 } 6930 6936 -
doc/generic_types/generic_types.tex
ra381b46 rc57d1935 82 82 % replace/adjust listing characters that look bad in sanserif 83 83 literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1 84 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 84 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1%{_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 85 85 {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2, 86 86 moredelim=**[is][\color{red}]{`}{`}, … … 185 185 (4) Extensions introduced by \CFA must be translated in the most efficient way possible. 186 186 These 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 paireddisadvantages 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. 188 188 189 189 \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). … … 199 199 200 200 \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 aregeneralized using a @forall@ clause (giving the language its name):201 The 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): 202 202 \begin{lstlisting} 203 203 `forall( otype T )` T identity( T val ) { return val; } … … 209 209 If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@). 210 210 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. 211 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; 212 the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual-function calls. 213 A design advantage is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat. 213 214 214 215 Since 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. 215 216 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: 217 \newpage 216 218 \begin{lstlisting} 217 219 forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x + x; } $\C{// ? denotes operands}$ … … 220 222 which works for any type @T@ with a matching addition operator. 221 223 The 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.224 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~\cite{Cormack81,Baker82,Ada}, in its type analysis. 223 225 The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@. 224 226 \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. … … 367 369 368 370 One 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 371 Broadly speaking, there are three approaches to implement abstract data-structures in C. 370 372 One approach is to write bespoke data structures for each context in which they are needed. 371 373 While 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. … … 377 379 \CC, Java, and other languages use \emph{generic types} to produce type-safe abstract data-types. 378 380 \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 381 However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates. 380 382 381 383 A 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: … … 457 459 Whether a type is concrete, dtype-static, or dynamic is decided solely on the type parameters and @forall@ clause on a declaration. 458 460 This 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.461 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. 460 462 461 463 … … 843 845 forall( otype R, otype S ) void ?{}( pair(R, S) *, R, S ); // (1) 844 846 forall( dtype T, ttype Params | sized(T) | { void ?{}( T *, Params ); } ) T * new( Params p ) { 845 return ((T *)malloc( sizeof(T) )){ p }; // construct into result of malloc847 return ((T *)malloc( sizeof(T) )){ p }; // construct into result of malloc 846 848 } 847 849 pair( int, char ) * x = new( 42, '!' ); … … 948 950 \label{sec:eval} 949 951 950 Though \CFA provides significant added functionality over C, these addedfeatures have a low runtime penalty.952 Though \CFA provides significant added functionality over C, these features have a low runtime penalty. 951 953 In 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 ofstandard 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 examinecommon 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 test s aresimilar 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.954 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}). 955 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. 956 A more illustrative benchmark is to show the costs of idiomatic use of each language's features covering common usage. 957 Figure~\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}. 958 The benchmark test is similar for C and \CC. 959 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. 958 960 959 961 The 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. … … 961 963 hence runtime checks are necessary to safely down-cast objects. 962 964 The 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. 965 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. 966 Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically. 964 967 965 968 \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] 967 970 int main( int argc, char *argv[] ) { 968 971 FILE * out = fopen( "cfa-out.txt", "w" ); … … 987 990 } 988 991 \end{lstlisting} 989 \caption{\CFA Micro-Benchmark}990 \label{fig: MicroBenchmark}992 \caption{\CFA Benchmark Test} 993 \label{fig:BenchmarkTest} 991 994 \end{figure} 992 995 … … 1002 1005 \label{tab:eval} 1003 1006 \newcommand{\CT}[1]{\multicolumn{1}{c}{#1}} 1004 \begin{tabular}{r |rrrr}1007 \begin{tabular}{rrrrr} 1005 1008 & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ \hline 1006 1009 maximum memory usage (MB) & 10001 & 2501 & 2503 & 11253 \\ … … 1011 1014 \end{table} 1012 1015 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. 1016 Figure~\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. 1017 The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted. 1018 All code is compiled at \texttt{-O2} by GCC or G++ 6.2.0, with all \CC code compiled as \CCfourteen. 1019 The 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 1021 The 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; 1022 this 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. 1024 \CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@); 1025 There are two outliers in the graph for \CFA: all prints and pop of @pair@. 1026 Both 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. 1028 Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries. 1020 1029 1021 1030 \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. 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; 1033 with their omission the \CCV line count is similar to C. 1034 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 wrapper types, which may be similarly verbose. 1025 1035 1026 1036 Raw line-count, however, is a fairly rough measure of code complexity; 1027 1037 another 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. 1038 Such 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@). 1039 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. 1040 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. 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. 1043 1029 1044 1030 1045 \section{Related Work} … … 1041 1056 In 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. 1042 1057 The 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;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; 1044 1059 furthermore, \CC concepts are restricted to template polymorphism. 1045 1060 … … 1050 1065 While 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. 1051 1066 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. 1053 1068 However, Objective-C is a radical departure from C, using an object-oriented model with message-passing. 1054 1069 Objective-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;1070 The~\citep{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage-collection to C; 1056 1071 these 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. 1058 1073 Java~\citep{Java8} included generic types in Java~5; 1059 1074 Java's generic types are type-checked at compilation and type-erased at runtime, similar to \CFA's. … … 1061 1076 Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens. 1062 1077 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.1078 D~\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. 1064 1079 However, 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. 1065 1080 D and Go are garbage-collected languages, imposing the associated runtime overhead. … … 1077 1092 SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types. 1078 1093 Tuples 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.1094 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 type unsafe. 1080 1095 KW-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. 1081 1096 The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-field access. … … 1089 1104 Go does not have tuples but supports MRVF. 1090 1105 Java'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.1106 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml} and~\cite{Scala}, which decompose tuples using pattern matching. 1092 1107 1093 1108 … … 1101 1116 On the surface, the project may appear as a rehash of similar mechanisms in \CC. 1102 1117 However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation. 1103 All of these new features are being used by the \CFA development-team to build the \CFA runtime 1118 All of these new features are being used by the \CFA development-team to build the \CFA runtime-system. 1104 1119 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 1105 1120 1106 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives. 1121 There 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.) 1107 1123 In addition, there are interesting future directions for the polymorphism design. 1108 1124 Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. 1109 1125 \CFA polymorphic functions, by contrast, uses a dynamic virtual dispatch. 1110 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. 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 tosome 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 inlinedcode.1127 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 some set of types. 1128 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat. 1129 In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code. 1114 1130 1115 1131 1116 1132 \begin{acks} 1117 The authors would like to recognize the design assi tance 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.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. 1118 1134 1119 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. … … 1124 1140 \bibliography{cfa} 1125 1141 1142 1126 1143 \appendix 1127 1144 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] 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 ); 1171 \end{lstlisting} 1172 1173 \medskip\noindent 1174 \CC 1175 \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...); } 1186 \end{lstlisting} 1187 1188 \medskip\noindent 1189 C 1190 \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, ... ); 1213 \end{lstlisting} 1214 1215 1216 \begin{comment} 1131 1217 Throughout, @/***/@ designates a counted redundant type annotation. 1132 1218 … … 1223 1309 1224 1310 \lstinputlisting[language=c++]{evaluation/cpp-vbench.cpp} 1311 \end{comment} 1225 1312 1226 1313 \end{document}
Note: See TracChangeset
for help on using the changeset viewer.