OCaml Labs compiler hacking

home

How to handle success

04 Feb 2014

(Update (2014-05-28): Added notes on delimcc and Catch me if you can to the Discoveries section.)

(Update (2014-05-05): The match/exception variant of this proposal has been merged into OCaml trunk, ready for release in 4.02.)

(Update: there's a Mantis issue open to discuss this proposal.)

OCaml's try construct is good at dealing with exceptions, but not so good at handling the case where no exception is raised. This post describes a simple extension to try that adds support for handling the "success" case.

Here's an example of code that benefits from the extension. On a recent caml-list thread, Simon Cruanes posted the following function for iterating over a stream:

let rec iter_stream f s =
  match (try Some (MyStream.get s) with End_of_stream -> None) with
  | None -> ()
  | Some (x, s') ->
      f x;
      iter_stream f s'

For each element of a stream, iter_stream wraps the element with Some, then unwraps it again and passes it to f. At first glance, wrapping and immediately unwrapping in this way seems like needless obfuscation. However, moving the last two lines out of the body of the try in this way serves two essential purposes: it turns the recursive call to iter_stream into a tail call, and it allows exceptions raised by f to propagate. More generally, this use of options makes it easy to specify the success continuation of a try expression, i.e. the piece of code that receives the value of the body when no exception is raised.

As Simon notes, the match (try Some ...) idiom is widely used in OCaml code. Examples can be found in the source of lwt, batteries, liquidsoap, sexplib, opa, uri, coq, unison, and many other packages.

In response to Simon's message, Oleg pointed out a solution: the 2001 paper Exceptional Syntax (Benton and Kennedy) extends try with a let-like binding construct that supports the success continuation idiom directly without the need for the option value.

This post describes a patch to OCaml that implements a variant of Benton and Kennedy's design called handler case. Like Exceptional Syntax, handler case extends try with explicit success continuation handling. However, unlike Exceptional syntax, handler case uses match binding for both the success continuation and the exception-handling clauses. Here's the extended try syntax:

try expr
with pattern_1 -> expr_1
   | ...
   | pattern_n -> expr_n
   | val pattern_1' -> expr_1'
   | ...
   | val pattern_n' -> expr_n'

As in current OCaml, the clauses pattern_1 -> expr_1 ... pattern_n -> expr_n handle exceptions raised during the evaluation of expr. The clauses val pattern_1' -> expr_1' ... val pattern_n' -> expr_n' handle the case where no exception is raised; in this case the value of expr is matched against pattern_1' ... pattern_n' to select the expression to evaluate to produce the result value. (The actual syntax is implemented slightly more permissively: it allows value-matching and exception-matching clauses to be freely interleaved.)

Using handler case we can rewrite iter_stream to remove the extraneous option value:

let rec iter_stream f s =
  try MyStream.get s
  with End_of_stream -> ()
     | val (x, s') -> f x;
                      iter_stream f s'

We don't need to look far to find other code that benefits from the new construct. Here's a function from the Big_int module in the standard library:

let int_of_big_int bi =
  try let n = int_of_nat bi.abs_value in
    if bi.sign = -1 then - n else n
  with Failure _ ->
    if eq_big_int bi monster_big_int then monster_int
    else failwith "int_of_big_int"

The core of the function --- the call to int_of_nat --- is rather buried in the complex control flow. There are two if-then-else constructs, a let binding, and a try expression with a complex body. Using handler case we can disentangle the code to make the four possible outcomes from the call to int_of_nat explicit:

let int_of_big_int bi =
  try int_of_nat bi.abs_value with
  | val n when bi.sign = -1 ->
     -n
  | val n ->
     n
  | Failure _ when eq_big_int bi monster_big_int ->
     monster_int
  | Failure _ ->
     failwith "int_of_big_int"

Here's a simpler example from the String module, which also involves code that cannot raise an exception in the body of a try block:

try ignore (index_rec s l i c); true with Not_found -> false

Using handler case we can separate the code that may raise an exception (the call to index_rec) from the expression that produces the result:

try index_rec s l i c with val _ -> true | Not_found -> false

Trying it out

Using opam you can install an OCaml compiler extended with handler case as follows:

$ opam remote add ocamllabs git@github.com:ocamllabs/opam-repo-dev.git
ocamllabs Fetching git@github.com:ocamllabs/opam-repo-dev.git
[...]
$ opam switch 4.02.0dev+handler-syntax
# To complete the configuration of OPAM, you need to run:
eval `opam config env`
$ eval `opam config env`

jsofocaml

You can also try out the handler case construct in your browser, using the following modified version of OCamlPro's Try OCaml application:

The discoveries of success continuations

As Philip Wadler notes, constructs for handling success continuations have been independently discovered multiple times. In fact, the history goes back even further than described in Wadler's blog; constructs like handler case date back over thirty years and have been introduced, apparently independently, into at least four languages. Curiously, all the languages use let-binding for success continuations and match binding for failure continuations.

Lisp

In Common Lisp the construct analogous to try is handler-case (from which the construct discussed here borrows its name). A handler-case expression has a body and a sequence of clauses which specify how various conditions (exceptions) should be handled. The special condition specification :no-error specifies the code to run when no condition is signalled. The iter_stream function might be written as follows in Common Lisp:

(defun iter-stream (f s)
   (handler-case (get-stream s)
      (end-of-stream (_) nil)
      (:no-error (x |s'|)
         (funcall f x)
         (iter-stream f |s'|))))

The Common Lisp specification was completed in 1994 but the handler-case construct and its :no-error clause were present in some of Common Lisp's progenitors. The construct was apparently introduced to Symbolics Lisp some time around 1982: it appears in the 5th edition of the Lisp Machine manual (January 1983) but not the 4th edition from 18 months earlier (July 1981).

Python

Python has supported success continuations in exception handlers since May 1994, when the else clause was added to try blocks. The Changelog in old versions of the Grammar/Grammar file has an entry

# 3-May-94:
#Added else clause to try-except

introduced in a commit from August 1994:

changeset:   1744:6c0e11b94009
branch:      legacy-trunk
user:        Guido van Rossum <guido@python.org>
date:        Mon Aug 01 11:00:20 1994 +0000
summary:     Bring alpha100 revision back to mainline

Unlike the :no-error clause in Lisp's handler-case, Python's else clause doesn't bind variables. Since Python variables have function scope, not block scope, bindings in the body of the try block are visible throughout the function. In Python we might write iter_stream as follows:

def iter_stream(f, s):
   try:
      (x, s_) = MyStream.get(s)
   except End_of_stream:
      pass
   else:
      f(x)
      iter_stream(f, s_)

The provenance of the else clause is unclear, but it doesn't seem to derive from Lisp's handler-case. The design of Python's exception handling constructs comes from Modula-3, but the exception handling construct described in the Modula-3 report does not include a way of specifying the success continuation. The syntax of the Modula-3 TRY/EXCEPT statement (found on p21 of the report) does include an ELSE clause:

   TRY    
     Body
   EXCEPT
     id1 (v1) => Handler1
   | ...
   | idn (vn) => Handlern
   ELSE Handler0
   END

However, whereas Python's else handles the case where no exception is raised, Modula-3's ELSE handles the case where an exception not named in one of the EXCEPT clauses is raised: it is equivalent to Python's catch-all except:.

Python also adds success handlers to other constructs. Both the for and the while statements have an optional else clause which is executed unless the loop terminates prematurely with an exception or break.

Exceptional Syntax

The 2001 paper Exceptional Syntax (Benton and Kennedy) proposed the following construct for handling exceptions in Standard ML:

let val pattern_1 <= expr_1
    ...
    val pattern_n <= expr_n
 in
    expr
unless
    pattern_1' => expr_1'
  | ...
  | pattern_n' => expr_n'
end

Evaluation of the let binding proceeds as normal, except that if any of expr_1 to expr_n raises an exception, control is transferred to the right hand side of the first of the clauses after unless whose left hand side matches the exception. The construct is largely similar to our proposed variation, except that the bindings used in the success continuation are based on let, so scrutinising the values requires a separate case (i.e. match) expression.

Using the Exceptional Syntax construct we might write iter_stream as follows:

fun iter_stream f s =
 let val (x, s') <= MyStream.get s in
     f x;
     iter_stream f s'
 unless End_of_stream => ()
 end

Exceptional Syntax has been implemented in the SML-to-Java compiler MLj.

Erlang

The 2004 paper Erlang's Exception Handling Revisited (Richard Carlsson, Björn Gustavsson and Patrik Nyblom) proposed an exception-handling construct for Erlang along the same lines as exceptional syntax, although apparently developed independently. In the proposed extension to Erlang we might write iter_stream as follows:

iter_stream(F, S) ->
   try Mystream:get(S) of
      {X, S_} ->
        _ = F(X),
        iter_stream(F, S_)
   with
    End_of_stream -> {}

Eff

Plotkin and Pretnar's work on handlers for algebraic effects generalises Exceptional Syntax to support effects other than exceptions. The programming language eff implements a design based on this work, and supports Exceptional Syntax, again with let binding for the success continuation. (Although the success continuation is incorporated into the exception matching construct, only a single success continuation pattern is allowed.) In eff we might write iter_stream as follows:

let rec iter_stream f s =
  handle my_stream_get s
  with exn#end_of_stream _ _ -> ()
     | val (x, s') -> f x;
                      iter_stream f s'

The second argument in the end_of_stream clauses binds the continuation of the effect, allowing handling strategies other than the usual stack unwinding. Since we ignore the continuation argument the behaviour is the same as for a regular exception handler.

The eff implementation uses the term "handler case" for the clauses of the handle construct.

OCaml

Several OCaml programmers have proposed or implemented constructs related to handler case.

Oleg's delimcc library for delimited continuations provides the operations needed to support the success continuation style. The programmer can use push_prompt to establish a context, then call shift or shift0 to return control to that context later, much as try establishes a context to which raise can transfer control. If shift is not called then control returns normally from the continuation argument to push_prompt. Using delimcc we might implement iter_stream as follows:

let rec iter_stream f s =
    let p = new_prompt () in
    match push_prompt p (fun () -> `Val (my_stream_get s p)) with
  | `Val (x, s') -> f x; iter_stream f s'
  | `End_of_stream -> ()

Martin Jambon has implemented a construct equivalent to Exceptional Syntax for OCaml as part of the micmatch extension. His implementation allows us to write iter_stream in much the same way as Benton and Kennedy's proposal:

let rec iter_stream f s =
  let try (x, s') = my_stream_get s
   in f x;
      iter_stream f s'
  with End_of_stream -> ()

The details of the implementation are discussed in Jake Donham's articles on Camlp4. The micmatch implementation has a novel feature: the let binding associated with the success continuation may be made recursive.

Alain Frisch has proposed and implemented a more powerful extension to OCaml, Static Exceptions, which allow transfer of control to lexically-visible handlers (along the lines of Common Lisp's block and return-from). Static exceptions are based on an equivalent feature in OCaml's intermediate language.

There is a straightforward translation from OCaml extended with handler case into OCaml extended with static exceptions by wrapping the body of each try expression in raise (`Val (...)), and changing the val keyword in the binding section to `Val. For example, iter_stream can be written using static exceptions as follows:

let rec iter_stream f s =
  try raise (`Val (MyStream.get s))
  with End_of_stream -> ()
     | `Val (x, s') -> f x;
                       iter_stream f s'

Of course, static exceptions allow many other programs to be expressed that are not readily expressible using handler case.

In their 2008 paper Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml David Teller Arnaud Spiwack and Till Varoquaux added an attempt keyword to OCaml that extends match-style pattern matching with both a single optional value case and an optional finally clause.

Finally, I discovered while writing this article that Christophe Raffalli proposed the handler case design fifteen years ago in a message to caml-list! Christophe's proposal wasn't picked up back then, but perhaps the time has now come to give OCaml programmers a way to handle success.

Postscript: a symmetric extension

The try construct in current OCaml supports matching against raised exceptions but not against the value produced when no exception is raised. Contrariwise, the match construct supports matching against the value produced when no exception is raised, but does not support matching against raised exceptions. As implemented, the patch addresses this asymmetry, extending match with clauses that specify the "failure continuation":

match expr
with pattern_1 -> expr_1
   | ...
   | pattern_n -> expr_n
   | exception pattern_1' -> expr_1'
   | ...
   | exception pattern_n' -> expr_n'

With this additional extension the choice between match and try becomes purely stylistic. We might optimise for succinctness, and use try in the case where exceptions are expected (for example, where they're used for control flow), reserving match for the case where exceptions are truly exceptional.

For the sake of completeness, here's iter_stream written with the extended match construct:

let rec iter_stream f s =
  match MyStream.get s with
     (x, s') -> f x;
                iter_stream f s'
   | exception End_of_stream -> ()

Since both val and exception are existing keywords, the extensions to both try and match are fully backwards compatible.