Wednesday, April 27, 2011

What's a condition system and why do you want one?

This post attempts to explain how Lisp condition systems surpass ordinary exception handling. Condition systems don't unwind the stack by default and thus allow computations to be restarted, which is a useful tool.

Exception handling
try {
throw new Exception();
catch (Exception e) {
... // handler code
}
Everybody knows what this exception handling code in Java does: the THROW searches for a CATCH clause (a handler) that catches subclasses of Exception, unwinds the stack, and calls the handler code with E bound to the exception object.

At the moment the exception is thrown, the stack looks like this:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // middle stack
  • THROW new Exception()
There's an outside stack that doesn't concern us. The middle stack is the stack between the TRY/CATCH and the THROW, which is actually empty in this example, but usually contains a whole lotta function calling going on.

Before the handler is called, the stack is unwound:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // middle stack
  • THROW new Exception()
When the handler is called, the stack looks like this:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // handler code
Condition systems

Condition systems in the Lisp family are based on the fundamental insight that calling a handler can be decoupled from unwinding the stack.

Imagine the following:
try {
throw new Exception();
} handle(Exception e) {
... // handler code
}
We've added a new keyword to Java, HANDLE. HANDLE is just like CATCH, except that the stack is not unwound when an Exception is thrown.

With this new keyword, the stack looks like this when the handler is called:
  • ... // outside stack
  • TRY/HANDLE(Exception e)
  • ... // middle stack
  • THROW new Exception()
  • ... // handler code
The handler runs inside the THROW statement (Common Lisp would say, during the dynamic extent of the THROW).

For many exceptions it makes sense to simply unwind the stack, like ordinary exception handling does. But for some exceptions, we gain a lot of power from the non-unwinding way condition systems enable.

Restarts

One of the most interesting aspects of not automatically unwinding the stack when an exception occurs is that the we can restart the computation that raised an exception.

Let's imagine two primitive API functions: GETVAL and SETVAL read and write a VAL variable.
Object val = null;
Object getVal() { return val; }
void setVal(Object newVal) { val = newVal; }
Now we want to add the contract that GETVAL should never return null. When VAL is NULL, and GETVAL is called then an exception is raised:
Object getVal() {
if (val == null) throw new NoValException();
else return val;
}
A user of GETVAL may install a handler like this:
try {
getVal();
} handle (NoValException e) { // note use of HANDLE, not CATCH
... // handler code
}
When GETVAL() is called and VAL is null, an exception is thrown, our handler gets called, and the stack looks like this:
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • THROW new NoValException()
  • ... // handler code
As you can see, our handler for NoValException runs, and the exception "isn't over yet", because the stack hasn't been unwound.

Thanks to the non-unwinding nature of condition systems, an application may decide to simply use a default value, when GETVAL is called and VAL is null.

We do this using restarts, which are simply an idiomatic use of non-unwinding exceptions:(1)

We rewrite GETVAL to provide a restart for using a value:
Object getVal() {
try {
if (val == null) throw new NoValException();
else return val;
} catch (UseValRestart r) {
return r.getVal();
}
}
GETVAL can be restarted by throwing a USEVALRESTART whose value will be returned by GETVAL. (Note that we use CATCH and not HANDLE to install the handler for the restart.)

In the application:
try {
getVal();
} handle (NoValException e) {
throw new UseValRestart("the default value");
}
(The USEVALRESTART is simply a condition/exception that can be constructed with a value as argument, and offers a single method GETVAL to read that value.)

Now, when GETVAL() is called and VAL is null, the stack looks like this:
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • TRY/CATCH(UseValRestart r) [1]
  • THROW new NoValException()
  • THROW new UseValRestart("the default value") [2]
The restart at [2] bubbles up, and is returned by the TRY/CATCH for the restart at [1], which means that GETVAL returns "the default value":
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • TRY/CATCH(UseValRestart r)
  • THROW new NoValException()
  • THROW new UseValRestart("the default value")
  • return r.getVal(); // "the default value"

A simple extension would be to offer a restart for letting the user interactively choose a value:
Object getVal() {
try {
if (val == null) throw new NoValException();
else return val;
} catch (UseValRestart r) {
return r.getVal();
} catch (LetUserChooseValRestart r) {
return showValDialog();
}
}
This assumes a function SHOWVALDIALOG that interactively asks the user for a value, and returns that value. The application can now decide to use a default value or let the user choose a value.

Summary

The ability to restart a computation is gained by decoupling calling a handler from unwinding the stack.

We have introduced a new keyword HANDLE, that's like CATCH, but doesn't unwind the stack (HANDLE and CATCH are analogous, but not equal, to Common Lisp's handler-bind and handler-case, respectively).

HANDLE is used to act from inside the THROW statement. We have used this to implement restarts, a stylized way to use exceptions.

I hope this post makes clear the difference between ordinary exception handling, and Lisp condition systems, all of which feature restarts in one form or another.

Further reading:
Footnotes:

(1) This is inspired by Dylan. Common Lisp actually treats conditions and restarts separately.

5 comments:

kbob said...

Most hardware exception mechanisms also decouple invoking the handler from unwinding the stack. And the C/Unix runtime also decouples signal handling from setjmp/longjmp.

So it's not exactly unique to Lisp, though Lisp was probably first to use the idea in a high level language.

As I become more familiar with Scheme, I look forward to finding occasions to restart from exceptions.

Archit said...

Shameless plug restarts in Ruby!!!

http://github.com/archit/restarts

Easy to implement in any language supporting call-cc.

史可 阆 said...

It could be more clear if you kindly also demonstrate how UseValRestart and LetUserChooseValRestart interact with the end user.

Anonymous said...

Java doesn't just unwind the stack. It also executes any protected regions to release locks from synchronized blocks and to make sure finally runs. How would condition handling affect that?

Manuel Simoni said...

Anon: when and if the stack is actually unwound (normally or through a "jump"), "finally" statements are processed as usual.