Struggling with and surviving TAGBODY and BLOCK compilation

At first glance, compilation of TAGBODY and BLOCK forms seems simple: the tags in the TAGBODY are all static and the exit point for the BLOCK is also well defined. Summarizing: no complexities with the dynamic environment of any kind.

However, taking a closer look and adding closures to the picture, things get a little more complicated: GO or RETURN-FROM can mean transfers of control to exit points outside the current function. Consider the snippet below:

(block NIL
  (funcall (lambda () (return-from NIL 3)))
  4)

Apart from the fact that the example is too obvious: the lambda form can be inlined, it demonstrates what I mean by "RETURN-FROM will cause a transfer of control to a non-local exit point": The exit point to jump to is located outside the lambda.

So far, so good: the above existed for a long time in ABCL and is achieved by raising Java exceptions. Now things get more contrived: we'll use a closure created inside a BLOCK form which is part of a recursively called function.

(defun foo (fun)
  (block B
      (if fun
         (funcall fun)
         (foo (lambda () (return-from B :good)))
      :bad))

Now, evaluating (foo nil) will cause the following function calls:

 1: (foo nil)
2:   (foo (lambda () ...)
3:     (funcall (lambda () ...)

To which exit point would you expect the lambda to return? You should expect it to return to the exit point associated with B block from the first FOO call. Now it's becoming clear what's so hairy about compiling BLOCK (and TAGBODY which has the same issue): there are 2 B blocks on the stack, so, which one to return to?

The way this last issue - recursive BLOCK and TAGBODY forms - was solved in ABCL just last weekend was to create a (hidden) variable which gets set to a certain unique value upon entry of the block at run time. Then, any non-local transfer of control uses that block identifier value to find the right block to jump to.

Actually, this solution has a slight advantage for TAGBODY over the pre-existing solution: the old solution checked all symbols in a TAGBODY before concluding the GO wasn't meant for the given tagbody. With the new approach, a single variable test (equality of object pointers) allows checking if the GO is meant for any given TAGBODY or that stack unwinding should continue.

But then there's another issue: closures can be assigned to variables which outlive the extent of the originating block or tagbody. Like the snippet below:

(progn
   (block B
      (setq a (lambda () (return-from B 3))))
   (funcall a))

As indicated above, ABCL uses Java exceptions for non-local transfers of control. Now, if the (funcall a) form would throw a Go exception, regardless of the fact that there's no matching try/catch block, the exception would remain unhandled and the processing thread would exit. This is the situation in ABCL as it existed before last weekend.

Now, the solution to the problem with the recursive function calls has a nice additional benefit. Since there's storage shared between the closure and the BLOCK - they now share a variable - the variable can be used to let the block communicate to the closure that its extent has ended by setting it to a specific value. The GO form can then check for that condition before it throws the actual Go exception, making sure there's always a matching try/catch block. If there's no such block ABCL now generates a call to ERROR, allowing interactive error handling and selection of restarts where it used to unwind the stack to some location which happened to catch the exception - or terminate the thread if that didn't happen. Quite an improvement I'd say.

As a consequence of the changes described above, the code presented in the lisp paste at http://paste.lisp.org/display/88240 - which tests the full requirements of the CL spec - does succeed with today's ABCL (whereas it didn't last week!)...