Index: doc/theses/aaron_moss_PhD/phd/.gitignore =================================================================== --- doc/theses/aaron_moss_PhD/phd/.gitignore (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/.gitignore (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,9 @@ +templates/ +thesis.pdf +thesis.aux +thesis.bbl +thesis.blg +thesis.log +thesis.out +thesis.toc +thesis.lot Index: doc/theses/aaron_moss_PhD/phd/Makefile =================================================================== --- doc/theses/aaron_moss_PhD/phd/Makefile (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/Makefile (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,38 @@ +LATEX = pdflatex -interaction=nonstopmode +BIBTEX = bibtex + +BASE = thesis +DOCUMENT = ${BASE}.pdf +AUX = ${BASE}.aux ${BASE}.bbl ${BASE}.blg ${BASE}.log ${BASE}.out ${BASE}.toc + +SOURCES = ${addsuffix .tex, \ +thesis \ +macros \ +cfa-macros \ +frontpgs \ +introduction \ +background \ +type-environment \ +resolution-heuristics \ +conclusion \ +} + +.PHONY : all rebuild-refs clean wc + +all : ${DOCUMENT} + +clean : + @rm -frv ${DOCUMENT} ${AUX} + +wc : + wc ${SOURCES} + +${DOCUMENT} : ${SOURCES} + ${LATEX} ${BASE} + ${LATEX} ${BASE} + +rebuild-refs : ${SOURCES} aaron-thesis.bib + ${LATEX} ${BASE} + ${BIBTEX} ${BASE} + ${LATEX} ${BASE} + ${LATEX} ${BASE} Index: doc/theses/aaron_moss_PhD/phd/aaron-thesis.bib =================================================================== --- doc/theses/aaron_moss_PhD/phd/aaron-thesis.bib (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/aaron-thesis.bib (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,97 @@ +% Predefined journal names: +% acmcs: Computing Surveys acta: Acta Infomatica +@string{acta="Acta Infomatica"} +% cacm: Communications of the ACM +% ibmjrd: IBM J. Research & Development ibmsj: IBM Systems Journal +% ieeese: IEEE Trans. on Soft. Eng. ieeetc: IEEE Trans. on Computers +% ieeetcad: IEEE Trans. on Computer-Aided Design of Integrated Circuits +% ipl: Information Processing Letters jacm: Journal of the ACM +% jcss: J. Computer & System Sciences scp: Science of Comp. Programming +% sicomp: SIAM J. on Computing tocs: ACM Trans. on Comp. Systems +% tods: ACM Trans. on Database Sys. tog: ACM Trans. on Graphics +% toms: ACM Trans. on Math. Software toois: ACM Trans. on Office Info. Sys. +% toplas: ACM Trans. on Prog. Lang. & Sys. +% tcs: Theoretical Computer Science +@string{ieeepds="IEEE Transactions on Parallel and Distributed Systems"} +@string{ieeese="IEEE Transactions on Software Engineering"} +@string{spe="Software---\-Practice and Experience"} +@string{ccpe="Concurrency and Computation: Practice and Experience"} +@string{sigplan="SIGPLAN Notices"} +@string{joop="Journal of Object-Oriented Programming"} +@string{popl="Conference Record of the ACM Symposium on Principles of Programming Languages"} +@string{osr="Operating Systems Review"} +@string{pldi="Programming Language Design and Implementation"} +@string{toplas="Transactions on Programming Languages and Systems"} +@string{mathann="Mathematische Annalen"} + +@mastersthesis{Bilson03, + keywords = {Cforall, parametric polymorphism, overloading}, + contributer = {pabuhr@plg}, + author = {Richard C. Bilson}, + title = {Implementing Overloading and Polymorphism in \textsf{C}$\mathbf{\forall}$}, + school = {School of Computer Science, University of Waterloo}, + year = 2003, + address = {Waterloo, Ontario, Canada, N2L 3G1}, + note = {\href{http://plg.uwaterloo.ca/theses/BilsonThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-BilsonThesis.pdf}}, +} + +@article{Buhr94a, + keywords = {assignment, parameter passing, multiple assignment}, + contributer = {pabuhr@plg}, + author = {P. A. Buhr and David Till and C. R. Zarnke}, + title = {Assignment as the Sole Means of Updating Objects}, + journal = spe, + month = sep, + year = 1994, + volume = 24, + number = 9, + pages = {835-870}, +} + +@mastersthesis{Delisle18, + author = {Thierry Delisle }, + title = {Concurrency in \textsf{C}$\mathbf{\forall}$}, + school = {School of Computer Science, University of Waterloo}, + year = 2018, + address = {Waterloo, Ontario, Canada, N2L 3G1}, + note = {\href{https://uwspace.uwaterloo.ca/handle/10012/12888}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-12888}}, +} + +@phdthesis{Ditchfield92, + keywords = {C, parametric polymorphism, overloading}, + contributer = {pabuhr@plg}, + author = {Glen Jeffrey Ditchfield}, + title = {Contextual Polymorphism}, + school = {Department of Computer Science, University of Waterloo}, + year = 1992, + address = {Waterloo, Ontario, Canada, N2L 3G1}, + note = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}} +} + +@article{Moss18, + keywords = {concurrency, C++}, + contributer = {pabuhr@plg}, + author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, + title = {\textsf{C}$\mathbf{\forall}$ : Adding Modern Programming Language Features to C}, + year = 2018, + journal = spe, + note = {Accepted, to appear}, +} + +@mastersthesis{Schluntz17, + keywords = {constructors, destructors, tuples}, + author = {Robert Schluntz}, + title = {Resource Management and Tuples in \textsf{C}$\mathbf{\forall}$}, + school = {School of Computer Science, University of Waterloo}, + year = 2017, + address = {Waterloo, Ontario, Canada, N2L 3G1}, + note = {\href{https://uwspace.uwaterloo.ca/handle/10012/11830}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-11830}}, +} + +@misc{TIOBE, + contributer = {pabuhr@plg}, + key = {TIOBE Index}, + title = {{TIOBE} Index}, + howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}}, + optnote = {Accessed: 2018-08}, +} Index: doc/theses/aaron_moss_PhD/phd/background.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/background.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/background.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,221 @@ +\chapter{Background} + +\CFA{} adds a number of features to C, some of them providing significant increases to the expressive power of the language, but all designed to maintain the existing procedural programming paradigm of C and to be as orthogonal as possible to each other. +To provide background for the contributions in subsequent chapters, this chapter provides a summary of the features of \CFA{} at the time this work was conducted. + +The core design of \CFA{} is laid out in Glen Ditchfield's 1992 PhD thesis, \emph{Contextual Polymorphism}\cite{Ditchfield92}; in that thesis, Ditchfield presents the theoretical underpinnings of the \CFA{} polymorphism model. +Building on Ditchfield's design for contextual polymorphism as well as KW-C\cite{Buhr94a}, an earlier set of (largely syntactic) extensions to C, Richard Bilson\cite{Bilson03} built the first version of the \CFA{} compiler, \CFACC{}, in the early 2000's. +This early \CFACC{} provided basic functionality, but incorporated a number of poor algorithmic choices due to a rushed implementation time frame, and as such lacked the runtime performance required for practical use; this thesis is substantially concerned with rectifying those deficits. + +The \CFA{} project was revived in 2015 with the intention of building a production-ready language and compiler; at the time of this writing, both \CFA{} and \CFACC{} have been under active development continuously since. +As this development has been proceeding concurrently with the work described in this thesis, the state of \CFA{} has been somewhat of a moving target; however, Moss~\etal\cite{Moss18} provides a reasonable summary of the current design. +Notable features added during this period include generic types (Chapter~\ref{generic-chap}), constructors and destructors\cite{Schluntz17}, improved support for tuples\cite{Schluntz17}, reference types\cite{Moss18}, first-class concurrent and parallel programming support\cite{Delisle18}, as well as numerous pieces of syntactic sugar and the start of an idiomatic standard library\cite{Moss18}. + +\section{\CFA{} Features} + +The selection of features presented in this chapter are chosen to elucidate the design constraints of the work presented in this thesis. +In some cases the interactions of multiple features make this design a significantly more complex problem than any individual feature would; in other cases a feature that does not by itself add any complexity to expression resolution triggers previously rare edge cases more frequently. + +\subsection{Procedural Paradigm} + +It is important to note that \CFA{} is not an object-oriented language. +This is a deliberate choice intended to maintain the applicability of the mental model and language idioms already possessed by C programmers. +This choice is in marked contrast to \CC{}, which, though it has backward-compatibility with C on the source code level, is a much larger and more complex language, and requires extensive developer re-training before they can write idiomatic, efficient code in \CC{}'s object-oriented paradigm. + +\CFA{} does have a system of implicit type conversions derived from C's ``usual arithmetic conversions''; while these conversions may be thought of as something like an inheritance hierarchy, the underlying semantics are significantly different and such an analogy is loose at best. +Particularly, \CFA{} has no concept of \emph{subclass}, and thus no need to integrate an inheritance-based form of polymorphism with its parametric and overloading-based polymorphism. +The graph structure of the \CFA{} type conversions is also markedly different than an inheritance hierarchy; it has neither a top nor a bottom type, and does not satisfy the lattice properties typical of inheritance hierarchies. + +Another aspect of \CFA{}'s procedural paradigm is that it retains C's translation-unit-based encapsulation model, rather than class-based encapsulation such as in \CC{}. +This choice implies that that separate compilation must be maintained to allow headers to act as an encapsulation boundary, rather than the header-only libraries used by \CC{} templates. + +\subsection{Name Overloading} \label{overloading-sec} + +In C, no more than one variable or function in the same scope may share the same name\footnote{Technically, C has multiple separated namespaces, one holding \lstinline{struct}, \lstinline{union}, and \lstinline{enum} tags, one holding labels, one holding \lstinline{typedef} names, variable, function, and enumerator identifiers, and one for each \lstinline{struct} and \lstinline{union} type holding the field names\cit{}.}, and variable or function declarations in inner scopes with the same name as a declaration in an outer scope hide the outer declaration. +This restriction makes finding the proper declaration to match to a variable expression or function application a simple matter of symbol-table lookup, which can be easily and efficiently implemented. +\CFA{}, on the other hand, allows overloading of variable and function names so long as the overloaded declarations do not have the same type, avoiding the multiplication of variable and function names for different types common in the C standard library, as in the following example: + +\begin{cfa} +#include + +const int max = INT_MAX; $\C[1.75in]{// (1)}$ +const double max = DBL_MAX; $\C[1.75in]{// (2)}$ +int max(int a, int b) { return a < b ? b : a; } $\C[1.75in]{// (3)}$ +double max(double a, double b) { return a < b ? b : a; } $\C[1.75in]{// (4)}$ + +max( 7, -max ); $\C[3.75in]{// uses (3) and (1), by matching int from 7}$ +max( max, 3.14 ); $\C[3.75in]{// uses (4) and (2), by matching double from 3.14}$ +max( max, -max ); $\C[3.75in]{// ERROR, ambiguous}$ +int m = max( max, -max ); $\C[3.75in]{// uses (3) and (1) twice, by matching return type}$ +\end{cfa} + +While the wisdom of giving both the maximum value of a type and the function to take the maximum of two values the same name is debatable, \eg{} some developers may prefer !MAX! for the former, the guiding philosophy of \CFA{} is ``describe, don't prescribe'' --- we prefer to trust programmers with powerful tools, and there is no technical reason to restrict overloading between variables and functions. +However, the expressivity of \CFA{}'s name overloading has the consequence that simple table lookup is insufficient to match identifiers to declarations, and a type-matching algorithm must be part of expression resolution. + +\subsubsection{Operator Overloading} + +C does allow name overloading in one context: operator overloading. +From the perspective of the type system, there is nothing special about operators as opposed to other functions, nor is it desirable to restrict the clear and readable syntax of operators to only the built-in types. +For these reasons, \CFA{} also allows overloading of operators by writing specially-named functions where !?! stands in for the operands\footnote{This example uses \CFA{}'s reference types, described in Section~\ref{type-features-sec}}: + +\begin{cfa} +struct counter { int x; }; + +counter& `++?`(counter& c) { ++c.x; return c; } $\C{// pre-increment}$ +counter `?++`(counter& c) { $\C{// post-increment}$ + counter tmp = c; ++c; return tmp; +} +bool `?value; +} +\end{cfa} + +In the example above, !(list_iterator, int)! satisfies !pointer_like! by the user-defined dereference function, and !(list_iterator, list)! also satisfies !pointer_like! by the built-in dereference operator for pointers. +Given a declaration !list_iterator it!, !*it! can be either an !int! or a !list!, with the meaning disambiguated by context (\eg{} !int x = *it;! interprets !*it! as !int!, while !(*it).value = 42;! interprets !*it! as !list!). +While a nominal-inheritance system with associated types could model one of those two relationships by making !El! an associated type of !Ptr! in the !pointer_like! implementation, few such systems could model both relationships simultaneously. + +The flexibility of \CFA{}'s implicit trait-satisfaction mechanism provides programmers with a great deal of power, but also blocks some optimization approaches for expression resolution. +The ability of types to begin or cease to satisfy traits when declarations go into or out of scope makes caching of trait satisfaction judgements difficult, and the ability of traits to take multiple type parameters can lead to a combinatorial explosion of work in any attempt to pre-compute trait satisfaction relationships. + +\subsection{Implicit Conversions} + +In addition to the multiple interpretations of an expression produced by name overloading and polymorphic functions, for backward compatibility \CFA{} must support all of the implicit conversions present in C, producing further candidate interpretations for expressions. +As mentioned above, C does not have an inheritance hierarchy of types, but the C standard's rules for the ``usual arithmetic conversions''\cit{} define which of the built-in tyhpes are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type. +\CFA{} adds to the usual arithmetic conversions rules defining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg{} !int! to !char!, but more expensive than any \emph{safe} (widening) conversion, \eg{} !int! to !double!. +One contribution of this thesis, discussed in Section \TODO{add to resolution chapter}, is a number of refinements to this cost model to more efficiently resolve polymorphic function calls. + +The expression resolution problem which is the focus of Chapter~\ref{resolution-chap} is to find the unique minimal-cost interpretation of each expression in the program, where all identifiers must be matched to a declaration, and implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression. +While semantically valid \CFA{} code always has such a unique minimal-cost interpretation, \CFACC{} must also be able to detect and report as errors expressions which have either no interpretation or multiple ambiguous minimal-cost interpretations. +Note that which subexpression interpretation is minimal-cost may require contextual information to disambiguate. +For instance, in the example in Section~\ref{overloading-sec}, !max(max, -max)! cannot be unambiguously resolved, but !int m = max(max, -max)! has a single minimal-cost resolution. +While the interpretation !int m = (int)max((double)max, -(double)max)! is also a valid interpretation, it is not minimal-cost due to the unsafe cast from the !double! result of !max! to the !int!\footnote{The two \lstinline{double} casts function as type ascriptions selecting \lstinline{double max} rather than casts from \lstinline{int max} to \lstinline{double}, and as such are zero-cost.}. +These contextual effects make the expression resolution problem for \CFA{} both theoretically and practically difficult, but the observation driving the work in Chapter~\ref{resolution-chap} is that of the many top-level expressions in a given program, most will likely be straightforward and idiomatic so that programmers writing and maintaining the code can easily understand them; it follows that effective heuristics for common cases can bring down compiler runtime enough that a small proportion of harder-to-resolve expressions should not increase compiler runtime or memory usage inordinately. + +\subsection{Type Features} \label{type-features-sec} + +\subsubsection{Reference Types} + +% TODO mention contribution on reference rebind + +\subsubsection{Lifetime Management} + +\subsubsection{0 and 1 Literals} Index: doc/theses/aaron_moss_PhD/phd/cfa-macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/cfa-macros.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,69 @@ +\usepackage{listings} + +% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore +% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR +% AFTER HYPERREF. +%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}} +\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} + +\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work +%\renewcommand*{\thefootnote}{\fnsymbol{footnote}} + +\makeatletter +% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for +% use rather than use \parident directly. +\newlength{\parindentlnth} +\setlength{\parindentlnth}{\parindent} + +\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{\lst@basicstyle{#1}}}} +\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}} +\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}} + +\newcommand{\C}[2][2in]{\hfill\makebox[#1][l]{\LstCommentStyle{#2}}} + +% CFA programming language, based on ANSI C (with some gcc additions) +\lstdefinelanguage{CFA}[ANSI]{C}{ + morekeywords={ + _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__, + auto, bool, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__, + coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally, + __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__, + inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or, + otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread, + _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__, + virtual, __volatile, __volatile__, waitfor, when, with, zero_t}, + moredirectives={defined,include_next}% +} + +\lstset{ +language=CFA, +columns=fullflexible, +basicstyle=\linespread{0.9}\sf, % reduce line spacing and use sanserif font +stringstyle=\tt, % use typewriter font +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, % +showstringspaces=false, % do not show spaces with cup +showlines=true, % show blank lines at end of code +aboveskip=4pt, % spacing above/below code block +belowskip=3pt, +% replace/adjust listing characters that look bad in sanserif +literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1 + {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 + {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1 + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2, +moredelim=**[is][\color{red}]{`}{`}, +}% lstset + +\lstnewenvironment{cfa}[1][] +{\lstset{#1}} +{} +\lstnewenvironment{C++}[1][] % use C++ style +{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}} +{} + +% inline code !...! +\lstMakeShortInline! + Index: doc/theses/aaron_moss_PhD/phd/conclusion.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/conclusion.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/conclusion.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,3 @@ +\chapter{Conclusion} + +Wrap it up --- Done, done done. Index: doc/theses/aaron_moss_PhD/phd/frontpgs.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/frontpgs.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/frontpgs.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,174 @@ +% T I T L E P A G E +% ------------------- + +% The title page is counted as page `i' but we need to suppress the +% page number. Also, we don't want any headers or footers. +\pagestyle{empty} +\pagenumbering{roman} + +% The contents of the title page are specified in the "titlepage" +% environment. +\begin{titlepage} + \begin{center} + \vspace*{1.0cm} + + \Huge + {\bf \CFA{} Type System Implementation } + + \vspace*{1.0cm} + + \normalsize + by \\ + + \vspace*{1.0cm} + + \Large + Aaron Moss \\ + + \vspace*{3.0cm} + + \normalsize + A thesis \\ + presented to the University of Waterloo \\ + in fulfillment of the \\ + thesis requirement for the degree of \\ + Doctor of Philosophy \\ + in \\ + Computer Science \\ + + \vspace*{2.0cm} + + Waterloo, Ontario, Canada, 2019 \\ + + \vspace*{1.0cm} + + \copyright\ Aaron Moss 2019 \\ + \end{center} +\end{titlepage} + +% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii' +\pagestyle{plain} +\setcounter{page}{2} + +\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed. +% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary. + +% E X A M I N I N G C O M M I T T E E +% ------------------------------------- + +\begin{center}\textbf{Examining Committee Membership}\end{center} + \noindent + The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote. + \bigskip + +% \noindent +% \begin{tabbing} +% Internal-External Member: \= \kill % using longest text to define tab length +% External Examiner: \> Bruce Bruce \\ +% \> Professor, Dept. of Philosophy of Zoology, University of Wallamaloo \\ +% \end{tabbing} +% \bigskip + + \noindent + \begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + Supervisor: \> Peter Buhr \\ + \> Professor, School of Computer Science, University of Waterloo \\ + \end{tabbing} + \bigskip + + \noindent + \begin{tabbing} + Internal-External Member: \= \kill % using longest text to define tab length + Internal Members: \> Gregor Richards \\ + \> Professor, School of Computer Science, University of Waterloo \\ + \> Ond\v{r}ej Lhot\a'ak \\ + \> Professor, School of Computer Science, University of Waterloo \\ + \end{tabbing} +% \bigskip + +% \noindent +% \begin{tabbing} +% Internal-External Member: \= \kill % using longest text to define tab length +% Internal-External Member: \> Deepa Thotta \\ +% \> Professor, Dept. of Philosophy, University of Waterloo \\ +% \end{tabbing} +% \bigskip + +% \noindent +% \begin{tabbing} +% Internal-External Member: \= \kill % using longest text to define tab length +% Other Member(s): \> Leeping Fang \\ +% \> Professor, Dept. of Fine Art, University of Waterloo \\ +% \end{tabbing} + + \cleardoublepage + +% D E C L A R A T I O N P A G E +% ------------------------------- + % The following is a sample Delaration Page as provided by the GSO + % December 13th, 2006. It is designed for an electronic thesis. + \noindent +I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. + + \bigskip + + \noindent +I understand that my thesis may be made electronically available to the public. + +\cleardoublepage + +% A B S T R A C T +% --------------- + +\begin{center}\textbf{Abstract}\end{center} + +This is the abstract. + +\cleardoublepage + +% A C K N O W L E D G E M E N T S +% ------------------------------- + +% \begin{center}\textbf{Acknowledgements}\end{center} + +% I would like to thank all the little people who made this thesis possible. +% \cleardoublepage + +% D E D I C A T I O N +% ------------------- + +% \begin{center}\textbf{Dedication}\end{center} + +% This is dedicated to the one I love. +% \cleardoublepage + +% T A B L E O F C O N T E N T S +% --------------------------------- +\renewcommand\contentsname{Table of Contents} +\tableofcontents +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% L I S T O F T A B L E S +% --------------------------- +\addcontentsline{toc}{chapter}{List of Tables} +\listoftables +\cleardoublepage +\phantomsection % allows hyperref to link to the correct page + +% 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 + +% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) +% ----------------------------- +% \printglossaries +% \cleardoublepage +% \phantomsection % allows hyperref to link to the correct page + +% Change page numbering back to Arabic numerals +\pagenumbering{arabic} Index: doc/theses/aaron_moss_PhD/phd/generic-types.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,8 @@ +\chapter{Generic Types} +\label{generic-chap} + +Talk about generic types. Pull from Moss~\etal\cite{Moss18}. + +% TODO mention impetus for zero_t design + +% TODO mention use in tuple-type implementation Index: doc/theses/aaron_moss_PhD/phd/introduction.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/introduction.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/introduction.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,37 @@ +\chapter{Introduction} + +The C programming language has had a wide-ranging impact on the design of software and programming languages. +In the 30 years since its first standardization, it has consistently been one of the most popular programming languages, with millions of lines of C code still in active use, and tens of thousands of trained programmers producing it. The TIOBE index\cite{TIOBE} tracks popularity of programming languages over time, and C has never dropped below second place: + +\begin{table}[h] +\label{tiobe-table} +\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years} + +\centering +\begin{tabular}{@{}cccccccc@{}} + & 2018 & 2013 & 2008 & 2003 & 1998 & 1993 & 1988 \\ +Java & 1 & 2 & 1 & 1 & 18 & -- & -- \\ +\textbf{C} & \textbf{2} & \textbf{1} & \textbf{2} & \textbf{2} & \textbf{1} & \textbf{1} & \textbf{1} \\ +\CC{} & 3 & 4 & 3 & 3 & 2 & 2 & 5 \\ +Python & 4 & 7 & 6 & 11 & 22 & 17 & -- \\ +\Csharp{} & 5 & 5 & 7 & 8 & -- & -- & -- \\ +\end{tabular} +\end{table} + +The impact of C on programming language design is also obvious from Table~\ref{tiobe-table}; with the exception of Python, all of the top five languages use C-like syntax and procedural control structures. +\CC{} is even a largely backwards-compatible extension of C, with development dating back nearly as far as C itself. +Though its lasting popularity and wide impact on programming language design point to the continued relevance of C, they also highlight the widespread desire of programmers for languages with more expressive power and programmer-friendly features; accommodating both low-impact maintenance of legacy C code and low-effort development of the software of the future is a difficult task for a single programming language. + +\CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or \CFL{}.} is an evolutionary modernization of the C programming language which aims to fulfill both these ends well. +\CFA{} both fixes existing design problems and adds multiple new features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others. +The new features make \CFA{} more powerful and expressive than C, while maintaining strong backward-compatibility with both C code and the procedural paradigm expected by C programmers. +However, these new features do impose a compile-time cost, particularly in the expression resolver, which must evaluate the typing rules of a significantly more complex type-system. + +This thesis is focused on making \CFA{} a more powerful and expressive language, both by adding new features to the \CFA{} type system and ensuring that both added and existing features can be efficiently implemented in \CFACC{}, the \CFA{} reference compiler. +Particular contributions of this work include design and implementation of +parametric-polymorphic (``generic'') types in a manner compatible with the existing polymorphism design of \CFA{} (Chapter~\ref{generic-chap}), a type environment data structure based on a novel variant of the union-find algorithm (Chapter~\ref{env-chap}), and a new expression resolution algorithm designed to quickly locate the optimal declarations for a \CFA{} expression (Chapter~\ref{resolution-chap}). +This expression resolution algorithm was designed with the aid of a purpose-built prototype system which encapsulates the essential aspects of the \CFA{} type system without incurring the technical debt of the existing system or the friction-inducing necessity of maintaining a working compiler; the goal of this prototype system was to discover effective heuristics to avoid performing unnecessary work in the process of locating the optimal \CFA{} expression resolution. + +Though the direction and validation of this work was fairly narrowly focused on the \CFA{} programming language, the tools used and results obtained should be of interest to a wider compiler and programming language design community. +In particular, with the addition of \emph{concepts} in \CCtwenty{}, conforming \CC{} compilers must support a model of type assertions very similar to that in \CFA{}, and the algorithmic techniques used in the expression resolution algorithm presented here may prove useful. +Type environments are also widely modelled in compiler implementations, particularly of functional languages, though also increasingly commonly in other languages (such as Rust) which perform type inference; the type environment presented here may be useful to those language implementers. Index: doc/theses/aaron_moss_PhD/phd/macros.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/macros.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/macros.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,22 @@ +% Common macros for this thesis +% Based on LaTeXmacros/common.tex + +\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}} % Cforall symbolic name +\newcommand{\CFA}{\protect\CFAIcon} % safe for section/caption +\newcommand{\CFL}{\textrm{Cforall}} % Cforall symbolic name +\newcommand{\CFACC}{\texttt{cfa-cc}} % Cforall compiler +\newcommand{\Celeven}{\textrm{C11}} % C11 symbolic name +\newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ symbolic name +\newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11} % C++11 symbolic name +\newcommand{\CCfourteen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}14} % C++14 symbolic name +\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{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name + +\newcommand{\ie}{\textit{i.e.}} +\newcommand{\eg}{\textit{e.g.}} +\newcommand{\etc}{\textit{etc.}} +\newcommand{\etal}{\textit{et~al.}} + +\newcommand{\TODO}[1]{\textbf{TODO:} \textit{#1}} +\newcommand{\cit}{\textsuperscript{[citation needed]}} Index: doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,6 @@ +\chapter{Resolution Heuristics} +\label{resolution-chap} + +Talk about the resolution heuristics. This is the bulk of the thesis. + +% Discuss changes to cost model, as promised in Ch. 2 Index: doc/theses/aaron_moss_PhD/phd/thesis.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/thesis.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/thesis.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,151 @@ +% Specify the document class, default style attributes, and page dimensions +% For hyperlinked PDF, suitable for viewing on a computer, use this: +\documentclass[letterpaper,12pt,titlepage,oneside,final]{book} + +% For PDF, suitable for double-sided printing, change the PrintVersion variable below +% to "true" and use this \documentclass line instead of the one above: +%\documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book} + +% common macros for this thesis +\input{macros} + +\newcommand{\href}[1]{#1} % does nothing, but defines the command so the +% print-optimized version will ignore \href tags (redefined by hyperref pkg). + +% This package allows if-then-else control structures. +\usepackage{ifthen} +\newboolean{PrintVersion} +\setboolean{PrintVersion}{false} +% CHANGE THIS VALUE TO "true" as necessary, to improve printed results for hard copies +% by overriding some options of the hyperref package below. + +\usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments +\usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver + +% Hyperlinks make it very easy to navigate an electronic document. +% In addition, this is where you should specify the thesis title +% and author as they appear in the properties of the PDF document. +% 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 +% N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing. + +\hypersetup{ + plainpages=false, % needed if Roman numbers in frontpages + unicode=false, % non-Latin characters in Acrobat’s bookmarks + pdftoolbar=true, % show Acrobat’s toolbar? + pdfmenubar=true, % show Acrobat’s menu? + pdffitwindow=false, % window fit to page when opened + pdfstartview={FitH}, % fits the width of the page to the window + pdftitle={Cforall\ Type\ System\ Implementation}, % title + pdfauthor={Aaron\ Moss}, % author + pdfsubject={Cforall}, % subject +% pdfkeywords={keyword1} {key2} {key3}, % list of keywords, and uncomment this line if desired + pdfnewwindow=true, % links in new window + colorlinks=true, % false: boxed links; true: colored links + linkcolor=blue, % color of internal links + citecolor=green, % color of links to bibliography + filecolor=magenta, % color of file links + urlcolor=cyan % color of external links +} +\ifthenelse{\boolean{PrintVersion}}{ % for improved print quality, change some hyperref options +\hypersetup{ % override some previously defined hyperref options +% colorlinks,% + citecolor=black,% + filecolor=black,% + linkcolor=black,% + urlcolor=black} +}{} % end of ifthenelse (no else) + +\input{cfa-macros} % must be loaded after hyperref + +% \usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package + +% Setting up the page margins... +% uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the +% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter +% margin (on binding side). While this is not an issue for electronic +% viewing, a PDF may be printed, and so we have the same page layout for +% both printed and electronic versions, we leave the gutter margin in. +% Set margins to minimum permitted by uWaterloo thesis regulations: +\setlength{\marginparwidth}{0pt} % width of margin notes +% N.B. If margin notes are used, you must adjust \textwidth, \marginparwidth +% and \marginparsep so that the space left between the margin notes and page +% edge is less than 15 mm (0.6 in.) +\setlength{\marginparsep}{0pt} % width of space between body text and margin notes +\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all +% even-numbered pages when the "twoside" printing option is selected +\setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages +% when "oneside" printing is selected, and to the left of all odd-numbered +% pages when "twoside" printing is selected +\setlength{\textwidth}{6.375in} % assuming US letter paper (8.5 in. x 11 in.) and +% side margins as above +\raggedbottom + +% The following statement specifies the amount of space between +% paragraphs. Other reasonable specifications are \bigskipamount and \smallskipamount. +\setlength{\parskip}{\medskipamount} + +% The following statement controls the line spacing. The default +% spacing corresponds to good typographic conventions and only slight +% changes (e.g., perhaps "1.2"), if any, should be made. +\renewcommand{\baselinestretch}{1} % this is the default line space setting + +% By default, each chapter will start on a recto (right-hand side) +% page. We also force each section of the front pages to start on +% a recto page by inserting \cleardoublepage commands. +% In many cases, this will require that the verso page be +% blank and, while it should be counted, a page number should not be +% printed. The following statements ensure a page number is not +% printed on an otherwise blank verso page. +\let\origdoublepage\cleardoublepage +\newcommand{\clearemptydoublepage}{% + \clearpage{\pagestyle{empty}\origdoublepage}} +\let\cleardoublepage\clearemptydoublepage + +%====================================================================== +% L O G I C A L D O C U M E N T +%====================================================================== +\begin{document} + +%---------------------------------------------------------------------- +% FRONT MATERIAL +%---------------------------------------------------------------------- +\input{frontpgs} + +%---------------------------------------------------------------------- +% MAIN BODY +%---------------------------------------------------------------------- +\input{introduction} +\input{background} +\input{generic-types} +\input{type-environment} +\input{resolution-heuristics} +\input{conclusion} + +% B I B L I O G R A P H Y +% ----------------------- + +% The following statement selects the style to use for references. It controls the sort order of the entries in the bibliography and also the formatting for the in-text labels. +\bibliographystyle{plain} +% This specifies the location of the file containing the bibliographic information. +% It assumes you're using BibTeX (if not, why not?). +\cleardoublepage % This is needed if the book class is used, to place the anchor in the correct page, + % because the bibliography will start on its own page. + % Use \clearpage instead if the document class uses the "oneside" argument +\phantomsection % With hyperref package, enables hyperlinking from the table of contents to bibliography +% The following statement causes the title "References" to be used for the bibliography section: +\renewcommand*{\bibname}{References} + +% Add the References to the Table of Contents +\addcontentsline{toc}{chapter}{\textbf{References}} + +\bibliography{aaron-thesis} +% Tip 5: You can create multiple .bib files to organize your references. +% Just list them all in the \bibliogaphy command, separated by commas (no spaces). + +% The following statement causes the specified references to be added to the bibliography% even if they were not +% cited in the text. The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional). +% \nocite{*} + +\end{document} Index: doc/theses/aaron_moss_PhD/phd/type-environment.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/type-environment.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) +++ doc/theses/aaron_moss_PhD/phd/type-environment.tex (revision 67982887d6d6ffea6e1c510c7ded3be0a1acea1f) @@ -0,0 +1,4 @@ +\chapter{Type Environment} +\label{env-chap} + +Talk about the type environment data structure. Pull from your presentation.