Changes in / [1a6a6f2:315e5e3]


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

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/conclusion.tex

    r1a6a6f2 r315e5e3  
    11\chapter{Conclusion}
    2 \label{c:conclusion}
    32% Just a little knot to tie the paper together.
    43

  • doc/theses/andrew_beach_MMath/existing.tex

    r1a6a6f2 r315e5e3  
    1010
    1111Only those \CFA features pertaining to this thesis are discussed.
     12% Also, only new features of \CFA will be discussed,
    1213A familiarity with
    1314C or C-like languages is assumed.
    … …  
    1617\CFA has extensive overloading, allowing multiple definitions of the same name
    1718to be defined~\cite{Moss18}.
    18 \begin{cfa}
    19 char i; int i; double i;
    20 int f(); double f();
    21 void g( int ); void g( double );
    22 \end{cfa}
     19\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     20char @i@; int @i@; double @i@;
     21int @f@(); double @f@();
     22void @g@( int ); void @g@( double );
     23\end{lstlisting}
    2324This feature requires name mangling so the assembly symbols are unique for
    2425different overloads. For compatibility with names in C, there is also a syntax
    … …  
    6263int && rri = ri;
    6364rri = 3;
    64 &ri = &j;
     65&ri = &j; // rebindable
    6566ri = 5;
    6667\end{cfa}
    … …  
    7879\end{minipage}
    7980
    80 References are intended to be used when the indirection of a pointer is
    81 required, but the address is not as important as the value and dereferencing
    82 is the common usage.
     81References are intended for pointer situations where dereferencing is the common usage,
     82\ie the value is more important than the pointer.
    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.
    85 % ???
     84with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
    8685
    8786\section{Operators}
    8887
    8988\CFA implements operator overloading by providing special names, where
    90 operator expressions are translated into function calls using these names.
     89operator usages are translated into function calls using these names.
    9190An operator name is created by taking the operator symbols and joining them with
    9291@?@s to show where the arguments go.
    … …  
    9594This syntax make it easy to tell the difference between prefix operations
    9695(such as @++?@) and post-fix operations (@?++@).
    97 
    98 As an example, here are the addition and equality operators for a point type.
     96For example, plus and equality operators are defined for a point type.
    9997\begin{cfa}
    10098point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
    … …  
    104102}
    105103\end{cfa}
    106 Note that this syntax works effectively but a textual transformation,
    107 the compiler converts all operators into functions and then resolves them
    108 normally. This means any combination of types may be used,
    109 although nonsensical ones (like @double ?==?(point, int);@) are discouraged.
    110 This feature is also used for all builtin operators as well,
    111 although those are implicitly provided by the language.
     104Note these special names are not limited to builtin
     105operators, and hence, may be used with arbitrary types.
     106\begin{cfa}
     107double ?+?( 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.
     112Because operators are never part of the type definition they may be added
     113at any time, including on built-in types.
    112114
    113115%\subsection{Constructors and Destructors}
    114 In \CFA, constructors and destructors are operators, which means they are
    115 functions with special operator names rather than type names in \Cpp.
    116 Both constructors and destructors can be implicity called by the compiler,
    117 however the operator names allow explicit calls.
    118 % Placement new means that this is actually equivant to C++.
     116
     117\CFA also provides constructors and destructors as operators, which means they
     118are functions with special operator names rather than type names in \Cpp.
     119While constructors and destructions are normally called implicitly by the compiler,
     120the special operator names, allow explicit calls.
     121
     122% Placement new means that this is actually equivalent to C++.
    119123
    120124The special name for a constructor is @?{}@, which comes from the
    … …  
    125129struct Example { ... };
    126130void ?{}(Example & this) { ... }
    127 {
    128         Example a;
    129         Example b = {};
    130 }
    131131void ?{}(Example & this, char first, int num) { ... }
    132 {
    133         Example c = {'a', 2};
    134 }
    135 \end{cfa}
    136 Both @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.
    139 Currently, there is no general way to skip initialation.
    140 % I don't use @= anywhere in the thesis.
    141 
     132Example a;              // implicit constructor calls
     133Example b = {};
     134Example c = {'a', 2};
     135\end{cfa}
     136Both @a@ and @b@ are initialized with the first constructor,
     137while @c@ is initialized with the second.
     138Constructor calls can be replaced with C initialization using special operator \lstinline{@=}.
     139\begin{cfa}
     140Example d @= {42};
     141\end{cfa}
    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.
    145147\begin{cfa}
    146148void ^?{}(Example & this) { ... }
    147149{
    148         Example d;
    149         ^?{}(d);
    150 
    151         Example e;
    152 } // Implicit call of ^?{}(e);
     150        Example e;      // implicit constructor call
     151        ^?{}(e);                // explicit destructor call
     152        ?{}(e);         // explicit constructor call
     153} // implicit destructor call
    153154\end{cfa}
    154155
    … …  
    224225The global definition of @do_once@ is ignored, however if quadruple took a
    225226@double@ argument, then the global definition would be used instead as it
    226 would then be a better match.
    227 \todo{cite Aaron's thesis (maybe)}
    228 
    229 To avoid typing long lists of assertions, constraints can be collected into
    230 convenient a package called a @trait@, which can then be used in an assertion
     227is a better match.
     228% Aaron's thesis might be a good reference here.
     229
     230To avoid typing long lists of assertions, constraints can be collect into
     231convenient package called a @trait@, which can then be used in an assertion
    231232instead of the individual constraints.
    232233\begin{cfa}
    … …  
    252253        node(T) * next;
    253254        T * data;
    254 };
     255}
    255256node(int) inode;
    256257\end{cfa}
    … …  
    292293};
    293294CountUp countup;
     295for (10) sout | resume(countup).next; // print 10 values
    294296\end{cfa}
    295297Each coroutine has a @main@ function, which takes a reference to a coroutine
    296298object and returns @void@.
    297299%[numbers=left] Why numbers on this one?
    298 \begin{cfa}
     300\begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
    299301void main(CountUp & this) {
    300         for (unsigned int next = 0 ; true ; ++next) {
    301                 this.next = next;
     302        for (unsigned int up = 0;; ++up) {
     303                this.next = up;
    302304                suspend;$\label{suspend}$
    303305        }
    … …  
    305307\end{cfa}
    306308In this function, or functions called by this function (helper functions), the
    307 @suspend@ statement is used to return execution to the coroutine's caller
    308 without terminating the coroutine's function.
     309@suspend@ statement is used to return execution to the coroutine's resumer
     310without terminating the coroutine's function(s).
    309311
    310312A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    311313The first resume calls the @main@ function at the top. Thereafter, resume calls
    312314continue a coroutine in the last suspended function after the @suspend@
    313 statement. In this case there is only one and, hence, the difference between
    314 subsequent calls is the state of variables inside the function and the
    315 coroutine object.
    316 The return value of @resume@ is a reference to the coroutine, to make it
    317 convent to access fields of the coroutine in the same expression.
    318 Here is a simple example in a helper function:
    319 \begin{cfa}
    320 unsigned int get_next(CountUp & this) {
    321         return resume(this).next;
    322 }
    323 \end{cfa}
    324 
    325 When the main function returns the coroutine halts and can no longer be
    326 resumed.
     315statement, in this case @main@ line~\ref{suspend}.  The @resume@ function takes
     316a reference to the coroutine structure and returns the same reference. The
     317return value allows easy access to communication variables defined in the
     318coroutine object. For example, the @next@ value for coroutine object @countup@
     319is both generated and collected in the single expression:
     320@resume(countup).next@.
    327321
    328322\subsection{Monitor and Mutex Parameter}
    … …  
    336330exclusion on a monitor object by qualifying an object reference parameter with
    337331@mutex@.
    338 \begin{cfa}
    339 void example(MonitorA & mutex argA, MonitorB & mutex argB);
    340 \end{cfa}
     332\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     333void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
     334\end{lstlisting}
    341335When the function is called, it implicitly acquires the monitor lock for all of
    342336the mutex parameters without deadlock.  This semantics means all functions with
    … …  
    368362{
    369363        StringWorker stringworker; // fork thread running in "main"
    370 } // Implicit call to join(stringworker), waits for completion.
     364} // implicitly join with thread / wait for completion
    371365\end{cfa}
    372366The thread main is where a new thread starts execution after a fork operation

  • doc/theses/andrew_beach_MMath/features.tex

    r1a6a6f2 r315e5e3  
    1919
    2020\paragraph{Raise}
    21 The raise is the starting point for exception handling,
     21The raise is the starting point for exception handling
    2222by raising an exception, which passes it to
    2323the EHM.
    … …  
    3030\paragraph{Handle}
    3131The primary purpose of an EHM is to run some user code to handle a raised
    32 exception. This code is given, along with some other information,
    33 in a handler.
     32exception. This code is given, with some other information, in a handler.
    3433
    3534A handler has three common features: the previously mentioned user code, a
    36 region of code it guards and an exception label/condition that matches
    37 against the raised exception.
     35region of code it guards, and an exception label/condition that matches
     36the raised exception.
    3837Only raises inside the guarded region and raising exceptions that match the
    3938label can be handled by a given handler.
    … …  
    4241
    4342The @try@ statements of \Cpp, Java and Python are common examples. All three
    44 also show another common feature of handlers, they are grouped by the guarded
    45 region.
     43show the common features of guarded region, raise, matching and handler.
     44\begin{cfa}
     45try {                           // guarded region
     46        ...     
     47        throw exception;        // raise
     48        ...     
     49} catch( exception ) {  // matching condition, with exception label
     50        ...                             // handler code
     51}
     52\end{cfa}
    4653
    4754\subsection{Propagation}
    4855After an exception is raised comes what is usually the biggest step for the
    49 EHM: finding and setting up the handler for execution.
    50 The propagation from raise to
     56EHM: finding and setting up the handler for execution. The propagation from raise to
    5157handler can be broken up into three different tasks: searching for a handler,
    5258matching against the handler and installing the handler.
    … …  
    5460\paragraph{Searching}
    5561The EHM begins by searching for handlers that might be used to handle
    56 the exception.
    57 The search will find handlers that have the raise site in their guarded
     62the exception. The search is restricted to
     63handlers that have the raise site in their guarded
    5864region.
    5965The search includes handlers in the current function, as well as any in
    … …  
    6167
    6268\paragraph{Matching}
    63 Each handler found is with the raised exception. The exception
     69Each handler found is matched with the raised exception. The exception
    6470label defines a condition that is used with the exception and decides if
    6571there is a match or not.
    66 %
    6772In languages where the first match is used, this step is intertwined with
    6873searching; a match check is performed immediately after the search finds
    … …  
    7984different course of action for this case.
    8085This situation only occurs with unchecked exceptions as checked exceptions
    81 (such as in Java) can make the guarantee.
     86(such as in Java) are guaranteed to find a matching handler.
    8287The unhandled action is usually very general, such as aborting the program.
    8388
    … …  
    9398A handler labeled with any given exception can handle exceptions of that
    9499type or any child type of that exception. The root of the exception hierarchy
    95 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types
     100(here \code{C}{exception}) acts as a catch-all, leaf types catch single types,
    96101and the exceptions in the middle can be used to catch different groups of
    97102related exceptions.
    98103
    99104This system has some notable advantages, such as multiple levels of grouping,
    100 the ability for libraries to add new exception types and the isolation
     105the ability for libraries to add new exception types, and the isolation
    101106between different sub-hierarchies.
    102107This design is used in \CFA even though it is not a object-orientated
    … …  
    118123For effective exception handling, additional information is often passed
    119124from the raise to the handler and back again.
    120 So far, only communication of the exceptions' identity is covered.
    121 A common communication method for adding information to an exception
    122 is putting fields into the exception instance
     125So far, only communication of the exception's identity is covered.
     126A common communication method for passing more information is putting fields into the exception instance
    123127and giving the handler access to them.
    124 % You can either have pointers/references in the exception, or have p/rs to
    125 % the exception when it doesn't have to be copied.
    126 Passing references or pointers allows data at the raise location to be
    127 updated, passing information in both directions.
     128Using reference fields pointing to data at the raise location allows data to be
     129passed in both directions.
    128130
    129131\section{Virtuals}
    130 \label{s:virtuals}
     132\label{s:Virtuals}
    131133Virtual types and casts are not part of \CFA's EHM nor are they required for
    132134an EHM.
    133135However, one of the best ways to support an exception hierarchy
    134136is via a virtual hierarchy and dispatch system.
    135 Ideally, the virtual system would have been part of \CFA before the work
     137Ideally, the virtual system should have been part of \CFA before the work
    136138on exception handling began, but unfortunately it was not.
    137139Hence, only the features and framework needed for the EHM were
    138 designed and implemented for this thesis.
    139 Other features were considered to ensure that
     140designed and implemented for this thesis. Other features were considered to ensure that
    140141the structure could accommodate other desirable features in the future
    141142but are not implemented.
    142143The rest of this section only discusses the implemented subset of the
    143 virtual system design.
     144virtual-system design.
    144145
    145146The virtual system supports multiple ``trees" of types. Each tree is
    … …  
    148149number of children.
    149150Any type that belongs to any of these trees is called a virtual type.
     151For 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}
     156vtype V0, V1(V0), V2(V0);
     157vtype W0, W1(W0), W2(W1);
     158\end{cfa}
     159&
     160\raisebox{-0.6\totalheight}{\input{vtable}}
     161\end{tabular}
     162\lstMakeShortInline@
     163\end{flushleft}
    150164% A type's ancestors are its parent and its parent's ancestors.
    151165% The root type has no ancestors.
    152166% A type's descendants are its children and its children's descendants.
    153 
    154 For the purposes of illistration, a proposed -- but unimplemented syntax --
    155 will be used. Each virtual type is repersented by a trait with an annotation
    156 that makes it a virtual type. This annotation is empty for a root type, which
    157 creates a new tree:
    158 \begin{cfa}
    159 trait root_type(T) virtual() {}
    160 \end{cfa}
    161 The annotation may also refer to any existing virtual type to make this new
    162 type a child of that type and part of the same tree. The parent may itself
    163 be a child or a root type and may have any number of existing children.
    164 \begin{cfa}
    165 trait child_a(T) virtual(root_type) {}
    166 trait grandchild(T) virtual(child_a) {}
    167 trait child_b(T) virtual(root_type) {}
    168 \end{cfa}
    169 \todo{Update the diagram in vtable.fig to show the new type tree.}
    170 
    171 Every virtual type also has a list of virtual members and a unique id,
    172 both are stored in a virtual table.
    173 Every instance of a virtual type also has a pointer to a virtual table stored
    174 in it, although there is no per-type virtual table as in many other languages.
    175 
    176 The list of virtual members is built up down the tree. Every virtual type
    177 inherits the list of virtual members from its parent and may add more
    178 virtual members to the end of the list which are passed on to its children.
    179 Again, using the unimplemented syntax this might look like:
    180 \begin{cfa}
    181 trait root_type(T) virtual() {
    182         const char * to_string(T const & this);
    183         unsigned int size;
    184 }
    185 
    186 trait child_type(T) virtual(root_type) {
    187         char * irrelevant_function(int, char);
    188 }
    189 \end{cfa}
    190 % Consider adding a diagram, but we might be good with the explanation.
    191 
    192 As @child_type@ is a child of @root_type@ it has the virtual members of
    193 @root_type@ (@to_string@ and @size@) as well as the one it declared
    194 (@irrelivant_function@).
    195 
    196 It is important to note that these are virtual members, and may contain   
    197 arbitrary fields, functions or otherwise.
    198 The names ``size" and ``align" are reserved for the size and alignment of the
    199 virtual type, and are always automatically initialized as such.
    200 The other special case are uses of the trait's polymorphic argument
    201 (@T@ in the example), which are always updated to refer to the current
    202 virtual type. This allows functions that refer to to polymorphic argument
    203 to act as traditional virtual methods (@to_string@ in the example), as the
    204 object can always be passed to a virtual method in its virtual table.
     167Every 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
     169details). Children inherit their parent's list of virtual members but may add
     170and/or replace members.  For example,
     171\begin{cfa}
     172vtable W0 | { int ?<?( int, int ); int ?+?( int, int ); }
     173vtable W1 | { int ?+?( int, int ); int w, int ?-?( int, int ); }
     174\end{cfa}
     175creates a virtual table for @W0@ initialized with the matching @<@ and @+@
     176operations visible at this declaration context.  Similarly, @W1@ is initialized
     177with @<@ from inheritance with @W0@, @+@ is replaced, and @-@ is added, where
     178both operations are matched at this declaration context. It is important to
     179note that these are virtual members, not virtual methods of object-orientated
     180programming, and can be of any type. Finally, trait names can be used to
     181specify the list of virtual members.
     182
     183\PAB{Need to look at these when done.
     184
     185\CFA still supports virtual methods as a special case of virtual members.
     186Function pointers that take a pointer to the virtual type are modified
     187with each level of inheritance so that refers to the new type.
     188This means an object can always be passed to a function in its virtual table
     189as if it were a method.
     190\todo{Clarify (with an example) virtual methods.}
     191}%
    205192
    206193Up until this point the virtual system is similar to ones found in
    207 object-oriented languages but this is where \CFA diverges.
    208 Objects encapsulate a single set of methods in each type,
    209 universally across the entire program,
    210 and indeed all programs that use that type definition.
    211 The only way to change any method is to inherit and define a new type with
    212 its own universal implementation. In this sense,
    213 these object-oriented types are ``closed" and cannot be altered.
    214 % Because really they are class oriented.
    215 
    216 In \CFA, types do not encapsulate any code.
    217 Whether or not satisfies any given assertion, and hence any trait, is
    218 context sensitive. Types can begin to satisfy a trait, stop satisfying it or
    219 satisfy the same trait at any lexical location in the program.
    220 In this sense, an type's implementation in the set of functions and variables
    221 that allow it to satisfy a trait is ``open" and can change
    222 throughout the program.
     194object-orientated languages but this is where \CFA diverges. Objects encapsulate a
     195single set of methods in each type, universally across the entire program,
     196and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
     197single set of methods. In this sense,
     198object-oriented types are ``closed" and cannot be altered.
     199
     200In \CFA, types do not encapsulate any code. Traits are local for each function and
     201types can satisfy a local trait, stop satisfying it or, satisfy the same
     202trait in a different way at any lexical location in the program where a function is call.
     203In 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.
    223204This capability means it is impossible to pick a single set of functions
    224205that represent a type's implementation across a program.
    … …  
    227208type. A user can define virtual tables that are filled in at their
    228209declaration and given a name. Anywhere that name is visible, even if it is
    229 defined locally inside a function (although in this case the user must ensure
    230 it outlives any objects that use it), it can be used.
     210defined locally inside a function \PAB{What does this mean? (although that means it does not have a
     211static lifetime)}, it can be used.
    231212Specifically, a virtual type is ``bound" to a virtual table that
    232213sets the virtual members for that object. The virtual members can be accessed
    233214through the object.
    234 
    235 This means virtual tables are declared and named in \CFA.
    236 They are declared as variables, using the type
    237 @vtable(VIRTUAL_TYPE)@ and any valid name. For example:
    238 \begin{cfa}
    239 vtable(virtual_type_name) table_name;
    240 \end{cfa}
    241 
    242 Like any variable they may be forward declared with the @extern@ keyword.
    243 Forward declaring virtual tables is relatively common.
    244 Many virtual types have an ``obvious" implementation that works in most
    245 cases.
    246 A pattern that has appeared in the early work using virtuals is to
    247 implement a virtual table with the the obvious definition and place a forward
    248 declaration of it in the header beside the definition of the virtual type.
    249 
    250 Even on the full declaration, no initializer should be used.
    251 Initialization is automatic.
    252 The type id and special virtual members ``size" and ``align" only depend on
    253 the virtual type, which is fixed given the type of the virtual table and
    254 so the compiler fills in a fixed value.
    255 The other virtual members are resolved, using the best match to the member's
    256 name and type, in the same context as the virtual table is declared using
    257 \CFA's normal resolution rules.
    258215
    259216While much of the virtual infrastructure is created, it is currently only used
    … …  
    271228@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    272229
    273 \section{Exceptions}
    274 
    275 The syntax for declaring an exception is the same as declaring a structure
    276 except the keyword that is swapped out:
    277 \begin{cfa}
    278 exception TYPE_NAME {
    279         FIELDS
    280 };
    281 \end{cfa}
    282 
    283 Fields are filled in the same way as a structure as well. However an extra
    284 field is added, this field contains the pointer to the virtual table.
    285 It must be explicitly initialised by the user when the exception is
    286 constructed.
    287 
    288 Here is an example of declaring an exception type along with a virtual table,
    289 assuming the exception has an ``obvious" implementation and a default
    290 virtual table makes sense.
    291 
    292 \begin{minipage}[t]{0.4\textwidth}
    293 Header:
    294 \begin{cfa}
    295 exception Example {
    296         int data;
    297 };
    298 
    299 extern vtable(Example)
    300         example_base_vtable;
    301 \end{cfa}
    302 \end{minipage}
    303 \begin{minipage}[t]{0.6\textwidth}
    304 Source:
    305 \begin{cfa}
    306 vtable(Example) example_base_vtable
    307 \end{cfa}
    308 \vfil
    309 \end{minipage}
    310 
    311 %\subsection{Exception Details}
    312 If one is only raising and handling exceptions, that is the only interface
    313 that is needed. However it is actually a short hand for a more complex
    314 trait based interface.
    315 
    316 The language views exceptions through a series of traits,
     230\section{Exception}
     231% Leaving until later, hopefully it can talk about actual syntax instead
     232% of my many strange macros. Syntax aside I will also have to talk about the
     233% features all exceptions support.
     234
     235Exceptions are defined by the trait system; there are a series of traits, and
    317236if a type satisfies them, then it can be used as an exception. The following
    318237is the base trait all exceptions need to match.
    … …  
    328247completing the virtual system). The imaginary assertions would probably come
    329248from a trait defined by the virtual system, and state that the exception type
    330 is a virtual type, is a descendant of @exception_t@ (the base exception type)
    331 and allow the user to find the virtual table type.
     249is a virtual type, is a descendant of @exception_t@ (the base exception type),
     250and note its virtual table type.
    332251
    333252% I did have a note about how it is the programmer's responsibility to make
    … …  
    348267\end{cfa}
    349268Both traits ensure a pair of types are an exception type, its virtual table
    350 type
     269type,
    351270and defines one of the two default handlers. The default handlers are used
    352271as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
    … …  
    357276facing way. So these three macros are provided to wrap these traits to
    358277simplify referring to the names:
    359 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
     278@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
    360279
    361280All three take one or two arguments. The first argument is the name of the
    … …  
    380299These twin operations are the core of \CFA's exception handling mechanism.
    381300This section covers the general patterns shared by the two operations and
    382 then goes on to cover the details each individual operation.
     301then goes on to cover the details of each individual operation.
    383302
    384303Both operations follow the same set of steps.
    385304First, a user raises an exception.
    386 Second, the exception propagates up the stack, searching for a handler.
     305Second, the exception propagates up the stack.
    387306Third, if a handler is found, the exception is caught and the handler is run.
    388307After that control continues at a raise-dependent location.
    389 As an alternate to the third step,
    390 if a handler is not found, a default handler is run and, if it returns,
    391 then control
     308Fourth, if a handler is not found, a default handler is run and, if it returns, then control
    392309continues after the raise.
    393310
    394 The differences between the two operations include how propagation is
    395 performed, where excecution after an exception is handler
    396 and which default handler is run.
     311%This general description covers what the two kinds have in common.
     312The differences in the two operations include how propagation is performed, where execution continues
     313after an exception is caught and handled, and which default handler is run.
    397314
    398315\subsection{Termination}
    399316\label{s:Termination}
    400 Termination handling is the familiar kind of handling
    401 and used in most programming
     317Termination handling is the familiar EHM and used in most programming
    402318languages with exception handling.
    403319It is a dynamic, non-local goto. If the raised exception is matched and
    … …  
    431347Then propagation starts with the search. \CFA uses a ``first match" rule so
    432348matching is performed with the copied exception as the search key.
    433 It starts from the raise site and proceeds towards base of the stack,
     349It starts from the raise in the throwing function and proceeds towards the base of the stack,
    434350from callee to caller.
    435351At each stack frame, a check is made for termination handlers defined by the
    … …  
    445361\end{cfa}
    446362When viewed on its own, a try statement simply executes the statements
    447 in the \snake{GUARDED_BLOCK} and when those are finished,
     363in the \snake{GUARDED_BLOCK}, and when those are finished,
    448364the try statement finishes.
    449365
    … …  
    471387termination exception types.
    472388The global default termination handler performs a cancellation
    473 (as described in \vref{s:Cancellation})
    474 on the current stack with the copied exception.
    475 Since it is so general, a more specific handler can be defined,
    476 overriding the default behaviour for the specific exception types.
     389(see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
     390Since it is so general, a more specific handler is usually
     391defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
    477392
    478393\subsection{Resumption}
    479394\label{s:Resumption}
    480395
    481 Resumption exception handling is less familar form of exception handling,
    482 but is
     396Resumption exception handling is the less familar EHM, but is
    483397just as old~\cite{Goodenough75} and is simpler in many ways.
    484398It is a dynamic, non-local function call. If the raised exception is
    … …  
    489403function once the error is corrected, and
    490404ignorable events, such as logging where nothing needs to happen and control
    491 should always continue from the raise site.
    492 
    493 Except for the changes to fit into that pattern, resumption exception
    494 handling is symmetric with termination exception handling, by design
    495 (see \autoref{s:Termination}).
     405should always continue from the raise point.
    496406
    497407A resumption raise is started with the @throwResume@ statement:
    … …  
    500410\end{cfa}
    501411\todo{Decide on a final set of keywords and use them everywhere.}
    502 It works much the same way as the termination raise, except the
    503 type must satisfy the \snake{is_resumption_exception} that uses the
    504 default handler: \defaultResumptionHandler.
    505 This can be specialized for particular exception types.
    506 
    507 At run-time, no exception copy is made. Since
     412It works much the same way as the termination throw.
     413The expression must return a reference to a resumption exception,
     414where the resumption exception is any type that satisfies the trait
     415@is_resumption_exception@ at the call site.
     416The assertions from this trait are available to
     417the exception system while handling the exception.
     418
     419At run-time, no exception copy is made, since
    508420resumption does not unwind the stack nor otherwise remove values from the
    509 current scope, there is no need to manage memory to keep the exception
    510 allocated.
    511 
    512 Then propagation starts with the search,
    513 following the same search path as termination,
    514 from the raise site to the base of stack and top of try statement to bottom.
    515 However, the handlers on try statements are defined by @catchResume@ clauses.
     421current scope, so there is no need to manage memory to keep the exception in scope.
     422
     423Then propagation starts with the search. It starts from the raise in the
     424resuming function and proceeds towards the base of the stack,
     425from callee to caller.
     426At each stack frame, a check is made for resumption handlers defined by the
     427@catchResume@ clauses of a @try@ statement.
    516428\begin{cfa}
    517429try {
    … …  
    523435}
    524436\end{cfa}
    525 Note that termination handlers and resumption handlers may be used together
     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
     467The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
     468for resumption as for termination, as does exception matching at each
     469@catchResume@. Similarly, if no resumption handler is found during the search,
     470then the currently visible default handler (\defaultResumptionHandler) is
     471called and control continues after the raise statement if it returns. Finally,
     472there is also a global @defaultResumptionHandler@, which can be overridden,
     473that is polymorphic over all resumption exceptions but performs a termination
     474throw on the exception rather than a cancellation.
     475
     476Throwing the exception in @defaultResumptionHandler@ has the positive effect of
     477walking the stack a second time for a recovery handler. Hence, a programmer has
     478two chances for help with a problem, fixup or recovery, should either kind of
     479handler appear on the stack. However, this dual stack walk leads to following
     480apparent anomaly:
     481\begin{cfa}
     482try {
     483        throwResume E;
     484} catch (E) {
     485        // this handler runs
     486}
     487\end{cfa}
     488because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
     489matches with @catchResume@. The anomaly results because the unmatched
     490@catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
     491
     492% I wonder if there would be some good central place for this.
     493Note, termination and resumption handlers may be used together
    526494in a single try statement, intermixing @catch@ and @catchResume@ freely.
    527495Each type of handler only interacts with exceptions from the matching
    528496kind of raise.
    529 Like @catch@ clauses, @catchResume@ clauses have no effect if an exception
    530 is not raised.
    531 
    532 The matching rules are exactly the same as well.
    533 The first major difference here is that after
    534 @EXCEPTION_TYPE@$_i$ is matched and @NAME@$_i$ is bound to the exception,
    535 @HANDLER_BLOCK@$_i$ is executed right away without first unwinding the stack.
    536 After the block has finished running control jumps to the raise site, where
    537 the just handled exception came from, and continues executing after it,
    538 not after the try statement.
    539497
    540498\subsubsection{Resumption Marking}
    … …  
    544502and run, its try block (the guarded statements) and every try statement
    545503searched before it are still on the stack. There presence can lead to
    546 the recursive resumption problem.
    547 \todo{Is there a citation for the recursive resumption problem?}
     504the \emph{recursive resumption problem}.
    548505
    549506The recursive resumption problem is any situation where a resumption handler
    … …  
    559516When this code is executed, the guarded @throwResume@ starts a
    560517search and matches the handler in the @catchResume@ clause. This
    561 call is placed on the stack above the try-block.
    562 Now the second raise in the handler searches the same try block,
    563 matches again and then puts another instance of the
     518call is placed on the stack above the try-block. Now the second raise in the handler
     519searches the same try block, matches, and puts another instance of the
    564520same handler on the stack leading to infinite recursion.
    565521
    566 While this situation is trivial and easy to avoid, much more complex cycles
    567 can form with multiple handlers and different exception types.
     522While this situation is trivial and easy to avoid, much more complex cycles can
     523form with multiple handlers and different exception types.  The key point is
     524that the programmer's intuition expects every raise in a handler to start
     525searching \emph{below} the @try@ statement, making it difficult to understand
     526and fix the problem.
     527
    568528To prevent all of these cases, each try statement is ``marked" from the
    569 time the exception search reaches it to either when a handler completes
    570 handling that exception or when the search reaches the base
     529time the exception search reaches it to either when a matching handler
     530completes or when the search reaches the base
    571531of the stack.
    572532While a try statement is marked, its handlers are never matched, effectively
    … …  
    580540for instance, marking just the handlers that caught the exception,
    581541would also prevent recursive resumption.
    582 However, the rules selected mirrors what happens with termination,
    583 so this reduces the amount of rules and patterns a programmer has to know.
    584 
    585 The marked try statements are the ones that would be removed from
     542However, the rule selected mirrors what happens with termination,
     543and hence, matches programmer intuition that a raise searches below a try.
     544
     545In detail, the marked try statements are the ones that would be removed from
    586546the stack for a termination exception, \ie those on the stack
    587547between the handler and the raise statement.
    … …  
    649609
    650610\subsection{Comparison with Reraising}
    651 In languages without conditional catch, that is no ability to match an
    652 exception based on something other than its type, it can be mimicked
    653 by matching all exceptions of the right type, checking any additional
    654 conditions inside the handler and re-raising the exception if it does not
    655 match those.
    656 
    657 Here is a minimal example comparing both patterns, using @throw;@
    658 (no argument) to start a re-raise.
     611Without conditional catch, the only approach to match in more detail is to reraise
     612the exception after it has been caught, if it could not be handled.
    659613\begin{center}
    660 \begin{tabular}{l r}
    661 \begin{cfa}
    662 try {
    663     do_work_may_throw();
    664 } catch(exception_t * exc ;
    665                 can_handle(exc)) {
    666     handle(exc);
    667 }
    668 
    669 
    670 
     614\begin{tabular}{l|l}
     615\begin{cfa}
     616try {
     617        do_work_may_throw();
     618} catch(excep_t * ex; can_handle(ex)) {
     619
     620        handle(ex);
     621
     622
     623
     624}
    671625\end{cfa}
    672626&
    673627\begin{cfa}
    674628try {
    675     do_work_may_throw();
    676 } catch(exception_t * exc) {
    677     if (can_handle(exc)) {
    678         handle(exc);
    679     } else {
    680         throw;
    681     }
    682 }
    683 \end{cfa}
    684 \end{tabular}
    685 \end{center}
    686 At first glance catch-and-reraise may appear to just be a quality of life
    687 feature, but there are some significant differences between the two
    688 stratagies.
    689 
    690 A simple difference that is more important for \CFA than many other languages
    691 is that the raise site changes, with a re-raise but does not with a
    692 conditional catch.
    693 This is important in \CFA because control returns to the raise site to run
    694 the per-site default handler. Because of this only a conditional catch can
    695 allow the original raise to continue.
    696 
    697 The more complex issue comes from the difference in how conditional
    698 catches and re-raises handle multiple handlers attached to a single try
    699 statement. A conditional catch will continue checking later handlers while
    700 a re-raise will skip them.
    701 If the different handlers could handle some of the same exceptions,
    702 translating a try statement that uses one to use the other can quickly
    703 become non-trivial:
    704 
    705 \noindent
    706 Original, with conditional catch:
    707 \begin{cfa}
    708 ...
    709 } catch (an_exception * e ; check_a(e)) {
    710         handle_a(e);
    711 } catch (exception_t * e ; check_b(e)) {
    712         handle_b(e);
    713 }
    714 \end{cfa}
    715 Translated, with re-raise:
    716 \begin{cfa}
    717 ...
    718 } catch (exception_t * e) {
    719         an_exception * an_e = (virtual an_exception *)e;
    720         if (an_e && check_a(an_e)) {
    721                 handle_a(an_e);
    722         } else if (check_b(e)) {
    723                 handle_b(e);
     629        do_work_may_throw();
     630} catch(excep_t * ex) {
     631        if (can_handle(ex)) {
     632                handle(ex);
    724633        } else {
    725634                throw;
    … …  
    727636}
    728637\end{cfa}
    729 (There is a simpler solution if @handle_a@ never raises exceptions,
    730 using nested try statements.)
    731 
    732 % } catch (an_exception * e ; check_a(e)) {
    733 %     handle_a(e);
    734 % } catch (exception_t * e ; !(virtual an_exception *)e && check_b(e)) {
    735 %     handle_b(e);
    736 % }
     638\end{tabular}
     639\end{center}
     640Notice catch-and-reraise increases complexity by adding additional data and
     641code to the exception process. Nevertheless, catch-and-reraise can simulate
     642conditional catch straightforwardly, when exceptions are disjoint, \ie no
     643inheritance.
     644
     645However, catch-and-reraise simulation becomes unusable for exception inheritance.
     646\begin{flushleft}
     647\begin{cfa}[xleftmargin=6pt]
     648exception E1;
     649exception E2(E1); // inheritance
     650\end{cfa}
     651\begin{tabular}{l|l}
     652\begin{cfa}
     653try {
     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}
     667try {
     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}
     681The derived exception @E2@ must be ordered first in the catch list, otherwise
     682the 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
     685problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
     686reraise, and its handler must duplicate the inner handler code for @bar@. To
     687generalize, this fix for any amount of inheritance and complexity of try
     688statement requires a technique called \emph{try-block
     689splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
     690sufficient to state that conditional catch is more expressive than
     691catch-and-reraise in terms of complexity.
     692
     693\begin{comment}
     694That is, they have the same behaviour in isolation.
     695Two things can expose differences between these cases.
     696
     697One is the existence of multiple handlers on a single try statement.
     698A reraise skips all later handlers for a try statement but a conditional
     699catch does not.
     700% Hence, if an earlier handler contains a reraise later handlers are
     701% implicitly skipped, with a conditional catch they are not.
     702Still, they are equivalently powerful,
     703both can be used two mimic the behaviour of the other,
     704as reraise can pack arbitrary code in the handler and conditional catches
     705can put arbitrary code in the predicate.
     706% I was struggling with a long explanation about some simple solutions,
     707% like repeating a condition on later handlers, and the general solution of
     708% merging everything together. I don't think it is useful though unless its
     709% for a proof.
     710% https://en.cppreference.com/w/cpp/language/throw
     711
     712The question then becomes ``Which is a better default?"
     713We believe that not skipping possibly useful handlers is a better default.
     714If a handler can handle an exception it should and if the handler can not
     715handle the exception then it is probably safer to have that explicitly
     716described in the handler itself instead of implicitly described by its
     717ordering with other handlers.
     718% Or you could just alter the semantics of the throw statement. The handler
     719% index is in the exception so you could use it to know where to start
     720% searching from in the current try statement.
     721% No place for the `goto else;` metaphor.
     722
     723The other issue is all of the discussion above assumes that the only
     724way to tell apart two raises is the exception being raised and the remaining
     725search path.
     726This is not true generally, the current state of the stack can matter in
     727a number of cases, even only for a stack trace after an program abort.
     728But \CFA has a much more significant need of the rest of the stack, the
     729default handlers for both termination and resumption.
     730
     731% For resumption it turns out it is possible continue a raise after the
     732% exception has been caught, as if it hadn't been caught in the first place.
     733This becomes a problem combined with the stack unwinding used in termination
     734exception handling.
     735The stack is unwound before the handler is installed, and hence before any
     736reraises can run. So if a reraise happens the previous stack is gone,
     737the place on the stack where the default handler was supposed to run is gone,
     738if the default handler was a local function it may have been unwound too.
     739There is no reasonable way to restore that information, so the reraise has
     740to be considered as a new raise.
     741This is the strongest advantage conditional catches have over reraising,
     742they happen before stack unwinding and avoid this problem.
     743
     744% The one possible disadvantage of conditional catch is that it runs user
     745% code during the exception search. While this is a new place that user code
     746% can be run destructors and finally clauses are already run during the stack
     747% unwinding.
    737748%
    738 % } catch (an_exception * e)
    739 %   if (check_a(e)) {
    740 %     handle_a(e);
    741 %   } else throw;
    742 % } catch (exception_t * e)
    743 %   if (check_b(e)) {
    744 %     handle_b(e);
    745 %   } else throw;
    746 % }
    747 In similar simple examples translating from re-raise to conditional catch
    748 takes less code but it does not have a general trivial solution either.
    749 
    750 So, given that the two patterns do not trivially translate into each other,
    751 it becomes a matter of which on should be encouraged and made the default.
    752 From the premise that if a handler that could handle an exception then it
    753 should, it follows that checking as many handlers as possible is preferred.
    754 So conditional catch and checking later handlers is a good default.
     749% https://www.cplusplus.com/reference/exception/current_exception/
     750%   `exception_ptr current_exception() noexcept;`
     751% https://www.python.org/dev/peps/pep-0343/
     752\end{comment}
    755753
    756754\section{Finally Clauses}
    … …  
    768766The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    769767stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    770 finishes or during an unwind.
     768finishes, or during an unwind.
    771769The only time the block is not executed is if the program is exited before
    772770the stack is unwound.
    … …  
    788786they have their own strengths, similar to top-level function and lambda
    789787functions with closures.
    790 Destructors take more work to create, but if there is clean-up code
     788Destructors take more work for their creation, but if there is clean-up code
    791789that needs to be run every time a type is used, they are much easier
    792 to set-up for each use. % It's automatic.
     790to set-up.
    793791On the other hand finally clauses capture the local context, so is easy to
    794792use when the clean-up is not dependent on the type of a variable or requires
    … …  
    806804raise, this exception is not used in matching only to pass information about
    807805the cause of the cancellation.
    808 Finally, as no handler is provided, there is no default handler.
     806Finaly, since a cancellation only unwinds and forwards, there is no default handler.
    809807
    810808After @cancel_stack@ is called the exception is copied into the EHM's memory
    … …  
    817815After the main stack is unwound there is a program-level abort.
    818816
    819 The first reason for this behaviour is for sequential programs where there
    820 is only one stack, and hence to stack to pass information to.
    821 Second, even in concurrent programs, the main stack has no dependency
    822 on another stack and no reliable way to find another living stack.
    823 Finally, keeping the same behaviour in both sequential and concurrent
    824 programs is simple and easy to understand.
     817The reasons for this semantics in a sequential program is that there is no more code to execute.
     818This semantics also applies to concurrent programs, too, even if threads are running.
     819That is, if any threads starts a cancellation, it implies all threads terminate.
     820Keeping the same behaviour in sequential and concurrent programs is simple.
     821Also, even in concurrent programs there may not currently be any other stacks
     822and even if other stacks do exist, main has no way to know where they are.
    825823
    826824\paragraph{Thread Stack}
    … …  
    852850
    853851With explicit join and a default handler that triggers a cancellation, it is
    854 possible to cascade an error across any number of threads,
    855 alternating between the resumption (possibly termination) and cancellation,
    856 cleaning up each
     852possible to cascade an error across any number of threads, cleaning up each
    857853in turn, until the error is handled or the main thread is reached.
    858854
    … …  
    867863caller's context and passes it to the internal report.
    868864
    869 A coroutine only knows of two other coroutines,
    870 its starter and its last resumer.
     865A coroutine only knows of two other coroutines, its starter and its last resumer.
    871866The starter has a much more distant connection, while the last resumer just
    872867(in terms of coroutine state) called resume on this coroutine, so the message
    … …  
    874869
    875870With a default handler that triggers a cancellation, it is possible to
    876 cascade an error across any number of coroutines,
    877 alternating between the resumption (possibly termination) and cancellation,
    878 cleaning up each in turn,
     871cascade an error across any number of coroutines, cleaning up each in turn,
    879872until 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
     875talk about handling a cancellation in the last sentence. Which is correct?}

  • doc/theses/andrew_beach_MMath/intro.tex

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

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

    r1a6a6f2 r315e5e3  
    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}]{@}{@}}
    212214% Annotations from Peter:
    213215\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
Note: See TracChangeset for help on using the changeset viewer.