- Timestamp:
- Apr 6, 2017, 10:54:26 AM (7 years ago)
- 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:
- 221c2de7, 3db60cb
- Parents:
- 2264c11
- Location:
- doc/generic_types
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/acmart.cls
r2264c11 r115a868c 354 354 \let\@footnotemark@nolink\@footnotemark 355 355 \let\@footnotetext@nolink\@footnotetext 356 \RequirePackage[bookmarksnumbered ]{hyperref}356 \RequirePackage[bookmarksnumbered,breaklinks]{hyperref} 357 357 \urlstyle{rm} 358 358 \ifcase\ACM@format@nr -
doc/generic_types/generic_types.tex
r2264c11 r115a868c 51 51 stringstyle=\tt, % use typewriter font 52 52 tabsize=4, % 4 space tabbing 53 xleftmargin=\parindent ,% indent code to paragraph indentation53 xleftmargin=\parindentlnth, % indent code to paragraph indentation 54 54 %mathescape=true, % LaTeX math escape in CFA code $...$ 55 55 escapechar=\$, % LaTeX escape in CFA code … … 167 167 int forty_two = identity( 42 ); $\C{// T is bound to int, forty\_two == 42}$ 168 168 \end{lstlisting} 169 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 encoding 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''.170 171 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 is similar to \CC virtual function calls. An advantage of this design is that, unlike \CC template functions, \CFA @forall@ functions are compatible with C \emph{separate} compilation.169 The @identity@ function above can be applied to any complete \emph{object type} (or @otype@). The 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. 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 a \emph{data type} (or @dtype@). 170 171 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 is similar to \CC virtual function calls. An advantage of this design is that, unlike \CC template functions, \CFA polymorphic functions are compatible with C \emph{separate} compilation, preventing code bloat. 172 172 173 173 Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable. For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: … … 176 176 int val = twice( twice( 3.7 ) ); 177 177 \end{lstlisting} 178 which works for any type @T@ with a matching addition operator. The 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@. 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 in its type analysis. The first approach has a late conversion from @int@ to @double@ on the final assignment, while the second has an eager conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. 179 180 Monomorphic specializations of polymorphic functions can satisfy polymorphic type-assertions. 181 % \begin{lstlisting} 182 % forall(otype T `| { T twice(T); }`) $\C{// type assertion}$ 183 % T four_times(T x) { return twice( twice(x) ); } 184 % double twice(double d) { return d * 2.0; } $\C{// (1)}$ 185 % double magic = four_times(10.5); $\C{// T bound to double, uses (1) to satisfy type assertion}$ 186 % \end{lstlisting} 187 \begin{lstlisting} 188 forall( otype T `| { int ?<?( T, T ); }` ) void qsort( const T * arr, size_t size ); 189 forall( otype T `| { int ?<?( T, T ); }` ) T * bsearch( T key, const T * arr, size_t size ); 190 double vals[10] = { /* 10 floating-point values */ }; 191 qsort( vals, 10 ); $\C{// sort array}$ 192 double * val = bsearch( 5.0, vals, 10 ); $\C{// binary search sorted array for key}$ 193 \end{lstlisting} 194 @qsort@ and @bsearch@ work for any type @T@ with a matching @<@ operator, and the built-in monomorphic specialization of @<@ for type @double@ is passed as an implicit parameter to the calls of @qsort@ and @bsearch@. 195 196 Crucial to the design of a new programming language are the libraries to access thousands of external features. 197 \CFA inherits a massive compatible library-base, where other programming languages have to rewrite or provide fragile inter-language communication with C. 198 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@, shown here searching a floating-point array: 178 which works for any type @T@ with a matching addition operator. The 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@. 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{Ada} in its type analysis. The first approach has a late conversion from @int@ to @double@ on the final assignment, while the second has an eager conversion to @int@. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach, which corresponds with C-programmer intuition. 179 180 Crucial to the design of a new programming language are the libraries to access thousands of external software features. 181 \CFA inherits a massive compatible library-base, where other programming languages must rewrite or provide fragile inter-language communication with C. 182 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted floating-point array: 199 183 \begin{lstlisting} 200 184 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size, … … 202 186 int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 : 203 187 *(double *)t2 < *(double *)t1 ? 1 : 0; } 188 double vals[10] = { /* 10 floating-point values */ }; 204 189 double key = 5.0; 205 double * val = (double *)bsearch( &key, vals, size, sizeof(vals[0]), comp );206 \end{lstlisting} 207 which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrapper :190 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$ 191 \end{lstlisting} 192 which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrappers: 208 193 \begin{lstlisting} 209 194 forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) { 210 195 int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ } 211 return (T *)bsearch( &key, arr, size, sizeof(T), comp ); 212 } 196 return (T *)bsearch( &key, arr, size, sizeof(T), comp ); } 213 197 forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) { 214 198 T *result = bsearch( key, arr, size ); $\C{// call first version}$ 215 return result ? result - arr : size; $\C{// pointer subtraction includes sizeof(T)}$ 216 } 199 return result ? result - arr : size; } $\C{// pointer subtraction includes sizeof(T)}$ 217 200 double * val = bsearch( 5.0, vals, 10 ); $\C{// selection based on return type}$ 218 201 int posn = bsearch( 5.0, vals, 10 ); … … 222 205 \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@. 223 206 224 Call-site inferencing and nested functions provide a localized form of inheritance. For example, @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour: 225 \begin{lstlisting} 226 { 227 int ?<?( double x, double y ) { return x `>` y; } $\C{// override behaviour}$ 207 \CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations. 208 For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@: 209 \begin{lstlisting} 210 forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)(void *)malloc( (size_t)sizeof(T) ); } 211 int * ip = malloc(); $\C{// select type and size from left-hand side}$ 212 double * dp = malloc(); 213 struct S {...} * sp = malloc(); 214 \end{lstlisting} 215 where the return type supplies the type/size of the allocation, which is impossible in most type systems. 216 217 Call-site inferencing and nested functions provide a localized form of inheritance. For example, the \CFA @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour: 218 \begin{lstlisting} 219 forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ } 220 { int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behaviour}$ 228 221 qsort( vals, size ); $\C{// descending sort}$ 229 222 } … … 251 244 \smallskip\par\noindent 252 245 Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@. 246 As well, restricted constant overloading is allowed for the values @0@ and @1@, which have special status in C, \eg the value @0@ is both an integer and a pointer literal, so its meaning depends on context. 247 In addition, several operations are defined in terms values @0@ and @1@. 248 For example, 249 \begin{lstlisting} 250 int x; 251 if (x) // if (x != 0) 252 x++; // x += 1; 253 \end{lstlisting} 254 Every if statement in C compares the condition with @0@, and every increment and decrement operator is semantically equivalent to adding or subtracting the value @1@ and storing the result. 255 Due to these rewrite rules, the values @0@ and @1@ have the types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly connect to all special @0@ and @1@ contexts. 256 The types @zero_t@ and @one_t@ have special built in implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work as normal. 253 257 254 258 … … 262 266 T ?+=?( T *, T ); 263 267 T ++?( T * ); 264 T ?++( T * ); 265 }; 268 T ?++( T * ); }; 266 269 forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) { // use trait 267 270 `T` total = { `0` }; $\C{// instantiate T from 0 by calling its constructor}$ 268 271 for ( unsigned int i = 0; i < size; i += 1 ) 269 272 total `+=` a[i]; $\C{// select appropriate +}$ 270 return total; 271 } 273 return total; } 272 274 \end{lstlisting} 273 275 … … 278 280 void ?{}( T *, T ); $\C{// copy constructor}$ 279 281 void ?=?( T *, T ); $\C{// assignment operator}$ 280 void ^?{}( T * ); $\C{// destructor}$ 281 }; 282 void ^?{}( T * ); }; $\C{// destructor}$ 282 283 \end{lstlisting} 283 284 Given 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. … … 385 386 \end{lstlisting} 386 387 388 387 389 \subsection{Dynamic Generic Types} 388 390
Note: See TracChangeset
for help on using the changeset viewer.