Changeset 6a8ac0b for doc/generic_types/generic_types.tex
- Timestamp:
- Apr 25, 2017, 8:21:10 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:
- 89a9be2
- Parents:
- b3d70eba
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/generic_types.tex
rb3d70eba r6a8ac0b 232 232 int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 : 233 233 *(double *)t2 < *(double *)t1 ? 1 : 0; } 234 double key = 5.0, vals[10] = { /* 10 floating-point values */ };234 double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ }; 235 235 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$ 236 236 \end{lstlisting} … … 354 354 One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms. 355 355 Broadly speaking, there are three approaches to implement abstract data-structures in C. 356 One approach is to write bespoke data 356 One approach is to write bespoke data-structures for each context in which they are needed. 357 357 While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures. 358 358 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@; an approach which does allow reuse of code for common functionality. … … 542 542 \end{lstlisting} 543 543 where the tuple variable-name serves the same purpose as the parameter name(s). 544 Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown .544 Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C. 545 545 546 546 One way to access the tuple-variable components is with assignment or composition: … … 552 552 \begin{lstlisting} 553 553 [int, int] * p = &qr; $\C{// tuple pointer}$ 554 int rem = qr .1;$\C{// access remainder}$555 int quo = div( 13, 5 ) .0; $\C{// access quotient}$556 p ->0= 5; $\C{// change quotient}$557 bar( qr .1, qr ); $\C{// pass remainder and quotient/remainder}$558 rem = [42, div( 13, 5 )] .0.1; $\C{// access 2nd component of 1st component of tuple expression}$554 int rem = qr`.1`; $\C{// access remainder}$ 555 int quo = div( 13, 5 )`.0`; $\C{// access quotient}$ 556 p`->0` = 5; $\C{// change quotient}$ 557 bar( qr`.1`, qr ); $\C{// pass remainder and quotient/remainder}$ 558 rem = [42, div( 13, 5 )]`.0.1`; $\C{// access 2nd component of 1st component of tuple expression}$ 559 559 \end{lstlisting} 560 560 … … 616 616 This semantics means mass assignment differs from C cascading assignment (\eg @a = b = c@) in that conversions are applied in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment. 617 617 For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@; 618 whereas C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.618 whereas, C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@. 619 619 Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C. 620 620 This example shows mass, multiple, and cascading assignment used in one expression: … … 742 742 \end{lstlisting} 743 743 Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution. 744 This relaxation is possible by extending the thunk scheme described by 744 This relaxation is possible by extending the thunk scheme described by~\citet{Bilson03}. 745 745 Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function: 746 746 \begin{lstlisting} … … 748 748 \end{lstlisting} 749 749 so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism. 750 These thunks take advantage of GCC C nested-functions to produce closures that have the usual function 750 These thunks take advantage of GCC C nested-functions to produce closures that have the usual function-pointer signature. 751 751 752 752 … … 829 829 \subsection{Implementation} 830 830 831 Tuples are implemented in the \CFA translator via a transformation into generic types.831 Tuples are implemented in the \CFA translator via a transformation into \emph{generic types}. 832 832 For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg: 833 833 \begin{lstlisting} … … 1086 1086 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 1087 1087 1088 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, concurrent primitives and modules.1088 There is ongoing work on a wide range of \CFA feature extensions, including reference types, arrays with size, exceptions, concurrent primitives and modules. 1089 1089 (While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.) 1090 1090 In addition, there are interesting future directions for the polymorphism design. … … 1092 1092 \CFA polymorphic functions use dynamic virtual-dispatch; 1093 1093 the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code. 1094 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types .1094 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization). 1095 1095 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat. 1096 1096 In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code. … … 1117 1117 Throughout, @/***/@ designates a counted redundant type annotation. 1118 1118 1119 \ medskip\noindent1119 \smallskip\noindent 1120 1120 \CFA 1121 1121 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
Note: See TracChangeset
for help on using the changeset viewer.