Context Navigation

-                      r5438e41
+                      rf42a6b8
 % The highest level overview of Cforall and EHMs. Get this done right away.
 This thesis covers the design and implementation of the exception handling
+This thesis goes over the design and implementation of the exception handling
 mechanism (EHM) of
 \CFA (pronounced sea-for-all and may be written Cforall or CFA).
 \CFA is a new programming language that extends C, which maintains
+\CFA is a new programming language that extends C, that maintains
 backwards-compatibility while introducing modern programming features.
 Adding exception handling to \CFA gives it new ways to handle errors and
 make large control-flow jumps.
+make other large control-flow jumps.
 % Now take a step back and explain what exceptions are generally.
-A language's EHM is a combination of language syntax and run-time
-components that are used to construct, raise, and handle exceptions,
-including all control flow.
-Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
 Exception handling provides dynamic inter-function control flow.
 There are two forms of exception handling covered in this thesis:
 termination, which acts as a multi-level return,
 and resumption, which is a dynamic function call.
-% PAB: Maybe this sentence was suppose to be deleted?
 Termination handling is much more common,
+to the extent that it is often seen as the only form of handling.
+% PAB: I like this sentence better than the next sentence.
+% This separation is uncommon because termination exception handling is so
+% much more common that it is often assumed.
+to the extent that it is often seen
+This seperation is uncommon because termination exception handling is so
+much more common that it is often assumed.
 % WHY: Mention other forms of continuation and \cite{CommonLisp} here?
+Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
+A language's EHM is the combination of language syntax and run-time
+components that are used to construct, raise and handle exceptions,
+including all control flow.
+Termination exception handling allows control to return to any previous
+function on the stack directly, skipping any functions between it and the
+current function.
 \begin{center}
+\begin{tabular}[t]{ll}
+\begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
+void f( void (*hp)() ) {
+        hp();
+}
+void g( void (*hp)() ) {
+        f( hp );
+}
+void h( int @i@, void (*hp)() ) {
+        void @handler@() { // nested
+                printf( "%d\n", @i@ );
+        }
+        if ( i == 1 ) hp = handler;
+        if ( i > 0 ) h( i - 1, hp );
+        else g( hp );
+}
+h( 2, 0 );
+\end{lstlisting}
+&
+\raisebox{-0.5\totalheight}{\input{handler}}
+\end{tabular}
+\input{callreturn}
 \end{center}
+The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
+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.
+Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
+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.
+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.
+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.
+\begin{center}
+\input{termination}
+\end{center}
+Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
+After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
+Unwinding allows recover to any previous
+function on the stack, skipping any functions between it and the
+function containing the matching handler.
+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.
+\begin{center}
+\input{resumption}
+\end{center}
+After the handler returns, control continues after the resume in @f@ (dynamic return).
+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.
+Resumption exception handling seaches the stack for a handler and then calls
+it without adding or removing any other stack frames.
+\todo{Add a diagram showing control flow for resumption.}
 Although a powerful feature, exception handling tends to be complex to set up
 and expensive to use
 so it is often limited to unusual or ``exceptional" cases.
 The classic example is error handling, where exceptions are used to
 remove error handling logic from the main execution path, while paying
+so they are often limited to unusual or ``exceptional" cases.
+The classic example of this is error handling, exceptions can be used to
+remove error handling logic from the main execution path and while paying
 most of the cost only when the error actually occurs.
 …
 some of the underlying tools used to implement and express exception handling
 in other languages are absent in \CFA.
 Still the resulting basic syntax resembles that of other languages:
 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
 @try@ {
+Still the resulting syntax resembles that of other languages:
+\begin{cfa}
+try {
         ...
         T * object = malloc(request_size);
         if (!object) {
                 @throw@ OutOfMemory{fixed_allocation, request_size};
+                throw OutOfMemory{fixed_allocation, request_size};
+        }
         ...
 } @catch@ (OutOfMemory * error) {
+} catch (OutOfMemory * error) {
         ...
+}
+\end{lstlisting}
+\end{cfa}
 % A note that yes, that was a very fast overview.
 The design and implementation of all of \CFA's EHM's features are
 …
 % The current state of the project and what it contributes.
+The majority of the \CFA EHM is implemented in \CFA, except for a small amount of assembler code.
+In addition,
+a suite of tests and performance benchmarks were created as part of this project.
+The \CFA implementation techniques are generally applicable in other programming
+All of these features have been implemented in \CFA, along with
+a suite of test cases as part of this project.
+The implementation techniques are generally applicable in other programming
 languages and much of the design is as well.
+Some parts of the EHM use features unique to \CFA, and hence,
+are harder to replicate in other programming languages.
+Some parts of the EHM use other features unique to \CFA and these would be
+harder to replicate in other programming languages.
 % Talk about other programming languages.
+Three well known programming languages with EHMs, %/exception handling
+C++, Java and Python are examined in the performance work. However, these languages focus on termination
+exceptions, so there is no comparison with resumption.
+Some existing programming languages that include EHMs/exception handling
+include C++, Java and Python. All three examples focus on termination
+exceptions which unwind the stack as part of the
+Exceptions also can replace return codes and return unions.
 The contributions of this work are:
 \begin{enumerate}
 \item Designing \CFA's exception handling mechanism, adapting designs from
 other programming languages, and creating new features.
 \item Implementing stack unwinding for the \CFA EHM, including updating
 the \CFA compiler and run-time environment to generate and execute the EHM code.
 \item Designing and implementing a prototype virtual system.
+other programming languages and the creation of new features.
+\item Implementing stack unwinding and the EHM in \CFA, including updating
+the compiler and the run-time environment.
+\item Designed and implemented a prototype virtual system.
 % I think the virtual system and per-call site default handlers are the only
 % "new" features, everything else is a matter of implementation.
-\item Creating tests and performance benchmarks to compare with EHM's in other languages.
 \end{enumerate}
 %\todo{I can't figure out a good lead-in to the roadmap.}
 The thesis is organization as follows.
 The next section and parts of \autoref{c:existing} cover existing EHMs.
 New \CFA EHM features are introduced in \autoref{c:features},
 covering their usage and design.
 That is followed by the implementation of these features in
+\todo{I can't figure out a good lead-in to the roadmap.}
+The next section covers the existing state of exceptions.
+The existing state of \CFA is also covered in \autoref{c:existing}.
+The new features are introduced in \autoref{c:features},
+which explains their usage and design.
+That is followed by the implementation of those features in
 \autoref{c:implement}.
 Performance results are presented in \autoref{c:performance}.
 Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
+The performance results are examined in \autoref{c:performance}.
+Possibilities to extend this project are discussed in \autoref{c:future}.
 \section{Background}
 \label{s:background}
+Exception handling is a well examined area in programming languages,
+with papers on the subject dating back the 70s~\cite{Goodenough75}.
+Early exceptions were often treated as signals, which carried no information
+except their identity. Ada~\cite{Ada} still uses this system.
+Exception handling is not a new concept,
+with papers on the subject dating back 70s.\cite{Goodenough}
+Early exceptions were often treated as signals. They carried no information
+except their identity. Ada still uses this system.
 The modern flag-ship for termination exceptions is \Cpp,
 …
 in 1990.
 % https://en.cppreference.com/w/cpp/language/history
+While many EHMs have special exception types,
+\Cpp has the ability to use any type as an exception.
+However, this generality is not particularly useful, and has been pushed aside for classes, with a convention of inheriting from
+\Cpp has the ability to use any value of any type as an exception.
+However that seems to immediately pushed aside for classes inherited from
 \code{C++}{std::exception}.
+While \Cpp has a special catch-all syntax @catch(...)@, there is no way to discriminate its exception type, so nothing can
 be done with the caught value because nothing is known about it.
 Instead the base exception-type \code{C++}{std::exception} is defined with common functionality (such as
 the ability to print a message when the exception is raised but not caught) and all
 exceptions have this functionality.
 Having a root exception-type seems to be the standard now, as the guaranteed functionality is worth
 any lost in flexibility from limiting exceptions types to classes.
 Java~\cite{Java} was the next popular language to use exceptions.
 Its exception system largely reflects that of \Cpp, except it requires
 exceptions to be a subtype of \code{Java}{java.lang.Throwable}
+Although there is a special catch-all syntax it does not allow anything to
+be done with the caught value becuase nothing is known about it.
+So instead a base type is defined with some common functionality (such as
+the ability to describe the reason the exception was raised) and all
+exceptions have that functionality.
+This seems to be the standard now, as the garentied functionality is worth
+any lost flexibility from limiting it to a single type.
+Java was the next popular language to use exceptions.
+Its exception system largely reflects that of \Cpp, except that requires
+you throw a child type of \code{Java}{java.lang.Throwable}
 and it uses checked exceptions.
+Checked exceptions are part of a function's interface defining all exceptions it or its called functions raise.
+Using this information, it is possible to statically verify if a handler exists for all raised exception, \ie no uncaught exceptions.
+Making exception information explicit, improves clarity and
+Checked exceptions are part of the function interface they are raised from.
+This includes functions they propogate through, until a handler for that
+type of exception is found.
+This makes exception information explicit, which can improve clarity and
 safety, but can slow down programming.
+For example, programming complexity increases when dealing with high-order methods or an overly specified
+throws clause. However some of the issues are more
+programming annoyances, such as writing/updating many exception signatures after adding or remove calls.
+Java programmers have developed multiple programming ``hacks'' to circumvent checked exceptions negating the robustness it is suppose to provide.
+For example, the ``catch-and-ignore" pattern, where the handler is empty because the exception does not appear relevant to the programmer versus
+repairing or recovering from the exception.
+%\subsection
+Resumption exceptions are less popular,
+although resumption is as old as termination;
+hence, few
+Some of these, such as dealing with high-order methods or an overly specified
+throws clause, are technical. However some of the issues are much more
+human, in that writing/updating all the exception signatures can be enough
+of a burden people will hack the system to avoid them.
+Including the ``catch-and-ignore" pattern where a catch block is used without
+anything to repair or recover from the exception.
+%\subsection
+Resumption exceptions have been much less popular.
+Although resumption has a history as old as termination's, very few
 programming languages have implemented them.
 % http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
 %   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
 Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
 is quoted as being one of the reasons resumptions are not
+Mesa is one programming languages that did. Experiance with Mesa
+is quoted as being one of the reasons resumptions were not
 included in the \Cpp standard.
 % https://en.wikipedia.org/wiki/Exception_handling
+As a result, resumption has ignored in main-stream programming languages.
+However, ``what goes around comes around'' and resumption is being revisited now (like user-level threading).
+While rejecting resumption might have been the right decision in the past, there are decades
+of developments in computer science that have changed the situation.
+Some of these developments, such as functional programming's resumption
+equivalent, algebraic effects\cite{Zhang19}, are enjoying significant success.
+A complete reexamination of resumptions is beyond this thesis, but their re-emergence is
+enough to try them in \CFA.
+Since then resumptions have been ignored in the main-stream.
+All of this does call into question the use of resumptions, is
+something largely rejected decades ago worth revisiting now?
+Yes, even if it was the right call at the time there have been decades
+of other developments in computer science that have changed the situation
+since then.
+Some of these developments, such as in functional programming's resumption
+equivalent: algebraic effects\cite{Zhang19}, are directly related to
+resumptions as well.
+A complete rexamination of resumptions is beyond a single paper, but it is
+enough to try them again in \CFA.
 % Especially considering how much easier they are to implement than
 % termination exceptions.
 %\subsection
 Functional languages tend to use other solutions for their primary EHM,
 but exception-like constructs still appear.
+Functional languages tend to use other solutions for their primary error
+handling mechanism, exception-like constructs still appear.
 Termination appears in error construct, which marks the result of an
 expression as an error; thereafter, the result of any expression that tries to use it is also an
 error, and so on until an appropriate handler is reached.
 Resumption appears in algebraic effects, where a function dispatches its
+expression as an error, the result of any expression that tries to use it as
+an error, and so on until an approprate handler is reached.
+Resumption appears in algebric effects, where a function dispatches its
 side-effects to its caller for handling.
 %\subsection
+Some programming languages have moved to a restricted kind of EHM
 called ``panic".
 In Rust~\cite{Rust}, a panic is just a program level abort that may be implemented by
+More recently exceptions seem to be vanishing from newer programming
+languages, replaced by ``panic".
+In Rust a panic is just a program level abort that may be implemented by
 unwinding the stack like in termination exception handling.
 % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
 In Go~\cite{Go}, a panic is very similar to a termination, except it only supports
+Go's panic through is very similar to a termination except it only supports
 a catch-all by calling \code{Go}{recover()}, simplifying the interface at
 the cost of flexibility.
 %\subsection
+While exception handling's most common use cases are in error handling,
 here are other ways to handle errors with comparisons to exceptions.
+the cost of flexability.
+%\subsection
+Exception handling's most common use cases are in error handling.
+Here are some other ways to handle errors and comparisons with exceptions.
 \begin{itemize}
 \item\emph{Error Codes}:
+This pattern has a function return an enumeration (or just a set of fixed values) to indicate
+if an error occurred and possibly which error it was.
+Error codes mix exceptional and normal values, artificially enlarging the type and/or value range.
+Some languages address this issue by returning multiple values or a tuple, separating the error code from the function result.
+However, the main issue with error codes is forgetting to checking them,
+which leads to an error being quietly and implicitly ignored.
+Some new languages have tools that issue warnings, if the error code is
+discarded to avoid this problem.
+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..
+This pattern uses an enumeration (or just a set of fixed values) to indicate
+that an error has occured and which error it was.
+There are some issues if a function wants to return an error code and another
+value. The main issue is that it can be easy to forget checking the error
+code, which can lead to an error being quitely and implicitly ignored.
+Some new languages have tools that raise warnings if the return value is
+discarded to avoid this.
+It also puts more code on the main execution path.
 \item\emph{Special Return with Global Store}:
+Some functions only return a boolean indicating success or failure
+and store the exact reason for the error in a fixed global location.
+For example, many C routines return non-zero or -1, indicating success or failure,
+and write error details into the C standard variable @errno@.
+This approach avoids the multiple results issue encountered with straight error codes
+but otherwise has many (if not more) of the disadvantages.
+For example, everything that uses the global location must agree on all possible errors and global variable are unsafe with concurrency.
+A function that encounters an error returns some value indicating that it
+encountered a value but store which error occured in a fixed global location.
+Perhaps the C standard @errno@ is the most famous example of this,
+where some standard library functions will return some non-value (often a
+NULL pointer) and set @errno@.
+This avoids the multiple results issue encountered with straight error codes
+but otherwise many of the same advantages and disadvantages.
+It does however introduce one other major disadvantage:
+Everything that uses that global location must agree on all possible errors.
 \item\emph{Return Union}:
 This pattern replaces error codes with a tagged union.
+Replaces error codes with a tagged union.
 Success is one tag and the errors are another.
 It is also possible to make each possible error its own tag and carry its own
 …
 so that one type can be used everywhere in error handling code.
 This pattern is very popular in functional or any semi-functional language with
 primitive support for tagged unions (or algebraic data types).
+This pattern is very popular in functional or semi-functional language,
+anything with primitive support for tagged unions (or algebraic data types).
 % We need listing Rust/rust to format code snipits from it.
 % Rust's \code{rust}{Result<T, E>}
+The main advantage is providing for more information about an
 error, other than one of a fix-set of ids.
+While some languages use checked union access to force error-code checking,
 it is still possible to bypass the checking.
 The main disadvantage is again significant error code on the main execution path and cascading through called functions.
+The main disadvantage is again it puts code on the main execution path.
+This is also the first technique that allows for more information about an
+error, other than one of a fix-set of ids, to be sent.
+They can be missed but some languages can force that they are checked.
+It is also implicitly forced in any languages with checked union access.
 \item\emph{Handler Functions}:
+This pattern implicitly associates functions with errors.
+On error, the function that produced the error implicitly calls another function to
+On error the function that produced the error calls another function to
 handle it.
 The handler function can be provided locally (passed in as an argument,
 either directly as as a field of a structure/object) or globally (a global
 variable).
+C++ uses this approach as its fallback system if exception handling fails, \eg
+C++ uses this as its fallback system if exception handling fails.
 \snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
 Handler functions work a lot like resumption exceptions, without the dynamic handler search.
 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,
 are more suited to frequent exceptional situations.
 % The exception being global handlers if they are rarely change as the time
 % in both cases shrinks towards zero.
+Handler functions work a lot like resumption exceptions.
+The difference is they are more expencive to set up but cheaper to use, and
+so are more suited to more fequent errors.
+The exception being global handlers if they are rarely change as the time
+in both cases strinks towards zero.
 \end{itemize}
 %\subsection
+Because of their cost, exceptions are rarely used for hot paths of execution.
+Therefore, there is an element of self-fulfilling prophecy for implementation
+techniques to make exceptions cheap to set-up at the cost
+of expensive usage.
+This cost differential is less important in higher-level scripting languages, where use of exceptions for other tasks is more common.
+An iconic example is Python's @StopIteration@ exception that is thrown by
+an iterator to indicate that it is exhausted, especially when combined with Python's heavy
+use of the iterator-based for-loop.
+Because of their cost exceptions are rarely used for hot paths of execution.
+There is an element of self-fulfilling prophocy here as implementation
+techniques have been designed to make exceptions cheap to set-up at the cost
+of making them expencive to use.
+Still, use of exceptions for other tasks is more common in higher-level
+scripting languages.
+An iconic example is Python's StopIteration exception which is thrown by
+an iterator to indicate that it is exausted. Combined with Python's heavy
+use of the iterator based for-loop.
 % https://docs.python.org/3/library/exceptions.html#StopIteration

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset f42a6b8 for doc/theses/andrew_beach_MMath/intro.tex

Legend:

doc/theses/andrew_beach_MMath/intro.tex

Download in other formats: