Changes in / [cdc02f2:ee27df2]


Ignore:
Files:
7 deleted
27 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/pl.bib

    rcdc02f2 ree27df2  
    830830    month       = oct,
    831831    type        = {Diplomarbeit},
    832     note        = {\href{https://plg.uwaterloo.ca/~usystem/theses/KrischerThesis.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-theses/\-KrischerThesis.pdf}},
     832    note        = {{\small\textsf{ftp://\-plg.uwaterloo.ca/\-pub/\-theses/\-KrischerThesis.ps.gz}}},
    833833}
    834834
    … …  
    925925    key         = {Cforall},
    926926    author      = {{\textsf{C}{$\mathbf{\forall}$} Features}},
    927     howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-$\sim$cforall/\-features}},
     927    howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-~cforall/\-features}},
    928928    optnote     = {Accessed: 2018-01-01},
    929929}
    … …  
    11011101    month       = oct,
    11021102    year        = 2001,
    1103     note        = {\href{http://plg.uwaterloo.ca/~cforall/cfa.ps}{http://\-plg.uwaterloo.ca/\-$\sim$cforall/\-cfa.ps}},
     1103    note        = {\href{http://plg.uwaterloo.ca/~cforall/cfa.ps}{http://\-plg.uwaterloo.ca/\-\char`\~cforall/\-cfa.ps}},
    11041104}
    11051105
    … …  
    15161516    month       = dec,
    15171517    year        = 2017,
    1518     note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}},
     1518    note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-~usystem/\-pub/\-uSystem/uC++.pdf}},
    15191519}
    15201520
    … …  
    18091809    author      = {Glen Ditchfield},
    18101810    title       = {Conversions for \textsf{C}$\mathbf{\forall}$},
    1811     note        = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-$\sim$cforall/\-Conversions/\-index.html}},
     1811    note        = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-\textasciitilde cforall/\-Conversions/\-index.html}},
    18121812    month       = {Nov},
    18131813    year        = {2002},
    … …  
    18771877    title       = {CS343},
    18781878    year        = 2018,
    1879     howpublished= {\href{https://www.student.cs.uwaterloo.ca/~cs343}{https://\-www.student.cs.uwaterloo.ca/\-$\sim$cs343}},
     1879    howpublished= {\href{https://www.student.cs.uwaterloo.ca/~cs343}{https://\-www.student.cs.uwaterloo.ca/\-~cs343}},
    18801880}
    18811881
    … …  
    41444144    month       = sep,
    41454145    year        = 2006,
    4146     note        = {\textsf{http://cs.anu.edu.au/\-$\sim$Robin.Garner/\-mmtk-guide.pdf}},
     4146    note        = {\textsf{http://cs.anu.edu.au/\-\char`\~Robin.Garner/\-mmtk-guide.pdf}},
    41474147}
    41484148
    … …  
    42484248    month       = sep,
    42494249    year        = 1994,
    4250     note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uSystem.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/\-uSystem.pdf}},
     4250    note        = {{\small\textsf{ftp://\-plg.uwaterloo.ca/\-pub/\-uSystem/\-uSystem.ps.gz}}},
    42514251}
    42524252
    … …  
    47904790    year        = 1995,
    47914791    number      = 31,
    4792     note        = {{\small\textsf{http://\-www.cs.wustl.edu/\-$\sim$schmidt/\-PDF/\-IPC\_SAP-92.pdf}}},
     4792    note        = {{\small\textsf{http://\-www.cs.wustl.edu/\-\char`\~schmidt/\-PDF/\-IPC\_SAP-92.pdf}}},
    47934793}
    47944794
    … …  
    61326132    month       = apr,
    61336133    type        = {Diplomarbeit},
    6134     note        = {\href{https://plg.uwaterloo.ca/~usystem/theses/SchusterThesis.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-theses/\-SchusterThesis.pdf}},
     6134    note        = {\href{ftp://plg.uwaterloo.ca/pub/theses/SchusterThesis.ps.gz}{ftp://\-plg.uwaterloo.ca/\-pub/\-theses/\-SchusterThesis.ps.gz}},
    61356135}
    61366136

  • doc/papers/concurrency/Makefile

    rcdc02f2 ree27df2  
    44Figures = figures
    55Macros = ../AMA/AMA-stix/ama
    6 TeXLIB = .:../../LaTeXmacros:${Macros}:${Build}:
     6TeXLIB = .:annex:../../LaTeXmacros:${Macros}:${Build}:../../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    8 BibTeX = BIBINPUTS=annex:../../bibliography: && export BIBINPUTS && bibtex
     8BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    99
    1010MAKEFLAGS = --no-print-directory # --silent

  • doc/papers/general/Makefile

    rcdc02f2 ree27df2  
    44Figures = figures
    55Macros = ../AMA/AMA-stix/ama
    6 TeXLIB = .:${Macros}:${Build}:
     6TeXLIB = .:${Macros}:${Build}:../../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    8 BibTeX = BIBINPUTS=../../bibliography: && export BIBINPUTS && bibtex
     8BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    99
    1010MAKEFLAGS = --no-print-directory # --silent

  • doc/theses/aaron_moss_PhD/phd/.gitignore

    rcdc02f2 ree27df2  
    11templates/
    2 code/a.out
    32thesis.pdf
    43thesis.aux

  • doc/theses/aaron_moss_PhD/phd/Makefile

    rcdc02f2 ree27df2  
    11BUILD = build
    22BIBDIR = ../../../bibliography
    3 EVALDIR = evaluation
    43TEXLIB = .:${BUILD}:${BIBDIR}:
    54
    6 # LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction=nonstopmode -halt-on-error -output-directory=${BUILD}
    7 LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
     5LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction= -output-directory=${BUILD}
    86BIBTEX = BIBINPUTS=${TEXLIB} && export BIBINPUTS && bibtex
    9 
    10 VPATH = ${EVALDIR}
    117
    128BASE = thesis
    … …  
    2117introduction \
    2218background \
    23 generic-types \
    2419type-environment \
    2520resolution-heuristics \
    2621conclusion \
    27 }
    28 
    29 GRAPHS = ${addsuffix .tex, \
    30 generic-timing \
    3122}
    3223
    … …  
    4132        wc ${SOURCES}
    4233
    43 ${DOCUMENT} : ${BASE}.ps
    44         ps2pdf ${BUILD}/$<
     34${DOCUMENT} : ${SOURCES} ${BUILD}
     35        ${LATEX} ${BASE}
     36        ${LATEX} ${BASE}
    4537
    46 ${BASE}.ps : ${BASE}.dvi
    47         dvips ${BUILD}/$< -o ${BUILD}/$@
    48 
    49 ${BASE}.dvi : Makefile ${SOURCES} ${GRAPHS} ${BIBFILE} ${BUILD}
     38rebuild-refs : ${SOURCES} ${BIBFILE} ${BUILD}
    5039        ${LATEX} ${BASE}
    5140        ${BIBTEX} ${BUILD}/${BASE}
    … …  
    5342        ${LATEX} ${BASE}
    5443
    55 ${GRAPHS} : generic-timing.gp generic-timing.dat ${BUILD}
    56         gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/generic-timing.gp
    57 
    5844${BUILD}:
    5945        mkdir -p ${BUILD}

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

    rcdc02f2 ree27df2  
    4343tabsize=5,                                                                                              % N space tabbing
    4444xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
     45%mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
    4546escapechar=\$,                                                                                  % LaTeX escape in CFA code
    4647keepspaces=true,                                                                                %

  • doc/theses/aaron_moss_PhD/phd/frontpgs.tex

    rcdc02f2 ree27df2  
    160160% L I S T   O F   F I G U R E S
    161161% -----------------------------
    162 \addcontentsline{toc}{chapter}{List of Figures}
    163 \listoffigures
    164 \cleardoublepage
    165 \phantomsection         % allows hyperref to link to the correct page
     162% \addcontentsline{toc}{chapter}{List of Figures}
     163% \listoffigures
     164% \cleardoublepage
     165% \phantomsection               % allows hyperref to link to the correct page
    166166
    167167% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)

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

    rcdc02f2 ree27df2  
    22\label{generic-chap}
    33
    4 A significant shortcoming in standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms.
    5 Broadly speaking, there are three approaches to implement abstract data structures in C.
    6 One approach is to write bespoke data structures for each context in which they are needed.
    7 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.
    8 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.
    9 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.
    10 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.
    11 Furthermore, writing and using preprocessor macros is unnatural and inflexible.
    12 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.
     4Talk about generic types. Pull from Moss~\etal\cite{Moss18}.
    135
    14 \begin{figure}
    15         \begin{cfa}
    16                 struct int_list { int value; struct int_list* next; };
     6% TODO discuss layout function algorithm, application to separate compilation
     7% TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation
    178
    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                 }
     9% TODO mention impetus for zero_t design
    2310
    24                 int int_list_head( const struct int_list* ls ) { return ls->value; }
     11% TODO mention use in tuple-type implementation
    2512
    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 generic linked list implementation.} \label{macro-generic-fig}
    134 \end{figure}
    135 
    136 \CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types.
    137 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.
    138 \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.
    139 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.
    140 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}.
    141 
    142 \begin{figure}
    143         \begin{cfa}
    144                 forall(otype T) struct list { T value; list(T)* next; };
    145 
    146                 $\C[\textwidth]{// single polymorphic implementation of each function}$
    147                 $\C[\textwidth]{// overloading reduces need for namespace prefixes}$
    148 
    149                 forall(otype T) void insert( list(T)** ls, T x ) {
    150                         list(T)* node = alloc();  $\C{// type-inferring alloc}$
    151                         (*node){ x, *ls };  $\C{// concise constructor syntax}$
    152                         *ls = node;
    153                 }
    154 
    155                 forall(otype T) T head( const list(T)* ls ) { return ls->value; }
    156 
    157                 $\C[\textwidth]{// use is clear and efficient}$
    158 
    159                 int main() {
    160                         list(int)* il = 0;
    161                         insert( &il, 42 );  $\C{// inferred polymorphic T}$
    162                         printf("%d\n", head(il));
    163                        
    164                         list(const char*)* sl = 0;
    165                         insert( &sl, "hello" );
    166                         printf("%s\n", head(sl));
    167                 }
    168         \end{cfa}
    169 
    170         \caption{\CFA{} generic linked list implementation.} \label{cfa-generic-fig}
    171 \end{figure}
    172 
    173 \section{Design}
    174 
    175 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.
    176 The guiding principle was to maintain an unsurprising language model for C programmers without compromising runtime efficiency.
    177 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.
    178 
    179 \subsection{Related Work}
    180 
    181 One approach to the design of generic types is that taken by \CC{} templates\cite{C++}.
    182 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.
    183 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.
    184 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.
    185 The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms.
    186 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.
    187 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{}.
    188 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{}.
    189 
    190 Java\cite{Java8} has another prominent implementation for generic types, introduced in Java~5 and based on a significantly different approach than \CC{}.
    191 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.
    192 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.
    193 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.
    194 
    195 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.
    196 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.
    197 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!.
    198 In the \CFA{} terminology discussed in Section~\ref{generic-impl-sec}, all Cyclone polymorphism must be dtype-static.
    199 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{}.
    200 
    201 Many other languages include some form of generic types.
    202 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.
    203 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{}.
    204 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.
    205 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.
    206 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.
    207 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.
    208 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.
    209 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.
    210 
    211 \subsection{\CFA{} Generics}
    212 
    213 The generic types design in \CFA{} draws inspiration from both \CC{} and Java generics, capturing the better aspects of each.
    214 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.
    215 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.
    216 As an example, consider the following generic type and function \TODO{test this}:
    217 
    218 \begin{cfa}
    219 forall( otype R, otype S ) struct pair { R first; S second; };
    220 
    221 pair(const char*, int) with_len( const char* s ) {
    222         return (pair(const char*), int){ s, strlen(s) };
    223 }
    224 \end{cfa}
    225 
    226 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!.
    227 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.
    228 
    229 !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.
    230 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.
    231 Since the parameters to this polymorphic constructor call are all statically known, compiler inlining can eliminate any runtime overhead of this polymorphic call.
    232 
    233 \CFA{} deliberately does not support \CC{}-style partial specializations of generic types.
    234 A particularly infamous example in the \CC{} standard library is !vector<bool>!, which is represented as a bitstring rather than the array representation of the other !vector! instantiations.
    235 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.
    236 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.
    237 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.
    238 
    239 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.
    240 As an example, the !with_len! function above could be an optimization of the following more general function:
    241 
    242 \begin{cfa}
    243 forall(otype T, otype I | { I len(T); })
    244 pair(T, I) with_len( T s ) {
    245         return (pair(T,I)){ s, len(s) };
    246 }
    247 \end{cfa}
    248 
    249 \CFA{} generic types also support the type constraints from !forall! functions.
    250 For example, the following declaration of a sorted set type ensures that the set key implements equality and relational comparison:
    251 
    252 \begin{cfa}
    253 forall(otype Key | { int ?==?(Key, Key); int ?<?(Key, Key); }) struct sorted_set;
    254 \end{cfa}
    255 
    256 These constraints are implemented by applying equivalent constraints to the compiler-generated constructors for this type.
    257 
    258 \section{Implementation} \label{generic-impl-sec}
    259 
    260 The ability to use generic types in polymorphic contexts means that the \CFA{} implementation in \CFACC{} must support a mechanism for accessing fields of generic types dynamically at runtime.
    261 While \CFACC{} could in principle use this same mechanism for accessing fields of all generic types, such an approach would throw away compiler knowledge of static types and impose an unnecessary runtime cost, limiting the utility of the generic type design.
    262 Instead, my design for generic type support in \CFACC{} distinguishes between \emph{concrete} generic types that have a fixed memory layout regardless of type parameters and \emph{dynamic} generic types that may vary in memory layout depending on their type parameters.
    263 A \emph{dtype-static} type has polymorphic parameters but is still concrete.
    264 Polymorphic pointers are an example of dtype-static types; given some type variable !T!, T is a polymorphic type, but !T*! has a fixed size and can therefore be represented by a !void*! in code generation.
    265 In particular, generic types where all parameters are un-!sized! (\ie{} they do not conform to the built-in !sized! trait because the compiler does not know their size and alignment) are always concrete, as there is no possibility for their layout to vary based on type parameters of unknown size and alignment.
    266 More precisely, a type is concrete if and only if all of its !sized! type parameters are concrete, and a concrete type is dtype-static if any of its type parameters are (possibly recursively) polymorphic.
    267 To illustrate, the following code using the !pair! type from above \TODO{test this} has each use of !pair! commented with its class:
    268 
    269 \begin{cfa}
    270 //dynamic, layout varies based on T
    271 forall(otype T) T value( pair(const char*, T) p ) { return p.second; }
    272 
    273 // dtype-static, F* and T* are concrete but recursively polymorphic
    274 forall(dtype F, otype T) T value( pair(F*, T*) ) { return *p.second; }
    275 
    276 pair(const char*, int) p = {"magic", 42}; $\C[2.5in]{// concrete}$
    277 int i = value(p);
    278 pair(void*, int*) q = {0, &p.second}; $\C[2.5in]{// concrete}$
    279 i = value(q);
    280 double d = 1.0;
    281 pair(double*, double*) r = {&d, &d}; $\C[2.5in]{// concrete}$
    282 d = value(r);
    283 \end{cfa}
    284 
    285 \subsection{Concrete Generic Types}
    286 
    287 The \CFACC{} translator template expands concrete generic types into new structure types, affording maximal inlining.
    288 To enable interoperation among equivalent instantiations of a generic type, \CFACC{} saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate.
    289 In particular, tuple types are implemented as a single compiler-generated generic type definition per tuple arity, and can be instantiated and reused according to the usual rules for generic types.
    290 A function declaration that accepts or returns a concrete generic type produces a declaration for the instantiated structure in the same scope, which all callers may reuse.
    291 As an example, the concrete instantiation for !pair(const char*, int)! is\footnote{This omits the field name mangling performed by \CFACC{} for overloading purposes.\label{mangle-foot}}
    292 
    293 \begin{cfa}
    294 struct _pair_conc0 { const char * first; int second; };
    295 \end{cfa}
    296 
    297 A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
    298 In the example above, the !pair(F*, T*)! parameter to !value! is such a type; its expansion is below\footref{mangle-foot}, and it is used as the type of the variables !q! and !r! as well, with casts for member access where appropriate.
    299 
    300 \begin{cfa}
    301 struct _pair_conc1 { void* first; void* second; };
    302 \end{cfa}
    303 
    304 \subsection{Dynamic Generic Types}
    305 
    306 In addition to this efficient implementation of concrete generic types, \CFA{} also offers flexibility with powerful support for dynamic generic types.
    307 In the pre-existing compiler design, !otype! (and all !sized!) type parameters come with implicit size and alignment parameters provided by the caller.
    308 The design for generic types presented here adds an \emph{offset array} containing structure-member offsets for dynamic generic !struct! types.
    309 A dynamic generic !union! needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
    310 Access to members of a dynamic structure is provided at runtime via base displacement addressing the structure pointer and the member offset (similar to the !offsetof! macro), moving a compile-time offset calculation to runtime.
    311 
    312 the offset arrays are statically generated where possible.
    313 If a dynamic generic type is passed or returned by value from a polymorphic function, \CFACC{} can safely assume that the generic type is complete (\ie{} has a known layout) at any call site, and the offset array is passed from the caller; if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C !offsetof! macro.
    314 As an example, the body of the second !value! function above is implemented as
    315 
    316 \begin{cfa}
    317 _assign_T( _retval, p + _offsetof_pair[1] ); $\C[2in]{// return *p.second}$
    318 \end{cfa}
    319 
    320 Here, !_assign_T! is passed in as an implicit parameter from !otype T! and takes two !T*! (!void*! in the generated code), a destination and a source, and !_retval! is the pointer to a caller-allocated buffer for the return value, the usual \CFA{} method to handle dynamically-sized return types.
    321 !_offsetof_pair! is the offset array passed into !value!; this array is generated at the call site as
    322 
    323 \begin{cfa}
    324 size_t _offsetof_pair[] = {offsetof(_pair_conc0, first),  offsetof(_pair_conc0, second)};
    325 \end{cfa}
    326 
    327 \subsubsection{Layout Functions}
    328 
    329 In some cases, the offset arrays cannot be statically generated.
    330 For instance, modularity is generally provided in C by including an opaque forward declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately-compiled \texttt{.c} file.
    331 \CFA{} supports this pattern for generic types, implying that the caller of a polymorphic function may not know the actual layout or size of a dynamic generic type and only holds it by pointer.
    332 \CFACC{} automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed into a function from that functions's caller.
    333 These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all !sized! parameters to the generic structure.
    334 Un!sized! parameters not passed because they are forbidden from being used in a context that affects layout by C's usual rules about incomplete types.
    335 Similarly, the layout function can only safely be called from a context where the generic type definition is visible, because otherwise the caller will not know how large to allocate the array of member offsets.
    336 
    337 The C standard does not specify a memory layout for structs, but the POSIX ABI for x86\cit{} does; this memory layout is common for C implementations, but is a platform-specific issue for porting \CFA{}.
    338 This algorithm, sketched below in pseudo-\CFA{}, is a straightforward mapping of consecutive fields into the first properly-aligned offset in the !struct! layout; layout functions for !union! types omit the offset array and simply calculate the maximum size and alignment over all union variants.
    339 Since \CFACC{} generates a distinct layout function for each type, constant-folding and loop unrolling are applied.
    340 
    341 \begin{cfa}
    342 forall(dtype T1, dtype T2, ... | sized(T1) | sized(T2) | ...)
    343 void layout(size_t* size, size_t* align, size_t* offsets) {
    344         // initialize values
    345         *size = 0; *align = 1;
    346         // set up members
    347         for ( int i = 0; i < n_fields; ++i ) {
    348                 // pad to alignment
    349                 size_t off_align = *size % alignof(field[i]);
    350                 if ( off_align != 0 ) { *size += alignof(field[i]) - off_align; }
    351                 // mark member, increase size, and fix alignment
    352                 offsets[i] = *size;
    353                 *size += sizeof(field[i]);
    354                 if ( *align < alignof(field[i]) ) { *align = alignof(field[i]); }
    355         }
    356         // final padding to alignment
    357         size_t off_align = *size % *align;
    358         if ( off_align != 0 ) { *size += *align - off_align; }
    359 }
    360 \end{cfa}
    361 
    362 Results of layout function calls are cached so that they are only computed once per type per function.
    363 Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature, an important implemenation-hiding constraint of the design.
    364 For instance, a function that strips duplicate values from an unsorted !list(T)! likely has a reference to the list as its only explicit parameter, but uses some sort of !set(T)! internally to test for duplicate values.
    365 This function could acquire the layout for !set(T)! by calling its layout function, providing as an argument the layout of !T! implicitly passed into that function.
    366 
    367 Whether a type is concrete, dtype-static, or dynamic is decided solely on the basis of the type arguments and !forall! clause type paramters.
    368 This design allows opaque forward declarations of generic types, \eg{} !forall(otype T) struct Box;! like in C, all uses of $Box(T)$ can be separately compiled, and callers from other translation units know the proper calling conventions to use.
    369 In an alternate design where the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static --- \eg{} !Box! could be defined with a body !{ T* p; }!, and would thus not depend on !T! for its layout.
    370 However, the existence of an !otype! parameter !T! means that !Box! \emph{could} depend on !T! for its layout if this definition is not visible, and we judged preserving separate compilation (and the associated C compatibility) in the implemented design to be an acceptable trade-off.
    371 
    372 \subsection{Applications of Dtype-static Types} \label{dtype-static-sec}
    373 
    374 The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
    375 The most important such pattern is using !forall(dtype T) T*! as a type-checked replacement for !void*!, \eg{} creating a lexicographic comparison function for pairs of pointers.
    376 
    377 \begin{cfa}
    378 forall(dtype T)
    379 int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
    380         int c = cmp( a->first, b->first );
    381         return c ? c : cmp( a->second, b->second );
    382 }
    383 \end{cfa}
    384 
    385 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.
    386 
    387 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \emph{tag structures}.
    388 Sometimes, information is only used for type checking and can be omitted at runtime.
    389 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 !?+?!.
    390 These implementations may even be separately compiled, unlike \CC{} template functions.
    391 However, the \CFA{} type checker ensures matching types are used by all calls to !?+?!, preventing nonsensical computations like adding a length to a volume.
    392 
    393 \begin{cfa}
    394 forall(dtype Unit) struct scalar { unsigned long value; };
    395 struct metres {};
    396 struct litres {};
    397 
    398 forall(dtype U) scalar(U) ?+?(scalar(U) a, scalar(U) b) {
    399         return (scalar(U)){ a.value + b.value };
    400 }
    401 
    402 scalar(metres) half_marathon = { 21098 };
    403 scalar(litres) pool = { 2500000 };
    404 scalar(metres) marathon = half_marathon + half_marathon;
    405 `marathon + pool;` $\C[4in]{// compiler ERROR, mismatched types}$
    406 \end{cfa}
    407 
    408 \section{Performance Experiments} \label{generic-performance-sec}
    409 
    410 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}.
    411 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.
    412 A more illustrative comparison measures the costs of idiomatic usage of each language's features.
    413 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.
    414 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.
    415 
    416 \begin{cfa}
    417 int main() {
    418         int max = 0, val = 42;
    419         stack( int ) si, ti;
    420 
    421         REPEAT_TIMED( "push_int", N, push( si, val ); )
    422         TIMED( "copy_int", ti{ si }; )
    423         TIMED( "clear_int", clear( si ); )
    424         REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
    425 
    426         pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
    427         stack( pair( short, char ) ) sp, tp;
    428 
    429         REPEAT_TIMED( "push_pair", N, push( sp, val ); )
    430         TIMED( "copy_pair", tp{ sp }; )
    431         TIMED( "clear_pair", clear( sp ); )
    432         REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp );
    433                 if ( x > max ) max = x; )
    434 }
    435 \end{cfa}
    436 
    437 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{}.
    438 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.
    439 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.
    440 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.
    441 
    442 Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark.
    443 The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted.
    444 All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}.
    445 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.
    446 I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation.
    447 
    448 \begin{figure}
    449 \centering
    450 \input{generic-timing}
    451 \caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig}
    452 \end{figure}
    453 
    454 \begin{table}
    455 \caption{Properties of benchmark code} \label{generic-eval-table}
    456 \centering
    457 \newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
    458 \begin{tabular}{lrrrr}
    459                                                                         & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\
    460 maximum memory usage (MB)                       & 10\,001       & 2\,502        & 2\,503        & 11\,253               \\
    461 source code size (lines)                        & 201           & 191           & 125           & 294                   \\
    462 redundant type annotations (lines)      & 27            & 0                     & 2                     & 16                    \\
    463 binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
    464 \end{tabular}
    465 \end{table}
    466 
    467 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.
    468 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.
    469 \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.
    470 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.
    471 Finally, the binary size for \CFA{} is larger because of static linking with \CFA{} libraries.
    472 
    473 \CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort.
    474 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.
    475 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.
    476 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.
    477 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.
    478 \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.
    479 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.
    480 
    481 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.
    482 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.
    483 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.
    484 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.
    485 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.
    486 
    487 \section{Future Work}
    488 
    489 The generic types design presented here is already sufficiently expressive to implement a variety of useful library types.
    490 However, some other features based on this design could further improve \CFA{}.
    491 
    492 The most pressing addition is the ability to have non-type generic parameters.
    493 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.
    494 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.
    495 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.
    496 
    497 The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}.
    498 One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables.
    499 Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types.
    500 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.
    501 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{}.
    502 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.
    503 \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.
    504 
    505 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.
    506 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.
    507 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.
    508 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
    509 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.
     13% TODO pull benchmarks from Moss et al.

  • doc/theses/aaron_moss_PhD/phd/introduction.tex

    rcdc02f2 ree27df2  
    55
    66\begin{table}[h]
    7 \caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years} \label{tiobe-table}
     7\label{tiobe-table}
     8\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years}
    89
    910\centering

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

    rcdc02f2 ree27df2  
    1212\newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name
    1313\newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name
    14 \newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj} % C++ virtual symbolic name
    1514\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name
    1615
    … …  
    2019\newcommand{\etal}{\textit{et~al.}}
    2120
    22 \newcommand{\myset}[1]{\left\{#1\right\}}
    23 
    2421\newcommand{\TODO}[1]{\textbf{TODO:} \textit{#1}}
    2522\newcommand{\cit}{\textsuperscript{[citation needed]}}

  • doc/theses/aaron_moss_PhD/phd/thesis.tex

    rcdc02f2 ree27df2  
    2121
    2222\usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments
    23 % \usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver
    24 \usepackage{graphicx}
    25 
    26 \usepackage{footmisc} % for double refs to the same footnote
     23\usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver
    2724
    2825% Hyperlinks make it very easy to navigate an electronic document.
    … …  
    3128% Use the "hyperref" package
    3229% N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE
    33 %\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options
    34 \usepackage[pagebackref=false]{hyperref}
     30\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options
    3531% N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing.
    3632
    … …  
    124120\input{background}
    125121\input{generic-types}
     122\input{type-environment}
    126123\input{resolution-heuristics}
    127 \input{type-environment}
    128124\input{conclusion}
    129125

  • doc/theses/aaron_moss_PhD/phd/type-environment.tex

    rcdc02f2 ree27df2  
    22\label{env-chap}
    33
    4 One key data structure for expression resolution is the \emph{type environment}.
    5 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.
    6 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.
    7 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.
    8 
    9 \section{Definitions}
    10 
    11 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|}}$.
    12 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.
    13 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).
    14 
    15 \begin{table}
    16 \caption[Type environment operation summary]{Summary of type environment operations.}
    17 \label{env-op-table}
    18 \centering
    19 \begin{tabular}{r@{\hskip 0.25em}ll}
    20         $find(T, v_{i,j})$ & $\rightarrow T_i | \bot$           & Locate class for variable             \\
    21         $report(T_i)$ & $\rightarrow \{ v_{i,j} \cdots \}$      & List variables for class              \\
    22         $bound(T_i)$ & $\rightarrow b_i | \bot$                         & Get bound for class                   \\
    23         $insert(v_{i,1})$ &                                                                     & New single-variable class             \\
    24         $add(T_i, v_{i,j})$ &                                                           & Add variable to class                 \\
    25         $bind(T_i, b_i)$ &                                                                      & Set or update class bound             \\
    26         $remove(T, T_i)$ &                                                                      & Remove class from environment \\
    27         $unify(T, T_i, T_j)$ & $\rightarrow \top | \bot$        & Combine two type classes              \\
    28         $combine(T, T')$ & $\rightarrow \top | \bot$            & Merge two environments                \\
    29         $save(T)$ & $\rightarrow H$                                                     & Get handle for current state  \\
    30         $backtrack(T, H)$ &                                                                     & Return to handle state
    31 \end{tabular}
    32 \end{table}
    33 
    34 Given this basic structure, type environments in \CFACC{} need to support eleven basic operations, summarized in Table~\ref{env-op-table}.
    35 The first seven operations are straightforward queries and updates on these data structures:
    36 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.
    37 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.
    38 
    39 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$.
    40 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$.
    41 $bind(T_i, b_i)$ mutates the bound for a type class, setting or updating the current bound.
    42 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$.
    43 
    44 The $unify$ operation is the fundamental non-trivial operation a type environment data structure must support.
    45 $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.
    46 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.
    47 $unify$ depends on an internal $unify_bound$ operation which may fail.
    48 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.
    49 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.
    50 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!.
    51 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.
    52 
    53 Given the nature of the expression resolution problem as backtracking search, caching and concurrency are both useful tools to decrease runtime.
    54 However, both of these approaches may produce multiple distinct descendants of the same initial type environment, which have possibly been mutated in incompatible ways.
    55 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.
    56 $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.
    57 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.
    58 $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'$.
    59 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.
    60 
    61 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.
    62 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$.
    63 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.
    64 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.
    65 
    66 % Future work: design multi-threaded version of C&F persistent map --- core idea is some sort of thread-boundary edit node
     4Talk about the type environment data structure. Pull from your presentation.

  • doc/user/Makefile

    rcdc02f2 ree27df2  
    44Figures = figures
    55Macros = ../LaTeXmacros
    6 TeXLIB = .:${Macros}:${Build}:
     6TeXLIB = .:${Macros}:${Build}:../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    8 BibTeX = BIBINPUTS=../bibliography: && export BIBINPUTS && bibtex
     8BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    99
    1010MAKEFLAGS = --no-print-directory --silent #

  • driver/as.cc

    rcdc02f2 ree27df2  
    1 //
     1// 
    22// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
    33//
    44// The contents of this file are covered under the licence agreement in the
    55// file "LICENCE" distributed with Cforall.
    6 //
     6// 
    77// as.c -- map assembler file, scan for debug information. If found, expand file by one character and insert Cforall
    88//         language code on the N line from the start of the debug information.
    9 //
     9// 
    1010// Author           : Peter A. Buhr
    1111// Created On       : Wed Aug  1 10:49:42 2018
    … …  
    1313// Last Modified On : Sat Sep  8 08:40:16 2018
    1414// Update Count     : 97
    15 //
     15// 
    1616
    1717#include <cstdio>                                                                               // perror
    … …  
    4545
    4646        if ( size ) {                                                                           // cannot map 0 sized file
    47                 char * start = (char *)mmap( NULL, size + 2, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 );
     47                char * start = (char *)mmap( NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0 );
    4848                if ( start == (void *)-1 ) { perror( "mmap" ); exit( EXIT_FAILURE ); };
    4949
    … …  
    6565                } // if
    6666
    67                 if ( munmap( start, size + 2 ) ) { perror( "munmap" ); exit( EXIT_FAILURE ); }; // update on disk
     67                if ( munmap( start, size ) ) { perror( "munmap" ); exit( EXIT_FAILURE ); }; // update on disk
    6868        } // if
    6969

  • driver/cfa.cc

    rcdc02f2 ree27df2  
    1010// Created On       : Tue Aug 20 13:44:49 2002
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Sep 14 23:02:59 2018
    13 // Update Count     : 277
     12// Last Modified On : Mon Sep  3 16:47:59 2018
     13// Update Count     : 275
    1414//
    1515
    … …  
    114114        bool std_flag = false;                                                          // -std= flag
    115115        bool noincstd_flag = false;                                                     // -no-include-stdhdr= flag
     116        bool xflag = false;                                                                     // user supplied -x flag
    116117        bool debugging __attribute(( unused )) = false;         // -g flag
    117118        bool m32 = false;                                    // -m32 flag
    … …  
    290291                        } // if
    291292                        nonoptarg = true;
     293                        xflag = false;
    292294                } // if
    293295        } // for
    294296
    295     args[nargs] = "-x";                                                                 // turn off language
     297    args[nargs] = "-x";                                 // turn off language
    296298    nargs += 1;
    297299    args[nargs] = "none";

  • libcfa/src/Makefile.am

    rcdc02f2 ree27df2  
    6868libdeps = $(join \
    6969        $(addsuffix $(DEPDIR)/ , $(dir $(libobjs) ) ), \
    70         $(notdir ${libobjs:.lo=.Plo}) \
     70        $(notdir ${libobjs:.lo=.Po}) \
    7171)
    7272
    73 include $(libdeps)
    74 
    75 $(libdeps):
    76         @mkdir -p $(dir $@)
    77         @echo '#dummy' > $@
     73-include $(libdeps)
    7874
    7975prelude.o : prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@

  • libcfa/src/Makefile.in

    rcdc02f2 ree27df2  
    407407am__v_CFA_0 = @echo "  CFA     " $@;
    408408am__v_CFA_1 =
    409 AM_V_JAVAC = $(am__v_JAVAC_@AM_V@)
    410 am__v_JAVAC_ = $(am__v_JAVAC_@AM_DEFAULT_V@)
    411 am__v_JAVAC_0 = @echo "  JAVAC   " $@;
    412 am__v_JAVAC_1 =
    413 AM_V_GOC = $(am__v_GOC_@AM_V@)
    414 am__v_GOC_ = $(am__v_GOC_@AM_DEFAULT_V@)
    415 am__v_GOC_0 = @echo "  GOC     " $@;
    416 am__v_GOC_1 =
    417 UPPCOMPILE = $(UPPCC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_UPPFLAGS) $(UPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) $(AM_CFLAGS) $(CFLAGS)
    418 AM_V_UPP = $(am__v_UPP_@AM_V@)
    419 am__v_UPP_ = $(am__v_UPP_@AM_DEFAULT_V@)
    420 am__v_UPP_0 = @echo "  UPP     " $@;
    421 am__v_UPP_1 =
    422409lib_LTLIBRARIES = libcfa.la
    423410
    … …  
    466453libdeps = $(join \
    467454        $(addsuffix $(DEPDIR)/ , $(dir $(libobjs) ) ), \
    468         $(notdir ${libobjs:.lo=.Plo}) \
     455        $(notdir ${libobjs:.lo=.Po}) \
    469456)
    470457
    … …  
    922909$(libobjs) : @CFACC@ @CFACPP@ prelude.cfa
    923910
    924 include $(libdeps)
    925 
    926 $(libdeps):
    927         @mkdir -p $(dir $@)
    928         @echo '#dummy' > $@
     911-include $(libdeps)
    929912
    930913prelude.o : prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@
    931         ${AM_V_GEN}@CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree @CONFIG_CFAFLAGS@ -XCFA -l ${<} -c -o ${@}
     914        ${AM_V_GEN}@CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree -XCFA -l ${<} -c -o ${@}
    932915
    933916prelude.lo: prelude.cfa extras.cf gcc-builtins.cf builtins.cf @CFACC@ @CFACPP@
    934917        ${AM_V_GEN}$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile \
    935         @CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree @CONFIG_CFAFLAGS@ -XCFA -l ${<} -c -o ${@}
     918        @CFACC@ ${AM_CFLAGS} ${CFLAGS} -quiet -in-tree -XCFA -l ${<} -c -o ${@}
    936919
    937920#----------------------------------------------------------------------------------------------------------------

  • libcfa/src/bits/locks.hfa

    rcdc02f2 ree27df2  
    3737#endif
    3838
     39#if defined( __i386 ) || defined( __x86_64 ) || defined( __ARM_ARCH )
     40        // Intel recommendation
     41        #define __ALIGN__ __attribute__(( aligned (128) ))
     42#elif defined( __sparc )
     43        #define __ALIGN__ CALIGN
     44#else
     45        #error unsupported architecture
     46#endif
     47
    3948struct __spinlock_t {
    4049        // Wrap in struct to prevent false sharing with debug info
    41         volatile bool lock;
     50        struct {
     51                // Align lock on 128-bit boundary
     52                __ALIGN__ volatile bool lock;
     53        };
    4254        #ifdef __CFA_DEBUG__
    4355                // previous function to acquire the lock
    … …  
    4658                void* prev_thrd;
    4759        #endif
    48 };
     60} __ALIGN__;
    4961
    5062#ifdef __cforall

  • libcfa/src/time.hfa

    rcdc02f2 ree27df2  
    1010// Created On       : Wed Mar 14 23:18:57 2018
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Sep 22 12:25:34 2018
    13 // Update Count     : 643
     12// Last Modified On : Sat Aug 11 13:55:33 2018
     13// Update Count     : 642
    1414//
    1515
    … …  
    2323#include <sys/time.h>                                                                   // timeval
    2424}
    25 #include <time_t.hfa>                                                                   // Duration/Time types
     25#include <time_t.hfa>                                                                           // Duration/Time types
    2626
    2727enum { TIMEGRAN = 1_000_000_000LL };                                    // nanosecond granularity, except for timeval
    … …  
    104104
    105105        timeval ?=?( timeval & t, zero_t ) { return t{ 0 }; }
    106         timeval ?+?( timeval lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_usec + rhs.tv_usec }; }
    107         timeval ?-?( timeval lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_usec - rhs.tv_usec }; }
     106        timeval ?+?( timeval & lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_usec + rhs.tv_usec }; }
     107        timeval ?-?( timeval & lhs, timeval rhs ) { return (timeval)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_usec - rhs.tv_usec }; }
    108108        bool ?==?( timeval lhs, timeval rhs ) { return lhs.tv_sec == rhs.tv_sec && lhs.tv_usec == rhs.tv_usec; }
    109109        bool ?!=?( timeval lhs, timeval rhs ) { return lhs.tv_sec != rhs.tv_sec || lhs.tv_usec != rhs.tv_usec; }
    … …  
    119119
    120120        timespec ?=?( timespec & t, zero_t ) { return t{ 0 }; }
    121         timespec ?+?( timespec lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_nsec + rhs.tv_nsec }; }
    122         timespec ?-?( timespec lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_nsec - rhs.tv_nsec }; }
     121        timespec ?+?( timespec & lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec + rhs.tv_sec, lhs.tv_nsec + rhs.tv_nsec }; }
     122        timespec ?-?( timespec & lhs, timespec rhs ) { return (timespec)@{ lhs.tv_sec - rhs.tv_sec, lhs.tv_nsec - rhs.tv_nsec }; }
    123123        bool ?==?( timespec lhs, timespec rhs ) { return lhs.tv_sec == rhs.tv_sec && lhs.tv_nsec == rhs.tv_nsec; }
    124124        bool ?!=?( timespec lhs, timespec rhs ) { return lhs.tv_sec != rhs.tv_sec || lhs.tv_nsec != rhs.tv_nsec; }

  • src/CodeTools/ResolvProtoDump.cc

    rcdc02f2 ree27df2  
    204204                /// ensures type inst names are uppercase
    205205                static void ti_name( const std::string& name, std::stringstream& ss ) {
    206                         // replace built-in wide character types with named types
    207                         if ( name == "char16_t" || name == "char32_t" || name == "wchar_t" ) {
    208                                 ss << "#" << name;
    209                                 return;
    210                         }
    211 
    212                         // strip leading underscore
    213206                        unsigned i = 0;
    214207                        while ( i < name.size() && name[i] == '_' ) { ++i; }
    … …  
    217210                                return;
    218211                        }
    219 
    220                         std::string stripped = name.substr(i);
    221                         // strip trailing "_generic_" from autogen names (avoids some user-generation issues)
    222                         char generic[] = "_generic_"; size_t n_generic = sizeof(generic) - 1;
    223                         if ( stripped.size() >= n_generic
    224                                         && stripped.substr( stripped.size() - n_generic ) == generic ) {
    225                                 stripped.resize( stripped.size() - n_generic );
    226                         }
    227 
    228                         // uppercase first character
    229                         ss << (char)std::toupper( static_cast<unsigned char>(stripped[0]) )
    230                            << (stripped.c_str() + 1);
     212                        ss << (char)std::toupper( static_cast<unsigned char>(name[i]) )
     213                           << (name.c_str() + i + 1);
    231214                }
    232215
    … …  
    321304                        }
    322305
    323                         // TODO support variable args for functions
    324                         void previsit( VarArgsType* ) {
    325                                 // only include varargs for top level (argument type)
    326                                 if ( depth == 0 ) { ss << "#$varargs"; }
    327                         }
     306                        // TODO support VarArgsType
    328307
    329308                        // replace 0 and 1 with int
    … …  
    418397                        }
    419398
    420                         /// Handle already-resolved variables as type constants
    421                         void previsit( VariableExpr* expr ) {
    422                                 PassVisitor<TypePrinter> tyPrinter{ closed, ss };
    423                                 expr->var->get_type()->accept( tyPrinter );
    424                                 visit_children = false;
    425                         }
    426 
    427399                        /// Calls handled as calls
    428400                        void previsit( UntypedExpr* expr ) {
    … …  
    454426                        }
    455427
    456                         /// Already-resolved calls reduced to their type constant
    457                         void previsit( ApplicationExpr* expr ) {
    458                                 PassVisitor<TypePrinter> tyPrinter{ closed, ss };
    459                                 expr->result->accept( tyPrinter );
     428                        /// Already-resolved calls skipped
     429                        void previsit( ApplicationExpr* ) {
    460430                                visit_children = false;
    461431                        }
    … …  
    562532                                for ( Initializer* it : li->initializers ) {
    563533                                        build( it, ss );
     534                                        ss << ' ';
    564535                                }
    565536                        }
    … …  
    568539                /// Adds an object initializer to the list of expressions
    569540                void build( const std::string& name, Initializer* init, std::stringstream& ss ) {
    570                         ss << "$constructor( &";
     541                        ss << "$constructor( ";
    571542                        rp_name( name, ss );
    572                         ss << ' ';
     543                        ss << "() ";
    573544                        build( init, ss );
    574545                        ss << ')';
    … …  
    705676                }
    706677
    707                 void previsit( AsmStmt* ) {
    708                         // skip asm statements
    709                         visit_children = false;
    710                 }
    711 
    712678                void previsit( Expression* expr ) {
    713679                        std::stringstream ss;
    … …  
    720686                /// Print non-prelude global declarations for resolv proto
    721687                void printGlobals() const {
    722                         std::cout << "#$ptr<T> $addr T" << std::endl;  // &?
     688                        std::cout << "#ptr<T> $addr T" << std::endl;  // &?
    723689                        int i = (int)BasicType::SignedInt;
    724690                        std::cout << i << " $and " << i << ' ' << i << std::endl;  // ?&&?

  • src/SynTree/Constant.cc

    rcdc02f2 ree27df2  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Andrew Beach
    12 // Last Modified On : Fri Spt 28 14:49:00 2018
    13 // Update Count     : 30
     12// Last Modified On : Fri Jul 14 14:50:00 2017
     13// Update Count     : 29
    1414//
    1515
    … …  
    1919
    2020#include "Constant.h"
    21 #include "Expression.h" // for ConstantExpr
    2221#include "Type.h"    // for BasicType, Type, Type::Qualifiers, PointerType
    2322
    … …  
    4948Constant Constant::from_double( double d ) {
    5049        return Constant( new BasicType( Type::Qualifiers(), BasicType::Double ), std::to_string( d ), d );
    51 }
    52 
    53 Constant Constant::from_string( std::string const & str ) {
    54         return Constant(
    55                 new ArrayType(
    56                         noQualifiers,
    57                         new BasicType( Type::Qualifiers( Type::Const ), BasicType::Char ),
    58                         new ConstantExpr( Constant::from_int( str.size() + 1 /* \0 */ )),
    59                         false, false ),
    60                 std::string("\"") + str + "\"", (unsigned long long int)0 );
    6150}
    6251

  • src/SynTree/Constant.h

    rcdc02f2 ree27df2  
    99// Author           : Richard C. Bilson
    1010// Created On       : Mon May 18 07:44:20 2015
    11 // Last Modified By : Andrew Beach
    12 // Last Modified On : Fri Spt 28 14:48:00 2018
    13 // Update Count     : 18
     11// Last Modified By : Peter A. Buhr
     12// Last Modified On : Sat Jul 22 09:54:46 2017
     13// Update Count     : 17
    1414//
    1515
    … …  
    5151        /// generates a floating point constant of the given double
    5252        static Constant from_double( double d );
    53         /// generates an array of chars constant of the given string
    54         static Constant from_string( std::string const & s );
    5553
    5654        /// generates a null pointer value for the given type. void * if omitted.

  • tests/concurrent/coroutineYield.c

    rcdc02f2 ree27df2  
    11#include <fstream.hfa>
    2 #include <kernel.hfa>
     2#include <kernel.hfa>hfa>
    33#include <stdlib.hfa>
    44#include <thread.hfa>

  • tests/concurrent/preempt.c

    rcdc02f2 ree27df2  
    1 #include <kernel.hfa>
     1#include <kernel.hfa>hfa>
    22#include <thread.hfa>
    33#include <time.hfa>

  • tests/concurrent/signal/block.c

    rcdc02f2 ree27df2  
    88
    99#include <fstream.hfa>
    10 #include <kernel.hfa>
     10#include <kernel.hfa>hfa>
    1111#include <monitor.hfa>
    1212#include <stdlib.hfa>

  • tests/concurrent/signal/disjoint.c

    rcdc02f2 ree27df2  
    11#include <fstream.hfa>
    2 #include <kernel.hfa>
     2#include <kernel.hfa>hfa>
    33#include <monitor.hfa>
    44#include <thread.hfa>

  • tests/concurrent/signal/wait.c

    rcdc02f2 ree27df2  
    66
    77#include <fstream.hfa>
    8 #include <kernel.hfa>
     8#include <kernel.hfa>hfa>
    99#include <monitor.hfa>
    1010#include <stdlib.hfa>
Note: See TracChangeset for help on using the changeset viewer.