Changeset 6f71276


Ignore:
Timestamp:
Apr 3, 2017, 2:29:11 PM (5 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
bbc9b64
Parents:
8396044 (diff), 7444113 (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 plg2:software/cfa/cfa-cc

Files:
7 edited

Legend:

Unmodified
Added
Removed
  • doc/bibliography/cfa.bib

    r8396044 r6f71276  
    860860}
    861861
    862 @manual{C11,
     862@techreport{C11,
     863    type = {International Standard},
    863864    keywords    = {ISO/IEC C 11},
    864865    contributer = {pabuhr@plg},
    865     key         = {C11},
     866    key         = {{ISO/IEC} 9889-2011},
    866867    title       = {American National Standard Information technology -- Programming Languages -- {C}},
    867     organization= {International Standard ISO/IEC 9899-2011[2012]},
    868     publisher   = {International Standard Organization},
     868    institution = {International Standard Organization},
    869869    address     = {http://www.iso.org},
    870870    year        = 2012,
    871871}
    872872
    873 @manual{C++Concepts,
     873@techreport{C++Concepts,
     874    type = {International Standard},
    874875    keywords    = {ISO/IEC TS 19217:2015},
    875876    contributer = {a3moss@uwaterloo.ca},
    876     key         = {C++ Concepts},
     877    key         = {{ISO/IEC} {TS} 19217},
    877878    title       = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts},
    878     organization= {International Standard ISO/IEC TS 19217:2015},
    879     publisher   = {International Standard Organization},
     879    institution = {International Standard Organization},
    880880    address     = {http://www.iso.org},
    881881    year        = 2015
  • doc/generic_types/.gitignore

    r8396044 r6f71276  
    1616*.lot
    1717*.synctex.gz
     18comment.cut
  • doc/generic_types/generic_types.tex

    r8396044 r6f71276  
    2929\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
    3030
    31 \newcommand{\TODO}{\textbf{TODO}}
     31\newcommand{\TODO}[1]{\textbf{TODO}: #1} % TODO included
     32%\newcommand{\TODO}[1]{} % TODO elided
    3233\newcommand{\eg}{\textit{e}.\textit{g}.,\xspace}
    3334\newcommand{\ie}{\textit{i}.\textit{e}.,\xspace}
     
    123124\maketitle
    124125
    125 
    126126\section{Introduction \& Background}
    127127
     
    146146int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
    147147\end{lstlisting}
    148 The @identity@ function above can be applied to any complete object-type (or ``@otype@''). The type variable @T@ is transformed into a set of additional implicit parameters to @identity@ that encode sufficient information about @T@ to create and return a variable of that type. The \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. If this extra information is not needed, e.g., for a pointer, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.
     148The @identity@ function above can be applied to any complete object-type (or ``@otype@''). The type variable @T@ is transformed into a set of additional implicit parameters to @identity@ that encode sufficient information about @T@ to create and return a variable of that type. The \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. If this extra information is not needed, \eg for a pointer, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.
    149149
    150150Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC virtual function calls. An advantage of this design is that, unlike \CC template functions, \CFA @forall@ functions are compatible with C separate compilation.
     
    281281};
    282282\end{lstlisting}
    283 Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @sum@ function produces generated code something like the following (simplified for clarity and brevity) \TODO{} fix example, maybe elide, it's likely too long with the more complicated function:
     283Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @sum@ function produces generated code something like the following (simplified for clarity and brevity)\TODO{fix example, maybe elide, it's likely too long with the more complicated function}:
    284284\begin{lstlisting}
    285285void abs( size_t _sizeof_M, size_t _alignof_M,
     
    387387\subsection{Dynamic Generic Types}
    388388
    389 Though \CFA implements concrete generic types efficiently, it also has a fully general system for computing with dynamic generic types. As 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. Dynamic generic structs have the same size and alignment parameter, and also an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0; the size and alignment parameters are still provided for dynamic unions, however.}. Access to members\footnote{The \lstinline@offsetof@ macro is implemented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where necessary.
     389Though \CFA implements concrete generic types efficiently, it also has a fully general system for computing with dynamic generic types. As 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. Dynamic generic structs also have implicit size and alignment parameters, and also an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0; the size and alignment parameters are still provided for dynamic unions, however.}. Access to members\footnote{The \lstinline@offsetof@ macro is implemented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where necessary.
    390390
    391391These offset arrays are statically generated where possible. If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume that the generic type is complete (that is, has a known layout) at any call-site, and the offset array is passed from the caller; if the generic type is concrete at the call site the elements of this offset array can even be statically generated using the C @offsetof@ macro. As an example, @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 in to @value@ for @pair(const char*, T)@. The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) };@.
     
    521521In \CFA, each of these calls is valid. In the call to @f@, @x@ is implicitly flattened so that the components of @x@ are passed as the two arguments to @f@. For the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the type of the parameter of @g@. Finally, in the call to @h@, @y@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@. The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure.
    522522
    523 In {K-W C}~\citep{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring. Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
     523% In {K-W C} \citep{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring. Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
    524524
    525525In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations. Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match. In resolving a function call expression, each combination of function value and list of argument alternatives is examined. Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions. Then the flattened list of expressions is compared with each value in the function's parameter list. If the parameter's type is not a tuple type, then the current argument value is unified with the parameter type, and on success the next argument and parameter are examined. If the parameter's type is a tuple type, then the structuring conversion takes effect, recursively applying the parameter matching algorithm using the tuple's component types as the parameter list types. Assuming a successful unification, eventually the algorithm gets to the end of the tuple type, which causes all of the matching expressions to be consumed and structured into a tuple expression. For example, in
     
    630630  [int, [int, int], int] g();
    631631
    632   ([int, double])f();           // (1)
    633   ([int, int, int])g();         // (2)
    634   ([void, [int, int]])g();      // (3)
    635   ([int, int, int, int])g();    // (4)
    636   ([int, [int, int, int]])g();  // (5)
     632  ([int, double])f();           $\C{// (1)}$
     633  ([int, int, int])g();         $\C{// (2)}$
     634  ([void, [int, int]])g();      $\C{// (3)}$
     635  ([int, int, int, int])g();    $\C{// (4)}$
     636  ([int, [int, int, int]])g();  $\C{// (5)}$
    637637\end{lstlisting}
    638638
     
    767767In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@.
    768768
    769 \TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
     769\TODO{Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).}
    770770
    771771\subsection{Implementation}
     
    850850The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions. A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg in a unique expression. The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language. However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new.
    851851
     852\section{Evaluation}
     853
     854\TODO{Magnus suggests we need some graphs, it's kind of a done thing that the reviewers will be looking for. Also, we've made some unsubstantiated claims about the runtime performance of \CFA, which some micro-benchmarks could help with. I'm thinking a simple stack push and pop, with an idiomatic \lstinline@void*@, \CFA, \CC template and \CC virtual inheritance versions (the void* and virtual inheritance versions likely need to be linked lists, or clumsy in their API -- possibly both versions) to test generics, and variadic print to test tuples. We measure SLOC, runtime performance, executable size (making sure to include benchmarks for multiple types in the executable), and possibly manually count the number of places where the programmer must provide un-type-checked type information. Appendices don't count against our page limit, so we might want to include the source code for the benchmarks (or at least the relevant implementation details) in one.}
     855
    852856\section{Related Work}
    853857
     
    856860Cyclone also provides capabilities for polymorphic functions and existential types~\citep{Grossman06}, similar in concept to \CFA's @forall@ functions and generic types. Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, a tedious and potentially error-prone process. Furthermore, Cyclone's polymorphic functions and types are restricted in that they may only abstract over types with the same layout and calling convention as @void*@, in practice only pointer types and @int@ - in \CFA terms, all Cyclone polymorphism must be dtype-static. This design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, but is more restrictive than \CFA's more general model.
    857861
    858 Go and Rust are both modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in Go and \emph{traits} in Rust. However, both languages represent dramatic departures from C in terms of language model, and neither has the same level of compatibility with C as \CFA. Go is a garbage-collected language, imposing the associated runtime overhead, and complicating foreign-function calls with the necessity of accounting for data transfer between the managed Go runtime and the unmanaged C runtime. Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more. Rust is not garbage-collected, and thus has a lighter-weight runtime that is more easily interoperable with C. It also possesses much more powerful abstraction capabilities for writing generic code than Go. On the other hand, Rust's borrow-checker, while it does provide strong safety guarantees, is complex and difficult to learn, and imposes a distinctly idiomatic programming style on Rust. \CFA, with its more modest safety features, is significantly easier to port C code to, while maintaining the idiomatic style of the original source.
     862Go \citep{Go} and Rust \citep{Rust} are both modern, compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in Go and \emph{traits} in Rust. However, both languages represent dramatic departures from C in terms of language model, and neither has the same level of compatibility with C as \CFA. Go is a garbage-collected language, imposing the associated runtime overhead, and complicating foreign-function calls with the necessity of accounting for data transfer between the managed Go runtime and the unmanaged C runtime. Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more. Rust is not garbage-collected, and thus has a lighter-weight runtime that is more easily interoperable with C. It also possesses much more powerful abstraction capabilities for writing generic code than Go. On the other hand, Rust's borrow-checker, while it does provide strong safety guarantees, is complex and difficult to learn, and imposes a distinctly idiomatic programming style on Rust. \CFA, with its more modest safety features, is significantly easier to port C code to, while maintaining the idiomatic style of the original source.
    859863
    860864\section{Conclusion \& Future Work}
     
    863867
    864868\begin{acks}
     869The authors would like to thank Magnus Madsen for valuable editorial feedback.
     870
    865871This work is supported in part by a corporate partnership with \grantsponsor{Huawei}{Huawei Ltd.}{http://www.huawei.com}\ and 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.
    866872\end{acks}
  • src/GenPoly/InstantiateGeneric.cc

    r8396044 r6f71276  
    255255                }
    256256
    257                 assert( baseParam == baseParams.end() && param == params.end() && "Type parameters should match type variables" );
     257                assertf( baseParam == baseParams.end() && param == params.end(), "Type parameters should match type variables" );
    258258                return gt;
    259259        }
  • src/ResolvExpr/PtrsCastable.cc

    r8396044 r6f71276  
    6868                return 1;
    6969        }
     70        int functionCast( Type *src, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
     71                return -1 * objectCast( src, env, indexer );  // reverse the sense of objectCast
     72        }
    7073
    7174        int ptrsCastable( Type *src, Type *dest, const TypeEnvironment &env, const SymTab::Indexer &indexer ) {
     
    106109
    107110        void PtrsCastable::visit(FunctionType *functionType) {
    108                 result = -1;
     111                // result = -1;
     112                result = functionCast( dest, env, indexer );
    109113        }
    110114
     
    136140
    137141        void PtrsCastable::visit(TypeInstType *inst) {
    138                 result = objectCast( inst, env, indexer ) > 0 && objectCast( dest, env, indexer ) > 0 ? 1 : -1;
     142                //result = objectCast( inst, env, indexer ) > 0 && objectCast( dest, env, indexer ) > 0 ? 1 : -1;
     143                result = objectCast( inst, env, indexer ) == objectCast( dest, env, indexer ) ? 1 : -1;
    139144        }
    140145
  • src/ResolvExpr/Unify.cc

    r8396044 r6f71276  
    134134                  case TypeDecl::Ftype:
    135135                        return isFtype( type, indexer );
    136                         case TypeDecl::Ttype:
     136                  case TypeDecl::Ttype:
    137137                        // ttype unifies with any tuple type
    138138                        return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
     
    592592                for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
    593593                        TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
    594                         assert(param && "Aggregate parameters should be type expressions");
     594                        assertf(param, "Aggregate parameters should be type expressions");
    595595                        TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
    596                         assert(otherParam && "Aggregate parameters should be type expressions");
    597 
    598                         if ( ! unifyExact( param->get_type(), otherParam->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
     596                        assertf(otherParam, "Aggregate parameters should be type expressions");
     597                       
     598                        Type* paramTy = param->get_type();
     599                        Type* otherParamTy = otherParam->get_type();
     600
     601                        bool tupleParam = Tuples::isTtype( paramTy );
     602                        bool otherTupleParam = Tuples::isTtype( otherParamTy );
     603
     604                        if ( tupleParam && otherTupleParam ) {
     605                                ++it; ++jt;  // skip ttype parameters for break
     606                        } else if ( tupleParam ) {
     607                                // bundle other parameters into tuple to match
     608                                TupleType* binder = new TupleType{ paramTy->get_qualifiers() };
     609
     610                                do {
     611                                        binder->get_types().push_back( otherParam->get_type()->clone() );
     612                                        ++jt;
     613
     614                                        if ( jt == otherParams.end() ) break;
     615
     616                                        otherParam = dynamic_cast< TypeExpr* >(*jt);
     617                                        assertf(otherParam, "Aggregate parameters should be type expressions");
     618                                } while (true);
     619
     620                                otherParamTy = binder;
     621                                ++it;  // skip ttype parameter for break
     622                        } else if ( otherTupleParam ) {
     623                                // bundle parameters into tuple to match other
     624                                TupleType* binder = new TupleType{ otherParamTy->get_qualifiers() };
     625
     626                                do {
     627                                        binder->get_types().push_back( param->get_type()->clone() );
     628                                        ++it;
     629
     630                                        if ( it == params.end() ) break;
     631
     632                                        param = dynamic_cast< TypeExpr* >(*it);
     633                                        assertf(param, "Aggregate parameters should be type expressions");
     634                                } while (true);
     635
     636                                paramTy = binder;
     637                                ++jt;  // skip ttype parameter for break
     638                        }
     639
     640                        if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
    599641                                result = false;
    600642                                return;
    601643                        }
     644
     645                        // ttype parameter should be last
     646                        if ( tupleParam || otherTupleParam ) break;
    602647                }
    603648                result = ( it == params.end() && jt == otherParams.end() );
  • src/libcfa/startup.h

    r8396044 r6f71276  
    1818#define STARTUP_H
    1919
     20#if GCC_VERSION > 50000
    2021extern "C" {
    2122        enum {
     
    2627        };
    2728}
     29#else
     30#define STARTUP_PRIORITY_CORE       101
     31#define STARTUP_PRIORITY_KERNEL     102
     32#define STARTUP_PRIORITY_MEMORY     103
     33#define STARTUP_PRIORITY_IOSTREAM   104
     34#endif
    2835
    2936#endif //STARTUP_H
Note: See TracChangeset for help on using the changeset viewer.