Changeset 4075228


Ignore:
Timestamp:
Sep 25, 2018, 1:39:34 PM (6 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum
Children:
48b7085e
Parents:
91a950c
Message:

Start generics chapter of thesis, add code examples of C polymorphic types

Location:
doc/theses/aaron_moss_PhD/phd
Files:
4 added
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/aaron_moss_PhD/phd/.gitignore

    r91a950c r4075228  
    11templates/
     2code/a.out
    23thesis.pdf
    34thesis.aux

  • doc/theses/aaron_moss_PhD/phd/cfa-macros.tex

    r91a950c r4075228  
    4343tabsize=5,                                                                                              % N space tabbing
    4444xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
    45 %mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
    4645escapechar=\$,                                                                                  % LaTeX escape in CFA code
    4746keepspaces=true,                                                                                %

  • doc/theses/aaron_moss_PhD/phd/generic-types.tex

    r91a950c r4075228  
    22\label{generic-chap}
    33
    4 Talk about generic types. Pull from Moss~\etal\cite{Moss18}.
     4A significant shortcoming in standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms.
     5Broadly speaking, there are three approaches to implement abstract data structures in C.
     6One approach is to write bespoke data structures for each context in which they are needed.
     7While 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.
     8A second approach is to use !void*!-based polymorphism, \eg{} the C standard library functions !bsearch! and !qsort!, which allow for the reuse of common functionality.
     9However, basing all polymorphism on !void*! eliminates the type checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is otherwise not needed.
     10A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type checked, but errors in such code may be difficult to locate and debug.
     11Furthermore, writing and using preprocessor macros is unnatural and inflexible.
     12Figure~\ref{bespoke-generic-fig} demonstrates the bespoke approach for a simple linked list and !head! operation, while Figure~\ref{void-generic-fig} and Figure~\ref{macro-generic-fig} show the same example using !void*!- and !#define!-based polymorphism, respectively.
     13
     14\begin{figure}
     15        \begin{cfa}
     16                struct int_list { int value; struct int_list* next; };
     17
     18                void int_list_insert( struct int_list** ls, int x ) {
     19                        struct int_list* node = malloc(sizeof(struct int_list));
     20                        node->value = x; node->next = *ls;
     21                        *ls = node;
     22                }
     23
     24                int int_list_head( const struct int_list* ls ) { return ls->value; }
     25
     26                $\C[\textwidth]{// all code must be duplicated for every generic instantiation}$
     27
     28                struct string_list { const char* value; struct string_list* next; };
     29
     30                void string_list_insert( struct string_list** ls, const char* x ) {
     31                        struct string_list* node = malloc(sizeof(struct string_list));
     32                        node->value = x; node->next = *ls;
     33                        *ls = node;
     34                }
     35
     36                const char* string_list_head( const struct string_list* ls )
     37                        { return ls->value; }
     38
     39                $\C[\textwidth]{// use is efficient and idiomatic}$
     40
     41                int main() {
     42                        struct int_list* il = NULL;
     43                        int_list_insert( &il, 42 );
     44                        printf("%d\n", int_list_head(il));
     45                       
     46                        struct string_list* sl = NULL;
     47                        string_list_insert( &sl, "hello" );
     48                        printf("%s\n", string_list_head(sl) );
     49                }
     50        \end{cfa}
     51
     52        \caption{Bespoke code for linked list implementation.} \label{bespoke-generic-fig}
     53\end{figure}
     54
     55\begin{figure}
     56        \begin{cfa}
     57                // single code implementation
     58
     59                struct list { void* value; struct list* next; };
     60
     61                $\C[\textwidth]{// internal memory management requires helper functions}$
     62
     63                void list_insert( struct list** ls, void* x, void* (*copy)(void*) ) {
     64                        struct list* node = malloc(sizeof(struct list));
     65                        node->value = copy(x); node->next = *ls;
     66                        *ls = node;
     67                }
     68
     69                void* list_head( const struct list* ls ) { return ls->value; }
     70
     71                $\C[\textwidth]{// helpers duplicated per type}$
     72
     73                void* int_copy(void* x) {
     74                        int* n = malloc(sizeof(int));
     75                        *n = *(int*)x;
     76                        return n;
     77                }
     78
     79                void* string_copy(void* x) { return strdup((const char*)x); }
     80
     81                int main() {
     82                        struct list* il = NULL;
     83                        int i = 42;
     84                        list_insert( &il, &i, int_copy );
     85                        printf("%d\n", *(int*)list_head(il));  $\C[2in]{// unsafe type cast}$
     86                       
     87                        struct list* sl = NULL;
     88                        list_insert( &sl, "hello", string_copy );
     89                        printf("%s\n", (char*)list_head(sl) );  $\C[2in]{// unsafe type cast}$
     90                }
     91        \end{cfa}
     92
     93        \caption{\lstinline{void*}-polymorphic code for linked list implementation.} \label{void-generic-fig}
     94\end{figure}
     95
     96\begin{figure}
     97        \begin{cfa}
     98                $\C[\textwidth]{// code is nested in macros}$
     99
     100                #define list(N) N ## _list
     101
     102                #define list_insert(N) N ## _list_insert
     103
     104                #define list_head(N) N ## _list_head
     105
     106                #define define_list(N, T) $\C[0.25in]{ \textbackslash }$
     107                        struct list(N) { T value; struct list(N)* next; }; $\C[0.25in]{ \textbackslash }$
     108                        $\C[0.25in]{ \textbackslash }$
     109                        void list_insert(N)( struct list(N)** ls, T x ) { $\C[0.25in]{ \textbackslash }$
     110                                struct list(N)* node = malloc(sizeof(struct list(N))); $\C[0.25in]{ \textbackslash }$
     111                                node->value = x; node->next = *ls; $\C[0.25in]{ \textbackslash }$
     112                                *ls = node; $\C[0.25in]{ \textbackslash }$
     113                        } $\C[0.25in]{ \textbackslash }$
     114                        $\C[0.25in]{ \textbackslash }$
     115                        T list_head(N)( const struct list(N)* ls ) { return ls->value; }
     116
     117                define_list(int, int); $\C[3in]{// defines int\_list}$
     118                define_list(string, const char*); $\C[3in]{// defines string\_list}$
     119
     120                $\C[\textwidth]{// use is efficient, but syntactically idiosyncratic}$
     121
     122                int main() {
     123                        struct list(int)* il = NULL; $\C[3in]{// does not match compiler-visible name}$
     124                        list_insert(int)( &il, 42 );
     125                        printf("%d\n", list_head(int)(il));
     126                       
     127                        struct list(string)* sl = NULL;
     128                        list_insert(string)( &sl, "hello" );
     129                        printf("%s\n", list_head(string)(sl) );
     130                }
     131        \end{cfa}
     132
     133        \caption{Macros for linked list implementation.} \label{macro-generic-fig}
     134\end{figure}
     135
     136
     137% discuss at length design alternatives to support polymorphism with separate compilation, C backward compatibility, and support for overriding pre-defined functions
    5138
    6139% TODO discuss layout function algorithm, application to separate compilation
    7 % TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation
    8 
    9 % TODO mention impetus for zero_t design
    10 
    11 % TODO mention use in tuple-type implementation
     140% TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation (actually no, you need to be able to see the type for it to be sized)
    12141
    13142% TODO pull benchmarks from Moss et al.
Note: See TracChangeset for help on using the changeset viewer.