source: doc/theses/andrew_beach_MMath/intro.tex @ fcaa1e4

jacob/cs343-translationnew-ast-unique-expr
Last change on this file since fcaa1e4 was fcaa1e4, checked in by Andrew Beach <ajbeach@…>, 3 months ago

Andrew MMath: Updated the introduction/background section.

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