- Timestamp:
- Apr 14, 2021, 10:06:22 AM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- f6106a6
- Parents:
- ea1c97b
- Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 2 deleted
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/Makefile
rea1c97b rde47a9d 1 1 ### Makefile for Andrew Beach's Masters Thesis 2 2 3 DOC = uw-ethesis.pdf 4 BASE = ${DOC:%.pdf=%} # remove suffix 5 # directory for latex clutter files 6 BUILD = build 7 TEXSRC = $(wildcard *.tex) 8 FIGSRC = $(wildcard *.fig) 9 BIBSRC = $(wildcard *.bib) 10 STYSRC = $(wildcard *.sty) 11 CLSSRC = $(wildcard *.cls) 12 TEXLIB = .:../../LaTeXmacros:${BUILD}: # common latex macros 13 BIBLIB = .:../../bibliography # common citation repository 3 DOC=uw-ethesis.pdf 4 BUILD=out 5 TEXSRC=$(wildcard *.tex) 6 BIBSRC=$(wildcard *.bib) 7 STYSRC=$(wildcard *.sty) 8 CLSSRC=$(wildcard *.cls) 9 TEXLIB= .:../../LaTeXmacros:${BUILD}: 10 BIBLIB= .:../../bibliography 14 11 15 MAKEFLAGS = --no-print-directory # --silent 16 VPATH = ${BUILD}12 # Since tex programs like to add their own file extensions: 13 BASE= ${DOC:%.pdf=%} 17 14 18 15 ### Special Rules: 19 16 20 17 .PHONY: all clean deepclean 21 .PRECIOUS: %.dvi %.ps # do not delete intermediate files22 18 23 19 ### Commands: 24 LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS &&latex -halt-on-error -output-directory=${BUILD}25 BIBTEX =BIBINPUTS=${BIBLIB} bibtex26 GLOSSARY =INDEXSTYLE=${BUILD} makeglossaries-lite20 LATEX=TEXINPUTS=${TEXLIB} pdflatex -halt-on-error -output-directory=${BUILD} 21 BIBTEX=BIBINPUTS=${BIBLIB} bibtex 22 GLOSSARY=INDEXSTYLE=${BUILD} makeglossaries-lite 27 23 28 ### Rules and Recip es:24 ### Rules and Recipies: 29 25 30 26 all: ${DOC} 31 27 32 ${BUILD}/ %.dvi: ${TEXSRC} ${FIGSRC:.fig=.tex} ${BIBSRC} ${STYSRC} ${CLSSRC} Makefile | ${BUILD}28 ${BUILD}/${DOC}: ${TEXSRC} ${BIBSRC} ${STYSRC} ${CLSSRC} Makefile | ${BUILD} 33 29 ${LATEX} ${BASE} 34 30 ${BIBTEX} ${BUILD}/${BASE} … … 37 33 ${LATEX} ${BASE} 38 34 35 ${DOC}: ${BUILD}/${DOC} 36 cp $< $@ 37 39 38 ${BUILD}: 40 39 mkdir $@ 41 40 42 %.pdf : ${BUILD}/%.ps | ${BUILD}43 ps2pdf $<44 45 %.ps : %.dvi | ${BUILD}46 dvips $< -o $@47 48 %.tex : %.fig | ${BUILD}49 fig2dev -L eepic $< > ${BUILD}/$@50 51 %.ps : %.fig | ${BUILD}52 fig2dev -L ps $< > ${BUILD}/$@53 54 %.pstex : %.fig | ${BUILD}55 fig2dev -L pstex $< > ${BUILD}/$@56 fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t57 58 41 clean: 59 @rm -frv ${BUILD} *.fig.bak42 -@rm -rv ${BUILD} 60 43 61 44 deepclean: clean 62 -@rm - fv ${DOC}45 -@rm -v ${DOC} -
doc/theses/andrew_beach_MMath/features.tex
rea1c97b rde47a9d 3 3 This chapter covers the design and user interface of the \CFA 4 4 exception-handling mechanism (EHM). % or exception system. 5 While an EHM is free to add many features,6 the following overview covers the basic features that all EHMs use, but it is not an7 exhaustive list of everything an EHM can do.8 5 9 6 % We should cover what is an exception handling mechanism and what is an … … 12 9 \paragraph{Raise / Handle} 13 10 An exception operation has two main parts: raise and handle. 11 These are the two parts that the user will write themselves and so 12 might be the only two pieces of the EHM that have any syntax. 14 13 These terms are sometimes also known as throw and catch but this work uses 15 14 throw/catch as a particular kind of raise/handle. 16 These are the two parts a programmer writes and so17 are the only two pieces of the EHM that have language syntax.18 15 19 16 \subparagraph{Raise} 20 The raise is the starting point for exception handling and usually how \PAB{This sentence is cut off.}21 Some well known examples include the @throw@ statementof \Cpp and Java and22 the \lstinline[language=Python]{raise}statement from Python.23 24 For this overview , a raise startsthe handling of an25 exception, which is called \newterm{raising} an exception. This simple description is sufficient26 forthe overview.17 The raise is the starting point for exception handling and usually how 18 Some well known examples include the throw statements of \Cpp and Java and 19 the raise statement from Python. 20 21 For this overview a raise does nothing more kick off the handling of an 22 exception, which is called raising the exception. This is inexact but close 23 enough for the broad strokes of the overview. 27 24 28 25 \subparagraph{Handle} 29 The purpose of raising an exception is to run user code to address (handle) the30 issue found at the raise point.31 The @try@ statement of \Cpp illustrates a common approach for specifying multiple handlers.32 A handler has three common features: the scope in which it applies, an33 exception label that describes what exceptions it can handle,and code to run34 that deals with the raised issue.35 Each handler can handle exceptions raised in th e region matching its36 exception label. For multiple matches, different EHMs have different rules for matching an exception to a handler label,37 such as ``best match" or ``first found".26 The purpose of most exception operations is to run some sort of handler that 27 contains user code. 28 The try statement of \Cpp illistrates the common features 29 Handlers have three common features: a region of code they apply to, an 30 exception label that describes what exceptions they handle and code to run 31 when they handle an exception. 32 Each handler can handle exceptions raised in that region that match their 33 exception label. Different EHMs will have different rules to pick a handler 34 if multipe handlers could be used such as ``best match" or ``first found". 38 35 39 36 \paragraph{Propagation} 40 After an exception is raised, comes the most complex step for the 41 EHM: finding and setting up the handler. This propagation of exception from raise to handler can be broken up into three 42 different tasks: searching, matching, and 43 installing the handler so it can execute. 44 45 \subparagraph{Searching} 46 The EHM searches for possible handlers that can be used to handle 47 the exception. Searching is usually independent of the exception that is 48 thrown and instead depends on the call stack: current function, its caller 37 After an exception is raised comes what is usually the biggest step for the 38 EHM, finding and setting up the handler. This can be broken up into three 39 different tasks: searching for a handler, matching against the handler and 40 installing the handler. 41 42 First the EHM must search for possible handlers that could be used to handle 43 the exception. Searching is usually independent of the exception that was 44 thrown and instead depends on the call stack, the current function, its caller 49 45 and repeating down the stack. 50 46 51 \subparagraph{Matching} 52 For each handler found, it compares the raised exception with the handler label to see which one is the 53 best match, and hence, which one should be used to handle the exception. 54 In languages where the best match is the first match, these two steps are often 55 intertwined, \ie a match check is performed immediately after the search finds 47 Second it much match the exception with each handler to see which one is the 48 best match and hence which one should be used to handle the exception. 49 In languages where the best match is the first match these two are often 50 intertwined, a match check is preformed immediately after the search finds 56 51 a possible handler. 57 52 58 \subparagraph{Installing} 59 After a handler is chosen, it must be made ready to run. 60 This step varies widely to fit with the rest of the 61 design of the EHM. The installation step might be trivial or it can be 53 Third, after a handler is chosen it must be made ready to run. 54 What this actually involves can vary widely to fit with the rest of the 55 design of the EHM. The installation step might be trivial or it could be 62 56 the most expensive step in handling an exception. The latter tends to be the 63 57 case when stack unwinding is involved. 64 An alternate action occurs if no appropriate handler is found, then some implicit action 65 is performed. This step is only required with unchecked 66 exceptions as checked exceptions (Java) promise a handler is always found. The implicit action 67 also installs a handler but it is a default handle that may be 58 59 As an alternate third step if no appropriate handler is found then some sort 60 of recovery has to be preformed. This is only required with unchecked 61 exceptions as checked exceptions can promise that a handler is found. It also 62 is also installing a handler but it is a special default that may be 68 63 installed differently. 69 64 70 65 \subparagraph{Hierarchy} 71 Some EHM (\CFA, Java) organize exceptions in a hierarchical structure.72 This strat egy is borrowed from object-orientated languages where the66 In \CFA the EHM uses a hierarchial system to organise its exceptions. 67 This stratagy is borrowed from object-orientated languages where the 73 68 exception hierarchy is a natural extension of the object hierarchy. 74 69 75 70 Consider the following hierarchy of exceptions: 76 71 \begin{center} 77 \input{exceptionHierarchy} 72 \setlength{\unitlength}{4000sp}% 73 \begin{picture}(1605,612)(2011,-1951) 74 \put(2100,-1411){\vector(1, 0){225}} 75 \put(3450,-1411){\vector(1, 0){225}} 76 \put(3550,-1411){\line(0,-1){225}} 77 \put(3550,-1636){\vector(1, 0){150}} 78 \put(3550,-1636){\line(0,-1){225}} 79 \put(3550,-1861){\vector(1, 0){150}} 80 \put(2025,-1490){\makebox(0,0)[rb]{\LstBasicStyle{exception}}} 81 \put(2400,-1460){\makebox(0,0)[lb]{\LstBasicStyle{arithmetic}}} 82 \put(3750,-1460){\makebox(0,0)[lb]{\LstBasicStyle{underflow}}} 83 \put(3750,-1690){\makebox(0,0)[lb]{\LstBasicStyle{overflow}}} 84 \put(3750,-1920){\makebox(0,0)[lb]{\LstBasicStyle{zerodivide}}} 85 \end{picture}% 78 86 \end{center} 87 79 88 A handler labelled with any given exception can handle exceptions of that 80 89 type or any child type of that exception. The root of the exception hierarchy 81 (here \ lstinline[language=C++]{exception}) acts as a catch-all, leaf types catch single types90 (here \texttt{exception}) acts as a catch-all, leaf types catch single types 82 91 and the exceptions in the middle can be used to catch different groups of 83 92 related exceptions. 84 93 85 94 This system has some notable advantages, such as multiple levels of grouping, 86 the ability for libraries to add new exception types ,and the isolation87 between different sub-hierarchies. This capability had to be adapted for \CFA, which isa95 the ability for libraries to add new exception types and the isolation 96 between different sub-hierarchies. So the design was adapted for a 88 97 non-object-orientated language. 89 98 … … 91 100 92 101 \paragraph{Completion} 93 After the handler has returned, the entire exception operation has to complete 94 and continue executing somewhere. This step is usually simple, 95 both logically and in its implementation, as the installation of the handler 96 usually does the preparation. 97 The EHM can return control to different places, 98 where the most common are after the handler definition or after the raise. 102 After the handler has finished the entire exception operation has to complete 103 and continue executing somewhere else. This step is usually very simple 104 both logically and in its implementation as the installation of the handler 105 usually does the heavy lifting. 106 107 The EHM can return control to many different places. 108 However, the most common is after the handler definition and the next most 109 common is after the raise. 99 110 100 111 \paragraph{Communication} 101 For effective exception handling, additional information is usually passed from the raise, 102 where this basic model only communicates the exception's identity. A common 103 methods for communication is putting fields into an exception and 104 allowing a handler to access these fields via an exception instance in the handler's scope. 112 For effective exception handling, additional information is usually required 113 as this base model only communicates the exception's identity. Common 114 additional methods of communication are putting fields on an exception and 115 allowing a handler to access the lexical scope it is defined in (usually 116 a function's local variables). 117 118 \paragraph{Other Features} 119 Any given exception handling mechanism is free at add other features on top 120 of this. This is an overview of the base that all EHMs use but it is not an 121 exaustive list of everything an EHM can do. 105 122 106 123 \section{Virtuals} 107 Virtual types and casts are not part of an EHMnor are they108 required for an EHM. But as pointed out, an object-oriented-style hierarchy is an109 excellent way of organizing exceptions. Hence,a minimal virtual system has been added110 to \CFA to support hierarchical exceptions.124 Virtual types and casts are not part of the exception system nor are they 125 required for an exception system. But an object-oriented style hierarchy is a 126 great way of organizing exceptions so a minimal virtual system has been added 127 to \CFA. 111 128 112 129 The virtual system supports multiple ``trees" of types. Each tree is 113 130 a simple hierarchy with a single root type. Each type in a tree has exactly 114 one parent - - except for the root type with zero parents -- and any131 one parent - except for the root type which has zero parents - and any 115 132 number of children. 116 133 Any type that belongs to any of these trees is called a virtual type. … … 118 135 % A type's ancestors are its parent and its parent's ancestors. 119 136 % The root type has no ancestors. 120 % A type's descendents are its children and its children's descendents. 121 122 Every virtual type has a list of virtual members. Children inherit 123 their parent's virtual members but may add new members to it. 124 It is important to note that these are virtual members, not virtual methods of an object type. 125 However, as \CFA has function pointers, they can be used to mimic virtual 126 methods. 127 128 Each virtual type has a unique id. 129 The unique id for the virtual type and all its virtual members are combined 130 into a virtual-table type. Each virtual type has a pointer to a virtual table 137 % A type's decendents are its children and its children's decendents. 138 139 Every virtual type also has a list of virtual members. Children inherit 140 their parent's list of virtual members but may add new members to it. 141 It is important to note that these are virtual members, not virtual methods. 142 However as function pointers are allowed they can be used to mimic virtual 143 methods as well. 144 145 The unique id for the virtual type and all the virtual members are combined 146 into a virtual table type. Each virtual type has a pointer to a virtual table 131 147 as a hidden field. 132 148 133 Up to this point, a virtual system is similar to ones found in object-oriented134 languages but this is where \CFA diverges. Objects encapsulate a149 Up until this point the virtual system is a lot like ones found in object- 150 orientated languages but this where they diverge. Objects encapsulate a 135 151 single set of behaviours in each type, universally across the entire program, 136 and indeed all programs that use that type definition. In this sense ,the152 and indeed all programs that use that type definition. In this sense the 137 153 types are ``closed" and cannot be altered. 138 However, \CFA types do not encapsulate any behaviour. Instead, traits are used and 139 types can satisfy a trait, stop satisfying a trait, or satisfy the same 140 trait in a different way depending on the lexical context. In this sense, the types are 141 ``open" as their behaviour can change in different scopes. This capability means it is impossible to pick 142 a single set of functions that represent the type's virtual members. 143 144 Hence, \CFA does not have a single virtual table for a type. A user can define different virtual tables, 145 which are filled in at their declaration and given a name. 146 That name is used as the virtual table, even if it is defined locally 147 inside a function, although lifetime issues must be considered. 148 Specifically, an object of a virtual type is ``bound" to a virtual table instance, which 154 155 However in \CFA types do not encapsulate any behaviour. Traits are local and 156 types can begin to statify a trait, stop satifying a trait or satify the same 157 trait in a different way with each new definition. In this sense they are 158 ``open" as they can change at any time. This means it is implossible to pick 159 a single set of functions that repersent the type. 160 161 So we don't try to have a single value. The user can define virtual tables 162 which are filled in at their declaration and given a name. Anywhere you can 163 see that name you can use that virtual table; even if it is defined locally 164 inside a function, although in that case you must respect its lifetime. 165 166 An object of a virtual type is ``bound" to a virtual table instance which 149 167 sets the virtual members for that object. The virtual members can be accessed 150 168 through the object. … … 160 178 \Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be 161 179 a pointer to a virtual type. 162 The cast dynamically checks if the @EXPRESSION@ type is the same or a sub type180 The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type 163 181 of @TYPE@, and if true, returns a pointer to the 164 182 @EXPRESSION@ object, otherwise it returns @0p@ (null pointer). … … 178 196 \end{cfa} 179 197 The trait is defined over two types, the exception type and the virtual table 180 type. Th ese type should have a one-to-one relationship:each exception type has only one virtual198 type. This should be one-to-one, each exception type has only one virtual 181 199 table type and vice versa. The only assertion in the trait is 182 200 @get_exception_vtable@, which takes a pointer of the exception type and 183 returns a reference to the virtual -table type-instance.201 returns a reference to the virtual table type instance. 184 202 185 203 The function @get_exception_vtable@ is actually a constant function. 186 Regardless of the value passed in (including the null pointer) it 187 return s a reference to the virtual-table instance for that type.188 The reason it is a function instead of a constant is t omake type189 annotations easier to write using the exception type rather thanthe190 virtual -table type, which usually has a mangled name because it is an internal component of the EHM.204 Regardless of the value passed in (including the null pointer) it should 205 return a reference to the virtual table instance for that type. 206 The reason it is a function instead of a constant is that it make type 207 annotations easier to write as you can use the exception type instead of the 208 virtual table type; which usually has a mangled name. 191 209 % Also \CFA's trait system handles functions better than constants and doing 192 210 % it this way reduce the amount of boiler plate we need. … … 194 212 % I did have a note about how it is the programmer's responsibility to make 195 213 % sure the function is implemented correctly. But this is true of every 196 % similar system I know of (except Ada's I guess) so I took it out. 197 198 There are two more exception traits defined as follows: 214 % similar system I know of (except Agda's I guess) so I took it out. 215 216 There are two more traits for exceptions @is_termination_exception@ and 217 @is_resumption_exception@. They are defined as follows: 218 199 219 \begin{cfa} 200 220 trait is_termination_exception( … … 208 228 }; 209 229 \end{cfa} 210 These traits ensure a given type and virtual type are an 211 exception type and defines one of the two default handlers. The default handlers 212 are used in the main exception-handling operations and discussed in detail in \VRef{s:ExceptionHandling}. 213 214 However, all three of these traits are tricky to use directly. 215 While there is a bit of repetition required, 216 the largest issue is that the virtual-table type is mangled and not in a user 217 facing way. So three macros are provided to wrap these traits 218 to simplify referring to the names: 230 231 In other words they make sure that a given type and virtual type is an 232 exception and defines one of the two default handlers. These default handlers 233 are used in the main exception handling operations \see{Exception Handling} 234 and their use will be detailed there. 235 236 However all three of these traits can be tricky to use directly. 237 There is a bit of repetition required but 238 the largest issue is that the virtual table type is mangled and not in a user 239 facing way. So there are three macros that can be used to wrap these traits 240 when you need to refer to the names: 219 241 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@. 220 242 221 These macrostake one or two arguments. The first argument is the name of the222 exception type. The macro passes the unmangled and mangled formto the trait.243 All take one or two arguments. The first argument is the name of the 244 exception type. Its unmangled and mangled form are passed to the trait. 223 245 The second (optional) argument is a parenthesized list of polymorphic 224 arguments. This argument is only usedwith polymorphic exceptions and the225 list ispassed to both types.226 In the current set-up ,the base name and the polymorphic arguments have to246 arguments. This argument should only with polymorphic exceptions and the 247 list will be passed to both types. 248 In the current set-up the base name and the polymorphic arguments have to 227 249 match so these macros can be used without losing flexibility. 228 250 … … 230 252 defined arithmetic exception: 231 253 \begin{cfa} 232 forall(Num | @IS_EXCEPTION(Arithmetic, Num)@)254 forall(Num | IS_EXCEPTION(Arithmetic, (Num))) 233 255 void some_math_function(Num & left, Num & right); 234 256 \end{cfa} 235 where the function may raise exception @Arithmetic@ or any of its decedents.236 257 237 258 \section{Exception Handling} 238 \label{s:ExceptionHandling} 239 \CFA provides two kinds of exception handling: termination and resumption. 240 These twin mechanisms are the core of the \CFA EHM and 241 multiple features are provided to support them. 242 This section covers the general patterns shared by the two kinds of exceptions and 243 then covers the individual detail operations. 244 245 Both mechanisms follow the same set of steps to do their operations. Both 246 start with the user performing an exception raise. 247 Then there is the handler search. If one is found, than the exception 248 is caught and the handler is run. When the handler returns, control returns to an 249 location appropriate for each kind of exception. 250 251 \begin{sloppypar} 252 If the search fails, an appropriate default handler, @defaultTermiationHandler@ 253 or @defaultResumptionHandler@, is run and control returns to the 254 appropriate location. 255 \end{sloppypar} 259 \CFA provides two kinds of exception handling, termination and resumption. 260 These twin operations are the core of the exception handling mechanism and 261 are the reason for the features of exceptions. 262 This section will cover the general patterns shared by the two operations and 263 then go on to cover the details each individual operation. 264 265 Both operations follow the same set of steps to do their operation. They both 266 start with the user preforming a throw on an exception. 267 Then there is the search for a handler, if one is found than the exception 268 is caught and the handler is run. After that control returns to normal 269 execution. 270 271 If the search fails a default handler is run and then control 272 returns to normal execution immediately. That is where the default handlers 273 @defaultTermiationHandler@ and @defaultResumptionHandler@ are used. 256 274 257 275 \subsection{Termination} 258 276 \label{s:Termination} 259 Termination handling is familiar and used in most programming 277 278 Termination handling is more familiar kind and used in most programming 260 279 languages with exception handling. 261 It is a dynamic, non-local goto. The raise starts searching, and if matched and handled, the stack is262 unwound and control (usually) continues in thefunction on263 the call stack containing the handler. Terminate is commonly used for an error whererecovery264 is impossible in the function performing the raise.280 It is dynamic, non-local goto. If a throw is successful then the stack will 281 be unwound and control will (usually) continue in a different function on 282 the call stack. They are commonly used when an error has occurred and recovery 283 is impossible in the current function. 265 284 266 285 % (usually) Control can continue in the current function but then a different 267 286 % control flow construct should be used. 268 287 269 A termination raiseis started with the @throw@ statement:288 A termination throw is started with the @throw@ statement: 270 289 \begin{cfa} 271 290 throw EXPRESSION; 272 291 \end{cfa} 273 292 The expression must return a reference to a termination exception, where the 274 termination exception is any type that satisfies trait 275 @is_termination_exception@ at the call site. Through \CFA's trait system, the 276 trait functions are implicitly passed into the hidden throw code and available 277 to the exception system while handling the exception. A new 278 @defaultTerminationHandler@ can be defined in any scope to change the throw's 279 unhandled behaviour (see below). 280 281 The throw must copy the provided exception into managed memory because the stack is unwounded. 282 The lifetime of the exception copy is managed by the exception runtime. 283 It is the user's responsibility to ensure the original exception is cleaned up, where allocating it on the unwound stack is sufficient. 284 285 The exception search walks the stack matching with the copied exception. 286 It starts from the throwing function and proceeds to the base of the stack, 293 termination exception is any type that satisfies @is_termination_exception@ 294 at the call site. 295 Through \CFA's trait system the functions in the traits are passed into the 296 throw code. A new @defaultTerminationHandler@ can be defined in any scope to 297 change the throw's behavior (see below). 298 299 The throw will copy the provided exception into managed memory. It is the 300 user's responsibility to ensure the original exception is cleaned up if the 301 stack is unwound (allocating it on the stack should be sufficient). 302 303 Then the exception system searches the stack using the copied exception. 304 It starts starts from the throw and proceeds to the base of the stack, 287 305 from callee to caller. 288 At each stack frame, a check is made for termination handlers defined by the306 At each stack frame, a check is made for resumption handlers defined by the 289 307 @catch@ clauses of a @try@ statement. 290 308 \begin{cfa} 291 309 try { 292 310 GUARDED_BLOCK 293 } catch (EXCEPTION_TYPE$\(_1\)$ [* NAME$\(_1\)$]) {311 } catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) { 294 312 HANDLER_BLOCK$\(_1\)$ 295 } catch (EXCEPTION_TYPE$\(_2\)$ [* NAME$\(_2\)$]) {313 } catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) { 296 314 HANDLER_BLOCK$\(_2\)$ 297 315 } 298 316 \end{cfa} 299 When viewed on its own, a @try@ statement with @catch@ clauses simply executes the statements in 300 the @GUARDED_BLOCK@, and when those are finished, the try statement finishes. 301 302 However, while the guarded statements are being executed, including any invoked 303 functions, a termination exception may be thrown. If that exception is not handled by a try 304 statement further up the stack, the handlers following the try block are now 305 searched for a matching termination exception-type from top to bottom. 306 307 Exception matching checks each @catch@ clasue from top to bottom, if the representation of the thrown exception-type is 308 the same or a descendant type of the exception types in the @catch@ clauses. If 309 it is the same or a descendant of @EXCEPTION_TYPE@$_i$, then the optional @NAME@$_i$ is 317 When viewed on its own a try statement will simply execute the statements in 318 @GUARDED_BLOCK@ and when those are finished the try statement finishes. 319 320 However, while the guarded statements are being executed, including any 321 functions they invoke, all the handlers following the try block are now 322 or any functions invoked from those 323 statements, throws an exception, and the exception 324 is not handled by a try statement further up the stack, the termination 325 handlers are searched for a matching exception type from top to bottom. 326 327 Exception matching checks the representation of the thrown exception-type is 328 the same or a descendant type of the exception types in the handler clauses. If 329 it is the same of a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is 310 330 bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$ 311 331 are executed. If control reaches the end of the handler, the exception is 312 freed and control continues after the @try@ statement. 313 314 If no termination handler is found during the search, the default termination 315 handler visible at the raise is called. Through \CFA's trait-system the best 316 default-handler match at the throw sight is used. This function is 317 passed the copied exception given to the raise. After the default handler is 318 run, control continues after the @throw@ statement. 319 320 There is a global @defaultTerminationHandler@ function that that is polymorphic 321 over all exception types allowing new default handlers to be defined for 322 different exception types and so different exception types can have different 323 default handlers. The global default termination-handler performs a 324 cancellation \see{\VRef{s:Cancellation}} on the current stack with the copied 325 exception. 332 freed and control continues after the try statement. 333 334 If no handler is found during the search then the default handler is run. 335 Through \CFA's trait system the best match at the throw sight will be used. 336 This function is run and is passed the copied exception. After the default 337 handler is run control continues after the throw statement. 338 339 There is a global @defaultTerminationHandler@ that cancels the current stack 340 with the copied exception. However it is generic over all exception types so 341 new default handlers can be defined for different exception types and so 342 different exception types can have different default handlers. 326 343 327 344 \subsection{Resumption} 328 345 \label{s:Resumption} 329 Resumption exception-handling is a less common counterpart to termination but is 330 just as old~\cite{Goodenough75} and is simpler to understand. 331 It is a dynamic, non-local function call (like Lisp). If the throw is successful, a 332 closure is taken from up the stack and executed, after which the throwing 333 function continues executing. 334 Resumption is used when an error occurred, and if the error is repaired, 346 347 Resumption exception handling is a less common form than termination but is 348 just as old~\cite{Goodenough75} and is in some sense simpler. 349 It is a dynamic, non-local function call. If the throw is successful a 350 closure will be taken from up the stack and executed, after which the throwing 351 function will continue executing. 352 These are most often used when an error occurred and if the error is repaired 335 353 then the function can continue. 336 354 337 An alternative approach is explicitly passing fixup functions with local338 closures up the stack to be called when an error occurs. However, fixup339 functions significantly expand the parameters list of functions, even when the340 fixup function is not used by a function but must be passed to other called341 functions.342 343 355 A resumption raise is started with the @throwResume@ statement: 344 356 \begin{cfa} 345 357 throwResume EXPRESSION; 346 358 \end{cfa} 347 Like termination, the expression must return a reference to a resumption 348 exception, where the resumption exception is any type that satisfies the trait 349 @is_termination_exception@ at the call site. 350 The assertions for this trait are available to 359 The semantics of the @throwResume@ statement are like the @throw@, but the 360 expression has return a reference a type that satisfies the trait 361 @is_resumption_exception@. The assertions from this trait are available to 351 362 the exception system while handling the exception. 352 363 353 At run time, no exception copy is made, as the stack is not unwound. Hence,the exception and354 any values on the stack remain in scope while the resumption is handled.355 356 The exception searches walks the stack matching withthe provided exception.357 It starts from the resuming functionand proceeds to the base of the stack,364 At run-time, no copies are made. As the stack is not unwound the exception and 365 any values on the stack will remain in scope while the resumption is handled. 366 367 Then the exception system searches the stack using the provided exception. 368 It starts starts from the throw and proceeds to the base of the stack, 358 369 from callee to caller. 359 370 At each stack frame, a check is made for resumption handlers defined by the … … 362 373 try { 363 374 GUARDED_BLOCK 364 } catchResume (EXCEPTION_TYPE$\(_1\)$ [* NAME$\(_1\)$]) {375 } catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) { 365 376 HANDLER_BLOCK$\(_1\)$ 366 } catchResume (EXCEPTION_TYPE$\(_2\)$ [* NAME$\(_2\)$]) {377 } catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) { 367 378 HANDLER_BLOCK$\(_2\)$ 368 379 } 369 380 \end{cfa} 370 Termination and resumption handlers may be intermixed in a @try@ 371 statement but the kind of throw must match with kind of handler for it to be 372 considered as a possible match. 373 Like termination, when viewed on its own, a @try@ statement with 374 @catchResume@ clauses simply executes the statements in the @GUARDED_BLOCK@, 375 and when those are finished, the try statement finishes. 376 377 However, while the guarded statements are being executed, including any invoked 378 functions, a resumption exception may be thrown. If that exception is not handled by a try 379 statement further up the stack, the handlers following the try block are now 380 searched for a matching resumption exception-type from top to bottom. 381 382 Like termination, exception matching checks each @catch@ clasue from top to bottom, if the representation of the thrown exception-type is 383 the same or a descendant type of the exception types in the @catchResume@ clauses. If 384 it is the same or a descendant of @EXCEPTION_TYPE@$_i$, then the optional @NAME@$_i$ is 385 bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$ 386 are executed. If control reaches the end of the handler, the exception is 387 freed and control continues after the @throwResume@ statement. 388 389 Like termination, if no resumption handler is found during the search, the 390 default resumption handler visible at the raise is called, which is the best 391 match at the according to \CFA's overloading rules. This function is passed the 392 exception given to the raise. After the default handler is run, execution 393 continues after the @throwResume@ statement. 394 395 There is a global @defaultResumptionHandler@ that is polymorphic over all 396 resumption and preforms a termination throw on the exception. 381 If the handlers are not involved in a search this will simply execute the 382 @GUARDED_BLOCK@ and then continue to the next statement. 383 Its purpose is to add handlers onto the stack. 384 (Note, termination and resumption handlers may be intermixed in a @try@ 385 statement but the kind of throw must be the same as the handler for it to be 386 considered as a possible match.) 387 388 If a search for a resumption handler reaches a try block it will check each 389 @catchResume@ clause, top-to-bottom. 390 At each handler if the thrown exception is or is a child type of 391 @EXCEPTION_TYPE@$_i$ then the a pointer to the exception is bound to 392 @NAME@$_i$ and then @HANDLER_BLOCK@$_i$ is executed. After the block is 393 finished control will return to the @throwResume@ statement. 394 395 Like termination, if no resumption handler is found, the default handler 396 visible at the throw statement is called. It will use the best match at the 397 call sight according to \CFA's overloading rules. The default handler is 398 passed the exception given to the throw. When the default handler finishes 399 execution continues after the throw statement. 400 401 There is a global @defaultResumptionHandler@ is polymorphic over all 402 termination exceptions and preforms a termination throw on the exception. 397 403 The @defaultTerminationHandler@ for that throw is matched at the original 398 404 throw statement (the resumption @throwResume@) and it can be customized by 399 405 introducing a new or better match as well. 400 406 401 \subsection{Resumption Marking} 407 % \subsubsection? 408 402 409 A key difference between resumption and termination is that resumption does 403 not unwind the stack. A side effect is that when a handler is matched404 and run it s try block (the guarded statements) and every try statement410 not unwind the stack. A side effect that is that when a handler is matched 411 and run it's try block (the guarded statements) and every try statement 405 412 searched before it are still on the stack. This can lead to the recursive 406 413 resumption problem. … … 416 423 } 417 424 \end{cfa} 418 When this code is executed the guarded @throwResume@ startsa419 search and match es the handler in the @catchResume@ clause. The handler is420 call ed and placed on the stack on top of the try-block. The second throw in the handler421 searches the same try block and callsanother instance of the425 When this code is executed the guarded @throwResume@ will throw, start a 426 search and match the handler in the @catchResume@ clause. This will be 427 call and placed on the stack on top of the try-block. The second throw then 428 throws and will search the same try block and put call another instance of the 422 429 same handler leading to an infinite loop. 423 430 424 While this situation is trivial and easy to avoid,much more complex cycles431 This situation is trivial and easy to avoid, but much more complex cycles 425 432 can form with multiple handlers and different exception types. 426 433 427 To prevent this case, examined try statements on the stack are marked, so that 428 subsequent resumption searches skip over them and continue with the next unmarked section 429 of the stack. 430 Unmarking occurs when that exception is handled 431 or the search completes without finding a handler. 434 To prevent all of these cases we mask sections of the stack, or equivalently 435 the try statements on the stack, so that the resumption search skips over 436 them and continues with the next unmasked section of the stack. 437 438 A section of the stack is marked when it is searched to see if it contains 439 a handler for an exception and unmarked when that exception has been handled 440 or the search was completed without finding a handler. 432 441 433 442 % This might need a diagram. But it is an important part of the justification 434 443 % of the design of the traversal order. 435 436 \begin{center} 437 %\begin{verbatim} 438 % throwResume2 ----------. 439 % | | 440 % generated from handler | 441 % | | 442 % handler | 443 % | | 444 % throwResume1 -----. : 445 % | | : 446 % try | : search skip 447 % | | : 448 % catchResume <----' : 449 % | | 450 %\end{verbatim} 451 \input{stackMarking} 452 \end{center} 453 454 The resulting search can be understood by thinking about what is searched for 455 termination. When a throw happens in a handler, a termination handler 444 \begin{verbatim} 445 throwResume2 ----------. 446 | | 447 generated from handler | 448 | | 449 handler | 450 | | 451 throwResume1 -----. : 452 | | : 453 try | : search skip 454 | | : 455 catchResume <----' : 456 | | 457 \end{verbatim} 458 459 The rules can be remembered as thinking about what would be searched in 460 termination. So when a throw happens in a handler; a termination handler 456 461 skips everything from the original throw to the original catch because that 457 part of the stack is unwound. A resumption handler skips the same 458 section of stack because it is marked. 459 A throw in a resumption default-handler performs the same search as the original 460 @throwResume@ because for resumption nothing has been unwound. 461 462 The symmetry between resumption masking and termination searching is why this pattern was picked. Other patterns, 463 such as marking just the handlers that caught, also work but the 464 symmetry seems to match programmer intuition. 462 part of the stack has been unwound, a resumption handler skips the same 463 section of stack because it has been masked. 464 A throw in a default handler will preform the same search as the original 465 throw because; for termination nothing has been unwound, for resumption 466 the mask will be the same. 467 468 The symmetry with termination is why this pattern was picked. Other patterns, 469 such as marking just the handlers that caught, also work but lack the 470 symmetry which means there is more to remember. 465 471 466 472 \section{Conditional Catch} 467 Both termination and resumption handler -clauses can be given an additional468 condition to further control which exceptions is handled:469 \begin{cfa} 470 catch (EXCEPTION_TYPE [* NAME] @; CONDITION@)473 Both termination and resumption handler clauses can be given an additional 474 condition to further control which exceptions they handle: 475 \begin{cfa} 476 catch (EXCEPTION_TYPE * NAME ; CONDITION) 471 477 \end{cfa} 472 478 First, the same semantics is used to match the exception type. Second, if the 473 479 exception matches, @CONDITION@ is executed. The condition expression may 474 reference all names in the scopeof the try block and @NAME@480 reference all names in scope at the beginning of the try block and @NAME@ 475 481 introduced in the handler clause. If the condition is true, then the handler 476 482 matches. Otherwise, the exception search continues as if the exception type 477 483 did not match. 478 479 Conditional catch allows fine-gain matching based on object values as well as exception types.480 For example, assume the exception hierarchy @OpenFailure@ $\rightarrow$ @CreateFailure@ and these exceptions are raised by function @open@.481 \begin{cfa}482 try {483 f1 = open( ... ); // open raises CreateFailure/OpenFailure484 f2 = open( ... ); // with the associate file485 ...486 } catch( CreateFailure * f ; @fd( f ) == f1@ ) {487 // only handle IO failure for f1488 } catch( OpenFailure * f ; @fd( f ) == f2@ ) {489 // only handle IO failure for f2490 }491 \end{cfa}492 Here, matching is very precise on the I/O exception and particular file with an open problem.493 This capability cannot be easily mimiced within the handler.494 484 \begin{cfa} 495 485 try { … … 497 487 f2 = open( ... ); 498 488 ... 499 } catch( CreateFailure * f ) { 500 if ( @fd( f ) == f1@ ) ... else // reraise 501 } catch( OpenFailure * f ) { 502 if ( @fd( f ) == f2@ ) ... else // reraise 489 } catch( IOFailure * f ; fd( f ) == f1 ) { 490 // only handle IO failure for f1 503 491 } 504 492 \end{cfa} 505 When an exception @CreateFailure@ is raised, the first handler catchesthe506 derived exception and reraises it if the object is inappropriate. The reraise 507 immediately terminates the current guarded block, which precludes the handler 508 for the base exception @OpenFailure@ from consideration for object 509 @f2@. Therefore, the ``catch first, then reraise'' approach is an incomplete 510 substitute for conditional catch. 511 512 \section{Reraise} 493 Note, catching @IOFailure@, checking for @f1@ in the handler, and re-raising the 494 exception if not @f1@ is different because the re-raise does not examine any of 495 remaining handlers in the current try statement. 496 497 \section{Rethrowing} 498 \colour{red}{From Andrew: I recomend we talk about why the language doesn't 499 have rethrows/reraises instead.} 500 513 501 \label{s:Rethrowing} 514 \colour{red}{From Andrew: I recommend we talk about why the language doesn't515 have rethrows/reraises instead.}516 517 502 Within the handler block or functions called from the handler block, it is 518 503 possible to reraise the most recently caught exception with @throw@ or … … 533 518 is part of an unwound stack frame. To prevent this problem, a new default 534 519 handler is generated that does a program-level abort. 535 \PAB{I don't see how this is different from the normal throw/throwResume.}536 520 537 521 \section{Finally Clauses} 538 Finally clauses are used to p erform unconditional clean-up when leaving a539 scope and appear at the end of a try statement after any catch clauses:522 Finally clauses are used to preform unconditional clean-up when leaving a 523 scope. They are placed at the end of a try statement: 540 524 \begin{cfa} 541 525 try { … … 548 532 The @FINALLY_BLOCK@ is executed when the try statement is removed from the 549 533 stack, including when the @GUARDED_BLOCK@ finishes, any termination handler 550 finishes ,or during an unwind.534 finishes or during an unwind. 551 535 The only time the block is not executed is if the program is exited before 552 536 the stack is unwound. 553 537 554 538 Execution of the finally block should always finish, meaning control runs off 555 the end of the block. This requirement ensures executionalways continues as if the556 finally clause is not present, \ie @finally@is for cleanup not changing control539 the end of the block. This requirement ensures always continues as if the 540 finally clause is not present, \ie finally is for cleanup not changing control 557 541 flow. Because of this requirement, local control flow out of the finally block 558 542 is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or 559 543 @return@ that causes control to leave the finally block. Other ways to leave 560 544 the finally block, such as a long jump or termination are much harder to check, 561 and at best requir e additional run-time overhead, and so are545 and at best requiring additional run-time overhead, and so are mealy 562 546 discouraged. 563 547 564 548 Not all languages with exceptions have finally clauses. Notably \Cpp does 565 without it as des tructors serve a similar role. Although destructors and566 finally clauses can be used in many of the same areas ,they have their own549 without it as descructors serve a similar role. Although destructors and 550 finally clauses can be used in many of the same areas they have their own 567 551 use cases like top-level functions and lambda functions with closures. 568 552 Destructors take a bit more work to set up but are much easier to reuse while 569 finally clauses are good for on e-off situations and can easilyinclude local information.553 finally clauses are good for once offs and can include local information. 570 554 571 555 \section{Cancellation} 572 \label{s:Cancellation} 573 Cancellation is a stack-level abort, which can be thought of as an 574 uncatchable termination. It unwinds the entire stack, and when 575 possible, forwards the cancellation exception to a different stack. 556 Cancellation is a stack-level abort, which can be thought of as as an 557 uncatchable termination. It unwinds the entirety of the current stack, and if 558 possible forwards the cancellation exception to a different stack. 576 559 577 560 Cancellation is not an exception operation like termination or resumption. … … 580 563 throw, this exception is not used in matching only to pass information about 581 564 the cause of the cancellation. 582 (This semantics also means matching cannot fail so there is no default handler.)583 584 After @cancel_stack@ is called , the exception is copied into the EHM's585 memory andthe current stack is565 (This also means matching cannot fail so there is no default handler either.) 566 567 After @cancel_stack@ is called the exception is copied into the exception 568 handling mechanism's memory. Then the entirety of the current stack is 586 569 unwound. After that it depends one which stack is being cancelled. 587 570 \begin{description} 588 571 \item[Main Stack:] 589 572 The main stack is the one used by the program main at the start of execution, 590 and is the only stack in a sequential program. Even in a concurrent program ,591 the main stack is o ften used as the environment to start the concurrent threads.573 and is the only stack in a sequential program. Even in a concurrent program 574 the main stack is only dependent on the environment that started the program. 592 575 Hence, when the main stack is cancelled there is nowhere else in the program 593 to go. Hence, after the mainstack is unwound, there is a program-level abort.576 to notify. After the stack is unwound, there is a program-level abort. 594 577 595 578 \item[Thread Stack:] 596 A thread stack is created for a \CFA@thread@ object or object that satisfies the579 A thread stack is created for a @thread@ object or object that satisfies the 597 580 @is_thread@ trait. A thread only has two points of communication that must 598 happen: start and join. A thread must be running to perform a 599 cancellation (a thread cannot cancel another thread). Therefore, a cancellation must 600 occur after start and before join, so join is used 601 for cancellation communication. 581 happen: start and join. As the thread must be running to perform a 582 cancellation, it must occur after start and before join, so join is used 583 for communication here. 602 584 After the stack is unwound, the thread halts and waits for 603 585 another thread to join with it. The joining thread checks for a cancellation, 604 586 and if present, resumes exception @ThreadCancelled@. 605 587 606 \begin{sloppypar}607 588 There is a subtle difference between the explicit join (@join@ function) and 608 implicit join (from a @thread@'sdestructor call). The explicit join takes the default589 implicit join (from a destructor call). The explicit join takes the default 609 590 handler (@defaultResumptionHandler@) from its calling context, which is used if 610 591 the exception is not caught. The implicit join does a program abort instead. 611 \end{sloppypar} 612 613 \PAB{uC++ does not have these issues, but catch(...) is not working.} 614 \begin{lstlisting}[language=uC++] 615 #include <iostream> 616 using namespace std; 617 618 struct Cl { 619 ~Cl() { cout << "C" << endl; } 620 }; 621 _Coroutine C { 622 void main() { 623 Cl c; 624 try { 625 cancel(); 626 } catch( ... ) { 627 cout << "..." << endl; 628 } _Finally { 629 cout << "F" << endl; 630 } 631 } 632 public: 633 void mem() { resume(); } 634 }; 635 _Task T { 636 void main() { 637 Cl c; 638 try { 639 cancel(); 640 } catch( ... ) { 641 cout << "..." << endl; 642 } _Finally { 643 cout << "F" << endl; 644 } 645 } 646 }; 647 int main() { 648 C c; 649 cout << "here1" << endl; 650 c.mem(); 651 cout << "here2" << endl; 652 { 653 T t; 654 } 655 cout << "here3" << endl; 656 } 657 \end{lstlisting} 658 659 \PAB{This discussion should be its own section.} 592 660 593 This semantics is for safety. If an unwind is triggered while another unwind 661 is underway only one of them can proceed as they both want to ``consume "the594 is underway only one of them can proceed as they both want to ``consume'' the 662 595 stack. Letting both try to proceed leads to very undefined behaviour. 663 596 Both termination and cancellation involve unwinding and, since the default … … 665 598 happen in an implicate join inside a destructor. So there is an error message 666 599 and an abort instead. 667 668 600 \todo{Perhaps have a more general disucssion of unwind collisions before 669 601 this point.} … … 688 620 for the exception. So it will use the default handler like a regular throw. 689 621 \end{description} 690 691 \PAB{You should have more test programs that compare \CFA EHM to uC++ EHM.} -
doc/theses/andrew_beach_MMath/uw-ethesis.tex
rea1c97b rde47a9d 105 105 \usepackage{amsmath,amssymb,amstext} 106 106 % For including graphics N.B. pdftex graphics driver 107 %\usepackage[pdftex]{graphicx} 108 \usepackage{epic,eepic} 109 \usepackage{graphicx} 107 \usepackage[pdftex]{graphicx} 110 108 % Removes large sections of the document. 111 109 \usepackage{comment} … … 119 117 % Use the "hyperref" package 120 118 % N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE 121 %\usepackage[pdftex,pagebackref=true]{hyperref} % with basic options 122 \usepackage[pagebackref=true]{hyperref} % with basic options 119 \usepackage[pdftex,pagebackref=true]{hyperref} % with basic options 123 120 %\usepackage[pdftex,pagebackref=true]{hyperref} 124 121 % N.B. pagebackref=true provides links back from the References to the body
Note: See TracChangeset
for help on using the changeset viewer.