Home

Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml

Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml, by David Teller, Arnaud Spiwack, Till Varoquaux:

This is the year 2008 and ML-style exceptions are everywhere. Most modern languages, whether academic or industrial, feature some variant of this mechanism. Languages such as Java even have a degree of out-of-the-box static coverage-checking for such exceptions, which is currently not available for ML languages, at least not without resorting to external tools.

In this document, we demonstrate a design principle and a tiny library for managing errors in a functional manner, with static coverage-checking, automatically-inferred, structurally typed and hierarchical exceptional cases, all of this for what we believe is a reasonable run-time cost. Our work is based on OCaml and features simple uses of higher-order programming, low-level exceptions, phantom types, polymorphic variants and compile-time code
rewriting.

Exhaustively checked, user-friendly exception handling was a bit of an open problem for awhile. As the paper details, languages supported either cumbersome, exhaustively checked polymorphic exceptions, as in Haskell, or we had unchecked easily extensible monomorphic exceptions, as in ML, or we had checked, extensible exceptions using a universal type as in Java.

Supporting exhaustively checked, easily extensible polymorphic exceptions seemed quite a challenge, which this paper solves using monadic error handling and nested polymorphic variants. The paper also gives a good overview of current techniques of exception checking in OCaml, ie. ocamlexc.

The performance of such exceptions is understandably lower than native exceptions, given all the thunking and indirection that monads entail. The authors attempt various implementations and test their performance against native exceptions. Ultimately, monadic error management seems acceptable for actual error handling, but not for control flow as native exceptions are sometimes used in OCaml.

One interesting extension is to consider how efficient the implementations would be given more sophisticated control flow operators, such as continuations, coroutines, or delimited continuations, or whether native exceptions can be salvaged using a type and effects system in place of monads.

By naasking at 2008-07-11 15:16 | Functional | Implementation | Software Engineering | other blogs | 20613 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Exceptions and control flow

While in the ML world using exceptions as a control flow mechanism is widely accepted, it is not in the C++ world.

Exceptions are meant for exceptional situations, such as errors you do not know how to handle without context. Given that assumption, it is possible to optimize exceptions in a way that there is absolutely zero overhead in the case where an exception isn't raised.

AFAIK C++ is the only language that implements such an exception system (except on Windows, the Microsoft Exception ABI is usually followed instead) and is much more efficient than Java/C# or (Ca/S)ML/Haskell.

I know that a lot of people are avoiding exceptions in Java/C# because they add an important runtime cost even when they're not raised.
So really, what's the point of introducing something that's even more costly, and that adds basically nothing?

C++ exceptions are already type-safe, hierarchical (inheritance), lightweight (only require simple runtime type identification) and extremely efficient, and much more than these.
Making them polymorphic is fairly difficult though, since the type of the exception being caught can only be known at runtime.
That means the whole type structure of the object must be available at runtime, hardly lightweight.

By Mathias Gaunard at Sun, 2008-07-13 15:34 | login or register to post comments

I doubt C++ exceptions are

I doubt C++ exceptions are more efficient than OCaml exceptions. When not using exceptions, OCaml incurs no cost. Entering a try-catch expression incurs a single pointer update IIRC. How could C++ exceptions possibly be more efficient than that?

SML/NJ also has efficient exception handling because programs are in CPS form. Arbitrary control flow operators are trivial in CPS programs.

By naasking at Sun, 2008-07-13 16:21 | login or register to post comments

Almost free when not used

How could C++ exceptions possibly be more efficient than that?

The way C++ exceptions are usually implemented, no explicit catch frame is built during execution. When an exception is thrown, the runtime will walk the stack and look up the program counters in a static table generated by the compiler.

This makes exception processing quite expensive, especially with modern ABIs without a frame pointer - even walking the stack requires the use of special unwind tables, similar to debugging information. I suppose the cost would be proportional to the number of frames traversed (call depth) as well.

On the other hand, if no exception is thrown, try-catch statements are very cheap. Not entirely free, as the compiler must still take into account the possibilities of control flow in more ways - this can influence register allocation and fill/spill decisions.

By Mattias Engdeg at Mon, 2008-07-14 10:27 | login or register to post comments

Is that really so?

Correct me if I am wrong, but last I looked none of the major compilers (Visual Studio, gcc) implement exceptions that way. Instead, they do it the old-fashioned way, by adding prologues and epilogues to functions. Not terribly expensive, but not free even in the no-exception case.

By tomlu at Mon, 2008-07-28 14:03 | login or register to post comments

It depends on the platform

It depends on the platform and ABI. You are quite correct in that the method to use is not dictated by the C++ language, and gcc can emit "old-fashioned" setjmp/longjmp-based exception handling code if configured to do so. However, more recently designed ABIs seem to prefer the stack unwind based methods, probably on the grounds that exceptions are very rarely raised in practice (because everybody know that it is expensive, and so on).

By Mattias Engdeg at Sun, 2008-08-24 15:36 | login or register to post comments

is zero overhead really true?

[[it is possible to optimize exceptions in a way that there is absolutely zero overhead in the case where an exception isn't raised.]]

Sure there's zero "maintenance" cost, but if you have A followed by B, and as an optimisation doing B before A would be better this can be a problem if A raise an exception: so either the compiler must leave B after A or must ensure that B is 'undoable' which has a cost usually (and add the undo code in the exception handler which is free when no exception is raised).
So exceptions do have a cost, even when there is no maintenance cost I think..

By renox at Mon, 2008-07-14 13:12 | login or register to post comments

There is atleast one more

There is atleast one more option, you can define the semantics of the program to be one of the possible exceptions from it. Without this you are not allowed to move around arithmetic computations in the program since they might divide by zero, and this might be hidden by a non-terminating block that you move them into so they never get executed.

By Peter A Jonsson at Mon, 2008-07-14 13:42 | login or register to post comments

Java exceptions are cheap

AFAIK C++ is the only language that implements such an exception system (except on Windows, the Microsoft Exception ABI is usually followed instead) and is much more efficient than Java/C# or (Ca/S)ML/Haskell.

Java exceptions are very cheap. See John Rose's blog for more information. In a nutshell, try-catch blocks cost mostly nothing and the cost of throwing an exception is extremely cheap - it's only the cost of constructing a stack trace that is expensive. You can avoid that cost if you're willing to use any of several techniques to skip calling Throwable.fillInStackTrace. The JVM languages group has some good discussion about using the technique for non-local control flow in non-Java languages on the JVM.

I don't think this can be said for most C++ implementations, where I'm pretty sure that unwinding the stack due to an exception is typically pretty expensive.

By rreyelts at Fri, 2008-07-25 05:48 | login or register to post comments

Connection refused

Was this paper pulled from the server? Anyone has a copy?

By Denis Bredelet -jido at Wed, 2008-07-16 13:30 | login or register to post comments

Works4Me

Works4Me

By Chris Rathman at Wed, 2008-07-16 17:06 | login or register to post comments

Thanks for the update

Seems good now.

By Denis Bredelet -jido at Wed, 2008-07-16 17:39 | login or register to post comments