Changeset f891424 for doc

Timestamp:

Apr 15, 2017, 12:54:03 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

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:

b23d969

Parents:

1c38f5b (diff), 160af1e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

doc

Files:

• bibliography/cfa.bib (modified) (6 diffs)
• generic_types/generic_types.tex (modified) (14 diffs)

doc/bibliography/cfa.bib

@@ -433 +433 @@
     keywords    = {Parametric polymorphism, alphard, iterators, nested types},
     contributer = {gjditchfield@plg},
+    key         = {Alphard},
     editor      = {Mary Shaw},
     title       = {{ALPHARD}: Form and Content},
@@ -861 +862 @@
 
 @techreport{C11,
-    type = {International Standard},
+    type        = {International Standard},
     keywords    = {ISO/IEC C 11},
     contributer = {pabuhr@plg},
@@ -872 +873 @@
 
 @techreport{C++Concepts,
-    type = {International Standard},
+    type        = {International Standard},
     keywords    = {ISO/IEC TS 19217:2015},
     contributer = {a3moss@uwaterloo.ca},
@@ -5317 +5318 @@
     title       = {Programming with Sets: An Introduction to {SETL}},
     publisher   = {Springer},
+    address     = {New York, NY, USA},
     year        = 1986,
 }
@@ -6312 +6314 @@
 }
 
-@article{Sutter15,
+@online{Sutter15,
     contributer = {pabuhr@plg},
     author      = {Herb Sutter and Bjarne Stroustrup and Gabriel Dos Reis},
@@ -6764 +6766 @@
     number      = 6,
     month       = jun,
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
     year        = 1990,
     pages       = {127-136},

doc/generic_types/generic_types.tex

@@ -194 +194 @@
 The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
 
+
 \subsection{Polymorphic Functions}
 \label{sec:poly-fns}
 
 \CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}.
-The signature feature of \CFA is parametric-polymorphic functions where functions are generalized using a @forall@ clause (giving the language its name):
+The signature feature of \CFA is parametric-polymorphic functions~\citep{forceone:impl,Cormack90} where functions are generalized using a @forall@ clause (giving the language its name):
 \begin{lstlisting}
 `forall( otype T )` T identity( T val ) { return val; }
@@ -211 +212 @@
 An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and 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.
+Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion}~\cite{alphard} 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:
 \begin{lstlisting}
@@ -291 +292 @@
 \smallskip\par\noindent
 \lstMakeShortInline@%
-Hence, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
+Here, 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@, \eg:
@@ -298 +299 @@
 if (x) x++                                                                      $\C{// if (x != 0) 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.
+Every if and iteration 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.
@@ -319 +320 @@
 \end{lstlisting}
 
-In fact, the set of trait operators is incomplete, as there is no assignment requirement for type @T@, but @otype@ is syntactic sugar for the following implicit trait:
+In fact, the set of @summable@ trait operators is incomplete, as it is missing assignment for type @T@, but @otype@ is syntactic sugar for the following implicit trait:
 \begin{lstlisting}
 trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
@@ -515 +516 @@
 [ int, int ] div( int num, int den );           $\C{// return two integers}$
 [ double, double ] div( double num, double den ); $\C{// return two doubles}$
-int q, r;                                                                       $\C{// overload variable names}$
+int q, r;                                                                       $\C{// overloaded variable names}$
 double q, r;
 [ q, r ] = div( 13, 5 );                                        $\C{// select appropriate div and q, r}$
-[ q, r ] = div( 13.5, 5.2 );
+[ q, r ] = div( 13.5, 5.2 );                            $\C{// assign into tuple}$
 \end{lstlisting}
 Clearly, this approach is straightforward to understand and use;
 therefore, why do few programming languages support this obvious feature or provide it awkwardly?
 The answer is that there are complex consequences that cascade through multiple aspects of the language, especially the type-system.
-This section show these consequences and how \CFA deals with them.
+This section show these consequences and how \CFA handles them.
 
 
@@ -536 +537 @@
 printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
 \end{lstlisting}
-Here, the values returned by @div@ are composed with the call to @printf@.
+Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments.
 However, the \CFA type-system must support significantly more complex composition:
 \begin{lstlisting}
@@ -552 +553 @@
 
 An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF.
-\CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types.
-As a consequence, \CFA allows declaration of \emph{tuple variables} that can be initialized from an MRVF, \eg:
+\CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types, \eg:
 \begin{lstlisting}
 [ int, int ] qr = div( 13, 5 );                         $\C{// tuple-variable declaration and initialization}$
@@ -665 +665 @@
 x.[0, 1] = x.[1, 0];    $\C[1in]{// rearrange: [x.0, x.1] = [x.1, x.0]}$
 f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}\CRT{}$
-[int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.
-x.2]
+[int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]
 \end{lstlisting}
 \end{tabular}
@@ -954 +953 @@
 Instead, the presented benchmarks show the costs of idiomatic use of each language's features to examine common usage.
 Figure~\ref{fig:MicroBenchmark} shows the \CFA benchmark tests for a generic stack based on a singly linked-list, a generic pair-data-structure, and a variadic @print@ routine similar to that in Section~\ref{sec:variadic-tuples}.
-The tests are similar for C and \CC.
-The first two experiments use element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, and find the maximum value in the other stack.
-The last experiment creates a file and prints $N=40M$ elements of type @int@ and @pair( _Bool, char)@ using a variadic print.
-
-The structure of each implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
+The benchmark tests are similar for C and \CC.
+The experiment uses element types @int@ and @pair( _Bool, char)@, and push $N=40M$ elements on a generic stack, copy the stack, clear one of the stacks, find the maximum value in the other stack, and print $N$ constant values.
+
+The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the different presented features, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
 The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
 hence runtime checks are necessary to safely down-cast objects.
@@ -965 +963 @@
 For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
 Preliminary tests show the difference has little runtime effect.
-Finally, the C @rand@ function is used generate random numbers.
+%Finally, the C @rand@ function is used generate random numbers.
 
 \begin{figure}
 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt,numbers=left,numberstyle=\tt\small,numberblanklines=false]
 int main( int argc, char *argv[] ) {
-        int max = 0;
-        stack(int) s, t;
-        REPEAT_TIMED( "push_int", push( &s, 42 ); )
-        TIMED( "copy_int", t = s; )
-        TIMED( "clear_int", clear( &s ); )
-        REPEAT_TIMED( "pop_int", max = max( max, pop( &t ) ); )
-
-        stack(pair(_Bool, char)) s1, t1;
-        pair(_Bool, char) max = { (_Bool)0, '\0' };
-        REPEAT_TIMED( "push_pair", push( &s1, (pair(_Bool, char)){ (_Bool)0, 'a' } ); )
-        TIMED( "copy_pair", t1 = s1; )
-        TIMED( "clear_pair", clear( &s1 ); )
-        REPEAT_TIMED( "pop_pair", max = max( max, pop( &t1 ) ); )
-
         FILE * out = fopen( "cfa-out.txt", "w" );
-        REPEAT_TIMED( "print_int", print( out, 42, ":", 42, "\n" ); )
-        REPEAT_TIMED( "print_pair", print( out, (pair(_Bool, char)){ (_Bool)0, 'a' }, ":",
-                                                         (pair(_Bool, char)){ (_Bool)0, 'a' }, "\n" ); )
+        int max = 0, vali = 42;
+        stack(int) si, ti;
+
+        REPEAT_TIMED( "push_int", push( &si, vali ); )
+        TIMED( "copy_int", ti = si; )
+        TIMED( "clear_int", clear( &si ); )
+        REPEAT_TIMED( "pop_int", max = max( max, pop( &ti ) ); )
+        REPEAT_TIMED( "print_int", print( out, vali, ":", vali, "\n" ); )
+
+        pair(_Bool, char) maxp  = { (_Bool)0, '\0' }, valp = { (_Bool)0, 'a' };
+        stack(pair(_Bool, char)) sp, tp;
+
+        REPEAT_TIMED( "push_pair", push( &sp, valp ); )
+        TIMED( "copy_pair", tp = sp; )
+        TIMED( "clear_pair", clear( &sp ); )
+        REPEAT_TIMED( "pop_pair", maxp = max( maxp, pop( &tp ) ); )
+        REPEAT_TIMED( "print_pair", print( out, valp, ":", valp, "\n" ); )
         fclose(out);
 }
 \end{lstlisting}
-\caption{Micro-Benchmark}
+\caption{\CFA Micro-Benchmark}
 \label{fig:MicroBenchmark}
 \end{figure}
@@ -1007 +1005 @@
 \newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
 \begin{tabular}{r|rrrr}
-                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      &       \CT{\CCV}       \\ \hline
-maximum memory usage (MB)       & 10001         & 2501          & 2503          &       11253           \\
-source code size (lines)        & 301           & 224           & 188           &       437                     \\
-redundant type annotations (lines)      & 46            & 3                     & 2                     &       15                      \\
-binary size (KB)                        & 18            & 234           & 18            &       42                      \\
+                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
+maximum memory usage (MB)                       & 10001         & 2501          & 2503          & 11253                 \\
+source code size (lines)                        & 301           & 224           & 188           & 437                   \\
+redundant type annotations (lines)      & 46            & 3                     & 2                     & 15                    \\
+binary size (KB)                                        & 18            & 234           & 18            & 42                    \\
 \end{tabular}
 \end{table}
@@ -1100 +1098 @@
 \section{Conclusion \& Future Work}
 
+The \CFA goal is to provide an evolutionary pathway for large C development-environments to be more productive and safer, while respecting the talent and skill of C programmers.
+While other programming languages purport to be a better C, they are in fact new and interesting languages in their own right, but not C extensions.
+The purpose of this paper is to introduce \CFA, and showcase two language features that illustrate the \CFA type-system and approaches taken to achieve the evolutionary goal.
+The contributions are a powerful type-system using parametric polymorphism and overloading, generic types, and tuples, which all have complex interactions.
+The work is a challenging design, engineering, and implementation exercise.
+On the surface, the project may appear as a rehash of similar mechanisms in \CC.
+However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation.
+All of these new features are being used by the \CFA development-team to build the \CFA runtime system.
+Finally, we demonstrate that \CFA performance for some idiomtic cases is better than C and close to \CC, showing the design is competitive.
+
 There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, and concurrent programming primitives.
 In addition to this work, there are some interesting future directions the polymorphism design could take.
@@ -1108 +1116 @@
 These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unnecessary.
 
-In conclusion, the authors' design for generic types and tuples, unlike those available in existing work, is both reusable and type-checked, while still supporting a full range of C features, including separately-compiled modules.
-We have experimentally validated the performance of our design against both \CC and standard C, showing it is comparable to both, and in some cases better.
-
 
 \begin{acks}