Code for This Chapter

In this chapter we discuss the close relationships between option types, exceptions, and continuations.  They each provide the means for handling failure to produce a value in a computation.  Option types provide the means of explicitly indicating in the type of a function the possibility that it may fail to yield a "normal" result.  The result type of the function forces the caller to dispatch explicitly on whether or not it returned a normal value.  Exceptions provide the means of implicitly signalling failure to return a normal result value, without sacrificing the requirement that an application of such a function cannot ignore failure to yield a value.   Continuations provide another means of handling failure by providing a function to invoke in the case that normal return is impossible.

We will explore the trade-offs between these three approaches by considering three different implementations of the n-queens problem: find a way to place n queens on an nxn chessboard in such a way that no two queens attack one another.   The general strategy is to place queens in successive columns in such a way that it is not attacked by a previously placed queen.  Unfortunately it's not possible to do this in one pass; we may find that we can safely place k<n queens on the board, only to discover that there is no way to place the next one.  To find a solution we must reconsider earlier decisions, and work forward from there.  If all possible reconsiderations of all previous decisions all lead to failure, then the problem is unsolvable.  For example, there is no safe placement of three queens on a 3x3 chessboard.  This trial-and-error approach to solving the n-queens problem is called backtracking search.

A solution to the n-queens problem consists of an nxn chessboard with n queens safely placed on it.  The following signature defines a chessboard abstraction:

signature BOARD = sig
type board
val new : int -> board
val complete : board -> bool
val place : board * int -> board
val safe : board * int -> bool
val size : board -> int
val positions : board -> (int * int) list
end

The operation `new` creates a new board of a given dimension n>=0.   The operation `complete` checks whether the board contains a complete safe placement of n queens.  The function `safe` checks whether it is safe to place a queen at row i in the next free column of a board B.   The operation `place` puts a queen at row i in the next available column of the board.  The function `size` returns the size of a board, and the function `positions` returns the coordinates of the queens on the board.

The board abstraction may be implemented as follows:

structure Board :> BOARD = struct

(* representation: size, next free column, number placed, placements *)
(* rep'n invariant: size >=0, 1<=next free<=size, length(placements) = number placed *)
type board = int * int * int * (int * int) list

fun new n = (n, 1, 0, nil)

fun size (n, _, _, _) = n
fun complete (n, _, k, _) = (k=n)
fun positions (_, _, _, qs) = qs

fun place ((n, i, k, qs),j) = (n, i+1, k+1, (i,j)::qs)

fun threatens ((i,j), (i',j')) = i=i' orelse j=j' orelse i+j = i'+j' orelse i-j = i'-j'
fun conflicts (q, nil) = false
| conflicts (q, q'::qs) = threatens (q, q') orelse conflicts (q, qs)
fun safe ((_, i, _, qs), j) = not (conflicts ((i,j), qs))

end

The representation type contains "redundant" information in order to make the individual operations more efficient.  The representation invariant ensures that the components of the representation are properly related to one another (e.g., the claimed number of placements is indeed the length of the list of placed queens, and so on.)

Our goal is to define a function

val queens : int -> Board.board option

such that if n>=0, then `queens` n evaluates either to `NONE` if there is no safe placement of n queens on an nxn board, or to `SOME` B otherwise, with B a complete board containing a safe placement of n queens.  We will consider three different solutions, one using option types, one using exceptions, and one using a failure continuation.

Here's a solution based on option types:

(* addqueen bd evaluates to SOME bd', where bd' is a complete safe placement
extending bd, if one exists, and yields NONE otherwise *)
fun addqueen bd =
let
fun try j =
if j > Board.size bd then
NONE
else if Board.safe (bd, j) then
case addqueen (Board.place (bd, j))
of NONE => try (j+1)
| r as (SOME bd') => r
else
try (j+1)
in
if Board.complete bd then
SOME bd
else
try 1
end

fun queens n = addqueen (Board.new n)

The characteristic feature of this solution is that we must explicitly check the result of each recursive call to `addqueen` to determine whether a safe placement is possible from that position.  If so, we simply return it; if not, we must reconsider the placement of a queen in row j of the next available column.  If no placement is possible in the current column, the function yields `NONE`, which forces reconsideration of the placement of a queen in the preceding row.  Eventually we either find a safe placement, or yield `NONE` indicating that no solution is possible.

The explicit check on the result of each recursive call can be replaced by the use of exceptions.  Rather than have `addqueen` return a value of type ```Board.board option```, we instead have it return a value of type `Board.board`, if possible, and otherwise raise an exception indicating failure.  The case analysis on the result is replaced by a use of an exception handler.  Here's the code:

exception Fail

(* addqueen bd evaluates to bd', where bd' is a complete safe placement
extending bd, if one exists, and raises Fail otherwise *)
fun addqueen bd =
let
fun try j =
if j > Board.size bd then
raise Fail
else if Board.safe (bd, j) then
addqueen (Board.place (bd, j))
handle Fail => try (j+1)
else
try (j+1)
in
if Board.complete bd then
bd
else
try 1
end

fun queens n = SOME (addqueen (Board.new n)) handle Fail => NONE

The main difference between this solution and the previous one is that both calls to `addqueen` must handle the possibility that it raises the exception `Fail`.  In the outermost call this corresponds to a complete failure to find a safe placement, which means that `queens` must return `NONE`.  If a safe placement is indeed found, it is wrapped with the constructor `SOME` to indicate success.  In the recursive call within `try`, an exception handler is required to handle the possibility of there being no safe placement starting in the current position.  This check corresponds directly to the case analysis required in the solution based on option types.

What are the trade-offs between the two solutions?

1. The solution based on option types makes explicit in the type of the function `addqueen` the possibility of failure.  This forces the programmer to explicitly test for failure using a case analysis on the result of the call.  The type checker will ensure that one cannot use a `Board.board option` where a `Board.board` is expected.  The solution based on exceptions does not explicitly indicate failure in its type.  However, the programmer is nevertheless forced to handle the failure, for otherwise an uncaught exception error would be raised at run-time, rather than compile-time.
2. The solution based on option types requires an explicit case analysis on the result of each recursive call.  If "most" results are successful, the check is redundant and therefore excessively costly.  The solution based on exceptions is free of this overhead: it is biased towards the "normal" case of returning a board, rather than the "failure" case of not returning a board at all.  The implementation of exceptions ensures that the use of a handler is more efficient than an explicit case analysis in the case that failure is rare compared to success.

For the n-queens problem it is not clear which solution is preferable.   In general, if efficiency is paramount, we tend to prefer exceptions if failure is a rarity, and to prefer options if failure is relatively common.  If, on the other hand, static checking is paramount, then it is advantageous to use options since the type checker will enforce the requirement that the programmer check for failure, rather than having the error arise only at run-time.

We turn now to a third solution based on continuation-passing.  The idea is quite simple: an exception handler is essentially a function that we invoke when we reach a blind alley.  Ordinarily we achieve this invocation by raising an exception and relying on the caller to catch it and pass control to the handler.  But we can, if we wish, pass the handler around as an additional argument, the failure continuation of the computation.  Here's how it's done in the case of the n-queens problem:

(* addqueen bd evaluates to bd', where bd' is a complete safe placement
extending bd, if one exists, and otherwise yields the value of fc () *)
fun addqueen (bd, fc) =
let
fun try j =
if j > Board.size bd then
fc ()
else if Board.safe (bd, j) then
addqueen (Board.place (bd, j), fn () => try (j+1))
else
try (j+1)
in
if Board.complete bd then
SOME bd
else
try 1
end

fun queens n = addqueen (Board.new n, fn () => NONE)

Here again the differences are small, but significant.  The initial continuation simply yields `NONE`, reflecting the ultimate failure to find a safe placement.   On a recursive call we pass to `addqueen` a continuation that resumes search at the next row of the current column.  Should we exceed the number of rows on the board, we invoke the failure continuation of the most recent call to `addqueen`.

The solution based on continuations is very close to the solution based on exceptions, both in form and in terms of efficiency.  Which is preferable?  Here again there is no easy answer, we can only offer general advice.  First off, as we've seen in the case of  regular expression matching, failure continuations are more powerful than exceptions; there is no obvious way to replace the use of a failure continuation with a use of exceptions in the matcher.  However, in the case that exceptions would suffice, it is generally preferable to use them since one may then avoid passing an explicit failure continuation.  More significantly, the compiler ensures that an uncaught exception aborts the program gracefully, whereas failure to invoke a continuation is not in itself a run-time fault.  Using the right tool for the right job makes life easier.