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?
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.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.