 Timestamp:
 Apr 6, 2017, 10:54:26 AM (7 years ago)
 Branches:
 ADT, aaronthesis, armeh, astexperimental, cleanupdtors, deferred_resn, demangler, enum, forallpointerdecay, jacob/cs343translation, jenkinssandbox, master, newast, newastuniqueexpr, newenv, no_list, persistentindexer, pthreademulation, qualifiedEnum, resolvnew, 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 objecttype (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 polymorphictypes 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 typevariable. 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 Cprogrammer intuition. 179 180 Monomorphic specializations of polymorphic functions can satisfy polymorphic typeassertions. 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 floatingpoint 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 builtin 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 librarybase, where other programming languages have to rewrite or provide fragile interlanguage communication with C. 198 A simple example is leveraging the existing typeunsafe (@void *@) C @bsearch@, shown here searching a floatingpoint 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 Cprogrammer 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 librarybase, where other programming languages must rewrite or provide fragile interlanguage communication with C. 182 A simple example is leveraging the existing typeunsafe (@void *@) C @bsearch@ to binary search a sorted floatingpoint 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 floatingpoint 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, typesafe, \CFAoverloaded 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, typesafe, \CFAoverloaded 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 typesystem 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 Callsite 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 typesafe \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 lefthand 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 Callsite 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 typespecific 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: stackallocatable, default or copyinitialized, 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.