Changeset 32cab5b for doc/papers/general/Paper.tex
- Timestamp:
- Apr 17, 2018, 12:01:09 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:
- 3265399
- Parents:
- b2fe1c9 (diff), 81bb114 (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. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Paper.tex
rb2fe1c9 r32cab5b 1 \documentclass{article} 2 3 \usepackage{fullpage} 1 \documentclass[AMA,STIX1COL]{WileyNJD-v2} 2 3 \articletype{RESEARCH ARTICLE}% 4 5 \received{26 April 2016} 6 \revised{6 June 2016} 7 \accepted{6 June 2016} 8 9 \raggedbottom 10 11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 12 13 % Latex packages used in the document. 14 4 15 \usepackage{epic,eepic} 5 \usepackage{xspace,calc,comment} 16 \usepackage{xspace} 17 \usepackage{comment} 6 18 \usepackage{upquote} % switch curled `'" to straight 7 19 \usepackage{listings} % format program code 8 \usepackage{enumitem} 9 \setlist[itemize]{topsep=3pt,itemsep=2pt,parsep=0pt}% global 10 \usepackage[flushmargin]{footmisc} % support label/reference in footnote 11 \usepackage{rotating} 12 \usepackage[usenames]{color} 13 \usepackage{pslatex} % reduce size of san serif font 14 \usepackage[plainpages=false,pdfpagelabels,pdfpagemode=UseNone,pagebackref=true,breaklinks=true,colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} 15 \urlstyle{sf} 16 \usepackage{breakurl} 17 18 \setlength{\textheight}{9in} 19 %\oddsidemargin 0.0in 20 \renewcommand{\topfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page 21 \renewcommand{\bottomfraction}{0.8} % float must be greater than X of the page before it is forced onto its own page 22 \renewcommand{\floatpagefraction}{0.8} % float must be greater than X of the page before it is forced onto its own page 23 \renewcommand{\textfraction}{0.0} % the entire page maybe devoted to floats with no text on the page at all 20 %\usepackage{enumitem} 21 %\setlist[itemize]{topsep=3pt,itemsep=2pt,parsep=0pt}% global 22 %\usepackage{rotating} 23 24 \hypersetup{breaklinks=true} 25 \definecolor{ForestGreen}{cmyk}{1, 0, 0.99995, 0} 26 27 \usepackage[pagewise]{lineno} 28 \renewcommand{\linenumberfont}{\scriptsize\sffamily} 24 29 25 30 \lefthyphenmin=4 % hyphen only after 4 characters 26 31 \righthyphenmin=4 32 33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 27 34 28 35 % Names used in the document. … … 64 71 \newlength{\gcolumnposn} % temporary hack because lstlisting does not handle tabs correctly 65 72 \newlength{\columnposn} 66 \setlength{\gcolumnposn}{ 2.75in}73 \setlength{\gcolumnposn}{3.5in} 67 74 \setlength{\columnposn}{\gcolumnposn} 68 75 \newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}} … … 97 104 }% 98 105 \newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}} 99 \ newcommand*{\etal}{%106 \renewcommand*{\etal}{% 100 107 \@ifnextchar{.}{\protect\ETAL}% 101 108 {\protect\ETAL.\xspace}% … … 145 152 belowskip=3pt, 146 153 % replace/adjust listing characters that look bad in sanserif 147 literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scripts criptstyle\land\,$}}1148 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {@}{\small{@}}1% {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1149 {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0. 4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2,154 literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1 155 {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 156 {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2, 150 157 moredelim=**[is][\color{red}]{`}{`}, 151 158 }% lstset 152 153 % inline code @...@154 \lstMakeShortInline@%155 159 156 160 \lstnewenvironment{cfa}[1][] … … 161 165 {} 162 166 163 164 \title{\protect\CFA : Adding Modern Programming Language Features to C} 165 166 \author{Aaron Moss, Robert Schluntz, Peter Buhr} 167 % \email{a3moss@uwaterloo.ca} 168 % \email{rschlunt@uwaterloo.ca} 169 % \email{pabuhr@uwaterloo.ca} 170 % \affiliation{% 171 % \institution{University of Waterloo} 172 % \department{David R. Cheriton School of Computer Science} 173 % \streetaddress{Davis Centre, University of Waterloo} 174 % \city{Waterloo} 175 % \state{ON} 176 % \postcode{N2L 3G1} 177 % \country{Canada} 178 % } 179 180 %\terms{generic, tuple, variadic, types} 181 %\keywords{generic types, tuple types, variadic types, polymorphic functions, C, Cforall} 182 183 \begin{document} 184 \maketitle 185 186 187 \begin{abstract} 167 % inline code @...@ 168 \lstMakeShortInline@% 169 170 171 \title{\texorpdfstring{\protect\CFA : Adding Modern Programming Language Features to C}{Cforall : Adding Modern Programming Language Features to C}} 172 173 \author[1]{Aaron Moss} 174 \author[1]{Robert Schluntz} 175 \author[1]{Peter A. Buhr*} 176 \authormark{Aaron Moss \textsc{et al}} 177 178 \address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}} 179 180 \corres{*Peter A. Buhr, \email{pabuhr{\char`\@}uwaterloo.ca}} 181 \presentaddress{David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada} 182 183 184 \abstract[Summary]{ 188 185 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects. 189 186 This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. … … 195 192 This paper presents a quick tour of \CFA features showing how their design avoids shortcomings of similar features in C and other C-like languages. 196 193 Finally, experimental results are presented to validate several of the new features. 197 \end{abstract} 194 }% 195 196 \keywords{generic types, tuple types, variadic types, polymorphic functions, C, Cforall} 197 198 199 \begin{document} 200 \linenumbers % comment out to turn off line numbering 201 202 \maketitle 198 203 199 204 … … 217 222 Love it or hate it, C is extremely popular, highly used, and one of the few systems languages. 218 223 In many cases, \CC is often used solely as a better C. 219 N onetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.224 Nevertheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. 220 225 221 226 \CFA (pronounced ``C-for-all'', and written \CFA or Cforall) is an evolutionary extension of the C programming language that aims to add modern language features to C while maintaining both source compatibility with C and a familiar programming model for programmers. … … 230 235 \CFA is currently implemented as a 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). 231 236 Ultimately, a compiler is necessary for advanced features and optimal performance. 232 All of the features discussed in this paper are working, unless a feature states it is a future feature for completion.237 All features discussed in this paper are working, unless otherwise stated as under construction. 233 238 234 239 Finally, it is impossible to describe a programming language without usages before definitions. … … 258 263 259 264 \begin{cfa} 260 int max = 2147483647; $\C[3.75in]{// (1)}$265 int max = 2147483647; $\C[4in]{// (1)}$ 261 266 double max = 1.7976931348623157E+308; $\C{// (2)}$ 262 267 int max( int a, int b ) { return a < b ? b : a; } $\C{// (3)}$ 263 268 double max( double a, double b ) { return a < b ? b : a; } $\C{// (4)}\CRT$ 264 max( 7, -max ); $\C{// uses (3) and (1), by matching int from constant 7}$265 max( max, 3.14 ); 266 max( max, -max ); 267 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}$269 max( 7, -max ); $\C[2.75in]{// uses (3) and (1), by matching int from constant 7}$ 270 max( max, 3.14 ); $\C{// uses (4) and (2), by matching double from constant 3.14}$ 271 max( max, -max ); $\C{// ERROR: ambiguous}$ 272 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}\CRT$ 268 273 \end{cfa} 269 274 … … 292 297 \begin{cfa} 293 298 `forall( otype T )` T identity( T val ) { return val; } 294 int forty_two = identity( 42 ); 299 int forty_two = identity( 42 ); $\C{// T is bound to int, forty\_two == 42}$ 295 300 \end{cfa} 296 301 This @identity@ function can be applied to any complete \newterm{object type} (or @otype@). … … 306 311 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: 307 312 \begin{cfa} 308 forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; } 313 forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; } $\C{// ? denotes operands}$ 309 314 int val = twice( twice( 3.7 ) ); 310 315 \end{cfa} … … 325 330 } 326 331 double key = 5.0, vals[10] = { /* 10 sorted float values */ }; 327 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); 332 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$ 328 333 \end{cfa} 329 334 which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrappers: … … 335 340 forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) { 336 341 T * result = bsearch( key, arr, size ); $\C{// call first version}$ 337 return result ? result - arr : size; 338 } 339 double * val = bsearch( 5.0, vals, 10 ); 342 return result ? result - arr : size; $\C{// pointer subtraction includes sizeof(T)}$ 343 } 344 double * val = bsearch( 5.0, vals, 10 ); $\C{// selection based on return type}$ 340 345 int posn = bsearch( 5.0, vals, 10 ); 341 346 \end{cfa} … … 361 366 forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ } 362 367 { 363 int ?<?( double x, double y ) { return x `>` y; } 368 int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behaviour}$ 364 369 qsort( vals, size ); $\C{// descending sort}$ 365 370 } … … 367 372 Within the block, the nested version of @?<?@ performs @?>?@ and this local version overrides the built-in @?<?@ so it is passed to @qsort@. 368 373 Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types. 374 375 Under construction is a mechanism to distribute @forall@ over routines/types, where each block declaration is prefixed with the initial @forall@ clause significantly reducing duplication (see @stack@ examples in Section~\ref{sec:eval}): 376 \begin{cfa} 377 forall( otype `T` ) { $\C{// forall block}$ 378 struct stack { stack_node(`T`) * head; }; $\C{// generic type}$ 379 void push( stack(`T`) & s, `T` value ) ... $\C{// generic operations}$ 380 T pop( stack(`T`) & s ) ... 381 } 382 \end{cfa} 369 383 370 384 … … 378 392 T ?+=?( T *, T ); 379 393 T ++?( T * ); 380 T ?++( T * ); };381 394 T ?++( T * ); 395 }; 382 396 forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) { // use trait 383 397 `T` total = { `0` }; $\C{// instantiate T from 0 by calling its constructor}$ 384 398 for ( unsigned int i = 0; i < size; i += 1 ) total `+=` a[i]; $\C{// select appropriate +}$ 385 return total; } 399 return total; 400 } 386 401 \end{cfa} 387 402 … … 392 407 void ?{}( T &, T ); $\C{// copy constructor}$ 393 408 void ?=?( T &, T ); $\C{// assignment operator}$ 394 void ^?{}( T & ); }; $\C{// destructor}$ 409 void ^?{}( T & ); $\C{// destructor}$ 410 }; 395 411 \end{cfa} 396 412 Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete type: stack-allocatable, default or copy-initialized, assigned, and deleted. … … 436 452 One approach is to write bespoke data-structures for each context in which they are needed. 437 453 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. 438 A second approach is to use @void *@ 454 A second approach is to use @void *@-based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality. 439 455 However, basing all polymorphism on @void *@ eliminates the type-checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is not otherwise needed. 440 456 A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type-checked, but errors may be difficult to interpret. … … 526 542 Results of these layout functions are cached so that they are only computed once per type per function. %, as in the example below for @pair@. 527 543 Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature. 528 For instance, a function that strips duplicate values from an unsorted @vector(T)@ would likely have a pointer to the vector as its only explicit parameter, but usesome sort of @set(T)@ internally to test for duplicate values.544 For instance, a function that strips duplicate values from an unsorted @vector(T)@ likely has a pointer to the vector as its only explicit parameter, but uses some sort of @set(T)@ internally to test for duplicate values. 529 545 This function could acquire the layout for @set(T)@ by calling its layout function with the layout of @T@ implicitly passed into the function. 530 546 … … 553 569 struct litres {}; 554 570 555 forall( dtype U ) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {571 forall( dtype U ) scalar(U) ?+?( scalar(U) a, scalar(U) b ) { 556 572 return (scalar(U)){ a.value + b.value }; 557 573 } … … 592 608 [ q, r ] = div( 13.5, 5.2 ); $\C{// assign into tuple}$ 593 609 \end{cfa} 594 Clearly, this approach is straightforward to understand and use;610 This approach is straightforward to understand and use; 595 611 therefore, why do few programming languages support this obvious feature or provide it awkwardly? 596 T he answer is thatthere are complex consequences that cascade through multiple aspects of the language, especially the type-system.612 To answer, there are complex consequences that cascade through multiple aspects of the language, especially the type-system. 597 613 This section show these consequences and how \CFA handles them. 598 614 … … 644 660 p`->0` = 5; $\C{// change quotient}$ 645 661 bar( qr`.1`, qr ); $\C{// pass remainder and quotient/remainder}$ 646 rem = [div( 13, 5 ), 42]`.0.1`; $\C{// access 2nd component of 1st component of tuple expression}$662 rem = [div( 13, 5 ), 42]`.0.1`; $\C{// access 2nd component of 1st component}$ 647 663 \end{cfa} 648 664 … … 653 669 Tuple flattening recursively expands a tuple into the list of its basic components. 654 670 Tuple structuring packages a list of expressions into a value of tuple type, \eg: 655 %\lstDeleteShortInline@%656 %\par\smallskip657 %\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}658 671 \begin{cfa} 659 672 int f( int, int ); 660 intg( [int, int] );661 inth( int, [int, int] );673 [int] g( [int, int] ); 674 [int] h( int, [int, int] ); 662 675 [int, int] x; 663 676 int y; 664 f( x ); $\C{// flatten}$ 665 g( y, 10 ); $\C{// structure}$ 666 h( x, y ); $\C{// flatten and structure}$ 667 \end{cfa} 668 %\end{cfa} 669 %& 670 %\begin{cfa} 671 %\end{tabular} 672 %\smallskip\par\noindent 673 %\lstMakeShortInline@% 677 f( x ); $\C{// flatten}$ 678 g( y, 10 ); $\C{// structure}$ 679 h( x, y ); $\C{// flatten and structure}$ 680 \end{cfa} 674 681 In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as the two arguments. 675 682 In the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the parameter type of @g@. … … 682 689 An assignment where the left side is a tuple type is called \newterm{tuple assignment}. 683 690 There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \newterm{multiple} and \newterm{mass assignment}, respectively. 684 %\lstDeleteShortInline@%685 %\par\smallskip686 %\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}687 691 \begin{cfa} 688 692 int x = 10; … … 694 698 [y, x] = 3.14; $\C{// mass assignment}$ 695 699 \end{cfa} 696 %\end{cfa}697 %&698 %\begin{cfa}699 %\end{tabular}700 %\smallskip\par\noindent701 %\lstMakeShortInline@%702 700 Both kinds of tuple assignment have parallel semantics, so that each value on the left and right side is evaluated before any assignments occur. 703 701 As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function, \eg, @[x, y] = [y, x]@. … … 708 706 This example shows mass, multiple, and cascading assignment used in one expression: 709 707 \begin{cfa} 710 voidf( [int, int] );708 [void] f( [int, int] ); 711 709 f( [x, y] = z = 1.5 ); $\C{// assignments in parameter list}$ 712 710 \end{cfa} … … 723 721 Here, the mass assignment sets all members of @s@ to zero. 724 722 Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (\eg rearrange, drop, and duplicate components). 725 %\lstDeleteShortInline@%726 %\par\smallskip727 %\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}728 723 \begin{cfa} 729 724 [int, int, long, double] x; … … 733 728 [int, int, int] y = x.[2, 0, 2]; $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$ 734 729 \end{cfa} 735 %\end{cfa}736 %&737 %\begin{cfa}738 %\end{tabular}739 %\smallskip\par\noindent740 %\lstMakeShortInline@%741 730 It is also possible for a member access to contain other member accesses, \eg: 742 731 \begin{cfa} … … 796 785 Since @void@ is effectively a 0-element tuple, (3) discards the first and third return values, which is effectively equivalent to @[(int)(g().1.0), (int)(g().1.1)]@). 797 786 798 Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions would requiremore precise matching of types than allowed for function arguments and parameters.}.787 Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions requires more precise matching of types than allowed for function arguments and parameters.}. 799 788 As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3. 800 789 Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid. … … 813 802 where @[5, "hello"]@ is flattened, giving argument list @5, "hello"@, and @T@ binds to @int@ and @U@ binds to @const char@. 814 803 Tuples, however, may contain polymorphic components. 815 For example, a plus operator can be written to add two triples together.804 For example, a plus operator can be written to sum two triples. 816 805 \begin{cfa} 817 806 forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) { … … 825 814 Flattening and restructuring conversions are also applied to tuple types in polymorphic type assertions. 826 815 \begin{cfa} 827 intf( [int, double], double );816 [int] f( [int, double], double ); 828 817 forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U ); 829 818 g( 5, 10.21 ); … … 836 825 % \end{cfa} 837 826 % so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism. 838 % These thunks are generated locally using gcc nested-functions, rather ho siting them to the external scope, so they can easily access local state.827 % These thunks are generated locally using gcc nested-functions, rather hoisting them to the external scope, so they can easily access local state. 839 828 840 829 … … 847 836 As such, @ttype@ variables are also called \newterm{argument packs}. 848 837 849 Like variadic templates, the main way to manipulate @ttype@ polymorphic functions isvia recursion.838 Like variadic templates, @ttype@ polymorphic functions are primarily manipulated via recursion. 850 839 Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful. 851 840 Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled. 852 For example, a generalized @sum@ function written using @ttype@:841 For example, a generalized @sum@ function: 853 842 \begin{cfa} 854 843 int sum$\(_0\)$() { return 0; } … … 1028 1017 \begin{cquote} 1029 1018 \lstDeleteShortInline@% 1030 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}1031 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1019 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1020 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1032 1021 \begin{cfa} 1033 1022 case 2, 10, 34, 42: … … 1040 1029 \lstMakeShortInline@% 1041 1030 \end{cquote} 1042 for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, because a space is required after a number, otherwise theperiod is a decimal point.}1031 for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, as a space is required after a number, otherwise the first period is a decimal point.} 1043 1032 \begin{cquote} 1044 1033 \lstDeleteShortInline@% 1045 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}1046 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1034 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1035 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1047 1036 \begin{cfa} 1048 1037 case 2~42: … … 1060 1049 \end{cfa} 1061 1050 1062 C allows placement of @case@ clauses \emph{within} statements nested in the @switch@ body ( seeDuff's device~\cite{Duff83});1051 C allows placement of @case@ clauses \emph{within} statements nested in the @switch@ body (called Duff's device~\cite{Duff83}); 1063 1052 \begin{cfa} 1064 1053 switch ( i ) { … … 1071 1060 } 1072 1061 \end{cfa} 1073 \CFA precludes this form of transfer intoa control structure because it causes undefined behaviour, especially with respect to missed initialization, and provides very limited functionality.1062 \CFA precludes this form of transfer \emph{into} a control structure because it causes undefined behaviour, especially with respect to missed initialization, and provides very limited functionality. 1074 1063 1075 1064 C allows placement of declaration within the @switch@ body and unreachable code at the start, resulting in undefined behaviour: … … 1136 1125 \end{figure} 1137 1126 1138 Finally, @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases: 1139 \begin{cquote} 1127 Finally, Figure~\ref{f:FallthroughStatement} shows @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases. 1128 The target label must be below the @fallthrough@ and may not be nested in a control structure, \ie @fallthrough@ cannot form a loop, and the target label must be at the same or higher level as the containing @case@ clause and located at the same level as a @case@ clause; 1129 the target label may be case @default@, but only associated with the current @switch@/@choose@ statement. 1130 1131 \begin{figure} 1132 \centering 1140 1133 \lstDeleteShortInline@% 1141 1134 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} … … 1159 1152 case 4: 1160 1153 ... `fallthrough common;` 1161 common:1154 `common`: // below fallthrough at same level as case clauses 1162 1155 ... // common code for cases 3 and 4 1163 1156 // implicit break … … 1166 1159 \end{tabular} 1167 1160 \lstMakeShortInline@% 1168 \end{cquote} 1169 The target label may be case @default@. 1170 1171 Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety. 1161 \caption{\lstinline|fallthrough| Statement} 1162 \label{f:FallthroughStatement} 1163 \end{figure} 1172 1164 1173 1165 … … 1299 1291 R r; 1300 1292 ... `resume( r );` ... 1301 ... r.fix // control does returnhere after handler1293 ... r.fix // control returns here after handler 1302 1294 } 1303 1295 `try` { … … 1412 1404 1413 1405 1414 \subsection{\texorpdfstring{\protect\lstinline{with} Clause / Statement}{with Clause /Statement}}1415 \label{s:With ClauseStatement}1406 \subsection{\texorpdfstring{\protect\lstinline{with} Statement}{with Statement}} 1407 \label{s:WithStatement} 1416 1408 1417 1409 Grouping heterogeneous data into \newterm{aggregate}s (structure/union) is a common programming practice, and an aggregate can be further organized into more complex structures, such as arrays and containers: … … 1433 1425 A similar situation occurs in object-oriented programming, \eg \CC: 1434 1426 \begin{C++} 1435 class C{1427 struct S { 1436 1428 char c; $\C{// fields}$ 1437 1429 int i; 1438 1430 double d; 1439 intf() { $\C{// implicit ``this'' aggregate}$1431 void f() { $\C{// implicit ``this'' aggregate}$ 1440 1432 `this->`c; `this->`i; `this->`d; $\C{// access containing fields}$ 1441 1433 } 1442 1434 } 1443 1435 \end{C++} 1444 Object-oriented nesting of member functions in a \lstinline[language=C++]@class @ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping.1436 Object-oriented nesting of member functions in a \lstinline[language=C++]@class/struct@ allows eliding \lstinline[language=C++]@this->@ because of lexical scoping. 1445 1437 However, for other aggregate parameters, qualification is necessary: 1446 1438 \begin{cfa} 1447 1439 struct T { double m, n; }; 1448 int C::f( T & t ) { $\C{// multiple aggregate parameters}$1449 c; i; d; $\C{\color{red}// this- \textgreater.c, this-\textgreater.i, this-\textgreater.d}$1440 int S::f( T & t ) { $\C{// multiple aggregate parameters}$ 1441 c; i; d; $\C{\color{red}// this--{\textgreater}.c, this--{\textgreater}.i, this--{\textgreater}.d}$ 1450 1442 `t.`m; `t.`n; $\C{// must qualify}$ 1451 1443 } … … 1461 1453 with the generality of opening multiple aggregate-parameters: 1462 1454 \begin{cfa} 1463 intf( S & s, T & t ) `with ( s, t )` { $\C{// multiple aggregate parameters}$1455 void f( S & s, T & t ) `with ( s, t )` { $\C{// multiple aggregate parameters}$ 1464 1456 c; i; d; $\C{\color{red}// s.c, s.i, s.d}$ 1465 1457 m; n; $\C{\color{red}// t.m, t.n}$ … … 1527 1519 \begin{cfa} 1528 1520 struct S { int i, j; } sv; 1529 with ( sv ) { $\C{ implicit reference}$1521 with ( sv ) { $\C{// implicit reference}$ 1530 1522 S & sr = sv; 1531 with ( sr ) { $\C{ explicit reference}$1523 with ( sr ) { $\C{// explicit reference}$ 1532 1524 S * sp = &sv; 1533 with ( *sp ) { $\C{ computed reference}$1534 i = 3; j = 4; $\C{\color{red}// sp- {\textgreater}i, sp-{\textgreater}j}$1525 with ( *sp ) { $\C{// computed reference}$ 1526 i = 3; j = 4; $\C{\color{red}// sp--{\textgreater}i, sp--{\textgreater}j}$ 1535 1527 } 1536 1528 i = 2; j = 3; $\C{\color{red}// sr.i, sr.j}$ … … 1539 1531 } 1540 1532 \end{cfa} 1533 1534 Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety. 1541 1535 1542 1536 … … 1582 1576 \begin{cquote} 1583 1577 \lstDeleteShortInline@% 1584 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}1585 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1578 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 1579 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1586 1580 \begin{cfa} 1587 1581 `[5] *` int x1; … … 1598 1592 \begin{cfa} 1599 1593 // array of 5 pointers to int 1600 // pointer to a n array of 5 int1601 // function returning pointer to a n array of 5 int and taking anint1594 // pointer to array of 5 int 1595 // function returning pointer to array of 5 int and taking int 1602 1596 \end{cfa} 1603 1597 \end{tabular} … … 1610 1604 \begin{cquote} 1611 1605 \lstDeleteShortInline@% 1612 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}1613 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1606 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1607 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1614 1608 \begin{cfa} 1615 1609 `*` int x, y; … … 1630 1624 \begin{cquote} 1631 1625 \lstDeleteShortInline@% 1632 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}1633 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}} \\1626 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 1627 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ 1634 1628 \begin{cfa} 1635 1629 [ 5 ] int z; … … 1672 1666 \begin{cquote} 1673 1667 \lstDeleteShortInline@% 1674 \begin{tabular}{@{}l@{\hspace{ 1em}}l@{\hspace{1em}}l@{}}1675 \multicolumn{1}{c@{\hspace{ 1em}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}} \\1668 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 1669 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ 1676 1670 \begin{cfa} 1677 1671 extern const * const int x; 1678 static const * [ 5] const int y;1672 static const * [5] const int y; 1679 1673 \end{cfa} 1680 1674 & 1681 1675 \begin{cfa} 1682 1676 int extern const * const x; 1683 static const int (* const y)[ 5]1677 static const int (* const y)[5] 1684 1678 \end{cfa} 1685 1679 & … … 1697 1691 \begin{cquote} 1698 1692 \lstDeleteShortInline@% 1699 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}1700 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1693 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1694 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1701 1695 \begin{cfa} 1702 1696 y = (* int)x; … … 1715 1709 as well, parameter names are optional, \eg: 1716 1710 \begin{cfa} 1717 [ int x ] f ( /* void */ ); $\C{// returning int with no parameters}$1718 [ int x ] f (...); 1719 [ * int ] g ( int y ); 1720 [ void ] h ( int, char ); 1721 [ * int, int ] j ( int ); $\C{// returning pointer to int and int,with int parameter}$1711 [ int x ] f ( /* void */ ); $\C[2.5in]{// returning int with no parameters}$ 1712 [ int x ] f (...); $\C{// returning int with unknown parameters}$ 1713 [ * int ] g ( int y ); $\C{// returning pointer to int with int parameter}$ 1714 [ void ] h ( int, char ); $\C{// returning no result with int and char parameters}$ 1715 [ * int, int ] j ( int ); $\C{// returning pointer to int and int with int parameter}$ 1722 1716 \end{cfa} 1723 1717 This syntax allows a prototype declaration to be created by cutting and pasting source text from the function-definition header (or vice versa). … … 1725 1719 \begin{cquote} 1726 1720 \lstDeleteShortInline@% 1727 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}1728 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\1721 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1722 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 1729 1723 \begin{cfa} 1730 1724 [double] foo(), foo( int ), foo( double ) {...} … … 1741 1735 The syntax for pointers to \CFA functions specifies the pointer name on the right, \eg: 1742 1736 \begin{cfa} 1743 * [ int x ] () fp; 1744 * [ * int ] ( int y ) gp; 1745 * [ ] ( int, char ) hp; 1746 * [ * int, int ] ( int ) jp; $\C{// pointer to function returning pointer to int and int,with int parameter}$1737 * [ int x ] () fp; $\C{// pointer to function returning int with no parameters}$ 1738 * [ * int ] ( int y ) gp; $\C{// pointer to function returning pointer to int with int parameter}$ 1739 * [ ] ( int, char ) hp; $\C{// pointer to function returning no result with int and char parameters}$ 1740 * [ * int, int ] ( int ) jp; $\C{// pointer to function returning pointer to int and int with int parameter}$ 1747 1741 \end{cfa} 1748 1742 Note, a function name cannot be specified: 1749 1743 \begin{cfa} 1750 * [ int x ] f () fp; $\C{// function name "f" is disallowed}$1744 * [ int x ] f () fp; $\C{// function name "f" is disallowed}\CRT$ 1751 1745 \end{cfa} 1752 1746 … … 1863 1857 \begin{cfa} 1864 1858 struct S { double x, y; }; 1865 int i, j;1859 int x, y; 1866 1860 void f( int & i, int & j, S & s, int v[] ); 1867 f( 3, i + j, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } );$\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$1861 f( 3, x + y, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } ); $\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$ 1868 1862 \end{cfa} 1869 1863 This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of explicit definition of a temporary variable or the runtime cost of pass-by-value. … … 1952 1946 1953 1947 One of the strengths (and weaknesses) of C is memory-management control, allowing resource release to be precisely specified versus unknown release with garbage-collected memory-management. 1954 However, this manual approach is oftenverbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.1948 However, this manual approach is verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory. 1955 1949 \CC addresses these issues using Resource Aquisition Is Initialization (RAII), implemented by means of \newterm{constructor} and \newterm{destructor} functions; 1956 1950 \CFA adopts constructors and destructors (and @finally@) to facilitate RAII. … … 2004 1998 { 2005 1999 VLA x, y = { 20, 0x01 }, z = y; $\C{// z points to y}$ 2006 // ?{}( x ); ?{}( y, 20, 0x01 );?{}( z, y );2000 // ?{}( x ); ?{}( y, 20, 0x01 ); ?{}( z, y ); 2007 2001 ^x{}; $\C{// deallocate x}$ 2008 2002 x{}; $\C{// reallocate x}$ … … 2052 2046 \begin{cquote} 2053 2047 \lstDeleteShortInline@% 2054 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}2048 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 2055 2049 \begin{cfa} 2056 2050 20_`hh` // signed char … … 2105 2099 2106 2100 For readability, it is useful to associate units to scale literals, \eg weight (stone, pound, kilogram) or time (seconds, minutes, hours). 2107 The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call-syntax ( literal argument before function name), using the backquote, to convert basic literals into user literals.2101 The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call-syntax (postfix: literal argument before function name), using the backquote, to convert basic literals into user literals. 2108 2102 The backquote is a small character, making the unit (function name) predominate. 2109 2103 For examples, the multi-precision integer-type in Section~\ref{s:MultiPrecisionIntegers} has user literals: … … 2113 2107 y = "12345678901234567890123456789"|`mp| + "12345678901234567890123456789"|`mp|; 2114 2108 \end{cfa} 2115 Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions .2109 Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions, where @?`@ denotes a postfix-function name and @`@ denotes a postfix-function call. 2116 2110 }% 2111 \begin{cquote} 2112 \lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}} 2113 \lstDeleteShortInline@% 2114 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 2115 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}} & \multicolumn{1}{c}{\textbf{postfix pointer}} \\ 2116 \begin{cfa} 2117 int ?`h( int s ); 2118 int ?`h( double s ); 2119 int ?`m( char c ); 2120 int ?`m( const char * s ); 2121 int ?`t( int a, int b, int c ); 2122 \end{cfa} 2123 & 2124 \begin{cfa} 2125 0 `h; 2126 3.5`h; 2127 '1'`m; 2128 "123" "456"`m; 2129 [1,2,3]`t; 2130 \end{cfa} 2131 & 2132 \begin{cfa} 2133 int i = 7; 2134 i`h; 2135 (i + 3)`h; 2136 (i + 3.5)`h; 2137 2138 \end{cfa} 2139 & 2140 \begin{cfa} 2141 int (* ?`p)( int i ); 2142 ?`p = ?`h; 2143 3`p; 2144 i`p; 2145 (i + 3)`p; 2146 \end{cfa} 2147 \end{tabular} 2148 \lstMakeShortInline@% 2149 \end{cquote} 2117 2150 2118 2151 The right of Figure~\ref{f:UserLiteral} shows the equivalent \CC version using the underscore for the call-syntax. … … 2136 2169 return (W){ l.stones + r.stones }; 2137 2170 } 2138 W |?`st|( double w) { return (W){ w }; }2139 W |?`lb|( double w ) { return (W){ w /14.0 }; }2140 W |?`kg|( double w ) { return (W) { w *0.16 }; }2171 W |?`st|(double w) { return (W){ w }; } 2172 W |?`lb|(double w) { return (W){ w/14.0 }; } 2173 W |?`kg|(double w) { return (W){ w*0.16 }; } 2141 2174 2142 2175 … … 2154 2187 \begin{cfa} 2155 2188 struct W { 2156 2157 2158 2189 double stones; 2190 W() { stones = 0.0; } 2191 W( double w ) { stones = w; } 2159 2192 }; 2160 2193 W operator+( W l, W r ) { 2161 2194 return W( l.stones + r.stones ); 2162 2195 } 2163 W |operator"" _st|( unsigned long long int w ) { return W( w); }2164 W |operator"" _lb|( unsigned long long int w ) { return W( w / 14.0); }2165 W |operator"" _kg|( unsigned long long int w ) { return W( w * 0.16); }2166 W |operator"" _st|(long double w ) { return W( w ); }2167 W |operator"" _lb|(long double w ) { return W( w / 14.0 ); }2168 W |operator"" _kg|(long double w ) { return W( w * 0.16 ); }2196 W |operator""_st|(unsigned long long int w) {return W(w); } 2197 W |operator""_lb|(unsigned long long int w) {return W(w/14.0); } 2198 W |operator""_kg|(unsigned long long int w) {return W(w*0.16); } 2199 W |operator""_st|(long double w ) { return W( w ); } 2200 W |operator""_lb|(long double w ) { return W( w / 14.0 ); } 2201 W |operator""_kg|(long double w ) { return W( w * 0.16 ); } 2169 2202 int main() { 2170 2203 W w, heavy = { 20 }; … … 2199 2232 \begin{cquote} 2200 2233 \lstDeleteShortInline@% 2201 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2202 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\2234 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2235 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ 2203 2236 \begin{cfa} 2204 2237 const short int `MIN` = -32768; … … 2218 2251 \begin{cquote} 2219 2252 \lstDeleteShortInline@% 2220 \lstset{basicstyle=\linespread{0.9}\sf\small} 2221 \begin{tabular}{@{}l@{\hspace{0.5\parindentlnth}}l@{}} 2222 \multicolumn{1}{c@{\hspace{0.5\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 2253 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2254 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 2223 2255 \begin{cfa} 2224 2256 MIN 2257 2225 2258 MAX 2259 2226 2260 PI 2227 2261 E … … 2229 2263 & 2230 2264 \begin{cfa} 2231 SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN 2232 SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX 2265 SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, 2266 FLT_MIN, DBL_MIN, LDBL_MIN 2267 SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, 2268 FLT_MAX, DBL_MAX, LDBL_MAX 2233 2269 M_PI, M_PIl 2234 2270 M_E, M_El … … 2245 2281 \begin{cquote} 2246 2282 \lstDeleteShortInline@% 2247 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2248 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\2283 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2284 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ 2249 2285 \begin{cfa} 2250 2286 float `log`( float x ); … … 2264 2300 \begin{cquote} 2265 2301 \lstDeleteShortInline@% 2266 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2267 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\2302 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2303 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 2268 2304 \begin{cfa} 2269 2305 log … … 2292 2328 \begin{cquote} 2293 2329 \lstDeleteShortInline@% 2294 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2295 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\2330 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2331 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{Definition}} & \multicolumn{1}{c}{\textbf{Usage}} \\ 2296 2332 \begin{cfa} 2297 2333 unsigned int `abs`( int ); … … 2311 2347 \begin{cquote} 2312 2348 \lstDeleteShortInline@% 2313 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2314 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\2349 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2350 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 2315 2351 \begin{cfa} 2316 2352 abs … … 2331 2367 The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety. 2332 2368 C/\Celeven provide a number of complex and overlapping storage-management operation to support the following capabilities: 2333 \begin{description} [topsep=3pt,itemsep=2pt,parsep=0pt]2369 \begin{description}%[topsep=3pt,itemsep=2pt,parsep=0pt] 2334 2370 \item[fill] 2335 2371 an allocation with a specified character. … … 2381 2417 \end{cfa} 2382 2418 \lstDeleteShortInline@% 2383 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2384 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\2419 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2420 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ 2385 2421 \begin{cfa} 2386 2422 ip = alloc(); … … 2403 2439 ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) ); 2404 2440 ip = (int *)realloc( ip, 2 * dim * sizeof( int ) ); 2405 ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) );2406 2441 ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); 2442 memset( ip, fill, 4 * dim * sizeof( int ) ); 2407 2443 ip = memalign( 16, sizeof( int ) ); 2408 2444 ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) ); … … 2441 2477 \begin{cquote} 2442 2478 \lstDeleteShortInline@% 2443 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}l@{}}2444 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{\CC}} \\2479 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 2480 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{\CC}} \\ 2445 2481 \begin{cfa} 2446 2482 int x = 1, y = 2, z = 3; … … 2525 2561 The \CFA interface wraps GMP functions into operator functions to make programming with multi-precision integers identical to using fixed-sized integers. 2526 2562 The \CFA type name for multi-precision signed-integers is @Int@ and the header file is @gmp@. 2527 The following multi-precision factorial programs contrast using GMP with the \CFA and C interfaces. 2528 \begin{cquote} 2563 Figure~\ref{f:GMPInterface} shows a multi-precision factorial-program contrasting the GMP interface in \CFA and C. 2564 2565 \begin{figure} 2566 \centering 2529 2567 \lstDeleteShortInline@% 2530 \begin{tabular}{@{}l@{\hspace{ \parindentlnth}}@{\hspace{\parindentlnth}}l@{}}2531 \multicolumn{1}{c@{\hspace{ \parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}} \\2568 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}@{\hspace{2\parindentlnth}}l@{}} 2569 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{2\parindentlnth}}c}{\textbf{C}} \\ 2532 2570 \begin{cfa} 2533 2571 #include <gmp> … … 2557 2595 \end{tabular} 2558 2596 \lstMakeShortInline@% 2559 \end{cquote} 2597 \caption{GMP Interface \CFA versus C} 2598 \label{f:GMPInterface} 2599 \end{figure} 2560 2600 2561 2601 … … 2566 2606 In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code. 2567 2607 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}). 2568 Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other thanin length and clarity of source code.2569 A more illustrative benchmarkmeasures the costs of idiomatic usage of each language's features.2570 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@ function similar to that in Section~\ref{sec:variadic-tuples}.2571 The benchmark test is similar for C and \CC.2572 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/2$ (to reduce graph height) constants.2608 Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code. 2609 A more illustrative comparison measures the costs of idiomatic usage of each language's features. 2610 Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list. 2611 The benchmark test is similar for the other languages. 2612 The experiment uses element types @int@ and @pair(short, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack. 2573 2613 2574 2614 \begin{figure} 2575 2615 \begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt] 2576 int main( int argc, char * argv[]) {2616 int main() { 2577 2617 int max = 0, val = 42; 2578 2618 stack( int ) si, ti; 2579 2619 2580 2620 REPEAT_TIMED( "push_int", N, push( si, val ); ) 2581 TIMED( "copy_int", ti = si; )2621 TIMED( "copy_int", ti{ si }; ) 2582 2622 TIMED( "clear_int", clear( si ); ) 2583 2623 REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; ) 2584 2624 2585 pair( _Bool, char ) max = { (_Bool)0, '\0' }, val = { (_Bool)1, 'a' };2586 stack( pair( _Bool, char ) ) sp, tp;2625 pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' }; 2626 stack( pair( short, char ) ) sp, tp; 2587 2627 2588 2628 REPEAT_TIMED( "push_pair", N, push( sp, val ); ) 2589 TIMED( "copy_pair", tp = sp; )2629 TIMED( "copy_pair", tp{ sp }; ) 2590 2630 TIMED( "clear_pair", clear( sp ); ) 2591 REPEAT_TIMED( "pop_pair", N, pair( _Bool, char) x = pop( tp ); if ( x > max ) max = x; )2631 REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); if ( x > max ) max = x; ) 2592 2632 } 2593 2633 \end{cfa} … … 2600 2640 hence runtime checks are necessary to safely down-cast objects. 2601 2641 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. 2602 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 negligible runtime impact. 2603 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. 2642 Note that the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically. 2604 2643 2605 2644 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. 2606 2645 The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted. 2607 All code is compiled at \texttt{-O2} by gcc or g++ 6. 2.0, with all \CC code compiled as \CCfourteen.2646 All code is compiled at \texttt{-O2} by gcc or g++ 6.3.0, with all \CC code compiled as \CCfourteen. 2608 2647 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. 2609 2648 … … 2622 2661 \begin{tabular}{rrrrr} 2623 2662 & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ \hline 2624 maximum memory usage (MB) & 10 001 & 2502 & 2503 & 11253\\2625 source code size (lines) & 247 & 222 & 165 & 339\\2626 redundant type annotations (lines) & 39 & 2 & 2 & 15\\2627 binary size (KB) & 14 & 2 29 & 18 & 38\\2663 maximum memory usage (MB) & 10,001 & 2,502 & 2,503 & 11,253 \\ 2664 source code size (lines) & 196 & 186 & 125 & 290 \\ 2665 redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ 2666 binary size (KB) & 14 & 257 & 14 & 37 \\ 2628 2667 \end{tabular} 2629 2668 \end{table} 2630 2669 2631 2670 The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types; 2632 this inefficiency is exacerbated by the second level of generic types in the pair -basedbenchmarks.2633 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, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.2671 this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. 2672 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @short@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead. 2634 2673 \CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@); 2635 There are two outliers in the graph for \CFA: all prints and pop of @pair@. 2636 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. 2637 A compiler designed for \CFA could easily perform these optimizations. 2674 The outlier in the graph for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code. 2675 The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA could easily perform these optimizations. 2638 2676 Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries. 2639 2677 2640 \CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 73 and 54 lines, respectively. 2678 \CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 39 and 42 lines, respectively. 2679 The difference between the \CFA and \CC line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA library would be similar in length to the \CC version. 2641 2680 On the other hand, C does not have a generic collections-library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers. 2642 \CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @ bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;2681 \CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @char@, @short@, and @int@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library; 2643 2682 with their omission, the \CCV line count is similar to C. 2644 2683 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. 2645 2684 2646 Raw line-count, however,is a fairly rough measure of code complexity;2647 another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.2648 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 pointer s 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@).2649 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.2685 Line-count is a fairly rough measure of code complexity; 2686 another important factor is how much type information the programmer must specify manually, especially where that information is not compiler-checked. 2687 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 pointer arguments and format codes, or \CCV, with its extensive use of untype-checked downcasts, \eg @object@ to @integer@ when popping a stack. 2688 To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression. 2650 2689 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. 2651 The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler). 2652 These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous. 2690 The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}. 2653 2691 2654 2692 … … 2658 2696 \subsection{Polymorphism} 2659 2697 2660 \CC is the most similar language to \CFA; 2661 both are extensions to C with source and runtime backwards compatibility. 2662 The fundamental difference is the engineering approach to maintain C compatibility and programmer expectation. 2663 While \CC provides good compatibility with C, it has a steep learning curve for many of its extensions. 2664 For example, polymorphism is provided via three disjoint mechanisms: overloading, inheritance, and templates. 2698 \CC provides three disjoint polymorphic extensions to C: overloading, inheritance, and templates. 2665 2699 The overloading is restricted because resolution does not use the return type, inheritance requires learning object-oriented programming and coping with a restricted nominal-inheritance hierarchy, templates cannot be separately compiled resulting in compilation/code bloat and poor error messages, and determining how these mechanisms interact and which to use is confusing. 2666 2700 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. … … 2717 2751 2718 2752 2753 \subsection{C Extensions} 2754 2755 \CC is the best known C-based language, and is similar to \CFA in that both are extensions to C with source and runtime backwards compatibility. 2756 Specific difference between \CFA and \CC have been identified in prior sections, with a final observation that \CFA has equal or fewer tokens to express the same notion in many cases. 2757 The key difference in design philosophies is that \CFA is easier for C programmers to understand by maintaining a procedural paradigm and avoiding complex interactions among extensions. 2758 \CC, on the other hand, has multiple overlapping features (such as the three forms of polymorphism), many of which have complex interactions with its object-oriented design. 2759 As a result, \CC has a steep learning curve for even experienced C programmers, especially when attempting to maintain performance equivalent to C legacy-code. 2760 2761 There are several other C extension-languages with less usage and even more dramatic changes than \CC. 2762 Objective-C and Cyclone are two other extensions to C with different design goals than \CFA, as discussed above. 2763 Other languages extend C with more focused features. 2764 $\mu$\CC~\cite{uC++book}, CUDA~\cite{Nickolls08}, ispc~\cite{Pharr12}, and Sierra~\cite{Leissa14} add concurrent or data-parallel primitives to C or \CC; 2765 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 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} 2719 2770 \subsection{Control Structures / Declarations / Literals} 2720 2771 … … 2734 2785 0/1 Literals \\ 2735 2786 user defined: D, Objective-C 2787 \end{comment} 2736 2788 2737 2789 … … 2748 2800 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 2749 2801 2750 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules.2751 (While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.) 2752 In addition, there areinteresting future directions for the polymorphism design.2802 There is ongoing work on a wide range of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules. 2803 While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these extensions. 2804 There are also interesting future directions for the polymorphism design. 2753 2805 Notably, \CC template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. 2754 2806 \CFA polymorphic functions use dynamic virtual-dispatch; … … 2761 2813 \section{Acknowledgments} 2762 2814 2763 The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, and Andrew Beach on the features described in this paper, and thank Magnus Madsen for feedback in the writing. 2764 This work is supported through a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada. 2765 2766 % 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. 2767 2768 2769 \bibliographystyle{plain} 2815 The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, Andrew Beach and Brice Dobry on the features described in this paper, and thank Magnus Madsen for feedback on the writing. 2816 This work is supported by a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada. 2817 2818 2770 2819 \bibliography{pl} 2771 2820 … … 2776 2825 \label{sec:BenchmarkStackImplementation} 2777 2826 2778 \lstset{basicstyle=\linespread{0.9}\sf\small} 2779 2780 Throughout, @/***/@ designates a counted redundant type annotation. 2827 Throughout, @/***/@ designates a counted redundant type annotation; code reformatted for brevity. 2781 2828 2782 2829 \smallskip\noindent 2830 C 2831 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2832 struct stack_node { 2833 void * value; 2834 struct stack_node * next; 2835 }; 2836 struct stack { struct stack_node* head; }; 2837 void clear_stack( struct stack * s, void (*free_el)( void * ) ) { 2838 for ( struct stack_node * next = s->head; next; ) { 2839 struct stack_node * crnt = next; 2840 next = crnt->next; 2841 free_el( crnt->value ); 2842 free( crnt ); 2843 } 2844 s->head = NULL; 2845 } 2846 struct stack new_stack() { return (struct stack){ NULL }; /***/ } 2847 void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) { 2848 struct stack_node ** crnt = &s->head; 2849 for ( struct stack_node * next = t->head; next; next = next->next ) { 2850 *crnt = malloc( sizeof(struct stack_node) ); /***/ 2851 (*crnt)->value = copy( next->value ); 2852 crnt = &(*crnt)->next; 2853 } 2854 *crnt = NULL; 2855 } 2856 struct stack * assign_stack( struct stack * s, const struct stack * t, 2857 void * (*copy_el)( const void * ), void (*free_el)( void * ) ) { 2858 if ( s->head == t->head ) return s; 2859 clear_stack( s, free_el ); /***/ 2860 copy_stack( s, t, copy_el ); /***/ 2861 return s; 2862 } 2863 _Bool stack_empty( const struct stack * s ) { return s->head == NULL; } 2864 void push_stack( struct stack * s, void * v ) { 2865 struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/ 2866 *n = (struct stack_node){ v, s->head }; /***/ 2867 s->head = n; 2868 } 2869 void * pop_stack( struct stack * s ) { 2870 struct stack_node * n = s->head; 2871 s->head = n->next; 2872 void * v = n->value; 2873 free( n ); 2874 return v; 2875 } 2876 \end{cfa} 2877 2878 \medskip\noindent 2783 2879 \CFA 2784 2880 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2785 forall( otype T ) struct stack_node;2786 forall( otype T ) struct stack {2787 stack_node(T) * head;2788 };2789 2881 forall( otype T ) struct stack_node { 2790 2882 T value; 2791 2883 stack_node(T) * next; 2792 2884 }; 2793 forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2794 forall( otype T) void ?{}( stack(T) & s, stack(T) t ) { 2885 forall( otype T ) struct stack { stack_node(T) * head; }; 2886 forall( otype T ) void clear( stack(T) & s ) with( s ) { 2887 for ( stack_node(T) * next = head; next; ) { 2888 stack_node(T) * crnt = next; 2889 next = crnt->next; 2890 ^(*crnt){}; 2891 free(crnt); 2892 } 2893 head = 0; 2894 } 2895 forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2896 forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) { 2795 2897 stack_node(T) ** crnt = &s.head; 2796 2898 for ( stack_node(T) * next = t.head; next; next = next->next ) { 2797 stack_node(T) * new_node = ((stack_node(T)*)malloc()); 2798 (*new_node){ next->value }; /***/ 2799 *crnt = new_node; 2800 stack_node(T) * acrnt = *crnt; 2801 crnt = &acrnt->next; 2899 *crnt = alloc(); 2900 ((*crnt)->value){ next->value }; 2901 crnt = &(*crnt)->next; 2802 2902 } 2803 2903 *crnt = 0; … … 2811 2911 forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); } 2812 2912 forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; } 2813 forall( otype T ) void push( stack(T) & s, T value ) {2814 stack_node(T) * n ew_node = ((stack_node(T)*)malloc());2815 (*n ew_node){ value, s.head }; /***/2816 s.head = new_node;2817 } 2818 forall( otype T ) T pop( stack(T) & s ) {2819 stack_node(T) * n = s.head;2820 s.head = n->next;2913 forall( otype T ) void push( stack(T) & s, T value ) with( s ) { 2914 stack_node(T) * n = alloc(); 2915 (*n){ value, head }; 2916 head = n; 2917 } 2918 forall( otype T ) T pop( stack(T) & s ) with( s ) { 2919 stack_node(T) * n = head; 2920 head = n->next; 2821 2921 T v = n->value; 2822 delete( n ); 2922 ^(*n){}; 2923 free( n ); 2823 2924 return v; 2824 2925 } 2825 forall( otype T ) void clear( stack(T) & s ) { 2826 for ( stack_node(T) * next = s.head; next; ) { 2827 stack_node(T) * crnt = next; 2828 next = crnt->next; 2829 delete( crnt ); 2926 \end{cfa} 2927 2928 \begin{comment} 2929 forall( otype T ) { 2930 struct stack_node { 2931 T value; 2932 stack_node(T) * next; 2933 }; 2934 struct stack { stack_node(T) * head; }; 2935 void clear( stack(T) & s ) with( s ) { 2936 for ( stack_node(T) * next = head; next; ) { 2937 stack_node(T) * crnt = next; 2938 next = crnt->next; 2939 ^(*crnt){}; 2940 free(crnt); 2941 } 2942 head = 0; 2830 2943 } 2831 s.head = 0; 2832 } 2833 \end{cfa} 2944 void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2945 void ?{}( stack(T) & s, stack(T) t ) { 2946 stack_node(T) ** crnt = &s.head; 2947 for ( stack_node(T) * next = t.head; next; next = next->next ) { 2948 *crnt = alloc(); 2949 ((*crnt)->value){ next->value }; 2950 crnt = &(*crnt)->next; 2951 } 2952 *crnt = 0; 2953 } 2954 stack(T) ?=?( stack(T) & s, stack(T) t ) { 2955 if ( s.head == t.head ) return s; 2956 clear( s ); 2957 s{ t }; 2958 return s; 2959 } 2960 void ^?{}( stack(T) & s) { clear( s ); } 2961 _Bool empty( const stack(T) & s ) { return s.head == 0; } 2962 void push( stack(T) & s, T value ) with( s ) { 2963 stack_node(T) * n = alloc(); 2964 (*n){ value, head }; 2965 head = n; 2966 } 2967 T pop( stack(T) & s ) with( s ) { 2968 stack_node(T) * n = head; 2969 head = n->next; 2970 T v = n->value; 2971 ^(*n){}; 2972 free( n ); 2973 return v; 2974 } 2975 } 2976 \end{comment} 2834 2977 2835 2978 \medskip\noindent 2836 2979 \CC 2837 2980 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2838 template<typename T> classstack {2981 template<typename T> struct stack { 2839 2982 struct node { 2840 2983 T value; 2841 2984 node * next; 2842 node( const T & v, node * n = nullptr ) : value( v), next(n) {}2985 node( const T & v, node * n = nullptr ) : value( v ), next( n ) {} 2843 2986 }; 2844 2987 node * head; 2845 void copy(const stack<T>& o) { 2846 node ** crnt = &head; 2847 for ( node * next = o.head;; next; next = next->next ) { 2848 *crnt = new node{ next->value }; /***/ 2849 crnt = &(*crnt)->next; 2850 } 2851 *crnt = nullptr; 2852 } 2853 public: 2854 stack() : head(nullptr) {} 2855 stack(const stack<T>& o) { copy(o); } 2856 stack(stack<T> && o) : head(o.head) { o.head = nullptr; } 2857 ~stack() { clear(); } 2858 stack & operator= (const stack<T>& o) { 2859 if ( this == &o ) return *this; 2860 clear(); 2861 copy(o); 2862 return *this; 2863 } 2864 stack & operator= (stack<T> && o) { 2865 if ( this == &o ) return *this; 2866 head = o.head; 2867 o.head = nullptr; 2868 return *this; 2869 } 2870 bool empty() const { return head == nullptr; } 2871 void push(const T & value) { head = new node{ value, head }; /***/ } 2872 T pop() { 2873 node * n = head; 2874 head = n->next; 2875 T x = std::move(n->value); 2876 delete n; 2877 return x; 2878 } 2988 stack() : head( nullptr ) {} 2989 stack( const stack<T> & o ) { copy( o ); } 2879 2990 void clear() { 2880 2991 for ( node * next = head; next; ) { … … 2885 2996 head = nullptr; 2886 2997 } 2998 void copy( const stack<T> & o ) { 2999 node ** crnt = &head; 3000 for ( node * next = o.head; next; next = next->next ) { 3001 *crnt = new node{ next->value }; /***/ 3002 crnt = &(*crnt)->next; 3003 } 3004 *crnt = nullptr; 3005 } 3006 ~stack() { clear(); } 3007 stack & operator= ( const stack<T> & o ) { 3008 if ( this == &o ) return *this; 3009 clear(); 3010 copy( o ); 3011 return *this; 3012 } 3013 bool empty() const { return head == nullptr; } 3014 void push( const T & value ) { head = new node{ value, head }; /***/ } 3015 T pop() { 3016 node * n = head; 3017 head = n->next; 3018 T v = std::move( n->value ); 3019 delete n; 3020 return v; 3021 } 2887 3022 }; 2888 \end{cfa}2889 2890 \medskip\noindent2891 C2892 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]2893 struct stack_node {2894 void * value;2895 struct stack_node * next;2896 };2897 struct stack new_stack() { return (struct stack){ NULL }; /***/ }2898 void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {2899 struct stack_node ** crnt = &s->head;2900 for ( struct stack_node * next = t->head; next; next = next->next ) {2901 *crnt = malloc(sizeof(struct stack_node)); /***/2902 **crnt = (struct stack_node){ copy(next->value) }; /***/2903 crnt = &(*crnt)->next;2904 }2905 *crnt = 0;2906 }2907 _Bool stack_empty(const struct stack * s) { return s->head == NULL; }2908 void push_stack(struct stack * s, void * value) {2909 struct stack_node * n = malloc(sizeof(struct stack_node)); /***/2910 *n = (struct stack_node){ value, s->head }; /***/2911 s->head = n;2912 }2913 void * pop_stack(struct stack * s) {2914 struct stack_node * n = s->head;2915 s->head = n->next;2916 void * x = n->value;2917 free(n);2918 return x;2919 }2920 void clear_stack(struct stack * s, void (*free_el)(void *)) {2921 for ( struct stack_node * next = s->head; next; ) {2922 struct stack_node * crnt = next;2923 next = crnt->next;2924 free_el(crnt->value);2925 free(crnt);2926 }2927 s->head = NULL;2928 }2929 3023 \end{cfa} 2930 3024 … … 2932 3026 \CCV 2933 3027 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2934 stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {} 2935 void stack::copy(const stack & o) { 2936 node ** crnt = &head; 2937 for ( node * next = o.head; next; next = next->next ) { 2938 *crnt = new node{ *next->value }; 2939 crnt = &(*crnt)->next; 3028 struct stack { 3029 struct node { 3030 ptr<object> value; 3031 node * next; 3032 node( const object & v, node * n = nullptr ) : value( v.new_copy() ), next( n ) {} 3033 }; 3034 node * head; 3035 void clear() { 3036 for ( node * next = head; next; ) { 3037 node * crnt = next; 3038 next = crnt->next; 3039 delete crnt; 3040 } 3041 head = nullptr; 2940 3042 } 2941 *crnt = nullptr; 2942 } 2943 stack::stack() : head(nullptr) {} 2944 stack::stack(const stack & o) { copy(o); } 2945 stack::stack(stack && o) : head(o.head) { o.head = nullptr; } 2946 stack::~stack() { clear(); } 2947 stack & stack::operator= (const stack & o) { 2948 if ( this == &o ) return *this; 2949 clear(); 2950 copy(o); 2951 return *this; 2952 } 2953 stack & stack::operator= (stack && o) { 2954 if ( this == &o ) return *this; 2955 head = o.head; 2956 o.head = nullptr; 2957 return *this; 2958 } 2959 bool stack::empty() const { return head == nullptr; } 2960 void stack::push(const object & value) { head = new node{ value, head }; /***/ } 2961 ptr<object> stack::pop() { 2962 node * n = head; 2963 head = n->next; 2964 ptr<object> x = std::move(n->value); 2965 delete n; 2966 return x; 2967 } 2968 void stack::clear() { 2969 for ( node * next = head; next; ) { 2970 node * crnt = next; 2971 next = crnt->next; 2972 delete crnt; 3043 void copy( const stack & o ) { 3044 node ** crnt = &head; 3045 for ( node * next = o.head; next; next = next->next ) { 3046 *crnt = new node{ *next->value }; /***/ 3047 crnt = &(*crnt)->next; 3048 } 3049 *crnt = nullptr; 2973 3050 } 2974 head = nullptr; 2975 } 3051 stack() : head( nullptr ) {} 3052 stack( const stack & o ) { copy( o ); } 3053 ~stack() { clear(); } 3054 stack & operator= ( const stack & o ) { 3055 if ( this == &o ) return *this; 3056 clear(); 3057 copy( o ); 3058 return *this; 3059 } 3060 bool empty() const { return head == nullptr; } 3061 void push( const object & value ) { head = new node{ value, head }; /***/ } 3062 ptr<object> pop() { 3063 node * n = head; 3064 head = n->next; 3065 ptr<object> v = std::move( n->value ); 3066 delete n; 3067 return v; 3068 } 3069 }; 2976 3070 \end{cfa} 2977 3071
Note:
See TracChangeset
for help on using the changeset viewer.