Changeset cb6b8cb


Ignore:
Timestamp:
Aug 12, 2021, 3:13:22 PM (3 years ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum
Children:
be497c6
Parents:
f42a6b8
Message:

Andrew MMath: Fixes in the conclusion and main body. Used Peter's infroduction feedback; which was never wrong in the first place.

Location:
doc/theses/andrew_beach_MMath
Files:
3 edited

Legend:

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

    rf42a6b8 rcb6b8cb  
    11\chapter{Conclusion}
     2\label{c:conclusion}
    23% Just a little knot to tie the paper together.
    34
  • doc/theses/andrew_beach_MMath/intro.tex

    rf42a6b8 rcb6b8cb  
    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.
    1313Exception handling provides dynamic inter-function control flow.
     14A language's EHM is a combination of language syntax and run-time
     15components that construct, raise, propagate and handle exceptions,
     16to provide all of that control flow.
    1417There are two forms of exception handling covered in this thesis:
    1518termination, which acts as a multi-level return,
    1619and resumption, which is a dynamic function call.
    17 Termination 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.
    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.
    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.
     20% About other works:
     21Often, when this separation is not made, termination exceptions are assumed
     22as they are more common and may be the only form of handling provided in
     23a language.
     24
     25All types of exception handling link a raise with a handler.
     26Both operations are usually language primitives, although raises can be
     27treated as a primitive function that takes an exception argument.
     28Handlers are more complex as they are added to and removed from the stack
     29during execution, must specify what they can handle and give the code to
     30handle the exception.
     31
     32Exceptions work with different execution models but for the descriptions
     33that follow a simple call stack, with functions added and removed in a
     34first-in-last-out order, is assumed.
     35
     36Termination exception handling searches the stack for the handler, then
     37unwinds the stack to where the handler was found before calling it.
     38The handler is run inside the function that defined it and when it finishes
     39it returns control to that function.
    2940\begin{center}
    3041\input{callreturn}
    3142\end{center}
    3243
    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.}
     44Resumption exception handling searches the stack for a handler and then calls
     45it without removing any other stack frames.
     46The handler is run on top of the existing stack, often as a new function or
     47closure capturing the context in which the handler was defined.
     48After the handler has finished running it returns control to the function
     49that preformed the raise, usually starting after the raise.
     50\begin{center}
     51\input{resumption}
     52\end{center}
    3653
    3754Although a powerful feature, exception handling tends to be complex to set up
    3855and 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
     56so it is often limited to unusual or ``exceptional" cases.
     57The classic example is error handling, exceptions can be used to
     58remove error handling logic from the main execution path, and pay
    4259most of the cost only when the error actually occurs.
    4360
     
    6279}
    6380\end{cfa}
    64 
    6581% A note that yes, that was a very fast overview.
    6682The design and implementation of all of \CFA's EHM's features are
     
    6985
    7086% 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.
     87All of these features have been implemented in \CFA,
     88covering both changes to the compiler and the run-time.
     89In addition, a suite of test cases and performance benchmarks were created
     90along side the implementation.
    7391The implementation techniques are generally applicable in other programming
    7492languages and much of the design is as well.
    75 Some parts of the EHM use other features unique to \CFA and these would be
     93Some parts of the EHM use other features unique to \CFA and would be
    7694harder to replicate in other programming languages.
    77 
    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.
    8395
    8496The contributions of this work are:
    8597\begin{enumerate}
    8698\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.
     99other programming languages and creating new features.
     100\item Implementing stack unwinding and the \CFA EHM, including updating
     101the \CFA compiler and the run-time environment.
    90102\item Designed and implemented a prototype virtual system.
    91103% I think the virtual system and per-call site default handlers are the only
    92104% "new" features, everything else is a matter of implementation.
     105\item Creating tests to check the behaviour of the EHM.
     106\item Creating benchmarks to check the performances of the EHM,
     107as compared to other languages.
    93108\end{enumerate}
    94109
    95 \todo{I can't figure out a good lead-in to the roadmap.}
    96 The next section covers the existing state of exceptions.
     110The rest of this thesis is organized as follows.
     111The current state of exceptions is covered in \autoref{s:background}.
    97112The 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
     113New EHM features are introduced in \autoref{c:features},
     114covering their usage and design.
     115That is followed by the implementation of these features in
    101116\autoref{c:implement}.
    102 The performance results are examined in \autoref{c:performance}.
     117Performance results are examined in \autoref{c:performance}.
    103118Possibilities to extend this project are discussed in \autoref{c:future}.
     119Finally, the project is summarized in \autoref{c:conclusion}.
    104120
    105121\section{Background}
    106122\label{s:background}
    107123
    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.
     124Exception handling has been examined before in programming languages,
     125with papers on the subject dating back 70s.\cite{Goodenough75}
     126Early exceptions were often treated as signals, which carried no information
     127except their identity. Ada still uses this system.\todo{cite Ada}
    113128
    114129The modern flag-ship for termination exceptions is \Cpp,
    115130which added them in its first major wave of non-object-orientated features
    116131in 1990.
    117 % 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
     132\todo{cite https://en.cppreference.com/w/cpp/language/history}
     133Many EHMs have special exception types,
     134however \Cpp has the ability to use any type as an exception.
     135These were found to be not very useful and have been pushed aside for classes
     136inheriting from
    120137\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
     138Although there is a special catch-all syntax (@catch(...)@) there are no
     139operations that can be performed on the caught value, not even type inspection.
     140Instead the base exception-type \code{C++}{std::exception} defines common
     141functionality (such as
    124142the 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.
     143exceptions have this functionality.
     144That trade-off, restricting usable types to gain guaranteed functionality,
     145is almost universal now, as without some common functionality it is almost
     146impossible to actually handle any errors.
     147
     148Java was the next popular language to use exceptions. \todo{cite Java}
    130149Its exception system largely reflects that of \Cpp, except that requires
    131150you throw a child type of \code{Java}{java.lang.Throwable}
    132151and 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
    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
     152Checked exceptions are part of a function's interface,
     153the exception signature of the function.
     154Every function that could be raised from a function, either directly or
     155because it is not handled from a called function, is given.
     156Using this information, it is possible to statically verify if any given
     157exception is handled and guarantee that no exception will go unhandled.
     158Making exception information explicit improves clarity and safety,
     159but can slow down or restrict programming.
     160For example, programming high-order functions becomes much more complex
     161if the argument functions could raise exceptions.
     162However, as odd it may seem, the worst problems are rooted in the simple
     163inconvenience of writing and updating exception signatures.
     164This has caused Java programmers to develop multiple programming ``hacks''
     165to circumvent checked exceptions, negating their advantages.
     166One particularly problematic example is the ``catch-and-ignore'' pattern,
     167where an empty handler is used to handle an exception without doing any
     168recovery or repair. In theory that could be good enough to properly handle
     169the exception, but more often is used to ignore an exception that the       
     170programmer does not feel is worth the effort of handling it, for instance if
     171they do not believe it will ever be raised.
     172If they are incorrect the exception will be silenced, while in a similar
     173situation with unchecked exceptions the exception would at least activate   
     174the language's unhandled exception code (usually program abort with an 
     175error message).
     176
     177%\subsection
     178Resumption exceptions are less popular,
     179although resumption is as old as termination; hence, few
    148180programming languages have implemented them.
    149181% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    150182%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
    151 Mesa is one programming languages that did. Experiance with Mesa
     183Mesa is one programming language that did.\todo{cite Mesa} Experience with Mesa
    152184is quoted as being one of the reasons resumptions were not
    153185included in the \Cpp standard.
    154186% 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.
     187Since then resumptions have been ignored in main-stream programming languages.
     188However, resumption is being revisited in the context of decades of other
     189developments in programming languages.
     190While rejecting resumption may have been the right decision in the past,
     191the situation has changed since then.
     192Some developments, such as the function programming equivalent to resumptions,
     193algebraic effects\cite{Zhang19}, are enjoying success.
     194A complete reexamination of resumptions is beyond this thesis,
     195but there reemergence is enough to try them in \CFA.
    167196% Especially considering how much easier they are to implement than
    168 % termination exceptions.
     197% termination exceptions and how much Peter likes them.
    169198
    170199%\subsection
    171200Functional 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
     201handling mechanism, but exception-like constructs still appear.
     202Termination appears in the error construct, which marks the result of an
     203expression as an error; then the result of any expression that tries to use
     204it also results in an error, and so on until an appropriate handler is reached.
     205Resumption appears in algebraic effects, where a function dispatches its
    177206side-effects to its caller for handling.
    178207
     
    180209More recently exceptions seem to be vanishing from newer programming
    181210languages, 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.
     211In Rust, a panic is just a program level abort that may be implemented by
     212unwinding the stack like in termination exception handling.\todo{cite Rust}
    184213% 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
     214Go's panic through is very similar to a termination, except it only supports
    186215a 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.
     216the cost of flexibility.\todo{cite Go}
     217
     218%\subsection
     219While exception handling's most common use cases are in error handling,
     220here are some other ways to handle errors with comparisons with exceptions.
    192221\begin{itemize}
    193222\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.
     223This pattern has a function return an enumeration (or just a set of fixed
     224values) to indicate if an error has occurred and possibly which error it was.
     225
     226Error codes mix exceptional/error and normal values, enlarging the range of
     227possible return values. This can be addressed with multiple return values
     228(or a tuple) or a tagged union.
     229However, the main issue with error codes is forgetting to check them,
     230which leads to an error being quietly and implicitly ignored.
     231Some new languages and tools will try to issue warnings when an error code
     232is discarded to avoid this problem.
     233Checking error codes also bloats the main execution path,
     234especially if the error is not handled immediately hand has to be passed
     235through multiple functions before it is addressed.
     236
    203237\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.
     238Similar to the error codes pattern but the function itself only returns
     239that there was an error
     240and store the reason for the error in a fixed global location.
     241For example many routines in the C standard library will only return some
     242error value (such as -1 or a null pointer) and the error code is written into
     243the standard variable @errno@.
     244
     245This approach avoids the multiple results issue encountered with straight
     246error codes but otherwise has the same disadvantages and more.
     247Every function that reads or writes to the global store must agree on all
     248possible errors and managing it becomes more complex with concurrency.
     249
    215250\item\emph{Return Union}:
    216 Replaces error codes with a tagged union.
     251This pattern replaces error codes with a tagged union.
    217252Success is one tag and the errors are another.
    218253It is also possible to make each possible error its own tag and carry its own
     
    220255so that one type can be used everywhere in error handling code.
    221256
    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.
     257This pattern is very popular in any functional or semi-functional language
     258with primitive support for tagged unions (or algebraic data types).
     259% We need listing Rust/rust to format code snippets from it.
    225260% 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.
     261The main advantage is that an arbitrary object can be used to represent an
     262error so it can include a lot more information than a simple error code.
     263The disadvantages include that the it does have to be checked along the main
     264execution and if there aren't primitive tagged unions proper usage can be
     265hard to enforce.
     266
    232267\item\emph{Handler Functions}:
    233 On error the function that produced the error calls another function to
     268This pattern associates errors with functions.
     269On error, the function that produced the error calls another function to
    234270handle it.
    235271The handler function can be provided locally (passed in as an argument,
    236272either directly as as a field of a structure/object) or globally (a global
    237273variable).
    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.
     274C++ uses this approach as its fallback system if exception handling fails,
     275such as \snake{std::terminate_handler} and, for a time,
     276\snake{std::unexpected_handler}.
     277
     278Handler functions work a lot like resumption exceptions,
     279but without the dynamic search for a handler.
     280Since setting up the handler can be more complex/expensive,
     281especially when the handler has to be passed through multiple layers of
     282function calls, but cheaper (constant time) to call,
     283they are more suited to more frequent (less exceptional) situations.
    247284\end{itemize}
    248285
    249286%\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.
     287Because of their cost, exceptions are rarely used for hot paths of execution.
     288Hence, there is an element of self-fulfilling prophecy as implementation
     289techniques have been focused on making them cheap to set-up,
     290happily making them expensive to use in exchange.
     291This difference is less important in higher-level scripting languages,
     292where using exception for other tasks is more common.
     293An iconic example is Python's \code{Python}{StopIteration} exception that
     294is thrown by an iterator to indicate that it is exhausted.
     295When paired with Python's iterator-based for-loop this will be thrown every
     296time the end of the loop is reached.
     297\todo{Cite Python StopIteration and for-each loop.}
    259298% https://docs.python.org/3/library/exceptions.html#StopIteration
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    rf42a6b8 rcb6b8cb  
    210210\lstMakeShortInline@
    211211\lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt}
    212 \lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
    213212% Annotations from Peter:
    214213\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
     
    246245\input{performance}
    247246\input{future}
     247\input{conclusion}
    248248
    249249%----------------------------------------------------------------------
Note: See TracChangeset for help on using the changeset viewer.