Changes in doc/generic_types/generic_types.tex [e2ef6bf:2b8a897]

File:

• doc/generic_types/generic_types.tex (modified) (27 diffs)

doc/generic_types/generic_types.tex

@@ -278 +278 @@
 
 Finally, \CFA allows variable overloading:
-%\lstDeleteShortInline@%
-%\par\smallskip
-%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
+\lstDeleteShortInline@%
+\par\smallskip
+\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
 \begin{lstlisting}
 short int MAX = ...;
 int MAX = ...;
 double MAX = ...;
-short int s = MAX;  $\C{// select correct MAX}$
+\end{lstlisting}
+&
+\begin{lstlisting}
+short int s = MAX;  // select correct MAX
 int i = MAX;
 double d = MAX;
 \end{lstlisting}
-%\end{lstlisting}
-%&
-%\begin{lstlisting}
-%\end{tabular}
-%\smallskip\par\noindent
-%\lstMakeShortInline@%
+\end{tabular}
+\smallskip\par\noindent
+\lstMakeShortInline@%
 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.
@@ -585 +585 @@
 Tuple flattening recursively expands a tuple into the list of its basic components.
 Tuple structuring packages a list of expressions into a value of tuple type, \eg:
-%\lstDeleteShortInline@%
-%\par\smallskip
-%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
+\lstDeleteShortInline@%
+\par\smallskip
+\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
 \begin{lstlisting}
 int f( int, int );
@@ -593 +593 @@
 int h( int, [int, int] );
 [int, int] x;
+\end{lstlisting}
+&
+\begin{lstlisting}
 int y;
-f( x );                 $\C{// flatten}$
+f( x );                 $\C[1in]{// flatten}$
 g( y, 10 );             $\C{// structure}$
-h( x, y );              $\C{// flatten and structure}$
-\end{lstlisting}
-%\end{lstlisting}
-%&
-%\begin{lstlisting}
-%\end{tabular}
-%\smallskip\par\noindent
-%\lstMakeShortInline@%
+h( x, y );              $\C{// flatten and structure}\CRT{}$
+\end{lstlisting}
+\end{tabular}
+\smallskip\par\noindent
+\lstMakeShortInline@%
 In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as the two arguments.
 In the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the parameter type of @g@.
@@ -614 +614 @@
 An assignment where the left side is a tuple type is called \emph{tuple assignment}.
 There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \emph{multiple} and \emph{mass assignment}, respectively.
-%\lstDeleteShortInline@%
-%\par\smallskip
-%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
+\lstDeleteShortInline@%
+\par\smallskip
+\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
 \begin{lstlisting}
 int x = 10;
 double y = 3.5;
 [int, double] z;
-z = [x, y];             $\C{// multiple assignment}$
+
+\end{lstlisting}
+&
+\begin{lstlisting}
+z = [x, y];             $\C[1in]{// multiple assignment}$
 [x, y] = z;             $\C{// multiple assignment}$
 z = 10;                 $\C{// mass assignment}$
-[y, x] = 3.14;  $\C{// mass assignment}$
-\end{lstlisting}
-%\end{lstlisting}
-%&
-%\begin{lstlisting}
-%\end{tabular}
-%\smallskip\par\noindent
-%\lstMakeShortInline@%
+[y, x] = 3.14;  $\C{// mass assignment}\CRT{}$
+\end{lstlisting}
+\end{tabular}
+\smallskip\par\noindent
+\lstMakeShortInline@%
 Both kinds of tuple assignment have parallel semantics, so that each value on the left and right side is evaluated before any assignments occur.
 As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function, \eg, @[x, y] = [y, x]@.
@@ -655 +656 @@
 Here, the mass assignment sets all members of @s@ to zero.
 Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (\eg rearrange, drop, and duplicate components).
-%\lstDeleteShortInline@%
-%\par\smallskip
-%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
+\lstDeleteShortInline@%
+\par\smallskip
+\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
 \begin{lstlisting}
 [int, int, long, double] x;
 void f( double, long );
-x.[0, 1] = x.[1, 0];    $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
-f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}$
-[int, int, int] y = x.[2, 0, 2]; $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
-\end{lstlisting}
-%\end{lstlisting}
-%&
-%\begin{lstlisting}
-%\end{tabular}
-%\smallskip\par\noindent
-%\lstMakeShortInline@%
+
+\end{lstlisting}
+&
+\begin{lstlisting}
+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]
+\end{lstlisting}
+\end{tabular}
+\smallskip\par\noindent
+\lstMakeShortInline@%
 It is also possible for a member access to contain other member accesses, \eg:
 \begin{lstlisting}
@@ -859 +861 @@
 is transformed into:
 \begin{lstlisting}
+// generated before the first 2-tuple
 forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
-        T0 field_0;                     $\C{// generated before the first 2-tuple}$
+        T0 field_0;
         T1 field_1;
 };
 _tuple2(int, int) f() {
         _tuple2(double, double) x;
+        // generated before the first 3-tuple
         forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
-                T0 field_0;             $\C{// generated before the first 3-tuple}$
+                T0 field_0;
                 T1 field_1;
                 T2 field_2;
@@ -873 +877 @@
 }
 \end{lstlisting}
-Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
+Tuple expressions are then simply converted directly into compound literals:
+\begin{lstlisting}
+[5, 'x', 1.24];
+\end{lstlisting}
+becomes:
+\begin{lstlisting}
+(_tuple3(int, char, double)){ 5, 'x', 1.24 };
+\end{lstlisting}
 
 \begin{comment}
@@ -938 +949 @@
 In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}).
-Since all these languages share a subset comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
-A more illustrative benchmark is the idiomatic costs of each language's features covering common usage.
+Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code.
+A more illustrative benchmark measures the costs of idiomatic usage of each language's features.
 Figure~\ref{fig:BenchmarkTest} 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 benchmark test is similar for C and \CC.
-The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N/2$ (to reduce graph height) constants.
+The experiment uses element types @int@ and @pair(_Bool, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, finds the maximum value in the other stack, and prints $N$ values of each type (2 per @print@ call).
+
+The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the 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.
+The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
+For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has negligible runtime impact.
+Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
 
 \begin{figure}
@@ -974 +992 @@
 \end{figure}
 
-The structure of each benchmark implemented is: C with @void *@-based polymorphism, \CFA with the 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.
-The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
-For the print benchmark, idiomatic printing is used: the C and \CFA variants used @stdio.h@, while the \CC and \CCV variants used @iostream@; preliminary tests show this distinction has little runtime impact.
-Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
-
 Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:BenchmarkTest} and its C, \CC, and \CCV equivalents. 
 The graph plots the median of 5 consecutive runs of each program, with an initial warm-up run omitted.
@@ -1000 +1011 @@
                                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\ \hline
 maximum memory usage (MB)                       & 10001         & 2502          & 2503          & 11253                 \\
-source code size (lines)                        & 247           & 223           & 165           & 339                   \\
+source code size (lines)                        & 247           & 222           & 165           & 339                   \\
 redundant type annotations (lines)      & 39            & 2                     & 2                     & 15                    \\
 binary size (KB)                                        & 14            & 229           & 18            & 38                    \\
@@ -1008 +1019 @@
 The C and \CCV variants are generally the slowest with the largest memory footprint, because of their less-efficient memory layout and the pointer-indirection necessary to implement generic types;
 this inefficiency is exacerbated by the second level of generic types in the pair-based benchmarks.
-By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent.
+By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair of @_Bool@ and @char@ because the storage layout is equivalent, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
 \CCV is slower than C largely due to the cost of runtime type-checking of down-casts (implemented with @dynamic_cast@);
 There are two outliers in the graph for \CFA: all prints and pop of @pair@.
 Both of these cases result from the complexity of the C-generated polymorphic code, so that the GCC compiler is unable to optimize some dead code and condense nested calls.
-A compiler for \CFA could easily perform these optimizations.
+A compiler designed for \CFA could easily perform these optimizations.
 Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
 
-\CC performs best because it uses header-only inlined libraries (\ie no separate compilation).
-\CFA and \CC have the advantage of a pre-written generic @pair@ and @stack@ type to reduce line count, while C and \CCV require it to written by the programmer, as C does not have a generic collections-library and \CCV does not use the \CC standard template library by construction.
-For \CCV, the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ are included in the line count, which inflates its line count, as an actual object-oriented language would include these in the standard library;
+\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, though it should be noted that \CFA and \CC have pre-written data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 73 and 54 lines, respectively. 
+On the other hand, C does not have a generic collections-library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers.
+\CCV does not use the \CC standard template library by construction, and in fact includes the definition of @object@ and wrapper classes for @bool@, @char@, @int@, and @const char *@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library; 
 with their omission the \CCV line count is similar to C.
 We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose.
@@ -1165 +1176 @@
 std::forward_list wrapped in std::stack interface
 
-template<typename T> void print(ostream & out, const T & x) { out << x; }
-template<> void print<bool>(ostream & out, const bool & x) { out << (x ? "true" : "false"); }
-template<> void print<char>(ostream & out, const char & x ) { out << "'" << x << "'"; }
-template<typename R, typename S> ostream & operator<< (ostream & out, const pair<R, S>& x) {
+template<typename T> void print(ostream& out, const T& x) { out << x; }
+template<> void print<bool>(ostream& out, const bool& x) { out << (x ? "true" : "false"); }
+template<> void print<char>(ostream& out, const char& x ) { out << "'" << x << "'"; }
+template<typename R, typename S> ostream& operator<< (ostream& out, const pair<R, S>& x) {
         out << "["; print(out, x.first); out << ", "; print(out, x.second); return out << "]"; }
-template<typename T, typename... Args> void print(ostream & out, const T & arg, const Args &... rest) {
+template<typename T, typename... Args> void print(ostream& out, const T& arg, const Args&... rest) {
         out << arg;     print(out, rest...); }
 \end{lstlisting}
@@ -1209 +1220 @@
 forall(otype T) struct stack_node {
         T value;
-        stack_node(T) * next;
+        stack_node(T)* next;
 };
-forall(otype T) void ?{}(stack(T) * s) { (&s->head){ 0 }; }
-forall(otype T) void ?{}(stack(T) * s, stack(T) t) {
-        stack_node(T) ** crnt = &s->head;
-        for ( stack_node(T) * next = t.head; next; next = next->next ) {
-                *crnt = ((stack_node(T) *)malloc()){ next->value }; /***/
-                stack_node(T) * acrnt = *crnt;
+forall(otype T) void ?{}(stack(T)* s) { (&s->head){ 0 }; }
+forall(otype T) void ?{}(stack(T)* s, stack(T) t) {
+        stack_node(T)** crnt = &s->head;
+        for ( stack_node(T)* next = t.head; next; next = next->next ) {
+                *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
+                stack_node(T)* acrnt = *crnt;
                 crnt = &acrnt->next;
         }
         *crnt = 0;
 }
-forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t) {
+forall(otype T) stack(T) ?=?(stack(T)* s, stack(T) t) {
         if ( s->head == t.head ) return *s;
         clear(s);
@@ -1227 +1238 @@
         return *s;
 }
-forall(otype T) void ^?{}(stack(T) * s) { clear(s); }
-forall(otype T) _Bool empty(const stack(T) * s) { return s->head == 0; }
-forall(otype T) void push(stack(T) * s, T value) {
-        s->head = ((stack_node(T) *)malloc()){ value, s->head }; /***/
-}
-forall(otype T) T pop(stack(T) * s) {
-        stack_node(T) * n = s->head;
+forall(otype T) void ^?{}(stack(T)* s) { clear(s); }
+forall(otype T) _Bool empty(const stack(T)* s) { return s->head == 0; }
+forall(otype T) void push(stack(T)* s, T value) {
+        s->head = ((stack_node(T)*)malloc()){ value, s->head }; /***/
+}
+forall(otype T) T pop(stack(T)* s) {
+        stack_node(T)* n = s->head;
         s->head = n->next;
         T x = n->value;
@@ -1240 +1251 @@
         return x;
 }
-forall(otype T) void clear(stack(T) * s) {
-        for ( stack_node(T) * next = s->head; next; ) {
-                stack_node(T) * crnt = next;
+forall(otype T) void clear(stack(T)* s) {
+        for ( stack_node(T)* next = s->head; next; ) {
+                stack_node(T)* crnt = next;
                 next = crnt->next;
                 delete(crnt);
@@ -1256 +1267 @@
         struct node {
                 T value;
-                node * next;
-                node( const T & v, node * n = nullptr ) : value(v), next(n) {}
+                node* next;
+                node( const T& v, node* n = nullptr ) : value(v), next(n) {}
         };
-        node * head;
+        node* head;
         void copy(const stack<T>& o) {
-                node ** crnt = &head;
-                for ( node * next = o.head;; next; next = next->next ) {
+                node** crnt = &head;
+                for ( node* next = o.head;; next; next = next->next ) {
                         *crnt = new node{ next->value }; /***/
                         crnt = &(*crnt)->next;
@@ -1271 +1282 @@
         stack() : head(nullptr) {}
         stack(const stack<T>& o) { copy(o); }
-        stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
+        stack(stack<T>&& o) : head(o.head) { o.head = nullptr; }
         ~stack() { clear(); }
-        stack & operator= (const stack<T>& o) {
+        stack& operator= (const stack<T>& o) {
                 if ( this == &o ) return *this;
                 clear();
@@ -1279 +1290 @@
                 return *this;
         }
-        stack & operator= (stack<T> && o) {
+        stack& operator= (stack<T>&& o) {
                 if ( this == &o ) return *this;
                 head = o.head;
@@ -1286 +1297 @@
         }
         bool empty() const { return head == nullptr; }
-        void push(const T & value) { head = new node{ value, head };  /***/ }
+        void push(const T& value) { head = new node{ value, head };  /***/ }
         T pop() {
-                node * n = head;
+                node* n = head;
                 head = n->next;
                 T x = std::move(n->value);
@@ -1295 +1306 @@
         }
         void clear() {
-                for ( node * next = head; next; ) {
-                        node * crnt = next;
+                for ( node* next = head; next; ) {
+                        node* crnt = next;
                         next = crnt->next;
                         delete crnt;
@@ -1309 +1320 @@
 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
 struct stack_node {
-        void * value;
-        struct stack_node * next;
+        void* value;
+        struct stack_node* next;
 };
 struct stack new_stack() { return (struct stack){ NULL }; /***/ }
-void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
-        struct stack_node ** crnt = &s->head;
-        for ( struct stack_node * next = t->head; next; next = next->next ) {
+void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
+        struct stack_node** crnt = &s->head;
+        for ( struct stack_node* next = t->head; next; next = next->next ) {
                 *crnt = malloc(sizeof(struct stack_node)); /***/
                 **crnt = (struct stack_node){ copy(next->value) }; /***/
@@ -1322 +1333 @@
         *crnt = 0;
 }
-_Bool stack_empty(const struct stack * s) { return s->head == NULL; }
-void push_stack(struct stack * s, void * value) {
-        struct stack_node * n = malloc(sizeof(struct stack_node)); /***/
+_Bool stack_empty(const struct stack* s) { return s->head == NULL; }
+void push_stack(struct stack* s, void* value) {
+        struct stack_node* n = malloc(sizeof(struct stack_node)); /***/
         *n = (struct stack_node){ value, s->head }; /***/
         s->head = n;
 }
-void * pop_stack(struct stack * s) {
-        struct stack_node * n = s->head;
+void* pop_stack(struct stack* s) {
+        struct stack_node* n = s->head;
         s->head = n->next;
-        void * x = n->value;
+        void* x = n->value;
         free(n);
         return x;
 }
-void clear_stack(struct stack * s, void (*free_el)(void *)) {
-        for ( struct stack_node * next = s->head; next; ) {
-                struct stack_node * crnt = next;
+void clear_stack(struct stack* s, void (*free_el)(void*)) {
+        for ( struct stack_node* next = s->head; next; ) {
+                struct stack_node* crnt = next;
                 next = crnt->next;
                 free_el(crnt->value);
@@ -1349 +1360 @@
 \CCV
 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
-stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
-void stack::copy(const stack & o) {
-        node ** crnt = &head;
-        for ( node * next = o.head; next; next = next->next ) {
+stack::node::node( const object& v, node* n ) : value( v.new_copy() ), next( n ) {}
+void stack::copy(const stack& o) {
+        node** crnt = &head;
+        for ( node* next = o.head; next; next = next->next ) {
                 *crnt = new node{ *next->value };
                 crnt = &(*crnt)->next;
@@ -1359 +1370 @@
 }
 stack::stack() : head(nullptr) {}
-stack::stack(const stack & o) { copy(o); }
-stack::stack(stack && o) : head(o.head) { o.head = nullptr; }
+stack::stack(const stack& o) { copy(o); }
+stack::stack(stack&& o) : head(o.head) { o.head = nullptr; }
 stack::~stack() { clear(); }
-stack & stack::operator= (const stack & o) {
+stack& stack::operator= (const stack& o) {
         if ( this == &o ) return *this;
         clear();
@@ -1368 +1379 @@
         return *this;
 }
-stack & stack::operator= (stack && o) {
+stack& stack::operator= (stack&& o) {
         if ( this == &o ) return *this;
         head = o.head;
@@ -1375 +1386 @@
 }
 bool stack::empty() const { return head == nullptr; }
-void stack::push(const object & value) { head = new node{ value, head }; /***/ }
+void stack::push(const object& value) { head = new node{ value, head }; /***/ }
 ptr<object> stack::pop() {
-        node * n = head;
+        node* n = head;
         head = n->next;
         ptr<object> x = std::move(n->value);
@@ -1384 +1395 @@
 }
 void stack::clear() {
-        for ( node * next = head; next; ) {
-                node * crnt = next;
+        while ( node* next = head; next; ) {
+                node* crnt = next;
                 next = crnt->next;
                 delete crnt;