source: doc/theses/aaron_moss_PhD/phd/generic-types.tex @ 4075228

\chapter{Generic Types}
\label{generic-chap}

A significant shortcoming in standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms. 
Broadly speaking, there are three approaches to implement abstract data structures in C. 
One approach is to write bespoke data structures for each context in which they are needed. 
While 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. 
A 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. 
However, 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. 
A 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. 
Furthermore, writing and using preprocessor macros is unnatural and inflexible.
Figure~\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.

\begin{figure}
        \begin{cfa}
                struct int_list { int value; struct int_list* next; };

                void int_list_insert( struct int_list** ls, int x ) {
                        struct int_list* node = malloc(sizeof(struct int_list));
                        node->value = x; node->next = *ls;
                        *ls = node;
                }

                int int_list_head( const struct int_list* ls ) { return ls->value; }

                $\C[\textwidth]{// all code must be duplicated for every generic instantiation}$

                struct string_list { const char* value; struct string_list* next; };

                void string_list_insert( struct string_list** ls, const char* x ) {
                        struct string_list* node = malloc(sizeof(struct string_list));
                        node->value = x; node->next = *ls;
                        *ls = node;
                }

                const char* string_list_head( const struct string_list* ls )
                        { return ls->value; }

                $\C[\textwidth]{// use is efficient and idiomatic}$

                int main() {
                        struct int_list* il = NULL;
                        int_list_insert( &il, 42 );
                        printf("%d\n", int_list_head(il));
                        
                        struct string_list* sl = NULL;
                        string_list_insert( &sl, "hello" );
                        printf("%s\n", string_list_head(sl) );
                }
        \end{cfa}

        \caption{Bespoke code for linked list implementation.} \label{bespoke-generic-fig}
\end{figure}

\begin{figure}
        \begin{cfa}
                // single code implementation

                struct list { void* value; struct list* next; };

                $\C[\textwidth]{// internal memory management requires helper functions}$

                void list_insert( struct list** ls, void* x, void* (*copy)(void*) ) {
                        struct list* node = malloc(sizeof(struct list));
                        node->value = copy(x); node->next = *ls;
                        *ls = node;
                }

                void* list_head( const struct list* ls ) { return ls->value; }

                $\C[\textwidth]{// helpers duplicated per type}$

                void* int_copy(void* x) {
                        int* n = malloc(sizeof(int));
                        *n = *(int*)x;
                        return n;
                }

                void* string_copy(void* x) { return strdup((const char*)x); }

                int main() {
                        struct list* il = NULL;
                        int i = 42;
                        list_insert( &il, &i, int_copy );
                        printf("%d\n", *(int*)list_head(il));  $\C[2in]{// unsafe type cast}$
                        
                        struct list* sl = NULL;
                        list_insert( &sl, "hello", string_copy );
                        printf("%s\n", (char*)list_head(sl) );  $\C[2in]{// unsafe type cast}$
                }
        \end{cfa}

        \caption{\lstinline{void*}-polymorphic code for linked list implementation.} \label{void-generic-fig}
\end{figure}

\begin{figure}
        \begin{cfa}
                $\C[\textwidth]{// code is nested in macros}$

                #define list(N) N ## _list

                #define list_insert(N) N ## _list_insert

                #define list_head(N) N ## _list_head

                #define define_list(N, T) $\C[0.25in]{ \textbackslash }$
                        struct list(N) { T value; struct list(N)* next; }; $\C[0.25in]{ \textbackslash }$
                        $\C[0.25in]{ \textbackslash }$
                        void list_insert(N)( struct list(N)** ls, T x ) { $\C[0.25in]{ \textbackslash }$
                                struct list(N)* node = malloc(sizeof(struct list(N))); $\C[0.25in]{ \textbackslash }$
                                node->value = x; node->next = *ls; $\C[0.25in]{ \textbackslash }$
                                *ls = node; $\C[0.25in]{ \textbackslash }$
                        } $\C[0.25in]{ \textbackslash }$
                        $\C[0.25in]{ \textbackslash }$
                        T list_head(N)( const struct list(N)* ls ) { return ls->value; }

                define_list(int, int); $\C[3in]{// defines int\_list}$
                define_list(string, const char*); $\C[3in]{// defines string\_list}$

                $\C[\textwidth]{// use is efficient, but syntactically idiosyncratic}$

                int main() {
                        struct list(int)* il = NULL; $\C[3in]{// does not match compiler-visible name}$
                        list_insert(int)( &il, 42 );
                        printf("%d\n", list_head(int)(il));
                        
                        struct list(string)* sl = NULL;
                        list_insert(string)( &sl, "hello" );
                        printf("%s\n", list_head(string)(sl) );
                }
        \end{cfa}

        \caption{Macros for linked list implementation.} \label{macro-generic-fig}
\end{figure}


% discuss at length design alternatives to support polymorphism with separate compilation, C backward compatibility, and support for overriding pre-defined functions

% TODO discuss layout function algorithm, application to separate compilation
% 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)

% TODO pull benchmarks from Moss et al.