Ignore:
Timestamp:
Aug 9, 2021, 4:35:49 PM (16 months ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum
Children:
cb6b8cb
Parents:
5438e41
Message:

Copied out and reverted changes to thesis.

File:
1 edited

Legend:

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

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