Ignore:
Timestamp:
Feb 12, 2021, 12:27:38 PM (8 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
eb24cec0
Parents:
da3963a (diff), 52f6250 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

File:
1 edited

Legend:

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

    rda3963a r565acf59  
    55
    66\section{Virtuals}
     7Virtual types and casts are not part of the exception system nor are they
     8required for an exception system. But an object-oriented style hierarchy is a
     9great way of organizing exceptions so a minimal virtual system has been added
     10to \CFA.
     11
     12The pattern of a simple hierarchy was borrowed from object-oriented
     13programming was chosen for several reasons.
     14The first is that it allows new exceptions to be added in user code
     15and in libraries independently of each other. Another is it allows for
     16different levels of exception grouping (all exceptions, all IO exceptions or
     17a particular IO exception). Also it also provides a simple way of passing
     18data back and forth across the throw.
     19
    720Virtual types and casts are not required for a basic exception-system but are
    821useful for advanced exception features. However, \CFA is not object-oriented so
    9 there is no obvious concept of virtuals.  Hence, to create advanced exception
    10 features for this work, I needed to designed and implemented a virtual-like
     22there is no obvious concept of virtuals. Hence, to create advanced exception
     23features for this work, I needed to design and implement a virtual-like
    1124system for \CFA.
    1225
     26% NOTE: Maybe we should but less of the rational here.
    1327Object-oriented languages often organized exceptions into a simple hierarchy,
    1428\eg Java.
     
    3044\end{center}
    3145The hierarchy provides the ability to handle an exception at different degrees
    32 of specificity (left to right).  Hence, it is possible to catch a more general
     46of specificity (left to right). Hence, it is possible to catch a more general
    3347exception-type in higher-level code where the implementation details are
    3448unknown, which reduces tight coupling to the lower-level implementation.
     
    6175While much of the virtual infrastructure is created, it is currently only used
    6276internally for exception handling. The only user-level feature is the virtual
    63 cast, which is the same as the \CC \lstinline[language=C++]|dynamic_cast|.
     77cast, which is the same as the \Cpp \lstinline[language=C++]|dynamic_cast|.
     78\label{p:VirtualCast}
    6479\begin{cfa}
    6580(virtual TYPE)EXPRESSION
    6681\end{cfa}
    67 Note, the syntax and semantics matches a C-cast, rather than the unusual \CC
    68 syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be a
    69 pointer to a virtual type. The cast dynamically checks if the @EXPRESSION@ type
    70 is the same or a subtype of @TYPE@, and if true, returns a pointer to the
     82Note, the syntax and semantics matches a C-cast, rather than the function-like
     83\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
     84a pointer to a virtual type.
     85The cast dynamically checks if the @EXPRESSION@ type is the same or a subtype
     86of @TYPE@, and if true, returns a pointer to the
    7187@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    7288
     
    7793
    7894Exceptions are defined by the trait system; there are a series of traits, and
    79 if a type satisfies them, then it can be used as an exception.  The following
     95if a type satisfies them, then it can be used as an exception. The following
    8096is the base trait all exceptions need to match.
    8197\begin{cfa}
    8298trait is_exception(exceptT &, virtualT &) {
    83         virtualT const & @get_exception_vtable@(exceptT *);
     99        virtualT const & get_exception_vtable(exceptT *);
    84100};
    85101\end{cfa}
    86 The function takes any pointer, including the null pointer, and returns a
    87 reference to the virtual-table object. Defining this function also establishes
    88 the virtual type and a virtual-table pair to the \CFA type-resolver and
    89 promises @exceptT@ is a virtual type and a child of the base exception-type.
    90 
    91 {\color{blue} PAB: I do not understand this paragraph.}
    92 One odd thing about @get_exception_vtable@ is that it should always be a
    93 constant function, returning the same value regardless of its argument.  A
    94 pointer or reference to the virtual table instance could be used instead,
    95 however using a function has some ease of implementation advantages and allows
    96 for easier disambiguation because the virtual type name (or the address of an
    97 instance that is in scope) can be used instead of the mangled virtual table
    98 name.  Also note the use of the word ``promise'' in the trait
    99 description. Currently, \CFA cannot check to see if either @exceptT@ or
    100 @virtualT@ match the layout requirements. This is considered part of
    101 @get_exception_vtable@'s correct implementation.
     102The trait is defined over two types, the exception type and the virtual table
     103type. This should be one-to-one, each exception type has only one virtual
     104table type and vice versa. The only assertion in the trait is
     105@get_exception_vtable@, which takes a pointer of the exception type and
     106returns a reference to the virtual table type instance.
     107
     108The function @get_exception_vtable@ is actually a constant function.
     109Recardless of the value passed in (including the null pointer) it should
     110return a reference to the virtual table instance for that type.
     111The reason it is a function instead of a constant is that it make type
     112annotations easier to write as you can use the exception type instead of the
     113virtual table type; which usually has a mangled name.
     114% Also \CFA's trait system handles functions better than constants and doing
     115% it this way
     116
     117% I did have a note about how it is the programmer's responsibility to make
     118% sure the function is implemented correctly. But this is true of every
     119% similar system I know of (except Agda's I guess) so I took it out.
    102120
    103121\section{Raise}
    104 \CFA provides two kinds of exception raise: termination (see
    105 \VRef{s:Termination}) and resumption (see \VRef{s:Resumption}), which are
     122\CFA provides two kinds of exception raise: termination
     123\see{\VRef{s:Termination}} and resumption \see{\VRef{s:Resumption}}, which are
    106124specified with the following traits.
    107125\begin{cfa}
    108126trait is_termination_exception(
    109127                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
    110         void @defaultTerminationHandler@(exceptT &);
     128        void defaultTerminationHandler(exceptT &);
    111129};
    112130\end{cfa}
     
    118136trait is_resumption_exception(
    119137                exceptT &, virtualT & | is_exception(exceptT, virtualT)) {
    120         void @defaultResumptionHandler@(exceptT &);
     138        void defaultResumptionHandler(exceptT &);
    121139};
    122140\end{cfa}
     
    125143
    126144Finally there are three convenience macros for referring to the these traits:
    127 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.  Each
    128 takes the virtual type's name, and for polymorphic types only, the
    129 parenthesized list of polymorphic arguments. These macros do the name mangling
    130 to get the virtual-table name and provide the arguments to both sides
    131 {\color{blue}(PAB: What's a ``side''?)}
     145@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
     146All three traits are hard to use while naming the virtual table as it has an
     147internal mangled name. These macros take the exception name as their first
     148argument and do the mangling. They all take a second argument for polymorphic
     149types which is the parenthesized list of polymorphic arguments. These
     150arguments are passed to both the exception type and the virtual table type as
     151the arguments do have to match.
     152
     153For example consider a function that is polymorphic over types that have a
     154defined arithmetic exception:
     155\begin{cfa}
     156forall(Num | IS_EXCEPTION(Arithmetic, (Num)))
     157void some_math_function(Num & left, Num & right);
     158\end{cfa}
    132159
    133160\subsection{Termination}
     
    146173throw EXPRESSION;
    147174\end{cfa}
    148 The expression must return a termination-exception reference, where the
    149 termination exception has a type with a @void defaultTerminationHandler(T &)@
    150 (default handler) defined. The handler is found at the call site using \CFA's
    151 trait system and passed into the exception system along with the exception
    152 itself.
    153 
    154 At runtime, a representation of the exception type and an instance of the
    155 exception type is copied into managed memory (heap) to ensure it remains in
     175The expression must return a reference to a termination exception, where the
     176termination exception is any type that satifies @is_termination_exception@
     177at the call site.
     178Through \CFA's trait system the functions in the traits are passed into the
     179throw code. A new @defaultTerminationHandler@ can be defined in any scope to
     180change the throw's behavior (see below).
     181
     182At runtime, the exception returned by the expression
     183is copied into managed memory (heap) to ensure it remains in
    156184scope during unwinding. It is the user's responsibility to ensure the original
    157185exception object at the throw is freed when it goes out of scope. Being
     
    165193try {
    166194        GUARDED_BLOCK
    167 } @catch (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // termination handler 1
     195} catch (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) { // termination handler 1
    168196        HANDLER_BLOCK$\(_1\)$
    169 } @catch (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // termination handler 2
     197} catch (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) { // termination handler 2
    170198        HANDLER_BLOCK$\(_2\)$
    171199}
     
    178206Exception matching checks the representation of the thrown exception-type is
    179207the same or a descendant type of the exception types in the handler clauses. If
    180 there is a match, a pointer to the exception object created at the throw is
    181 bound to @NAME@ and the statements in the associated @HANDLER_BLOCK@ are
    182 executed. If control reaches the end of the handler, the exception is freed,
    183 and control continues after the try statement.
     208it is the same of a descendent of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$ is
     209bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
     210are executed. If control reaches the end of the handler, the exception is
     211freed and control continues after the try statement.
    184212
    185213The default handler visible at the throw statement is used if no matching
    186214termination handler is found after the entire stack is searched. At that point,
    187215the default handler is called with a reference to the exception object
    188 generated at the throw. If the default handler returns, the system default
    189 action is executed, which often terminates the program. This feature allows
     216generated at the throw. If the default handler returns, control continues
     217from after the throw statement. This feature allows
    190218each exception type to define its own action, such as printing an informative
    191219error message, when an exception is not handled in the program.
     220However the default handler for all exception types triggers a cancellation
     221using the exception.
    192222
    193223\subsection{Resumption}
     
    196226Resumption raise, called ``resume'', is as old as termination
    197227raise~\cite{Goodenough75} but is less popular. In many ways, resumption is
    198 simpler and easier to understand, as it is simply a dynamic call (as in
    199 Lisp). The semantics of resumption is: search the stack for a matching handler,
     228simpler and easier to understand, as it is simply a dynamic call.
     229The semantics of resumption is: search the stack for a matching handler,
    200230execute the handler, and continue execution after the resume. Notice, the stack
    201231cannot be unwound because execution returns to the raise point. Resumption is
     
    209239\end{cfa}
    210240The semantics of the @throwResume@ statement are like the @throw@, but the
    211 expression has a type with a @void defaultResumptionHandler(T &)@ (default
    212 handler) defined, where the handler is found at the call site by the type
    213 system.  At runtime, a representation of the exception type and an instance of
    214 the exception type is \emph{not} copied because the stack is maintained during
    215 the handler search.
     241expression has return a reference a type that satifies the trait
     242@is_resumption_exception@. Like with termination the exception system can
     243use these assertions while (throwing/raising/handling) the exception.
     244
     245At runtime, no copies are made. As the stack is not unwound the exception and
     246any values on the stack will remain in scope while the resumption is handled.
    216247
    217248Then the exception system searches the stack starting from the resume and
    218 proceeding towards the base of the stack, from callee to caller. At each stack
     249proceeding to the base of the stack, from callee to caller. At each stack
    219250frame, a check is made for resumption handlers defined by the @catchResume@
    220251clauses of a @try@ statement.
     
    222253try {
    223254        GUARDED_BLOCK
    224 } @catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME)@ { // resumption handler 1
     255} catchResume (EXCEPTION_TYPE$\(_1\)$ * NAME$\(_1\)$) {
    225256        HANDLER_BLOCK$\(_1\)$
    226 } @catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME)@ { // resumption handler 2
     257} catchResume (EXCEPTION_TYPE$\(_2\)$ * NAME$\(_2\)$) {
    227258        HANDLER_BLOCK$\(_2\)$
    228259}
     
    253284current point on the stack because new try statements may have been pushed by
    254285the handler or functions called from the handler. If there is no match back to
    255 the point of the current handler, the search skips the stack frames already
    256 searched by the first resume and continues after the try statement. The default
    257 handler always continues from default handler associated with the point where
    258 the exception is created.
     286the point of the current handler, the search skips\label{p:searchskip} the
     287stack frames already searched by the first resume and continues after
     288the try statement. The default handler always continues from default
     289handler associated with the point where the exception is created.
    259290
    260291% This might need a diagram. But it is an important part of the justification
     
    275306\end{verbatim}
    276307
    277 This resumption search-pattern reflect the one for termination, which matches
    278 with programmer expectations. However, it avoids the \emph{recursive
    279 resumption} problem. If parts of the stack are searched multiple times, loops
     308This resumption search pattern reflects the one for termination, and so
     309should come naturally to most programmers.
     310However, it avoids the \emph{recursive resumption} problem.
     311If parts of the stack are searched multiple times, loops
    280312can easily form resulting in infinite recursion.
    281313
     
    283315\begin{cfa}
    284316try {
    285         throwResume$\(_1\)$ (E &){};
    286 } catch( E * ) {
    287         throwResume;
    288 }
    289 \end{cfa}
    290 Based on termination semantics, programmer expectation is for the re-resume to
    291 continue searching the stack frames after the try statement. However, the
    292 current try statement is still on the stack below the handler issuing the
    293 reresume (see \VRef{s:Reraise}). Hence, the try statement catches the re-raise
    294 again and does another re-raise \emph{ad infinitum}, which is confusing and
    295 difficult to debug. The \CFA resumption search-pattern skips the try statement
    296 so the reresume search continues after the try, mathcing programmer
    297 expectation.
     317        throwResume (E &){}; // first
     318} catchResume(E *) {
     319        throwResume (E &){}; // second
     320}
     321\end{cfa}
     322If this handler is ever used it will be placed on top of the stack above the
     323try statement. If the stack was not masked than the @throwResume@ in the
     324handler would always be caught by the handler, leading to an infinite loop.
     325Masking avoids this problem and other more complex versions of it involving
     326multiple handlers and exception types.
     327
     328Other masking stratagies could be used; such as masking the handlers that
     329have caught an exception. This one was choosen because it creates a symmetry
     330with termination (masked sections of the stack would be unwound with
     331termination) and having only one pattern to learn is easier.
    298332
    299333\section{Conditional Catch}
    300 Both termination and resumption handler-clauses may perform conditional matching:
     334Both termination and resumption handler clauses can be given an additional
     335condition to further control which exceptions they handle:
    301336\begin{cfa}
    302337catch (EXCEPTION_TYPE * NAME ; @CONDITION@)
     
    305340exception matches, @CONDITION@ is executed. The condition expression may
    306341reference all names in scope at the beginning of the try block and @NAME@
    307 introduced in the handler clause.  If the condition is true, then the handler
     342introduced in the handler clause. If the condition is true, then the handler
    308343matches. Otherwise, the exception search continues at the next appropriate kind
    309344of handler clause in the try block.
     
    322357
    323358\section{Reraise}
     359\color{red}{From Andrew: I recomend we talk about why the language doesn't
     360have rethrows/reraises instead.}
     361
    324362\label{s:Reraise}
    325363Within the handler block or functions called from the handler block, it is
     
    327365@throwResume@, respective.
    328366\begin{cfa}
    329 catch( ... ) {
     367try {
     368        ...
     369} catch( ... ) {
    330370        ... throw; // rethrow
    331371} catchResume( ... ) {
     
    340380handler is generated that does a program-level abort.
    341381
    342 
    343382\section{Finally Clauses}
    344383A @finally@ clause may be placed at the end of a @try@ statement.
     
    346385try {
    347386        GUARDED_BLOCK
    348 } ...   // any number or kind of handler clauses
    349 } finally {
     387} ... // any number or kind of handler clauses
     388... finally {
    350389        FINALLY_BLOCK
    351390}
    352391\end{cfa}
    353 The @FINALLY_BLOCK@ is executed when the try statement is unwound from the
    354 stack, \ie when the @GUARDED_BLOCK@ or any handler clause finishes. Hence, the
    355 finally block is always executed.
     392The @FINALLY_BLOCK@ is executed when the try statement is removed from the
     393stack, including when the @GUARDED_BLOCK@ or any handler clause finishes or
     394during an unwind.
     395The only time the block is not executed is if the program is exited before
     396that happens.
    356397
    357398Execution of the finally block should always finish, meaning control runs off
    358399the end of the block. This requirement ensures always continues as if the
    359400finally clause is not present, \ie finally is for cleanup not changing control
    360 flow.  Because of this requirement, local control flow out of the finally block
    361 is forbidden.  The compiler precludes any @break@, @continue@, @fallthru@ or
     401flow. Because of this requirement, local control flow out of the finally block
     402is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
    362403@return@ that causes control to leave the finally block. Other ways to leave
    363404the finally block, such as a long jump or termination are much harder to check,
     
    369410possible forwards the cancellation exception to a different stack.
    370411
     412Cancellation is not an exception operation like termination or resumption.
    371413There is no special statement for starting a cancellation; instead the standard
    372 library function @cancel_stack@ is called passing an exception.  Unlike a
     414library function @cancel_stack@ is called passing an exception. Unlike a
    373415raise, this exception is not used in matching only to pass information about
    374416the cause of the cancellation.
     
    377419\begin{description}
    378420\item[Main Stack:]
    379 
    380421The main stack is the one used by the program main at the start of execution,
    381 and is the only stack in a sequential program.  Hence, when cancellation is
    382 forwarded to the main stack, there is no other forwarding stack, so after the
    383 stack is unwound, there is a program-level abort.
     422and is the only stack in a sequential program. Even in a concurrent program
     423the main stack is only dependent on the environment that started the program.
     424Hence, when the main stack is cancelled there is nowhere else in the program
     425to notify. After the stack is unwound, there is a program-level abort.
    384426
    385427\item[Thread Stack:]
    386428A thread stack is created for a @thread@ object or object that satisfies the
    387 @is_thread@ trait.  A thread only has two points of communication that must
     429@is_thread@ trait. A thread only has two points of communication that must
    388430happen: start and join. As the thread must be running to perform a
    389 cancellation, it must occur after start and before join, so join is a
    390 cancellation point.  After the stack is unwound, the thread halts and waits for
    391 another thread to join with it. The joining thread, checks for a cancellation,
     431cancellation, it must occur after start and before join, so join is used
     432for communication here.
     433After the stack is unwound, the thread halts and waits for
     434another thread to join with it. The joining thread checks for a cancellation,
    392435and if present, resumes exception @ThreadCancelled@.
    393436
     
    397440the exception is not caught. The implicit join does a program abort instead.
    398441
    399 This semantics is for safety. One difficult problem for any exception system is
    400 defining semantics when an exception is raised during an exception search:
    401 which exception has priority, the original or new exception? No matter which
    402 exception is selected, it is possible for the selected one to disrupt or
    403 destroy the context required for the other. {\color{blue} PAB: I do not
    404 understand the following sentences.} This loss of information can happen with
    405 join but as the thread destructor is always run when the stack is being unwound
    406 and one termination/cancellation is already active. Also since they are
    407 implicit they are easier to forget about.
     442This semantics is for safety. If an unwind is triggered while another unwind
     443is underway only one of them can proceed as they both want to ``consume'' the
     444stack. Letting both try to proceed leads to very undefined behaviour.
     445Both termination and cancellation involve unwinding and, since the default
     446@defaultResumptionHandler@ preforms a termination that could more easily
     447happen in an implicate join inside a destructor. So there is an error message
     448and an abort instead.
     449
     450The recommended way to avoid the abort is to handle the intial resumption
     451from the implicate join. If required you may put an explicate join inside a
     452finally clause to disable the check and use the local
     453@defaultResumptionHandler@ instead.
    408454
    409455\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object
    410 or object that satisfies the @is_coroutine@ trait.  A coroutine only knows of
    411 two other coroutines, its starter and its last resumer.  The last resumer has
    412 the tightest coupling to the coroutine it activated.  Hence, cancellation of
     456or object that satisfies the @is_coroutine@ trait. A coroutine only knows of
     457two other coroutines, its starter and its last resumer. The last resumer has
     458the tightest coupling to the coroutine it activated. Hence, cancellation of
    413459the active coroutine is forwarded to the last resumer after the stack is
    414460unwound, as the last resumer has the most precise knowledge about the current
Note: See TracChangeset for help on using the changeset viewer.