Changeset 9d6f011 for doc/papers


Ignore:
Timestamp:
Mar 8, 2018, 3:38:44 PM (7 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
037c072
Parents:
28bc8c8 (diff), 70969f8 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/papers/general
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    r28bc8c8 r9d6f011  
    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    \\
    … …  
    25622581        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; )
     2583        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
    25662584
    25672585        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
    … …  
    25712589        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(short, char) x = pop( tp ); if ( x > max ) max = x; )
    25752592}
    25762593\end{cfa}
    … …  
    26052622                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
    26062623maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
    2607 source code size (lines)                        & 187           & 188           & 133           & 303                   \\
     2624source code size (lines)                        & 187           & 186           & 133           & 303                   \\
    26082625redundant type annotations (lines)      & 25            & 0                     & 2                     & 16                    \\
    26092626binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
    … …  
    26192636Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
    26202637
    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.
     2638\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 39 and 42 lines, respectively.
    26222639On 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.
    26232640\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;
    … …  
    27252742Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    27262743
    2727 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.
     2744There 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.
    27282745(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.)
    27292746In addition, there are interesting future directions for the polymorphism design.
    … …  
    27602777\CFA
    27612778\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2762 forall(otype T) struct stack_node {
     2779forall( otype T ) struct stack_node {
    27632780        T value;
    27642781        stack_node(T) * next;
    27652782};
    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 ) {
     2783forall( otype T ) struct stack { stack_node(T) * head; };
     2784forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2785forall( otype T ) void ?{}( stack(T) & s, stack(T) t ) {
    27692786        stack_node(T) ** crnt = &s.head;
    27702787        for ( stack_node(T) * next = t.head; next; next = next->next ) {
    … …  
    27752792        *crnt = 0;
    27762793}
    2777 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2794forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
    27782795        if ( s.head == t.head ) return s;
    27792796        clear( s );
    … …  
    27812798        return s;
    27822799}
    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 ) {
     2800forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
     2801forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2802forall( otype T ) void push( stack(T) & s, T value ) with( s ) {
    27862803        stack_node(T) * n = alloc();
    27872804        (*n){ value, head };
    27882805        head = n;
    27892806}
    2790 forall(otype T) T pop( stack(T) & s ) {
     2807forall( otype T ) T pop( stack(T) & s ) with( s ) {
    27912808        stack_node(T) * n = head;
    27922809        head = n->next;
    … …  
    27962813        return x;
    27972814}
    2798 forall(otype T) void clear( stack(T) & s ) {
     2815forall( otype T ) void clear( stack(T) & s ) with( s ) {
    27992816        for ( stack_node(T) * next = head; next; ) {
    28002817                stack_node(T) * crnt = next;

  • doc/papers/general/evaluation/cfa-bench.c

    r28bc8c8 r9d6f011  
    1010        TIMED( "copy_int", ti{ si }; )
    1111        TIMED( "clear_int", clear( si ); )
    12         REPEAT_TIMED( "pop_int", N,
    13                 int x = pop( ti ); if ( x > max ) max = x; )
     12        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
    1413
    1514        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
    … …  
    1918        TIMED( "copy_pair", tp{ sp }; )
    2019        TIMED( "clear_pair", clear( sp ); )
    21         REPEAT_TIMED( "pop_pair", N,
    22                 pair(short, char) x = pop( tp ); if ( x > max ) max = x; )
     20        REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); if ( x > max ) max = x; )
    2321}
Note: See TracChangeset for help on using the changeset viewer.