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

Timestamp:

Aug 29, 2021, 11:46:13 AM (3 years ago)

Author:

Andrew Beach <ajbeach@…>

Branches:

ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum

Children:

75f8e04

Parents:

1d402be (diff), cfbab07 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'andrew-mmath' into 'master', latest round of updates to the thesis.

File:

• doc/theses/andrew_beach_MMath/intro.tex (modified) (4 diffs)

doc/theses/andrew_beach_MMath/intro.tex

@@ -11 +11 @@
 
 % Now take a step back and explain what exceptions are generally.
+Exception handling provides dynamic inter-function control flow.
 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.
+components that construct, raise, propagate and handle exceptions,
+to provide all of that 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.
-% 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.
+% About other works:
+Often, when this separation is not made, termination exceptions are assumed
+as they are more common and may be the only form of handling provided in
+a language.
+
+All types of exception handling link a raise with a handler.
+Both operations are usually language primitives, although raises can be
+treated as a primitive function that takes an exception argument.
+Handlers are more complex as they are added to and removed from the stack
+during execution, must specify what they can handle and give the code to
+handle the exception.
+
+Exceptions work with different execution models but for the descriptions
+that follow a simple call stack, with functions added and removed in a
+first-in-last-out order, is assumed.
+
+Termination exception handling searches the stack for the handler, then
+unwinds the stack to where the handler was found before calling it.
+The handler is run inside the function that defined it and when it finishes
+it returns control to that 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.
+
+Resumption exception handling searches the stack for a handler and then calls
+it without removing any other stack frames.
+The handler is run on top of the existing stack, often as a new function or
+closure capturing the context in which the handler was defined.
+After the handler has finished running it returns control to the function
+that preformed the raise, usually starting after the raise.
 \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.
 
 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
+The classic example is error handling, exceptions can be used to
+remove error handling logic from the main execution path, and pay
 most of the cost only when the error actually occurs.
 
@@ -88 +66 @@
 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
@@ -107 +85 @@
 
 % 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,
+covering both changes to the compiler and the run-time.
+In addition, a suite of test cases and performance benchmarks were created
+along side the implementation.
+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.
-% 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 parts of the EHM use other features unique to \CFA and would be
+harder to replicate in other programming languages.
 
 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 creating new features.
+\item Implementing stack unwinding and the \CFA EHM, including updating
+the \CFA 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.
+\item Creating tests to check the behaviour of the EHM.
+\item Creating benchmarks to check the performances of the EHM,
+as compared to 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},
+The rest of this thesis is organized as follows.
+The current state of exceptions is covered in \autoref{s:background}.
+The existing state of \CFA is also covered in \autoref{c:existing}.
+New EHM features are introduced in \autoref{c:features},
 covering their usage and design.
 That is followed by the implementation of these 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}.
+Performance results are examined in \autoref{c:performance}.
+Possibilities to extend this project are discussed in \autoref{c:future}.
+Finally, the project is summarized in \autoref{c:conclusion}.
 
 \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}.
+Exception handling has been examined before in programming languages,
+with papers on the subject dating back 70s.\cite{Goodenough75}
 Early exceptions were often treated as signals, which carried no information
-except their identity. Ada~\cite{Ada} still uses this system.
+except their identity. Ada still uses this system.\todo{cite Ada}
 
 The modern flag-ship for termination exceptions is \Cpp,
 which added them in its first major wave of non-object-orientated features
 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
+\todo{cite https://en.cppreference.com/w/cpp/language/history}
+Many EHMs have special exception types,
+however \Cpp has the ability to use any type as an exception.
+These were found to be not very useful and have been pushed aside for classes
+inheriting 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
+Although there is a special catch-all syntax (@catch(...)@) there are no
+operations that can be performed on the caught value, not even type inspection.
+Instead the base exception-type \code{C++}{std::exception} defines common
+functionality (such as
+the ability to describe the reason the exception was raised) 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}
+That trade-off, restricting usable types to gain guaranteed functionality,
+is almost universal now, as without some common functionality it is almost
+impossible to actually handle any errors.
+
+Java was the next popular language to use exceptions. \todo{cite Java}
+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
-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.
+Checked exceptions are part of a function's interface,
+the exception signature of the function.
+Every function that could be raised from a function, either directly or
+because it is not handled from a called function, is given.
+Using this information, it is possible to statically verify if any given
+exception is handled and guarantee that no exception will go unhandled.
+Making exception information explicit improves clarity and safety,
+but can slow down or restrict programming.
+For example, programming high-order functions becomes much more complex
+if the argument functions could raise exceptions.
+However, as odd it may seem, the worst problems are rooted in the simple
+inconvenience of writing and updating exception signatures.
+This has caused Java programmers to develop multiple programming ``hacks''
+to circumvent checked exceptions, negating their advantages.
+One particularly problematic example is the ``catch-and-ignore'' pattern,
+where an empty handler is used to handle an exception without doing any
+recovery or repair. In theory that could be good enough to properly handle
+the exception, but more often is used to ignore an exception that the       
+programmer does not feel is worth the effort of handling it, for instance if
+they do not believe it will ever be raised.
+If they are incorrect the exception will be silenced, while in a similar
+situation with unchecked exceptions the exception would at least activate    
+the language's unhandled exception code (usually program abort with an  
+error message).
 
 %\subsection
 Resumption exceptions are less popular,
-although resumption is as old as termination;
-hence, few
+although resumption is as old as termination; hence, 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 language that did.\todo{cite Mesa} Experience 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 main-stream programming languages.
+However, resumption is being revisited in the context of decades of other
+developments in programming languages.
+While rejecting resumption may have been the right decision in the past,
+the situation has changed since then.
+Some developments, such as the function programming equivalent to resumptions,
+algebraic effects\cite{Zhang19}, are enjoying success.
+A complete reexamination of resumptions is beyond this thesis,
+but there reemergence is enough to try them 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.
-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.
+% termination exceptions and how much Peter likes them.
+
+%\subsection
+Functional languages tend to use other solutions for their primary error
+handling mechanism, but exception-like constructs still appear.
+Termination appears in the error construct, which marks the result of an
+expression as an error; then the result of any expression that tries to use
+it also results in an error, and so on until an appropriate handler is reached.
 Resumption appears in algebraic 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
-unwinding the stack like in termination exception handling.
+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.\todo{cite Rust}
 % 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.
+the cost of flexibility.\todo{cite Go}
 
 %\subsection
 While exception handling's most common use cases are in error handling,
-here are other ways to handle errors with comparisons to exceptions.
+here are some other ways to handle errors with 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,
+This pattern has a function return an enumeration (or just a set of fixed
+values) to indicate if an error has occurred and possibly which error it was.
+
+Error codes mix exceptional/error and normal values, enlarging the range of
+possible return values. This can be addressed with multiple return values
+(or a tuple) or a tagged union.
+However, the main issue with error codes is forgetting to check 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..
+Some new languages and tools will try to issue warnings when an error code
+is discarded to avoid this problem.
+Checking error codes also bloats the main execution path,
+especially if the error is not handled immediately hand has to be passed
+through multiple functions before it is addressed.
 
 \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.
+Similar to the error codes pattern but the function itself only returns
+that there was an error
+and store the reason for the error in a fixed global location.
+For example many routines in the C standard library will only return some
+error value (such as -1 or a null pointer) and the error code is written into
+the standard variable @errno@.
+
+This approach avoids the multiple results issue encountered with straight
+error codes but otherwise has the same disadvantages and more.
+Every function that reads or writes to the global store must agree on all
+possible errors and managing it becomes more complex with concurrency.
 
 \item\emph{Return Union}:
@@ -254 +255 @@
 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).
-% We need listing Rust/rust to format code snipits from it.
+This pattern is very popular in any functional or semi-functional language
+with primitive support for tagged unions (or algebraic data types).
+% We need listing Rust/rust to format code snippets 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 advantage is that an arbitrary object can be used to represent an
+error so it can include a lot more information than a simple error code.
+The disadvantages include that the it does have to be checked along the main
+execution and if there aren't primitive tagged unions proper usage can be
+hard to enforce.
 
 \item\emph{Handler Functions}:
-This pattern implicitly associates functions with errors.
-On error, the function that produced the error implicitly calls another function to
+This pattern associates errors with functions.
+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
-\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.
+C++ uses this approach as its fallback system if exception handling fails,
+such as \snake{std::terminate_handler} and, for a time,
+\snake{std::unexpected_handler}.
+
+Handler functions work a lot like resumption exceptions,
+but without the dynamic search for a handler.
+Since setting up the handler can be more complex/expensive,
+especially when the handler has to be passed through multiple layers of
+function calls, but cheaper (constant time) to call,
+they are more suited to more frequent (less exceptional) situations.
 \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.
+Hence, there is an element of self-fulfilling prophecy as implementation
+techniques have been focused on making them cheap to set-up,
+happily making them expensive to use in exchange.
+This difference is less important in higher-level scripting languages,
+where using exception for other tasks is more common.
+An iconic example is Python's \code{Python}{StopIteration} exception that
+is thrown by an iterator to indicate that it is exhausted.
+When paired with Python's iterator-based for-loop this will be thrown every
+time the end of the loop is reached.
+\todo{Cite Python StopIteration and for-each loop.}
 % https://docs.python.org/3/library/exceptions.html#StopIteration