continuation in common lisp by macros -- regarding an implemetation in OnLisp

Question

In On Lisp, p. 267, Paul Graham provides an implementation of continuation passing macros:

(setq *cont* #'identity)

(defmacro =lambda (parms &body body)
  `#'(lambda (*cont* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
  (let ((f (intern (concatenate 'string
                "=" (symbol-name name)))))
    `(progn
       (defmacro ,name ,parms
     `(,',f *cont* ,,@parms))
       (defun ,f (*cont* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
  `(let ((*cont* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

The following code to traverse a tree t2 for each leaf of a tree t1, uses this implementation, and I am wondering what happens when restart is called, especially after when the leaf of t1 changed from A (the first element) to B (the second element). When restart is called, it simply pops a lambda function from *saved*, and that lambda function calls dft-node with (cdr tree) again. But this call is made outside the scope of the outermost =bind, and =bind was responsible for binding *cont*. How is the binding of *cont* introduced by the outer =bind still in scope, then?

(setq *saved* nil)

(=defun dft-node (tree)
    (cond ((null tree) (restart))
          ((atom tree) (=values tree))
          (t (push #'(lambda () (dft-node (cdr tree))) *saved*)
             (dft-node (car tree)))))

(=defun restart ()
    (if *saved*
        (funcall (pop *saved*))
      (=values 'done)))

(setq t1 '(a (b (d h)) (c e (f i) g))
      t2 '(1 (2 (3 6 7) 4 5)))

(=bind (node1) (dft-node t1)
  (if (eq node1 'done)
      'done
    (=bind (node2) (dft-node t2)
      (list node1 node2))))

The last form expands to

(let ((*cont* (lambda (node1)
                (if (eq node1 'done)
                    'done
                    (let ((*cont* (lambda (node2)
                                    (list node1 node2))))
                      (dft-node t2))
  (dft-node t1))))))

This produces (a 1). According to Graham, subsequent calls to restart should produce (a 2), and so on, up to (a 5), and then subsequent calls should produce (b 1), (b 2), and so on, until finally (g 5):

> (let ((node1 (dft-node t1)))
    (if (eq? node1 ’done)
        ’done
        (list node1 (dft-node t2))))
(A 1)
> (restart)
(A 2)
…
> (restart)
(B 1)

After (a 1), the binding of *cont* established by let should no longer be in place. How do subsequent calls to restart these values? Is the scope of let still applied to a separate call to restart? What is going on here?

Piccoloist

Your interpretation that this doesn't make much sense is absolutely right. Graham notes later on that this doesn't work if *cont* is declared as a special (i.e., dynamically scoped) variable; *cont* needs to be lexically scoped. However, there are no lexically scoped global variables in Common Lisp, and his assumption that (setq *cont* …) makes one is just wrong. I've updated my answer to reflect this, and I now better understand your question. – Carbonari

However, there are no lexically scoped global variables in Common Lisp This part is true. Common Lisp doesn't have global lexical variables. and his assumption that (setq *cont* …) makes one is just wrong. I was incorrect about this. On Lisp slightly predates the specification of Common Lisp, so Graham didn't have a the ANSI Common Lisp specification to work against. The assumption doesn't hold for Common Lisp, but that does not mean that Graham was incorrect in making that assumption in On Lisp. – Carbonari

Answer 1

On Lisp slightly predates Common Lisp, so there are some incompatibilities

On Lisp was written before Common Lisp had actually been solidified as a language, so there are some incompatibilities between the code that appears in On Lisp and Common Lisp. The CLiki entry on On Lisp notes that these continuation passing macros are actually one of the places where there's an incompatibility (emphasis added):

When defining continuation-passing macros (p. 267) Paul Graham seems to be assuming that cont global variable has lexical scope. This contradicts Common Lisp standard. With present day Common Lisp implementations, the aforementioned macros just don't work. Also, this issue can be very confusing for newcomers. Suggested solutions for fixing the macros are (note that #'values is used instead of #'identity - according to Paul Graham's Errata):

• emulate lexically scoped global variable cont using symbol-macro that can be shadowed by let or lambda:
  (defvar actual-cont #'values)
  (define-symbol-macro *cont* *actual-cont*)
• just omit (setq *cont* #'identity) and call "top-level" continuation-passing function as (=somefunc #'values ...)
• …

That's a pretty short description of the problem, and it's worth looking into a bit more, to help any newcomers who come across it in the future. It may also be helpful to see other discussions of this same issue, including:

• Page 268 of <On Lisp>... A comp.lang.lisp thread from 2006 in which a user asks about the difference between (setq *cont* …) and (defvar *cont* …). In this thread, people note that On Lisp predates ANSI Common Lisp.

What's actually happening?

Since (=bind …) expands to (let ((*cont* …)) …), you're absolutely right in that, if *cont* is a special variable (i.e., with dynamic extent), then once you're outside of that let, the original binding of *cont*, which is identity is what should be in place for calls to restarts. If *cont* is declared special, then you get the following behavior:

CONTINUATIONS> (=bind (node1) (dft-node '(a (b (d h)) (c e (f i) g)))
                 (if (eq node1 'done)
                     'done
                     (=bind (node2) (dft-node '(1 (2 (3 6 7) 4 5)))
                       (list node1 node2))))
(A 1)
CONTINUATIONS> (restart)
2
CONTINUATIONS> (restart)
3
CONTINUATIONS> (restart)
6
CONTINUATIONS> (restart)
7
CONTINUATIONS> (restart)
4
CONTINUATIONS> (restart)
5
CONTINUATIONS> (restart)
B
CONTINUATIONS> (restart)
D

This makes sense, because after getting (a 1), *saved* contains two functions. The first is one that will continue traversing the numeric tree on the next branch, and the *cont* that will be called is the global one, #'identity, since we're now outside of the =bind form. That's why we get 2, 3, … as results. The second function in *saved* at this point is the one that will continue traversing the alphabetic tree at B.

The reason that we don't get a bunch of lists (a 1), (a 2), …, (b 1), etc., above is that we (reasonably) assumed that *cont* is special, i.e., dynamically bound. It turns out that Graham intends for *cont* not to be special; he wants it to be a global lexical. From On Lisp, page 268:

It is by manipulating *cont* that we will get the effect of continuations. Although *cont* has a global value, this will rarely be the one used: *cont* will nearly always be a parameter, captured by =values and the macros defined by =defun. Within the body of add1, for example, *cont* is a parameter and not the global variable. This distinction is important because these macros wouldn’t work if *cont* were not a local variable. That’s why *cont* is given its initial value in a setq instead of a defvar: the latter would also proclaim it to be special.

On Lisp slightly predates Common Lisp, so this wasn't necessarily incorrect at the time of writing, but Common Lisp doesn't actually have global lexical variables, so it's not the case that using (setq *cont* …) at the top-level will necessarily create a global lexical variable. In Common Lisp, the exact results are unspecified. Some implementations will treat it like a global lexical, others will assume that you meant defparameter or defvar, and you'll end up with a global special variable. As Graham notes, that won't work. It sounds like you've got an implementation that does the latter, so things don't work.

Some implementations will actually complain about his code. SBCL, for instance, rightly complains at (setq *cont* …), printing "warning: undefined variable: CONTINUATIONS::*CONT*", and issues a style warning when *cont* is used that it is "using the lexical binding of the symbol (CONTINUATIONS::*CONT*), not the dynamic binding, even though the name follows the usual naming convention (names like *FOO*) for special variables."

What's supposed to happen?

To understand how this is supposed to work, it's probably easier to look at a simpler implementation that doesn't have all the plumbing that's in the On Lisp version:

(defparameter *restarts* '())

(defun do-restart ()
  (if (endp *restarts*) nil
      (funcall (pop *restarts*))))

(defun traverse-tree (k tree)
  (cond
    ((null tree) (do-restart))
    ((atom tree) (funcall k tree))
    (t (push (lambda () (traverse-tree k (cdr tree))) *restarts*)
       (traverse-tree k (car tree)))))

Here we don't hide any of the continuation passing mechanism or the *restarts* list. With this, we get this behavior:

CL-USER> (traverse-tree 'identity '((1 2) (3 4)))
1
CL-USER> (do-restart)
2
CL-USER> (do-restart)
3
CL-USER> (do-restart)
4
CL-USER> (do-restart)
NIL

We can recreate the multiple-list traversal one, too, and I think we get the results that you were expecting:

CL-USER> (let ((k (lambda (num)
                    (traverse-tree (lambda (alpha)
                                     (list num alpha))
                                   '(a (b) c)))))
           (traverse-tree k '((1 2) 3)))
(1 A)
CL-USER> (do-restart)
(1 B)
CL-USER> (do-restart)
(1 C)
CL-USER> (do-restart)
(2 A)
CL-USER> (do-restart)
(2 B)
CL-USER> (do-restart)
(2 C)
CL-USER> (do-restart)
(3 A)
CL-USER> (do-restart)
(3 B)
CL-USER> (do-restart)
(3 C)
CL-USER> (do-restart)
NIL

The difference here is that there are no references to *cont* that change meaning once we leave the scope of the let that bound the continuation for us.

In my opinion, a better implementation would simply use a normal lexical a variable to store the continuation (sort of like k above, but probably with a name produced by gensym), and would just require that "calls to continuation passing functions must ultimately be wrapped in a =bind that defines the outermost continuation.

Carbonari

There are not many implementations which treat (setq var ...) as doing a special declaration for a new variable. CMUCL (and Scieneer CL) is known for this. But that can be switched off. See ext:*top-level-auto-declare*. I would always turn that off. Generally there is a lot of undefined and stuff in CL, but real implementations make a choice: TCO yes/no, Conditions as CLOS, Streams as CLOS, SETQ undefined variable as special or not, default packages, ... – Brigidbrigida

@RainerJoswig Certainly. If more implementations made (setq *cont* …) at the top level do the special declaration, then Graham might not have ended up with a working example. If fewer did, then the OP might not have ended up with a disconnect between the code in a book and the results in the REPL. What I find frustrating in this is not necessarily the use of unspecified behavior, but the use of unspecified behavior where it's so easily avoidable. – Carbonari

I have nothing against creating 'standards' by convention. Common Lisp has way too much undefined behavior in the standard. Implementors should refrain from exploiting this and should provide a robust system with less surprises. I'd either avoid or patch implementations which provide these surprise. – Brigidbrigida

@RainerJoswig I agree about standards by convention. That's why things like the CDR - Common Lisp Document Repository are great. The problem here is that current implementations do different things with top level assignments to undeclared variables, and Graham is (i) assuming that they all do the same thing (no note that "some implementations will do something different"), and (ii) abusing conventions that do exist by using the *...* notation for a global lexical, and (iii) doing (i) and (ii) this when it's easy to avoid the problem altogether. – Carbonari

@JoshuaTaylor Note that On Lisp was published before the ANSI standard. An alternative to requiring the continuation forms to be called within an =bind is to use deflex or a symbol macro to portably implement the current semantics. – Smudge

@Smudge Oh, that is a good point. I think I'd mentally conflated his ANSI Common Lisp and On Lisp. That does probably excuse this incompatibility. Some sites mention On Lisp as a Common Lisp book, but that's clearly not the case; Common Lisp wasn't around just yet. The CLiki page about On Lisp calls it a Common Lisp book, but explicitly calls out the issue with these continuation passing macros! I'm going to tone down some of my (not entirely mertited) criticism. – Carbonari

Hi, I still cannot understand what is happening if Graham's assumption is correct. – Piccoloist

And 1 more confusion when Graham said "=bind, is intended to be used in the same way as multiple-value-bind. It takes a list of parameters, an expression, and a body of code: the parameters are bound to the values returned by the expression, and the code body is evaluated with those bindings."; I cannot see the binding directly from the macro definition itself. Does this only happens when =values come in? – Piccoloist

@Piccoloist About your first comment: do you mean the assumption about the that *cont* will not be a special variable because it is assigned with setq rather that declared with defvar? – Carbonari

@Piccoloist The implementation of =bind would expand code like (=bind (a b c) expr body...) into (let ((*cont* #'(lambda (a b c) body...))) expr). The intent is that *cont* will eventually be called with three values, and because the parameter list of *cont* is (a b c), those three values will be bound to a, b, and c, and then the body will be evaluated in the scope of those bindings. So (=bind (a b c) expr body) behaves very much like (multiple-value-bind (a b c) expr body). You're right, though, that if there are mutiple variables, then the expr should – Carbonari

@Piccoloist (eventually) end with (=values ...). – Carbonari

@Joshua Taylor for the first part, I just want to know what Graham expected when he wrote the book, especially when the result change from (A 5) to (B 1). I just wonder at this moment if the cont is the lambda function created by the first =bind or by the second if his assumption was correct – Piccoloist