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

\chapter{Introduction}

% The highest level overview of Cforall and EHMs. Get this done right away.
This thesis covers the design and implementation of the exception handling
mechanism (EHM) of
\CFA (pronounced sea-for-all and may be written Cforall or CFA).
\CFA is a new programming language that extends C, which maintains
backwards-compatibility while introducing modern programming features.
Adding exception handling to \CFA gives it new ways to handle errors and
make large control-flow jumps.

% Now take a step back and explain what exceptions are generally.
Exception handling provides dynamic inter-function control flow.
A language's EHM is a combination of language syntax and run-time
components that construct, raise, propagate and handle exceptions,
to provide all of that control flow.
There are two forms of exception handling covered in this thesis:
termination, which acts as a multi-level return,
and resumption, which is a dynamic function call.
% About other works:
Often, when this separation is not made, termination exceptions are assumed
as they are more common and may be the only form of handling provided in
a language.

All types of exception handling link a raise with a handler.
Both operations are usually language primitives, although raises can be
treated as a function that takes an exception argument.
Handlers are more complex, as they are added to and removed from the stack
during execution, must specify what they can handle and must give the code to
handle the exception.

Exceptions work with different execution models but for the descriptions
that follow a simple call stack, with functions added and removed in a
first-in-last-out order, is assumed.

Termination exception handling searches the stack for the handler, then
unwinds the stack to where the handler was found before calling it.
The handler is run inside the function that defined it and when it finishes
it returns control to that function.
\begin{center}
%\input{termination}
%
%\medskip
\input{termhandle.pstex_t}
% I hate these diagrams, but I can't access xfig to fix them and they are
% better than the alternative.
\end{center}

Resumption exception handling searches the stack for a handler and then calls
it without removing any other stack frames.
The handler is run on top of the existing stack, often as a new function or
closure capturing the context in which the handler was defined.
After the handler has finished running, it returns control to the function
that preformed the raise, usually starting after the raise.
\begin{center}
%\input{resumption}
%
%\medskip
\input{resumhandle.pstex_t}
% The other one.
\end{center}

Although a powerful feature, exception handling tends to be complex to set up
and expensive to use,
so it is often limited to unusual or ``exceptional" cases.
The classic example is error handling; exceptions can be used to
remove error handling logic from the main execution path, and pay
most of the cost only when the error actually occurs.

\section{Thesis Overview}
This work describes the design and implementation of the \CFA EHM.
The \CFA EHM implements all of the common exception features (or an
equivalent) found in most other EHMs and adds some features of its own.
The design of all the features had to be adapted to \CFA's feature set, as
some of the underlying tools used to implement and express exception handling
in other languages are absent in \CFA.
Still, the resulting syntax resembles that of other languages:
\begin{cfa}
try {
        ...
        T * object = malloc(request_size);
        if (!object) {
                throw OutOfMemory{fixed_allocation, request_size};
        }
        ...
} catch (OutOfMemory * error) {
        ...
}
\end{cfa}
% A note that yes, that was a very fast overview.
The design and implementation of all of \CFA's EHM's features are
described in detail throughout this thesis, whether they are a common feature
or one unique to \CFA.

% The current state of the project and what it contributes.
All of these features have been implemented in \CFA,
covering both changes to the compiler and the run-time.
In addition, a suite of test cases and performance benchmarks were created
alongside the implementation.
The implementation techniques are generally applicable in other programming
languages and much of the design is as well.
Some parts of the EHM use other features unique to \CFA and would be
harder to replicate in other programming languages.

The contributions of this work are:
\begin{enumerate}
\item Designing \CFA's exception handling mechanism, adapting designs from
other programming languages and creating new features.
\item Implementing stack unwinding and the \CFA EHM, including updating
the \CFA compiler and the run-time environment.
\item Designing and implementing a prototype virtual system.
% I think the virtual system and per-call site default handlers are the only
% "new" features, everything else is a matter of implementation.
\item Creating tests to check the behaviour of the EHM.
\item Creating benchmarks to check the performance of the EHM,
as compared to other languages.
\end{enumerate}

The rest of this thesis is organized as follows.
The current state of exceptions is covered in \autoref{s:background}.
The existing state of \CFA is covered in \autoref{c:existing}.
New EHM features are introduced in \autoref{c:features},
covering their usage and design.
That is followed by the implementation of these features in
\autoref{c:implement}.
Performance results are examined in \autoref{c:performance}.
Possibilities to extend this project are discussed in \autoref{c:future}.
Finally, the project is summarized in \autoref{c:conclusion}.

\section{Background}
\label{s:background}

Exception handling has been examined before in programming languages,
with papers on the subject dating back 70s.\cite{Goodenough75}
Early exceptions were often treated as signals, which carried no information
except their identity.
Ada originally used this system\cite{Ada}, but now allows for a string
message as a payload\cite{Ada12}.

The modern flagship for termination exceptions -- if one exists -- is \Cpp,
which added them in its first major wave of non-object-orientated features
in 1990.\cite{CppHistory}
Many EHMs have special exception types,
however \Cpp has the ability to use any type as an exception.
These were found to be not very useful and have been pushed aside for classes
inheriting from
\code{C++}{std::exception}.
Although there is a special catch-all syntax (@catch(...)@), there are no
operations that can be performed on the caught value, not even type inspection.
Instead, the base exception-type \code{C++}{std::exception} defines common
functionality (such as
the ability to describe the reason the exception was raised) and all
exceptions have this functionality.
That trade-off, restricting usable types to gain guaranteed functionality,
is almost universal now, as without some common functionality it is almost
impossible to actually handle any errors.

Java was the next popular language to use exceptions.\cite{Java8}
Its exception system largely reflects that of \Cpp, except that it requires
you throw a child type of \code{Java}{java.lang.Throwable}
and it uses checked exceptions.
Checked exceptions are part of a function's interface,
the exception signature of the function.
Every exception that could be raised from a function, either directly or
because it is not handled from a called function, is given.
Using this information, it is possible to statically verify if any given
exception is handled, and guarantee that no exception will go unhandled.
Making exception information explicit improves clarity and safety,
but can slow down or restrict programming.
For example, programming high-order functions becomes much more complex
if the argument functions could raise exceptions.
However, as odd it may seem, the worst problems are rooted in the simple
inconvenience of writing and updating exception signatures.
This has caused Java programmers to develop multiple programming ``hacks''
to circumvent checked exceptions, negating their advantages.
One particularly problematic example is the ``catch-and-ignore'' pattern,
where an empty handler is used to handle an exception without doing any
recovery or repair. In theory that could be good enough to properly handle
the exception, but more often is used to ignore an exception that the       
programmer does not feel is worth the effort of handling, for instance if
they do not believe it will ever be raised.
If they are incorrect, the exception will be silenced, while in a similar
situation with unchecked exceptions the exception would at least activate    
the language's unhandled exception code (usually, a program abort with an
error message).

%\subsection
Resumption exceptions are less popular,
although resumption is as old as termination; that is, few
programming languages have implemented them.
% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
Mesa is one programming language that did.\cite{Mesa} Experience with Mesa
is quoted as being one of the reasons resumptions were not
included in the \Cpp standard.
% https://en.wikipedia.org/wiki/Exception_handling
Since then, resumptions have been ignored in mainstream programming languages.
However, resumption is being revisited in the context of decades of other
developments in programming languages.
While rejecting resumption may have been the right decision in the past,
the situation has changed since then.
Some developments, such as the functional programming equivalent to resumptions,
algebraic effects\cite{Zhang19}, are enjoying success.
A complete reexamination of resumption is beyond this thesis,
but their reemergence is enough reason to try them in \CFA.
% Especially considering how much easier they are to implement than
% termination exceptions and how much Peter likes them.

%\subsection
Functional languages tend to use other solutions for their primary error
handling mechanism, but exception-like constructs still appear.
Termination appears in the error construct, which marks the result of an
expression as an error; then the result of any expression that tries to use
it also results in an error, and so on until an appropriate handler is reached.
Resumption appears in algebraic effects, where a function dispatches its
side-effects to its caller for handling.

%\subsection
More recently, exceptions seem to be vanishing from newer programming
languages, replaced by ``panic".
In Rust, a panic is just a program level abort that may be implemented by
unwinding the stack like in termination exception
handling.\cite{RustPanicMacro}\cite{RustPanicModule}
Go's panic though is very similar to a termination, except it only supports
a catch-all by calling \code{Go}{recover()}, simplifying the interface at
the cost of flexibility.\cite{Go:2021}

%\subsection
As exception handling's most common use cases are in error handling,
here are some other ways to handle errors with comparisons with exceptions.
\begin{itemize}
\item\emph{Error Codes}:
This pattern has a function return an enumeration (or just a set of fixed
values) to indicate if an error has occurred and possibly which error it was.

Error codes mix exceptional/error and normal values, enlarging the range of
possible return values. This can be addressed with multiple return values
(or a tuple) or a tagged union.
However, the main issue with error codes is forgetting to check them,
which leads to an error being quietly and implicitly ignored.
Some new languages and tools will try to issue warnings when an error code
is discarded to avoid this problem.
Checking error codes also bloats the main execution path,
especially if the error is not handled immediately and has to be passed
through multiple functions before it is addressed.

Here is an example of the pattern in Bash, where commands can only  ``return"
numbers and most output is done through streams of text.
\begin{lstlisting}[language=bash,escapechar={}]
# Immediately after running a command:
case $? in
0)
        # Success
        ;;
1)
        # Error Code 1
        ;;
2|3)
        # Error Code 2 or Error Code 3
        ;;
# Add more cases as needed.
asac
\end{lstlisting}

\item\emph{Special Return with Global Store}:
Similar to the error codes pattern but the function itself only returns
that there was an error,
and stores the reason for the error in a fixed global location.
For example, many routines in the C standard library will only return some
error value (such as -1 or a null pointer) and the error code is written into
the standard variable @errno@.

This approach avoids the multiple results issue encountered with straight
error codes as only a single error value has to be returned,
but otherwise has the same disadvantages and more.
Every function that reads or writes to the global store must agree on all
possible errors and managing it becomes more complex with concurrency.

This example shows some of what has to be done to robustly handle a C
standard library function that reports errors this way.
\begin{lstlisting}[language=C]
// Now a library function can set the error.
int handle = open(path_name, flags);
if (-1 == handle) {
        switch (errno) {
    case ENAMETOOLONG:
                // path_name is a bad argument.
                break;
        case ENFILE:
                // A system resource has been exausted.
                break;
        // And many more...
    }
}
\end{lstlisting}
% cite open man page?

\item\emph{Return Union}:
This pattern replaces error codes with a tagged union.
Success is one tag and the errors are another.
It is also possible to make each possible error its own tag and carry its own
additional information, but the two-branch format is easy to make generic
so that one type can be used everywhere in error handling code.

This pattern is very popular in any functional or semi-functional language
with primitive support for tagged unions (or algebraic data types).
Return unions can also be expressed as monads (evaluation in a context)
and often are in languages with special syntax for monadic evaluation,
such as Haskell's \code{haskell}{do} blocks.

The main advantage is that an arbitrary object can be used to represent an
error, so it can include a lot more information than a simple error code.
The disadvantages include that the it does have to be checked along the main
execution, and if there aren't primitive tagged unions proper, usage can be
hard to enforce.
% We need listing Rust/rust to format code snippets from it.
% Rust's \code{rust}{Result<T, E>}

This is a simple example of examining the result of a failing function in
Haskell, using its \code{haskell}{Either} type.
Examining \code{haskell}{error} further would likely involve more matching,
but the type of \code{haskell}{error} is user defined so there are no
general cases.
\begin{lstlisting}[language=haskell]
case failingFunction argA argB of
    Right value -> -- Use the successful computed value.
    Left error -> -- Handle the produced error.
\end{lstlisting}

Return unions as monads will result in the same code, but can hide most
of the work to propagate errors in simple cases. The code to actually handle
the errors, or to interact with other monads (a common case in these
languages) still has to be written by hand.

If \code{haskell}{failingFunction} is implemented with two helpers that
use the same error type, then it can be implemented with a \code{haskell}{do}
block.
\begin{lstlisting}[language=haskell,literate={}]
failingFunction x y = do
        z <- helperOne x
        helperTwo y z
\end{lstlisting}

\item\emph{Handler Functions}:
This pattern associates errors with functions.
On error, the function that produced the error calls another function to
handle it.
The handler function can be provided locally (passed in as an argument,
either directly as as a field of a structure/object) or globally (a global
variable).
C++ uses this approach as its fallback system if exception handling fails,
such as \snake{std::terminate} and, for a time,
\snake{std::unexpected}.\footnote{\snake{std::unexpected} was part of the
Dynamic Exception Specification, which has been removed from the standard
as of C++20.\cite{CppExceptSpec}}

Handler functions work a lot like resumption exceptions,
but without the dynamic search for a handler.
Since setting up the handler can be more complex/expensive,
especially when the handler has to be passed through multiple layers of
function calls, but cheaper (constant time) to call,
they are more suited to more frequent (less exceptional) situations.
Although, in \Cpp and other languages that do not have checked exceptions,
they can actually be enforced by the type system be more reliable.

This is a more local example in \Cpp, using a function to provide
a default value for a mapping.
\begin{lstlisting}[language=C++]
ValueT Map::key_or_default(KeyT key, ValueT(*make_default)(KeyT)) {
        ValueT * value = find_value(key);
        if (nullptr != value) {
                return *value;
        } else {
                return make_default(key);
        }
}
\end{lstlisting}
\end{itemize}

%\subsection
Because of their cost, exceptions are rarely used for hot paths of execution.
Hence, there is an element of self-fulfilling prophecy as implementation
techniques have been focused on making them cheap to set up,
happily making them expensive to use in exchange.
This difference is less important in higher-level scripting languages,
where using exceptions for other tasks is more common.
An iconic example is Python's
\code{Python}{StopIteration}\cite{PythonExceptions} exception, that
is thrown by an iterator to indicate that it is exhausted.
When paired with Python's iterator-based for-loop, this will be thrown every
time the end of the loop is reached.\cite{PythonForLoop}