Changes in / [e56eabac:d8f8d08]
- Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/conclusion.tex
re56eabac rd8f8d08 1 1 \chapter{Conclusion} 2 \label{c:conclusion} 2 3 % Just a little knot to tie the paper together. 3 4 -
doc/theses/andrew_beach_MMath/existing.tex
re56eabac rd8f8d08 10 10 11 11 Only those \CFA features pertaining to this thesis are discussed. 12 % Also, only new features of \CFA will be discussed,13 12 A familiarity with 14 13 C or C-like languages is assumed. … … 17 16 \CFA has extensive overloading, allowing multiple definitions of the same name 18 17 to be defined~\cite{Moss18}. 19 \begin{ lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]20 char @i@; int @i@; double @i@;21 int @f@(); double @f@();22 void @g@( int ); void @g@( double );23 \end{ lstlisting}18 \begin{cfa} 19 char i; int i; double i; 20 int f(); double f(); 21 void g( int ); void g( double ); 22 \end{cfa} 24 23 This feature requires name mangling so the assembly symbols are unique for 25 24 different overloads. For compatibility with names in C, there is also a syntax … … 63 62 int && rri = ri; 64 63 rri = 3; 65 &ri = &j; // rebindable64 &ri = &j; 66 65 ri = 5; 67 66 \end{cfa} … … 79 78 \end{minipage} 80 79 81 References are intended for pointer situations where dereferencing is the common usage, 82 \ie the value is more important than the pointer. 80 References are intended to be used when the indirection of a pointer is 81 required, but the address is not as important as the value and dereferencing 82 is the common usage. 83 83 Mutable references may be assigned to by converting them to a pointer 84 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above 84 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above. 85 % ??? 85 86 86 87 \section{Operators} 87 88 88 89 \CFA implements operator overloading by providing special names, where 89 operator usages are translated into function calls using these names.90 operator expressions are translated into function calls using these names. 90 91 An operator name is created by taking the operator symbols and joining them with 91 92 @?@s to show where the arguments go. … … 94 95 This syntax make it easy to tell the difference between prefix operations 95 96 (such as @++?@) and post-fix operations (@?++@). 96 For example, plus and equality operators are defined for a point type. 97 98 As an example, here are the addition and equality operators for a point type. 97 99 \begin{cfa} 98 100 point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; } … … 102 104 } 103 105 \end{cfa} 104 Note these special names are not limited to builtin 105 operators, and hence, may be used with arbitrary types. 106 \begin{cfa} 107 double ?+?( int x, point y ); // arbitrary types 108 \end{cfa} 109 % Some ``near misses", that are that do not match an operator form but looks like 110 % it may have been supposed to, will generate warning but otherwise they are 111 % left alone. 112 Because operators are never part of the type definition they may be added 113 at any time, including on built-in types. 106 Note that this syntax works effectively but a textual transformation, 107 the compiler converts all operators into functions and then resolves them 108 normally. This means any combination of types may be used, 109 although nonsensical ones (like @double ?==?(point, int);@) are discouraged. 110 This feature is also used for all builtin operators as well, 111 although those are implicitly provided by the language. 114 112 115 113 %\subsection{Constructors and Destructors} 116 117 \CFA also provides constructors and destructors as operators, which means they 118 are functions with special operator names rather than type names in \Cpp. 119 While constructors and destructions are normally called implicitly by the compiler, 120 the special operator names, allow explicit calls. 121 122 % Placement new means that this is actually equivalent to C++. 114 In \CFA, constructors and destructors are operators, which means they are 115 functions with special operator names rather than type names in \Cpp. 116 Both constructors and destructors can be implicity called by the compiler, 117 however the operator names allow explicit calls. 118 % Placement new means that this is actually equivant to C++. 123 119 124 120 The special name for a constructor is @?{}@, which comes from the … … 129 125 struct Example { ... }; 130 126 void ?{}(Example & this) { ... } 127 { 128 Example a; 129 Example b = {}; 130 } 131 131 void ?{}(Example & this, char first, int num) { ... } 132 Example a; // implicit constructor calls 133 Example b = {};134 Example c = {'a', 2}; 135 \end{cfa} 136 Both @a@ and @b@ are initialized with the first constructor,137 while @c@ is initialized with the second.138 Constructor calls can be replaced with C initialization using special operator \lstinline{@=}.139 \begin{cfa} 140 Example d @= {42}; 141 \end{cfa} 132 { 133 Example c = {'a', 2}; 134 } 135 \end{cfa} 136 Both @a@ and @b@ will be initalized with the first constructor, 137 @b@ because of the explicit call and @a@ implicitly. 138 @c@ will be initalized with the second constructor. 139 Currently, there is no general way to skip initialation. 140 % I don't use @= anywhere in the thesis. 141 142 142 % I don't like the \^{} symbol but $^\wedge$ isn't better. 143 143 Similarly, destructors use the special name @^?{}@ (the @^@ has no special 144 144 meaning). 145 % These are a normally called implicitly called on a variable when it goes out146 % of scope. They can be called explicitly as well.147 145 \begin{cfa} 148 146 void ^?{}(Example & this) { ... } 149 147 { 150 Example e; // implicit constructor call 151 ^?{}(e); // explicit destructor call 152 ?{}(e); // explicit constructor call 153 } // implicit destructor call 148 Example d; 149 ^?{}(d); 150 151 Example e; 152 } // Implicit call of ^?{}(e); 154 153 \end{cfa} 155 154 … … 225 224 The global definition of @do_once@ is ignored, however if quadruple took a 226 225 @double@ argument, then the global definition would be used instead as it 227 isa better match.228 % Aaron's thesis might be a good reference here. 229 230 To avoid typing long lists of assertions, constraints can be collect into231 convenient package called a @trait@, which can then be used in an assertion226 would then be a better match. 227 \todo{cite Aaron's thesis (maybe)} 228 229 To avoid typing long lists of assertions, constraints can be collected into 230 convenient a package called a @trait@, which can then be used in an assertion 232 231 instead of the individual constraints. 233 232 \begin{cfa} … … 253 252 node(T) * next; 254 253 T * data; 255 } 254 }; 256 255 node(int) inode; 257 256 \end{cfa} … … 293 292 }; 294 293 CountUp countup; 295 for (10) sout | resume(countup).next; // print 10 values296 294 \end{cfa} 297 295 Each coroutine has a @main@ function, which takes a reference to a coroutine 298 296 object and returns @void@. 299 297 %[numbers=left] Why numbers on this one? 300 \begin{cfa} [numbers=left,numberstyle=\scriptsize\sf]298 \begin{cfa} 301 299 void main(CountUp & this) { 302 for (unsigned int up = 0;; ++up) {303 this.next = up;300 for (unsigned int next = 0 ; true ; ++next) { 301 this.next = next; 304 302 suspend;$\label{suspend}$ 305 303 } … … 307 305 \end{cfa} 308 306 In this function, or functions called by this function (helper functions), the 309 @suspend@ statement is used to return execution to the coroutine's resumer310 without terminating the coroutine's function (s).307 @suspend@ statement is used to return execution to the coroutine's caller 308 without terminating the coroutine's function. 311 309 312 310 A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@. 313 311 The first resume calls the @main@ function at the top. Thereafter, resume calls 314 312 continue a coroutine in the last suspended function after the @suspend@ 315 statement, in this case @main@ line~\ref{suspend}. The @resume@ function takes 316 a reference to the coroutine structure and returns the same reference. The 317 return value allows easy access to communication variables defined in the 318 coroutine object. For example, the @next@ value for coroutine object @countup@ 319 is both generated and collected in the single expression: 320 @resume(countup).next@. 313 statement. In this case there is only one and, hence, the difference between 314 subsequent calls is the state of variables inside the function and the 315 coroutine object. 316 The return value of @resume@ is a reference to the coroutine, to make it 317 convent to access fields of the coroutine in the same expression. 318 Here is a simple example in a helper function: 319 \begin{cfa} 320 unsigned int get_next(CountUp & this) { 321 return resume(this).next; 322 } 323 \end{cfa} 324 325 When the main function returns the coroutine halts and can no longer be 326 resumed. 321 327 322 328 \subsection{Monitor and Mutex Parameter} … … 330 336 exclusion on a monitor object by qualifying an object reference parameter with 331 337 @mutex@. 332 \begin{ lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@argB);334 \end{ lstlisting}338 \begin{cfa} 339 void example(MonitorA & mutex argA, MonitorB & mutex argB); 340 \end{cfa} 335 341 When the function is called, it implicitly acquires the monitor lock for all of 336 342 the mutex parameters without deadlock. This semantics means all functions with … … 362 368 { 363 369 StringWorker stringworker; // fork thread running in "main" 364 } // implicitly join with thread / wait for completion370 } // Implicit call to join(stringworker), waits for completion. 365 371 \end{cfa} 366 372 The thread main is where a new thread starts execution after a fork operation -
doc/theses/andrew_beach_MMath/features.tex
re56eabac rd8f8d08 19 19 20 20 \paragraph{Raise} 21 The raise is the starting point for exception handling 21 The raise is the starting point for exception handling, 22 22 by raising an exception, which passes it to 23 23 the EHM. … … 30 30 \paragraph{Handle} 31 31 The primary purpose of an EHM is to run some user code to handle a raised 32 exception. This code is given, with some other information, in a handler. 32 exception. This code is given, along with some other information, 33 in a handler. 33 34 34 35 A handler has three common features: the previously mentioned user code, a 35 region of code it guards ,and an exception label/condition that matches36 the raised exception.36 region of code it guards and an exception label/condition that matches 37 against the raised exception. 37 38 Only raises inside the guarded region and raising exceptions that match the 38 39 label can be handled by a given handler. … … 41 42 42 43 The @try@ statements of \Cpp, Java and Python are common examples. All three 43 show the common features of guarded region, raise, matching and handler. 44 \begin{cfa} 45 try { // guarded region 46 ... 47 throw exception; // raise 48 ... 49 } catch( exception ) { // matching condition, with exception label 50 ... // handler code 51 } 52 \end{cfa} 44 also show another common feature of handlers, they are grouped by the guarded 45 region. 53 46 54 47 \subsection{Propagation} 55 48 After an exception is raised comes what is usually the biggest step for the 56 EHM: finding and setting up the handler for execution. The propagation from raise to 49 EHM: finding and setting up the handler for execution. 50 The propagation from raise to 57 51 handler can be broken up into three different tasks: searching for a handler, 58 52 matching against the handler and installing the handler. … … 60 54 \paragraph{Searching} 61 55 The EHM begins by searching for handlers that might be used to handle 62 the exception. The search is restricted to63 handlers that have the raise site in their guarded56 the exception. 57 The search will find handlers that have the raise site in their guarded 64 58 region. 65 59 The search includes handlers in the current function, as well as any in … … 67 61 68 62 \paragraph{Matching} 69 Each handler found is matchedwith the raised exception. The exception63 Each handler found is with the raised exception. The exception 70 64 label defines a condition that is used with the exception and decides if 71 65 there is a match or not. 66 % 72 67 In languages where the first match is used, this step is intertwined with 73 68 searching; a match check is performed immediately after the search finds … … 84 79 different course of action for this case. 85 80 This situation only occurs with unchecked exceptions as checked exceptions 86 (such as in Java) are guaranteed to find a matching handler.81 (such as in Java) can make the guarantee. 87 82 The unhandled action is usually very general, such as aborting the program. 88 83 … … 98 93 A handler labeled with any given exception can handle exceptions of that 99 94 type or any child type of that exception. The root of the exception hierarchy 100 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types ,95 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types 101 96 and the exceptions in the middle can be used to catch different groups of 102 97 related exceptions. 103 98 104 99 This system has some notable advantages, such as multiple levels of grouping, 105 the ability for libraries to add new exception types ,and the isolation100 the ability for libraries to add new exception types and the isolation 106 101 between different sub-hierarchies. 107 102 This design is used in \CFA even though it is not a object-orientated … … 123 118 For effective exception handling, additional information is often passed 124 119 from the raise to the handler and back again. 125 So far, only communication of the exception's identity is covered. 126 A common communication method for passing more information is putting fields into the exception instance 120 So far, only communication of the exceptions' identity is covered. 121 A common communication method for adding information to an exception 122 is putting fields into the exception instance 127 123 and giving the handler access to them. 128 Using reference fields pointing to data at the raise location allows data to be 129 passed in both directions. 124 % You can either have pointers/references in the exception, or have p/rs to 125 % the exception when it doesn't have to be copied. 126 Passing references or pointers allows data at the raise location to be 127 updated, passing information in both directions. 130 128 131 129 \section{Virtuals} 132 \label{s: Virtuals}130 \label{s:virtuals} 133 131 Virtual types and casts are not part of \CFA's EHM nor are they required for 134 132 an EHM. 135 133 However, one of the best ways to support an exception hierarchy 136 134 is via a virtual hierarchy and dispatch system. 137 Ideally, the virtual system should have been part of \CFA before the work135 Ideally, the virtual system would have been part of \CFA before the work 138 136 on exception handling began, but unfortunately it was not. 139 137 Hence, only the features and framework needed for the EHM were 140 designed and implemented for this thesis. Other features were considered to ensure that 138 designed and implemented for this thesis. 139 Other features were considered to ensure that 141 140 the structure could accommodate other desirable features in the future 142 141 but are not implemented. 143 142 The rest of this section only discusses the implemented subset of the 144 virtual -system design.143 virtual system design. 145 144 146 145 The virtual system supports multiple ``trees" of types. Each tree is … … 149 148 number of children. 150 149 Any type that belongs to any of these trees is called a virtual type. 151 For example, the following hypothetical syntax creates two virtual-type trees.152 \begin{flushleft}153 \lstDeleteShortInline@154 \begin{tabular}{@{\hspace{20pt}}l@{\hspace{20pt}}l}155 \begin{cfa}156 vtype V0, V1(V0), V2(V0);157 vtype W0, W1(W0), W2(W1);158 \end{cfa}159 &160 \raisebox{-0.6\totalheight}{\input{vtable}}161 \end{tabular}162 \lstMakeShortInline@163 \end{flushleft}164 150 % A type's ancestors are its parent and its parent's ancestors. 165 151 % The root type has no ancestors. 166 152 % A type's descendants are its children and its children's descendants. 167 Every virtual type (tree node) has a pointer to a virtual table with a unique 168 @Id@ and a list of virtual members (see \autoref{s:VirtualSystem} for 169 details). Children inherit their parent's list of virtual members but may add 170 and/or replace members. For example, 171 \begin{cfa} 172 vtable W0 | { int ?<?( int, int ); int ?+?( int, int ); } 173 vtable W1 | { int ?+?( int, int ); int w, int ?-?( int, int ); } 174 \end{cfa} 175 creates a virtual table for @W0@ initialized with the matching @<@ and @+@ 176 operations visible at this declaration context. Similarly, @W1@ is initialized 177 with @<@ from inheritance with @W0@, @+@ is replaced, and @-@ is added, where 178 both operations are matched at this declaration context. It is important to 179 note that these are virtual members, not virtual methods of object-orientated 180 programming, and can be of any type. Finally, trait names can be used to 181 specify the list of virtual members. 182 183 \PAB{Need to look at these when done. 184 185 \CFA still supports virtual methods as a special case of virtual members. 186 Function pointers that take a pointer to the virtual type are modified 187 with each level of inheritance so that refers to the new type. 188 This means an object can always be passed to a function in its virtual table 189 as if it were a method. 190 \todo{Clarify (with an example) virtual methods.} 191 }% 153 154 For the purposes of illistration, a proposed -- but unimplemented syntax -- 155 will be used. Each virtual type is repersented by a trait with an annotation 156 that makes it a virtual type. This annotation is empty for a root type, which 157 creates a new tree: 158 \begin{cfa} 159 trait root_type(T) virtual() {} 160 \end{cfa} 161 The annotation may also refer to any existing virtual type to make this new 162 type a child of that type and part of the same tree. The parent may itself 163 be a child or a root type and may have any number of existing children. 164 \begin{cfa} 165 trait child_a(T) virtual(root_type) {} 166 trait grandchild(T) virtual(child_a) {} 167 trait child_b(T) virtual(root_type) {} 168 \end{cfa} 169 \todo{Update the diagram in vtable.fig to show the new type tree.} 170 171 Every virtual type also has a list of virtual members and a unique id, 172 both are stored in a virtual table. 173 Every instance of a virtual type also has a pointer to a virtual table stored 174 in it, although there is no per-type virtual table as in many other languages. 175 176 The list of virtual members is built up down the tree. Every virtual type 177 inherits the list of virtual members from its parent and may add more 178 virtual members to the end of the list which are passed on to its children. 179 Again, using the unimplemented syntax this might look like: 180 \begin{cfa} 181 trait root_type(T) virtual() { 182 const char * to_string(T const & this); 183 unsigned int size; 184 } 185 186 trait child_type(T) virtual(root_type) { 187 char * irrelevant_function(int, char); 188 } 189 \end{cfa} 190 % Consider adding a diagram, but we might be good with the explanation. 191 192 As @child_type@ is a child of @root_type@ it has the virtual members of 193 @root_type@ (@to_string@ and @size@) as well as the one it declared 194 (@irrelivant_function@). 195 196 It is important to note that these are virtual members, and may contain 197 arbitrary fields, functions or otherwise. 198 The names ``size" and ``align" are reserved for the size and alignment of the 199 virtual type, and are always automatically initialized as such. 200 The other special case are uses of the trait's polymorphic argument 201 (@T@ in the example), which are always updated to refer to the current 202 virtual type. This allows functions that refer to to polymorphic argument 203 to act as traditional virtual methods (@to_string@ in the example), as the 204 object can always be passed to a virtual method in its virtual table. 192 205 193 206 Up until this point the virtual system is similar to ones found in 194 object-orientated languages but this is where \CFA diverges. Objects encapsulate a 195 single set of methods in each type, universally across the entire program, 196 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a 197 single set of methods. In this sense, 198 object-oriented types are ``closed" and cannot be altered. 199 200 In \CFA, types do not encapsulate any code. Traits are local for each function and 201 types can satisfy a local trait, stop satisfying it or, satisfy the same 202 trait in a different way at any lexical location in the program where a function is call. 203 In this sense, the set of functions/variables that satisfy a trait for a type is ``open" as the set can change at every call site. 207 object-oriented languages but this is where \CFA diverges. 208 Objects encapsulate a single set of methods in each type, 209 universally across the entire program, 210 and indeed all programs that use that type definition. 211 The only way to change any method is to inherit and define a new type with 212 its own universal implementation. In this sense, 213 these object-oriented types are ``closed" and cannot be altered. 214 % Because really they are class oriented. 215 216 In \CFA, types do not encapsulate any code. 217 Whether or not satisfies any given assertion, and hence any trait, is 218 context sensitive. Types can begin to satisfy a trait, stop satisfying it or 219 satisfy the same trait at any lexical location in the program. 220 In this sense, an type's implementation in the set of functions and variables 221 that allow it to satisfy a trait is ``open" and can change 222 throughout the program. 204 223 This capability means it is impossible to pick a single set of functions 205 224 that represent a type's implementation across a program. … … 208 227 type. A user can define virtual tables that are filled in at their 209 228 declaration and given a name. Anywhere that name is visible, even if it is 210 defined locally inside a function \PAB{What does this mean? (although that means it does not have a211 static lifetime)}, it can be used.229 defined locally inside a function (although in this case the user must ensure 230 it outlives any objects that use it), it can be used. 212 231 Specifically, a virtual type is ``bound" to a virtual table that 213 232 sets the virtual members for that object. The virtual members can be accessed 214 233 through the object. 234 235 This means virtual tables are declared and named in \CFA. 236 They are declared as variables, using the type 237 @vtable(VIRTUAL_TYPE)@ and any valid name. For example: 238 \begin{cfa} 239 vtable(virtual_type_name) table_name; 240 \end{cfa} 241 242 Like any variable they may be forward declared with the @extern@ keyword. 243 Forward declaring virtual tables is relatively common. 244 Many virtual types have an ``obvious" implementation that works in most 245 cases. 246 A pattern that has appeared in the early work using virtuals is to 247 implement a virtual table with the the obvious definition and place a forward 248 declaration of it in the header beside the definition of the virtual type. 249 250 Even on the full declaration, no initializer should be used. 251 Initialization is automatic. 252 The type id and special virtual members ``size" and ``align" only depend on 253 the virtual type, which is fixed given the type of the virtual table and 254 so the compiler fills in a fixed value. 255 The other virtual members are resolved, using the best match to the member's 256 name and type, in the same context as the virtual table is declared using 257 \CFA's normal resolution rules. 215 258 216 259 While much of the virtual infrastructure is created, it is currently only used … … 228 271 @EXPRESSION@ object, otherwise it returns @0p@ (null pointer). 229 272 230 \section{Exception} 231 % Leaving until later, hopefully it can talk about actual syntax instead 232 % of my many strange macros. Syntax aside I will also have to talk about the 233 % features all exceptions support. 234 235 Exceptions are defined by the trait system; there are a series of traits, and 273 \section{Exceptions} 274 275 The syntax for declaring an exception is the same as declaring a structure 276 except the keyword that is swapped out: 277 \begin{cfa} 278 exception TYPE_NAME { 279 FIELDS 280 }; 281 \end{cfa} 282 283 Fields are filled in the same way as a structure as well. However an extra 284 field is added, this field contains the pointer to the virtual table. 285 It must be explicitly initialised by the user when the exception is 286 constructed. 287 288 Here is an example of declaring an exception type along with a virtual table, 289 assuming the exception has an ``obvious" implementation and a default 290 virtual table makes sense. 291 292 \begin{minipage}[t]{0.4\textwidth} 293 Header: 294 \begin{cfa} 295 exception Example { 296 int data; 297 }; 298 299 extern vtable(Example) 300 example_base_vtable; 301 \end{cfa} 302 \end{minipage} 303 \begin{minipage}[t]{0.6\textwidth} 304 Source: 305 \begin{cfa} 306 vtable(Example) example_base_vtable 307 \end{cfa} 308 \vfil 309 \end{minipage} 310 311 %\subsection{Exception Details} 312 If one is only raising and handling exceptions, that is the only interface 313 that is needed. However it is actually a short hand for a more complex 314 trait based interface. 315 316 The language views exceptions through a series of traits, 236 317 if a type satisfies them, then it can be used as an exception. The following 237 318 is the base trait all exceptions need to match. … … 247 328 completing the virtual system). The imaginary assertions would probably come 248 329 from a trait defined by the virtual system, and state that the exception type 249 is a virtual type, is a descendant of @exception_t@ (the base exception type) ,250 and note itsvirtual table type.330 is a virtual type, is a descendant of @exception_t@ (the base exception type) 331 and allow the user to find the virtual table type. 251 332 252 333 % I did have a note about how it is the programmer's responsibility to make … … 267 348 \end{cfa} 268 349 Both traits ensure a pair of types are an exception type, its virtual table 269 type ,350 type 270 351 and defines one of the two default handlers. The default handlers are used 271 352 as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}. … … 276 357 facing way. So these three macros are provided to wrap these traits to 277 358 simplify referring to the names: 278 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ ,and @IS_RESUMPTION_EXCEPTION@.359 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@. 279 360 280 361 All three take one or two arguments. The first argument is the name of the … … 299 380 These twin operations are the core of \CFA's exception handling mechanism. 300 381 This section covers the general patterns shared by the two operations and 301 then goes on to cover the details ofeach individual operation.382 then goes on to cover the details each individual operation. 302 383 303 384 Both operations follow the same set of steps. 304 385 First, a user raises an exception. 305 Second, the exception propagates up the stack .386 Second, the exception propagates up the stack, searching for a handler. 306 387 Third, if a handler is found, the exception is caught and the handler is run. 307 388 After that control continues at a raise-dependent location. 308 Fourth, if a handler is not found, a default handler is run and, if it returns, then control 389 As an alternate to the third step, 390 if a handler is not found, a default handler is run and, if it returns, 391 then control 309 392 continues after the raise. 310 393 311 %This general description covers what the two kinds have in common. 312 The differences in the two operations include how propagation is performed, where execution continues 313 a fter an exception is caught and handled, and which default handler is run.394 The differences between the two operations include how propagation is 395 performed, where excecution after an exception is handler 396 and which default handler is run. 314 397 315 398 \subsection{Termination} 316 399 \label{s:Termination} 317 Termination handling is the familiar EHM and used in most programming 400 Termination handling is the familiar kind of handling 401 and used in most programming 318 402 languages with exception handling. 319 403 It is a dynamic, non-local goto. If the raised exception is matched and … … 347 431 Then propagation starts with the search. \CFA uses a ``first match" rule so 348 432 matching is performed with the copied exception as the search key. 349 It starts from the raise in the throwing function and proceeds towards thebase of the stack,433 It starts from the raise site and proceeds towards base of the stack, 350 434 from callee to caller. 351 435 At each stack frame, a check is made for termination handlers defined by the … … 361 445 \end{cfa} 362 446 When viewed on its own, a try statement simply executes the statements 363 in the \snake{GUARDED_BLOCK} ,and when those are finished,447 in the \snake{GUARDED_BLOCK} and when those are finished, 364 448 the try statement finishes. 365 449 … … 387 471 termination exception types. 388 472 The global default termination handler performs a cancellation 389 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception. 390 Since it is so general, a more specific handler is usually 391 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler. 473 (as described in \vref{s:Cancellation}) 474 on the current stack with the copied exception. 475 Since it is so general, a more specific handler can be defined, 476 overriding the default behaviour for the specific exception types. 392 477 393 478 \subsection{Resumption} 394 479 \label{s:Resumption} 395 480 396 Resumption exception handling is the less familar EHM, but is 481 Resumption exception handling is less familar form of exception handling, 482 but is 397 483 just as old~\cite{Goodenough75} and is simpler in many ways. 398 484 It is a dynamic, non-local function call. If the raised exception is … … 403 489 function once the error is corrected, and 404 490 ignorable events, such as logging where nothing needs to happen and control 405 should always continue from the raise point. 491 should always continue from the raise site. 492 493 Except for the changes to fit into that pattern, resumption exception 494 handling is symmetric with termination exception handling, by design 495 (see \autoref{s:Termination}). 406 496 407 497 A resumption raise is started with the @throwResume@ statement: … … 410 500 \end{cfa} 411 501 \todo{Decide on a final set of keywords and use them everywhere.} 412 It works much the same way as the termination throw. 413 The expression must return a reference to a resumption exception, 414 where the resumption exception is any type that satisfies the trait 415 @is_resumption_exception@ at the call site. 416 The assertions from this trait are available to 417 the exception system while handling the exception. 418 419 At run-time, no exception copy is made, since 502 It works much the same way as the termination raise, except the 503 type must satisfy the \snake{is_resumption_exception} that uses the 504 default handler: \defaultResumptionHandler. 505 This can be specialized for particular exception types. 506 507 At run-time, no exception copy is made. Since 420 508 resumption does not unwind the stack nor otherwise remove values from the 421 current scope, so there is no need to manage memory to keep the exception in scope.422 423 Then propagation starts with the search. It starts from the raise in the 424 resuming function and proceeds towards the base of the stack,425 f rom callee to caller.426 At each stack frame, a check is made for resumption handlers defined by the 427 @catchResume@ clauses of a @try@ statement.509 current scope, there is no need to manage memory to keep the exception 510 allocated. 511 512 Then propagation starts with the search, 513 following the same search path as termination, 514 from the raise site to the base of stack and top of try statement to bottom. 515 However, the handlers on try statements are defined by @catchResume@ clauses. 428 516 \begin{cfa} 429 517 try { … … 435 523 } 436 524 \end{cfa} 437 % PAB, you say this above. 438 % When a try statement is executed, it simply executes the statements in the 439 % @GUARDED_BLOCK@ and then finishes. 440 % 441 % However, while the guarded statements are being executed, including any 442 % invoked functions, all the handlers in these statements are included in the 443 % search path. 444 % Hence, if a resumption exception is raised, these handlers may be matched 445 % against the exception and may handle it. 446 % 447 % Exception matching checks the handler in each catch clause in the order 448 % they appear, top to bottom. If the representation of the raised exception type 449 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$ 450 % (if provided) is bound to a pointer to the exception and the statements in 451 % @HANDLER_BLOCK@$_i$ are executed. 452 % If control reaches the end of the handler, execution continues after the 453 % the raise statement that raised the handled exception. 454 % 455 % Like termination, if no resumption handler is found during the search, 456 % then the default handler (\defaultResumptionHandler) visible at the raise 457 % statement is called. It will use the best match at the raise sight according 458 % to \CFA's overloading rules. The default handler is 459 % passed the exception given to the raise. When the default handler finishes 460 % execution continues after the raise statement. 461 % 462 % There is a global @defaultResumptionHandler{} is polymorphic over all 463 % resumption exceptions and performs a termination throw on the exception. 464 % The \defaultTerminationHandler{} can be overridden by providing a new 465 % function that is a better match. 466 467 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same 468 for resumption as for termination, as does exception matching at each 469 @catchResume@. Similarly, if no resumption handler is found during the search, 470 then the currently visible default handler (\defaultResumptionHandler) is 471 called and control continues after the raise statement if it returns. Finally, 472 there is also a global @defaultResumptionHandler@, which can be overridden, 473 that is polymorphic over all resumption exceptions but performs a termination 474 throw on the exception rather than a cancellation. 475 476 Throwing the exception in @defaultResumptionHandler@ has the positive effect of 477 walking the stack a second time for a recovery handler. Hence, a programmer has 478 two chances for help with a problem, fixup or recovery, should either kind of 479 handler appear on the stack. However, this dual stack walk leads to following 480 apparent anomaly: 481 \begin{cfa} 482 try { 483 throwResume E; 484 } catch (E) { 485 // this handler runs 486 } 487 \end{cfa} 488 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only 489 matches with @catchResume@. The anomaly results because the unmatched 490 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@. 491 492 % I wonder if there would be some good central place for this. 493 Note, termination and resumption handlers may be used together 525 Note that termination handlers and resumption handlers may be used together 494 526 in a single try statement, intermixing @catch@ and @catchResume@ freely. 495 527 Each type of handler only interacts with exceptions from the matching 496 528 kind of raise. 529 Like @catch@ clauses, @catchResume@ clauses have no effect if an exception 530 is not raised. 531 532 The matching rules are exactly the same as well. 533 The first major difference here is that after 534 @EXCEPTION_TYPE@$_i$ is matched and @NAME@$_i$ is bound to the exception, 535 @HANDLER_BLOCK@$_i$ is executed right away without first unwinding the stack. 536 After the block has finished running control jumps to the raise site, where 537 the just handled exception came from, and continues executing after it, 538 not after the try statement. 497 539 498 540 \subsubsection{Resumption Marking} … … 502 544 and run, its try block (the guarded statements) and every try statement 503 545 searched before it are still on the stack. There presence can lead to 504 the \emph{recursive resumption problem}. 546 the recursive resumption problem. 547 \todo{Is there a citation for the recursive resumption problem?} 505 548 506 549 The recursive resumption problem is any situation where a resumption handler … … 516 559 When this code is executed, the guarded @throwResume@ starts a 517 560 search and matches the handler in the @catchResume@ clause. This 518 call is placed on the stack above the try-block. Now the second raise in the handler 519 searches the same try block, matches, and puts another instance of the 561 call is placed on the stack above the try-block. 562 Now the second raise in the handler searches the same try block, 563 matches again and then puts another instance of the 520 564 same handler on the stack leading to infinite recursion. 521 565 522 While this situation is trivial and easy to avoid, much more complex cycles can 523 form with multiple handlers and different exception types. The key point is 524 that the programmer's intuition expects every raise in a handler to start 525 searching \emph{below} the @try@ statement, making it difficult to understand 526 and fix the problem. 527 566 While this situation is trivial and easy to avoid, much more complex cycles 567 can form with multiple handlers and different exception types. 528 568 To prevent all of these cases, each try statement is ``marked" from the 529 time the exception search reaches it to either when a matching handler530 completesor when the search reaches the base569 time the exception search reaches it to either when a handler completes 570 handling that exception or when the search reaches the base 531 571 of the stack. 532 572 While a try statement is marked, its handlers are never matched, effectively … … 540 580 for instance, marking just the handlers that caught the exception, 541 581 would also prevent recursive resumption. 542 However, the rule selected mirrors what happens with termination,543 and hence, matches programmer intuition that a raise searches below a try.544 545 In detail, the marked try statements are the ones that would be removed from582 However, the rules selected mirrors what happens with termination, 583 so this reduces the amount of rules and patterns a programmer has to know. 584 585 The marked try statements are the ones that would be removed from 546 586 the stack for a termination exception, \ie those on the stack 547 587 between the handler and the raise statement. … … 609 649 610 650 \subsection{Comparison with Reraising} 611 Without conditional catch, the only approach to match in more detail is to reraise 612 the exception after it has been caught, if it could not be handled. 651 In languages without conditional catch, that is no ability to match an 652 exception based on something other than its type, it can be mimicked 653 by matching all exceptions of the right type, checking any additional 654 conditions inside the handler and re-raising the exception if it does not 655 match those. 656 657 Here is a minimal example comparing both patterns, using @throw;@ 658 (no argument) to start a re-raise. 613 659 \begin{center} 614 \begin{tabular}{l |l}660 \begin{tabular}{l r} 615 661 \begin{cfa} 616 662 try { 617 618 } catch(excep _t * ex; can_handle(ex)) {619 620 handle(ex);621 622 623 624 } 663 do_work_may_throw(); 664 } catch(exception_t * exc ; 665 can_handle(exc)) { 666 handle(exc); 667 } 668 669 670 625 671 \end{cfa} 626 672 & 627 673 \begin{cfa} 628 674 try { 629 do_work_may_throw(); 630 } catch(excep_t * ex) { 631 if (can_handle(ex)) { 632 handle(ex); 675 do_work_may_throw(); 676 } catch(exception_t * exc) { 677 if (can_handle(exc)) { 678 handle(exc); 679 } else { 680 throw; 681 } 682 } 683 \end{cfa} 684 \end{tabular} 685 \end{center} 686 At first glance catch-and-reraise may appear to just be a quality of life 687 feature, but there are some significant differences between the two 688 stratagies. 689 690 A simple difference that is more important for \CFA than many other languages 691 is that the raise site changes, with a re-raise but does not with a 692 conditional catch. 693 This is important in \CFA because control returns to the raise site to run 694 the per-site default handler. Because of this only a conditional catch can 695 allow the original raise to continue. 696 697 The more complex issue comes from the difference in how conditional 698 catches and re-raises handle multiple handlers attached to a single try 699 statement. A conditional catch will continue checking later handlers while 700 a re-raise will skip them. 701 If the different handlers could handle some of the same exceptions, 702 translating a try statement that uses one to use the other can quickly 703 become non-trivial: 704 705 \noindent 706 Original, with conditional catch: 707 \begin{cfa} 708 ... 709 } catch (an_exception * e ; check_a(e)) { 710 handle_a(e); 711 } catch (exception_t * e ; check_b(e)) { 712 handle_b(e); 713 } 714 \end{cfa} 715 Translated, with re-raise: 716 \begin{cfa} 717 ... 718 } catch (exception_t * e) { 719 an_exception * an_e = (virtual an_exception *)e; 720 if (an_e && check_a(an_e)) { 721 handle_a(an_e); 722 } else if (check_b(e)) { 723 handle_b(e); 633 724 } else { 634 725 throw; … … 636 727 } 637 728 \end{cfa} 638 \end{tabular} 639 \end{center} 640 Notice catch-and-reraise increases complexity by adding additional data and 641 code to the exception process. Nevertheless, catch-and-reraise can simulate 642 conditional catch straightforwardly, when exceptions are disjoint, \ie no 643 inheritance. 644 645 However, catch-and-reraise simulation becomes unusable for exception inheritance. 646 \begin{flushleft} 647 \begin{cfa}[xleftmargin=6pt] 648 exception E1; 649 exception E2(E1); // inheritance 650 \end{cfa} 651 \begin{tabular}{l|l} 652 \begin{cfa} 653 try { 654 ... foo(); ... // raise E1/E2 655 ... bar(); ... // raise E1/E2 656 } catch( E2 e; e.rtn == foo ) { 657 ... 658 } catch( E1 e; e.rtn == foo ) { 659 ... 660 } catch( E1 e; e.rtn == bar ) { 661 ... 662 } 663 664 \end{cfa} 665 & 666 \begin{cfa} 667 try { 668 ... foo(); ... 669 ... bar(); ... 670 } catch( E2 e ) { 671 if ( e.rtn == foo ) { ... 672 } else throw; // reraise 673 } catch( E1 e ) { 674 if (e.rtn == foo) { ... 675 } else if (e.rtn == bar) { ... 676 else throw; // reraise 677 } 678 \end{cfa} 679 \end{tabular} 680 \end{flushleft} 681 The derived exception @E2@ must be ordered first in the catch list, otherwise 682 the base exception @E1@ catches both exceptions. In the catch-and-reraise code 683 (right), the @E2@ handler catches exceptions from both @foo@ and 684 @bar@. However, the reraise misses the following catch clause. To fix this 685 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the 686 reraise, and its handler must duplicate the inner handler code for @bar@. To 687 generalize, this fix for any amount of inheritance and complexity of try 688 statement requires a technique called \emph{try-block 689 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is 690 sufficient to state that conditional catch is more expressive than 691 catch-and-reraise in terms of complexity. 692 693 \begin{comment} 694 That is, they have the same behaviour in isolation. 695 Two things can expose differences between these cases. 696 697 One is the existence of multiple handlers on a single try statement. 698 A reraise skips all later handlers for a try statement but a conditional 699 catch does not. 700 % Hence, if an earlier handler contains a reraise later handlers are 701 % implicitly skipped, with a conditional catch they are not. 702 Still, they are equivalently powerful, 703 both can be used two mimic the behaviour of the other, 704 as reraise can pack arbitrary code in the handler and conditional catches 705 can put arbitrary code in the predicate. 706 % I was struggling with a long explanation about some simple solutions, 707 % like repeating a condition on later handlers, and the general solution of 708 % merging everything together. I don't think it is useful though unless its 709 % for a proof. 710 % https://en.cppreference.com/w/cpp/language/throw 711 712 The question then becomes ``Which is a better default?" 713 We believe that not skipping possibly useful handlers is a better default. 714 If a handler can handle an exception it should and if the handler can not 715 handle the exception then it is probably safer to have that explicitly 716 described in the handler itself instead of implicitly described by its 717 ordering with other handlers. 718 % Or you could just alter the semantics of the throw statement. The handler 719 % index is in the exception so you could use it to know where to start 720 % searching from in the current try statement. 721 % No place for the `goto else;` metaphor. 722 723 The other issue is all of the discussion above assumes that the only 724 way to tell apart two raises is the exception being raised and the remaining 725 search path. 726 This is not true generally, the current state of the stack can matter in 727 a number of cases, even only for a stack trace after an program abort. 728 But \CFA has a much more significant need of the rest of the stack, the 729 default handlers for both termination and resumption. 730 731 % For resumption it turns out it is possible continue a raise after the 732 % exception has been caught, as if it hadn't been caught in the first place. 733 This becomes a problem combined with the stack unwinding used in termination 734 exception handling. 735 The stack is unwound before the handler is installed, and hence before any 736 reraises can run. So if a reraise happens the previous stack is gone, 737 the place on the stack where the default handler was supposed to run is gone, 738 if the default handler was a local function it may have been unwound too. 739 There is no reasonable way to restore that information, so the reraise has 740 to be considered as a new raise. 741 This is the strongest advantage conditional catches have over reraising, 742 they happen before stack unwinding and avoid this problem. 743 744 % The one possible disadvantage of conditional catch is that it runs user 745 % code during the exception search. While this is a new place that user code 746 % can be run destructors and finally clauses are already run during the stack 747 % unwinding. 729 (There is a simpler solution if @handle_a@ never raises exceptions, 730 using nested try statements.) 731 732 % } catch (an_exception * e ; check_a(e)) { 733 % handle_a(e); 734 % } catch (exception_t * e ; !(virtual an_exception *)e && check_b(e)) { 735 % handle_b(e); 736 % } 748 737 % 749 % https://www.cplusplus.com/reference/exception/current_exception/ 750 % `exception_ptr current_exception() noexcept;` 751 % https://www.python.org/dev/peps/pep-0343/ 752 \end{comment} 738 % } catch (an_exception * e) 739 % if (check_a(e)) { 740 % handle_a(e); 741 % } else throw; 742 % } catch (exception_t * e) 743 % if (check_b(e)) { 744 % handle_b(e); 745 % } else throw; 746 % } 747 In similar simple examples translating from re-raise to conditional catch 748 takes less code but it does not have a general trivial solution either. 749 750 So, given that the two patterns do not trivially translate into each other, 751 it becomes a matter of which on should be encouraged and made the default. 752 From the premise that if a handler that could handle an exception then it 753 should, it follows that checking as many handlers as possible is preferred. 754 So conditional catch and checking later handlers is a good default. 753 755 754 756 \section{Finally Clauses} … … 766 768 The @FINALLY_BLOCK@ is executed when the try statement is removed from the 767 769 stack, including when the @GUARDED_BLOCK@ finishes, any termination handler 768 finishes ,or during an unwind.770 finishes or during an unwind. 769 771 The only time the block is not executed is if the program is exited before 770 772 the stack is unwound. … … 786 788 they have their own strengths, similar to top-level function and lambda 787 789 functions with closures. 788 Destructors take more work for their creation, but if there is clean-up code790 Destructors take more work to create, but if there is clean-up code 789 791 that needs to be run every time a type is used, they are much easier 790 to set-up .792 to set-up for each use. % It's automatic. 791 793 On the other hand finally clauses capture the local context, so is easy to 792 794 use when the clean-up is not dependent on the type of a variable or requires … … 804 806 raise, this exception is not used in matching only to pass information about 805 807 the cause of the cancellation. 806 Final y, since a cancellation only unwinds and forwards, there is no default handler.808 Finally, as no handler is provided, there is no default handler. 807 809 808 810 After @cancel_stack@ is called the exception is copied into the EHM's memory … … 815 817 After the main stack is unwound there is a program-level abort. 816 818 817 The reasons for this semantics in a sequential program is that there is no more code to execute.818 This semantics also applies to concurrent programs, too, even if threads are running.819 That is, if any threads starts a cancellation, it implies all threads terminate. 820 Keeping the same behaviour in sequential and concurrent programs is simple.821 Also, even in concurrent programs there may not currently be any other stacks 822 and even if other stacks do exist, main has no way to know where they are.819 The first reason for this behaviour is for sequential programs where there 820 is only one stack, and hence to stack to pass information to. 821 Second, even in concurrent programs, the main stack has no dependency 822 on another stack and no reliable way to find another living stack. 823 Finally, keeping the same behaviour in both sequential and concurrent 824 programs is simple and easy to understand. 823 825 824 826 \paragraph{Thread Stack} … … 850 852 851 853 With explicit join and a default handler that triggers a cancellation, it is 852 possible to cascade an error across any number of threads, cleaning up each 854 possible to cascade an error across any number of threads, 855 alternating between the resumption (possibly termination) and cancellation, 856 cleaning up each 853 857 in turn, until the error is handled or the main thread is reached. 854 858 … … 863 867 caller's context and passes it to the internal report. 864 868 865 A coroutine only knows of two other coroutines, its starter and its last resumer. 869 A coroutine only knows of two other coroutines, 870 its starter and its last resumer. 866 871 The starter has a much more distant connection, while the last resumer just 867 872 (in terms of coroutine state) called resume on this coroutine, so the message … … 869 874 870 875 With a default handler that triggers a cancellation, it is possible to 871 cascade an error across any number of coroutines, cleaning up each in turn, 876 cascade an error across any number of coroutines, 877 alternating between the resumption (possibly termination) and cancellation, 878 cleaning up each in turn, 872 879 until the error is handled or a thread stack is reached. 873 874 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you875 talk about handling a cancellation in the last sentence. Which is correct?} -
doc/theses/andrew_beach_MMath/intro.tex
re56eabac rd8f8d08 11 11 12 12 % Now take a step back and explain what exceptions are generally. 13 Exception handling provides dynamic inter-function control flow. 13 14 A language's EHM is a combination of language syntax and run-time 14 components that are used to construct, raise, and handle exceptions, 15 including all control flow. 16 Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust). 17 Exception handling provides dynamic inter-function control flow. 15 components that construct, raise, propagate and handle exceptions, 16 to provide all of that control flow. 18 17 There are two forms of exception handling covered in this thesis: 19 18 termination, which acts as a multi-level return, 20 19 and resumption, which is a dynamic function call. 21 % PAB: Maybe this sentence was suppose to be deleted? 22 Termination handling is much more common, 23 to the extent that it is often seen as the only form of handling. 24 % PAB: I like this sentence better than the next sentence. 25 % This separation is uncommon because termination exception handling is so 26 % much more common that it is often assumed. 27 % WHY: Mention other forms of continuation and \cite{CommonLisp} here? 28 29 Exception handling relies on the concept of nested functions to create handlers that deal with exceptions. 20 % About other works: 21 Often, when this separation is not made, termination exceptions are assumed 22 as they are more common and may be the only form of handling provided in 23 a language. 24 25 All types of exception handling link a raise with a handler. 26 Both operations are usually language primitives, although raises can be 27 treated as a primitive function that takes an exception argument. 28 Handlers are more complex as they are added to and removed from the stack 29 during execution, must specify what they can handle and give the code to 30 handle the exception. 31 32 Exceptions work with different execution models but for the descriptions 33 that follow a simple call stack, with functions added and removed in a 34 first-in-last-out order, is assumed. 35 36 Termination exception handling searches the stack for the handler, then 37 unwinds the stack to where the handler was found before calling it. 38 The handler is run inside the function that defined it and when it finishes 39 it returns control to that function. 30 40 \begin{center} 31 \begin{tabular}[t]{ll} 32 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] 33 void f( void (*hp)() ) { 34 hp(); 35 } 36 void g( void (*hp)() ) { 37 f( hp ); 38 } 39 void h( int @i@, void (*hp)() ) { 40 void @handler@() { // nested 41 printf( "%d\n", @i@ ); 42 } 43 if ( i == 1 ) hp = handler; 44 if ( i > 0 ) h( i - 1, hp ); 45 else g( hp ); 46 } 47 h( 2, 0 ); 48 \end{lstlisting} 49 & 50 \raisebox{-0.5\totalheight}{\input{handler}} 51 \end{tabular} 41 \input{callreturn} 52 42 \end{center} 53 The nested function @handler@ in the second stack frame is explicitly passed to function @f@. 54 When this handler is called in @f@, it uses the parameter @i@ in the second stack frame, which is accessible by an implicit lexical-link pointer. 55 Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler. 56 Exception handling extends this idea by eliminating explicit handler passing, and instead, performing a stack search for a handler that matches some criteria (conditional dynamic call), and calls the handler at the top of the stack. 57 It is the runtime search $O(N)$ that differentiates an EHM call (raise) from normal dynamic call $O(1)$ via a function or virtual-member pointer. 58 59 Termination exception handling searches the stack for a handler, unwinds the stack to the frame containing the matching handler, and calling the handler at the top of the stack. 60 \begin{center} 61 \input{termination} 62 \end{center} 63 Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call. 64 After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}. 65 Unwinding allows recover to any previous 66 function on the stack, skipping any functions between it and the 67 function containing the matching handler. 68 69 Resumption exception handling searches the stack for a handler, does \emph{not} unwind the stack to the frame containing the matching handler, and calls the handler at the top of the stack. 43 44 Resumption exception handling searches the stack for a handler and then calls 45 it without removing any other stack frames. 46 The handler is run on top of the existing stack, often as a new function or 47 closure capturing the context in which the handler was defined. 48 After the handler has finished running it returns control to the function 49 that preformed the raise, usually starting after the raise. 70 50 \begin{center} 71 51 \input{resumption} 72 52 \end{center} 73 After the handler returns, control continues after the resume in @f@ (dynamic return).74 Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.75 53 76 54 Although a powerful feature, exception handling tends to be complex to set up 77 55 and expensive to use 78 56 so it is often limited to unusual or ``exceptional" cases. 79 The classic example is error handling, where exceptions are used to80 remove error handling logic from the main execution path, while paying57 The classic example is error handling, exceptions can be used to 58 remove error handling logic from the main execution path, and pay 81 59 most of the cost only when the error actually occurs. 82 60 … … 88 66 some of the underlying tools used to implement and express exception handling 89 67 in other languages are absent in \CFA. 90 Still the resulting basicsyntax resembles that of other languages:91 \begin{ lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]92 @try@{68 Still the resulting syntax resembles that of other languages: 69 \begin{cfa} 70 try { 93 71 ... 94 72 T * object = malloc(request_size); 95 73 if (!object) { 96 @throw@OutOfMemory{fixed_allocation, request_size};74 throw OutOfMemory{fixed_allocation, request_size}; 97 75 } 98 76 ... 99 } @catch@(OutOfMemory * error) {77 } catch (OutOfMemory * error) { 100 78 ... 101 79 } 102 \end{ lstlisting}80 \end{cfa} 103 81 % A note that yes, that was a very fast overview. 104 82 The design and implementation of all of \CFA's EHM's features are … … 107 85 108 86 % The current state of the project and what it contributes. 109 The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code. 110 In addition, 111 a suite of tests and performance benchmarks were created as part of this project. 112 The \CFA implementation techniques are generally applicable in other programming 87 All of these features have been implemented in \CFA, 88 covering both changes to the compiler and the run-time. 89 In addition, a suite of test cases and performance benchmarks were created 90 along side the implementation. 91 The implementation techniques are generally applicable in other programming 113 92 languages and much of the design is as well. 114 Some parts of the EHM use features unique to \CFA, and hence, 115 are harder to replicate in other programming languages. 116 % Talk about other programming languages. 117 Three well known programming languages with EHMs, %/exception handling 118 C++, Java and Python are examined in the performance work. However, these languages focus on termination 119 exceptions, so there is no comparison with resumption. 93 Some parts of the EHM use other features unique to \CFA and would be 94 harder to replicate in other programming languages. 120 95 121 96 The contributions of this work are: 122 97 \begin{enumerate} 123 98 \item Designing \CFA's exception handling mechanism, adapting designs from 124 other programming languages ,and creating new features.125 \item Implementing stack unwinding forthe \CFA EHM, including updating126 the \CFA compiler and run-time environment to generate and execute the EHM code.127 \item Design ing and implementinga prototype virtual system.99 other programming languages and creating new features. 100 \item Implementing stack unwinding and the \CFA EHM, including updating 101 the \CFA compiler and the run-time environment. 102 \item Designed and implemented a prototype virtual system. 128 103 % I think the virtual system and per-call site default handlers are the only 129 104 % "new" features, everything else is a matter of implementation. 130 \item Creating tests and performance benchmarks to compare with EHM's in other languages. 105 \item Creating tests to check the behaviour of the EHM. 106 \item Creating benchmarks to check the performances of the EHM, 107 as compared to other languages. 131 108 \end{enumerate} 132 109 133 %\todo{I can't figure out a good lead-in to the roadmap.} 134 The thesis is organization as follows.135 The next section and parts of \autoref{c:existing} cover existing EHMs.136 New \CFAEHM features are introduced in \autoref{c:features},110 The rest of this thesis is organized as follows. 111 The current state of exceptions is covered in \autoref{s:background}. 112 The existing state of \CFA is also covered in \autoref{c:existing}. 113 New EHM features are introduced in \autoref{c:features}, 137 114 covering their usage and design. 138 115 That is followed by the implementation of these features in 139 116 \autoref{c:implement}. 140 Performance results are presented in \autoref{c:performance}. 141 Summing up and possibilities for extending this project are discussed in \autoref{c:future}. 117 Performance results are examined in \autoref{c:performance}. 118 Possibilities to extend this project are discussed in \autoref{c:future}. 119 Finally, the project is summarized in \autoref{c:conclusion}. 142 120 143 121 \section{Background} 144 122 \label{s:background} 145 123 146 Exception handling is a well examined areain programming languages,147 with papers on the subject dating back the 70s~\cite{Goodenough75}.124 Exception handling has been examined before in programming languages, 125 with papers on the subject dating back 70s.\cite{Goodenough75} 148 126 Early exceptions were often treated as signals, which carried no information 149 except their identity. Ada ~\cite{Ada} still uses this system.127 except their identity. Ada still uses this system.\todo{cite Ada} 150 128 151 129 The modern flag-ship for termination exceptions is \Cpp, 152 130 which added them in its first major wave of non-object-orientated features 153 131 in 1990. 154 % https://en.cppreference.com/w/cpp/language/history 155 While many EHMs have special exception types, 156 \Cpp has the ability to use any type as an exception. 157 However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from 132 \todo{cite https://en.cppreference.com/w/cpp/language/history} 133 Many EHMs have special exception types, 134 however \Cpp has the ability to use any type as an exception. 135 These were found to be not very useful and have been pushed aside for classes 136 inheriting from 158 137 \code{C++}{std::exception}. 159 While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can 160 be done with the caught value because nothing is known about it. 161 Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as 162 the ability to print a message when the exception is raised but not caught) and all 138 Although there is a special catch-all syntax (@catch(...)@) there are no 139 operations that can be performed on the caught value, not even type inspection. 140 Instead the base exception-type \code{C++}{std::exception} defines common 141 functionality (such as 142 the ability to describe the reason the exception was raised) and all 163 143 exceptions have this functionality. 164 Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth 165 any lost in flexibility from limiting exceptions types to classes. 166 167 Java~\cite{Java} was the next popular language to use exceptions. 168 Its exception system largely reflects that of \Cpp, except it requires 169 exceptions to be a subtype of \code{Java}{java.lang.Throwable} 144 That trade-off, restricting usable types to gain guaranteed functionality, 145 is almost universal now, as without some common functionality it is almost 146 impossible to actually handle any errors. 147 148 Java was the next popular language to use exceptions. \todo{cite Java} 149 Its exception system largely reflects that of \Cpp, except that requires 150 you throw a child type of \code{Java}{java.lang.Throwable} 170 151 and it uses checked exceptions. 171 Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise. 172 Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions. 173 Making exception information explicit, improves clarity and 174 safety, but can slow down programming. 175 For example, programming complexity increases when dealing with high-order methods or an overly specified 176 throws clause. However some of the issues are more 177 programming annoyances, such as writing/updating many exception signatures after adding or remove calls. 178 Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide. 179 For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus 180 repairing or recovering from the exception. 152 Checked exceptions are part of a function's interface, 153 the exception signature of the function. 154 Every function that could be raised from a function, either directly or 155 because it is not handled from a called function, is given. 156 Using this information, it is possible to statically verify if any given 157 exception is handled and guarantee that no exception will go unhandled. 158 Making exception information explicit improves clarity and safety, 159 but can slow down or restrict programming. 160 For example, programming high-order functions becomes much more complex 161 if the argument functions could raise exceptions. 162 However, as odd it may seem, the worst problems are rooted in the simple 163 inconvenience of writing and updating exception signatures. 164 This has caused Java programmers to develop multiple programming ``hacks'' 165 to circumvent checked exceptions, negating their advantages. 166 One particularly problematic example is the ``catch-and-ignore'' pattern, 167 where an empty handler is used to handle an exception without doing any 168 recovery or repair. In theory that could be good enough to properly handle 169 the exception, but more often is used to ignore an exception that the 170 programmer does not feel is worth the effort of handling it, for instance if 171 they do not believe it will ever be raised. 172 If they are incorrect the exception will be silenced, while in a similar 173 situation with unchecked exceptions the exception would at least activate 174 the language's unhandled exception code (usually program abort with an 175 error message). 181 176 182 177 %\subsection 183 178 Resumption exceptions are less popular, 184 although resumption is as old as termination; 185 hence, few 179 although resumption is as old as termination; hence, few 186 180 programming languages have implemented them. 187 181 % http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/ 188 182 % CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf 189 Mesa ~\cite{Mesa} is one programming languages that did.Experience with Mesa190 is quoted as being one of the reasons resumptions are not183 Mesa is one programming language that did.\todo{cite Mesa} Experience with Mesa 184 is quoted as being one of the reasons resumptions were not 191 185 included in the \Cpp standard. 192 186 % https://en.wikipedia.org/wiki/Exception_handling 193 As a result, resumption has ignored in main-stream programming languages. 194 However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading). 195 While rejecting resumption might have been the right decision in the past, there are decades 196 of developments in computer science that have changed the situation. 197 Some of these developments, such as functional programming's resumption 198 equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success. 199 A complete reexamination of resumptions is beyond this thesis, but their re-emergence is 200 enough to try them in \CFA. 187 Since then resumptions have been ignored in main-stream programming languages. 188 However, resumption is being revisited in the context of decades of other 189 developments in programming languages. 190 While rejecting resumption may have been the right decision in the past, 191 the situation has changed since then. 192 Some developments, such as the function programming equivalent to resumptions, 193 algebraic effects\cite{Zhang19}, are enjoying success. 194 A complete reexamination of resumptions is beyond this thesis, 195 but there reemergence is enough to try them in \CFA. 201 196 % Especially considering how much easier they are to implement than 202 % termination exceptions .203 204 %\subsection 205 Functional languages tend to use other solutions for their primary EHM,206 but exception-like constructs still appear.207 Termination appears in error construct, which marks the result of an208 expression as an error; the reafter, the result of any expression that tries to use it is also an209 error, and so on until an appropriate handler is reached.197 % termination exceptions and how much Peter likes them. 198 199 %\subsection 200 Functional languages tend to use other solutions for their primary error 201 handling mechanism, but exception-like constructs still appear. 202 Termination appears in the error construct, which marks the result of an 203 expression as an error; then the result of any expression that tries to use 204 it also results in an error, and so on until an appropriate handler is reached. 210 205 Resumption appears in algebraic effects, where a function dispatches its 211 206 side-effects to its caller for handling. 212 207 213 208 %\subsection 214 Some programming languages have moved to a restricted kind of EHM 215 called``panic".216 In Rust ~\cite{Rust}, a panic is just a program level abort that may be implemented by217 unwinding the stack like in termination exception handling. 209 More recently exceptions seem to be vanishing from newer programming 210 languages, replaced by ``panic". 211 In Rust, a panic is just a program level abort that may be implemented by 212 unwinding the stack like in termination exception handling.\todo{cite Rust} 218 213 % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html 219 In Go~\cite{Go}, a panicis very similar to a termination, except it only supports214 Go's panic through is very similar to a termination, except it only supports 220 215 a catch-all by calling \code{Go}{recover()}, simplifying the interface at 221 the cost of flexibility. 216 the cost of flexibility.\todo{cite Go} 222 217 223 218 %\subsection 224 219 While exception handling's most common use cases are in error handling, 225 here are other ways to handle errors with comparisons toexceptions.220 here are some other ways to handle errors with comparisons with exceptions. 226 221 \begin{itemize} 227 222 \item\emph{Error Codes}: 228 This pattern has a function return an enumeration (or just a set of fixed values) to indicate 229 if an error occurred and possibly which error it was. 230 231 Error codes mix exceptional and normal values, artificially enlarging the type and/or value range. 232 Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result. 233 However, the main issue with error codes is forgetting to checking them, 223 This pattern has a function return an enumeration (or just a set of fixed 224 values) to indicate if an error has occurred and possibly which error it was. 225 226 Error codes mix exceptional/error and normal values, enlarging the range of 227 possible return values. This can be addressed with multiple return values 228 (or a tuple) or a tagged union. 229 However, the main issue with error codes is forgetting to check them, 234 230 which leads to an error being quietly and implicitly ignored. 235 Some new languages have tools that issue warnings, if the error code is 236 discarded to avoid this problem. 237 Checking error codes also results in bloating the main execution path, especially if an error is not dealt with locally and has to be cascaded down the call stack to a higher-level function.. 231 Some new languages and tools will try to issue warnings when an error code 232 is discarded to avoid this problem. 233 Checking error codes also bloats the main execution path, 234 especially if the error is not handled immediately hand has to be passed 235 through multiple functions before it is addressed. 238 236 239 237 \item\emph{Special Return with Global Store}: 240 Some functions only return a boolean indicating success or failure 241 and store the exact reason for the error in a fixed global location. 242 For example, many C routines return non-zero or -1, indicating success or failure, 243 and write error details into the C standard variable @errno@. 244 245 This approach avoids the multiple results issue encountered with straight error codes 246 but otherwise has many (if not more) of the disadvantages. 247 For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency. 238 Similar to the error codes pattern but the function itself only returns 239 that there was an error 240 and store the reason for the error in a fixed global location. 241 For example many routines in the C standard library will only return some 242 error value (such as -1 or a null pointer) and the error code is written into 243 the standard variable @errno@. 244 245 This approach avoids the multiple results issue encountered with straight 246 error codes but otherwise has the same disadvantages and more. 247 Every function that reads or writes to the global store must agree on all 248 possible errors and managing it becomes more complex with concurrency. 248 249 249 250 \item\emph{Return Union}: … … 254 255 so that one type can be used everywhere in error handling code. 255 256 256 This pattern is very popular in functional or any semi-functional language with257 primitive support for tagged unions (or algebraic data types).258 % We need listing Rust/rust to format code snip its from it.257 This pattern is very popular in any functional or semi-functional language 258 with primitive support for tagged unions (or algebraic data types). 259 % We need listing Rust/rust to format code snippets from it. 259 260 % Rust's \code{rust}{Result<T, E>} 260 The main advantage is providing for more information about an261 error , other than one of a fix-set of ids.262 While some languages use checked union access to force error-code checking, 263 it is still possible to bypass the checking. 264 The main disadvantage is again significant error code on the main execution path and cascading through called functions.261 The main advantage is that an arbitrary object can be used to represent an 262 error so it can include a lot more information than a simple error code. 263 The disadvantages include that the it does have to be checked along the main 264 execution and if there aren't primitive tagged unions proper usage can be 265 hard to enforce. 265 266 266 267 \item\emph{Handler Functions}: 267 This pattern implicitly associates functions with errors.268 On error, the function that produced the error implicitlycalls another function to268 This pattern associates errors with functions. 269 On error, the function that produced the error calls another function to 269 270 handle it. 270 271 The handler function can be provided locally (passed in as an argument, 271 272 either directly as as a field of a structure/object) or globally (a global 272 273 variable). 273 C++ uses this approach as its fallback system if exception handling fails, \eg 274 \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler} 275 276 Handler functions work a lot like resumption exceptions, without the dynamic handler search. 277 Therefore, setting setting up the handler can be more complex/expensive, especially if the handle must be passed through multiple function calls, but cheaper to call $O(1)$, and hence, 278 are more suited to frequent exceptional situations. 279 % The exception being global handlers if they are rarely change as the time 280 % in both cases shrinks towards zero. 274 C++ uses this approach as its fallback system if exception handling fails, 275 such as \snake{std::terminate_handler} and, for a time, 276 \snake{std::unexpected_handler}. 277 278 Handler functions work a lot like resumption exceptions, 279 but without the dynamic search for a handler. 280 Since setting up the handler can be more complex/expensive, 281 especially when the handler has to be passed through multiple layers of 282 function calls, but cheaper (constant time) to call, 283 they are more suited to more frequent (less exceptional) situations. 281 284 \end{itemize} 282 285 283 286 %\subsection 284 287 Because of their cost, exceptions are rarely used for hot paths of execution. 285 Therefore, there is an element of self-fulfilling prophecy for implementation 286 techniques to make exceptions cheap to set-up at the cost 287 of expensive usage. 288 This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common. 289 An iconic example is Python's @StopIteration@ exception that is thrown by 290 an iterator to indicate that it is exhausted, especially when combined with Python's heavy 291 use of the iterator-based for-loop. 288 Hence, there is an element of self-fulfilling prophecy as implementation 289 techniques have been focused on making them cheap to set-up, 290 happily making them expensive to use in exchange. 291 This difference is less important in higher-level scripting languages, 292 where using exception for other tasks is more common. 293 An iconic example is Python's \code{Python}{StopIteration} exception that 294 is thrown by an iterator to indicate that it is exhausted. 295 When paired with Python's iterator-based for-loop this will be thrown every 296 time the end of the loop is reached. 297 \todo{Cite Python StopIteration and for-each loop.} 292 298 % https://docs.python.org/3/library/exceptions.html#StopIteration -
doc/theses/andrew_beach_MMath/uw-ethesis.tex
re56eabac rd8f8d08 210 210 \lstMakeShortInline@ 211 211 \lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt} 212 % PAB causes problems with inline @=213 %\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}214 212 % Annotations from Peter: 215 213 \newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
Note: See TracChangeset
for help on using the changeset viewer.