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

aaron-thesisarm-ehcleanup-dtorsdeferred_resnenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexer
Last change on this file since 4075228 was 4075228, checked in by Aaron Moss <a3moss@…>, 4 years ago

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

  • Property mode set to 100644
File size: 5.5 KB
Line 
1\chapter{Generic Types}
2\label{generic-chap}
3
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
138
139% TODO discuss layout function algorithm, application to separate compilation
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)
141
142% TODO pull benchmarks from Moss et al.
Note: See TracBrowser for help on using the repository browser.