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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 4706098 was 4706098, checked in by Peter A. Buhr <pabuhr@…>, 9 months ago

proofread chapter "features", and adjust formatting

  • Property mode set to 100644
File size: 19.7 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 required for a basic exception-system but are
8useful for advanced exception features. However, \CFA is not object-oriented so
9there is no obvious concept of virtuals.  Hence, to create advanced exception
10features for this work, I needed to designed and implemented a virtual-like
11system for \CFA.
12
13Object-oriented languages often organized exceptions into a simple hierarchy,
14\eg Java.
15\begin{center}
16\setlength{\unitlength}{4000sp}%
17\begin{picture}(1605,612)(2011,-1951)
18\put(2100,-1411){\vector(1, 0){225}}
19\put(3450,-1411){\vector(1, 0){225}}
20\put(3550,-1411){\line(0,-1){225}}
21\put(3550,-1636){\vector(1, 0){150}}
22\put(3550,-1636){\line(0,-1){225}}
23\put(3550,-1861){\vector(1, 0){150}}
24\put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}}
25\put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}}
26\put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}}
27\put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}}
28\put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}}
29\end{picture}%
30\end{center}
31The hierarchy provides the ability to handle an exception at different degrees
32of specificity (left to right).  Hence, it is possible to catch a more general
33exception-type in higher-level code where the implementation details are
34unknown, which reduces tight coupling to the lower-level implementation.
35Otherwise, low-level code changes require higher-level code changes, \eg,
36changing from raising @underflow@ to @overflow@ at the low level means changing
37the matching catch at the high level versus catching the general @arithmetic@
38exception. In detail, each virtual type may have a parent and can have any
39number of children. A type's descendants are its children and its children's
40descendants. A type may not be its own descendant.
41
42The exception hierarchy allows a handler (@catch@ clause) to match multiple
43exceptions, \eg a base-type handler catches both base and derived
44exception-types.
45\begin{cfa}
46try {
47        ...
48} catch(arithmetic &) {
49        ... // handle arithmetic, underflow, overflow, zerodivide
50}
51\end{cfa}
52Most exception mechanisms perform a linear search of the handlers and select
53the first matching handler, so the order of handers is now important because
54matching is many to one.
55
56Each virtual type needs an associated virtual table. A virtual table is a
57structure with fields for all the virtual members of a type. A virtual type has
58all the virtual members of its parent and can add more. It may also update the
59values of the virtual members and often does.
60
61While much of the virtual infrastructure is created, it is currently only used
62internally for exception handling. The only user-level feature is the virtual
63cast, which is the same as the \CC \lstinline[language=C++]|dynamic_cast|.
64\begin{cfa}
65(virtual TYPE)EXPRESSION
66\end{cfa}
67Note, the syntax and semantics matches a C-cast, rather than the unusual \CC
68syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be a
69pointer to a virtual type. The cast dynamically checks if the @EXPRESSION@ type
70is the same or a subtype of @TYPE@, and if true, returns a pointer to the
71@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
72
73\section{Exception}
74% Leaving until later, hopefully it can talk about actual syntax instead
75% of my many strange macros. Syntax aside I will also have to talk about the
76% features all exceptions support.
77
78Exceptions are defined by the trait system; there are a series of traits, and
79if a type satisfies them, then it can be used as an exception.  The following
80is the base trait all exceptions need to match.
81\begin{cfa}
82trait is_exception(exceptT &, virtualT &) {
83        virtualT const & @get_exception_vtable@(exceptT *);
84};
85\end{cfa}
86The function takes any pointer, including the null pointer, and returns a
87reference to the virtual-table object. Defining this function also establishes
88the virtual type and a virtual-table pair to the \CFA type-resolver and
89promises @exceptT@ is a virtual type and a child of the base exception-type.
90
91{\color{blue} PAB: I do not understand this paragraph.}
92One odd thing about @get_exception_vtable@ is that it should always be a
93constant function, returning the same value regardless of its argument.  A
94pointer or reference to the virtual table instance could be used instead,
95however using a function has some ease of implementation advantages and allows
96for easier disambiguation because the virtual type name (or the address of an
97instance that is in scope) can be used instead of the mangled virtual table
98name.  Also note the use of the word ``promise'' in the trait
99description. Currently, \CFA cannot check to see if either @exceptT@ or
100@virtualT@ match the layout requirements. This is considered part of
101@get_exception_vtable@'s correct implementation.
102
103\section{Raise}
104\CFA provides two kinds of exception raise: termination (see
105\VRef{s:Termination}) and resumption (see \VRef{s:Resumption}), which are
106specified with the following traits.
107\begin{cfa}
108trait is_termination_exception(
109                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
110        void @defaultTerminationHandler@(exceptT &);
111};
112\end{cfa}
113The function is required to allow a termination raise, but is only called if a
114termination raise does not find an appropriate handler.
115
116Allowing a resumption raise is similar.
117\begin{cfa}
118trait is_resumption_exception(
119                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
120        void @defaultResumptionHandler@(exceptT &);
121};
122\end{cfa}
123The function is required to allow a resumption raise, but is only called if a
124resumption raise does not find an appropriate handler.
125
126Finally there are three convenience macros for referring to the these traits:
127@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.  Each
128takes the virtual type's name, and for polymorphic types only, the
129parenthesized list of polymorphic arguments. These macros do the name mangling
130to get the virtual-table name and provide the arguments to both sides
131{\color{blue}(PAB: What's a ``side''?)}
132
133\subsection{Termination}
134\label{s:Termination}
135
136Termination raise, called ``throw'', is familiar and used in most programming
137languages with exception handling. The semantics of termination is: search the
138stack for a matching handler, unwind the stack frames to the matching handler,
139execute the handler, and continue execution after the handler. Termination is
140used when execution \emph{cannot} return to the throw. To continue execution,
141the program must \emph{recover} in the handler from the failed (unwound)
142execution at the raise to safely proceed after the handler.
143
144A termination raise is started with the @throw@ statement:
145\begin{cfa}
146throw EXPRESSION;
147\end{cfa}
148The expression must return a termination-exception reference, where the
149termination exception has a type with a @void defaultTerminationHandler(T &)@
150(default handler) defined. The handler is found at the call site using \CFA's
151trait system and passed into the exception system along with the exception
152itself.
153
154At runtime, a representation of the exception type and an instance of the
155exception type is copied into managed memory (heap) to ensure it remains in
156scope during unwinding. It is the user's responsibility to ensure the original
157exception object at the throw is freed when it goes out of scope. Being
158allocated on the stack is sufficient for this.
159
160Then the exception system searches the stack starting from the throw and
161proceeding towards the base of the stack, from callee to caller. At each stack
162frame, a check is made for termination handlers defined by the @catch@ clauses
163of a @try@ statement.
164\begin{cfa}
165try {
166        GUARDED_BLOCK
167} @catch (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // termination handler 1
168        HANDLER_BLOCK$\(_1\)$
169} @catch (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // termination handler 2
170        HANDLER_BLOCK$\(_2\)$
171}
172\end{cfa}
173The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
174functions invoked from those statements, throws an exception, and the exception
175is not handled by a try statement further up the stack, the termination
176handlers are searched for a matching exception type from top to bottom.
177
178Exception matching checks the representation of the thrown exception-type is
179the same or a descendant type of the exception types in the handler clauses. If
180there is a match, a pointer to the exception object created at the throw is
181bound to @NAME@ and the statements in the associated @HANDLER_BLOCK@ are
182executed. If control reaches the end of the handler, the exception is freed,
183and control continues after the try statement.
184
185The default handler visible at the throw statement is used if no matching
186termination handler is found after the entire stack is searched. At that point,
187the default handler is called with a reference to the exception object
188generated at the throw. If the default handler returns, the system default
189action is executed, which often terminates the program. This feature allows
190each exception type to define its own action, such as printing an informative
191error message, when an exception is not handled in the program.
192
193\subsection{Resumption}
194\label{s:Resumption}
195
196Resumption raise, called ``resume'', is as old as termination
197raise~\cite{Goodenough75} but is less popular. In many ways, resumption is
198simpler and easier to understand, as it is simply a dynamic call (as in
199Lisp). The semantics of resumption is: search the stack for a matching handler,
200execute the handler, and continue execution after the resume. Notice, the stack
201cannot be unwound because execution returns to the raise point. Resumption is
202used used when execution \emph{can} return to the resume. To continue
203execution, the program must \emph{correct} in the handler for the failed
204execution at the raise so execution can safely continue after the resume.
205
206A resumption raise is started with the @throwResume@ statement:
207\begin{cfa}
208throwResume EXPRESSION;
209\end{cfa}
210The semantics of the @throwResume@ statement are like the @throw@, but the
211expression has a type with a @void defaultResumptionHandler(T &)@ (default
212handler) defined, where the handler is found at the call site by the type
213system.  At runtime, a representation of the exception type and an instance of
214the exception type is \emph{not} copied because the stack is maintained during
215the handler search.
216
217Then the exception system searches the stack starting from the resume and
218proceeding towards the base of the stack, from callee to caller. At each stack
219frame, a check is made for resumption handlers defined by the @catchResume@
220clauses of a @try@ statement.
221\begin{cfa}
222try {
223        GUARDED_BLOCK
224} @catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // resumption handler 1
225        HANDLER_BLOCK$\(_1\)$
226} @catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // resumption handler 2
227        HANDLER_BLOCK$\(_2\)$
228}
229\end{cfa}
230The statements in the @GUARDED_BLOCK@ are executed. If those statements, or any
231functions invoked from those statements, resumes an exception, and the
232exception is not handled by a try statement further up the stack, the
233resumption handlers are searched for a matching exception type from top to
234bottom. (Note, termination and resumption handlers may be intermixed in a @try@
235statement but the kind of raise (throw/resume) only matches with the
236corresponding kind of handler clause.)
237
238The exception search and matching for resumption is the same as for
239termination, including exception inheritance. The difference is when control
240reaches the end of the handler: the resumption handler returns after the resume
241rather than after the try statement. The resume point assumes the handler has
242corrected the problem so execution can safely continue.
243
244Like termination, if no resumption handler is found, the default handler
245visible at the resume statement is called, and the system default action is
246executed.
247
248For resumption, the exception system uses stack marking to partition the
249resumption search. If another resumption exception is raised in a resumption
250handler, the second exception search does not start at the point of the
251original raise. (Remember the stack is not unwound and the current handler is
252at the top of the stack.) The search for the second resumption starts at the
253current point on the stack because new try statements may have been pushed by
254the handler or functions called from the handler. If there is no match back to
255the point of the current handler, the search skips the stack frames already
256searched by the first resume and continues after the try statement. The default
257handler always continues from default handler associated with the point where
258the exception is created.
259
260% This might need a diagram. But it is an important part of the justification
261% of the design of the traversal order.
262\begin{verbatim}
263       throwResume2 ----------.
264            |                 |
265 generated from handler       |
266            |                 |
267         handler              |
268            |                 |
269        throwResume1 -----.   :
270            |             |   :
271           try            |   : search skip
272            |             |   :
273        catchResume  <----'   :
274            |                 |
275\end{verbatim}
276
277This resumption search-pattern reflect the one for termination, which matches
278with programmer expectations. However, it avoids the \emph{recursive
279resumption} problem. If parts of the stack are searched multiple times, loops
280can easily form resulting in infinite recursion.
281
282Consider the trivial case:
283\begin{cfa}
284try {
285        throwResume$\(_1\)$ (E &){};
286} catch( E * ) {
287        throwResume;
288}
289\end{cfa}
290Based on termination semantics, programmer expectation is for the re-resume to
291continue searching the stack frames after the try statement. However, the
292current try statement is still on the stack below the handler issuing the
293reresume (see \VRef{s:Reraise}). Hence, the try statement catches the re-raise
294again and does another re-raise \emph{ad infinitum}, which is confusing and
295difficult to debug. The \CFA resumption search-pattern skips the try statement
296so the reresume search continues after the try, mathcing programmer
297expectation.
298
299\section{Conditional Catch}
300Both termination and resumption handler-clauses may perform conditional matching:
301\begin{cfa}
302catch (EXCEPTION_TYPE * NAME ; @CONDITION@)
303\end{cfa}
304First, the same semantics is used to match the exception type. Second, if the
305exception matches, @CONDITION@ is executed. The condition expression may
306reference all names in scope at the beginning of the try block and @NAME@
307introduced in the handler clause.  If the condition is true, then the handler
308matches. Otherwise, the exception search continues at the next appropriate kind
309of handler clause in the try block.
310\begin{cfa}
311try {
312        f1 = open( ... );
313        f2 = open( ... );
314        ...
315} catch( IOFailure * f ; fd( f ) == f1 ) {
316        // only handle IO failure for f1
317}
318\end{cfa}
319Note, catching @IOFailure@, checking for @f1@ in the handler, and reraising the
320exception if not @f1@ is different because the reraise does not examine any of
321remaining handlers in the current try statement.
322
323\section{Reraise}
324\label{s:Reraise}
325Within the handler block or functions called from the handler block, it is
326possible to reraise the most recently caught exception with @throw@ or
327@throwResume@, respective.
328\begin{cfa}
329catch( ... ) {
330        ... throw; // rethrow
331} catchResume( ... ) {
332        ... throwResume; // reresume
333}
334\end{cfa}
335The only difference between a raise and a reraise is that reraise does not
336create a new exception; instead it continues using the current exception, \ie
337no allocation and copy. However the default handler is still set to the one
338visible at the raise point, and hence, for termination could refer to data that
339is part of an unwound stack frame. To prevent this problem, a new default
340handler is generated that does a program-level abort.
341
342
343\section{Finally Clauses}
344A @finally@ clause may be placed at the end of a @try@ statement.
345\begin{cfa}
346try {
347        GUARDED_BLOCK
348} ...   // any number or kind of handler clauses
349} finally {
350        FINALLY_BLOCK
351}
352\end{cfa}
353The @FINALLY_BLOCK@ is executed when the try statement is unwound from the
354stack, \ie when the @GUARDED_BLOCK@ or any handler clause finishes. Hence, the
355finally block is always executed.
356
357Execution of the finally block should always finish, meaning control runs off
358the end of the block. This requirement ensures always continues as if the
359finally clause is not present, \ie finally is for cleanup not changing control
360flow.  Because of this requirement, local control flow out of the finally block
361is forbidden.  The compiler precludes any @break@, @continue@, @fallthru@ or
362@return@ that causes control to leave the finally block. Other ways to leave
363the finally block, such as a long jump or termination are much harder to check,
364and at best requiring additional run-time overhead, and so are discouraged.
365
366\section{Cancellation}
367Cancellation is a stack-level abort, which can be thought of as as an
368uncatchable termination. It unwinds the entirety of the current stack, and if
369possible forwards the cancellation exception to a different stack.
370
371There is no special statement for starting a cancellation; instead the standard
372library function @cancel_stack@ is called passing an exception.  Unlike a
373raise, this exception is not used in matching only to pass information about
374the cause of the cancellation.
375
376Handling of a cancellation depends on which stack is being cancelled.
377\begin{description}
378\item[Main Stack:]
379
380The main stack is the one used by the program main at the start of execution,
381and is the only stack in a sequential program.  Hence, when cancellation is
382forwarded to the main stack, there is no other forwarding stack, so after the
383stack is unwound, there is a program-level abort.
384
385\item[Thread Stack:]
386A thread stack is created for a @thread@ object or object that satisfies the
387@is_thread@ trait.  A thread only has two points of communication that must
388happen: start and join. As the thread must be running to perform a
389cancellation, it must occur after start and before join, so join is a
390cancellation point.  After the stack is unwound, the thread halts and waits for
391another thread to join with it. The joining thread, checks for a cancellation,
392and if present, resumes exception @ThreadCancelled@.
393
394There is a subtle difference between the explicit join (@join@ function) and
395implicit join (from a destructor call). The explicit join takes the default
396handler (@defaultResumptionHandler@) from its calling context, which is used if
397the exception is not caught. The implicit join does a program abort instead.
398
399This semantics is for safety. One difficult problem for any exception system is
400defining semantics when an exception is raised during an exception search:
401which exception has priority, the original or new exception? No matter which
402exception is selected, it is possible for the selected one to disrupt or
403destroy the context required for the other. {\color{blue} PAB: I do not
404understand the following sentences.} This loss of information can happen with
405join but as the thread destructor is always run when the stack is being unwound
406and one termination/cancellation is already active. Also since they are
407implicit they are easier to forget about.
408
409\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
410or object that satisfies the @is_coroutine@ trait.  A coroutine only knows of
411two other coroutines, its starter and its last resumer.  The last resumer has
412the tightest coupling to the coroutine it activated.  Hence, cancellation of
413the active coroutine is forwarded to the last resumer after the stack is
414unwound, as the last resumer has the most precise knowledge about the current
415execution. When the resumer restarts, it resumes exception
416@CoroutineCancelled@, which is polymorphic over the coroutine type and has a
417pointer to the cancelled coroutine.
418
419The resume function also has an assertion that the @defaultResumptionHandler@
420for the exception. So it will use the default handler like a regular throw.
421\end{description}
Note: See TracBrowser for help on using the repository browser.