Changeset e84382b for doc/papers/general


Ignore:
Timestamp:
Mar 9, 2018, 1:34:04 PM (6 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:
860f19f
Parents:
b51e5fdb (diff), 3d8f2f8 (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/papers/general
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • doc/papers/general/Paper.tex

    rb51e5fdb re84382b  
    368368Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
    369369
     370Unconstruction is a mechanism to distribute @forall@ over related routines/types (see @stack@ examples in Section~\ref{sec:eval}):
     371\begin{cfa}
     372forall( otype T ) {                                                     $\C{// forall block}$
     373        struct stack { stack_node(T) * head; }; $\C{// generic type}$
     374        void push( stack(T) & s, T value ) ...  $\C{// generic operations}$
     375        T pop( stack(T) & s ) ...
     376}
     377\end{cfa}
     378Each block declaration is prefixed with the initial @forall@ clause significantly reducing duplication.
     379
    370380
    371381\subsection{Traits}
    … …  
    836846% \end{cfa}
    837847% so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    838 % These thunks are generated locally using gcc nested-functions, rather hositing them to the external scope, so they can easily access local state.
     848% These thunks are generated locally using gcc nested-functions, rather hoisting them to the external scope, so they can easily access local state.
    839849
    840850
    … …  
    11671177\lstMakeShortInline@%
    11681178\end{cquote}
    1169 The target label must be below the @fallthrough@, \ie @fallthrough@ cannot form a loop, and the label may not be nested in a control structor, \ie it must be at the same level as the @case@ clauses;
     1179The target label must be below the @fallthrough@, \ie @fallthrough@ cannot form a loop, and the label may not be nested in a control structure, \ie it must be at the same level as the @case@ clauses;
    11701180the target label may be case @default@.
    11711181
    … …  
    21552165\begin{cfa}
    21562166struct W {
    2157     double stones;
    2158     W() { stones = 0.0; }
    2159     W( double w ) { stones = w; }
     2167        double stones;
     2168        W() { stones = 0.0; }
     2169        W( double w ) { stones = w; }
    21602170};
    21612171W operator+( W l, W r ) {
    … …  
    27192729
    27202730\CC is the best known C-based language, and is similar to \CFA in that both are extensions to C with source and runtime backwards compatibility.
    2721 Specific difference between \CFA and \CC have been identified in prior sections, with a final observation that \CFA has equal or few tokens to express the same notion in several cases.
    2722 The key difference between design philosophies is that \CFA is easier for C programmers to understand, by maintaining a procedural paradigm and avoiding complex interactions among extensions.
     2731Specific difference between \CFA and \CC have been identified in prior sections, with a final observation that \CFA has equal or fewer tokens to express the same notion in many cases.
     2732The key difference in design philosophies is that \CFA is easier for C programmers to understand by maintaining a procedural paradigm and avoiding complex interactions among extensions.
    27232733\CC, on the other hand, has multiple overlapping features (such as the three forms of polymorphism), many of which have complex interactions with its object-oriented design.
    2724 As a result, \CC has a steep learning curve for even experienced C programmers, especially when attempting to maintain performance equivalent to C legacy code.
     2734As a result, \CC has a steep learning curve for even experienced C programmers, especially when attempting to maintain performance equivalent to C legacy-code.
    27252735
    27262736There are several other C extension-languages with less usage and even more dramatic changes than \CC.
    … …  
    27282738Other languages extend C with more focused features.
    27292739CUDA~\cite{Nickolls08}, ispc~\cite{Pharr12}, and Sierra~\cite{Leissa14} add data-parallel primitives to C or \CC;
    2730 such features have not yet been added to \CFA, but are not precluded by the design.
    2731 Finaly, some C extensions (or suggested extensions) attempt to provide a more memory-safe C~\cite{Boehm88};
    2732 type-checked polymorphism in \CFA covers several of C's memory-safety holes, but more aggressive approaches such as annotating all pointer types with their nullability are contradictory to \CFA's backwards compatibility goals.
     2740such features have not yet been added to \CFA, but are easily incorporated within its design.
     2741Finally, some C extensions (or suggested extensions) attempt to provide a more memory-safe C~\cite{Boehm88,Rafkind09};
     2742type-checked polymorphism in \CFA covers several of C's memory-safety issues, but more aggressive approaches such as annotating all pointer types with their nullability are contradictory to \CFA's backwards compatibility goals.
    27332743
    27342744
    … …  
    28412851        struct stack_node * n = s->head;
    28422852        s->head = n->next;
    2843         void * x = n->value;
     2853        void * v = n->value;
    28442854        free( n );
    2845         return x;
     2855        return v;
    28462856}
    28472857\end{cfa}
    … …  
    28972907\end{cfa}
    28982908
     2909\begin{comment}
     2910forall( otype T ) {
     2911        struct stack_node {
     2912                T value;
     2913                stack_node(T) * next;
     2914        };
     2915        struct stack { stack_node(T) * head; };
     2916        void clear( stack(T) & s ) with( s ) {
     2917                for ( stack_node(T) * next = head; next; ) {
     2918                        stack_node(T) * crnt = next;
     2919                        next = crnt->next;
     2920                        ^(*crnt){};
     2921                        free(crnt);
     2922                }
     2923                head = 0;
     2924        }
     2925        void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2926        void ?{}( stack(T) & s, stack(T) t ) {
     2927                stack_node(T) ** crnt = &s.head;
     2928                for ( stack_node(T) * next = t.head; next; next = next->next ) {
     2929                        *crnt = alloc();
     2930                        ((*crnt)->value){ next->value };
     2931                        crnt = &(*crnt)->next;
     2932                }
     2933                *crnt = 0;
     2934        }
     2935        stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2936                if ( s.head == t.head ) return s;
     2937                clear( s );
     2938                s{ t };
     2939                return s;
     2940        }
     2941        void ^?{}( stack(T) & s) { clear( s ); }
     2942        _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2943        void push( stack(T) & s, T value ) with( s ) {
     2944                stack_node(T) * n = alloc();
     2945                (*n){ value, head };
     2946                head = n;
     2947        }
     2948        T pop( stack(T) & s ) with( s ) {
     2949                stack_node(T) * n = head;
     2950                head = n->next;
     2951                T v = n->value;
     2952                ^(*n){};
     2953                free( n );
     2954                return v;
     2955        }
     2956}
     2957\end{comment}
     2958
    28992959\medskip\noindent
    29002960\CC
    … …  
    29072967        };
    29082968        node * head;
     2969        stack() : head( nullptr ) {}
     2970        stack( const stack<T> & o) { copy( o ); }
     2971        stack( stack<T> && o ) : head( o.head ) { o.head = nullptr; }
    29092972        void clear() {
    29102973                for ( node * next = head; next; ) {
    … …  
    29232986                *crnt = nullptr;
    29242987        }
    2925         stack() : head( nullptr) {}
    2926         stack( const stack<T> & o ) { copy( o ); }
    29272988        ~stack() { clear(); }
    2928         stack & operator= ( const stack<T> & o) {
     2989        stack & operator= ( const stack<T> & o ) {
    29292990                if ( this == &o ) return *this;
    29302991                clear();
    … …  
    29372998                node * n = head;
    29382999                head = n->next;
    2939                 T x = std::move( n->value );
     3000                T v = std::move( n->value );
    29403001                delete n;
    2941                 return x;
     3002                return v;
    29423003        }
    29433004};
    … …  
    29503011        struct node {
    29513012                ptr<object> value;
    2952                 node* next;
    2953                 node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
     3013                node * next;
     3014                node( const object & v, node * n = nullptr ) : value( v.new_copy() ), next( n ) {}
    29543015        };
    2955         node* head;
     3016        node * head;
    29563017        void clear() {
    29573018                for ( node * next = head; next; ) {
    … …  
    29723033        stack() : head( nullptr ) {}
    29733034        stack( const stack & o ) { copy( o ); }
    2974                 ~stack() { clear(); }
     3035        ~stack() { clear(); }
    29753036        stack & operator= ( const stack & o ) {
    29763037                if ( this == &o ) return *this;
    … …  
    29843045                node * n = head;
    29853046                head = n->next;
    2986                 ptr<object> x = std::move( n->value );
     3047                ptr<object> v = std::move( n->value );
    29873048                delete n;
    2988                 return x;
     3049                return v;
    29893050        }
    29903051};

  • doc/papers/general/evaluation/c-stack.c

    rb51e5fdb re84382b  
    33
    44struct stack_node {
    5         void* value;
    6         struct stack_node* next;
     5        void * value;
     6        struct stack_node * next;
    77};
     8
     9void clear_stack( struct stack * s, void (*free_el)( void * ) ) {
     10        for ( struct stack_node * next = s->head; next; ) {
     11                struct stack_node * crnt = next;
     12                next = crnt->next;
     13                free_el( crnt->value );
     14                free( crnt );
     15        }
     16        s->head = NULL;
     17}
    818
    919struct stack new_stack() { return (struct stack){ NULL }; /***/ }
    1020
    11 void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
    12         struct stack_node** crnt = &s->head;
    13         for ( struct stack_node* next = t->head; next; next = next->next ) {
    14                 *crnt = malloc(sizeof(struct stack_node)); /***/
    15                 (*crnt)->value = copy(next->value);
     21void copy_stack( struct stack * s, const struct stack * t, void * (*copy)( const void * ) ) {
     22        struct stack_node ** crnt = &s->head;
     23        for ( struct stack_node * next = t->head; next; next = next->next ) {
     24                *crnt = malloc( sizeof(struct stack_node) ); /***/
     25                (*crnt)->value = copy( next->value );
    1626                crnt = &(*crnt)->next;
    1727        }
    1828        *crnt = NULL;
    1929}
    20 
    21 struct stack* assign_stack(struct stack* s, const struct stack* t,
    22                 void* (*copy_el)(const void*), void (*free_el)(void*)) {
     30struct stack * assign_stack( struct stack * s, const struct stack * t,
     31                void * (*copy_el)( const void * ), void (*free_el)( void * ) ) {
    2332        if ( s->head == t->head ) return s;
    2433        clear_stack( s, free_el ); /***/
    … …  
    2736}
    2837
    29 void clear_stack(struct stack* s, void (*free_el)(void*)) {
    30     for ( struct stack_node* next = s->head; next; ) {
    31                 struct stack_node* crnt = next;
    32                 next = crnt->next;
    33                 free_el(crnt->value);
    34                 free(crnt);
    35         }
    36         s->head = NULL;
    37 }
     38_Bool stack_empty( const struct stack * s ) { return s->head == NULL; }
    3839
    39 _Bool stack_empty(const struct stack* s) { return s->head == NULL; }
    40 
    41 void push_stack(struct stack* s, void* value) {
    42         struct stack_node* n = malloc(sizeof(struct stack_node)); /***/
     40void push_stack( struct stack * s, void * value ) {
     41        struct stack_node * n = malloc( sizeof(struct stack_node) ); /***/
    4342        *n = (struct stack_node){ value, s->head }; /***/
    4443        s->head = n;
    4544}
    4645
    47 void* pop_stack(struct stack* s) {
    48         struct stack_node* n = s->head;
     46void * pop_stack( struct stack * s ) {
     47        struct stack_node * n = s->head;
    4948        s->head = n->next;
    50         void* x = n->value;
    51         free(n);
    52         return x;
     49        void * v = n->value;
     50        free( n );
     51        return v;
    5352}

  • doc/papers/general/evaluation/cfa-stack.c

    rb51e5fdb re84382b  
    66        stack_node(T) * next;
    77};
     8
     9forall( otype T ) void clear( stack(T) & s ) with( s ) {
     10        for ( stack_node(T) * next = head; next; ) {
     11                stack_node(T) * crnt = next;
     12                next = crnt->next;
     13                ^(*crnt){};
     14                free(crnt);
     15        }
     16        head = 0;
     17}
    818
    919forall( otype T ) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    … …  
    4454        return v;
    4555}
    46 
    47 forall( otype T ) void clear( stack(T) & s ) with( s ) {
    48         for ( stack_node(T) * next = head; next; ) {
    49                 stack_node(T) * crnt = next;
    50                 next = crnt->next;
    51                 ^(*crnt){};
    52                 free(crnt);
    53         }
    54         head = 0;
    55 }

  • doc/papers/general/evaluation/cpp-stack.hpp

    rb51e5fdb re84382b  
    22#include <utility>
    33
    4 template<typename T> class stack {
     4template<typename T> struct stack {
    55        struct node {
    66                T value;
    7                 node* next;
     7                node * next;
     8                node( const T & v, node * n = nullptr ) : value( v ), next( n ) {}
     9        };
     10        node * head;
    811
    9                 node( const T& v, node* n = nullptr ) : value(v), next(n) {}
    10         };
    11         node* head;
     12        stack() : head( nullptr ) {}
     13        stack( const stack<T> & o ) { copy( o ); }
     14        stack( stack<T> && o ) : head( o.head ) { o.head = nullptr; }
    1215
    13         void copy(const stack<T>& o) {
    14                 node** crnt = &head;
    15                 for ( node* next = o.head; next; next = next->next ) {
    16                         *crnt = new node{ next->value }; /***/
    17                         crnt = &(*crnt)->next;
    18                 }
    19                 *crnt = nullptr;
    20         }
    21 public:
    2216        void clear() {
    23             for ( node* next = head; next; ) {
    24                         node* crnt = next;
     17                for ( node * next = head; next; ) {
     18                        node * crnt = next;
    2519                        next = crnt->next;
    2620                        delete crnt;
    … …  
    2923        }
    3024
    31         stack() : head(nullptr) {}
    32         stack(const stack<T>& o) { copy(o); }
     25        void copy( const stack<T> & o ) {
     26                node ** crnt = &head;
     27                for ( node * next = o.head; next; next = next->next ) {
     28                        *crnt = new node{ next->value }; /***/
     29                        crnt = &(*crnt)->next;
     30                }
     31                *crnt = nullptr;
     32        }
     33
    3334        ~stack() { clear(); }
    3435
    35         stack& operator= (const stack<T>& o) {
     36        stack & operator= ( const stack<T> & o ) {
    3637                if ( this == &o ) return *this;
    3738                clear();
    38                 copy(o);
     39                copy( o );
    3940                return *this;
    4041        }
    … …  
    4243        bool empty() const { return head == nullptr; }
    4344
    44         void push(const T& value) { head = new node{ value, head };  /***/ }
     45        void push( const T & value ) { head = new node{ value, head };  /***/ }
    4546
    4647        T pop() {
    47                 node* n = head;
     48                node * n = head;
    4849                head = n->next;
    49                 T x = std::move(n->value);
     50                T v = std::move( n->value );
    5051                delete n;
    51                 return x;
     52                return v;
    5253        }
    5354};

  • doc/papers/general/evaluation/cpp-vstack.cpp

    rb51e5fdb re84382b  
    22#include <utility>
    33
    4 stack::node::node( const object& v, node* n ) : value( v.new_copy() ), next( n ) {}
     4stack::node::node( const object & v, node * n ) : value( v.new_copy() ), next( n ) {}
    55
    6 void stack::copy(const stack& o) {
    7         node** crnt = &head;
    8         for ( node* next = o.head; next; next = next->next ) {
     6void stack::clear() {
     7        for ( node * next = head; next; ) {
     8                node * crnt = next;
     9                next = crnt->next;
     10                delete crnt;
     11        }
     12        head = nullptr;
     13}
     14
     15void stack::copy( const stack & o ) {
     16        node ** crnt = &head;
     17        for ( node * next = o.head; next; next = next->next ) {
    918                *crnt = new node{ *next->value }; /***/
    1019                crnt = &(*crnt)->next;
    … …  
    1322}
    1423
    15 stack::stack() : head(nullptr) {}
    16 stack::stack(const stack& o) { copy(o); }
     24stack::stack() : head( nullptr ) {}
     25stack::stack( const stack & o ) { copy( o ); }
     26stack::stack( stack && o ) : head( o.head ) { o.head = nullptr; }
    1727stack::~stack() { clear(); }
    1828
    19 stack& stack::operator= (const stack& o) {
     29stack & stack::operator=( const stack & o ) {
    2030        if ( this == &o ) return *this;
    2131        clear();
    22         copy(o);
     32        copy( o );
    2333        return *this;
    2434}
    2535
    26 void stack::clear() {
    27     for ( node* next = head; next; ) {
    28                 node* crnt = next;
    29                 next = crnt->next;
    30                 delete crnt;
    31         }
    32         head = nullptr;
     36stack & stack::operator=( stack && o ) {
     37        if ( this == &o ) return *this;
     38        head = o.head;
     39        o.head = nullptr;
     40        return *this;
    3341}
    34 
    3542
    3643bool stack::empty() const { return head == nullptr; }
    3744
    38 void stack::push(const object& value) { head = new node{ value, head }; /***/ }
     45void stack::push( const object & value ) { head = new node{ value, head }; /***/ }
    3946
    4047ptr<object> stack::pop() {
    41         node* n = head;
     48        node * n = head;
    4249        head = n->next;
    43         ptr<object> x = std::move(n->value);
     50        ptr<object> v = std::move( n->value );
    4451        delete n;
    45         return x;
     52        return v;
    4653}

  • doc/papers/general/evaluation/cpp-vstack.hpp

    rb51e5fdb re84382b  
    22#include "object.hpp"
    33
    4 class stack {
     4struct stack {
    55        struct node {
    66                ptr<object> value;
    7                 node* next;
    8 
    9                 node( const object& v, node* n = nullptr );
     7                node * next;
     8                node( const object & v, node * n = nullptr );
    109        };
    11         node* head;
    12 
    13         void copy(const stack& o);
    14 public:
    15         stack();
    16         stack(const stack& o);
    17         ~stack();
    18         stack& operator= (const stack& o);
     10        node * head;
    1911
    2012        void clear();
     13        void copy( const stack & o );
     14
     15        stack();
     16        stack( const stack & o );
     17        stack( stack && o );
     18        ~stack();
     19        stack & operator=( const stack& o );
     20        stack & operator=( stack && o );
    2121        bool empty() const;
    22         void push(const object& value);
     22        void push( const object & value );
    2323        ptr<object> pop();
    2424};
Note: See TracChangeset for help on using the changeset viewer.