source: doc/theses/andrew_beach_MMath/intro.tex @ 417e8ea

jacob/cs343-translationnew-ast-unique-expr
Last change on this file since 417e8ea was 417e8ea, checked in by Peter A. Buhr <pabuhr@…>, 3 months ago

proofread intro chapter of Andrew's thesis

  • Property mode set to 100644
File size: 15.6 KB
Line 
1\chapter{Introduction}
2
3% The highest level overview of Cforall and EHMs. Get this done right away.
4This thesis covers 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, which maintains
8backwards-compatibility while introducing modern programming features.
9Adding exception handling to \CFA gives it new ways to handle errors and
10make large control-flow jumps.
11
12% Now take a step back and explain what exceptions are generally.
13A language's EHM is a combination of language syntax and run-time
14components that are used to construct, raise, and handle exceptions,
15including all control flow.
16Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
17Exception handling provides dynamic inter-function control flow.
18There are two forms of exception handling covered in this thesis:
19termination, which acts as a multi-level return,
20and resumption, which is a dynamic function call.
21% PAB: Maybe this sentence was suppose to be deleted?
22Termination handling is much more common,
23to the extent that it is often seen as the only form of handling.
24% PAB: I like this sentence better than the next sentence.
25% This separation is uncommon because termination exception handling is so
26% much more common that it is often assumed.
27% WHY: Mention other forms of continuation and \cite{CommonLisp} here?
28
29Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
30\begin{center}
31\begin{tabular}[t]{ll}
32\begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
33void f( void (*hp)() ) {
34        hp();
35}
36void g( void (*hp)() ) {
37        f( hp );
38}
39void h( int @i@, void (*hp)() ) {
40        void @handler@() { // nested
41                printf( "%d\n", @i@ );
42        }
43        if ( i == 1 ) hp = handler;
44        if ( i > 0 ) h( i - 1, hp );
45        else g( hp );
46}
47h( 2, 0 );
48\end{lstlisting}
49&
50\raisebox{-0.5\totalheight}{\input{handler}}
51\end{tabular}
52\end{center}
53The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
54When this handler is called in @f@, it uses the parameter @i@ in the second stack frame, which is accessible by an implicit lexical-link pointer.
55Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
56Exception handling extends this idea by eliminating explicit handler passing, and instead, performing a stack search for a handler that matches some criteria (conditional dynamic call), and calls the handler at the top of the stack.
57It is the runtime search $O(N)$ that differentiates an EHM call (raise) from normal dynamic call $O(1)$ via a function or virtual-member pointer.
58
59Termination exception handling searches the stack for a handler, unwinds the stack to the frame containing the matching handler, and calling the handler at the top of the stack.
60\begin{center}
61\input{termination}
62\end{center}
63Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
64After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
65Unwinding allows recover to any previous
66function on the stack, skipping any functions between it and the
67function containing the matching handler.
68
69Resumption exception handling searches the stack for a handler, does \emph{not} unwind the stack to the frame containing the matching handler, and calls the handler at the top of the stack.
70\begin{center}
71\input{resumption}
72\end{center}
73After the handler returns, control continues after the resume in @f@ (dynamic return).
74Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.
75
76Although a powerful feature, exception handling tends to be complex to set up
77and expensive to use
78so it is often limited to unusual or ``exceptional" cases.
79The classic example is error handling, where exceptions are used to
80remove error handling logic from the main execution path, while paying
81most of the cost only when the error actually occurs.
82
83\section{Thesis Overview}
84This work describes the design and implementation of the \CFA EHM.
85The \CFA EHM implements all of the common exception features (or an
86equivalent) found in most other EHMs and adds some features of its own.
87The design of all the features had to be adapted to \CFA's feature set as
88some of the underlying tools used to implement and express exception handling
89in other languages are absent in \CFA.
90Still the resulting basic syntax resembles that of other languages:
91\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
92@try@ {
93        ...
94        T * object = malloc(request_size);
95        if (!object) {
96                @throw@ OutOfMemory{fixed_allocation, request_size};
97        }
98        ...
99} @catch@ (OutOfMemory * error) {
100        ...
101}
102\end{lstlisting}
103% A note that yes, that was a very fast overview.
104The design and implementation of all of \CFA's EHM's features are
105described in detail throughout this thesis, whether they are a common feature
106or one unique to \CFA.
107
108% The current state of the project and what it contributes.
109The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code.
110In addition,
111a suite of tests and performance benchmarks were created as part of this project.
112The \CFA implementation techniques are generally applicable in other programming
113languages and much of the design is as well.
114Some parts of the EHM use features unique to \CFA, and hence,
115are harder to replicate in other programming languages.
116% Talk about other programming languages.
117Three well known programming languages with EHMs, %/exception handling
118C++, Java and Python are examined in the performance work. However, these languages focus on termination
119exceptions, so there is no comparison with resumption.
120
121The contributions of this work are:
122\begin{enumerate}
123\item Designing \CFA's exception handling mechanism, adapting designs from
124other programming languages, and creating new features.
125\item Implementing stack unwinding for the \CFA EHM, including updating
126the \CFA compiler and run-time environment to generate and execute the EHM code.
127\item Designing and implementing a prototype virtual system.
128% I think the virtual system and per-call site default handlers are the only
129% "new" features, everything else is a matter of implementation.
130\item Creating tests and performance benchmarks to compare with EHM's in other languages.
131\end{enumerate}
132
133%\todo{I can't figure out a good lead-in to the roadmap.}
134The thesis is organization as follows.
135The next section and parts of \autoref{c:existing} cover existing EHMs.
136New \CFA EHM features are introduced in \autoref{c:features},
137covering their usage and design.
138That is followed by the implementation of these features in
139\autoref{c:implement}.
140Performance results are presented in \autoref{c:performance}.
141Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
142
143\section{Background}
144\label{s:background}
145
146Exception handling is a well examined area in programming languages,
147with papers on the subject dating back the 70s~\cite{Goodenough75}.
148Early exceptions were often treated as signals, which carried no information
149except their identity. Ada~\cite{Ada} still uses this system.
150
151The modern flag-ship for termination exceptions is \Cpp,
152which added them in its first major wave of non-object-orientated features
153in 1990.
154% https://en.cppreference.com/w/cpp/language/history
155While many EHMs have special exception types,
156\Cpp has the ability to use any type as an exception.
157However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from
158\code{C++}{std::exception}.
159While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can
160be done with the caught value because nothing is known about it.
161Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as
162the ability to print a message when the exception is raised but not caught) and all
163exceptions have this functionality.
164Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth
165any lost in flexibility from limiting exceptions types to classes.
166
167Java~\cite{Java} was the next popular language to use exceptions.
168Its exception system largely reflects that of \Cpp, except it requires
169exceptions to be a subtype of \code{Java}{java.lang.Throwable}
170and it uses checked exceptions.
171Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise.
172Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions.
173Making exception information explicit, improves clarity and
174safety, but can slow down programming.
175For example, programming complexity increases when dealing with high-order methods or an overly specified
176throws clause. However some of the issues are more
177programming annoyances, such as writing/updating many exception signatures after adding or remove calls.
178Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide.
179For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus
180repairing or recovering from the exception.
181
182%\subsection
183Resumption exceptions are less popular,
184although resumption is as old as termination;
185hence, few
186programming languages have implemented them.
187% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
188%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
189Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
190is quoted as being one of the reasons resumptions are not
191included in the \Cpp standard.
192% https://en.wikipedia.org/wiki/Exception_handling
193As a result, resumption has ignored in main-stream programming languages.
194However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading).
195While rejecting resumption might have been the right decision in the past, there are decades
196of developments in computer science that have changed the situation.
197Some of these developments, such as functional programming's resumption
198equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success.
199A complete reexamination of resumptions is beyond this thesis, but their re-emergence is
200enough to try them in \CFA.
201% Especially considering how much easier they are to implement than
202% termination exceptions.
203
204%\subsection
205Functional languages tend to use other solutions for their primary EHM,
206but exception-like constructs still appear.
207Termination appears in error construct, which marks the result of an
208expression as an error; thereafter, the result of any expression that tries to use it is also an
209error, and so on until an appropriate handler is reached.
210Resumption appears in algebraic effects, where a function dispatches its
211side-effects to its caller for handling.
212
213%\subsection
214Some programming languages have moved to a restricted kind of EHM
215called ``panic".
216In Rust~\cite{Rust}, a panic is just a program level abort that may be implemented by
217unwinding the stack like in termination exception handling.
218% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
219In Go~\cite{Go}, a panic is very similar to a termination, except it only supports
220a catch-all by calling \code{Go}{recover()}, simplifying the interface at
221the cost of flexibility.
222
223%\subsection
224While exception handling's most common use cases are in error handling,
225here are other ways to handle errors with comparisons to exceptions.
226\begin{itemize}
227\item\emph{Error Codes}:
228This pattern has a function return an enumeration (or just a set of fixed values) to indicate
229if an error occurred and possibly which error it was.
230
231Error codes mix exceptional and normal values, artificially enlarging the type and/or value range.
232Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result.
233However, the main issue with error codes is forgetting to checking them,
234which leads to an error being quietly and implicitly ignored.
235Some new languages have tools that issue warnings, if the error code is
236discarded to avoid this problem.
237Checking error codes also results in bloating the main execution path, especially if an error is not dealt with locally and has to be cascaded down the call stack to a higher-level function..
238
239\item\emph{Special Return with Global Store}:
240Some functions only return a boolean indicating success or failure
241and store the exact reason for the error in a fixed global location.
242For example, many C routines return non-zero or -1, indicating success or failure,
243and write error details into the C standard variable @errno@.
244
245This approach avoids the multiple results issue encountered with straight error codes
246but otherwise has many (if not more) of the disadvantages.
247For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency.
248
249\item\emph{Return Union}:
250This pattern replaces error codes with a tagged union.
251Success is one tag and the errors are another.
252It is also possible to make each possible error its own tag and carry its own
253additional information, but the two branch format is easy to make generic
254so that one type can be used everywhere in error handling code.
255
256This pattern is very popular in functional or any semi-functional language with
257primitive support for tagged unions (or algebraic data types).
258% We need listing Rust/rust to format code snipits from it.
259% Rust's \code{rust}{Result<T, E>}
260The main advantage is providing for more information about an
261error, other than one of a fix-set of ids.
262While some languages use checked union access to force error-code checking,
263it is still possible to bypass the checking.
264The main disadvantage is again significant error code on the main execution path and cascading through called functions.
265
266\item\emph{Handler Functions}:
267This pattern implicitly associates functions with errors.
268On error, the function that produced the error implicitly calls another function to
269handle it.
270The handler function can be provided locally (passed in as an argument,
271either directly as as a field of a structure/object) or globally (a global
272variable).
273C++ uses this approach as its fallback system if exception handling fails, \eg
274\snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
275
276Handler functions work a lot like resumption exceptions, without the dynamic handler search.
277Therefore, setting setting up the handler can be more complex/expensive, especially if the handle must be passed through multiple function calls, but cheaper to call $O(1)$, and hence,
278are more suited to frequent exceptional situations.
279% The exception being global handlers if they are rarely change as the time
280% in both cases shrinks towards zero.
281\end{itemize}
282
283%\subsection
284Because of their cost, exceptions are rarely used for hot paths of execution.
285Therefore, there is an element of self-fulfilling prophecy for implementation
286techniques to make exceptions cheap to set-up at the cost
287of expensive usage.
288This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common.
289An iconic example is Python's @StopIteration@ exception that is thrown by
290an iterator to indicate that it is exhausted, especially when combined with Python's heavy
291use of the iterator-based for-loop.
292% https://docs.python.org/3/library/exceptions.html#StopIteration
Note: See TracBrowser for help on using the repository browser.