Changes in / [32bcef7:4f57930]

Location:

doc/generic_types

Files:

• evaluation/Makefile (modified) (1 diff)
• evaluation/bench.h (modified) (1 diff)
• evaluation/bench.hpp (modified) (1 diff)
• evaluation/c-bench.c (modified) (3 diffs)
• evaluation/c-pair.c (added)
• evaluation/c-pair.h (added)
• evaluation/c-stack.c (modified) (2 diffs)
• evaluation/c-stack.h (modified) (1 diff)
• evaluation/cfa-bench.c (modified) (2 diffs)
• evaluation/cfa-pair.c (added)
• evaluation/cfa-stack.c (modified) (1 diff)
• evaluation/cpp-bench.cpp (modified) (2 diffs)
• evaluation/cpp-vbench.cpp (modified) (2 diffs)
• evaluation/object.hpp (modified) (5 diffs)
• evaluation/pair (added)
• generic_types.tex (modified) (3 diffs)

doc/generic_types/evaluation/Makefile

@@ -25 +25 @@
         $(COMPILE.cfa) $(OUTPUT_OPTION) -c $<
 
-COBJS = c-stack.o
+COBJS = c-stack.o c-pair.o
 CPPOBJS = 
 CPPVOBJS = cpp-vstack.o
-CFAOBJS = cfa-stack.o
+CFAOBJS = cfa-stack.o cfa-pair.o
 
 c-bench: c-bench.c c-bench.d $(COBJS)

doc/generic_types/evaluation/bench.h

@@ -4 +4 @@
 #include <time.h>
 
-#define N 100000000
+#define N 50000000
 
 long ms_between(clock_t start, clock_t end) {

doc/generic_types/evaluation/bench.hpp

@@ -5 +5 @@
 #include <time.h>
 
-static const int N = 100000000;
+static const int N = 50000000;
 
 long ms_between(clock_t start, clock_t end) {

doc/generic_types/evaluation/c-bench.c

@@ -1 +1 @@
 #include <stdlib.h>
 #include "bench.h"
+#include "c-pair.h"
 #include "c-stack.h"
 
-void* copy_int( void* p ) {
+_Bool* new_bool( _Bool b ) {
+        _Bool* q = malloc(sizeof(_Bool));
+        *q = b;
+        return q;
+}
+
+char* new_char( char c ) {
+        char* q = malloc(sizeof(char));
+        *q = c;
+        return q;
+}
+
+int* new_int( int i ) {
         int* q = malloc(sizeof(int));
-        *q = *(int*)p;
+        *q = i;
         return q;
+}
+
+void* copy_bool( const void* p ) { return new_bool( *(const _Bool*)p ); }
+
+void* copy_char( const void* p ) { return new_char( *(const char*)p ); }
+
+void* copy_int( const void* p ) { return new_int( *(const int*)p ); }
+
+void* copy_pair_bool_char( const void* p ) { return copy_pair( p, copy_bool, copy_char ); }
+
+void free_pair_bool_char( void* p ) { free_pair( p, free, free ); }
+
+int cmp_bool( const void* a, const void* b ) {
+        return *(const _Bool*)a == *(const _Bool*)b ? 0 : *(const _Bool*)a < *(const _Bool*)b ? -1 : 1;
+}
+
+int cmp_char( const void* a, const void* b ) {
+        return *(const char*)a == *(const char*)b ? 0 : *(const char*)a < *(const char*)b ? -1 : 1;
 }
 
@@ -14 +45 @@
         struct stack s = new_stack();
         REPEAT_TIMED( "push_int",
-                int* x = malloc(sizeof(int));
-                *x = rand();
-                push_stack(&s, x);
+                push_stack(&s, new_int( rand() ));
         )
 
@@ -25 +54 @@
 
         TIMED( "clear_int",
-                clear_stack(&s);
+                clear_stack(&s, free);
         )
 
-        int sum;
+        int max = 0;
         REPEAT_TIMED( "pop_int", 
                 int* x = pop_stack(&t);
-                sum += *x;
+                if ( *x > max ) { max = *x; }
                 free(x);
         )
+
+        struct stack s2 = new_stack();
+        REPEAT_TIMED( "push_bool_char", 
+                push_stack(&s2, new_pair( new_bool( rand() & 0x1 ), new_char( rand() & 0x7F ) ));
+        )
+
+        struct stack t2;
+        TIMED( "copy_bool_char", 
+                copy_stack(&t2, &s2, copy_pair_bool_char);
+        )
+
+        TIMED( "clear_bool_char", 
+                clear_stack(&s2, free_pair_bool_char);
+        )
+
+        struct pair* max2 = new_pair( new_bool(0), new_char('\0') );
+        REPEAT_TIMED( "pop_bool_char", 
+                struct pair* x = pop_stack(&t2);
+                if ( cmp_pair( x, max2, cmp_bool, cmp_char ) > 0 ) {
+                        free_pair_bool_char( max2 );
+                        max2 = x;
+                } else {
+                        free_pair_bool_char( x );
+                }
+        )
+        free_pair_bool_char( max2 );
 }

doc/generic_types/evaluation/c-stack.c

@@ -11 +11 @@
 }
 
-void copy_stack(struct stack* s, struct stack* t, void* (*copy)(void*)) {
+void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
         struct stack_node** crnt = &s->head;
         struct stack_node* next = t->head;
@@ -23 +23 @@
 }
 
-void clear_stack(struct stack* s) {
+void clear_stack(struct stack* s, void (*free_el)(void*)) {
         struct stack_node* next = s->head;
         while ( next ) {
                 struct stack_node* crnt = next;
                 next = crnt->next;
-                free(crnt->value);
+                free_el(crnt->value);
                 free(crnt);
         }

doc/generic_types/evaluation/c-stack.h

@@ -9 +9 @@
 struct stack new_stack();
 
-void copy_stack(struct stack* dst, struct stack* src, void* (*copy)(void*));
+void copy_stack(struct stack* dst, const struct stack* src, void* (*copy)(const void*));
 
-void clear_stack(struct stack* s);
+void clear_stack(struct stack* s, void (*free_el)(void*));
 
 _Bool stack_empty(const struct stack* s);

doc/generic_types/evaluation/cfa-bench.c

@@ +1 @@
+#include <stdlib>
 #include <stdlib.h>
+#include "pair"
 #include "bench.h"
 #include "cfa-stack.h"
@@ -20 +22 @@
         )
 
-        int sum;
+        int max = 0;
         REPEAT_TIMED( "pop_int", 
-                sum += pop( &t );
+                max = max( max, pop( &t ) );
+        )
+
+        stack(pair(_Bool, unsigned char)) s2;
+        REPEAT_TIMED( "push_bool_char",
+                push( &s2, (pair(_Bool, unsigned char)){ rand() & 0x1, rand() & 0x7F } );
+        )
+
+        stack(pair(_Bool, unsigned char)) t2;
+        TIMED( "copy_bool_char", 
+                t2 = s2;
+        )
+
+        TIMED( "clear_bool_char", 
+                clear( &s2 );
+        )
+
+        pair(_Bool, unsigned char) max2 = { (_Bool)0, '\0' };
+        REPEAT_TIMED( "pop_bool_char",
+                max2 = max( max2, pop( &t2 ) );
         )
 }

doc/generic_types/evaluation/cfa-stack.c

@@ -1 @@
-#include <assert>
 #include <stdlib>
 #include "cfa-stack.h"

doc/generic_types/evaluation/cpp-bench.cpp

@@ +1 @@
+#include <algorithm>
 #include <stdlib.h>
+#include <utility>
 #include "bench.hpp"
 #include "cpp-stack.hpp"
@@ -20 +22 @@
         )
 
-        int sum;
+        int max = 0;
         REPEAT_TIMED( "pop_int",
-                sum += t.pop();
+                max = std::max( max, t.pop() );
+        )
+
+        stack<std::pair<bool, char>> s2;
+        REPEAT_TIMED( "push_bool_char",
+                s2.push( std::pair<bool, char>{ rand() & 0x1, rand() & 0x7F } );
+        )
+
+        stack<std::pair<bool,char>> t2;
+        TIMED( "copy_bool_char", 
+                t2 = s2;
+        )
+
+        TIMED( "clear_bool_char", 
+                s2.clear();
+        )
+
+        std::pair<bool, char> max2 = { false, '\0' };
+        REPEAT_TIMED( "pop_bool_char",
+                max2 = std::max( max2, t2.pop() );
         )
 }

doc/generic_types/evaluation/cpp-vbench.cpp

@@ +1 @@
+#include <algorithm>
 #include <stdlib.h>
 #include "bench.hpp"
 #include "cpp-vstack.hpp"
+#include "object.hpp"
 
 int main(int argc, char** argv) {
@@ -20 +22 @@
         )
 
-        integer sum;
+        integer max;
         REPEAT_TIMED( "pop_int",
-                sum += t.pop()->as<integer>();
+                max = std::max( max, t.pop()->as<integer>() );
+        )
+
+        stack s2;
+        REPEAT_TIMED( "push_bool_char",
+                s2.push( std::make_unique<pair>( std::make_unique<boolean>( rand() & 0x1 ), 
+                        std::make_unique<character>( rand() & 0x7F ) ) );
+        )
+
+        stack t2;
+        TIMED( "copy_bool_char", 
+                t2 = s2;
+        )
+
+        TIMED( "clear_bool_char", 
+                s2.clear();
+        )
+
+        pair max2 = { std::make_unique<boolean>(false), std::make_unique<character>('\0') };
+        REPEAT_TIMED( "pop_bool_char",
+                max2 = std::max( max2, t2.pop()->as<pair>() );
         )
 }

doc/generic_types/evaluation/object.hpp

@@ -19 +19 @@
 };
 
+template<typename T>
+std::type_index class_of() { return { typeid(T) }; }
+
 class object {
 public:
@@ -25 +28 @@
         template<typename T>
         T& as() {
-                std::type_index from = get_class(), to = { typeid(T) };
+                std::type_index from = get_class(), to = class_of<T>();
                 if ( from != to ) throw bad_cast{ from, to };
                 return reinterpret_cast<T&>(*this);
@@ -32 +35 @@
         template<typename T>
         const T& as() const {
-                std::type_index from = get_class(), to = { typeid(T) };
+                std::type_index from = get_class(), to = class_of<T>();
                 if ( from != to ) throw bad_cast{ from, to };
                 return reinterpret_cast<const T&>(*this);
@@ -46 +49 @@
 };
 
-class integer : public object {
+template<typename T>
+T* as_subclass_of( object* o ) {
+        T* r = dynamic_cast<T*>( o );
+        if ( r == nullptr ) throw bad_cast{ o->get_class(), class_of<T>() };
+        return r;
+}
+
+template<typename T>
+const T* as_subclass_of( const object* o ) {
+        const T* r = dynamic_cast<const T*>( o );
+        if ( r == nullptr ) throw bad_cast{ o->get_class(), class_of<T>() };
+        return r;
+}
+
+class ordered : public object {
+public:
+        virtual int cmp(const ordered&) const = 0;
+
+        bool operator< (const ordered& that) const { return cmp(that) < 0; }
+
+        bool operator<= ( const ordered& that ) const { return cmp(that) <= 0; }
+
+        bool operator== ( const ordered& that ) const { return cmp(that) == 0; }
+
+        bool operator!= ( const ordered& that ) const { return cmp(that) != 0; }
+
+        bool operator> ( const ordered& that ) const { return cmp(that) > 0; }
+
+        bool operator>= ( const ordered& that ) const { return cmp(that) >= 0; }
+};
+
+class boolean : public ordered {
+private:
+        bool x;
+
+public:
+        boolean() = default;
+
+        boolean(bool x) : x(x) {}
+
+        std::unique_ptr<object> new_inst() const override { return std::make_unique<boolean>(); }
+        
+        std::unique_ptr<object> new_copy() const override { return std::make_unique<boolean>(*this); }
+
+        boolean& operator= (const boolean& that) {
+                x = that.x;
+                return *this;   
+        }
+
+        object& operator= (const object& that) override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return *this = static_cast<const boolean&>(that);
+        }
+
+        ~boolean() override = default;
+
+        int cmp(const boolean& that) const { return x == that.x ? 0 : x == false ? -1 : 1; }
+
+        // bool operator< (const boolean& that) const { return x < that.x; }
+
+        // bool operator== (const boolean& that) const { return x == that.x; }
+
+        int cmp(const ordered& that) const override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return cmp( static_cast<const boolean&>(that) );
+        }
+};
+
+class character : public ordered {
+private:
+        char x;
+
+public:
+        character() = default;
+
+        character(char x) : x(x) {}
+
+        std::unique_ptr<object> new_inst() const override { return std::make_unique<character>(); }
+        
+        std::unique_ptr<object> new_copy() const override { return std::make_unique<character>(*this); }
+
+        character& operator= (const character& that) {
+                x = that.x;
+                return *this;   
+        }
+
+        object& operator= (const object& that) override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return *this = static_cast<const character&>(that);
+        }
+
+        ~character() override = default;
+
+        int cmp(const character& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
+
+        // bool operator< (const character& that) const { return x < that.x; }
+
+        // bool operator== (const character& that) const { return x == that.x; }
+
+        int cmp(const ordered& that) const override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return cmp( static_cast<const character&>(that) );
+        }
+};
+
+class integer : public ordered {
 private:
         int x;
@@ -67 +179 @@
                 std::type_index from = that.get_class(), to = get_class();
                 if ( from != to ) throw bad_cast{ from, to };
-                return *this = reinterpret_cast<const integer&>(that);
+                return *this = static_cast<const integer&>(that);
         }
 
         ~integer() override = default;
 
-        integer& operator+= (const integer& that) {
-                x += that.x;
+        int cmp(const integer& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
+
+        // bool operator< (const integer& that) const { return x < that.x; }
+
+        // bool operator== (const integer& that) const { return x == that.x; }
+
+        int cmp(const ordered& that) const override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return cmp( static_cast<const integer&>(that) );
+        }
+};
+
+class pair : public ordered {
+private:
+        std::unique_ptr<object> x;
+        std::unique_ptr<object> y;
+
+public:
+        pair() = default;
+
+        pair(std::unique_ptr<object>&& x, std::unique_ptr<object>&& y)
+                : x(std::move(x)), y(std::move(y)) {}
+        
+        std::unique_ptr<object> new_inst() const override { return std::make_unique<pair>(); }
+
+        std::unique_ptr<object> new_copy() const override {
+                return std::make_unique<pair>(x->new_copy(), y->new_copy());
+        }
+
+        pair& operator= (const pair& that) {
+                x = that.x->new_copy();
+                y = that.y->new_copy();
                 return *this;
         }
-};
+
+        object& operator= (const object& that) override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return *this = static_cast<const pair&>(that);
+        }
+
+        ~pair() override = default;
+
+        int cmp(const pair& that) const {
+                const ordered* a = as_subclass_of<ordered>( x.get() );
+                const ordered* b = as_subclass_of<ordered>( that.x.get() );
+                int c = a->cmp( *b );
+                if ( c != 0 ) return c;
+                a = as_subclass_of<ordered>( y.get() );
+                b = as_subclass_of<ordered>( that.y.get() );
+                return a->cmp( *b );
+        }
+
+        // bool operator< (const pair& that) const { return cmp(that) < 0; }
+
+        // bool operator== ( const pair& that) const { return cmp(that) == 0; }
+
+        int cmp(const ordered& that) const override {
+                std::type_index from = that.get_class(), to = get_class();
+                if ( from != to ) throw bad_cast{ from, to };
+                return cmp( static_cast<const pair&>(that) );
+        }
+};

doc/generic_types/generic_types.tex

@@ -1 +1 @@
 % take off review (for line numbers) and anonymous (for anonymization) on submission
-% \documentclass[format=acmlarge, anonymous, review]{acmart}
-\documentclass[format=acmlarge,review]{acmart}
+\documentclass[format=acmlarge,anonymous,review]{acmart}
+% \documentclass[format=acmlarge,review]{acmart}
 
 \usepackage{xspace,calc,comment}
@@ -758 +758 @@
 It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions. For example, it is possible to write @new@ as a library function:
 \begin{lstlisting}
-struct Pair(otype R, otype S);
+struct pair(otype R, otype S);
 forall(otype R, otype S)
-void ?{}(Pair(R, S) *, R, S);  // (1)
+void ?{}(pair(R, S) *, R, S);  // (1)
 
 forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
@@ -767 +767 @@
 }
 
-Pair(int, char) * x = new(42, '!');
+pair(int, char) * x = new(42, '!');
 \end{lstlisting}
 The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects. This function provides the type-safety of @new@ in \CC, without the need to specify the allocated type again, thanks to return-type inference.
 
-In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@.
-
-\TODO{Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).}
+In the call to @new@, @pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(pair(int, char) *, int, char)@.
 
 \subsection{Implementation}