Changeset 5541ea3d for doc/theses/andrew_beach_MMath/intro.tex

Timestamp:

Aug 4, 2021, 2:40:11 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

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

Children:

199894e

Parents:

0640189e (diff), df5b2c8 (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 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

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

doc/theses/andrew_beach_MMath/intro.tex

@@ -2 +2 @@
 
 % The highest level overview of Cforall and EHMs. Get this done right away.
-This thesis goes over the design and implementation of the exception handling
+This thesis covers 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, that maintains
+\CFA is a new programming language that extends C, which maintains
 backwards-compatibility while introducing modern programming features.
 Adding exception handling to \CFA gives it new ways to handle errors and
-make other large control-flow jumps.
+make 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
-This seperation is uncommon because termination exception handling is so
-much more common that it is often assumed.
+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?
-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.
+
+Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
 \begin{center}
-\input{callreturn}
+\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}
 \end{center}
-
-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.}
+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.
 
 Although a powerful feature, exception handling tends to be complex to set up
 and expensive to use
-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
+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
 most of the cost only when the error actually occurs.
 
@@ -49 +88 @@
 some of the underlying tools used to implement and express exception handling
 in other languages are absent in \CFA.
-Still the resulting syntax resembles that of other languages:
-\begin{cfa}
-try {
+Still the resulting basic syntax resembles that of other languages:
+\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
+@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{cfa}
-
+\end{lstlisting}
 % A note that yes, that was a very fast overview.
 The design and implementation of all of \CFA's EHM's features are
@@ -69 +107 @@
 
 % The current state of the project and what it contributes.
-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
+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
 languages and much of the design is as well.
-Some parts of the EHM use other features unique to \CFA and these would be
-harder to replicate in other programming languages.
-
+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.
-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.
+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.
 
 The contributions of this work are:
 \begin{enumerate}
 \item Designing \CFA's exception handling mechanism, adapting designs from
-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.
+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.
 % 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 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
+%\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
 \autoref{c:implement}.
-The performance results are examined in \autoref{c:performance}.
-Possibilities to extend this project are discussed in \autoref{c:future}.
+Performance results are presented in \autoref{c:performance}.
+Summing up and possibilities for extending this project are discussed in \autoref{c:future}.
 
 \section{Background}
 \label{s:background}
 
-Exception handling is not a new concept,
-with papers on the subject dating back 70s.
-
-Their were popularised by \Cpp,
+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.
+
+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
-
-Java was the next popular language to use exceptions. It is also the most
-popular language with checked exceptions.
-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
+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
+\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}
+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.
-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 implement them.
+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
+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 is one programming languages that did and experiance with that
-languages is quoted as being one of the reasons resumptions were not
+Mesa~\cite{Mesa} is one programming languages that did. Experience with Mesa
+is quoted as being one of the reasons resumptions are not
 included in the \Cpp standard.
 % https://en.wikipedia.org/wiki/Exception_handling
-\todo{A comment about why we did include them when they are so unpopular
-might be approprate.}
-
-%\subsection
-Functional languages, tend to use solutions like the return union, but some
-exception-like constructs still appear.
-
-For instance Haskell's built in error mechanism can make the result of any
-expression, including function calls. Any expression that examines an
-error value will in-turn produce an error. This continues until the main
-function produces an error or until it is handled by one of the catch
-functions.
-
-%\subsection
-More recently exceptions seem to be vanishing from newer programming
-languages.
-Rust and Go reduce this feature to panics.
-Panicing is somewhere between a termination exception and a program abort.
-Notably in Rust a panic can trigger either, a panic may unwind the stack or
-simply kill the process.
+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.
+% 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.
+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.
 % https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
-Go's panic is much more similar to a termination exception but there is
-only a catch-all function with \code{Go}{recover()}.
-So exceptions still are appearing, just in reduced forms.
-
-%\subsection
-Exception handling's most common use cases are in error handling.
-Here are some other ways to handle errors and comparisons with exceptions.
+In Go~\cite{Go}, a panic 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.
 \begin{itemize}
 \item\emph{Error Codes}:
-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.
+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..
+
 \item\emph{Special Return with Global Store}:
-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.
+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.
+
 \item\emph{Return Union}:
-Replaces error codes with a tagged union.
+This pattern 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
@@ -196 +254 @@
 so that one type can be used everywhere in error handling code.
 
-This pattern is very popular in functional or semi-functional language,
-anything with primitive support for tagged unions (or algebraic data types).
+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.
 % Rust's \code{rust}{Result<T, E>}
-
-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.
+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.
+
 \item\emph{Handler Functions}:
-On error the function that produced the error calls another function to
+This pattern implicitly associates functions with errors.
+On error, the function that produced the error implicitly 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 as its fallback system if exception handling fails.
+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.
-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.
+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.
 \end{itemize}
 
 %\subsection
-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.
+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.
 % https://docs.python.org/3/library/exceptions.html#StopIteration