[e8a7ca2] | 1 | \chapter{Introduction} |
---|
| 2 | |
---|
[471ff17] | 3 | % The highest level overview of Cforall and EHMs. Get this done right away. |
---|
[21f2e92] | 4 | This thesis goes over the design and implementation of the exception handling |
---|
| 5 | mechanism (EHM) of |
---|
[6071efc] | 6 | \CFA (pronounced sea-for-all and may be written Cforall or CFA). |
---|
| 7 | \CFA is a new programming language that extends C, that maintains |
---|
| 8 | backwards-compatibility while introducing modern programming features. |
---|
| 9 | Adding exception handling to \CFA gives it new ways to handle errors and |
---|
| 10 | make other 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. |
---|
[553f8abe] | 14 | There are two forms of exception handling covered in this thesis: |
---|
| 15 | termination, which acts as a multi-level return, |
---|
| 16 | and resumption, which is a dynamic function call. |
---|
[471ff17] | 17 | Termination handling is much more common, |
---|
| 18 | to the extent that it is often seen |
---|
[21f2e92] | 19 | This seperation is uncommon because termination exception handling is so |
---|
| 20 | much more common that it is often assumed. |
---|
[471ff17] | 21 | % 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. |
---|
[553f8abe] | 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. |
---|
[e46ea00] | 29 | \begin{center} |
---|
| 30 | \input{callreturn} |
---|
| 31 | \end{center} |
---|
| 32 | |
---|
[6071efc] | 33 | Resumption exception handling seaches the stack for a handler and then calls |
---|
| 34 | it without adding or removing any other stack frames. |
---|
[553f8abe] | 35 | \todo{Add a diagram showing control flow for resumption.} |
---|
[e46ea00] | 36 | |
---|
[553f8abe] | 37 | Although a powerful feature, exception handling tends to be complex to set up |
---|
| 38 | and 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 |
---|
| 42 | most of the cost only when the error actually occurs. |
---|
[e8a7ca2] | 43 | |
---|
[471ff17] | 44 | \section{Thesis Overview} |
---|
[21f2e92] | 45 | This work describes the design and implementation of the \CFA EHM. |
---|
[553f8abe] | 46 | The \CFA EHM implements all of the common exception features (or an |
---|
[e8a7ca2] | 47 | equivalent) found in most other EHMs and adds some features of its own. |
---|
| 48 | The design of all the features had to be adapted to \CFA's feature set as |
---|
| 49 | some of the underlying tools used to implement and express exception handling |
---|
| 50 | in other languages are absent in \CFA. |
---|
| 51 | Still the resulting syntax resembles that of other languages: |
---|
| 52 | \begin{cfa} |
---|
| 53 | try { |
---|
| 54 | ... |
---|
| 55 | T * object = malloc(request_size); |
---|
| 56 | if (!object) { |
---|
| 57 | throw OutOfMemory{fixed_allocation, request_size}; |
---|
| 58 | } |
---|
| 59 | ... |
---|
| 60 | } catch (OutOfMemory * error) { |
---|
| 61 | ... |
---|
| 62 | } |
---|
| 63 | \end{cfa} |
---|
| 64 | |
---|
| 65 | % A note that yes, that was a very fast overview. |
---|
[471ff17] | 66 | The design and implementation of all of \CFA's EHM's features are |
---|
[553f8abe] | 67 | described in detail throughout this thesis, whether they are a common feature |
---|
[e8a7ca2] | 68 | or one unique to \CFA. |
---|
| 69 | |
---|
| 70 | % The current state of the project and what it contributes. |
---|
[471ff17] | 71 | All of these features have been implemented in \CFA, along with |
---|
[553f8abe] | 72 | a suite of test cases as part of this project. |
---|
[e8a7ca2] | 73 | The implementation techniques are generally applicable in other programming |
---|
[553f8abe] | 74 | languages 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. |
---|
[e46ea00] | 77 | |
---|
[553f8abe] | 78 | % 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. |
---|
[e46ea00] | 83 | |
---|
| 84 | The contributions of this work are: |
---|
| 85 | \begin{enumerate} |
---|
[553f8abe] | 86 | \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. |
---|
| 91 | % I think the virtual system and per-call site default handlers are the only |
---|
| 92 | % "new" features, everything else is a matter of implementation. |
---|
[e46ea00] | 93 | \end{enumerate} |
---|
| 94 | |
---|
[471ff17] | 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. |
---|
[553f8abe] | 100 | That is followed by the implementation of those features in |
---|
| 101 | \autoref{c:implement}. |
---|
[471ff17] | 102 | The performance results are examined in \autoref{c:performance}. |
---|
| 103 | Possibilities to extend this project are discussed in \autoref{c:future}. |
---|
| 104 | |
---|
| 105 | \section{Background} |
---|
| 106 | \label{s:background} |
---|
| 107 | |
---|
| 108 | Exception handling is not a new concept, |
---|
[fcaa1e4] | 109 | with papers on the subject dating back 70s.\cite{Goodenough} |
---|
[471ff17] | 110 | |
---|
[fcaa1e4] | 111 | Early exceptions were often treated as signals. They carried no information |
---|
| 112 | except their identity. Ada still uses this system. |
---|
| 113 | |
---|
| 114 | The modern flag-ship for termination exceptions is \Cpp, |
---|
[471ff17] | 115 | which added them in its first major wave of non-object-orientated features |
---|
| 116 | in 1990. |
---|
| 117 | % https://en.cppreference.com/w/cpp/language/history |
---|
[fcaa1e4] | 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 |
---|
| 120 | \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} |
---|
| 132 | and it uses checked exceptions. |
---|
[471ff17] | 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 |
---|
| 137 | safety, 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 |
---|
[fcaa1e4] | 148 | programming languages have implemented them. |
---|
[471ff17] | 149 | % http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/ |
---|
| 150 | % CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf |
---|
[fcaa1e4] | 151 | Mesa is one programming languages that did. Experiance with Mesa |
---|
| 152 | is quoted as being one of the reasons resumptions were not |
---|
[471ff17] | 153 | included in the \Cpp standard. |
---|
| 154 | % https://en.wikipedia.org/wiki/Exception_handling |
---|
[fcaa1e4] | 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. |
---|
| 167 | % Especially considering how much easier they are to implement than |
---|
| 168 | % termination exceptions. |
---|
[471ff17] | 169 | |
---|
| 170 | %\subsection |
---|
[fcaa1e4] | 171 | Functional languages tend to use other solutions for their primary error |
---|
| 172 | handling mechanism, exception-like constructs still appear. |
---|
| 173 | Termination 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 |
---|
| 177 | side-effects to its caller for handling. |
---|
[471ff17] | 178 | |
---|
| 179 | %\subsection |
---|
| 180 | More recently exceptions seem to be vanishing from newer programming |
---|
[fcaa1e4] | 181 | languages, replaced by ``panic". |
---|
| 182 | In Rust a panic is just a program level abort that may be implemented by |
---|
| 183 | unwinding the stack like in termination exception handling. |
---|
[471ff17] | 184 | % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html |
---|
[fcaa1e4] | 185 | Go's panic through is very similar to a termination except it only supports |
---|
| 186 | a catch-all by calling \code{Go}{recover()}, simplifying the interface at |
---|
| 187 | the cost of flexability. |
---|
[471ff17] | 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. |
---|
| 192 | \begin{itemize} |
---|
| 193 | \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. |
---|
| 203 | \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. |
---|
| 215 | \item\emph{Return Union}: |
---|
| 216 | Replaces error codes with a tagged union. |
---|
| 217 | Success is one tag and the errors are another. |
---|
| 218 | It is also possible to make each possible error its own tag and carry its own |
---|
| 219 | additional information, but the two branch format is easy to make generic |
---|
| 220 | so that one type can be used everywhere in error handling code. |
---|
| 221 | |
---|
| 222 | This pattern is very popular in functional or semi-functional language, |
---|
| 223 | anything with primitive support for tagged unions (or algebraic data types). |
---|
| 224 | % We need listing Rust/rust to format code snipits from it. |
---|
| 225 | % 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. |
---|
| 232 | \item\emph{Handler Functions}: |
---|
| 233 | On error the function that produced the error calls another function to |
---|
| 234 | handle it. |
---|
| 235 | The handler function can be provided locally (passed in as an argument, |
---|
| 236 | either directly as as a field of a structure/object) or globally (a global |
---|
| 237 | variable). |
---|
| 238 | |
---|
| 239 | C++ uses this as its fallback system if exception handling fails. |
---|
| 240 | \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler} |
---|
| 241 | |
---|
| 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. |
---|
| 247 | \end{itemize} |
---|
| 248 | |
---|
| 249 | %\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. |
---|
| 259 | % https://docs.python.org/3/library/exceptions.html#StopIteration |
---|