Changeset 779a4a3 for doc/papers/general
- Timestamp:
- May 3, 2018, 4:33:19 PM (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, with_gc
- Children:
- f3152ab
- Parents:
- f465f0e (diff), c9d5c4f (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. - Location:
- doc/papers/general
- Files:
-
- 12 edited
-
Makefile (modified) (1 diff)
-
Paper.tex (modified) (24 diffs)
-
evaluation/c-stack.c (modified) (2 diffs)
-
evaluation/c-stack.h (modified) (1 diff)
-
evaluation/cfa-stack.c (modified) (3 diffs)
-
evaluation/cfa-stack.h (modified) (1 diff)
-
evaluation/cpp-stack.hpp (modified) (3 diffs)
-
evaluation/cpp-vstack.cpp (modified) (3 diffs)
-
evaluation/cpp-vstack.hpp (modified) (1 diff)
-
evaluation/timing.dat (modified) (1 diff)
-
evaluation/timing.gp (modified) (1 diff)
-
evaluation/timing.xlsx (modified) ( previous)
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Makefile
rf465f0e r779a4a3 69 69 mkdir -p ${Build} 70 70 71 ${BASE}.out.ps: 72 ln -fs build/Paper.out.ps .71 ${BASE}.out.ps: ${Build} 72 ln -fs ${Build}/Paper.out.ps . 73 73 74 74 WileyNJD-AMA.bst: 75 75 ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst . 76 76 77 ${GRAPHS} : timing.gp timing.dat77 ${GRAPHS} : ${Build} timing.gp timing.dat 78 78 gnuplot -e Build="'${Build}/'" evaluation/timing.gp 79 79 80 %.tex : %.fig 80 %.tex : %.fig ${Build} 81 81 fig2dev -L eepic $< > ${Build}/$@ 82 82 83 %.ps : %.fig 83 %.ps : %.fig ${Build} 84 84 fig2dev -L ps $< > ${Build}/$@ 85 85 86 %.pstex : %.fig 86 %.pstex : %.fig ${Build} 87 87 fig2dev -L pstex $< > ${Build}/$@ 88 88 fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t -
doc/papers/general/Paper.tex
rf465f0e r779a4a3 228 228 Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. 229 229 230 \CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that a ims to add modern languagefeatures to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers.230 \CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that adds modern language-features to C, while maintaining both source and runtime compatibility with C and a familiar programming model for programmers. 231 231 The four key design goals for \CFA~\cite{Bilson03} are: 232 232 (1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler; … … 237 237 \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. 238 238 239 All languages features discussed in this paper are working, except some advanced exception-handling features. 240 Not discussed in this paper are the integrated concurrency-constructs and user-level threading-library~\cite{Delisle18}. 239 241 \CFA is an \emph{open-source} project implemented as an source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3). 240 242 Ultimately, a compiler is necessary for advanced features and optimal performance. 241 All features discussed in this paper are working, unless otherwise stated as under construction. 243 % @plg2[9]% cd cfa-cc/src; cloc ArgTweak CodeGen CodeTools Common Concurrency ControlStruct Designators GenPoly InitTweak MakeLibCfa.cc MakeLibCfa.h Parser ResolvExpr SymTab SynTree Tuples driver prelude main.cc 244 % ------------------------------------------------------------------------------- 245 % Language files blank comment code 246 % ------------------------------------------------------------------------------- 247 % C++ 108 5420 5232 34961 248 % C/C++ Header 86 2379 2450 8464 249 % Teamcenter def 2 115 65 1387 250 % make 5 168 87 1052 251 % C 20 109 403 488 252 % awk 1 12 26 121 253 % sed 1 0 0 6 254 % ------------------------------------------------------------------------------- 255 % SUM: 223 8203 8263 46479 256 % ------------------------------------------------------------------------------- 257 The \CFA translator is 200+ files and 46,000+ lines of code written in C/\CC. 258 Starting with a translator versus a compiler makes it easier and faster to generate and debug C object-code rather than intermediate, assembler or machine code. 259 The translator design is based on the \emph{visitor pattern}, allowing multiple passes over the abstract code-tree, which works well for incrementally adding new feature through additional visitor passes. 260 At the heart of the translator is the type resolver, which handles the polymorphic routine/type overload-resolution. 261 % @plg2[8]% cd cfa-cc/src; cloc libcfa 262 % ------------------------------------------------------------------------------- 263 % Language files blank comment code 264 % ------------------------------------------------------------------------------- 265 % C 35 1256 1240 9116 266 % C/C++ Header 54 358 1106 1198 267 % make 2 201 325 1167 268 % C++ 3 18 17 124 269 % Assembly 3 56 97 111 270 % Bourne Shell 2 2 0 25 271 % awk 1 4 0 22 272 % ------------------------------------------------------------------------------- 273 % SUM: 100 1895 2785 11763 274 % ------------------------------------------------------------------------------- 275 The \CFA runtime system is 100+ files and 11,000+ lines of code, written in \CFA. 276 Currently, the \CFA runtime is the largest \emph{user} of \CFA providing a vehicle to test the language features and implementation. 277 % @plg2[6]% cd cfa-cc/src; cloc tests examples benchmark 278 % ------------------------------------------------------------------------------- 279 % Language files blank comment code 280 % ------------------------------------------------------------------------------- 281 % C 237 12260 2869 23286 282 % make 8 464 245 2838 283 % C/C++ Header 22 225 175 785 284 % Python 5 131 93 420 285 % C++ 10 48 5 201 286 % Lua 2 31 4 126 287 % Java 4 5 0 80 288 % Go 2 11 9 40 289 % ------------------------------------------------------------------------------- 290 % SUM: 290 13175 3400 27776 291 % ------------------------------------------------------------------------------- 292 The \CFA tests are 290+ files and 27,000+ lines of code. 293 The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks. 294 The tests check for correctness and are used for daily regression testing of commits (3800+). 242 295 243 296 Finally, it is impossible to describe a programming language without usages before definitions. … … 260 313 There are only two hard things in Computer Science: cache invalidation and \emph{naming things} -- Phil Karlton 261 314 \end{quote} 315 \vspace{-10pt} 262 316 C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax. 263 317 \CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; … … 354 408 355 409 \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}). 356 For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@ :410 For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@, where the return type supplies the type/size of the allocation, which is impossible in most type systems. 357 411 \begin{cfa} 358 412 forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); } 359 int * ip = malloc(); $\C{// select type and size from left-hand side}$ 360 double * dp = malloc(); 361 struct S {...} * sp = malloc(); 362 \end{cfa} 363 where the return type supplies the type/size of the allocation, which is impossible in most type systems. 413 // select type and size from left-hand side 414 int * ip = malloc(); double * dp = malloc(); struct S {...} * sp = malloc(); 415 \end{cfa} 364 416 365 417 Call-site inferencing and nested functions provide a localized form of inheritance. … … 373 425 } 374 426 \end{cfa} 375 Within the block, the nested version of @?<?@ performs @?>?@ and this local version overridesthe built-in @?<?@ so it is passed to @qsort@.427 The local version of @?<?@ performs @?>?@ overriding the built-in @?<?@ so it is passed to @qsort@. 376 428 Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types. 377 429 … … 382 434 inline { $\C{// nested distribution block, add forall/inline to declarations}$ 383 435 void push( stack(`T`) & s, `T` value ) ... $\C{// generic operations}$ 384 T pop( stack(`T`) & s ) ...385 436 } 386 437 } … … 388 439 389 440 441 \vspace*{-2pt} 390 442 \subsection{Traits} 391 443 392 444 \CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration: 445 393 446 \begin{cquote} 394 447 \lstDeleteShortInline@% … … 462 515 463 516 517 \vspace*{-2pt} 464 518 \section{Generic Types} 465 519 … … 474 528 475 529 \CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data-types. 476 \CFA also implements generic types thatintegrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.530 \CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation. 477 531 However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates. 478 532 … … 480 534 \begin{cquote} 481 535 \lstDeleteShortInline@% 482 \begin{tabular}{@{}l @{\hspace{2\parindentlnth}}l@{}}536 \begin{tabular}{@{}l|@{\hspace{2\parindentlnth}}l@{}} 483 537 \begin{cfa} 484 538 forall( otype R, otype S ) struct pair { … … 1373 1427 resume( $\emph{alternate-stack}$ ) 1374 1428 \end{cfa} 1375 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task \footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}~\cite{Delisle18}.1429 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task~\cite{Delisle18}. 1376 1430 Nonlocal raise is restricted to resumption to provide the exception handler the greatest flexibility because processing the exception does not unwind its stack, allowing it to continue after the handler returns. 1377 1431 … … 2040 2094 2041 2095 2096 \begin{comment} 2042 2097 \subsection{Integral Suffixes} 2043 2098 … … 2073 2128 \lstMakeShortInline@% 2074 2129 \end{cquote} 2130 \end{comment} 2075 2131 2076 2132 … … 2644 2700 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. 2645 2701 The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted. 2646 All code is compiled at \texttt{-O2} by gcc or g++ 6. 3.0, with all \CC code compiled as \CCfourteen.2702 All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen. 2647 2703 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. 2648 2704 … … 2662 2718 & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ \hline 2663 2719 maximum memory usage (MB) & 10,001 & 2,502 & 2,503 & 11,253 \\ 2664 source code size (lines) & 196 & 186 & 125 & 290\\2720 source code size (lines) & 201 & 191 & 125 & 294 \\ 2665 2721 redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ 2666 2722 binary size (KB) & 14 & 257 & 14 & 37 \\ … … 2765 2821 data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, while concurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}. 2766 2822 Finally, CCured~\cite{Necula02} and Ironclad \CC~\cite{DeLozier13} attempt to provide a more memory-safe C by annotating pointer types with garbage collection information; type-checked polymorphism in \CFA covers several of C's memory-safety issues, but more aggressive approaches such as annotating all pointer types with their nullability or requiring runtime garbage collection are contradictory to \CFA's backwards compatibility goals. 2767 2768 2769 \begin{comment}2770 \subsection{Control Structures / Declarations / Literals}2771 2772 Java has default fall through like C/\CC.2773 Pascal/Ada/Go/Rust do not have default fall through.2774 \Csharp does not have fall through but still requires a break.2775 Python uses dictionary mapping. \\2776 \CFA choose is like Rust match.2777 2778 Java has labelled break/continue. \\2779 Languages with and without exception handling.2780 2781 Alternative C declarations. \\2782 Different references \\2783 Constructors/destructors2784 2785 0/1 Literals \\2786 user defined: D, Objective-C2787 \end{comment}2788 2823 2789 2824 … … 2875 2910 } 2876 2911 _Bool stack_empty( const stack * s ) { 2877 2912 return s->head == NULL; 2878 2913 } 2879 2914 void push_stack( stack * s, void * v ) { 2880 node * n = malloc( sizeof(node)); /***/2915 node * n = malloc( sizeof(node) ); /***/ 2881 2916 *n = (node){ v, s->head }; /***/ 2882 2917 s->head = n; … … 2908 2943 }; 2909 2944 struct stack { node(T) * head; }; 2910 void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2911 void ?{}( stack(T) & s, stack(T) t ) { 2945 void ?{}( stack(T) & s, stack(T) t ) { // copy 2912 2946 node(T) ** cr = &s.head; 2913 2947 for ( node(T) * nx = t.head; nx; nx = nx->next ) { … … 2923 2957 nx = cr->next; 2924 2958 ^(*cr){}; 2925 free( cr);2959 free( cr ); 2926 2960 } 2927 2961 head = 0; 2928 2962 } 2963 2929 2964 \end{cfa} 2930 2965 & 2931 2966 \begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt] 2967 void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2932 2968 void ^?{}( stack(T) & s) { clear( s ); } 2933 2969 stack(T) ?=?( stack(T) & s, stack(T) t ) { … … 2954 2990 } 2955 2991 } 2956 2957 2992 \end{cfa} 2958 2993 \end{tabular} … … 3003 3038 return *this; 3004 3039 } 3005 bool empty() const { return head == nullptr; } 3040 bool empty() const { 3041 return head == nullptr; 3042 } 3006 3043 void push( const T & value ) { 3007 3044 head = new node{ value, head }; /***/ … … 3015 3052 } 3016 3053 }; 3017 3018 3019 3054 3020 3055 \end{cfa} … … 3066 3101 return *this; 3067 3102 } 3068 bool empty() const { return head == nullptr; } 3103 bool empty() const { 3104 return head == nullptr; 3105 } 3069 3106 void push( const object & value ) { 3070 3107 head = new node{ value, head }; /***/ … … 3079 3116 }; 3080 3117 3081 3082 3083 3118 \end{cfa} 3084 3119 \end{tabular} -
doc/papers/general/evaluation/c-stack.c
rf465f0e r779a4a3 27 27 } 28 28 29 stack new_stack() { return (stack){ NULL }; /***/ } 29 stack new_stack() { 30 return (stack){ NULL }; /***/ 31 } 30 32 31 33 stack * assign_stack( stack * s, const stack * t, … … 37 39 } 38 40 39 _Bool stack_empty( const stack * s ) { return s->head == NULL; } 41 _Bool stack_empty( const stack * s ) { 42 return s->head == NULL; 43 } 40 44 41 45 void push_stack( stack * s, void * v ) { -
doc/papers/general/evaluation/c-stack.h
rf465f0e r779a4a3 6 6 } stack; 7 7 8 void copy_stack(stack * dst, const stack * src, void * (* copy)(const void *)); 9 void clear_stack(stack * s, void (*free_el)(void *)); 8 10 stack new_stack(); 9 void copy_stack(stack * dst, const stack * src, void * (* copy)(const void *));10 11 stack * assign_stack( stack * dst, const stack * src, 11 12 void * (* copy_el)(const void *), void (* free_el)(void *)); 12 void clear_stack(stack * s, void (*free_el)(void *));13 13 14 14 _Bool stack_empty( const stack * s ); -
doc/papers/general/evaluation/cfa-stack.c
rf465f0e r779a4a3 8 8 }; 9 9 10 void ?{}( stack(T) & s ) { (s.head){ 0 }; } 11 12 void ?{}( stack(T) & s, stack(T) t ) { 10 void ?{}( stack(T) & s, stack(T) t ) { // copy 13 11 node(T) ** cr = &s.head; 14 12 for ( node(T) * nx = t.head; nx; nx = nx->next ) { … … 20 18 } 21 19 22 void ^?{}( stack(T) & s) { clear( s ); } 23 24 void clear( stack(T) & s ) with( s ) { 20 void clear( stack(T) & s ) with( s ) { 25 21 for ( node(T) * nx = head; nx; ) { 26 22 node(T) * cr = nx; 27 23 nx = cr->next; 28 24 ^(*cr){}; 29 free( cr);25 free( cr ); 30 26 } 31 27 head = 0; 32 28 } 29 30 void ?{}( stack(T) & s ) { (s.head){ 0 }; } 31 void ^?{}( stack(T) & s) { clear( s ); } 33 32 34 33 stack(T) ?=?( stack(T) & s, stack(T) t ) { … … 39 38 } 40 39 41 _Bool empty( const stack(T) & s ) { return s.head == 0; } 40 _Bool empty( const stack(T) & s ) { 41 return s.head == 0; 42 } 42 43 43 44 void push( stack(T) & s, T value ) with( s ) { -
doc/papers/general/evaluation/cfa-stack.h
rf465f0e r779a4a3 7 7 }; 8 8 9 void ?{}( stack(T) & s, stack(T) t ); 10 void clear( stack(T) & s ); 9 11 void ?{}( stack(T) & s ); 10 void ?{}( stack(T) & s, stack(T) t );11 12 void ^?{}( stack(T) & s); 12 void clear( stack(T) & s );13 13 14 14 stack(T) ?=?( stack(T) & s, stack(T) t ); -
doc/papers/general/evaluation/cpp-stack.hpp
rf465f0e r779a4a3 10 10 node * head; 11 11 12 stack() : head( nullptr ) {} 13 stack( const stack<T> & o ) { copy( o ); } 12 void copy( const stack<T> & o ) { 13 node ** cr = &head; 14 for ( node * nx = o.head; nx; nx = nx->next ) { 15 *cr = new node{ nx->value }; /***/ 16 cr = &(*cr)->next; 17 } 18 *cr = nullptr; 19 } 14 20 15 21 void clear() { … … 22 28 } 23 29 24 void copy( const stack<T> & o ) { 25 node ** cr = &head; 26 for ( node * nx = o.head; nx; nx = nx->next ) { 27 *cr = new node{ nx->value }; /***/ 28 cr = &(*cr)->next; 29 } 30 *cr = nullptr; 31 } 32 30 stack() : head( nullptr ) {} 31 stack( const stack<T> & o ) { copy( o ); } 33 32 ~stack() { clear(); } 34 33 35 stack & operator= 34 stack & operator=( const stack<T> & o ) { 36 35 if ( this == &o ) return *this; 37 36 clear(); … … 40 39 } 41 40 42 bool empty() const { return head == nullptr; } 41 bool empty() const { 42 return head == nullptr; 43 } 43 44 44 void push( const T & value ) { head = new node{ value, head }; /***/ } 45 void push( const T & value ) { 46 head = new node{ value, head }; /***/ 47 } 45 48 46 49 T pop() { -
doc/papers/general/evaluation/cpp-vstack.cpp
rf465f0e r779a4a3 3 3 4 4 stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {} 5 6 void stack::copy( const stack & o ) { 7 node ** cr = &head; 8 for ( node * nx = o.head; nx; nx = nx->next ) { 9 *cr = new node{ *nx->value }; /***/ 10 cr = &(*cr)->next; 11 } 12 *cr = nullptr; 13 } 5 14 6 15 void stack::clear() { … … 11 20 } 12 21 head = nullptr; 13 }14 15 void stack::copy( const stack & o ) {16 node ** cr = &head;17 for ( node * nx = o.head; nx; nx = nx->next ) {18 *cr = new node{ *nx->value }; /***/19 cr = &(*cr)->next;20 }21 *cr = nullptr;22 22 } 23 23 … … 33 33 } 34 34 35 bool stack::empty() const { return head == nullptr; } 35 bool stack::empty() const { 36 return head == nullptr; 37 } 36 38 37 void stack::push( const object & value ) { head = new node{ value, head }; /***/ } 39 void stack::push( const object & value ) { 40 head = new node{ value, head }; /***/ 41 } 38 42 39 43 ptr<object> stack::pop() { -
doc/papers/general/evaluation/cpp-vstack.hpp
rf465f0e r779a4a3 10 10 node * head; 11 11 12 void copy( const stack & o ); 12 13 void clear(); 13 void copy( const stack & o );14 14 15 15 stack(); -
doc/papers/general/evaluation/timing.dat
rf465f0e r779a4a3 1 1 "400 million repetitions" "C" "\\CFA{}" "\\CC{}" "\\CC{obj}" 2 "push\nint" 3002 2459 1542 3269 3 "copy\nint" 2985 2057 1539 3083 4 "clear\nint" 1374 827 756 1469 5 "pop\nint" 1416 1221 760 5098 6 "push\npair" 4214 2752 950 6873 7 "copy\npair" 6127 2105 987 7293 8 "clear\npair" 2881 885 751 3460 9 "pop\npair" 3046 5434 822 24962 2 "push\nint" 2911 2034 1504 3246 3 "copy\nint" 2953 1622 1526 3075 4 "clear\nint" 1397 754 753 1452 5 "pop\nint" 1446 1203 760 5016 6 "push\npair" 3673 2297 955 6971 7 "copy\npair" 6027 1183 998 7204 8 "clear\npair" 2840 773 748 3511 9 "pop\npair" 3025 5414 813 23867 10 -
doc/papers/general/evaluation/timing.gp
rf465f0e r779a4a3 24 24 set yrange [0:10] 25 25 26 set label "2 5.0" at 7.125,10.526 set label "23.9" at 7.125,10.5 27 27 28 28 # set datafile separator ","
Note:
See TracChangeset
for help on using the changeset viewer.
