Context Navigation

-                      r72a5a75
+                      r5346dce
 \author[1]{Robert Schluntz}
 \author[1]{Peter A. Buhr}
-\author[]{\textcolor{blue}{Q1 AUTHOR NAMES CORRECT}}
 \authormark{MOSS \textsc{et al}}
 …
 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.
 This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more.
 Nevertheless, C, which was first standardized almost 30 \textcolor{blue}{CHANGE ``40'' TO ``30''} years ago, lacks many features that make programming in more modern languages safer and more productive.
+Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive.
 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.
 Prior projects have attempted similar goals but failed to honor the C programming style;
 …
+\vspace*{-10pt}
 \section{Introduction}
 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.
 This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more.
 The TIOBE index~\cite{TIOBE} \textcolor{blue}{CHANGE ``TIOBE'' TO ``The TIOBE index''} 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.
+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.
 The top three rankings over the past 30 years are as follows.
-\newpage
-\textcolor{blue}{MOVE TABLE HERE}
 \begin{center}
 \setlength{\tabcolsep}{10pt}
 …
 \lstMakeShortInline@%
 \end{center}
 Love it or hate it, C is extremely popular, highly used, and one of the few systems languages.
 In many cases, \CC is often used solely as a better C.
 Nevertheless, C, which was first standardized almost 30 \textcolor{blue}{CHANGE ``40'' TO ``30''} years ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive.
+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.
 \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.
 …
 ultimately, a compiler is necessary for advanced features and optimal performance.
 % 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.
 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 C code for a C compiler that supports none of these features.
+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.
 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.
 % @plg2[8]% cd cfa-cc/src; cloc libcfa
 …
 Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C.
 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.
+\textcolor{blue}{REMOVE ``We have the following as an example''}
 \newpage
-\textcolor{blue}{UPDATE FOLLOWING PROGRAM EXAMPLE WITH ADJUSTED COMMENTS TO FIT PAGE WIDTH.}
 \begin{cfa}
 int max = 2147483647;                                           $\C[4in]{// (1)}$
 …
 In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
 In the above, the name @max@ has a consistent meaning, and a programmer only needs to remember the single concept: maximum.
 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).
+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).
 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.
 …
 \label{sec:poly-fns}
 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). \textcolor{blue}{REMOVE ``as follows''}
+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).
 \begin{cfa}
 `forall( otype T )` T identity( T val ) { return val; }
 …
 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.
 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading. \textcolor{blue}{REMOVE ``as follows''}
+For example, the function @twice@ can be defined using the \CFA syntax for operator overloading.
 \begin{cfa}
 forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; }  $\C{// ? denotes operands}$
 …
 Crucial to the design of a new programming language are the libraries to access thousands of external software features.
 Like \CC, \CFA inherits a massive compatible library base, where other programming languages must rewrite or provide fragile interlanguage communication with C.
 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array. \textcolor{blue}{REMOVE ``as follows''}
+A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array.
 \begin{cfa}
 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
 …
 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.
 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.
 For example, the concrete instantiation for @pair( const char *, int )@ is \textcolor{blue}{REMOVE ``as follows.''}
+For example, the concrete instantiation for @pair( const char *, int )@ is
 \begin{cfa}
 struct _pair_conc0 {
 …
 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;
 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.
 As an example, the body of the second @value@ function is implemented as \textcolor{blue}{REMOVE ``follows.''}
+As an example, the body of the second @value@ function is implemented as
 \begin{cfa}
 _assign_T( _retval, p + _offsetof_pair[1] ); $\C{// return *p.second}$
 …
 \newpage
 \noindent
 \textcolor{blue}{NO PARAGRAPH INDENT} 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.
+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.
 @_offsetof_pair@ is the offset array passed into @value@;
 this array is generated at the call site as \textcolor{blue}{REMOVE ``follows.''}
+this array is generated at the call site as
 \begin{cfa}
 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) }
 …
 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag structures}.
 Sometimes, information is only used for type checking and can be omitted at runtime. \textcolor{blue}{REMOVE ``As an example, we have the following''}
+Sometimes, information is only used for type checking and can be omitted at runtime.
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 Both approaches are awkward.
 % FIX
 Alternatively, a programming language can directly support returning multiple values, \eg \CFA provides the following. \textcolor{blue}{REPLACE ``in \CFA, we have the following'' WITH ``\CFA provides the following''}
+Alternatively, a programming language can directly support returning multiple values, \eg \CFA provides the following.
 \begin{cfa}
 [ int, int ] div( int num, int den );           $\C{// return two integers}$
 …
 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}.
 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. \textcolor{blue}{REPLACE ``As an example, we have the following'' WITH ``\CFA provides the following''}
+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.
 \begin{cfa}
 printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
 …
 printf( "%d %d\n", qr );
 \end{cfa}
 \CFA also supports \newterm{tuple indexing} to access single components of a tuple expression. \textcolor{blue}{REMOVE ``as follows''}
+\CFA also supports \newterm{tuple indexing} to access single components of a tuple expression.
 \begin{cfa}
 [int, int] * p = &qr;                                           $\C{// tuple pointer}$
 …
 In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as two arguments.
 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@.
 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 \textcolor{blue}{CHANGE ``components'' TO ``component''} of @x@ and @y@ are structured into the second argument of type @[int, int]@.
 The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both SRVFs and MRVFs \textcolor{blue}{REMOVE ``and''} with any number of arguments of arbitrarily complex structure.
+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]@.
+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.
 \subsection{Tuple assignment}
+\enlargethispage{-10pt}
 An assignment where the left side is a tuple type is called \newterm{tuple assignment}.
 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.
 …
 Both kinds of tuple assignment have parallel semantics, so that each value on the left and right sides is evaluated before any assignments occur.
 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]@.
+This semantics means mass assignment differs from C cascading
+\newpage
+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.
+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.
 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@.
 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.
 …
 [int, int, int] y = x.[2, 0, 2];                        $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
 \end{cfa}
 It is also possible for a member access to contain other member accesses. \textcolor{blue}{REMOVE ``, as follows.''}
+It is also possible for a member access to contain other member accesses.
 \begin{cfa}
 struct A { double i; int j; };
 …
 Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful.
 Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
 For example, the following is a \textcolor{blue}{CHANGE ``As an example, we have the following'' TO ``For example, the following is a''} generalized @sum@ function.
+For example, the following is a generalized @sum@ function.
 \begin{cfa}
 int sum$\(_0\)$() { return 0; }
 …
 Unlike C variadic functions, it is unnecessary to hard code the number and expected types.
 Furthermore, this code is extendable for any user-defined type with a @?+?@ operator.
 Summing \textcolor{blue}{REMOVE ``up''} arbitrary heterogeneous lists is possible with similar code by adding the appropriate type variables and addition operators.
+Summing arbitrary heterogeneous lists is possible with similar code by adding the appropriate type variables and addition operators.
 It is also possible to write a type-safe variadic print function to replace @printf@:
 …
 Tuples are implemented in the \CFA translator via a transformation into \newterm{generic types}.
 For each $N$, the first time an $N$-tuple is seen in a scope, a generic type with $N$ type parameters is generated.
 For example, the following \textcolor{blue}{CHANGE ``, as follows:'' TO ``For example, the following''}
+For example, the following
 \begin{cfa}
 [int, int] f() {
 …
 \end{cfa}
 \textcolor{blue}{PARAGRAPH INDENT} Finally, \CFA provides a Java-like  @finally@ clause after the catch clauses.
+Finally, \CFA provides a Java-like  @finally@ clause after the catch clauses.
 \begin{cfa}
 try {
 …
 C declaration syntax is notoriously confusing and error prone.
 For example, many C programmers are confused by a declaration as simple as the following. \textcolor{blue}{CHANGE ``simple a declaration as in'' TO ``declaration as simple as''}
+For example, many C programmers are confused by a declaration as simple as the following.
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 % 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.
 However, unlike C, \CFA type declaration tokens are distributed across all variables in the declaration list.
 For instance, variables @x@ and @y@ of type pointer to integer are defined in \CFA as \textcolor{blue}{REMOVE ``follows.''}
+For instance, variables @x@ and @y@ of type pointer to integer are defined in \CFA as
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 Since \CFA in not object oriented, adopting dynamic scoping does not make sense;
 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}).
+In the C left example, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope.
+In the \CFA right example, the types are not hoisted and accessible.
 \begin{figure}
 …
 \vspace*{-8pt}
 \end{figure}
-In the C left example, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope.
-In the \CFA right example, the types are not hoisted and accessible.
 …
 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}.
 \CFA also provides syntax for \newterm{initialization} and \newterm{copy}. \textcolor{blue}{REMOVE ``, as follows''}
+\CFA also provides syntax for \newterm{initialization} and \newterm{copy}.
 \begin{cfa}
 void ?{}( VLA & vla, int size, char fill = '\0' ) {  $\C{// initialization}$
 …
 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.
 \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 \textcolor{blue}{Q2 CHANGE ``IDEs'' TO ``integrated development environments (IDEs)''}, which must be extended to deal with this alternate use of the single quote.
+\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.
 …
 y = "12345678901234567890123456789"|`mp| + "12345678901234567890123456789"|`mp|;
 \end{cfa}
 Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions, where @?`@ \textcolor{blue}{USE CHARACTER \lstinline@`@ NOT \textsf{'}} denotes a postfix-function name and @`@ \textcolor{blue}{USE CHARACTER \lstinline@`@ NOT `} denotes a postfix-function call.
+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.
 }%
 \begin{cquote}
 …
 \lstMakeShortInline@%
 \end{cquote}
 The result is a significant reduction in names to access typed constants. \textcolor{blue}{REMOVE ``, as follows.''}
+The result is a significant reduction in names to access typed constants.
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 \lstMakeShortInline@%
 \end{cquote}
 The result is a significant reduction in names to access math functions. \textcolor{blue}{REMOVE ``, as follows.''}
+The result is a significant reduction in names to access math functions.
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 \lstMakeShortInline@%
 \end{cquote}
 The result is a significant reduction in names to access the utility functions. \textcolor{blue}{REMOVE ``, as follows.''}
+The result is a significant reduction in names to access the utility functions.
 \begin{cquote}
 \lstDeleteShortInline@%
 …
 In addition, there are polymorphic functions, like @min@ and @max@, that work on any type with operator @?<?@ or @?>?@.
 The following shows one example where \CFA \textcolor{blue}{ADD SPACE} \emph{extends} an existing standard C interface to reduce complexity and provide safety.
+The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
 C/\Celeven provide a number of complex and overlapping storage-management operations to support the following capabilities.
 \begin{list}{}{\itemsep=0pt\parsep=0pt\labelwidth=0pt\leftmargin\parindent\itemindent-\leftmargin\let\makelabel\descriptionlabel}
 …
 \label{s:MultiPrecisionIntegers}
 \CFA has an interface to the \textcolor{blue}{Q3 CHANGE ``GMP multiprecision'' TO ``GNU multiple precision (GMP)''} signed integers~\cite{GMP}, similar to the \CC interface provided by GMP.
+\CFA has an interface to the GNU multiple precision (GMP) signed integers~\cite{GMP}, similar to the \CC interface provided by GMP.
 The \CFA interface wraps GMP functions into operator functions to make programming with multiprecision integers identical to using fixed-sized integers.
 The \CFA type name for multiprecision signed integers is @Int@ and the header file is @gmp@.
 …
 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.
 The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted.
 All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen. \textcolor{blue}{CHANGE ``\CC{}fourteen'' TO ``\CCfourteen''}
 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 \textcolor{blue}{REMOVE ``of''} maximum clock frequency.
+All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen.
+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.
 \begin{figure}
 …
 \end{table}
+\enlargethispage{-10pt}
 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;
 this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
 …
 Tuples are a generalization of @std::pair@, in that they allow for arbitrary length, fixed-size aggregation of heterogeneous values.
 Operations include @std::get<N>@ to extract values, @std::tie@ to create a tuple of references used for assignment, and lexicographic comparisons.
 \CCseventeen \textcolor{blue}{CHANGE ``\CC{}seventeen TO ``\CCseventeen''} proposes \emph{structured bindings}~\cite{Sutter15} to eliminate predeclaring variables and the use of @std::tie@ for binding the results.
+\CCseventeen proposes \emph{structured bindings}~\cite{Sutter15} to eliminate predeclaring variables and the use of @std::tie@ for binding the results.
 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.
 Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 5346dce for doc/papers/general

Legend:

doc/papers/general/Paper.tex

Download in other formats: