Ignore:
Timestamp:
Apr 19, 2021, 12:03:12 PM (8 months ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
72f246d
Parents:
de47a9d
Message:

Updated features to incorperate Peter's feedback.

Location:
doc/theses/andrew_beach_MMath
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/andrew_beach_MMath/features.tex

    rde47a9d rf6106a6  
    33This chapter covers the design and user interface of the \CFA
    44exception-handling mechanism (EHM). % or exception system.
     5
     6We will begin with an overview of EHMs in general. It is not a strict
     7definition of all EHMs nor an exaustive list of all possible features.
     8However it does cover the most common structure and features found in them.
    59
    610% We should cover what is an exception handling mechanism and what is an
     
    913\paragraph{Raise / Handle}
    1014An exception operation has two main parts: raise and handle.
    11 These are the two parts that the user will write themselves and so
    12 might be the only two pieces of the EHM that have any syntax.
    1315These terms are sometimes also known as throw and catch but this work uses
    1416throw/catch as a particular kind of raise/handle.
     17These are the two parts that the user will write themselves and may
     18be the only two pieces of the EHM that have any syntax in the language.
    1519
    1620\subparagraph{Raise}
    17 The raise is the starting point for exception handling and usually how
    18 Some well known examples include the throw statements of \Cpp and Java and
    19 the raise statement from Python.
    20 
    21 For this overview a raise does nothing more kick off the handling of an
    22 exception, which is called raising the exception. This is inexact but close
    23 enough for the broad strokes of the overview.
     21The raise is the starting point for exception handling. It marks the beginning
     22of exception handling by \newterm{raising} an excepion, which passes it to
     23the EHM.
     24
     25Some well known examples include the @throw@ statements of \Cpp and Java and
     26the \codePy{raise} statement from Python. In real systems a raise may preform
     27some other work (such as memory management) but for the purposes of this
     28overview that can be ignored.
    2429
    2530\subparagraph{Handle}
    26 The purpose of most exception operations is to run some sort of handler that
    27 contains user code.
    28 The try statement of \Cpp illistrates the common features
    29 Handlers have three common features: a region of code they apply to, an
    30 exception label that describes what exceptions they handle and code to run
    31 when they handle an exception.
    32 Each handler can handle exceptions raised in that region that match their
    33 exception label. Different EHMs will have different rules to pick a handler
     31The purpose of most exception operations is to run some user code to handle
     32that exception. This code is given, with some other information, in a handler.
     33
     34A handler has three common features: the previously mentioned user code, a
     35region of code they cover and an exception label/condition that matches
     36certain exceptions.
     37Only raises inside the covered region and raising exceptions that match the
     38label can be handled by a given handler.
     39Different EHMs will have different rules to pick a handler
    3440if multipe handlers could be used such as ``best match" or ``first found".
     41
     42The @try@ statements of \Cpp, Java and Python are common examples. All three
     43also show another common feature of handlers, they are grouped by the covered
     44region.
    3545
    3646\paragraph{Propagation}
    3747After an exception is raised comes what is usually the biggest step for the
    38 EHM, finding and setting up the handler. This can be broken up into three
    39 different tasks: searching for a handler, matching against the handler and
    40 installing the handler.
    41 
    42 First the EHM must search for possible handlers that could be used to handle
     48EHM: finding and setting up the handler. The propogation from raise to
     49handler can be broken up into three different tasks: searching for a handler,
     50matching against the handler and installing the handler.
     51
     52\subparagraph{Searching}
     53The EHM begins by searching for handlers that might be used to handle
    4354the exception. Searching is usually independent of the exception that was
    44 thrown and instead depends on the call stack, the current function, its caller
    45 and repeating down the stack.
    46 
    47 Second it much match the exception with each handler to see which one is the
    48 best match and hence which one should be used to handle the exception.
    49 In languages where the best match is the first match these two are often
    50 intertwined, a match check is preformed immediately after the search finds
     55thrown as it looks for handlers that have the raise site in their covered
     56region.
     57This includes handlers in the current function, as well as any in callers
     58on the stack that have the function call in their covered region.
     59
     60\subparagraph{Matching}
     61Each handler found has to be matched with the raised exception. The exception
     62label defines a condition that be use used with exception and decides if
     63there is a match or not.
     64
     65In languages where the first match is used this step is intertwined with
     66searching, a match check is preformed immediately after the search finds
    5167a possible handler.
    5268
    53 Third, after a handler is chosen it must be made ready to run.
    54 What this actually involves can vary widely to fit with the rest of the
     69\subparagraph{Installing}
     70After a handler is chosen it must be made ready to run.
     71The implementation can vary widely to fit with the rest of the
    5572design of the EHM. The installation step might be trivial or it could be
    5673the most expensive step in handling an exception. The latter tends to be the
    5774case when stack unwinding is involved.
    5875
    59 As an alternate third step if no appropriate handler is found then some sort
    60 of recovery has to be preformed. This is only required with unchecked
    61 exceptions as checked exceptions can promise that a handler is found. It also
    62 is also installing a handler but it is a special default that may be
    63 installed differently.
     76If a matching handler is not guarantied to be found the EHM will need a
     77different course of action here in the cases where no handler matches.
     78This is only required with unchecked exceptions as checked exceptions
     79(such as in Java) can make than guaranty.
     80This different action can also be installing a handler but it is usually an
     81implicat and much more general one.
    6482
    6583\subparagraph{Hierarchy}
    66 In \CFA the EHM uses a hierarchial system to organise its exceptions.
    67 This stratagy is borrowed from object-orientated languages where the
     84A common way to organize exceptions is in a hierarchical structure.
     85This is especially true in object-orientated languages where the
    6886exception hierarchy is a natural extension of the object hierarchy.
    6987
     
    88106A handler labelled with any given exception can handle exceptions of that
    89107type or any child type of that exception. The root of the exception hierarchy
    90 (here \texttt{exception}) acts as a catch-all, leaf types catch single types
     108(here \codeC{exception}) acts as a catch-all, leaf types catch single types
    91109and the exceptions in the middle can be used to catch different groups of
    92110related exceptions.
     
    94112This system has some notable advantages, such as multiple levels of grouping,
    95113the ability for libraries to add new exception types and the isolation
    96 between different sub-hierarchies. So the design was adapted for a
    97 non-object-orientated language.
     114between different sub-hierarchies.
     115This design is used in \CFA even though it is not a object-orientated
     116language using different tools to create the hierarchy.
    98117
    99118% Could I cite the rational for the Python IO exception rework?
     
    101120\paragraph{Completion}
    102121After the handler has finished the entire exception operation has to complete
    103 and continue executing somewhere else. This step is usually very simple
    104 both logically and in its implementation as the installation of the handler
    105 usually does the heavy lifting.
    106 
    107 The EHM can return control to many different places.
    108 However, the most common is after the handler definition and the next most
    109 common is after the raise.
     122and continue executing somewhere else. This step is usually simple,
     123both logically and in its implementation, as the installation of the handler
     124is usually set up to do most of the work.
     125
     126The EHM can return control to many different places,
     127the most common are after the handler definition and after the raise.
    110128
    111129\paragraph{Communication}
    112 For effective exception handling, additional information is usually required
    113 as this base model only communicates the exception's identity. Common
    114 additional methods of communication are putting fields on an exception and
    115 allowing a handler to access the lexical scope it is defined in (usually
    116 a function's local variables).
    117 
    118 \paragraph{Other Features}
    119 Any given exception handling mechanism is free at add other features on top
    120 of this. This is an overview of the base that all EHMs use but it is not an
    121 exaustive list of everything an EHM can do.
     130For effective exception handling, additional information is usually passed
     131from the raise to the handler.
     132So far only communication of the exceptions' identity has been covered.
     133A common method is putting fields into the exception instance and giving the
     134handler access to them.
    122135
    123136\section{Virtuals}
    124 Virtual types and casts are not part of the exception system nor are they
    125 required for an exception system. But an object-oriented style hierarchy is a
    126 great way of organizing exceptions so a minimal virtual system has been added
    127 to \CFA.
     137Virtual types and casts are not part of \CFA's EHM nor are they required for
     138any EHM. But \CFA uses a hierarchial system of exceptions and this feature
     139is leveraged to create that.
     140
     141% Maybe talk about why the virtual system is so minimal.
     142% Created for but not a part of the exception system.
    128143
    129144The virtual system supports multiple ``trees" of types. Each tree is
    130145a simple hierarchy with a single root type. Each type in a tree has exactly
    131 one parent - except for the root type which has zero parents - and any
     146one parent -- except for the root type which has zero parents -- and any
    132147number of children.
    133148Any type that belongs to any of these trees is called a virtual type.
     
    139154Every virtual type also has a list of virtual members. Children inherit
    140155their parent's list of virtual members but may add new members to it.
    141 It is important to note that these are virtual members, not virtual methods.
    142 However as function pointers are allowed they can be used to mimic virtual
    143 methods as well.
    144 
    145 The unique id for the virtual type and all the virtual members are combined
     156It is important to note that these are virtual members, not virtual methods
     157of object-orientated programming, and can be of any type.
     158However, since \CFA has function pointers and they are allowed, virtual
     159members can be used to mimic virtual methods.
     160
     161Each virtual type has a unique id.
     162This unique id and all the virtual members are combined
    146163into a virtual table type. Each virtual type has a pointer to a virtual table
    147164as a hidden field.
    148165
    149 Up until this point the virtual system is a lot like ones found in object-
    150 orientated languages but this where they diverge. Objects encapsulate a
     166Up until this point the virtual system is similar to ones found in
     167object-orientated languages but this where \CFA diverges. Objects encapsulate a
    151168single set of behaviours in each type, universally across the entire program,
    152169and indeed all programs that use that type definition. In this sense the
    153170types are ``closed" and cannot be altered.
    154171
    155 However in \CFA types do not encapsulate any behaviour. Traits are local and
     172In \CFA types do not encapsulate any behaviour. Traits are local and
    156173types can begin to statify a trait, stop satifying a trait or satify the same
    157 trait in a different way with each new definition. In this sense they are
    158 ``open" as they can change at any time. This means it is implossible to pick
    159 a single set of functions that repersent the type.
    160 
    161 So we don't try to have a single value. The user can define virtual tables
    162 which are filled in at their declaration and given a name. Anywhere you can
    163 see that name you can use that virtual table; even if it is defined locally
    164 inside a function, although in that case you must respect its lifetime.
    165 
    166 An object of a virtual type is ``bound" to a virtual table instance which
     174trait in a different way at any lexical location in the program.
     175In this sense they are ``open" as they can change at any time. This means it
     176is implossible to pick a single set of functions that repersent the type's
     177implementation across the program.
     178
     179\CFA side-steps this issue by not having a single virtual table for each
     180type. A user can define virtual tables which are filled in at their
     181declaration and given a name. Anywhere that name is visible, even if it was
     182defined locally inside a function (although that means it will not have a
     183static lifetime), it can be used.
     184Specifically, a virtual type is ``bound" to a virtual table which
    167185sets the virtual members for that object. The virtual members can be accessed
    168186through the object.
     
    196214\end{cfa}
    197215The trait is defined over two types, the exception type and the virtual table
    198 type. This should be one-to-one, each exception type has only one virtual
     216type. This should be one-to-one: each exception type has only one virtual
    199217table type and vice versa. The only assertion in the trait is
    200218@get_exception_vtable@, which takes a pointer of the exception type and
    201219returns a reference to the virtual table type instance.
    202220
     221% TODO: This section, and all references to get_exception_vtable, are
     222% out-of-data. Perhaps wait until the update is finished before rewriting it.
    203223The function @get_exception_vtable@ is actually a constant function.
    204224Regardless of the value passed in (including the null pointer) it should
     
    214234% similar system I know of (except Agda's I guess) so I took it out.
    215235
    216 There are two more traits for exceptions @is_termination_exception@ and
    217 @is_resumption_exception@. They are defined as follows:
    218 
     236There are two more traits for exceptions defined as follows:
    219237\begin{cfa}
    220238trait is_termination_exception(
     
    228246};
    229247\end{cfa}
    230 
    231 In other words they make sure that a given type and virtual type is an
    232 exception and defines one of the two default handlers. These default handlers
    233 are used in the main exception handling operations \see{Exception Handling}
    234 and their use will be detailed there.
    235 
    236 However all three of these traits can be tricky to use directly.
    237 There is a bit of repetition required but
     248Both traits ensure a pair of types are an exception type and its virtual table
     249and defines one of the two default handlers. The default handlers are used
     250as fallbacks and are discussed in detail in \VRef{s:ExceptionHandling}.
     251
     252However, all three of these traits can be tricky to use directly.
     253While there is a bit of repetition required,
    238254the largest issue is that the virtual table type is mangled and not in a user
    239 facing way. So there are three macros that can be used to wrap these traits
    240 when you need to refer to the names:
     255facing way. So these three macros are provided to wrap these traits to
     256simplify referring to the names:
    241257@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    242258
    243 All take one or two arguments. The first argument is the name of the
    244 exception type. Its unmangled and mangled form are passed to the trait.
     259All three take one or two arguments. The first argument is the name of the
     260exception type. The macro passes its unmangled and mangled form to the trait.
    245261The second (optional) argument is a parenthesized list of polymorphic
    246 arguments. This argument should only with polymorphic exceptions and the
    247 list will be passed to both types.
    248 In the current set-up the base name and the polymorphic arguments have to
    249 match so these macros can be used without losing flexibility.
     262arguments. This argument is only used with polymorphic exceptions and the
     263list is be passed to both types.
     264In the current set-up, the two types always have the same polymorphic
     265arguments so these macros can be used without losing flexibility.
    250266
    251267For example consider a function that is polymorphic over types that have a
     
    257273
    258274\section{Exception Handling}
    259 \CFA provides two kinds of exception handling, termination and resumption.
    260 These twin operations are the core of the exception handling mechanism and
    261 are the reason for the features of exceptions.
     275\label{s:ExceptionHandling}
     276\CFA provides two kinds of exception handling: termination and resumption.
     277These twin operations are the core of \CFA's exception handling mechanism.
    262278This section will cover the general patterns shared by the two operations and
    263279then go on to cover the details each individual operation.
    264280
    265 Both operations follow the same set of steps to do their operation. They both
    266 start with the user preforming a throw on an exception.
    267 Then there is the search for a handler, if one is found than the exception
    268 is caught and the handler is run. After that control returns to normal
    269 execution.
    270 
     281Both operations follow the same set of steps.
     282Both start with the user preforming a raise on an exception.
     283Then the exception propogates up the stack.
     284If a handler is found the exception is caught and the handler is run.
     285After that control returns to normal execution.
    271286If the search fails a default handler is run and then control
    272 returns to normal execution immediately. That is where the default handlers
    273 @defaultTermiationHandler@ and @defaultResumptionHandler@ are used.
     287returns to normal execution after the raise.
     288
     289This general description covers what the two kinds have in common.
     290Differences include how propogation is preformed, where exception continues
     291after an exception is caught and handled and which default handler is run.
    274292
    275293\subsection{Termination}
    276294\label{s:Termination}
    277 
    278 Termination handling is more familiar kind and used in most programming
     295Termination handling is the familiar kind and used in most programming
    279296languages with exception handling.
    280 It is dynamic, non-local goto. If a throw is successful then the stack will
    281 be unwound and control will (usually) continue in a different function on
    282 the call stack. They are commonly used when an error has occurred and recovery
    283 is impossible in the current function.
     297It is dynamic, non-local goto. If the raised exception is matched and
     298handled the stack is unwound and control will (usually) continue the function
     299on the call stack that defined the handler.
     300Termination is commonly used when an error has occurred and recovery is
     301impossible locally.
    284302
    285303% (usually) Control can continue in the current function but then a different
    286304% control flow construct should be used.
    287305
    288 A termination throw is started with the @throw@ statement:
     306A termination raise is started with the @throw@ statement:
    289307\begin{cfa}
    290308throw EXPRESSION;
    291309\end{cfa}
    292310The expression must return a reference to a termination exception, where the
    293 termination exception is any type that satisfies @is_termination_exception@
    294 at the call site.
    295 Through \CFA's trait system the functions in the traits are passed into the
    296 throw code. A new @defaultTerminationHandler@ can be defined in any scope to
     311termination exception is any type that satisfies the trait
     312@is_termination_exception@ at the call site.
     313Through \CFA's trait system the trait functions are implicity passed into the
     314throw code and the EHM.
     315A new @defaultTerminationHandler@ can be defined in any scope to
    297316change the throw's behavior (see below).
    298317
    299 The throw will copy the provided exception into managed memory. It is the
    300 user's responsibility to ensure the original exception is cleaned up if the
    301 stack is unwound (allocating it on the stack should be sufficient).
    302 
    303 Then the exception system searches the stack using the copied exception.
    304 It starts starts from the throw and proceeds to the base of the stack,
     318The throw will copy the provided exception into managed memory to ensure
     319the exception is not destroyed if the stack is unwound.
     320It is the user's responsibility to ensure the original exception is cleaned
     321up wheither the stack is unwound or not. Allocating it on the stack is
     322usually sufficient.
     323
     324Then propogation starts with the search. \CFA uses a ``first match" rule so
     325matching is preformed with the copied exception as the search continues.
     326It starts from the throwing function and proceeds to the base of the stack,
    305327from callee to caller.
    306328At each stack frame, a check is made for resumption handlers defined by the
     
    309331try {
    310332        GUARDED_BLOCK
    311 } catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
     333} catch (EXCEPTION_TYPE$\(_1\)$ * [NAME$\(_1\)$]) {
    312334        HANDLER_BLOCK$\(_1\)$
    313 } catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
     335} catch (EXCEPTION_TYPE$\(_2\)$ * [NAME$\(_2\)$]) {
    314336        HANDLER_BLOCK$\(_2\)$
    315337}
    316338\end{cfa}
    317 When viewed on its own a try statement will simply execute the statements in
    318 @GUARDED_BLOCK@ and when those are finished the try statement finishes.
     339When viewed on its own, a try statement will simply execute the statements
     340in @GUARDED_BLOCK@ and when those are finished the try statement finishes.
    319341
    320342However, while the guarded statements are being executed, including any
    321 functions they invoke, all the handlers following the try block are now
    322 or any functions invoked from those
    323 statements, throws an exception, and the exception
    324 is not handled by a try statement further up the stack, the termination
    325 handlers are searched for a matching exception type from top to bottom.
    326 
    327 Exception matching checks the representation of the thrown exception-type is
    328 the same or a descendant type of the exception types in the handler clauses. If
    329 it is the same of a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
     343invoked functions, all the handlers in the statement are now on the search
     344path. If a termination exception is thrown and not handled further up the
     345stack they will be matched against the exception.
     346
     347Exception matching checks the handler in each catch clause in the order
     348they appear, top to bottom. If the representation of the thrown exception type
     349is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
     350(if provided) is
    330351bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    331352are executed. If control reaches the end of the handler, the exception is
    332353freed and control continues after the try statement.
    333354
    334 If no handler is found during the search then the default handler is run.
     355If no termination handler is found during the search then the default handler
     356(@defaultTerminationHandler@) is run.
    335357Through \CFA's trait system the best match at the throw sight will be used.
    336358This function is run and is passed the copied exception. After the default
    337359handler is run control continues after the throw statement.
    338360
    339 There is a global @defaultTerminationHandler@ that cancels the current stack
    340 with the copied exception. However it is generic over all exception types so
    341 new default handlers can be defined for different exception types and so
    342 different exception types can have different default handlers.
     361There is a global @defaultTerminationHandler@ that is polymorphic over all
     362exception types. Since it is so general a more specific handler can be
     363defined and will be used for those types, effectively overriding the handler
     364for particular exception type.
     365The global default termination handler performs a cancellation
     366\see{\VRef{s:Cancellation}} on the current stack with the copied exception.
    343367
    344368\subsection{Resumption}
    345369\label{s:Resumption}
    346370
    347 Resumption exception handling is a less common form than termination but is
    348 just as old~\cite{Goodenough75} and is in some sense simpler.
    349 It is a dynamic, non-local function call. If the throw is successful a
    350 closure will be taken from up the stack and executed, after which the throwing
    351 function will continue executing.
     371Resumption exception handling is less common than termination but is
     372just as old~\cite{Goodenough75} and is simpler in many ways.
     373It is a dynamic, non-local function call. If the raised exception is
     374matched a closure will be taken from up the stack and executed,
     375after which the raising function will continue executing.
    352376These are most often used when an error occurred and if the error is repaired
    353377then the function can continue.
     
    357381throwResume EXPRESSION;
    358382\end{cfa}
    359 The semantics of the @throwResume@ statement are like the @throw@, but the
    360 expression has return a reference a type that satisfies the trait
    361 @is_resumption_exception@. The assertions from this trait are available to
     383It works much the same way as the termination throw.
     384The expression must return a reference to a resumption exception,
     385where the resumption exception is any type that satisfies the trait
     386@is_resumption_exception@ at the call site.
     387The assertions from this trait are available to
    362388the exception system while handling the exception.
    363389
    364 At run-time, no copies are made. As the stack is not unwound the exception and
     390At run-time, no exception copy is made.
     391As the stack is not unwound the exception and
    365392any values on the stack will remain in scope while the resumption is handled.
    366393
    367 Then the exception system searches the stack using the provided exception.
    368 It starts starts from the throw and proceeds to the base of the stack,
    369 from callee to caller.
     394The EHM then begins propogation. The search starts from the raise in the
     395resuming function and proceeds to the base of the stack, from callee to caller.
    370396At each stack frame, a check is made for resumption handlers defined by the
    371397@catchResume@ clauses of a @try@ statement.
     
    373399try {
    374400        GUARDED_BLOCK
    375 } catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
     401} catchResume (EXCEPTION_TYPE$\(_1\)$ * [NAME$\(_1\)$]) {
    376402        HANDLER_BLOCK$\(_1\)$
    377 } catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
     403} catchResume (EXCEPTION_TYPE$\(_2\)$ * [NAME$\(_2\)$]) {
    378404        HANDLER_BLOCK$\(_2\)$
    379405}
    380406\end{cfa}
    381 If the handlers are not involved in a search this will simply execute the
    382 @GUARDED_BLOCK@ and then continue to the next statement.
    383 Its purpose is to add handlers onto the stack.
    384 (Note, termination and resumption handlers may be intermixed in a @try@
    385 statement but the kind of throw must be the same as the handler for it to be
    386 considered as a possible match.)
    387 
    388 If a search for a resumption handler reaches a try block it will check each
    389 @catchResume@ clause, top-to-bottom.
    390 At each handler if the thrown exception is or is a child type of
    391 @EXCEPTION_TYPE@$_i$ then the a pointer to the exception is bound to
    392 @NAME@$_i$ and then @HANDLER_BLOCK@$_i$ is executed. After the block is
    393 finished control will return to the @throwResume@ statement.
     407% I wonder if there would be some good central place for this.
     408Note that termination handlers and resumption handlers may be used together
     409in a single try statement, intermixing @catch@ and @catchResume@ freely.
     410Each type of handler will only interact with exceptions from the matching
     411type of raise.
     412When a try statement is executed it simply executes the statements in the
     413@GUARDED_BLOCK@ and then finishes.
     414
     415However, while the guarded statements are being executed, including any
     416invoked functions, all the handlers in the statement are now on the search
     417path. If a resumption exception is reported and not handled further up the
     418stack they will be matched against the exception.
     419
     420Exception matching checks the handler in each catch clause in the order
     421they appear, top to bottom. If the representation of the thrown exception type
     422is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
     423(if provided) is bound to a pointer to the exception and the statements in
     424@HANDLER_BLOCK@$_i$ are executed.
     425If control reaches the end of the handler, execution continues after the
     426the raise statement that raised the handled exception.
    394427
    395428Like termination, if no resumption handler is found, the default handler
     
    397430call sight according to \CFA's overloading rules. The default handler is
    398431passed the exception given to the throw. When the default handler finishes
    399 execution continues after the throw statement.
     432execution continues after the raise statement.
    400433
    401434There is a global @defaultResumptionHandler@ is polymorphic over all
    402435termination exceptions and preforms a termination throw on the exception.
    403 The @defaultTerminationHandler@ for that throw is matched at the original
    404 throw statement (the resumption @throwResume@) and it can be customized by
     436The @defaultTerminationHandler@ for that raise is matched at the original
     437raise statement (the resumption @throwResume@) and it can be customized by
    405438introducing a new or better match as well.
    406439
    407 % \subsubsection?
    408 
     440\subsubsection{Resumption Marking}
    409441A key difference between resumption and termination is that resumption does
    410442not unwind the stack. A side effect that is that when a handler is matched
     
    432464can form with multiple handlers and different exception types.
    433465
    434 To prevent all of these cases we mask sections of the stack, or equivalently
    435 the try statements on the stack, so that the resumption search skips over
    436 them and continues with the next unmasked section of the stack.
    437 
    438 A section of the stack is marked when it is searched to see if it contains
    439 a handler for an exception and unmarked when that exception has been handled
    440 or the search was completed without finding a handler.
     466To prevent all of these cases we mark try statements on the stack.
     467A try statement is marked when a match check is preformed with it and an
     468exception. The statement will be unmarked when the handling of that exception
     469is completed or the search completes without finding a handler.
     470While a try statement is marked its handlers are never matched, effectify
     471skipping over it to the next try statement.
    441472
    442473% This might need a diagram. But it is an important part of the justification
     
    457488\end{verbatim}
    458489
    459 The rules can be remembered as thinking about what would be searched in
    460 termination. So when a throw happens in a handler; a termination handler
    461 skips everything from the original throw to the original catch because that
    462 part of the stack has been unwound, a resumption handler skips the same
    463 section of stack because it has been masked.
    464 A throw in a default handler will preform the same search as the original
    465 throw because; for termination nothing has been unwound, for resumption
    466 the mask will be the same.
    467 
    468 The symmetry with termination is why this pattern was picked. Other patterns,
    469 such as marking just the handlers that caught, also work but lack the
    470 symmetry which means there is more to remember.
     490These rules mirror what happens with termination.
     491When a termination throw happens in a handler the search will not look at
     492any handlers from the original throw to the original catch because that
     493part of the stack has been unwound.
     494A resumption raise in the same situation wants to search the entire stack,
     495but it will not try to match the exception with try statements in the section
     496that would have been unwound as they are marked.
     497
     498The symmetry between resumption termination is why this pattern was picked.
     499Other patterns, such as marking just the handlers that caught, also work but
     500lack the symmetry means there are less rules to remember.
    471501
    472502\section{Conditional Catch}
     
    474504condition to further control which exceptions they handle:
    475505\begin{cfa}
    476 catch (EXCEPTION_TYPE * NAME ; CONDITION)
     506catch (EXCEPTION_TYPE * [NAME] ; CONDITION)
    477507\end{cfa}
    478508First, the same semantics is used to match the exception type. Second, if the
     
    482512matches. Otherwise, the exception search continues as if the exception type
    483513did not match.
     514
     515The condition matching allows finer matching by allowing the match to check
     516more kinds of information than just the exception type.
    484517\begin{cfa}
    485518try {
    486         f1 = open( ... );
    487         f2 = open( ... );
     519        handle1 = open( f1, ... );
     520        handle2 = open( f2, ... );
     521        handle3 = open( f3, ... );
    488522        ...
    489523} catch( IOFailure * f ; fd( f ) == f1 ) {
    490         // only handle IO failure for f1
     524        // Only handle IO failure for f1.
     525} catch( IOFailure * f ; fd( f ) == f3 ) {
     526        // Only handle IO failure for f3.
    491527}
    492 \end{cfa}
    493 Note, catching @IOFailure@, checking for @f1@ in the handler, and re-raising the
    494 exception if not @f1@ is different because the re-raise does not examine any of
    495 remaining handlers in the current try statement.
    496 
    497 \section{Rethrowing}
    498 \colour{red}{From Andrew: I recomend we talk about why the language doesn't
    499 have rethrows/reraises instead.}
    500 
    501 \label{s:Rethrowing}
     528// Can't handle a failure relating to f2 here.
     529\end{cfa}
     530In this example the file that experianced the IO error is used to decide
     531which handler should be run, if any at all.
     532
     533\begin{comment}
     534% I know I actually haven't got rid of them yet, but I'm going to try
     535% to write it as if I had and see if that makes sense:
     536\section{Reraising}
     537\label{s:Reraising}
    502538Within the handler block or functions called from the handler block, it is
    503539possible to reraise the most recently caught exception with @throw@ or
     
    518554is part of an unwound stack frame. To prevent this problem, a new default
    519555handler is generated that does a program-level abort.
     556\end{comment}
     557
     558\subsection{Comparison with Reraising}
     559A more popular way to allow handlers to match in more detail is to reraise
     560the exception after it has been caught if it could not be handled here.
     561On the surface these two features seem interchangable.
     562
     563If we used @throw;@ to start a termination reraise then these two statements
     564would have the same behaviour:
     565\begin{cfa}
     566try {
     567    do_work_may_throw();
     568} catch(exception_t * exc ; can_handle(exc)) {
     569    handle(exc);
     570}
     571\end{cfa}
     572
     573\begin{cfa}
     574try {
     575    do_work_may_throw();
     576} catch(exception_t * exc) {
     577    if (can_handle(exc)) {
     578        handle(exc);
     579    } else {
     580        throw;
     581    }
     582}
     583\end{cfa}
     584If there are further handlers after this handler only the first version will
     585check them. If multiple handlers on a single try block could handle the same
     586exception the translations get more complex but they are equivilantly
     587powerful.
     588
     589Until stack unwinding comes into the picture. In termination handling, a
     590conditional catch happens before the stack is unwound, but a reraise happens
     591afterwards. Normally this might only cause you to loose some debug
     592information you could get from a stack trace (and that can be side stepped
     593entirely by collecting information during the unwind). But for \CFA there is
     594another issue, if the exception isn't handled the default handler should be
     595run at the site of the original raise.
     596
     597There are two problems with this: the site of the original raise doesn't
     598exist anymore and the default handler might not exist anymore. The site will
     599always be removed as part of the unwinding, often with the entirety of the
     600function it was in. The default handler could be a stack allocated nested
     601function removed during the unwind.
     602
     603This means actually trying to pretend the catch didn't happening, continuing
     604the original raise instead of starting a new one, is infeasible.
     605That is the expected behaviour for most languages and we can't replicate
     606that behaviour.
    520607
    521608\section{Finally Clauses}
     609\label{s:FinallyClauses}
    522610Finally clauses are used to preform unconditional clean-up when leaving a
    523 scope. They are placed at the end of a try statement:
     611scope and are placed at the end of a try statement after any handler clauses:
    524612\begin{cfa}
    525613try {
     
    537625
    538626Execution of the finally block should always finish, meaning control runs off
    539 the end of the block. This requirement ensures always continues as if the
    540 finally clause is not present, \ie finally is for cleanup not changing control
    541 flow. Because of this requirement, local control flow out of the finally block
     627the end of the block. This requirement ensures control always continues as if
     628the finally clause is not present, \ie finally is for cleanup not changing
     629control flow.
     630Because of this requirement, local control flow out of the finally block
    542631is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
    543632@return@ that causes control to leave the finally block. Other ways to leave
    544633the finally block, such as a long jump or termination are much harder to check,
    545 and at best requiring additional run-time overhead, and so are mealy
     634and at best requiring additional run-time overhead, and so are only
    546635discouraged.
    547636
    548 Not all languages with exceptions have finally clauses. Notably \Cpp does
     637Not all languages with unwinding have finally clauses. Notably \Cpp does
    549638without it as descructors serve a similar role. Although destructors and
    550639finally clauses can be used in many of the same areas they have their own
    551640use cases like top-level functions and lambda functions with closures.
    552641Destructors take a bit more work to set up but are much easier to reuse while
    553 finally clauses are good for once offs and can include local information.
     642finally clauses are good for one-off uses and
     643can easily include local information.
    554644
    555645\section{Cancellation}
     646\label{s:Cancellation}
    556647Cancellation is a stack-level abort, which can be thought of as as an
    557 uncatchable termination. It unwinds the entirety of the current stack, and if
     648uncatchable termination. It unwinds the entire current stack, and if
    558649possible forwards the cancellation exception to a different stack.
    559650
     
    561652There is no special statement for starting a cancellation; instead the standard
    562653library function @cancel_stack@ is called passing an exception. Unlike a
    563 throw, this exception is not used in matching only to pass information about
     654raise, this exception is not used in matching only to pass information about
    564655the cause of the cancellation.
    565 (This also means matching cannot fail so there is no default handler either.)
    566 
    567 After @cancel_stack@ is called the exception is copied into the exception
    568 handling mechanism's memory. Then the entirety of the current stack is
     656(This also means matching cannot fail so there is no default handler.)
     657
     658After @cancel_stack@ is called the exception is copied into the EHM's memory
     659and the current stack is
    569660unwound. After that it depends one which stack is being cancelled.
    570661\begin{description}
    571662\item[Main Stack:]
    572663The main stack is the one used by the program main at the start of execution,
    573 and is the only stack in a sequential program. Even in a concurrent program
    574 the main stack is only dependent on the environment that started the program.
    575 Hence, when the main stack is cancelled there is nowhere else in the program
    576 to notify. After the stack is unwound, there is a program-level abort.
     664and is the only stack in a sequential program.
     665After the main stack is unwound there is a program-level abort.
     666
     667There are two reasons for this. The first is that it obviously had to do this
     668in a sequential program as there is nothing else to notify and the simplicity
     669of keeping the same behaviour in sequential and concurrent programs is good.
     670Also, even in concurrent programs there is no stack that an innate connection
     671to, so it would have be explicitly managed.
    577672
    578673\item[Thread Stack:]
    579 A thread stack is created for a @thread@ object or object that satisfies the
    580 @is_thread@ trait. A thread only has two points of communication that must
    581 happen: start and join. As the thread must be running to perform a
    582 cancellation, it must occur after start and before join, so join is used
    583 for communication here.
    584 After the stack is unwound, the thread halts and waits for
    585 another thread to join with it. The joining thread checks for a cancellation,
    586 and if present, resumes exception @ThreadCancelled@.
    587 
    588 There is a subtle difference between the explicit join (@join@ function) and
    589 implicit join (from a destructor call). The explicit join takes the default
    590 handler (@defaultResumptionHandler@) from its calling context, which is used if
    591 the exception is not caught. The implicit join does a program abort instead.
    592 
    593 This semantics is for safety. If an unwind is triggered while another unwind
    594 is underway only one of them can proceed as they both want to ``consume'' the
    595 stack. Letting both try to proceed leads to very undefined behaviour.
    596 Both termination and cancellation involve unwinding and, since the default
    597 @defaultResumptionHandler@ preforms a termination that could more easily
    598 happen in an implicate join inside a destructor. So there is an error message
    599 and an abort instead.
    600 \todo{Perhaps have a more general disucssion of unwind collisions before
    601 this point.}
    602 
    603 The recommended way to avoid the abort is to handle the initial resumption
    604 from the implicate join. If required you may put an explicate join inside a
    605 finally clause to disable the check and use the local
    606 @defaultResumptionHandler@ instead.
    607 
    608 \item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
    609 or object that satisfies the @is_coroutine@ trait. A coroutine only knows of
    610 two other coroutines, its starter and its last resumer. Of the two the last
    611 resumer has the tightest coupling to the coroutine it activated and the most
    612 up-to-date information.
    613 
    614 Hence, cancellation of the active coroutine is forwarded to the last resumer
    615 after the stack is unwound. When the resumer restarts, it resumes exception
    616 @CoroutineCancelled@, which is polymorphic over the coroutine type and has a
    617 pointer to the cancelled coroutine.
    618 
    619 The resume function also has an assertion that the @defaultResumptionHandler@
    620 for the exception. So it will use the default handler like a regular throw.
     674A thread stack is created for a \CFA @thread@ object or object that satisfies
     675the @is_thread@ trait.
     676After a thread stack is unwound there exception is stored until another
     677thread attempts to join with it. Then the exception @ThreadCancelled@,
     678which stores a reference to the thread and to the exception passed to the
     679cancellation, is reported from the join.
     680There is one difference between an explicit join (with the @join@ function)
     681and an implicit join (from a destructor call). The explicit join takes the
     682default handler (@defaultResumptionHandler@) from its calling context while
     683the implicit join provides its own which does a program abort if the
     684@ThreadCancelled@ exception cannot be handled.
     685
     686Communication is done at join because a thread only has to have to points of
     687communication with other threads: start and join.
     688Since a thread must be running to perform a cancellation (and cannot be
     689cancelled from another stack), the cancellation must be after start and
     690before the join. So join is the one that we will use.
     691
     692% TODO: Find somewhere to discuss unwind collisions.
     693The difference between the explicit and implicit join is for safety and
     694debugging. It helps prevent unwinding collisions by avoiding throwing from
     695a destructor and prevents cascading the error across multiple threads if
     696the user is not equipped to deal with it.
     697Also you can always add an explicit join if that is the desired behaviour.
     698
     699\item[Coroutine Stack:]
     700A coroutine stack is created for a @coroutine@ object or object that
     701satisfies the @is_coroutine@ trait.
     702After a coroutine stack is unwound control returns to the resume function
     703that most recently resumed it. The resume statement reports a
     704@CoroutineCancelled@ exception, which contains a references to the cancelled
     705coroutine and the exception used to cancel it.
     706The resume function also takes the @defaultResumptionHandler@ from the
     707caller's context and passes it to the internal report.
     708
     709A coroutine knows of two other coroutines, its starter and its last resumer.
     710The starter has a much more distant connection while the last resumer just
     711(in terms of coroutine state) called resume on this coroutine, so the message
     712is passed to the latter.
    621713\end{description}
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rde47a9d rf6106a6  
    217217\pdfstringdefDisableCommands{\def\Cpp{C++}}
    218218
     219% Wrappers for inline code snippits.
     220\newrobustcmd*\codeCFA[1]{\lstinline[language=CFA]{#1}}
     221\newrobustcmd*\codeC[1]{\lstinline[language=C]{#1}}
     222\newrobustcmd*\codeCpp[1]{\lstinline[language=C++]{#1}}
     223\newrobustcmd*\codePy[1]{\lstinline[language=Python]{#1}}
     224
    219225% Colour text, formatted in LaTeX style instead of TeX style.
    220226\newcommand*\colour[2]{{\color{#1}#2}}
Note: See TracChangeset for help on using the changeset viewer.