why is `(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")` evaluated to "HEY!"?

Question

I am reading The scheme programming language and seeing this example in continuation section:

(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!") => "HEY!"

I cannot figure out why this expression evaluating to "HEY!"

According to the CSE 341 lecture notes: (call/cc expr) does the following:

1. Captures the current continuation.
2. Constructs a function C that takes one argument, and applies the current continuation with that argument value.
3. Passes this function as an argument to expr --- i.e., it invokes (expr C).
4. Returns the result of evaluating (expr C), unless expr calls C, in which case the value that is passed to C is returned.

So, in this example (((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!") => "HEY!"

1. the current continuation of call/cc is

   (lambda (v)
      ((v (lambda (x) x)) "HEY!")
   

2. the constructed function C is

   (lambda (y)
      ((lambda (v)
          ((v (lambda (x) x)) "HEY!")) y))
   

3. invokes ((lambda (x) x) C)

4. returns the result of evaluating ((lambda (x) x) C), which is C itself

Therefore, (call/cc (lambda (k) k)) evaluates to C. The whole expression will be:

(((lambda (y)
  ((lambda (v)
      ((v (lambda (x) x)) "HEY!")) y)) (lambda (x) x)) "HEY!")

i.e. ((C (lambda (x) x)) "HEY!"), which is ("HEY!" "HEY!"). This will result in an exception: Wrong type to apply: "HEY!", meaning applying a non-function value "HEY!".

Where am I wrong?

Answer 1

I'll attempt to break it down.

Starting with

(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")

the result of evaluating ((call/cc (lambda (k) k)) (lambda (x) x)) needs to be a function, and it's called with the argument "HEY!".

(call/cc (lambda (k) k))

calls an anonymous function and passes it a continuation, a special function that when called, will return its argument to where call/cc returns to. The anonymous function just returns that continuation without calling it. Call that continuation kont, and substitute it for the whole call/cc expression:

(kont (lambda (x) x))

That continuation is now called, with an anonymous function that takes one argument and returns it as its argument. That function is thus the result of evaluating the continuation. So basically ((call/cc (lambda (k) k)) (lambda (x) x)) is equivalent to (lambda (x) x). Which is then called with the argument "HEY!", which it then returns.

Answer 2

Here is how I read it, expressed in CPS:

(define (identity& v k)
  (k v))

(define (call/cc& f& k)
  (f& (lambda (v ingnored-k) (k v)) k))

(define (repl-print v)
  v)

(call/cc& identity&
          (lambda (v&)
            (v& identity&
                (lambda (v2&)
                  (v2& "HEY!" repl-print)))))

So the current continuation of call/cc& call is:

(lambda (v&)
  (v& identity&
      (lambda (v2&)
        (v2& "HEY!" repl-print))))

1. The first round, v& is a continuation function that, when called, will pass the value not to its own continuation (ignored-k), but the continuation of call/cc&. Thus the above will be called if v& gets called.

2. v& gets called with identity& as result. Thus the original continuation gets called and this time v& is identity&

3. v& (identity&) gets called with identity& as argument and continuation (lambda (v2&) ...)

4. v2& is identity&and it gets called with "HEY!" and the continuation repl-print

5. repl-print gets called with "HEY!". The text gets shown and the program terminates.

Notice that #1 and #2 ends up calling the same continuation with different values. If it was the same you would have a loop.