How are `tagbody` and `go` implemented under the hood in Common Lisp?

Question

How are tagbody and go implemented in Common Lisp? Is it some form of setjmp/longjmp or is there a more elegant way of handling this?

I'm writing a lispy language implemented in C and would like to have something like this.

Pothook

Answer 1

Simplifying Common Lisp's go to other languages goto is, well, too much simplification.

In Common Lisp, go can unwind the stack. For instance:

(tagbody
    (mapc #'(lambda (el1 el2)
              (format t "el1: ~a, el2: ~a~%" el1 el2)
              (when (or (null el1) (null el2))
                (go stop)))
          list1
          list2)
  stop)

If you're implementing Common Lisp in terms of C, then a non-unwinding go may be a regular goto, but an unwinding go requires setjmp/longjmp or equivalent functionality, with proper stack unwinding, followed by a regular goto if needed, i.e. in case the tagged Lisp form is not the C statement or expression after setjmp.

You'll probably want to use the operating system's exception handling, if you can afford the time abstracting it. It may payoff better if you later want to integrate with other languages' features, such as C++ exceptions, and the platform might already have a stack of handlers, thus running unwind-protect clean-up forms automatically up to a certain stack frame.

If you want to keep it portable with minimum effort, you can manage a thread-local stack of setjmp contexts where you longjmp to the most recent context with enough information to keep longjmping up to the right context, running unwind-protect clean-up forms throughout. This way, you may still want to use the platform's exception handling capabilities, but only to setup unwinding frames from/to foreign calls.

Ottavia

Answer 2

From an implementation standpoint, if you're interpreting a Lisp-like program, you might do something a bit like this:

• Upon entering a tagbody, begin a table of destinations. (a map of symbol→address pairs)
• Iterate each form within the tagbody
• if (symbolp this-element), then store the address (a pointer to that form) into the table
• otherwise, (eval this-element) as usual
• When encountering a go form, look up the destination symbol, and (destructively) change your program's "current instruction" pointer to that value. Then, jump to your routine to fetch the next instruction.
• When exiting the tagbody, just discard the destination table.

The destination tables will (ultimately) need to be a stack (referred-to in older Lisp documentation as a "push-down list" or PDL), since you'll search upwards through dynamic scope to find the tag in question. Keep in mind, in Common Lisp, go tags are a separate namespace from variables, functions, classes, et al.

@jlahd is correct, it's effectively identical to a (limited-range) goto in C, but if you're interpreting the code, you'll actually be overwriting the "program counter" pointer with the stored value.

Kweiyang