Ignore:
Timestamp:
Apr 25, 2017, 8:21:10 AM (5 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
89a9be2
Parents:
b3d70eb
Message:

more cleanup

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    rb3d70eb r6a8ac0b  
    232232int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    233233                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
    234 double key = 5.0, vals[10] = { /* 10 floating-point values */ };
     234double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ };
    235235double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    236236\end{lstlisting}
     
    354354One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
    355355Broadly speaking, there are three approaches to implement abstract data-structures in C.
    356 One approach is to write bespoke data structures for each context in which they are needed.
     356One approach is to write bespoke data-structures for each context in which they are needed.
    357357While 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.
    358358A 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.
     
    542542\end{lstlisting}
    543543where 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.
     544Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C.
    545545
    546546One way to access the tuple-variable components is with assignment or composition:
     
    552552\begin{lstlisting}
    553553[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}$
     554int rem = qr`.1`;                                                       $\C{// access remainder}$
     555int quo = div( 13, 5 )`.0`;                                     $\C{// access quotient}$
     556p`->0` = 5;                                                                     $\C{// change quotient}$
     557bar( qr`.1`, qr );                                                      $\C{// pass remainder and quotient/remainder}$
     558rem = [42, div( 13, 5 )]`.0.1`;                         $\C{// access 2nd component of 1st component of tuple expression}$
    559559\end{lstlisting}
    560560
     
    616616This 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.
    617617For 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@.
     618whereas, C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
    619619Finally, 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.
    620620This example shows mass, multiple, and cascading assignment used in one expression:
     
    742742\end{lstlisting}
    743743Hence, 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 \citet{Bilson03}.
     744This relaxation is possible by extending the thunk scheme described by~\citet{Bilson03}.
    745745Whenever 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:
    746746\begin{lstlisting}
     
    748748\end{lstlisting}
    749749so 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 pointer signature.
     750These thunks take advantage of GCC C nested-functions to produce closures that have the usual function-pointer signature.
    751751
    752752
     
    829829\subsection{Implementation}
    830830
    831 Tuples are implemented in the \CFA translator via a transformation into generic types.
     831Tuples are implemented in the \CFA translator via a transformation into \emph{generic types}.
    832832For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg:
    833833\begin{lstlisting}
     
    10861086Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    10871087
    1088 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, concurrent primitives and modules.
     1088There is ongoing work on a wide range of \CFA feature extensions, including reference types, arrays with size, exceptions, concurrent primitives and modules.
    10891089(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.)
    10901090In addition, there are interesting future directions for the polymorphism design.
     
    10921092\CFA polymorphic functions use dynamic virtual-dispatch;
    10931093the 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.
     1094Two 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).
    10951095These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    10961096In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code.
     
    11171117Throughout, @/***/@ designates a counted redundant type annotation.
    11181118
    1119 \medskip\noindent
     1119\smallskip\noindent
    11201120\CFA
    11211121\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
Note: See TracChangeset for help on using the changeset viewer.