Changeset 9e67e92


Ignore:
Timestamp:
Jun 4, 2021, 4:59:34 PM (16 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
4969efd
Parents:
dad9c9f (diff), 4ed7946e (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/theses/andrew_beach_MMath
Files:
5 edited

Legend:

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

    rdad9c9f r9e67e92  
    11\chapter{\CFA Existing Features}
    2 
    3 \CFA (C-for-all)~\cite{Cforall} is an open-source project extending ISO C with
     2\label{c:existing}
     3
     4\CFA is an open-source project extending ISO C with
    45modern safety and productivity features, while still ensuring backwards
    56compatibility with C and its programmers.  \CFA is designed to have an
     
    89existing C code-base allowing programmers to learn \CFA on an as-needed basis.
    910
    10 Only those \CFA features pertinent to this thesis are discussed.  Many of the
     11Only those \CFA features pertaining to this thesis are discussed.  Many of the
    1112\CFA syntactic and semantic features used in the thesis should be fairly
    1213obvious to the reader.
     
    2829// name mangling on by default
    2930int i; // _X1ii_1
    30 extern "C" {  // disables name mangling
     31@extern "C"@ {  // disables name mangling
    3132        int j; // j
    32         extern "Cforall" {  // enables name mangling
     33        @extern "Cforall"@ {  // enables name mangling
    3334                int k; // _X1ki_1
    3435        }
     
    4445\CFA adds a reference type to C as an auto-dereferencing pointer.
    4546They work very similarly to pointers.
    46 Reference-types are written the same way as a pointer-type is but each
     47Reference-types are written the same way as a pointer-type but each
    4748asterisk (@*@) is replaced with a ampersand (@&@);
    48 this includes cv-qualifiers and multiple levels of reference.
    49 
    50 They are intended for cases where you would want to use pointers but would
    51 be dereferencing them (almost) every usage.
    52 In most cases a reference can just be thought of as a pointer that
    53 automatically puts a dereference infront of each of its uses (per-level of
    54 reference).
    55 The address-of operator (@&@) acts as an escape and removes one of the
    56 automatic dereference operations.
    57 Mutable references may be assigned to by converting them to a pointer
    58 with a @&@ and then assigning a pointer too them.
     49this includes cv-qualifiers and multiple levels of reference, \eg:
    5950
    6051\begin{minipage}{0,5\textwidth}
     
    6556int && rri = ri;
    6657rri = 3;
    67 &ri = &j;
     58&ri = &j; // reference assignment
    6859ri = 5;
    6960\end{cfa}
     
    7667int ** ppi = &pi;
    7768**ppi = 3;
    78 pi = &j;
     69pi = &j; // pointer assignment
    7970*pi = 5;
    8071\end{cfa}
    8172\end{minipage}
    8273
    83 \section{Constructors and Destructors}
    84 
    85 Both constructors and destructors are operators, which means they are
    86 functions with special operator names rather than type names in \Cpp. The
    87 special operator names may be used to call the functions explicitly (not
    88 allowed in \Cpp for constructors).
     74References are intended for cases where you would want to use pointers but would
     75be dereferencing them (almost) every usage.
     76In most cases a reference can just be thought of as a pointer that
     77automatically puts a dereference in front of each of its uses (per-level of
     78reference).
     79The address-of operator (@&@) acts as an escape and removes one of the
     80automatic dereference operations.
     81Mutable references may be assigned by converting them to a pointer
     82with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above.
     83
     84\section{Operators}
    8985
    9086In general, operator names in \CFA are constructed by bracketing an operator
     
    9490(such as @++?@) and post-fix operations (@?++@).
    9591
    96 The special name for a constructor is @?{}@, which comes from the
    97 initialization syntax in C. That initialation syntax is also the operator
    98 form. \CFA will generate a constructor call each time a variable is declared,
    99 passing the initialization arguments to the constructort.
    100 \begin{cfa}
    101 struct Example { ... };
    102 void ?{}(Example & this) { ... }
    103 {
    104         Example a;
    105         Example b = {};
    106 }
    107 void ?{}(Example & this, char first, int num) { ... }
    108 {
    109         Example c = {'a', 2};
    110 }
    111 \end{cfa}
    112 Both @a@ and @b@ will be initalized with the first constructor (there is no
    113 general way to skip initialation) while @c@ will be initalized with the
    114 second.
     92An operator name may describe any function signature (it is just a name) but
     93only certain signatures may be called in operator form.
     94\begin{cfa}
     95int ?+?( int i, int j, int k ) { return i + j + k; }
     96{
     97        sout | ?+?( 3, 4, 5 ); // no infix form
     98}
     99\end{cfa}
     100Some ``near-misses" for unary/binary operator prototypes generate warnings.
     101
     102Both constructors and destructors are operators, which means they are
     103functions with special operator names rather than type names in \Cpp. The
     104special operator names may be used to call the functions explicitly (not
     105allowed in \Cpp for constructors).
     106
     107The special name for a constructor is @?{}@, where the name @{}@ comes from the
     108initialization syntax in C, \eg @Structure s = {...}@.
     109% That initialization syntax is also the operator form.
     110\CFA generates a constructor call each time a variable is declared,
     111passing the initialization arguments to the constructor.
     112\begin{cfa}
     113struct Structure { ... };
     114void ?{}(Structure & this) { ... }
     115{
     116        Structure a;
     117        Structure b = {};
     118}
     119void ?{}(Structure & this, char first, int num) { ... }
     120{
     121        Structure c = {'a', 2};
     122}
     123\end{cfa}
     124Both @a@ and @b@ are initialized with the first constructor,
     125while @c@ is initialized with the second.
     126Currently, there is no general way to skip initialization.
    115127
    116128% I don't like the \^{} symbol but $^\wedge$ isn't better.
    117 Similarly destructors use the special name @^?{}@ (the @^@ has no special
    118 meaning). They can be called explicatly as well but normally they are
    119 implicitly called on a variable when it goes out of scope.
    120 \begin{cfa}
    121 void ^?{}(Example & this) { ... }
    122 {
    123     Example d;
     129Similarly, destructors use the special name @^?{}@ (the @^@ has no special
     130meaning).  Normally, they are implicitly called on a variable when it goes out
     131of scope but they can be called explicitly as well.
     132\begin{cfa}
     133void ^?{}(Structure & this) { ... }
     134{
     135        Structure d;
    124136} // <- implicit destructor call
    125137\end{cfa}
    126 No operator name is restricted in what function signatures they may be bound
    127 to although most of the forms cannot be called in operator form. Some
    128 ``near-misses" will generate warnings.
    129 
    130 Whenever a type is defined, \CFA will create a default zero-argument
     138
     139Whenever a type is defined, \CFA creates a default zero-argument
    131140constructor, a copy constructor, a series of argument-per-field constructors
    132141and a destructor. All user constructors are defined after this.
     
    152161char capital_a = identity( 'A' );
    153162\end{cfa}
    154 Each use of a polymorphic declaration will resolve its polymorphic parameters
     163Each use of a polymorphic declaration resolves its polymorphic parameters
    155164(in this case, just @T@) to concrete types (@int@ in the first use and @char@
    156165in the second).
     
    158167To allow a polymorphic function to be separately compiled, the type @T@ must be
    159168constrained by the operations used on @T@ in the function body. The @forall@
    160 clauses is augmented with a list of polymorphic variables (local type names)
     169clause is augmented with a list of polymorphic variables (local type names)
    161170and assertions (constraints), which represent the required operations on those
    162171types used in a function, \eg:
    163172\begin{cfa}
    164 forall( T | { void do_once(T); })
     173forall( T | { void do_once(T); } )
    165174void do_twice(T value) {
    166175        do_once(value);
     
    189198void do_once(double y) { ... }
    190199int quadruple(int x) {
    191         void do_once(int y) { y = y * 2; }
    192         do_twice(x);
     200        void do_once(int y) { y = y * 2; } // replace global do_once
     201        do_twice(x); // use local do_once
     202        do_twice(x + 1.5); // use global do_once
    193203        return x;
    194204}
    195205\end{cfa}
    196206Specifically, the complier deduces that @do_twice@'s T is an integer from the
    197 argument @x@. It then looks for the most specific definition matching the
     207argument @x@. It then looks for the most \emph{specific} definition matching the
    198208assertion, which is the nested integral @do_once@ defined within the
    199209function. The matched assertion function is then passed as a function pointer
    200 to @do_twice@ and called within it.
    201 The global definition of @do_once@ is ignored.
     210to @do_twice@ and called within it.  The global definition of @do_once@ is used
     211for the second call because the float-point argument is a better match.
    202212
    203213To avoid typing long lists of assertions, constraints can be collect into
     
    269279Each coroutine has a @main@ function, which takes a reference to a coroutine
    270280object and returns @void@.
    271 \begin{cfa}
     281\begin{cfa}[numbers=left]
    272282void main(CountUp & this) {
    273     for (unsigned int next = 0 ; true ; ++next) {
     283        for (unsigned int next = 0 ; true ; ++next) {
    274284                next = up;
    275285                suspend;$\label{suspend}$
  • doc/theses/andrew_beach_MMath/features.tex

    rdad9c9f r9e67e92  
    11\chapter{Exception Features}
     2\label{c:features}
    23
    34This chapter covers the design and user interface of the \CFA
    4 exception-handling mechanism (EHM). % or exception system.
    5 
    6 We will begin with an overview of EHMs in general. It is not a strict
    7 definition of all EHMs nor an exaustive list of all possible features.
    8 However it does cover the most common structure and features found in them.
     5EHM, % or exception system.
     6and begins with a general overview of EHMs. It is not a strict
     7definition of all EHMs nor an exhaustive list of all possible features.
     8However it does cover the most common structures and features found in them.
    99
    1010% We should cover what is an exception handling mechanism and what is an
    1111% exception before this. Probably in the introduction. Some of this could
    1212% move there.
    13 \paragraph{Raise / Handle}
     13\section{Raise / Handle}
    1414An exception operation has two main parts: raise and handle.
    1515These terms are sometimes also known as throw and catch but this work uses
    1616throw/catch as a particular kind of raise/handle.
    17 These are the two parts that the user will write themselves and may
     17These are the two parts that the user writes and may
    1818be the only two pieces of the EHM that have any syntax in the language.
    1919
    20 \subparagraph{Raise}
     20\paragraph{Raise}
    2121The raise is the starting point for exception handling. It marks the beginning
    22 of exception handling by raising an excepion, which passes it to
     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 from Python. In real systems a raise may
    27 preform some other work (such as memory management) but for the
     26the \code{Python}{raise} statement from Python. A raise may
     27perform some other work (such as memory management) but for the
    2828purposes of this overview that can be ignored.
    2929
    30 \subparagraph{Handle}
     30\paragraph{Handle}
    3131The purpose of most exception operations is to run some user code to handle
    3232that 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 they cover and an exception label/condition that matches
     35region of code they guard, and an exception label/condition that matches
    3636certain exceptions.
    37 Only raises inside the covered region and raising exceptions that match the
     37Only raises inside the guarded region and raising exceptions that match the
    3838label can be handled by a given handler.
    39 Different EHMs will have different rules to pick a handler
    40 if multipe handlers could be used such as ``best match" or ``first found".
     39Different EHMs have different rules to pick a handler,
     40if multiple handlers could be used, such as ``best match" or ``first found".
    4141
    4242The @try@ statements of \Cpp, Java and Python are common examples. All three
    43 also show another common feature of handlers, they are grouped by the covered
     43also show another common feature of handlers, they are grouped by the guarded
    4444region.
    4545
    46 \paragraph{Propagation}
     46\section{Propagation}
    4747After an exception is raised comes what is usually the biggest step for the
    48 EHM: finding and setting up the handler. The propogation from raise to
     48EHM: finding and setting up the handler. The propagation from raise to
    4949handler can be broken up into three different tasks: searching for a handler,
    50 matching against the handler and installing the handler.
    51 
    52 \subparagraph{Searching}
     50matching against the handler, and installing the handler.
     51
     52\paragraph{Searching}
    5353The EHM begins by searching for handlers that might be used to handle
    5454the exception. Searching is usually independent of the exception that was
    55 thrown as it looks for handlers that have the raise site in their covered
     55thrown as it looks for handlers that have the raise site in their guarded
    5656region.
    57 This includes handlers in the current function, as well as any in callers
    58 on the stack that have the function call in their covered region.
    59 
    60 \subparagraph{Matching}
     57This search includes handlers in the current function, as well as any in callers
     58on the stack that have the function call in their guarded region.
     59
     60\paragraph{Matching}
    6161Each handler found has to be matched with the raised exception. The exception
    62 label defines a condition that be use used with exception and decides if
     62label defines a condition that is used with the exception to decide if
    6363there is a match or not.
    6464
    65 In languages where the first match is used this step is intertwined with
    66 searching, a match check is preformed immediately after the search finds
     65In languages where the first match is used, this step is intertwined with
     66searching: a match check is performed immediately after the search finds
    6767a possible handler.
    6868
    69 \subparagraph{Installing}
     69\section{Installing}
    7070After a handler is chosen it must be made ready to run.
    7171The implementation can vary widely to fit with the rest of the
     
    7474case when stack unwinding is involved.
    7575
    76 If a matching handler is not guarantied to be found the EHM will need a
    77 different course of action here in the cases where no handler matches.
    78 This is only required with unchecked exceptions as checked exceptions
    79 (such as in Java) can make than guaranty.
    80 This different action can also be installing a handler but it is usually an
    81 implicat and much more general one.
    82 
    83 \subparagraph{Hierarchy}
     76If a matching handler is not guarantied to be found, the EHM needs a
     77different course of action for the case where no handler matches.
     78This situation only occurs with unchecked exceptions as checked exceptions
     79(such as in Java) can make the guarantee.
     80This unhandled action can abort the program or install a very general handler.
     81
     82\paragraph{Hierarchy}
    8483A common way to organize exceptions is in a hierarchical structure.
    85 This is especially true in object-orientated languages where the
     84This organization is often used in object-orientated languages where the
    8685exception hierarchy is a natural extension of the object hierarchy.
    8786
     
    112111
    113112The EHM can return control to many different places,
    114 the most common are after the handler definition and after the raise.
     113the most common are after the handler definition (termination) and after the raise (resumption).
    115114
    116115\paragraph{Communication}
    117116For effective exception handling, additional information is often passed
    118 from the raise to the handler.
     117from the raise to the handler and back again.
    119118So far only communication of the exceptions' identity has been covered.
    120 A common method is putting fields into the exception instance and giving the
    121 handler access to them.
     119A common communication method is putting fields into the exception instance and giving the
     120handler access to them. References in the exception instance can push data back to the raise.
    122121
    123122\section{Virtuals}
    124123Virtual types and casts are not part of \CFA's EHM nor are they required for
    125124any EHM.
    126 However the \CFA uses a hierarchy built with the virtual system as the basis
    127 for exceptions and exception matching.
    128 
    129 The virtual system would have ideally been part of \CFA before the work
     125However, one of the best ways to support an exception hierarchy is via a virtual system
     126among exceptions and used for exception matching.
     127
     128Ideally, the virtual system would have been part of \CFA before the work
    130129on exception handling began, but unfortunately it was not.
    131 Because of this only the features and framework needed for the EHM were
     130Therefore, only the features and framework needed for the EHM were
    132131designed and implemented. Other features were considered to ensure that
    133 the structure could accomidate other desirable features but they were not
     132the structure could accommodate other desirable features in the future but they were not
    134133implemented.
    135 The rest of this section will only discuss the finalized portion of the
    136 virtual system.
     134The rest of this section discusses the implemented subset of the
     135virtual-system design.
    137136
    138137The virtual system supports multiple ``trees" of types. Each tree is
     
    144143% A type's ancestors are its parent and its parent's ancestors.
    145144% The root type has no ancestors.
    146 % A type's decendents are its children and its children's decendents.
     145% A type's decedents are its children and its children's decedents.
    147146
    148147Every virtual type also has a list of virtual members. Children inherit
     
    150149It is important to note that these are virtual members, not virtual methods
    151150of object-orientated programming, and can be of any type.
     151
     152\PAB{I do not understand these sentences. Can you add an example? $\Rightarrow$
    152153\CFA still supports virtual methods as a special case of virtual members.
    153 Function pointers that take a pointer to the virtual type will be modified
     154Function pointers that take a pointer to the virtual type are modified
    154155with each level of inheritance so that refers to the new type.
    155156This means an object can always be passed to a function in its virtual table
    156 as if it were a method.
     157as if it were a method.}
    157158
    158159Each virtual type has a unique id.
    159 This unique id and all the virtual members are combined
     160This id and all the virtual members are combined
    160161into a virtual table type. Each virtual type has a pointer to a virtual table
    161162as a hidden field.
     163
     164\PAB{God forbid, maybe you need a UML diagram to relate these entities.}
    162165
    163166Up until this point the virtual system is similar to ones found in
    164167object-orientated languages but this where \CFA diverges. Objects encapsulate a
    165168single set of behaviours in each type, universally across the entire program,
    166 and indeed all programs that use that type definition. In this sense the
     169and indeed all programs that use that type definition. In this sense, the
    167170types are ``closed" and cannot be altered.
    168171
    169 In \CFA types do not encapsulate any behaviour. Traits are local and
    170 types can begin to statify a trait, stop satifying a trait or satify the same
     172In \CFA, types do not encapsulate any behaviour. Traits are local and
     173types can begin to satisfy a trait, stop satisfying a trait or satisfy the same
    171174trait in a different way at any lexical location in the program.
    172 In this sense they are ``open" as they can change at any time. This means it
    173 is implossible to pick a single set of functions that repersent the type's
     175In this sense, they are ``open" as they can change at any time. This capability means it
     176is impossible to pick a single set of functions that represent the type's
    174177implementation across the program.
    175178
    176179\CFA side-steps this issue by not having a single virtual table for each
    177 type. A user can define virtual tables which are filled in at their
    178 declaration and given a name. Anywhere that name is visible, even if it was
    179 defined locally inside a function (although that means it will not have a
     180type. A user can define virtual tables that are filled in at their
     181declaration and given a name. Anywhere that name is visible, even if
     182defined locally inside a function (although that means it does not have a
    180183static lifetime), it can be used.
    181 Specifically, a virtual type is ``bound" to a virtual table which
     184Specifically, a virtual type is ``bound" to a virtual table that
    182185sets the virtual members for that object. The virtual members can be accessed
    183186through the object.
    184187
     188\PAB{The above explanation is very good!}
     189
    185190While much of the virtual infrastructure is created, it is currently only used
    186191internally for exception handling. The only user-level feature is the virtual
    187 cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
     192cast
    188193\label{p:VirtualCast}
    189194\begin{cfa}
    190195(virtual TYPE)EXPRESSION
    191196\end{cfa}
     197which is the same as the \Cpp \code{C++}{dynamic_cast}.
    192198Note, the syntax and semantics matches a C-cast, rather than the function-like
    193199\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
     
    211217\end{cfa}
    212218The trait is defined over two types, the exception type and the virtual table
    213 type. Each exception type should have but a single virtual table type.
    214 Now there are no actual assertions in this trait because the trait system
    215 actually can't express them (adding such assertions would be part of
     219type. Each exception type should have a single virtual table type.
     220There are no actual assertions in this trait because currently the trait system
     221cannot express them (adding such assertions would be part of
    216222completing the virtual system). The imaginary assertions would probably come
    217223from a trait defined by the virtual system, and state that the exception type
    218 is a virtual type, is a decendent of @exception_t@ (the base exception type)
     224is a virtual type, is a descendent of @exception_t@ (the base exception type)
    219225and note its virtual table type.
    220226
     
    235241};
    236242\end{cfa}
    237 Both traits ensure a pair of types are an exception type and its virtual table
     243Both traits ensure a pair of types are an exception type and its virtual table,
    238244and defines one of the two default handlers. The default handlers are used
    239245as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
     
    263269\section{Exception Handling}
    264270\label{s:ExceptionHandling}
    265 \CFA provides two kinds of exception handling: termination and resumption.
     271As stated, \CFA provides two kinds of exception handling: termination and resumption.
    266272These twin operations are the core of \CFA's exception handling mechanism.
    267 This section will cover the general patterns shared by the two operations and
    268 then go on to cover the details each individual operation.
     273This section covers the general patterns shared by the two operations and
     274then go on to cover the details of each individual operation.
    269275
    270276Both operations follow the same set of steps.
    271 Both start with the user preforming a raise on an exception.
    272 Then the exception propogates up the stack.
     277Both start with the user performing a raise on an exception.
     278Then the exception propagates up the stack.
    273279If a handler is found the exception is caught and the handler is run.
    274 After that control returns to normal execution.
    275 If the search fails a default handler is run and then control
    276 returns to normal execution after the raise.
     280After that control returns to a point specific to the kind of exception.
     281If the search fails a default handler is run, and if it returns, control
     282continues after the raise. Note, the default handler may further change control flow rather than return.
    277283
    278284This general description covers what the two kinds have in common.
    279 Differences include how propogation is preformed, where exception continues
     285Differences include how propagation is performed, where exception continues
    280286after an exception is caught and handled and which default handler is run.
    281287
    282288\subsection{Termination}
    283289\label{s:Termination}
     290
    284291Termination handling is the familiar kind and used in most programming
    285292languages with exception handling.
    286 It is dynamic, non-local goto. If the raised exception is matched and
    287 handled the stack is unwound and control will (usually) continue the function
     293It is a dynamic, non-local goto. If the raised exception is matched and
     294handled, the stack is unwound and control (usually) continues in the function
    288295on the call stack that defined the handler.
    289296Termination is commonly used when an error has occurred and recovery is
     
    300307termination exception is any type that satisfies the trait
    301308@is_termination_exception@ at the call site.
    302 Through \CFA's trait system the trait functions are implicity passed into the
     309Through \CFA's trait system, the trait functions are implicitly passed into the
    303310throw code and the EHM.
    304311A new @defaultTerminationHandler@ can be defined in any scope to
    305 change the throw's behavior (see below).
    306 
    307 The throw will copy the provided exception into managed memory to ensure
    308 the exception is not destroyed if the stack is unwound.
     312change the throw's behaviour (see below).
     313
     314The throw copies the provided exception into managed memory to ensure
     315the exception is not destroyed when the stack is unwound.
    309316It is the user's responsibility to ensure the original exception is cleaned
    310 up wheither the stack is unwound or not. Allocating it on the stack is
     317up whether the stack is unwound or not. Allocating it on the stack is
    311318usually sufficient.
    312319
    313 Then propogation starts with the search. \CFA uses a ``first match" rule so
    314 matching is preformed with the copied exception as the search continues.
    315 It starts from the throwing function and proceeds to the base of the stack,
     320Then propagation starts the search. \CFA uses a ``first match" rule so
     321matching is performed with the copied exception as the search continues.
     322It starts from the throwing function and proceeds towards the base of the stack,
    316323from callee to caller.
    317324At each stack frame, a check is made for resumption handlers defined by the
     
    326333}
    327334\end{cfa}
    328 When viewed on its own, a try statement will simply execute the statements
    329 in \snake{GUARDED_BLOCK} and when those are finished the try statement finishes.
     335When viewed on its own, a try statement simply executes the statements
     336in \snake{GUARDED_BLOCK} and when those are finished, the try statement finishes.
    330337
    331338However, while the guarded statements are being executed, including any
    332 invoked functions, all the handlers in the statement are now on the search
    333 path. If a termination exception is thrown and not handled further up the
    334 stack they will be matched against the exception.
     339invoked functions, all the handlers in these statements are included on the search
     340path. Hence, if a termination exception is raised, the search includes the added handlers associated with the guarded block and those further up the
     341stack from the guarded block.
    335342
    336343Exception matching checks the handler in each catch clause in the order
    337 they appear, top to bottom. If the representation of the thrown exception type
     344they appear, top to bottom. If the representation of the raised exception type
    338345is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
    339 (if provided) is
    340 bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
    341 are executed. If control reaches the end of the handler, the exception is
     346(if provided) is bound to a pointer to the exception and the statements in
     347@HANDLER_BLOCK@$_i$ are executed.
     348If control reaches the end of the handler, the exception is
    342349freed and control continues after the try statement.
    343350
    344 If no termination handler is found during the search then the default handler
    345 (\defaultTerminationHandler) is run.
    346 Through \CFA's trait system the best match at the throw sight will be used.
    347 This function is run and is passed the copied exception. After the default
    348 handler is run control continues after the throw statement.
     351If no termination handler is found during the search, the default handler
     352(\defaultTerminationHandler) visible at the raise statement is called.
     353Through \CFA's trait system, the best match at the raise sight is used.
     354This function is run and is passed the copied exception. If the default
     355handler returns, control continues after the throw statement.
    349356
    350357There is a global @defaultTerminationHandler@ that is polymorphic over all
    351 exception types. Since it is so general a more specific handler can be
    352 defined and will be used for those types, effectively overriding the handler
    353 for particular exception type.
     358termination exception types. Since it is so general, a more specific handler can be
     359defined and is used for those types, effectively overriding the handler
     360for a particular exception type.
    354361The global default termination handler performs a cancellation
    355362(see \vref{s:Cancellation}) on the current stack with the copied exception.
     
    361368just as old~\cite{Goodenough75} and is simpler in many ways.
    362369It is a dynamic, non-local function call. If the raised exception is
    363 matched a closure will be taken from up the stack and executed,
    364 after which the raising function will continue executing.
    365 These are most often used when an error occurred and if the error is repaired
    366 then the function can continue.
     370matched a closure is taken from up the stack and executed,
     371after which the raising function continues executing.
     372These are most often used when a potentially repairable error occurs, some handler is found on the stack to fix it, and
     373the raising function can continue with the correction.
     374Another common usage is dynamic event analysis, \eg logging, without disrupting control flow.
     375Note, if an event is raised and there is no interest, control continues normally.
     376
     377\PAB{We also have \lstinline{report} instead of \lstinline{throwResume}, \lstinline{recover} instead of \lstinline{catch}, and \lstinline{fixup} instead of \lstinline{catchResume}.
     378You may or may not want to mention it. You can still stick with \lstinline{catch} and \lstinline{throw/catchResume} in the thesis.}
    367379
    368380A resumption raise is started with the @throwResume@ statement:
     
    375387@is_resumption_exception@ at the call site.
    376388The assertions from this trait are available to
    377 the exception system while handling the exception.
    378 
    379 At run-time, no exception copy is made.
    380 As the stack is not unwound the exception and
    381 any values on the stack will remain in scope while the resumption is handled.
     389the exception system, while handling the exception.
     390
     391Resumption does not need to copy the raised exception, as the stack is not unwound.
     392The exception and
     393any values on the stack remain in scope, while the resumption is handled.
    382394
    383395The EHM then begins propogation. The search starts from the raise in the
    384 resuming function and proceeds to the base of the stack, from callee to caller.
     396resuming function and proceeds towards the base of the stack, from callee to caller.
    385397At each stack frame, a check is made for resumption handlers defined by the
    386398@catchResume@ clauses of a @try@ statement.
     
    397409Note that termination handlers and resumption handlers may be used together
    398410in a single try statement, intermixing @catch@ and @catchResume@ freely.
    399 Each type of handler will only interact with exceptions from the matching
    400 type of raise.
    401 When a try statement is executed it simply executes the statements in the
    402 @GUARDED_BLOCK@ and then finishes.
     411Each type of handler only interacts with exceptions from the matching
     412kind of raise.
     413When a try statement is executed, it simply executes the statements in the
     414@GUARDED_BLOCK@ and then returns.
    403415
    404416However, while the guarded statements are being executed, including any
    405 invoked functions, all the handlers in the statement are now on the search
    406 path. If a resumption exception is reported and not handled further up the
    407 stack they will be matched against the exception.
     417invoked functions, all the handlers in these statements are included on the search
     418path. Hence, if a resumption exception is raised the search includes the added handlers associated with the guarded block and those further up the
     419stack from the guarded block.
    408420
    409421Exception matching checks the handler in each catch clause in the order
    410 they appear, top to bottom. If the representation of the thrown exception type
     422they appear, top to bottom. If the representation of the raised exception type
    411423is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
    412424(if provided) is bound to a pointer to the exception and the statements in
     
    415427the raise statement that raised the handled exception.
    416428
    417 Like termination, if no resumption handler is found, the default handler
    418 visible at the throw statement is called. It will use the best match at the
    419 call sight according to \CFA's overloading rules. The default handler is
     429Like termination, if no resumption handler is found during the search, the default handler
     430(\defaultResumptionHandler) visible at the raise statement is called.
     431It uses the best match at the
     432raise sight according to \CFA's overloading rules. The default handler is
    420433passed the exception given to the throw. When the default handler finishes
    421434execution continues after the raise statement.
    422435
    423 There is a global \defaultResumptionHandler{} is polymorphic over all
    424 termination exceptions and preforms a termination throw on the exception.
    425 The \defaultTerminationHandler{} for that raise is matched at the
    426 original raise statement (the resumption @throw@\-@Resume@) and it can be
     436There is a global \defaultResumptionHandler{} that is polymorphic over all
     437resumption exception types and preforms a termination throw on the exception.
     438The \defaultTerminationHandler{} can be
    427439customized by introducing a new or better match as well.
    428440
    429441\subsubsection{Resumption Marking}
    430442\label{s:ResumptionMarking}
     443
    431444A key difference between resumption and termination is that resumption does
    432445not unwind the stack. A side effect that is that when a handler is matched
    433 and run it's try block (the guarded statements) and every try statement
    434 searched before it are still on the stack. This can lead to the recursive
     446and run, its try block (the guarded statements) and every try statement
     447searched before it are still on the stack. Their existence can lead to the recursive
    435448resumption problem.
    436449
     
    445458}
    446459\end{cfa}
    447 When this code is executed the guarded @throwResume@ will throw, start a
    448 search and match the handler in the @catchResume@ clause. This will be
    449 call and placed on the stack on top of the try-block. The second throw then
    450 throws and will search the same try block and put call another instance of the
    451 same handler leading to an infinite loop.
    452 
    453 This situation is trivial and easy to avoid, but much more complex cycles
     460When this code is executed, the guarded @throwResume@ starts a
     461search and matchs the handler in the @catchResume@ clause. This
     462call is placed on the top of stack above the try-block. The second throw
     463searchs the same try block and puts call another instance of the
     464same handler on the stack leading to an infinite recursion.
     465
     466While this situation is trivial and easy to avoid, much more complex cycles
    454467can form with multiple handlers and different exception types.
    455468
    456 To prevent all of these cases we mark try statements on the stack.
     469To prevent all of these cases, the exception search marks the try statements it visits.
    457470A try statement is marked when a match check is preformed with it and an
    458 exception. The statement will be unmarked when the handling of that exception
     471exception. The statement is unmarked when the handling of that exception
    459472is completed or the search completes without finding a handler.
    460 While a try statement is marked its handlers are never matched, effectify
    461 skipping over it to the next try statement.
     473While a try statement is marked, its handlers are never matched, effectify
     474skipping over them to the next try statement.
    462475
    463476\begin{center}
     
    466479
    467480These rules mirror what happens with termination.
    468 When a termination throw happens in a handler the search will not look at
     481When a termination throw happens in a handler, the search does not look at
    469482any handlers from the original throw to the original catch because that
    470 part of the stack has been unwound.
     483part of the stack is unwound.
    471484A resumption raise in the same situation wants to search the entire stack,
    472 but it will not try to match the exception with try statements in the section
    473 that would have been unwound as they are marked.
    474 
    475 The symmetry between resumption termination is why this pattern was picked.
    476 Other patterns, such as marking just the handlers that caught, also work but
    477 lack the symmetry means there are more rules to remember.
     485but with marking, the search does match exceptions for try statements at equivalent sections
     486that would have been unwound by termination.
     487
     488The symmetry between resumption termination is why this pattern is picked.
     489Other patterns, such as marking just the handlers that caught the exception, also work but
     490lack the symmetry, meaning there are more rules to remember.
    478491
    479492\section{Conditional Catch}
     493
    480494Both termination and resumption handler clauses can be given an additional
    481495condition to further control which exceptions they handle:
     
    490504did not match.
    491505
    492 The condition matching allows finer matching by allowing the match to check
     506The condition matching allows finer matching to check
    493507more kinds of information than just the exception type.
    494508\begin{cfa}
     
    505519// Can't handle a failure relating to f2 here.
    506520\end{cfa}
    507 In this example the file that experianced the IO error is used to decide
     521In this example, the file that experianced the IO error is used to decide
    508522which handler should be run, if any at all.
    509523
     
    534548
    535549\subsection{Comparison with Reraising}
     550
    536551A more popular way to allow handlers to match in more detail is to reraise
    537 the exception after it has been caught if it could not be handled here.
     552the exception after it has been caught, if it could not be handled here.
    538553On the surface these two features seem interchangable.
    539554
    540 If we used @throw;@ to start a termination reraise then these two statements
    541 would have the same behaviour:
     555If @throw@ is used to start a termination reraise then these two statements
     556have the same behaviour:
    542557\begin{cfa}
    543558try {
     
    559574}
    560575\end{cfa}
    561 If there are further handlers after this handler only the first version will
    562 check them. If multiple handlers on a single try block that could handle the
    563 same exception the translations get more complex but they are equivilantly
    564 powerful.
    565 
    566 Until stack unwinding comes into the picture. In termination handling, a
     576However, if there are further handlers after this handler only the first is
     577check. For multiple handlers on a single try block that could handle the
     578same exception, the equivalent translations to conditional catch becomes more complex, resulting is multiple nested try blocks for all possible reraises.
     579So while catch-with-reraise is logically equivilant to conditional catch, there is a lexical explosion for the former.
     580
     581\PAB{I think the following discussion makes an incorrect assumption.
     582A conditional catch CAN happen with the stack unwound.
     583Roy talked about this issue in Section 2.3.3 here: \newline
     584\url{http://plg.uwaterloo.ca/theses/KrischerThesis.pdf}}
     585
     586Specifically for termination handling, a
    567587conditional catch happens before the stack is unwound, but a reraise happens
    568588afterwards. Normally this might only cause you to loose some debug
    569589information you could get from a stack trace (and that can be side stepped
    570590entirely by collecting information during the unwind). But for \CFA there is
    571 another issue, if the exception isn't handled the default handler should be
     591another issue, if the exception is not handled the default handler should be
    572592run at the site of the original raise.
    573593
    574 There are two problems with this: the site of the original raise doesn't
    575 exist anymore and the default handler might not exist anymore. The site will
    576 always be removed as part of the unwinding, often with the entirety of the
     594There are two problems with this: the site of the original raise does not
     595exist anymore and the default handler might not exist anymore. The site is
     596always removed as part of the unwinding, often with the entirety of the
    577597function it was in. The default handler could be a stack allocated nested
    578598function removed during the unwind.
     
    585605\section{Finally Clauses}
    586606\label{s:FinallyClauses}
     607
    587608Finally clauses are used to preform unconditional clean-up when leaving a
    588609scope and are placed at the end of a try statement after any handler clauses:
     
    597618The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    598619stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    599 finishes or during an unwind.
     620finishes, or during an unwind.
    600621The only time the block is not executed is if the program is exited before
    601622the stack is unwound.
     
    613634
    614635Not all languages with unwinding have finally clauses. Notably \Cpp does
    615 without it as descructors serve a similar role. Although destructors and
    616 finally clauses can be used in many of the same areas they have their own
    617 use cases like top-level functions and lambda functions with closures.
    618 Destructors take a bit more work to set up but are much easier to reuse while
    619 finally clauses are good for one-off uses and
    620 can easily include local information.
     636without it as destructors with RAII serve a similar role. Although destructors and
     637finally clauses have overlapping usage cases, they have their own
     638specializations, like top-level functions and lambda functions with closures.
     639Destructors take more work if a number of unrelated, local variables without destructors or dynamically allocated variables must be passed for de-intialization.
     640Maintaining this destructor during local-block modification is a source of errors.
     641A finally clause places local de-intialization inline with direct access to all local variables.
    621642
    622643\section{Cancellation}
     
    631652raise, this exception is not used in matching only to pass information about
    632653the cause of the cancellation.
    633 (This also means matching cannot fail so there is no default handler.)
     654(This restriction also means matching cannot fail so there is no default handler.)
    634655
    635656After @cancel_stack@ is called the exception is copied into the EHM's memory
    636657and the current stack is
    637 unwound. After that it depends one which stack is being cancelled.
     658unwound.
     659The result of a cancellation depends on the kind of stack that is being unwound.
    638660
    639661\paragraph{Main Stack}
     
    642664After the main stack is unwound there is a program-level abort.
    643665
    644 There are two reasons for this. The first is that it obviously had to do this
     666There are two reasons for this semantics. The first is that it obviously had to do the abort
    645667in a sequential program as there is nothing else to notify and the simplicity
    646668of keeping the same behaviour in sequential and concurrent programs is good.
    647 Also, even in concurrent programs there is no stack that an innate connection
    648 to, so it would have be explicitly managed.
     669\PAB{I do not understand this sentence. $\Rightarrow$ Also, even in concurrent programs, there is no stack that an innate connection
     670to, so it would have be explicitly managed.}
    649671
    650672\paragraph{Thread Stack}
    651673A thread stack is created for a \CFA @thread@ object or object that satisfies
    652674the @is_thread@ trait.
    653 After a thread stack is unwound there exception is stored until another
     675After a thread stack is unwound, the exception is stored until another
    654676thread attempts to join with it. Then the exception @ThreadCancelled@,
    655677which stores a reference to the thread and to the exception passed to the
    656 cancellation, is reported from the join.
     678cancellation, is reported from the join to the joining thread.
    657679There is one difference between an explicit join (with the @join@ function)
    658680and an implicit join (from a destructor call). The explicit join takes the
    659681default handler (@defaultResumptionHandler@) from its calling context while
    660 the implicit join provides its own which does a program abort if the
     682the implicit join provides its own, which does a program abort if the
    661683@ThreadCancelled@ exception cannot be handled.
    662684
    663 Communication is done at join because a thread only has to have to points of
    664 communication with other threads: start and join.
     685\PAB{Communication can occur during the lifetime of a thread using shared variable and \lstinline{waitfor} statements.
     686Are you sure you mean communication here? Maybe you mean synchronization (rendezvous) point. $\Rightarrow$ Communication is done at join because a thread only has two points of
     687communication with other threads: start and join.}
    665688Since a thread must be running to perform a cancellation (and cannot be
    666689cancelled from another stack), the cancellation must be after start and
    667 before the join. So join is the one that we will use.
     690before the join, so join is use.
    668691
    669692% TODO: Find somewhere to discuss unwind collisions.
     
    677700A coroutine stack is created for a @coroutine@ object or object that
    678701satisfies the @is_coroutine@ trait.
    679 After a coroutine stack is unwound control returns to the resume function
    680 that most recently resumed it. The resume statement reports a
    681 @CoroutineCancelled@ exception, which contains a references to the cancelled
     702After a coroutine stack is unwound, control returns to the @resume@ function
     703that most recently resumed it. The resume reports a
     704@CoroutineCancelled@ exception, which contains references to the cancelled
    682705coroutine and the exception used to cancel it.
    683 The resume function also takes the \defaultResumptionHandler{} from the
    684 caller's context and passes it to the internal report.
     706The @resume@ function also takes the \defaultResumptionHandler{} from the
     707caller's context and passes it to the internal cancellation.
    685708
    686709A coroutine knows of two other coroutines, its starter and its last resumer.
    687 The starter has a much more distant connection while the last resumer just
     710The starter has a much more distant connection, while the last resumer just
    688711(in terms of coroutine state) called resume on this coroutine, so the message
    689712is passed to the latter.
  • doc/theses/andrew_beach_MMath/future.tex

    rdad9c9f r9e67e92  
    11\chapter{Future Work}
     2\label{c:future}
    23
    34\section{Language Improvements}
  • doc/theses/andrew_beach_MMath/implement.tex

    rdad9c9f r9e67e92  
    11\chapter{Implementation}
    2 % Goes over how all the features are implemented.
     2\label{c:implement}
    33
    44The implementation work for this thesis covers two components: the virtual
  • doc/theses/andrew_beach_MMath/intro.tex

    rdad9c9f r9e67e92  
    11\chapter{Introduction}
    22
     3\PAB{Stay in the present tense. \newline
     4\url{https://plg.uwaterloo.ca/~pabuhr/technicalWriting.shtml}}
     5\newline
     6\PAB{Note, \lstinline{lstlisting} normally bolds keywords. None of the keywords in your thesis are bolded.}
     7
    38% Talk about Cforall and exceptions generally.
    4 This thesis goes over the design and implementation of the exception handling
    5 mechanism (EHM) of
    6 \CFA (pronounced see-for-all and also written Cforall or CFA).
    7 Exception handling provides more complex dynamic inter-function control flow.
    8 For example, normally function call is a strict linear form: function @h@ calls @g@,
    9 @g@ calls @f@, @f@ returns to @g@ and @g@ to @h@.
     9%This thesis goes over the design and implementation of the exception handling
     10%mechanism (EHM) of
     11%\CFA (pernounced sea-for-all and may be written Cforall or CFA).
     12Exception handling provides alternative dynamic inter-function control flow.
     13There are two forms of exception handling covered in this thesis:
     14termination, which acts as a multi-level return,
     15and resumption, which is a dynamic function call.
     16Note, termination exception handling is so common it is often assumed to be the only form.
     17Lesser know derivations of inter-function control flow are continuation passing in Lisp~\cite{CommonLisp}.
     18
     19Termination exception handling allows control to return to any previous
     20function on the stack directly, skipping any functions between it and the
     21current function.
    1022\begin{center}
    1123\input{callreturn}
    1224\end{center}
    13 Exception handling allows deviations,
    14 such as @f@ returning directly to @h@ and the intervening call to @g@ is unwound.
    15 Other derivations include dynamic function call (old Lisp~\cite{CommonLisp} call) versus static or continuation passing.
    16 Basically, any non-linear form of call-return can be part of an EHM.
    1725
    18 Although
    19 powerful, an EHM tends to be conceptually more complex and expensive to use, and hence often limited
    20 to unusual or ``exceptional" cases.
     26Resumption exception handling calls a function, but asks the functions on the
     27stack what function that is.
     28\todo{Add a diagram showing control flow for resumption.}
     29
     30Although a powerful feature, exception handling tends to be complex to set up
     31and expensive to use
     32so they are often limited to unusual or ``exceptional" cases.
    2133The classic example of this is error handling, exceptions can be used to
    22 remove error-handling logic from the main execution path and paying a higher
    23 performance cost only when the error actually occurs.
    24 
    25 \section{Background}
    26 
    27 Programming languages that provide different forms of EHM are: ...
    28 
    29 Mention the popular ``return union'' approach, which does not change the call/return control-flow.
    30 
    31 \section{New Work}
     34remove error handling logic from the main execution path and while paying
     35most of the cost only when the error actually occurs.
    3236
    3337% Overview of exceptions in Cforall.
    34 This thesis describes the design and implementation of the \CFA EHM.
    35 The work implements all of the common exception features (or an
     38
     39\PAB{You need section titles here. Don't take them out.}
     40
     41\section{Thesis Overview}
     42
     43This thesis goes over the design and implementation of the exception handling
     44mechanism (EHM) of
     45\CFA (pernounced sea-for-all and may be written Cforall or CFA).
     46%This thesis describes the design and implementation of the \CFA EHM.
     47The \CFA EHM implements all of the common exception features (or an
    3648equivalent) found in most other EHMs and adds some features of its own.
    3749The design of all the features had to be adapted to \CFA's feature set as
     
    5466% A note that yes, that was a very fast overview.
    5567The design and implementation of all of \CFA's EHM's features are
    56 described in detail throughout in this thesis, whether they are a common feature
     68described in detail throughout this thesis, whether they are a common feature
    5769or one unique to \CFA.
    5870
    5971% The current state of the project and what it contributes.
    6072All of these features have been implemented in \CFA, along with
    61 a suite of test cases, as part of this thesis.
     73a suite of test cases as part of this project.
    6274The implementation techniques are generally applicable in other programming
    63 languages and much of the design as well. Although some of \CFA's more unusual EHM feature
    64 would not be found in other programming languages.
     75languages and much of the design is as well.
     76Some parts of the EHM use other features unique to \CFA and these would be
     77harder to replicate in other programming languages.
     78
     79\section{Background}
     80
     81% Talk about other programming languages.
     82Some existing programming languages that include EHMs/exception handling
     83include C++, Java and Python. All three examples focus on termination
     84exceptions which unwind the stack as part of the
     85Exceptions also can replace return codes and return unions.
     86In functional languages will also sometimes fold exceptions into monads.
     87
     88\PAB{You must demonstrate knowledge of background material here.
     89It should be at least a full page.}
    6590
    6691\section{Contributions}
     
    6893The contributions of this work are:
    6994\begin{enumerate}
    70 \item
    71 \item
    72 \item
    73 \item
     95\item Designing \CFA's exception handling mechanism, adapting designs from
     96other programming languages and the creation of new features.
     97\item Implementing stack unwinding and the EHM in \CFA, including updating
     98the compiler and the run-time environment.
     99\item Designed and implemented a prototype virtual system.
     100% I think the virtual system and per-call site default handlers are the only
     101% "new" features, everything else is a matter of implementation.
    74102\end{enumerate}
    75103
    76 \section{Road Map}
     104\todo{I can't figure out a good lead-in to the overview.}
     105Covering the existing \CFA features in \autoref{c:existing}.
     106Then the new features are introduce in \autoref{c:features}, explaining their
     107usage and design.
     108That is followed by the implementation of those features in
     109\autoref{c:implement}.
     110% Future Work \autoref{c:future}
Note: See TracChangeset for help on using the changeset viewer.