source: doc/theses/andrew_beach_MMath/features.tex @ 1830a86

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 1830a86 was 1830a86, checked in by Andrew Beach <ajbeach@…>, 8 months ago

Andrew MMath: Updated exception features chapter.

  • Property mode set to 100644
File size: 23.8 KB
Line 
1\chapter{Exception Features}
2
3This chapter covers the design and user interface of the \CFA
4exception-handling mechanism.
5
6\section{Virtuals}
7Virtual types and casts are not part of the exception system nor are they
8required for an exception system. But an object-oriented style hierarchy is a
9great way of organizing exceptions so a minimal virtual system has been added
10to \CFA.
11
12The pattern of a simple hierarchy was borrowed from object-oriented
13programming was chosen for several reasons.
14The first is that it allows new exceptions to be added in user code
15and in libraries independently of each other. Another is it allows for
16different levels of exception grouping (all exceptions, all IO exceptions or
17a particular IO exception). Also it also provides a simple way of passing
18data back and forth across the throw.
19
20Virtual types and casts are not required for a basic exception-system but are
21useful for advanced exception features. However, \CFA is not object-oriented so
22there is no obvious concept of virtuals. Hence, to create advanced exception
23features for this work, I needed to design and implement a virtual-like
24system for \CFA.
25
26% NOTE: Maybe we should but less of the rational here.
27Object-oriented languages often organized exceptions into a simple hierarchy,
28\eg Java.
29\begin{center}
30\setlength{\unitlength}{4000sp}%
31\begin{picture}(1605,612)(2011,-1951)
32\put(2100,-1411){\vector(1, 0){225}}
33\put(3450,-1411){\vector(1, 0){225}}
34\put(3550,-1411){\line(0,-1){225}}
35\put(3550,-1636){\vector(1, 0){150}}
36\put(3550,-1636){\line(0,-1){225}}
37\put(3550,-1861){\vector(1, 0){150}}
38\put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}}
39\put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}}
40\put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}}
41\put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}}
42\put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}}
43\end{picture}%
44\end{center}
45The hierarchy provides the ability to handle an exception at different degrees
46of specificity (left to right). Hence, it is possible to catch a more general
47exception-type in higher-level code where the implementation details are
48unknown, which reduces tight coupling to the lower-level implementation.
49Otherwise, low-level code changes require higher-level code changes, \eg,
50changing from raising @underflow@ to @overflow@ at the low level means changing
51the matching catch at the high level versus catching the general @arithmetic@
52exception. In detail, each virtual type may have a parent and can have any
53number of children. A type's descendants are its children and its children's
54descendants. A type may not be its own descendant.
55
56The exception hierarchy allows a handler (@catch@ clause) to match multiple
57exceptions, \eg a base-type handler catches both base and derived
58exception-types.
59\begin{cfa}
60try {
61        ...
62} catch(arithmetic &) {
63        ... // handle arithmetic, underflow, overflow, zerodivide
64}
65\end{cfa}
66Most exception mechanisms perform a linear search of the handlers and select
67the first matching handler, so the order of handers is now important because
68matching is many to one.
69
70Each virtual type needs an associated virtual table. A virtual table is a
71structure with fields for all the virtual members of a type. A virtual type has
72all the virtual members of its parent and can add more. It may also update the
73values of the virtual members and often does.
74
75While much of the virtual infrastructure is created, it is currently only used
76internally for exception handling. The only user-level feature is the virtual
77cast, which is the same as the \Cpp \lstinline[language=C++]|dynamic_cast|.
78\label{p:VirtualCast}
79\begin{cfa}
80(virtual TYPE)EXPRESSION
81\end{cfa}
82Note, the syntax and semantics matches a C-cast, rather than the function-like
83\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
84a pointer to a virtual type.
85The cast dynamically checks if the @EXPRESSION@ type is the same or a subtype
86of @TYPE@, and if true, returns a pointer to the
87@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
88
89\section{Exception}
90% Leaving until later, hopefully it can talk about actual syntax instead
91% of my many strange macros. Syntax aside I will also have to talk about the
92% features all exceptions support.
93
94Exceptions are defined by the trait system; there are a series of traits, and
95if a type satisfies them, then it can be used as an exception. The following
96is the base trait all exceptions need to match.
97\begin{cfa}
98trait is_exception(exceptT &, virtualT &) {
99        virtualT const & get_exception_vtable(exceptT *);
100};
101\end{cfa}
102The trait is defined over two types, the exception type and the virtual table
103type. This should be one-to-one, each exception type has only one virtual
104table type and vice versa. The only assertion in the trait is
105@get_exception_vtable@, which takes a pointer of the exception type and
106returns a reference to the virtual table type instance.
107
108The function @get_exception_vtable@ is actually a constant function.
109Recardless of the value passed in (including the null pointer) it should
110return a reference to the virtual table instance for that type.
111The reason it is a function instead of a constant is that it make type
112annotations easier to write as you can use the exception type instead of the
113virtual table type; which usually has a mangled name.
114% Also \CFA's trait system handles functions better than constants and doing
115% it this way reduce the amount of boiler plate we need.
116
117% I did have a note about how it is the programmer's responsibility to make
118% sure the function is implemented correctly. But this is true of every
119% similar system I know of (except Agda's I guess) so I took it out.
120
121There are two more traits for exceptions @is_termination_exception@ and
122@is_resumption_exception@. They are defined as follows:
123
124\begin{cfa}
125trait is_termination_exception(
126                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
127        void defaultTerminationHandler(exceptT &);
128};
129
130trait is_resumption_exception(
131                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
132        void defaultResumptionHandler(exceptT &);
133};
134\end{cfa}
135
136In other words they make sure that a given type and virtual type is an
137exception and defines one of the two default handlers. These default handlers
138are used in the main exception handling operations \see{Exception Handling}
139and their use will be detailed there.
140
141However all three of these traits can be trickly to use directly.
142There is a bit of repetition required but
143the largest issue is that the virtual table type is mangled and not in a user
144facing way. So there are three macros that can be used to wrap these traits
145when you need to refer to the names:
146@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
147
148All take one or two arguments. The first argument is the name of the
149exception type. Its unmangled and mangled form are passed to the trait.
150The second (optional) argument is a parenthesized list of polymorphic
151arguments. This argument should only with polymorphic exceptions and the
152list will be passed to both types.
153In the current set-up the base name and the polymorphic arguments have to
154match so these macros can be used without losing flexability.
155
156For example consider a function that is polymorphic over types that have a
157defined arithmetic exception:
158\begin{cfa}
159forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
160void some_math_function(Num & left, Num & right);
161\end{cfa}
162
163\section{Exception Handling}
164\CFA provides two kinds of exception handling, termination and resumption.
165These twin operations are the core of the exception handling mechanism and
166are the reason for the features of exceptions.
167This section will cover the general patterns shared by the two operations and
168then go on to cover the details each individual operation.
169
170Both operations follow the same set of steps to do their operation. They both
171start with the user preforming a throw on an exception.
172Then there is the search for a handler, if one is found than the exception
173is caught and the handler is run. After that control returns to normal
174execution.
175
176If the search fails a default handler is run and then control
177returns to normal execution immediately. That is where the default handlers
178@defaultTermiationHandler@ and @defaultResumptionHandler@ are used.
179
180\subsection{Termination}
181\label{s:Termination}
182
183Termination handling is more familiar kind and used in most programming
184languages with exception handling.
185It is dynamic, non-local goto. If a throw is successful then the stack will
186be unwound and control will (usually) continue in a different function on
187the call stack. They are commonly used when an error has occured and recovery
188is impossible in the current function.
189
190% (usually) Control can continue in the current function but then a different
191% control flow construct should be used.
192
193A termination throw is started with the @throw@ statement:
194\begin{cfa}
195throw EXPRESSION;
196\end{cfa}
197The expression must return a reference to a termination exception, where the
198termination exception is any type that satifies @is_termination_exception@
199at the call site.
200Through \CFA's trait system the functions in the traits are passed into the
201throw code. A new @defaultTerminationHandler@ can be defined in any scope to
202change the throw's behavior (see below).
203
204The throw will copy the provided exception into managed memory. It is the
205user's responcibility to ensure the original exception is cleaned up if the
206stack is unwound (allocating it on the stack should be sufficient).
207
208Then the exception system searches the stack using the copied exception.
209It starts starts from the throw and proceeds to the base of the stack,
210from callee to caller.
211At each stack frame, a check is made for resumption handlers defined by the
212@catch@ clauses of a @try@ statement.
213\begin{cfa}
214try {
215        GUARDED_BLOCK
216} catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
217        HANDLER_BLOCK$\(_1\)$
218} catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
219        HANDLER_BLOCK$\(_2\)$
220}
221\end{cfa}
222When viewed on its own a try statement will simply exceute the statements in
223@GUARDED_BLOCK@ and when those are finished the try statement finishes.
224
225However, while the guarded statements are being executed, including any
226functions they invoke, all the handlers following the try block are now
227or any functions invoked from those
228statements, throws an exception, and the exception
229is not handled by a try statement further up the stack, the termination
230handlers are searched for a matching exception type from top to bottom.
231
232Exception matching checks the representation of the thrown exception-type is
233the same or a descendant type of the exception types in the handler clauses. If
234it is the same of a descendent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
235bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
236are executed. If control reaches the end of the handler, the exception is
237freed and control continues after the try statement.
238
239If no handler is found during the search then the default handler is run.
240Through \CFA's trait system the best match at the throw sight will be used.
241This function is run and is passed the copied exception. After the default
242handler is run control continues after the throw statement.
243
244There is a global @defaultTerminationHandler@ that cancels the current stack
245with the copied exception. However it is generic over all exception types so
246new default handlers can be defined for different exception types and so
247different exception types can have different default handlers.
248
249\subsection{Resumption}
250\label{s:Resumption}
251
252Resumption exception handling is a less common form than termination but is
253just as old~\cite{Goodenough75} and is in some sense simpler.
254It is a dynamic, non-local function call. If the throw is successful a
255closure will be taken from up the stack and executed, after which the throwing
256function will continue executing.
257These are most often used when an error occured and if the error is repaired
258then the function can continue.
259
260A resumption raise is started with the @throwResume@ statement:
261\begin{cfa}
262throwResume EXPRESSION;
263\end{cfa}
264The semantics of the @throwResume@ statement are like the @throw@, but the
265expression has return a reference a type that satifies the trait
266@is_resumption_exception@. The assertions from this trait are available to
267the exception system while handling the exception.
268
269At runtime, no copies are made. As the stack is not unwound the exception and
270any values on the stack will remain in scope while the resumption is handled.
271
272Then the exception system searches the stack using the provided exception.
273It starts starts from the throw and proceeds to the base of the stack,
274from callee to caller.
275At each stack frame, a check is made for resumption handlers defined by the
276@catchResume@ clauses of a @try@ statement.
277\begin{cfa}
278try {
279        GUARDED_BLOCK
280} catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
281        HANDLER_BLOCK$\(_1\)$
282} catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
283        HANDLER_BLOCK$\(_2\)$
284}
285\end{cfa}
286If the handlers are not involved in a search this will simply execute the
287@GUARDED_BLOCK@ and then continue to the next statement.
288Its purpose is to add handlers onto the stack.
289(Note, termination and resumption handlers may be intermixed in a @try@
290statement but the kind of throw must be the same as the handler for it to be
291considered as a possible match.)
292
293If a search for a resumption handler reaches a try block it will check each
294@catchResume@ clause, top-to-bottom.
295At each handler if the thrown exception is or is a child type of
296@EXCEPTION_TYPE@$_i$ then the a pointer to the exception is bound to
297@NAME@$_i$ and then @HANDLER_BLOCK@$_i$ is executed. After the block is
298finished control will return to the @throwResume@ statement.
299
300Like termination, if no resumption handler is found, the default handler
301visible at the throw statement is called. It will use the best match at the
302call sight according to \CFA's overloading rules. The default handler is
303passed the exception given to the throw. When the default handler finishes
304execution continues after the throw statement.
305
306There is a global @defaultResumptionHandler@ is polymorphic over all
307termination exceptions and preforms a termination throw on the exception.
308The @defaultTerminationHandler@ for that throw is matched at the original
309throw statement (the resumption @throwResume@) and it can be customized by
310introducing a new or better match as well.
311
312% \subsubsection?
313
314A key difference between resumption and termination is that resumption does
315not unwind the stack. A side effect that is that when a handler is matched
316and run it's try block (the guarded statements) and every try statement
317searched before it are still on the stack. This can lead to the recursive
318resumption problem.
319
320The recursive resumption problem is any situation where a resumption handler
321ends up being called while it is running.
322Consider a trivial case:
323\begin{cfa}
324try {
325        throwResume (E &){};
326} catchResume(E *) {
327        throwResume (E &){};
328}
329\end{cfa}
330When this code is executed the guarded @throwResume@ will throw, start a
331search and match the handler in the @catchResume@ clause. This will be
332call and placed on the stack on top of the try-block. The second throw then
333throws and will seach the same try block and put call another instance of the
334same handler leading to an infinite loop.
335
336This situation is trivial and easy to avoid, but much more complex cycles
337can form with multiple handlers and different exception types.
338
339To prevent all of these cases we mask sections of the stack, or equvilantly
340the try statements on the stack, so that the resumption seach skips over
341them and continues with the next unmasked section of the stack.
342
343A section of the stack is marked when it is searched to see if it contains
344a handler for an exception and unmarked when that exception has been handled
345or the search was completed without finding a handler.
346
347% This might need a diagram. But it is an important part of the justification
348% of the design of the traversal order.
349\begin{verbatim}
350       throwResume2 ----------.
351            |                 |
352 generated from handler       |
353            |                 |
354         handler              |
355            |                 |
356        throwResume1 -----.   :
357            |             |   :
358           try            |   : search skip
359            |             |   :
360        catchResume  <----'   :
361            |                 |
362\end{verbatim}
363
364The rules can be remembered as thinking about what would be searched in
365termination. So when a throw happens in a handler; a termination handler
366skips everything from the original throw to the original catch because that
367part of the stack has been unwound, a resumption handler skips the same
368section of stack because it has been masked.
369A throw in a default handler will preform the same search as the original
370throw because; for termination nothing has been unwound, for resumption
371the mask will be the same.
372
373The symmetry with termination is why this pattern was picked. Other patterns,
374such as marking just the handlers that caught, also work but lack the
375symmetry whih means there is more to remember.
376
377\section{Conditional Catch}
378Both termination and resumption handler clauses can be given an additional
379condition to further control which exceptions they handle:
380\begin{cfa}
381catch (EXCEPTION_TYPE * NAME ; CONDITION)
382\end{cfa}
383First, the same semantics is used to match the exception type. Second, if the
384exception matches, @CONDITION@ is executed. The condition expression may
385reference all names in scope at the beginning of the try block and @NAME@
386introduced in the handler clause. If the condition is true, then the handler
387matches. Otherwise, the exception search continues as if the exception type
388did not match.
389\begin{cfa}
390try {
391        f1 = open( ... );
392        f2 = open( ... );
393        ...
394} catch( IOFailure * f ; fd( f ) == f1 ) {
395        // only handle IO failure for f1
396}
397\end{cfa}
398Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
399exception if not @f1@ is different because the reraise does not examine any of
400remaining handlers in the current try statement.
401
402\section{Rethrowing}
403\colour{red}{From Andrew: I recomend we talk about why the language doesn't
404have rethrows/reraises instead.}
405
406\label{s:Rethrowing}
407Within the handler block or functions called from the handler block, it is
408possible to reraise the most recently caught exception with @throw@ or
409@throwResume@, respectively.
410\begin{cfa}
411try {
412        ...
413} catch( ... ) {
414        ... throw;
415} catchResume( ... ) {
416        ... throwResume;
417}
418\end{cfa}
419The only difference between a raise and a reraise is that reraise does not
420create a new exception; instead it continues using the current exception, \ie
421no allocation and copy. However the default handler is still set to the one
422visible at the raise point, and hence, for termination could refer to data that
423is part of an unwound stack frame. To prevent this problem, a new default
424handler is generated that does a program-level abort.
425
426\section{Finally Clauses}
427Finally clauses are used to preform unconditional clean-up when leaving a
428scope. They are placed at the end of a try statement:
429\begin{cfa}
430try {
431        GUARDED_BLOCK
432} ... // any number or kind of handler clauses
433... finally {
434        FINALLY_BLOCK
435}
436\end{cfa}
437The @FINALLY_BLOCK@ is executed when the try statement is removed from the
438stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
439finishes or during an unwind.
440The only time the block is not executed is if the program is exited before
441the stack is unwound.
442
443Execution of the finally block should always finish, meaning control runs off
444the end of the block. This requirement ensures always continues as if the
445finally clause is not present, \ie finally is for cleanup not changing control
446flow. Because of this requirement, local control flow out of the finally block
447is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
448@return@ that causes control to leave the finally block. Other ways to leave
449the finally block, such as a long jump or termination are much harder to check,
450and at best requiring additional run-time overhead, and so are mearly
451discouraged.
452
453Not all languages with exceptions have finally clauses. Notably \Cpp does
454without it as descructors serve a similar role. Although destructors and
455finally clauses can be used in many of the same areas they have their own
456use cases like top-level functions and lambda functions with closures.
457Destructors take a bit more work to set up but are much easier to reuse while
458finally clauses are good for once offs and can include local information.
459
460\section{Cancellation}
461Cancellation is a stack-level abort, which can be thought of as as an
462uncatchable termination. It unwinds the entirety of the current stack, and if
463possible forwards the cancellation exception to a different stack.
464
465Cancellation is not an exception operation like termination or resumption.
466There is no special statement for starting a cancellation; instead the standard
467library function @cancel_stack@ is called passing an exception. Unlike a
468throw, this exception is not used in matching only to pass information about
469the cause of the cancellation.
470(This also means matching cannot fail so there is no default handler either.)
471
472After @cancel_stack@ is called the exception is copied into the exception
473handling mechanism's memory. Then the entirety of the current stack is
474unwound. After that it depends one which stack is being cancelled.
475\begin{description}
476\item[Main Stack:]
477The main stack is the one used by the program main at the start of execution,
478and is the only stack in a sequential program. Even in a concurrent program
479the main stack is only dependent on the environment that started the program.
480Hence, when the main stack is cancelled there is nowhere else in the program
481to notify. After the stack is unwound, there is a program-level abort.
482
483\item[Thread Stack:]
484A thread stack is created for a @thread@ object or object that satisfies the
485@is_thread@ trait. A thread only has two points of communication that must
486happen: start and join. As the thread must be running to perform a
487cancellation, it must occur after start and before join, so join is used
488for communication here.
489After the stack is unwound, the thread halts and waits for
490another thread to join with it. The joining thread checks for a cancellation,
491and if present, resumes exception @ThreadCancelled@.
492
493There is a subtle difference between the explicit join (@join@ function) and
494implicit join (from a destructor call). The explicit join takes the default
495handler (@defaultResumptionHandler@) from its calling context, which is used if
496the exception is not caught. The implicit join does a program abort instead.
497
498This semantics is for safety. If an unwind is triggered while another unwind
499is underway only one of them can proceed as they both want to ``consume'' the
500stack. Letting both try to proceed leads to very undefined behaviour.
501Both termination and cancellation involve unwinding and, since the default
502@defaultResumptionHandler@ preforms a termination that could more easily
503happen in an implicate join inside a destructor. So there is an error message
504and an abort instead.
505\todo{Perhaps have a more general disucssion of unwind collisions before
506this point.}
507
508The recommended way to avoid the abort is to handle the intial resumption
509from the implicate join. If required you may put an explicate join inside a
510finally clause to disable the check and use the local
511@defaultResumptionHandler@ instead.
512
513\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
514or object that satisfies the @is_coroutine@ trait. A coroutine only knows of
515two other coroutines, its starter and its last resumer. Of the two the last
516resumer has the tightest coupling to the coroutine it activated and the most
517up-to-date information.
518
519Hence, cancellation of the active coroutine is forwarded to the last resumer
520after the stack is unwound. When the resumer restarts, it resumes exception
521@CoroutineCancelled@, which is polymorphic over the coroutine type and has a
522pointer to the cancelled coroutine.
523
524The resume function also has an assertion that the @defaultResumptionHandler@
525for the exception. So it will use the default handler like a regular throw.
526\end{description}
Note: See TracBrowser for help on using the repository browser.