Changeset b067d9b for doc/papers/general/Paper.tex
- Timestamp:
- Oct 29, 2019, 4:01:24 PM (6 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 773db65, 9421f3d8
- Parents:
- 7951100 (diff), 8364209 (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
-
doc/papers/general/Paper.tex (modified) (124 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Paper.tex
r7951100 rb067d9b 1 1 \documentclass[AMA,STIX1COL]{WileyNJD-v2} 2 \setlength\typewidth{170mm} 3 \setlength\textwidth{170mm} 2 4 3 5 \articletype{RESEARCH ARTICLE}% 4 6 5 \received{26 April 2016} 6 \revised{6 June 2016} 7 \accepted{6 June 2016} 8 7 \received{12 March 2018} 8 \revised{8 May 2018} 9 \accepted{28 June 2018} 10 11 \setlength\typewidth{168mm} 12 \setlength\textwidth{168mm} 9 13 \raggedbottom 10 14 … … 187 191 } 188 192 189 \title{\texorpdfstring{\protect\CFA : Adding Modern Programming Language Features to C}{Cforall : Adding Modern Programming Language Features to C}}193 \title{\texorpdfstring{\protect\CFA : Adding modern programming language features to C}{Cforall : Adding modern programming language features to C}} 190 194 191 195 \author[1]{Aaron Moss} 192 196 \author[1]{Robert Schluntz} 193 \author[1]{Peter A. Buhr *}197 \author[1]{Peter A. Buhr} 194 198 \authormark{MOSS \textsc{et al}} 195 199 196 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, O N}, \country{Canada}}}197 198 \corres{ *Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON,N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}}200 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, Ontario}, \country{Canada}}} 201 202 \corres{Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}} 199 203 200 204 \fundingInfo{Natural Sciences and Engineering Research Council of Canada} 201 205 202 206 \abstract[Summary]{ 203 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating-systems. 204 This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. 205 Nevertheless, C, first standardized almost forty years ago, lacks many features that make programming in more modern languages safer and more productive. 206 207 The goal of the \CFA project (pronounced ``C-for-all'') is to create an extension of C that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. 208 Prior projects have attempted similar goals but failed to honour C programming-style; 209 for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. 210 Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and programmers. 211 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. 212 Finally, experimental results are presented to validate several of the new features. 207 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems. 208 This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more. 209 Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive. 210 The goal of the \CFA project (pronounced ``C for all'') is to create an extension of C that provides modern safety and productivity features while still ensuring strong backward compatibility with C and its programmers. 211 Prior projects have attempted similar goals but failed to honor the C programming style; 212 for instance, adding object-oriented or functional programming with garbage collection is a nonstarter for many C developers. 213 Specifically, \CFA is designed to have an orthogonal feature set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and programmers. 214 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. 215 Experimental results are presented to validate several of the new features. 213 216 }% 214 217 215 \keywords{ generic types, tuple types, variadic types, polymorphic functions, C, Cforall}218 \keywords{C, Cforall, generic types, polymorphic functions, tuple types, variadic types} 216 219 217 220 218 221 \begin{document} 219 \linenumbers % comment out to turn off line numbering222 %\linenumbers % comment out to turn off line numbering 220 223 221 224 \maketitle 222 225 223 226 227 \vspace*{-10pt} 224 228 \section{Introduction} 225 229 226 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating -systems.227 This installation base and the programmers producing it represent a massive software -engineering investment spanning decades and likely to continue for decades more.228 The TIOBE ~\cite{TIOBE} ranks the top 5 most \emph{popular} programming languages as: Java 15\%, \Textbf{C 12\%}, \Textbf{\CC 5.5\%},Python 5\%, \Csharp 4.5\% = 42\%, where the next 50 languages are less than 4\% each with a long tail.229 The top 3 rankings over the past 30 years are:230 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems. 231 This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more. 232 The TIOBE index~\cite{TIOBE} ranks the top five most \emph{popular} programming languages as Java 15\%, \Textbf{C 12\%}, \Textbf{\CC 5.5\%}, and Python 5\%, \Csharp 4.5\% = 42\%, where the next 50 languages are less than 4\% each with a long tail. 233 The top three rankings over the past 30 years are as follows. 230 234 \begin{center} 231 235 \setlength{\tabcolsep}{10pt} 232 \lstDeleteShortInline@% 233 \begin{tabular}{@{}rccccccc@{}} 234 & 2018 & 2013 & 2008 & 2003 & 1998 & 1993 & 1988 \\ \hline 235 Java & 1 & 2 & 1 & 1 & 18 & - & - \\ 236 \fontsize{9bp}{11bp}\selectfont 237 \lstDeleteShortInline@% 238 \begin{tabular}{@{}cccccccc@{}} 239 & 2018 & 2013 & 2008 & 2003 & 1998 & 1993 & 1988 \\ 240 Java & 1 & 2 & 1 & 1 & 18 & -- & -- \\ 236 241 \Textbf{C}& \Textbf{2} & \Textbf{1} & \Textbf{2} & \Textbf{2} & \Textbf{1} & \Textbf{1} & \Textbf{1} \\ 237 242 \CC & 3 & 4 & 3 & 3 & 2 & 2 & 5 \\ … … 241 246 Love it or hate it, C is extremely popular, highly used, and one of the few systems languages. 242 247 In many cases, \CC is often used solely as a better C. 243 Nevertheless, C, first standardized almost fortyyears ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive.244 245 \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 source and runtime compatibility in the familiar C programming model.246 The four key design goals for \CFA~\cite{Bilson03} are :247 (1) The behaviour of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler;248 (2) Standard C code must be as fast and as small when translated by a \CFA compiler as when translated by a C compiler;249 (3) \CFA code must be at least as portable as standard C code;250 (4) Extensions introduced by \CFA must be translated in the most efficient way possible.251 These goals ensure existing C code-bases can be convertedto \CFA incrementally with minimal effort, and C programmers can productively generate \CFA code without training beyond the features being used.252 \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.253 254 All language sfeatures discussed in this paper are working, except some advanced exception-handling features.255 Not discussed in this paper are the integrated concurrency -constructs and user-level threading-library~\cite{Delisle18}.248 Nevertheless, C, which was first standardized almost 30 years ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive. 249 250 \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 source and runtime compatibility in the familiar C programming model. 251 The four key design goals for \CFA~\cite{Bilson03} are as follows: 252 (1) the behavior of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler; 253 (2) the standard C code must be as fast and as small when translated by a \CFA compiler as when translated by a C compiler; 254 (3) the \CFA code must be at least as portable as standard C code; 255 (4) extensions introduced by \CFA must be translated in the most efficient way possible. 256 These goals ensure that the existing C code bases can be converted into \CFA incrementally with minimal effort, and C programmers can productively generate \CFA code without training beyond the features being used. 257 \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. 258 259 All language features discussed in this paper are working, except some advanced exception-handling features. 260 Not discussed in this paper are the integrated concurrency constructs and user-level threading library~\cite{Delisle18}. 256 261 \CFA is an \emph{open-source} project 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). 257 Ultimately, a compiler is necessary for advanced features and optimal performance.258 262 % @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 259 263 % ------------------------------------------------------------------------------- … … 270 274 % SUM: 223 8203 8263 46479 271 275 % ------------------------------------------------------------------------------- 272 The \CFA translator is 200+ files and 46,000+ lines of code written in C/\CC. 273 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. 274 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. 275 At the heart of the translator is the type resolver, which handles the polymorphic function/type overload-resolution. 276 The \CFA translator is 200+ files and 46\,000+ lines of code written in C/\CC. 277 A translator versus a compiler makes it easier and faster to generate and debug the C object code rather than the intermediate, assembler, or machine code; 278 ultimately, a compiler is necessary for advanced features and optimal performance. 279 % 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. 280 Two key translator components are expression analysis, determining expression validity and what operations are required for its implementation, and code generation, dealing with multiple forms of overloading, polymorphism, and multiple return values by converting them into the C code for a C compiler that supports none of these features. 281 Details of these components are available in chapters 2 and 3 in the work of Bilson~\cite{Bilson03} and form the base for the current \CFA translator. 276 282 % @plg2[8]% cd cfa-cc/src; cloc libcfa 277 283 % ------------------------------------------------------------------------------- … … 288 294 % SUM: 100 1895 2785 11763 289 295 % ------------------------------------------------------------------------------- 290 The \CFA runtime system is 100+ files and 11 ,000+ lines of code, written in \CFA.296 The \CFA runtime system is 100+ files and 11\,000+ lines of code, written in \CFA. 291 297 Currently, the \CFA runtime is the largest \emph{user} of \CFA providing a vehicle to test the language features and implementation. 292 298 % @plg2[6]% cd cfa-cc/src; cloc tests examples benchmark … … 305 311 % SUM: 290 13175 3400 27776 306 312 % ------------------------------------------------------------------------------- 307 The \CFA tests are 290+ files and 27,000+ lines of code. 308 The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks. 309 The tests check for correctness and are used for daily regression testing of 3800+ commits. 310 311 Finally, it is impossible to describe a programming language without usages before definitions. 312 Therefore, syntax and semantics appear before explanations, and related work (Section~\ref{s:RelatedWork}) is deferred until \CFA is presented; 313 hence, patience is necessary until details are discussed. 314 315 313 % The \CFA tests are 290+ files and 27,000+ lines of code. 314 % The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks. 315 % The tests check for correctness and are used for daily regression testing of 3800+ commits. 316 317 Finally, it is impossible to describe a programming language without usage before definition. 318 Therefore, syntax and semantics appear before explanations; 319 hence, patience is necessary until sufficient details are presented and discussed. 320 Similarly, a detailed comparison with other programming languages is postponed until Section~\ref{s:RelatedWork}. 321 322 323 \vspace*{-6pt} 316 324 \section{Polymorphic Functions} 317 325 318 \CFA introduces both ad -hoc and parametric polymorphism to C, with a design originally formalized by Ditchfield~\cite{Ditchfield92},and first implemented by Bilson~\cite{Bilson03}.319 Shortcomings are identified in existing approaches to generic and variadic data types in C-like languages and how these shortcomings are avoided in \CFA.320 Specifically, the solution is both reusable and type -checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions.326 \CFA introduces both ad hoc and parametric polymorphism to C, with a design originally formalized by Ditchfield~\cite{Ditchfield92} and first implemented by Bilson~\cite{Bilson03}. 327 Shortcomings are identified in the existing approaches to generic and variadic data types in C-like languages and how these shortcomings are avoided in \CFA. 328 Specifically, the solution is both reusable and type checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions. 321 329 The new constructs are empirically compared with C and \CC approaches via performance experiments in Section~\ref{sec:eval}. 322 330 323 331 324 \subsection{Name Overloading} 332 \vspace*{-6pt} 333 \subsection{Name overloading} 325 334 \label{s:NameOverloading} 326 335 327 336 \begin{quote} 328 There are only two hard things in Computer Science: cache invalidation and \emph{naming things} --Phil Karlton337 ``There are only two hard things in Computer Science: cache invalidation and \emph{naming things}.''---Phil Karlton 329 338 \end{quote} 330 339 \vspace{-9pt} 331 C already has a limited form of ad -hoc polymorphism in its basic arithmetic operators, which apply to a variety of different types using identical syntax.340 C already has a limited form of ad hoc polymorphism in its basic arithmetic operators, which apply to a variety of different types using identical syntax. 332 341 \CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; 333 342 Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C. 334 343 Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads. 335 As an example: 344 345 \newpage 336 346 \begin{cfa} 337 347 int max = 2147483647; $\C[4in]{// (1)}$ … … 339 349 int max( int a, int b ) { return a < b ? b : a; } $\C{// (3)}$ 340 350 double max( double a, double b ) { return a < b ? b : a; } $\C{// (4)}\CRT$ 341 max( 7, -max ); $\C {// uses (3) and (1), by matching int from constant 7}$351 max( 7, -max ); $\C[3in]{// uses (3) and (1), by matching int from constant 7}$ 342 352 max( max, 3.14 ); $\C{// uses (4) and (2), by matching double from constant 3.14}$ 343 353 max( max, -max ); $\C{// ERROR, ambiguous}$ 344 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type} $354 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}\CRT$ 345 355 \end{cfa} 346 356 … … 348 358 In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction. 349 359 In the above, the name @max@ has a consistent meaning, and a programmer only needs to remember the single concept: maximum. 350 To prevent significant ambiguities, \CFA uses the return type in selecting overloads, \eg in the assignment to @m@, the compiler use @m@'s type to unambiguously select the most appropriate call to function @max@ (as does Ada).360 To prevent significant ambiguities, \CFA uses the return type in selecting overloads, \eg in the assignment to @m@, the compiler uses @m@'s type to unambiguously select the most appropriate call to function @max@ (as does Ada). 351 361 As is shown later, there are a number of situations where \CFA takes advantage of available type information to disambiguate, where other programming languages generate ambiguities. 352 362 353 \Celeven added @_Generic@ expressions ~\cite[\S~6.5.1.1]{C11}, which is used with preprocessor macros to provide ad-hoc polymorphism;363 \Celeven added @_Generic@ expressions (see section~6.5.1.1 of the ISO/IEC 9899~\cite{C11}), which is used with preprocessor macros to provide ad hoc polymorphism; 354 364 however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading. 355 The macro wrapping the generic expression imposes some limitations; 356 \eg, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@. 365 The macro wrapping the generic expression imposes some limitations, for instance, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@. 357 366 Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the dispatch functions, which must all have distinct names. 358 \CFA supports @_Generic@ expressions for backward s compatibility, but it is an unnecessary mechanism. \TODO{actually implement that}367 \CFA supports @_Generic@ expressions for backward compatibility, but it is an unnecessary mechanism. 359 368 360 369 % http://fanf.livejournal.com/144696.html … … 363 372 364 373 365 \subsection{\texorpdfstring{\protect\lstinline{forall} Functions}{forall Functions}} 374 \vspace*{-10pt} 375 \subsection{\texorpdfstring{\protect\lstinline{forall} functions}{forall functions}} 366 376 \label{sec:poly-fns} 367 377 368 The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name) :378 The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name). 369 379 \begin{cfa} 370 380 `forall( otype T )` T identity( T val ) { return val; } … … 373 383 This @identity@ function can be applied to any complete \newterm{object type} (or @otype@). 374 384 The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type. 375 The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor.376 If this extra information is not needed, \egfor a pointer, the type parameter can be declared as a \newterm{data type} (or @dtype@).377 378 In \CFA, the polymorphic runtime -cost is spread over each polymorphic call, because more arguments are passed to polymorphic functions;379 the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual -function calls.380 A design advantage is that, unlike \CC template -functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.381 382 Since bare polymorphic -types provide a restricted set of available operations, \CFA provides a \newterm{type assertion}~\cite[pp.~37-44]{Alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.383 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading :385 The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor, and destructor. 386 If this extra information is not needed, for instance, for a pointer, the type parameter can be declared as a \newterm{data type} (or @dtype@). 387 388 In \CFA, the polymorphic runtime cost is spread over each polymorphic call, because more arguments are passed to polymorphic functions; 389 the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual function calls. 390 A design advantage is that, unlike \CC template functions, \CFA polymorphic functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat. 391 392 Since bare polymorphic types provide a restricted set of available operations, \CFA provides a \newterm{type assertion}~\cite[pp.~37-44]{Alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type variable. 393 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading. 384 394 \begin{cfa} 385 395 forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; } $\C{// ? denotes operands}$ 386 396 int val = twice( twice( 3.7 ) ); $\C{// val == 14}$ 387 397 \end{cfa} 388 which works for any type @T@ with a matching addition operator. 389 The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@. 390 There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada} in its type analysis. 391 The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an early conversion to @int@. 392 \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. 398 This works for any type @T@ with a matching addition operator. 399 The polymorphism is achieved by creating a wrapper function for calling @+@ with the @T@ bound to @double@ and then passing this function to the first call of @twice@. 400 There is now the option of using the same @twice@ and converting the result into @int@ on assignment or creating another @twice@ with the type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada} in its type analysis. 401 The first approach has a late conversion from @double@ to @int@ on the final assignment, whereas the second has an early conversion to @int@. 402 \CFA minimizes the number of conversions and their potential to lose information; 403 hence, it selects the first approach, which corresponds with C programmer intuition. 393 404 394 405 Crucial to the design of a new programming language are the libraries to access thousands of external software features. 395 Like \CC, \CFA inherits a massive compatible library -base, where other programming languages must rewrite or provide fragile inter-language communication with C.396 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array :406 Like \CC, \CFA inherits a massive compatible library base, where other programming languages must rewrite or provide fragile interlanguage communication with C. 407 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array. 397 408 \begin{cfa} 398 409 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, … … 404 415 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$ 405 416 \end{cfa} 406 which can be augmented simply with generalized, type-safe, \CFA-overloaded wrappers: 417 This can be augmented simply with generalized, type-safe, \CFA-overloaded wrappers. 407 418 \begin{cfa} 408 419 forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) { … … 418 429 \end{cfa} 419 430 The nested function @comp@ provides the hidden interface from typed \CFA to untyped (@void *@) C, plus the cast of the result. 420 Providing a hidden @comp@ function in \CC is awkward as lambdas do not use C calling-conventions and template declarations cannot appear at block scope. 421 As well, an alternate kind of return is made available: position versus pointer to found element. 422 \CC's type-system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a template @bsearch@. 431 % FIX 432 Providing a hidden @comp@ function in \CC is awkward as lambdas do not use C calling conventions and template declarations cannot appear in block scope. 433 In addition, an alternate kind of return is made available: position versus pointer to found element. 434 \CC's type system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a template @bsearch@. 423 435 424 436 \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}). … … 430 442 \end{cfa} 431 443 432 Call -site inferencing and nested functions provide a localized form of inheritance.444 Call site inferencing and nested functions provide a localized form of inheritance. 433 445 For example, the \CFA @qsort@ only sorts in ascending order using @<@. 434 However, it is trivial to locally change this behavio ur:446 However, it is trivial to locally change this behavior. 435 447 \begin{cfa} 436 448 forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ } 437 449 int main() { 438 int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behavio ur}$450 int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behavior}$ 439 451 qsort( vals, 10 ); $\C{// descending sort}$ 440 452 } 441 453 \end{cfa} 442 454 The local version of @?<?@ performs @?>?@ overriding the built-in @?<?@ so it is passed to @qsort@. 443 Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.444 445 To reduce duplication, it is possible to distribute a group of @forall@ (and storage-class qualifiers) over functions/types, s o each block declaration is prefixed by the group (see example in Appendix~\ref{s:CforallStack}).455 Therefore, programmers can easily form local environments, adding and modifying appropriate functions, to maximize the reuse of other existing functions and types. 456 457 To reduce duplication, it is possible to distribute a group of @forall@ (and storage-class qualifiers) over functions/types, such that each block declaration is prefixed by the group (see the example in Appendix~\ref{s:CforallStack}). 446 458 \begin{cfa} 447 459 forall( otype `T` ) { $\C{// distribution block, add forall qualifier to declarations}$ … … 454 466 455 467 456 \vspace*{-2pt}457 468 \subsection{Traits} 458 469 459 \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: 460 470 \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. 461 471 \begin{cquote} 462 472 \lstDeleteShortInline@% … … 485 495 \end{cquote} 486 496 487 Note ,the @sumable@ trait does not include a copy constructor needed for the right side of @?+=?@ and return;488 it is provided by @otype@, which is syntactic sugar for the following trait :497 Note that the @sumable@ trait does not include a copy constructor needed for the right side of @?+=?@ and return; 498 it is provided by @otype@, which is syntactic sugar for the following trait. 489 499 \begin{cfa} 490 500 trait otype( dtype T | sized(T) ) { // sized is a pseudo-trait for types with known size and alignment … … 495 505 }; 496 506 \end{cfa} 497 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.498 499 In summation, the \CFA type -system uses \newterm{nominal typing} for concrete types, matching with the C type-system, and \newterm{structural typing} for polymorphic types.507 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. 508 509 In summation, the \CFA type system uses \newterm{nominal typing} for concrete types, matching with the C type system, and \newterm{structural typing} for polymorphic types. 500 510 Hence, trait names play no part in type equivalence; 501 511 the names are simply macros for a list of polymorphic assertions, which are expanded at usage sites. 502 Nevertheless, trait names form a logical subtype -hierarchy with @dtype@ at the top, where traits often contain overlapping assertions, \eg operator @+@.503 Traits are used like interfaces in Java or abstract base -classes in \CC, but without the nominal inheritance-relationships.504 Instead, each polymorphic function (or generic type) defines the structural type needed for its execution (polymorphic type -key), and this key is fulfilled at each call site from the lexical environment, which is similar toGo~\cite{Go} interfaces.505 Hence, new lexical scopes and nested functions are used extensively to create local subtypes, as in the @qsort@ example, without having to manage a nominal -inheritance hierarchy.512 Nevertheless, trait names form a logical subtype hierarchy with @dtype@ at the top, where traits often contain overlapping assertions, \eg operator @+@. 513 Traits are used like interfaces in Java or abstract base classes in \CC, but without the nominal inheritance relationships. 514 Instead, each polymorphic function (or generic type) defines the structural type needed for its execution (polymorphic type key), and this key is fulfilled at each call site from the lexical environment, which is similar to the Go~\cite{Go} interfaces. 515 Hence, new lexical scopes and nested functions are used extensively to create local subtypes, as in the @qsort@ example, without having to manage a nominal inheritance hierarchy. 506 516 % (Nominal inheritance can be approximated with traits using marker variables or functions, as is done in Go.) 507 517 … … 534 544 535 545 A significant shortcoming of standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms. 536 Broadly speaking, there are three approaches to implement abstract data -structures in C.537 One approach is to write bespoke data -structures for each context in which they are needed.538 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.539 A second approach is to use @void *@-based polymorphism, \eg the C standard -library functions @bsearch@ and @qsort@, which allowreuse of code with common functionality.540 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 otherwiseneeded.541 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.546 Broadly speaking, there are three approaches to implement abstract data structures in C. 547 One approach is to write bespoke data structures for each context in which they are needed. 548 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. 549 A second approach is to use @void *@-based polymorphism, \eg the C standard library functions @bsearch@ and @qsort@, which allow for the reuse of code with common functionality. 550 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 otherwise not needed. 551 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. 542 552 Furthermore, writing and using preprocessor macros is unnatural and inflexible. 543 553 544 \CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data -types.545 \CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backward scompatibility with C and providing separate compilation.554 \CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data types. 555 \CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backward compatibility with C and providing separate compilation. 546 556 However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates. 547 557 548 A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration , and instantiated using a parenthesized list of types after the type name:558 A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration and instantiated using a parenthesized list of types after the type name. 549 559 \begin{cquote} 550 560 \lstDeleteShortInline@% … … 574 584 575 585 \CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}. 576 Concrete types have a fixed memory layout regardless of type parameters, wh iledynamic types vary in memory layout depending on their type parameters.586 Concrete types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on their type parameters. 577 587 A \newterm{dtype-static} type has polymorphic parameters but is still concrete. 578 588 Polymorphic pointers are an example of dtype-static types; 579 given some type variable @T@, @T@ is a polymorphic type, as is @T *@, but @T *@ has a fixed size and can thereforebe represented by @void *@ in code generation.580 581 \CFA generic types also allow checked argument -constraints.582 For example, the following declaration of a sorted set -type ensures the set key supports equality and relational comparison:589 given some type variable @T@, @T@ is a polymorphic type, as is @T *@, but @T *@ has a fixed size and can, therefore, be represented by @void *@ in code generation. 590 591 \CFA generic types also allow checked argument constraints. 592 For example, the following declaration of a sorted set type ensures the set key supports equality and relational comparison. 583 593 \begin{cfa} 584 594 forall( otype Key | { _Bool ?==?(Key, Key); _Bool ?<?(Key, Key); } ) struct sorted_set; … … 586 596 587 597 588 \subsection{Concrete Generic-Types}589 590 The \CFA translator template -expands concrete generic-types into new structure types, affording maximal inlining.591 To enable inter -operation among equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate.592 A function declaration that accepts or returns a concrete generic -type produces a declaration for the instantiated structure in the same scope, which all callers may reuse.593 For example, the concrete instantiation for @pair( const char *, int )@ is :598 \subsection{Concrete generic types} 599 600 The \CFA translator template expands concrete generic types into new structure types, affording maximal inlining. 601 To enable interoperation among equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate. 602 A function declaration that accepts or returns a concrete generic type produces a declaration for the instantiated structure in the same scope, which all callers may reuse. 603 For example, the concrete instantiation for @pair( const char *, int )@ is 594 604 \begin{cfa} 595 605 struct _pair_conc0 { … … 598 608 \end{cfa} 599 609 600 A concrete generic -type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.601 In the above example, the @pair( F *, T * )@ parameter to @value@ is such a type; its expansion is below and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:610 A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations. 611 In the above example, the @pair( F *, T * )@ parameter to @value@ is such a type; its expansion is below, and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate. 602 612 \begin{cfa} 603 613 struct _pair_conc1 { … … 607 617 608 618 609 \subsection{Dynamic Generic-Types} 610 611 Though \CFA implements concrete generic-types efficiently, it also has a fully general system for dynamic generic types. 612 As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. 613 Dynamic generic-types also have an \newterm{offset array} containing structure-member offsets. 614 A dynamic generic-@union@ needs no such offset array, as all members are at offset 0, but size and alignment are still necessary. 615 Access to members of a dynamic structure is provided at runtime via base-displacement addressing with the structure pointer and the member offset (similar to the @offsetof@ macro), moving a compile-time offset calculation to runtime. 619 \subsection{Dynamic generic types} 620 621 Though \CFA implements concrete generic types efficiently, it also has a fully general system for dynamic generic types. 622 As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact, all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. 623 Dynamic generic types also have an \newterm{offset array} containing structure-member offsets. 624 A dynamic generic @union@ needs no such offset array, as all members are at offset 0, but size and alignment are still necessary. 625 Access to members of a dynamic structure is provided at runtime via base displacement addressing 626 % FIX 627 using the structure pointer and the member offset (similar to the @offsetof@ macro), moving a compile-time offset calculation to runtime. 616 628 617 629 The offset arrays are statically generated where possible. 618 If a dynamic generic -type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume the generic type is complete (\ie has a known layout) at any call-site, and the offset array is passed from the caller;630 If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume that the generic type is complete (\ie has a known layout) at any call site, and the offset array is passed from the caller; 619 631 if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C @offsetof@ macro. 620 As an example, the body of the second @value@ function is implemented as :632 As an example, the body of the second @value@ function is implemented as 621 633 \begin{cfa} 622 634 _assign_T( _retval, p + _offsetof_pair[1] ); $\C{// return *p.second}$ 623 635 \end{cfa} 624 @_assign_T@ is passed in as an implicit parameter from @otype T@, and takes two @T *@ (@void *@ in the generated code), a destination and a source; @_retval@ is the pointer to a caller-allocated buffer for the return value, the usual \CFA method to handle dynamically-sized return types. 625 @_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as: 636 \newpage 637 \noindent 638 Here, @_assign_T@ is passed in as an implicit parameter from @otype T@, and takes two @T *@ (@void *@ in the generated code), a destination and a source, and @_retval@ is the pointer to a caller-allocated buffer for the return value, the usual \CFA method to handle dynamically sized return types. 639 @_offsetof_pair@ is the offset array passed into @value@; 640 this array is generated at the call site as 626 641 \begin{cfa} 627 642 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) } 628 643 \end{cfa} 629 644 630 In some cases the offset arrays cannot be statically generated.631 For instance, modularity is generally provided in C by including an opaque forward -declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately-compiled @.c@ file.632 \CFA supports this pattern for generic types, but the caller does not know the actual layout or size of the dynamic generic -type,and only holds it by a pointer.645 In some cases, the offset arrays cannot be statically generated. 646 For instance, modularity is generally provided in C by including an opaque forward declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately compiled @.c@ file. 647 \CFA supports this pattern for generic types, but the caller does not know the actual layout or size of the dynamic generic type and only holds it by a pointer. 633 648 The \CFA translator automatically generates \newterm{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed into a function from that function's caller. 634 649 These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic structure (un@sized@ parameters are forbidden from being used in a context that affects layout). … … 640 655 Whether a type is concrete, dtype-static, or dynamic is decided solely on the @forall@'s type parameters. 641 656 This design allows opaque forward declarations of generic types, \eg @forall(otype T)@ @struct Box@ -- like in C, all uses of @Box(T)@ can be separately compiled, and callers from other translation units know the proper calling conventions to use. 642 If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T)@ @struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off. 657 If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T)@ @struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.); 658 however, preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off. 643 659 644 660 … … 653 669 } 654 670 \end{cfa} 655 Since @pair( T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the members of both pairs and the arguments to the comparison function match in type. 656 657 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}. 658 Sometimes information is only used for type-checking and can be omitted at runtime, \eg: 671 Since @pair( T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@; 672 hence, the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type checked to ensure members of both pairs and arguments to the comparison function match in type. 673 674 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag structures}. 675 Sometimes, information is only used for type checking and can be omitted at runtime. 659 676 \begin{cquote} 660 677 \lstDeleteShortInline@% … … 675 692 half_marathon; 676 693 scalar(litres) two_pools = pool + pool; 677 `marathon + pool;` // ERROR, mismatched types694 `marathon + pool;` // ERROR, mismatched types 678 695 \end{cfa} 679 696 \end{tabular} 680 697 \lstMakeShortInline@% 681 698 \end{cquote} 682 @scalar@ is a dtype-static type, so all uses have a single structure definition, containing @unsigned long@, and can share the same implementations of common functions like @?+?@. 699 Here, @scalar@ is a dtype-static type; 700 hence, all uses have a single structure definition, containing @unsigned long@, and can share the same implementations of common functions like @?+?@. 683 701 These implementations may even be separately compiled, unlike \CC template functions. 684 However, the \CFA type -checker ensures matching types are used by all calls to @?+?@, preventing nonsensical computations like adding a length to a volume.702 However, the \CFA type checker ensures matching types are used by all calls to @?+?@, preventing nonsensical computations like adding a length to a volume. 685 703 686 704 … … 688 706 \label{sec:tuples} 689 707 690 In many languages, functions can return at mostone value;708 In many languages, functions can return, at most, one value; 691 709 however, many operations have multiple outcomes, some exceptional. 692 710 Consider C's @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and float values, respectively. … … 699 717 double r = remquo( 13.5, 5.2, &q ); $\C{// return remainder, alias quotient}$ 700 718 \end{cfa} 701 @div@ aggregates the quotient/remainder in a structure, while@remquo@ aliases a parameter to an argument.719 Here, @div@ aggregates the quotient/remainder in a structure, whereas @remquo@ aliases a parameter to an argument. 702 720 Both approaches are awkward. 703 Alternatively, a programming language can directly support returning multiple values, \eg in \CFA: 721 % FIX 722 Alternatively, a programming language can directly support returning multiple values, \eg \CFA provides the following. 704 723 \begin{cfa} 705 724 [ int, int ] div( int num, int den ); $\C{// return two integers}$ … … 712 731 This approach is straightforward to understand and use; 713 732 therefore, why do few programming languages support this obvious feature or provide it awkwardly? 714 To answer, there are complex consequences that cascade through multiple aspects of the language, especially the type -system.715 This section show these consequences and how \CFA handles them.733 To answer, there are complex consequences that cascade through multiple aspects of the language, especially the type system. 734 This section shows these consequences and how \CFA handles them. 716 735 717 736 718 737 \subsection{Tuple Expressions} 719 738 720 The addition of multiple-return-value functions (MRVF ) are \emph{useless} without a syntax for accepting multiple values at the call-site.739 The addition of multiple-return-value functions (MRVFs) is \emph{useless} without a syntax for accepting multiple values at the call site. 721 740 The simplest mechanism for capturing the return values is variable assignment, allowing the values to be retrieved directly. 722 741 As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions (as above), called a \newterm{tuple}. 723 742 724 However, functions also use \newterm{composition} (nested calls), with the direct consequence that MRVFs must also support composition to be orthogonal with single-returning-value functions (SRVF ), \eg:743 However, functions also use \newterm{composition} (nested calls), with the direct consequence that MRVFs must also support composition to be orthogonal with single-returning-value functions (SRVFs), \eg, \CFA provides the following. 725 744 \begin{cfa} 726 745 printf( "%d %d\n", div( 13, 5 ) ); $\C{// return values seperated into arguments}$ 727 746 \end{cfa} 728 747 Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments. 729 However, the \CFA type-system must support significantly more complex composition :748 However, the \CFA type-system must support significantly more complex composition. 730 749 \begin{cfa} 731 750 [ int, int ] foo$\(_1\)$( int ); $\C{// overloaded foo functions}$ … … 734 753 `bar`( foo( 3 ), foo( 3 ) ); 735 754 \end{cfa} 736 The type-resolver only has the tuple return-types to resolve the call to @bar@ as the @foo@ parameters are identical, which involves unifying the possible @foo@ functions with @bar@'s parameter list. 737 No combination of @foo@s are an exact match with @bar@'s parameters, so the resolver applies C conversions. 755 The type resolver only has the tuple return types to resolve the call to @bar@ as the @foo@ parameters are identical, which involves unifying the possible @foo@ functions with @bar@'s parameter list. 756 No combination of @foo@s is an exact match with @bar@'s parameters; 757 thus, the resolver applies C conversions. 758 % FIX 738 759 The minimal cost is @bar( foo@$_1$@( 3 ), foo@$_2$@( 3 ) )@, giving (@int@, {\color{ForestGreen}@int@}, @double@) to (@int@, {\color{ForestGreen}@double@}, @double@) with one {\color{ForestGreen}safe} (widening) conversion from @int@ to @double@ versus ({\color{red}@double@}, {\color{ForestGreen}@int@}, {\color{ForestGreen}@int@}) to ({\color{red}@int@}, {\color{ForestGreen}@double@}, {\color{ForestGreen}@double@}) with one {\color{red}unsafe} (narrowing) conversion from @double@ to @int@ and two safe conversions. 739 760 740 761 741 \subsection{Tuple Variables}762 \subsection{Tuple variables} 742 763 743 764 An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF. 744 \CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types, \eg: 765 \CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types. 766 \newpage 745 767 \begin{cfa} 746 768 [ int, int ] qr = div( 13, 5 ); $\C{// tuple-variable declaration and initialization}$ 747 769 [ double, double ] qr = div( 13.5, 5.2 ); 748 770 \end{cfa} 749 where the tuple variable-name serves the same purpose as the parameter name(s).771 Here, the tuple variable name serves the same purpose as the parameter name(s). 750 772 Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C. 751 773 752 One way to access the tuple -variable components is with assignment or composition:774 One way to access the tuple variable components is with assignment or composition. 753 775 \begin{cfa} 754 776 [ q, r ] = qr; $\C{// access tuple-variable components}$ 755 777 printf( "%d %d\n", qr ); 756 778 \end{cfa} 757 \CFA also supports \newterm{tuple indexing} to access single components of a tuple expression :779 \CFA also supports \newterm{tuple indexing} to access single components of a tuple expression. 758 780 \begin{cfa} 759 781 [int, int] * p = &qr; $\C{// tuple pointer}$ … … 766 788 767 789 768 \subsection{Flattening and Restructuring}790 \subsection{Flattening and restructuring} 769 791 770 792 In function call contexts, tuples support implicit flattening and restructuring conversions. 771 793 Tuple flattening recursively expands a tuple into the list of its basic components. 772 Tuple structuring packages a list of expressions into a value of tuple type , \eg:794 Tuple structuring packages a list of expressions into a value of tuple type. 773 795 \begin{cfa} 774 796 int f( int, int ); … … 781 803 h( x, y ); $\C{// flatten and structure}$ 782 804 \end{cfa} 783 In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as t he two arguments.805 In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as two arguments. 784 806 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@. 785 807 Finally, in the call to @h@, @x@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@. 786 The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both SRVF and MRVF, and with any number of arguments of arbitrarily complex structure. 787 788 789 \subsection{Tuple Assignment} 790 808 The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both SRVFs and MRVFs with any number of arguments of arbitrarily complex structure. 809 810 811 \subsection{Tuple assignment} 812 813 \enlargethispage{-10pt} 791 814 An assignment where the left side is a tuple type is called \newterm{tuple assignment}. 792 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.815 There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a nontuple type, called \newterm{multiple} and \newterm{mass assignment}, respectively. 793 816 \begin{cfa} 794 817 int x = 10; … … 800 823 [y, x] = 3.14; $\C{// mass assignment}$ 801 824 \end{cfa} 802 Both kinds of tuple assignment have parallel semantics, so that each value on the left and right side is evaluated before any assignments occur.825 Both kinds of tuple assignment have parallel semantics, so that each value on the left and right sides is evaluated before any assignments occur. 803 826 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]@. 804 827 This semantics means mass assignment differs from C cascading assignment (\eg @a = b = c@) in that conversions are applied in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment. 805 For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@; 806 whereas, C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@. 828 For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@, whereas C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@. 807 829 Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C. 808 This example shows mass, multiple, and cascading assignment used in one expression :830 This example shows mass, multiple, and cascading assignment used in one expression. 809 831 \begin{cfa} 810 832 [void] f( [int, int] ); … … 813 835 814 836 815 \subsection{Member Access}816 817 It is also possible to access multiple members from a single expression using a \newterm{member -access}.818 The result is a single tuple-valued expression whose type is the tuple of the types of the members , \eg:837 \subsection{Member access} 838 839 It is also possible to access multiple members from a single expression using a \newterm{member access}. 840 The result is a single tuple-valued expression whose type is the tuple of the types of the members. 819 841 \begin{cfa} 820 842 struct S { int x; double y; char * z; } s; … … 830 852 [int, int, int] y = x.[2, 0, 2]; $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$ 831 853 \end{cfa} 832 It is also possible for a member access to contain other member accesses , \eg:854 It is also possible for a member access to contain other member accesses. 833 855 \begin{cfa} 834 856 struct A { double i; int j; }; … … 897 919 898 920 Tuples also integrate with \CFA polymorphism as a kind of generic type. 899 Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non -tuple types, \eg:921 Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with nontuple types. 900 922 \begin{cfa} 901 923 forall( otype T, dtype U ) void f( T x, U * y ); 902 924 f( [5, "hello"] ); 903 925 \end{cfa} 904 where@[5, "hello"]@ is flattened, giving argument list @5, "hello"@, and @T@ binds to @int@ and @U@ binds to @const char@.926 Here, @[5, "hello"]@ is flattened, giving argument list @5, "hello"@, and @T@ binds to @int@ and @U@ binds to @const char@. 905 927 Tuples, however, may contain polymorphic components. 906 928 For example, a plus operator can be written to sum two triples. … … 920 942 g( 5, 10.21 ); 921 943 \end{cfa} 944 \newpage 922 945 Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution. 923 946 This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}. … … 930 953 931 954 932 \subsection{Variadic Tuples}955 \subsection{Variadic tuples} 933 956 \label{sec:variadic-tuples} 934 957 935 To define variadic functions, \CFA adds a new kind of type parameter, @ttype@ (tuple type).936 Matching against a @ttype@ parameter consumes all remaining argument components and packages them into a tuple, binding to the resulting tuple of types.937 In a given parameter list, there must be at mostone @ttype@ parameter that occurs last, which matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates.958 To define variadic functions, \CFA adds a new kind of type parameter, \ie @ttype@ (tuple type). 959 Matching against a @ttype@ parameter consumes all the remaining argument components and packages them into a tuple, binding to the resulting tuple of types. 960 In a given parameter list, there must be, at most, one @ttype@ parameter that occurs last, which matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates. 938 961 As such, @ttype@ variables are also called \newterm{argument packs}. 939 962 … … 941 964 Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful. 942 965 Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled. 943 For example, a generalized @sum@ function:966 For example, the following is a generalized @sum@ function. 944 967 \begin{cfa} 945 968 int sum$\(_0\)$() { return 0; } … … 950 973 \end{cfa} 951 974 Since @sum@\(_0\) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@. 952 In order to call @sum@\(_1\), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list and @Params@ is bound to @[20, 30]@.975 In order to call @sum@\(_1\), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list, and @Params@ is bound to @[20, 30]@. 953 976 The process continues until @Params@ is bound to @[]@, requiring an assertion @int sum()@, which matches @sum@\(_0\) and terminates the recursion. 954 977 Effectively, this algorithm traces as @sum(10, 20, 30)@ $\rightarrow$ @10 + sum(20, 30)@ $\rightarrow$ @10 + (20 + sum(30))@ $\rightarrow$ @10 + (20 + (30 + sum()))@ $\rightarrow$ @10 + (20 + (30 + 0))@. 955 978 956 It is reasonable to take the @sum@ function a step further to enforce a minimum number of arguments :979 It is reasonable to take the @sum@ function a step further to enforce a minimum number of arguments. 957 980 \begin{cfa} 958 981 int sum( int x, int y ) { return x + y; } … … 961 984 } 962 985 \end{cfa} 963 One more step permits the summation of any sumable type with all arguments of the same type :986 One more step permits the summation of any sumable type with all arguments of the same type. 964 987 \begin{cfa} 965 988 trait sumable( otype T ) { … … 990 1013 This example showcases a variadic-template-like decomposition of the provided argument list. 991 1014 The individual @print@ functions allow printing a single element of a type. 992 The polymorphic @print@ allows printing any list of types, where aseach individual type has a @print@ function.1015 The polymorphic @print@ allows printing any list of types, where each individual type has a @print@ function. 993 1016 The individual print functions can be used to build up more complicated @print@ functions, such as @S@, which cannot be done with @printf@ in C. 994 1017 This mechanism is used to seamlessly print tuples in the \CFA I/O library (see Section~\ref{s:IOLibrary}). 995 1018 996 1019 Finally, it is possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions. 997 For example, it is possible to write @new@ as a library function :1020 For example, it is possible to write @new@ as a library function. 998 1021 \begin{cfa} 999 1022 forall( otype R, otype S ) void ?{}( pair(R, S) *, R, S ); … … 1004 1027 \end{cfa} 1005 1028 The @new@ function provides the combination of type-safe @malloc@ with a \CFA constructor call, making it impossible to forget constructing dynamically allocated objects. 1006 This function provides the type -safety of @new@ in \CC, without the need to specify the allocated type again, thanksto return-type inference.1029 This function provides the type safety of @new@ in \CC, without the need to specify the allocated type again, due to return-type inference. 1007 1030 1008 1031 … … 1010 1033 1011 1034 Tuples are implemented in the \CFA translator via a transformation into \newterm{generic types}. 1012 For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg: 1035 For each $N$, the first time an $N$-tuple is seen in a scope, a generic type with $N$ type parameters is generated. 1036 For example, the following 1013 1037 \begin{cfa} 1014 1038 [int, int] f() { … … 1017 1041 } 1018 1042 \end{cfa} 1019 is transformed into :1043 is transformed into 1020 1044 \begin{cfa} 1021 1045 forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 { … … 1083 1107 1084 1108 The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions. 1085 A variable is generated to store the value produced by a statement expression, since its members may need to be constructed with a non -trivial constructor and it may need to be referred to multiple time, \eg in a unique expression.1109 A variable is generated to store the value produced by a statement expression, since its members may need to be constructed with a nontrivial constructor and it may need to be referred to multiple time, \eg in a unique expression. 1086 1110 The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language. 1087 1111 However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new. … … 1091 1115 \section{Control Structures} 1092 1116 1093 \CFA identifies inconsistent, problematic, and missing control structures in C, a ndextends, modifies, and adds control structures to increase functionality and safety.1094 1095 1096 \subsection{\texorpdfstring{\protect\lstinline {if} Statement}{if Statement}}1097 1098 The @if@ expression allows declarations, similar to @for@ declaration expression:1117 \CFA identifies inconsistent, problematic, and missing control structures in C, as well as extends, modifies, and adds control structures to increase functionality and safety. 1118 1119 1120 \subsection{\texorpdfstring{\protect\lstinline@if@ statement}{if statement}} 1121 1122 The @if@ expression allows declarations, similar to the @for@ declaration expression. 1099 1123 \begin{cfa} 1100 1124 if ( int x = f() ) ... $\C{// x != 0}$ … … 1103 1127 \end{cfa} 1104 1128 Unless a relational expression is specified, each variable is compared not equal to 0, which is the standard semantics for the @if@ expression, and the results are combined using the logical @&&@ operator.\footnote{\CC only provides a single declaration always compared not equal to 0.} 1105 The scope of the declaration(s) is local to the @if@ statement but exist within both the ``then'' and ``else'' clauses.1106 1107 1108 \subsection{\texorpdfstring{\protect\lstinline {switch} Statement}{switch Statement}}1129 The scope of the declaration(s) is local to the @if@ statement but exists within both the ``then'' and ``else'' clauses. 1130 1131 1132 \subsection{\texorpdfstring{\protect\lstinline@switch@ statement}{switch statement}} 1109 1133 1110 1134 There are a number of deficiencies with the C @switch@ statements: enumerating @case@ lists, placement of @case@ clauses, scope of the switch body, and fall through between case clauses. 1111 1135 1112 C has no shorthand for specifying a list of case values, whether the list is non -contiguous or contiguous\footnote{C provides this mechanism via fall through.}.1113 \CFA provides a shorthand for a non -contiguous list:1136 C has no shorthand for specifying a list of case values, whether the list is noncontiguous or contiguous\footnote{C provides this mechanism via fall through.}. 1137 \CFA provides a shorthand for a noncontiguous list: 1114 1138 \begin{cquote} 1115 1139 \lstDeleteShortInline@% … … 1126 1150 \lstMakeShortInline@% 1127 1151 \end{cquote} 1128 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.} 1152 for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, as a space is required after a number; 1153 otherwise, the first period is a decimal point.} 1129 1154 \begin{cquote} 1130 1155 \lstDeleteShortInline@% … … 1157 1182 } 1158 1183 \end{cfa} 1159 \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.1160 1161 C allows placement of declaration within the @switch@ body and unreachable code at the start, resulting in undefined behaviour:1184 \CFA precludes this form of transfer \emph{into} a control structure because it causes an undefined behavior, especially with respect to missed initialization, and provides very limited functionality. 1185 1186 C allows placement of declaration within the @switch@ body and unreachable code at the start, resulting in an undefined behavior. 1162 1187 \begin{cfa} 1163 1188 switch ( x ) { … … 1176 1201 1177 1202 C @switch@ provides multiple entry points into the statement body, but once an entry point is selected, control continues across \emph{all} @case@ clauses until the end of the @switch@ body, called \newterm{fall through}; 1178 @case@ clauses are made disjoint by the @break@ statement. 1203 @case@ clauses are made disjoint by the @break@ 1204 \newpage 1205 \noindent 1206 statement. 1179 1207 While fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in errors from missing @break@ statements. 1180 For backward s compatibility, \CFA provides a \emph{new} control structure,@choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}), similar to Go.1208 For backward compatibility, \CFA provides a \emph{new} control structure, \ie @choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}), similar to Go. 1181 1209 1182 1210 \begin{figure} 1183 1211 \centering 1212 \fontsize{9bp}{11bp}\selectfont 1184 1213 \lstDeleteShortInline@% 1185 1214 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} … … 1218 1247 \end{tabular} 1219 1248 \lstMakeShortInline@% 1220 \caption{\lstinline|choose| versus \lstinline|switch| Statements}1249 \caption{\lstinline|choose| versus \lstinline|switch| statements} 1221 1250 \label{f:ChooseSwitchStatements} 1251 \vspace*{-11pt} 1222 1252 \end{figure} 1223 1253 1224 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.1254 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. 1225 1255 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; 1226 1256 the target label may be case @default@, but only associated with the current @switch@/@choose@ statement. … … 1228 1258 \begin{figure} 1229 1259 \centering 1260 \fontsize{9bp}{11bp}\selectfont 1230 1261 \lstDeleteShortInline@% 1231 1262 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} … … 1256 1287 \end{tabular} 1257 1288 \lstMakeShortInline@% 1258 \caption{\lstinline|fallthrough| Statement}1289 \caption{\lstinline|fallthrough| statement} 1259 1290 \label{f:FallthroughStatement} 1291 \vspace*{-11pt} 1260 1292 \end{figure} 1261 1293 1262 1294 1263 \subsection{\texorpdfstring{Labelled \protect\lstinline{continue} / \protect\lstinline{break}}{Labelled continue / break}} 1295 \vspace*{-8pt} 1296 \subsection{\texorpdfstring{Labeled \protect\lstinline@continue@ / \protect\lstinline@break@}{Labeled continue / break}} 1264 1297 1265 1298 While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure. 1266 Unfortunately, this restriction forces programmers to use @goto@ to achieve the equivalent control -flow for more than one level of nesting.1267 To prevent having to switch to the @goto@, \CFA extends the @continue@ and @break@ with a target label to support static multi-level exit~\cite{Buhr85}, as in Java.1299 Unfortunately, this restriction forces programmers to use @goto@ to achieve the equivalent control flow for more than one level of nesting. 1300 To prevent having to switch to the @goto@, \CFA extends @continue@ and @break@ with a target label to support static multilevel exit~\cite{Buhr85}, as in Java. 1268 1301 For both @continue@ and @break@, the target label must be directly associated with a @for@, @while@ or @do@ statement; 1269 1302 for @break@, the target label can also be associated with a @switch@, @if@ or compound (@{}@) statement. 1270 Figure~\ref{f:MultiLevelExit} shows @continue@ and @break@ indicating the specific control structure ,and the corresponding C program using only @goto@ and labels.1271 The innermost loop has 7 exit points, which cause continuation or termination of one or more of the 7 nested control-structures.1303 Figure~\ref{f:MultiLevelExit} shows @continue@ and @break@ indicating the specific control structure and the corresponding C program using only @goto@ and labels. 1304 The innermost loop has seven exit points, which cause a continuation or termination of one or more of the seven nested control structures. 1272 1305 1273 1306 \begin{figure} 1307 \fontsize{9bp}{11bp}\selectfont 1274 1308 \lstDeleteShortInline@% 1275 1309 \begin{tabular}{@{\hspace{\parindentlnth}}l|@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}} … … 1336 1370 \end{tabular} 1337 1371 \lstMakeShortInline@% 1338 \caption{Multi -level Exit}1372 \caption{Multilevel exit} 1339 1373 \label{f:MultiLevelExit} 1374 \vspace*{-5pt} 1340 1375 \end{figure} 1341 1376 1342 With respect to safety, both label led @continue@ and @break@ are a @goto@ restricted in the following ways:1343 \begin{ itemize}1377 With respect to safety, both labeled @continue@ and @break@ are @goto@ restricted in the following ways. 1378 \begin{list}{$\bullet$}{\topsep=4pt\itemsep=0pt\parsep=0pt} 1344 1379 \item 1345 1380 They cannot create a loop, which means only the looping constructs cause looping. … … 1347 1382 \item 1348 1383 They cannot branch into a control structure. 1349 This restriction prevents missing declarations and/or initializations at the start of a control structure resulting in undefined behaviour. 1350 \end{itemize} 1351 The advantage of the labelled @continue@/@break@ is allowing static multi-level exits without having to use the @goto@ statement, and tying control flow to the target control structure rather than an arbitrary point in a program. 1352 Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader (eye candy) that complex control-flow is occurring in the body of the control structure. 1384 This restriction prevents missing declarations and/or initializations at the start of a control structure resulting in an undefined behavior. 1385 \end{list} 1386 The advantage of the labeled @continue@/@break@ is allowing static multilevel exits without having to use the @goto@ statement and tying control flow to the target control structure rather than an arbitrary point in a program. 1387 Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader (eye candy) that complex control flow is 1388 occurring in the body of the control structure. 1353 1389 With @goto@, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader. 1354 Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting existing constructs.1390 Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting the existing constructs. 1355 1391 Otherwise, the implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed. 1356 1392 1357 1393 1358 \subsection{Exception Handling} 1359 1360 The following framework for \CFA exception-handling is in place, excluding some runtime type-information and virtual functions. 1394 \vspace*{-5pt} 1395 \subsection{Exception handling} 1396 1397 The following framework for \CFA exception handling is in place, excluding some runtime type information and virtual functions. 1361 1398 \CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}. 1362 Both mechanisms provide dynamic call to a handler using dynamic name -lookup, where fix-up has dynamic return and recovery has static return from the handler.1399 Both mechanisms provide dynamic call to a handler using dynamic name lookup, where fix-up has dynamic return and recovery has static return from the handler. 1363 1400 \CFA restricts exception types to those defined by aggregate type @exception@. 1364 1401 The form of the raise dictates the set of handlers examined during propagation: \newterm{resumption propagation} (@resume@) only examines resumption handlers (@catchResume@); \newterm{terminating propagation} (@throw@) only examines termination handlers (@catch@). 1365 If @resume@ or @throw@ ha ve no exception type, it is a reresume/rethrow, meaning the currentlyexception continues propagation.1402 If @resume@ or @throw@ has no exception type, it is a reresume/rethrow, which means that the current exception continues propagation. 1366 1403 If there is no current exception, the reresume/rethrow results in a runtime error. 1367 1404 1368 1405 \begin{figure} 1406 \fontsize{9bp}{11bp}\selectfont 1407 \lstDeleteShortInline@% 1369 1408 \begin{cquote} 1370 \lstDeleteShortInline@%1371 1409 \begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}} 1372 1410 \multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{Resumption}} & \multicolumn{1}{c@{}}{\textbf{Termination}} \\ … … 1399 1437 \end{cfa} 1400 1438 \end{tabular} 1401 \lstMakeShortInline@%1402 1439 \end{cquote} 1403 \caption{\CFA Exception Handling} 1440 \lstMakeShortInline@% 1441 \caption{\CFA exception handling} 1404 1442 \label{f:CFAExceptionHandling} 1443 \vspace*{-5pt} 1405 1444 \end{figure} 1406 1445 1407 The set of exception types in a list of catch clause may include both a resumption and termination handler:1446 The set of exception types in a list of catch clauses may include both a resumption and a termination handler. 1408 1447 \begin{cfa} 1409 1448 try { … … 1419 1458 The termination handler is available because the resumption propagation did not unwind the stack. 1420 1459 1421 An additional feature is conditional matching in a catch clause :1460 An additional feature is conditional matching in a catch clause. 1422 1461 \begin{cfa} 1423 1462 try { … … 1428 1467 catch ( IOError err ) { ... } $\C{// handler error from other files}$ 1429 1468 \end{cfa} 1430 where the throw inserts the failing file-handle into the I/O exception.1431 Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible. .1432 1433 The resumption raise can specify an alternate stack on which to raise an exception, called a \newterm{nonlocal raise} :1469 Here, the throw inserts the failing file handle into the I/O exception. 1470 Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible. 1471 1472 The resumption raise can specify an alternate stack on which to raise an exception, called a \newterm{nonlocal raise}. 1434 1473 \begin{cfa} 1435 1474 resume( $\emph{exception-type}$, $\emph{alternate-stack}$ ) … … 1439 1478 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. 1440 1479 1441 To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception -propagation.1442 The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks:1480 To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception propagation. 1481 The constructs for controlling propagation of nonlocal exceptions are the @enable@ and @disable@ blocks. 1443 1482 \begin{cquote} 1444 1483 \lstDeleteShortInline@% … … 1446 1485 \begin{cfa} 1447 1486 enable $\emph{exception-type-list}$ { 1448 // allow non -local raise1487 // allow nonlocal raise 1449 1488 } 1450 1489 \end{cfa} … … 1452 1491 \begin{cfa} 1453 1492 disable $\emph{exception-type-list}$ { 1454 // disallow non -local raise1493 // disallow nonlocal raise 1455 1494 } 1456 1495 \end{cfa} … … 1460 1499 The arguments for @enable@/@disable@ specify the exception types allowed to be propagated or postponed, respectively. 1461 1500 Specifying no exception type is shorthand for specifying all exception types. 1462 Both @enable@ and @disable@ blocks can be nested, turning propagation on/off on entry, and on exit, the specified exception types are restored to their prior state. 1463 Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled. 1501 Both @enable@ and @disable@ blocks can be nested; 1502 turning propagation on/off on entry and on exit, the specified exception types are restored to their prior state. 1503 Coroutines and tasks start with nonlocal exceptions disabled, allowing handlers to be put in place, before nonlocal exceptions are explicitly enabled. 1464 1504 \begin{cfa} 1465 1505 void main( mytask & t ) { $\C{// thread starts here}$ 1466 // non -local exceptions disabled1467 try { $\C{// establish handles for non -local exceptions}$1468 enable { $\C{// allow non -local exception delivery}$1506 // nonlocal exceptions disabled 1507 try { $\C{// establish handles for nonlocal exceptions}$ 1508 enable { $\C{// allow nonlocal exception delivery}$ 1469 1509 // task body 1470 1510 } … … 1474 1514 \end{cfa} 1475 1515 1476 Finally, \CFA provides a Java like @finally@ clause after the catch clauses:1516 Finally, \CFA provides a Java-like @finally@ clause after the catch clauses. 1477 1517 \begin{cfa} 1478 1518 try { … … 1483 1523 } 1484 1524 \end{cfa} 1485 The finally clause is always executed, i.e., if the try block ends normally or if an exception is raised.1525 The finally clause is always executed, \ie, if the try block ends normally or if an exception is raised. 1486 1526 If an exception is raised and caught, the handler is run before the finally clause. 1487 1527 Like a destructor (see Section~\ref{s:ConstructorsDestructors}), a finally clause can raise an exception but not if there is an exception being propagated. 1488 Mimicking the @finally@ clause with mechanisms like R AII is non-trivial when there are multiple types and local accesses.1489 1490 1491 \subsection{\texorpdfstring{\protect\lstinline{with} Statement}{with Statement}}1528 Mimicking the @finally@ clause with mechanisms like Resource Aquisition Is Initialization (RAII) is nontrivial when there are multiple types and local accesses. 1529 1530 1531 \subsection{\texorpdfstring{\protect\lstinline{with} statement}{with statement}} 1492 1532 \label{s:WithStatement} 1493 1533 1494 Heterogeneous data isoften aggregated into a structure/union.1495 To reduce syntactic noise, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate member-qualification by opening a scope containing the member identifiers.1534 Heterogeneous data are often aggregated into a structure/union. 1535 To reduce syntactic noise, \CFA provides a @with@ statement (see section~4.F in the Pascal User Manual and Report~\cite{Pascal}) to elide aggregate member qualification by opening a scope containing the member identifiers. 1496 1536 \begin{cquote} 1497 1537 \vspace*{-\baselineskip}%??? … … 1521 1561 Object-oriented programming languages only provide implicit qualification for the receiver. 1522 1562 1523 In detail, the @with@ statement has the form :1563 In detail, the @with@ statement has the form 1524 1564 \begin{cfa} 1525 1565 $\emph{with-statement}$: … … 1527 1567 \end{cfa} 1528 1568 and may appear as the body of a function or nested within a function body. 1529 Each expression in the expression -list provides a type and object.1569 Each expression in the expression list provides a type and object. 1530 1570 The type must be an aggregate type. 1531 1571 (Enumerations are already opened.) 1532 The object is the implicit qualifier for the open structure -members.1572 The object is the implicit qualifier for the open structure members. 1533 1573 1534 1574 All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right. 1535 The difference between parallel and nesting occurs for members with the same name and type :1575 The difference between parallel and nesting occurs for members with the same name and type. 1536 1576 \begin{cfa} 1537 1577 struct S { int `i`; int j; double m; } s, w; $\C{// member i has same type in structure types S and T}$ … … 1547 1587 } 1548 1588 \end{cfa} 1549 For parallel semantics, both @s.i@ and @t.i@ are visible , so@i@ is ambiguous without qualification;1550 for nested semantics, @t.i@ hides @s.i@ , so@i@ implies @t.i@.1589 For parallel semantics, both @s.i@ and @t.i@ are visible and, therefore, @i@ is ambiguous without qualification; 1590 for nested semantics, @t.i@ hides @s.i@ and, therefore, @i@ implies @t.i@. 1551 1591 \CFA's ability to overload variables means members with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates. 1552 1592 Qualification or a cast is used to disambiguate. 1553 1593 1554 There is an interesting problem between parameters and the function -body @with@, \eg:1594 There is an interesting problem between parameters and the function body @with@. 1555 1595 \begin{cfa} 1556 1596 void ?{}( S & s, int i ) with ( s ) { $\C{// constructor}$ … … 1558 1598 } 1559 1599 \end{cfa} 1560 Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function -body @with@.1561 To solve this problem, parameters are treated like an initialized aggregate :1600 Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function body @with@. 1601 To solve this problem, parameters are treated like an initialized aggregate 1562 1602 \begin{cfa} 1563 1603 struct Params { … … 1566 1606 } params; 1567 1607 \end{cfa} 1568 and implicitly opened \emph{after} a function-body open, to give them higher priority: 1608 \newpage 1609 and implicitly opened \emph{after} a function body open, to give them higher priority 1569 1610 \begin{cfa} 1570 1611 void ?{}( S & s, int `i` ) with ( s ) `{` `with( $\emph{\color{red}params}$ )` { … … 1572 1613 } `}` 1573 1614 \end{cfa} 1574 Finally, a cast may be used to disambiguate among overload variables in a @with@ expression :1615 Finally, a cast may be used to disambiguate among overload variables in a @with@ expression 1575 1616 \begin{cfa} 1576 1617 with ( w ) { ... } $\C{// ambiguous, same name and no context}$ 1577 1618 with ( (S)w ) { ... } $\C{// unambiguous, cast}$ 1578 1619 \end{cfa} 1579 and @with@ expressions may be complex expressions with type reference (see Section~\ref{s:References}) to aggregate :1620 and @with@ expressions may be complex expressions with type reference (see Section~\ref{s:References}) to aggregate 1580 1621 \begin{cfa} 1581 1622 struct S { int i, j; } sv; … … 1601 1642 \CFA attempts to correct and add to C declarations, while ensuring \CFA subjectively ``feels like'' C. 1602 1643 An important part of this subjective feel is maintaining C's syntax and procedural paradigm, as opposed to functional and object-oriented approaches in other systems languages such as \CC and Rust. 1603 Maintaining the C approach means that C coding -patterns remain not only useable but idiomatic in \CFA, reducing the mental burden of retraining C programmers and switching between C and \CFA development.1644 Maintaining the C approach means that C coding patterns remain not only useable but idiomatic in \CFA, reducing the mental burden of retraining C programmers and switching between C and \CFA development. 1604 1645 Nevertheless, some features from other approaches are undeniably convenient; 1605 1646 \CFA attempts to adapt these features to the C paradigm. 1606 1647 1607 1648 1608 \subsection{Alternative Declaration Syntax}1649 \subsection{Alternative declaration syntax} 1609 1650 1610 1651 C declaration syntax is notoriously confusing and error prone. 1611 For example, many C programmers are confused by a declaration as simple as :1652 For example, many C programmers are confused by a declaration as simple as the following. 1612 1653 \begin{cquote} 1613 1654 \lstDeleteShortInline@% … … 1621 1662 \lstMakeShortInline@% 1622 1663 \end{cquote} 1623 Is this an array of 5 pointers to integers or a pointer to an array of 5integers?1664 Is this an array of five pointers to integers or a pointer to an array of five integers? 1624 1665 If there is any doubt, it implies productivity and safety issues even for basic programs. 1625 1666 Another example of confusion results from the fact that a function name and its parameters are embedded within the return type, mimicking the way the return value is used at the function's call site. 1626 For example, a function returning a pointer to an array of integers is defined and used in the following way :1667 For example, a function returning a pointer to an array of integers is defined and used in the following way. 1627 1668 \begin{cfa} 1628 1669 int `(*`f`())[`5`]` {...}; $\C{// definition}$ … … 1632 1673 While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice. 1633 1674 1634 \CFA provides its own type, variable and function declarations, using a different syntax~\cite[pp.~856--859]{Buhr94a}. 1635 The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right. 1675 \newpage 1676 \CFA provides its own type, variable, and function declarations, using a different syntax~\cite[pp.~856--859]{Buhr94a}. 1677 The new declarations place qualifiers to the left of the base type, whereas C declarations place qualifiers to the right. 1636 1678 The qualifiers have the same meaning but are ordered left to right to specify a variable's type. 1637 1679 \begin{cquote} … … 1659 1701 \lstMakeShortInline@% 1660 1702 \end{cquote} 1661 The only exception is bit-field specification, which always appear to the right of the base type.1703 The only exception is bit-field specification, which always appears to the right of the base type. 1662 1704 % Specifically, the character @*@ is used to indicate a pointer, square brackets @[@\,@]@ are used to represent an array or function return value, and parentheses @()@ are used to indicate a function parameter. 1663 1705 However, unlike C, \CFA type declaration tokens are distributed across all variables in the declaration list. 1664 For instance, variables @x@ and @y@ of type pointer to integer are defined in \CFA as follows:1706 For instance, variables @x@ and @y@ of type pointer to integer are defined in \CFA as 1665 1707 \begin{cquote} 1666 1708 \lstDeleteShortInline@% … … 1725 1767 \end{comment} 1726 1768 1727 All specifiers (@extern@, @static@, \etc) and qualifiers (@const@, @volatile@, \etc) are used in the normal way with the new declarations and also appear left to right , \eg:1769 All specifiers (@extern@, @static@, \etc) and qualifiers (@const@, @volatile@, \etc) are used in the normal way with the new declarations and also appear left to right. 1728 1770 \begin{cquote} 1729 1771 \lstDeleteShortInline@% 1730 1772 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}} 1731 1773 \multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}} \\ 1732 \begin{cfa} 1774 \begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf] 1733 1775 extern const * const int x; 1734 1776 static const * [5] const int y; 1735 1777 \end{cfa} 1736 1778 & 1737 \begin{cfa} 1779 \begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf] 1738 1780 int extern const * const x; 1739 1781 static const int (* const y)[5] 1740 1782 \end{cfa} 1741 1783 & 1742 \begin{cfa} 1784 \begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf] 1743 1785 // external const pointer to const int 1744 1786 // internal const pointer to array of 5 const int … … 1748 1790 \end{cquote} 1749 1791 Specifiers must appear at the start of a \CFA function declaration\footnote{\label{StorageClassSpecifier} 1750 The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature .~\cite[\S~6.11.5(1)]{C11}}.1792 The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature (see section~6.11.5(1) in ISO/IEC 9899~\cite{C11}).}. 1751 1793 1752 1794 The new declaration syntax can be used in other contexts where types are required, \eg casts and the pseudo-function @sizeof@: … … 1769 1811 1770 1812 The syntax of the new function-prototype declaration follows directly from the new function-definition syntax; 1771 a s well, parameter names are optional, \eg:1813 also, parameter names are optional. 1772 1814 \begin{cfa} 1773 1815 [ int x ] f ( /* void */ ); $\C[2.5in]{// returning int with no parameters}$ … … 1777 1819 [ * int, int ] j ( int ); $\C{// returning pointer to int and int with int parameter}$ 1778 1820 \end{cfa} 1779 This syntax allows a prototype declaration to be created by cutting and pasting source text from the function-definition header (or vice versa).1780 Like C, it is possible to declare multiple function -prototypes in a single declaration, where the return type is distributed across \emph{all} function names in the declaration list, \eg:1821 This syntax allows a prototype declaration to be created by cutting and pasting the source text from the function-definition header (or vice versa). 1822 Like C, it is possible to declare multiple function prototypes in a single declaration, where the return type is distributed across \emph{all} function names in the declaration list. 1781 1823 \begin{cquote} 1782 1824 \lstDeleteShortInline@% … … 1793 1835 \lstMakeShortInline@% 1794 1836 \end{cquote} 1795 where\CFA allows the last function in the list to define its body.1796 1797 The syntax for pointers to \CFA functions specifies the pointer name on the right , \eg:1837 Here, \CFA allows the last function in the list to define its body. 1838 1839 The syntax for pointers to \CFA functions specifies the pointer name on the right. 1798 1840 \begin{cfa} 1799 1841 * [ int x ] () fp; $\C{// pointer to function returning int with no parameters}$ … … 1802 1844 * [ * int, int ] ( int ) jp; $\C{// pointer to function returning pointer to int and int with int parameter}\CRT$ 1803 1845 \end{cfa} 1804 Note, the name of the function pointer is specified last, as for other variable declarations. 1805 1806 Finally, new \CFA declarations may appear together with C declarations in the same program block, but cannot be mixed within a specific declaration. 1807 Therefore, a programmer has the option of either continuing to use traditional C declarations or take advantage of the new style. 1808 Clearly, both styles need to be supported for some time due to existing C-style header-files, particularly for UNIX-like systems. 1846 \newpage 1847 \noindent 1848 Note that the name of the function pointer is specified last, as for other variable declarations. 1849 1850 Finally, new \CFA declarations may appear together with C declarations in the same program block but cannot be mixed within a specific declaration. 1851 Therefore, a programmer has the option of either continuing to use traditional C declarations or taking advantage of the new style. 1852 Clearly, both styles need to be supported for some time due to existing C-style header files, particularly for UNIX-like systems. 1809 1853 1810 1854 … … 1814 1858 All variables in C have an \newterm{address}, a \newterm{value}, and a \newterm{type}; 1815 1859 at the position in the program's memory denoted by the address, there exists a sequence of bits (the value), with the length and semantic meaning of this bit sequence defined by the type. 1816 The C type -system does not always track the relationship between a value and its address;1817 a value that does not have a corresponding address is called a \newterm{rvalue} (for ``right-hand value''), while a value that does have an address is called a\newterm{lvalue} (for ``left-hand value'').1818 For example, in @int x; x = 42;@ the variable expression @x@ on the left-hand -side of the assignment is a lvalue, while the constant expression @42@ on the right-hand-side of the assignment is arvalue.1819 Despite the nomenclature of ``left-hand'' and ``right-hand'', an expression's classification as lvalue or rvalue is entirely dependent on whether it has an address or not; in imperative programming, the address of a value is used for both reading and writing (mutating) a value, and as such, lvalues can be convertedto rvalues and read from, but rvalues cannot be mutated because they lack a location to store the updated value.1860 The C type system does not always track the relationship between a value and its address; 1861 a value that does not have a corresponding address is called an \newterm{rvalue} (for ``right-hand value''), whereas a value that does have an address is called an \newterm{lvalue} (for ``left-hand value''). 1862 For example, in @int x; x = 42;@ the variable expression @x@ on the left-hand side of the assignment is an lvalue, whereas the constant expression @42@ on the right-hand side of the assignment is an rvalue. 1863 Despite the nomenclature of ``left-hand'' and ``right-hand'', an expression's classification as an lvalue or an rvalue is entirely dependent on whether it has an address or not; in imperative programming, the address of a value is used for both reading and writing (mutating) a value, and as such, lvalues can be converted into rvalues and read from, but rvalues cannot be mutated because they lack a location to store the updated value. 1820 1864 1821 1865 Within a lexical scope, lvalue expressions have an \newterm{address interpretation} for writing a value or a \newterm{value interpretation} to read a value. 1822 For example, in @x = y@, @x@ has an address interpretation, wh ile@y@ has a value interpretation.1866 For example, in @x = y@, @x@ has an address interpretation, whereas @y@ has a value interpretation. 1823 1867 While this duality of interpretation is useful, C lacks a direct mechanism to pass lvalues between contexts, instead relying on \newterm{pointer types} to serve a similar purpose. 1824 1868 In C, for any type @T@ there is a pointer type @T *@, the value of which is the address of a value of type @T@. 1825 A pointer rvalue can be explicitly \newterm{dereferenced} to the pointed-to lvalue with the dereference operator @*?@, while the rvalue representing the address of a lvalue can be obtained with the address-of operator @&?@. 1826 1869 A pointer rvalue can be explicitly \newterm{dereferenced} to the pointed-to lvalue with the dereference operator @*?@, whereas the rvalue representing the address of an lvalue can be obtained with the address-of operator @&?@. 1827 1870 \begin{cfa} 1828 1871 int x = 1, y = 2, * p1, * p2, ** p3; … … 1832 1875 *p2 = ((*p1 + *p2) * (**p3 - *p1)) / (**p3 - 15); 1833 1876 \end{cfa} 1834 1835 1877 Unfortunately, the dereference and address-of operators introduce a great deal of syntactic noise when dealing with pointed-to values rather than pointers, as well as the potential for subtle bugs because of pointer arithmetic. 1836 1878 For both brevity and clarity, it is desirable for the compiler to figure out how to elide the dereference operators in a complex expression such as the assignment to @*p2@ above. 1837 However, since C defines a number of forms of \newterm{pointer arithmetic}, two similar expressions involving pointers to arithmetic types (\eg @*p1 + x@ and @p1 + x@) may each have well-defined but distinct semantics, introducing the possibility that a programmer may write one when they mean the other ,and precluding any simple algorithm for elision of dereference operators.1879 However, since C defines a number of forms of \newterm{pointer arithmetic}, two similar expressions involving pointers to arithmetic types (\eg @*p1 + x@ and @p1 + x@) may each have well-defined but distinct semantics, introducing the possibility that a programmer may write one when they mean the other and precluding any simple algorithm for elision of dereference operators. 1838 1880 To solve these problems, \CFA introduces reference types @T &@; 1839 a @T &@ has exactly the same value as a @T *@, but where the @T *@ takes the address interpretation by default, a @T &@ takes the value interpretation by default, as below: 1840 1881 a @T &@ has exactly the same value as a @T *@, but where the @T *@ takes the address interpretation by default, a @T &@ takes the value interpretation by default, as below. 1841 1882 \begin{cfa} 1842 1883 int x = 1, y = 2, & r1, & r2, && r3; … … 1846 1887 r2 = ((r1 + r2) * (r3 - r1)) / (r3 - 15); $\C{// implicit dereferencing}$ 1847 1888 \end{cfa} 1848 1849 1889 Except for auto-dereferencing by the compiler, this reference example is exactly the same as the previous pointer example. 1850 Hence, a reference behaves like a variable name -- an lvalue expression which is interpreted as a value --but also has the type system track the address of that value.1851 One way to conceptualize a reference is via a rewrite rule, where the compiler inserts a dereference operator before the reference variable for each reference qualifier in the reference variable declaration , so the previous example implicitly acts like:1852 1890 Hence, a reference behaves like a variable name---an lvalue expression that is interpreted as a value---but also has the type system track the address of that value. 1891 One way to conceptualize a reference is via a rewrite rule, where the compiler inserts a dereference operator before the reference variable for each reference qualifier in the reference variable declaration; 1892 thus, the previous example implicitly acts like the following. 1853 1893 \begin{cfa} 1854 1894 `*`r2 = ((`*`r1 + `*`r2) * (`**`r3 - `*`r1)) / (`**`r3 - 15); 1855 1895 \end{cfa} 1856 1857 1896 References in \CFA are similar to those in \CC, with important improvements, which can be seen in the example above. 1858 1897 Firstly, \CFA does not forbid references to references. 1859 This provides a much more orthogonal design for library implementors, obviating the need for workarounds such as @std::reference_wrapper@.1898 This provides a much more orthogonal design for library \mbox{implementors}, obviating the need for workarounds such as @std::reference_wrapper@. 1860 1899 Secondly, \CFA references are rebindable, whereas \CC references have a fixed address. 1861 Rebinding allows \CFA references to be default -initialized (\eg to a null pointer\footnote{1862 While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any non -managed languages (C/\CC), given that it only handles one of many different error situations, \eg using a pointer after its storage is deleted.}) and point to different addresses throughout their lifetime, like pointers.1900 Rebinding allows \CFA references to be default initialized (\eg to a null pointer\footnote{ 1901 While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any nonmanaged languages (C/\CC), given that it only handles one of many different error situations, \eg using a pointer after its storage is deleted.}) and point to different addresses throughout their lifetime, like pointers. 1863 1902 Rebinding is accomplished by extending the existing syntax and semantics of the address-of operator in C. 1864 1903 1865 In C, the address of a lvalue is always a rvalue, as in general that address is not stored anywhere in memory,and does not itself have an address.1866 In \CFA, the address of a @T &@ is a lvalue @T *@, as the address of the underlying @T@ is stored in the reference,and can thus be mutated there.1904 In C, the address of an lvalue is always an rvalue, as, in general, that address is not stored anywhere in memory and does not itself have an address. 1905 In \CFA, the address of a @T &@ is an lvalue @T *@, as the address of the underlying @T@ is stored in the reference and can thus be mutated there. 1867 1906 The result of this rule is that any reference can be rebound using the existing pointer assignment semantics by assigning a compatible pointer into the address of the reference, \eg @&r1 = &x;@ above. 1868 1907 This rebinding occurs to an arbitrary depth of reference nesting; 1869 1908 loosely speaking, nested address-of operators produce a nested lvalue pointer up to the depth of the reference. 1870 1909 These explicit address-of operators can be thought of as ``cancelling out'' the implicit dereference operators, \eg @(&`*`)r1 = &x@ or @(&(&`*`)`*`)r3 = &(&`*`)r1@ or even @(&`*`)r2 = (&`*`)`*`r3@ for @&r2 = &r3@. 1871 More precisely: 1910 The precise rules are 1872 1911 \begin{itemize} 1873 1912 \item 1874 if @R@ is an rvalue of type {@T &@$_1 \cdots$@ &@$_r$} where $r \ge 1$ references (@&@ symbols) then @&R@ has type {@T `*`&@$_{\color{red}2} \cdots$@ &@$_{\color{red}r}$}, \\ \ie @T@ pointer with $r-1$ references (@&@ symbols). 1875 1913 If @R@ is an rvalue of type @T &@$_1\cdots$ @&@$_r$, where $r \ge 1$ references (@&@ symbols), than @&R@ has type @T `*`&@$_{\color{red}2}\cdots$ @&@$_{\color{red}r}$, \ie @T@ pointer with $r-1$ references (@&@ symbols). 1876 1914 \item 1877 if @L@ is an lvalue of type {@T &@$_1 \cdots$@ &@$_l$} where $l \ge 0$ references (@&@ symbols) then @&L@ has type {@T `*`&@$_{\color{red}1} \cdots$@ &@$_{\color{red}l}$}, \\\ie @T@ pointer with $l$ references (@&@ symbols).1915 If @L@ is an lvalue of type @T &@$_1\cdots$ @&@$_l$, where $l \ge 0$ references (@&@ symbols), than @&L@ has type @T `*`&@$_{\color{red}1}\cdots$ @&@$_{\color{red}l}$, \ie @T@ pointer with $l$ references (@&@ symbols). 1878 1916 \end{itemize} 1879 Since pointers and references share the same internal representation, code using either is equally performant; in fact the \CFA compiler converts references to pointers internally, and the choice between them is made solely on convenience, \eg many pointer or value accesses. 1917 Since pointers and references share the same internal representation, code using either is equally performant; 1918 in fact, the \CFA compiler converts references into pointers internally, and the choice between them is made solely on convenience, \eg many pointer or value accesses. 1880 1919 1881 1920 By analogy to pointers, \CFA references also allow cv-qualifiers such as @const@: … … 1892 1931 There are three initialization contexts in \CFA: declaration initialization, argument/parameter binding, and return/temporary binding. 1893 1932 In each of these contexts, the address-of operator on the target lvalue is elided. 1894 The syntactic motivation is clearest when considering overloaded operator -assignment, \eg @int ?+=?(int &, int)@; given @int x, y@, the expected call syntax is @x += y@, not @&x += y@.1895 1896 More generally, this initialization of references from lvalues rather than pointers is an instance of a ``lvalue-to-reference'' conversion rather than an elision of the address-of operator;1933 The syntactic motivation is clearest when considering overloaded operator assignment, \eg @int ?+=?(int &, int)@; given @int x, y@, the expected call syntax is @x += y@, not @&x += y@. 1934 1935 More generally, this initialization of references from lvalues rather than pointers is an instance of an ``lvalue-to-reference'' conversion rather than an elision of the address-of operator; 1897 1936 this conversion is used in any context in \CFA where an implicit conversion is allowed. 1898 Similarly, use of athe value pointed to by a reference in an rvalue context can be thought of as a ``reference-to-rvalue'' conversion, and \CFA also includes a qualifier-adding ``reference-to-reference'' conversion, analogous to the @T *@ to @const T *@ conversion in standard C.1899 The final reference conversion included in \CFA is ``rvalue-to-reference'' conversion, implemented by means of an implicit temporary.1937 Similarly, use of the value pointed to by a reference in an rvalue context can be thought of as a ``reference-to-rvalue'' conversion, and \CFA also includes a qualifier-adding ``reference-to-reference'' conversion, analogous to the @T *@ to @const T *@ conversion in standard C. 1938 The final reference conversion included in \CFA is an ``rvalue-to-reference'' conversion, implemented by means of an implicit temporary. 1900 1939 When an rvalue is used to initialize a reference, it is instead used to initialize a hidden temporary value with the same lexical scope as the reference, and the reference is initialized to the address of this temporary. 1901 1940 \begin{cfa} … … 1905 1944 f( 3, x + y, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } ); $\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$ 1906 1945 \end{cfa} 1907 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. 1908 \CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const poisoning} problem~\cite{Taylor10}, in which addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers. 1909 1910 1911 \subsection{Type Nesting} 1912 1913 Nested types provide a mechanism to organize associated types and refactor a subset of members into a named aggregate (\eg sub-aggregates @name@, @address@, @department@, within aggregate @employe@). 1914 Java nested types are dynamic (apply to objects), \CC are static (apply to the \lstinline[language=C++]@class@), and C hoists (refactors) nested types into the enclosing scope, meaning there is no need for type qualification. 1915 Since \CFA in not object-oriented, adopting dynamic scoping does not make sense; 1916 instead \CFA adopts \CC static nesting, using the member-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@'' (see Figure~\ref{f:TypeNestingQualification}). 1946 This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of the explicit definition of a temporary variable or the runtime cost of pass-by-value. 1947 \CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const poisoning} problem~\cite{Taylor10}, in which the addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers. 1948 1949 1950 \subsection{Type nesting} 1951 1952 Nested types provide a mechanism to organize associated types and refactor a subset of members into a named aggregate (\eg subaggregates @name@, @address@, @department@, within aggregate @employe@). 1953 Java nested types are dynamic (apply to objects), \CC are static (apply to the \lstinline[language=C++]@class@), and C hoists (refactors) nested types into the enclosing scope, which means there is no need for type qualification. 1954 Since \CFA in not object oriented, adopting dynamic scoping does not make sense; 1955 instead, \CFA adopts \CC static nesting, using the member-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@'' (see Figure~\ref{f:TypeNestingQualification}). 1956 In the C left example, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope. 1957 In the \CFA right example, the types are not hoisted and accessible. 1958 1917 1959 \begin{figure} 1918 1960 \centering 1961 \fontsize{9bp}{11bp}\selectfont\sf 1919 1962 \lstDeleteShortInline@% 1920 1963 \begin{tabular}{@{}l@{\hspace{3em}}l|l@{}} … … 1978 2021 \end{tabular} 1979 2022 \lstMakeShortInline@% 1980 \caption{Type Nesting / Qualification}2023 \caption{Type nesting / qualification} 1981 2024 \label{f:TypeNestingQualification} 2025 \vspace*{-8pt} 1982 2026 \end{figure} 1983 In the C left example, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope. 1984 In the \CFA right example, the types are not hoisted and accessible. 1985 1986 1987 \subsection{Constructors and Destructors} 2027 2028 2029 \vspace*{-8pt} 2030 \subsection{Constructors and destructors} 1988 2031 \label{s:ConstructorsDestructors} 1989 2032 1990 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.2033 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. 1991 2034 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. 1992 \CC addresses these issues using R esource Aquisition Is Initialization (RAII), implemented by means of \newterm{constructor} and \newterm{destructor} functions;2035 \CC addresses these issues using RAII, implemented by means of \newterm{constructor} and \newterm{destructor} functions; 1993 2036 \CFA adopts constructors and destructors (and @finally@) to facilitate RAII. 1994 While constructors and destructors are a common feature of object-oriented programming -languages, they are an independent capability allowing \CFA to adopt them while retaining a procedural paradigm.1995 Specifically, \CFA constructors and destructors are denoted by name and first parameter -type versus name and nesting in an aggregate type.2037 While constructors and destructors are a common feature of object-oriented programming languages, they are an independent capability allowing \CFA to adopt them while retaining a procedural paradigm. 2038 Specifically, \CFA constructors and destructors are denoted by name and first parameter type versus name and nesting in an aggregate type. 1996 2039 Constructor calls seamlessly integrate with existing C initialization syntax, providing a simple and familiar syntax to C programmers and allowing constructor calls to be inserted into legacy C code with minimal code changes. 1997 2040 … … 2002 2045 The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed. 2003 2046 While the first parameter is informally called the @this@ parameter, as in object-oriented languages, any variable name may be used. 2004 Both constructors and destructors allow additional parameters after the @this@ parameter for specifying values for initialization/de -initialization\footnote{2005 Destruction parameters are useful for specifying storage-management actions, such as de -initialize but not deallocate.}.2006 \begin{cfa} 2047 Both constructors and destructors allow additional parameters after the @this@ parameter for specifying values for initialization/deinitialization\footnote{ 2048 Destruction parameters are useful for specifying storage-management actions, such as deinitialize but not deallocate.}. 2049 \begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{11bp}\selectfont\sf] 2007 2050 struct VLA { int size, * data; }; $\C{// variable length array of integers}$ 2008 2051 void ?{}( VLA & vla ) with ( vla ) { size = 10; data = alloc( size ); } $\C{// default constructor}$ … … 2013 2056 \end{cfa} 2014 2057 @VLA@ is a \newterm{managed type}\footnote{ 2015 A managed type affects the runtime environment versus a self-contained type.}: a type requiring a non -trivial constructor or destructor, or with a member of a managed type.2058 A managed type affects the runtime environment versus a self-contained type.}: a type requiring a nontrivial constructor or destructor, or with a member of a managed type. 2016 2059 A managed type is implicitly constructed at allocation and destructed at deallocation to ensure proper interaction with runtime resources, in this case, the @data@ array in the heap. 2017 For details of the code-generation placement of implicit constructor and destructor calls among complex executable statements see~\cite[\S~2.2]{Schluntz17}.2018 2019 \CFA also provides syntax for \newterm{initialization} and \newterm{copy} :2060 For details of the code-generation placement of implicit constructor and destructor calls among complex executable statements, see section~2.2 in the work of Schlintz~\cite{Schluntz17}. 2061 2062 \CFA also provides syntax for \newterm{initialization} and \newterm{copy}. 2020 2063 \begin{cfa} 2021 2064 void ?{}( VLA & vla, int size, char fill = '\0' ) { $\C{// initialization}$ … … 2026 2069 } 2027 2070 \end{cfa} 2028 (Note ,the example is purposely simplified using shallow-copy semantics.)2029 An initialization constructor -call has the same syntax as a C initializer, except the initialization values are passed as arguments to a matching constructor (number and type of paremeters).2071 (Note that the example is purposely simplified using shallow-copy semantics.) 2072 An initialization constructor call has the same syntax as a C initializer, except that the initialization values are passed as arguments to a matching constructor (number and type of parameters). 2030 2073 \begin{cfa} 2031 2074 VLA va = `{` 20, 0 `}`, * arr = alloc()`{` 5, 0 `}`; 2032 2075 \end{cfa} 2033 Note , the use of a \newterm{constructor expression} to initialize the storage from the dynamic storage-allocation.2076 Note the use of a \newterm{constructor expression} to initialize the storage from the dynamic storage allocation. 2034 2077 Like \CC, the copy constructor has two parameters, the second of which is a value parameter with the same type as the first parameter; 2035 2078 appropriate care is taken to not recursively call the copy constructor when initializing the second parameter. … … 2037 2080 \CFA constructors may be explicitly called, like Java, and destructors may be explicitly called, like \CC. 2038 2081 Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of members in user-defined constructors and reuse of existing storage allocations. 2039 Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls :2082 Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls. 2040 2083 \begin{cfa} 2041 2084 { … … 2053 2096 To provide a uniform type interface for @otype@ polymorphism, the \CFA compiler automatically generates a default constructor, copy constructor, assignment operator, and destructor for all types. 2054 2097 These default functions can be overridden by user-generated versions. 2055 For compatibility with the standard behavio ur of C, the default constructor and destructor for all basic, pointer, and reference types do nothing, whilethe copy constructor and assignment operator are bitwise copies;2056 if default zero -initialization is desired, the default constructors can be overridden.2098 For compatibility with the standard behavior of C, the default constructor and destructor for all basic, pointer, and reference types do nothing, whereas the copy constructor and assignment operator are bitwise copies; 2099 if default zero initialization is desired, the default constructors can be overridden. 2057 2100 For user-generated types, the four functions are also automatically generated. 2058 2101 @enum@ types are handled the same as their underlying integral type, and unions are also bitwise copied and no-op initialized and destructed. 2059 2102 For compatibility with C, a copy constructor from the first union member type is also defined. 2060 For @struct@ types, each of the four functions areimplicitly defined to call their corresponding functions on each member of the struct.2061 To better simulate the behavio ur of C initializers, a set of \newterm{member constructors} is also generated for structures.2062 A constructor is generated for each non -empty prefix of a structure's member-list to copy-construct the members passed as parameters and default-construct the remaining members.2103 For @struct@ types, each of the four functions is implicitly defined to call their corresponding functions on each member of the struct. 2104 To better simulate the behavior of C initializers, a set of \newterm{member constructors} is also generated for structures. 2105 A constructor is generated for each nonempty prefix of a structure's member list to copy-construct the members passed as parameters and default-construct the remaining members. 2063 2106 To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all member constructors for that type are hidden from expression resolution; 2064 similarly, the generated default constructor is hidden upon declaration of any constructor.2107 similarly, the generated default constructor is hidden upon the declaration of any constructor. 2065 2108 These semantics closely mirror the rule for implicit declaration of constructors in \CC\cite[p.~186]{ANSI98:C++}. 2066 2109 2067 In some circumstance programmers may not wish to have implicit constructor and destructor generation and calls. 2068 In these cases, \CFA provides the initialization syntax \lstinline|S x `@=` {}|, and the object becomes unmanaged, so implicit constructor and destructor calls are not generated. 2110 In some circumstance, programmers may not wish to have implicit constructor and destructor generation and calls. 2111 In these cases, \CFA provides the initialization syntax \lstinline|S x `@=` {}|, and the object becomes unmanaged; 2112 hence, implicit \mbox{constructor} and destructor calls are not generated. 2069 2113 Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics. 2070 2114 The same syntax can be used in a compound literal, \eg \lstinline|a = (VLA)`@`{ 0, 0x0 }|, to create a C-style literal. 2071 The point of \lstinline|@=| is to provide a migration path from legacy C code to \CFA, by providing a mechanism to incrementally convert to implicit initialization.2115 The point of \lstinline|@=| is to provide a migration path from legacy C code to \CFA, by providing a mechanism to incrementally convert into implicit initialization. 2072 2116 2073 2117 … … 2077 2121 \section{Literals} 2078 2122 2079 C already includes limited polymorphism for literals -- @0@ can be either an integer or a pointer literal, depending on context, whilethe syntactic forms of literals of the various integer and float types are very similar, differing from each other only in suffix.2080 In keeping with the general \CFA approach of adding features while respecting the ``C -style'' of doing things, C's polymorphic constants and typed literal syntax are extended to interoperate with user-defined types, while maintaining a backwards-compatible semantics.2123 C already includes limited polymorphism for literals---@0@ can be either an integer or a pointer literal, depending on context, whereas the syntactic forms of literals of the various integer and float types are very similar, differing from each other only in suffix. 2124 In keeping with the general \CFA approach of adding features while respecting the ``C style'' of doing things, C's polymorphic constants and typed literal syntax are extended to interoperate with user-defined types, while maintaining a backward-compatible semantics. 2081 2125 2082 2126 A simple example is allowing the underscore, as in Ada, to separate prefixes, digits, and suffixes in all \CFA constants, \eg @0x`_`1.ffff`_`ffff`_`p`_`128`_`l@, where the underscore is also the standard separator in C identifiers. 2083 \CC uses a single quote as a separator but it is restricted among digits, precluding its use in the literal prefix or suffix, \eg @0x1.ffff@@`'@@ffffp128l@, and causes problems with most IDEs, which must be extended to deal with this alternate use of the single quote.2127 \CC uses a single quote as a separator, but it is restricted among digits, precluding its use in the literal prefix or suffix, \eg @0x1.ffff@@`'@@ffffp128l@, and causes problems with most integrated development environments (IDEs), which must be extended to deal with this alternate use of the single quote. 2084 2128 2085 2129 … … 2124 2168 2125 2169 In C, @0@ has the special property that it is the only ``false'' value; 2126 by the standard, any value that compares equal to @0@ is false, wh ileany value that compares unequal to @0@ is true.2127 As such, an expression @x@ in any boolean context (such as the condition of an @if@ or @while@ statement, or the arguments to @&&@, @||@, or @?:@\,) can be rewritten as @x != 0@ without changing its semantics.2170 by the standard, any value that compares equal to @0@ is false, whereas any value that compares unequal to @0@ is true. 2171 As such, an expression @x@ in any Boolean context (such as the condition of an @if@ or @while@ statement, or the arguments to @&&@, @||@, or @?:@\,) can be rewritten as @x != 0@ without changing its semantics. 2128 2172 Operator overloading in \CFA provides a natural means to implement this truth-value comparison for arbitrary types, but the C type system is not precise enough to distinguish an equality comparison with @0@ from an equality comparison with an arbitrary integer or pointer. 2129 2173 To provide this precision, \CFA introduces a new type @zero_t@ as the type of literal @0@ (somewhat analagous to @nullptr_t@ and @nullptr@ in \CCeleven); … … 2131 2175 With this addition, \CFA rewrites @if (x)@ and similar expressions to @if ( (x) != 0 )@ or the appropriate analogue, and any type @T@ is ``truthy'' by defining an operator overload @int ?!=?( T, zero_t )@. 2132 2176 \CC makes types truthy by adding a conversion to @bool@; 2133 prior to the addition of explicit cast operators in \CCeleven, this approach had the pitfall of making truthy types transitively convert ableto any numeric type;2177 prior to the addition of explicit cast operators in \CCeleven, this approach had the pitfall of making truthy types transitively convertible into any numeric type; 2134 2178 \CFA avoids this issue. 2135 2179 … … 2142 2186 2143 2187 2144 \subsection{User Literals}2188 \subsection{User literals} 2145 2189 2146 2190 For readability, it is useful to associate units to scale literals, \eg weight (stone, pound, kilogram) or time (seconds, minutes, hours). 2147 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.2191 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. 2148 2192 The backquote is a small character, making the unit (function name) predominate. 2149 For examples, the multi -precision integer-type in Section~\ref{s:MultiPrecisionIntegers} has user literals:2193 For examples, the multiprecision integer type in Section~\ref{s:MultiPrecisionIntegers} has the following user literals. 2150 2194 {\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}} 2151 2195 \begin{cfa} … … 2153 2197 y = "12345678901234567890123456789"|`mp| + "12345678901234567890123456789"|`mp|; 2154 2198 \end{cfa} 2155 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.2199 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. 2156 2200 }% 2157 2201 \begin{cquote} … … 2195 2239 \end{cquote} 2196 2240 2197 The right of Figure~\ref{f:UserLiteral} shows the equivalent \CC version using the underscore for the call -syntax.2241 The right of Figure~\ref{f:UserLiteral} shows the equivalent \CC version using the underscore for the call syntax. 2198 2242 However, \CC restricts the types, \eg @unsigned long long int@ and @long double@ to represent integral and floating literals. 2199 2243 After which, user literals must match (no conversions); … … 2202 2246 \begin{figure} 2203 2247 \centering 2248 \fontsize{9bp}{11bp}\selectfont 2204 2249 \lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}} 2205 2250 \lstDeleteShortInline@% … … 2257 2302 \end{tabular} 2258 2303 \lstMakeShortInline@% 2259 \caption{User Literal}2304 \caption{User literal} 2260 2305 \label{f:UserLiteral} 2261 2306 \end{figure} … … 2265 2310 \label{sec:libraries} 2266 2311 2267 As stated in Section~\ref{sec:poly-fns}, \CFA inherits a large corpus of library code, where other programming languages must rewrite or provide fragile inter -language communication with C.2312 As stated in Section~\ref{sec:poly-fns}, \CFA inherits a large corpus of library code, where other programming languages must rewrite or provide fragile interlanguage communication with C. 2268 2313 \CFA has replacement libraries condensing hundreds of existing C names into tens of \CFA overloaded names, all without rewriting the actual computations. 2269 In many cases, the interface is an inline wrapper providing overloading during compilation but zero cost at runtime.2314 In many cases, the interface is an inline wrapper providing overloading during compilation but of zero cost at runtime. 2270 2315 The following sections give a glimpse of the interface reduction to many C libraries. 2271 2316 In many cases, @signed@/@unsigned@ @char@, @short@, and @_Complex@ functions are available (but not shown) to ensure expression computations remain in a single type, as conversions can distort results. … … 2275 2320 2276 2321 C library @limits.h@ provides lower and upper bound constants for the basic types. 2277 \CFA name overloading is used to condense these typed constants , \eg:2322 \CFA name overloading is used to condense these typed constants. 2278 2323 \begin{cquote} 2279 2324 \lstDeleteShortInline@% … … 2294 2339 \lstMakeShortInline@% 2295 2340 \end{cquote} 2296 The result is a significant reduction in names to access typed constants , \eg:2341 The result is a significant reduction in names to access typed constants. 2297 2342 \begin{cquote} 2298 2343 \lstDeleteShortInline@% … … 2320 2365 2321 2366 C library @math.h@ provides many mathematical functions. 2322 \CFA function overloading is used to condense these mathematical functions , \eg:2367 \CFA function overloading is used to condense these mathematical functions. 2323 2368 \begin{cquote} 2324 2369 \lstDeleteShortInline@% … … 2339 2384 \lstMakeShortInline@% 2340 2385 \end{cquote} 2341 The result is a significant reduction in names to access math functions , \eg:2386 The result is a significant reduction in names to access math functions. 2342 2387 \begin{cquote} 2343 2388 \lstDeleteShortInline@% … … 2358 2403 \lstMakeShortInline@% 2359 2404 \end{cquote} 2360 While \Celeven has type-generic math ~\cite[\S~7.25]{C11}in @tgmath.h@ to provide a similar mechanism, these macros are limited, matching a function name with a single set of floating type(s).2405 While \Celeven has type-generic math (see section~7.25 of the ISO/IEC 9899\cite{C11}) in @tgmath.h@ to provide a similar mechanism, these macros are limited, matching a function name with a single set of floating type(s). 2361 2406 For example, it is impossible to overload @atan@ for both one and two arguments; 2362 instead the names @atan@ and @atan2@ are required (see Section~\ref{s:NameOverloading}).2363 The key observation is that only a restricted set of type-generic macros areprovided for a limited set of function names, which do not generalize across the type system, as in \CFA.2407 instead, the names @atan@ and @atan2@ are required (see Section~\ref{s:NameOverloading}). 2408 The key observation is that only a restricted set of type-generic macros is provided for a limited set of function names, which do not generalize across the type system, as in \CFA. 2364 2409 2365 2410 … … 2367 2412 2368 2413 C library @stdlib.h@ provides many general functions. 2369 \CFA function overloading is used to condense these utility functions , \eg:2414 \CFA function overloading is used to condense these utility functions. 2370 2415 \begin{cquote} 2371 2416 \lstDeleteShortInline@% … … 2386 2431 \lstMakeShortInline@% 2387 2432 \end{cquote} 2388 The result is a significant reduction in names to access utility functions, \eg:2433 The result is a significant reduction in names to access the utility functions. 2389 2434 \begin{cquote} 2390 2435 \lstDeleteShortInline@% … … 2405 2450 \lstMakeShortInline@% 2406 2451 \end{cquote} 2407 In addit on, there are polymorphic functions, like @min@ and @max@, that work on any type with operators@?<?@ or @?>?@.2452 In addition, there are polymorphic functions, like @min@ and @max@, that work on any type with operator @?<?@ or @?>?@. 2408 2453 2409 2454 The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety. 2410 C/\Celeven provide a number of complex and overlapping storage-management operation to support the following capabilities:2411 \begin{ description}%[topsep=3pt,itemsep=2pt,parsep=0pt]2455 C/\Celeven provide a number of complex and overlapping storage-management operations to support the following capabilities. 2456 \begin{list}{}{\itemsep=0pt\parsep=0pt\labelwidth=0pt\leftmargin\parindent\itemindent-\leftmargin\let\makelabel\descriptionlabel} 2412 2457 \item[fill] 2413 2458 an allocation with a specified character. 2414 2459 \item[resize] 2415 2460 an existing allocation to decrease or increase its size. 2416 In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation iscopied.2461 In either case, new storage may or may not be allocated, and if there is a new allocation, as much data from the existing allocation are copied. 2417 2462 For an increase in storage size, new storage after the copied data may be filled. 2463 \newpage 2418 2464 \item[align] 2419 2465 an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes. … … 2421 2467 allocation with a specified number of elements. 2422 2468 An array may be filled, resized, or aligned. 2423 \end{ description}2424 Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation -functions and how all the capabilities can be combined into two \CFA functions.2425 \CFA storage-management functions extend the C equivalents by overloading, providing shallow type -safety, and removing the need to specify the base allocation-size.2426 Figure~\ref{f:StorageAllocation} contrasts \CFA and C storage -allocation performing the same operations with the same type safety.2469 \end{list} 2470 Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation functions and how all the capabilities can be combined into two \CFA functions. 2471 \CFA storage-management functions extend the C equivalents by overloading, providing shallow type safety, and removing the need to specify the base allocation size. 2472 Figure~\ref{f:StorageAllocation} contrasts \CFA and C storage allocation performing the same operations with the same type safety. 2427 2473 2428 2474 \begin{table} 2429 \caption{Storage- Management Operations}2475 \caption{Storage-management operations} 2430 2476 \label{t:StorageManagementOperations} 2431 2477 \centering 2432 2478 \lstDeleteShortInline@% 2433 2479 \lstMakeShortInline~% 2434 \begin{tabular}{@{}r|r|l|l|l|l@{}} 2435 \multicolumn{1}{c}{}& & \multicolumn{1}{c|}{fill} & resize & align & array \\ 2436 \hline 2480 \begin{tabular}{@{}rrllll@{}} 2481 \multicolumn{1}{c}{}& & \multicolumn{1}{c}{fill} & resize & align & array \\ 2437 2482 C & ~malloc~ & no & no & no & no \\ 2438 2483 & ~calloc~ & yes (0 only) & no & no & yes \\ … … 2440 2485 & ~memalign~ & no & no & yes & no \\ 2441 2486 & ~posix_memalign~ & no & no & yes & no \\ 2442 \hline2443 2487 C11 & ~aligned_alloc~ & no & no & yes & no \\ 2444 \hline2445 2488 \CFA & ~alloc~ & yes/copy & no/yes & no & yes \\ 2446 2489 & ~align_alloc~ & yes & no & yes & yes \\ … … 2452 2495 \begin{figure} 2453 2496 \centering 2497 \fontsize{9bp}{11bp}\selectfont 2454 2498 \begin{cfa}[aboveskip=0pt,xleftmargin=0pt] 2455 2499 size_t dim = 10; $\C{// array dimension}$ … … 2489 2533 \end{tabular} 2490 2534 \lstMakeShortInline@% 2491 \caption{\CFA versus C Storage-Allocation}2535 \caption{\CFA versus C storage allocation} 2492 2536 \label{f:StorageAllocation} 2493 2537 \end{figure} 2494 2538 2495 2539 Variadic @new@ (see Section~\ref{sec:variadic-tuples}) cannot support the same overloading because extra parameters are for initialization. 2496 Hence, there are @new@ and @anew@ functions for single and array variables, and the fill value is the arguments to the constructor , \eg:2540 Hence, there are @new@ and @anew@ functions for single and array variables, and the fill value is the arguments to the constructor. 2497 2541 \begin{cfa} 2498 2542 struct S { int i, j; }; … … 2501 2545 S * as = anew( dim, 2, 3 ); $\C{// each array element initialized to 2, 3}$ 2502 2546 \end{cfa} 2503 Note ,\CC can only initialize array elements via the default constructor.2504 2505 Finally, the \CFA memory -allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap.2547 Note that \CC can only initialize array elements via the default constructor. 2548 2549 Finally, the \CFA memory allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap. 2506 2550 When a @realloc@ is performed, the sticky properties are respected, so that new storage is correctly aligned and initialized with the fill character. 2507 2551 … … 2510 2554 \label{s:IOLibrary} 2511 2555 2512 The goal of \CFA I/O is to simplify the common cases, while fully supporting polymorphism and user defined types in a consistent way.2556 The goal of \CFA I/O is to simplify the common cases, while fully supporting polymorphism and user-defined types in a consistent way. 2513 2557 The approach combines ideas from \CC and Python. 2514 2558 The \CFA header file for the I/O library is @fstream@. … … 2539 2583 \lstMakeShortInline@% 2540 2584 \end{cquote} 2541 The \CFA form has half the characters of the \CC form ,and is similar to Python I/O with respect to implicit separators.2585 The \CFA form has half the characters of the \CC form and is similar to Python I/O with respect to implicit separators. 2542 2586 Similar simplification occurs for tuple I/O, which prints all tuple values separated by ``\lstinline[showspaces=true]@, @''. 2543 2587 \begin{cfa} … … 2572 2616 \lstMakeShortInline@% 2573 2617 \end{cquote} 2574 There is a weak similarity between the \CFA logical-or operator and the Shell pipe -operator for moving data, where data flows in the correct direction for input butthe opposite direction for output.2618 There is a weak similarity between the \CFA logical-or operator and the Shell pipe operator for moving data, where data flow in the correct direction for input but in the opposite direction for output. 2575 2619 \begin{comment} 2576 2620 The implicit separator character (space/blank) is a separator not a terminator. … … 2593 2637 \end{itemize} 2594 2638 \end{comment} 2595 There are functions to set and get the separator string ,and manipulators to toggle separation on and off in the middle of output.2596 2597 2598 \subsection{Multi -precision Integers}2639 There are functions to set and get the separator string and manipulators to toggle separation on and off in the middle of output. 2640 2641 2642 \subsection{Multiprecision integers} 2599 2643 \label{s:MultiPrecisionIntegers} 2600 2644 2601 \CFA has an interface to the G MP multi-precision signed-integers~\cite{GMP}, similar to the \CC interface provided by GMP.2602 The \CFA interface wraps GMP functions into operator functions to make programming with multi -precision integers identical to using fixed-sized integers.2603 The \CFA type name for multi -precision signed-integers is @Int@ and the header file is @gmp@.2604 Figure~\ref{f:GMPInterface} shows a multi -precision factorial-program contrasting the GMP interface in \CFA and C.2605 2606 \begin{figure} 2645 \CFA has an interface to the GNU multiple precision (GMP) signed integers~\cite{GMP}, similar to the \CC interface provided by GMP. 2646 The \CFA interface wraps GMP functions into operator functions to make programming with multiprecision integers identical to using fixed-sized integers. 2647 The \CFA type name for multiprecision signed integers is @Int@ and the header file is @gmp@. 2648 Figure~\ref{f:GMPInterface} shows a multiprecision factorial program contrasting the GMP interface in \CFA and C. 2649 2650 \begin{figure}[b] 2607 2651 \centering 2652 \fontsize{9bp}{11bp}\selectfont 2608 2653 \lstDeleteShortInline@% 2609 2654 \begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}} … … 2636 2681 \end{tabular} 2637 2682 \lstMakeShortInline@% 2638 \caption{GMP Interface \CFA versus C}2683 \caption{GMP interface \CFA versus C} 2639 2684 \label{f:GMPInterface} 2640 2685 \end{figure} 2641 2686 2642 2687 2688 \vspace{-4pt} 2643 2689 \section{Polymorphism Evaluation} 2644 2690 \label{sec:eval} … … 2649 2695 % Though \CFA provides significant added functionality over C, these features have a low runtime penalty. 2650 2696 % In fact, it is shown that \CFA's generic programming can enable faster runtime execution than idiomatic @void *@-based C code. 2651 The experiment is a set of generic-stack micro -benchmarks~\cite{CFAStackEvaluation} in C, \CFA, and \CC (see implementations in Appendix~\ref{sec:BenchmarkStackImplementations}).2697 The experiment is a set of generic-stack microbenchmarks~\cite{CFAStackEvaluation} in C, \CFA, and \CC (see implementations in Appendix~\ref{sec:BenchmarkStackImplementations}). 2652 2698 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. 2653 2699 A more illustrative comparison measures the costs of idiomatic usage of each language's features. 2654 Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked -list.2700 Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked list. 2655 2701 The benchmark test is similar for the other languages. 2656 2702 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. 2657 2703 2658 2704 \begin{figure} 2705 \fontsize{9bp}{11bp}\selectfont 2659 2706 \begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt] 2660 2707 int main() { … … 2676 2723 } 2677 2724 \end{cfa} 2678 \caption{\protect\CFA Benchmark Test}2725 \caption{\protect\CFA benchmark test} 2679 2726 \label{fig:BenchmarkTest} 2727 \vspace*{-10pt} 2680 2728 \end{figure} 2681 2729 2682 The structure of each benchmark implemented is :C with @void *@-based polymorphism, \CFA with parametric polymorphism, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.2730 The structure of each benchmark implemented is C with @void *@-based polymorphism, \CFA with parametric polymorphism, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV. 2683 2731 The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface; 2684 hence runtime checks are necessary to safely down-cast objects.2685 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, wh ile C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.2686 Note , the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.2732 hence, runtime checks are necessary to safely downcast objects. 2733 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, whereas C and \CCV lack such capability and, instead, must store generic objects via pointers to separately allocated objects. 2734 Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA and \CC provide type safety statically. 2687 2735 2688 2736 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. 2689 The graph plots the median of 5consecutive runs of each program, with an initial warm-up run omitted.2737 The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted. 2690 2738 All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen. 2691 2739 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. … … 2693 2741 \begin{figure} 2694 2742 \centering 2695 \ input{timing}2696 \caption{Benchmark Timing Results (smaller is better)}2743 \resizebox{0.7\textwidth}{!}{\input{timing}} 2744 \caption{Benchmark timing results (smaller is better)} 2697 2745 \label{fig:eval} 2746 \vspace*{-10pt} 2698 2747 \end{figure} 2699 2748 2700 2749 \begin{table} 2750 \vspace*{-10pt} 2701 2751 \caption{Properties of benchmark code} 2702 2752 \label{tab:eval} 2703 2753 \centering 2754 \vspace*{-4pt} 2704 2755 \newcommand{\CT}[1]{\multicolumn{1}{c}{#1}} 2705 \begin{tabular}{ rrrrr}2706 & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ \hline2707 maximum memory usage (MB) & 10 ,001 & 2,502 & 2,503 & 11,253 \\2756 \begin{tabular}{lrrrr} 2757 & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ 2758 maximum memory usage (MB) & 10\,001 & 2\,502 & 2\,503 & 11\,253 \\ 2708 2759 source code size (lines) & 201 & 191 & 125 & 294 \\ 2709 2760 redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ 2710 2761 binary size (KB) & 14 & 257 & 14 & 37 \\ 2711 2762 \end{tabular} 2763 \vspace*{-16pt} 2712 2764 \end{table} 2713 2765 2714 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; 2766 \enlargethispage{-10pt} 2767 The C and \CCV variants are generally the slowest with the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types; 2715 2768 this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. 2716 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair because of equivalent storage layout, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.2717 \CCV is slower than C largely due to the cost of runtime type -checking of down-casts (implemented with @dynamic_cast@);2769 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead. 2770 \CCV is slower than C largely due to the cost of runtime type checking of downcasts (implemented with @dynamic_cast@). 2718 2771 The outlier for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code. 2719 2772 The gcc compiler is unable to optimize some dead code and condense nested calls; … … 2721 2774 Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries. 2722 2775 2723 \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.2776 \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, although it should be noted that \CFA and \CC have prewritten 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. 2724 2777 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. 2725 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.2726 \CCV does not use the \CC standard template library by construction , and in factincludes 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;2778 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. 2779 \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; 2727 2780 with their omission, the \CCV line count is similar to C. 2728 2781 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. 2729 2782 2730 Line -count is a fairly rough measure of code complexity;2731 another important factor is how much type information the programmer must specify manually, especially where that information is not compiler -checked.2732 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 un-type-checked downcasts, \eg @object@ to @integer@ when popping a stack.2783 Line count is a fairly rough measure of code complexity; 2784 another important factor is how much type information the programmer must specify manually, especially where that information is not compiler checked. 2785 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 un-type-checked downcasts, \eg @object@ to @integer@ when popping a stack. 2733 2786 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. 2734 The \CC benchmark uses two redundant type annotations to create a new stack nodes, wh ilethe C and \CCV benchmarks have several such annotations spread throughout their code.2787 The \CC benchmark uses two redundant type annotations to create a new stack nodes, whereas the C and \CCV benchmarks have several such annotations spread throughout their code. 2735 2788 The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}. 2736 2789 2737 We conjecture these results scale across most generic data-types as the underlying polymorphism implement is constant. 2738 2739 2790 We conjecture that these results scale across most generic data types as the underlying polymorphism implement is constant. 2791 2792 2793 \vspace*{-8pt} 2740 2794 \section{Related Work} 2741 2795 \label{s:RelatedWork} … … 2753 2807 \CC provides three disjoint polymorphic extensions to C: overloading, inheritance, and templates. 2754 2808 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. 2755 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.2809 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. 2756 2810 The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed type properties. 2757 Until \CC concepts~\cite{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way to specifythe requirements of a generic function beyond compilation errors during template expansion;2811 Until \CC concepts~\cite{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way of specifying the requirements of a generic function beyond compilation errors during template expansion; 2758 2812 furthermore, \CC concepts are restricted to template polymorphism. 2759 2813 2760 2814 Cyclone~\cite{Grossman06} also provides capabilities for polymorphic functions and existential types, similar to \CFA's @forall@ functions and generic types. 2761 Cyclone existential types can include function pointers in a construct similar to a virtual function -table, but these pointers must be explicitly initialized at some point in the code,a tedious and potentially error-prone process.2815 Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, which is a tedious and potentially error-prone process. 2762 2816 Furthermore, Cyclone's polymorphic functions and types are restricted to abstraction over types with the same layout and calling convention as @void *@, \ie only pointer types and @int@. 2763 2817 In \CFA terms, all Cyclone polymorphism must be dtype-static. 2764 2818 While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model. 2765 Smith and Volpano~\cite{Smith98} present Polymorphic C, an ML dialect with polymorphic functions, C-like syntax, and pointer types; it lacks many of C's features, however, most notably structure types, and so is not a practical C replacement. 2819 Smith and Volpano~\cite{Smith98} present Polymorphic C, an ML dialect with polymorphic functions, C-like syntax, and pointer types; 2820 it lacks many of C's features, most notably structure types, and hence, is not a practical C replacement. 2766 2821 2767 2822 Objective-C~\cite{obj-c-book} is an industrially successful extension to C. 2768 However, Objective-C is a radical departure from C, using an object-oriented model with message -passing.2823 However, Objective-C is a radical departure from C, using an object-oriented model with message passing. 2769 2824 Objective-C did not support type-checked generics until recently \cite{xcode7}, historically using less-efficient runtime checking of object types. 2770 The GObject~\cite{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage -collection to C;2771 these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference -counting.2772 Vala~\cite{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code -bases.2773 Java~\cite{Java8} included generic types in Java~5, which are type -checked at compilation and type-erased at runtime, similar to \CFA's.2774 However, in Java, each object carries its own table of method pointers, wh ile\CFA passes the method pointers separately to maintain a C-compatible layout.2825 The GObject~\cite{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage collection to C; 2826 these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference counting. 2827 Vala~\cite{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code bases. 2828 Java~\cite{Java8} included generic types in Java~5, which are type checked at compilation and type erased at runtime, similar to \CFA's. 2829 However, in Java, each object carries its own table of method pointers, whereas \CFA passes the method pointers separately to maintain a C-compatible layout. 2775 2830 Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens. 2776 2831 2777 D~\cite{D}, Go, and Rust~\cite{Rust} are modern , compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Goand \emph{traits} in Rust.2832 D~\cite{D}, Go, and Rust~\cite{Rust} are modern compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go, and \emph{traits} in Rust. 2778 2833 However, each language represents a significant departure from C in terms of language model, and none has the same level of compatibility with C as \CFA. 2779 2834 D and Go are garbage-collected languages, imposing the associated runtime overhead. 2780 2835 The necessity of accounting for data transfer between managed runtimes and the unmanaged C runtime complicates foreign-function interfaces to C. 2781 2836 Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more. 2782 D restricts garbage collection to its own heap by default, wh ile Rust is not garbage-collected, and thushas a lighter-weight runtime more interoperable with C.2837 D restricts garbage collection to its own heap by default, whereas Rust is not garbage collected and, thus, has a lighter-weight runtime more interoperable with C. 2783 2838 Rust also possesses much more powerful abstraction capabilities for writing generic code than Go. 2784 On the other hand, Rust's borrow -checker provides strong safety guarantees but is complex and difficult to learn and imposes a distinctly idiomatic programming style.2839 On the other hand, Rust's borrow checker provides strong safety guarantees but is complex and difficult to learn and imposes a distinctly idiomatic programming style. 2785 2840 \CFA, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source. 2786 2841 2787 2842 2788 \subsection{Tuples/Variadics} 2789 2843 \vspace*{-18pt} 2844 \subsection{Tuples/variadics} 2845 2846 \vspace*{-5pt} 2790 2847 Many programming languages have some form of tuple construct and/or variadic functions, \eg SETL, C, KW-C, \CC, D, Go, Java, ML, and Scala. 2791 2848 SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types. 2792 2849 Tuples in SETL allow subscripting, dynamic expansion, and multiple assignment. 2793 C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types, so the mechanism is type unsafe. 2850 C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types; 2851 thus, the mechanism is type unsafe. 2794 2852 KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL. 2795 2853 The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-member access. 2796 \CCeleven introduced @std::tuple@ as a library variadic template structure.2854 \CCeleven introduced @std::tuple@ as a library variadic-template structure. 2797 2855 Tuples are a generalization of @std::pair@, in that they allow for arbitrary length, fixed-size aggregation of heterogeneous values. 2798 2856 Operations include @std::get<N>@ to extract values, @std::tie@ to create a tuple of references used for assignment, and lexicographic comparisons. 2799 \CCseventeen proposes \emph{structured bindings}~\cite{Sutter15} to eliminate pre -declaring variables anduse of @std::tie@ for binding the results.2800 This extension requires the use of @auto@ to infer the types of the new variables , so complicated expressions with a non-obvious type must be documented with some other mechanism.2857 \CCseventeen proposes \emph{structured bindings}~\cite{Sutter15} to eliminate predeclaring variables and the use of @std::tie@ for binding the results. 2858 This extension requires the use of @auto@ to infer the types of the new variables; hence, complicated expressions with a nonobvious type must be documented with some other mechanism. 2801 2859 Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables. 2802 2860 Like \CC, D provides tuples through a library variadic-template structure. 2803 2861 Go does not have tuples but supports MRVF. 2804 Java's variadic functions appear similar to C's but are type -safe using homogeneous arrays, which are less useful than \CFA's heterogeneously-typed variadic functions.2862 Java's variadic functions appear similar to C's but are type safe using homogeneous arrays, which are less useful than \CFA's heterogeneously typed variadic functions. 2805 2863 Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml}, Haskell, and Scala~\cite{Scala}, which decompose tuples using pattern matching. 2806 2864 2807 2865 2866 \vspace*{-18pt} 2808 2867 \subsection{C Extensions} 2809 2868 2810 \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. 2811 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. 2869 \vspace*{-5pt} 2870 \CC is the best known C-based language and is similar to \CFA in that both are extensions to C with source and runtime backward compatibility. 2871 Specific differences 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. 2812 2872 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. 2813 2873 \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. 2814 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.2815 2816 There are several other C extension -languages with less usage and even more dramatic changes than \CC.2817 Objective-Cand Cyclone are two other extensions to C with different design goals than \CFA, as discussed above.2874 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. 2875 2876 There are several other C extension languages with less usage and even more dramatic changes than \CC. 2877 \mbox{Objective-C} and Cyclone are two other extensions to C with different design goals than \CFA, as discussed above. 2818 2878 Other languages extend C with more focused features. 2819 2879 $\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; 2820 data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, wh ileconcurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}.2821 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 backward scompatibility goals.2880 data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, whereas concurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}. 2881 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 backward compatibility goals. 2822 2882 2823 2883 2824 2884 \section{Conclusion and Future Work} 2825 2885 2826 The goal of \CFA is to provide an evolutionary pathway for large C development -environments to be more productive and safer, while respecting the talent and skill of C programmers.2827 While other programming languages purport to be a better C, they are in factnew and interesting languages in their own right, but not C extensions.2828 The purpose of this paper is to introduce \CFA, and showcase language features that illustrate the \CFA type -system and approaches taken to achieve the goal of evolutionary C extension.2829 The contributions are a powerful type -system using parametric polymorphism and overloading, generic types, tuples, advanced control structures, and extended declarations, which all have complex interactions.2886 The goal of \CFA is to provide an evolutionary pathway for large C development environments to be more productive and safer, while respecting the talent and skill of C programmers. 2887 While other programming languages purport to be a better C, they are, in fact, new and interesting languages in their own right, but not C extensions. 2888 The purpose of this paper is to introduce \CFA, and showcase language features that illustrate the \CFA type system and approaches taken to achieve the goal of evolutionary C extension. 2889 The contributions are a powerful type system using parametric polymorphism and overloading, generic types, tuples, advanced control structures, and extended declarations, which all have complex interactions. 2830 2890 The work is a challenging design, engineering, and implementation exercise. 2831 2891 On the surface, the project may appear as a rehash of similar mechanisms in \CC. 2832 2892 However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation. 2833 All of these new features are being used by the \CFA development -team to build the \CFA runtime-system.2893 All of these new features are being used by the \CFA development team to build the \CFA runtime system. 2834 2894 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 2835 2895 2836 While all examples in the paper compile and run, a public beta-release of \CFA will take 6--8 months to reduce compilation time, provide better debugging, and add a few more libraries. 2837 There is also new work on a number of \CFA features, including arrays with size, runtime type-information, virtual functions, user-defined conversions, and modules. 2838 While \CFA polymorphic functions use dynamic virtual-dispatch with low runtime overhead (see Section~\ref{sec:eval}), it is not as low as \CC template-inlining. 2839 Hence it may be beneficial to provide a mechanism for performance-sensitive code. 2840 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization). 2841 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat. 2842 In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code. 2896 While all examples in the paper compile and run, there are ongoing efforts to reduce compilation time, provide better debugging, and add more libraries; 2897 when this work is complete in early 2019, a public beta release will be available at \url{https://github.com/cforall/cforall}. 2898 There is also new work on a number of \CFA features, including arrays with size, runtime type information, virtual functions, user-defined conversions, and modules. 2899 While \CFA polymorphic functions use dynamic virtual dispatch with low runtime overhead (see Section~\ref{sec:eval}), it is not as low as \CC template inlining. 2900 Hence, it may be beneficial to provide a mechanism for performance-sensitive code. 2901 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function definitions to instantiate a specialized version for some set of types (\CC template specialization). 2902 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat. 2903 In general, we believe separate compilation, producing smaller code, works well with loaded hardware caches, which may offset the benefit of larger inlined code. 2843 2904 2844 2905 2845 2906 \section{Acknowledgments} 2846 2907 2847 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.2848 Funding for this project has been provided by 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.2908 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. 2909 Funding for this project was provided by Huawei Ltd (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr were partially funded by the Natural Sciences and Engineering Research Council of Canada. 2849 2910 2850 2911 {% 2851 2912 \fontsize{9bp}{12bp}\selectfont% 2913 \vspace*{-3pt} 2852 2914 \bibliography{pl} 2853 2915 }% … … 2928 2990 2929 2991 2992 \enlargethispage{1000pt} 2930 2993 \subsection{\CFA} 2931 2994 \label{s:CforallStack} … … 2994 3057 2995 3058 3059 \newpage 2996 3060 \subsection{\CC} 2997 3061
Note:
See TracChangeset
for help on using the changeset viewer.