Is it theoretically possible to rewrite tagbody in terms of labels?

Question

I have been thinking about how one could implement common lisp's tagbody in a lisp that doesn't provide explicit gotos, but does provide labels.

The reason this interests me is that I want to write a recursive interpreter that supports goto statements that work exactly like in common lisp.

Assuming one had labels available, would it be possible to implement tagbody as a macro written in terms of labels?

Consider this example written in terms of tagbody:

(tagbody
        (go middle)

    start
        (print "start")
        (go end)

    middle
        (print "middle")
        (go start)

    end
        (print "end"))

Now consider this other example written in terms of labels:

(labels
    ((entry-point () (middle))
     (start () (print "start") (end))
     (middle () (print "middle") (start))
     (end () (print "end")))
    (entry-point))

On the surface they seem to do the same thing. Does anyone know if they actually do? Are they really 100% semantically equivalent?

If someone wrote a macro that translates one form to the other, would there be edge cases where a subtle difference might resurface? Things such as different outputs for same inputs, or subtle variable scope differences, or differences in stack unwinding, etc.

Answer 1

If you assume that tail calls are turned into GO TO (which means your code would not be portable CL) then this is theoretically possible, but probably very hard in practice.

The reason it's hard in practice is that you need to handle dynamic state, which would turn into a nightmare. For instance consider

(setf *x* 0)
(tagbody
 start
 (if (> *x* 0)
     (go end)
     (let ((*x* 1))
       (go start)))
 end)

where *x* is a special variable. This fails to terminate. But

(setf *x* 0)
(labels ((start ()
          (if (> *x* 0)
              (end)
              (let ((*x* 1))
                (start))))
         (end ()))
  (start))

which will terminate under the same assumptions.

There are many other bits of dynamic state in the language, such as catch tags, exception handlers, and just lots of other things which you would need to cope with.

It is easier to think of this going the other way: given a call to a function which looks like a tail call, you need to know about what the dynamic state is to know if it really is a tail call. A go essentially forces the 'call' to be a tail call, and thus must be willing to unwind any bits of dynamic state which were established between the go and its target. (I think that in CL you never need to install bits of dynamic state in this case.)