how to understand this continuation?

Question

(let ([x (call/cc (lambda (k) k))])
    (x (lambda (ignore) "hi")))  => "hi"

How can I write the executing steps of this continuation?

Answer 1

The call/cc operator is used to call a given procedure with the current continuation (hence the name call-with-current-continuation). So to understand how it works, we need to know what the current continuation is.

In your program, at the point that the call/cc is executed, the continuation looks like this:

CONT = (let ([x HOLE])
         (x (lambda (ignore) "hi")))

where HOLE is a placeholder for a value to plug in. In other words, the continuation is the remaining computation. You can stick a value into the continuation if you want to progress.

Now, call/cc captures this continuation and passes it to the procedure (lambda (k) k). You can see that this procedure just immediately returns the continuation. So the program reduces to:

(let ([x CONT])
  (x (lambda (ignore) "hi")))

Applying a continuation captured by call/cc replaces the current computation with that continuation plugged with the value you give it. So the application (x (lambda (ignore) "hi")) turns into:

(let ([x (lambda (ignore) "hi")])
  (x (lambda (ignore) "hi")))

and the rest should follow from what you already know about lambdas and application.

Answer 2

In the first line [x (call/cc (lambda (k) k))] we're creating a new continuation which is bound to the k parameter in the received lambda. That k is returned and in turn bound to the x local variable - therefore, x is a continuation.

In the second line, x is called with a single-argument lambda; the argument is ignored and the result of invoking (lambda (ignore) "hi") is "hi", which is finally returned as the result of the continuation. This is equivalent to simply calling:

(call/cc
 (lambda (k)
   (k "hi")))

Answer 3

Why does this expression evaluate to "hi" ?

(let ([x (call/cc (lambda (k) k))])
  (x (lambda (ignore) "hi")))

The first step is to decide what k looks like:

(define k
  (lambda (value)
    (let ((x value))
      (x (lambda (ignore) "hi")))))

We see immediately that this is the same as

(define k
  (lambda (x)
    (x (lambda (ignore) "hi"))))

But, I failed to mention one little detail. If k is ever invoked, it is as if it were invoked in tail position.

So (f (k 3)) for all continuations k built by call/cc is the same as (k 3). That is always a little bit tricky.

So, let's use lambda^ to mean that the function it introduces is to be invoked as if it were in tail position.

(define k
  (lambda^ (x)
    (x (lambda (ignore) "hi"))))

Now we know what k is, we also need to know that returning out of (call/cc (lambda (k) k)) is really using a default.

It should have been written correctly as

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

There is always an implied invocation of k at the top of the body of the lambda expression passed to call/cc.

We know what k is.

So, we know that this must be the same as, (for ease of reading let's turn the x's in the argument position into y's.)

((lambda^ (x) (x (lambda (ignore) "hi")))
 (lambda^ (y) (y (lambda (ignore) "hi"))))

So, we evaluate both positions to functions.

Once we invoke the function in function position, we are done, since it is headed by lambda^ So, we need to know that

((lambda^ (x) (x (lambda (ignore) "hi")))
 (lambda^ (y) (y (lambda (ignore) "hi"))))

evaluates to, substituting for x

((lambda^ (y) (y (lambda (ignore) "hi")))
 (lambda (ignore) "hi"))

and one more step, substituting for y

leads to

((lambda (ignore) "hi") (lambda (ignore) "hi")), which ignores its argument and returns "hi"