Changeset 7b0dfa4


Ignore:
Timestamp:
Mar 7, 2018, 4:08:29 PM (6 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
f4abc58
Parents:
e6c5e79 (diff), 6dba9f99 (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
Files:
14 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/pl.bib

    re6c5e79 r7b0dfa4  
    14391439    contributer = {pabuhr@plg},
    14401440    author      = {Peter A. Buhr},
    1441     title       = {$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Annotated Reference Manual, Version 6.1.0},
     1441    title       = {$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Annotated Reference Manual, Version 7.0.0},
    14421442    institution = {School of Computer Science, University of Waterloo},
    14431443    address     = {Waterloo, Ontario, Canada, N2L 3G1},
    1444     month       = jul,
    1445     year        = 2015,
    1446     note        = {\href{http://plg.uwaterloo.ca/~usystem/pub/uSystem/u++-6.1.0.sh}{http://\-plg.\-uwaterloo.\-ca/\-$\sim$usystem/\-pub/\-uSystem/\-u++-6.1.0.sh}},
     1444    month       = dec,
     1445    year        = 2017,
     1446    note        = {\href{http://plg.uwaterloo.ca/~usystem/pub/uSystem/u++-7.0.0.sh}{http://\-plg.\-uwaterloo.\-ca/\-$\sim$usystem/\-pub/\-uSystem/\-u++-7.0.0.sh}},
    14471447}
    14481448
  • doc/papers/general/Paper.tex

    re6c5e79 r7b0dfa4  
    5858\setlength{\parindentlnth}{\parindent}
    5959
     60\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{\lst@basicstyle{#1}}}}
    6061\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
    6162\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
     
    231232All of the features discussed in this paper are working, unless a feature states it is a future feature for completion.
    232233
     234Finally, it is impossible to describe a programming language without usages before definitions.
     235Therefore, syntax and semantics appear before explanations;
     236hence, patience is necessary until details are presented.
     237
    233238
    234239\section{Polymorphic Functions}
     
    263268\end{cfa}
    264269\CFA maximizes the ability to reuse names to aggressively address the naming problem.
    265 In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction for a programmer.
     270In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
    266271In the above, the name @max@ has a consistent meaning, and a programmer only needs to remember the single concept: maximum.
    267272To prevent significant ambiguities, \CFA uses the return type in selecting overloads, \eg in the assignment to @m@, the compiler use @m@'s type to unambiguously select the most appropriate call to function @max@ (as does Ada).
    268273As is shown later, there are a number of situations where \CFA takes advantage of available type information to disambiguate, where other programming languages generate ambiguities.
    269274
    270 \Celeven added @_Generic@ expressions, which can be used in preprocessor macros to provide a form of ad-hoc polymorphism; however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading.
    271 The macro wrapping the generic expression imposes some limitations; as an example, it could not implement the example above, because the variables @max@ would collide with the functions @max@.
    272 Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the functions dispatched to, which must all have distinct names.
    273 Though name-overloading removes a major use-case for @_Generic@ expressions, \CFA implements @_Generic@ for backwards-compatibility purposes. \TODO{actually implement that}
     275\Celeven added @_Generic@ expressions, which is used in preprocessor macros to provide a form of ad-hoc polymorphism;
     276however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading.
     277The macro wrapping the generic expression imposes some limitations;
     278\eg, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@.
     279Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the dispatch functions, which must all have distinct names.
     280For backwards compatibility, \CFA supports @_Generic@ expressions, but it is an unnecessary mechanism. \TODO{actually implement that}
    274281
    275282% http://fanf.livejournal.com/144696.html
     
    286293int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
    287294\end{cfa}
    288 The @identity@ function above can be applied to any complete \newterm{object type} (or @otype@).
     295This @identity@ function can be applied to any complete \newterm{object type} (or @otype@).
    289296The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type.
    290297The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor.
    291298If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \newterm{data type} (or @dtype@).
    292299
    293 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions;
     300In \CFA, the polymorphic runtime-cost is spread over each polymorphic call, because more arguments are passed to polymorphic functions;
    294301the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual-function calls.
    295302A design advantage is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
     
    303310which works for any type @T@ with a matching addition operator.
    304311The polymorphism is achieved by creating a wrapper function for calling @+@ with @T@ bound to @double@, then passing this function to the first call of @twice@.
    305 There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada}, in its type analysis.
     312There is now the option of using the same @twice@ and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada} in its type analysis.
    306313The first approach has a late conversion from @double@ to @int@ on the final assignment, while the second has an eager conversion to @int@.
    307314\CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition.
     
    312319\begin{cfa}
    313320void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
    314                                 int (* compar)( const void *, const void * ));
    315 
    316 int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    317                                 *(double *)t2 < *(double *)t1 ? 1 : 0; }
    318 
     321                                         int (* compar)( const void *, const void * ));
     322int comp( const void * t1, const void * t2 ) {
     323         return *(double *)t1 < *(double *)t2 ? -1 : *(double *)t2 < *(double *)t1 ? 1 : 0;
     324}
    319325double key = 5.0, vals[10] = { /* 10 sorted float values */ };
    320326double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
     
    324330forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
    325331        int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ }
    326         return (T *)bsearch( &key, arr, size, sizeof(T), comp ); }
    327 
     332        return (T *)bsearch( &key, arr, size, sizeof(T), comp );
     333}
    328334forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
    329335        T * result = bsearch( key, arr, size ); $\C{// call first version}$
    330         return result ? result - arr : size; }  $\C{// pointer subtraction includes sizeof(T)}$
    331 
     336        return result ? result - arr : size;    $\C{// pointer subtraction includes sizeof(T)}$
     337}
    332338double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
    333339int posn = bsearch( 5.0, vals, 10 );
     
    336342Providing a hidden @comp@ function in \CC is awkward as lambdas do not use C calling-conventions and template declarations cannot appear at block scope.
    337343As well, an alternate kind of return is made available: position versus pointer to found element.
    338 \CC's type-system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a templated @bsearch@.
     344\CC's type-system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a template @bsearch@.
    339345
    340346\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}).
     
    382388\begin{cfa}
    383389trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
    384         void ?{}( T * );                                                $\C{// default constructor}$
    385         void ?{}( T *, T );                                             $\C{// copy constructor}$
    386         void ?=?( T *, T );                                             $\C{// assignment operator}$
    387         void ^?{}( T * ); };                                    $\C{// destructor}$
     390        void ?{}( T & );                                                $\C{// default constructor}$
     391        void ?{}( T &, T );                                             $\C{// copy constructor}$
     392        void ?=?( T &, T );                                             $\C{// assignment operator}$
     393        void ^?{}( T & ); };                                    $\C{// destructor}$
    388394\end{cfa}
    389395Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete type: stack-allocatable, default or copy-initialized, assigned, and deleted.
     
    429435One approach is to write bespoke data-structures for each context in which they are needed.
    430436While 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.
    431 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allows 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.
    432438However, 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.
    433439A 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.
    434 Furthermore, writing and using preprocessor macros can be unnatural and inflexible.
     440Furthermore, writing and using preprocessor macros is unnatural and inflexible.
    435441
    436442\CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data-types.
     
    444450        S second;
    445451};
    446 forall( otype T ) T value( pair( const char *, T ) p ) { return p.second; }
    447 forall( dtype F, otype T ) T value( pair( F *, T * ) p ) { return *p.second; }
    448 
    449 pair( const char *, int ) p = { "magic", 42 };
     452forall( otype T ) T value( pair( const char *, T ) p ) { return p.second; } $\C{// dynamic}$
     453forall( dtype F, otype T ) T value( pair( F *, T * ) p ) { return *p.second; } $\C{// dtype-static (concrete)}$
     454
     455pair( const char *, int ) p = { "magic", 42 }; $\C{// concrete}$
    450456int i = value( p );
    451 pair( void *, int * ) q = { 0, &p.second };
     457pair( void *, int * ) q = { 0, &p.second }; $\C{// concrete}$
    452458i = value( q );
    453459double d = 1.0;
    454 pair( double *, double * ) r = { &d, &d };
     460pair( double *, double * ) r = { &d, &d }; $\C{// concrete}$
    455461d = value( r );
    456462\end{cfa}
     
    458464\CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}.
    459465Concrete types have a fixed memory layout regardless of type parameters, while dynamic types vary in memory layout depending on their type parameters.
    460 A type may have polymorphic parameters but still be concrete, called \newterm{dtype-static}.
     466A \newterm{dtype-static} type has polymorphic parameters but is still concrete.
    461467Polymorphic pointers are an example of dtype-static types, \eg @forall(dtype T) T *@ is a polymorphic type, but for any @T@, @T *@  is a fixed-sized pointer, and therefore, can be represented by a @void *@ in code generation.
    462468
     
    475481For example, the concrete instantiation for @pair( const char *, int )@ is:
    476482\begin{cfa}
    477 struct _pair_conc1 {
     483struct _pair_conc0 {
    478484        const char * first;
    479485        int second;
     
    482488
    483489A concrete generic-type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
    484 In the above example, the @pair( F *, T * )@ parameter to @value_p@ is such a type; its expansion is below and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
    485 \begin{cfa}
    486 struct _pair_conc0 {
     490In the above example, the @pair( F *, T * )@ parameter to @value@ is such a type; its expansion is below and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
     491\begin{cfa}
     492struct _pair_conc1 {
    487493        void * first;
    488494        void * second;
     
    496502As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller.
    497503Dynamic generic-types also have an \newterm{offset array} containing structure-member offsets.
    498 A dynamic generic-union needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
     504A dynamic generic-@union@ needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
    499505Access to members of a dynamic structure is provided at runtime via base-displacement addressing with the structure pointer and the member offset (similar to the @offsetof@ macro), moving a compile-time offset calculation to runtime.
    500506
    501507The offset arrays are statically generated where possible.
    502508If 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;
    503 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.
    504 As an example, @p.second@ in the @value@ function above is implemented as @*(p + _offsetof_pair[1])@, where @p@ is a @void *@, and @_offsetof_pair@ is the offset array passed into @value@ for @pair( const char *, T )@.
    505 The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) }@.
     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.
     515@_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as:
     516\begin{cfa}
     517size_t _offsetof_pair[] = { offsetof(_pair_conc0, first), offsetof(_pair_conc0, second) }
     518\end{cfa}
    506519
    507520In some cases the offset arrays cannot be statically generated.
     
    586599\subsection{Tuple Expressions}
    587600
    588 The addition of multiple-return-value functions (MRVF) are useless without a syntax for accepting multiple values at the call-site.
     601The addition of multiple-return-value functions (MRVF) are \emph{useless} without a syntax for accepting multiple values at the call-site.
    589602The simplest mechanism for capturing the return values is variable assignment, allowing the values to be retrieved directly.
    590603As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions (as above), called a \newterm{tuple}.
     
    822835\end{cfa}
    823836so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    824 These thunks take advantage of gcc C nested-functions to produce closures that have the usual function-pointer signature.
     837These thunks take advantage of gcc C nested-functions to produce closures that have the usual function-pointer signature WHAT DOES THIS MEAN???.
    825838
    826839
     
    878891        print(arg);  print(rest);
    879892}
    880 void print( char * x ) { printf( "%s", x ); }
     893void print( const char * x ) { printf( "%s", x ); }
    881894void print( int x ) { printf( "%d", x ); }
    882895void print( S s ) { print( "{ ", s.x, ",", s.y, " }" ); }
     
    887900The polymorphic @print@ allows printing any list of types, where as each individual type has a @print@ function.
    888901The individual print functions can be used to build up more complicated @print@ functions, such as @S@, which cannot be done with @printf@ in C.
     902This mechanism is used to seamlessly print tuples in the \CFA I/O library (see Section~\ref{s:IOLibrary}).
    889903
    890904Finally, it is possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
     
    10781092While 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.
    10791093For 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
    10801095Collectively, these enhancements reduce programmer burden and increase readability and safety.
    10811096
     
    12371252\end{figure}
    12381253
    1239 Both labelled @continue@ and @break@ are a @goto@ restricted in the following ways:
     1254With respect to safety, both labelled @continue@ and @break@ are a @goto@ restricted in the following ways:
    12401255\begin{itemize}
    12411256\item
     
    12501265With @goto@, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader.
    12511266Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting existing constructs.
    1252 The implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed.
     1267Otherwise, the implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed.
    12531268
    12541269
    12551270\subsection{Exception Handling}
    12561271
    1257 The following framework for \CFA exception handling is in place, excluding a run-time type information and dynamic casts.
    1258 \CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling}).
     1272The following framework for \CFA exception handling is in place, excluding some run-time type-information and dynamic casts.
     1273\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
    12591274Both 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.
    12601275\CFA restricts exception types to those defined by aggregate type @exception@.
     
    13331348resume( $\emph{alternate-stack}$ )
    13341349\end{cfa}
    1335 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another coroutine or task~\cite{Delisle18}.
     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.}
    13361351Nonlocal 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.
    13371352
     
    13581373Specifying no exception type is shorthand for specifying all exception types.
    13591374Both @enable@ and @disable@ blocks can be nested, turning propagation on/off on entry, and on exit, the specified exception types are restored to their prior state.
     1375Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled.
     1376\begin{cfa}
     1377void main( mytask & c ) {
     1378        try {
     1379                enable {                        $\C{// now allow non-local exception delivery}$
     1380                        // task body
     1381                }
     1382        // appropriate catchResume/catch
     1383        }
     1384}
     1385\end{cfa}
    13601386
    13611387Finally, \CFA provides a Java like  @finally@ clause after the catch clauses:
     
    14611487Qualification or a cast is used to disambiguate.
    14621488
    1463 There is an interesting problem between parameters and the function @with@, \eg:
     1489There is an interesting problem between parameters and the function-body @with@, \eg:
    14641490\begin{cfa}
    14651491void ?{}( S & s, int i ) with ( s ) {           $\C{// constructor}$
     
    14671493}
    14681494\end{cfa}
    1469 Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function @with@.
     1495Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function-body @with@.
    14701496To solve this problem, parameters are treated like an initialized aggregate:
    14711497\begin{cfa}
     
    14751501} params;
    14761502\end{cfa}
    1477 and implicitly opened \emph{after} a function open, to give them higher priority:
    1478 \begin{cfa}
    1479 void ?{}( S & s, int i ) with ( s ) `with( $\emph{\color{red}params}$ )` {
    1480         s.i = i; j = 3; m = 5.5;
     1503and implicitly opened \emph{after} a function-body open, to give them higher priority:
     1504\begin{cfa}
     1505void ?{}( S & s, int `i` ) with ( s ) `with( $\emph{\color{red}params}$ )` {
     1506        s.i = `i`; j = 3; m = 5.5;
    14811507}
    14821508\end{cfa}
     
    15391565While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice.
    15401566
    1541 \CFA provides its own type, variable and function declarations, using a different syntax.
     1567\CFA provides its own type, variable and function declarations, using a different syntax~\cite[pp.~856--859]{Buhr94a}.
    15421568The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right.
    15431569The qualifiers have the same meaning but are ordered left to right to specify a variable's type.
     
    19511977}
    19521978\end{cfa}
    1953 (Note, the example is purposely kept simple by using shallow-copy semantics.)
     1979(Note, the example is purposely simplified using shallow-copy semantics.)
    19541980An initialization constructor-call has the same syntax as a C initializer, except the initialization values are passed as arguments to a matching constructor (number and type of paremeters).
    19551981\begin{cfa}
     
    20042030C already includes limited polymorphism for literals -- @0@ can be either an integer or a pointer literal, depending on context, while the syntactic forms of literals of the various integer and float types are very similar, differing from each other only in suffix.
    20052031In keeping with the general \CFA approach of adding features while respecting the ``C-style'' of doing things, C's polymorphic constants and typed literal syntax are extended to interoperate with user-defined types, while maintaining a backwards-compatible semantics.
    2006 A trivial example is allowing the underscore, as in Ada, to separate prefixes, digits, and suffixes in all \CFA constants, \eg @0x`_`1.ffff`_`ffff`_`p`_`128`_`l@.
     2032
     2033A simple example is allowing the underscore, as in Ada, to separate prefixes, digits, and suffixes in all \CFA constants, \eg @0x`_`1.ffff`_`ffff`_`p`_`128`_`l@, where the underscore is also the standard separator in C identifiers.
     2034\CC uses a single quote as a separator but it is restricted among digits, precluding its use in the literal prefix or suffix, \eg @0x1.ffff@@`'@@ffffp128l@, and causes problems with most IDEs, which must be extended to deal with this alternate use of the single quote.
    20072035
    20082036
     
    20142042\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
    20152043\begin{cfa}
    2016 20`_hh`     // signed char
    2017 21`_hhu`   // unsigned char
    2018 22`_h`       // signed short int
    2019 23`_uh`     // unsigned short int
    2020 24`z`         // size_t
    2021 \end{cfa}
    2022 &
    2023 \begin{cfa}
    2024 20`_L8`      // int8_t
    2025 21`_ul8`     // uint8_t
    2026 22`_l16`     // int16_t
    2027 23`_ul16`   // uint16_t
    2028 24`_l32`     // int32_t
    2029 \end{cfa}
    2030 &
    2031 \begin{cfa}
    2032 25`_ul32`      // uint32_t
    2033 26`_l64`        // int64_t
    2034 27`_l64u`      // uint64_t
    2035 26`_L128`     // int128
    2036 27`_L128u`   // unsigned int128
     204420_`hh`     // signed char
     204521_`hhu`   // unsigned char
     204622_`h`       // signed short int
     204723_`uh`     // unsigned short int
     204824_`z`       // size_t
     2049\end{cfa}
     2050&
     2051\begin{cfa}
     205220_`L8`      // int8_t
     205321_`ul8`     // uint8_t
     205422_`l16`     // int16_t
     205523_`ul16`   // uint16_t
     205624_`l32`     // int32_t
     2057\end{cfa}
     2058&
     2059\begin{cfa}
     206025_`ul32`      // uint32_t
     206126_`l64`        // int64_t
     206227_`l64u`      // uint64_t
     206326_`L128`     // int128
     206427_`L128u`   // unsigned int128
    20372065\end{cfa}
    20382066\end{tabular}
     
    20732101After which, user literals must match (no conversions);
    20742102hence, it is necessary to overload the unit with all appropriate types.
    2075 Finally, the use of the single quote as a separator is restricted to digits, precluding its use in the literal prefix or suffix, and causes problems with most IDEs, which must be extended to deal with this alternate use of the single quote.
    20762103
    20772104\begin{figure}
     
    21252152        w = 155|_lb|;
    21262153        w = 0b1111|_lb|;       // error, binary unsupported
    2127         w = 0${\color{red}'}$233|_lb|;          // quote separator
     2154        w = 0${\color{red}\LstBasicStyle{'}}$233|_lb|;          // quote separator
    21282155        w = 0x9b|_kg|;
    21292156        w = 5.5d|_st| + 8|_kg| + 25.01|_lb| + heavy;
     
    22872314\begin{description}[topsep=3pt,itemsep=2pt,parsep=0pt]
    22882315\item[fill]
    2289 after allocation the storage is filled with a specified character.
     2316an allocation with a specified character.
    22902317\item[resize]
    2291 an existing allocation is decreased or increased in size.
     2318an existing allocation to decreased or increased its size.
    22922319In 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.
    22932320For an increase in storage size, new storage after the copied data may be filled.
    22942321\item[alignment]
    2295 an allocation starts on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
     2322an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
    22962323\item[array]
    2297 the allocation size is scaled to the specified number of array elements.
     2324allocation of the specified number of elements.
    22982325An array may be filled, resized, or aligned.
    22992326\end{description}
    23002327Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation-functions and how all the capabilities can be combined into two \CFA functions.
    23012328\CFA storage-management functions extend the C equivalents by overloading, providing shallow type-safety, and removing the need to specify the base allocation-size.
    2302 Figure~\ref{f:StorageAllocation} contrasts \CFA and C storage-allocation operation performing the same operations with the same type safety.
     2329Figure~\ref{f:StorageAllocation} contrasts \CFA and C storage-allocation performing the same operations with the same type safety.
    23032330
    23042331\begin{table}
     
    24432470\end{cfa}
    24442471\\
    2445 \textbf{output:}
    24462472&
    24472473\begin{cfa}[showspaces=true,aboveskip=0pt]
     
    25302556\begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    25312557int main( int argc, char * argv[] ) {
    2532         ofstream out = { "cfa-out.txt" };
    25332558        int max = 0, val = 42;
    2534         stack( int ) s, t;
    2535 
    2536         REPEAT_TIMED( "push_int", N, push( s, val ); )
    2537         TIMED( "copy_int", t = s; )
    2538         TIMED( "clear_int", clear( s ); )
    2539         REPEAT_TIMED( "pop_int", N, int v = pop( t ); max = max( v, max ); )
    2540         REPEAT_TIMED( "print_int", N/2, out | val | ':' | val | endl; )
    2541 
    2542         pair( _Bool, char ) max = { false, '\0' }, val = { true, 'a' };
    2543         stack( pair( _Bool, char ) ) s, t;
    2544 
    2545         REPEAT_TIMED( "push_pair", N, push( s, val ); )
    2546         TIMED( "copy_pair", t = s; )
    2547         TIMED( "clear_pair", clear( s ); )
    2548         REPEAT_TIMED( "pop_pair", N, pair(_Bool, char) v = pop( t ); max = max( v, max ); )
    2549         REPEAT_TIMED( "print_pair", N/2, out | val | ':' | val | endl; )
     2559        stack( int ) si, ti;
     2560
     2561        REPEAT_TIMED( "push_int", N, push( si, val ); )
     2562        TIMED( "copy_int", ti = si; )
     2563        TIMED( "clear_int", clear( si ); )
     2564        REPEAT_TIMED( "pop_int", N,
     2565                int x = pop( ti ); if ( x > max ) max = x; )
     2566
     2567        pair( _Bool, char ) max = { (_Bool)0, '\0' }, val = { (_Bool)1, 'a' };
     2568        stack( pair( _Bool, char ) ) sp, tp;
     2569
     2570        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
     2571        TIMED( "copy_pair", tp = sp; )
     2572        TIMED( "clear_pair", clear( sp ); )
     2573        REPEAT_TIMED( "pop_pair", N,
     2574                pair(_Bool, char) x = pop( tp ); if ( x > max ) max = x; )
    25502575}
    25512576\end{cfa}
     
    26772702\subsection{Control Structures / Declarations / Literals}
    26782703
     2704Java has default fall through like C/\CC.
     2705Pascal/Ada/Go/Rust do not have default fall through.
     2706\Csharp does not have fall through but still requires a break.
     2707Python uses dictionary mapping. \\
     2708\CFA choose is like Rust match.
     2709
     2710Java has labelled break/continue. \\
     2711Languages with and without exception handling.
     2712
     2713Alternative C declarations. \\
     2714Different references \\
     2715Constructors/destructors
     2716
     27170/1 Literals \\
     2718user defined: D, Objective-C
    26792719
    26802720\section{Conclusion and Future Work}
     
    26832723While other programming languages purport to be a better C, they are in fact new and interesting languages in their own right, but not C extensions.
    26842724The purpose of this paper is to introduce \CFA, and showcase language features that illustrate the \CFA type-system and approaches taken to achieve the goal of evolutionary C extension.
    2685 The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions.
     2725The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, tuples, advanced control structures, and extended declarations, which all have complex interactions.
    26862726The work is a challenging design, engineering, and implementation exercise.
    26872727On the surface, the project may appear as a rehash of similar mechanisms in \CC.
     
    26902730Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    26912731
    2692 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, exceptions, concurrent primitives, modules, and user-defined conversions.
     2732There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.
    26932733(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.)
    26942734In addition, there are interesting future directions for the polymorphism design.
     
    27032743\section{Acknowledgments}
    27042744
    2705 The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, and Thierry Delisle on the features described in this paper, and thank Magnus Madsen for feedback in the writing.
    2706 This work is supported through a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are funded by the Natural Sciences and Engineering Research Council of Canada.
     2745The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, and Andrew Beach on the features described in this paper, and thank Magnus Madsen for feedback in the writing.
     2746This work is supported through a corporate partnership with Huawei Ltd.\ (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr are partially funded by the Natural Sciences and Engineering Research Council of Canada.
    27072747
    27082748% the first author's \grantsponsor{NSERC-PGS}{NSERC PGS D}{http://www.nserc-crsng.gc.ca/Students-Etudiants/PG-CS/BellandPostgrad-BelletSuperieures_eng.asp} scholarship.
  • doc/papers/general/evaluation/Makefile

    re6c5e79 r7b0dfa4  
    22CFA = cfa
    33DEPFLAGS = -MMD -MP
     4ifdef DBG
     5CFLAGS = -O0 -ggdb -DN=500
     6else
    47CFLAGS = -O2
    58ifdef N
    69CFLAGS += -DN=$(N)
     10endif
    711endif
    812CXXFLAGS = $(CFLAGS) --std=c++14
     
    2731        $(COMPILE.cfa) $(OUTPUT_OPTION) -c $<
    2832
    29 COBJS = c-stack.o c-pair.o c-print.o c-bench.o
     33COBJS = c-stack.o c-pair.o c-bench.o
    3034CPPOBJS = cpp-bench.o
    3135CPPVOBJS = cpp-vstack.o cpp-vbench.o
    32 CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o cfa-bench.o
     36CFAOBJS = cfa-stack.o cfa-pair.o cfa-bench.o
    3337
    3438${COBJS} ${CPPOBJS} ${CPPVOBJS} ${CFAOBJS} : ${MAKEFILE_NAME}
    3539
    3640CFILES = bench.h $(patsubst c-bench.h,,$(COBJS:.o=.h)) $(COBJS:.o=.c)
    37 CPPFILES = bench.hpp cpp-stack.hpp cpp-pair.hpp cpp-print.hpp $(CPPOBJS:.o=.cpp)
    38 CPPVFILES = bench.hpp object.hpp cpp-vprint.hpp $(patsubst cpp-vbench.hpp,,$(CPPVOBJS:.o=.hpp)) $(CPPVOBJS:.o=.cpp)
     41CPPFILES = bench.hpp cpp-stack.hpp cpp-pair.hpp $(CPPOBJS:.o=.cpp)
     42CPPVFILES = bench.hpp object.hpp $(patsubst cpp-vbench.hpp,,$(CPPVOBJS:.o=.hpp)) $(CPPVOBJS:.o=.cpp)
    3943CFAFILES = bench.h $(patsubst cfa-bench.h,,$(CFAOBJS:.o=.h)) $(CFAOBJS:.o=.c)
    4044
  • doc/papers/general/evaluation/bench.h

    re6c5e79 r7b0dfa4  
    55long ms_between(clock_t start, clock_t end) { return (end - start) / (CLOCKS_PER_SEC / 1000); }
    66
     7#ifndef N
    78#define N 40000000
     9#endif
     10
    811#define TIMED(name, code) { \
    912        volatile clock_t _start, _end; \
  • doc/papers/general/evaluation/bench.hpp

    re6c5e79 r7b0dfa4  
    66long ms_between(clock_t start, clock_t end) { return (end - start) / (CLOCKS_PER_SEC / 1000); }
    77
     8#ifndef N
    89static const int N = 40000000;
     10#endif
     11
    912#define TIMED(name, code) { \
    1013        volatile clock_t _start, _end; \
  • doc/papers/general/evaluation/c-bench.c

    re6c5e79 r7b0dfa4  
    44#include "c-pair.h"
    55#include "c-stack.h"
    6 #include "c-print.h"
    76
    87_Bool* new_bool( _Bool b ) {
     
    3938
    4039int main(int argc, char** argv) {
    41         FILE * out = fopen("/dev/null", "w");
    4240        int maxi = 0, vali = 42;
    4341        struct stack si = new_stack(), ti;
     
    5048                if ( *xi > maxi ) { maxi = *xi; }
    5149                free(xi); )
    52         REPEAT_TIMED( "print_int", N/2, print( out, "dsds", vali, ":", vali, "\n" ); /***/ )
    5350
    5451        struct pair * maxp = new_pair( new_bool(0), new_char('\0') ),
     
    6764                        free_pair_bool_char( xp ); /***/
    6865                } )
    69         REPEAT_TIMED( "print_pair", N/2, print( out, "pbcspbcs", *valp, ":", *valp, "\n" ); /***/ )
    7066        free_pair_bool_char( maxp ); /***/
    7167        free_pair_bool_char( valp ); /***/
    72         fclose(out);
    7368}
  • doc/papers/general/evaluation/cfa-bench.c

    re6c5e79 r7b0dfa4  
    1 #include <fstream>
    2 #include <stdlib>
    3 #include <stdbool.h>
    41#include "bench.h"
    52#include "cfa-stack.h"
    63#include "cfa-pair.h"
    7 #include "cfa-print.h"
    84
    95int main( int argc, char * argv[] ) {
    10         ofstream out = { "/dev/null" };
    116        int max = 0, val = 42;
    12         stack( int ) s, t;
     7        stack( int ) si, ti;
    138
    14         REPEAT_TIMED( "push_int", N, push( s, val ); )
    15         TIMED( "copy_int", t = s; )
    16         TIMED( "clear_int", clear( s ); )
    17         REPEAT_TIMED( "pop_int", N, int x = pop( t ); max = max( x, max ); )
    18         REPEAT_TIMED( "print_int", N/2, out | val | ':' | val | endl; )
     9        REPEAT_TIMED( "push_int", N, push( si, val ); )
     10        TIMED( "copy_int", ti = si; )
     11        TIMED( "clear_int", clear( si ); )
     12        REPEAT_TIMED( "pop_int", N,
     13                int x = pop( ti ); if ( x > max ) max = x; )
    1914
    20         pair( _Bool, char ) max = { (_Bool)false, '\0' }, val = { (_Bool)true, 'a' };
    21         stack( pair( _Bool, char ) ) s, t;
     15        pair( _Bool, char ) max = { (_Bool)0 /***/, '\0' }, val = { (_Bool)1 /***/, 'a' };
     16        stack( pair( _Bool, char ) ) sp, tp;
    2217
    23         REPEAT_TIMED( "push_pair", N, push( s, val ); )
    24         TIMED( "copy_pair", t = s; )
    25         TIMED( "clear_pair", clear( s ); )
    26         REPEAT_TIMED( "pop_pair", N, pair(_Bool, char) x = pop( t ); max = max( x, max ); )
    27         REPEAT_TIMED( "print_pair", N/2, out | val | ':' | val | endl; )
     18        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
     19        TIMED( "copy_pair", tp = sp; )
     20        TIMED( "clear_pair", clear( sp ); )
     21        REPEAT_TIMED( "pop_pair", N,
     22                pair(_Bool, char) x = pop( tp ); if ( x > max ) max = x; )
    2823}
  • doc/papers/general/evaluation/cfa-pair.c

    re6c5e79 r7b0dfa4  
    3636}
    3737
    38 forall(otype R, otype S)
    39 forall(dtype ostype | ostream( ostype ) | { ostype & ?|?( ostype &, R ); ostype & ?|?( ostype &, S );  })
    40 ostype & ?|?( ostype & os, pair(R, S) p ) {
    41         return os | '[' | p.first | ',' | p.second | ']';
    42 } // ?|?
     38// forall(otype R, otype S)
     39// forall(dtype ostype | ostream( ostype ) | { ostype & ?|?( ostype &, R ); ostype & ?|?( ostype &, S );  })
     40// ostype & ?|?( ostype & os, pair(R, S) p ) {
     41//      return os | '[' | p.first | ',' | p.second | ']';
     42// } // ?|?
  • doc/papers/general/evaluation/cfa-pair.h

    re6c5e79 r7b0dfa4  
    3030int ?>=?(pair(R, S) p, pair(R, S) q);
    3131
    32 forall(otype R, otype S)
    33 forall(dtype ostype | ostream( ostype ) | { ostype & ?|?( ostype &, pair(R, S) ); })
    34 ostype & ?|?( ostype & os, pair(R, S) );
     32// forall(otype R, otype S)
     33// forall(dtype ostype | ostream( ostype ) | { ostype & ?|?( ostype &, R ); ostype & ?|?( ostype &, S ); })
     34// ostype & ?|?( ostype & os, pair(R, S) );
  • doc/papers/general/evaluation/cfa-stack.c

    re6c5e79 r7b0dfa4  
    66        stack_node(T) * next;
    77};
    8 forall(otype T) void ?{}( stack_node(T) & node, T value, stack_node(T) * next ) {
    9     node.value = value;
    10     node.next = next;
    11 }
    128
    139forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     
    1612        stack_node(T) ** crnt = &s.head;
    1713        for ( stack_node(T) * next = t.head; next; next = next->next ) {
    18                 // *crnt = new( next->value, 0 );
    19                 stack_node(T)* new_node = ((stack_node(T)*)malloc());
    20                 (*new_node){ next->value }; /***/
     14                stack_node(T)* new_node = (stack_node(T)*)malloc(); /***/
     15                (*new_node){ next->value };
    2116                *crnt = new_node;
    22                 stack_node(T) * acrnt = *crnt;
    23                 crnt = &acrnt->next;
     17                crnt = &(*crnt)->next;
    2418        }
    2519        *crnt = 0;
     
    3832
    3933forall(otype T) void push( stack(T) & s, T value ) {
    40         // s.head = new( value, s.head );
    41         stack_node(T)* new_node = ((stack_node(T)*)malloc());
    42         (*new_node){ value, s.head }; /***/
     34        stack_node(T)* new_node = (stack_node(T)*)malloc(); /***/
     35        (*new_node){ value, s.head };
    4336        s.head = new_node;
    4437}
     
    4841        s.head = n->next;
    4942        T v = n->value;
    50         delete( n );
     43        ^(*n){};
     44        free( n );
    5145        return v;
    5246}
     
    5650                stack_node(T) * crnt = next;
    5751                next = crnt->next;
    58                 delete( crnt );
     52                ^(*crnt){};
     53                free(crnt);
    5954        }
    6055        s.head = 0;
  • doc/papers/general/evaluation/cpp-bench.cpp

    re6c5e79 r7b0dfa4  
    11#include <algorithm>
    2 #include <fstream>
    32#include "bench.hpp"
    43#include "cpp-stack.hpp"
    54#include "cpp-pair.hpp"
    6 #include "cpp-print.hpp"
    75
    86int main(int argc, char** argv) {
    9         std::ofstream out{"/dev/null"};
    107        int maxi = 0, vali = 42;
    118        stack<int> si, ti;
     
    1512        TIMED( "clear_int", si.clear(); )
    1613        REPEAT_TIMED( "pop_int", N, maxi = std::max( maxi, ti.pop() ); )
    17         REPEAT_TIMED( "print_int", N/2, print( out, vali, ":", vali, "\n" ); )
    1814
    1915        pair<bool, char> maxp = { false, '\0' }, valp = { true, 'a' };
     
    2420        TIMED( "clear_pair", sp.clear(); )
    2521        REPEAT_TIMED( "pop_pair", N, maxp = std::max( maxp, tp.pop() ); )
    26         REPEAT_TIMED( "print_pair", N/2, print( out, valp, ":", valp, "\n" ); )
    2722}
  • doc/papers/general/evaluation/cpp-vbench.cpp

    re6c5e79 r7b0dfa4  
    11#include <algorithm>
    2 #include <fstream>
    32#include "bench.hpp"
    43#include "cpp-vstack.hpp"
    5 #include "cpp-vprint.hpp"
    64#include "object.hpp"
    75
    86int main(int argc, char** argv) {
    9         std::ofstream out{"/dev/null"};
    107        integer maxi{ 0 }, vali{ 42 };
    118        stack si, ti;
     
    1512        TIMED( "clear_int", si.clear(); )
    1613        REPEAT_TIMED( "pop_int", N, maxi = std::max( maxi, ti.pop()->as<integer>() ); /***/ )
    17         REPEAT_TIMED( "print_int", N/2, print( out, vali, c_string{":"}, vali, c_string{"\n"} ); )
    1814
    1915        ptr<pair> maxp = make<pair>( make<boolean>(false), make<character>('\0') );
     
    2723                ptr<pair> xp = as_ptr<pair>( tp.pop() ); /***/
    2824                if ( *xp > *maxp ) { maxp = std::move(xp); } )
    29         REPEAT_TIMED( "print_pair", N/2, print( out, valp, c_string{":"}, valp, c_string{"\n"} ); )
    3025}
  • doc/papers/general/evaluation/timing.dat

    re6c5e79 r7b0dfa4  
    11"400 million repetitions"       "C"     "\\CFA{}"       "\\CC{}"        "\\CC{obj}"
    2 "push\nint"     3002    2459    1520    3305
    3 "copy\nint"     2985    2057    1521    3152
    4 "clear\nint"    1374    827     718     1469
    5 "pop\nint"      1416    1221    717     5467
    6 "print\nint"    5656    6758    3120    3121
    7 "push\npair"    4214    2752    946     6826
    8 "copy\npair"    6127    2105    993     7330
    9 "clear\npair"   2881    885     711     3564
    10 "pop\npair"     3046    5434    783     26538
    11 "print\npair"   7514    10714   8717    16525
     2"push\nint"     2976    2225    1522    3266
     3"copy\nnt"      2932    7072    1526    3110
     4"clear\nint"    1380    731     750     1488
     5"pop\nint"      1444    1196    756     5156
     6"push\npair"    3695    2257    953     6840
     7"copy\npair"    6034    6650    994     7224
     8"clear\npair"   2832    848     742     3297
     9"pop\npair"     3009    5348    797     25235
     10
Note: See TracChangeset for help on using the changeset viewer.