Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/bibliography/pl.bib (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -830,5 +830,5 @@ month = oct, type = {Diplomarbeit}, - note = {{\small\textsf{ftp://\-plg.uwaterloo.ca/\-pub/\-theses/\-KrischerThesis.ps.gz}}}, + note = {\href{https://plg.uwaterloo.ca/~usystem/theses/KrischerThesis.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-theses/\-KrischerThesis.pdf}}, } @@ -925,5 +925,5 @@ key = {Cforall}, author = {{\textsf{C}{$\mathbf{\forall}$} Features}}, - howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-~cforall/\-features}}, + howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-$\sim$cforall/\-features}}, optnote = {Accessed: 2018-01-01}, } @@ -1101,5 +1101,5 @@ month = oct, year = 2001, - note = {\href{http://plg.uwaterloo.ca/~cforall/cfa.ps}{http://\-plg.uwaterloo.ca/\-\char`\~cforall/\-cfa.ps}}, + note = {\href{http://plg.uwaterloo.ca/~cforall/cfa.ps}{http://\-plg.uwaterloo.ca/\-$\sim$cforall/\-cfa.ps}}, } @@ -1516,5 +1516,5 @@ month = dec, year = 2017, - note = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-~usystem/\-pub/\-uSystem/uC++.pdf}}, + note = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}}, } @@ -1809,5 +1809,5 @@ author = {Glen Ditchfield}, title = {Conversions for \textsf{C}$\mathbf{\forall}$}, - note = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-\textasciitilde cforall/\-Conversions/\-index.html}}, + note = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-$\sim$cforall/\-Conversions/\-index.html}}, month = {Nov}, year = {2002}, @@ -1877,5 +1877,5 @@ title = {CS343}, year = 2018, - howpublished= {\href{https://www.student.cs.uwaterloo.ca/~cs343}{https://\-www.student.cs.uwaterloo.ca/\-~cs343}}, + howpublished= {\href{https://www.student.cs.uwaterloo.ca/~cs343}{https://\-www.student.cs.uwaterloo.ca/\-$\sim$cs343}}, } @@ -4144,5 +4144,5 @@ month = sep, year = 2006, - note = {\textsf{http://cs.anu.edu.au/\-\char`\~Robin.Garner/\-mmtk-guide.pdf}}, + note = {\textsf{http://cs.anu.edu.au/\-$\sim$Robin.Garner/\-mmtk-guide.pdf}}, } @@ -4248,5 +4248,5 @@ month = sep, year = 1994, - note = {{\small\textsf{ftp://\-plg.uwaterloo.ca/\-pub/\-uSystem/\-uSystem.ps.gz}}}, + note = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uSystem.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/\-uSystem.pdf}}, } @@ -4790,5 +4790,5 @@ year = 1995, number = 31, - note = {{\small\textsf{http://\-www.cs.wustl.edu/\-\char`\~schmidt/\-PDF/\-IPC\_SAP-92.pdf}}}, + note = {{\small\textsf{http://\-www.cs.wustl.edu/\-$\sim$schmidt/\-PDF/\-IPC\_SAP-92.pdf}}}, } @@ -6132,5 +6132,5 @@ month = apr, type = {Diplomarbeit}, - note = {\href{ftp://plg.uwaterloo.ca/pub/theses/SchusterThesis.ps.gz}{ftp://\-plg.uwaterloo.ca/\-pub/\-theses/\-SchusterThesis.ps.gz}}, + note = {\href{https://plg.uwaterloo.ca/~usystem/theses/SchusterThesis.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-theses/\-SchusterThesis.pdf}}, } Index: doc/papers/concurrency/Makefile =================================================================== --- doc/papers/concurrency/Makefile (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/papers/concurrency/Makefile (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -4,7 +4,7 @@ Figures = figures Macros = ../AMA/AMA-stix/ama -TeXLIB = .:annex:../../LaTeXmacros:${Macros}:${Build}:../../bibliography: +TeXLIB = .:../../LaTeXmacros:${Macros}:${Build}: LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex +BibTeX = BIBINPUTS=annex:../../bibliography: && export BIBINPUTS && bibtex MAKEFLAGS = --no-print-directory # --silent Index: doc/papers/general/Makefile =================================================================== --- doc/papers/general/Makefile (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/papers/general/Makefile (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -4,7 +4,7 @@ Figures = figures Macros = ../AMA/AMA-stix/ama -TeXLIB = .:${Macros}:${Build}:../../bibliography: +TeXLIB = .:${Macros}:${Build}: LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex +BibTeX = BIBINPUTS=../../bibliography: && export BIBINPUTS && bibtex MAKEFLAGS = --no-print-directory # --silent Index: doc/theses/aaron_moss_PhD/phd/.gitignore =================================================================== --- doc/theses/aaron_moss_PhD/phd/.gitignore (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/.gitignore (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,3 +1,4 @@ templates/ +code/a.out thesis.pdf thesis.aux Index: doc/theses/aaron_moss_PhD/phd/Makefile =================================================================== --- doc/theses/aaron_moss_PhD/phd/Makefile (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/Makefile (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,8 +1,12 @@ BUILD = build BIBDIR = ../../../bibliography +EVALDIR = evaluation TEXLIB = .:${BUILD}:${BIBDIR}: -LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction= -output-directory=${BUILD} +# LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction=nonstopmode -halt-on-error -output-directory=${BUILD} +LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD} BIBTEX = BIBINPUTS=${TEXLIB} && export BIBINPUTS && bibtex + +VPATH = ${EVALDIR} BASE = thesis @@ -17,7 +21,12 @@ introduction \ background \ +generic-types \ type-environment \ resolution-heuristics \ conclusion \ +} + +GRAPHS = ${addsuffix .tex, \ +generic-timing \ } @@ -32,9 +41,11 @@ wc ${SOURCES} -${DOCUMENT} : ${SOURCES} ${BUILD} - ${LATEX} ${BASE} - ${LATEX} ${BASE} +${DOCUMENT} : ${BASE}.ps + ps2pdf ${BUILD}/$< -rebuild-refs : ${SOURCES} ${BIBFILE} ${BUILD} +${BASE}.ps : ${BASE}.dvi + dvips ${BUILD}/$< -o ${BUILD}/$@ + +${BASE}.dvi : Makefile ${SOURCES} ${GRAPHS} ${BIBFILE} ${BUILD} ${LATEX} ${BASE} ${BIBTEX} ${BUILD}/${BASE} @@ -42,4 +53,7 @@ ${LATEX} ${BASE} +${GRAPHS} : generic-timing.gp generic-timing.dat ${BUILD} + gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/generic-timing.gp + ${BUILD}: mkdir -p ${BUILD} Index: doc/theses/aaron_moss_PhD/phd/cfa-macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -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 cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/code/bespoke-generic.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -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/cfa-generic.cfa =================================================================== --- doc/theses/aaron_moss_PhD/phd/code/cfa-generic.cfa (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/code/cfa-generic.cfa (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -0,0 +1,27 @@ +#include +#include + +forall(otype T) struct list { T value; list(T)* next; }; + +// single polymorphic implementation of each function +// overloading reduces need for namespace prefixes + +forall(otype T) void insert( list(T)** ls, T x ) { + list(T)* node = alloc(); // type-inferring alloc + (*node){ x, *ls }; // concise constructor syntax + *ls = node; +} + +forall(otype T) T head( const list(T)* ls ) { return ls->value; } + +// use is clear and efficient + +int main() { + list(int)* il = 0; + insert( &il, 42 ); // inferred polymorphic T + printf("%d\n", head(il)); + + list(const char*)* sl = 0; + insert( &sl, "hello" ); + printf("%s\n", head(sl)); +} Index: doc/theses/aaron_moss_PhD/phd/code/macro-generic.c =================================================================== --- doc/theses/aaron_moss_PhD/phd/code/macro-generic.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/code/macro-generic.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -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 cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/code/void-generic.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -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/evaluation/generic-timing.dat =================================================================== --- doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -0,0 +1,10 @@ +"400 million repetitions" "C" "\\CFA{}" "\\CC{}" "\\CCV{}" +"push\nint" 2911 2034 1504 3246 +"copy\nint" 2953 1622 1526 3075 +"clear\nint" 1397 754 753 1452 +"pop\nint" 1446 1203 760 5016 +"push\npair" 3673 2297 955 6971 +"copy\npair" 6027 1183 998 7204 +"clear\npair" 2840 773 748 3511 +"pop\npair" 3025 5414 813 23867 + Index: doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp =================================================================== --- doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -0,0 +1,29 @@ +# set terminal pdfcairo linewidth 3 size 6,3 +# set output "timing.pdf" +set terminal pslatex size 6.25,2.125 color solid +set output BUILD."generic-timing.tex" + +set pointsize 2.0 +set grid linetype 0 +set style data histogram +set style histogram cluster gap 2 +set style fill solid border -1 +set offset -0.5,-0.35 +set boxwidth 0.8 + +set key top left reverse Left + +set style fill solid noborder +set linetype 1 lc rgb 'black' +set linetype 2 lc rgb 'red' +set linetype 3 lc rgb 'blue' +set linetype 4 lc rgb 'green' + +SCALE=1000 +set ylabel "seconds" +set yrange [0:10] + +set label "23.9" at 7.125,10.5 +set style fill pattern 4 border lt -1 +# set datafile separator "," +plot for [COL=2:5] 'evaluation/generic-timing.dat' using (column(COL)/SCALE):xticlabels(1) title columnheader Index: doc/theses/aaron_moss_PhD/phd/frontpgs.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/frontpgs.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/frontpgs.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -160,8 +160,8 @@ % L I S T O F F I G U R E S % ----------------------------- -% \addcontentsline{toc}{chapter}{List of Figures} -% \listoffigures -% \cleardoublepage -% \phantomsection % allows hyperref to link to the correct page +\addcontentsline{toc}{chapter}{List of Figures} +\listoffigures +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page % GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) Index: doc/theses/aaron_moss_PhD/phd/generic-types.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -2,12 +2,508 @@ \label{generic-chap} -Talk about generic types. Pull from Moss~\etal\cite{Moss18}. - -% 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 pull benchmarks from Moss et al. +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 with !insert! and !head! operations, 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 generic linked list implementation.} \label{macro-generic-fig} +\end{figure} + +\CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types. +Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18} and from which this chapter is closely based. +\CFA{} generic types integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backward compatibility with C in layout and support for separate compilation. +A generic type can be declared in \CFA{} by placing a !forall! specifier on a !struct! or !union! declaration, and instantiated using a parenthesized list of types after the generic name. +An example comparable to the C polymorphism examples in Figures~\ref{bespoke-generic-fig}, \ref{void-generic-fig}, and \ref{macro-generic-fig} can be seen in Figure~\ref{cfa-generic-fig} \TODO{test this code}. + +\begin{figure} + \begin{cfa} + forall(otype T) struct list { T value; list(T)* next; }; + + $\C[\textwidth]{// single polymorphic implementation of each function}$ + $\C[\textwidth]{// overloading reduces need for namespace prefixes}$ + + forall(otype T) void insert( list(T)** ls, T x ) { + list(T)* node = alloc(); $\C{// type-inferring alloc}$ + (*node){ x, *ls }; $\C{// concise constructor syntax}$ + *ls = node; + } + + forall(otype T) T head( const list(T)* ls ) { return ls->value; } + + $\C[\textwidth]{// use is clear and efficient}$ + + int main() { + list(int)* il = 0; + insert( &il, 42 ); $\C{// inferred polymorphic T}$ + printf("%d\n", head(il)); + + list(const char*)* sl = 0; + insert( &sl, "hello" ); + printf("%s\n", head(sl)); + } + \end{cfa} + + \caption{\CFA{} generic linked list implementation.} \label{cfa-generic-fig} +\end{figure} + +\section{Design} + +Though a number of languages have some implementation of generic types, backward compatibility with both C and existing \CFA{} polymorphism presented some unique design constraints for this project. +The guiding principle was to maintain an unsurprising language model for C programmers without compromising runtime efficiency. +A key insight for this design was that C already possesses a handful of built-in generic types (\emph{compound types} in the language of the standard\cit{}), notably pointer (!T*!) and array (!T[]!), and that user-definable generics should act similarly. + +\subsection{Related Work} + +One approach to the design of generic types is that taken by \CC{} templates\cite{C++}. +The template approach is closely related to the macro-expansion approach to C polymorphism demonstrated in Figure~\ref{macro-generic-fig}, but where the macro-expansion syntax has been given first-class language support. +Template expansion has the benefit of generating code with near-optimal runtime efficiency, as distinct optimizations can be applied for each instantiation of the template. +On the other hand, template expansion can also lead to significant code bloat, exponential in the worst case\cit{}, and the costs of increased instruction cache pressure at runtime and wasted developer time when compiling cannot be discounted. +The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms. +Because a \CC{} template is not actually code, but rather a sort of ``recipe'' to generate code, template code must be visible at its call site to be used. +Furthermore, \CC{} template code cannot be type-checked without instantiating it, a time consuming process with no hope of improvement until \CC{} concepts\cite{C++Concepts} are standardized in \CCtwenty{}. +C code, by contrast, only needs a !struct! or function declaration to call that function or use (by-pointer) values of that type, a desirable property to maintain for \CFA{}. + +Java\cite{Java8} has another prominent implementation for generic types, introduced in Java~5 and based on a significantly different approach than \CC{}. +The Java approach has much more in common with the !void*!-polymorphism shown in Figure~\ref{void-generic-fig}; since in Java nearly all data is stored by reference, the Java approach to polymorphic data is to store pointers to arbitrary data and insert type-checked implicit casts at compile-time. +This process of \emph{type erasure} has the benefit of allowing a single instantiation of polymorphic code, but relies heavily on Java's object model and garbage collector. +To use this model, a more C-like language such as \CFA{} would be required to dynamically allocate internal storage for variables, track their lifetime, and properly clean them up afterward. + +Cyclone\cite{Grossman06} is another language extending C, and also provides capabilities for polymorphic functions and existential types, similar to \CFA{}'s !forall! functions and generic types. +Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, which is tedious and error-prone compared to \CFA{}'s implicit assertion satisfaction. +Furthermore, Cyclone's polymorphic functions and types are restricted to abstraction over types with the same layout and calling convention as !void*!, \ie{} only pointer types and !int!. +In the \CFA{} terminology discussed in Section~\ref{generic-impl-sec}, all Cyclone polymorphism must be dtype-static. +While the Cyclone polymorphism design provides the efficiency benefits discussed in Section~\ref{dtype-static-sec} for dtype-static polymorphism, it is more restrictive than the more general model of \CFA{}. + +Many other languages include some form of generic types. +As a brief survey, ML\cite{ML} was the first language to support parameteric polymorphism, but unlike \CFA{} does not support the use of assertions and traits to constrain type arguments. +Haskell\cite{Haskell10} combines ML-style polymorphism with the notion of type classes, similar to \CFA{} traits, but requiring an explicit association with their implementing types, unlike \CFA{}. +Objective-C\cite{obj-c-book} is an extension to C which has had some industrial success; however, it did not support type-checked generics until recently\cite{xcode7}, and it's garbage-collected, message-passing object-oriented model is a radical departure from C. +Go\cite{Go}, and Rust\cite{Rust} are modern compiled languages with abstraction features similar to \CFA{} traits, \emph{interfaces} in Go and \emph{traits} in Rust. +Go has implicit interface implementation and uses a ``fat pointer'' construct to pass polymorphic objects to functions, similar in principle to \CFA{}'s implicit forall paramters. +Go does not, however, allow user code to define generic types, restricting Go programmers to the small set of generic types defined by the compiler. +Rust has powerful abstractions for generic programming, including explicit implemenation of traits and options for both separately-compiled virtual dispatch and template-instantiated static dispatch in functions. +On the other hand, the safety guarantees of Rust's \emph{lifetime} abstraction and borrow checker impose a distinctly idiosyncratic programming style and steep learning curve; \CFA{}, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source. + +\subsection{\CFA{} Generics} + +The generic types design in \CFA{} draws inspiration from both \CC{} and Java generics, capturing the better aspects of each. +Like \CC{} template types, generic !struct!s and !union!s in \CFA{} have macro-expanded storage layouts, but, like Java generics, \CFA{} generic types can be used with separately-compiled polymorphic functions without requiring either the type or function definition to be visible to the other. +The fact that the storage layout of any instantiation of a \CFA{} generic type is identical to that of the monomorphic type produced by simple macro replacement of the generic type parameters is important to provide consistent and predictable runtime performance, and to not impose any undue abstraction penalty on generic code. +As an example, consider the following generic type and function \TODO{test this}: + +\begin{cfa} +forall( otype R, otype S ) struct pair { R first; S second; }; + +pair(const char*, int) with_len( const char* s ) { + return (pair(const char*), int){ s, strlen(s) }; +} +\end{cfa} + +In this example, !with_len! is defined at the same scope as !pair!, but it could be called from any context that can see the definition of !pair! and a declaration of !with_len!. +If its return type was !pair(const char*, int)*!, callers of !with_len! would only need the declaration !forall(otype R, otype S) struct pair! to call it, in accordance with the usual C rules for opaque types. + +!with_len! is itself a monomorphic function, returning a type that is structurally identical to !struct { const char* first; int second; }!, and as such could be called from C given an appropriate redeclaration and demangling flags. +However, the definition of !with_len! depends on a polymorphic function call to the !pair! constructor, which only needs to be written once (in this case, implicitly by the compiler according to the usual \CFA{} constructor generation\cite{Moss18}) and can be re-used for a wide variety of !pair! instantiations. +Since the parameters to this polymorphic constructor call are all statically known, compiler inlining can eliminate any runtime overhead of this polymorphic call. + +\CFA{} deliberately does not support \CC{}-style partial specializations of generic types. +A particularly infamous example in the \CC{} standard library is !vector!, which is represented as a bitstring rather than the array representation of the other !vector! instantiations. +Complications from this inconsistency (chiefly the fact that a single bit is not addressable, unlike an array element) make the \CC{} !vector! unpleasant to use in generic contexts due to the break in its public interface. +Rather than attempting to plug leaks in the template specialization abstraction with a detailed method interface, \CFA{} takes the more principled position that two types with an unrelated data layout are in fact unrelated types, and should be handled with different code. +Of course, to the degree that distinct types are similar enough to share an interface, the \CFA{} !trait! system allows one to be defined, and objects of types implementing that !trait! to be operated on in the same polymorphic functions. + +Since \CFA{} polymorphic functions can operate over polymorphic generic types, functions over such types can be partially or completely specialized using the usual overload selection rules. +As an example, the !with_len! function above could be an optimization of the following more general function: + +\begin{cfa} +forall(otype T, otype I | { I len(T); }) +pair(T, I) with_len( T s ) { + return (pair(T,I)){ s, len(s) }; +} +\end{cfa} + +\CFA{} generic types also support the type constraints from !forall! functions. +For example, the following declaration of a sorted set type ensures that the set key implements equality and relational comparison: + +\begin{cfa} +forall(otype Key | { int ?==?(Key, Key); int ?first, b->first ); + return c ? c : cmp( a->second, b->second ); +} +\end{cfa} + +Since !pair(T*, T*)! is a concrete type, there are no implicit parameters passed to !lexcmp!; hence, the generated code is identical to a function written in standard C using !void*!, yet the \CFA{} version is type-checked to ensure members of both pairs and arguments to the comparison function match in type. + +Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \emph{tag structures}. +Sometimes, information is only used for type checking and can be omitted at runtime. +In the example below, !scalar! is a dtype-static type; hence, all uses have a single structure definition containing !unsigned long! and can share the same implementations of common functions like !?+?!. +These implementations may even be separately compiled, unlike \CC{} template functions. +However, the \CFA{} type checker ensures matching types are used by all calls to !?+?!, preventing nonsensical computations like adding a length to a volume. + +\begin{cfa} +forall(dtype Unit) struct scalar { unsigned long value; }; +struct metres {}; +struct litres {}; + +forall(dtype U) scalar(U) ?+?(scalar(U) a, scalar(U) b) { + return (scalar(U)){ a.value + b.value }; +} + +scalar(metres) half_marathon = { 21098 }; +scalar(litres) pool = { 2500000 }; +scalar(metres) marathon = half_marathon + half_marathon; +`marathon + pool;` $\C[4in]{// compiler ERROR, mismatched types}$ +\end{cfa} + +\section{Performance Experiments} \label{generic-performance-sec} + +To validate the practicality of this generic type design I have conducted microbenchmark-based tests against a number of comparable code designs in C and \CC{}, first published in \cite{Moss18}. +Since all these languages are compiled with the same compiler backend and share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code. +A more illustrative comparison measures the costs of idiomatic usage of each language's features. +The code below shows the \CFA{} benchmark tests for a generic stack based on a singly-linked list; the test suite is equivalent for the other other languages. +The experiment uses element types !int! and !pair(short, char)! and pushes $N = 40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack. + +\begin{cfa} +int main() { + int max = 0, val = 42; + stack( int ) si, ti; + + REPEAT_TIMED( "push_int", N, push( si, val ); ) + TIMED( "copy_int", ti{ si }; ) + TIMED( "clear_int", clear( si ); ) + REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; ) + + pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' }; + stack( pair( short, char ) ) sp, tp; + + REPEAT_TIMED( "push_pair", N, push( sp, val ); ) + TIMED( "copy_pair", tp{ sp }; ) + TIMED( "clear_pair", clear( sp ); ) + REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); + if ( x > max ) max = x; ) +} +\end{cfa} + +The four versions of the benchmark implemented are C with !void*!-based polymorphism, \CFA{} with parameteric polymorphism, \CC{} with templates, and \CC{} using only class inheritance for polymorphism, denoted \CCV{}. +The \CCV{} variant illustrates an alternative object-oriented idiom where all objects inherit from a base !object! class, mimicking a Java-like interface; in particular, runtime checks are necessary to safely downcast objects. +The most notable difference among the implementations is the memory layout of generic types: \CFA{} and \CC{} inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV{} lack such capability and, instead, must store generic objects via pointers to separately allocated objects. +Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA{} and \CC{} provide type safety statically. + +Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark. +The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted. +All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}. +The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency. +I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation. + +\begin{figure} +\centering +\input{generic-timing} +\caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig} +\end{figure} + +\begin{table} +\caption{Properties of benchmark code} \label{generic-eval-table} +\centering +\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}} +\begin{tabular}{lrrrr} + & \CT{C} & \CT{\CFA} & \CT{\CC} & \CT{\CCV} \\ +maximum memory usage (MB) & 10\,001 & 2\,502 & 2\,503 & 11\,253 \\ +source code size (lines) & 201 & 191 & 125 & 294 \\ +redundant type annotations (lines) & 27 & 0 & 2 & 16 \\ +binary size (KB) & 14 & 257 & 14 & 37 \\ +\end{tabular} +\end{table} + +The C and \CCV{} variants are generally the slowest and have the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types in those languages; this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. +By contrast, the \CFA{} and \CC{} variants run in roughly equivalent time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie{} no separate compilation) and greater maturity of the \CC{} compiler contributing to its lead. +\CCV{} is slower than C largely due to the cost of runtime type checking of downcasts (implemented with !dynamic_cast!); the outlier for \CFA{}, pop !pair!, results from the complexity of the generated-C polymorphic code. +The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA{} could more easily perform these optimizations. +Finally, the binary size for \CFA{} is larger because of static linking with \CFA{} libraries. + +\CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort. +The line counts in Table~\ref{generic-eval-table} include implementations of !pair! and !stack! types for all four languages for purposes of direct comparison, although it should be noted that \CFA{} and \CC{} have prewritten data structures in their standard libraries that programmers would generally use instead. +Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA{} and \CC{} code to 39 and 42 lines, respectively. +The difference between the \CFA{} and \CC{} line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA{} library is similar in length to the \CC{} version. +On the other hand, due to the language shortcomings mentioned at the beginning of the chapter, C does not have a generic collections library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers. +\CCV{} does not use the \CC{} standard template library by construction, and, in fact, includes the definition of !object! and wrapper classes for !char!, !short!, and !int! in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library. +I justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose. + +Line count is a fairly rough measure of code complexity; another important factor is how much type information the programmer must specify manually, especially where that information is not type-checked. +Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs and is much less common in \CFA{} than C, with its manually specified function pointer arguments and format codes, or \CCV{}, with its extensive use of un-type-checked downcasts, \eg{} !object! to !integer! when popping a stack. +To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{generic-eval-table} counts the number of lines on which the known type of a variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a !sizeof!, !struct! literal, or !new! expression. +The \CC{} benchmark uses two redundant type annotations to create new stack nodes, whereas the C and \CCV{} benchmarks have several such annotations spread throughout their code. +The \CFA{} benchmark is able to eliminate \emph{all} redundant type annotations through use of the return-type polymorphic !alloc! function in the \CFA{} standard library. + +\section{Future Work} + +The generic types design presented here is already sufficiently expressive to implement a variety of useful library types. +However, some other features based on this design could further improve \CFA{}. + +The most pressing addition is the ability to have non-type generic parameters. +C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters, and allowing \CFA{} users the capability to build similar types is a requested feature. +More exotically, the ability to have these non-type parameters depend on dynamic runtime values rather than static compile-time constants opens up interesting opportunities for type-checking problematic code patterns. +For example, if a collection iterator was parameterized over the pointer to the collection it was drawn from, then a sufficiently powerful static analysis pass could ensure that that iterator was only used for that collection, eliminating one source of hard-to-find bugs. + +The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}. +One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables. +Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types. +Simulating field access can already be done more flexibly in \CFA{} by declaring a trait containing an accessor function to be called from polymorphic code, but these accessor functions impose some overhead both to write and call, and directly providing field access via an implicit offset parameter would be both more concise and more efficient. +Of course, there are language design trade-offs to such an approach, notably that providing the two similar features of field and function assertions would impose a burden of choice on programmers writing traits, with field assertions more efficient, but function assertions more general; given this open design question we have deferred a decision on field assertions until we have more experience using \CFA{}. +If field assertions are included in the language, a natural extension would be to provide a structural inheritance mechanism for every !struct! type that simply turns the list of !struct! fields into a list of field assertions, allowing monomorphic functions over that type to be generalized to polymorphic functions over other similar types with added or reordered fields. +\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- the layout function would need to be re-written, but nothing in the use of the offset arrays implies that the field offsets need be monotonically increasing. + +With respect to the broader \CFA{} polymorphism design, the experimental results in Section~\ref{generic-performance-sec} demonstrate that though the runtime impact of \CFA{}'s dynamic virtual dispatch is low, it is not as low as the static dispatch of \CC{} template inlining. +However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, we are considering more targeted mechanisms for performance-sensitive code. +Two promising approaches are are an !inline! annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing a different !inline! annotation on polymorphic function definitions to instantiate a specialized version of the function for some set of types. +These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat. +In general, the \CFA{} team believes that separate compilation works well with loaded hardware caches by producing smaller code, which may offset the benefit of larger inlined code. Index: doc/theses/aaron_moss_PhD/phd/introduction.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/introduction.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/introduction.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -5,6 +5,5 @@ \begin{table}[h] -\label{tiobe-table} -\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years} +\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years} \label{tiobe-table} \centering Index: doc/theses/aaron_moss_PhD/phd/macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/macros.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/macros.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -12,4 +12,5 @@ \newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name \newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name +\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj} % C++ virtual symbolic name \newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name @@ -19,4 +20,6 @@ \newcommand{\etal}{\textit{et~al.}} +\newcommand{\myset}[1]{\left\{#1\right\}} + \newcommand{\TODO}[1]{\textbf{TODO:} \textit{#1}} \newcommand{\cit}{\textsuperscript{[citation needed]}} Index: doc/theses/aaron_moss_PhD/phd/thesis.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/thesis.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/thesis.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -21,5 +21,8 @@ \usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments -\usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver +% \usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver +\usepackage{graphicx} + +\usepackage{footmisc} % for double refs to the same footnote % Hyperlinks make it very easy to navigate an electronic document. @@ -28,5 +31,6 @@ % Use the "hyperref" package % N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE -\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options +%\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options +\usepackage[pagebackref=false]{hyperref} % N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing. @@ -120,6 +124,6 @@ \input{background} \input{generic-types} +\input{resolution-heuristics} \input{type-environment} -\input{resolution-heuristics} \input{conclusion} Index: doc/theses/aaron_moss_PhD/phd/timeline.md =================================================================== --- doc/theses/aaron_moss_PhD/phd/timeline.md (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) +++ doc/theses/aaron_moss_PhD/phd/timeline.md (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -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 Index: doc/theses/aaron_moss_PhD/phd/type-environment.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/type-environment.tex (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/theses/aaron_moss_PhD/phd/type-environment.tex (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -2,3 +2,65 @@ \label{env-chap} -Talk about the type environment data structure. Pull from your presentation. +One key data structure for expression resolution is the \emph{type environment}. +As discussed in Chapter~\ref{resolution-chap}, being able to efficiently determine which type variables are bound to which concrete types or whether two type environments are compatible is a core requirement of the resolution algorithm. +Furthermore, expression resolution involves a search through many related possible solutions, so being able to re-use shared subsets of type environment data and to switch between environments quickly is desirable for performance. +In this chapter I discuss and empirically compare a number of type environment data structure variants, including some novel variations on the union-find\cit{} data structure introduced in this thesis. + +\section{Definitions} + +For purposes of this chapter, a \emph{type environment} $T$ is a set of \emph{type classes} $\myset{T_1, T_2, \cdots, T_{|T|}}$. +Each type class $T_i$ contains a set of \emph{type variables} $\myset{v_{i,1}, v_{i,2}, \cdots, v_{i,|T_i|}}$; note that the sets of variables contained in two distinct classes in the same environment must be disjoint. +Each individual type class $T_i$ may also be associated with a \emph{bound}, $b_i$; this bound contains the \emph{bound type} which the variables in the type class are replaced with, but also includes other information in \CFACC{}, including whether type conversions are permissible on the bound type and what sort of type variables are contained in the class (data types, function types, or variadic tuples). + +\begin{table} +\caption[Type environment operation summary]{Summary of type environment operations.} +\label{env-op-table} +\centering +\begin{tabular}{r@{\hskip 0.25em}ll} + $find(T, v_{i,j})$ & $\rightarrow T_i | \bot$ & Locate class for variable \\ + $report(T_i)$ & $\rightarrow \{ v_{i,j} \cdots \}$ & List variables for class \\ + $bound(T_i)$ & $\rightarrow b_i | \bot$ & Get bound for class \\ + $insert(v_{i,1})$ & & New single-variable class \\ + $add(T_i, v_{i,j})$ & & Add variable to class \\ + $bind(T_i, b_i)$ & & Set or update class bound \\ + $remove(T, T_i)$ & & Remove class from environment \\ + $unify(T, T_i, T_j)$ & $\rightarrow \top | \bot$ & Combine two type classes \\ + $combine(T, T')$ & $\rightarrow \top | \bot$ & Merge two environments \\ + $save(T)$ & $\rightarrow H$ & Get handle for current state \\ + $backtrack(T, H)$ & & Return to handle state +\end{tabular} +\end{table} + +Given this basic structure, type environments in \CFACC{} need to support eleven basic operations, summarized in Table~\ref{env-op-table}. +The first seven operations are straightforward queries and updates on these data structures: +The lookup operation $find(T, v_{i,j})$ produces $T_i$, the type class in $T$ which contains variable $v_{i,j}$, or an invalid sentinel value for no such class. +The other two query operations act on type classes, where $report(T_i)$ produces the set $\myset{v_{i,1}, v_{i,2}, \cdots, v_{i,|T_i|}}$ of all type variables in a class $T_i$ and $bound(T_i)$ produces the bound $b_i$ of that class, or a sentinel indicating no bound is set. + +The update operation $insert(T, v_{i,1})$ creates a new type class $T_i$ in $T$ that contains only the variable $v_{i,1}$ and no bound; due to the disjointness property $v_{i,1}$ cannot belong to any other type class in $T$. +The $add(T_i, v_{i,j})$ operation adds a new type variable $v_{i,j}$ to class $T_i$; again, $v_{i,j}$ cannot exist elsewhere in $T$. +$bind(T_i, b_i)$ mutates the bound for a type class, setting or updating the current bound. +The final basic mutation operation is $remove(T, T_i)$, which removes a class $T_i$ and all its type variables from an environment $T$. + +The $unify$ operation is the fundamental non-trivial operation a type environment data structure must support. +$unify(T, T_i, T_j)$ merges a type class $T_j$ into another $T_i$, producing a failure result and leaving $T$ in an invalid state if this merge fails. +It is always possible to unify the type variables of both classes by simply taking the union of both sets; given the disjointness property, no checks for set containment are required, and the variable sets can simply be concatenated if supported by the underlying data structure. +$unify$ depends on an internal $unify_bound$ operation which may fail. +In \CFACC{}, $unify_bound(b_i, b_j) \rightarrow b'_i|\bot$ checks that the type classes contain the same sort of variable, takes the tighter of the two conversion permissions, and checks if the bound types can be unified. +If the bound types cannot be unified (\eg{} !struct A! with !int*!), then $unify_bound$ fails, while other combinations of bound types may result in recursive calls. +For instance, unifying !R*! with !S*! for type variables !R! and !S! will result in a call to $unify(T, find($!R!$), find($!S!$))$, while unifying !R*! with !int*! will result in a call to $unify_bound$ on !int! and the bound type of the class containing !R!. +As such, a call to $unify(T, T_i, T_j)$ may touch every type class in $T$, not just $T_i$ and $T_j$, collapsing the entirety of $T$ into a single type class in extreme cases. + +Given the nature of the expression resolution problem as backtracking search, caching and concurrency are both useful tools to decrease runtime. +However, both of these approaches may produce multiple distinct descendants of the same initial type environment, which have possibly been mutated in incompatible ways. +As such, to effectively employ either concurrency or caching, the type environment data structure must support an efficient method to check if two type environments are compatible and merge them if so. +$combine(T,T')$ attempts to merge an environment $T'$ into another environment $T$, producing $\top$ if successful or leaving $T$ in an invalid state and producing $\bot$ otherwise. +The invalid state of $T$ on failure is not important, given that a combination failure will result in the resolution algorithm backtracking to a different environment. +$combine$ proceeds by calls to $insert$, $add$, and $unify$ as needed, and can be roughly thought of as calling $unify$ on every pair of classes in $T$ that have variables $v'_{i,j}$ and $v'_{i,k}$ in the same class $T'_i$ in $T'$. +Like for $unify$, $combine$ can always find a mutually-consistent division of type variables into classes (in the extreme case, all type variables from $T$ and $T'$ in a single type class), but may fail due to inconsistent bounds on merged type classes. + +Finally, the backtracking access patterns of the compiler can be exploited to reduce memory usage or runtime through use of an appropriately designed data structure. +The set of mutations to a type environment across the execution of the resolution algorithm produce an implicit tree of related environments, and the backtracking search typically focuses only on one leaf of the tree at once, or at most a small number of closely-related nodes as arguments to $combine$. +As such, the ability to save and restore particular type environment states is useful, and supported by the $save(T) \rightarrow H$ and $backtrack(T, H)$ operations, which produce a handle for the current environment state and mutate an environment back to a previous state, respectively. +These operations can be naively implemented by a deep copy of $T$ into $H$ and vice versa, but have more efficient implementations in persistency-aware data structures. + +% Future work: design multi-threaded version of C&F persistent map --- core idea is some sort of thread-boundary edit node Index: doc/user/Makefile =================================================================== --- doc/user/Makefile (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ doc/user/Makefile (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -4,7 +4,7 @@ Figures = figures Macros = ../LaTeXmacros -TeXLIB = .:${Macros}:${Build}:../bibliography: +TeXLIB = .:${Macros}:${Build}: LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build} -BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex +BibTeX = BIBINPUTS=../bibliography: && export BIBINPUTS && bibtex MAKEFLAGS = --no-print-directory --silent # Index: driver/as.cc =================================================================== --- driver/as.cc (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ driver/as.cc (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,11 +1,11 @@ -// +// // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo // // The contents of this file are covered under the licence agreement in the // file "LICENCE" distributed with Cforall. -// +// // as.c -- map assembler file, scan for debug information. If found, expand file by one character and insert Cforall // language code on the N line from the start of the debug information. -// +// // Author : Peter A. Buhr // Created On : Wed Aug 1 10:49:42 2018 @@ -13,5 +13,5 @@ // Last Modified On : Sat Sep 8 08:40:16 2018 // Update Count : 97 -// +// #include // perror @@ -45,5 +45,5 @@ if ( size ) { // cannot map 0 sized file - char * start = (char *)mmap( NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 ); + char * start = (char *)mmap( NULL, size + 2, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 ); if ( start == (void *)-1 ) { perror( "mmap" ); exit( EXIT_FAILURE ); }; @@ -65,5 +65,5 @@ } // if - if ( munmap( start, size ) ) { perror( "munmap" ); exit( EXIT_FAILURE ); }; // update on disk + if ( munmap( start, size + 2 ) ) { perror( "munmap" ); exit( EXIT_FAILURE ); }; // update on disk } // if Index: driver/cfa.cc =================================================================== --- driver/cfa.cc (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ driver/cfa.cc (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -10,6 +10,6 @@ // Created On : Tue Aug 20 13:44:49 2002 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Sep 3 16:47:59 2018 -// Update Count : 275 +// Last Modified On : Fri Sep 14 23:02:59 2018 +// Update Count : 277 // @@ -114,5 +114,4 @@ bool std_flag = false; // -std= flag bool noincstd_flag = false; // -no-include-stdhdr= flag - bool xflag = false; // user supplied -x flag bool debugging __attribute(( unused )) = false; // -g flag bool m32 = false; // -m32 flag @@ -291,9 +290,8 @@ } // if nonoptarg = true; - xflag = false; } // if } // for - args[nargs] = "-x"; // turn off language + args[nargs] = "-x"; // turn off language nargs += 1; args[nargs] = "none"; Index: libcfa/src/Makefile.am =================================================================== --- libcfa/src/Makefile.am (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ libcfa/src/Makefile.am (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -68,8 +68,12 @@ libdeps = $(join \ $(addsuffix $(DEPDIR)/ , $(dir $(libobjs) ) ), \ - $(notdir ${libobjs:.lo=.Po}) \ + $(notdir ${libobjs:.lo=.Plo}) \ ) --include $(libdeps) +include $(libdeps) + +$(libdeps): + @mkdir -p $(dir $@) + @echo '#dummy' > $@ prelude.o : prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@ Index: libcfa/src/Makefile.in =================================================================== --- libcfa/src/Makefile.in (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ libcfa/src/Makefile.in (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -407,4 +407,17 @@ am__v_CFA_0 = @echo " CFA " $@; am__v_CFA_1 = +AM_V_JAVAC = $(am__v_JAVAC_@AM_V@) +am__v_JAVAC_ = $(am__v_JAVAC_@AM_DEFAULT_V@) +am__v_JAVAC_0 = @echo " JAVAC " $@; +am__v_JAVAC_1 = +AM_V_GOC = $(am__v_GOC_@AM_V@) +am__v_GOC_ = $(am__v_GOC_@AM_DEFAULT_V@) +am__v_GOC_0 = @echo " GOC " $@; +am__v_GOC_1 = +UPPCOMPILE = $(UPPCC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_UPPFLAGS) $(UPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) $(AM_CFLAGS) $(CFLAGS) +AM_V_UPP = $(am__v_UPP_@AM_V@) +am__v_UPP_ = $(am__v_UPP_@AM_DEFAULT_V@) +am__v_UPP_0 = @echo " UPP " $@; +am__v_UPP_1 = lib_LTLIBRARIES = libcfa.la @@ -453,5 +466,5 @@ libdeps = $(join \ $(addsuffix $(DEPDIR)/ , $(dir $(libobjs) ) ), \ - $(notdir ${libobjs:.lo=.Po}) \ + $(notdir ${libobjs:.lo=.Plo}) \ ) @@ -909,12 +922,16 @@ $(libobjs) : @CFACC@ @CFACPP@ prelude.cfa --include $(libdeps) +include $(libdeps) + +$(libdeps): + @mkdir -p $(dir $@) + @echo '#dummy' > $@ prelude.o : prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@ - ${AM_V_GEN}@CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree -XCFA -l ${<} -c -o ${@} + ${AM_V_GEN}@CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree @CONFIG_CFAFLAGS@ -XCFA -l ${<} -c -o ${@} prelude.lo: prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@ ${AM_V_GEN}$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile \ - @CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree -XCFA -l ${<} -c -o ${@} + @CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree @CONFIG_CFAFLAGS@ -XCFA -l ${<} -c -o ${@} #---------------------------------------------------------------------------------------------------------------- Index: libcfa/src/bits/locks.hfa =================================================================== --- libcfa/src/bits/locks.hfa (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ libcfa/src/bits/locks.hfa (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -37,19 +37,7 @@ #endif -#if defined( __i386 ) || defined( __x86_64 ) || defined( __ARM_ARCH ) - // Intel recommendation - #define __ALIGN__ __attribute__(( aligned (128) )) -#elif defined( __sparc ) - #define __ALIGN__ CALIGN -#else - #error unsupported architecture -#endif - struct __spinlock_t { // Wrap in struct to prevent false sharing with debug info - struct { - // Align lock on 128-bit boundary - __ALIGN__ volatile bool lock; - }; + volatile bool lock; #ifdef __CFA_DEBUG__ // previous function to acquire the lock @@ -58,5 +46,5 @@ void* prev_thrd; #endif -} __ALIGN__; +}; #ifdef __cforall Index: libcfa/src/time.hfa =================================================================== --- libcfa/src/time.hfa (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ libcfa/src/time.hfa (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -10,6 +10,6 @@ // Created On : Wed Mar 14 23:18:57 2018 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Aug 11 13:55:33 2018 -// Update Count : 642 +// Last Modified On : Sat Sep 22 12:25:34 2018 +// Update Count : 643 // @@ -23,5 +23,5 @@ #include // timeval } -#include // Duration/Time types +#include // Duration/Time types enum { TIMEGRAN = 1_000_000_000LL }; // nanosecond granularity, except for timeval @@ -104,6 +104,6 @@ timeval ?=?( timeval & t, zero_t ) { return t{ 0 }; } - timeval ?+?( timeval & lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_usec + rhs.tv_usec }; } - timeval ?-?( timeval & lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_usec - rhs.tv_usec }; } + timeval ?+?( timeval lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_usec + rhs.tv_usec }; } + timeval ?-?( timeval lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_usec - rhs.tv_usec }; } bool ?==?( timeval lhs, timeval rhs ) { return lhs.tv_sec == rhs.tv_sec && lhs.tv_usec == rhs.tv_usec; } bool ?!=?( timeval lhs, timeval rhs ) { return lhs.tv_sec != rhs.tv_sec || lhs.tv_usec != rhs.tv_usec; } @@ -119,6 +119,6 @@ timespec ?=?( timespec & t, zero_t ) { return t{ 0 }; } - timespec ?+?( timespec & lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_nsec + rhs.tv_nsec }; } - timespec ?-?( timespec & lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_nsec - rhs.tv_nsec }; } + timespec ?+?( timespec lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_nsec + rhs.tv_nsec }; } + timespec ?-?( timespec lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_nsec - rhs.tv_nsec }; } bool ?==?( timespec lhs, timespec rhs ) { return lhs.tv_sec == rhs.tv_sec && lhs.tv_nsec == rhs.tv_nsec; } bool ?!=?( timespec lhs, timespec rhs ) { return lhs.tv_sec != rhs.tv_sec || lhs.tv_nsec != rhs.tv_nsec; } Index: src/CodeTools/ResolvProtoDump.cc =================================================================== --- src/CodeTools/ResolvProtoDump.cc (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ src/CodeTools/ResolvProtoDump.cc (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -204,4 +204,11 @@ /// ensures type inst names are uppercase static void ti_name( const std::string& name, std::stringstream& ss ) { + // replace built-in wide character types with named types + if ( name == "char16_t" || name == "char32_t" || name == "wchar_t" ) { + ss << "#" << name; + return; + } + + // strip leading underscore unsigned i = 0; while ( i < name.size() && name[i] == '_' ) { ++i; } @@ -210,6 +217,16 @@ return; } - ss << (char)std::toupper( static_cast(name[i]) ) - << (name.c_str() + i + 1); + + std::string stripped = name.substr(i); + // strip trailing "_generic_" from autogen names (avoids some user-generation issues) + char generic[] = "_generic_"; size_t n_generic = sizeof(generic) - 1; + if ( stripped.size() >= n_generic + && stripped.substr( stripped.size() - n_generic ) == generic ) { + stripped.resize( stripped.size() - n_generic ); + } + + // uppercase first character + ss << (char)std::toupper( static_cast(stripped[0]) ) + << (stripped.c_str() + 1); } @@ -304,5 +321,9 @@ } - // TODO support VarArgsType + // TODO support variable args for functions + void previsit( VarArgsType* ) { + // only include varargs for top level (argument type) + if ( depth == 0 ) { ss << "#$varargs"; } + } // replace 0 and 1 with int @@ -397,4 +418,11 @@ } + /// Handle already-resolved variables as type constants + void previsit( VariableExpr* expr ) { + PassVisitor tyPrinter{ closed, ss }; + expr->var->get_type()->accept( tyPrinter ); + visit_children = false; + } + /// Calls handled as calls void previsit( UntypedExpr* expr ) { @@ -426,6 +454,8 @@ } - /// Already-resolved calls skipped - void previsit( ApplicationExpr* ) { + /// Already-resolved calls reduced to their type constant + void previsit( ApplicationExpr* expr ) { + PassVisitor tyPrinter{ closed, ss }; + expr->result->accept( tyPrinter ); visit_children = false; } @@ -532,5 +562,4 @@ for ( Initializer* it : li->initializers ) { build( it, ss ); - ss << ' '; } } @@ -539,7 +568,7 @@ /// Adds an object initializer to the list of expressions void build( const std::string& name, Initializer* init, std::stringstream& ss ) { - ss << "$constructor( "; + ss << "$constructor( &"; rp_name( name, ss ); - ss << "() "; + ss << ' '; build( init, ss ); ss << ')'; @@ -676,4 +705,9 @@ } + void previsit( AsmStmt* ) { + // skip asm statements + visit_children = false; + } + void previsit( Expression* expr ) { std::stringstream ss; @@ -686,5 +720,5 @@ /// Print non-prelude global declarations for resolv proto void printGlobals() const { - std::cout << "#ptr $addr T" << std::endl; // &? + std::cout << "#$ptr $addr T" << std::endl; // &? int i = (int)BasicType::SignedInt; std::cout << i << " $and " << i << ' ' << i << std::endl; // ?&&? Index: src/SynTree/Constant.cc =================================================================== --- src/SynTree/Constant.cc (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ src/SynTree/Constant.cc (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -10,6 +10,6 @@ // Created On : Mon May 18 07:44:20 2015 // Last Modified By : Andrew Beach -// Last Modified On : Fri Jul 14 14:50:00 2017 -// Update Count : 29 +// Last Modified On : Fri Spt 28 14:49:00 2018 +// Update Count : 30 // @@ -19,4 +19,5 @@ #include "Constant.h" +#include "Expression.h" // for ConstantExpr #include "Type.h" // for BasicType, Type, Type::Qualifiers, PointerType @@ -48,4 +49,14 @@ Constant Constant::from_double( double d ) { return Constant( new BasicType( Type::Qualifiers(), BasicType::Double ), std::to_string( d ), d ); +} + +Constant Constant::from_string( std::string const & str ) { + return Constant( + new ArrayType( + noQualifiers, + new BasicType( Type::Qualifiers( Type::Const ), BasicType::Char ), + new ConstantExpr( Constant::from_int( str.size() + 1 /* \0 */ )), + false, false ), + std::string("\"") + str + "\"", (unsigned long long int)0 ); } Index: src/SynTree/Constant.h =================================================================== --- src/SynTree/Constant.h (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ src/SynTree/Constant.h (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:54:46 2017 -// Update Count : 17 +// Last Modified By : Andrew Beach +// Last Modified On : Fri Spt 28 14:48:00 2018 +// Update Count : 18 // @@ -51,4 +51,6 @@ /// generates a floating point constant of the given double static Constant from_double( double d ); + /// generates an array of chars constant of the given string + static Constant from_string( std::string const & s ); /// generates a null pointer value for the given type. void * if omitted. Index: tests/concurrent/coroutineYield.c =================================================================== --- tests/concurrent/coroutineYield.c (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ tests/concurrent/coroutineYield.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,4 +1,4 @@ #include -#include hfa> +#include #include #include Index: tests/concurrent/preempt.c =================================================================== --- tests/concurrent/preempt.c (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ tests/concurrent/preempt.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,3 +1,3 @@ -#include hfa> +#include #include #include Index: tests/concurrent/signal/block.c =================================================================== --- tests/concurrent/signal/block.c (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ tests/concurrent/signal/block.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -8,5 +8,5 @@ #include -#include hfa> +#include #include #include Index: tests/concurrent/signal/disjoint.c =================================================================== --- tests/concurrent/signal/disjoint.c (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ tests/concurrent/signal/disjoint.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -1,4 +1,4 @@ #include -#include hfa> +#include #include #include Index: tests/concurrent/signal/wait.c =================================================================== --- tests/concurrent/signal/wait.c (revision ee27df2fdf76c37c966500ec374ee044b40e7a0a) +++ tests/concurrent/signal/wait.c (revision cdc02f28045dea7a293c384abb175ac0c5185dcc) @@ -6,5 +6,5 @@ #include -#include hfa> +#include #include #include