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.

7 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.

Anonymous said...

kbob, you're unlikely to get a chance to restart from an exception in Scheme. MIT Scheme is the only Scheme variant that supports non-unwinding exceptions and restarts, that I'm aware of.

You can kind of emulate unwinding exceptions by using continuations, but they're not the same thing, since the stack unwinds, and then you UN-unwind the stack by calling the continuation. When the stack unwinds, any DYNAMIC-WIND unwind handlers get called, which can lead to the state being different when you call the continuation than it was when the exception was thrown.

In Common Lisp, conditions can be handled before UNWIND-PROTECT cleanup forms get executed.

vzq said...

Interesting. So in a condition system, two things are needed.
Some code in the "handle" block of the caller:
throw new UseValRestart("the default value");
And some code in the "resume catch" block of the callee:
return r.getVal();

It seems to me that conditions can be trivially implemented in any language that only supports non-resumable exceptions.

Instead of the "handle" block in the caller, we'd write this:
the_global_function = function() { return "the default value"; }
And in the callee, we'd just replace the
throw new NoValException();
by
if (the_global_function == null)
throw new NoValException();
else
return the_global_function();

Of course, in the general case it's not that simple. If we want to support multiple handlers among the call stack, we'd need the_global_function to be a stack of functions instead. And we need to set the_global_function back to null when the caller returns.
The value of conditions seems to be that they make invisible this global function circuitry.

But would we often need such a system? Sometimes we don't need multiple handlers. In that case, the "no condition" rewritten code seems overall simpler and shorter.
And maybe in some cases we could even just pass the function as a parameter instead of as a global.
In other cases yet, we could simplify further and eliminate the "if (the_global_function == null)", or move it into the handler function.

In conclusion, from reading only this post, I'm not really convinced how useful conditions are in practice, compared to just non-resumable exceptions.

It also seems that the API of every function would be more complex in a language with conditions.
In a language with exceptions, I have to know what exceptions are thrown by what I call.
In a language with conditions, I have to know what exceptions are thrown, and whether they are resumable, and in how many ways I can resume them, and what exceptions I need to throw to make them resume.