Sample Code for this Chapter

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:

  1. Exceptions.  Evaluation may be aborted by signaling an exceptional condition.
  2. Mutation.  Storage may be allocated and modified during evaluation.
  3. I/O.  It is possible to read from an input source and write to an output sink during evaluation.
  4. Communication.  Data may be sent to and received from communication channels.

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:

  1. We may use them to create values of a datatype (perhaps by applying them to other values).
  2. We may use them to match values of a datatype (perhaps also matching a constituent value).

The situation with exception constructors is symmetric.

  1. We may use them to create an exception (perhaps with an associated value).
  2. We may use them to match an exception (perhaps also matching the associated value).

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.

Sample Code for this Chapter