Monday, May 31, 2004

Just don't kill any of your ancestors.

I've been playing around with functional programming lately, and I learned something completely wacky. Exceptions in a lazy functional language are weird.

Consider the following function written in classic functional style (and Haskell syntax).

inverses [] = []
inverses (x:xs) = ( (1/x) : inverses(xs) )

This function takes a list and returns a list of equal length with each element inverted. (In Haskell, (x:xs) is a list in which x is the first element and xs is the rest of the list.)
Suppose that division by zero throws an exception. We can expect inverses [3 5 10 4 0 8] to throw because the fifth element is a zero. If we don't want our program to crash and burn, we need to handle the exception somehow.
Perhaps we decide to handle it outside of inverses itself. We wrap it in a "safer" version:

safe_inverses y = try
inverses y

This function tries inverses y, but if that fails for any reason, it returns an empty list instead. (Not a particularly good strategy, but good enough for our purposes.) (And no, we're not to the weird part yet. Bear with me.)
Now suppose we call safe_inverses and pass the result on to some other function foo:

foo (safe_inverses [3 5 10 4 0 8])

Since there's a zero in the list, an exception is thrown and caught and foo gets the emtpy list, right? Not necessarily. It depends on what foo does. In a lazy functional language (such as Haskell), all work is deferred for as long as possible. In our example, that means that inverses doesn't return its whole result at once: it returns a list with the first element (1/3) plus a magic thingy that knows how to generate the rest of the list. And that magic thingy (it's called a "thunk") is only called if the rest of the list is needed. Notably, if the rest of the list is never needed, the thunk is never used.
In our example, the zero is not the first element of the list. That means that inverses doesn't throw the exception right away. It returns the partial list (starting with 1/3), and does not trigger the catch clause. The partial list "escapes", and makes it all the way to foo. If foo only uses the first element, then no exception is thrown, despite the sinister presence of the zero in the list.
Here comes the weird part. Suppose foo does use the whole list. As it iterates through the elements, thunks are firing behind the scenes to produce values lazily. At some point, one thunk is going to divide by zero, and throw an exception.
But wait! We've "escaped" the try/catch block. We're outside it, right? It's too late for us to handle the exception, isn't it?
Maybe not. If the language is implemented in a certain way, time travel can occur. Here's how.
foo may be outside the try/catch block, but some of those thunks firing behind the scenes are not. Each thunk knows which exception handlers are active for that particular thunk. If one of those thunks throws an exception, it becomes clear that we should have been caught by the try/catch block. And if the language is purely functional, it's trivial to discard all the work we did "between then and now", and go back to the catch clause that we should have taken. We warp back to the catch clause, and so foo does get the empty list.
A disclaimer: this presumes a lazy language with support for continuations. Haskell is lazy, but doesn't support continuations--at least, not at this level. Scheme supports continuations, but is not lazy--at least, not at this level. So I don't know of any language with exceptions that work as described above. (If anybody else does, let me know.) But I'm told it's possible, and I'm working on it in my own toy language.