Index: doc/generic_types/generic_types.tex =================================================================== --- doc/generic_types/generic_types.tex (revision 2b8a89702850db0bd2de14ded00886ddcf967e39) +++ doc/generic_types/generic_types.tex (revision 7aa78b45be1e6204e84666fe221b25625624e630) @@ -278,21 +278,21 @@ 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 = ...; -\end{lstlisting} -& -\begin{lstlisting} -short int s = MAX; // select correct MAX +short int s = MAX; $\C{// select correct MAX}$ int i = MAX; double d = MAX; \end{lstlisting} -\end{tabular} -\smallskip\par\noindent -\lstMakeShortInline@% +%\end{lstlisting} +%& +%\begin{lstlisting} +%\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,7 +585,7 @@ 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,15 +593,15 @@ int h( int, [int, int] ); [int, int] x; -\end{lstlisting} -& -\begin{lstlisting} int y; -f( x ); $\C[1in]{// flatten}$ +f( x ); $\C{// flatten}$ g( y, 10 ); $\C{// structure}$ -h( x, y ); $\C{// flatten and structure}\CRT{}$ -\end{lstlisting} -\end{tabular} -\smallskip\par\noindent -\lstMakeShortInline@% +h( x, y ); $\C{// flatten and structure}$ +\end{lstlisting} +%\end{lstlisting} +%& +%\begin{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,23 +614,22 @@ 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; - -\end{lstlisting} -& -\begin{lstlisting} -z = [x, y]; $\C[1in]{// multiple assignment}$ +z = [x, y]; $\C{// multiple assignment}$ [x, y] = z; $\C{// multiple assignment}$ z = 10; $\C{// mass assignment}$ -[y, x] = 3.14; $\C{// mass assignment}\CRT{}$ -\end{lstlisting} -\end{tabular} -\smallskip\par\noindent -\lstMakeShortInline@% +[y, x] = 3.14; $\C{// mass assignment}$ +\end{lstlisting} +%\end{lstlisting} +%& +%\begin{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]@. @@ -656,21 +655,20 @@ 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 ); - -\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@% +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@% It is also possible for a member access to contain other member accesses, \eg: \begin{lstlisting} @@ -861,14 +859,12 @@ 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; + T0 field_0; $\C{// generated before the first 2-tuple}$ 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; + T0 field_0; $\C{// generated before the first 3-tuple}$ T1 field_1; T2 field_2; @@ -877,12 +873,5 @@ } \end{lstlisting} -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} +Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@. \begin{comment} @@ -953,12 +942,5 @@ 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$ 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. +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. \begin{figure} @@ -991,4 +973,11 @@ \label{fig:BenchmarkTest} \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 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. 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. @@ -1176,10 +1165,10 @@ std::forward_list wrapped in std::stack interface -template void print(ostream& out, const T& x) { out << x; } -template<> void print(ostream& out, const bool& x) { out << (x ? "true" : "false"); } -template<> void print(ostream& out, const char& x ) { out << "'" << x << "'"; } -template ostream& operator<< (ostream& out, const pair& x) { +template void print(ostream & out, const T & x) { out << x; } +template<> void print(ostream & out, const bool & x) { out << (x ? "true" : "false"); } +template<> void print(ostream & out, const char & x ) { out << "'" << x << "'"; } +template ostream & operator<< (ostream & out, const pair& x) { out << "["; print(out, x.first); out << ", "; print(out, x.second); return out << "]"; } -template void print(ostream& out, const T& arg, const Args&... rest) { +template void print(ostream & out, const T & arg, const Args &... rest) { out << arg; print(out, rest...); } \end{lstlisting} @@ -1220,17 +1209,17 @@ 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); @@ -1238,11 +1227,11 @@ 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; @@ -1251,7 +1240,7 @@ 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); @@ -1267,11 +1256,11 @@ 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& 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; @@ -1282,7 +1271,7 @@ stack() : head(nullptr) {} stack(const stack& o) { copy(o); } - stack(stack&& o) : head(o.head) { o.head = nullptr; } + stack(stack && o) : head(o.head) { o.head = nullptr; } ~stack() { clear(); } - stack& operator= (const stack& o) { + stack & operator= (const stack& o) { if ( this == &o ) return *this; clear(); @@ -1290,5 +1279,5 @@ return *this; } - stack& operator= (stack&& o) { + stack & operator= (stack && o) { if ( this == &o ) return *this; head = o.head; @@ -1297,7 +1286,7 @@ } 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); @@ -1306,6 +1295,6 @@ } void clear() { - for ( node* next = head; next; ) { - node* crnt = next; + for ( node * next = head; next; ) { + node * crnt = next; next = crnt->next; delete crnt; @@ -1320,11 +1309,11 @@ \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) }; /***/ @@ -1333,20 +1322,20 @@ *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); @@ -1360,8 +1349,8 @@ \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; @@ -1370,8 +1359,8 @@ } 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(); @@ -1379,5 +1368,5 @@ return *this; } -stack& stack::operator= (stack&& o) { +stack & stack::operator= (stack && o) { if ( this == &o ) return *this; head = o.head; @@ -1386,7 +1375,7 @@ } 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 stack::pop() { - node* n = head; + node * n = head; head = n->next; ptr x = std::move(n->value); @@ -1395,6 +1384,6 @@ } void stack::clear() { - while ( node* next = head; next; ) { - node* crnt = next; + for ( node * next = head; next; ) { + node * crnt = next; next = crnt->next; delete crnt;