source: doc/theses/andrew_beach_MMath/features.tex @ 29c9b23

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

Andrew MMath: Supposed to be focused on features but it ended up leaking out.

  • Property mode set to 100644
File size: 21.5 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
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
121\section{Raise}
122\CFA provides two kinds of exception raise: termination
123\see{\VRef{s:Termination}} and resumption \see{\VRef{s:Resumption}}, which are
124specified with the following traits.
125\begin{cfa}
126trait is_termination_exception(
127                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
128        void defaultTerminationHandler(exceptT &);
129};
130\end{cfa}
131The function is required to allow a termination raise, but is only called if a
132termination raise does not find an appropriate handler.
133
134Allowing a resumption raise is similar.
135\begin{cfa}
136trait is_resumption_exception(
137                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
138        void defaultResumptionHandler(exceptT &);
139};
140\end{cfa}
141The function is required to allow a resumption raise, but is only called if a
142resumption raise does not find an appropriate handler.
143
144Finally there are three convenience macros for referring to the these traits:
145@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
146All three traits are hard to use while naming the virtual table as it has an
147internal mangled name. These macros take the exception name as their first
148argument and do the mangling. They all take a second argument for polymorphic
149types which is the parenthesized list of polymorphic arguments. These
150arguments are passed to both the exception type and the virtual table type as
151the arguments do have to match.
152
153For example consider a function that is polymorphic over types that have a
154defined arithmetic exception:
155\begin{cfa}
156forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
157void some_math_function(Num & left, Num & right);
158\end{cfa}
159
160\subsection{Termination}
161\label{s:Termination}
162
163Termination raise, called ``throw'', is familiar and used in most programming
164languages with exception handling. The semantics of termination is: search the
165stack for a matching handler, unwind the stack frames to the matching handler,
166execute the handler, and continue execution after the handler. Termination is
167used when execution \emph{cannot} return to the throw. To continue execution,
168the program must \emph{recover} in the handler from the failed (unwound)
169execution at the raise to safely proceed after the handler.
170
171A termination raise is started with the @throw@ statement:
172\begin{cfa}
173throw EXPRESSION;
174\end{cfa}
175The expression must return a reference to a termination exception, where the
176termination exception is any type that satifies @is_termination_exception@
177at the call site.
178Through \CFA's trait system the functions in the traits are passed into the
179throw code. A new @defaultTerminationHandler@ can be defined in any scope to
180change the throw's behavior (see below).
181
182At runtime, the exception returned by the expression
183is copied into managed memory (heap) to ensure it remains in
184scope during unwinding. It is the user's responsibility to ensure the original
185exception object at the throw is freed when it goes out of scope. Being
186allocated on the stack is sufficient for this.
187
188Then the exception system searches the stack starting from the throw and
189proceeding towards the base of the stack, from callee to caller. At each stack
190frame, a check is made for termination handlers defined by the @catch@ clauses
191of a @try@ statement.
192\begin{cfa}
193try {
194        GUARDED_BLOCK
195} catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) { // termination handler 1
196        HANDLER_BLOCK$\(_1\)$
197} catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) { // termination handler 2
198        HANDLER_BLOCK$\(_2\)$
199}
200\end{cfa}
201The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
202functions invoked from those statements, throws an exception, and the exception
203is not handled by a try statement further up the stack, the termination
204handlers are searched for a matching exception type from top to bottom.
205
206Exception matching checks the representation of the thrown exception-type is
207the same or a descendant type of the exception types in the handler clauses. If
208it is the same of a descendent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
209bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
210are executed. If control reaches the end of the handler, the exception is
211freed and control continues after the try statement.
212
213The default handler visible at the throw statement is used if no matching
214termination handler is found after the entire stack is searched. At that point,
215the default handler is called with a reference to the exception object
216generated at the throw. If the default handler returns, control continues
217from after the throw statement. This feature allows
218each exception type to define its own action, such as printing an informative
219error message, when an exception is not handled in the program.
220However the default handler for all exception types triggers a cancellation
221using the exception.
222
223\subsection{Resumption}
224\label{s:Resumption}
225
226Resumption raise, called ``resume'', is as old as termination
227raise~\cite{Goodenough75} but is less popular. In many ways, resumption is
228simpler and easier to understand, as it is simply a dynamic call.
229The semantics of resumption is: search the stack for a matching handler,
230execute the handler, and continue execution after the resume. Notice, the stack
231cannot be unwound because execution returns to the raise point. Resumption is
232used used when execution \emph{can} return to the resume. To continue
233execution, the program must \emph{correct} in the handler for the failed
234execution at the raise so execution can safely continue after the resume.
235
236A resumption raise is started with the @throwResume@ statement:
237\begin{cfa}
238throwResume EXPRESSION;
239\end{cfa}
240The semantics of the @throwResume@ statement are like the @throw@, but the
241expression has return a reference a type that satifies the trait
242@is_resumption_exception@. Like with termination the exception system can
243use these assertions while (throwing/raising/handling) the exception.
244
245At runtime, no copies are made. As the stack is not unwound the exception and
246any values on the stack will remain in scope while the resumption is handled.
247
248Then the exception system searches the stack starting from the resume and
249proceeding to the base of the stack, from callee to caller. At each stack
250frame, a check is made for resumption handlers defined by the @catchResume@
251clauses of a @try@ statement.
252\begin{cfa}
253try {
254        GUARDED_BLOCK
255} catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
256        HANDLER_BLOCK$\(_1\)$
257} catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
258        HANDLER_BLOCK$\(_2\)$
259}
260\end{cfa}
261The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
262functions invoked from those statements, resumes an exception, and the
263exception is not handled by a try statement further up the stack, the
264resumption handlers are searched for a matching exception type from top to
265bottom. (Note, termination and resumption handlers may be intermixed in a @try@
266statement but the kind of raise (throw/resume) only matches with the
267corresponding kind of handler clause.)
268
269The exception search and matching for resumption is the same as for
270termination, including exception inheritance. The difference is when control
271reaches the end of the handler: the resumption handler returns after the resume
272rather than after the try statement. The resume point assumes the handler has
273corrected the problem so execution can safely continue.
274
275Like termination, if no resumption handler is found, the default handler
276visible at the resume statement is called, and the system default action is
277executed.
278
279For resumption, the exception system uses stack marking to partition the
280resumption search. If another resumption exception is raised in a resumption
281handler, the second exception search does not start at the point of the
282original raise. (Remember the stack is not unwound and the current handler is
283at the top of the stack.) The search for the second resumption starts at the
284current point on the stack because new try statements may have been pushed by
285the handler or functions called from the handler. If there is no match back to
286the point of the current handler, the search skips\label{p:searchskip} the
287stack frames already searched by the first resume and continues after
288the try statement. The default handler always continues from default
289handler associated with the point where the exception is created.
290
291% This might need a diagram. But it is an important part of the justification
292% of the design of the traversal order.
293\begin{verbatim}
294       throwResume2 ----------.
295            |                 |
296 generated from handler       |
297            |                 |
298         handler              |
299            |                 |
300        throwResume1 -----.   :
301            |             |   :
302           try            |   : search skip
303            |             |   :
304        catchResume  <----'   :
305            |                 |
306\end{verbatim}
307
308This resumption search pattern reflects the one for termination, and so
309should come naturally to most programmers.
310However, it avoids the \emph{recursive resumption} problem.
311If parts of the stack are searched multiple times, loops
312can easily form resulting in infinite recursion.
313
314Consider the trivial case:
315\begin{cfa}
316try {
317        throwResume (E &){}; // first
318} catchResume(E *) {
319        throwResume (E &){}; // second
320}
321\end{cfa}
322If this handler is ever used it will be placed on top of the stack above the
323try statement. If the stack was not masked than the @throwResume@ in the
324handler would always be caught by the handler, leading to an infinite loop.
325Masking avoids this problem and other more complex versions of it involving
326multiple handlers and exception types.
327
328Other masking stratagies could be used; such as masking the handlers that
329have caught an exception. This one was choosen because it creates a symmetry
330with termination (masked sections of the stack would be unwound with
331termination) and having only one pattern to learn is easier.
332
333\section{Conditional Catch}
334Both termination and resumption handler clauses can be given an additional
335condition to further control which exceptions they handle:
336\begin{cfa}
337catch (EXCEPTION_TYPE * NAME ; @CONDITION@)
338\end{cfa}
339First, the same semantics is used to match the exception type. Second, if the
340exception matches, @CONDITION@ is executed. The condition expression may
341reference all names in scope at the beginning of the try block and @NAME@
342introduced in the handler clause. If the condition is true, then the handler
343matches. Otherwise, the exception search continues at the next appropriate kind
344of handler clause in the try block.
345\begin{cfa}
346try {
347        f1 = open( ... );
348        f2 = open( ... );
349        ...
350} catch( IOFailure * f ; fd( f ) == f1 ) {
351        // only handle IO failure for f1
352}
353\end{cfa}
354Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
355exception if not @f1@ is different because the reraise does not examine any of
356remaining handlers in the current try statement.
357
358\section{Reraise}
359\color{red}{From Andrew: I recomend we talk about why the language doesn't
360have rethrows/reraises instead.}
361
362\label{s:Reraise}
363Within the handler block or functions called from the handler block, it is
364possible to reraise the most recently caught exception with @throw@ or
365@throwResume@, respective.
366\begin{cfa}
367try {
368        ...
369} catch( ... ) {
370        ... throw; // rethrow
371} catchResume( ... ) {
372        ... throwResume; // reresume
373}
374\end{cfa}
375The only difference between a raise and a reraise is that reraise does not
376create a new exception; instead it continues using the current exception, \ie
377no allocation and copy. However the default handler is still set to the one
378visible at the raise point, and hence, for termination could refer to data that
379is part of an unwound stack frame. To prevent this problem, a new default
380handler is generated that does a program-level abort.
381
382\section{Finally Clauses}
383A @finally@ clause may be placed at the end of a @try@ statement.
384\begin{cfa}
385try {
386        GUARDED_BLOCK
387} ... // any number or kind of handler clauses
388... finally {
389        FINALLY_BLOCK
390}
391\end{cfa}
392The @FINALLY_BLOCK@ is executed when the try statement is removed from the
393stack, including when the @GUARDED_BLOCK@ or any handler clause finishes or
394during an unwind.
395The only time the block is not executed is if the program is exited before
396that happens.
397
398Execution of the finally block should always finish, meaning control runs off
399the end of the block. This requirement ensures always continues as if the
400finally clause is not present, \ie finally is for cleanup not changing control
401flow. Because of this requirement, local control flow out of the finally block
402is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
403@return@ that causes control to leave the finally block. Other ways to leave
404the finally block, such as a long jump or termination are much harder to check,
405and at best requiring additional run-time overhead, and so are discouraged.
406
407\section{Cancellation}
408Cancellation is a stack-level abort, which can be thought of as as an
409uncatchable termination. It unwinds the entirety of the current stack, and if
410possible forwards the cancellation exception to a different stack.
411
412Cancellation is not an exception operation like termination or resumption.
413There is no special statement for starting a cancellation; instead the standard
414library function @cancel_stack@ is called passing an exception. Unlike a
415raise, this exception is not used in matching only to pass information about
416the cause of the cancellation.
417
418Handling of a cancellation depends on which stack is being cancelled.
419\begin{description}
420\item[Main Stack:]
421The main stack is the one used by the program main at the start of execution,
422and is the only stack in a sequential program. Even in a concurrent program
423the main stack is only dependent on the environment that started the program.
424Hence, when the main stack is cancelled there is nowhere else in the program
425to notify. After the stack is unwound, there is a program-level abort.
426
427\item[Thread Stack:]
428A thread stack is created for a @thread@ object or object that satisfies the
429@is_thread@ trait. A thread only has two points of communication that must
430happen: start and join. As the thread must be running to perform a
431cancellation, it must occur after start and before join, so join is used
432for communication here.
433After the stack is unwound, the thread halts and waits for
434another thread to join with it. The joining thread checks for a cancellation,
435and if present, resumes exception @ThreadCancelled@.
436
437There is a subtle difference between the explicit join (@join@ function) and
438implicit join (from a destructor call). The explicit join takes the default
439handler (@defaultResumptionHandler@) from its calling context, which is used if
440the exception is not caught. The implicit join does a program abort instead.
441
442This semantics is for safety. If an unwind is triggered while another unwind
443is underway only one of them can proceed as they both want to ``consume'' the
444stack. Letting both try to proceed leads to very undefined behaviour.
445Both termination and cancellation involve unwinding and, since the default
446@defaultResumptionHandler@ preforms a termination that could more easily
447happen in an implicate join inside a destructor. So there is an error message
448and an abort instead.
449
450The recommended way to avoid the abort is to handle the intial resumption
451from the implicate join. If required you may put an explicate join inside a
452finally clause to disable the check and use the local
453@defaultResumptionHandler@ instead.
454
455\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
456or object that satisfies the @is_coroutine@ trait. A coroutine only knows of
457two other coroutines, its starter and its last resumer. The last resumer has
458the tightest coupling to the coroutine it activated. Hence, cancellation of
459the active coroutine is forwarded to the last resumer after the stack is
460unwound, as the last resumer has the most precise knowledge about the current
461execution. When the resumer restarts, it resumes exception
462@CoroutineCancelled@, which is polymorphic over the coroutine type and has a
463pointer to the cancelled coroutine.
464
465The resume function also has an assertion that the @defaultResumptionHandler@
466for the exception. So it will use the default handler like a regular throw.
467\end{description}
Note: See TracBrowser for help on using the repository browser.