Index: doc/theses/aaron_moss_PhD/phd/.gitignore =================================================================== --- doc/theses/aaron_moss_PhD/phd/.gitignore (revision 91a950c7292013a3025a751cd505c386ddfb031b) +++ doc/theses/aaron_moss_PhD/phd/.gitignore (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -1,3 +1,4 @@ templates/ +code/a.out thesis.pdf thesis.aux Index: doc/theses/aaron_moss_PhD/phd/cfa-macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision 91a950c7292013a3025a751cd505c386ddfb031b) +++ doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -43,5 +43,4 @@ tabsize=5, % N space tabbing xleftmargin=\parindentlnth, % indent code to paragraph indentation -%mathescape=true, % LaTeX math escape in CFA code $...$ escapechar=\$, % LaTeX escape in CFA code keepspaces=true, % Index: doc/theses/aaron_moss_PhD/phd/code/bespoke-generic.c =================================================================== --- doc/theses/aaron_moss_PhD/phd/code/bespoke-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) +++ doc/theses/aaron_moss_PhD/phd/code/bespoke-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -0,0 +1,37 @@ +#include +#include + +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; } + +// 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; } + +// 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) ); +} Index: doc/theses/aaron_moss_PhD/phd/code/macro-generic.c =================================================================== --- doc/theses/aaron_moss_PhD/phd/code/macro-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) +++ doc/theses/aaron_moss_PhD/phd/code/macro-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -0,0 +1,36 @@ +#include +#include + +// 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) \ + struct list(N) { T value; struct list(N)* next; }; \ + \ + void list_insert(N)( struct list(N)** ls, T x ) { \ + struct list(N)* node = malloc(sizeof(struct list(N))); \ + node->value = x; node->next = *ls; \ + *ls = node; \ + } \ + \ + T list_head(N)( const struct list(N)* ls ) { return ls->value; } + +define_list(int, int); // defines int_list +define_list(string, const char*); // defines string_list + +// use is efficient, but syntactically idiosyncratic + +int main() { + struct list(int)* il = NULL; + 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) ); +} Index: doc/theses/aaron_moss_PhD/phd/code/void-generic.c =================================================================== --- doc/theses/aaron_moss_PhD/phd/code/void-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) +++ doc/theses/aaron_moss_PhD/phd/code/void-generic.c (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -0,0 +1,38 @@ +#include +#include +#include + +// single code implementation + +struct list { void* value; struct list* next; }; + +// 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; } + +// 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)); // unsafe type cast + + struct list* sl = NULL; + list_insert( &sl, "hello", string_copy ); + printf("%s\n", (char*)list_head(sl) ); +} Index: doc/theses/aaron_moss_PhD/phd/generic-types.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 91a950c7292013a3025a751cd505c386ddfb031b) +++ doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -2,12 +2,141 @@ \label{generic-chap} -Talk about generic types. Pull from Moss~\etal\cite{Moss18}. +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 - -% TODO mention impetus for zero_t design - -% TODO mention use in tuple-type implementation +% 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. Index: doc/theses/aaron_moss_PhD/phd/timeline.md =================================================================== --- doc/theses/aaron_moss_PhD/phd/timeline.md (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) +++ doc/theses/aaron_moss_PhD/phd/timeline.md (revision 4075228f1dad43acaa6f29142f46e66e9920b4f1) @@ -0,0 +1,31 @@ +# PhD Completion Deadlines # +* 30 Apr --- Deadline for June convocation +* 4-6 week display period +* +1 week committee approval paperwork + +## Relaxed Timeline ## +* 30 Apr --- Completed +* 2 Apr --- Defence +* 19 Feb --- Committee draft posted +* 12 Feb --- Committee approval paperwork +* 22 Jan --- First draft + +## Comfortable Timeline ## +* 30 Apr --- Completed +* 9 Apr --- Defence +* 5 Mar --- Committee draft posted +* 26 Feb --- Committee approval paperwork +* 12 Feb --- First draft + +## Strict Timeline ## +* 30 Apr --- Completed +* 12 Apr --- Defence +* 15 Mar --- Committee draft posted +* 8 Mar --- Committee approval paperwork +* 27 Feb --- First draft + +# Intermediate Targets # +* 22 Jan --- Run experiments and finish chapter drafts +* 1 Jan --- Draft ``Resolution'' chapter +* 20 Nov --- Draft ``Environment'' chapter +* 23 Oct --- Draft ``Generics'' chapter