Ignore:
Timestamp:
Apr 6, 2017, 10:54:26 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:
221c2de, 3db60cb
Parents:
2264c11
Message:

additions and compression of first 5 pages

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    r2264c11 r115a868  
    5151stringstyle=\tt,                                                                                % use typewriter font
    5252tabsize=4,                                                                                              % 4 space tabbing
    53 xleftmargin=\parindent,                                                                 % indent code to paragraph indentation
     53xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
    5454%mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
    5555escapechar=\$,                                                                                  % LaTeX escape in CFA code
     
    167167int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
    168168\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.
     169The @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
     171Here, 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.
    172172
    173173Since 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:
     
    176176int val = twice( twice( 3.7 ) );
    177177\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:
     178which 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
     180Crucial 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.
     182A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted floating-point array:
    199183\begin{lstlisting}
    200184void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
     
    202186int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    203187                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
     188double vals[10] = { /* 10 floating-point values */ };
    204189double 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:
     190double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
     191\end{lstlisting}
     192which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrappers:
    208193\begin{lstlisting}
    209194forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
    210195        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 ); }
    213197forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
    214198        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)}$
    217200double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
    218201int posn = bsearch( 5.0, vals, 10 );
     
    222205\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@.
    223206
    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.
     208For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@:
     209\begin{lstlisting}
     210forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)(void *)malloc( (size_t)sizeof(T) ); }
     211int * ip = malloc();                                            $\C{// select type and size from left-hand side}$
     212double * dp = malloc();
     213struct S {...} * sp = malloc();
     214\end{lstlisting}
     215where the return type supplies the type/size of the allocation, which is impossible in most type systems.
     216
     217Call-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}
     219forall( 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}$
    228221        qsort( vals, size );                                    $\C{// descending sort}$
    229222}
     
    251244\smallskip\par\noindent
    252245Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
     246As 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.
     247In addition, several operations are defined in terms values @0@ and @1@.
     248For example,
     249\begin{lstlisting}
     250int x;
     251if (x)        // if (x != 0)
     252        x++;    //   x += 1;
     253\end{lstlisting}
     254Every 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.
     255Due 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.
     256The 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.
    253257
    254258
     
    262266        T ?+=?( T *, T );
    263267        T ++?( T * );
    264         T ?++( T * );
    265 };
     268        T ?++( T * ); };
    266269forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) {  // use trait
    267270        `T` total = { `0` };                                    $\C{// instantiate T from 0 by calling its constructor}$
    268271        for ( unsigned int i = 0; i < size; i += 1 )
    269272                total `+=` a[i];                                        $\C{// select appropriate +}$
    270         return total;
    271 }
     273        return total; }
    272274\end{lstlisting}
    273275
     
    278280        void ?{}( T *, T );                                             $\C{// copy constructor}$
    279281        void ?=?( T *, T );                                             $\C{// assignment operator}$
    280         void ^?{}( T * );                                               $\C{// destructor}$
    281 };
     282        void ^?{}( T * ); };                                    $\C{// destructor}$
    282283\end{lstlisting}
    283284Given 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.
     
    385386\end{lstlisting}
    386387
     388
    387389\subsection{Dynamic Generic Types}
    388390
Note: See TracChangeset for help on using the changeset viewer.