Changeset b680198

Ignore:
Timestamp:
Jun 23, 2021, 2:06:12 PM (7 months ago)
Branches:
jacob/cs343-translation, master, new-ast-unique-expr
Children:
68b52b0
Parents:
6ba6846 (diff), 929d925 (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:
6 edited

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

 r6ba6846 \chapter{\CFA Existing Features} \chapter{\CFA{} Existing Features} \label{c:existing} existing C code-base allowing programmers to learn \CFA on an as-needed basis. Only those \CFA features pertaining to this thesis are discussed.  Many of the \CFA syntactic and semantic features used in the thesis should be fairly obvious to the reader. Only those \CFA features pertaining to this thesis are discussed. Also, only new features of \CFA will be discussed, a familiarity with C or C-like languages is assumed. \section{Overloading and \lstinline{extern}} // name mangling on by default int i; // _X1ii_1 @extern "C"@ {  // disables name mangling extern "C" {  // disables name mangling int j; // j @extern "Cforall"@ {  // enables name mangling extern "Cforall" {  // enables name mangling int k; // _X1ki_1 } Reference-types are written the same way as a pointer-type but each asterisk (@*@) is replaced with a ampersand (@&@); this includes cv-qualifiers and multiple levels of reference, \eg: this includes cv-qualifiers and multiple levels of reference. Generally, references act like pointers with an implicate dereferencing operation added to each use of the variable. These automatic dereferences may be disabled with the address-of operator (@&@). % Check to see if these are generating errors. \begin{minipage}{0,5\textwidth} With references: int && rri = ri; rri = 3; &ri = &j; // reference assignment &ri = &j; ri = 5; \end{cfa} int ** ppi = π **ppi = 3; pi = &j; // pointer assignment pi = &j; *pi = 5; \end{cfa} \end{minipage} References are intended for cases where you would want to use pointers but would References are intended to be used when you would use pointers but would be dereferencing them (almost) every usage. In most cases a reference can just be thought of as a pointer that automatically puts a dereference in front of each of its uses (per-level of reference). The address-of operator (@&@) acts as an escape and removes one of the automatic dereference operations. Mutable references may be assigned by converting them to a pointer with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above. Mutable references may be assigned to by converting them to a pointer with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above \section{Operators} In general, operator names in \CFA are constructed by bracketing an operator token with @?@, which indicates the position of the arguments. For example, \CFA implements operator overloading by providing special names. Operator uses are translated into function calls using these names. These names are created by taking the operator symbols and joining them with @?@s to show where the arguments go. For example, infixed multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it easy to tell the difference between prefix operations (such as @++?@) and post-fix operations (@?++@). An operator name may describe any function signature (it is just a name) but only certain signatures may be called in operator form. \begin{cfa} int ?+?( int i, int j, int k ) { return i + j + k; } { sout | ?+?( 3, 4, 5 ); // no infix form } \end{cfa} Some near-misses" for unary/binary operator prototypes generate warnings. \begin{cfa} point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; } bool ?==?(point a, point b) { return a.x == b.x && a.y == b.y; } { assert(point{1, 2} + point{3, 4} == point{4, 6}); } \end{cfa} Note that these special names are not limited to just being used for these operator functions, and may be used name other declarations. Some near misses", that will not match an operator form but looks like it may have been supposed to, will generate wantings but otherwise they are left alone. %\subsection{Constructors and Destructors} Both constructors and destructors are operators, which means they are functions with special operator names rather than type names in \Cpp. The special operator names may be used to call the functions explicitly (not allowed in \Cpp for constructors). The special name for a constructor is @?{}@, where the name @{}@ comes from the initialization syntax in C, \eg @Structure s = {...}@. % That initialization syntax is also the operator form. \CFA generates a constructor call each time a variable is declared, passing the initialization arguments to the constructor. \begin{cfa} struct Structure { ... }; void ?{}(Structure & this) { ... } { Structure a; Structure b = {}; } void ?{}(Structure & this, char first, int num) { ... } { Structure c = {'a', 2}; } \end{cfa} Both @a@ and @b@ are initialized with the first constructor, while @c@ is initialized with the second. Currently, there is no general way to skip initialization. special operator names may be used to call the functions explicitly. % Placement new means that this is actually equivant to C++. The special name for a constructor is @?{}@, which comes from the initialization syntax in C, \eg @Example e = { ... }@. \CFA will generate a constructor call each time a variable is declared, passing the initialization arguments to the constructort. \begin{cfa} struct Example { ... }; void ?{}(Example & this) { ... } { Example a; Example b = {}; } void ?{}(Example & this, char first, int num) { ... } { Example c = {'a', 2}; } \end{cfa} Both @a@ and @b@ will be initalized with the first constructor, while @c@ will be initalized with the second. Currently, there is no general way to skip initialation. % I don't like the \^{} symbol but $^\wedge$ isn't better. Similarly, destructors use the special name @^?{}@ (the @^@ has no special meaning).  Normally, they are implicitly called on a variable when it goes out of scope but they can be called explicitly as well. \begin{cfa} void ^?{}(Structure & this) { ... } { Structure d; Similarly destructors use the special name @^?{}@ (the @^@ has no special meaning). These are a normally called implicitly called on a variable when it goes out of scope. They can be called explicitly as well. \begin{cfa} void ^?{}(Example & this) { ... } { Example d; } // <- implicit destructor call \end{cfa} Whenever a type is defined, \CFA creates a default zero-argument Whenever a type is defined, \CFA will create a default zero-argument constructor, a copy constructor, a series of argument-per-field constructors and a destructor. All user constructors are defined after this. void do_once(double y) { ... } int quadruple(int x) { void do_once(int y) { y = y * 2; } // replace global do_once do_twice(x); // use local do_once do_twice(x + 1.5); // use global do_once void do_once(int & y) { y = y * 2; } do_twice(x); return x; } \end{cfa} Specifically, the complier deduces that @do_twice@'s T is an integer from the argument @x@. It then looks for the most \emph{specific} definition matching the argument @x@. It then looks for the most specific definition matching the assertion, which is the nested integral @do_once@ defined within the function. The matched assertion function is then passed as a function pointer to @do_twice@ and called within it.  The global definition of @do_once@ is used for the second call because the float-point argument is a better match. to @do_twice@ and called within it. The global definition of @do_once@ is ignored, however if quadruple took a @double@ argument then the global definition would be used instead as it would be a better match. % Aaron's thesis might be a good reference here. To avoid typing long lists of assertions, constraints can be collect into Each coroutine has a @main@ function, which takes a reference to a coroutine object and returns @void@. \begin{cfa}[numbers=left] %[numbers=left] Why numbers on this one? \begin{cfa} void main(CountUp & this) { for (unsigned int next = 0 ; true ; ++next) {
• doc/theses/andrew_beach_MMath/features.tex

 r6ba6846 \label{c:features} This chapter covers the design and user interface of the \CFA EHM, % or exception system. This chapter covers the design and user interface of the \CFA EHM and begins with a general overview of EHMs. It is not a strict definition of all EHMs nor an exhaustive list of all possible features. However it does cover the most common structures and features found in them. However it does cover the most common structure and features found in them. \section{Overview of EHMs} % We should cover what is an exception handling mechanism and what is an % exception before this. Probably in the introduction. Some of this could % move there. \section{Raise / Handle} \subsection{Raise / Handle} An exception operation has two main parts: raise and handle. These terms are sometimes also known as throw and catch but this work uses These terms are sometimes known as throw and catch but this work uses throw/catch as a particular kind of raise/handle. These are the two parts that the user writes and may Some well known examples include the @throw@ statements of \Cpp and Java and the \code{Python}{raise} statement from Python. A raise may perform some other work (such as memory management) but for the the \code{Python}{raise} statement from Python. In real systems a raise may preform some other work (such as memory management) but for the purposes of this overview that can be ignored. A handler has three common features: the previously mentioned user code, a region of code they guard, and an exception label/condition that matches region of code they guard and an exception label/condition that matches certain exceptions. Only raises inside the guarded region and raising exceptions that match the label can be handled by a given handler. Different EHMs have different rules to pick a handler, if multiple handlers could be used, such as best match" or first found". If multiple handlers could can handle an exception, EHMs will define a rule to pick one, such as best match" or first found". The @try@ statements of \Cpp, Java and Python are common examples. All three region. \section{Propagation} \subsection{Propagation} After an exception is raised comes what is usually the biggest step for the EHM: finding and setting up the handler. The propagation from raise to handler can be broken up into three different tasks: searching for a handler, matching against the handler, and installing the handler. matching against the handler and installing the handler. \paragraph{Searching} thrown as it looks for handlers that have the raise site in their guarded region. This search includes handlers in the current function, as well as any in callers on the stack that have the function call in their guarded region. The search includes handlers in the current function, as well as any in callers on the stack that have the function call in their guarded region. \paragraph{Matching} Each handler found has to be matched with the raised exception. The exception label defines a condition that is used with the exception to decide if label defines a condition that is used with exception and decides if there is a match or not. In languages where the first match is used, this step is intertwined with searching: a match check is performed immediately after the search finds searching; a match check is preformed immediately after the search finds a possible handler. \section{Installing} \paragraph{Installing} After a handler is chosen it must be made ready to run. The implementation can vary widely to fit with the rest of the case when stack unwinding is involved. If a matching handler is not guarantied to be found, the EHM needs a If a matching handler is not guaranteed to be found, the EHM needs a different course of action for the case where no handler matches. This situation only occurs with unchecked exceptions as checked exceptions (such as in Java) can make the guarantee. This unhandled action can abort the program or install a very general handler. This unhandled action is usually very general, such as aborting the program. \paragraph{Hierarchy} A common way to organize exceptions is in a hierarchical structure. This organization is often used in object-orientated languages where the This pattern comes from object-orientated languages where the exception hierarchy is a natural extension of the object hierarchy. \end{center} A handler labelled with any given exception can handle exceptions of that A handler labeled with any given exception can handle exceptions of that type or any child type of that exception. The root of the exception hierarchy (here \code{C}{exception}) acts as a catch-all, leaf types catch single types % Could I cite the rational for the Python IO exception rework? \paragraph{Completion} After the handler has finished the entire exception operation has to complete \subsection{Completion} After the handler has finished, the entire exception operation has to complete and continue executing somewhere else. This step is usually simple, both logically and in its implementation, as the installation of the handler The EHM can return control to many different places, the most common are after the handler definition (termination) and after the raise (resumption). \paragraph{Communication} the most common are after the handler definition (termination) and after the raise (resumption). \subsection{Communication} For effective exception handling, additional information is often passed from the raise to the handler and back again. So far only communication of the exceptions' identity has been covered. A common communication method is putting fields into the exception instance and giving the handler access to them. References in the exception instance can push data back to the raise. A common communication method is putting fields into the exception instance and giving the handler access to them. Passing the exception by reference instead of by value can allow data to be passed in both directions. \section{Virtuals} Virtual types and casts are not part of \CFA's EHM nor are they required for any EHM. However, one of the best ways to support an exception hierarchy is via a virtual system among exceptions and used for exception matching. However, it is one of the best ways to support an exception hierarchy is via a virtual hierarchy and dispatch system. Ideally, the virtual system would have been part of \CFA before the work on exception handling began, but unfortunately it was not. Therefore, only the features and framework needed for the EHM were Hence, only the features and framework needed for the EHM were designed and implemented. Other features were considered to ensure that the structure could accommodate other desirable features in the future but they were not implemented. The rest of this section discusses the implemented subset of the virtual-system design. the structure could accommodate other desirable features in the future but they were not implemented. The rest of this section will only discuss the implemented subset of the virtual system design. The virtual system supports multiple trees" of types. Each tree is % A type's ancestors are its parent and its parent's ancestors. % The root type has no ancestors. % A type's decedents are its children and its children's decedents. % A type's descendants are its children and its children's descendants. Every virtual type also has a list of virtual members. Children inherit of object-orientated programming, and can be of any type. \PAB{I do not understand these sentences. Can you add an example? $\Rightarrow$ \CFA still supports virtual methods as a special case of virtual members. Function pointers that take a pointer to the virtual type are modified with each level of inheritance so that refers to the new type. This means an object can always be passed to a function in its virtual table as if it were a method.} as if it were a method. \todo{Clarify (with an example) virtual methods.} Each virtual type has a unique id. into a virtual table type. Each virtual type has a pointer to a virtual table as a hidden field. \PAB{God forbid, maybe you need a UML diagram to relate these entities.} \todo{Might need a diagram for virtual structure.} Up until this point the virtual system is similar to ones found in types can begin to satisfy a trait, stop satisfying a trait or satisfy the same trait in a different way at any lexical location in the program. In this sense, they are open" as they can change at any time. This capability means it is impossible to pick a single set of functions that represent the type's implementation across the program. In this sense, they are open" as they can change at any time. This capability means it is impossible to pick a single set of functions that represent the type's implementation across the program. \CFA side-steps this issue by not having a single virtual table for each type. A user can define virtual tables that are filled in at their declaration and given a name. Anywhere that name is visible, even if declaration and given a name. Anywhere that name is visible, even if it is defined locally inside a function (although that means it does not have a static lifetime), it can be used. through the object. \PAB{The above explanation is very good!} While much of the virtual infrastructure is created, it is currently only used internally for exception handling. The only user-level feature is the virtual cast cast, which is the same as the \Cpp \code{C++}{dynamic_cast}. \label{p:VirtualCast} \begin{cfa} (virtual TYPE)EXPRESSION \end{cfa} which is the same as the \Cpp \code{C++}{dynamic_cast}. Note, the syntax and semantics matches a C-cast, rather than the function-like \Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be The trait is defined over two types, the exception type and the virtual table type. Each exception type should have a single virtual table type. There are no actual assertions in this trait because currently the trait system cannot express them (adding such assertions would be part of There are no actual assertions in this trait because the trait system cannot express them yet (adding such assertions would be part of completing the virtual system). The imaginary assertions would probably come from a trait defined by the virtual system, and state that the exception type is a virtual type, is a descendent of @exception_t@ (the base exception type) is a virtual type, is a descendant of @exception_t@ (the base exception type) and note its virtual table type. }; \end{cfa} Both traits ensure a pair of types are an exception type and its virtual table, Both traits ensure a pair of types are an exception type, its virtual table type and defines one of the two default handlers. The default handlers are used as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}. \section{Exception Handling} \label{s:ExceptionHandling} As stated, \CFA provides two kinds of exception handling: termination and resumption. As stated, \CFA provides two kinds of exception handling: termination and resumption. These twin operations are the core of \CFA's exception handling mechanism. This section covers the general patterns shared by the two operations and then go on to cover the details of each individual operation. This section will cover the general patterns shared by the two operations and then go on to cover the details each individual operation. Both operations follow the same set of steps. Both start with the user performing a raise on an exception. Both start with the user preforming a raise on an exception. Then the exception propagates up the stack. If a handler is found the exception is caught and the handler is run. After that control returns to a point specific to the kind of exception. If the search fails a default handler is run, and if it returns, control continues after the raise. Note, the default handler may further change control flow rather than return. After that control continues at a raise-dependent location. If the search fails a default handler is run and, if it returns, then control continues after the raise. This general description covers what the two kinds have in common. Differences include how propagation is performed, where exception continues Differences include how propagation is preformed, where exception continues after an exception is caught and handled and which default handler is run. \subsection{Termination} \label{s:Termination} Termination handling is the familiar kind and used in most programming languages with exception handling. The throw copies the provided exception into managed memory to ensure the exception is not destroyed when the stack is unwound. the exception is not destroyed if the stack is unwound. It is the user's responsibility to ensure the original exception is cleaned up whether the stack is unwound or not. Allocating it on the stack is usually sufficient. Then propagation starts the search. \CFA uses a first match" rule so matching is performed with the copied exception as the search continues. It starts from the throwing function and proceeds towards the base of the stack, % How to say propagation starts, its first sub-step is the search. Then propagation starts with the search. \CFA uses a first match" rule so matching is preformed with the copied exception as the search continues. It starts from the throwing function and proceeds towards base of the stack, from callee to caller. At each stack frame, a check is made for resumption handlers defined by the \end{cfa} When viewed on its own, a try statement simply executes the statements in \snake{GUARDED_BLOCK} and when those are finished, the try statement finishes. in \snake{GUARDED_BLOCK} and when those are finished, the try statement finishes. However, while the guarded statements are being executed, including any invoked functions, all the handlers in these statements are included on the search path. Hence, if a termination exception is raised, the search includes the added handlers associated with the guarded block and those further up the stack from the guarded block. invoked functions, all the handlers in these statements are included in the search path. Hence, if a termination exception is raised these handlers may be matched against the exception and may handle it. Exception matching checks the handler in each catch clause in the order they appear, top to bottom. If the representation of the raised exception type is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ (if provided) is bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$ are executed. If control reaches the end of the handler, the exception is (if provided) is bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$ are executed. If control reaches the end of the handler, the exception is freed and control continues after the try statement. If no termination handler is found during the search, the default handler (\defaultTerminationHandler) visible at the raise statement is called. Through \CFA's trait system, the best match at the raise sight is used. This function is run and is passed the copied exception. If the default handler returns, control continues after the throw statement. If no termination handler is found during the search then the default handler (\defaultTerminationHandler) visible at the raise statement is run. Through \CFA's trait system the best match at the raise statement will be used. This function is run and is passed the copied exception. If the default handler is run control continues after the raise statement. There is a global @defaultTerminationHandler@ that is polymorphic over all termination exception types. Since it is so general, a more specific handler can be termination exception types. Since it is so general a more specific handler can be defined and is used for those types, effectively overriding the handler for a particular exception type. matched a closure is taken from up the stack and executed, after which the raising function continues executing. These are most often used when a potentially repairable error occurs, some handler is found on the stack to fix it, and the raising function can continue with the correction. Another common usage is dynamic event analysis, \eg logging, without disrupting control flow. Note, if an event is raised and there is no interest, control continues normally. \PAB{We also have \lstinline{report} instead of \lstinline{throwResume}, \lstinline{recover} instead of \lstinline{catch}, and \lstinline{fixup} instead of \lstinline{catchResume}. You may or may not want to mention it. You can still stick with \lstinline{catch} and \lstinline{throw/catchResume} in the thesis.} The common uses for resumption exceptions include potentially repairable errors, where execution can continue in the same function once the error is corrected, and ignorable events, such as logging where nothing needs to happen and control should always continue from the same place. A resumption raise is started with the @throwResume@ statement: throwResume EXPRESSION; \end{cfa} \todo{Decide on a final set of keywords and use them everywhere.} It works much the same way as the termination throw. The expression must return a reference to a resumption exception, @is_resumption_exception@ at the call site. The assertions from this trait are available to the exception system, while handling the exception. Resumption does not need to copy the raised exception, as the stack is not unwound. The exception and any values on the stack remain in scope, while the resumption is handled. The EHM then begins propogation. The search starts from the raise in the resuming function and proceeds towards the base of the stack, from callee to caller. the exception system while handling the exception. At run-time, no exception copy is made. Resumption does not unwind the stack nor otherwise remove values from the current scope, so there is no need to manage memory to keep things in scope. The EHM then begins propagation. The search starts from the raise in the resuming function and proceeds towards the base of the stack, from callee to caller. At each stack frame, a check is made for resumption handlers defined by the @catchResume@ clauses of a @try@ statement. kind of raise. When a try statement is executed, it simply executes the statements in the @GUARDED_BLOCK@ and then returns. @GUARDED_BLOCK@ and then finishes. However, while the guarded statements are being executed, including any invoked functions, all the handlers in these statements are included on the search path. Hence, if a resumption exception is raised the search includes the added handlers associated with the guarded block and those further up the stack from the guarded block. invoked functions, all the handlers in these statements are included in the search path. Hence, if a resumption exception is raised these handlers may be matched against the exception and may handle it. Exception matching checks the handler in each catch clause in the order the raise statement that raised the handled exception. Like termination, if no resumption handler is found during the search, the default handler (\defaultResumptionHandler) visible at the raise statement is called. It uses the best match at the raise sight according to \CFA's overloading rules. The default handler is passed the exception given to the throw. When the default handler finishes Like termination, if no resumption handler is found during the search, the default handler (\defaultResumptionHandler) visible at the raise statement is called. It will use the best match at the raise sight according to \CFA's overloading rules. The default handler is passed the exception given to the raise. When the default handler finishes execution continues after the raise statement. There is a global \defaultResumptionHandler{} that is polymorphic over all resumption exception types and preforms a termination throw on the exception. The \defaultTerminationHandler{} can be customized by introducing a new or better match as well. There is a global \defaultResumptionHandler{} is polymorphic over all resumption exceptions and preforms a termination throw on the exception. The \defaultTerminationHandler{} can be overridden by providing a new function that is a better match. \subsubsection{Resumption Marking} \label{s:ResumptionMarking} A key difference between resumption and termination is that resumption does not unwind the stack. A side effect that is that when a handler is matched and run, its try block (the guarded statements) and every try statement searched before it are still on the stack. Their existence can lead to the recursive resumption problem. and run it's try block (the guarded statements) and every try statement searched before it are still on the stack. There presence can lead to the recursive resumption problem. The recursive resumption problem is any situation where a resumption handler \end{cfa} When this code is executed, the guarded @throwResume@ starts a search and matchs the handler in the @catchResume@ clause. This call is placed on the top of stack above the try-block. The second throw searchs the same try block and puts call another instance of the same handler on the stack leading to an infinite recursion. search and matches the handler in the @catchResume@ clause. This call is placed on the stack above the try-block. The second raise then searches the same try block and puts another instance of the same handler on the stack leading to infinite recursion. While this situation is trivial and easy to avoid, much more complex cycles can form with multiple handlers and different exception types. To prevent all of these cases, the exception search marks the try statements it visits. A try statement is marked when a match check is preformed with it and an exception. The statement is unmarked when the handling of that exception is completed or the search completes without finding a handler. While a try statement is marked, its handlers are never matched, effectify skipping over them to the next try statement. To prevent all of these cases, a each try statement is marked" from the time the exception search reaches it to either when the exception is being handled completes the matching handler or when the search reaches the base of the stack. While a try statement is marked, its handlers are never matched, effectively skipping over it to the next try statement. \begin{center} \end{center} These rules mirror what happens with termination. When a termination throw happens in a handler, the search does not look at any handlers from the original throw to the original catch because that part of the stack is unwound. A resumption raise in the same situation wants to search the entire stack, but with marking, the search does match exceptions for try statements at equivalent sections that would have been unwound by termination. The symmetry between resumption termination is why this pattern is picked. Other patterns, such as marking just the handlers that caught the exception, also work but lack the symmetry, meaning there are more rules to remember. There are other sets of marking rules that could be used, for instance, marking just the handlers that caught the exception, would also prevent recursive resumption. However, these rules mirror what happens with termination. The try statements that are marked are the ones that would be removed from the stack if this was a termination exception, that is those on the stack between the handler and the raise statement. This symmetry applies to the default handler as well, as both kinds of default handlers are run at the raise statement, rather than (physically or logically) at the bottom of the stack. % In early development having the default handler happen after % unmarking was just more useful. We assume that will continue. \section{Conditional Catch} Both termination and resumption handler clauses can be given an additional condition to further control which exceptions they handle: did not match. The condition matching allows finer matching to check The condition matching allows finer matching by checking more kinds of information than just the exception type. \begin{cfa} // Can't handle a failure relating to f2 here. \end{cfa} In this example, the file that experianced the IO error is used to decide In this example the file that experienced the IO error is used to decide which handler should be run, if any at all. \subsection{Comparison with Reraising} A more popular way to allow handlers to match in more detail is to reraise the exception after it has been caught, if it could not be handled here. On the surface these two features seem interchangable. If @throw@ is used to start a termination reraise then these two statements have the same behaviour: On the surface these two features seem interchangeable. If @throw;@ (no argument) starts a termination reraise, which is the same as a raise but reuses the last caught exception, then these two statements have the same behaviour: \begin{cfa} try { } \end{cfa} However, if there are further handlers after this handler only the first is check. For multiple handlers on a single try block that could handle the same exception, the equivalent translations to conditional catch becomes more complex, resulting is multiple nested try blocks for all possible reraises. So while catch-with-reraise is logically equivilant to conditional catch, there is a lexical explosion for the former. \PAB{I think the following discussion makes an incorrect assumption. A conditional catch CAN happen with the stack unwound. Roy talked about this issue in Section 2.3.3 here: \newline \url{http://plg.uwaterloo.ca/theses/KrischerThesis.pdf}} Specifically for termination handling, a conditional catch happens before the stack is unwound, but a reraise happens afterwards. Normally this might only cause you to loose some debug information you could get from a stack trace (and that can be side stepped entirely by collecting information during the unwind). But for \CFA there is another issue, if the exception is not handled the default handler should be run at the site of the original raise. There are two problems with this: the site of the original raise does not exist anymore and the default handler might not exist anymore. The site is always removed as part of the unwinding, often with the entirety of the function it was in. The default handler could be a stack allocated nested function removed during the unwind. This means actually trying to pretend the catch didn't happening, continuing the original raise instead of starting a new one, is infeasible. That is the expected behaviour for most languages and we can't replicate that behaviour. That is, they will have the same behaviour in isolation. Two things can expose differences between these cases. One is the existence of multiple handlers on a single try statement. A reraise skips all later handlers on this try statement but a conditional catch does not. Hence, if an earlier handler contains a reraise later handlers are implicitly skipped, with a conditional catch they are not. Still, they are equivalently powerful, both can be used two mimic the behaviour of the other, as reraise can pack arbitrary code in the handler and conditional catches can put arbitrary code in the predicate. % I was struggling with a long explanation about some simple solutions, % like repeating a condition on later handlers, and the general solution of % merging everything together. I don't think it is useful though unless its % for a proof. % https://en.cppreference.com/w/cpp/language/throw The question then becomes Which is a better default?" We believe that not skipping possibly useful handlers is a better default. If a handler can handle an exception it should and if the handler can not handle the exception then it is probably safer to have that explicitly described in the handler itself instead of implicitly described by its ordering with other handlers. % Or you could just alter the semantics of the throw statement. The handler % index is in the exception so you could use it to know where to start % searching from in the current try statement. % No place for the goto else; metaphor. The other issue is all of the discussion above assumes that the only way to tell apart two raises is the exception being raised and the remaining search path. This is not true generally, the current state of the stack can matter in a number of cases, even only for a stack trace after an program abort. But \CFA has a much more significant need of the rest of the stack, the default handlers for both termination and resumption. % For resumption it turns out it is possible continue a raise after the % exception has been caught, as if it hadn't been caught in the first place. This becomes a problem combined with the stack unwinding used in termination exception handling. The stack is unwound before the handler is installed, and hence before any reraises can run. So if a reraise happens the previous stack is gone, the place on the stack where the default handler was supposed to run is gone, if the default handler was a local function it may have been unwound too. There is no reasonable way to restore that information, so the reraise has to be considered as a new raise. This is the strongest advantage conditional catches have over reraising, they happen before stack unwinding and avoid this problem. % The one possible disadvantage of conditional catch is that it runs user % code during the exception search. While this is a new place that user code % can be run destructors and finally clauses are already run during the stack % unwinding. % % https://www.cplusplus.com/reference/exception/current_exception/ %   exception_ptr current_exception() noexcept; % https://www.python.org/dev/peps/pep-0343/ \section{Finally Clauses} \label{s:FinallyClauses} Finally clauses are used to preform unconditional clean-up when leaving a scope and are placed at the end of a try statement after any handler clauses: The @FINALLY_BLOCK@ is executed when the try statement is removed from the stack, including when the @GUARDED_BLOCK@ finishes, any termination handler finishes, or during an unwind. finishes or during an unwind. The only time the block is not executed is if the program is exited before the stack is unwound. Not all languages with unwinding have finally clauses. Notably \Cpp does without it as destructors with RAII serve a similar role. Although destructors and finally clauses have overlapping usage cases, they have their own specializations, like top-level functions and lambda functions with closures. Destructors take more work if a number of unrelated, local variables without destructors or dynamically allocated variables must be passed for de-intialization. Maintaining this destructor during local-block modification is a source of errors. A finally clause places local de-intialization inline with direct access to all local variables. without it as descructors, and the RAII design pattern, serve a similar role. Although destructors and finally clauses can be used in the same cases, they have their own strengths, similar to top-level function and lambda functions with closures. Destructors take more work for their first use, but if there is clean-up code that needs to be run every time a type is used they soon become much easier to set-up. On the other hand finally clauses capture the local context, so is easy to use when the clean-up is not dependent on the type of a variable or requires information from multiple variables. % To Peter: I think these are the main points you were going for. \section{Cancellation} raise, this exception is not used in matching only to pass information about the cause of the cancellation. (This restriction also means matching cannot fail so there is no default handler.) (This also means matching cannot fail so there is no default handler.) After @cancel_stack@ is called the exception is copied into the EHM's memory and the current stack is unwound. The result of a cancellation depends on the kind of stack that is being unwound. and the current stack is unwound. The behaviour after that depends on the kind of stack being cancelled. \paragraph{Main Stack} After the main stack is unwound there is a program-level abort. There are two reasons for this semantics. The first is that it obviously had to do the abort There are two reasons for these semantics. The first is that it had to do this abort. in a sequential program as there is nothing else to notify and the simplicity of keeping the same behaviour in sequential and concurrent programs is good. \PAB{I do not understand this sentence. $\Rightarrow$ Also, even in concurrent programs, there is no stack that an innate connection to, so it would have be explicitly managed.} Also, even in concurrent programs there may not currently be any other stacks and even if other stacks do exist, main has no way to know where they are. \paragraph{Thread Stack} and an implicit join (from a destructor call). The explicit join takes the default handler (@defaultResumptionHandler@) from its calling context while the implicit join provides its own, which does a program abort if the the implicit join provides its own; which does a program abort if the @ThreadCancelled@ exception cannot be handled. \PAB{Communication can occur during the lifetime of a thread using shared variable and \lstinline{waitfor} statements. Are 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 communication with other threads: start and join.} The communication and synchronization are done here because threads only have two structural points (not dependent on user-code) where communication/synchronization happens: start and join. Since a thread must be running to perform a cancellation (and cannot be cancelled from another stack), the cancellation must be after start and before the join, so join is use. before the join, so join is used. % TODO: Find somewhere to discuss unwind collisions. a destructor and prevents cascading the error across multiple threads if the user is not equipped to deal with it. Also you can always add an explicit join if that is the desired behaviour. It is always possible to add an explicit join if that is the desired behaviour. With explicit join and a default handler that triggers a cancellation, it is possible to cascade an error across any number of threads, cleaning up each in turn, until the error is handled or the main thread is reached. \paragraph{Coroutine Stack} satisfies the @is_coroutine@ trait. After a coroutine stack is unwound, control returns to the @resume@ function that most recently resumed it. The resume reports a @CoroutineCancelled@ exception, which contains references to the cancelled that most recently resumed it. @resume@ reports a @CoroutineCancelled@ exception, which contains a references to the cancelled coroutine and the exception used to cancel it. The @resume@ function also takes the \defaultResumptionHandler{} from the caller's context and passes it to the internal cancellation. caller's context and passes it to the internal report. A coroutine knows of two other coroutines, its starter and its last resumer. (in terms of coroutine state) called resume on this coroutine, so the message is passed to the latter. With a default handler that triggers a cancellation, it is possible to cascade an error across any number of coroutines, cleaning up each in turn, until the error is handled or a thread stack is reached.
• doc/theses/andrew_beach_MMath/future.tex

 r6ba6846 \section{Language Improvements} \todo{Future/Language Improvements seems to have gotten mixed up. It is presented as waiting on language improvements" but really its more non-research based impovements.} \CFA is a developing programming language. As such, there are partially or unimplemented features of the language (including several broken components) \item The implementation of termination is not portable because it includes hand-crafted assembly statements. These sections must be ported by hand to hand-crafted assembly statements. The existing compilers cannot translate that for other platforms and those sections must be ported by hand to support more hardware architectures, such as the ARM processor. \PAB{I think this is a straw-man problem because the hand-coded assembler code has to be generated somewhere, and that somewhere is hand-coded.} \item Due to a type-system problem, the catch clause cannot bind the exception to a There is no detection of colliding unwinds. It is possible for clean-up code run during an unwind to trigger another unwind that escapes the clean-up code itself, \eg, a termination exception caught further down the stack or a cancellation. There do exist ways to handle this issue, but currently they are not even detected and the first unwind is simply dropped, often leaving it in a bad state. \Cpp terminates the program in this case, and Java picks the ... itself; such as a termination exception caught further down the stack or a cancellation. There do exist ways to handle this but currently they are not even detected and the first unwind will simply be forgotten, often leaving it in a bad state. \item Also the exception system did not have a lot of time to be tried and tested. bad software engineering. Non-local/concurrent raise requires more coordination between the concurrency system Non-local/concurrent raise requires more coordination between the concurrency system and the exception system. Many of the interesting design decisions centre around masking, \ie controlling which exceptions may be thrown at a stack. It passed on. However checked exceptions were never seriously considered for this project because they have significant usability and reuse trade-offs in However checked exceptions were never seriously considered for this project because they have significant trade-offs in usablity and code reuse in exchange for the increased safety. These trade-offs are most problematic when trying to pass exceptions through over safety design) so additional research is needed. Follow-up work might find a compromise design for checked exceptions in \CFA, possibly using polymorphic exception signatures, a form of tunneling\cite{Zhang19}, or Follow-up work might add some form of checked exceptions to \CFA, possibly using polymorphic exception signatures, a form of tunneling\cite{Zhang19} or checked and unchecked raises. For instance, resumption could be extended to cover this use by allowing local control flow out of it. This approach would require an unwind as part of the transition as there are stack frames that have to be removed back to the resumption handler.  This approach means no special statement is required in the handler to continue after it. Currently, \CFA allows a termination exception to be thrown from within any resumption handler so there is already a way to partially mimic signal exceptions. transition as there are stack frames that have to be removed between where the resumption handler is installed and where it is defined. This approach would not require, but might benefit from, a special statement to leave the handler. Currently, mimicking this behaviour in \CFA is possible by throwing a termination inside a resumption handler. % Maybe talk about the escape; and escape CONTROL_STMT; statements or how
• doc/theses/andrew_beach_MMath/implement.tex

 r6ba6846 pointer to the virtual table, which is called the \emph{virtual-table pointer}. Internally, the field is called \snake{virtual_table}. The field is fixed after construction and is the first field in the The field is fixed after construction. It is always the first field in the structure so that its location is always known. \todo{Talk about constructors for virtual types (after they are working).} The virtual-table pointer is what binds an instance of a virtual type to its virtual table. This pointer is used as an identity check, and to access the The virtual table pointer binds an instance of a virtual type to a virtual table. The pointer is also the table's id and how the system accesses the virtual table and the virtual members there. \subsection{Type Id} Every virtual type has a unique id. Type ids can be compared for equality (\ie the types represented are the same) Type ids can be compared for equality, which checks if the types reperented are the same, or used to access the type's type information. The type information currently is only the parent's type id or, if the type has no parent, @0p@. type has no parent, the null pointer. The id's are implemented as pointers to the type's type information instance. Dereferencing the pointer gets the type information. The ancestors of a virtual type are found by traversing the type id through The ancestors of a virtual type are found by traversing type ids through the type information. An id also pushes the issue of creating a unique value (for The information pushes the issue of creating a unique value (for the type id) to the problem of creating a unique instance (for type information), which the linker can solve. Advanced linker support is required because there is no place that appears only once to attach the type information to. There should be one structure definition but it is included in multiple translation units because of separate compilation. Each virtual table definition should be unique but there are an arbitrary number of these, so the special section prefix \texttt{.gnu.linkonce} is used. With a generated unique suffix (making the entire section name unique) the linker removes multiple definition ensuring only one version exists after linking. Then it is just a matter of making sure there is a unique name for each type. These steps are done in three phases. The advanced linker support is used here to avoid having to create a new declaration to attach this data to. With C/\CFA's header/implementation file divide for something to appear exactly once it must come from a declaration that appears in exactly one implementation file; the declarations in header files may exist only once they can be included in many different translation units. Therefore, structure's declaration will not work. Neither will attaching the type information to the virtual table -- although a vtable declarations are in implemention files they are not unique, see \autoref{ss:VirtualTable}. Instead the same type information is generated multiple times and then the new attribute \snake{cfa_linkone} is used to removed duplicates. Type information is constructed as follows: \begin{enumerate} \item The first phase is to generate a new structure definition to store the type Use the type's name to generate a name for the type information structure. This is saved so it may be reused. \item Generate a new structure definition to store the type information. The layout is the same in each case, just the parent's type id, but the types are changed. The structure's name is change, it is based off the virtual type's name, and the type of the parent's type id. If the virtual type is polymorphic, then the type information structure is but the types used change from instance to instance. The generated name is used for both this structure and, if relivant, the parent pointer. If the virtual type is polymorphic then the type information structure is polymorphic as well, with the same polymorphic arguments. \item The second phase is to generate an instance of the type information with a almost unique name, generated by mangling the virtual type name. A seperate name for instances is generated from the type's name. \item The third phase is implicit with \CFA's overloading scheme. \CFA mangles names with type information so that all of the symbols exported to the linker are unique even if in the \CFA code they are the same. Having two declarations with the same name and same type is forbidden because it is impossible for overload resolution to pick between them. This is the reason why a unique type is generated for each virtual type. Polymorphic information is included in this mangling so polymorphic types have separate instances for each set of polymorphic arguments. The definition is generated and initialised. The parent id is set to the null pointer or to the address of the parent's type information instance. Name resolution handles the rest. \item \CFA's name mangler does its regular name mangling encoding the type of the declaration into the instance name. This gives a completely unique name including different instances of the same polymorphic type. \end{enumerate} The following example shows the components for a generated virtual type. \begin{cfa} struct TYPE_ID_TYPE { PARENT_ID_TYPE const * parent; \todo{The list is making me realise, some of this isn't ordered.} Writing that code manually, with helper macros for the early name mangling, would look like this: \begin{cfa} struct INFO_TYPE(TYPE) { INFO_TYPE(PARENT) const * parent; }; __attribute__((cfa_linkonce)) TYPE_ID_TYPE const TYPE_ID_NAME = { &PARENT_ID_NAME, INFO_TYPE(TYPE) const INFO_NAME(TYPE) = { &INFO_NAME(PARENT), }; \end{cfa} \subsubsection{\lstinline{cfa_linkonce} Attribute} \subsubsection{\lstinline{cfa\_linkonce} Attribute} % I just realised: This is an extension of the inline keyword. % An extension of C's at least, it is very similar to C++'s. Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}. This attribute is attached to an object or function definition (any global declaration with a name and a type) allowing it to be defined multiple times. All matching definitions must have the link-once attribute on them and should be identical. This attributed prototype is placed in a header file with other forward declaration. This technique is used for type-id instances, as there is no unique location associated with a type, except for the type definition in a header. The result is the unique type-id object generated by the linker. All matching definitions mush have the link-once attribute and their implementations should be identical as well. A single definition with the attribute can be included in a header file as if it was a forward declaration, except no definition is required. This technique is used for type-id instances. A link-once definition is generated each time the structure is seen. This will result in multiple copies but the link-once attribute ensures all but one are removed for a unique instance. Internally, @cfa_linkonce@ is replaced with @section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the mangled name of the object. Any other @section@ attributes are also removed from the declaration. Any other @section@ attributes are removed from the declaration. The prefix \texttt{.gnu.linkonce} in section names is recognized by the linker. If two of these sections appear with the same name, including everything that comes after the special prefix, then only one is used and the other discarded. linker. If two of these sections appear with the same name, including everything that comes after the special prefix, then only one is used and the other is discarded. \subsection{Virtual Table} \label{ss:VirtualTable} Each virtual type has a virtual table type that stores its type id and virtual members. below. Figure~\ref{f:VirtualTableLayout} shows the layout is in three parts. \PAB{Number the parts in the figure.} \begin{enumerate} \item The layout always comes in three parts. \todo{Add labels to the virtual table layout figure.} The first section is just the type id at the head of the table. It is always there to ensure that \PAB{... missing text to end this sentence} \item there to ensure that it can be found even when the accessing code does not know which virtual type it has. The second section are all the virtual members of the parent, in the same order as they appear in the parent's virtual table. Note that the type may change slightly as references to the @this@ change. This structure is limited to change slightly as references to the this" will change. This is limited to inside pointers/references and via function pointers so that the size (and hence the offsets) are the same. \item The third section is similar to the second except that it is the new virtual members introduced at this level in the hierarchy. \end{enumerate} \begin{figure} prefix that has the same layout and types as its parent virtual table. This, combined with the fixed offset to the virtual table pointer, means that for any virtual type, it or any of its descendants can be accessed through the virtual table pointer. From there, it is safe to check the type id to identify the exact type of the underlying object, access any of the virtual members, and pass the object to for any virtual type, it is always safe to access its virtual table and, from there, it is safe to check the type id to identify the exact type of the underlying object, access any of the virtual members and pass the object to any of the method-like virtual members. the context of the declaration. The type id is always fixed with each virtual table type having The type id is always fixed; with each virtual table type having exactly one possible type id. The virtual members are usually filled in during type resolution. The best match for a given name and type at the declaration site is used. There are two exceptions to that rule: the @size@ field is the type's size set using a @sizeof@ expression, and the @align@ field is the type's alignment set using an @alignof@ expression. The virtual members are usually filled in by type resolution. The best match for a given name and type at the declaration site is used. There are two exceptions to that rule: the @size@ field, the type's size, is set using a @sizeof@ expression and the @align@ field, the type's alignment, is set using an @alignof@ expression. \subsubsection{Concurrency Integration} at the definition of the main function. Figure~\ref{f:ConcurrencyTransformations} shows ... \todo{Improve Concurrency Transformations figure.} This is showned through code re-writing in \autoref{f:ConcurrencyTransformations}. \begin{figure} \label{f:ConcurrencyTransformations} \end{figure} \todo{Improve Concurrency Transformations figure.} \subsection{Virtual Cast} the cast target is passed in as @child@. The generated C code wraps both arguments and the result with type casts. For generated C code wraps both arguments and the result with type casts. There is also an internal check inside the compiler to make sure that the target type is a virtual type. % It also checks for conflicting definitions. The virtual cast either returns the original pointer as a new type or 0p. So the function just does the parent check and returns the appropriate value. The virtual cast either returns the original pointer or the null pointer as the new type. So the function does the parent check and returns the appropriate value. The parent check is a simple linear search of child's ancestors using the type information. Allocating/deallocating stack space is usually an $O(1)$ operation achieved by bumping the hardware stack-pointer up or down as needed. In fact, constructing/destructing values within a stack frame is of similar complexity but often takes longer. Constructing/destructing values within a stack frame has a similar complexity but can add additional work and take longer. Unwinding across multiple stack frames is more complex because that information is no longer contained within the current function. With separate compilation a function has no way of knowing what its callers so it can not know how large those frames are. Without altering the main code path, it is also hard to pass that work off With seperate compilation a function has no way of knowing what its callers are so it can't know how large those frames are. Without altering the main code path it is also hard to pass that work off to the caller. stack. It is up to the programmer to ensure the snap-shot is valid when it is reset and that all required clean-up from the unwound stacks is performed. This approach is fragile and forces extra work in the surrounding code. With respect to the extra work in the surrounding code, This approach is fragile and requires extra work in the surrounding code. With respect to the extra work in the surounding code, many languages define clean-up actions that must be taken when certain sections of the stack are removed. Such as when the storage for a variable is removed from the stack or when a @try@ statement with a finally clause is is removed from the stack or when a try statement with a finally clause is (conceptually) popped from the stack. None of these should be handled explicitly by the user --- that would contradict the None of these should be handled by the user --- that would contradict the intention of these features --- so they need to be handled automatically. instruction pointer is within a region's start/end, then execution is currently executing in that region. Regions are used to mark out the scopes of objects with destructors and @try@ blocks. with destructors and try blocks. % Libunwind actually does very little, it simply moves down the stack from The attribute is used on a variable and specifies a function, in this case @clean_up@, run when the variable goes out of scope. This capability is enough to mimic destructors, but not @try@ statements which can effect This feature is enough to mimic destructors, but not try statements which can effect the unwinding. To get full unwinding support, all of these components must done directly with assembly and assembler directives, particularly the cfi directives \snake{.cfi_Leda} and \snake{.cfi_personality}. To get full unwinding support, all of these features must be handled directly in assembly and assembler directives; partiularly the cfi directives \snake{.cfi_lsda} and \snake{.cfi_personality}. \subsection{Personality Functions} The @exception_class@ argument is a copy of the \code{C}{exception}'s @exception_class@ field, which is a number that identifies the exception handling mechanism that created the \PAB{... missing text to end this sentence} which is a number that identifies the exception handling mechanism that created the exception. The \code{C}{exception} argument is a pointer to a user messages for special cases (some of which should never be used by the personality function) and error codes. However, unless otherwise noted, the personality function always return @_URC_CONTINUE_UNWIND@. personality function always returns @_URC_CONTINUE_UNWIND@. \subsection{Raise Exception} Raising an exception is the central function of libunwind and it performs the Raising an exception is the central function of libunwind and it performs two-staged unwinding. \begin{cfa} \Cpp exceptions closely. The main complication for \CFA is that the compiler generates C code, making it very difficult to generate the assembly to form the LSDA for @try@ blocks or destructors. form the LSDA for try blocks or destructors. \subsection{Memory Management} \label{f:ExceptionLayout} \end{figure} \todo*{Convert the exception layout to an actual diagram.} Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}). Exceptions are stored in variable-sized blocks (see \autoref{f:ExceptionLayout}). The first component is a fixed-sized data structure that contains the information for libunwind and the exception system. The second component is an high enough), which must be allocated. The previous exceptions may not be freed because the handler/catch clause has not been run. Therefore, the EHM must keep all of these exceptions alive while it allocates exceptions for new throws. Therefore, the EHM must keep all unhandled exceptions alive while it allocates exceptions for new throws. \begin{figure} exception into managed memory. After the exception is handled, the free function is used to clean up the exception and then the entire node is passed to free so the memory is returned to the heap. passed to free, returning the memory back to the heap. \subsection{Try Statements and Catch Clauses} The @try@ statement with termination handlers is complex because it must compensate for the C code-generation versus assembly-code generation from \CFA. Libunwind The try statement with termination handlers is complex because it must compensate for the C code-generation versus assembly-code generated from \CFA. Libunwind requires an LSDA and personality function for control to unwind across a function. The LSDA in particular is hard to mimic in generated C code. The workaround is a function called @__cfaehm_try_terminate@ in the standard library. The contents of a @try@ block and the termination handlers are converted library. The contents of a try block and the termination handlers are converted into functions. These are then passed to the try terminate function and it calls them. Because this function is known and fixed (and not an arbitrary function that happens to contain a @try@ statement), the LSDA can be generated ahead happens to contain a try statement), the LSDA can be generated ahead of time. embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains enough information for a single @try@ statement the function represents. enough information for a single try statement the function repersents. The three functions passed to try terminate are: \begin{description} \item[try function:] This function is the @try@ block, where all the code inside the @try@ block is wrapped inside the function. It takes no parameters and has no \item[try function:] This function is the try block, it is where all the code from inside the try block is placed. It takes no parameters and has no return value. This function is called during regular execution to run the try block. handler that matches the exception. \item[handler function:] This function handles the exception, where the code inside is constructed by stitching together the bodies of each handler of a @try@ statement and dispatches to the selected handler. \item[handler function:] This function handles the exception, and contains all the code from the handlers in the try statement, joined with a switch statement on the handler's id. It takes a pointer to the exception and the handler's id and returns nothing. It is called \end{description} All three functions are created with GCC nested functions. GCC nested functions can be used to create closures, \ie functions that can refer to the state of other can be used to create closures, in other words functions that can refer to the state of other functions on the stack. This approach allows the functions to refer to all the variables in scope for the function containing the @try@ statement. These Using this pattern, \CFA implements destructors with the cleanup attribute. Figure~\ref{f:TerminationTransformation} shows an example transformation for a \CFA @try@ statement with  @catch@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.} \autoref{f:TerminationTransformation} shows the pattern used to transform a \CFA try statement with catch clauses into the approprate C functions. \todo{Explain the Termination Transformation figure.} \begin{figure} \hrule \medskip \todo*{Termination Transformation divider feels too strong.} \begin{cfa} Instead of storing the data in a special area using assembly, there is just a linked list of possible handlers for each stack, with each list node representing a @try@ statement on the stack. with each node on the list reperenting a try statement on the stack. The head of the list is stored in the exception context. The nodes are stored in order, with the more recent @try@ statements closer The nodes are stored in order, with the more recent try statements closer to the head of the list. Instead of traversing the stack, resumption handling traverses the list. At each node, the EHM checks to see if the @try@ statement it represents At each node, the EHM checks to see if the try statement the node repersents can handle the exception. If it can, then the exception is handled and the operation finishes, otherwise the search continues to the next node. If the search reaches the end of the list without finding a @try@ statement If the search reaches the end of the list without finding a try statement that can handle the exception, the default handler is executed and the operation finishes. if the exception is handled and false otherwise. For each @catchResume@ clause, the handler function: \begin{itemize} \item checks to see if the raised exception is a descendant type of the declared exception type, \item if it is and there is a conditional expression then it runs the test, \item if both checks pass the handling code for the clause is run and the function returns true, \item otherwise it moves onto the next clause. \end{itemize} If this is the last @catchResume@ clause then instead of moving onto the next clause the function returns false as no handler could be found. Figure~\ref{f:ResumptionTransformation} shows an example transformation for a \CFA @try@ statement with @catchResume@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.} The handler function checks each of its internal handlers in order, top-to-bottom, until it funds a match. If a match is found that handler is run, after which the function returns true, ignoring all remaining handlers. If no match is found the function returns false. The match is performed in two steps, first a virtual cast is used to see if the thrown exception is an instance of the declared exception or one of its descendant type, then check to see if passes the custom predicate if one is defined. This ordering gives the type guarantee used in the predicate. \autoref{f:ResumptionTransformation} shows the pattern used to transform a \CFA try statement with catch clauses into the approprate C functions. \todo{Explain the Resumption Transformation figure.} \begin{figure} } \end{cfa} \medskip \hrule \medskip \todo*{Resumption Transformation divider feels too strong.} \begin{cfa} % Recursive Resumption Stuff: Figure~\ref{f:ResumptionMarking} shows the search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of \autoref{f:ResumptionMarking} shows search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of the stack already examined, is accomplished by updating the front of the list as the is updated to the next node of the current node. After the search is complete, successful or not, the head of the list is reset. % No paragraph? This mechanism means the current handler and every handler that has already been checked are not on the list while a handler is run. If a resumption is thrown during the handling of another resumption, the active handlers and all the other handler checked up to this point are not checked again. % No paragraph? This structure also supports new handlers added while the resumption is being handled. These are added to the front of the list, pointing back along the stack -- the first one points over all the checked handlers -- and the ordering is maintained. \PAB{Maybe number the figure and use the numbers in the description to help the reader follow.} stack --- the first one points over all the checked handlers --- and the ordering is maintained. \begin{figure} \caption{Resumption Marking} \label{f:ResumptionMarking} \todo*{Convert Resumption Marking into a line figure.} \todo*{Label Resumption Marking to aid clarity.} \end{figure} \label{p:zero-cost} Finally, the resumption implementation has a cost for entering/exiting a @try@ statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ Finally, the resumption implementation has a cost for entering/exiting a try statement with @catchResume@ clauses, whereas a try statement with @catch@ clauses has zero-cost entry/exit. While resumption does not need the stack unwinding and cleanup provided by libunwind, it could use the search phase to around the context of the associated @try@ statement. The rest is handled by GCC. The @try@ block and all handlers are inside this The rest is handled by GCC. The try block and all handlers are inside this block. At completion, control exits the block and the empty object is cleaned up, which runs the function that contains the finally code. The first step of cancellation is to find the cancelled stack and its type: coroutine or thread. Fortunately, the thread library stores the main thread pointer and the current thread pointer, and every thread stores a pointer to its coroutine and the coroutine it is currently executing. coroutine, thread or main thread. In \CFA, a thread (the construct the user works with) is a user-level thread (point of execution) paired with a coroutine, the thread's main coroutine. The thread library also stores pointers to the main thread and the current thread. If the current thread's main and current coroutines are the same then the current stack is a thread stack, otherwise it is a coroutine stack. Note, the runtime considers a thread as a coroutine with an associated user-level thread; hence, for many operations a thread and coroutine are treated uniformly. %\todo*{Consider adding a description of how threads are coroutines.} % Furthermore it is easy to compare the % current thread to the main thread to see if they are the same. And if this % is not a thread stack then it must be a coroutine stack. If the current stack is a thread stack, it is also the main thread stack if and only if the main and current threads are the same. However, if the threading library is not linked, the sequential execution is on passed to the forced-unwind function. The general pattern of all three stop functions is the same: continue unwinding until the end of stack and then perform the appropriate transfer. then preform the appropriate transfer. For main stack cancellation, the transfer is just a program abort. cancelled exception. It is then resumed as a regular exception with the default handler coming from the context of the resumption call. This semantics allows a cancellation to cascade through an arbitrary set of resumed coroutines back to the thread's coroutine, performing cleanup along the way. For thread cancellation, the exception is stored on the thread's main stack and null (as it is for the auto-generated joins on destructor call), the default is used, which is a program abort. This semantics allows a cancellation to cascade through an arbitrary set of joining threads back to the program's main, performing cleanup along the way. %; which gives the required handling on implicate join.
• doc/theses/andrew_beach_MMath/intro.tex

 r6ba6846 \chapter{Introduction} \PAB{Stay in the present tense. \newline \url{https://plg.uwaterloo.ca/~pabuhr/technicalWriting.shtml}} \newline \PAB{Note, \lstinline{lstlisting} normally bolds keywords. None of the keywords in your thesis are bolded.} % Talk about Cforall and exceptions generally. %This thesis goes over the design and implementation of the exception handling %mechanism (EHM) of %\CFA (pernounced sea-for-all and may be written Cforall or CFA). Exception handling provides alternative dynamic inter-function control flow. % The highest level overview of Cforall and EHMs. Get this done right away. This thesis goes over the design and implementation of the exception handling mechanism (EHM) of \CFA (pronounced sea-for-all and may be written Cforall or CFA). \CFA is a new programming language that extends C, that maintains backwards-compatibility while introducing modern programming features. Adding exception handling to \CFA gives it new ways to handle errors and make other large control-flow jumps. % Now take a step back and explain what exceptions are generally. Exception handling provides dynamic inter-function control flow. There are two forms of exception handling covered in this thesis: termination, which acts as a multi-level return, and resumption, which is a dynamic function call. Note, termination exception handling is so common it is often assumed to be the only form. Lesser know derivations of inter-function control flow are continuation passing in Lisp~\cite{CommonLisp}. Termination handling is much more common, to the extent that it is often seen This seperation is uncommon because termination exception handling is so much more common that it is often assumed. % WHY: Mention other forms of continuation and \cite{CommonLisp} here? A language's EHM is the combination of language syntax and run-time components that are used to construct, raise and handle exceptions, including all control flow. Termination exception handling allows control to return to any previous \end{center} Resumption exception handling calls a function, but asks the functions on the stack what function that is. Resumption exception handling seaches the stack for a handler and then calls it without adding or removing any other stack frames. \todo{Add a diagram showing control flow for resumption.} most of the cost only when the error actually occurs. % Overview of exceptions in Cforall. \PAB{You need section titles here. Don't take them out.} \section{Thesis Overview} This thesis goes over the design and implementation of the exception handling mechanism (EHM) of \CFA (pernounced sea-for-all and may be written Cforall or CFA). %This thesis describes the design and implementation of the \CFA EHM. This work describes the design and implementation of the \CFA EHM. The \CFA EHM implements all of the common exception features (or an equivalent) found in most other EHMs and adds some features of its own. harder to replicate in other programming languages. \section{Background} % Talk about other programming languages. Some existing programming languages that include EHMs/exception handling exceptions which unwind the stack as part of the Exceptions also can replace return codes and return unions. In functional languages will also sometimes fold exceptions into monads. \PAB{You must demonstrate knowledge of background material here. It should be at least a full page.} \section{Contributions} The contributions of this work are: \end{enumerate} \todo{I can't figure out a good lead-in to the overview.} Covering the existing \CFA features in \autoref{c:existing}. Then the new features are introduce in \autoref{c:features}, explaining their usage and design. \todo{I can't figure out a good lead-in to the roadmap.} The next section covers the existing state of exceptions. The existing state of \CFA is also covered in \autoref{c:existing}. The new features are introduced in \autoref{c:features}, which explains their usage and design. That is followed by the implementation of those features in \autoref{c:implement}. % Future Work \autoref{c:future} The performance results are examined in \autoref{c:performance}. Possibilities to extend this project are discussed in \autoref{c:future}. \section{Background} \label{s:background} Exception handling is not a new concept, with papers on the subject dating back 70s. Their were popularised by \Cpp, which added them in its first major wave of non-object-orientated features in 1990. % https://en.cppreference.com/w/cpp/language/history Java was the next popular language to use exceptions. It is also the most popular language with checked exceptions. Checked exceptions are part of the function interface they are raised from. This includes functions they propogate through, until a handler for that type of exception is found. This makes exception information explicit, which can improve clarity and safety, but can slow down programming. Some of these, such as dealing with high-order methods or an overly specified throws clause, are technical. However some of the issues are much more human, in that writing/updating all the exception signatures can be enough of a burden people will hack the system to avoid them. Including the catch-and-ignore" pattern where a catch block is used without anything to repair or recover from the exception. %\subsection Resumption exceptions have been much less popular. Although resumption has a history as old as termination's, very few programming languages have implement them. % http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/ %   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf Mesa is one programming languages that did and experiance with that languages is quoted as being one of the reasons resumptions were not included in the \Cpp standard. % https://en.wikipedia.org/wiki/Exception_handling \todo{A comment about why we did include them when they are so unpopular might be approprate.} %\subsection Functional languages, tend to use solutions like the return union, but some exception-like constructs still appear. For instance Haskell's built in error mechanism can make the result of any expression, including function calls. Any expression that examines an error value will in-turn produce an error. This continues until the main function produces an error or until it is handled by one of the catch functions. %\subsection More recently exceptions seem to be vanishing from newer programming languages. Rust and Go reduce this feature to panics. Panicing is somewhere between a termination exception and a program abort. Notably in Rust a panic can trigger either, a panic may unwind the stack or simply kill the process. % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html Go's panic is much more similar to a termination exception but there is only a catch-all function with \code{Go}{recover()}. So exceptions still are appearing, just in reduced forms. %\subsection Exception handling's most common use cases are in error handling. Here are some other ways to handle errors and comparisons with exceptions. \begin{itemize} \item\emph{Error Codes}: This pattern uses an enumeration (or just a set of fixed values) to indicate that an error has occured and which error it was. There are some issues if a function wants to return an error code and another value. The main issue is that it can be easy to forget checking the error code, which can lead to an error being quitely and implicitly ignored. Some new languages have tools that raise warnings if the return value is discarded to avoid this. It also puts more code on the main execution path. \item\emph{Special Return with Global Store}: A function that encounters an error returns some value indicating that it encountered a value but store which error occured in a fixed global location. Perhaps the C standard @errno@ is the most famous example of this, where some standard library functions will return some non-value (often a NULL pointer) and set @errno@. This avoids the multiple results issue encountered with straight error codes but otherwise many of the same advantages and disadvantages. It does however introduce one other major disadvantage: Everything that uses that global location must agree on all possible errors. \item\emph{Return Union}: Replaces error codes with a tagged union. Success is one tag and the errors are another. It is also possible to make each possible error its own tag and carry its own additional information, but the two branch format is easy to make generic so that one type can be used everywhere in error handling code. This pattern is very popular in functional or semi-functional language, anything with primitive support for tagged unions (or algebraic data types). % We need listing Rust/rust to format code snipits from it. % Rust's \code{rust}{Result} The main disadvantage is again it puts code on the main execution path. This is also the first technique that allows for more information about an error, other than one of a fix-set of ids, to be sent. They can be missed but some languages can force that they are checked. It is also implicitly forced in any languages with checked union access. \item\emph{Handler Functions}: On error the function that produced the error calls another function to handle it. The handler function can be provided locally (passed in as an argument, either directly as as a field of a structure/object) or globally (a global variable). C++ uses this as its fallback system if exception handling fails. \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler} Handler functions work a lot like resumption exceptions. The difference is they are more expencive to set up but cheaper to use, and so are more suited to more fequent errors. The exception being global handlers if they are rarely change as the time in both cases strinks towards zero. \end{itemize} %\subsection Because of their cost exceptions are rarely used for hot paths of execution. There is an element of self-fulfilling prophocy here as implementation techniques have been designed to make exceptions cheap to set-up at the cost of making them expencive to use. Still, use of exceptions for other tasks is more common in higher-level scripting languages. An iconic example is Python's StopIteration exception which is thrown by an iterator to indicate that it is exausted. Combined with Python's heavy use of the iterator based for-loop. % https://docs.python.org/3/library/exceptions.html#StopIteration
• doc/theses/andrew_beach_MMath/performance.tex

 r6ba6846 \textbf{Just because of the stage of testing there are design notes for the tests as well as commentary on them.} \todo{Revisit organization of the performance chapter once tests are chosen.} % What are good tests for resumption? Performance has been of secondary importance for most of this project. Instead, the goal has been to get the features working. The only performance requirements is to ensure the exception tests for correctness ran in a reasonable Instead, the focus has been to get the features working. The only performance requirements is to ensure the tests for correctness run in a reasonable amount of time. Much of the implementation is still reasonable and could be used for similar prototypes. Hence, the work still has some use. To get a rough idea about the \CFA implementation, tests are run on \CFA, C++ and Java, which have similar termination-handling exceptions. Tests are also run on \CFA and uC++, which has similar resumption-handling exceptions. \section{Termination Comparison} %\section{Termination Comparison} \section{Test Set-Up} Tests will be run on \CFA, C++ and Java. C++ is the most comparable language because both it and \CFA use the same framework, libunwind. there are some features it does not handle. The Java comparison is an opportunity to compare a managed memory model with unmanaged, to see if there are any effects related to the exception model. Java is another very popular language with similar termination semantics. It is implemented in a very different environment, a virtual machine with garbage collection. It also implements the finally clause on try blocks allowing for a direct feature-to-feature comparison. \subsection{Test Set-Up} All tests are run inside a main loop that performs the test repeatedly. This design avoids start-up or tear-down time from All tests are run inside a main loop which will perform the test repeatedly. This is to avoids start-up or tear-down time from affecting the timing results. A consequence is that tests cannot terminate the program, which does limit how tests can be implemented. There are catch-alls to keep unhandled A consequence of this is that tests cannot terminate the program, which does limit how tests can be implemented. There are catch-alls to keep unhandled exceptions from terminating tests. The exceptions used in this test are always a new exception based off of The exceptions used in these tests will always be a exception based off of the base exception. This requirement minimizes performance differences based on the object model. hot. \subsection{Tests} The following tests capture the most important aspects of exception handling and should provide a reasonable guide to programmers of where EHM costs occur. \section{Tests} The following tests were selected to test the performance of different components of the exception system. The should provide a guide as to where the EHM's costs can be found. \paragraph{Raise/Handle} There are a number of factors that can effect this. For \CFA this includes the type of raise, For \CFA this includes the type of raise, Main loop, pass through a catch-all, call through some empty helper functions This has the same set-up as the raise/handle test except the intermediate stack frames contain either an object declaration with a destructor or a @try@ statement with no handlers except and a @finally@ clause. try statement with no handlers except for a finally clause. \paragraph{Enter/Leave} is thrown? The test is a simple matter of entering This test is a simple pattern of entering and leaving a try statement. In this case different languages approach this problem differently, either through a re-throw or a conditional-catch. Where \CFA uses its condition, other languages must unconditionally Where \CFA uses its condition other languages will have to unconditionally catch the exception then re-throw if the condition if the condition is false. % We could do a Cforall test without the catch all and a new default handler % that does a catch all. As a point of comparison, one of the raise/handle tests (which one?) has As a point of comparison one of the raise/handle tests (which one?) has same layout but never catches anything. %related to -fexceptions.) \section{Resumption Comparison} % Some languages I left out: % Python: Its a scripting language, different % uC++: Not well known and should the same results as C++, except for %   resumption which should be the same. %\section{Resumption Comparison} \todo{Can we find a good language to compare resumptions in.}
Note: See TracChangeset for help on using the changeset viewer.