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