In the first chapter of these notes we mentioned that expressions in Standard ML always have a type, may have a value, and may engender an effect. So far we've concentrated on typing and evaluation. In this chapter we will introduce the concept of an effect. While it's hard to give a precise general definition of what we mean by an effect, the idea is that an effect is any action resulting from evaluation of an expression other than returning a value. From this point of view we might consider non-termination to be an effect, but we don't usually think of failure to terminate as a positive "action" in its own right, rather as a failure to take any action. What are some other examples? The main examples are these:
This chapter is concerned with exceptions; the other forms of effects will be dealt with later in these notes.
A basic use of exceptions in ML is to signal error conditions. ML is a safe language in the sense that its execution behavior may be understood entirely in terms of the constructs of the language itself. Behavior such as "dumping core" or incurring a "bus error" are extra-linguistic notions that may only be explained by appeal to the underlying implementation of the language. It can be proved that ML is safe, from which it follows that such behaviors cannot arise (except through the failure of the compiler to implement the language properly.) In unsafe languages (such as C) these sorts of errors can and do arise, typically because of the (mis)use of a primitive operation on a value that does not lie in its domain of definition. For example, in C we may cast an integer as a function pointer, then invoke it by applying it to an argument. The behavior of such a program cannot be predicted at the level of the language itself since it relies on the details of the memory layout and the interpretation of data as code. To ensure safety, and hence freedom from mysterious run-time faults, ML ensures that the primitive operations may only be applied to appropriate arguments. This is achieved in part by the static type discipline, which rules out expressions that are manifestly inappropriate (e.g., adding a string to an integer or casting an integer as a function), and partly by dynamic checks that rule out violations that cannot be detected statically (e.g., division by zero or arithmetic overflow). Static violations are signalled by type checking errors; dynamic violations are signalled by raising exceptions.
For example, the expression 3 + "3"
is ill-typed, and hence
cannot be evaluated. In contrast the expression 3 div 0
is well-typed
(with type int
), but incurs a run-time fault that is signalled by raising the
exception Div
. We will indicate this by writing
3 div 0 => raise Div
Thus an exception is a form of "answer" to the question "what is
the value this expression?". In most implementations an exception such as this
is reported by an error message of the form "Uncaught exception Div
",
together with the line number (or some other indication) of the point in the program where
the exception occurred.
Exceptions have names so that we may distinguish different sources of error from one
another. For example, evaluation of the expression maxint * maxint
(where maxint
is the largest representable integer) causes the exception Overflow
to be raised, indicating that an arithmetic overflow error arose in the attempt to carry
out the multiplication.
At this point you may be wondering about the overhead of checking for arithmetic faults. The compiler must generate instructions that ensure that an overflow fault is caught before any subsequent operations are performed. This can be quite expensive on pipelined processors, which sacrifice precise delivery of arithmetic faults in the interest of speeding up execution in the non-faulting case. Unfortunately it is necessary to incur this overhead if we are to avoid having the behavior of an ML program depend on the underlying processor on which it is implemented.
Another source of run-time exceptions is an inexhaustive match. Suppose we define
the function hd
as follows
fun hd (h::_) = h
This definition is inexhaustive since it makes no provision for the possibility of the
argument being nil
. What happens if we apply hd
to nil
?
The exception Match
is raised, indicating the failure of the
pattern-matching process:
hd nil => raise Match
The occurrence of a Match
exception at run-time is indicative of a
violation of a pre-condition to the invocation of a function somewhere in the program.
Recall that it is often OK for a function to be inexhaustive, provided that we take
care to ensure that it is never applied to a value outside of its domain. Should
this occur (because of a mistake by the programmer, evidently), the result is nevertheless
well-defined because ML checks for pattern match failure, rather than leaving the behavior
of the application undefined. In other words: ML programs are implicitly
"bullet-proofed" against failures of pattern matching. The flip side is
that if no inexhaustive match warnings arise during type checking, then the exception
Match can never be raised during evaluation (and hence no run-time checking need be
performed).
A related situation is the use of a pattern in a val
binding to
destructure a value. If the pattern can fail to match a value of this type, then a Bind
exception is raised at run-time. For example, evaluation of the binding
val h::_ = nil
raises the exception Bind
since the pattern h::_
does not
match the value nil
. Here again observe that a Bind
exception cannot arise unless the compiler has previously warned us of the possibility: no
warning, no Bind
exception.
These are all examples of the use of pre-defined exceptions to indicate fatal error
conditions. Since the built-in exceptions have a built-in meaning, it is generally
inadvisable to use these to signal program-specific error conditions. Instead we
introduce a new exception using an exception
declaration, and signal
it using a raise
expression when a run-time violation occurs. That way
we can associate specific exceptions with specific pieces of code, easing the process of
tracking down the source of the error.
Here's an example. Suppose that we wish to define a "checked factorial" function that ensures that its argument is non-negative. Here's a first attempt at defining such a function:
exception Factorial
fun checked_factorial n =
if n < 0 then
raise Factorial
else if n=0 then
1
else n * checked_factorial (n-1)
The declaration exception Factorial
introduces an exception Factorial
,
which we raise in the case that checked_factorial
is applied to a negative
number.
The definition of checked_factorial
is unsatisfactory in at least two
ways. One relatively minor issue is that it does not make effective use of pattern
matching, but instead relies on explicit comparison operations. To some extent this
is unavoidable since we wish to check explicitly for negative arguments, which cannot be
done using a pattern. A more significant problem is that checked_factorial
repeatedly checks the validity of its argument on each recursive call, even
though we can prove that if the initial argument is non-negative, then so must be the
argument on each recursive call. This fact is not reflected in the code. We
can improve the definition by introducing an auxiliary function as follows:
exception Factorial
local
fun fact 0 = 1
| fact n = n * fact (n-1)
in
fun checked_factorial n =
if n >= 0 then
fact n
else
raise Factorial
end
Notice that we perform the range check exactly once, and that the auxiliary function makes effective use of pattern-matching.
The use of exceptions to signal error conditions suggests that raising an exception is fatal: execution of the program terminates with the raised exception. But signaling an error is only one use of the exception mechanism. More generally, exceptions can be used to effect non-local transfers of control. By using an exception handler we may "catch" a raised exception and continue evaluation along some other path. A very simple example is provided by the following driver for the factorial function that accepts numbers from the keyboard, computes their factorial, and prints the result.
fun factorial_driver () =
let
val input = read_integer ()
val result = makestring (checked_factorial input)
in
print result
end
handle Factorial => print "Out of range.\n"
The expression exp handle
match is an exception handler.
It is evaluated by attempting to evaluate exp. If it returns a
value, then that is the value of the entire expression; the handler plays no role in this
case. If, however, exp raises an exception exn, then the exception
value is matched against the clauses of the match (exactly as in the application of a
clausal function to an argument) to determine how to proceed. If the pattern of a
clause matches the exception exn, then evaluation resumes with the expression
part of that clause. If no pattern matches, the exception exn is re-raised
so that outer exception handlers may dispatch on it. If no handler handles the
exception, then the uncaught exception is signaled as the final result of evaluation.
That is, computation is aborted with the uncaught exception exn.
In more operational terms, evaluation of exp handle
match
proceeds by installing an exception handler determined by match, then evaluating exp.
The previous binding of the exception handler is preserved so that it may be
restored once the given handler is no longer needed. Raising an exception consists
of passing a value of type exn
to the current exception handler.
Passing an exception to a handler de-installs that handler, and re-installs the previously
active handler. This ensures that if the handler itself raises an exception, or
fails to handle the given exception, then the exception is propagated to the handler
active prior to evaluation of the handle
expression. If the expression
does not raise an exception, the previous handler is restored as part of completing the
evaluation of the handle
expression.
Returning to the function factorial_driver
, we see that evaluation
proceeds by attempting to compute the factorial of a given number (read from the keyboard
by an unspecified function read_integer
), printing the result if the given
number is in range, and otherwise reporting that the number is out of range. The
example is trivialized to focus on the role of exceptions, but one could easily imagine
generalizing it in a number of ways that also make use of exceptions. For example,
we might repeatedly read integers until the user terminates the input stream (by typing
the end of file character). Termination of input might be signaled by an EndOfFile
exception, which is handled by the driver. Similarly, we might expect that the
function read_integer
raises the exception SyntaxError
in the
case that the input is not properly formatted. Again we would handle this exception,
print a suitable message, and resume. Here's a sketch of a more complicated
factorial driver:
fun factorial_driver () =
let
val input = read_integer ()
val result = makestring (checked_factorial input)
val _ = print result
in
factorial_driver ()
end
handle EndOfFile => print "Done.\n"
| SyntaxError =>
let val _ = print "Syntax error.\n" in factorial_driver () end
| Factorial =>
let val _ = print "Out of range.\n" in factorial_driver () end
We will return to a more detailed discussion of input/output later in these notes. The point to notice here is that the code is structured with a completely uncluttered "normal path" that reads an integer, computes its factorial, formats it, prints it, and repeats. The exception handler takes care of the exceptional cases: end of file, syntax error, and domain error. In the latter two cases we report an error, and resume reading. In the former we simply report completion and we are done.
The reader is encouraged to imagine how one might structure this program without the use of exceptions. The primary benefits of the exception mechanism are that they force you to consider the exceptional case (if you don't, you'll get an uncaught exception at run-time), and that they allow you to segregate the special case from the normal case in the code (rather than clutter the code with explicit checks).
Another typical use of exceptions is to implement backtracking, a programming technique based on exhaustive search of a state space. A very simple, albeit somewhat artificial, example is provided by the following function to compute change from an arbitrary list of coin values. What is at issue is that the obvious "greedy" algorithm for making change that proceeds by doling out as many coins as possible in decreasing order of value does not always work. Given only a 5 cent and a 2 cent coin, we cannot make 16 cents in change by first taking three 5's and then proceeding to dole out 2's. In fact we must use two 5's and three 2's to make 16 cents. Here's a method that works for any set of coins:
exception Change
fun change _ 0 = nil
| change nil _ = raise Change
| change (coin::coins) amt =
if coin > amt then
change coins amt
else
(coin :: change (coin::coins) (amt-coin))
handle Change => change coins amt
The idea is to proceed greedily, but if we get "stuck", we undo the most
recent greedy decision and proceed again from there. Simulate evaluation of the
example of change [5,2] 16
to see how the code works.
Exceptions can also carry values. For example, we might associate with a SyntaxError
exception a string indicating the precise nature of the error. For example, we might
write
raise SyntaxError "Integer expected"
to indicate a malformed expression in a situation where an integer is expected, and write
raise SyntaxError "Identifier expected"
to indicate a badly-formed identifier. Such an exception is introduced by the declaration
exception SyntaxError of string
which introduces the exception SyntaxError
as an exception carrying a
string as value. This declaration introduces the exception constructor SyntaxError
.
Exception constructors are in many ways similar to value constructors. In
particular they can be used in patterns, as in the following code fragment:
... handle SyntaxError msg => print "Syntax error: " ^ msg ^ "\n"
Here we specify a pattern for SyntaxError
exceptions that also binds the
string associated with the exception to the identifier msg
and prints that
string along with an error indication.
Exception constructors raise the question of the status of exceptions in the language. Recall that we may use value constructors in two ways:
The situation with exception constructors is symmetric.
Value constructors have types, as we previously mentioned. For example, the list
constructors nil
and ::
have types
'a list
and
'a * 'a list -> 'a list
respectively. What about exception constructors? A "bare"
exception constructor (such as Factorial
above) has type
exn
and a value-carrying exception constructor (such as SyntaxError
) has type
string -> exn
Thus Factorial
is a value of type exn
, and SyntaxError
"Integer expected"
is a value of type exn
.
The type exn
is the type of exception packets, the data values
associated with an exception. The primitive operation raise
takes any
value of type exn
as argument and raises an exception with that value.
The clauses of a handler may be applied to any value of type exn
using the
rules of pattern matching described earlier; if an exception constructor is no longer in
scope, then the handler cannot catch it (other than via a wild-card pattern).
The type exn
may be thought of as a kind of built-in datatype, except
that the constructors of this type are not determined once and for all (as they are
with a datatype
declaration), but rather are incrementally
introduced as needed in a program. For this reason the type exn
is
sometimes called an extensible datatype.