Changeset 06ccbc7


Ignore:
Timestamp:
Mar 22, 2017, 5:17:03 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
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:
c4187df
Parents:
1c2c253
Message:

Further updates to generics paper

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    r1c2c253 r06ccbc7  
    4242literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
    4343        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
    44         {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2,
     44        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{$\rightarrow$}2,
    4545% moredelim=**[is][\color{red}]{®}{®},                                  % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    4646% moredelim=**[is][\color{blue}]{ß}{ß},                                 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
     
    7070}
    7171\email{a3moss@uwaterloo.ca}
     72
     73\author{Robert Schluntz}
     74\affiliation{%
     75        \institution{University of Waterloo}
     76        \department{David R. Cheriton School of Computer Science}
     77        \streetaddress{Davis Centre, University of Waterloo}
     78        \city{Waterloo}
     79        \state{ON}
     80        \postcode{N2L 3G1}
     81        \country{Canada}
     82}
     83\email{rschlunt@uwaterloo.ca}
     84
     85\author{Peter Buhr}
     86\affiliation{%
     87        \institution{University of Waterloo}
     88        \department{David R. Cheriton School of Computer Science}
     89        \streetaddress{Davis Centre, University of Waterloo}
     90        \city{Waterloo}
     91        \state{ON}
     92        \postcode{N2L 3G1}
     93        \country{Canada}
     94}
     95\email{pabuhr@uwaterloo.ca}
    7296
    7397\terms{generic, types}
     
    115139\begin{lstlisting}
    116140forall(otype T)
    117 T identity(T x) {
     141T identity(T x) {is_
    118142    return x;
    119143}
     
    121145int forty_two = identity(42); // T is bound to int, forty_two == 42
    122146\end{lstlisting}
    123 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@, which 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. Here, 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.
     147The @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@, which 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, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.
     148
     149Here, 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 separate compilation.
    124150
    125151Since bare polymorphic types do not provide a great range of available operations, \CFA{} provides a \emph{type assertion} mechanism to provide further information about a type:
     
    166192\end{lstlisting}
    167193
     194@otype@ is essentially syntactic sugar for the following trait:
     195\begin{lstlisting}
     196trait otype(dtype T | sized(T)) {
     197        // sized is a compiler-provided pseudo-trait for types with known size & alignment
     198        void ?{}(T*);  // default constructor
     199        void ?{}(T*, T);  // copy constructor
     200        T ?=?(T*, T);  // assignment operator
     201        void ^?{}(T*);  // destructor
     202};
     203\end{lstlisting}
     204
    168205Semantically, traits are simply a named lists of type assertions, but they may be used for many of the same purposes that interfaces in Java or abstract base classes in \CC{} are used for. Unlike Java interfaces or \CC{} base classes, \CFA{} types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to implementation of an interface in Go, as opposed to the nominal inheritance model of Java and \CC{}. Nominal inheritance can be simulated with traits using marker variables or functions:
    169206\begin{lstlisting}
     
    200237While a nominal-inheritance system with associated types could model one of those two relationships by making @El@ an associated type of @Ptr@ in the @pointer_like@ implementation, few such systems could model both relationships simultaneously.
    201238
     239\section{Generic Types}
     240
     241The generic types design for \CFA{} must integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backwards compatibility with C; maintaining separate compilation is a particularly important constraint on the design. However, where the concrete parameters of the generic type are known, there should not be extra overhead for the use of a generic type.
     242
     243A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration, and instantiated using a parenthesized list of types after the type name:
     244\begin{lstlisting}
     245forall(otype R, otype S) struct pair {
     246    R first;
     247    S second;
     248};
     249
     250forall(otype T)
     251T value( pair(const char*, T) *p ) { return p->second; }
     252
     253forall(dtype F, otype T)
     254T value_p( pair(F*, T*) p ) { return *p.second; }
     255
     256pair(const char*, int) p = { "magic", 42 };
     257int magic = value( &p );
     258
     259pair(void*, int*) q = { 0, &p.second };
     260magic = value_p( q );
     261double d = 1.0;
     262pair(double*, double*) r = { &d, &d };
     263d = value_p( r );
     264\end{lstlisting}
     265
     266\CFA{} classifies generic types as either \emph{concrete} or \emph{dynamic}. Dynamic generic types vary in their in-memory layout depending on their type parameters, while concrete generic types have a fixed memory layout regardless of type parameters. A type may have polymorphic parameters but still be concrete; \CFA{} refers to such types as \emph{dtype-static}. Polymorphic pointers are an example of dtype-static types -- @forall(dtype T) T*@ is a polymorphic type, but for any @T@ chosen, @T*@ will have exactly the same in-memory representation as a @void*@, and can therefore be represented by a @void*@ in code generation.
     267
     268The \CFA{} compiler instantiates concrete generic types by template-expanding them to fresh struct types; concrete generic types can therefore be used with zero runtime overhead. To enable interoperation between equivalent instantiations of a generic type, the compiler saves the set of instantiations currently in scope and re-uses the generated struct declarations where appropriate. As an example, the concrete instantiation for @pair(const char*, int)@ would look something like this:
     269\begin{lstlisting}
     270struct _pair_conc1 {
     271        const char* first;
     272        int second;
     273};
     274\end{lstlisting}
     275
     276A concrete generic type with dtype-static parameters is also expanded to a struct type, but this struct type is used for all matching instantiations. In the example above, the @pair(F*, T*)@ parameter to @value_p@ is such a type; its expansion would look something like this, and be used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
     277\begin{lstlisting}
     278struct _pair_conc0 {
     279        void* first;
     280        void* second;
     281};
     282\end{lstlisting}
     283
     284\TODO{} Maybe move this after the rest of the discussion.
     285This re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers:
     286\begin{lstlisting}
     287forall(dtype T)
     288int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
     289        int c = cmp(a->first, b->first);
     290        if ( c == 0 ) c = cmp(a->second, b->second);
     291        return c;
     292}
     293\end{lstlisting}
     294Since @pair(T*, T*)@ is a concrete type, there are no added implicit parameters to @lexcmp@, so the code generated by \CFA{} will be effectively identical to a version of this written in standard C using @void*@, yet the \CFA{} version will be type-checked to ensure that the fields of both pairs and the arguments to the comparison function match in type.
     295
     296\TODO{} The second is zero-cost ``tag'' structs.
     297
     298\section{Tuples}
     299
     300\TODO{} Integrate Rob's work
     301
     302\TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
     303
     304\section{Related Work}
     305
     306\TODO{} Talk about \CC{}, Cyclone, \etc{}
     307
     308\section{Conclusion}
     309
     310\TODO{}
     311
    202312\bibliographystyle{ACM-Reference-Format}
    203313\bibliography{generic_types}
Note: See TracChangeset for help on using the changeset viewer.