Understanding cl-cont semantics without thinking about CPS

Understanding the way that cl-cont transforms forms is one way to understand the sometimes counterintuitive behavior of that code. However, the difficulty of dissecting the meaning of code written in continuation-passing style is one of the major reasons that we use a CPS transformer at all instead of writing it out manually.

As a cl-cont user, you may find it easier to understand a behavior model that removes consideration of CPS entirely. After all, CPS is only the implementation method; the goal is to think of the code as "continuable".

Understanding first

To follow along with the behavior model of cl-cont, you should be familiar with dynamic context (such as that established by unwind-protect), lexical context, and the behavior of full continuations such as you would find in Scheme.

Understanding "ordinary" continuations is especially important, because cl-cont's behavior is more complex than full continuations, and you will be lost without preexisting knowledge of what they are.

Defining some terms

First, a continuation, unless otherwise qualified, is always a first-class continuation—a function that, when called, returns its arguments as values to the place where the call/cc call that created the continuation was called. This is just to be clear that I hardly ever mean something abstract when I say "continuation".

The macro with-call/cc introduces a lexical continuable context for the forms lexically contained within it. We will refer to this so often that I will call it LCC henceforth to avoid confusion. For all current purposes, it only matters whether code exists within any LCC, so you can think of "LCC-ness" as a flag on all code. We also say that any code not within an LCC is in an LNCC (lexical non-continuable context). We will define more rules for determining whether code is in an LCC later.

Entering an LCC at the beginning creates a dynamic continuable context or DCC. Understanding DCC behavior is the key to understanding cl-cont. Unlike LCC, you can have multiple distinct DCCs active at any time, possibly even sharing code, just as one function calling mapcar doesn't preclude you from doing so. All code not executing within a DCC is executing within a DNCC (dynamic non-continuable context).

Lexical continuable contexts

As I have said, with-call/cc introduces an LCC. This is an implicit progn. A few convenient macros, such as lambda/cc and defun/cc, wrap their non-cc counterparts with with-call/cc. Within this form, an LNCC can be inserted with the macro without-call/cc. The pseudo-function call/cc also implies a without-call/cc around its sole argument. Within any LNCC, including the implicit one around every program, further LCCs may be introduced with with-call/cc.

There are some cases where you might think that an LCC is there or doesn't matter, where it actually does. In this code:

(defun x ()
 (with-call/cc
   1 2))

The LCC only contains the 1 and 2 forms, not the function entry and function exit. Therefore, calling X from any code will result in first executing code in an LNCC, then some LCC code, then some LNCC code. The importance of this distinction will become clear once we start discussing DCCs. To solve this, move the with-call/cc to outside the defun, or use the equivalent defun/cc convenience macro.

A similar situation holds for this code:

(lambda () (with-call/cc 3 4))

Calling this function is the same as calling X above, and the same solutions apply.

One final area of confusion may be:

(with-call/cc
 (without-call/cc
   (with-call/cc 5 6)))

This is not a smooth contour of an LCC; the without-call/cc always creates an LNCC, even if a new one is created immediately therein.

Basic DCC execution

Entering any LCC from a DNCC, by either calling a function created or defined in an LCC or simply evaluating a with-call/cc form, creates a DCC. Upon creation, beyond the usual frame info, one property is captured and saved permanently for that DCC: the exit point. Consider this code:

(defun/cc bob ()
 (cons 4 2)
 :bob)
(defun/cc slack ()
 (bob)
 :slack)
(defun moo ()
 (bob)
 (slack))

Calling bob in moo creates a DCC whose exit point is the code that returns the keyword :bob. Calling slack in moo creates another one whose exit point is returning :slack. The call to bob within the call to slack does not create a new DCC, or even alter the existing one! Whether calling bob creates a new DCC depends on the nature of the calling code.

While in a DCC, calling a function defined in an LNCC suspends that DCC. That happens in bob above when calling cons, which, like all CL standard functions, is defined in some LNCC. Whether the compiler optimizes away the cons is irrelevant to our semantic model. When the function returns, the same DCC is resumed; as such, the cons above destroys neither DCC's exit point information.

The function rule sounds like a special case, but it is really just a subcase of the continuation case. Invoking a continuation enters the DCC in which it was created. In cl-cont, calling LNCC functions is handled by grabbing the continuationand invoking it with the function's result after it finishes.

After exiting a DCC, the only way to reenter it is to invoke one of its continuations. Calling a function defined therein only creates a new DCC delimited by that function's body.

Finally, a point about call/cc that will surprise you if you are used to Scheme: Invoking call/cc exits the DCC, returning the values returned by the function you gave it. You are, of course, free to simulate Scheme behavior by invoking the continuation from right within that function.

Strange exit point behavior

This may seem a little surprising:

(defvar *cc*)
(defun/cc foo ()
 (let/cc cc (setf *cc* cc) 'saved)
 'foo)

(defun/cc bar ()
 (foo)
 'bar)

(progn
 (foo) ; ⇒SAVED
 (funcall *cc*) ; ⇒FOO
 (bar) ; ⇒SAVED
 (funcall *cc*) ; ⇒BAR
)

The important thing to remember is that it doesn't matter at all what context you invoke a continuation in from a DNCC; you always get the exit point of the continuation's DCC.

Nested DCCs

Certain code looks like it should really be resuming something that it actually can't, and it has to do with nesting DCCs. Here's what I mean:

(let (keep-going list)
 (progn (with-call/cc
          (setf list (mapcar (lambda (n)
                               (let/cc k (setf keep-going k) 42))
                             (list 1 2 3 4 5))))
   (dotimes (n 5)
     (funcall keep-going (+ n 6)))
   list))

If mapcar was defined in an LCC, you would get the result you expect, (6 7 8 9 10). What you expect is that for each element in (1 2 3 4 5), let/cc saves and suspends the continuation.. The first time, the dotimes would be entered, and the next four times it would do another iteration, each time invoking the continuation saved above. In the first case, the 42 would be delivered to the first progn location (and discarded), and the further four times to the implicit progn in dotimes (and discarded).

Instead, you get the result (42 42 42 42 42). Why?

The mapcar throws a kink in. Consider that when mapcar is running, the enclosing DCC is suspended, because mapcar is defined in an LNCC and therefore creates a DNCC by being called. Now, when it calls the LCC-defined function passed to it, a new DCC is created each time. In each of these a continuation is saved and 42 is returned, creating the contents of the list, but only the last saved continuation is ever seen by the dotimes. When mapcar finishes, it resumes the enclosing continuation and it finishes execution before the dotimes can even start.

Now that dotimes has started, it is resuming the DCC solely delimited by the function passed to mapcar. As you can see, the exit point of that function is to return whatever was passed to the continuation. Accordingly, if you wrap the funcall above with a print, you'll see it print 6, 7, 8, 9, and 10, in order.