By Brandon Wu, June 2020
So far, we have seen how we can manipulate the constructs of SML to create unique control flow behavior in the form of continuation passing style. In this section, we will discuss exceptions, which are themselves a builtin feature of the language. With exceptions, we can cover cases where continuing to evaluate an exprerssion does not make sense or is ill-defined at run-time.
We have seen how SML interprets computation as evaluation, and how we can reduce our entire notion of program execution to application of simple reduction rules. Sometimes, however, we run into cases where attempting to apply some rule results in an error, or in some output that we cannot actually express. In such cases, it is necessary to actually halt evaluation with some manner of effect - this is the behavior that exceptions will introduce.
While we would like to be able to push as many of these errors as possible to compile time, it is not always the case that this is possible - this is usually when dealing with cases where computation is made infeasible by the values that are bound to identifiers, which cannot be determined a priori at compile time. As such, we have no way of telling beforehand if such errors will occur - forcing us to define some notion of a run-time error.
You have likely already encountered exceptions - the canonical example is of
1 div 0, which, when entered in the REPL, will result in an
uncaught exception Div. This is because we cannot sensically evaluate
1 div 0 to some value -
what integer could we possibly return? The other option, then, is to simply
quit, and not even try to evaluate further. This is why division by zero results
in an exception.
Another example is of the declaration
val x::xs = . This signifies an
attempt at pattern matching, where we attempt to pattern match
Plainly, however, we cannot possibly carry this out - what values could we bind
xs to make this valid? Thus, we will also need to have some
exception for an incorrect binding - which is appropriately named as the
Finally, in general we are interested in writing functions that are exhaustive, in that they are defined on all values of their input type. Even if a function is only meant to be called on values within a certain domain, it is often a good idea to be safe and cover all of the cases anyways. We call such a function that is not defined on certain inputs nonexhaustive, and defining them will generally result in a non-exhaustive match warning, though it will still be permitted.
Consider the function
fn true => 1, which is plainly nonexhaustive, not
false case. Nonetheless, it is a function of type
bool -> int
that can be bound to an identifier. How, then, should we handle the case of
attempting to evaluate
(fn true => 1) false? This is a well-typed expression,
causing it to fly under the radar of our compile-time tests. At run-time, then,
we cannot evaluate this expression through function application - the function
does not specify what it should return in this case! As such, we will simply
Match exception, signifying that the function's input was not able to
match to any particular clause of the function. Note how this differs from
Bind, which occurs as a result of attempting to produce a binding, not when
attempting to apply a function.
We have now seen the built-in exceptions that are automatically raised for
certain prescribed use cases. Oftentimes, however, we are interested in our own
specified use cases, meaning that we likely do not want to use the exceptions
Bind, which may be unrelated. In this case, we want to
define our own exceptions.
The syntax for defining exceptions is as follows:
This introduces the constructor named Error, which corresponds to the
identically named exception Error. Exception constructors are first class,
meaning that they are themselves values. The type of exception constructors is
exn, so this line really introduces the value
Error : exn. The type
stands for "exception name", but it is also useful to think of it as standing
for "extensible", since the type
exn is extensible. This means that we
can extend the values that populate
exn with new constructors, like we did
Error is not, by itself, an exception, however we can use it to
raise exceptions with the
raise keyword. We can think of the
as being "like" a function of type
exn -> 'a, in that it "takes in" a value of
exn and has type
'a. It is important to remember that
raise is not
a function really, though - it merely has similar behavior when used to raise
exceptions, but it is not first class.
The polymorphic "return type" of the
raise keyword is so that raising
exceptions can be compatible with our type system. Suppose we want to write a
factorial function that, instead of looping forever on negative inputs, raises
exception Negative fun fact' 0 = 1 | fact' n = if n < 0 then raise Negative else n * fact' (n-1)
This code fragment should carry out our desired behavior. Consider the type of
raise Negative - we would like to raise an exception, but we know that the
expressions in both branches of an if then else expression must be the same
type. In the positive case, this has type
int, corresponding to just
calculating the actual factorial. Therefore the negative case must also be
int, though we also want to raise an exception. To be compatible with this,
raise Negative must have type
We would not like
raise Negative to have type
int in general, however -
this depends on our use case! We want raising exceptions to be able to just
work, type-wise, since we know that it never returns a well-defined value anyways.
As such, we define raising exceptions to have a polymorphic return type, so that
it fits within our type system correctly, no matter the use case. This is also
the reason why we can write
raise Fail "Unimplemented" as the output of
not-yet defined functions and still pass typechecking, no matter how complicated
At this point, we have seen how exceptions let us implement a very limited form
of "control flow", in that we can stop the flow of control entirely - upon
encountering a raised exception, computation ceases. This is rather rudimentary
in terms of expressiveness - we can only create programs that forcibly
terminate! In this section, however, we will explore the usage of
keyword that allows us to have more sophisticated behavior with respect to
programs deal with raised exceptions.
[handle] For expressions
e : t,
e1 : t...
en : t, and different values
Exn1 : exn...
ExnN : exn, if the expression
eraises the exception
ExnI, then the expression
e handle Exn2 => e1 | Exn2 => e3 ... | ExnN => en
In other words, the
handlekeyword lets us case on the exception raised by an expression.
It is important to note that all the expressions
en have to be
of the same type. Consider what would happen if they were not:
e handle Div => "Oh no!"
e be an expression of type
int. Suppose that, in this case,
so ostensibly this expression should reduce to
"Oh no!". However, what would happen
Div was not raised? Then, we would have
e, which is of type
We've violated type safety here. We cannot "sometimes" have an expression be one
type and another time have it be another. We must have static type guarantees.
As such, all the arms of a
handle must agree, and additionally they must agree
with the type of the expression being handled.
We say that an exception that is raised can either propagate up to the top
level (in which case the program or expression simply results in an uncaught
exception), or to the nearest handler. To clarify the meaning of "nearest",
take the evaluation of the expression
(1 + (1 div 0)) * 3 handle Div => 5, for
example. We see that
1 div 0 raises the exception
Div, so the inner
expression is extensionally equivalent to
(1 + raise Div) * 3. Then, applying
this logic one more time,
1 + raise Div clearly should also raise
Div, so we
get that it is extensionally equivalent to
raise Div * 3, which is then
extensionally equivalent to
raise Div. What we see is that this raised
exception "propagates up" as it subsumes more and more expressions, until
eventually it reaches a handler.
While we now see how we can handle different kinds of exceptions, we might want to make a more educated choice about what our next action should be. It might be the case that we raise an exception in some failed branch of the program, but we want to have more information about exactly what happened, or what the program was doing at the time. We will now discuss information-carrying exceptions, which are nothing other than an extension of our declarations of exceptions to being more akin to how we declare datatypes.
In a similar vein to how we can declare
datatype Foo = Bar of int to denote
that a value of type
Foo is the constructor
Bar wrapping a value of type
int, we can declare values of type
exn to also be constructors wrapping
values. This takes the form:
exception Crash of int
which denotes that
Crash 1 and
Crash 5, among others, are values of type
exn, and can thus be
raised. Note that
Crash thus has type
int -> exn.
Concretely, we can "pattern match" on the data contained by the exception handler by doing something like the following:
exception Return of int fun factException 0 = raise Return 1 | factException n = factException (n - 1) handle (Return res) => raise Return (n - 1)
NOTE: It is not clear why anyone would want to define
fact this way.
This example makes use of an exception,
Return : int -> exn, which wraps the
return value of
fact, at each step, simply raises an exception
containing its return value, which (in a future recursive call) is handled, the
value unwrapped (bound to
res), then multiplied by the current value of
generate the next value, which is simply raised again. This is very similar to a
case expression - we simply pattern match on the raised exception's constructor
using the handler (you can pattern match on exception constructors with
well, though not raised exceptions). Thus, the behavior of
is to be extensionally equivalent to
raise Return (fact n).
For an abstract idea of a potential use case, consider some recursive function
f that carries out some sequence of calculations, with a potential for error.
We might be interested in how many recursive calls such a function makes when it
ultimately fails - however, if we were to return the number of recursive calls,
we would constrain the return type to be
int, or barring that, some datatype
that could be either a valid result (say,
Valid res) or a signal for failure,
with a line number (say,
Fail line). We might desire that on a fail, execution
actually stops, however. We could then simply raise the exception
which, as a raised exception, has a polymorphic type. As such, exceptions allow
us to propagate back information without altering types, which can be
convenient for our purposes.
For a concrete example of using such exceptions, see the next section.
In the previous section, we discussed how continuation passing style could be used to devise complicated control flow schemas, in some instances being based around the idea of a success and failure continuation, which could both potentially execute disjoint sets of instructions. With continuations, we can relate them to a common other construct in programming languages, that being a goto. With a goto, we abandon whatever we are currently in the process of doing in favor of something else. In this, we can see that continuations and exceptions share similar characteristics, of being able to just "stop" execution in favor of some other route.
Consider the knapsack example from the previous section. We will now implement a solution to the knapsack problem using exception handling style.
exception Failure type weight = int type value = int (* knapsackEHS : * (value * weight) list -> * value -> * weight -> * ((value * weight) list -> 'a) -> * 'a * REQUIRES: The weights and values of the elements in L are strictly positive. * ENSURES: knapsackEHS L minVal maxWeight sc fc ~= sc L' for some L' that only * contains elements of L, such that the total value of L' >= minVal and the * total weight of L' <= maxWeight, if such an L' exists. If no such L' exists, * then it should be equivalent to raise Failure. *) fun knapsackEHS (L : (value * weight) list) (minVal : value) (maxWeight : weight) (sc : (value * weight) list -> 'a) : 'a = case L of  => if minVal <= 0 andalso maxWeight >= 0 then sc  else raise Failure | (v, w)::xs => if maxWeight < 0 then raise Failure else knapsackEHS ((v, w)::xs) (minVal - v) (maxWeight - w) (fn L' => sc ((v, w)::L')) handle Failure => knapsackEHS xs minVal maxWeight sc
It should be apparent that this function shares very close similarities to
knapsackCPS, with the exception  of
omitting the failure continuation for raising the
Failure exception. In fact,
we can claim that
knapsackCPS L minVal maxWeight sc fc ~= knapsackEHS L minVal maxWeight sc handle Failure => fc (), for all relevant values. Take a moment to
assure yourself that this is the case. The code does not look very different,
with the largest change being the recursive case, where the failure continuation
has instead been offloaded to a handler.
Recall that we can think of the recursive call in the knapsack problem as a
"choice" to "keep" or "not keep" the item at the head of the list. We said
previously that, arbitrarily, we could commit to the choice of "keep", with a
provision in the failure continuation to instead "not keep", should that failure
continuation ever be executed. When evaluating the expression
knapsackEHS ((v, w)::xs) (minVal - v) (maxWeight - w) (fn L' => sc ((v, w)::L'))
 , we know that one of two things can
happen - it can either succeed or fail. Now, however, our definition of
failure is different - instead of calling its failure continuation, an instance
knapsackEHS which fails should instead raise
Failure. Thus, it is exactly
the right thing to do to do what we would ordinarily do upon a failure, should
our call to
Note, however, that in this implementation we put a slight amount more burden on
the user, since the ill-defined behavior of this function now results in a
Failure, instead of just invoking
fc (), for some pre-defined
that we input. This offers us the same advantages, however, since the return
knapsackCPS must be the same. As such, if we want
knapsackCPS to return some indicative value (without using an option type), we
might not have an appropriate return value for the failure case. Thus,
knapsackEHS might have the behavior we're looking for, since the type of
raise Failure allows us to "unconstrain" the type of our success. In the
general case, however, we will not make heavy usage of exception handling style,
in favor of continuation passing style, which can be cleaner.
This is not the most committed that we could have made
converting to exception handling style - we could have also represented success
continuations with a raised exception, an
exception Success of (int * int) list. We will not cover such an implementation in this chapter, but we invite
the reader to try it out.
In this chapter, we explored exceptions, which allow us to have quick transfers of control flow, albeit in a less "controlled" fashion than ways that we have seen in the past. The success of so-called exception handling style is heavily contingent on intelligent placement and consideration of handlers, which decide where control is transferred to. We also have seen that we have a way of passing information back through the raised exception, which allows us to have a more powerful manner of communication than just an indicator of failure. Exceptions ultimately allow us a robust and type-safe way to deal with run-time errors in our programs.