Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    r87555b7 r28bc8c8  
    267267int m = max( max, -max );                                       $\C{// uses (3) and (1) twice, by matching return type}$
    268268\end{cfa}
    269 
    270269\CFA maximizes the ability to reuse names to aggressively address the naming problem.
    271270In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
    … …  
    286285
    287286
    288 \subsection{\texorpdfstring{\protect\lstinline{forall} Functions}{forall Functions}}
     287\subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}}
    289288\label{sec:poly-fns}
    290289
    … …  
    436435One approach is to write bespoke data-structures for each context in which they are needed.
    437436While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
    438 A second approach is to use @void *@ based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality.
     437A 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.
    439438However, 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.
    440439A 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.
    … …  
    508507The offset arrays are statically generated where possible.
    509508If 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;
    510 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.
    511 As 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.
     509if 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. 
     510As 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.
    516515@_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as:
    517516\begin{cfa}
    518 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) }
     517size_t _offsetof_pair[] = { offsetof(_pair_conc0, first), offsetof(_pair_conc0, second) }
    519518\end{cfa}
    520519
    … …  
    540539The 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@:
    541540\begin{cfa}
    542 forall( dtype T ) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
     541forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
    543542        return cmp( a->first, b->first ) ? : cmp( a->second, b->second );
    544543}
    545544\end{cfa}
    546 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.
     545Since @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.
    547546
    548547Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    549548Sometimes information is only used for type-checking and can be omitted at runtime, \eg:
    550549\begin{cfa}
    551 forall( dtype Unit ) struct scalar { unsigned long value; };
     550forall(dtype Unit) struct scalar { unsigned long value; };
    552551struct metres {};
    553552struct litres {};
    554553
    555 forall( dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
     554forall(dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
    556555        return (scalar(U)){ a.value + b.value };
    557556}
    … …  
    808807Due 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:
    809808\begin{cfa}
    810 forall( otype T, dtype U ) void f( T x, U * y );
     809forall(otype T, dtype U) void f( T x, U * y );
    811810f( [5, "hello"] );
    812811\end{cfa}
    … …  
    815814For example, a plus operator can be written to add two triples together.
    816815\begin{cfa}
    817 forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
     816forall(otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
    818817        return [x.0 + y.0, x.1 + y.1, x.2 + y.2];
    819818}
    … …  
    826825\begin{cfa}
    827826int f( [int, double], double );
    828 forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U );
     827forall(otype T, otype U | { T f( T, U, U ); }) void g( T, U );
    829828g( 5, 10.21 );
    830829\end{cfa}
    831830Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
    832831This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}.
    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.
     832Whenever 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}
     834int _thunk( int _p0, double _p1, double _p2 ) { return f( [_p0, _p1], _p2 ); }
     835\end{cfa}
     836so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
     837These thunks take advantage of gcc C nested-functions to produce closures that have the usual function-pointer signature WHAT DOES THIS MEAN???.
    839838
    840839
    … …  
    853852\begin{cfa}
    854853int sum$\(_0\)$() { return 0; }
    855 forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
     854forall(ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
    856855        return x + sum( rest );
    857856}
    … …  
    866865\begin{cfa}
    867866int sum( int x, int y ) { return x + y; }
    868 forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
     867forall(ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
    869868        return sum( x + y, rest );
    870869}
    … …  
    872871One more step permits the summation of any summable type with all arguments of the same type:
    873872\begin{cfa}
    874 trait summable( otype T ) {
     873trait summable(otype T) {
    875874        T ?+?( T, T );
    876875};
    877 forall( otype R | summable( R ) ) R sum( R x, R y ) {
     876forall(otype R | summable( R ) ) R sum( R x, R y ) {
    878877        return x + y;
    879878}
    880 forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
     879forall(otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
    881880        return sum( x + y, rest );
    882881}
    … …  
    889888\begin{cfa}
    890889struct S { int x, y; };
    891 forall( otype T, ttype Params | { void print(T); void print(Params); } ) void print(T arg, Params rest) {
     890forall(otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {
    892891        print(arg);  print(rest);
    893892}
    … …  
    928927is transformed into:
    929928\begin{cfa}
    930 forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
     929forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
    931930        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    932931        T1 field_1;
    … …  
    934933_tuple2(int, int) f() {
    935934        _tuple2(double, double) x;
    936         forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 {
     935        forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
    937936                T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    938937                T1 field_1;
    … …  
    942941}
    943942\end{cfa}
    944 {\sloppy
     943\begin{sloppypar}
    945944Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
    946 \par}%
     945\end{sloppypar}
    947946
    948947\begin{comment}
    … …  
    10051004\section{Control Structures}
    10061005
    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}}
     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}}
    10111010
    10121011The @if@ expression allows declarations, similar to @for@ declaration expression:
    … …  
    10201019
    10211020
    1022 \subsection{\texorpdfstring{\protect\lstinline{switch} Statement}{switch Statement}}
     1021\subsection{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}}
    10231022
    10241023There 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.
    … …  
    10401039\lstMakeShortInline@%
    10411040\end{cquote}
    1042 for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, because a space is required after a number, otherwise the period is a decimal point.}
     1041for a contiguous list:\footnote{gcc provides the same mechanism with awkward syntax, \lstinline@2 ... 42@, where spaces are required around the ellipse.}
    10431042\begin{cquote}
    10441043\lstDeleteShortInline@%
    … …  
    10911090C @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};
    10921091@case@ clauses are made disjoint by the @break@ statement.
    1093 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.
    1094 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}), similar to Go.
     1092While 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.
     1093For 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
     1095Collectively, these enhancements reduce programmer burden and increase readability and safety.
    10951096
    10961097\begin{figure}
    … …  
    11361137\end{figure}
    11371138
    1138 Finally, @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases:
    1139 \begin{cquote}
    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}
    1144 choose ( ... ) {
    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}
    1156 choose ( ... ) {
    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}
    1169 The target label may be case @default@.
    1170 
    1171 Collectively, 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}}
     1139\begin{comment}
     1140Forgotten @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.
     1142Since 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.
     1143Where 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}
     1146choose( 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}}
    11751164
    11761165While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
    … …  
    12811270\subsection{Exception Handling}
    12821271
    1283 The following framework for \CFA exception handling is in place, excluding some runtime type-information and virtual functions.
     1272The following framework for \CFA exception handling is in place, excluding some run-time type-information and dynamic casts.
    12841273\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
    12851274Both 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.
    … …  
    13511340   catch ( IOError err ) { ... }                        $\C{// handler error from other files}$
    13521341\end{cfa}
    1353 where the throw inserts the failing file-handle into the I/O exception.
     1342where the throw inserts the failing file-handle in the I/O exception.
    13541343Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible..
    13551344
    … …  
    13591348resume( $\emph{alternate-stack}$ )
    13601349\end{cfa}
    1361 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task\footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}~\cite{Delisle18}.
    1362 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.
    1363 
    1364 To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.
     1350These 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.}
     1351Nonlocal 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
     1353To facilitate nonlocal exception, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.
    13651354The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks:
    13661355\begin{cquote}
    … …  
    13691358\begin{cfa}
    13701359enable $\emph{exception-type-list}$ {
    1371         // allow non-local raise
     1360        // allow non-local resumption
    13721361}
    13731362\end{cfa}
    … …  
    13751364\begin{cfa}
    13761365disable $\emph{exception-type-list}$ {
    1377         // disallow non-local raise
     1366        // disallow non-local resumption
    13781367}
    13791368\end{cfa}
    … …  
    13861375Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled.
    13871376\begin{cfa}
    1388 void 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}$
     1377void main( mytask & c ) {
     1378        try {
     1379                enable {                        $\C{// now allow non-local exception delivery}$
    13921380                        // task body
    13931381                }
    1394         // appropriate catchResume/catch handlers
     1382        // appropriate catchResume/catch
    13951383        }
    13961384}
    … …  
    14121400
    14131401
    1414 \subsection{\texorpdfstring{\protect\lstinline{with} Clause / Statement}{with Clause / Statement}}
     1402\subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}
    14151403\label{s:WithClauseStatement}
    14161404
    … …  
    18121800int & r = *new( int );
    18131801...                                                                                     $\C{// non-null reference}$
    1814 delete &r;                                                                      $\C{// unmanaged (programmer) memory-management}$
     1802delete &r;
    18151803r += 1;                                                                         $\C{// undefined reference}$
    18161804\end{cfa}
    … …  
    19591947Constructor 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.
    19601948
    1961 In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@\footnote{%
     1949In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@.
     1950The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@\footnote{%
    19621951The symbol \lstinline+^+ is used for the destructor name because it was the last binary operator that could be used in a unary context.}.
    1963 The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@.
    19641952Like other \CFA operators, these names represent the syntax used to call the constructor or destructor, \eg @?{}(x, ...)@ or @^{}(x, ...)@.
    19651953The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed.
    … …  
    20832071\subsection{0/1}
    20842072
    2085 In C, @0@ has the special property that it is the only ``false'' value;
    2086 from the standard, any value that compares equal to @0@ is false, while any value that compares unequal to @0@ is true.
    2087 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.
    2088 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.
    2089 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);
    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.
    2091 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)@.
    2092 \CC makes types truthy by adding a conversion to @bool@;
    2093 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;
    2094 \CFA avoids this issue.
    2095 
    2096 Similarly, \CFA also has a special type for @1@, @one_t@;
    2097 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 for operations @++@ and @--@.
    2098 The 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}
    2100 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)@;
    2101 analogous overloads for the decrement operators are present as well.
     2073In 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.
     2074As 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.
     2075The 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.
     2076To 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.
     2077With 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.
     2081The 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.
    21022083
    21032084
    … …  
    21072088The 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.
    21082089The backquote is a small character, making the unit (function name) predominate.
    2109 For examples, the multi-precision integer-type in Section~\ref{s:MultiPrecisionIntegers} has user literals:
     2090For examples, the multi-precision integers in Section~\ref{s:MultiPrecisionIntegers} make use of user literals:
    21102091{\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
    21112092\begin{cfa}
    … …  
    23272308\lstMakeShortInline@%
    23282309\end{cquote}
    2329 In additon, there are polymorphic functions, like @min@ and @max@, that work on any type with operators @?<?@ or @?>?@.
     2310In additon, there are polymorphic functions, like @min@ and @max@, which work on any type with operators @?<?@ or @?>?@.
    23302311
    23312312The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
    … …  
    23382319In 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.
    23392320For an increase in storage size, new storage after the copied data may be filled.
    2340 \item[align]
     2321\item[alignment]
    23412322an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
    23422323\item[array]
    2343 allocation with a specified number of elements.
     2324allocation of the specified number of elements.
    23442325An array may be filled, resized, or aligned.
    23452326\end{description}
    … …  
    23532334\lstMakeShortInline~%
    23542335\begin{tabular}{@{}r|r|l|l|l|l@{}}
    2355 \multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & align & array \\
     2336\multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
    23562337\hline
    23572338C               & ~malloc~                      & no                    & no            & no            & no    \\
    … …  
    25662547In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
    25672548This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
    2568 Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
     2549Since 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.
    25692550A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
    2570 Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ function similar to that in Section~\ref{sec:variadic-tuples}.
     2551Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked-list.
    25712552The benchmark test is similar for C and \CC.
    2572 The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N/2$ (to reduce graph height) constants.
     2553The 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.
    25732554
    25742555\begin{figure}
    25752556\begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2576 int main( int argc, char * argv[] ) {
     2557int main() {
    25772558        int max = 0, val = 42;
    25782559        stack( int ) si, ti;
    25792560
    25802561        REPEAT_TIMED( "push_int", N, push( si, val ); )
    2581         TIMED( "copy_int", ti = si; )
     2562        TIMED( "copy_int", ti{ si }; )
    25822563        TIMED( "clear_int", clear( si ); )
    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;
     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;
    25872569
    25882570        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
    2589         TIMED( "copy_pair", tp = sp; )
     2571        TIMED( "copy_pair", tp{ sp }; )
    25902572        TIMED( "clear_pair", clear( sp ); )
    2591         REPEAT_TIMED( "pop_pair", N, pair(_Bool, char) x = pop( tp ); if ( x > max ) max = x; )
     2573        REPEAT_TIMED( "pop_pair", N,
     2574                pair(short, char) x = pop( tp ); if ( x > max ) max = x; )
    25922575}
    25932576\end{cfa}
    … …  
    26002583hence runtime checks are necessary to safely down-cast objects.
    26012584The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
    2602 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has negligible runtime impact.
    2603 Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
     2585Note 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.
    26042586
    26052587Figure~\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.
    26062588The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
    2607 All code is compiled at \texttt{-O2} by gcc or g++ 6.2.0, with all \CC code compiled as \CCfourteen.
     2589All code is compiled at \texttt{-O2} by gcc or g++ 6.3.0, with all \CC code compiled as \CCfourteen.
    26082590The 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.
    26092591
    … …  
    26232605                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    26242606maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
    2625 source code size (lines)                        & 247           & 222           & 165           & 339                   \\
    2626 redundant type annotations (lines)      & 39            & 2                     & 2                     & 15                    \\
    2627 binary size (KB)                                        & 14            & 229           & 18            & 38                    \\
     2607source code size (lines)                        & 187           & 188           & 133           & 303                   \\
     2608redundant type annotations (lines)      & 25            & 0                     & 2                     & 16                    \\
     2609binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
    26282610\end{tabular}
    26292611\end{table}
    26302612
    26312613The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
    2632 this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
    2633 By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
     2614this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
     2615By 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.
    26342616\CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
    2635 There are two outliers in the graph for \CFA: all prints and pop of @pair@.
    2636 Both of these cases result from the complexity of the C-generated polymorphic code, so that the gcc compiler is unable to optimize some dead code and condense nested calls.
    2637 A compiler designed for \CFA could easily perform these optimizations.
     2617The outlier in the graph for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code.
     2618The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA could easily perform these optimizations.
    26382619Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    26392620
    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.
     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.
    26412622On the other hand, C does not have a generic collections-library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers.
    2642 \CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;
     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;
    26432624with their omission, the \CCV line count is similar to C.
    26442625We 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.
    … …  
    26462627Raw line-count, however, is a fairly rough measure of code complexity;
    26472628another important factor is how much type information the programmer must manually specify, especially where that information is not checked by the compiler.
    2648 Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs, and is much less common in \CFA than C, with its manually specified function 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@).
     2629Such 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@).
    26492630To 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.
    26502631The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
    2651 The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
    2652 These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous.
    2653 
     2632The \CFA benchmark was able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
    26542633
    26552634\section{Related Work}
    2656 
    26572635
    26582636\subsection{Polymorphism}
    … …  
    27352713user defined: D, Objective-C
    27362714
    2737 
    27382715\section{Conclusion and Future Work}
    27392716
    … …  
    27482725Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    27492726
    2750 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, runtime type-information, virtual functions, user-defined conversions, concurrent primitives, and modules.
     2727There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.
    27512728(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.)
    27522729In addition, there are interesting future directions for the polymorphism design.
    … …  
    27832760\CFA
    27842761\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2785 forall( otype T ) struct stack_node;
    2786 forall( otype T ) struct stack {
    2787         stack_node(T) * head;
    2788 };
    2789 forall( otype T ) struct stack_node {
     2762forall(otype T) struct stack_node {
    27902763        T value;
    27912764        stack_node(T) * next;
    27922765};
    2793 forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    2794 forall( otype T) void ?{}( stack(T) & s, stack(T) t ) {
     2766forall(otype T) struct stack { stack_node(T) * head; };
     2767forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2768forall(otype T) void ?{}( stack(T) & s, stack(T) t ) {
    27952769        stack_node(T) ** crnt = &s.head;
    27962770        for ( stack_node(T) * next = t.head; next; next = next->next ) {
    2797                 stack_node(T) * new_node = ((stack_node(T)*)malloc());
    2798                 (*new_node){ next->value }; /***/
    2799                 *crnt = new_node;
    2800                 stack_node(T) * acrnt = *crnt;
    2801                 crnt = &acrnt->next;
     2771                *crnt = alloc();
     2772                ((*crnt)->value){ next->value };
     2773                crnt = &(*crnt)->next;
    28022774        }
    28032775        *crnt = 0;
    28042776}
    2805 forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2777forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {
    28062778        if ( s.head == t.head ) return s;
    28072779        clear( s );
    … …  
    28092781        return s;
    28102782}
    2811 forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
    2812 forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
    2813 forall( otype T ) void push( stack(T) & s, T value ) {
    2814         stack_node(T) * new_node = ((stack_node(T)*)malloc());
    2815         (*new_node){ value, s.head }; /***/
    2816         s.head = new_node;
    2817 }
    2818 forall( otype T ) T pop( stack(T) & s ) {
    2819         stack_node(T) * n = s.head;
    2820         s.head = n->next;
    2821         T v = n->value;
    2822         delete( n );
    2823         return v;
    2824 }
    2825 forall( otype T ) void clear( stack(T) & s ) {
    2826         for ( stack_node(T) * next = s.head; next; ) {
     2783forall(otype T) void ^?{}( stack(T) & s) { clear( s ); }
     2784forall(otype T) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2785forall(otype T) void push( stack(T) & s, T value ) {
     2786        stack_node(T) * n = alloc();
     2787        (*n){ value, head };
     2788        head = n;
     2789}
     2790forall(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}
     2798forall(otype T) void clear( stack(T) & s ) {
     2799        for ( stack_node(T) * next = head; next; ) {
    28272800                stack_node(T) * crnt = next;
    28282801                next = crnt->next;
    2829                 delete( crnt );
     2802                ^(*crnt){};
     2803                free(crnt);
    28302804        }
    2831         s.head = 0;
     2805        head = 0;
    28322806}
    28332807\end{cfa}
    … …  
    28362810\CC
    28372811\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2838 template<typename T> class stack {
     2812template<typename T> struct stack {
    28392813        struct node {
    28402814                T value;
    … …  
    28432817        };
    28442818        node * head;
    2845         void copy(const stack<T>& o) {
     2819        void copy(const stack<T> & o) {
    28462820                node ** crnt = &head;
    28472821                for ( node * next = o.head;; next; next = next->next ) {
    … …  
    28512825                *crnt = nullptr;
    28522826        }
    2853   public:
    28542827        stack() : head(nullptr) {}
    2855         stack(const stack<T>& o) { copy(o); }
     2828        stack(const stack<T> & o) { copy(o); }
    28562829        stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
    28572830        ~stack() { clear(); }
    2858         stack & operator= (const stack<T>& o) {
     2831        stack & operator= (const stack<T> & o) {
    28592832                if ( this == &o ) return *this;
    28602833                clear();
    … …  
    28952868        struct stack_node * next;
    28962869};
     2870struct stack { struct stack_node* head; };
    28972871struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    28982872void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
    … …  
    29002874        for ( struct stack_node * next = t->head; next; next = next->next ) {
    29012875                *crnt = malloc(sizeof(struct stack_node)); /***/
    2902                 **crnt = (struct stack_node){ copy(next->value) }; /***/
     2876                (*crnt)->value = copy(next->value);
    29032877                crnt = &(*crnt)->next;
    29042878        }
    2905         *crnt = 0;
     2879        *crnt = NULL;
    29062880}
    29072881_Bool stack_empty(const struct stack * s) { return s->head == NULL; }
    … …  
    29322906\CCV
    29332907\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2934 stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
    2935 void stack::copy(const stack & o) {
    2936         node ** crnt = &head;
    2937         for ( node * next = o.head; next; next = next->next ) {
    2938                 *crnt = new node{ *next->value };
    2939                 crnt = &(*crnt)->next;
     2908struct 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;
    29402922        }
    2941         *crnt = nullptr;
    2942 }
    2943 stack::stack() : head(nullptr) {}
    2944 stack::stack(const stack & o) { copy(o); }
    2945 stack::stack(stack && o) : head(o.head) { o.head = nullptr; }
    2946 stack::~stack() { clear(); }
    2947 stack & stack::operator= (const stack & o) {
    2948         if ( this == &o ) return *this;
    2949         clear();
    2950         copy(o);
    2951         return *this;
    2952 }
    2953 stack & stack::operator= (stack && o) {
    2954         if ( this == &o ) return *this;
    2955         head = o.head;
    2956         o.head = nullptr;
    2957         return *this;
    2958 }
    2959 bool stack::empty() const { return head == nullptr; }
    2960 void stack::push(const object & value) { head = new node{ value, head }; /***/ }
    2961 ptr<object> stack::pop() {
    2962         node * n = head;
    2963         head = n->next;
    2964         ptr<object> x = std::move(n->value);
    2965         delete n;
    2966         return x;
    2967 }
    2968 void stack::clear() {
    2969         for ( node * next = head; next; ) {
    2970                 node * crnt = next;
    2971                 next = crnt->next;
    2972                 delete crnt;
     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;
    29732932        }
    2974         head = nullptr;
    2975 }
     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};
    29762957\end{cfa}
    29772958
Note: See TracChangeset for help on using the changeset viewer.