Changeset de47a9d


Ignore:
Timestamp:
Apr 14, 2021, 10:06:22 AM (3 years ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
f6106a6
Parents:
ea1c97b
Message:

Reverted Peter's changes after making local copies.

Location:
doc/theses/andrew_beach_MMath
Files:
2 deleted
3 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/andrew_beach_MMath/Makefile

    rea1c97b rde47a9d  
    11### Makefile for Andrew Beach's Masters Thesis
    22
    3 DOC = uw-ethesis.pdf
    4 BASE = ${DOC:%.pdf=%} # remove suffix
    5 # directory for latex clutter files
    6 BUILD = build
    7 TEXSRC = $(wildcard *.tex)
    8 FIGSRC = $(wildcard *.fig)
    9 BIBSRC = $(wildcard *.bib)
    10 STYSRC = $(wildcard *.sty)
    11 CLSSRC = $(wildcard *.cls)
    12 TEXLIB = .:../../LaTeXmacros:${BUILD}: # common latex macros
    13 BIBLIB = .:../../bibliography # common citation repository
     3DOC=uw-ethesis.pdf
     4BUILD=out
     5TEXSRC=$(wildcard *.tex)
     6BIBSRC=$(wildcard *.bib)
     7STYSRC=$(wildcard *.sty)
     8CLSSRC=$(wildcard *.cls)
     9TEXLIB= .:../../LaTeXmacros:${BUILD}:
     10BIBLIB= .:../../bibliography
    1411
    15 MAKEFLAGS = --no-print-directory # --silent
    16 VPATH = ${BUILD}
     12# Since tex programs like to add their own file extensions:
     13BASE= ${DOC:%.pdf=%}
    1714
    1815### Special Rules:
    1916
    2017.PHONY: all clean deepclean
    21 .PRECIOUS: %.dvi %.ps # do not delete intermediate files
    2218
    2319### Commands:
    24 LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
    25 BIBTEX = BIBINPUTS=${BIBLIB} bibtex
    26 GLOSSARY = INDEXSTYLE=${BUILD} makeglossaries-lite
     20LATEX=TEXINPUTS=${TEXLIB} pdflatex -halt-on-error -output-directory=${BUILD}
     21BIBTEX=BIBINPUTS=${BIBLIB} bibtex
     22GLOSSARY=INDEXSTYLE=${BUILD} makeglossaries-lite
    2723
    28 ### Rules and Recipes:
     24### Rules and Recipies:
    2925
    3026all: ${DOC}
    3127
    32 ${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:.fig=.tex} ${BIBSRC} ${STYSRC} ${CLSSRC} Makefile | ${BUILD}
     28${BUILD}/${DOC}: ${TEXSRC} ${BIBSRC} ${STYSRC} ${CLSSRC} Makefile | ${BUILD}
    3329        ${LATEX} ${BASE}
    3430        ${BIBTEX} ${BUILD}/${BASE}
     
    3733        ${LATEX} ${BASE}
    3834
     35${DOC}: ${BUILD}/${DOC}
     36        cp $< $@
     37
    3938${BUILD}:
    4039        mkdir $@
    4140
    42 %.pdf : ${BUILD}/%.ps | ${BUILD}
    43         ps2pdf $<
    44 
    45 %.ps : %.dvi | ${BUILD}
    46         dvips $< -o $@
    47 
    48 %.tex : %.fig | ${BUILD}
    49         fig2dev -L eepic $< > ${BUILD}/$@
    50 
    51 %.ps : %.fig | ${BUILD}
    52         fig2dev -L ps $< > ${BUILD}/$@
    53 
    54 %.pstex : %.fig | ${BUILD}
    55         fig2dev -L pstex $< > ${BUILD}/$@
    56         fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t
    57 
    5841clean:
    59         @rm -frv ${BUILD} *.fig.bak
     42        -@rm -rv ${BUILD}
    6043
    6144deepclean: clean
    62         -@rm -fv ${DOC}
     45        -@rm -v ${DOC}
  • doc/theses/andrew_beach_MMath/features.tex

    rea1c97b rde47a9d  
    33This chapter covers the design and user interface of the \CFA
    44exception-handling mechanism (EHM). % or exception system.
    5 While an EHM is free to add many features,
    6 the following overview covers the basic features that all EHMs use, but it is not an
    7 exhaustive list of everything an EHM can do.
    85
    96% We should cover what is an exception handling mechanism and what is an
     
    129\paragraph{Raise / Handle}
    1310An exception operation has two main parts: raise and handle.
     11These are the two parts that the user will write themselves and so
     12might be the only two pieces of the EHM that have any syntax.
    1413These terms are sometimes also known as throw and catch but this work uses
    1514throw/catch as a particular kind of raise/handle.
    16 These are the two parts a programmer writes and so
    17 are the only two pieces of the EHM that have language syntax.
    1815
    1916\subparagraph{Raise}
    20 The raise is the starting point for exception handling and usually how \PAB{This sentence is cut off.}
    21 Some well known examples include the @throw@ statement of \Cpp and Java and
    22 the \lstinline[language=Python]{raise} statement from Python.
    23 
    24 For this overview, a raise starts the handling of an
    25 exception, which is called \newterm{raising} an exception. This simple description is sufficient
    26 for the overview.
     17The raise is the starting point for exception handling and usually how
     18Some well known examples include the throw statements of \Cpp and Java and
     19the raise statement from Python.
     20
     21For this overview a raise does nothing more kick off the handling of an
     22exception, which is called raising the exception. This is inexact but close
     23enough for the broad strokes of the overview.
    2724
    2825\subparagraph{Handle}
    29 The purpose of raising an exception is to run user code to address (handle) the
    30 issue found at the raise point.
    31 The @try@ statement of \Cpp illustrates a common approach for specifying multiple handlers.
    32 A handler has three common features: the scope in which it applies, an
    33 exception label that describes what exceptions it can handle, and code to run
    34 that deals with the raised issue.
    35 Each handler can handle exceptions raised in the region matching its
    36 exception label. For multiple matches, different EHMs have different rules for matching an exception to a handler label,
    37 such as ``best match" or ``first found".
     26The purpose of most exception operations is to run some sort of handler that
     27contains user code.
     28The try statement of \Cpp illistrates the common features
     29Handlers have three common features: a region of code they apply to, an
     30exception label that describes what exceptions they handle and code to run
     31when they handle an exception.
     32Each handler can handle exceptions raised in that region that match their
     33exception label. Different EHMs will have different rules to pick a handler
     34if multipe handlers could be used such as ``best match" or ``first found".
    3835
    3936\paragraph{Propagation}
    40 After an exception is raised, comes the most complex step for the
    41 EHM: finding and setting up the handler. This propagation of exception from raise to handler can be broken up into three
    42 different tasks: searching, matching, and
    43 installing the handler so it can execute.
    44 
    45 \subparagraph{Searching}
    46 The EHM searches for possible handlers that can be used to handle
    47 the exception. Searching is usually independent of the exception that is
    48 thrown and instead depends on the call stack: current function, its caller
     37After an exception is raised comes what is usually the biggest step for the
     38EHM, finding and setting up the handler. This can be broken up into three
     39different tasks: searching for a handler, matching against the handler and
     40installing the handler.
     41
     42First the EHM must search for possible handlers that could be used to handle
     43the exception. Searching is usually independent of the exception that was
     44thrown and instead depends on the call stack, the current function, its caller
    4945and repeating down the stack.
    5046
    51 \subparagraph{Matching}
    52 For each handler found, it compares the raised exception with the handler label to see which one is the
    53 best match, and hence, which one should be used to handle the exception.
    54 In languages where the best match is the first match, these two steps are often
    55 intertwined, \ie a match check is performed immediately after the search finds
     47Second it much match the exception with each handler to see which one is the
     48best match and hence which one should be used to handle the exception.
     49In languages where the best match is the first match these two are often
     50intertwined, a match check is preformed immediately after the search finds
    5651a possible handler.
    5752
    58 \subparagraph{Installing}
    59 After a handler is chosen, it must be made ready to run.
    60 This step varies widely to fit with the rest of the
    61 design of the EHM. The installation step might be trivial or it can be
     53Third, after a handler is chosen it must be made ready to run.
     54What this actually involves can vary widely to fit with the rest of the
     55design of the EHM. The installation step might be trivial or it could be
    6256the most expensive step in handling an exception. The latter tends to be the
    6357case when stack unwinding is involved.
    64 An alternate action occurs if no appropriate handler is found, then some implicit action
    65 is performed. This step is only required with unchecked
    66 exceptions as checked exceptions (Java) promise a handler is always found. The implicit action
    67 also installs a handler but it is a default handle that may be
     58
     59As an alternate third step if no appropriate handler is found then some sort
     60of recovery has to be preformed. This is only required with unchecked
     61exceptions as checked exceptions can promise that a handler is found. It also
     62is also installing a handler but it is a special default that may be
    6863installed differently.
    6964
    7065\subparagraph{Hierarchy}
    71 Some EHM (\CFA, Java) organize exceptions in a hierarchical structure.
    72 This strategy is borrowed from object-orientated languages where the
     66In \CFA the EHM uses a hierarchial system to organise its exceptions.
     67This stratagy is borrowed from object-orientated languages where the
    7368exception hierarchy is a natural extension of the object hierarchy.
    7469
    7570Consider the following hierarchy of exceptions:
    7671\begin{center}
    77 \input{exceptionHierarchy}
     72\setlength{\unitlength}{4000sp}%
     73\begin{picture}(1605,612)(2011,-1951)
     74\put(2100,-1411){\vector(1, 0){225}}
     75\put(3450,-1411){\vector(1, 0){225}}
     76\put(3550,-1411){\line(0,-1){225}}
     77\put(3550,-1636){\vector(1, 0){150}}
     78\put(3550,-1636){\line(0,-1){225}}
     79\put(3550,-1861){\vector(1, 0){150}}
     80\put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}}
     81\put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}}
     82\put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}}
     83\put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}}
     84\put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}}
     85\end{picture}%
    7886\end{center}
     87
    7988A handler labelled with any given exception can handle exceptions of that
    8089type or any child type of that exception. The root of the exception hierarchy
    81 (here \lstinline[language=C++]{exception}) acts as a catch-all, leaf types catch single types
     90(here \texttt{exception}) acts as a catch-all, leaf types catch single types
    8291and the exceptions in the middle can be used to catch different groups of
    8392related exceptions.
    8493
    8594This system has some notable advantages, such as multiple levels of grouping,
    86 the ability for libraries to add new exception types, and the isolation
    87 between different sub-hierarchies. This capability had to be adapted for \CFA, which is a
     95the ability for libraries to add new exception types and the isolation
     96between different sub-hierarchies. So the design was adapted for a
    8897non-object-orientated language.
    8998
     
    91100
    92101\paragraph{Completion}
    93 After the handler has returned, the entire exception operation has to complete
    94 and continue executing somewhere. This step is usually simple,
    95 both logically and in its implementation, as the installation of the handler
    96 usually does the preparation.
    97 The EHM can return control to different places,
    98 where the most common are after the handler definition or after the raise.
     102After the handler has finished the entire exception operation has to complete
     103and continue executing somewhere else. This step is usually very simple
     104both logically and in its implementation as the installation of the handler
     105usually does the heavy lifting.
     106
     107The EHM can return control to many different places.
     108However, the most common is after the handler definition and the next most
     109common is after the raise.
    99110
    100111\paragraph{Communication}
    101 For effective exception handling, additional information is usually passed from the raise,
    102 where this basic model only communicates the exception's identity. A common
    103 methods for communication is putting fields into an exception and
    104 allowing a handler to access these fields via an exception instance in the handler's scope.
     112For effective exception handling, additional information is usually required
     113as this base model only communicates the exception's identity. Common
     114additional methods of communication are putting fields on an exception and
     115allowing a handler to access the lexical scope it is defined in (usually
     116a function's local variables).
     117
     118\paragraph{Other Features}
     119Any given exception handling mechanism is free at add other features on top
     120of this. This is an overview of the base that all EHMs use but it is not an
     121exaustive list of everything an EHM can do.
    105122
    106123\section{Virtuals}
    107 Virtual types and casts are not part of an EHM nor are they
    108 required for an EHM. But as pointed out, an object-oriented-style hierarchy is an
    109 excellent way of organizing exceptions. Hence, a minimal virtual system has been added
    110 to \CFA to support hierarchical exceptions.
     124Virtual types and casts are not part of the exception system nor are they
     125required for an exception system. But an object-oriented style hierarchy is a
     126great way of organizing exceptions so a minimal virtual system has been added
     127to \CFA.
    111128
    112129The virtual system supports multiple ``trees" of types. Each tree is
    113130a simple hierarchy with a single root type. Each type in a tree has exactly
    114 one parent -- except for the root type with zero parents -- and any
     131one parent - except for the root type which has zero parents - and any
    115132number of children.
    116133Any type that belongs to any of these trees is called a virtual type.
     
    118135% A type's ancestors are its parent and its parent's ancestors.
    119136% The root type has no ancestors.
    120 % A type's descendents are its children and its children's descendents.
    121 
    122 Every virtual type has a list of virtual members. Children inherit
    123 their parent's virtual members but may add new members to it.
    124 It is important to note that these are virtual members, not virtual methods of an object type.
    125 However, as \CFA has function pointers, they can be used to mimic virtual
    126 methods.
    127 
    128 Each virtual type has a unique id.
    129 The unique id for the virtual type and all its virtual members are combined
    130 into a virtual-table type. Each virtual type has a pointer to a virtual table
     137% A type's decendents are its children and its children's decendents.
     138
     139Every virtual type also has a list of virtual members. Children inherit
     140their parent's list of virtual members but may add new members to it.
     141It is important to note that these are virtual members, not virtual methods.
     142However as function pointers are allowed they can be used to mimic virtual
     143methods as well.
     144
     145The unique id for the virtual type and all the virtual members are combined
     146into a virtual table type. Each virtual type has a pointer to a virtual table
    131147as a hidden field.
    132148
    133 Up to this point, a virtual system is similar to ones found in object-oriented
    134 languages but this is where \CFA diverges. Objects encapsulate a
     149Up until this point the virtual system is a lot like ones found in object-
     150orientated languages but this where they diverge. Objects encapsulate a
    135151single set of behaviours in each type, universally across the entire program,
    136 and indeed all programs that use that type definition. In this sense, the
     152and indeed all programs that use that type definition. In this sense the
    137153types are ``closed" and cannot be altered.
    138 However, \CFA types do not encapsulate any behaviour. Instead, traits are used and
    139 types can satisfy a trait, stop satisfying a trait, or satisfy the same
    140 trait in a different way depending on the lexical context. In this sense, the types are
    141 ``open" as their behaviour can change in different scopes. This capability means it is impossible to pick
    142 a single set of functions that represent the type's virtual members.
    143 
    144 Hence, \CFA does not have a single virtual table for a type. A user can define different virtual tables,
    145 which are filled in at their declaration and given a name.
    146 That name is used as the virtual table, even if it is defined locally
    147 inside a function, although lifetime issues must be considered.
    148 Specifically, an object of a virtual type is ``bound" to a virtual table instance, which
     154
     155However in \CFA types do not encapsulate any behaviour. Traits are local and
     156types can begin to statify a trait, stop satifying a trait or satify the same
     157trait 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
     159a single set of functions that repersent the type.
     160
     161So we don't try to have a single value. The user can define virtual tables
     162which are filled in at their declaration and given a name. Anywhere you can
     163see that name you can use that virtual table; even if it is defined locally
     164inside a function, although in that case you must respect its lifetime.
     165
     166An object of a virtual type is ``bound" to a virtual table instance which
    149167sets the virtual members for that object. The virtual members can be accessed
    150168through the object.
     
    160178\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
    161179a pointer to a virtual type.
    162 The cast dynamically checks if the @EXPRESSION@ type is the same or a subtype
     180The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type
    163181of @TYPE@, and if true, returns a pointer to the
    164182@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
     
    178196\end{cfa}
    179197The trait is defined over two types, the exception type and the virtual table
    180 type. These type should have a one-to-one relationship: each exception type has only one virtual
     198type. This should be one-to-one, each exception type has only one virtual
    181199table type and vice versa. The only assertion in the trait is
    182200@get_exception_vtable@, which takes a pointer of the exception type and
    183 returns a reference to the virtual-table type-instance.
     201returns a reference to the virtual table type instance.
    184202
    185203The function @get_exception_vtable@ is actually a constant function.
    186 Regardless of the value passed in (including the null pointer) it
    187 returns a reference to the virtual-table instance for that type.
    188 The reason it is a function instead of a constant is to make type
    189 annotations easier to write using the exception type rather than the
    190 virtual-table type, which usually has a mangled name because it is an internal component of the EHM.
     204Regardless of the value passed in (including the null pointer) it should
     205return a reference to the virtual table instance for that type.
     206The reason it is a function instead of a constant is that it make type
     207annotations easier to write as you can use the exception type instead of the
     208virtual table type; which usually has a mangled name.
    191209% Also \CFA's trait system handles functions better than constants and doing
    192210% it this way reduce the amount of boiler plate we need.
     
    194212% I did have a note about how it is the programmer's responsibility to make
    195213% sure the function is implemented correctly. But this is true of every
    196 % similar system I know of (except Ada's I guess) so I took it out.
    197 
    198 There are two more exception traits defined as follows:
     214% similar system I know of (except Agda's I guess) so I took it out.
     215
     216There are two more traits for exceptions @is_termination_exception@ and
     217@is_resumption_exception@. They are defined as follows:
     218
    199219\begin{cfa}
    200220trait is_termination_exception(
     
    208228};
    209229\end{cfa}
    210 These traits ensure a given type and virtual type are an
    211 exception type and defines one of the two default handlers. The default handlers
    212 are used in the main exception-handling operations and discussed in detail in \VRef{s:ExceptionHandling}.
    213 
    214 However, all three of these traits are tricky to use directly.
    215 While there is a bit of repetition required,
    216 the largest issue is that the virtual-table type is mangled and not in a user
    217 facing way. So three macros are provided to wrap these traits
    218 to simplify referring to the names:
     230
     231In other words they make sure that a given type and virtual type is an
     232exception and defines one of the two default handlers. These default handlers
     233are used in the main exception handling operations \see{Exception Handling}
     234and their use will be detailed there.
     235
     236However all three of these traits can be tricky to use directly.
     237There is a bit of repetition required but
     238the largest issue is that the virtual table type is mangled and not in a user
     239facing way. So there are three macros that can be used to wrap these traits
     240when you need to refer to the names:
    219241@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    220242
    221 These macros take one or two arguments. The first argument is the name of the
    222 exception type. The macro passes the unmangled and mangled form to the trait.
     243All take one or two arguments. The first argument is the name of the
     244exception type. Its unmangled and mangled form are passed to the trait.
    223245The second (optional) argument is a parenthesized list of polymorphic
    224 arguments. This argument is only used with polymorphic exceptions and the
    225 list is passed to both types.
    226 In the current set-up, the base name and the polymorphic arguments have to
     246arguments. This argument should only with polymorphic exceptions and the
     247list will be passed to both types.
     248In the current set-up the base name and the polymorphic arguments have to
    227249match so these macros can be used without losing flexibility.
    228250
     
    230252defined arithmetic exception:
    231253\begin{cfa}
    232 forall(Num | @IS_EXCEPTION(Arithmetic, Num)@)
     254forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
    233255void some_math_function(Num & left, Num & right);
    234256\end{cfa}
    235 where the function may raise exception @Arithmetic@ or any of its decedents.
    236257
    237258\section{Exception Handling}
    238 \label{s:ExceptionHandling}
    239 \CFA provides two kinds of exception handling: termination and resumption.
    240 These twin mechanisms are the core of the \CFA EHM and
    241 multiple features are provided to support them.
    242 This section covers the general patterns shared by the two kinds of exceptions and
    243 then covers the individual detail operations.
    244 
    245 Both mechanisms follow the same set of steps to do their operations. Both
    246 start with the user performing an exception raise.
    247 Then there is the handler search. If one is found, than the exception
    248 is caught and the handler is run. When the handler returns, control returns to an
    249 location appropriate for each kind of exception.
    250 
    251 \begin{sloppypar}
    252 If the search fails, an appropriate default handler, @defaultTermiationHandler@
    253 or @defaultResumptionHandler@, is run and  control returns to the
    254 appropriate location.
    255 \end{sloppypar}
     259\CFA provides two kinds of exception handling, termination and resumption.
     260These twin operations are the core of the exception handling mechanism and
     261are the reason for the features of exceptions.
     262This section will cover the general patterns shared by the two operations and
     263then go on to cover the details each individual operation.
     264
     265Both operations follow the same set of steps to do their operation. They both
     266start with the user preforming a throw on an exception.
     267Then there is the search for a handler, if one is found than the exception
     268is caught and the handler is run. After that control returns to normal
     269execution.
     270
     271If the search fails a default handler is run and then control
     272returns to normal execution immediately. That is where the default handlers
     273@defaultTermiationHandler@ and @defaultResumptionHandler@ are used.
    256274
    257275\subsection{Termination}
    258276\label{s:Termination}
    259 Termination handling is familiar and used in most programming
     277
     278Termination handling is more familiar kind and used in most programming
    260279languages with exception handling.
    261 It is a dynamic, non-local goto. The raise starts searching, and if matched and handled, the stack is
    262 unwound and control (usually) continues in the function on
    263 the call stack containing the handler. Terminate is commonly used for an error where recovery
    264 is impossible in the function performing the raise.
     280It is dynamic, non-local goto. If a throw is successful then the stack will
     281be unwound and control will (usually) continue in a different function on
     282the call stack. They are commonly used when an error has occurred and recovery
     283is impossible in the current function.
    265284
    266285% (usually) Control can continue in the current function but then a different
    267286% control flow construct should be used.
    268287
    269 A termination raise is started with the @throw@ statement:
     288A termination throw is started with the @throw@ statement:
    270289\begin{cfa}
    271290throw EXPRESSION;
    272291\end{cfa}
    273292The expression must return a reference to a termination exception, where the
    274 termination exception is any type that satisfies trait
    275 @is_termination_exception@ at the call site.  Through \CFA's trait system, the
    276 trait functions are implicitly passed into the hidden throw code and available
    277 to the exception system while handling the exception. A new
    278 @defaultTerminationHandler@ can be defined in any scope to change the throw's
    279 unhandled behaviour (see below).
    280 
    281 The throw must copy the provided exception into managed memory because the stack is unwounded.
    282 The lifetime of the exception copy is managed by the exception runtime.
    283 It is the user's responsibility to ensure the original exception is cleaned up, where allocating it on the unwound stack is sufficient.
    284 
    285 The exception search walks the stack matching with the copied exception.
    286 It starts from the throwing function and proceeds to the base of the stack,
     293termination exception is any type that satisfies @is_termination_exception@
     294at the call site.
     295Through \CFA's trait system the functions in the traits are passed into the
     296throw code. A new @defaultTerminationHandler@ can be defined in any scope to
     297change the throw's behavior (see below).
     298
     299The throw will copy the provided exception into managed memory. It is the
     300user's responsibility to ensure the original exception is cleaned up if the
     301stack is unwound (allocating it on the stack should be sufficient).
     302
     303Then the exception system searches the stack using the copied exception.
     304It starts starts from the throw and proceeds to the base of the stack,
    287305from callee to caller.
    288 At each stack frame, a check is made for termination handlers defined by the
     306At each stack frame, a check is made for resumption handlers defined by the
    289307@catch@ clauses of a @try@ statement.
    290308\begin{cfa}
    291309try {
    292310        GUARDED_BLOCK
    293 } catch (EXCEPTION_TYPE$\(_1\)$ [* NAME$\(_1\)$]) {
     311} catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
    294312        HANDLER_BLOCK$\(_1\)$
    295 } catch (EXCEPTION_TYPE$\(_2\)$ [* NAME$\(_2\)$]) {
     313} catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
    296314        HANDLER_BLOCK$\(_2\)$
    297315}
    298316\end{cfa}
    299 When viewed on its own, a @try@ statement with @catch@ clauses simply executes the statements in
    300 the @GUARDED_BLOCK@, and when those are finished, the try statement finishes.
    301 
    302 However, while the guarded statements are being executed, including any invoked
    303 functions, a termination exception may be thrown. If that exception is not handled by a try
    304 statement further up the stack, the handlers following the try block are now
    305 searched for a matching termination exception-type from top to bottom.
    306 
    307 Exception matching checks each @catch@ clasue from top to bottom, if the representation of the thrown exception-type is
    308 the same or a descendant type of the exception types in the @catch@ clauses. If
    309 it is the same or a descendant of @EXCEPTION_TYPE@$_i$, then the optional @NAME@$_i$ is
     317When 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.
     319
     320However, while the guarded statements are being executed, including any
     321functions they invoke, all the handlers following the try block are now
     322or any functions invoked from those
     323statements, throws an exception, and the exception
     324is not handled by a try statement further up the stack, the termination
     325handlers are searched for a matching exception type from top to bottom.
     326
     327Exception matching checks the representation of the thrown exception-type is
     328the same or a descendant type of the exception types in the handler clauses. If
     329it is the same of a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
    310330bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    311331are executed. If control reaches the end of the handler, the exception is
    312 freed and control continues after the @try@ statement.
    313 
    314 If no termination handler is found during the search, the default termination
    315 handler visible at the raise is called.  Through \CFA's trait-system the best
    316 default-handler match at the throw sight is used.  This function is
    317 passed the copied exception given to the raise. After the default handler is
    318 run, control continues after the @throw@ statement.
    319 
    320 There is a global @defaultTerminationHandler@ function that that is polymorphic
    321 over all exception types allowing new default handlers to be defined for
    322 different exception types and so different exception types can have different
    323 default handlers.  The global default termination-handler performs a
    324 cancellation \see{\VRef{s:Cancellation}} on the current stack with the copied
    325 exception.
     332freed and control continues after the try statement.
     333
     334If no handler is found during the search then the default handler is run.
     335Through \CFA's trait system the best match at the throw sight will be used.
     336This function is run and is passed the copied exception. After the default
     337handler is run control continues after the throw statement.
     338
     339There is a global @defaultTerminationHandler@ that cancels the current stack
     340with the copied exception. However it is generic over all exception types so
     341new default handlers can be defined for different exception types and so
     342different exception types can have different default handlers.
    326343
    327344\subsection{Resumption}
    328345\label{s:Resumption}
    329 Resumption exception-handling is a less common counterpart to termination but is
    330 just as old~\cite{Goodenough75} and is simpler to understand.
    331 It is a dynamic, non-local function call (like Lisp). If the throw is successful, a
    332 closure is taken from up the stack and executed, after which the throwing
    333 function continues executing.
    334 Resumption is used when an error occurred, and if the error is repaired,
     346
     347Resumption exception handling is a less common form than termination but is
     348just as old~\cite{Goodenough75} and is in some sense simpler.
     349It is a dynamic, non-local function call. If the throw is successful a
     350closure will be taken from up the stack and executed, after which the throwing
     351function will continue executing.
     352These are most often used when an error occurred and if the error is repaired
    335353then the function can continue.
    336354
    337 An alternative approach is explicitly passing fixup functions with local
    338 closures up the stack to be called when an error occurs. However, fixup
    339 functions significantly expand the parameters list of functions, even when the
    340 fixup function is not used by a function but must be passed to other called
    341 functions.
    342 
    343355A resumption raise is started with the @throwResume@ statement:
    344356\begin{cfa}
    345357throwResume EXPRESSION;
    346358\end{cfa}
    347 Like termination, the expression must return a reference to a resumption
    348 exception, where the resumption exception is any type that satisfies the trait
    349 @is_termination_exception@ at the call site.
    350 The assertions for this trait are available to
     359The semantics of the @throwResume@ statement are like the @throw@, but the
     360expression has return a reference a type that satisfies the trait
     361@is_resumption_exception@. The assertions from this trait are available to
    351362the exception system while handling the exception.
    352363
    353 At runtime, no exception copy is made, as the stack is not unwound. Hence, the exception and
    354 any values on the stack remain in scope while the resumption is handled.
    355 
    356 The exception searches walks the stack matching with the provided exception.
    357 It starts from the resuming function and proceeds to the base of the stack,
     364At run-time, no copies are made. As the stack is not unwound the exception and
     365any values on the stack will remain in scope while the resumption is handled.
     366
     367Then the exception system searches the stack using the provided exception.
     368It starts starts from the throw and proceeds to the base of the stack,
    358369from callee to caller.
    359370At each stack frame, a check is made for resumption handlers defined by the
     
    362373try {
    363374        GUARDED_BLOCK
    364 } catchResume (EXCEPTION_TYPE$\(_1\)$ [* NAME$\(_1\)$]) {
     375} catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
    365376        HANDLER_BLOCK$\(_1\)$
    366 } catchResume (EXCEPTION_TYPE$\(_2\)$ [* NAME$\(_2\)$]) {
     377} catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
    367378        HANDLER_BLOCK$\(_2\)$
    368379}
    369380\end{cfa}
    370 Termination and resumption handlers may be intermixed in a @try@
    371 statement but the kind of throw must match with kind of handler for it to be
    372 considered as a possible match.
    373 Like termination, when viewed on its own, a @try@ statement with
    374 @catchResume@ clauses simply executes the statements in the @GUARDED_BLOCK@,
    375 and when those are finished, the try statement finishes.
    376 
    377 However, while the guarded statements are being executed, including any invoked
    378 functions, a resumption exception may be thrown. If that exception is not handled by a try
    379 statement further up the stack, the handlers following the try block are now
    380 searched for a matching resumption exception-type from top to bottom.
    381 
    382 Like termination, exception matching checks each @catch@ clasue from top to bottom, if the representation of the thrown exception-type is
    383 the same or a descendant type of the exception types in the @catchResume@ clauses. If
    384 it is the same or a descendant of @EXCEPTION_TYPE@$_i$, then the optional @NAME@$_i$ is
    385 bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    386 are executed. If control reaches the end of the handler, the exception is
    387 freed and control continues after the @throwResume@ statement.
    388 
    389 Like termination, if no resumption handler is found during the search, the
    390 default resumption handler visible at the raise is called, which is the best
    391 match at the according to \CFA's overloading rules. This function is passed the
    392 exception given to the raise. After the default handler is run, execution
    393 continues after the @throwResume@ statement.
    394 
    395 There is a global @defaultResumptionHandler@ that is polymorphic over all
    396 resumption and preforms a termination throw on the exception.
     381If the handlers are not involved in a search this will simply execute the
     382@GUARDED_BLOCK@ and then continue to the next statement.
     383Its purpose is to add handlers onto the stack.
     384(Note, termination and resumption handlers may be intermixed in a @try@
     385statement but the kind of throw must be the same as the handler for it to be
     386considered as a possible match.)
     387
     388If a search for a resumption handler reaches a try block it will check each
     389@catchResume@ clause, top-to-bottom.
     390At 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
     393finished control will return to the @throwResume@ statement.
     394
     395Like termination, if no resumption handler is found, the default handler
     396visible at the throw statement is called. It will use the best match at the
     397call sight according to \CFA's overloading rules. The default handler is
     398passed the exception given to the throw. When the default handler finishes
     399execution continues after the throw statement.
     400
     401There is a global @defaultResumptionHandler@ is polymorphic over all
     402termination exceptions and preforms a termination throw on the exception.
    397403The @defaultTerminationHandler@ for that throw is matched at the original
    398404throw statement (the resumption @throwResume@) and it can be customized by
    399405introducing a new or better match as well.
    400406
    401 \subsection{Resumption Marking}
     407% \subsubsection?
     408
    402409A key difference between resumption and termination is that resumption does
    403 not unwind the stack. A side effect is that when a handler is matched
    404 and run its try block (the guarded statements) and every try statement
     410not unwind the stack. A side effect that is that when a handler is matched
     411and run it's try block (the guarded statements) and every try statement
    405412searched before it are still on the stack. This can lead to the recursive
    406413resumption problem.
     
    416423}
    417424\end{cfa}
    418 When this code is executed the guarded @throwResume@ starts a
    419 search and matches the handler in the @catchResume@ clause. The handler is
    420 called and placed on the stack on top of the try-block. The second throw in the handler
    421 searches the same try block and calls another instance of the
     425When this code is executed the guarded @throwResume@ will throw, start a
     426search and match the handler in the @catchResume@ clause. This will be
     427call and placed on the stack on top of the try-block. The second throw then
     428throws and will search the same try block and put call another instance of the
    422429same handler leading to an infinite loop.
    423430
    424 While this situation is trivial and easy to avoid, much more complex cycles
     431This situation is trivial and easy to avoid, but much more complex cycles
    425432can form with multiple handlers and different exception types.
    426433
    427 To prevent this case, examined try statements on the stack are marked, so that
    428 subsequent resumption searches skip over them and continue with the next unmarked section
    429 of the stack.
    430 Unmarking occurs when that exception is handled
    431 or the search completes without finding a handler.
     434To prevent all of these cases we mask sections of the stack, or equivalently
     435the try statements on the stack, so that the resumption search skips over
     436them and continues with the next unmasked section of the stack.
     437
     438A section of the stack is marked when it is searched to see if it contains
     439a handler for an exception and unmarked when that exception has been handled
     440or the search was completed without finding a handler.
    432441
    433442% This might need a diagram. But it is an important part of the justification
    434443% of the design of the traversal order.
    435 
    436 \begin{center}
    437 %\begin{verbatim}
    438 %       throwResume2 ----------.
    439 %            |                 |
    440 % generated from handler       |
    441 %            |                 |
    442 %         handler              |
    443 %            |                 |
    444 %        throwResume1 -----.   :
    445 %            |             |   :
    446 %           try            |   : search skip
    447 %            |             |   :
    448 %        catchResume  <----'   :
    449 %            |                 |
    450 %\end{verbatim}
    451 \input{stackMarking}
    452 \end{center}
    453 
    454 The resulting search can be understood by thinking about what is searched for
    455 termination. When a throw happens in a handler, a termination handler
     444\begin{verbatim}
     445       throwResume2 ----------.
     446            |                 |
     447 generated from handler       |
     448            |                 |
     449         handler              |
     450            |                 |
     451        throwResume1 -----.   :
     452            |             |   :
     453           try            |   : search skip
     454            |             |   :
     455        catchResume  <----'   :
     456            |                 |
     457\end{verbatim}
     458
     459The rules can be remembered as thinking about what would be searched in
     460termination. So when a throw happens in a handler; a termination handler
    456461skips everything from the original throw to the original catch because that
    457 part of the stack is unwound. A resumption handler skips the same
    458 section of stack because it is marked.
    459 A throw in a resumption default-handler performs the same search as the original
    460 @throwResume@ because for resumption nothing has been unwound.
    461 
    462 The symmetry between resumption masking and termination searching is why this pattern was picked. Other patterns,
    463 such as marking just the handlers that caught, also work but the
    464 symmetry seems to match programmer intuition.
     462part of the stack has been unwound, a resumption handler skips the same
     463section of stack because it has been masked.
     464A throw in a default handler will preform the same search as the original
     465throw because; for termination nothing has been unwound, for resumption
     466the mask will be the same.
     467
     468The symmetry with termination is why this pattern was picked. Other patterns,
     469such as marking just the handlers that caught, also work but lack the
     470symmetry which means there is more to remember.
    465471
    466472\section{Conditional Catch}
    467 Both termination and resumption handler-clauses can be given an additional
    468 condition to further control which exceptions is handled:
    469 \begin{cfa}
    470 catch (EXCEPTION_TYPE [* NAME] @; CONDITION@)
     473Both termination and resumption handler clauses can be given an additional
     474condition to further control which exceptions they handle:
     475\begin{cfa}
     476catch (EXCEPTION_TYPE * NAME ; CONDITION)
    471477\end{cfa}
    472478First, the same semantics is used to match the exception type. Second, if the
    473479exception matches, @CONDITION@ is executed. The condition expression may
    474 reference all names in the scope of the try block and @NAME@
     480reference all names in scope at the beginning of the try block and @NAME@
    475481introduced in the handler clause. If the condition is true, then the handler
    476482matches. Otherwise, the exception search continues as if the exception type
    477483did not match.
    478 
    479 Conditional catch allows fine-gain matching based on object values as well as exception types.
    480 For example, assume the exception hierarchy @OpenFailure@ $\rightarrow$ @CreateFailure@ and these exceptions are raised by function @open@.
    481 \begin{cfa}
    482 try {
    483         f1 = open( ... ); // open raises CreateFailure/OpenFailure
    484         f2 = open( ... ); //    with the associate file
    485         ...
    486 } catch( CreateFailure * f ; @fd( f ) == f1@ ) {
    487         // only handle IO failure for f1
    488 } catch( OpenFailure * f ; @fd( f ) == f2@ ) {
    489         // only handle IO failure for f2
    490 }
    491 \end{cfa}
    492 Here, matching is very precise on the I/O exception and particular file with an open problem.
    493 This capability cannot be easily mimiced within the handler.
    494484\begin{cfa}
    495485try {
     
    497487        f2 = open( ... );
    498488        ...
    499 } catch( CreateFailure * f ) {
    500         if ( @fd( f ) == f1@ ) ... else // reraise
    501 } catch( OpenFailure * f ) {
    502         if ( @fd( f ) == f2@ ) ... else // reraise
     489} catch( IOFailure * f ; fd( f ) == f1 ) {
     490        // only handle IO failure for f1
    503491}
    504492\end{cfa}
    505 When an exception @CreateFailure@ is raised, the first handler catches the
    506 derived exception and reraises it if the object is inappropriate. The reraise
    507 immediately terminates the current guarded block, which precludes the handler
    508 for the base exception @OpenFailure@ from consideration for object
    509 @f2@. Therefore, the ``catch first, then reraise'' approach is an incomplete
    510 substitute for conditional catch.
    511 
    512 \section{Reraise}
     493Note, catching @IOFailure@, checking for @f1@ in the handler, and re-raising the
     494exception if not @f1@ is different because the re-raise does not examine any of
     495remaining 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
     499have rethrows/reraises instead.}
     500
    513501\label{s:Rethrowing}
    514 \colour{red}{From Andrew: I recommend we talk about why the language doesn't
    515 have rethrows/reraises instead.}
    516 
    517502Within the handler block or functions called from the handler block, it is
    518503possible to reraise the most recently caught exception with @throw@ or
     
    533518is part of an unwound stack frame. To prevent this problem, a new default
    534519handler is generated that does a program-level abort.
    535 \PAB{I don't see how this is different from the normal throw/throwResume.}
    536520
    537521\section{Finally Clauses}
    538 Finally clauses are used to perform unconditional clean-up when leaving a
    539 scope and appear at the end of a try statement after any catch clauses:
     522Finally clauses are used to preform unconditional clean-up when leaving a
     523scope. They are placed at the end of a try statement:
    540524\begin{cfa}
    541525try {
     
    548532The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    549533stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    550 finishes, or during an unwind.
     534finishes or during an unwind.
    551535The only time the block is not executed is if the program is exited before
    552536the stack is unwound.
    553537
    554538Execution of the finally block should always finish, meaning control runs off
    555 the end of the block. This requirement ensures execution always continues as if the
    556 finally clause is not present, \ie @finally@ is for cleanup not changing control
     539the end of the block. This requirement ensures always continues as if the
     540finally clause is not present, \ie finally is for cleanup not changing control
    557541flow. Because of this requirement, local control flow out of the finally block
    558542is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
    559543@return@ that causes control to leave the finally block. Other ways to leave
    560544the finally block, such as a long jump or termination are much harder to check,
    561 and at best require additional run-time overhead, and so are
     545and at best requiring additional run-time overhead, and so are mealy
    562546discouraged.
    563547
    564548Not all languages with exceptions have finally clauses. Notably \Cpp does
    565 without it as destructors serve a similar role. Although destructors and
    566 finally clauses can be used in many of the same areas, they have their own
     549without it as descructors serve a similar role. Although destructors and
     550finally clauses can be used in many of the same areas they have their own
    567551use cases like top-level functions and lambda functions with closures.
    568552Destructors take a bit more work to set up but are much easier to reuse while
    569 finally clauses are good for one-off situations and can easily include local information.
     553finally clauses are good for once offs and can include local information.
    570554
    571555\section{Cancellation}
    572 \label{s:Cancellation}
    573 Cancellation is a stack-level abort, which can be thought of as an
    574 uncatchable termination. It unwinds the entire stack, and when
    575 possible, forwards the cancellation exception to a different stack.
     556Cancellation is a stack-level abort, which can be thought of as as an
     557uncatchable termination. It unwinds the entirety of the current stack, and if
     558possible forwards the cancellation exception to a different stack.
    576559
    577560Cancellation is not an exception operation like termination or resumption.
     
    580563throw, this exception is not used in matching only to pass information about
    581564the cause of the cancellation.
    582 (This semantics also means matching cannot fail so there is no default handler.)
    583 
    584 After @cancel_stack@ is called, the exception is copied into the EHM's
    585 memory and the current stack is
     565(This also means matching cannot fail so there is no default handler either.)
     566
     567After @cancel_stack@ is called the exception is copied into the exception
     568handling mechanism's memory. Then the entirety of the current stack is
    586569unwound. After that it depends one which stack is being cancelled.
    587570\begin{description}
    588571\item[Main Stack:]
    589572The main stack is the one used by the program main at the start of execution,
    590 and is the only stack in a sequential program. Even in a concurrent program,
    591 the main stack is often used as the environment to start the concurrent threads.
     573and is the only stack in a sequential program. Even in a concurrent program
     574the main stack is only dependent on the environment that started the program.
    592575Hence, when the main stack is cancelled there is nowhere else in the program
    593 to go. Hence, after the main stack is unwound, there is a program-level abort.
     576to notify. After the stack is unwound, there is a program-level abort.
    594577
    595578\item[Thread Stack:]
    596 A thread stack is created for a \CFA @thread@ object or object that satisfies the
     579A thread stack is created for a @thread@ object or object that satisfies the
    597580@is_thread@ trait. A thread only has two points of communication that must
    598 happen: start and join. A thread must be running to perform a
    599 cancellation (a thread cannot cancel another thread). Therefore, a cancellation must
    600 occur after start and before join, so join is used
    601 for cancellation communication.
     581happen: start and join. As the thread must be running to perform a
     582cancellation, it must occur after start and before join, so join is used
     583for communication here.
    602584After the stack is unwound, the thread halts and waits for
    603585another thread to join with it. The joining thread checks for a cancellation,
    604586and if present, resumes exception @ThreadCancelled@.
    605587
    606 \begin{sloppypar}
    607588There is a subtle difference between the explicit join (@join@ function) and
    608 implicit join (from a @thread@'s destructor call). The explicit join takes the default
     589implicit join (from a destructor call). The explicit join takes the default
    609590handler (@defaultResumptionHandler@) from its calling context, which is used if
    610591the exception is not caught. The implicit join does a program abort instead.
    611 \end{sloppypar}
    612 
    613 \PAB{uC++ does not have these issues, but catch(...) is not working.}
    614 \begin{lstlisting}[language=uC++]
    615 #include <iostream>
    616 using namespace std;
    617 
    618 struct Cl {
    619         ~Cl() { cout << "C" << endl; }
    620 };
    621 _Coroutine C {
    622         void main() {
    623                 Cl c;
    624                 try {
    625                         cancel();
    626                 } catch( ... ) {
    627                         cout << "..." << endl;
    628                 } _Finally {
    629                         cout << "F" << endl;
    630                 }
    631                 }
    632   public:
    633         void mem() { resume(); }
    634 };
    635 _Task T {
    636         void main() {
    637                 Cl c;
    638                 try {
    639                         cancel();
    640                 } catch( ... ) {
    641                         cout << "..." << endl;
    642                 } _Finally {
    643                         cout << "F" << endl;
    644                 }
    645         }
    646 };
    647 int main() {
    648         C c;
    649         cout << "here1" << endl;
    650         c.mem();
    651         cout << "here2" << endl;
    652         {
    653                 T t;
    654         }
    655         cout << "here3" << endl;
    656 }
    657 \end{lstlisting}
    658 
    659 \PAB{This discussion should be its own section.}
     592
    660593This semantics is for safety. If an unwind is triggered while another unwind
    661 is underway only one of them can proceed as they both want to ``consume" the
     594is underway only one of them can proceed as they both want to ``consume'' the
    662595stack. Letting both try to proceed leads to very undefined behaviour.
    663596Both termination and cancellation involve unwinding and, since the default
     
    665598happen in an implicate join inside a destructor. So there is an error message
    666599and an abort instead.
    667 
    668600\todo{Perhaps have a more general disucssion of unwind collisions before
    669601this point.}
     
    688620for the exception. So it will use the default handler like a regular throw.
    689621\end{description}
    690 
    691 \PAB{You should have more test programs that compare \CFA EHM to uC++ EHM.}
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rea1c97b rde47a9d  
    105105\usepackage{amsmath,amssymb,amstext}
    106106% For including graphics N.B. pdftex graphics driver
    107 %\usepackage[pdftex]{graphicx}
    108 \usepackage{epic,eepic}
    109 \usepackage{graphicx}
     107\usepackage[pdftex]{graphicx}
    110108% Removes large sections of the document.
    111109\usepackage{comment}
     
    119117% Use the "hyperref" package
    120118% N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE
    121 %\usepackage[pdftex,pagebackref=true]{hyperref} % with basic options
    122 \usepackage[pagebackref=true]{hyperref} % with basic options
     119\usepackage[pdftex,pagebackref=true]{hyperref} % with basic options
    123120%\usepackage[pdftex,pagebackref=true]{hyperref}
    124121% N.B. pagebackref=true provides links back from the References to the body
Note: See TracChangeset for help on using the changeset viewer.