call cc example racket

Question

I'm analyzing this code regarding the use of call/cc. This function is kind of mystical, and it's quite complicated to fully understand.

I really cannot understand how this code is working. Below is my interpretation.

(define (print+sub x y)
  (display x)
  (display " ")
  (display y)
  (display " -> ")
  (- x y))

(define (puzzle)
  (call/cc (lambda (exit)
             (define (local e)
               (call/cc
                (lambda (local-exit)
                  (exit (print+sub e
                           (call/cc
                            (lambda (new-exit)
                              (set! exit new-exit)
                              (local-exit #f))))))))
             (local 6)
             (exit 2))))

(define x (puzzle))

call/cc is called through

    call/cc (lambda(exit))

and then again through

              (call/cc
                (lambda (local-exit)

The function local is called with parameter 6 which is passed to print+sub as x. But how does the value 2 arrives to print+sub as y?

And the most important part, what is the order in which all these instructions are performed?

Answer 1

Calling (puzzle) sets up a continuation exit such that calling (exit val) is the same as if that call (puzzle) had just returned that val value.

Then the call (local 6) is made. It sets up a continuation local-exit such that calling (local-exit val2) is the same as if that call (local 6) had just returned that val2 value. Of course that return value is ignored, and the next call, (exit 2) would be made next.

Now, after setting up local-exit, the call (exit (print+sub e ...)) is made. It needs to find out the value val3 of (print+sub e ...) first, so it could pass it to the call (exit val3).

print+sub expects two parameters. The call has two expressions which must be evaluated, so the values found, if any, will be passed as x and y to print+sub.

Evaluating e is simple. It is 6.

Evaluating the second expression, (call/cc (lambda (new-exit) ...)), sets up yet another continuation, new-exit, such that calling (new-exit y) is equivalent to returning that y into that slot {y} awaiting it in the call (print+sub 6 {y}).

Then the body of

      (lambda (new-exit)
          (set! exit new-exit)
          (local-exit #f))

is entered. (set! exit new-exit) changes the meaning of any call (exit val) to be from now on the same as if (new-exit val) was called instead.

Now, finally, (local-exit #f) is called. It jumps out of the (local 6) call, immediately returning that #f, which is then ignored. The call (exit 2) is made. It is the same as if the call (new-exit 2) was made. That means returning 2 into that {y} slot, so the call (print+sub e 2) inside (exit (print+sub e 2)) is now performed.

print+sub prints what it prints and returns 4, so that (exit 4) is now called.

Now the crucial tidbit is, what is the value of exit used here? Is it the original exit continuation, or the changed one, new-exit?

Suppose the Scheme standard says that in any function application (foo a1 a2 ... an) foo is evaluated first, then ais are evaluated in an unspecified order, then the functional value is applied to the n argument values just found. This would mean that this exit to be called is the original exit continuation, and so the value 4 is returned as the final value of the original call (puzzle) (this is what really happens in DrRacket).

Suppose the Scheme standard doesn't say this. Then exit could actually be new-exit now. Calling it would thus lead to an infinite loop. This is not what happens in DrRacket.

Indeed if we replace exit with (lambda (v) (exit v)),

           ((lambda (v) (exit v))
                (print+sub e
                           (call/cc
                            (lambda (new-exit)
                              (set! exit new-exit)
                              (local-exit #f))))))))

the code does go into the infinite loop.

---

Continuations are like jump (a GOTO) with a value. When we have some code like ...... (foo) ..... with a normal function foo, when the evaluation of foo ends, the returned value is used further in that code, according to what's written there.

With puzzle used as foo, the evaluation proceeds the same. Scheme attempts to find out the return value of puzzle to use it further in the surrounding code.

But puzzle calls call/cc immediately, so it creates this marker, a GOTO label to go to, so that when / if / deep inside puzzle a call is made to (exit 42), the control jumps to - goes to - that marker, that label, and 42 is used as the return value.

So when deep inside (puzzle) a call (exit 42) is made, it has the same effect as if that call to (puzzle) has just returned with the 42 as the return value into its surrounding code, without going through all the remaining code inside puzzle.

That's how continuations work. A continuation is a marker to jump to, with a value, to be used in the subsequent code as if returned normally by the preceding piece of code.

---

The code can be a bit easier to read with Racket's let/cc, or an equivalent macro:

(define-syntax with-current-continuation    ; let/cc
  (syntax-rules ()
    ((_ c a b ...)
     (call/cc (lambda (c) a b ...)))))

(define (puzzle2)
  (let/cc exit  ; --->>--------------->>------------>>-------------.
    (define (local e)                                            ; |
      (let/cc local-exit  ; --->>----------------------------.     |
        (exit (print+sub e                                 ; |     |
                         (let/cc new-exit  ;  -->>----.      |     |
                           (set! exit new-exit)    ;  |      |     |
                           (local-exit #f))        ;  |      |     |
                                          ;; --<<-----*      |     |
                         )))                               ; |     |
                           ;; --<<-----------------<<--------*     |
      )                                                          ; |
    (local 6)                                                    ; |
    (exit 2))                                                    ; |
            ;; --<<---------------<<------------------<<-----------*
  )

Imagine you're in a debugger and you've placed a breakpoint on the closing bracket of each let/cc form. Each continuation, if invoked, jumps directly to its defining let/cc's closing paren, so that the passed value is used as that expression's return value in the subsequent calculations. That's basically it.

The mind-bending part though is that in Scheme, you can jump to the closing paren from outside that form, thus re-entering old control context.