Chapter 15. Raising and Catching Exceptions

Exceptions provide a mechanism for altering the (normal) control-flow during program execution. Raising an exception is somewhat like executing a goto-statement. A handler for handling a raised exception is essentially a pattern matching clause guarded by a pattern (for matching exceptions). Intuitively speaking, a raised exception passes through a stack of handlers; the raised exception is handled by a handler if the exception matches the guard of the handler, or it simply tries the next handler to see if it can be handled; the raised exception terminates program execution abnormally if it is not handled by any of the handlers.

In ATS, a try-expression (or try-with-expression) is of the form (try exp with clseq), where try is a keyword, exp is an expression, with is also a keyword, and clseq is a sequence of pattern matching clauses (used as exception-handlers). When evaluating such a try-expression, we first evaluate exp. If the evaluation of exp leads to a value, then the value is also the value of the try-expression. If the evaluation of exp leads to a raised exception, then we match the exception against the guards of the matching clauses in clseq. If there is a match, the raised exception is caught and we continue to evaluate the body of the first clause whose guard is matched. If there is no match, the raised exception is uncaught. In the following example, list0_exists is implemented based on list0_foreach:

// implement {a}(*tmp*) list0_exists (xs, test) = let // exception True of () // in // try let // val () = list0_foreach<a> ( xs , lam(x) => if test(x) then $raise True() ) // in false end with ~True() => true // end // end of [list0_exists] //

Given a list and a predicate, list0_exists returns a boolean value to indicate whether there exists an element in the list that satisfies the predicate. There is a built-in type exn in ATS, which is somewhat like an extensible datatype in the sense that a new constructor associated with exn can be introduced through an exception-declaration. For instance, True is introduced as a nullary exception-constructor in the body of list0_exists. Given a list and a function, list0_foreach normally traverses until the end of the list while appying the function to each encountered element. When the call to list0_foreach in the body of list0_exists is evaluated, an exception (True()) is raised to stop further traversing if an element satisfying the predicate test is encountered. If the call to list0_foreach returns, then the value false is the return value of list0_exists. If True() is raised during the evaluation of the call, then this raised exception is to be caught by the handler following the keyword with, resulting in the value true becoming the return value of list0_exists. Note that a raised exception is considered a resource in ATS and it needs to be properly freed or re-raised after being caught. The symbol ~ in the pattern ~True() indicates that the caught execption is freed.

By raising an exception, a function can efficiently pass some information gathered during its evaluation. Let us see a typical example of this kind as follows. A datatype tree is decared for representing binary trees:

// datatype tree(a:t@ype) = | tree_nil of () | tree_cons of (tree(a), a, tree(a)) //

For instance, the function for computing the height of a given binary tree can be implemented as follows:

// fun {a:t@ype} tree_height(t0: tree(a)): int = ( case+ t0 of | tree_nil() => 0 | tree_cons(tl, _, tr) => 1 + max(tree_height<a>(tl), tree_height<a>(tr)) ) //

Note that tree_height is O(n)-time, where n is the size of its argument. A binary is perfect if it is empty or both of its children are perfect and of the same height. For instance, the following function tree_is_perfect checks whether a given binary tree is perfect:

// fun {a:t@ype} tree_is_perfect (t0: tree(a)): bool = ( case+ t0 of | tree_nil() => true | tree_cons(tl, _, tr) => tree_is_perfect<a>(tl) && tree_is_perfect<a>(tr) && (tree_height<a>(tl) = tree_height<a>(tr)) ) //

Clearly, the time complexity of tree_is_perfect is O(n(log(n))) where n is the size of its argument. By making use of exception, we can readily implement the following function of O(n)-time that also checks whether a given tree is perfect:

// fun {a:t@ype} tree_is_perfect2 (t0: tree(a)): bool = let // exception NotPerfect of () // fun aux(t0: tree(a)): int = case+ t0 of | tree_nil() => 0 | tree_cons(tl, _, tr) => let val hl = aux(tl) and hr = aux(tr) in if hl = hr then 1+max(hl, hr) else $raise NotPerfect end // in try let val _ = aux(t0) in true end with ~NotPerfect() => false end // end of [tree_is_perfect2] //

The inner function aux inside tree_is_perfect2 returns the height of a given tree only if the tree is perfect. Otherwise, an exception (NotPerfect()) is raised. In other words, if a call to aux on a tree returns, we know that the tree is pefect while obtaining its height. This is often dubbed a hitting-two-birds-with-one-stone scenario.

Please find on-line the entirety of the code used in this chapter.