Changeset 7aa78b4 for doc/generic_types


Ignore:
Timestamp:
Apr 17, 2017, 6:20:51 PM (7 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:
b31fbf2
Parents:
2b8a897 (diff), e2ef6bf (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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/generic_types/generic_types.tex

    r2b8a897 r7aa78b4  
    278278
    279279Finally, \CFA allows variable overloading:
    280 \lstDeleteShortInline@%
    281 \par\smallskip
    282 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     280%\lstDeleteShortInline@%
     281%\par\smallskip
     282%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    283283\begin{lstlisting}
    284284short int MAX = ...;
    285285int MAX = ...;
    286286double MAX = ...;
    287 \end{lstlisting}
    288 &
    289 \begin{lstlisting}
    290 short int s = MAX;  // select correct MAX
     287short int s = MAX;  $\C{// select correct MAX}$
    291288int i = MAX;
    292289double d = MAX;
    293290\end{lstlisting}
    294 \end{tabular}
    295 \smallskip\par\noindent
    296 \lstMakeShortInline@%
     291%\end{lstlisting}
     292%&
     293%\begin{lstlisting}
     294%\end{tabular}
     295%\smallskip\par\noindent
     296%\lstMakeShortInline@%
    297297Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
    298298As 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.
    … …  
    585585Tuple flattening recursively expands a tuple into the list of its basic components.
    586586Tuple structuring packages a list of expressions into a value of tuple type, \eg:
    587 \lstDeleteShortInline@%
    588 \par\smallskip
    589 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     587%\lstDeleteShortInline@%
     588%\par\smallskip
     589%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    590590\begin{lstlisting}
    591591int f( int, int );
    … …  
    593593int h( int, [int, int] );
    594594[int, int] x;
    595 \end{lstlisting}
    596 &
    597 \begin{lstlisting}
    598595int y;
    599 f( x );                 $\C[1in]{// flatten}$
     596f( x );                 $\C{// flatten}$
    600597g( y, 10 );             $\C{// structure}$
    601 h( x, y );              $\C{// flatten and structure}\CRT{}$
    602 \end{lstlisting}
    603 \end{tabular}
    604 \smallskip\par\noindent
    605 \lstMakeShortInline@%
     598h( x, y );              $\C{// flatten and structure}$
     599\end{lstlisting}
     600%\end{lstlisting}
     601%&
     602%\begin{lstlisting}
     603%\end{tabular}
     604%\smallskip\par\noindent
     605%\lstMakeShortInline@%
    606606In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as the two arguments.
    607607In 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@.
    … …  
    614614An assignment where the left side is a tuple type is called \emph{tuple assignment}.
    615615There 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.
    616 \lstDeleteShortInline@%
    617 \par\smallskip
    618 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     616%\lstDeleteShortInline@%
     617%\par\smallskip
     618%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    619619\begin{lstlisting}
    620620int x = 10;
    621621double y = 3.5;
    622622[int, double] z;
    623 
    624 \end{lstlisting}
    625 &
    626 \begin{lstlisting}
    627 z = [x, y];             $\C[1in]{// multiple assignment}$
     623z = [x, y];             $\C{// multiple assignment}$
    628624[x, y] = z;             $\C{// multiple assignment}$
    629625z = 10;                 $\C{// mass assignment}$
    630 [y, x] = 3.14;  $\C{// mass assignment}\CRT{}$
    631 \end{lstlisting}
    632 \end{tabular}
    633 \smallskip\par\noindent
    634 \lstMakeShortInline@%
     626[y, x] = 3.14;  $\C{// mass assignment}$
     627\end{lstlisting}
     628%\end{lstlisting}
     629%&
     630%\begin{lstlisting}
     631%\end{tabular}
     632%\smallskip\par\noindent
     633%\lstMakeShortInline@%
    635634Both kinds of tuple assignment have parallel semantics, so that each value on the left and right side is evaluated before any assignments occur.
    636635As 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]@.
    … …  
    656655Here, the mass assignment sets all members of @s@ to zero.
    657656Since 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).
    658 \lstDeleteShortInline@%
    659 \par\smallskip
    660 \begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
     657%\lstDeleteShortInline@%
     658%\par\smallskip
     659%\begin{tabular}{@{}l@{\hspace{1.5\parindent}}||@{\hspace{1.5\parindent}}l@{}}
    661660\begin{lstlisting}
    662661[int, int, long, double] x;
    663662void f( double, long );
    664 
    665 \end{lstlisting}
    666 &
    667 \begin{lstlisting}
    668 x.[0, 1] = x.[1, 0];    $\C[1in]{// rearrange: [x.0, x.1] = [x.1, x.0]}$
    669 f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}\CRT{}$
    670 [int, int, int] y = x.[2, 0, 2]; // duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]
    671 \end{lstlisting}
    672 \end{tabular}
    673 \smallskip\par\noindent
    674 \lstMakeShortInline@%
     663x.[0, 1] = x.[1, 0];    $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
     664f( x.[0, 3] );            $\C{// drop: f(x.0, x.3)}$
     665[int, int, int] y = x.[2, 0, 2]; $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
     666\end{lstlisting}
     667%\end{lstlisting}
     668%&
     669%\begin{lstlisting}
     670%\end{tabular}
     671%\smallskip\par\noindent
     672%\lstMakeShortInline@%
    675673It is also possible for a member access to contain other member accesses, \eg:
    676674\begin{lstlisting}
    … …  
    861859is transformed into:
    862860\begin{lstlisting}
    863 // generated before the first 2-tuple
    864861forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
    865         T0 field_0;
     862        T0 field_0;                     $\C{// generated before the first 2-tuple}$
    866863        T1 field_1;
    867864};
    868865_tuple2(int, int) f() {
    869866        _tuple2(double, double) x;
    870         // generated before the first 3-tuple
    871867        forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {
    872                 T0 field_0;
     868                T0 field_0;             $\C{// generated before the first 3-tuple}$
    873869                T1 field_1;
    874870                T2 field_2;
    … …  
    877873}
    878874\end{lstlisting}
    879 Tuple expressions are then simply converted directly into compound literals:
    880 \begin{lstlisting}
    881 [5, 'x', 1.24];
    882 \end{lstlisting}
    883 becomes:
    884 \begin{lstlisting}
    885 (_tuple3(int, char, double)){ 5, 'x', 1.24 };
    886 \end{lstlisting}
     875Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
    887876
    888877\begin{comment}
    … …  
    953942Figure~\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}.
    954943The benchmark test is similar for C and \CC.
    955 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).
    956 
    957 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.
    958 The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
    959 hence runtime checks are necessary to safely down-cast objects.
    960 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.
    961 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.
    962 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.
     944The 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.
    963945
    964946\begin{figure}
    … …  
    991973\label{fig:BenchmarkTest}
    992974\end{figure}
     975
     976The 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.
     977The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
     978hence runtime checks are necessary to safely down-cast objects.
     979The 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.
     980For 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.
     981Note, the C benchmark uses unchecked casts as there is no runtime mechanism to perform such checks, while \CFA and \CC provide type-safety statically.
    993982
    994983Figure~\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.
    … …  
    11761165std::forward_list wrapped in std::stack interface
    11771166
    1178 template<typename T> void print(ostream& out, const T& x) { out << x; }
    1179 template<> void print<bool>(ostream& out, const bool& x) { out << (x ? "true" : "false"); }
    1180 template<> void print<char>(ostream& out, const char& x ) { out << "'" << x << "'"; }
    1181 template<typename R, typename S> ostream& operator<< (ostream& out, const pair<R, S>& x) {
     1167template<typename T> void print(ostream & out, const T & x) { out << x; }
     1168template<> void print<bool>(ostream & out, const bool & x) { out << (x ? "true" : "false"); }
     1169template<> void print<char>(ostream & out, const char & x ) { out << "'" << x << "'"; }
     1170template<typename R, typename S> ostream & operator<< (ostream & out, const pair<R, S>& x) {
    11821171        out << "["; print(out, x.first); out << ", "; print(out, x.second); return out << "]"; }
    1183 template<typename T, typename... Args> void print(ostream& out, const T& arg, const Args&... rest) {
     1172template<typename T, typename... Args> void print(ostream & out, const T & arg, const Args &... rest) {
    11841173        out << arg;     print(out, rest...); }
    11851174\end{lstlisting}
    … …  
    12201209forall(otype T) struct stack_node {
    12211210        T value;
    1222         stack_node(T)* next;
     1211        stack_node(T) * next;
    12231212};
    1224 forall(otype T) void ?{}(stack(T)* s) { (&s->head){ 0 }; }
    1225 forall(otype T) void ?{}(stack(T)* s, stack(T) t) {
    1226         stack_node(T)** crnt = &s->head;
    1227         for ( stack_node(T)* next = t.head; next; next = next->next ) {
    1228                 *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
    1229                 stack_node(T)* acrnt = *crnt;
     1213forall(otype T) void ?{}(stack(T) * s) { (&s->head){ 0 }; }
     1214forall(otype T) void ?{}(stack(T) * s, stack(T) t) {
     1215        stack_node(T) ** crnt = &s->head;
     1216        for ( stack_node(T) * next = t.head; next; next = next->next ) {
     1217                *crnt = ((stack_node(T) *)malloc()){ next->value }; /***/
     1218                stack_node(T) * acrnt = *crnt;
    12301219                crnt = &acrnt->next;
    12311220        }
    12321221        *crnt = 0;
    12331222}
    1234 forall(otype T) stack(T) ?=?(stack(T)* s, stack(T) t) {
     1223forall(otype T) stack(T) ?=?(stack(T) * s, stack(T) t) {
    12351224        if ( s->head == t.head ) return *s;
    12361225        clear(s);
    … …  
    12381227        return *s;
    12391228}
    1240 forall(otype T) void ^?{}(stack(T)* s) { clear(s); }
    1241 forall(otype T) _Bool empty(const stack(T)* s) { return s->head == 0; }
    1242 forall(otype T) void push(stack(T)* s, T value) {
    1243         s->head = ((stack_node(T)*)malloc()){ value, s->head }; /***/
    1244 }
    1245 forall(otype T) T pop(stack(T)* s) {
    1246         stack_node(T)* n = s->head;
     1229forall(otype T) void ^?{}(stack(T) * s) { clear(s); }
     1230forall(otype T) _Bool empty(const stack(T) * s) { return s->head == 0; }
     1231forall(otype T) void push(stack(T) * s, T value) {
     1232        s->head = ((stack_node(T) *)malloc()){ value, s->head }; /***/
     1233}
     1234forall(otype T) T pop(stack(T) * s) {
     1235        stack_node(T) * n = s->head;
    12471236        s->head = n->next;
    12481237        T x = n->value;
    … …  
    12511240        return x;
    12521241}
    1253 forall(otype T) void clear(stack(T)* s) {
    1254         for ( stack_node(T)* next = s->head; next; ) {
    1255                 stack_node(T)* crnt = next;
     1242forall(otype T) void clear(stack(T) * s) {
     1243        for ( stack_node(T) * next = s->head; next; ) {
     1244                stack_node(T) * crnt = next;
    12561245                next = crnt->next;
    12571246                delete(crnt);
    … …  
    12671256        struct node {
    12681257                T value;
    1269                 node* next;
    1270                 node( const T& v, node* n = nullptr ) : value(v), next(n) {}
     1258                node * next;
     1259                node( const T & v, node * n = nullptr ) : value(v), next(n) {}
    12711260        };
    1272         node* head;
     1261        node * head;
    12731262        void copy(const stack<T>& o) {
    1274                 node** crnt = &head;
    1275                 for ( node* next = o.head;; next; next = next->next ) {
     1263                node ** crnt = &head;
     1264                for ( node * next = o.head;; next; next = next->next ) {
    12761265                        *crnt = new node{ next->value }; /***/
    12771266                        crnt = &(*crnt)->next;
    … …  
    12821271        stack() : head(nullptr) {}
    12831272        stack(const stack<T>& o) { copy(o); }
    1284         stack(stack<T>&& o) : head(o.head) { o.head = nullptr; }
     1273        stack(stack<T> && o) : head(o.head) { o.head = nullptr; }
    12851274        ~stack() { clear(); }
    1286         stack& operator= (const stack<T>& o) {
     1275        stack & operator= (const stack<T>& o) {
    12871276                if ( this == &o ) return *this;
    12881277                clear();
    … …  
    12901279                return *this;
    12911280        }
    1292         stack& operator= (stack<T>&& o) {
     1281        stack & operator= (stack<T> && o) {
    12931282                if ( this == &o ) return *this;
    12941283                head = o.head;
    … …  
    12971286        }
    12981287        bool empty() const { return head == nullptr; }
    1299         void push(const T& value) { head = new node{ value, head };  /***/ }
     1288        void push(const T & value) { head = new node{ value, head };  /***/ }
    13001289        T pop() {
    1301                 node* n = head;
     1290                node * n = head;
    13021291                head = n->next;
    13031292                T x = std::move(n->value);
    … …  
    13061295        }
    13071296        void clear() {
    1308                 for ( node* next = head; next; ) {
    1309                         node* crnt = next;
     1297                for ( node * next = head; next; ) {
     1298                        node * crnt = next;
    13101299                        next = crnt->next;
    13111300                        delete crnt;
    … …  
    13201309\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    13211310struct stack_node {
    1322         void* value;
    1323         struct stack_node* next;
     1311        void * value;
     1312        struct stack_node * next;
    13241313};
    13251314struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    1326 void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
    1327         struct stack_node** crnt = &s->head;
    1328         for ( struct stack_node* next = t->head; next; next = next->next ) {
     1315void copy_stack(struct stack * s, const struct stack * t, void * (*copy)(const void *)) {
     1316        struct stack_node ** crnt = &s->head;
     1317        for ( struct stack_node * next = t->head; next; next = next->next ) {
    13291318                *crnt = malloc(sizeof(struct stack_node)); /***/
    13301319                **crnt = (struct stack_node){ copy(next->value) }; /***/
    … …  
    13331322        *crnt = 0;
    13341323}
    1335 _Bool stack_empty(const struct stack* s) { return s->head == NULL; }
    1336 void push_stack(struct stack* s, void* value) {
    1337         struct stack_node* n = malloc(sizeof(struct stack_node)); /***/
     1324_Bool stack_empty(const struct stack * s) { return s->head == NULL; }
     1325void push_stack(struct stack * s, void * value) {
     1326        struct stack_node * n = malloc(sizeof(struct stack_node)); /***/
    13381327        *n = (struct stack_node){ value, s->head }; /***/
    13391328        s->head = n;
    13401329}
    1341 void* pop_stack(struct stack* s) {
    1342         struct stack_node* n = s->head;
     1330void * pop_stack(struct stack * s) {
     1331        struct stack_node * n = s->head;
    13431332        s->head = n->next;
    1344         void* x = n->value;
     1333        void * x = n->value;
    13451334        free(n);
    13461335        return x;
    13471336}
    1348 void clear_stack(struct stack* s, void (*free_el)(void*)) {
    1349         for ( struct stack_node* next = s->head; next; ) {
    1350                 struct stack_node* crnt = next;
     1337void clear_stack(struct stack * s, void (*free_el)(void *)) {
     1338        for ( struct stack_node * next = s->head; next; ) {
     1339                struct stack_node * crnt = next;
    13511340                next = crnt->next;
    13521341                free_el(crnt->value);
    … …  
    13601349\CCV
    13611350\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    1362 stack::node::node( const object& v, node* n ) : value( v.new_copy() ), next( n ) {}
    1363 void stack::copy(const stack& o) {
    1364         node** crnt = &head;
    1365         for ( node* next = o.head; next; next = next->next ) {
     1351stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
     1352void stack::copy(const stack & o) {
     1353        node ** crnt = &head;
     1354        for ( node * next = o.head; next; next = next->next ) {
    13661355                *crnt = new node{ *next->value };
    13671356                crnt = &(*crnt)->next;
    … …  
    13701359}
    13711360stack::stack() : head(nullptr) {}
    1372 stack::stack(const stack& o) { copy(o); }
    1373 stack::stack(stack&& o) : head(o.head) { o.head = nullptr; }
     1361stack::stack(const stack & o) { copy(o); }
     1362stack::stack(stack && o) : head(o.head) { o.head = nullptr; }
    13741363stack::~stack() { clear(); }
    1375 stack& stack::operator= (const stack& o) {
     1364stack & stack::operator= (const stack & o) {
    13761365        if ( this == &o ) return *this;
    13771366        clear();
    … …  
    13791368        return *this;
    13801369}
    1381 stack& stack::operator= (stack&& o) {
     1370stack & stack::operator= (stack && o) {
    13821371        if ( this == &o ) return *this;
    13831372        head = o.head;
    … …  
    13861375}
    13871376bool stack::empty() const { return head == nullptr; }
    1388 void stack::push(const object& value) { head = new node{ value, head }; /***/ }
     1377void stack::push(const object & value) { head = new node{ value, head }; /***/ }
    13891378ptr<object> stack::pop() {
    1390         node* n = head;
     1379        node * n = head;
    13911380        head = n->next;
    13921381        ptr<object> x = std::move(n->value);
    … …  
    13951384}
    13961385void stack::clear() {
    1397         while ( node* next = head; next; ) {
    1398                 node* crnt = next;
     1386        for ( node * next = head; next; ) {
     1387                node * crnt = next;
    13991388                next = crnt->next;
    14001389                delete crnt;
Note: See TracChangeset for help on using the changeset viewer.