Scheme, call/cc

Question

So for I am trying to figure out this whole call/cc thing in Scheme. Below is the code I am working with:

(+ 1 (call/cc
  (lambda (k)
    (if (number? k)
        (call/cc (lambda (k) (k (- 1 k))))
        (k 4)))))

So here we start adding the two arguments in the first parenthesis. 1 and the rest which we have to evaluate because of eager evaluation. So we have a call/cc which accepts one arguments, a function, which the call/cc evaluates by calling. (am I right?) And at the same time it holds the rest of what has happened so far in our first parenthesis, namely (+ 1 []), which is the "continuation". (am I right?) So we call lambda k with the continuation as I have just described, (+ 1 []). In the function it then asks if this is a number, which it is not and does the "then". I get "lost" here, what does this second call/cc do? What is (k 4) invoked, to make this whole thing evaluate to 5?

Answer 1

You're pretty close! All of your questions are right, I think.

The function you pass to call/cc takes one argument (k in your example), and it's a way to return a value to the current continuation. k is a function of one argument. When you call that function with a value, that value is returned to and stands in place of the _ in this: (+ 1 _).

So in your example, (number? k) is never true, and the second call to call/cc is never executed. (Even if it were, it would fail with a runtime error where (- 1 k) subtracts a function from 1.) So it actually executes the "else" branch: (k 4), which returns 4 to (+ 1 4) so the result is 5.

Hope that's clear!

Answer 2

call/cc is like setjmp. It defines an exit point that the later code can directly "jump" to, like longjmp does.

It follows a certain protocol for that, so we always write

( .... surrounding code .....
   (call/cc (lambda (k)
      .... inner code which has access to the exit point "k" ....
      )) .... more surrounding code .... )

Under that protocol, the "inner" code executes as usual, but it also has a name, k, in its scope. None of the "surrounding" code has access to it, since it's out of k's scope.

k here is a first-class value (naturally, as it is named). The Scheme run-time system will assign it a continuation of the (call/cc ...) call point, automatically, behind the scenes. For a programmer, we can use it whenever we have access to it.

A continuation is a function of one argument. When that function is called, it will pass its argument on to the continuation's calling context. But since k is a first-class named value, we can pass it around freely. The "inner" code can be as complex as we want, it can call out into other functions defined elsewhere etc. If it passes k as an argument to such external function, it can use it just as well.

Calling k with a value means returning that value into the calling context of the original (call/cc ...) call. Directly. Just like longjmping there (except we can return any value there, not just int).