Resumable exceptions in plain OCaml

Resumable exceptions in plain OCaml

[oleg]

Resumable exceptions are the strict generalization of regular exceptions,
which lets the exception raising form return a value and so the
computation may continue. It's the exception handler that decides
either to abort the exceptional computation or to resume it with a
particular value. Resumable exceptions are made popular by Common
Lisp, where they are widely used: http://lambda-the-ultimate.org/node/1544

We show a conservative and elementary implementation of resumable
exceptions in OCaml: the implementation is a self-contained 100% pure
OCaml library; makes no changes to the OCaml system; supports the
existing style of defining exceptions; is compatible with the ordinary
exceptions; works in byte- or natively-compiled code; uses the most
basic facilities of ML and so can easily be translated to SML.

We impose no extra restrictions on the resumable exception raising and
handling forms. Like with ordinary exceptions, resumable ones may
encapsulate values of arbitrary types; the same exception handler may
process exceptions of many types -- and send resumption replies of
many types. The raise form may appear within the guarded code at many
places; different raise forms may resume with values of different
types. Furthermore, resumable exceptions are declared just like the
ordinary ones, with the `exception' keyword. If the resumable
exception handler never resumes, resumable exceptions act and feel
precisely as the regular ones.

The control aspect of resumable exceptions is quite trivial: as first
pointed out by Luc Moreau (HOSC1998), invoking a resumable expression
is sort of a regular function call, where the name of the function,
the handler, is obtained via dynamic binding. It is the typing aspect
of resumable exceptions -- imposing no restrictions on how and when
exceptions can be raised and resumed -- that took most of the
work. The resulting implementation involves less than common ways of
invoking functions and passing their results.

The implementation and illustration code is available at
	http://pobox.com/~oleg/ftp/ML/resumable.ml

The following is an excerpt from the above file, illustrating
resumable exceptions. As regular exceptions, resumable exceptions must
be declared, with the ordinary keyword 'exception'. A resumable
exception amounts to two (or more) ordinary exceptions. The first is
what used to raise the (resumable) exception.  The second is to
encapsulate the returned result. The function [rhandle] is equivalent to
the [try] form; it receives the exception handler and the thunk. The
function [rraise : exn -> (exn -> 'a) -> 'a] raises the resumable
exception. Its second argument receives the resumable exception,
should unpack it and return the resumption result, with which to
continue the computation.


(* Declare the first resumable exception. It has resumptions of two types *)
exception Foo of int
exception Foo_r1 of bool
exception Foo_r2 of string

(* Declare the second resumable exception *)
exception Bar of char
exception Bar_r of int

let handler v = try raise v with
  | Foo x -> Printf.printf "Got Foo of %d\n" x; 
      if x < 100 then resume (Foo_r1 (x < 4)) else resume (Foo_r2 "xxx")
  | Bar c -> Printf.printf "Got Bar of %c\n" c;
      if c < 'E' then resume (Bar_r (int_of_char c + 1))
      else 42.0                                          (* aborting *)

let () =
  let r = rhandle handler 
   (fun () ->
     for i = 1 to 5 do
       let v = rraise (Foo i) (fun e -> try raise e with Foo_r1 x -> x) in
       let () = Printf.printf "Resumed Foo1 with %b\n" v in
       let v = rraise (Foo (100 +i)) (fun e -> try raise e with Foo_r2 x -> x)
       in Printf.printf "Resumed Foo2 with %s\n" v
     done;
     for i = 65 to 100 do
       let v = rraise (Bar (char_of_int i)) 
               (fun e -> try raise e with Bar_r x -> x)
       in Printf.printf "Resumed Bar with %d\n" v
     done;
     assert false
   ) in
  Printf.printf "\nFinal result %g\n" r
;;

Re: [Caml-list] Resumable exceptions in plain OCaml

[Erik de Castro Lopo]

oleg@pobox.com wrote:

> 
> Resumable exceptions are the strict generalization of regular exceptions,
> which lets the exception raising form return a value and so the
> computation may continue. It's the exception handler that decides
> either to abort the exceptional computation or to resume it with a
> particular value. Resumable exceptions are made popular by Common
> Lisp, where they are widely used: http://lambda-the-ultimate.org/node/1544

I read that on LtU and loved the idea.

> We show a conservative and elementary implementation of resumable
> exceptions in OCaml: the implementation is a self-contained 100% pure
> OCaml library; makes no changes to the OCaml system; supports the
> existing style of defining exceptions; is compatible with the ordinary
> exceptions; works in byte- or natively-compiled code; uses the most
> basic facilities of ML and so can easily be translated to SML.

I am simply in *awe* that you managed to add this to Ocaml.

Thanks you.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
C++: The power, elegance and simplicity of a hand grenade.

Re: [Caml-list] Resumable exceptions in plain OCaml

[Christophe Raffalli]

Hi,

may be a little camlp4 would lead to a more natural and readable syntax. 
The idea is nice but the

   rraise (Foo i) (fun e -> try raise e with Foo_r1 x -> ...) looks 
confusing

while

   rraise Foo i with Foo_r1 x -> ...

is much clearer and certainly possible to define in camlp4 ?

Christophe Raffalli

Re: [Caml-list] Resumable exceptions in plain OCaml

[Christophe Raffalli]

Christophe Raffalli a écrit :
>
> Hi,
>
> may be a little camlp4 would lead to a more natural and readable 
> syntax. The idea is nice but the
>
>   rraise (Foo i) (fun e -> try raise e with Foo_r1 x -> ...) looks 
> confusing
>

yet another remark

rraise (Foo i) (function Foo_r1 x -> ... | e -> raise e)

seems shorter, equivalent and more efficient. Am I wrong ?

remark: it seems one very rarely use exceptions as values passed to 
function and matched with normal match ... but this is
completely legal in OCaml !

In fact exceptions in OCaml are one big polymorphic variant type that 
existed before polymorphic variant where introduced ;-)

Christophe Raffalli

Re: [Caml-list] Resumable exceptions in plain OCaml

[oleg]

Christophe Raffalli observed that

> rraise (Foo i) (function Foo_r1 x -> ... | e -> raise e)

"seems shorter, equivalent and more efficient" than 

>   rraise (Foo i) (fun e -> try raise e with Foo_r1 x -> ...) 

that appeared in the posted code.

I agree. In fact, to the best of my knowledge of the OCaml interpreter,
the former is the semantics of the latter -- or, to be even more
precise, the latter reduces to the former in the interpreter. The
reason I chose the latter is: (i) to avoid writing the default clause
"| e -> raise e", but mainly, (ii) to emphasize the similarity between
pattern matching on the value (when invoking a function, for example) and
pattern matching on the exception in the 'try' clause. The duality
seemed irresistible to pass.

> In fact exceptions in OCaml are one big polymorphic variant type that 
> existed before polymorphic variant where introduced ;-)

So true. One of the motivations for the code resumable.ml was to
(ab)use this fact.

Christophe Raffalli also suggested

>    rraise Foo i with Foo_r1 x -> ...
> is much clearer and certainly possible to define in camlp4 ?

I agree again. I specifically wanted to avoid camlp4 in the original
post, for the sake of naked details. Defining the right syntax, and
implementing it with camlp4, was to be the next step.

Re: [Caml-list] Resumable exceptions in plain OCaml

[Dmitry Bely]

On 6/15/06, oleg@pobox.com <oleg@pobox.com> wrote:

> The implementation and illustration code is available at
>         http://pobox.com/~oleg/ftp/ML/resumable.ml

Is your implementation thread-safe? My impression is it doesn't seems to be.

- Dmitry Bely

Re: [Caml-list] Resumable exceptions in plain OCaml

[oleg]

> Is your implementation thread-safe? My impression is it doesn't seems
> to be.

Interaction of dynamic binding and threading is quite an interesting
topic, which has been the subject of several papers (including ours,
which has been just accepted for ICFP). The implementation in
resumable.ml used so-called shallow-binding -- this is the common
technique of implementing dynamic binding in Lisp and Scheme
systems. Alas, it doesn't well generalize to a multi-threading
environment. For multi-threading, a better approach is dealing with
the stack of handlers explicitly, keeping it in the thread-local
storage. Incidentally, this is the approach adopted in Scheme48, which
has a quite an advanced multi-threading system with user-defined
schedulers, channels and software transactional memory.

The best approach, in my opinion, is to `bind' exceptions handlers to
the stack (because the stack is the best `representation' of the
dynamic context). It is very simple (albeit requiring a small bit of C
code in the library of resumable exceptions) to get hold of OCaml's
own exception handlers. Also, we can use delimited continuations to
implement dynamic binding. That too solves all the problems. Alas,
currently delimited continuations are available only for byte code.

In any event, these performance improvement and generalizations will
not change the published interface of resumable exceptions.