source:doc/theses/andrew_beach_MMath/intro.tex@471ff17

Last change on this file since 471ff17 was 471ff17, checked in by Andrew Beach <ajbeach@…>, 3 years ago

Andrew MMath: Addressed most of the changes in intro and worked on the new background section. (2/3 for this review.)

• Property mode set to 100644
File size: 10.5 KB
Line
1\chapter{Introduction}
2
3% The highest level overview of Cforall and EHMs. Get this done right away.
4This thesis goes over the design and implementation of the exception handling
5mechanism (EHM) of
6\CFA (pernounced sea-for-all and may be written Cforall or CFA).
7
8% Now take a step back and explain what exceptions are generally.
9Exception handling provides dynamic inter-function control flow.
10There are two forms of exception handling covered in this thesis:
11termination, which acts as a multi-level return,
12and resumption, which is a dynamic function call.
13Termination handling is much more common,
14to the extent that it is often seen
15This seperation is uncommon because termination exception handling is so
16much more common that it is often assumed.
17% WHY: Mention other forms of continuation and \cite{CommonLisp} here?
18A language's EHM is the combination of language syntax and run-time
19components that are used to construct, raise and handle exceptions,
20including all control flow.
21
23function on the stack directly, skipping any functions between it and the
24current function.
25\begin{center}
26\input{callreturn}
27\end{center}
28
29Resumption exception handling calls a function, but asks the functions on the
30stack what function that is.
31\todo{Add a diagram showing control flow for resumption.}
32
33Although a powerful feature, exception handling tends to be complex to set up
34and expensive to use
35so they are often limited to unusual or exceptional" cases.
36The classic example of this is error handling, exceptions can be used to
37remove error handling logic from the main execution path and while paying
38most of the cost only when the error actually occurs.
39
40\section{Thesis Overview}
41This work describes the design and implementation of the \CFA EHM.
42The \CFA EHM implements all of the common exception features (or an
43equivalent) found in most other EHMs and adds some features of its own.
44The design of all the features had to be adapted to \CFA's feature set as
45some of the underlying tools used to implement and express exception handling
46in other languages are absent in \CFA.
47Still the resulting syntax resembles that of other languages:
48\begin{cfa}
49try {
50        ...
51        T * object = malloc(request_size);
52        if (!object) {
53                throw OutOfMemory{fixed_allocation, request_size};
54        }
55        ...
56} catch (OutOfMemory * error) {
57        ...
58}
59\end{cfa}
60
61% A note that yes, that was a very fast overview.
62The design and implementation of all of \CFA's EHM's features are
63described in detail throughout this thesis, whether they are a common feature
64or one unique to \CFA.
65
66% The current state of the project and what it contributes.
67All of these features have been implemented in \CFA, along with
68a suite of test cases as part of this project.
69The implementation techniques are generally applicable in other programming
70languages and much of the design is as well.
71Some parts of the EHM use other features unique to \CFA and these would be
72harder to replicate in other programming languages.
73
74% Talk about other programming languages.
75Some existing programming languages that include EHMs/exception handling
76include C++, Java and Python. All three examples focus on termination
77exceptions which unwind the stack as part of the
78Exceptions also can replace return codes and return unions.
79In functional languages will also sometimes fold exceptions into monads.
80
81The contributions of this work are:
82\begin{enumerate}
83\item Designing \CFA's exception handling mechanism, adapting designs from
84other programming languages and the creation of new features.
85\item Implementing stack unwinding and the EHM in \CFA, including updating
86the compiler and the run-time environment.
87\item Designed and implemented a prototype virtual system.
88% I think the virtual system and per-call site default handlers are the only
89% "new" features, everything else is a matter of implementation.
90\end{enumerate}
91
93The next section covers the existing state of exceptions.
94The existing state of \CFA is also covered in \autoref{c:existing}.
95The new features are introduced in \autoref{c:features},
96which explains their usage and design.
97That is followed by the implementation of those features in
98\autoref{c:implement}.
99The performance results are examined in \autoref{c:performance}.
100Possibilities to extend this project are discussed in \autoref{c:future}.
101
102\section{Background}
103\label{s:background}
104
105Exception handling is not a new concept,
106with papers on the subject dating back 70s.
107
108Their were popularised by \Cpp,
109which added them in its first major wave of non-object-orientated features
110in 1990.
111% https://en.cppreference.com/w/cpp/language/history
112
113Java was the next popular language to use exceptions. It is also the most
114popular language with checked exceptions.
115Checked exceptions are part of the function interface they are raised from.
116This includes functions they propogate through, until a handler for that
117type of exception is found.
118This makes exception information explicit, which can improve clarity and
119safety, but can slow down programming.
120Some of these, such as dealing with high-order methods or an overly specified
121throws clause, are technical. However some of the issues are much more
122human, in that writing/updating all the exception signatures can be enough
123of a burden people will hack the system to avoid them.
124Including the catch-and-ignore" pattern where a catch block is used without
125anything to repair or recover from the exception.
126
127%\subsection
128Resumption exceptions have been much less popular.
129Although resumption has a history as old as termination's, very few
130programming languages have implement them.
131% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
132%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
133Mesa is one programming languages that did and experiance with that
134languages is quoted as being one of the reasons resumptions were not
135included in the \Cpp standard.
136% https://en.wikipedia.org/wiki/Exception_handling
137\todo{A comment about why we did include them when they are so unpopular
138might be approprate.}
139
140%\subsection
141Functional languages, tend to use solutions like the return union, but some
142exception-like constructs still appear.
143
144For instance Haskell's built in error mechanism can make the result of any
145expression, including function calls. Any expression that examines an
146error value will in-turn produce an error. This continues until the main
147function produces an error or until it is handled by one of the catch
148functions.
149
150%\subsection
151More recently exceptions seem to be vanishing from newer programming
152languages.
153Rust and Go reduce this feature to panics.
154Panicing is somewhere between a termination exception and a program abort.
155Notably in Rust a panic can trigger either, a panic may unwind the stack or
156simply kill the process.
157% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
158Go's panic is much more similar to a termination exception but there is
159only a catch-all function with \code{Go}{recover()}.
160So exceptions still are appearing, just in reduced forms.
161
162%\subsection
163Exception handling's most common use cases are in error handling.
164Here are some other ways to handle errors and comparisons with exceptions.
165\begin{itemize}
166\item\emph{Error Codes}:
167This pattern uses an enumeration (or just a set of fixed values) to indicate
168that an error has occured and which error it was.
169
170There are some issues if a function wants to return an error code and another
171value. The main issue is that it can be easy to forget checking the error
172code, which can lead to an error being quitely and implicitly ignored.
173Some new languages have tools that raise warnings if the return value is
175It also puts more code on the main execution path.
176\item\emph{Special Return with Global Store}:
177A function that encounters an error returns some value indicating that it
178encountered a value but store which error occured in a fixed global location.
179
180Perhaps the C standard @errno@ is the most famous example of this,
181where some standard library functions will return some non-value (often a
182NULL pointer) and set @errno@.
183
184This avoids the multiple results issue encountered with straight error codes
186It does however introduce one other major disadvantage:
187Everything that uses that global location must agree on all possible errors.
188\item\emph{Return Union}:
189Replaces error codes with a tagged union.
190Success is one tag and the errors are another.
191It is also possible to make each possible error its own tag and carry its own
192additional information, but the two branch format is easy to make generic
193so that one type can be used everywhere in error handling code.
194
195This pattern is very popular in functional or semi-functional language,
196anything with primitive support for tagged unions (or algebraic data types).
197% We need listing Rust/rust to format code snipits from it.
198% Rust's \code{rust}{Result<T, E>}
199
200The main disadvantage is again it puts code on the main execution path.
202error, other than one of a fix-set of ids, to be sent.
203They can be missed but some languages can force that they are checked.
204It is also implicitly forced in any languages with checked union access.
205\item\emph{Handler Functions}:
206On error the function that produced the error calls another function to
207handle it.
208The handler function can be provided locally (passed in as an argument,
209either directly as as a field of a structure/object) or globally (a global
210variable).
211
212C++ uses this as its fallback system if exception handling fails.
213\snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
214
215Handler functions work a lot like resumption exceptions.
216The difference is they are more expencive to set up but cheaper to use, and
217so are more suited to more fequent errors.
218The exception being global handlers if they are rarely change as the time
219in both cases strinks towards zero.
220\end{itemize}
221
222%\subsection
223Because of their cost exceptions are rarely used for hot paths of execution.
224There is an element of self-fulfilling prophocy here as implementation
225techniques have been designed to make exceptions cheap to set-up at the cost
226of making them expencive to use.
227Still, use of exceptions for other tasks is more common in higher-level
228scripting languages.
229An iconic example is Python's StopIteration exception which is thrown by
230an iterator to indicate that it is exausted. Combined with Python's heavy
231use of the iterator based for-loop.
232% https://docs.python.org/3/library/exceptions.html#StopIteration
Note: See TracBrowser for help on using the repository browser.