(call/cc call/cc) and friends

To track exactly what this does, we'll write v@(...) to name the continuation around that expression, and we'll write k@v to represent that continuation. Then

   a@(call/cc call/cc)
=> a@(call/cc k@a)
=> a@(k@a k@a)
=> a@k@a

So the expression (call/cc call/cc) “extracts” the continuation at the point where it is executed. What happens if we apply this continuation?

   (a@(call/cc call/cc) x)
=> (k@a x)
=> (x x)

So it turns out that ((call/cc call/cc) x) is the self-application (x x).

But fascinatingly, (call/cc call/cc) is itself the self-application of a function: call/cc. So (call/cc call/cc) is equivalent to ((call/cc call/cc) call/cc).

So some of the larger trees of call/cc share the behavior of (call/cc call/cc). What about (call/cc (call/cc call/cc))?

   a@(call/cc (call/cc call/cc))
=> a@((call/cc call/cc) k@a)
=> a@(k@a k@a)
=> a@k@a

Thus, like the other three-element tree, (call/cc (call/cc call/cc)) extracts its own continuation. (call/cc call/cc) is a fixed-point of call/cc. (I explore the symmetric idea of “xifed points” in another post.)

What if we continue this train of thought and build greater trees of calls to call/cc?

    (a@(call/cc call/cc) (call/cc call/cc))
=> ((call/cc call/cc) k@a)
=> (k@a k@a)
=> ((call/cc call/cc) k@a)

The self-application of self-application is a classic infinite loop. Here we recreate, bouncing between continuations.

We can divide trees of call/cc into three classes to describe their behavior. call/cc alone has a behavior we will call C. The self-extraction behavior of (call/cc call/cc) we’ll call E. And the infinite loop we’ll call ⊥.

Applying ⊥ on the left or the right is an infinite loop, since Scheme is a strict language. We’ve also determined that E applied to itself is ⊥, and applied to C on either side is E. We can summarize this in a table for the binary operation (x , y) ↦ (x y):

It's clear from this that if a tree's behavior is not looping forever, there aren’t that many choices for this tree. Any interior node of your tree cannot have both the function and the argument slot being applications. But if at each interior node only one of those two slots is an interior node, you always end up with the E behavior.

We can write a simple function to compute the behavior of a tree of calls to call/cc:

data CallCCTree = CallCC | Application CallCCTree CallCCTree
data Behavior = CallCC | Extract | Loop

reduce :: CallCCTree -> Behavior

Implementing this function is a simple encoding of the table of rules.

reduce CallCC = CallCC
reduce (Application CallCC CallCC) = Extract
reduce (Application CallCC _) = reduce _
reduce (Application _ CallCC) = reduce _
reduce (Application _ _) = Loop

We’ve discovered that this set of three behaviors has a (kind-of) natural binary operator. Perhaps this operator satisfies some interesting properties?

It is commutative, as is evident from the table.

It is not associative, since ((call/cc call/cc) (call/cc call/cc)) and (call/cc (call/cc (call/cc call/cc))) are different.

It does not have an identity, because the operator never returns C.

It does have a zero, looping.

So it this operator doesn't seem to form a nice mathematical structure, which is a pity. But then, aren't delimited continuations the one true continuation operator?

Edit: Thank you James Wilcox! noloop had a subtle bug. The order of two cases was swapped, and didn't properly handle (* *).

Edit: Previous versions of this post distinguished a “self-application” and an “extraction” behavior. They were in fact the same behavior.

Edit: Siyuan Chen clarified how the a@ annotation at the beginning of this section behaves.