functional-programmingschemeprogramming-languagescontinuationscallcc

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

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?

Solution

  • 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.