Tuesday, October 6, 2009

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

4 comments:

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

    This technique has been used in AKCL, KCL, GCL and ECL for several decades now. Sometimes it pays off to read other people's code, you know,

    ReplyDelete
  2. Reading and mimicking other people's code is less fun compared to solving problems on your own.

    ReplyDelete
  3. CLforJava has a similar re-naming mechanism for handling the TOC features. But thanks to ABCL. The FOO example showed up a bug in CLforJava!

    I also agree with Ville. It keeps my brain working and my students thinking and working.

    ReplyDelete
  4. "This technique has been used in AKCL, KCL, GCL and ECL for several decades now"

    ABCL is much younger than ECL and its ancestors, or, for that matter, most other Common Lisp implementations, FOSS and commercial. It simply cannot be compared to those in terms of maturity, although I use it regularly and I find it good enough for my purpose.

    "Sometimes it pays off to read other people's code, you know"

    In general I agree that looking at prior art is often useful, but you have to put things in context. Someone found a rather obscure bug in ABCL (how typical is the test code Erik posted?); Erik tried to understand the cause of the bug; by the time he figured out that it was caused by an erroneous implementation of TAGBODY and BLOCK, he was already more than halfway in solving the bug. He could have stopped to see how n other Lisps do the same thing, but he would have probably spent more time than if he immediately fixed the bug, as he did. In any case, I'm glad to hear that the solution he chose is a well-known one.

    Peace,
    Alessio

    ReplyDelete