source: doc/theses/andrew_beach_MMath/features.tex @ d06707e

\chapter{Exception Features}

This chapter covers the design and user interface of the \CFA
exception-handling mechanism.

\section{Virtuals}
Virtual types and casts are not part of the exception system nor are they
required for an exception system. But an object-oriented style hierarchy is a
great way of organizing exceptions so a minimal virtual system has been added
to \CFA.

The pattern of a simple hierarchy was borrowed from object-oriented
programming was chosen for several reasons.
The first is that it allows new exceptions to be added in user code
and in libraries independently of each other. Another is it allows for
different levels of exception grouping (all exceptions, all IO exceptions or
a particular IO exception). Also it also provides a simple way of passing
data back and forth across the throw.

Virtual types and casts are not required for a basic exception-system but are
useful for advanced exception features. However, \CFA is not object-oriented so
there is no obvious concept of virtuals. Hence, to create advanced exception
features for this work, I needed to design and implement a virtual-like
system for \CFA.

% NOTE: Maybe we should but less of the rational here.
Object-oriented languages often organized exceptions into a simple hierarchy,
\eg Java.
\begin{center}
\setlength{\unitlength}{4000sp}%
\begin{picture}(1605,612)(2011,-1951)
\put(2100,-1411){\vector(1, 0){225}}
\put(3450,-1411){\vector(1, 0){225}}
\put(3550,-1411){\line(0,-1){225}}
\put(3550,-1636){\vector(1, 0){150}}
\put(3550,-1636){\line(0,-1){225}}
\put(3550,-1861){\vector(1, 0){150}}
\put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}}
\put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}}
\put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}}
\put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}}
\put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}}
\end{picture}%
\end{center}
The hierarchy provides the ability to handle an exception at different degrees
of specificity (left to right). Hence, it is possible to catch a more general
exception-type in higher-level code where the implementation details are
unknown, which reduces tight coupling to the lower-level implementation.
Otherwise, low-level code changes require higher-level code changes, \eg,
changing from raising @underflow@ to @overflow@ at the low level means changing
the matching catch at the high level versus catching the general @arithmetic@
exception. In detail, each virtual type may have a parent and can have any
number of children. A type's descendants are its children and its children's
descendants. A type may not be its own descendant.

The exception hierarchy allows a handler (@catch@ clause) to match multiple
exceptions, \eg a base-type handler catches both base and derived
exception-types.
\begin{cfa}
try {
        ...
} catch(arithmetic &) {
        ... // handle arithmetic, underflow, overflow, zerodivide
}
\end{cfa}
Most exception mechanisms perform a linear search of the handlers and select
the first matching handler, so the order of handers is now important because
matching is many to one.

Each virtual type needs an associated virtual table. A virtual table is a
structure with fields for all the virtual members of a type. A virtual type has
all the virtual members of its parent and can add more. It may also update the
values of the virtual members and often does.

While much of the virtual infrastructure is created, it is currently only used
internally for exception handling. The only user-level feature is the virtual
cast, which is the same as the \Cpp \lstinline[language=C++]|dynamic_cast|.
\label{p:VirtualCast}
\begin{cfa}
(virtual TYPE)EXPRESSION
\end{cfa}
Note, the syntax and semantics matches a C-cast, rather than the function-like
\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
a pointer to a virtual type.
The cast dynamically checks if the @EXPRESSION@ type is the same or a subtype
of @TYPE@, and if true, returns a pointer to the
@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).

\section{Exception}
% Leaving until later, hopefully it can talk about actual syntax instead
% of my many strange macros. Syntax aside I will also have to talk about the
% features all exceptions support.

Exceptions are defined by the trait system; there are a series of traits, and
if a type satisfies them, then it can be used as an exception. The following
is the base trait all exceptions need to match.
\begin{cfa}
trait is_exception(exceptT &, virtualT &) {
        virtualT const & get_exception_vtable(exceptT *);
};
\end{cfa}
The trait is defined over two types, the exception type and the virtual table
type. This should be one-to-one, each exception type has only one virtual
table type and vice versa. The only assertion in the trait is
@get_exception_vtable@, which takes a pointer of the exception type and
returns a reference to the virtual table type instance.

The function @get_exception_vtable@ is actually a constant function.
Recardless of the value passed in (including the null pointer) it should
return a reference to the virtual table instance for that type.
The reason it is a function instead of a constant is that it make type
annotations easier to write as you can use the exception type instead of the
virtual table type; which usually has a mangled name.
% Also \CFA's trait system handles functions better than constants and doing
% it this way reduce the amount of boiler plate we need.

% I did have a note about how it is the programmer's responsibility to make
% sure the function is implemented correctly. But this is true of every
% similar system I know of (except Agda's I guess) so I took it out.

There are two more traits for exceptions @is_termination_exception@ and
@is_resumption_exception@. They are defined as follows:

\begin{cfa}
trait is_termination_exception(
                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
        void defaultTerminationHandler(exceptT &);
};

trait is_resumption_exception(
                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
        void defaultResumptionHandler(exceptT &);
};
\end{cfa}

In other words they make sure that a given type and virtual type is an
exception and defines one of the two default handlers. These default handlers
are used in the main exception handling operations \see{Exception Handling}
and their use will be detailed there.

However all three of these traits can be trickly to use directly.
There is a bit of repetition required but
the largest issue is that the virtual table type is mangled and not in a user
facing way. So there are three macros that can be used to wrap these traits
when you need to refer to the names:
@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.

All take one or two arguments. The first argument is the name of the
exception type. Its unmangled and mangled form are passed to the trait.
The second (optional) argument is a parenthesized list of polymorphic
arguments. This argument should only with polymorphic exceptions and the
list will be passed to both types.
In the current set-up the base name and the polymorphic arguments have to
match so these macros can be used without losing flexability.

For example consider a function that is polymorphic over types that have a
defined arithmetic exception:
\begin{cfa}
forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
void some_math_function(Num & left, Num & right);
\end{cfa}

\section{Exception Handling}
\CFA provides two kinds of exception handling, termination and resumption.
These twin operations are the core of the exception handling mechanism and
are the reason for the features of exceptions.
This section will cover the general patterns shared by the two operations and
then go on to cover the details each individual operation.

Both operations follow the same set of steps to do their operation. They both
start with the user preforming a throw on an exception.
Then there is the search for a handler, if one is found than the exception
is caught and the handler is run. After that control returns to normal
execution.

If the search fails a default handler is run and then control
returns to normal execution immediately. That is where the default handlers
@defaultTermiationHandler@ and @defaultResumptionHandler@ are used.

\subsection{Termination}
\label{s:Termination}

Termination handling is more familiar kind and used in most programming
languages with exception handling.
It is dynamic, non-local goto. If a throw is successful then the stack will
be unwound and control will (usually) continue in a different function on
the call stack. They are commonly used when an error has occured and recovery
is impossible in the current function.

% (usually) Control can continue in the current function but then a different
% control flow construct should be used.

A termination throw is started with the @throw@ statement:
\begin{cfa}
throw EXPRESSION;
\end{cfa}
The expression must return a reference to a termination exception, where the
termination exception is any type that satifies @is_termination_exception@
at the call site.
Through \CFA's trait system the functions in the traits are passed into the
throw code. A new @defaultTerminationHandler@ can be defined in any scope to
change the throw's behavior (see below).

The throw will copy the provided exception into managed memory. It is the
user's responcibility to ensure the original exception is cleaned up if the
stack is unwound (allocating it on the stack should be sufficient).

Then the exception system searches the stack using the copied exception.
It starts starts from the throw and proceeds to the base of the stack,
from callee to caller.
At each stack frame, a check is made for resumption handlers defined by the
@catch@ clauses of a @try@ statement.
\begin{cfa}
try {
        GUARDED_BLOCK
} catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
        HANDLER_BLOCK$\(_1\)$
} catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
        HANDLER_BLOCK$\(_2\)$
}
\end{cfa}
When viewed on its own a try statement will simply exceute the statements in
@GUARDED_BLOCK@ and when those are finished the try statement finishes.

However, while the guarded statements are being executed, including any
functions they invoke, all the handlers following the try block are now
or any functions invoked from those
statements, throws an exception, and the exception
is not handled by a try statement further up the stack, the termination
handlers are searched for a matching exception type from top to bottom.

Exception matching checks the representation of the thrown exception-type is
the same or a descendant type of the exception types in the handler clauses. If
it is the same of a descendent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
are executed. If control reaches the end of the handler, the exception is
freed and control continues after the try statement.

If no handler is found during the search then the default handler is run.
Through \CFA's trait system the best match at the throw sight will be used.
This function is run and is passed the copied exception. After the default
handler is run control continues after the throw statement.

There is a global @defaultTerminationHandler@ that cancels the current stack
with the copied exception. However it is generic over all exception types so
new default handlers can be defined for different exception types and so
different exception types can have different default handlers.

\subsection{Resumption}
\label{s:Resumption}

Resumption exception handling is a less common form than termination but is
just as old~\cite{Goodenough75} and is in some sense simpler.
It is a dynamic, non-local function call. If the throw is successful a
closure will be taken from up the stack and executed, after which the throwing
function will continue executing.
These are most often used when an error occured and if the error is repaired
then the function can continue.

A resumption raise is started with the @throwResume@ statement:
\begin{cfa}
throwResume EXPRESSION;
\end{cfa}
The semantics of the @throwResume@ statement are like the @throw@, but the
expression has return a reference a type that satifies the trait
@is_resumption_exception@. The assertions from this trait are available to
the exception system while handling the exception.

At runtime, no copies are made. As the stack is not unwound the exception and
any values on the stack will remain in scope while the resumption is handled.

Then the exception system searches the stack using the provided exception.
It starts starts from the throw and proceeds to the base of the stack,
from callee to caller.
At each stack frame, a check is made for resumption handlers defined by the
@catchResume@ clauses of a @try@ statement.
\begin{cfa}
try {
        GUARDED_BLOCK
} catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
        HANDLER_BLOCK$\(_1\)$
} catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
        HANDLER_BLOCK$\(_2\)$
}
\end{cfa}
If the handlers are not involved in a search this will simply execute the
@GUARDED_BLOCK@ and then continue to the next statement.
Its purpose is to add handlers onto the stack.
(Note, termination and resumption handlers may be intermixed in a @try@
statement but the kind of throw must be the same as the handler for it to be
considered as a possible match.)

If a search for a resumption handler reaches a try block it will check each
@catchResume@ clause, top-to-bottom.
At each handler if the thrown exception is or is a child type of
@EXCEPTION_TYPE@$_i$ then the a pointer to the exception is bound to
@NAME@$_i$ and then @HANDLER_BLOCK@$_i$ is executed. After the block is
finished control will return to the @throwResume@ statement.

Like termination, if no resumption handler is found, the default handler
visible at the throw statement is called. It will use the best match at the
call sight according to \CFA's overloading rules. The default handler is
passed the exception given to the throw. When the default handler finishes
execution continues after the throw statement.

There is a global @defaultResumptionHandler@ is polymorphic over all
termination exceptions and preforms a termination throw on the exception.
The @defaultTerminationHandler@ for that throw is matched at the original
throw statement (the resumption @throwResume@) and it can be customized by
introducing a new or better match as well.

% \subsubsection?

A key difference between resumption and termination is that resumption does
not unwind the stack. A side effect that is that when a handler is matched
and run it's try block (the guarded statements) and every try statement
searched before it are still on the stack. This can lead to the recursive
resumption problem.

The recursive resumption problem is any situation where a resumption handler
ends up being called while it is running.
Consider a trivial case:
\begin{cfa}
try {
        throwResume (E &){};
} catchResume(E *) {
        throwResume (E &){};
}
\end{cfa}
When this code is executed the guarded @throwResume@ will throw, start a
search and match the handler in the @catchResume@ clause. This will be
call and placed on the stack on top of the try-block. The second throw then
throws and will seach the same try block and put call another instance of the
same handler leading to an infinite loop.

This situation is trivial and easy to avoid, but much more complex cycles
can form with multiple handlers and different exception types.

To prevent all of these cases we mask sections of the stack, or equvilantly
the try statements on the stack, so that the resumption seach skips over
them and continues with the next unmasked section of the stack.

A section of the stack is marked when it is searched to see if it contains
a handler for an exception and unmarked when that exception has been handled
or the search was completed without finding a handler.

% This might need a diagram. But it is an important part of the justification
% of the design of the traversal order.
\begin{verbatim}
       throwResume2 ----------.
            |                 |
 generated from handler       |
            |                 |
         handler              |
            |                 |
        throwResume1 -----.   :
            |             |   :
           try            |   : search skip
            |             |   :
        catchResume  <----'   :
            |                 |
\end{verbatim}

The rules can be remembered as thinking about what would be searched in
termination. So when a throw happens in a handler; a termination handler
skips everything from the original throw to the original catch because that
part of the stack has been unwound, a resumption handler skips the same
section of stack because it has been masked.
A throw in a default handler will preform the same search as the original
throw because; for termination nothing has been unwound, for resumption
the mask will be the same.

The symmetry with termination is why this pattern was picked. Other patterns,
such as marking just the handlers that caught, also work but lack the
symmetry whih means there is more to remember.

\section{Conditional Catch}
Both termination and resumption handler clauses can be given an additional
condition to further control which exceptions they handle:
\begin{cfa}
catch (EXCEPTION_TYPE * NAME ; CONDITION)
\end{cfa}
First, the same semantics is used to match the exception type. Second, if the
exception matches, @CONDITION@ is executed. The condition expression may
reference all names in scope at the beginning of the try block and @NAME@
introduced in the handler clause. If the condition is true, then the handler
matches. Otherwise, the exception search continues as if the exception type
did not match.
\begin{cfa}
try {
        f1 = open( ... );
        f2 = open( ... );
        ...
} catch( IOFailure * f ; fd( f ) == f1 ) {
        // only handle IO failure for f1
}
\end{cfa}
Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
exception if not @f1@ is different because the reraise does not examine any of
remaining handlers in the current try statement.

\section{Rethrowing}
\colour{red}{From Andrew: I recomend we talk about why the language doesn't
have rethrows/reraises instead.}

\label{s:Rethrowing}
Within the handler block or functions called from the handler block, it is
possible to reraise the most recently caught exception with @throw@ or
@throwResume@, respectively.
\begin{cfa}
try {
        ...
} catch( ... ) {
        ... throw;
} catchResume( ... ) {
        ... throwResume;
}
\end{cfa}
The only difference between a raise and a reraise is that reraise does not
create a new exception; instead it continues using the current exception, \ie
no allocation and copy. However the default handler is still set to the one
visible at the raise point, and hence, for termination could refer to data that
is part of an unwound stack frame. To prevent this problem, a new default
handler is generated that does a program-level abort.

\section{Finally Clauses}
Finally clauses are used to preform unconditional clean-up when leaving a
scope. They are placed at the end of a try statement:
\begin{cfa}
try {
        GUARDED_BLOCK
} ... // any number or kind of handler clauses
... finally {
        FINALLY_BLOCK
}
\end{cfa}
The @FINALLY_BLOCK@ is executed when the try statement is removed from the
stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
finishes or during an unwind.
The only time the block is not executed is if the program is exited before
the stack is unwound.

Execution of the finally block should always finish, meaning control runs off
the end of the block. This requirement ensures always continues as if the
finally clause is not present, \ie finally is for cleanup not changing control
flow. Because of this requirement, local control flow out of the finally block
is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
@return@ that causes control to leave the finally block. Other ways to leave
the finally block, such as a long jump or termination are much harder to check,
and at best requiring additional run-time overhead, and so are mearly
discouraged.

Not all languages with exceptions have finally clauses. Notably \Cpp does
without it as descructors serve a similar role. Although destructors and
finally clauses can be used in many of the same areas they have their own
use cases like top-level functions and lambda functions with closures.
Destructors take a bit more work to set up but are much easier to reuse while
finally clauses are good for once offs and can include local information.

\section{Cancellation}
Cancellation is a stack-level abort, which can be thought of as as an
uncatchable termination. It unwinds the entirety of the current stack, and if
possible forwards the cancellation exception to a different stack.

Cancellation is not an exception operation like termination or resumption.
There is no special statement for starting a cancellation; instead the standard
library function @cancel_stack@ is called passing an exception. Unlike a
throw, this exception is not used in matching only to pass information about
the cause of the cancellation.
(This also means matching cannot fail so there is no default handler either.)

After @cancel_stack@ is called the exception is copied into the exception
handling mechanism's memory. Then the entirety of the current stack is
unwound. After that it depends one which stack is being cancelled.
\begin{description}
\item[Main Stack:]
The main stack is the one used by the program main at the start of execution,
and is the only stack in a sequential program. Even in a concurrent program
the main stack is only dependent on the environment that started the program.
Hence, when the main stack is cancelled there is nowhere else in the program
to notify. After the stack is unwound, there is a program-level abort.

\item[Thread Stack:]
A thread stack is created for a @thread@ object or object that satisfies the
@is_thread@ trait. A thread only has two points of communication that must
happen: start and join. As the thread must be running to perform a
cancellation, it must occur after start and before join, so join is used
for communication here.
After the stack is unwound, the thread halts and waits for
another thread to join with it. The joining thread checks for a cancellation,
and if present, resumes exception @ThreadCancelled@.

There is a subtle difference between the explicit join (@join@ function) and
implicit join (from a destructor call). The explicit join takes the default
handler (@defaultResumptionHandler@) from its calling context, which is used if
the exception is not caught. The implicit join does a program abort instead.

This semantics is for safety. If an unwind is triggered while another unwind
is underway only one of them can proceed as they both want to ``consume'' the
stack. Letting both try to proceed leads to very undefined behaviour.
Both termination and cancellation involve unwinding and, since the default
@defaultResumptionHandler@ preforms a termination that could more easily
happen in an implicate join inside a destructor. So there is an error message
and an abort instead.
\todo{Perhaps have a more general disucssion of unwind collisions before
this point.}

The recommended way to avoid the abort is to handle the intial resumption
from the implicate join. If required you may put an explicate join inside a
finally clause to disable the check and use the local
@defaultResumptionHandler@ instead.

\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
or object that satisfies the @is_coroutine@ trait. A coroutine only knows of
two other coroutines, its starter and its last resumer. Of the two the last
resumer has the tightest coupling to the coroutine it activated and the most
up-to-date information.

Hence, cancellation of the active coroutine is forwarded to the last resumer
after the stack is unwound. When the resumer restarts, it resumes exception
@CoroutineCancelled@, which is polymorphic over the coroutine type and has a
pointer to the cancelled coroutine.

The resume function also has an assertion that the @defaultResumptionHandler@
for the exception. So it will use the default handler like a regular throw.
\end{description}