Changeset 115a868c

Timestamp:

Apr 6, 2017, 10:54:26 AM (7 years ago)

Author:

Peter A. Buhr <pabuhr@…>

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

Message:

additions and compression of first 5 pages

Location:

doc/generic_types

Files:

• acmart.cls (modified) (1 diff)
• generic_types.tex (modified) (9 diffs)

doc/generic_types/acmart.cls

@@ -354 +354 @@
 \let\@footnotemark@nolink\@footnotemark
 \let\@footnotetext@nolink\@footnotetext
-\RequirePackage[bookmarksnumbered]{hyperref}
+\RequirePackage[bookmarksnumbered,breaklinks]{hyperref}
 \urlstyle{rm}
 \ifcase\ACM@format@nr

doc/generic_types/generic_types.tex

@@ -51 +51 @@
 stringstyle=\tt,                                                                                % use typewriter font
 tabsize=4,                                                                                              % 4 space tabbing
-xleftmargin=\parindent,                                                                 % indent code to paragraph indentation
+xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
 %mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
 escapechar=\$,                                                                                  % LaTeX escape in CFA code
@@ -167 +167 @@
 int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
 \end{lstlisting}
-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''.
-
-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.
+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@).
+
+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.
 
 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 ) );
 \end{lstlisting}
-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.
-
-Monomorphic specializations of polymorphic functions can satisfy polymorphic type-assertions.
-% \begin{lstlisting}
-% forall(otype T `| { T twice(T); }`)           $\C{// type assertion}$
-% T four_times(T x) { return twice( twice(x) ); }
-% double twice(double d) { return d * 2.0; }    $\C{// (1)}$
-% double magic = four_times(10.5);                      $\C{// T bound to double, uses (1) to satisfy type assertion}$
-% \end{lstlisting}
-\begin{lstlisting}
-forall( otype T `| { int ?<?( T, T ); }` ) void qsort( const T * arr, size_t size );
-forall( otype T `| { int ?<?( T, T ); }` ) T * bsearch( T key, const T * arr, size_t size );
-double vals[10] = { /* 10 floating-point values */ };
-qsort( vals, 10 );                                                      $\C{// sort array}$
-double * val = bsearch( 5.0, vals, 10 );        $\C{// binary search sorted array for key}$
-\end{lstlisting}
-@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@.
-
-Crucial to the design of a new programming language are the libraries to access thousands of external features.
-\CFA inherits a massive compatible library-base, where other programming languages have to rewrite or provide fragile inter-language communication with C.
-A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@, shown here searching a floating-point array:
+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.
+
+Crucial to the design of a new programming language are the libraries to access thousands of external software features.
+\CFA inherits a massive compatible library-base, where other programming languages must rewrite or provide fragile inter-language communication with C.
+A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted floating-point array:
 \begin{lstlisting}
 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 :
                                 *(double *)t2 < *(double *)t1 ? 1 : 0; }
+double vals[10] = { /* 10 floating-point values */ };
 double key = 5.0;
-double * val = (double *)bsearch( &key, vals, size, sizeof(vals[0]), comp );
-\end{lstlisting}
-which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrapper:
+double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
+\end{lstlisting}
+which can be augmented simply with a generalized, type-safe, \CFA-overloaded wrappers:
 \begin{lstlisting}
 forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
         int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ }
-        return (T *)bsearch( &key, arr, size, sizeof(T), comp );
-}
+        return (T *)bsearch( &key, arr, size, sizeof(T), comp ); }
 forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
         T *result = bsearch( key, arr, size );  $\C{// call first version}$
-        return result ? result - arr : size;            $\C{// pointer subtraction includes sizeof(T)}$
-}
+        return result ? result - arr : size; }  $\C{// pointer subtraction includes sizeof(T)}$
 double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
 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@.
 
-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:
-\begin{lstlisting}
-{
-        int ?<?( double x, double y ) { return x `>` y; }       $\C{// override behaviour}$
+\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations.
+For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@:
+\begin{lstlisting}
+forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)(void *)malloc( (size_t)sizeof(T) ); }
+int * ip = malloc();                                            $\C{// select type and size from left-hand side}$
+double * dp = malloc();
+struct S {...} * sp = malloc();
+\end{lstlisting}
+where the return type supplies the type/size of the allocation, which is impossible in most type systems.
+
+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:
+\begin{lstlisting}
+forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ }
+{       int ?<?( double x, double y ) { return x `>` y; }       $\C{// locally override behaviour}$
         qsort( vals, size );                                    $\C{// descending sort}$
 }
@@ -251 +244 @@
 \smallskip\par\noindent
 Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
+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.
+In addition, several operations are defined in terms values @0@ and @1@.
+For example,
+\begin{lstlisting}
+int x;
+if (x)        // if (x != 0)
+        x++;    //   x += 1;
+\end{lstlisting}
+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.
+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.
+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.
 
 
@@ -262 +266 @@
         T ?+=?( T *, T );
         T ++?( T * );
-        T ?++( T * );
-};
+        T ?++( T * ); };
 forall( otype T `| summable( T )` ) T sum( T a[$\,$], size_t size ) {  // use trait
         `T` total = { `0` };                                    $\C{// instantiate T from 0 by calling its constructor}$
         for ( unsigned int i = 0; i < size; i += 1 )
                 total `+=` a[i];                                        $\C{// select appropriate +}$
-        return total;
-}
+        return total; }
 \end{lstlisting}
 
@@ -278 +280 @@
         void ?{}( T *, T );                                             $\C{// copy constructor}$
         void ?=?( T *, T );                                             $\C{// assignment operator}$
-        void ^?{}( T * );                                               $\C{// destructor}$
-};
+        void ^?{}( T * ); };                                    $\C{// destructor}$
 \end{lstlisting}
 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}
 
+
 \subsection{Dynamic Generic Types}