Changes in / [278516c:026a0f5]


Ignore:
Location:
doc/generic_types
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • TabularUnified doc/generic_types/evaluation/Makefile

    r278516c r026a0f5  
    1 CC = gcc
    21CFA = cfa
    32DEPFLAGS = -MMD -MP
    … …  
    76endif
    87CXXFLAGS = $(CFLAGS) --std=c++14
    9 MAKEFILE_NAME = ${firstword ${MAKEFILE_LIST}}
    108
    11 .PHONY : all clean run-c run-cpp run-cfa run
     9.PHONY: all clean distclean run-c run-cpp run-cfa run
    1210
    13 all : c-bench cpp-bench cpp-vbench cfa-bench
     11all: c-bench cpp-bench cfa-bench cpp-vbench
    1412
    1513# rewrite object generation to auto-determine deps
    … …  
    1917
    2018c-%.o : c-%.c
     19c-%.o : c-%.c c-%.d
    2120        $(COMPILE.c) $(OUTPUT_OPTION) -c $<
    2221
    2322cpp-%.o : cpp-%.cpp
     23cpp-%.o : cpp-%.cpp cpp-%.d
    2424        $(COMPILE.cpp) $(OUTPUT_OPTION) -c $<
    2525
    2626cfa-%.o : cfa-%.c
     27cfa-%.o : cfa-%.c cfa-%.d
    2728        $(COMPILE.cfa) $(OUTPUT_OPTION) -c $<
    2829
    29 COBJS = c-stack.o c-pair.o c-print.o c-bench.o
    30 CPPOBJS = cpp-bench.o
    31 CPPVOBJS = cpp-vstack.o cpp-vbench.o
    32 CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o cfa-bench.o
     30COBJS = c-stack.o c-pair.o c-print.o
     31CPPOBJS =
     32CPPVOBJS = cpp-vstack.o
     33CFAOBJS = cfa-stack.o cfa-pair.o cfa-print.o
    3334
    34 ${COBJS} ${CPPOBJS} ${CPPVOBJS} ${CFAOBJS} : ${MAKEFILE_NAME}
     35CFILES = c-bench.c bench.h $(COBJS:.o=.h) $(COBJS:.o=.c)
     36CPPFILES = cpp-bench.cpp bench.hpp cpp-stack.hpp cpp-pair.hpp cpp-print.hpp
     37CPPVFILES = cpp-vbench.cpp bench.hpp object.hpp $(CPPVOBJS:.o=.hpp) $(CPPVOBJS:.o=.cpp) cpp-vprint.hpp
     38CFAFILES = cfa-bench.c bench.h $(CFAOBJS:.o=.h) $(CFAOBJS:.o=.c)
    3539
    36 CFILES = bench.h $(patsubst c-bench.h,,$(COBJS:.o=.h)) $(COBJS:.o=.c)
    37 CPPFILES = bench.hpp cpp-stack.hpp cpp-pair.hpp cpp-print.hpp $(CPPOBJS:.o=.cpp)
    38 CPPVFILES = bench.hpp object.hpp cpp-vprint.hpp $(patsubst cpp-vbench.hpp,,$(CPPVOBJS:.o=.hpp)) $(CPPVOBJS:.o=.cpp)
    39 CFAFILES = bench.h $(patsubst cfa-bench.h,,$(CFAOBJS:.o=.h)) $(CFAOBJS:.o=.c)
     40c-bench: c-bench.c c-bench.d $(COBJS)
     41        $(COMPILE.c) -o $@ $< $(COBJS) $(LDFLAGS)
    4042
    41 c-bench : $(COBJS) c-bench.o
    42         $(COMPILE.c) $(LDFLAGS) $^ -o $@
     43cpp-bench: cpp-bench.cpp cpp-bench.d $(CPPOBJS)
     44        $(COMPILE.cpp) -o $@ $< $(CPPOBJS) $(LDFLAGS)
    4345
    44 cpp-bench : $(CPPOBJS) cpp-bench.o
    45         $(COMPILE.cpp) $(LDFLAGS) $^ -o $@
     46cpp-vbench: cpp-vbench.cpp cpp-vbench.d $(CPPVOBJS)
     47        $(COMPILE.cpp) -o $@ $< $(CPPVOBJS) $(LDFLAGS)
    4648
    47 cpp-vbench : $(CPPVOBJS) cpp-vbench.o
    48         $(COMPILE.cpp) $(LDFLAGS) $^ -o $@
     49cfa-bench: cfa-bench.c cfa-bench.d $(CFAOBJS)
     50        $(COMPILE.cfa) -o $@ $< $(CFAOBJS) $(LDFLAGS)
    4951
    50 cfa-bench : $(CFAOBJS) cfa-bench.o
    51         $(COMPILE.cfa) $(LDFLAGS) $^ -o $@
     52clean:
     53        -rm $(COBJS) c-bench
     54        -rm $(CPPOBJS) cpp-bench
     55        -rm $(CPPVOBJS) cpp-vbench
     56        -rm $(CFAOBJS) cfa-bench
     57
     58distclean: clean
     59        -rm $(COBJS:.o=.d) c-bench.d
     60        -rm $(CPPOBJS:.o=.d) cpp-bench.d
     61        -rm $(CPPVOBJS:.o=.d) cpp-vbench.d
     62        -rm $(CFAOBJS:.o=.d) cfa-bench.d
     63
     64run-c: c-bench
     65        @echo
     66        @echo '## C ##'
     67        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./c-bench
     68        @printf 'source_size:\t%8d lines\n' `cat $(CFILES) | wc -l`
     69        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFILES) | fgrep '/***/' -c`
     70        @printf 'binary_size:\t%8d bytes\n' `stat -c %s c-bench`
     71
     72run-cfa: cfa-bench
     73        @echo
     74        @echo '## Cforall ##'
     75        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cfa-bench
     76        @printf 'source_size:\t%8d lines\n' `cat $(CFAFILES) | wc -l`
     77        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFAFILES) | fgrep '/***/' -c`
     78        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cfa-bench`
     79
     80run-cpp: cpp-bench
     81        @echo
     82        @echo '## C++ ##'
     83        @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./cpp-bench
     84        @printf 'source_size:\t%8d lines\n' `cat $(CPPFILES) | wc -l`
     85        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPFILES) | fgrep '/***/' -c`
     86        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-bench`
     87
     88run-cppv: cpp-vbench
     89        @echo
     90        @echo '## C++obj ##'
     91        @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./cpp-vbench
     92        @printf 'source_size:\t%8d lines\n' `cat $(CPPVFILES) | wc -l`
     93        @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPVFILES) | fgrep '/***/' -c`
     94        @printf 'binary_size:\t%8d bytes\n' `stat -c %s cpp-vbench`
     95
     96run: run-c run-cfa run-cpp run-cppv
     97
     98# so make doesn't fail without dependency files
     99%.d: ;
     100
     101# so make won't delete dependency files
     102.PRECIOUS: %.d
    52103
    53104# include dependency files
    54 -include $(COBJS:.o=.d)
    55 -include $(CPPOBJS:.o=.d)
    56 -include $(CPPVOBJS:.o=.d)
    57 -include $(CFAOBJS:.o=.d)
    58 
    59 clean :
    60         rm -f $(COBJS) $(COBJS:.o=.d) c-bench
    61         rm -f $(CPPOBJS) $(CPPOBJS:.o=.d) cpp-bench
    62         rm -f $(CPPVOBJS) $(CPPVOBJS:.o=.d) cpp-vbench
    63         rm -f $(CFAOBJS) $(CFAOBJS:.o=.d) cfa-bench
    64 
    65 run-c : c-bench
    66         @echo
    67         @echo '## C ##'
    68         @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./$<
    69         @printf 'source_size:\t%8d lines\n' `cat $(CFILES) | wc -l`
    70         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFILES) | fgrep '/***/' -c`
    71         @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    72 
    73 run-cpp : cpp-bench
    74         @echo
    75         @echo '## C++ ##'
    76         @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./$<
    77         @printf 'source_size:\t%8d lines\n' `cat $(CPPFILES) | wc -l`
    78         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPFILES) | fgrep '/***/' -c`
    79         @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    80 
    81 run-cppv : cpp-vbench
    82         @echo
    83         @echo '## C++obj ##'
    84         @/usr/bin/time -f 'max_memory:\t%M kilobytes' ./$<
    85         @printf 'source_size:\t%8d lines\n' `cat $(CPPVFILES) | wc -l`
    86         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CPPVFILES) | fgrep '/***/' -c`
    87         @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    88 
    89 run-cfa : cfa-bench
    90         @echo
    91         @echo '## Cforall ##'
    92         @/usr/bin/time -f 'max_memory:\t %M kilobytes' ./$<
    93         @printf 'source_size:\t%8d lines\n' `cat $(CFAFILES) | wc -l`
    94         @printf 'redundant_type_annotations:%8d lines\n' `cat $(CFAFILES) | fgrep '/***/' -c`
    95         @printf 'binary_size:\t%8d bytes\n' `stat -c %s $<`
    96 
    97 run : run-c run-cfa run-cpp run-cppv
     105-include: $(COBJS:.o=.d)
     106-include: $(CPPOBJS:.o=.d)
     107-include: $(CFAOBJS:.o=.d)
     108-include: c-bench.d
     109-include: cpp-bench.d
     110-include: cfa-bench.d

  • TabularUnified doc/generic_types/evaluation/c-bench.c

    r278516c r026a0f5  
    3939
    4040int main(int argc, char** argv) {
    41         FILE * out = fopen("/dev/null", "w");
     41        FILE * out = fopen("c-out.txt", "w");
    4242        int maxi = 0, vali = 42;
    4343        struct stack si = new_stack(), ti;

  • TabularUnified doc/generic_types/evaluation/c-stack.c

    r278516c r026a0f5  
    1111void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
    1212        struct stack_node** crnt = &s->head;
    13         for ( struct stack_node* next = t->head; next; next = next->next ) {
     13        struct stack_node* next = t->head;
     14        while ( next ) {
    1415                *crnt = malloc(sizeof(struct stack_node)); /***/
    1516                **crnt = (struct stack_node){ copy(next->value) }; /***/
    1617                crnt = &(*crnt)->next;
     18                next = next->next;
    1719        }
    1820        *crnt = 0;
    … …  
    2022
    2123void clear_stack(struct stack* s, void (*free_el)(void*)) {
    22     for ( struct stack_node* next = s->head; next; ) {
     24        struct stack_node* next = s->head;
     25        while ( next ) {
    2326                struct stack_node* crnt = next;
    2427                next = crnt->next;

  • TabularUnified doc/generic_types/evaluation/cfa-bench.c

    r278516c r026a0f5  
    66
    77int main( int argc, char *argv[] ) {
    8         FILE * out = fopen( "/dev/null", "w" );
     8        FILE * out = fopen( "cfa-out.txt", "w" );
    99        int maxi = 0, vali = 42;
    1010        stack(int) si, ti;

  • TabularUnified doc/generic_types/evaluation/cfa-stack.c

    r278516c r026a0f5  
    1111forall(otype T) void ?{}(stack(T)* s, stack(T) t) {
    1212        stack_node(T)** crnt = &s->head;
    13         for ( stack_node(T)* next = t.head; next; next = next->next ) {
     13        stack_node(T)* next = t.head;
     14        while ( next ) {
    1415                *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/
    1516                stack_node(T)* acrnt = *crnt;
    1617                crnt = &acrnt->next;
     18                next = next->next;
    1719        }
    1820        *crnt = 0;
    … …  
    4446
    4547forall(otype T) void clear(stack(T)* s) {
    46     for ( stack_node(T)* next = s->head; next; ) {
     48        stack_node(T)* next = s->head;
     49        while ( next ) {
    4750                stack_node(T)* crnt = next;
    4851                next = crnt->next;

  • TabularUnified doc/generic_types/evaluation/cpp-bench.cpp

    r278516c r026a0f5  
    77
    88int main(int argc, char** argv) {
    9         std::ofstream out{"/dev/null"};
     9        std::ofstream out{"cpp-out.txt"};
    1010        int maxi = 0, vali = 42;
    1111        stack<int> si, ti;

  • TabularUnified doc/generic_types/evaluation/cpp-stack.hpp

    r278516c r026a0f5  
    1313        void copy(const stack<T>& o) {
    1414                node** crnt = &head;
    15                 for ( node* next = o.head; next; next = next->next ) {
     15                node* next = o.head;
     16                while ( next ) {
    1617                        *crnt = new node{ next->value }; /***/
    1718                        crnt = &(*crnt)->next;
     19                        next = next->next;
    1820                }
    1921                *crnt = nullptr;
    … …  
    2123public:
    2224        void clear() {
    23             for ( node* next = head; next; ) {
     25                node* next = head;
     26                while ( next ) {
    2427                        node* crnt = next;
    2528                        next = crnt->next;

  • TabularUnified doc/generic_types/evaluation/cpp-vbench.cpp

    r278516c r026a0f5  
    77
    88int main(int argc, char** argv) {
    9         std::ofstream out{"/dev/null"};
     9        std::ofstream out{"cpp-vout.txt"};
    1010        integer maxi{ 0 }, vali{ 42 };
    1111        stack si, ti;

  • TabularUnified doc/generic_types/evaluation/cpp-vstack.cpp

    r278516c r026a0f5  
    66void stack::copy(const stack& o) {
    77        node** crnt = &head;
    8         for ( node* next = o.head; next; next = next->next ) {
     8        node* next = o.head;
     9        while ( next ) {
    910                *crnt = new node{ *next->value };
    1011                crnt = &(*crnt)->next;
     12                next = next->next;
    1113        }
    1214        *crnt = nullptr;
    … …  
    3335
    3436void stack::clear() {
    35     for ( node* next = head; next; ) {
     37        node* next = head;
     38        while ( next ) {
    3639                node* crnt = next;
    3740                next = crnt->next;

  • TabularUnified doc/generic_types/generic_types.tex

    r278516c r026a0f5  
    232232int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
    233233                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
    234 double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ };
     234double key = 5.0, vals[10] = { /* 10 floating-point values */ };
    235235double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    236236\end{lstlisting}
    … …  
    354354One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
    355355Broadly speaking, there are three approaches to implement abstract data-structures in C.
    356 One approach is to write bespoke data-structures for each context in which they are needed.
     356One approach is to write bespoke data structures for each context in which they are needed.
    357357While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
    358358A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@; an approach which does allow reuse of code for common functionality.
    … …  
    542542\end{lstlisting}
    543543where the tuple variable-name serves the same purpose as the parameter name(s).
    544 Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C.
     544Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown.
    545545
    546546One way to access the tuple-variable components is with assignment or composition:
    … …  
    552552\begin{lstlisting}
    553553[int, int] * p = &qr;                                           $\C{// tuple pointer}$
    554 int rem = qr`.1`;                                                       $\C{// access remainder}$
    555 int quo = div( 13, 5 )`.0`;                                     $\C{// access quotient}$
    556 p`->0` = 5;                                                                     $\C{// change quotient}$
    557 bar( qr`.1`, qr );                                                      $\C{// pass remainder and quotient/remainder}$
    558 rem = [42, div( 13, 5 )]`.0.1`;                         $\C{// access 2nd component of 1st component of tuple expression}$
     554int rem = qr.1;                                                         $\C{// access remainder}$
     555int quo = div( 13, 5 ).0;                                       $\C{// access quotient}$
     556p->0 = 5;                                                                       $\C{// change quotient}$
     557bar( qr.1, qr );                                                        $\C{// pass remainder and quotient/remainder}$
     558rem = [42, div( 13, 5 )].0.1;                           $\C{// access 2nd component of 1st component of tuple expression}$
    559559\end{lstlisting}
    560560
    … …  
    616616This semantics means mass assignment differs from C cascading assignment (\eg @a = b = c@) in that conversions are applied in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
    617617For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@;
    618 whereas, C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
     618whereas C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
    619619Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C.
    620620This example shows mass, multiple, and cascading assignment used in one expression:
    … …  
    742742\end{lstlisting}
    743743Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
    744 This relaxation is possible by extending the thunk scheme described by~\citet{Bilson03}.
     744This relaxation is possible by extending the thunk scheme described by \citet{Bilson03}.
    745745Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
    746746\begin{lstlisting}
    … …  
    748748\end{lstlisting}
    749749so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
    750 These thunks take advantage of GCC C nested-functions to produce closures that have the usual function-pointer signature.
     750These thunks take advantage of GCC C nested-functions to produce closures that have the usual function pointer signature.
    751751
    752752
    … …  
    829829\subsection{Implementation}
    830830
    831 Tuples are implemented in the \CFA translator via a transformation into \emph{generic types}.
     831Tuples are implemented in the \CFA translator via a transformation into generic types.
    832832For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated, \eg:
    833833\begin{lstlisting}
    … …  
    10861086Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    10871087
    1088 There is ongoing work on a wide range of \CFA feature extensions, including reference types, arrays with size, exceptions, concurrent primitives and modules.
     1088There is ongoing work on a wide range of \CFA feature extensions, including reference types, exceptions, concurrent primitives and modules.
    10891089(While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.)
    10901090In addition, there are interesting future directions for the polymorphism design.
    … …  
    10921092\CFA polymorphic functions use dynamic virtual-dispatch;
    10931093the runtime overhead of this approach is low, but not as low as inlining, and it may be beneficial to provide a mechanism for performance-sensitive code.
    1094 Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types (\CC template specialization).
     1094Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template-specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function-definitions to instantiate a specialized version for some set of types.
    10951095These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code-bloat.
    10961096In general, we believe separate compilation, producing smaller code, works well with loaded hardware-caches, which may offset the benefit of larger inlined-code.
    … …  
    11171117Throughout, @/***/@ designates a counted redundant type annotation.
    11181118
    1119 \smallskip\noindent
     1119\medskip\noindent
    11201120\CFA
    11211121\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
Note: See TracChangeset for help on using the changeset viewer.