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.

Code for This Chapter