Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    r28bc8c8 r87555b7  
    267267int m = max( max, -max );                                       $\C{// uses (3) and (1) twice, by matching return type}$
    268268\end{cfa}
     269
    269270\CFA maximizes the ability to reuse names to aggressively address the naming problem.
    270271In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
    … …  
    285286
    286287
    287 \subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}}
     288\subsection{\texorpdfstring{\protect\lstinline{forall} Functions}{forall Functions}}
    288289\label{sec:poly-fns}
    289290
    … …  
    435436One approach is to write bespoke data-structures for each context in which they are needed.
    436437While 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.
    437 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality.
     438A second approach is to use @void *@ based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality.
    438439However, basing all polymorphism on @void *@ eliminates the type-checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is not otherwise needed.
    439440A 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.
    … …  
    507508The offset arrays are statically generated where possible.
    508509If 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;
    509 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. 
    510 As an example, the body of the second @value@ function is implemented like this:
    511 \begin{cfa}
    512 _assign_T(_retval, p + _offsetof_pair[1]); $\C{// return *p.second}$
    513 \end{cfa}
    514 @_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.
     510if 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.
     511As an example, the body of the second @value@ function is implemented as:
     512\begin{cfa}
     513_assign_T( _retval, p + _offsetof_pair[1] ); $\C{// return *p.second}$
     514\end{cfa}
     515@_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.
    515516@_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as:
    516517\begin{cfa}
    517 size_t _offsetof_pair[] = { offsetof(_pair_conc0, first), offsetof(_pair_conc0, second) }
     518size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) }
    518519\end{cfa}
    519520
    … …  
    539540The most important such pattern is using @forall(dtype T) T *@ as a type-checked replacement for @void *@, \eg creating a lexicographic comparison for pairs of pointers used by @bsearch@ or @qsort@:
    540541\begin{cfa}
    541 forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
     542forall( dtype T ) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
    542543        return cmp( a->first, b->first ) ? : cmp( a->second, b->second );
    543544}
    544545\end{cfa}
    545 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 fields of both pairs and the arguments to the comparison function match in type.
     546Since @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 fields of both pairs and the arguments to the comparison function match in type.
    546547
    547548Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    548549Sometimes information is only used for type-checking and can be omitted at runtime, \eg:
    549550\begin{cfa}
    550 forall(dtype Unit) struct scalar { unsigned long value; };
     551forall( dtype Unit ) struct scalar { unsigned long value; };
    551552struct metres {};
    552553struct litres {};
    553554
    554 forall(dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
     555forall( dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
    555556        return (scalar(U)){ a.value + b.value };
    556557}
    … …  
    807808Due 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:
    808809\begin{cfa}
    809 forall(otype T, dtype U) void f( T x, U * y );
     810forall( otype T, dtype U ) void f( T x, U * y );
    810811f( [5, "hello"] );
    811812\end{cfa}
    … …  
    814815For example, a plus operator can be written to add two triples together.
    815816\begin{cfa}
    816 forall(otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
     817forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
    817818        return [x.0 + y.0, x.1 + y.1, x.2 + y.2];
    818819}
    … …  
    825826\begin{cfa}
    826827int f( [int, double], double );
    827 forall(otype T, otype U | { T f( T, U, U ); }) void g( T, U );
     828forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U );
    828829g( 5, 10.21 );
    829830\end{cfa}
    830831Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
    831832This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}.
    832 Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
    833 \begin{cfa}
    834 int _thunk( int _p0, double _p1, double _p2 ) { return f( [_p0, _p1], _p2 ); }
    835 \end{cfa}
    836 so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    837 These thunks take advantage of gcc C nested-functions to produce closures that have the usual function-pointer signature WHAT DOES THIS MEAN???.
     833% Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
     834% \begin{cfa}
     835% int _thunk( int _p0, double _p1, double _p2 ) { return f( [_p0, _p1], _p2 ); }
     836% \end{cfa}
     837% so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
     838% These thunks are generated locally using gcc nested-functions, rather hositing them to the external scope, so they can easily access local state.
    838839
    839840
    … …  
    852853\begin{cfa}
    853854int sum$\(_0\)$() { return 0; }
    854 forall(ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
     855forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
    855856        return x + sum( rest );
    856857}
    … …  
    865866\begin{cfa}
    866867int sum( int x, int y ) { return x + y; }
    867 forall(ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
     868forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
    868869        return sum( x + y, rest );
    869870}
    … …  
    871872One more step permits the summation of any summable type with all arguments of the same type:
    872873\begin{cfa}
    873 trait summable(otype T) {
     874trait summable( otype T ) {
    874875        T ?+?( T, T );
    875876};
    876 forall(otype R | summable( R ) ) R sum( R x, R y ) {
     877forall( otype R | summable( R ) ) R sum( R x, R y ) {
    877878        return x + y;
    878879}
    879 forall(otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
     880forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
    880881        return sum( x + y, rest );
    881882}
    … …  
    888889\begin{cfa}
    889890struct S { int x, y; };
    890 forall(otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {
     891forall( otype T, ttype Params | { void print(T); void print(Params); } ) void print(T arg, Params rest) {
    891892        print(arg);  print(rest);
    892893}
    … …  
    927928is transformed into:
    928929\begin{cfa}
    929 forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
     930forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
    930931        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    931932        T1 field_1;
    … …  
    933934_tuple2(int, int) f() {
    934935        _tuple2(double, double) x;
    935         forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
     936        forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 {
    936937                T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    937938                T1 field_1;
    … …  
    941942}
    942943\end{cfa}
    943 \begin{sloppypar}
     944{\sloppy
    944945Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
    945 \end{sloppypar}
     946\par}%
    946947
    947948\begin{comment}
    … …  
    10041005\section{Control Structures}
    10051006
    1006 \CFA identifies inconsistent, problematic, and missing control structures in C, and extends, modifies, and adds to control structures to increase functionality and safety.
    1007 
    1008 
    1009 \subsection{\texorpdfstring{\LstKeywordStyle{if} Statement}{if Statement}}
     1007\CFA identifies inconsistent, problematic, and missing control structures in C, and extends, modifies, and adds control structures to increase functionality and safety.
     1008
     1009
     1010\subsection{\texorpdfstring{\protect\lstinline{if} Statement}{if Statement}}
    10101011
    10111012The @if@ expression allows declarations, similar to @for@ declaration expression:
    … …  
    10191020
    10201021
    1021 \subsection{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}}
     1022\subsection{\texorpdfstring{\protect\lstinline{switch} Statement}{switch Statement}}
    10221023
    10231024There 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.
    … …  
    10391040\lstMakeShortInline@%
    10401041\end{cquote}
    1041 for a contiguous list:\footnote{gcc provides the same mechanism with awkward syntax, \lstinline@2 ... 42@, where spaces are required around the ellipse.}
     1042for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, because a space is required after a number, otherwise the period is a decimal point.}
    10421043\begin{cquote}
    10431044\lstDeleteShortInline@%
    … …  
    10901091C @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};
    10911092@case@ clauses are made disjoint by the @break@ statement.
    1092 While the ability to fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in many errors from missing @break@ statements.
    1093 For backwards compatibility, \CFA provides a \emph{new} control structure, @choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}).
    1094 
    1095 Collectively, these enhancements reduce programmer burden and increase readability and safety.
     1093While 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.
     1094For backwards 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.
    10961095
    10971096\begin{figure}
    … …  
    11371136\end{figure}
    11381137
    1139 \begin{comment}
    1140 Forgotten @break@ statements at the end of @switch@ cases are a persistent sort of programmer error in C, and the @break@ statements themselves introduce visual clutter and an un-C-like keyword-based block delimiter.
    1141 \CFA addresses this error by introducing a @choose@ statement, which works identically to a @switch@ except that its default end-of-case behaviour is to break rather than to fall through for all non-empty cases.
    1142 Since empty cases like @case 7:@ in @case 7: case 11:@ still have fall-through semantics and explicit @break@ is still allowed at the end of a @choose@ case, many idiomatic uses of @switch@ in standard C can be converted to @choose@ statements by simply changing the keyword.
    1143 Where fall-through is desired for a non-empty case, it can be specified with the new @fallthrough@ statement, making @choose@ equivalently powerful to @switch@, but more concise in the common case where most non-empty cases end with a @break@ statement, as in the example below:
    1144 
    1145 \begin{cfa}
    1146 choose( i ) {
    1147         case 2:
    1148                 printf("even ");
    1149                 fallthrough;
    1150         case 3: case 5: case 7:
    1151                 printf("small prime\n");
    1152         case 4,6,8,9:
    1153                 printf("small composite\n");
    1154         case 13~19:
    1155                 printf("teen\n");
    1156         default:
    1157                 printf("something else\n");
    1158 }
    1159 \end{cfa}
    1160 \end{comment}
    1161 
    1162 
    1163 \subsection{\texorpdfstring{Labelled \LstKeywordStyle{continue} / \LstKeywordStyle{break}}{Labelled continue / break}}
     1138Finally, @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases:
     1139\begin{cquote}
     1140\lstDeleteShortInline@%
     1141\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
     1142\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{non-terminator}}  & \multicolumn{1}{c}{\textbf{target label}}     \\
     1143\begin{cfa}
     1144choose ( ... ) {
     1145  case 3:
     1146        if ( ... ) {
     1147                ... `fallthrough;`  // goto case 4
     1148        } else {
     1149                ...
     1150        }
     1151        // implicit break
     1152  case 4:
     1153\end{cfa}
     1154&
     1155\begin{cfa}
     1156choose ( ... ) {
     1157  case 3:
     1158        ... `fallthrough common;`
     1159  case 4:
     1160        ... `fallthrough common;`
     1161  common:
     1162        ...      // common code for cases 3 and 4
     1163        // implicit break
     1164  case 4:
     1165\end{cfa}
     1166\end{tabular}
     1167\lstMakeShortInline@%
     1168\end{cquote}
     1169The target label may be case @default@.
     1170
     1171Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety.
     1172
     1173
     1174\subsection{\texorpdfstring{Labelled \protect\lstinline{continue} / \protect\lstinline{break}}{Labelled continue / break}}
    11641175
    11651176While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
    … …  
    12701281\subsection{Exception Handling}
    12711282
    1272 The following framework for \CFA exception handling is in place, excluding some run-time type-information and dynamic casts.
     1283The following framework for \CFA exception handling is in place, excluding some runtime type-information and virtual functions.
    12731284\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
    12741285Both 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.
    … …  
    13401351   catch ( IOError err ) { ... }                        $\C{// handler error from other files}$
    13411352\end{cfa}
    1342 where the throw inserts the failing file-handle in the I/O exception.
     1353where the throw inserts the failing file-handle into the I/O exception.
    13431354Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible..
    13441355
    … …  
    13481359resume( $\emph{alternate-stack}$ )
    13491360\end{cfa}
    1350 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task~\cite{Delisle18}.\footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}
    1351 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 handle returns.
    1352 
    1353 To facilitate nonlocal exception, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.
     1361These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task\footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}~\cite{Delisle18}.
     1362Nonlocal 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.
     1363
     1364To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.
    13541365The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks:
    13551366\begin{cquote}
    … …  
    13581369\begin{cfa}
    13591370enable $\emph{exception-type-list}$ {
    1360         // allow non-local resumption
     1371        // allow non-local raise
    13611372}
    13621373\end{cfa}
    … …  
    13641375\begin{cfa}
    13651376disable $\emph{exception-type-list}$ {
    1366         // disallow non-local resumption
     1377        // disallow non-local raise
    13671378}
    13681379\end{cfa}
    … …  
    13751386Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled.
    13761387\begin{cfa}
    1377 void main( mytask & c ) {
    1378         try {
    1379                 enable {                        $\C{// now allow non-local exception delivery}$
     1388void main( mytask & t ) {                                       $\C{// thread starts here}$
     1389        // non-local exceptions disabled
     1390        try {                                                                   $\C{// establish handles for non-local exceptions}$
     1391                enable {                                                        $\C{// allow non-local exception delivery}$
    13801392                        // task body
    13811393                }
    1382         // appropriate catchResume/catch
     1394        // appropriate catchResume/catch handlers
    13831395        }
    13841396}
    … …  
    14001412
    14011413
    1402 \subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}
     1414\subsection{\texorpdfstring{\protect\lstinline{with} Clause / Statement}{with Clause / Statement}}
    14031415\label{s:WithClauseStatement}
    14041416
    … …  
    18001812int & r = *new( int );
    18011813...                                                                                     $\C{// non-null reference}$
    1802 delete &r;
     1814delete &r;                                                                      $\C{// unmanaged (programmer) memory-management}$
    18031815r += 1;                                                                         $\C{// undefined reference}$
    18041816\end{cfa}
    … …  
    19471959Constructor 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.
    19481960
    1949 In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@.
    1950 The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@\footnote{%
     1961In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@\footnote{%
    19511962The symbol \lstinline+^+ is used for the destructor name because it was the last binary operator that could be used in a unary context.}.
     1963The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@.
    19521964Like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @?{}(x, ...)@ or @^{}(x, ...)@.
    19531965The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed.
    … …  
    20712083\subsection{0/1}
    20722084
    2073 In C, @0@ has the special property that it is the only ``false'' value; by the standard, any value which compares equal to @0@ is false, while any value that compares unequal to @0@ is true.
    2074 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.
    2075 The operator overloading feature of \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.
    2076 To provide this precision, \CFA introduces a new type @zero_t@ as type type of literal @0@ (somewhat analagous to @nullptr_t@ and @nullptr@ in \CCeleven); @zero_t@ can only take the value @0@, but has implicit conversions to the integer and pointer types so that C code involving @0@ continues to work properly.
    2077 With this addition, the \CFA compiler rewrites @if (x)@ and similar expressions to @if ((x) != 0)@ or the appropriate analogue, and any type @T@ can be made ``truthy'' by defining an operator overload @int ?!=?(T, zero_t)@.
    2078 \CC makes types truthy by adding a conversion to @bool@; prior to the addition of explicit cast operators in \CCeleven this approach had the pitfall of making truthy types transitively convertable to any numeric type; our design for \CFA avoids this issue.
    2079 
    2080 \CFA also includes a special type for @1@, @one_t@; like @zero_t@, @one_t@ has built-in implicit conversions to the various integral types so that @1@ maintains its expected semantics in legacy code.
    2081 The addition of @one_t@ allows generic algorithms to handle the unit value uniformly for types where that is meaningful.
    2082 \TODO{Make this sentence true} In particular, polymorphic functions in the \CFA prelude define @++x@ and @x++@ in terms of @x += 1@, allowing users to idiomatically define all forms of increment for a type @T@ by defining the single function @T & ?+=(T &, one_t)@; analogous overloads for the decrement operators are present as well.
     2085In C, @0@ has the special property that it is the only ``false'' value;
     2086from the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true.
     2087As 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.
     2088Operator 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.
     2089To 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);
     2090@zero_t@ can only take the value @0@, but has implicit conversions to the integer and pointer types so that C code involving @0@ continues to work.
     2091With 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)@.
     2092\CC makes types truthy by adding a conversion to @bool@;
     2093prior to the addition of explicit cast operators in \CCeleven, this approach had the pitfall of making truthy types transitively convertable to any numeric type;
     2094\CFA avoids this issue.
     2095
     2096Similarly, \CFA also has a special type for @1@, @one_t@;
     2097like @zero_t@, @one_t@ has built-in implicit conversions to the various integral types so that @1@ maintains its expected semantics in legacy code for operations @++@ and @--@.
     2098The addition of @one_t@ allows generic algorithms to handle the unit value uniformly for types where it is meaningful.
     2099\TODO{Make this sentence true}
     2100In particular, polymorphic functions in the \CFA prelude define @++x@ and @x++@ in terms of @x += 1@, allowing users to idiomatically define all forms of increment for a type @T@ by defining the single function @T & ?+=(T &, one_t)@;
     2101analogous overloads for the decrement operators are present as well.
    20832102
    20842103
    … …  
    20882107The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call-syntax (literal argument before function name), using the backquote, to convert basic literals into user literals.
    20892108The backquote is a small character, making the unit (function name) predominate.
    2090 For examples, the multi-precision integers in Section~\ref{s:MultiPrecisionIntegers} make use of user literals:
     2109For examples, the multi-precision integer-type in Section~\ref{s:MultiPrecisionIntegers} has user literals:
    20912110{\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
    20922111\begin{cfa}
    … …  
    23082327\lstMakeShortInline@%
    23092328\end{cquote}
    2310 In additon, there are polymorphic functions, like @min@ and @max@, which work on any type with operators @?<?@ or @?>?@.
     2329In additon, there are polymorphic functions, like @min@ and @max@, that work on any type with operators @?<?@ or @?>?@.
    23112330
    23122331The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
    … …  
    23192338In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation is copied.
    23202339For an increase in storage size, new storage after the copied data may be filled.
    2321 \item[alignment]
     2340\item[align]
    23222341an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
    23232342\item[array]
    2324 allocation of the specified number of elements.
     2343allocation with a specified number of elements.
    23252344An array may be filled, resized, or aligned.
    23262345\end{description}
    … …  
    23342353\lstMakeShortInline~%
    23352354\begin{tabular}{@{}r|r|l|l|l|l@{}}
    2336 \multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
     2355\multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & align & array \\
    23372356\hline
    23382357C               & ~malloc~                      & no                    & no            & no            & no    \\
    … …  
    25472566In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    25482567This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
    2549 Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, differing only in length and clarity of source code.
     2568Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
    25502569A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
    2551 Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list.
     2570Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ function similar to that in Section~\ref{sec:variadic-tuples}.
    25522571The benchmark test is similar for C and \CC.
    2553 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.
     2572The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N/2$ (to reduce graph height) constants.
    25542573
    25552574\begin{figure}
    25562575\begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2557 int main() {
     2576int main( int argc, char * argv[] ) {
    25582577        int max = 0, val = 42;
    25592578        stack( int ) si, ti;
    25602579
    25612580        REPEAT_TIMED( "push_int", N, push( si, val ); )
    2562         TIMED( "copy_int", ti{ si }; )
     2581        TIMED( "copy_int", ti = si; )
    25632582        TIMED( "clear_int", clear( si ); )
    2564         REPEAT_TIMED( "pop_int", N,
    2565                 int x = pop( ti ); if ( x > max ) max = x; )
    2566 
    2567         pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
    2568         stack( pair( short, char ) ) sp, tp;
     2583        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
     2584
     2585        pair( _Bool, char ) max = { (_Bool)0, '\0' }, val = { (_Bool)1, 'a' };
     2586        stack( pair( _Bool, char ) ) sp, tp;
    25692587
    25702588        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
    2571         TIMED( "copy_pair", tp{ sp }; )
     2589        TIMED( "copy_pair", tp = sp; )
    25722590        TIMED( "clear_pair", clear( sp ); )
    2573         REPEAT_TIMED( "pop_pair", N,
    2574                 pair(short, char) x = pop( tp ); if ( x > max ) max = x; )
     2591        REPEAT_TIMED( "pop_pair", N, pair(_Bool, char) x = pop( tp ); if ( x > max ) max = x; )
    25752592}
    25762593\end{cfa}
    … …  
    25832600hence runtime checks are necessary to safely down-cast objects.
    25842601The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
    2585 Note that the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
     2602For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has negligible runtime impact.
     2603Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    25862604
    25872605Figure~\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.
    25882606The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
    2589 All code is compiled at \texttt{-O2} by gcc or g++ 6.3.0, with all \CC code compiled as \CCfourteen.
     2607All code is compiled at \texttt{-O2} by gcc or g++ 6.2.0, with all \CC code compiled as \CCfourteen.
    25902608The 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.
    25912609
    … …  
    26052623                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    26062624maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
    2607 source code size (lines)                        & 187           & 188           & 133           & 303                   \\
    2608 redundant type annotations (lines)      & 25            & 0                     & 2                     & 16                    \\
    2609 binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
     2625source code size (lines)                        & 247           & 222           & 165           & 339                   \\
     2626redundant type annotations (lines)      & 39            & 2                     & 2                     & 15                    \\
     2627binary size (KB)                                        & 14            & 229           & 18            & 38                    \\
    26102628\end{tabular}
    26112629\end{table}
    26122630
    26132631The 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;
    2614 this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
    2615 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @short@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
     2632this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
     2633By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
    26162634\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    2617 The outlier in the graph for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code.
    2618 The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA could easily perform these optimizations.
     2635There are two outliers in the graph for \CFA: all prints and pop of @pair@.
     2636Both of these cases result from the complexity of the C-generated polymorphic code, so that the gcc compiler is unable to optimize some dead code and condense nested calls.
     2637A compiler designed for \CFA could easily perform these optimizations.
    26192638Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    26202639
    2621 \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 41 and 42 lines, respectively.
     2640\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 73 and 54 lines, respectively.
    26222641On 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.
    2623 \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;
     2642\CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;
    26242643with their omission, the \CCV line count is similar to C.
    26252644We 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.
    … …  
    26272646Raw line-count, however, is a fairly rough measure of code complexity;
    26282647another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    2629 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, or @object@ to @printable@ when printing the elements of a @pair@).
     2648Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function pointers arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts (\eg @object@ to @integer@ when popping a stack, or @object@ to @printable@ when printing the elements of a @pair@).
    26302649To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
    26312650The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
    2632 The \CFA benchmark was able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
     2651The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
     2652These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous.
     2653
    26332654
    26342655\section{Related Work}
     2656
    26352657
    26362658\subsection{Polymorphism}
    … …  
    27132735user defined: D, Objective-C
    27142736
     2737
    27152738\section{Conclusion and Future Work}
    27162739
    … …  
    27252748Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    27262749
    2727 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.
     2750There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules.
    27282751(While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.)
    27292752In addition, there are interesting future directions for the polymorphism design.
    … …  
    27602783\CFA
    27612784\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2762 forall(otype T) struct stack_node {
     2785forall( otype T ) struct stack_node;
     2786forall( otype T ) struct stack {
     2787        stack_node(T) * head;
     2788};
     2789forall( otype T ) struct stack_node {
    27632790        T value;
    27642791        stack_node(T) * next;
    27652792};
    2766 forall(otype T) struct stack { stack_node(T) * head; };
    2767 forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    2768 forall(otype T) void ?{}( stack(T) & s, stack(T) t ) {
     2793forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2794forall( otype T) void ?{}( stack(T) & s, stack(T) t ) {
    27692795        stack_node(T) ** crnt = &s.head;
    27702796        for ( stack_node(T) * next = t.head; next; next = next->next ) {
    2771                 *crnt = alloc();
    2772                 ((*crnt)->value){ next->value };
    2773                 crnt = &(*crnt)->next;
     2797                stack_node(T) * new_node = ((stack_node(T)*)malloc());
     2798                (*new_node){ next->value }; /***/
     2799                *crnt = new_node;
     2800                stack_node(T) * acrnt = *crnt;
     2801                crnt = &acrnt->next;
    27742802        }
    27752803        *crnt = 0;
    27762804}
    2777 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2805forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
    27782806        if ( s.head == t.head ) return s;
    27792807        clear( s );
    … …  
    27812809        return s;
    27822810}
    2783 forall(otype T) void ^?{}( stack(T) & s) { clear( s ); }
    2784 forall(otype T) _Bool empty( const stack(T) & s ) { return s.head == 0; }
    2785 forall(otype T) void push( stack(T) & s, T value ) {
    2786         stack_node(T) * n = alloc();
    2787         (*n){ value, head };
    2788         head = n;
    2789 }
    2790 forall(otype T) T pop( stack(T) & s ) {
    2791         stack_node(T) * n = head;
    2792         head = n->next;
    2793         T x = n->value;
    2794         ^(*n){};
    2795         free( n );
    2796         return x;
    2797 }
    2798 forall(otype T) void clear( stack(T) & s ) {
    2799         for ( stack_node(T) * next = head; next; ) {
     2811forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
     2812forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2813forall( otype T ) void push( stack(T) & s, T value ) {
     2814        stack_node(T) * new_node = ((stack_node(T)*)malloc());
     2815        (*new_node){ value, s.head }; /***/
     2816        s.head = new_node;
     2817}
     2818forall( otype T ) T pop( stack(T) & s ) {
     2819        stack_node(T) * n = s.head;
     2820        s.head = n->next;
     2821        T v = n->value;
     2822        delete( n );
     2823        return v;
     2824}
     2825forall( otype T ) void clear( stack(T) & s ) {
     2826        for ( stack_node(T) * next = s.head; next; ) {
    28002827                stack_node(T) * crnt = next;
    28012828                next = crnt->next;
    2802                 ^(*crnt){};
    2803                 free(crnt);
     2829                delete( crnt );
    28042830        }
    2805         head = 0;
     2831        s.head = 0;
    28062832}
    28072833\end{cfa}
    … …  
    28102836\CC
    28112837\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2812 template<typename T> struct stack {
     2838template<typename T> class stack {
    28132839        struct node {
    28142840                T value;
    … …  
    28172843        };
    28182844        node * head;
    2819         void copy(const stack<T> & o) {
     2845        void copy(const stack<T>& o) {
    28202846                node ** crnt = &head;
    28212847                for ( node * next = o.head;; next; next = next->next ) {
    … …  
    28252851                *crnt = nullptr;
    28262852        }
     2853  public:
    28272854        stack() : head(nullptr) {}
    2828         stack(const stack<T> & o) { copy(o); }
     2855        stack(const stack<T>& o) { copy(o); }
    28292856        stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
    28302857        ~stack() { clear(); }
    2831         stack & operator= (const stack<T> & o) {
     2858        stack & operator= (const stack<T>& o) {
    28322859                if ( this == &o ) return *this;
    28332860                clear();
    … …  
    28682895        struct stack_node * next;
    28692896};
    2870 struct stack { struct stack_node* head; };
    28712897struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    28722898void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
    … …  
    28742900        for ( struct stack_node * next = t->head; next; next = next->next ) {
    28752901                *crnt = malloc(sizeof(struct stack_node)); /***/
    2876                 (*crnt)->value = copy(next->value);
     2902                **crnt = (struct stack_node){ copy(next->value) }; /***/
    28772903                crnt = &(*crnt)->next;
    28782904        }
    2879         *crnt = NULL;
     2905        *crnt = 0;
    28802906}
    28812907_Bool stack_empty(const struct stack * s) { return s->head == NULL; }
    … …  
    29062932\CCV
    29072933\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2908 struct stack {
    2909         struct node {
    2910                 ptr<object> value;
    2911                 node* next;
    2912                 node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
    2913         };
    2914         node* head;
    2915         void copy(const stack & o) {
    2916                 node ** crnt = &head;
    2917                 for ( node * next = o.head; next; next = next->next ) {
    2918                         *crnt = new node{ *next->value }; /***/
    2919                         crnt = &(*crnt)->next;
    2920                 }
    2921                 *crnt = nullptr;
     2934stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
     2935void stack::copy(const stack & o) {
     2936        node ** crnt = &head;
     2937        for ( node * next = o.head; next; next = next->next ) {
     2938                *crnt = new node{ *next->value };
     2939                crnt = &(*crnt)->next;
    29222940        }
    2923         stack() : head(nullptr) {}
    2924         stack(const stack & o) { copy(o); }
    2925         stack(stack && o) : head(o.head) { o.head = nullptr; }
    2926         ~stack() { clear(); }
    2927         stack & operator= (const stack & o) {
    2928                 if ( this == &o ) return *this;
    2929                 clear();
    2930                 copy(o);
    2931                 return *this;
     2941        *crnt = nullptr;
     2942}
     2943stack::stack() : head(nullptr) {}
     2944stack::stack(const stack & o) { copy(o); }
     2945stack::stack(stack && o) : head(o.head) { o.head = nullptr; }
     2946stack::~stack() { clear(); }
     2947stack & stack::operator= (const stack & o) {
     2948        if ( this == &o ) return *this;
     2949        clear();
     2950        copy(o);
     2951        return *this;
     2952}
     2953stack & stack::operator= (stack && o) {
     2954        if ( this == &o ) return *this;
     2955        head = o.head;
     2956        o.head = nullptr;
     2957        return *this;
     2958}
     2959bool stack::empty() const { return head == nullptr; }
     2960void stack::push(const object & value) { head = new node{ value, head }; /***/ }
     2961ptr<object> stack::pop() {
     2962        node * n = head;
     2963        head = n->next;
     2964        ptr<object> x = std::move(n->value);
     2965        delete n;
     2966        return x;
     2967}
     2968void stack::clear() {
     2969        for ( node * next = head; next; ) {
     2970                node * crnt = next;
     2971                next = crnt->next;
     2972                delete crnt;
    29322973        }
    2933         stack & operator= (stack && o) {
    2934                 if ( this == &o ) return *this;
    2935                 head = o.head;
    2936                 o.head = nullptr;
    2937                 return *this;
    2938         }
    2939         bool empty() const { return head == nullptr; }
    2940         void push(const object & value) { head = new node{ value, head }; /***/ }
    2941         ptr<object> pop() {
    2942                 node * n = head;
    2943                 head = n->next;
    2944                 ptr<object> x = std::move(n->value);
    2945                 delete n;
    2946                 return x;
    2947         }
    2948         void clear() {
    2949                 for ( node * next = head; next; ) {
    2950                         node * crnt = next;
    2951                         next = crnt->next;
    2952                         delete crnt;
    2953                 }
    2954                 head = nullptr;
    2955         }
    2956 };
     2974        head = nullptr;
     2975}
    29572976\end{cfa}
    29582977
Note: See TracChangeset for help on using the changeset viewer.