\section{Continuations and Exceptions\hfill\fbox{25 Points}}

After learning the degree of control that continuations give us over
the control stack, it should come as no surprise to learn that we
can simulate the functionality of failures and handlers using continuations.

Consider the (H, K, e) machine introduced in class.  The handler stack is
just a list of ``frozen'' stack frames with handlers.

In Standard ML we can define such a handler stack as a mutable list of
unit continuations:

\begin{code}
val H = ref ([] : unit cont list)
\end{code}

You are asked to define two functions, {\tt tryow} and {\tt fail} that
will allow us the functionality of failures and handlers in Standard ML
without using the exception mechanism.

\begin{code}
tryow : (unit -> 'a) -> (unit -> 'a) -> 'a

fail : unit -> 'a
\end{code}

A function of type {\tt (unit -> 'a)} we call a ``thunk'' as it represents an
unexecuted SML expression (if we simply passed values of type {\tt 'a} to
{\tt tryow} there would obviously be no chance to grab the continuations
we'll need in order to implement failures and error handling.

The semantics of {\tt tryow} is such that {\tt tryow f1 f2} evaluates to
the result of calling {\tt f1} on {\tt ()} {\em unless} a {\tt fail ()} is
called during this execution, in which case {\tt tryow f1 f2} evaluates to
the result of evaluating {\tt f2 ()}.

More formally, the semantics should match that of the (H, K, e) machine
defined in class (with the appropriate translations to SML syntax rather than
\MinML{}).

As an example, if we define:
\begin{code}
fun x () = (print "fail x\\n"; fail ())

fun y () = tryow x (fn () => (print "fail y\\n"; fail ()));

fun z () = tryow y (fn () => (print "return 13\\n"; 13));
\end{code}

Then at toplevel we should be able to say:
\begin{code}
- tryow x z;
fail x
fail x
fail y
return 13
val it = 13 : int
- tryow z x;
fail x
fail y
return 13
val it = 13 : int
\end{code}

\begin{enumerate}
\item  Part 1 (10 points).

Define {\tt fail}:

(Remember to perform any ``tidying up'' that needs to be done to {\tt H}.)
Your {\tt fail} should raise an exception Uncaught if no handlers are
pending on the stack.

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip

\item Part 2 (15 points).

Define {\tt tryow}:

Again, make sure that {\tt H} is always in it's proper state; maintain as
an invariant that the head of {\tt !H} is the pending handler (the second
argument of some {\tt tryow} statement).

\end{enumerate}

\ifsoln

\clearpage

\begin{enumerate}
\item Answer 1.

\begin{code}
fun fail () =
  case H of
    ref (h::t) => (H := t;
		   throw h ())
  | \_ => raise Uncaught
\end{code}

\item Answer 2.

\begin{code}

fun tryow (f1 : unit -> 'a) (f2 : unit -> 'a) : 'a =
  (callcc (fn answer =>
	   (callcc (fn unitc =>
		    throw answer
		    (f2 (callcc (fn handler =>
				 (H := handler :: (!H);
				  throw unitc ())))));
	    (f1 ()) before (H := (tl (!H))))))
\end{code}

\end{enumerate}
