Ignore:
Timestamp:
Aug 2, 2021, 9:43:04 AM (3 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
jacob/cs343-translation, master, new-ast-unique-expr
Children:
fa7dbf1
Parents:
06c61e2
Message:

proofread intro chapter of Andrew's thesis

File:
1 edited

Legend:

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

    r06c61e2 r417e8ea  
    22
    33% The highest level overview of Cforall and EHMs. Get this done right away.
    4 This thesis goes over the design and implementation of the exception handling
     4This thesis covers the design and implementation of the exception handling
    55mechanism (EHM) of
    66\CFA (pronounced sea-for-all and may be written Cforall or CFA).
    7 \CFA is a new programming language that extends C, that maintains
     7\CFA is a new programming language that extends C, which maintains
    88backwards-compatibility while introducing modern programming features.
    99Adding exception handling to \CFA gives it new ways to handle errors and
    10 make other large control-flow jumps.
     10make large control-flow jumps.
    1111
    1212% Now take a step back and explain what exceptions are generally.
     13A language's EHM is a combination of language syntax and run-time
     14components that are used to construct, raise, and handle exceptions,
     15including all control flow.
     16Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
    1317Exception handling provides dynamic inter-function control flow.
    1418There are two forms of exception handling covered in this thesis:
    1519termination, which acts as a multi-level return,
    1620and resumption, which is a dynamic function call.
     21% PAB: Maybe this sentence was suppose to be deleted?
    1722Termination handling is much more common,
    18 to the extent that it is often seen
    19 This seperation is uncommon because termination exception handling is so
    20 much more common that it is often assumed.
     23to 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.
    2127% WHY: Mention other forms of continuation and \cite{CommonLisp} here?
    22 A language's EHM is the combination of language syntax and run-time
    23 components that are used to construct, raise and handle exceptions,
    24 including all control flow.
    25 
    26 Termination exception handling allows control to return to any previous
    27 function on the stack directly, skipping any functions between it and the
    28 current function.
     28
     29Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
    2930\begin{center}
    30 \input{callreturn}
     31\begin{tabular}[t]{ll}
     32\begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     33void f( void (*hp)() ) {
     34        hp();
     35}
     36void g( void (*hp)() ) {
     37        f( hp );
     38}
     39void 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}
     47h( 2, 0 );
     48\end{lstlisting}
     49&
     50\raisebox{-0.5\totalheight}{\input{handler}}
     51\end{tabular}
    3152\end{center}
    32 
    33 Resumption exception handling seaches the stack for a handler and then calls
    34 it without adding or removing any other stack frames.
    35 \todo{Add a diagram showing control flow for resumption.}
     53The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
     54When 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.
     55Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
     56Exception 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.
     57It 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
     59Termination 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}
     63Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
     64After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
     65Unwinding allows recover to any previous
     66function on the stack, skipping any functions between it and the
     67function containing the matching handler.
     68
     69Resumption 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.
     70\begin{center}
     71\input{resumption}
     72\end{center}
     73After the handler returns, control continues after the resume in @f@ (dynamic return).
     74Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.
    3675
    3776Although a powerful feature, exception handling tends to be complex to set up
    3877and expensive to use
    39 so they are often limited to unusual or ``exceptional" cases.
    40 The classic example of this is error handling, exceptions can be used to
    41 remove error handling logic from the main execution path and while paying
     78so it is often limited to unusual or ``exceptional" cases.
     79The classic example is error handling, where exceptions are used to
     80remove error handling logic from the main execution path, while paying
    4281most of the cost only when the error actually occurs.
    4382
     
    4988some of the underlying tools used to implement and express exception handling
    5089in other languages are absent in \CFA.
    51 Still the resulting syntax resembles that of other languages:
    52 \begin{cfa}
    53 try {
     90Still the resulting basic syntax resembles that of other languages:
     91\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     92@try@ {
    5493        ...
    5594        T * object = malloc(request_size);
    5695        if (!object) {
    57                 throw OutOfMemory{fixed_allocation, request_size};
     96                @throw@ OutOfMemory{fixed_allocation, request_size};
    5897        }
    5998        ...
    60 } catch (OutOfMemory * error) {
     99} @catch@ (OutOfMemory * error) {
    61100        ...
    62101}
    63 \end{cfa}
    64 
     102\end{lstlisting}
    65103% A note that yes, that was a very fast overview.
    66104The design and implementation of all of \CFA's EHM's features are
     
    69107
    70108% The current state of the project and what it contributes.
    71 All of these features have been implemented in \CFA, along with
    72 a suite of test cases as part of this project.
    73 The implementation techniques are generally applicable in other programming
     109The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code.
     110In addition,
     111a suite of tests and performance benchmarks were created as part of this project.
     112The \CFA implementation techniques are generally applicable in other programming
    74113languages and much of the design is as well.
    75 Some parts of the EHM use other features unique to \CFA and these would be
    76 harder to replicate in other programming languages.
    77 
     114Some parts of the EHM use features unique to \CFA, and hence,
     115are harder to replicate in other programming languages.
    78116% Talk about other programming languages.
    79 Some existing programming languages that include EHMs/exception handling
    80 include C++, Java and Python. All three examples focus on termination
    81 exceptions which unwind the stack as part of the
    82 Exceptions also can replace return codes and return unions.
     117Three well known programming languages with EHMs, %/exception handling
     118C++, Java and Python are examined in the performance work. However, these languages focus on termination
     119exceptions, so there is no comparison with resumption.
    83120
    84121The contributions of this work are:
    85122\begin{enumerate}
    86123\item Designing \CFA's exception handling mechanism, adapting designs from
    87 other programming languages and the creation of new features.
    88 \item Implementing stack unwinding and the EHM in \CFA, including updating
    89 the compiler and the run-time environment.
    90 \item Designed and implemented a prototype virtual system.
     124other programming languages, and creating new features.
     125\item Implementing stack unwinding for the \CFA EHM, including updating
     126the \CFA compiler and run-time environment to generate and execute the EHM code.
     127\item Designing and implementing a prototype virtual system.
    91128% I think the virtual system and per-call site default handlers are the only
    92129% "new" features, everything else is a matter of implementation.
     130\item Creating tests and performance benchmarks to compare with EHM's in other languages.
    93131\end{enumerate}
    94132
    95 \todo{I can't figure out a good lead-in to the roadmap.}
    96 The next section covers the existing state of exceptions.
    97 The existing state of \CFA is also covered in \autoref{c:existing}.
    98 The new features are introduced in \autoref{c:features},
    99 which explains their usage and design.
    100 That is followed by the implementation of those features in
     133%\todo{I can't figure out a good lead-in to the roadmap.}
     134The thesis is organization as follows.
     135The next section and parts of \autoref{c:existing} cover existing EHMs.
     136New \CFA EHM features are introduced in \autoref{c:features},
     137covering their usage and design.
     138That is followed by the implementation of these features in
    101139\autoref{c:implement}.
    102 The performance results are examined in \autoref{c:performance}.
    103 Possibilities to extend this project are discussed in \autoref{c:future}.
     140Performance results are presented in \autoref{c:performance}.
     141Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
    104142
    105143\section{Background}
    106144\label{s:background}
    107145
    108 Exception handling is not a new concept,
    109 with papers on the subject dating back 70s.\cite{Goodenough}
    110 
    111 Early exceptions were often treated as signals. They carried no information
    112 except their identity. Ada still uses this system.
     146Exception handling is a well examined area in programming languages,
     147with papers on the subject dating back the 70s~\cite{Goodenough75}.
     148Early exceptions were often treated as signals, which carried no information
     149except their identity. Ada~\cite{Ada} still uses this system.
    113150
    114151The modern flag-ship for termination exceptions is \Cpp,
     
    116153in 1990.
    117154% https://en.cppreference.com/w/cpp/language/history
    118 \Cpp has the ability to use any value of any type as an exception.
    119 However that seems to immediately pushed aside for classes inherited from
     155While many EHMs have special exception types,
     156\Cpp has the ability to use any type as an exception.
     157However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from
    120158\code{C++}{std::exception}.
    121 Although there is a special catch-all syntax it does not allow anything to
    122 be done with the caught value becuase nothing is known about it.
    123 So instead a base type is defined with some common functionality (such as
    124 the ability to describe the reason the exception was raised) and all
    125 exceptions have that functionality.
    126 This seems to be the standard now, as the garentied functionality is worth
    127 any lost flexibility from limiting it to a single type.
    128 
    129 Java was the next popular language to use exceptions.
    130 Its exception system largely reflects that of \Cpp, except that requires
    131 you throw a child type of \code{Java}{java.lang.Throwable}
     159While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can
     160be done with the caught value because nothing is known about it.
     161Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as
     162the ability to print a message when the exception is raised but not caught) and all
     163exceptions have this functionality.
     164Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth
     165any lost in flexibility from limiting exceptions types to classes.
     166
     167Java~\cite{Java} was the next popular language to use exceptions.
     168Its exception system largely reflects that of \Cpp, except it requires
     169exceptions to be a subtype of \code{Java}{java.lang.Throwable}
    132170and it uses checked exceptions.
    133 Checked exceptions are part of the function interface they are raised from.
    134 This includes functions they propogate through, until a handler for that
    135 type of exception is found.
    136 This makes exception information explicit, which can improve clarity and
     171Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise.
     172Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions.
     173Making exception information explicit, improves clarity and
    137174safety, but can slow down programming.
    138 Some of these, such as dealing with high-order methods or an overly specified
    139 throws clause, are technical. However some of the issues are much more
    140 human, in that writing/updating all the exception signatures can be enough
    141 of a burden people will hack the system to avoid them.
    142 Including the ``catch-and-ignore" pattern where a catch block is used without
    143 anything to repair or recover from the exception.
    144 
    145 %\subsection
    146 Resumption exceptions have been much less popular.
    147 Although resumption has a history as old as termination's, very few
     175For example, programming complexity increases when dealing with high-order methods or an overly specified
     176throws clause. However some of the issues are more
     177programming annoyances, such as writing/updating many exception signatures after adding or remove calls.
     178Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide.
     179For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus
     180repairing or recovering from the exception.
     181
     182%\subsection
     183Resumption exceptions are less popular,
     184although resumption is as old as termination;
     185hence, few
    148186programming languages have implemented them.
    149187% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    150188%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
    151 Mesa is one programming languages that did. Experiance with Mesa
    152 is quoted as being one of the reasons resumptions were not
     189Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
     190is quoted as being one of the reasons resumptions are not
    153191included in the \Cpp standard.
    154192% https://en.wikipedia.org/wiki/Exception_handling
    155 Since then resumptions have been ignored in the main-stream.
    156 
    157 All of this does call into question the use of resumptions, is
    158 something largely rejected decades ago worth revisiting now?
    159 Yes, even if it was the right call at the time there have been decades
    160 of other developments in computer science that have changed the situation
    161 since then.
    162 Some of these developments, such as in functional programming's resumption
    163 equivalent: algebraic effects\cite{Zhang19}, are directly related to
    164 resumptions as well.
    165 A complete rexamination of resumptions is beyond a single paper, but it is
    166 enough to try them again in \CFA.
     193As a result, resumption has ignored in main-stream programming languages.
     194However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading).
     195While rejecting resumption might have been the right decision in the past, there are decades
     196of developments in computer science that have changed the situation.
     197Some of these developments, such as functional programming's resumption
     198equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success.
     199A complete reexamination of resumptions is beyond this thesis, but their re-emergence is
     200enough to try them in \CFA.
    167201% Especially considering how much easier they are to implement than
    168202% termination exceptions.
    169203
    170204%\subsection
    171 Functional languages tend to use other solutions for their primary error
    172 handling mechanism, exception-like constructs still appear.
     205Functional languages tend to use other solutions for their primary EHM,
     206but exception-like constructs still appear.
    173207Termination appears in error construct, which marks the result of an
    174 expression as an error, the result of any expression that tries to use it as
    175 an error, and so on until an approprate handler is reached.
    176 Resumption appears in algebric effects, where a function dispatches its
     208expression as an error; thereafter, the result of any expression that tries to use it is also an
     209error, and so on until an appropriate handler is reached.
     210Resumption appears in algebraic effects, where a function dispatches its
    177211side-effects to its caller for handling.
    178212
    179213%\subsection
    180 More recently exceptions seem to be vanishing from newer programming
    181 languages, replaced by ``panic".
    182 In Rust a panic is just a program level abort that may be implemented by
     214Some programming languages have moved to a restricted kind of EHM
     215called ``panic".
     216In Rust~\cite{Rust}, a panic is just a program level abort that may be implemented by
    183217unwinding the stack like in termination exception handling.
    184218% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
    185 Go's panic through is very similar to a termination except it only supports
     219In Go~\cite{Go}, a panic is very similar to a termination, except it only supports
    186220a catch-all by calling \code{Go}{recover()}, simplifying the interface at
    187 the cost of flexability.
    188 
    189 %\subsection
    190 Exception handling's most common use cases are in error handling.
    191 Here are some other ways to handle errors and comparisons with exceptions.
     221the cost of flexibility.
     222
     223%\subsection
     224While exception handling's most common use cases are in error handling,
     225here are other ways to handle errors with comparisons to exceptions.
    192226\begin{itemize}
    193227\item\emph{Error Codes}:
    194 This pattern uses an enumeration (or just a set of fixed values) to indicate
    195 that an error has occured and which error it was.
    196 
    197 There are some issues if a function wants to return an error code and another
    198 value. The main issue is that it can be easy to forget checking the error
    199 code, which can lead to an error being quitely and implicitly ignored.
    200 Some new languages have tools that raise warnings if the return value is
    201 discarded to avoid this.
    202 It also puts more code on the main execution path.
     228This pattern has a function return an enumeration (or just a set of fixed values) to indicate
     229if an error occurred and possibly which error it was.
     230
     231Error codes mix exceptional and normal values, artificially enlarging the type and/or value range.
     232Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result.
     233However, the main issue with error codes is forgetting to checking them,
     234which leads to an error being quietly and implicitly ignored.
     235Some new languages have tools that issue warnings, if the error code is
     236discarded to avoid this problem.
     237Checking 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..
     238
    203239\item\emph{Special Return with Global Store}:
    204 A function that encounters an error returns some value indicating that it
    205 encountered a value but store which error occured in a fixed global location.
    206 
    207 Perhaps the C standard @errno@ is the most famous example of this,
    208 where some standard library functions will return some non-value (often a
    209 NULL pointer) and set @errno@.
    210 
    211 This avoids the multiple results issue encountered with straight error codes
    212 but otherwise many of the same advantages and disadvantages.
    213 It does however introduce one other major disadvantage:
    214 Everything that uses that global location must agree on all possible errors.
     240Some functions only return a boolean indicating success or failure
     241and store the exact reason for the error in a fixed global location.
     242For example, many C routines return non-zero or -1, indicating success or failure,
     243and write error details into the C standard variable @errno@.
     244
     245This approach avoids the multiple results issue encountered with straight error codes
     246but otherwise has many (if not more) of the disadvantages.
     247For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency.
     248
    215249\item\emph{Return Union}:
    216 Replaces error codes with a tagged union.
     250This pattern replaces error codes with a tagged union.
    217251Success is one tag and the errors are another.
    218252It is also possible to make each possible error its own tag and carry its own
     
    220254so that one type can be used everywhere in error handling code.
    221255
    222 This pattern is very popular in functional or semi-functional language,
    223 anything with primitive support for tagged unions (or algebraic data types).
     256This pattern is very popular in functional or any semi-functional language with
     257primitive support for tagged unions (or algebraic data types).
    224258% We need listing Rust/rust to format code snipits from it.
    225259% Rust's \code{rust}{Result<T, E>}
    226 
    227 The main disadvantage is again it puts code on the main execution path.
    228 This is also the first technique that allows for more information about an
    229 error, other than one of a fix-set of ids, to be sent.
    230 They can be missed but some languages can force that they are checked.
    231 It is also implicitly forced in any languages with checked union access.
     260The main advantage is providing for more information about an
     261error, other than one of a fix-set of ids.
     262While some languages use checked union access to force error-code checking,
     263it is still possible to bypass the checking.
     264The main disadvantage is again significant error code on the main execution path and cascading through called functions.
     265
    232266\item\emph{Handler Functions}:
    233 On error the function that produced the error calls another function to
     267This pattern implicitly associates functions with errors.
     268On error, the function that produced the error implicitly calls another function to
    234269handle it.
    235270The handler function can be provided locally (passed in as an argument,
    236271either directly as as a field of a structure/object) or globally (a global
    237272variable).
    238 
    239 C++ uses this as its fallback system if exception handling fails.
     273C++ uses this approach as its fallback system if exception handling fails, \eg
    240274\snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
    241275
    242 Handler functions work a lot like resumption exceptions.
    243 The difference is they are more expencive to set up but cheaper to use, and
    244 so are more suited to more fequent errors.
    245 The exception being global handlers if they are rarely change as the time
    246 in both cases strinks towards zero.
     276Handler functions work a lot like resumption exceptions, without the dynamic handler search.
     277Therefore, 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,
     278are 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.
    247281\end{itemize}
    248282
    249283%\subsection
    250 Because of their cost exceptions are rarely used for hot paths of execution.
    251 There is an element of self-fulfilling prophocy here as implementation
    252 techniques have been designed to make exceptions cheap to set-up at the cost
    253 of making them expencive to use.
    254 Still, use of exceptions for other tasks is more common in higher-level
    255 scripting languages.
    256 An iconic example is Python's StopIteration exception which is thrown by
    257 an iterator to indicate that it is exausted. Combined with Python's heavy
    258 use of the iterator based for-loop.
     284Because of their cost, exceptions are rarely used for hot paths of execution.
     285Therefore, there is an element of self-fulfilling prophecy for implementation
     286techniques to make exceptions cheap to set-up at the cost
     287of expensive usage.
     288This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common.
     289An iconic example is Python's @StopIteration@ exception that is thrown by
     290an iterator to indicate that it is exhausted, especially when combined with Python's heavy
     291use of the iterator-based for-loop.
    259292% https://docs.python.org/3/library/exceptions.html#StopIteration
Note: See TracChangeset for help on using the changeset viewer.