Changes in / [c9f9d4f:3b8acfb]


Ignore:
Location:
doc/theses/andrew_beach_MMath
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/conclusion.tex

    rc9f9d4f r3b8acfb  
    11\chapter{Conclusion}
     2\label{c:conclusion}
    23% Just a little knot to tie the paper together.
    34

  • doc/theses/andrew_beach_MMath/existing.tex

    rc9f9d4f r3b8acfb  
    1010
    1111Only those \CFA features pertaining to this thesis are discussed.
    12 % Also, only new features of \CFA will be discussed,
    1312A familiarity with
    1413C or C-like languages is assumed.
    … …  
    1716\CFA has extensive overloading, allowing multiple definitions of the same name
    1817to be defined~\cite{Moss18}.
    19 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    20 char @i@; int @i@; double @i@;
    21 int @f@(); double @f@();
    22 void @g@( int ); void @g@( double );
    23 \end{lstlisting}
     18\begin{cfa}
     19char i; int i; double i;
     20int f(); double f();
     21void g( int ); void g( double );
     22\end{cfa}
    2423This feature requires name mangling so the assembly symbols are unique for
    2524different overloads. For compatibility with names in C, there is also a syntax
    … …  
    6362int && rri = ri;
    6463rri = 3;
    65 &ri = &j; // rebindable
     64&ri = &j;
    6665ri = 5;
    6766\end{cfa}
    … …  
    7978\end{minipage}
    8079
    81 References are intended for pointer situations where dereferencing is the common usage,
    82 \ie the value is more important than the pointer.
     80References are intended to be used when the indirection of a pointer is
     81required, but the address is not as important as the value and dereferencing
     82is the common usage.
    8383Mutable references may be assigned to by converting them to a pointer
    84 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
     84with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above.
     85% ???
    8586
    8687\section{Operators}
    8788
    8889\CFA implements operator overloading by providing special names, where
    89 operator usages are translated into function calls using these names.
     90operator expressions are translated into function calls using these names.
    9091An operator name is created by taking the operator symbols and joining them with
    9192@?@s to show where the arguments go.
    … …  
    9495This syntax make it easy to tell the difference between prefix operations
    9596(such as @++?@) and post-fix operations (@?++@).
    96 For example, plus and equality operators are defined for a point type.
     97
     98As an example, here are the addition and equality operators for a point type.
    9799\begin{cfa}
    98100point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
    … …  
    102104}
    103105\end{cfa}
    104 Note these special names are not limited to builtin
    105 operators, and hence, may be used with arbitrary types.
    106 \begin{cfa}
    107 double ?+?( int x, point y ); // arbitrary types
    108 \end{cfa}
    109 % Some ``near misses", that are that do not match an operator form but looks like
    110 % it may have been supposed to, will generate warning but otherwise they are
    111 % left alone.
    112 Because operators are never part of the type definition they may be added
    113 at any time, including on built-in types.
     106Note that this syntax works effectively but a textual transformation,
     107the compiler converts all operators into functions and then resolves them
     108normally. This means any combination of types may be used,
     109although nonsensical ones (like @double ?==?(point, int);@) are discouraged.
     110This feature is also used for all builtin operators as well,
     111although those are implicitly provided by the language.
    114112
    115113%\subsection{Constructors and Destructors}
    116 
    117 \CFA also provides constructors and destructors as operators, which means they
    118 are functions with special operator names rather than type names in \Cpp.
    119 While constructors and destructions are normally called implicitly by the compiler,
    120 the special operator names, allow explicit calls.
    121 
    122 % Placement new means that this is actually equivalent to C++.
     114In \CFA, constructors and destructors are operators, which means they are
     115functions with special operator names rather than type names in \Cpp.
     116Both constructors and destructors can be implicity called by the compiler,
     117however the operator names allow explicit calls.
     118% Placement new means that this is actually equivant to C++.
    123119
    124120The special name for a constructor is @?{}@, which comes from the
    … …  
    129125struct Example { ... };
    130126void ?{}(Example & this) { ... }
     127{
     128        Example a;
     129        Example b = {};
     130}
    131131void ?{}(Example & this, char first, int num) { ... }
    132 Example a;              // implicit constructor calls
    133 Example b = {};
    134 Example c = {'a', 2};
    135 \end{cfa}
    136 Both @a@ and @b@ are initialized with the first constructor,
    137 while @c@ is initialized with the second.
    138 Constructor calls can be replaced with C initialization using special operator \lstinline{@=}.
    139 \begin{cfa}
    140 Example d @= {42};
    141 \end{cfa}
     132{
     133        Example c = {'a', 2};
     134}
     135\end{cfa}
     136Both @a@ and @b@ will be initalized with the first constructor,
     137@b@ because of the explicit call and @a@ implicitly.
     138@c@ will be initalized with the second constructor.
     139Currently, there is no general way to skip initialation.
     140% I don't use @= anywhere in the thesis.
     141
    142142% I don't like the \^{} symbol but $^\wedge$ isn't better.
    143143Similarly, destructors use the special name @^?{}@ (the @^@ has no special
    144144meaning).
    145 % These are a normally called implicitly called on a variable when it goes out
    146 % of scope. They can be called explicitly as well.
    147145\begin{cfa}
    148146void ^?{}(Example & this) { ... }
    149147{
    150         Example e;      // implicit constructor call
    151         ^?{}(e);                // explicit destructor call
    152         ?{}(e);         // explicit constructor call
    153 } // implicit destructor call
     148        Example d;
     149        ^?{}(d);
     150
     151        Example e;
     152} // Implicit call of ^?{}(e);
    154153\end{cfa}
    155154
    … …  
    225224The global definition of @do_once@ is ignored, however if quadruple took a
    226225@double@ argument, then the global definition would be used instead as it
    227 is a better match.
    228 % Aaron's thesis might be a good reference here.
    229 
    230 To avoid typing long lists of assertions, constraints can be collect into
    231 convenient package called a @trait@, which can then be used in an assertion
     226would then be a better match.
     227\todo{cite Aaron's thesis (maybe)}
     228
     229To avoid typing long lists of assertions, constraints can be collected into
     230convenient a package called a @trait@, which can then be used in an assertion
    232231instead of the individual constraints.
    233232\begin{cfa}
    … …  
    253252        node(T) * next;
    254253        T * data;
    255 }
     254};
    256255node(int) inode;
    257256\end{cfa}
    … …  
    293292};
    294293CountUp countup;
    295 for (10) sout | resume(countup).next; // print 10 values
    296294\end{cfa}
    297295Each coroutine has a @main@ function, which takes a reference to a coroutine
    298296object and returns @void@.
    299297%[numbers=left] Why numbers on this one?
    300 \begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
     298\begin{cfa}
    301299void main(CountUp & this) {
    302         for (unsigned int up = 0;; ++up) {
    303                 this.next = up;
     300        for (unsigned int next = 0 ; true ; ++next) {
     301                this.next = next;
    304302                suspend;$\label{suspend}$
    305303        }
    … …  
    307305\end{cfa}
    308306In this function, or functions called by this function (helper functions), the
    309 @suspend@ statement is used to return execution to the coroutine's resumer
    310 without terminating the coroutine's function(s).
     307@suspend@ statement is used to return execution to the coroutine's caller
     308without terminating the coroutine's function.
    311309
    312310A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    313311The first resume calls the @main@ function at the top. Thereafter, resume calls
    314312continue a coroutine in the last suspended function after the @suspend@
    315 statement, in this case @main@ line~\ref{suspend}.  The @resume@ function takes
    316 a reference to the coroutine structure and returns the same reference. The
    317 return value allows easy access to communication variables defined in the
    318 coroutine object. For example, the @next@ value for coroutine object @countup@
    319 is both generated and collected in the single expression:
    320 @resume(countup).next@.
     313statement. In this case there is only one and, hence, the difference between
     314subsequent calls is the state of variables inside the function and the
     315coroutine object.
     316The return value of @resume@ is a reference to the coroutine, to make it
     317convent to access fields of the coroutine in the same expression.
     318Here is a simple example in a helper function:
     319\begin{cfa}
     320unsigned int get_next(CountUp & this) {
     321        return resume(this).next;
     322}
     323\end{cfa}
     324
     325When the main function returns the coroutine halts and can no longer be
     326resumed.
    321327
    322328\subsection{Monitor and Mutex Parameter}
    … …  
    330336exclusion on a monitor object by qualifying an object reference parameter with
    331337@mutex@.
    332 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
    334 \end{lstlisting}
     338\begin{cfa}
     339void example(MonitorA & mutex argA, MonitorB & mutex argB);
     340\end{cfa}
    335341When the function is called, it implicitly acquires the monitor lock for all of
    336342the mutex parameters without deadlock.  This semantics means all functions with
    … …  
    362368{
    363369        StringWorker stringworker; // fork thread running in "main"
    364 } // implicitly join with thread / wait for completion
     370} // Implicit call to join(stringworker), waits for completion.
    365371\end{cfa}
    366372The thread main is where a new thread starts execution after a fork operation

  • doc/theses/andrew_beach_MMath/features.tex

    rc9f9d4f r3b8acfb  
    1616throw/catch as a particular kind of raise/handle.
    1717These are the two parts that the user writes and may
    18 be the only two pieces of the EHM that have any syntax in a language.
     18be the only two pieces of the EHM that have any syntax in the language.
    1919
    2020\paragraph{Raise}
    21 The raise is the starting point for exception handling
    22 by raising an exception, which passes it to
     21The raise is the starting point for exception handling. It marks the beginning
     22of exception handling by raising an exception, which passes it to
    2323the EHM.
    2424
    2525Some well known examples include the @throw@ statements of \Cpp and Java and
    26 the \code{Python}{raise} statement of Python. In real systems, a raise may
    27 perform some other work (such as memory management) but for the
     26the \code{Python}{raise} statement from Python. In real systems a raise may
     27preform some other work (such as memory management) but for the
    2828purposes of this overview that can be ignored.
    2929
    3030\paragraph{Handle}
    31 The primary purpose of an EHM is to run some user code to handle a raised
    32 exception. This code is given, with some other information, in 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.
    3333
    3434A handler has three common features: the previously mentioned user code, a
    35 region of code it guards, and an exception label/condition that matches
    36 the raised exception.
     35region of code they guard and an exception label/condition that matches
     36certain exceptions.
    3737Only raises inside the guarded region and raising exceptions that match the
    3838label can be handled by a given handler.
    3939If multiple handlers could can handle an exception,
    40 EHMs define a rule to pick one, such as ``best match" or ``first found".
     40EHMs will define a rule to pick one, such as ``best match" or ``first found".
    4141
    4242The @try@ statements of \Cpp, Java and Python are common examples. All three
    43 show the common features of guarded region, raise, matching and handler.
    44 \begin{cfa}
    45 try {                           // guarded region
    46         ...     
    47         throw exception;        // raise
    48         ...     
    49 } catch( exception ) {  // matching condition, with exception label
    50         ...                             // handler code
    51 }
    52 \end{cfa}
     43also show another common feature of handlers, they are grouped by the guarded
     44region.
    5345
    5446\subsection{Propagation}
    5547After an exception is raised comes what is usually the biggest step for the
    56 EHM: finding and setting up the handler for execution. The propagation from raise to
     48EHM: finding and setting up the handler. The propagation from raise to
    5749handler can be broken up into three different tasks: searching for a handler,
    5850matching against the handler and installing the handler.
    … …  
    6052\paragraph{Searching}
    6153The EHM begins by searching for handlers that might be used to handle
    62 the exception. The search is restricted to
    63 handlers that have the raise site in their guarded
     54the exception. Searching is usually independent of the exception that was
     55thrown as it looks for handlers that have the raise site in their guarded
    6456region.
    6557The search includes handlers in the current function, as well as any in
    … …  
    6759
    6860\paragraph{Matching}
    69 Each handler found is matched with the raised exception. The exception
    70 label defines a condition that is used with the exception and decides if
     61Each handler found has to be matched with the raised exception. The exception
     62label defines a condition that is used with exception and decides if
    7163there is a match or not.
     64
    7265In languages where the first match is used, this step is intertwined with
    73 searching; a match check is performed immediately after the search finds
    74 a handler.
     66searching; a match check is preformed immediately after the search finds
     67a possible handler.
    7568
    7669\paragraph{Installing}
    77 After a handler is chosen, it must be made ready to run.
     70After a handler is chosen it must be made ready to run.
    7871The implementation can vary widely to fit with the rest of the
    7972design of the EHM. The installation step might be trivial or it could be
    … …  
    8275
    8376If a matching handler is not guaranteed to be found, the EHM needs a
    84 different course of action for this case.
     77different course of action for the case where no handler matches.
    8578This situation only occurs with unchecked exceptions as checked exceptions
    86 (such as in Java) are guaranteed to find a matching handler.
    87 The unhandled action is usually very general, such as aborting the program.
     79(such as in Java) can make the guarantee.
     80This unhandled action is usually very general, such as aborting the program.
    8881
    8982\paragraph{Hierarchy}
    … …  
    9285exception hierarchy is a natural extension of the object hierarchy.
    9386
    94 Consider the following exception hierarchy:
     87Consider the following hierarchy of exceptions:
    9588\begin{center}
    9689\input{exception-hierarchy}
    9790\end{center}
     91
    9892A handler labeled with any given exception can handle exceptions of that
    9993type or any child type of that exception. The root of the exception hierarchy
    100 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types,
     94(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
    10195and the exceptions in the middle can be used to catch different groups of
    10296related exceptions.
    10397
    10498This system has some notable advantages, such as multiple levels of grouping,
    105 the ability for libraries to add new exception types, and the isolation
     99the ability for libraries to add new exception types and the isolation
    106100between different sub-hierarchies.
    107101This design is used in \CFA even though it is not a object-orientated
    … …  
    116110is usually set up to do most of the work.
    117111
    118 The EHM can return control to many different places, where
     112The EHM can return control to many different places,
    119113the most common are after the handler definition (termination)
    120114and after the raise (resumption).
    … …  
    123117For effective exception handling, additional information is often passed
    124118from the raise to the handler and back again.
    125 So far, only communication of the exception's identity is covered.
    126 A common communication method for passing more information is putting fields into the exception instance
     119So far only communication of the exceptions' identity has been covered.
     120A common communication method is putting fields into the exception instance
    127121and giving the handler access to them.
    128 Using reference fields pointing to data at the raise location allows data to be
     122Passing the exception by reference instead of by value can allow data to be
    129123passed in both directions.
    130124
    131125\section{Virtuals}
    132 \label{s:Virtuals}
     126\label{s:virtuals}
    133127Virtual types and casts are not part of \CFA's EHM nor are they required for
    134 an EHM.
    135 However, one of the best ways to support an exception hierarchy
     128any EHM.
     129However, it is one of the best ways to support an exception hierarchy
    136130is via a virtual hierarchy and dispatch system.
    137 Ideally, the virtual system should have been part of \CFA before the work
     131
     132Ideally, the virtual system would have been part of \CFA before the work
    138133on exception handling began, but unfortunately it was not.
    139134Hence, only the features and framework needed for the EHM were
    140 designed and implemented for this thesis. Other features were considered to ensure that
     135designed and implemented. Other features were considered to ensure that
    141136the structure could accommodate other desirable features in the future
    142 but are not implemented.
    143 The rest of this section only discusses the implemented subset of the
    144 virtual-system design.
     137but they were not implemented.
     138The rest of this section will only discuss the implemented subset of the
     139virtual system design.
    145140
    146141The virtual system supports multiple ``trees" of types. Each tree is
    … …  
    149144number of children.
    150145Any type that belongs to any of these trees is called a virtual type.
    151 For example, the following hypothetical syntax creates two virtual-type trees.
    152 \begin{flushleft}
    153 \lstDeleteShortInline@
    154 \begin{tabular}{@{\hspace{20pt}}l@{\hspace{20pt}}l}
    155 \begin{cfa}
    156 vtype V0, V1(V0), V2(V0);
    157 vtype W0, W1(W0), W2(W1);
    158 \end{cfa}
    159 &
    160 \raisebox{-0.6\totalheight}{\input{vtable}}
    161 \end{tabular}
    162 \lstMakeShortInline@
    163 \end{flushleft}
     146
    164147% A type's ancestors are its parent and its parent's ancestors.
    165148% The root type has no ancestors.
    166149% A type's descendants are its children and its children's descendants.
    167 Every virtual type (tree node) has a pointer to a virtual table with a unique
    168 @Id@ and a list of virtual members (see \autoref{s:VirtualSystem} for
    169 details). Children inherit their parent's list of virtual members but may add
    170 and/or replace members.  For example,
    171 \begin{cfa}
    172 vtable W0 | { int ?<?( int, int ); int ?+?( int, int ); }
    173 vtable W1 | { int ?+?( int, int ); int w, int ?-?( int, int ); }
    174 \end{cfa}
    175 creates a virtual table for @W0@ initialized with the matching @<@ and @+@
    176 operations visible at this declaration context.  Similarly, @W1@ is initialized
    177 with @<@ from inheritance with @W0@, @+@ is replaced, and @-@ is added, where
    178 both operations are matched at this declaration context. It is important to
    179 note that these are virtual members, not virtual methods of object-orientated
    180 programming, and can be of any type. Finally, trait names can be used to
    181 specify the list of virtual members.
    182 
    183 \PAB{Need to look at these when done.
     150
     151Every virtual type also has a list of virtual members. Children inherit
     152their parent's list of virtual members but may add new members to it.
     153It is important to note that these are virtual members, not virtual methods
     154of object-orientated programming, and can be of any type.
    184155
    185156\CFA still supports virtual methods as a special case of virtual members.
    … …  
    189160as if it were a method.
    190161\todo{Clarify (with an example) virtual methods.}
    191 }%
     162
     163Each virtual type has a unique id.
     164This id and all the virtual members are combined
     165into a virtual table type. Each virtual type has a pointer to a virtual table
     166as a hidden field.
     167\todo{Might need a diagram for virtual structure.}
    192168
    193169Up until this point the virtual system is similar to ones found in
    194 object-orientated languages but this is where \CFA diverges. Objects encapsulate a
    195 single set of methods in each type, universally across the entire program,
    196 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
    197 single set of methods. In this sense,
    198 object-oriented types are ``closed" and cannot be altered.
    199 
    200 In \CFA, types do not encapsulate any code. Traits are local for each function and
    201 types can satisfy a local trait, stop satisfying it or, satisfy the same
    202 trait in a different way at any lexical location in the program where a function is call.
    203 In this sense, the set of functions/variables that satisfy a trait for a type is ``open" as the set can change at every call site.
     170object-orientated languages but this where \CFA diverges. Objects encapsulate a
     171single set of behaviours in each type, universally across the entire program,
     172and indeed all programs that use that type definition. In this sense, the
     173types are ``closed" and cannot be altered.
     174
     175In \CFA, types do not encapsulate any behaviour. Traits are local and
     176types can begin to satisfy a trait, stop satisfying a trait or satisfy the same
     177trait in a different way at any lexical location in the program.
     178In this sense, they are ``open" as they can change at any time.
    204179This capability means it is impossible to pick a single set of functions
    205 that represent a type's implementation across a program.
     180that represent the type's implementation across the program.
    206181
    207182\CFA side-steps this issue by not having a single virtual table for each
    208183type. A user can define virtual tables that are filled in at their
    209184declaration and given a name. Anywhere that name is visible, even if it is
    210 defined locally inside a function \PAB{What does this mean? (although that means it does not have a
    211 static lifetime)}, it can be used.
     185defined locally inside a function (although that means it does not have a
     186static lifetime), it can be used.
    212187Specifically, a virtual type is ``bound" to a virtual table that
    213188sets the virtual members for that object. The virtual members can be accessed
    … …  
    247222completing the virtual system). The imaginary assertions would probably come
    248223from a trait defined by the virtual system, and state that the exception type
    249 is a virtual type, is a descendant of @exception_t@ (the base exception type),
     224is a virtual type, is a descendant of @exception_t@ (the base exception type)
    250225and note its virtual table type.
    251226
    … …  
    267242\end{cfa}
    268243Both traits ensure a pair of types are an exception type, its virtual table
    269 type,
     244type
    270245and defines one of the two default handlers. The default handlers are used
    271246as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
    … …  
    276251facing way. So these three macros are provided to wrap these traits to
    277252simplify referring to the names:
    278 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
     253@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    279254
    280255All three take one or two arguments. The first argument is the name of the
    … …  
    298273\CFA provides two kinds of exception handling: termination and resumption.
    299274These twin operations are the core of \CFA's exception handling mechanism.
    300 This section covers the general patterns shared by the two operations and
    301 then goes on to cover the details of each individual operation.
     275This section will cover the general patterns shared by the two operations and
     276then go on to cover the details each individual operation.
    302277
    303278Both operations follow the same set of steps.
    304 First, a user raises an exception.
    305 Second, the exception propagates up the stack.
    306 Third, if a handler is found, the exception is caught and the handler is run.
     279Both start with the user preforming a raise on an exception.
     280Then the exception propagates up the stack.
     281If a handler is found the exception is caught and the handler is run.
    307282After that control continues at a raise-dependent location.
    308 Fourth, if a handler is not found, a default handler is run and, if it returns, then control
     283If the search fails a default handler is run and, if it returns, then control
    309284continues after the raise.
    310285
    311 %This general description covers what the two kinds have in common.
    312 The differences in the two operations include how propagation is performed, where execution continues
    313 after an exception is caught and handled, and which default handler is run.
     286This general description covers what the two kinds have in common.
     287Differences include how propagation is preformed, where exception continues
     288after an exception is caught and handled and which default handler is run.
    314289
    315290\subsection{Termination}
    316291\label{s:Termination}
    317 Termination handling is the familiar EHM and used in most programming
     292Termination handling is the familiar kind and used in most programming
    318293languages with exception handling.
    319294It is a dynamic, non-local goto. If the raised exception is matched and
    … …  
    334309@is_termination_exception@ at the call site.
    335310Through \CFA's trait system, the trait functions are implicitly passed into the
    336 throw code for use by the EHM.
     311throw code and the EHM.
    337312A new @defaultTerminationHandler@ can be defined in any scope to
    338 change the throw's behaviour when a handler is not found (see below).
     313change the throw's behaviour (see below).
    339314
    340315The throw copies the provided exception into managed memory to ensure
    … …  
    346321% How to say propagation starts, its first sub-step is the search.
    347322Then propagation starts with the search. \CFA uses a ``first match" rule so
    348 matching is performed with the copied exception as the search key.
    349 It starts from the raise in the throwing function and proceeds towards the base of the stack,
     323matching is preformed with the copied exception as the search continues.
     324It starts from the throwing function and proceeds towards base of the stack,
    350325from callee to caller.
    351 At each stack frame, a check is made for termination handlers defined by the
     326At each stack frame, a check is made for resumption handlers defined by the
    352327@catch@ clauses of a @try@ statement.
    353328\begin{cfa}
    … …  
    361336\end{cfa}
    362337When viewed on its own, a try statement simply executes the statements
    363 in the \snake{GUARDED_BLOCK}, and when those are finished,
     338in \snake{GUARDED_BLOCK} and when those are finished,
    364339the try statement finishes.
    365340
    … …  
    367342invoked functions, all the handlers in these statements are included in the
    368343search path.
    369 Hence, if a termination exception is raised, these handlers may be matched
     344Hence, if a termination exception is raised these handlers may be matched
    370345against the exception and may handle it.
    371346
    372347Exception matching checks the handler in each catch clause in the order
    373348they appear, top to bottom. If the representation of the raised exception type
    374 is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
     349is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
    375350(if provided) is
    376351bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    … …  
    378353freed and control continues after the try statement.
    379354
    380 If no termination handler is found during the search, then the default handler
    381 (\defaultTerminationHandler) visible at the raise statement is called.
    382 Through \CFA's trait system the best match at the raise statement is used.
     355If no termination handler is found during the search then the default handler
     356(\defaultTerminationHandler) visible at the raise statement is run.
     357Through \CFA's trait system the best match at the raise statement will be used.
    383358This function is run and is passed the copied exception.
    384 If the default handler finishes, control continues after the raise statement.
     359If the default handler is run control continues after the raise statement.
    385360
    386361There is a global @defaultTerminationHandler@ that is polymorphic over all
    387362termination exception types.
     363Since it is so general a more specific handler can be
     364defined and is used for those types, effectively overriding the handler
     365for a particular exception type.
    388366The global default termination handler performs a cancellation
    389 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
    390 Since it is so general, a more specific handler is usually
    391 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
     367(see \vref{s:Cancellation}) on the current stack with the copied exception.
    392368
    393369\subsection{Resumption}
    394370\label{s:Resumption}
    395371
    396 Resumption exception handling is the less familar EHM, but is
     372Resumption exception handling is less common than termination but is
    397373just as old~\cite{Goodenough75} and is simpler in many ways.
    398374It is a dynamic, non-local function call. If the raised exception is
    399 matched, a closure is taken from up the stack and executed,
     375matched a closure is taken from up the stack and executed,
    400376after which the raising function continues executing.
    401377The common uses for resumption exceptions include
    … …  
    403379function once the error is corrected, and
    404380ignorable events, such as logging where nothing needs to happen and control
    405 should always continue from the raise point.
     381should always continue from the same place.
    406382
    407383A resumption raise is started with the @throwResume@ statement:
    … …  
    417393the exception system while handling the exception.
    418394
    419 At run-time, no exception copy is made, since
    420 resumption does not unwind the stack nor otherwise remove values from the
    421 current scope, so there is no need to manage memory to keep the exception in scope.
    422 
    423 Then propagation starts with the search. It starts from the raise in the
     395At run-time, no exception copy is made.
     396Resumption does not unwind the stack nor otherwise remove values from the
     397current scope, so there is no need to manage memory to keep things in scope.
     398
     399The EHM then begins propagation. The search starts from the raise in the
    424400resuming function and proceeds towards the base of the stack,
    425401from callee to caller.
    … …  
    435411}
    436412\end{cfa}
    437 % PAB, you say this above.
    438 % When a try statement is executed, it simply executes the statements in the
    439 % @GUARDED_BLOCK@ and then finishes.
    440 %
    441 % However, while the guarded statements are being executed, including any
    442 % invoked functions, all the handlers in these statements are included in the
    443 % search path.
    444 % Hence, if a resumption exception is raised, these handlers may be matched
    445 % against the exception and may handle it.
    446 %
    447 % Exception matching checks the handler in each catch clause in the order
    448 % they appear, top to bottom. If the representation of the raised exception type
    449 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
    450 % (if provided) is bound to a pointer to the exception and the statements in
    451 % @HANDLER_BLOCK@$_i$ are executed.
    452 % If control reaches the end of the handler, execution continues after the
    453 % the raise statement that raised the handled exception.
    454 %
    455 % Like termination, if no resumption handler is found during the search,
    456 % then the default handler (\defaultResumptionHandler) visible at the raise
    457 % statement is called. It will use the best match at the raise sight according
    458 % to \CFA's overloading rules. The default handler is
    459 % passed the exception given to the raise. When the default handler finishes
    460 % execution continues after the raise statement.
    461 %
    462 % There is a global @defaultResumptionHandler{} is polymorphic over all
    463 % resumption exceptions and performs a termination throw on the exception.
    464 % The \defaultTerminationHandler{} can be overridden by providing a new
    465 % function that is a better match.
    466 
    467 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
    468 for resumption as for termination, as does exception matching at each
    469 @catchResume@. Similarly, if no resumption handler is found during the search,
    470 then the currently visible default handler (\defaultResumptionHandler) is
    471 called and control continues after the raise statement if it returns. Finally,
    472 there is also a global @defaultResumptionHandler@, which can be overridden,
    473 that is polymorphic over all resumption exceptions but performs a termination
    474 throw on the exception rather than a cancellation.
    475 
    476 Throwing the exception in @defaultResumptionHandler@ has the positive effect of
    477 walking the stack a second time for a recovery handler. Hence, a programmer has
    478 two chances for help with a problem, fixup or recovery, should either kind of
    479 handler appear on the stack. However, this dual stack walk leads to following
    480 apparent anomaly:
    481 \begin{cfa}
    482 try {
    483         throwResume E;
    484 } catch (E) {
    485         // this handler runs
    486 }
    487 \end{cfa}
    488 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
    489 matches with @catchResume@. The anomaly results because the unmatched
    490 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
    491 
    492413% I wonder if there would be some good central place for this.
    493 Note, termination and resumption handlers may be used together
     414Note that termination handlers and resumption handlers may be used together
    494415in a single try statement, intermixing @catch@ and @catchResume@ freely.
    495416Each type of handler only interacts with exceptions from the matching
    496417kind of raise.
     418When a try statement is executed, it simply executes the statements in the
     419@GUARDED_BLOCK@ and then finishes.
     420
     421However, while the guarded statements are being executed, including any
     422invoked functions, all the handlers in these statements are included in the
     423search path.
     424Hence, if a resumption exception is raised these handlers may be matched
     425against the exception and may handle it.
     426
     427Exception matching checks the handler in each catch clause in the order
     428they appear, top to bottom. If the representation of the raised exception type
     429is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
     430(if provided) is bound to a pointer to the exception and the statements in
     431@HANDLER_BLOCK@$_i$ are executed.
     432If control reaches the end of the handler, execution continues after the
     433the raise statement that raised the handled exception.
     434
     435Like termination, if no resumption handler is found during the search,
     436the default handler (\defaultResumptionHandler) visible at the raise
     437statement is called. It will use the best match at the raise sight according
     438to \CFA's overloading rules. The default handler is
     439passed the exception given to the raise. When the default handler finishes
     440execution continues after the raise statement.
     441
     442There is a global \defaultResumptionHandler{} is polymorphic over all
     443resumption exceptions and preforms a termination throw on the exception.
     444The \defaultTerminationHandler{} can be overridden by providing a new
     445function that is a better match.
    497446
    498447\subsubsection{Resumption Marking}
    499448\label{s:ResumptionMarking}
    500449A key difference between resumption and termination is that resumption does
    501 not unwind the stack. A side effect is that, when a handler is matched
    502 and run, its try block (the guarded statements) and every try statement
     450not unwind the stack. A side effect that is that when a handler is matched
     451and run it's try block (the guarded statements) and every try statement
    503452searched before it are still on the stack. There presence can lead to
    504 the \emph{recursive resumption problem}.
     453the recursive resumption problem.
    505454
    506455The recursive resumption problem is any situation where a resumption handler
    … …  
    516465When this code is executed, the guarded @throwResume@ starts a
    517466search and matches the handler in the @catchResume@ clause. This
    518 call is placed on the stack above the try-block. Now the second raise in the handler
    519 searches the same try block, matches, and puts another instance of the
     467call is placed on the stack above the try-block. The second raise then
     468searches the same try block and puts another instance of the
    520469same handler on the stack leading to infinite recursion.
    521470
    522 While this situation is trivial and easy to avoid, much more complex cycles can
    523 form with multiple handlers and different exception types.  The key point is
    524 that the programmer's intuition expects every raise in a handler to start
    525 searching \emph{below} the @try@ statement, making it difficult to understand
    526 and fix the problem.
    527 
    528 To prevent all of these cases, each try statement is ``marked" from the
    529 time the exception search reaches it to either when a matching handler
    530 completes or when the search reaches the base
     471While this situation is trivial and easy to avoid, much more complex cycles
     472can form with multiple handlers and different exception types.
     473
     474To prevent all of these cases, a each try statement is ``marked" from the
     475time the exception search reaches it to either when the exception is being
     476handled completes the matching handler or when the search reaches the base
    531477of the stack.
    532478While a try statement is marked, its handlers are never matched, effectively
    … …  
    540486for instance, marking just the handlers that caught the exception,
    541487would also prevent recursive resumption.
    542 However, the rule selected mirrors what happens with termination,
    543 and hence, matches programmer intuition that a raise searches below a try.
    544 
    545 In detail, the marked try statements are the ones that would be removed from
    546 the stack for a termination exception, \ie those on the stack
     488However, these rules mirror what happens with termination.
     489
     490The try statements that are marked are the ones that would be removed from
     491the stack if this was a termination exception, that is those on the stack
    547492between the handler and the raise statement.
    548493This symmetry applies to the default handler as well, as both kinds of
    … …  
    578523        // Only handle IO failure for f3.
    579524}
    580 // Handle a failure relating to f2 further down the stack.
     525// Can't handle a failure relating to f2 here.
    581526\end{cfa}
    582527In this example the file that experienced the IO error is used to decide
    … …  
    609554
    610555\subsection{Comparison with Reraising}
    611 Without conditional catch, the only approach to match in more detail is to reraise
    612 the exception after it has been caught, if it could not be handled.
    613 \begin{center}
    614 \begin{tabular}{l|l}
     556A more popular way to allow handlers to match in more detail is to reraise
     557the exception after it has been caught, if it could not be handled here.
     558On the surface these two features seem interchangeable.
     559
     560If @throw;@ (no argument) starts a termination reraise,
     561which is the same as a raise but reuses the last caught exception,
     562then these two statements have the same behaviour:
    615563\begin{cfa}
    616564try {
    617         do_work_may_throw();
    618 } catch(excep_t * ex; can_handle(ex)) {
    619 
    620         handle(ex);
    621 
    622 
    623 
     565    do_work_may_throw();
     566} catch(exception_t * exc ; can_handle(exc)) {
     567    handle(exc);
    624568}
    625569\end{cfa}
    626 &
     570
    627571\begin{cfa}
    628572try {
    629         do_work_may_throw();
    630 } catch(excep_t * ex) {
    631         if (can_handle(ex)) {
    632                 handle(ex);
    633         } else {
    634                 throw;
    635         }
     573    do_work_may_throw();
     574} catch(exception_t * exc) {
     575    if (can_handle(exc)) {
     576        handle(exc);
     577    } else {
     578        throw;
     579    }
    636580}
    637581\end{cfa}
    638 \end{tabular}
    639 \end{center}
    640 Notice catch-and-reraise increases complexity by adding additional data and
    641 code to the exception process. Nevertheless, catch-and-reraise can simulate
    642 conditional catch straightforwardly, when exceptions are disjoint, \ie no
    643 inheritance.
    644 
    645 However, catch-and-reraise simulation becomes unusable for exception inheritance.
    646 \begin{flushleft}
    647 \begin{cfa}[xleftmargin=6pt]
    648 exception E1;
    649 exception E2(E1); // inheritance
    650 \end{cfa}
    651 \begin{tabular}{l|l}
    652 \begin{cfa}
    653 try {
    654         ... foo(); ... // raise E1/E2
    655         ... bar(); ... // raise E1/E2
    656 } catch( E2 e; e.rtn == foo ) {
    657         ...
    658 } catch( E1 e; e.rtn == foo ) {
    659         ...
    660 } catch( E1 e; e.rtn == bar ) {
    661         ...
    662 }
    663 
    664 \end{cfa}
    665 &
    666 \begin{cfa}
    667 try {
    668         ... foo(); ...
    669         ... bar(); ...
    670 } catch( E2 e ) {
    671         if ( e.rtn == foo ) { ...
    672         } else throw; // reraise
    673 } catch( E1 e ) {
    674         if (e.rtn == foo) { ...
    675         } else if (e.rtn == bar) { ...
    676         else throw; // reraise
    677 }
    678 \end{cfa}
    679 \end{tabular}
    680 \end{flushleft}
    681 The derived exception @E2@ must be ordered first in the catch list, otherwise
    682 the base exception @E1@ catches both exceptions. In the catch-and-reraise code
    683 (right), the @E2@ handler catches exceptions from both @foo@ and
    684 @bar@. However, the reraise misses the following catch clause. To fix this
    685 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
    686 reraise, and its handler must duplicate the inner handler code for @bar@. To
    687 generalize, this fix for any amount of inheritance and complexity of try
    688 statement requires a technique called \emph{try-block
    689 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
    690 sufficient to state that conditional catch is more expressive than
    691 catch-and-reraise in terms of complexity.
    692 
    693 \begin{comment}
    694 That is, they have the same behaviour in isolation.
     582That is, they will have the same behaviour in isolation.
    695583Two things can expose differences between these cases.
    696584
    697585One is the existence of multiple handlers on a single try statement.
    698 A reraise skips all later handlers for a try statement but a conditional
     586A reraise skips all later handlers on this try statement but a conditional
    699587catch does not.
    700 % Hence, if an earlier handler contains a reraise later handlers are
    701 % implicitly skipped, with a conditional catch they are not.
     588Hence, if an earlier handler contains a reraise later handlers are
     589implicitly skipped, with a conditional catch they are not.
    702590Still, they are equivalently powerful,
    703591both can be used two mimic the behaviour of the other,
    … …  
    750638%   `exception_ptr current_exception() noexcept;`
    751639% https://www.python.org/dev/peps/pep-0343/
    752 \end{comment}
    753640
    754641\section{Finally Clauses}
    … …  
    766653The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    767654stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    768 finishes, or during an unwind.
     655finishes or during an unwind.
    769656The only time the block is not executed is if the program is exited before
    770657the stack is unwound.
    … …  
    782669
    783670Not all languages with unwinding have finally clauses. Notably \Cpp does
    784 without it as destructors, and the RAII design pattern, serve a similar role.
    785 Although destructors and finally clauses can be used for the same cases,
     671without it as descructors, and the RAII design pattern, serve a similar role.
     672Although destructors and finally clauses can be used in the same cases,
    786673they have their own strengths, similar to top-level function and lambda
    787674functions with closures.
    788 Destructors take more work for their creation, but if there is clean-up code
    789 that needs to be run every time a type is used, they are much easier
     675Destructors take more work for their first use, but if there is clean-up code
     676that needs to be run every time a type is used they soon become much easier
    790677to set-up.
    791678On the other hand finally clauses capture the local context, so is easy to
    792679use when the clean-up is not dependent on the type of a variable or requires
    793680information from multiple variables.
     681% To Peter: I think these are the main points you were going for.
    794682
    795683\section{Cancellation}
    … …  
    804692raise, this exception is not used in matching only to pass information about
    805693the cause of the cancellation.
    806 Finaly, since a cancellation only unwinds and forwards, there is no default handler.
     694(This also means matching cannot fail so there is no default handler.)
    807695
    808696After @cancel_stack@ is called the exception is copied into the EHM's memory
    … …  
    815703After the main stack is unwound there is a program-level abort.
    816704
    817 The reasons for this semantics in a sequential program is that there is no more code to execute.
    818 This semantics also applies to concurrent programs, too, even if threads are running.
    819 That is, if any threads starts a cancellation, it implies all threads terminate.
    820 Keeping the same behaviour in sequential and concurrent programs is simple.
     705There are two reasons for these semantics.
     706The first is that it had to do this abort.
     707in a sequential program as there is nothing else to notify and the simplicity
     708of keeping the same behaviour in sequential and concurrent programs is good.
    821709Also, even in concurrent programs there may not currently be any other stacks
    822710and even if other stacks do exist, main has no way to know where they are.
    … …  
    863751caller's context and passes it to the internal report.
    864752
    865 A coroutine only knows of two other coroutines, its starter and its last resumer.
     753A coroutine knows of two other coroutines, its starter and its last resumer.
    866754The starter has a much more distant connection, while the last resumer just
    867755(in terms of coroutine state) called resume on this coroutine, so the message
    … …  
    871759cascade an error across any number of coroutines, cleaning up each in turn,
    872760until the error is handled or a thread stack is reached.
    873 
    874 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you
    875 talk about handling a cancellation in the last sentence. Which is correct?}

  • doc/theses/andrew_beach_MMath/intro.tex

    rc9f9d4f r3b8acfb  
    1111
    1212% Now take a step back and explain what exceptions are generally.
     13Exception handling provides dynamic inter-function control flow.
    1314A language's EHM is a combination of language syntax and run-time
    14 components that are used to construct, raise, and handle exceptions,
    15 including all control flow.
    16 Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
    17 Exception handling provides dynamic inter-function control flow.
     15components that construct, raise, propagate and handle exceptions,
     16to provide all of that control flow.
    1817There are two forms of exception handling covered in this thesis:
    1918termination, which acts as a multi-level return,
    2019and resumption, which is a dynamic function call.
    21 % PAB: Maybe this sentence was suppose to be deleted?
    22 Termination handling is much more common,
    23 to the extent that it is often seen as the only form of handling.
    24 % PAB: I like this sentence better than the next sentence.
    25 % This separation is uncommon because termination exception handling is so
    26 % much more common that it is often assumed.
    27 % WHY: Mention other forms of continuation and \cite{CommonLisp} here?
    28 
    29 Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
     20% About other works:
     21Often, when this separation is not made, termination exceptions are assumed
     22as they are more common and may be the only form of handling provided in
     23a language.
     24
     25All types of exception handling link a raise with a handler.
     26Both operations are usually language primitives, although raises can be
     27treated as a primitive function that takes an exception argument.
     28Handlers are more complex as they are added to and removed from the stack
     29during execution, must specify what they can handle and give the code to
     30handle the exception.
     31
     32Exceptions work with different execution models but for the descriptions
     33that follow a simple call stack, with functions added and removed in a
     34first-in-last-out order, is assumed.
     35
     36Termination exception handling searches the stack for the handler, then
     37unwinds the stack to where the handler was found before calling it.
     38The handler is run inside the function that defined it and when it finishes
     39it returns control to that function.
    3040\begin{center}
    31 \begin{tabular}[t]{ll}
    32 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    33 void f( void (*hp)() ) {
    34         hp();
    35 }
    36 void g( void (*hp)() ) {
    37         f( hp );
    38 }
    39 void h( int @i@, void (*hp)() ) {
    40         void @handler@() { // nested
    41                 printf( "%d\n", @i@ );
    42         }
    43         if ( i == 1 ) hp = handler;
    44         if ( i > 0 ) h( i - 1, hp );
    45         else g( hp );
    46 }
    47 h( 2, 0 );
    48 \end{lstlisting}
    49 &
    50 \raisebox{-0.5\totalheight}{\input{handler}}
    51 \end{tabular}
     41\input{callreturn}
    5242\end{center}
    53 The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
    54 When this handler is called in @f@, it uses the parameter @i@ in the second stack frame, which is accessible by an implicit lexical-link pointer.
    55 Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
    56 Exception handling extends this idea by eliminating explicit handler passing, and instead, performing a stack search for a handler that matches some criteria (conditional dynamic call), and calls the handler at the top of the stack.
    57 It is the runtime search $O(N)$ that differentiates an EHM call (raise) from normal dynamic call $O(1)$ via a function or virtual-member pointer.
    58 
    59 Termination exception handling searches the stack for a handler, unwinds the stack to the frame containing the matching handler, and calling the handler at the top of the stack.
    60 \begin{center}
    61 \input{termination}
    62 \end{center}
    63 Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
    64 After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
    65 Unwinding allows recover to any previous
    66 function on the stack, skipping any functions between it and the
    67 function containing the matching handler.
    68 
    69 Resumption exception handling searches the stack for a handler, does \emph{not} unwind the stack to the frame containing the matching handler, and calls the handler at the top of the stack.
     43
     44Resumption exception handling searches the stack for a handler and then calls
     45it without removing any other stack frames.
     46The handler is run on top of the existing stack, often as a new function or
     47closure capturing the context in which the handler was defined.
     48After the handler has finished running it returns control to the function
     49that preformed the raise, usually starting after the raise.
    7050\begin{center}
    7151\input{resumption}
    7252\end{center}
    73 After the handler returns, control continues after the resume in @f@ (dynamic return).
    74 Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.
    7553
    7654Although a powerful feature, exception handling tends to be complex to set up
    7755and expensive to use
    7856so it is often limited to unusual or ``exceptional" cases.
    79 The classic example is error handling, where exceptions are used to
    80 remove error handling logic from the main execution path, while paying
     57The classic example is error handling, exceptions can be used to
     58remove error handling logic from the main execution path, and pay
    8159most of the cost only when the error actually occurs.
    8260
    … …  
    8866some of the underlying tools used to implement and express exception handling
    8967in other languages are absent in \CFA.
    90 Still the resulting basic syntax resembles that of other languages:
    91 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    92 @try@ {
     68Still the resulting syntax resembles that of other languages:
     69\begin{cfa}
     70try {
    9371        ...
    9472        T * object = malloc(request_size);
    9573        if (!object) {
    96                 @throw@ OutOfMemory{fixed_allocation, request_size};
     74                throw OutOfMemory{fixed_allocation, request_size};
    9775        }
    9876        ...
    99 } @catch@ (OutOfMemory * error) {
     77} catch (OutOfMemory * error) {
    10078        ...
    10179}
    102 \end{lstlisting}
     80\end{cfa}
    10381% A note that yes, that was a very fast overview.
    10482The design and implementation of all of \CFA's EHM's features are
    … …  
    10785
    10886% The current state of the project and what it contributes.
    109 The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code.
    110 In addition,
    111 a suite of tests and performance benchmarks were created as part of this project.
    112 The \CFA implementation techniques are generally applicable in other programming
     87All of these features have been implemented in \CFA,
     88covering both changes to the compiler and the run-time.
     89In addition, a suite of test cases and performance benchmarks were created
     90along side the implementation.
     91The implementation techniques are generally applicable in other programming
    11392languages and much of the design is as well.
    114 Some parts of the EHM use features unique to \CFA, and hence,
    115 are harder to replicate in other programming languages.
    116 % Talk about other programming languages.
    117 Three well known programming languages with EHMs, %/exception handling
    118 C++, Java and Python are examined in the performance work. However, these languages focus on termination
    119 exceptions, so there is no comparison with resumption.
     93Some parts of the EHM use other features unique to \CFA and would be
     94harder to replicate in other programming languages.
    12095
    12196The contributions of this work are:
    12297\begin{enumerate}
    12398\item Designing \CFA's exception handling mechanism, adapting designs from
    124 other programming languages, and creating new features.
    125 \item Implementing stack unwinding for the \CFA EHM, including updating
    126 the \CFA compiler and run-time environment to generate and execute the EHM code.
    127 \item Designing and implementing a prototype virtual system.
     99other programming languages and creating new features.
     100\item Implementing stack unwinding and the \CFA EHM, including updating
     101the \CFA compiler and the run-time environment.
     102\item Designed and implemented a prototype virtual system.
    128103% I think the virtual system and per-call site default handlers are the only
    129104% "new" features, everything else is a matter of implementation.
    130 \item Creating tests and performance benchmarks to compare with EHM's in other languages.
     105\item Creating tests to check the behaviour of the EHM.
     106\item Creating benchmarks to check the performances of the EHM,
     107as compared to other languages.
    131108\end{enumerate}
    132109
    133 %\todo{I can't figure out a good lead-in to the roadmap.}
    134 The thesis is organization as follows.
    135 The next section and parts of \autoref{c:existing} cover existing EHMs.
    136 New \CFA EHM features are introduced in \autoref{c:features},
     110The rest of this thesis is organized as follows.
     111The current state of exceptions is covered in \autoref{s:background}.
     112The existing state of \CFA is also covered in \autoref{c:existing}.
     113New EHM features are introduced in \autoref{c:features},
    137114covering their usage and design.
    138115That is followed by the implementation of these features in
    139116\autoref{c:implement}.
    140 Performance results are presented in \autoref{c:performance}.
    141 Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
     117Performance results are examined in \autoref{c:performance}.
     118Possibilities to extend this project are discussed in \autoref{c:future}.
     119Finally, the project is summarized in \autoref{c:conclusion}.
    142120
    143121\section{Background}
    144122\label{s:background}
    145123
    146 Exception handling is a well examined area in programming languages,
    147 with papers on the subject dating back the 70s~\cite{Goodenough75}.
     124Exception handling has been examined before in programming languages,
     125with papers on the subject dating back 70s.\cite{Goodenough75}
    148126Early exceptions were often treated as signals, which carried no information
    149 except their identity. Ada~\cite{Ada} still uses this system.
     127except their identity. Ada still uses this system.\todo{cite Ada}
    150128
    151129The modern flag-ship for termination exceptions is \Cpp,
    152130which added them in its first major wave of non-object-orientated features
    153131in 1990.
    154 % https://en.cppreference.com/w/cpp/language/history
    155 While many EHMs have special exception types,
    156 \Cpp has the ability to use any type as an exception.
    157 However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from
     132\todo{cite https://en.cppreference.com/w/cpp/language/history}
     133Many EHMs have special exception types,
     134however \Cpp has the ability to use any type as an exception.
     135These were found to be not very useful and have been pushed aside for classes
     136inheriting from
    158137\code{C++}{std::exception}.
    159 While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can
    160 be done with the caught value because nothing is known about it.
    161 Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as
    162 the ability to print a message when the exception is raised but not caught) and all
     138Although there is a special catch-all syntax (@catch(...)@) there are no
     139operations that can be performed on the caught value, not even type inspection.
     140Instead the base exception-type \code{C++}{std::exception} defines common
     141functionality (such as
     142the ability to describe the reason the exception was raised) and all
    163143exceptions have this functionality.
    164 Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth
    165 any lost in flexibility from limiting exceptions types to classes.
    166 
    167 Java~\cite{Java} was the next popular language to use exceptions.
    168 Its exception system largely reflects that of \Cpp, except it requires
    169 exceptions to be a subtype of \code{Java}{java.lang.Throwable}
     144That trade-off, restricting usable types to gain guaranteed functionality,
     145is almost universal now, as without some common functionality it is almost
     146impossible to actually handle any errors.
     147
     148Java was the next popular language to use exceptions. \todo{cite Java}
     149Its exception system largely reflects that of \Cpp, except that requires
     150you throw a child type of \code{Java}{java.lang.Throwable}
    170151and it uses checked exceptions.
    171 Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise.
    172 Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions.
    173 Making exception information explicit, improves clarity and
    174 safety, but can slow down programming.
    175 For example, programming complexity increases when dealing with high-order methods or an overly specified
    176 throws clause. However some of the issues are more
    177 programming annoyances, such as writing/updating many exception signatures after adding or remove calls.
    178 Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide.
    179 For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus
    180 repairing or recovering from the exception.
     152Checked exceptions are part of a function's interface,
     153the exception signature of the function.
     154Every function that could be raised from a function, either directly or
     155because it is not handled from a called function, is given.
     156Using this information, it is possible to statically verify if any given
     157exception is handled and guarantee that no exception will go unhandled.
     158Making exception information explicit improves clarity and safety,
     159but can slow down or restrict programming.
     160For example, programming high-order functions becomes much more complex
     161if the argument functions could raise exceptions.
     162However, as odd it may seem, the worst problems are rooted in the simple
     163inconvenience of writing and updating exception signatures.
     164This has caused Java programmers to develop multiple programming ``hacks''
     165to circumvent checked exceptions, negating their advantages.
     166One particularly problematic example is the ``catch-and-ignore'' pattern,
     167where an empty handler is used to handle an exception without doing any
     168recovery or repair. In theory that could be good enough to properly handle
     169the exception, but more often is used to ignore an exception that the       
     170programmer does not feel is worth the effort of handling it, for instance if
     171they do not believe it will ever be raised.
     172If they are incorrect the exception will be silenced, while in a similar
     173situation with unchecked exceptions the exception would at least activate   
     174the language's unhandled exception code (usually program abort with an 
     175error message).
    181176
    182177%\subsection
    183178Resumption exceptions are less popular,
    184 although resumption is as old as termination;
    185 hence, few
     179although resumption is as old as termination; hence, few
    186180programming languages have implemented them.
    187181% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    188182%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
    189 Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
    190 is quoted as being one of the reasons resumptions are not
     183Mesa is one programming language that did.\todo{cite Mesa} Experience with Mesa
     184is quoted as being one of the reasons resumptions were not
    191185included in the \Cpp standard.
    192186% https://en.wikipedia.org/wiki/Exception_handling
    193 As a result, resumption has ignored in main-stream programming languages.
    194 However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading).
    195 While rejecting resumption might have been the right decision in the past, there are decades
    196 of developments in computer science that have changed the situation.
    197 Some of these developments, such as functional programming's resumption
    198 equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success.
    199 A complete reexamination of resumptions is beyond this thesis, but their re-emergence is
    200 enough to try them in \CFA.
     187Since then resumptions have been ignored in main-stream programming languages.
     188However, resumption is being revisited in the context of decades of other
     189developments in programming languages.
     190While rejecting resumption may have been the right decision in the past,
     191the situation has changed since then.
     192Some developments, such as the function programming equivalent to resumptions,
     193algebraic effects\cite{Zhang19}, are enjoying success.
     194A complete reexamination of resumptions is beyond this thesis,
     195but there reemergence is enough to try them in \CFA.
    201196% Especially considering how much easier they are to implement than
    202 % termination exceptions.
    203 
    204 %\subsection
    205 Functional languages tend to use other solutions for their primary EHM,
    206 but exception-like constructs still appear.
    207 Termination appears in error construct, which marks the result of an
    208 expression as an error; thereafter, the result of any expression that tries to use it is also an
    209 error, and so on until an appropriate handler is reached.
     197% termination exceptions and how much Peter likes them.
     198
     199%\subsection
     200Functional languages tend to use other solutions for their primary error
     201handling mechanism, but exception-like constructs still appear.
     202Termination appears in the error construct, which marks the result of an
     203expression as an error; then the result of any expression that tries to use
     204it also results in an error, and so on until an appropriate handler is reached.
    210205Resumption appears in algebraic effects, where a function dispatches its
    211206side-effects to its caller for handling.
    212207
    213208%\subsection
    214 Some programming languages have moved to a restricted kind of EHM
    215 called ``panic".
    216 In Rust~\cite{Rust}, a panic is just a program level abort that may be implemented by
    217 unwinding the stack like in termination exception handling.
     209More recently exceptions seem to be vanishing from newer programming
     210languages, replaced by ``panic".
     211In Rust, a panic is just a program level abort that may be implemented by
     212unwinding the stack like in termination exception handling.\todo{cite Rust}
    218213% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
    219 In Go~\cite{Go}, a panic is very similar to a termination, except it only supports
     214Go's panic through is very similar to a termination, except it only supports
    220215a catch-all by calling \code{Go}{recover()}, simplifying the interface at
    221 the cost of flexibility.
     216the cost of flexibility.\todo{cite Go}
    222217
    223218%\subsection
    224219While exception handling's most common use cases are in error handling,
    225 here are other ways to handle errors with comparisons to exceptions.
     220here are some other ways to handle errors with comparisons with exceptions.
    226221\begin{itemize}
    227222\item\emph{Error Codes}:
    228 This pattern has a function return an enumeration (or just a set of fixed values) to indicate
    229 if an error occurred and possibly which error it was.
    230 
    231 Error codes mix exceptional and normal values, artificially enlarging the type and/or value range.
    232 Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result.
    233 However, the main issue with error codes is forgetting to checking them,
     223This pattern has a function return an enumeration (or just a set of fixed
     224values) to indicate if an error has occurred and possibly which error it was.
     225
     226Error codes mix exceptional/error and normal values, enlarging the range of
     227possible return values. This can be addressed with multiple return values
     228(or a tuple) or a tagged union.
     229However, the main issue with error codes is forgetting to check them,
    234230which leads to an error being quietly and implicitly ignored.
    235 Some new languages have tools that issue warnings, if the error code is
    236 discarded to avoid this problem.
    237 Checking error codes also results in bloating the main execution path, especially if an error is not dealt with locally and has to be cascaded down the call stack to a higher-level function..
     231Some new languages and tools will try to issue warnings when an error code
     232is discarded to avoid this problem.
     233Checking error codes also bloats the main execution path,
     234especially if the error is not handled immediately hand has to be passed
     235through multiple functions before it is addressed.
    238236
    239237\item\emph{Special Return with Global Store}:
    240 Some functions only return a boolean indicating success or failure
    241 and store the exact reason for the error in a fixed global location.
    242 For example, many C routines return non-zero or -1, indicating success or failure,
    243 and write error details into the C standard variable @errno@.
    244 
    245 This approach avoids the multiple results issue encountered with straight error codes
    246 but otherwise has many (if not more) of the disadvantages.
    247 For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency.
     238Similar to the error codes pattern but the function itself only returns
     239that there was an error
     240and store the reason for the error in a fixed global location.
     241For example many routines in the C standard library will only return some
     242error value (such as -1 or a null pointer) and the error code is written into
     243the standard variable @errno@.
     244
     245This approach avoids the multiple results issue encountered with straight
     246error codes but otherwise has the same disadvantages and more.
     247Every function that reads or writes to the global store must agree on all
     248possible errors and managing it becomes more complex with concurrency.
    248249
    249250\item\emph{Return Union}:
    … …  
    254255so that one type can be used everywhere in error handling code.
    255256
    256 This pattern is very popular in functional or any semi-functional language with
    257 primitive support for tagged unions (or algebraic data types).
    258 % We need listing Rust/rust to format code snipits from it.
     257This pattern is very popular in any functional or semi-functional language
     258with primitive support for tagged unions (or algebraic data types).
     259% We need listing Rust/rust to format code snippets from it.
    259260% Rust's \code{rust}{Result<T, E>}
    260 The main advantage is providing for more information about an
    261 error, other than one of a fix-set of ids.
    262 While some languages use checked union access to force error-code checking,
    263 it is still possible to bypass the checking.
    264 The main disadvantage is again significant error code on the main execution path and cascading through called functions.
     261The main advantage is that an arbitrary object can be used to represent an
     262error so it can include a lot more information than a simple error code.
     263The disadvantages include that the it does have to be checked along the main
     264execution and if there aren't primitive tagged unions proper usage can be
     265hard to enforce.
    265266
    266267\item\emph{Handler Functions}:
    267 This pattern implicitly associates functions with errors.
    268 On error, the function that produced the error implicitly calls another function to
     268This pattern associates errors with functions.
     269On error, the function that produced the error calls another function to
    269270handle it.
    270271The handler function can be provided locally (passed in as an argument,
    271272either directly as as a field of a structure/object) or globally (a global
    272273variable).
    273 C++ uses this approach as its fallback system if exception handling fails, \eg
    274 \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
    275 
    276 Handler functions work a lot like resumption exceptions, without the dynamic handler search.
    277 Therefore, setting setting up the handler can be more complex/expensive, especially if the handle must be passed through multiple function calls, but cheaper to call $O(1)$, and hence,
    278 are more suited to frequent exceptional situations.
    279 % The exception being global handlers if they are rarely change as the time
    280 % in both cases shrinks towards zero.
     274C++ uses this approach as its fallback system if exception handling fails,
     275such as \snake{std::terminate_handler} and, for a time,
     276\snake{std::unexpected_handler}.
     277
     278Handler functions work a lot like resumption exceptions,
     279but without the dynamic search for a handler.
     280Since setting up the handler can be more complex/expensive,
     281especially when the handler has to be passed through multiple layers of
     282function calls, but cheaper (constant time) to call,
     283they are more suited to more frequent (less exceptional) situations.
    281284\end{itemize}
    282285
    283286%\subsection
    284287Because of their cost, exceptions are rarely used for hot paths of execution.
    285 Therefore, there is an element of self-fulfilling prophecy for implementation
    286 techniques to make exceptions cheap to set-up at the cost
    287 of expensive usage.
    288 This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common.
    289 An iconic example is Python's @StopIteration@ exception that is thrown by
    290 an iterator to indicate that it is exhausted, especially when combined with Python's heavy
    291 use of the iterator-based for-loop.
     288Hence, there is an element of self-fulfilling prophecy as implementation
     289techniques have been focused on making them cheap to set-up,
     290happily making them expensive to use in exchange.
     291This difference is less important in higher-level scripting languages,
     292where using exception for other tasks is more common.
     293An iconic example is Python's \code{Python}{StopIteration} exception that
     294is thrown by an iterator to indicate that it is exhausted.
     295When paired with Python's iterator-based for-loop this will be thrown every
     296time the end of the loop is reached.
     297\todo{Cite Python StopIteration and for-each loop.}
    292298% https://docs.python.org/3/library/exceptions.html#StopIteration

  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rc9f9d4f r3b8acfb  
    210210\lstMakeShortInline@
    211211\lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt}
    212 % PAB causes problems with inline @=
    213 %\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
    214212% Annotations from Peter:
    215213\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
Note: See TracChangeset for help on using the changeset viewer.