[e8a7ca2] | 1 | \chapter{Introduction} |
---|
| 2 | |
---|
[471ff17] | 3 | % The highest level overview of Cforall and EHMs. Get this done right away. |
---|
[cb6b8cb] | 4 | This thesis covers the design and implementation of the exception handling |
---|
[21f2e92] | 5 | mechanism (EHM) of |
---|
[6071efc] | 6 | \CFA (pronounced sea-for-all and may be written Cforall or CFA). |
---|
[cb6b8cb] | 7 | \CFA is a new programming language that extends C, which maintains |
---|
[6071efc] | 8 | backwards-compatibility while introducing modern programming features. |
---|
| 9 | Adding exception handling to \CFA gives it new ways to handle errors and |
---|
[cb6b8cb] | 10 | make large control-flow jumps. |
---|
[471ff17] | 11 | |
---|
| 12 | % Now take a step back and explain what exceptions are generally. |
---|
[21f2e92] | 13 | Exception handling provides dynamic inter-function control flow. |
---|
[cb6b8cb] | 14 | A language's EHM is a combination of language syntax and run-time |
---|
| 15 | components that construct, raise, propagate and handle exceptions, |
---|
| 16 | to provide all of that control flow. |
---|
[553f8abe] | 17 | There are two forms of exception handling covered in this thesis: |
---|
| 18 | termination, which acts as a multi-level return, |
---|
| 19 | and resumption, which is a dynamic function call. |
---|
[cb6b8cb] | 20 | % About other works: |
---|
| 21 | Often, when this separation is not made, termination exceptions are assumed |
---|
| 22 | as they are more common and may be the only form of handling provided in |
---|
| 23 | a language. |
---|
[553f8abe] | 24 | |
---|
[cb6b8cb] | 25 | All types of exception handling link a raise with a handler. |
---|
| 26 | Both operations are usually language primitives, although raises can be |
---|
[9cdfa5fb] | 27 | treated as a function that takes an exception argument. |
---|
| 28 | Handlers are more complex, as they are added to and removed from the stack |
---|
| 29 | during execution, must specify what they can handle and must give the code to |
---|
[cb6b8cb] | 30 | handle the exception. |
---|
| 31 | |
---|
| 32 | Exceptions work with different execution models but for the descriptions |
---|
| 33 | that follow a simple call stack, with functions added and removed in a |
---|
| 34 | first-in-last-out order, is assumed. |
---|
| 35 | |
---|
| 36 | Termination exception handling searches the stack for the handler, then |
---|
| 37 | unwinds the stack to where the handler was found before calling it. |
---|
| 38 | The handler is run inside the function that defined it and when it finishes |
---|
| 39 | it returns control to that function. |
---|
[e46ea00] | 40 | \begin{center} |
---|
[75f8e04] | 41 | \input{termination} |
---|
[432bffe] | 42 | |
---|
| 43 | \medskip |
---|
| 44 | \input{termhandle.pstex_t} |
---|
[e46ea00] | 45 | \end{center} |
---|
[6aa84e0] | 46 | \todo*{Can I make the new diagrams fit the old style?} |
---|
[e46ea00] | 47 | |
---|
[cb6b8cb] | 48 | Resumption exception handling searches the stack for a handler and then calls |
---|
| 49 | it without removing any other stack frames. |
---|
| 50 | The handler is run on top of the existing stack, often as a new function or |
---|
| 51 | closure capturing the context in which the handler was defined. |
---|
[9cdfa5fb] | 52 | After the handler has finished running, it returns control to the function |
---|
[cb6b8cb] | 53 | that preformed the raise, usually starting after the raise. |
---|
| 54 | \begin{center} |
---|
| 55 | \input{resumption} |
---|
[432bffe] | 56 | |
---|
| 57 | \medskip |
---|
| 58 | \input{resumhandle.pstex_t} |
---|
[cb6b8cb] | 59 | \end{center} |
---|
[e46ea00] | 60 | |
---|
[553f8abe] | 61 | Although a powerful feature, exception handling tends to be complex to set up |
---|
[9cdfa5fb] | 62 | and expensive to use, |
---|
[cb6b8cb] | 63 | so it is often limited to unusual or ``exceptional" cases. |
---|
[9cdfa5fb] | 64 | The classic example is error handling; exceptions can be used to |
---|
[cb6b8cb] | 65 | remove error handling logic from the main execution path, and pay |
---|
[553f8abe] | 66 | most of the cost only when the error actually occurs. |
---|
[e8a7ca2] | 67 | |
---|
[471ff17] | 68 | \section{Thesis Overview} |
---|
[21f2e92] | 69 | This work describes the design and implementation of the \CFA EHM. |
---|
[553f8abe] | 70 | The \CFA EHM implements all of the common exception features (or an |
---|
[e8a7ca2] | 71 | equivalent) found in most other EHMs and adds some features of its own. |
---|
[9cdfa5fb] | 72 | The design of all the features had to be adapted to \CFA's feature set, as |
---|
[e8a7ca2] | 73 | some of the underlying tools used to implement and express exception handling |
---|
| 74 | in other languages are absent in \CFA. |
---|
[9cdfa5fb] | 75 | Still, the resulting syntax resembles that of other languages: |
---|
[f42a6b8] | 76 | \begin{cfa} |
---|
| 77 | try { |
---|
[e8a7ca2] | 78 | ... |
---|
| 79 | T * object = malloc(request_size); |
---|
| 80 | if (!object) { |
---|
[f42a6b8] | 81 | throw OutOfMemory{fixed_allocation, request_size}; |
---|
[e8a7ca2] | 82 | } |
---|
| 83 | ... |
---|
[f42a6b8] | 84 | } catch (OutOfMemory * error) { |
---|
[e8a7ca2] | 85 | ... |
---|
| 86 | } |
---|
[f42a6b8] | 87 | \end{cfa} |
---|
[e8a7ca2] | 88 | % A note that yes, that was a very fast overview. |
---|
[471ff17] | 89 | The design and implementation of all of \CFA's EHM's features are |
---|
[553f8abe] | 90 | described in detail throughout this thesis, whether they are a common feature |
---|
[e8a7ca2] | 91 | or one unique to \CFA. |
---|
| 92 | |
---|
| 93 | % The current state of the project and what it contributes. |
---|
[cb6b8cb] | 94 | All of these features have been implemented in \CFA, |
---|
| 95 | covering both changes to the compiler and the run-time. |
---|
| 96 | In addition, a suite of test cases and performance benchmarks were created |
---|
[9cdfa5fb] | 97 | alongside the implementation. |
---|
[f42a6b8] | 98 | The implementation techniques are generally applicable in other programming |
---|
[553f8abe] | 99 | languages and much of the design is as well. |
---|
[cb6b8cb] | 100 | Some parts of the EHM use other features unique to \CFA and would be |
---|
[f42a6b8] | 101 | harder to replicate in other programming languages. |
---|
| 102 | |
---|
[e46ea00] | 103 | The contributions of this work are: |
---|
| 104 | \begin{enumerate} |
---|
[553f8abe] | 105 | \item Designing \CFA's exception handling mechanism, adapting designs from |
---|
[cb6b8cb] | 106 | other programming languages and creating new features. |
---|
| 107 | \item Implementing stack unwinding and the \CFA EHM, including updating |
---|
| 108 | the \CFA compiler and the run-time environment. |
---|
[9cdfa5fb] | 109 | \item Designing and implementing a prototype virtual system. |
---|
[553f8abe] | 110 | % I think the virtual system and per-call site default handlers are the only |
---|
| 111 | % "new" features, everything else is a matter of implementation. |
---|
[cb6b8cb] | 112 | \item Creating tests to check the behaviour of the EHM. |
---|
[9cdfa5fb] | 113 | \item Creating benchmarks to check the performance of the EHM, |
---|
[cb6b8cb] | 114 | as compared to other languages. |
---|
[e46ea00] | 115 | \end{enumerate} |
---|
| 116 | |
---|
[cb6b8cb] | 117 | The rest of this thesis is organized as follows. |
---|
| 118 | The current state of exceptions is covered in \autoref{s:background}. |
---|
[9cdfa5fb] | 119 | The existing state of \CFA is covered in \autoref{c:existing}. |
---|
[cb6b8cb] | 120 | New EHM features are introduced in \autoref{c:features}, |
---|
| 121 | covering their usage and design. |
---|
| 122 | That is followed by the implementation of these features in |
---|
[553f8abe] | 123 | \autoref{c:implement}. |
---|
[cb6b8cb] | 124 | Performance results are examined in \autoref{c:performance}. |
---|
[f42a6b8] | 125 | Possibilities to extend this project are discussed in \autoref{c:future}. |
---|
[cb6b8cb] | 126 | Finally, the project is summarized in \autoref{c:conclusion}. |
---|
[471ff17] | 127 | |
---|
| 128 | \section{Background} |
---|
| 129 | \label{s:background} |
---|
| 130 | |
---|
[cb6b8cb] | 131 | Exception handling has been examined before in programming languages, |
---|
| 132 | with papers on the subject dating back 70s.\cite{Goodenough75} |
---|
| 133 | Early exceptions were often treated as signals, which carried no information |
---|
[6cf21ed8] | 134 | except their identity. |
---|
| 135 | Ada originally used this system\cite{Ada}, but now allows for a string |
---|
| 136 | message as a payload\cite{Ada12}. |
---|
[fcaa1e4] | 137 | |
---|
| 138 | The modern flag-ship for termination exceptions is \Cpp, |
---|
[471ff17] | 139 | which added them in its first major wave of non-object-orientated features |
---|
[6cf21ed8] | 140 | in 1990.\cite{CppHistory} |
---|
[cb6b8cb] | 141 | Many EHMs have special exception types, |
---|
| 142 | however \Cpp has the ability to use any type as an exception. |
---|
| 143 | These were found to be not very useful and have been pushed aside for classes |
---|
| 144 | inheriting from |
---|
[fcaa1e4] | 145 | \code{C++}{std::exception}. |
---|
[9cdfa5fb] | 146 | Although there is a special catch-all syntax (@catch(...)@), there are no |
---|
[cb6b8cb] | 147 | operations that can be performed on the caught value, not even type inspection. |
---|
[9cdfa5fb] | 148 | Instead, the base exception-type \code{C++}{std::exception} defines common |
---|
[cb6b8cb] | 149 | functionality (such as |
---|
[f42a6b8] | 150 | the ability to describe the reason the exception was raised) and all |
---|
[cb6b8cb] | 151 | exceptions have this functionality. |
---|
| 152 | That trade-off, restricting usable types to gain guaranteed functionality, |
---|
| 153 | is almost universal now, as without some common functionality it is almost |
---|
| 154 | impossible to actually handle any errors. |
---|
[fcaa1e4] | 155 | |
---|
[6cf21ed8] | 156 | Java was the next popular language to use exceptions.\cite{Java8} |
---|
[9cdfa5fb] | 157 | Its exception system largely reflects that of \Cpp, except that it requires |
---|
[f42a6b8] | 158 | you throw a child type of \code{Java}{java.lang.Throwable} |
---|
[fcaa1e4] | 159 | and it uses checked exceptions. |
---|
[cb6b8cb] | 160 | Checked exceptions are part of a function's interface, |
---|
| 161 | the exception signature of the function. |
---|
[9cdfa5fb] | 162 | Every exception that could be raised from a function, either directly or |
---|
[cb6b8cb] | 163 | because it is not handled from a called function, is given. |
---|
| 164 | Using this information, it is possible to statically verify if any given |
---|
[9cdfa5fb] | 165 | exception is handled, and guarantee that no exception will go unhandled. |
---|
[cb6b8cb] | 166 | Making exception information explicit improves clarity and safety, |
---|
| 167 | but can slow down or restrict programming. |
---|
| 168 | For example, programming high-order functions becomes much more complex |
---|
| 169 | if the argument functions could raise exceptions. |
---|
| 170 | However, as odd it may seem, the worst problems are rooted in the simple |
---|
| 171 | inconvenience of writing and updating exception signatures. |
---|
| 172 | This has caused Java programmers to develop multiple programming ``hacks'' |
---|
| 173 | to circumvent checked exceptions, negating their advantages. |
---|
| 174 | One particularly problematic example is the ``catch-and-ignore'' pattern, |
---|
| 175 | where an empty handler is used to handle an exception without doing any |
---|
| 176 | recovery or repair. In theory that could be good enough to properly handle |
---|
| 177 | the exception, but more often is used to ignore an exception that the |
---|
[9cdfa5fb] | 178 | programmer does not feel is worth the effort of handling, for instance if |
---|
[cb6b8cb] | 179 | they do not believe it will ever be raised. |
---|
[9cdfa5fb] | 180 | If they are incorrect, the exception will be silenced, while in a similar |
---|
[cb6b8cb] | 181 | situation with unchecked exceptions the exception would at least activate |
---|
[9cdfa5fb] | 182 | the language's unhandled exception code (usually, a program abort with an |
---|
[cb6b8cb] | 183 | error message). |
---|
[471ff17] | 184 | |
---|
| 185 | %\subsection |
---|
[cb6b8cb] | 186 | Resumption exceptions are less popular, |
---|
[9cdfa5fb] | 187 | although resumption is as old as termination; that is, few |
---|
[fcaa1e4] | 188 | programming languages have implemented them. |
---|
[471ff17] | 189 | % http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/ |
---|
| 190 | % CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf |
---|
[6cf21ed8] | 191 | Mesa is one programming language that did.\cite{Mesa} Experience with Mesa |
---|
[f42a6b8] | 192 | is quoted as being one of the reasons resumptions were not |
---|
[471ff17] | 193 | included in the \Cpp standard. |
---|
| 194 | % https://en.wikipedia.org/wiki/Exception_handling |
---|
[9cdfa5fb] | 195 | Since then, resumptions have been ignored in main-stream programming languages. |
---|
[cb6b8cb] | 196 | However, resumption is being revisited in the context of decades of other |
---|
| 197 | developments in programming languages. |
---|
| 198 | While rejecting resumption may have been the right decision in the past, |
---|
| 199 | the situation has changed since then. |
---|
[9cdfa5fb] | 200 | Some developments, such as the functional programming equivalent to resumptions, |
---|
[cb6b8cb] | 201 | algebraic effects\cite{Zhang19}, are enjoying success. |
---|
[9cdfa5fb] | 202 | A complete reexamination of resumption is beyond this thesis, |
---|
| 203 | but their reemergence is enough reason to try them in \CFA. |
---|
[fcaa1e4] | 204 | % Especially considering how much easier they are to implement than |
---|
[cb6b8cb] | 205 | % termination exceptions and how much Peter likes them. |
---|
[471ff17] | 206 | |
---|
| 207 | %\subsection |
---|
[f42a6b8] | 208 | Functional languages tend to use other solutions for their primary error |
---|
[cb6b8cb] | 209 | handling mechanism, but exception-like constructs still appear. |
---|
| 210 | Termination appears in the error construct, which marks the result of an |
---|
| 211 | expression as an error; then the result of any expression that tries to use |
---|
| 212 | it also results in an error, and so on until an appropriate handler is reached. |
---|
| 213 | Resumption appears in algebraic effects, where a function dispatches its |
---|
[fcaa1e4] | 214 | side-effects to its caller for handling. |
---|
[471ff17] | 215 | |
---|
| 216 | %\subsection |
---|
[9cdfa5fb] | 217 | More recently exceptions, seem to be vanishing from newer programming |
---|
[f42a6b8] | 218 | languages, replaced by ``panic". |
---|
[cb6b8cb] | 219 | In Rust, a panic is just a program level abort that may be implemented by |
---|
[6cf21ed8] | 220 | unwinding the stack like in termination exception |
---|
| 221 | handling.\cite{RustPanicMacro}\cite{RustPanicModule} |
---|
[cb6b8cb] | 222 | Go's panic through is very similar to a termination, except it only supports |
---|
[fcaa1e4] | 223 | a catch-all by calling \code{Go}{recover()}, simplifying the interface at |
---|
[6cf21ed8] | 224 | the cost of flexibility.\cite{Go:2021} |
---|
[471ff17] | 225 | |
---|
| 226 | %\subsection |
---|
[9cdfa5fb] | 227 | As exception handling's most common use cases are in error handling, |
---|
[cb6b8cb] | 228 | here are some other ways to handle errors with comparisons with exceptions. |
---|
[471ff17] | 229 | \begin{itemize} |
---|
| 230 | \item\emph{Error Codes}: |
---|
[cb6b8cb] | 231 | This pattern has a function return an enumeration (or just a set of fixed |
---|
| 232 | values) to indicate if an error has occurred and possibly which error it was. |
---|
| 233 | |
---|
| 234 | Error codes mix exceptional/error and normal values, enlarging the range of |
---|
| 235 | possible return values. This can be addressed with multiple return values |
---|
| 236 | (or a tuple) or a tagged union. |
---|
| 237 | However, the main issue with error codes is forgetting to check them, |
---|
| 238 | which leads to an error being quietly and implicitly ignored. |
---|
| 239 | Some new languages and tools will try to issue warnings when an error code |
---|
| 240 | is discarded to avoid this problem. |
---|
| 241 | Checking error codes also bloats the main execution path, |
---|
[9cdfa5fb] | 242 | especially if the error is not handled immediately and has to be passed |
---|
[cb6b8cb] | 243 | through multiple functions before it is addressed. |
---|
[471ff17] | 244 | |
---|
| 245 | \item\emph{Special Return with Global Store}: |
---|
[cb6b8cb] | 246 | Similar to the error codes pattern but the function itself only returns |
---|
[9cdfa5fb] | 247 | that there was an error, |
---|
| 248 | and stores the reason for the error in a fixed global location. |
---|
| 249 | For example, many routines in the C standard library will only return some |
---|
[cb6b8cb] | 250 | error value (such as -1 or a null pointer) and the error code is written into |
---|
| 251 | the standard variable @errno@. |
---|
[471ff17] | 252 | |
---|
[cb6b8cb] | 253 | This approach avoids the multiple results issue encountered with straight |
---|
| 254 | error codes but otherwise has the same disadvantages and more. |
---|
| 255 | Every function that reads or writes to the global store must agree on all |
---|
| 256 | possible errors and managing it becomes more complex with concurrency. |
---|
[471ff17] | 257 | |
---|
| 258 | \item\emph{Return Union}: |
---|
[cb6b8cb] | 259 | This pattern replaces error codes with a tagged union. |
---|
[471ff17] | 260 | Success is one tag and the errors are another. |
---|
| 261 | It is also possible to make each possible error its own tag and carry its own |
---|
[9cdfa5fb] | 262 | additional information, but the two-branch format is easy to make generic |
---|
[471ff17] | 263 | so that one type can be used everywhere in error handling code. |
---|
| 264 | |
---|
[cb6b8cb] | 265 | This pattern is very popular in any functional or semi-functional language |
---|
| 266 | with primitive support for tagged unions (or algebraic data types). |
---|
| 267 | % We need listing Rust/rust to format code snippets from it. |
---|
[471ff17] | 268 | % Rust's \code{rust}{Result<T, E>} |
---|
[cb6b8cb] | 269 | The main advantage is that an arbitrary object can be used to represent an |
---|
[9cdfa5fb] | 270 | error, so it can include a lot more information than a simple error code. |
---|
[cb6b8cb] | 271 | The disadvantages include that the it does have to be checked along the main |
---|
[9cdfa5fb] | 272 | execution, and if there aren't primitive tagged unions proper, usage can be |
---|
[cb6b8cb] | 273 | hard to enforce. |
---|
[471ff17] | 274 | |
---|
| 275 | \item\emph{Handler Functions}: |
---|
[cb6b8cb] | 276 | This pattern associates errors with functions. |
---|
| 277 | On error, the function that produced the error calls another function to |
---|
[471ff17] | 278 | handle it. |
---|
| 279 | The handler function can be provided locally (passed in as an argument, |
---|
| 280 | either directly as as a field of a structure/object) or globally (a global |
---|
| 281 | variable). |
---|
[cb6b8cb] | 282 | C++ uses this approach as its fallback system if exception handling fails, |
---|
[9cdfa5fb] | 283 | such as \snake{std::terminate} and, for a time, |
---|
| 284 | \snake{std::unexpected}.\footnote{\snake{std::unexpected} was part of the |
---|
| 285 | Dynamic Exception Specification, which has been removed from the standard |
---|
| 286 | as of C++20.\cite{CppExceptSpec}} |
---|
[f42a6b8] | 287 | |
---|
[cb6b8cb] | 288 | Handler functions work a lot like resumption exceptions, |
---|
| 289 | but without the dynamic search for a handler. |
---|
| 290 | Since setting up the handler can be more complex/expensive, |
---|
| 291 | especially when the handler has to be passed through multiple layers of |
---|
| 292 | function calls, but cheaper (constant time) to call, |
---|
| 293 | they are more suited to more frequent (less exceptional) situations. |
---|
[471ff17] | 294 | \end{itemize} |
---|
| 295 | |
---|
| 296 | %\subsection |
---|
[cb6b8cb] | 297 | Because of their cost, exceptions are rarely used for hot paths of execution. |
---|
| 298 | Hence, there is an element of self-fulfilling prophecy as implementation |
---|
| 299 | techniques have been focused on making them cheap to set-up, |
---|
| 300 | happily making them expensive to use in exchange. |
---|
| 301 | This difference is less important in higher-level scripting languages, |
---|
[9cdfa5fb] | 302 | where using exceptions for other tasks is more common. |
---|
[6cf21ed8] | 303 | An iconic example is Python's |
---|
[9cdfa5fb] | 304 | \code{Python}{StopIteration}\cite{PythonExceptions} exception, that |
---|
[cb6b8cb] | 305 | is thrown by an iterator to indicate that it is exhausted. |
---|
[9cdfa5fb] | 306 | When paired with Python's iterator-based for-loop, this will be thrown every |
---|
[6cf21ed8] | 307 | time the end of the loop is reached.\cite{PythonForLoop} |
---|