Changes in / [c2bfb31:c4187df]
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/generic_types.tex
rc2bfb31 rc4187df 42 42 literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1 43 43 {~}{\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, 45 45 % moredelim=**[is][\color{red}]{®}{®}, % red highlighting ®...® (registered trademark symbol) emacs: C-q M-. 46 46 % moredelim=**[is][\color{blue}]{ß}{ß}, % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ … … 70 70 } 71 71 \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} 72 96 73 97 \terms{generic, types} … … 115 139 \begin{lstlisting} 116 140 forall(otype T) 117 T identity(T x) { 141 T identity(T x) {is_ 118 142 return x; 119 143 } … … 121 145 int forty_two = identity(42); // T is bound to int, forty_two == 42 122 146 \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. 147 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. If this extra information is not needed, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''. 148 149 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. An advantage of this design is that, unlike \CC{} template functions, \CFA{} @forall@ functions are compatible with separate compilation. 124 150 125 151 Since 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: … … 166 192 \end{lstlisting} 167 193 194 @otype@ is essentially syntactic sugar for the following trait: 195 \begin{lstlisting} 196 trait 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 168 205 Semantically, 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: 169 206 \begin{lstlisting} … … 200 237 While 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. 201 238 239 \section{Generic Types} 240 241 The 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 243 A 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} 245 forall(otype R, otype S) struct pair { 246 R first; 247 S second; 248 }; 249 250 forall(otype T) 251 T value( pair(const char*, T) *p ) { return p->second; } 252 253 forall(dtype F, otype T) 254 T value_p( pair(F*, T*) p ) { return *p.second; } 255 256 pair(const char*, int) p = { "magic", 42 }; 257 int magic = value( &p ); 258 259 pair(void*, int*) q = { 0, &p.second }; 260 magic = value_p( q ); 261 double d = 1.0; 262 pair(double*, double*) r = { &d, &d }; 263 d = 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 268 The \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} 270 struct _pair_conc1 { 271 const char* first; 272 int second; 273 }; 274 \end{lstlisting} 275 276 A 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} 278 struct _pair_conc0 { 279 void* first; 280 void* second; 281 }; 282 \end{lstlisting} 283 284 \TODO{} Maybe move this after the rest of the discussion. 285 This 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} 287 forall(dtype T) 288 int 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} 294 Since @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 202 312 \bibliographystyle{ACM-Reference-Format} 203 313 \bibliography{generic_types}
Note: See TracChangeset
for help on using the changeset viewer.