callcc

How to interpret (call/cc call/cc)?

I'm familiar with using call/cc to interpret CPS programs in a direct style:

(define (f return)                                                                                                                               
  (return 2)                                                                                                                                     
  3)

(f (lambda (x) x))
=> 3

(call/cc f)
=> 2

I'm also familiar with how (call/cc call/cc) behaves, with ((call/cc call/cc) x) being equivalent to (x x):

((call/cc call/cc) display)
=> #<procedure #2 display>

The outer call/cc calls the argument call/cc with f that represents a continuation

(★ display)

But what continuation does the inner call/cc pass to f, considering that it wasn't called at a source location and was called as "part of a higher-order function"/"a value"?

If it's treated as being evaluated at the source location, intuition tells me it'll reduce similarly to:

((¹call/cc ²call/cc) display)
(²call/cc ¹(★ display))
(²((¹call/cc ★) display) display)
((¹call/cc display) display)
(display ¹(★ display))

which does not match the behavior (display display).

Solution

  • Maybe you're being a bit misled by the Wikipedia page because it only explains continuations by examples, which are too limited to cover your question.

    Every expression has a continuation representing everything that happens afterward. Conventionally we write

    E[ expr ] c

    to say "the meaning of expr with continuation c". Scheme implements a set of rules concerning such meanings. For example

    E[ (+ A B) ] c = E[A] lambda (a) E[B] lambda (b) (c (+ a b))

    The meaning of the Scheme addition of A and B is the meaning of A with a continuation that accepts that value and finds the meaning of B with a continuation that accepts that value, adds both values, and calls the continuation with the result as a parameter.

    Okay. Now we're ready for the definition of call/cc:

    E[ (call/cc F) ] c = E[ (F c) ] c

    That is, the meaning of (call/cc f) with continuation c is the just the meaning of f applied to c with unchanged continuation. I think this answers your question: the continuation isn't altered by call/cc. It's just "exposed" as a parameter.

    (This rule actually leaves stuff out for simplicity. Finding the meaning of F before it's called should be spelled out.)

    So let's look at the case (call/cc call/cc):

    E[ (call/cc call/cc) ] c = E[ (call/cc c) ] c = E[ (c c) ] c

    That is, the meaning of (call/cc call/cc) is the continuation of this expression applied to itself.

    For example, suppose we have ((call/cc call/cc) foo). The continuation here is (lambda (c) (c foo)) (as in the Wikipedia page). So the result will be:

    ((lambda (c) (c foo)) (lambda (c) (c foo))) => ((lambda (c) (c foo)) foo) => (foo foo)

    So if foo is the identity, then so is the overall meaning of the expression.

    I hope this is helpful.