Changeset 9e67e92
- Timestamp:
- Jun 4, 2021, 4:59:34 PM (3 years ago)
- Branches:
- ADT, ast-experimental, 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. - Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/existing.tex
rdad9c9f r9e67e92 1 1 \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 4 5 modern safety and productivity features, while still ensuring backwards 5 6 compatibility with C and its programmers. \CFA is designed to have an … … 8 9 existing C code-base allowing programmers to learn \CFA on an as-needed basis. 9 10 10 Only those \CFA features pert inentto this thesis are discussed. Many of the11 Only those \CFA features pertaining to this thesis are discussed. Many of the 11 12 \CFA syntactic and semantic features used in the thesis should be fairly 12 13 obvious to the reader. … … 28 29 // name mangling on by default 29 30 int i; // _X1ii_1 30 extern "C"{ // disables name mangling31 @extern "C"@ { // disables name mangling 31 32 int j; // j 32 extern "Cforall"{ // enables name mangling33 @extern "Cforall"@ { // enables name mangling 33 34 int k; // _X1ki_1 34 35 } … … 44 45 \CFA adds a reference type to C as an auto-dereferencing pointer. 45 46 They work very similarly to pointers. 46 Reference-types are written the same way as a pointer-type isbut each47 Reference-types are written the same way as a pointer-type but each 47 48 asterisk (@*@) 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. 49 this includes cv-qualifiers and multiple levels of reference, \eg: 59 50 60 51 \begin{minipage}{0,5\textwidth} … … 65 56 int && rri = ri; 66 57 rri = 3; 67 &ri = &j; 58 &ri = &j; // reference assignment 68 59 ri = 5; 69 60 \end{cfa} … … 76 67 int ** ppi = π 77 68 **ppi = 3; 78 pi = &j; 69 pi = &j; // pointer assignment 79 70 *pi = 5; 80 71 \end{cfa} 81 72 \end{minipage} 82 73 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). 74 References are intended for cases where you would want to use pointers but would 75 be dereferencing them (almost) every usage. 76 In most cases a reference can just be thought of as a pointer that 77 automatically puts a dereference in front of each of its uses (per-level of 78 reference). 79 The address-of operator (@&@) acts as an escape and removes one of the 80 automatic dereference operations. 81 Mutable references may be assigned by converting them to a pointer 82 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above. 83 84 \section{Operators} 89 85 90 86 In general, operator names in \CFA are constructed by bracketing an operator … … 94 90 (such as @++?@) and post-fix operations (@?++@). 95 91 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. 92 An operator name may describe any function signature (it is just a name) but 93 only certain signatures may be called in operator form. 94 \begin{cfa} 95 int ?+?( int i, int j, int k ) { return i + j + k; } 96 { 97 sout | ?+?( 3, 4, 5 ); // no infix form 98 } 99 \end{cfa} 100 Some ``near-misses" for unary/binary operator prototypes generate warnings. 101 102 Both constructors and destructors are operators, which means they are 103 functions with special operator names rather than type names in \Cpp. The 104 special operator names may be used to call the functions explicitly (not 105 allowed in \Cpp for constructors). 106 107 The special name for a constructor is @?{}@, where the name @{}@ comes from the 108 initialization 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, 111 passing the initialization arguments to the constructor. 112 \begin{cfa} 113 struct Structure { ... }; 114 void ?{}(Structure & this) { ... } 115 { 116 Structure a; 117 Structure b = {}; 118 } 119 void ?{}(Structure & this, char first, int num) { ... } 120 { 121 Structure c = {'a', 2}; 122 } 123 \end{cfa} 124 Both @a@ and @b@ are initialized with the first constructor, 125 while @c@ is initialized with the second. 126 Currently, there is no general way to skip initialization. 115 127 116 128 % I don't like the \^{} symbol but $^\wedge$ isn't better. 117 Similarly destructors use the special name @^?{}@ (the @^@ has no special118 meaning). They can be called explicatly as well but normally they are119 implicitly called on a variable when it goes out of scope.120 \begin{cfa} 121 void ^?{}( Example & this) { ... }122 { 123 Example d;129 Similarly, destructors use the special name @^?{}@ (the @^@ has no special 130 meaning). Normally, they are implicitly called on a variable when it goes out 131 of scope but they can be called explicitly as well. 132 \begin{cfa} 133 void ^?{}(Structure & this) { ... } 134 { 135 Structure d; 124 136 } // <- implicit destructor call 125 137 \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 139 Whenever a type is defined, \CFA creates a default zero-argument 131 140 constructor, a copy constructor, a series of argument-per-field constructors 132 141 and a destructor. All user constructors are defined after this. … … 152 161 char capital_a = identity( 'A' ); 153 162 \end{cfa} 154 Each use of a polymorphic declaration will resolveits polymorphic parameters163 Each use of a polymorphic declaration resolves its polymorphic parameters 155 164 (in this case, just @T@) to concrete types (@int@ in the first use and @char@ 156 165 in the second). … … 158 167 To allow a polymorphic function to be separately compiled, the type @T@ must be 159 168 constrained by the operations used on @T@ in the function body. The @forall@ 160 clause sis augmented with a list of polymorphic variables (local type names)169 clause is augmented with a list of polymorphic variables (local type names) 161 170 and assertions (constraints), which represent the required operations on those 162 171 types used in a function, \eg: 163 172 \begin{cfa} 164 forall( T | { void do_once(T); } )173 forall( T | { void do_once(T); } ) 165 174 void do_twice(T value) { 166 175 do_once(value); … … 189 198 void do_once(double y) { ... } 190 199 int 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 193 203 return x; 194 204 } 195 205 \end{cfa} 196 206 Specifically, the complier deduces that @do_twice@'s T is an integer from the 197 argument @x@. It then looks for the most specificdefinition matching the207 argument @x@. It then looks for the most \emph{specific} definition matching the 198 208 assertion, which is the nested integral @do_once@ defined within the 199 209 function. 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.210 to @do_twice@ and called within it. The global definition of @do_once@ is used 211 for the second call because the float-point argument is a better match. 202 212 203 213 To avoid typing long lists of assertions, constraints can be collect into … … 269 279 Each coroutine has a @main@ function, which takes a reference to a coroutine 270 280 object and returns @void@. 271 \begin{cfa} 281 \begin{cfa}[numbers=left] 272 282 void main(CountUp & this) { 273 283 for (unsigned int next = 0 ; true ; ++next) { 274 284 next = up; 275 285 suspend;$\label{suspend}$ -
doc/theses/andrew_beach_MMath/features.tex
rdad9c9f r9e67e92 1 1 \chapter{Exception Features} 2 \label{c:features} 2 3 3 4 This 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. 5 EHM, % or exception system. 6 and begins with a general overview of EHMs. It is not a strict 7 definition of all EHMs nor an exhaustive list of all possible features. 8 However it does cover the most common structures and features found in them. 9 9 10 10 % We should cover what is an exception handling mechanism and what is an 11 11 % exception before this. Probably in the introduction. Some of this could 12 12 % move there. 13 \ paragraph{Raise / Handle}13 \section{Raise / Handle} 14 14 An exception operation has two main parts: raise and handle. 15 15 These terms are sometimes also known as throw and catch but this work uses 16 16 throw/catch as a particular kind of raise/handle. 17 These are the two parts that the user w ill write themselves and may17 These are the two parts that the user writes and may 18 18 be the only two pieces of the EHM that have any syntax in the language. 19 19 20 \ subparagraph{Raise}20 \paragraph{Raise} 21 21 The raise is the starting point for exception handling. It marks the beginning 22 of exception handling by raising an excep ion, which passes it to22 of exception handling by raising an exception, which passes it to 23 23 the EHM. 24 24 25 25 Some well known examples include the @throw@ statements of \Cpp and Java and 26 the \code{Python}{raise} statement from Python. In real systems araise may27 p reform some other work (such as memory management) but for the26 the \code{Python}{raise} statement from Python. A raise may 27 perform some other work (such as memory management) but for the 28 28 purposes of this overview that can be ignored. 29 29 30 \ subparagraph{Handle}30 \paragraph{Handle} 31 31 The purpose of most exception operations is to run some user code to handle 32 32 that exception. This code is given, with some other information, in a handler. 33 33 34 34 A handler has three common features: the previously mentioned user code, a 35 region of code they coverand an exception label/condition that matches35 region of code they guard, and an exception label/condition that matches 36 36 certain exceptions. 37 Only raises inside the covered region and raising exceptions that match the37 Only raises inside the guarded region and raising exceptions that match the 38 38 label can be handled by a given handler. 39 Different EHMs will have different rules to pick a handler40 if multip e handlers could be usedsuch as ``best match" or ``first found".39 Different EHMs have different rules to pick a handler, 40 if multiple handlers could be used, such as ``best match" or ``first found". 41 41 42 42 The @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 covered43 also show another common feature of handlers, they are grouped by the guarded 44 44 region. 45 45 46 \ paragraph{Propagation}46 \section{Propagation} 47 47 After an exception is raised comes what is usually the biggest step for the 48 EHM: finding and setting up the handler. The prop ogation from raise to48 EHM: finding and setting up the handler. The propagation from raise to 49 49 handler 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}50 matching against the handler, and installing the handler. 51 52 \paragraph{Searching} 53 53 The EHM begins by searching for handlers that might be used to handle 54 54 the exception. Searching is usually independent of the exception that was 55 thrown as it looks for handlers that have the raise site in their covered55 thrown as it looks for handlers that have the raise site in their guarded 56 56 region. 57 This includes handlers in the current function, as well as any in callers58 on the stack that have the function call in their covered region.59 60 \ subparagraph{Matching}57 This search includes handlers in the current function, as well as any in callers 58 on the stack that have the function call in their guarded region. 59 60 \paragraph{Matching} 61 61 Each handler found has to be matched with the raised exception. The exception 62 label defines a condition that be use used with exception and decidesif62 label defines a condition that is used with the exception to decide if 63 63 there is a match or not. 64 64 65 In languages where the first match is used this step is intertwined with66 searching , a match check is preformed immediately after the search finds65 In languages where the first match is used, this step is intertwined with 66 searching: a match check is performed immediately after the search finds 67 67 a possible handler. 68 68 69 \s ubparagraph{Installing}69 \section{Installing} 70 70 After a handler is chosen it must be made ready to run. 71 71 The implementation can vary widely to fit with the rest of the … … 74 74 case when stack unwinding is involved. 75 75 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} 76 If a matching handler is not guarantied to be found, the EHM needs a 77 different course of action for the case where no handler matches. 78 This situation only occurs with unchecked exceptions as checked exceptions 79 (such as in Java) can make the guarantee. 80 This unhandled action can abort the program or install a very general handler. 81 82 \paragraph{Hierarchy} 84 83 A common way to organize exceptions is in a hierarchical structure. 85 This is especially truein object-orientated languages where the84 This organization is often used in object-orientated languages where the 86 85 exception hierarchy is a natural extension of the object hierarchy. 87 86 … … 112 111 113 112 The EHM can return control to many different places, 114 the most common are after the handler definition and after the raise.113 the most common are after the handler definition (termination) and after the raise (resumption). 115 114 116 115 \paragraph{Communication} 117 116 For effective exception handling, additional information is often passed 118 from the raise to the handler .117 from the raise to the handler and back again. 119 118 So far only communication of the exceptions' identity has been covered. 120 A common method is putting fields into the exception instance and giving the121 handler access to them. 119 A common communication method is putting fields into the exception instance and giving the 120 handler access to them. References in the exception instance can push data back to the raise. 122 121 123 122 \section{Virtuals} 124 123 Virtual types and casts are not part of \CFA's EHM nor are they required for 125 124 any EHM. 126 However the \CFA uses a hierarchy built with the virtual system as the basis127 for exceptions andexception matching.128 129 The virtual system would have ideallybeen part of \CFA before the work125 However, one of the best ways to support an exception hierarchy is via a virtual system 126 among exceptions and used for exception matching. 127 128 Ideally, the virtual system would have been part of \CFA before the work 130 129 on exception handling began, but unfortunately it was not. 131 Because of thisonly the features and framework needed for the EHM were130 Therefore, only the features and framework needed for the EHM were 132 131 designed and implemented. Other features were considered to ensure that 133 the structure could accom idate other desirable featuresbut they were not132 the structure could accommodate other desirable features in the future but they were not 134 133 implemented. 135 The rest of this section will only discuss the finalized portionof the136 virtual system.134 The rest of this section discusses the implemented subset of the 135 virtual-system design. 137 136 138 137 The virtual system supports multiple ``trees" of types. Each tree is … … 144 143 % A type's ancestors are its parent and its parent's ancestors. 145 144 % The root type has no ancestors. 146 % A type's dece ndents are its children and its children's decendents.145 % A type's decedents are its children and its children's decedents. 147 146 148 147 Every virtual type also has a list of virtual members. Children inherit … … 150 149 It is important to note that these are virtual members, not virtual methods 151 150 of object-orientated programming, and can be of any type. 151 152 \PAB{I do not understand these sentences. Can you add an example? $\Rightarrow$ 152 153 \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 modified154 Function pointers that take a pointer to the virtual type are modified 154 155 with each level of inheritance so that refers to the new type. 155 156 This means an object can always be passed to a function in its virtual table 156 as if it were a method. 157 as if it were a method.} 157 158 158 159 Each virtual type has a unique id. 159 This uniqueid and all the virtual members are combined160 This id and all the virtual members are combined 160 161 into a virtual table type. Each virtual type has a pointer to a virtual table 161 162 as a hidden field. 163 164 \PAB{God forbid, maybe you need a UML diagram to relate these entities.} 162 165 163 166 Up until this point the virtual system is similar to ones found in 164 167 object-orientated languages but this where \CFA diverges. Objects encapsulate a 165 168 single set of behaviours in each type, universally across the entire program, 166 and indeed all programs that use that type definition. In this sense the169 and indeed all programs that use that type definition. In this sense, the 167 170 types are ``closed" and cannot be altered. 168 171 169 In \CFA types do not encapsulate any behaviour. Traits are local and170 types can begin to s tatify a trait, stop satifying a trait or satify the same172 In \CFA, types do not encapsulate any behaviour. Traits are local and 173 types can begin to satisfy a trait, stop satisfying a trait or satisfy the same 171 174 trait 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. Thismeans it173 is imp lossible to pick a single set of functions that repersent the type's175 In this sense, they are ``open" as they can change at any time. This capability means it 176 is impossible to pick a single set of functions that represent the type's 174 177 implementation across the program. 175 178 176 179 \CFA side-steps this issue by not having a single virtual table for each 177 type. A user can define virtual tables whichare filled in at their178 declaration and given a name. Anywhere that name is visible, even if it was179 defined locally inside a function (although that means it willnot have a180 type. A user can define virtual tables that are filled in at their 181 declaration and given a name. Anywhere that name is visible, even if 182 defined locally inside a function (although that means it does not have a 180 183 static lifetime), it can be used. 181 Specifically, a virtual type is ``bound" to a virtual table which184 Specifically, a virtual type is ``bound" to a virtual table that 182 185 sets the virtual members for that object. The virtual members can be accessed 183 186 through the object. 184 187 188 \PAB{The above explanation is very good!} 189 185 190 While much of the virtual infrastructure is created, it is currently only used 186 191 internally for exception handling. The only user-level feature is the virtual 187 cast , which is the same as the \Cpp \code{C++}{dynamic_cast}.192 cast 188 193 \label{p:VirtualCast} 189 194 \begin{cfa} 190 195 (virtual TYPE)EXPRESSION 191 196 \end{cfa} 197 which is the same as the \Cpp \code{C++}{dynamic_cast}. 192 198 Note, the syntax and semantics matches a C-cast, rather than the function-like 193 199 \Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be … … 211 217 \end{cfa} 212 218 The trait is defined over two types, the exception type and the virtual table 213 type. Each exception type should have buta single virtual table type.214 Now there are no actual assertions in this trait becausethe trait system215 actually can't express them (adding such assertions would be part of219 type. Each exception type should have a single virtual table type. 220 There are no actual assertions in this trait because currently the trait system 221 cannot express them (adding such assertions would be part of 216 222 completing the virtual system). The imaginary assertions would probably come 217 223 from a trait defined by the virtual system, and state that the exception type 218 is a virtual type, is a de cendent of @exception_t@ (the base exception type)224 is a virtual type, is a descendent of @exception_t@ (the base exception type) 219 225 and note its virtual table type. 220 226 … … 235 241 }; 236 242 \end{cfa} 237 Both traits ensure a pair of types are an exception type and its virtual table 243 Both traits ensure a pair of types are an exception type and its virtual table, 238 244 and defines one of the two default handlers. The default handlers are used 239 245 as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}. … … 263 269 \section{Exception Handling} 264 270 \label{s:ExceptionHandling} 265 \CFA provides two kinds of exception handling: termination and resumption.271 As stated, \CFA provides two kinds of exception handling: termination and resumption. 266 272 These twin operations are the core of \CFA's exception handling mechanism. 267 This section will coverthe general patterns shared by the two operations and268 then go on to cover the details each individual operation.273 This section covers the general patterns shared by the two operations and 274 then go on to cover the details of each individual operation. 269 275 270 276 Both operations follow the same set of steps. 271 Both start with the user p reforming a raise on an exception.272 Then the exception prop ogates up the stack.277 Both start with the user performing a raise on an exception. 278 Then the exception propagates up the stack. 273 279 If 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 thencontrol276 returns to normal execution after the raise.280 After that control returns to a point specific to the kind of exception. 281 If the search fails a default handler is run, and if it returns, control 282 continues after the raise. Note, the default handler may further change control flow rather than return. 277 283 278 284 This general description covers what the two kinds have in common. 279 Differences include how prop ogation is preformed, where exception continues285 Differences include how propagation is performed, where exception continues 280 286 after an exception is caught and handled and which default handler is run. 281 287 282 288 \subsection{Termination} 283 289 \label{s:Termination} 290 284 291 Termination handling is the familiar kind and used in most programming 285 292 languages with exception handling. 286 It is dynamic, non-local goto. If the raised exception is matched and287 handled the stack is unwound and control will (usually) continuethe function293 It is a dynamic, non-local goto. If the raised exception is matched and 294 handled, the stack is unwound and control (usually) continues in the function 288 295 on the call stack that defined the handler. 289 296 Termination is commonly used when an error has occurred and recovery is … … 300 307 termination exception is any type that satisfies the trait 301 308 @is_termination_exception@ at the call site. 302 Through \CFA's trait system the trait functions are implicity passed into the309 Through \CFA's trait system, the trait functions are implicitly passed into the 303 310 throw code and the EHM. 304 311 A new @defaultTerminationHandler@ can be defined in any scope to 305 change the throw's behavio r (see below).306 307 The throw will copythe provided exception into managed memory to ensure308 the exception is not destroyed ifthe stack is unwound.312 change the throw's behaviour (see below). 313 314 The throw copies the provided exception into managed memory to ensure 315 the exception is not destroyed when the stack is unwound. 309 316 It is the user's responsibility to ensure the original exception is cleaned 310 up whe ither the stack is unwound or not. Allocating it on the stack is317 up whether the stack is unwound or not. Allocating it on the stack is 311 318 usually sufficient. 312 319 313 Then prop ogation starts withthe search. \CFA uses a ``first match" rule so314 matching is p reformed with the copied exception as the search continues.315 It starts from the throwing function and proceeds to the base of the stack,320 Then propagation starts the search. \CFA uses a ``first match" rule so 321 matching is performed with the copied exception as the search continues. 322 It starts from the throwing function and proceeds towards the base of the stack, 316 323 from callee to caller. 317 324 At each stack frame, a check is made for resumption handlers defined by the … … 326 333 } 327 334 \end{cfa} 328 When viewed on its own, a try statement will simply executethe statements329 in \snake{GUARDED_BLOCK} and when those are finished the try statement finishes.335 When viewed on its own, a try statement simply executes the statements 336 in \snake{GUARDED_BLOCK} and when those are finished, the try statement finishes. 330 337 331 338 However, while the guarded statements are being executed, including any 332 invoked functions, all the handlers in the statement are nowon the search333 path. If a termination exception is thrown and not handledfurther up the334 stack they will be matched against the exception.339 invoked functions, all the handlers in these statements are included on the search 340 path. Hence, if a termination exception is raised, the search includes the added handlers associated with the guarded block and those further up the 341 stack from the guarded block. 335 342 336 343 Exception matching checks the handler in each catch clause in the order 337 they appear, top to bottom. If the representation of the thrownexception type344 they appear, top to bottom. If the representation of the raised exception type 338 345 is 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 is346 (if provided) is bound to a pointer to the exception and the statements in 347 @HANDLER_BLOCK@$_i$ are executed. 348 If control reaches the end of the handler, the exception is 342 349 freed and control continues after the try statement. 343 350 344 If no termination handler is found during the search thenthe default handler345 (\defaultTerminationHandler) is run.346 Through \CFA's trait system the best match at the throw sight will beused.347 This function is run and is passed the copied exception. Afterthe default348 handler is runcontrol continues after the throw statement.351 If no termination handler is found during the search, the default handler 352 (\defaultTerminationHandler) visible at the raise statement is called. 353 Through \CFA's trait system, the best match at the raise sight is used. 354 This function is run and is passed the copied exception. If the default 355 handler returns, control continues after the throw statement. 349 356 350 357 There is a global @defaultTerminationHandler@ that is polymorphic over all 351 exception types. Since it is so generala more specific handler can be352 defined and will beused for those types, effectively overriding the handler353 for particular exception type.358 termination exception types. Since it is so general, a more specific handler can be 359 defined and is used for those types, effectively overriding the handler 360 for a particular exception type. 354 361 The global default termination handler performs a cancellation 355 362 (see \vref{s:Cancellation}) on the current stack with the copied exception. … … 361 368 just as old~\cite{Goodenough75} and is simpler in many ways. 362 369 It 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. 370 matched a closure is taken from up the stack and executed, 371 after which the raising function continues executing. 372 These are most often used when a potentially repairable error occurs, some handler is found on the stack to fix it, and 373 the raising function can continue with the correction. 374 Another common usage is dynamic event analysis, \eg logging, without disrupting control flow. 375 Note, 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}. 378 You may or may not want to mention it. You can still stick with \lstinline{catch} and \lstinline{throw/catchResume} in the thesis.} 367 379 368 380 A resumption raise is started with the @throwResume@ statement: … … 375 387 @is_resumption_exception@ at the call site. 376 388 The 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 and381 any values on the stack will remain in scopewhile the resumption is handled.389 the exception system, while handling the exception. 390 391 Resumption does not need to copy the raised exception, as the stack is not unwound. 392 The exception and 393 any values on the stack remain in scope, while the resumption is handled. 382 394 383 395 The 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.396 resuming function and proceeds towards the base of the stack, from callee to caller. 385 397 At each stack frame, a check is made for resumption handlers defined by the 386 398 @catchResume@ clauses of a @try@ statement. … … 397 409 Note that termination handlers and resumption handlers may be used together 398 410 in a single try statement, intermixing @catch@ and @catchResume@ freely. 399 Each type of handler will only interactwith exceptions from the matching400 typeof raise.401 When a try statement is executed it simply executes the statements in the402 @GUARDED_BLOCK@ and then finishes.411 Each type of handler only interacts with exceptions from the matching 412 kind of raise. 413 When a try statement is executed, it simply executes the statements in the 414 @GUARDED_BLOCK@ and then returns. 403 415 404 416 However, while the guarded statements are being executed, including any 405 invoked functions, all the handlers in the statement are nowon the search406 path. If a resumption exception is reported and not handledfurther up the407 stack they will be matched against the exception.417 invoked functions, all the handlers in these statements are included on the search 418 path. Hence, if a resumption exception is raised the search includes the added handlers associated with the guarded block and those further up the 419 stack from the guarded block. 408 420 409 421 Exception matching checks the handler in each catch clause in the order 410 they appear, top to bottom. If the representation of the thrownexception type422 they appear, top to bottom. If the representation of the raised exception type 411 423 is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ 412 424 (if provided) is bound to a pointer to the exception and the statements in … … 415 427 the raise statement that raised the handled exception. 416 428 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 429 Like termination, if no resumption handler is found during the search, the default handler 430 (\defaultResumptionHandler) visible at the raise statement is called. 431 It uses the best match at the 432 raise sight according to \CFA's overloading rules. The default handler is 420 433 passed the exception given to the throw. When the default handler finishes 421 434 execution continues after the raise statement. 422 435 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 436 There is a global \defaultResumptionHandler{} that is polymorphic over all 437 resumption exception types and preforms a termination throw on the exception. 438 The \defaultTerminationHandler{} can be 427 439 customized by introducing a new or better match as well. 428 440 429 441 \subsubsection{Resumption Marking} 430 442 \label{s:ResumptionMarking} 443 431 444 A key difference between resumption and termination is that resumption does 432 445 not 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 statement434 searched before it are still on the stack. Th iscan lead to the recursive446 and run, its try block (the guarded statements) and every try statement 447 searched before it are still on the stack. Their existence can lead to the recursive 435 448 resumption problem. 436 449 … … 445 458 } 446 459 \end{cfa} 447 When this code is executed the guarded @throwResume@ will throw, starta448 search and match the handler in the @catchResume@ clause. This will be449 call and placed on the stack on top of the try-block. The second throw then450 throws and will search the same try block and putcall another instance of the451 same handler leading to an infinite loop.452 453 This situation is trivial and easy to avoid, butmuch more complex cycles460 When this code is executed, the guarded @throwResume@ starts a 461 search and matchs the handler in the @catchResume@ clause. This 462 call is placed on the top of stack above the try-block. The second throw 463 searchs the same try block and puts call another instance of the 464 same handler on the stack leading to an infinite recursion. 465 466 While this situation is trivial and easy to avoid, much more complex cycles 454 467 can form with multiple handlers and different exception types. 455 468 456 To prevent all of these cases we mark try statements on the stack.469 To prevent all of these cases, the exception search marks the try statements it visits. 457 470 A try statement is marked when a match check is preformed with it and an 458 exception. The statement will beunmarked when the handling of that exception471 exception. The statement is unmarked when the handling of that exception 459 472 is completed or the search completes without finding a handler. 460 While a try statement is marked its handlers are never matched, effectify461 skipping over itto the next try statement.473 While a try statement is marked, its handlers are never matched, effectify 474 skipping over them to the next try statement. 462 475 463 476 \begin{center} … … 466 479 467 480 These rules mirror what happens with termination. 468 When a termination throw happens in a handler the search willnot look at481 When a termination throw happens in a handler, the search does not look at 469 482 any handlers from the original throw to the original catch because that 470 part of the stack has beenunwound.483 part of the stack is unwound. 471 484 A 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 section473 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 but477 lack the symmetry meansthere are more rules to remember.485 but with marking, the search does match exceptions for try statements at equivalent sections 486 that would have been unwound by termination. 487 488 The symmetry between resumption termination is why this pattern is picked. 489 Other patterns, such as marking just the handlers that caught the exception, also work but 490 lack the symmetry, meaning there are more rules to remember. 478 491 479 492 \section{Conditional Catch} 493 480 494 Both termination and resumption handler clauses can be given an additional 481 495 condition to further control which exceptions they handle: … … 490 504 did not match. 491 505 492 The condition matching allows finer matching by allowing the matchto check506 The condition matching allows finer matching to check 493 507 more kinds of information than just the exception type. 494 508 \begin{cfa} … … 505 519 // Can't handle a failure relating to f2 here. 506 520 \end{cfa} 507 In this example the file that experianced the IO error is used to decide521 In this example, the file that experianced the IO error is used to decide 508 522 which handler should be run, if any at all. 509 523 … … 534 548 535 549 \subsection{Comparison with Reraising} 550 536 551 A 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.552 the exception after it has been caught, if it could not be handled here. 538 553 On the surface these two features seem interchangable. 539 554 540 If we used @throw;@to start a termination reraise then these two statements541 wouldhave the same behaviour:555 If @throw@ is used to start a termination reraise then these two statements 556 have the same behaviour: 542 557 \begin{cfa} 543 558 try { … … 559 574 } 560 575 \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 576 However, if there are further handlers after this handler only the first is 577 check. For multiple handlers on a single try block that could handle the 578 same exception, the equivalent translations to conditional catch becomes more complex, resulting is multiple nested try blocks for all possible reraises. 579 So 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. 582 A conditional catch CAN happen with the stack unwound. 583 Roy talked about this issue in Section 2.3.3 here: \newline 584 \url{http://plg.uwaterloo.ca/theses/KrischerThesis.pdf}} 585 586 Specifically for termination handling, a 567 587 conditional catch happens before the stack is unwound, but a reraise happens 568 588 afterwards. Normally this might only cause you to loose some debug 569 589 information you could get from a stack trace (and that can be side stepped 570 590 entirely by collecting information during the unwind). But for \CFA there is 571 another issue, if the exception is n't handled the default handler should be591 another issue, if the exception is not handled the default handler should be 572 592 run at the site of the original raise. 573 593 574 There are two problems with this: the site of the original raise does n't575 exist anymore and the default handler might not exist anymore. The site will576 always beremoved as part of the unwinding, often with the entirety of the594 There are two problems with this: the site of the original raise does not 595 exist anymore and the default handler might not exist anymore. The site is 596 always removed as part of the unwinding, often with the entirety of the 577 597 function it was in. The default handler could be a stack allocated nested 578 598 function removed during the unwind. … … 585 605 \section{Finally Clauses} 586 606 \label{s:FinallyClauses} 607 587 608 Finally clauses are used to preform unconditional clean-up when leaving a 588 609 scope and are placed at the end of a try statement after any handler clauses: … … 597 618 The @FINALLY_BLOCK@ is executed when the try statement is removed from the 598 619 stack, including when the @GUARDED_BLOCK@ finishes, any termination handler 599 finishes or during an unwind.620 finishes, or during an unwind. 600 621 The only time the block is not executed is if the program is exited before 601 622 the stack is unwound. … … 613 634 614 635 Not all languages with unwinding have finally clauses. Notably \Cpp does 615 without it as des cructorsserve a similar role. Although destructors and616 finally clauses can be used in many of the same areasthey have their own617 use caseslike top-level functions and lambda functions with closures.618 Destructors take a bit more work to set up but are much easier to reuse while619 finally clauses are good for one-off uses and 620 can easily include local information.636 without it as destructors with RAII serve a similar role. Although destructors and 637 finally clauses have overlapping usage cases, they have their own 638 specializations, like top-level functions and lambda functions with closures. 639 Destructors take more work if a number of unrelated, local variables without destructors or dynamically allocated variables must be passed for de-intialization. 640 Maintaining this destructor during local-block modification is a source of errors. 641 A finally clause places local de-intialization inline with direct access to all local variables. 621 642 622 643 \section{Cancellation} … … 631 652 raise, this exception is not used in matching only to pass information about 632 653 the 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.) 634 655 635 656 After @cancel_stack@ is called the exception is copied into the EHM's memory 636 657 and the current stack is 637 unwound. After that it depends one which stack is being cancelled. 658 unwound. 659 The result of a cancellation depends on the kind of stack that is being unwound. 638 660 639 661 \paragraph{Main Stack} … … 642 664 After the main stack is unwound there is a program-level abort. 643 665 644 There are two reasons for this . The first is that it obviously had to do this666 There are two reasons for this semantics. The first is that it obviously had to do the abort 645 667 in a sequential program as there is nothing else to notify and the simplicity 646 668 of keeping the same behaviour in sequential and concurrent programs is good. 647 Also, even in concurrent programsthere is no stack that an innate connection648 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 670 to, so it would have be explicitly managed.} 649 671 650 672 \paragraph{Thread Stack} 651 673 A thread stack is created for a \CFA @thread@ object or object that satisfies 652 674 the @is_thread@ trait. 653 After a thread stack is unwound there exception is stored until another675 After a thread stack is unwound, the exception is stored until another 654 676 thread attempts to join with it. Then the exception @ThreadCancelled@, 655 677 which stores a reference to the thread and to the exception passed to the 656 cancellation, is reported from the join .678 cancellation, is reported from the join to the joining thread. 657 679 There is one difference between an explicit join (with the @join@ function) 658 680 and an implicit join (from a destructor call). The explicit join takes the 659 681 default handler (@defaultResumptionHandler@) from its calling context while 660 the implicit join provides its own which does a program abort if the682 the implicit join provides its own, which does a program abort if the 661 683 @ThreadCancelled@ exception cannot be handled. 662 684 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. 686 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 687 communication with other threads: start and join.} 665 688 Since a thread must be running to perform a cancellation (and cannot be 666 689 cancelled from another stack), the cancellation must be after start and 667 before the join . So join is the one that we willuse.690 before the join, so join is use. 668 691 669 692 % TODO: Find somewhere to discuss unwind collisions. … … 677 700 A coroutine stack is created for a @coroutine@ object or object that 678 701 satisfies the @is_coroutine@ trait. 679 After a coroutine stack is unwound control returns to the resumefunction680 that most recently resumed it. The resume statementreports a681 @CoroutineCancelled@ exception, which contains areferences to the cancelled702 After a coroutine stack is unwound, control returns to the @resume@ function 703 that most recently resumed it. The resume reports a 704 @CoroutineCancelled@ exception, which contains references to the cancelled 682 705 coroutine and the exception used to cancel it. 683 The resumefunction also takes the \defaultResumptionHandler{} from the684 caller's context and passes it to the internal report.706 The @resume@ function also takes the \defaultResumptionHandler{} from the 707 caller's context and passes it to the internal cancellation. 685 708 686 709 A 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 just710 The starter has a much more distant connection, while the last resumer just 688 711 (in terms of coroutine state) called resume on this coroutine, so the message 689 712 is passed to the latter. -
doc/theses/andrew_beach_MMath/future.tex
rdad9c9f r9e67e92 1 1 \chapter{Future Work} 2 \label{c:future} 2 3 3 4 \section{Language Improvements} -
doc/theses/andrew_beach_MMath/implement.tex
rdad9c9f r9e67e92 1 1 \chapter{Implementation} 2 % Goes over how all the features are implemented. 2 \label{c:implement} 3 3 4 4 The implementation work for this thesis covers two components: the virtual -
doc/theses/andrew_beach_MMath/intro.tex
rdad9c9f r9e67e92 1 1 \chapter{Introduction} 2 2 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 3 8 % 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). 12 Exception handling provides alternative dynamic inter-function control flow. 13 There are two forms of exception handling covered in this thesis: 14 termination, which acts as a multi-level return, 15 and resumption, which is a dynamic function call. 16 Note, termination exception handling is so common it is often assumed to be the only form. 17 Lesser know derivations of inter-function control flow are continuation passing in Lisp~\cite{CommonLisp}. 18 19 Termination exception handling allows control to return to any previous 20 function on the stack directly, skipping any functions between it and the 21 current function. 10 22 \begin{center} 11 23 \input{callreturn} 12 24 \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.17 25 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. 26 Resumption exception handling calls a function, but asks the functions on the 27 stack what function that is. 28 \todo{Add a diagram showing control flow for resumption.} 29 30 Although a powerful feature, exception handling tends to be complex to set up 31 and expensive to use 32 so they are often limited to unusual or ``exceptional" cases. 21 33 The 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} 34 remove error handling logic from the main execution path and while paying 35 most of the cost only when the error actually occurs. 32 36 33 37 % 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 43 This thesis goes over the design and implementation of the exception handling 44 mechanism (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. 47 The \CFA EHM implements all of the common exception features (or an 36 48 equivalent) found in most other EHMs and adds some features of its own. 37 49 The design of all the features had to be adapted to \CFA's feature set as … … 54 66 % A note that yes, that was a very fast overview. 55 67 The design and implementation of all of \CFA's EHM's features are 56 described in detail throughout inthis thesis, whether they are a common feature68 described in detail throughout this thesis, whether they are a common feature 57 69 or one unique to \CFA. 58 70 59 71 % The current state of the project and what it contributes. 60 72 All of these features have been implemented in \CFA, along with 61 a suite of test cases , as part of this thesis.73 a suite of test cases as part of this project. 62 74 The 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. 75 languages and much of the design is as well. 76 Some parts of the EHM use other features unique to \CFA and these would be 77 harder to replicate in other programming languages. 78 79 \section{Background} 80 81 % Talk about other programming languages. 82 Some existing programming languages that include EHMs/exception handling 83 include C++, Java and Python. All three examples focus on termination 84 exceptions which unwind the stack as part of the 85 Exceptions also can replace return codes and return unions. 86 In functional languages will also sometimes fold exceptions into monads. 87 88 \PAB{You must demonstrate knowledge of background material here. 89 It should be at least a full page.} 65 90 66 91 \section{Contributions} … … 68 93 The contributions of this work are: 69 94 \begin{enumerate} 70 \item 71 \item 72 \item 73 \item 95 \item Designing \CFA's exception handling mechanism, adapting designs from 96 other programming languages and the creation of new features. 97 \item Implementing stack unwinding and the EHM in \CFA, including updating 98 the 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. 74 102 \end{enumerate} 75 103 76 \section{Road Map} 104 \todo{I can't figure out a good lead-in to the overview.} 105 Covering the existing \CFA features in \autoref{c:existing}. 106 Then the new features are introduce in \autoref{c:features}, explaining their 107 usage and design. 108 That 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.