Changeset f42a6b8 for doc/theses


Ignore:
Timestamp:
Aug 9, 2021, 4:35:49 PM (4 years ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum
Children:
cb6b8cb
Parents:
5438e41
Message:

Copied out and reverted changes to thesis.

Location:
doc/theses/andrew_beach_MMath
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/existing.tex

    r5438e41 rf42a6b8  
    1010
    1111Only those \CFA features pertaining to this thesis are discussed.
    12 % Also, only new features of \CFA will be discussed,
    13 A familiarity with
     12Also, only new features of \CFA will be discussed, a familiarity with
    1413C or C-like languages is assumed.
    1514
    … …  
    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 you would use pointers but would
     81be dereferencing them (almost) every usage.
    8382Mutable references may be assigned to by converting them to a pointer
    8483with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
    … …  
    8685\section{Operators}
    8786
    88 \CFA implements operator overloading by providing special names, where
    89 operator usages are translated into function calls using these names.
    90 An operator name is created by taking the operator symbols and joining them with
     87\CFA implements operator overloading by providing special names.
     88Operator uses are translated into function calls using these names.
     89These names are created by taking the operator symbols and joining them with
    9190@?@s to show where the arguments go.
    9291For example,
    93 infixed multiplication is @?*?@, while prefix dereference is @*?@.
     92infixed multiplication is @?*?@ while prefix dereference is @*?@.
    9493This syntax make it easy to tell the difference between prefix operations
    9594(such as @++?@) and post-fix operations (@?++@).
    96 For example, plus and equality operators are defined for a point type.
     95
    9796\begin{cfa}
    9897point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
    99 int ?==?(point a, point b) { return a.x == b.x && a.y == b.y; }
     98bool ?==?(point a, point b) { return a.x == b.x && a.y == b.y; }
    10099{
    101100        assert(point{1, 2} + point{3, 4} == point{4, 6});
    102101}
    103102\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.
     103Note that these special names are not limited to just being used for these
     104operator functions, and may be used name other declarations.
     105Some ``near misses", that will not match an operator form but looks like
     106it may have been supposed to, will generate wantings but otherwise they are
     107left alone.
     108
     109%\subsection{Constructors and Destructors}
     110
     111Both constructors and destructors are operators, which means they are
     112functions with special operator names rather than type names in \Cpp. The
     113special operator names may be used to call the functions explicitly.
     114% Placement new means that this is actually equivant to C++.
     115
     116The special name for a constructor is @?{}@, which comes from the
     117initialization syntax in C, \eg @Example e = { ... }@.
     118\CFA will generate a constructor call each time a variable is declared,
     119passing the initialization arguments to the constructort.
     120\begin{cfa}
     121struct Example { ... };
     122void ?{}(Example & this) { ... }
     123{
     124        Example a;
     125        Example b = {};
     126}
     127void ?{}(Example & this, char first, int num) { ... }
     128{
     129        Example c = {'a', 2};
     130}
     131\end{cfa}
     132Both @a@ and @b@ will be initalized with the first constructor,
     133while @c@ will be initalized with the second.
     134Currently, there is no general way to skip initialation.
     135
     136% I don't like the \^{} symbol but $^\wedge$ isn't better.
     137Similarly destructors use the special name @^?{}@ (the @^@ has no special
     138meaning).
     139These are a normally called implicitly called on a variable when it goes out
     140of scope. They can be called explicitly as well.
     141\begin{cfa}
     142void ^?{}(Example & this) { ... }
     143{
     144        Example d;
     145} // <- implicit destructor call
     146\end{cfa}
     147
     148Whenever a type is defined, \CFA will create a default zero-argument
     149constructor, a copy constructor, a series of argument-per-field constructors
     150and a destructor. All user constructors are defined after this.
    112151Because operators are never part of the type definition they may be added
    113152at any time, including on built-in types.
    114 
    115 %\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++.
    123 
    124 The special name for a constructor is @?{}@, which comes from the
    125 initialization syntax in C, \eg @Example e = { ... }@.
    126 \CFA generates a constructor call each time a variable is declared,
    127 passing the initialization arguments to the constructor.
    128 \begin{cfa}
    129 struct Example { ... };
    130 void ?{}(Example & this) { ... }
    131 void ?{}(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}
    142 % I don't like the \^{} symbol but $^\wedge$ isn't better.
    143 Similarly, destructors use the special name @^?{}@ (the @^@ has no special
    144 meaning).
    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.
    147 \begin{cfa}
    148 void ^?{}(Example & this) { ... }
    149 {
    150         Example e;      // implicit constructor call
    151         ^?{}(e);                // explicit destructor call
    152         ?{}(e);         // explicit constructor call
    153 } // implicit destructor call
    154 \end{cfa}
    155 
    156 Whenever a type is defined, \CFA creates a default zero-argument
    157 constructor, a copy constructor, a series of argument-per-field constructors
    158 and a destructor. All user constructors are defined after this.
    159153
    160154\section{Polymorphism}
    … …  
    208202Note, a function named @do_once@ is not required in the scope of @do_twice@ to
    209203compile it, unlike \Cpp template expansion. Furthermore, call-site inferencing
    210 allows local replacement of the specific parametric functions needs for a
     204allows local replacement of the most specific parametric functions needs for a
    211205call.
    212206\begin{cfa}
    … …  
    224218to @do_twice@ and called within it.
    225219The global definition of @do_once@ is ignored, however if quadruple took a
    226 @double@ argument, then the global definition would be used instead as it
    227 is a better match.
     220@double@ argument then the global definition would be used instead as it
     221would be a better match.
    228222% Aaron's thesis might be a good reference here.
    229223
    230224To 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
     225convenient packages called a @trait@, which can then be used in an assertion
    232226instead of the individual constraints.
    233227\begin{cfa}
    … …  
    245239functionality, like @sumable@, @listable@, \etc.
    246240
    247 Polymorphic structures and unions are defined by qualifying an aggregate type
     241Polymorphic structures and unions are defined by qualifying the aggregate type
    248242with @forall@. The type variables work the same except they are used in field
    249243declarations instead of parameters, returns, and local variable declarations.
    … …  
    291285coroutine CountUp {
    292286        unsigned int next;
    293 };
     287}
    294288CountUp countup;
    295 for (10) sout | resume(countup).next; // print 10 values
    296289\end{cfa}
    297290Each coroutine has a @main@ function, which takes a reference to a coroutine
    298291object and returns @void@.
    299292%[numbers=left] Why numbers on this one?
    300 \begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
     293\begin{cfa}
    301294void main(CountUp & this) {
    302         for (unsigned int up = 0;; ++up) {
    303                 this.next = up;
     295        for (unsigned int next = 0 ; true ; ++next) {
     296                next = up;
    304297                suspend;$\label{suspend}$
    305298        }
    … …  
    307300\end{cfa}
    308301In 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).
     302@suspend@ statement is used to return execution to the coroutine's caller
     303without terminating the coroutine's function.
    311304
    312305A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    … …  
    330323exclusion on a monitor object by qualifying an object reference parameter with
    331324@mutex@.
    332 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
    334 \end{lstlisting}
     325\begin{cfa}
     326void example(MonitorA & mutex argA, MonitorB & mutex argB);
     327\end{cfa}
    335328When the function is called, it implicitly acquires the monitor lock for all of
    336329the mutex parameters without deadlock.  This semantics means all functions with
    … …  
    362355{
    363356        StringWorker stringworker; // fork thread running in "main"
    364 } // implicitly join with thread / wait for completion
     357} // <- implicitly join with thread / wait for completion
    365358\end{cfa}
    366359The thread main is where a new thread starts execution after a fork operation

  • doc/theses/andrew_beach_MMath/features.tex

    r5438e41 rf42a6b8  
    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}
    132126Virtual types and casts are not part of \CFA's EHM nor are they required for
    133 an EHM.
    134 However, one of the best ways to support an exception hierarchy
     127any EHM.
     128However, it is one of the best ways to support an exception hierarchy
    135129is via a virtual hierarchy and dispatch system.
    136130
    137 Ideally, the virtual system should have been part of \CFA before the work
     131Ideally, the virtual system would have been part of \CFA before the work
    138132on exception handling began, but unfortunately it was not.
    139133Hence, only the features and framework needed for the EHM were
    140 designed and implemented for this thesis. Other features were considered to ensure that
     134designed and implemented. Other features were considered to ensure that
    141135the 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.
     136but they were not implemented.
     137The rest of this section will only discuss the implemented subset of the
     138virtual system design.
    145139
    146140The virtual system supports multiple ``trees" of types. Each tree is
    … …  
    158152It is important to note that these are virtual members, not virtual methods
    159153of object-orientated programming, and can be of any type.
    160 
    161 \PAB{Need to look at these when done.
    162154
    163155\CFA still supports virtual methods as a special case of virtual members.
    … …  
    173165as a hidden field.
    174166\todo{Might need a diagram for virtual structure.}
    175 }%
    176167
    177168Up until this point the virtual system is similar to ones found in
    178 object-orientated languages but this is where \CFA diverges. Objects encapsulate a
    179 single set of methods in each type, universally across the entire program,
    180 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
    181 single set of methods. In this sense,
    182 object-oriented types are ``closed" and cannot be altered.
    183 
    184 In \CFA, types do not encapsulate any code. Traits are local for each function and
    185 types can satisfy a local trait, stop satisfying it or, satisfy the same
    186 trait in a different way at any lexical location in the program where a function is call.
    187 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.
     169object-orientated languages but this where \CFA diverges. Objects encapsulate a
     170single set of behaviours in each type, universally across the entire program,
     171and indeed all programs that use that type definition. In this sense, the
     172types are ``closed" and cannot be altered.
     173
     174In \CFA, types do not encapsulate any behaviour. Traits are local and
     175types can begin to satisfy a trait, stop satisfying a trait or satisfy the same
     176trait in a different way at any lexical location in the program.
     177In this sense, they are ``open" as they can change at any time.
    188178This capability means it is impossible to pick a single set of functions
    189 that represent a type's implementation across a program.
     179that represent the type's implementation across the program.
    190180
    191181\CFA side-steps this issue by not having a single virtual table for each
    192182type. A user can define virtual tables that are filled in at their
    193183declaration and given a name. Anywhere that name is visible, even if it is
    194 defined locally inside a function \PAB{What does this mean? (although that means it does not have a
    195 static lifetime)}, it can be used.
     184defined locally inside a function (although that means it does not have a
     185static lifetime), it can be used.
    196186Specifically, a virtual type is ``bound" to a virtual table that
    197187sets the virtual members for that object. The virtual members can be accessed
    … …  
    231221completing the virtual system). The imaginary assertions would probably come
    232222from a trait defined by the virtual system, and state that the exception type
    233 is a virtual type, is a descendant of @exception_t@ (the base exception type),
     223is a virtual type, is a descendant of @exception_t@ (the base exception type)
    234224and note its virtual table type.
    235225
    … …  
    251241\end{cfa}
    252242Both traits ensure a pair of types are an exception type, its virtual table
    253 type,
     243type
    254244and defines one of the two default handlers. The default handlers are used
    255245as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
    … …  
    260250facing way. So these three macros are provided to wrap these traits to
    261251simplify referring to the names:
    262 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
     252@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    263253
    264254All three take one or two arguments. The first argument is the name of the
    … …  
    282272\CFA provides two kinds of exception handling: termination and resumption.
    283273These twin operations are the core of \CFA's exception handling mechanism.
    284 This section covers the general patterns shared by the two operations and
    285 then goes on to cover the details of each individual operation.
     274This section will cover the general patterns shared by the two operations and
     275then go on to cover the details each individual operation.
    286276
    287277Both operations follow the same set of steps.
    288 First, a user raises an exception.
    289 Second, the exception propagates up the stack.
    290 Third, if a handler is found, the exception is caught and the handler is run.
     278Both start with the user preforming a raise on an exception.
     279Then the exception propagates up the stack.
     280If a handler is found the exception is caught and the handler is run.
    291281After that control continues at a raise-dependent location.
    292 Fourth, if a handler is not found, a default handler is run and, if it returns, then control
     282If the search fails a default handler is run and, if it returns, then control
    293283continues after the raise.
    294284
    295 %This general description covers what the two kinds have in common.
    296 The differences in the two operations include how propagation is performed, where execution continues
    297 after an exception is caught and handled, and which default handler is run.
     285This general description covers what the two kinds have in common.
     286Differences include how propagation is preformed, where exception continues
     287after an exception is caught and handled and which default handler is run.
    298288
    299289\subsection{Termination}
    300290\label{s:Termination}
    301 Termination handling is the familiar EHM and used in most programming
     291Termination handling is the familiar kind and used in most programming
    302292languages with exception handling.
    303293It is a dynamic, non-local goto. If the raised exception is matched and
    … …  
    318308@is_termination_exception@ at the call site.
    319309Through \CFA's trait system, the trait functions are implicitly passed into the
    320 throw code for use by the EHM.
     310throw code and the EHM.
    321311A new @defaultTerminationHandler@ can be defined in any scope to
    322 change the throw's behaviour when a handler is not found (see below).
     312change the throw's behaviour (see below).
    323313
    324314The throw copies the provided exception into managed memory to ensure
    … …  
    330320% How to say propagation starts, its first sub-step is the search.
    331321Then propagation starts with the search. \CFA uses a ``first match" rule so
    332 matching is performed with the copied exception as the search key.
    333 It starts from the raise in the throwing function and proceeds towards the base of the stack,
     322matching is preformed with the copied exception as the search continues.
     323It starts from the throwing function and proceeds towards base of the stack,
    334324from callee to caller.
    335 At each stack frame, a check is made for termination handlers defined by the
     325At each stack frame, a check is made for resumption handlers defined by the
    336326@catch@ clauses of a @try@ statement.
    337327\begin{cfa}
    … …  
    345335\end{cfa}
    346336When viewed on its own, a try statement simply executes the statements
    347 in the \snake{GUARDED_BLOCK}, and when those are finished,
     337in \snake{GUARDED_BLOCK} and when those are finished,
    348338the try statement finishes.
    349339
    … …  
    351341invoked functions, all the handlers in these statements are included in the
    352342search path.
    353 Hence, if a termination exception is raised, these handlers may be matched
     343Hence, if a termination exception is raised these handlers may be matched
    354344against the exception and may handle it.
    355345
    356346Exception matching checks the handler in each catch clause in the order
    357347they appear, top to bottom. If the representation of the raised exception type
    358 is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
     348is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
    359349(if provided) is
    360350bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    … …  
    362352freed and control continues after the try statement.
    363353
    364 If no termination handler is found during the search, then the default handler
    365 (\defaultTerminationHandler) visible at the raise statement is called.
    366 Through \CFA's trait system the best match at the raise statement is used.
     354If no termination handler is found during the search then the default handler
     355(\defaultTerminationHandler) visible at the raise statement is run.
     356Through \CFA's trait system the best match at the raise statement will be used.
    367357This function is run and is passed the copied exception.
    368 If the default handler finishes, control continues after the raise statement.
     358If the default handler is run control continues after the raise statement.
    369359
    370360There is a global @defaultTerminationHandler@ that is polymorphic over all
    371361termination exception types.
     362Since it is so general a more specific handler can be
     363defined and is used for those types, effectively overriding the handler
     364for a particular exception type.
    372365The global default termination handler performs a cancellation
    373 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
    374 Since it is so general, a more specific handler is usually
    375 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
     366(see \vref{s:Cancellation}) on the current stack with the copied exception.
    376367
    377368\subsection{Resumption}
    378369\label{s:Resumption}
    379370
    380 Resumption exception handling is the less familar EHM, but is
     371Resumption exception handling is less common than termination but is
    381372just as old~\cite{Goodenough75} and is simpler in many ways.
    382373It is a dynamic, non-local function call. If the raised exception is
    383 matched, a closure is taken from up the stack and executed,
     374matched a closure is taken from up the stack and executed,
    384375after which the raising function continues executing.
    385376The common uses for resumption exceptions include
    … …  
    387378function once the error is corrected, and
    388379ignorable events, such as logging where nothing needs to happen and control
    389 should always continue from the raise point.
     380should always continue from the same place.
    390381
    391382A resumption raise is started with the @throwResume@ statement:
    … …  
    401392the exception system while handling the exception.
    402393
    403 At run-time, no exception copy is made, since
    404 resumption does not unwind the stack nor otherwise remove values from the
    405 current scope, so there is no need to manage memory to keep the exception in scope.
    406 
    407 Then propagation starts with the search. It starts from the raise in the
     394At run-time, no exception copy is made.
     395Resumption does not unwind the stack nor otherwise remove values from the
     396current scope, so there is no need to manage memory to keep things in scope.
     397
     398The EHM then begins propagation. The search starts from the raise in the
    408399resuming function and proceeds towards the base of the stack,
    409400from callee to caller.
    … …  
    419410}
    420411\end{cfa}
    421 % PAB, you say this above.
    422 % When a try statement is executed, it simply executes the statements in the
    423 % @GUARDED_BLOCK@ and then finishes.
    424 %
    425 % However, while the guarded statements are being executed, including any
    426 % invoked functions, all the handlers in these statements are included in the
    427 % search path.
    428 % Hence, if a resumption exception is raised, these handlers may be matched
    429 % against the exception and may handle it.
    430 %
    431 % Exception matching checks the handler in each catch clause in the order
    432 % they appear, top to bottom. If the representation of the raised exception type
    433 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
    434 % (if provided) is bound to a pointer to the exception and the statements in
    435 % @HANDLER_BLOCK@$_i$ are executed.
    436 % If control reaches the end of the handler, execution continues after the
    437 % the raise statement that raised the handled exception.
    438 %
    439 % Like termination, if no resumption handler is found during the search,
    440 % then the default handler (\defaultResumptionHandler) visible at the raise
    441 % statement is called. It will use the best match at the raise sight according
    442 % to \CFA's overloading rules. The default handler is
    443 % passed the exception given to the raise. When the default handler finishes
    444 % execution continues after the raise statement.
    445 %
    446 % There is a global @defaultResumptionHandler{} is polymorphic over all
    447 % resumption exceptions and performs a termination throw on the exception.
    448 % The \defaultTerminationHandler{} can be overridden by providing a new
    449 % function that is a better match.
    450 
    451 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
    452 for resumption as for termination, as does exception matching at each
    453 @catchResume@. Similarly, if no resumption handler is found during the search,
    454 then the currently visible default handler (\defaultResumptionHandler) is
    455 called and control continues after the raise statement if it returns. Finally,
    456 there is also a global @defaultResumptionHandler@, which can be overridden,
    457 that is polymorphic over all resumption exceptions but performs a termination
    458 throw on the exception rather than a cancellation.
    459 
    460 Throwing the exception in @defaultResumptionHandler@ has the positive effect of
    461 walking the stack a second time for a recovery handler. Hence, a programmer has
    462 two chances for help with a problem, fixup or recovery, should either kind of
    463 handler appear on the stack. However, this dual stack walk leads to following
    464 apparent anomaly:
    465 \begin{cfa}
    466 try {
    467         throwResume E;
    468 } catch (E) {
    469         // this handler runs
    470 }
    471 \end{cfa}
    472 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
    473 matches with @catchResume@. The anomaly results because the unmatched
    474 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
    475 
    476412% I wonder if there would be some good central place for this.
    477 Note, termination and resumption handlers may be used together
     413Note that termination handlers and resumption handlers may be used together
    478414in a single try statement, intermixing @catch@ and @catchResume@ freely.
    479415Each type of handler only interacts with exceptions from the matching
    480416kind of raise.
     417When a try statement is executed, it simply executes the statements in the
     418@GUARDED_BLOCK@ and then finishes.
     419
     420However, while the guarded statements are being executed, including any
     421invoked functions, all the handlers in these statements are included in the
     422search path.
     423Hence, if a resumption exception is raised these handlers may be matched
     424against the exception and may handle it.
     425
     426Exception matching checks the handler in each catch clause in the order
     427they appear, top to bottom. If the representation of the raised exception type
     428is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
     429(if provided) is bound to a pointer to the exception and the statements in
     430@HANDLER_BLOCK@$_i$ are executed.
     431If control reaches the end of the handler, execution continues after the
     432the raise statement that raised the handled exception.
     433
     434Like termination, if no resumption handler is found during the search,
     435the default handler (\defaultResumptionHandler) visible at the raise
     436statement is called. It will use the best match at the raise sight according
     437to \CFA's overloading rules. The default handler is
     438passed the exception given to the raise. When the default handler finishes
     439execution continues after the raise statement.
     440
     441There is a global \defaultResumptionHandler{} is polymorphic over all
     442resumption exceptions and preforms a termination throw on the exception.
     443The \defaultTerminationHandler{} can be overridden by providing a new
     444function that is a better match.
    481445
    482446\subsubsection{Resumption Marking}
    483447\label{s:ResumptionMarking}
    484448A key difference between resumption and termination is that resumption does
    485 not unwind the stack. A side effect is that, when a handler is matched
    486 and run, its try block (the guarded statements) and every try statement
     449not unwind the stack. A side effect that is that when a handler is matched
     450and run it's try block (the guarded statements) and every try statement
    487451searched before it are still on the stack. There presence can lead to
    488 the \emph{recursive resumption problem}.
     452the recursive resumption problem.
    489453
    490454The recursive resumption problem is any situation where a resumption handler
    … …  
    500464When this code is executed, the guarded @throwResume@ starts a
    501465search and matches the handler in the @catchResume@ clause. This
    502 call is placed on the stack above the try-block. Now the second raise in the handler
    503 searches the same try block, matches, and puts another instance of the
     466call is placed on the stack above the try-block. The second raise then
     467searches the same try block and puts another instance of the
    504468same handler on the stack leading to infinite recursion.
    505469
    506 While this situation is trivial and easy to avoid, much more complex cycles can
    507 form with multiple handlers and different exception types.  The key point is
    508 that the programmer's intuition expects every raise in a handler to start
    509 searching \emph{below} the @try@ statement, making it difficult to understand
    510 and fix the problem.
    511 
    512 To prevent all of these cases, each try statement is ``marked" from the
    513 time the exception search reaches it to either when a matching handler
    514 completes or when the search reaches the base
     470While this situation is trivial and easy to avoid, much more complex cycles
     471can form with multiple handlers and different exception types.
     472
     473To prevent all of these cases, a each try statement is ``marked" from the
     474time the exception search reaches it to either when the exception is being
     475handled completes the matching handler or when the search reaches the base
    515476of the stack.
    516477While a try statement is marked, its handlers are never matched, effectively
    … …  
    524485for instance, marking just the handlers that caught the exception,
    525486would also prevent recursive resumption.
    526 However, the rule selected mirrors what happens with termination,
    527 and hence, matches programmer intuition that a raise searches below a try.
    528 
    529 In detail, the marked try statements are the ones that would be removed from
    530 the stack for a termination exception, \ie those on the stack
     487However, these rules mirror what happens with termination.
     488
     489The try statements that are marked are the ones that would be removed from
     490the stack if this was a termination exception, that is those on the stack
    531491between the handler and the raise statement.
    532492This symmetry applies to the default handler as well, as both kinds of
    … …  
    562522        // Only handle IO failure for f3.
    563523}
    564 // Handle a failure relating to f2 further down the stack.
     524// Can't handle a failure relating to f2 here.
    565525\end{cfa}
    566526In this example the file that experienced the IO error is used to decide
    … …  
    593553
    594554\subsection{Comparison with Reraising}
    595 Without conditional catch, the only approach to match in more detail is to reraise
    596 the exception after it has been caught, if it could not be handled.
    597 \begin{center}
    598 \begin{tabular}{l|l}
     555A more popular way to allow handlers to match in more detail is to reraise
     556the exception after it has been caught, if it could not be handled here.
     557On the surface these two features seem interchangeable.
     558
     559If @throw;@ (no argument) starts a termination reraise,
     560which is the same as a raise but reuses the last caught exception,
     561then these two statements have the same behaviour:
    599562\begin{cfa}
    600563try {
    601         do_work_may_throw();
    602 } catch(excep_t * ex; can_handle(ex)) {
    603 
    604         handle(ex);
    605 
    606 
    607 
     564    do_work_may_throw();
     565} catch(exception_t * exc ; can_handle(exc)) {
     566    handle(exc);
    608567}
    609568\end{cfa}
    610 &
     569
    611570\begin{cfa}
    612571try {
    613         do_work_may_throw();
    614 } catch(excep_t * ex) {
    615         if (can_handle(ex)) {
    616                 handle(ex);
    617         } else {
    618                 throw;
    619         }
     572    do_work_may_throw();
     573} catch(exception_t * exc) {
     574    if (can_handle(exc)) {
     575        handle(exc);
     576    } else {
     577        throw;
     578    }
    620579}
    621580\end{cfa}
    622 \end{tabular}
    623 \end{center}
    624 Notice catch-and-reraise increases complexity by adding additional data and
    625 code to the exception process. Nevertheless, catch-and-reraise can simulate
    626 conditional catch straightforwardly, when exceptions are disjoint, \ie no
    627 inheritance.
    628 
    629 However, catch-and-reraise simulation becomes unusable for exception inheritance.
    630 \begin{flushleft}
    631 \begin{cfa}[xleftmargin=6pt]
    632 exception E1;
    633 exception E2(E1); // inheritance
    634 \end{cfa}
    635 \begin{tabular}{l|l}
    636 \begin{cfa}
    637 try {
    638         ... foo(); ... // raise E1/E2
    639         ... bar(); ... // raise E1/E2
    640 } catch( E2 e; e.rtn == foo ) {
    641         ...
    642 } catch( E1 e; e.rtn == foo ) {
    643         ...
    644 } catch( E1 e; e.rtn == bar ) {
    645         ...
    646 }
    647 
    648 \end{cfa}
    649 &
    650 \begin{cfa}
    651 try {
    652         ... foo(); ...
    653         ... bar(); ...
    654 } catch( E2 e ) {
    655         if ( e.rtn == foo ) { ...
    656         } else throw; // reraise
    657 } catch( E1 e ) {
    658         if (e.rtn == foo) { ...
    659         } else if (e.rtn == bar) { ...
    660         else throw; // reraise
    661 }
    662 \end{cfa}
    663 \end{tabular}
    664 \end{flushleft}
    665 The derived exception @E2@ must be ordered first in the catch list, otherwise
    666 the base exception @E1@ catches both exceptions. In the catch-and-reraise code
    667 (right), the @E2@ handler catches exceptions from both @foo@ and
    668 @bar@. However, the reraise misses the following catch clause. To fix this
    669 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
    670 reraise, and its handler must duplicate the inner handler code for @bar@. To
    671 generalize, this fix for any amount of inheritance and complexity of try
    672 statement requires a technique called \emph{try-block
    673 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
    674 sufficient to state that conditional catch is more expressive than
    675 catch-and-reraise in terms of complexity.
    676 
    677 \begin{comment}
    678 That is, they have the same behaviour in isolation.
     581That is, they will have the same behaviour in isolation.
    679582Two things can expose differences between these cases.
    680583
    681584One is the existence of multiple handlers on a single try statement.
    682 A reraise skips all later handlers for a try statement but a conditional
     585A reraise skips all later handlers on this try statement but a conditional
    683586catch does not.
    684 % Hence, if an earlier handler contains a reraise later handlers are
    685 % implicitly skipped, with a conditional catch they are not.
     587Hence, if an earlier handler contains a reraise later handlers are
     588implicitly skipped, with a conditional catch they are not.
    686589Still, they are equivalently powerful,
    687590both can be used two mimic the behaviour of the other,
    … …  
    734637%   `exception_ptr current_exception() noexcept;`
    735638% https://www.python.org/dev/peps/pep-0343/
    736 \end{comment}
    737639
    738640\section{Finally Clauses}
    … …  
    750652The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    751653stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    752 finishes, or during an unwind.
     654finishes or during an unwind.
    753655The only time the block is not executed is if the program is exited before
    754656the stack is unwound.
    … …  
    766668
    767669Not all languages with unwinding have finally clauses. Notably \Cpp does
    768 without it as destructors, and the RAII design pattern, serve a similar role.
    769 Although destructors and finally clauses can be used for the same cases,
     670without it as descructors, and the RAII design pattern, serve a similar role.
     671Although destructors and finally clauses can be used in the same cases,
    770672they have their own strengths, similar to top-level function and lambda
    771673functions with closures.
    772 Destructors take more work for their creation, but if there is clean-up code
    773 that needs to be run every time a type is used, they are much easier
     674Destructors take more work for their first use, but if there is clean-up code
     675that needs to be run every time a type is used they soon become much easier
    774676to set-up.
    775677On the other hand finally clauses capture the local context, so is easy to
    776678use when the clean-up is not dependent on the type of a variable or requires
    777679information from multiple variables.
     680% To Peter: I think these are the main points you were going for.
    778681
    779682\section{Cancellation}
    … …  
    788691raise, this exception is not used in matching only to pass information about
    789692the cause of the cancellation.
    790 Finaly, since a cancellation only unwinds and forwards, there is no default handler.
     693(This also means matching cannot fail so there is no default handler.)
    791694
    792695After @cancel_stack@ is called the exception is copied into the EHM's memory
    … …  
    799702After the main stack is unwound there is a program-level abort.
    800703
    801 The reasons for this semantics in a sequential program is that there is no more code to execute.
    802 This semantics also applies to concurrent programs, too, even if threads are running.
    803 That is, if any threads starts a cancellation, it implies all threads terminate.
    804 Keeping the same behaviour in sequential and concurrent programs is simple.
     704There are two reasons for these semantics.
     705The first is that it had to do this abort.
     706in a sequential program as there is nothing else to notify and the simplicity
     707of keeping the same behaviour in sequential and concurrent programs is good.
    805708Also, even in concurrent programs there may not currently be any other stacks
    806709and even if other stacks do exist, main has no way to know where they are.
    … …  
    847750caller's context and passes it to the internal report.
    848751
    849 A coroutine only knows of two other coroutines, its starter and its last resumer.
     752A coroutine knows of two other coroutines, its starter and its last resumer.
    850753The starter has a much more distant connection, while the last resumer just
    851754(in terms of coroutine state) called resume on this coroutine, so the message
    … …  
    855758cascade an error across any number of coroutines, cleaning up each in turn,
    856759until the error is handled or a thread stack is reached.
    857 
    858 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you
    859 talk about handling a cancellation in the last sentence. Which is correct?}

  • doc/theses/andrew_beach_MMath/intro.tex

    r5438e41 rf42a6b8  
    22
    33% The highest level overview of Cforall and EHMs. Get this done right away.
    4 This thesis covers the design and implementation of the exception handling
     4This thesis goes over the design and implementation of the exception handling
    55mechanism (EHM) of
    66\CFA (pronounced sea-for-all and may be written Cforall or CFA).
    7 \CFA is a new programming language that extends C, which maintains
     7\CFA is a new programming language that extends C, that maintains
    88backwards-compatibility while introducing modern programming features.
    99Adding exception handling to \CFA gives it new ways to handle errors and
    10 make large control-flow jumps.
     10make other large control-flow jumps.
    1111
    1212% Now take a step back and explain what exceptions are generally.
    13 A 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).
    1713Exception handling provides dynamic inter-function control flow.
    1814There are two forms of exception handling covered in this thesis:
    1915termination, which acts as a multi-level return,
    2016and resumption, which is a dynamic function call.
    21 % PAB: Maybe this sentence was suppose to be deleted?
    2217Termination 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.
     18to the extent that it is often seen
     19This seperation is uncommon because termination exception handling is so
     20much more common that it is often assumed.
    2721% 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.
     22A language's EHM is the combination of language syntax and run-time
     23components that are used to construct, raise and handle exceptions,
     24including all control flow.
     25
     26Termination exception handling allows control to return to any previous
     27function on the stack directly, skipping any functions between it and the
     28current function.
    3029\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}
     30\input{callreturn}
    5231\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.
    70 \begin{center}
    71 \input{resumption}
    72 \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.
     32
     33Resumption exception handling seaches the stack for a handler and then calls
     34it without adding or removing any other stack frames.
     35\todo{Add a diagram showing control flow for resumption.}
    7536
    7637Although a powerful feature, exception handling tends to be complex to set up
    7738and expensive to use
    78 so 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
     39so they are often limited to unusual or ``exceptional" cases.
     40The classic example of this is error handling, exceptions can be used to
     41remove error handling logic from the main execution path and while paying
    8142most of the cost only when the error actually occurs.
    8243
    … …  
    8849some of the underlying tools used to implement and express exception handling
    8950in 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@ {
     51Still the resulting syntax resembles that of other languages:
     52\begin{cfa}
     53try {
    9354        ...
    9455        T * object = malloc(request_size);
    9556        if (!object) {
    96                 @throw@ OutOfMemory{fixed_allocation, request_size};
     57                throw OutOfMemory{fixed_allocation, request_size};
    9758        }
    9859        ...
    99 } @catch@ (OutOfMemory * error) {
     60} catch (OutOfMemory * error) {
    10061        ...
    10162}
    102 \end{lstlisting}
     63\end{cfa}
     64
    10365% A note that yes, that was a very fast overview.
    10466The design and implementation of all of \CFA's EHM's features are
    … …  
    10769
    10870% 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
     71All of these features have been implemented in \CFA, along with
     72a suite of test cases as part of this project.
     73The implementation techniques are generally applicable in other programming
    11374languages 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.
     75Some parts of the EHM use other features unique to \CFA and these would be
     76harder to replicate in other programming languages.
     77
    11678% 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.
     79Some existing programming languages that include EHMs/exception handling
     80include C++, Java and Python. All three examples focus on termination
     81exceptions which unwind the stack as part of the
     82Exceptions also can replace return codes and return unions.
    12083
    12184The contributions of this work are:
    12285\begin{enumerate}
    12386\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.
     87other programming languages and the creation of new features.
     88\item Implementing stack unwinding and the EHM in \CFA, including updating
     89the compiler and the run-time environment.
     90\item Designed and implemented a prototype virtual system.
    12891% I think the virtual system and per-call site default handlers are the only
    12992% "new" features, everything else is a matter of implementation.
    130 \item Creating tests and performance benchmarks to compare with EHM's in other languages.
    13193\end{enumerate}
    13294
    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},
    137 covering their usage and design.
    138 That is followed by the implementation of these features in
     95\todo{I can't figure out a good lead-in to the roadmap.}
     96The next section covers the existing state of exceptions.
     97The existing state of \CFA is also covered in \autoref{c:existing}.
     98The new features are introduced in \autoref{c:features},
     99which explains their usage and design.
     100That is followed by the implementation of those features in
    139101\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}.
     102The performance results are examined in \autoref{c:performance}.
     103Possibilities to extend this project are discussed in \autoref{c:future}.
    142104
    143105\section{Background}
    144106\label{s:background}
    145107
    146 Exception handling is a well examined area in programming languages,
    147 with papers on the subject dating back the 70s~\cite{Goodenough75}.
    148 Early exceptions were often treated as signals, which carried no information
    149 except their identity. Ada~\cite{Ada} still uses this system.
     108Exception handling is not a new concept,
     109with papers on the subject dating back 70s.\cite{Goodenough}
     110
     111Early exceptions were often treated as signals. They carried no information
     112except their identity. Ada still uses this system.
    150113
    151114The modern flag-ship for termination exceptions is \Cpp,
    … …  
    153116in 1990.
    154117% 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
     118\Cpp has the ability to use any value of any type as an exception.
     119However that seems to immediately pushed aside for classes inherited from
    158120\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
    163 exceptions 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}
     121Although there is a special catch-all syntax it does not allow anything to
     122be done with the caught value becuase nothing is known about it.
     123So instead a base type is defined with some common functionality (such as
     124the ability to describe the reason the exception was raised) and all
     125exceptions have that functionality.
     126This seems to be the standard now, as the garentied functionality is worth
     127any lost flexibility from limiting it to a single type.
     128
     129Java was the next popular language to use exceptions.
     130Its exception system largely reflects that of \Cpp, except that requires
     131you throw a child type of \code{Java}{java.lang.Throwable}
    170132and 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
     133Checked exceptions are part of the function interface they are raised from.
     134This includes functions they propogate through, until a handler for that
     135type of exception is found.
     136This makes exception information explicit, which can improve clarity and
    174137safety, 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.
    181 
    182 %\subsection
    183 Resumption exceptions are less popular,
    184 although resumption is as old as termination;
    185 hence, few
     138Some of these, such as dealing with high-order methods or an overly specified
     139throws clause, are technical. However some of the issues are much more
     140human, in that writing/updating all the exception signatures can be enough
     141of a burden people will hack the system to avoid them.
     142Including the ``catch-and-ignore" pattern where a catch block is used without
     143anything to repair or recover from the exception.
     144
     145%\subsection
     146Resumption exceptions have been much less popular.
     147Although resumption has a history as old as termination's, very few
    186148programming languages have implemented them.
    187149% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    188150%   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
     151Mesa is one programming languages that did. Experiance with Mesa
     152is quoted as being one of the reasons resumptions were not
    191153included in the \Cpp standard.
    192154% 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.
     155Since then resumptions have been ignored in the main-stream.
     156
     157All of this does call into question the use of resumptions, is
     158something largely rejected decades ago worth revisiting now?
     159Yes, even if it was the right call at the time there have been decades
     160of other developments in computer science that have changed the situation
     161since then.
     162Some of these developments, such as in functional programming's resumption
     163equivalent: algebraic effects\cite{Zhang19}, are directly related to
     164resumptions as well.
     165A complete rexamination of resumptions is beyond a single paper, but it is
     166enough to try them again in \CFA.
    201167% Especially considering how much easier they are to implement than
    202168% termination exceptions.
    203169
    204170%\subsection
    205 Functional languages tend to use other solutions for their primary EHM,
    206 but exception-like constructs still appear.
     171Functional languages tend to use other solutions for their primary error
     172handling mechanism, exception-like constructs still appear.
    207173Termination 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.
    210 Resumption appears in algebraic effects, where a function dispatches its
     174expression as an error, the result of any expression that tries to use it as
     175an error, and so on until an approprate handler is reached.
     176Resumption appears in algebric effects, where a function dispatches its
    211177side-effects to its caller for handling.
    212178
    213179%\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
     180More recently exceptions seem to be vanishing from newer programming
     181languages, replaced by ``panic".
     182In Rust a panic is just a program level abort that may be implemented by
    217183unwinding the stack like in termination exception handling.
    218184% 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
     185Go's panic through is very similar to a termination except it only supports
    220186a catch-all by calling \code{Go}{recover()}, simplifying the interface at
    221 the cost of flexibility.
    222 
    223 %\subsection
    224 While exception handling's most common use cases are in error handling,
    225 here are other ways to handle errors with comparisons to exceptions.
     187the cost of flexability.
     188
     189%\subsection
     190Exception handling's most common use cases are in error handling.
     191Here are some other ways to handle errors and comparisons with exceptions.
    226192\begin{itemize}
    227193\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,
    234 which 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..
    238 
     194This pattern uses an enumeration (or just a set of fixed values) to indicate
     195that an error has occured and which error it was.
     196
     197There are some issues if a function wants to return an error code and another
     198value. The main issue is that it can be easy to forget checking the error
     199code, which can lead to an error being quitely and implicitly ignored.
     200Some new languages have tools that raise warnings if the return value is
     201discarded to avoid this.
     202It also puts more code on the main execution path.
    239203\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.
    248 
     204A function that encounters an error returns some value indicating that it
     205encountered a value but store which error occured in a fixed global location.
     206
     207Perhaps the C standard @errno@ is the most famous example of this,
     208where some standard library functions will return some non-value (often a
     209NULL pointer) and set @errno@.
     210
     211This avoids the multiple results issue encountered with straight error codes
     212but otherwise many of the same advantages and disadvantages.
     213It does however introduce one other major disadvantage:
     214Everything that uses that global location must agree on all possible errors.
    249215\item\emph{Return Union}:
    250 This pattern replaces error codes with a tagged union.
     216Replaces error codes with a tagged union.
    251217Success is one tag and the errors are another.
    252218It is also possible to make each possible error its own tag and carry its own
    … …  
    254220so that one type can be used everywhere in error handling code.
    255221
    256 This pattern is very popular in functional or any semi-functional language with
    257 primitive support for tagged unions (or algebraic data types).
     222This pattern is very popular in functional or semi-functional language,
     223anything with primitive support for tagged unions (or algebraic data types).
    258224% We need listing Rust/rust to format code snipits from it.
    259225% 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.
    265 
     226
     227The main disadvantage is again it puts code on the main execution path.
     228This is also the first technique that allows for more information about an
     229error, other than one of a fix-set of ids, to be sent.
     230They can be missed but some languages can force that they are checked.
     231It is also implicitly forced in any languages with checked union access.
    266232\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
     233On error the function that produced the error calls another function to
    269234handle it.
    270235The handler function can be provided locally (passed in as an argument,
    271236either directly as as a field of a structure/object) or globally (a global
    272237variable).
    273 C++ uses this approach as its fallback system if exception handling fails, \eg
     238
     239C++ uses this as its fallback system if exception handling fails.
    274240\snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
    275241
    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.
     242Handler functions work a lot like resumption exceptions.
     243The difference is they are more expencive to set up but cheaper to use, and
     244so are more suited to more fequent errors.
     245The exception being global handlers if they are rarely change as the time
     246in both cases strinks towards zero.
    281247\end{itemize}
    282248
    283249%\subsection
    284 Because 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.
     250Because of their cost exceptions are rarely used for hot paths of execution.
     251There is an element of self-fulfilling prophocy here as implementation
     252techniques have been designed to make exceptions cheap to set-up at the cost
     253of making them expencive to use.
     254Still, use of exceptions for other tasks is more common in higher-level
     255scripting languages.
     256An iconic example is Python's StopIteration exception which is thrown by
     257an iterator to indicate that it is exausted. Combined with Python's heavy
     258use of the iterator based for-loop.
    292259% https://docs.python.org/3/library/exceptions.html#StopIteration

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

    r5438e41 rf42a6b8  
    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}]{@}{@}}
     212\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
    214213% Annotations from Peter:
    215214\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
    … …  
    247246\input{performance}
    248247\input{future}
    249 \input{conclusion}
    250248
    251249%----------------------------------------------------------------------
Note: See TracChangeset for help on using the changeset viewer.