Changeset 43a284c for doc/generic_types/generic_types.tex

Timestamp:

Apr 17, 2017, 4:55:53 PM (7 years ago)

Author:

Peter A. Buhr <pabuhr@…>

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:

eb79750

Parents:

4ae83a4b

Message:

add stack implementation

File:

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

doc/generic_types/generic_types.tex

@@ -948 +948 @@
 Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
 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 source-code interfaces in Appendix~\ref{sec:BenchmarkInterfaces}).
+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 to show the costs of idiomatic use of each language's features covering common usage.
@@ -964 +964 @@
 \begin{figure}
 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
-int main( int argc, char *argv[] ) {
+int main( int argc, char * argv[] ) {
         FILE * out = fopen( "cfa-out.txt", "w" );
         int maxi = 0, vali = 42;
@@ -1039 +1039 @@
 To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
 The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code.
-The three instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
-These uses are similar to the @new@ expressions in \CC, though ongoing work on the \CFA compiler's type resolver should shortly render even these type casts superfluous.
+The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).
+These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous.
 
 
@@ -1143 +1143 @@
 \appendix
 
-\section{Benchmark Interfaces}
-\label{sec:BenchmarkInterfaces}
+\section{Benchmark Stack Implementation}
+\label{sec:BenchmarkStackImplementation}
 
 \lstset{basicstyle=\linespread{0.9}\sf\small}
 
+\begin{comment}
 \CFA
 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
@@ -1212 +1213 @@
 void print( FILE * out, const char * fmt, ... );
 \end{lstlisting}
+\end{comment}
+
+Throughout, @/***/@ designates a counted redundant type annotation.
+
+\medskip\noindent
+\CFA
+\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
+forall(otype T) struct stack_node {
+        T value;
+        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;
+                crnt = &acrnt->next;
+        }
+        *crnt = 0;
+}
+forall(otype T) stack(T) ?=?(stack(T)* s, stack(T) t) {
+        if ( s->head == t.head ) return *s;
+        clear(s);
+        s{ t };
+        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;
+        s->head = n->next;
+        T x = n->value;
+        ^n{};
+        free(n);
+        return x;
+}
+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);
+        }
+        s->head = 0;
+}
+\end{lstlisting}
+
+\medskip\noindent
+\CC
+\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
+template<typename T> class stack {
+        struct node {
+                T value;
+                node* next;
+                node( const T& v, node* n = nullptr ) : value(v), next(n) {}
+        };
+        node* head;
+        void copy(const stack<T>& o) {
+                node** crnt = &head;
+                for ( node* next = o.head;; next; next = next->next ) {
+                        *crnt = new node{ next->value }; /***/
+                        crnt = &(*crnt)->next;
+                }
+                *crnt = nullptr;
+        }
+  public:
+        stack() : head(nullptr) {}
+        stack(const stack<T>& o) { copy(o); }
+        stack(stack<T>&& o) : head(o.head) { o.head = nullptr; }
+        ~stack() { clear(); }
+        stack& operator= (const stack<T>& o) {
+                if ( this == &o ) return *this;
+                clear();
+                copy(o);
+                return *this;
+        }
+        stack& operator= (stack<T>&& o) {
+                if ( this == &o ) return *this;
+                head = o.head;
+                o.head = nullptr;
+                return *this;
+        }
+        bool empty() const { return head == nullptr; }
+        void push(const T& value) { head = new node{ value, head };  /***/ }
+        T pop() {
+                node* n = head;
+                head = n->next;
+                T x = std::move(n->value);
+                delete n;
+                return x;
+        }
+        void clear() {
+                for ( node* next = head; next; ) {
+                        node* crnt = next;
+                        next = crnt->next;
+                        delete crnt;
+                }
+                head = nullptr;
+        }
+};
+\end{lstlisting}
+
+\medskip\noindent
+C
+\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
+struct stack_node {
+        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 ) {
+                *crnt = malloc(sizeof(struct stack_node)); /***/
+                **crnt = (struct stack_node){ copy(next->value) }; /***/
+                crnt = &(*crnt)->next;
+        }
+        *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)); /***/
+        *n = (struct stack_node){ value, s->head }; /***/
+        s->head = n;
+}
+void* pop_stack(struct stack* s) {
+        struct stack_node* n = s->head;
+        s->head = n->next;
+        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;
+                next = crnt->next;
+                free_el(crnt->value);
+                free(crnt);
+        }
+        s->head = NULL;
+}
+\end{lstlisting}
+
+\medskip\noindent
+\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 ) {
+                *crnt = new node{ *next->value };
+                crnt = &(*crnt)->next;
+        }
+        *crnt = nullptr;
+}
+stack::stack() : 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) {
+        if ( this == &o ) return *this;
+        clear();
+        copy(o);
+        return *this;
+}
+stack& stack::operator= (stack&& o) {
+        if ( this == &o ) return *this;
+        head = o.head;
+        o.head = nullptr;
+        return *this;
+}
+bool stack::empty() const { return head == nullptr; }
+void stack::push(const object& value) { head = new node{ value, head }; /***/ }
+ptr<object> stack::pop() {
+        node* n = head;
+        head = n->next;
+        ptr<object> x = std::move(n->value);
+        delete n;
+        return x;
+}
+void stack::clear() {
+        while ( node* next = head; next; ) {
+                node* crnt = next;
+                next = crnt->next;
+                delete crnt;
+        }
+        head = nullptr;
+}
+\end{lstlisting}
 
 
 \begin{comment}
-Throughout, @/***/@ designates a counted redundant type annotation.
 
 \subsubsection{bench.h}