Changeset 546b51e


Ignore:
Timestamp:
Aug 29, 2018, 3:22:52 PM (6 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
42655e8, f8b69da7
Parents:
c9c9ac4f (diff), 514247d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

Location:
doc/theses/aaron_moss/phd
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/aaron_moss/phd/.gitignore

    rc9c9ac4f r546b51e  
     1templates/
    12thesis.pdf
    23thesis.aux
    … …  
    67thesis.out
    78thesis.toc
    8 templates/
     9thesis.lot

  • doc/theses/aaron_moss/phd/Makefile

    rc9c9ac4f r546b51e  
    66AUX = ${BASE}.aux ${BASE}.bbl ${BASE}.blg ${BASE}.log ${BASE}.out ${BASE}.toc
    77
    8 .PHONY : all rebuild-refs clean
     8SOURCES = ${addsuffix .tex, \
     9thesis \
     10frontpgs \
     11introduction \
     12background \
     13type-environment \
     14resolution-heuristics \
     15conclusion \
     16}
     17
     18.PHONY : all rebuild-refs clean wc
    919
    1020all : ${DOCUMENT}
    … …  
    1323        @rm -frv ${DOCUMENT} ${AUX}
    1424
    15 ${DOCUMENT} :
     25wc :
     26        wc ${SOURCES}
     27
     28${DOCUMENT} : ${SOURCES}
    1629        ${LATEX} ${BASE}
    1730        ${LATEX} ${BASE}
    1831
    19 rebuild-refs :
     32rebuild-refs : ${SOURCES} aaron-thesis.bib
    2033        ${LATEX} ${BASE}
    2134        ${BIBTEX} ${BASE}

  • doc/theses/aaron_moss/phd/aaron-thesis.bib

    rc9c9ac4f r546b51e  
    3636}
    3737
     38@article{Buhr94a,
     39    keywords    = {assignment, parameter passing, multiple assignment},
     40    contributer = {pabuhr@plg},
     41    author      = {P. A. Buhr and David Till and C. R. Zarnke},
     42    title       = {Assignment as the Sole Means of Updating Objects},
     43    journal     = spe,
     44    month       = sep,
     45    year        = 1994,
     46    volume      = 24,
     47    number      = 9,
     48    pages       = {835-870},
     49}
     50
     51@mastersthesis{Delisle18,
     52    author      = {Thierry Delisle },
     53    title       = {Concurrency in \textsf{C}$\mathbf{\forall}$},
     54    school      = {School of Computer Science, University of Waterloo},
     55    year        = 2018,
     56    address     = {Waterloo, Ontario, Canada, N2L 3G1},
     57    note        = {\href{https://uwspace.uwaterloo.ca/handle/10012/12888}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-12888}},
     58}
     59
    3860@phdthesis{Ditchfield92,
    3961    keywords    = {C, parametric polymorphism, overloading},
    … …  
    5678    note        = {Accepted, to appear},
    5779}
     80
     81@mastersthesis{Schluntz17,
     82    keywords    = {constructors, destructors, tuples},
     83    author      = {Robert Schluntz},
     84    title       = {Resource Management and Tuples in \textsf{C}$\mathbf{\forall}$},
     85    school      = {School of Computer Science, University of Waterloo},
     86    year        = 2017,
     87    address     = {Waterloo, Ontario, Canada, N2L 3G1},
     88    note        = {\href{https://uwspace.uwaterloo.ca/handle/10012/11830}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-11830}},
     89}
     90
     91@misc{TIOBE,
     92    contributer = {pabuhr@plg},
     93    key         = {TIOBE Index},
     94    title       = {{TIOBE} Index},
     95    howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}},
     96    optnote     = {Accessed: 2018-08},
     97}

  • doc/theses/aaron_moss/phd/background.tex

    rc9c9ac4f r546b51e  
    11\chapter{Background}
    22
    3 This is the background. Basically, need to cite Ditchfield\cite{Ditchfield92}, Bilson\cite{Bilson03}, and Moss~\etal\cite{Moss18}
     3\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 with each other.
     4To 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.
     5
     6The core design of \CFA{} is laid out in Glen Ditchfield's 1992 PhD thesis, \emph{Contextual Polymorphism}\cite{Ditchfield92}; in that thesis, Ditchfield lays out the theoretical underpinnings of the \CFA{} polymorphism model.
     7Building 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.
     8This 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.
     9
     10The \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.
     11As 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 of \CFA{}.
     12Notable 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}.
     13

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

    rc9c9ac4f r546b51e  
    153153% L I S T   O F   T A B L E S
    154154% ---------------------------
    155 % \addcontentsline{toc}{chapter}{List of Tables}
    156 % \listoftables
    157 % \cleardoublepage
    158 % \phantomsection               % allows hyperref to link to the correct page
     155\addcontentsline{toc}{chapter}{List of Tables}
     156\listoftables
     157\cleardoublepage
     158\phantomsection         % allows hyperref to link to the correct page
    159159
    160160% L I S T   O F   F I G U R E S

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

    rc9c9ac4f r546b51e  
    11\chapter{Generic Types}
     2\label{generic-chap}
    23
    34Talk about generic types. Pull from Moss~\etal\cite{Moss18}.

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

    rc9c9ac4f r546b51e  
    11\chapter{Introduction}
    22
    3 This is the introduction.
     3The C programming language has had a wide-ranging impact on the design of software and programming languages.
     4In 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:
     5
     6\begin{table}
     7\label{tiobe-table}
     8\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years}
     9
     10\centering
     11\begin{tabular}{@{}cccccccc@{}}
     12        & 2018  & 2013  & 2008  & 2003  & 1998  & 1993  & 1988  \\
     13Java            & 1             & 2             & 1             & 1             & 18    & --    & --    \\
     14\textbf{C}      & \textbf{2} & \textbf{1} & \textbf{2} & \textbf{2} & \textbf{1} & \textbf{1} & \textbf{1} \\
     15\CC{}           & 3             & 4             & 3             & 3             & 2             & 2             & 5             \\
     16Python          & 4             & 7             & 6             & 11    & 22    & 17    & --    \\
     17\Csharp{}       & 5             & 5             & 7             & 8             & --    & --    & --    \\
     18\end{tabular}
     19\end{table}
     20
     21The 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.
     22\CC is even a largely backwards-compatible extension of C, with development dating back nearly as far as C itself.
     23Though 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.
     24
     25\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.
     26\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.
     27The 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.
     28However, 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.
     29
     30This 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.
     31Particular contributions of this work include design and implementation of
     32parametric-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{} declaration (Chapter~\ref{resolution-chap}).
     33This 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.
     34
     35Though 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.
     36In 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.
     37Type environments are also widely modelled in compiler implementations, particularly of functional languages, though also increasingly commonly in other languages (such as Rust) which also perform type inference; the type environment presented here may be useful to those language implementers.

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

    rc9c9ac4f r546b51e  
    33
    44\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}} % Cforall symbolic name
    5 \newcommand{\CFA}{\protect\CFAIcon}             % safe for section/caption
     5\newcommand{\CFA}{\protect\CFAIcon}     % safe for section/caption
     6\newcommand{\CFL}{\textrm{Cforall}} % Cforall symbolic name
     7\newcommand{\CFACC}{\texttt{cfa-cc}} % Cforall compiler
     8\newcommand{\Celeven}{\textrm{C11}} % C11 symbolic name
     9\newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ symbolic name
     10\newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11} % C++11 symbolic name
     11\newcommand{\CCfourteen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}14} % C++14 symbolic name
     12\newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name
     13\newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name
     14\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name
    615
    716\newcommand{\ie}{\textit{i.e.}}
    … …  
    918\newcommand{\etc}{\textit{etc.}}
    1019\newcommand{\etal}{\textit{et~al.}}
     20
     21\newcommand{\TODO}[1]{\textbf{TODO:} \textit{#1}}

  • doc/theses/aaron_moss/phd/resolution-heuristics.tex

    rc9c9ac4f r546b51e  
    11\chapter{Resolution Heuristics}
     2\label{resolution-chap}
    23
    34Talk about the resolution heuristics. This is the bulk of the thesis.

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

    rc9c9ac4f r546b51e  
    11\chapter{Type Environment}
     2\label{env-chap}
    23
    34Talk about the type environment data structure. Pull from your presentation.
Note: See TracChangeset for help on using the changeset viewer.