Scheme: how does a nested call/cc work for a coroutine?

Question

I am looking at the following example for a coroutine from http://community.schemewiki.org/?call-with-current-continuation:

 (define (hefty-computation do-other-stuff) 
    (let loop ((n 5)) 
      (display "Hefty computation: ") 
      (display n) 
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) ; point A
      (display "Hefty computation (b)")  
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) 
      (display "Hefty computation (c)") 
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) 
      (if (> n 0) 
          (loop (- n 1)))))

superfluous work:

 ;; notionally displays a clock 
 (define (superfluous-computation do-other-stuff) 
    (let loop () 
      (for-each (lambda (graphic) 
                  (display graphic) 
                  (newline) 
                  (set! do-other-stuff (call/cc do-other-stuff))) 
                '("Straight up." "Quarter after." "Half past."  "Quarter til.")) ; point B
      (loop))) 


(hefty-computation superfluous-computation)

For the first usage of call/cc, what is the context supposed to be? When I say context, I mean where are we supposed to "return to" as a result of callcc's jump?

From what I understand, the first time you call call/cc, do-other-stuff essentially becomes a procedure that executes the code of superfluous-computation and then jumps to the point right after the set! (point A). The second time, it will wrap its "jump to point B" behavior around the "jump to point A and execute the context, or whatever code follows point A". Is this correct?

It doesn't seem like this code would work if the set! actually happened. Or is the set! necessary for this code to work?

A visual representation of what's going on would really help.

score 4 · Accepted Answer · edited Jan 15 '23 at 01:02

The context of call/cc is where ever call/cc is being called from. You can almost think of a call/cc like goto that jumps the code right back to where you were before and substitutes (call/cc whatever) with the return value.

call/cc basically says, "let's go do this function and give it away to jump right back here and forget about whatever else it was doing"

Ok when I was trying to understand call/cc for the first time, I found this code confusing in the extreme so let's look at a simplified coroutine example:

(define r1
  (lambda (cont2)
    (display "I'm in r1!")
    (newline)
    (r1 (call/cc cont2      ))))
    ;  ^---------------cont1

(define r2
  (lambda (cont1)
    (display "I'm in r2!")
    (newline)
    (r2 (call/cc cont1      ))))
    ;  ^---------------cont2

Ok this is exactly the same concept as your code. But it's much simpler.

In this case, if we call (r1 r2) this prints

I'm in r1
I'm in r2
I'm in r1
I'm in r2    
I'm in r1
I'm in r2    
I'm in r1
I'm in r2
...

Why? Because r1 first takes in r2 as cont2 so it announces to us that it's in r1. And then it recurses on itself with the result of (call/cc cont2) aka (call/cc r2).

Ok so what's the return of this? well (call/cc r2) calls r2 with the current continuation as cont1 so will announce that it's in r2 and then recurse on itself with the result of (call/cc cont1). Ok so what was cont1 again? cont1 was a continuation to that expression before in r1. So when we call it here, we pass back a continuation to the spot we're currently at. Then we forget anything about what we were doing in r2 and hop back into executing r1.

This repeats in r1 now. We announce stuff and then jump back to where we where before in r2 with and our expression from before, (call/cc cont1) returns a continuation to where we were in r1 and then we continue in our merry infinite loop.

Back to your code

In your code the concept is exactly the same. In fact `superfluous-computation` is almost identical to the above functions when you stop and think about it. So what's up with the `set!`s? In this code all they do is change the value of `do-other-work` to the newest continuation. That's it. In my example I used recursion. In this example they use `set!`.

When you say "cont2 was a continuation to that expression before in r1", are you saying that cont2 is a procedure that jumps back to the line `r1 (call/cc cont)`, except `(call/cc cont)` is replaced with a procedure that jumps to where r2 is about to recurse? I'm having trouble understanding what the `call/cc cont` finally ends up evaluating to before you actually finish the result of `r1 (call/cont)`. — hxngsun, Nov 12 '12 at 06:14
saying `(cont2 val)` is akin to saying jump back to `r1 (call/cc cont)` and replacing `(call/cc cont)` with val — daniel gratzer, Nov 12 '12 at 06:18
Really when I say replace, I mean that `(call/cc cont)` evaluates to val. You can think of it like a replacement if it helps — daniel gratzer, Nov 12 '12 at 06:19
Okay, so if I understand correctly when call/cc cont2 is being performed, we perform the jump to (r1 val) where val is the continuation of r2. Then we recurse into r1, and cont becomes the "jump to where r2 was about to call itself recursively"? Thanks so much for your help so far, I really appreciate it. I've spent the whole day kind of trying to figure out how stuff was working. — hxngsun, Nov 12 '12 at 08:40
Yep thats the general idea, it helped me too follow along with 2 fingers, 1 being whats executed and 1 being the location for the next continuation to jump too — daniel gratzer, Nov 12 '12 at 11:10

score 0 · Answer 2 · edited Jan 13 '23 at 08:58

There are two rules at play.

Rule 1. Taking a function f as its only argument, (call/cc f) within an expression is applied to the current continuation of the expression. For example ((call/cc f) e2) is equivalent to applying f to the current continuation of the expression. The current continuation is given by replacing (call/cc f) by a variable c bound by a lambda abstraction, so the current continuation is (lambda (c) (c e2)). Applying the function f to it gives the final result (f (lambda (c) (c e2))).

As a complementary example, in an expression (e1 (call/cc f)), the continuation for the sub-expression (call/cc f) is (lambda (c) (e1 c)), so the whole expression is equivalent to (f (lambda (c) (e1 c))). In other words it takes a "snapshot" of the current control context or control state of the program as an object and applies f to it.[1]

So, we can think about a continuation as a function. In simple cases we have

((call/cc f) e2) is equal to (f (lambda (c) (c e2)))
(e1 (call/cc f)) is equal to (f (lambda (c) (e1 c)))

For example

(apply + '(1 2))

gives the same result as

(define (f cont1) 
        (cont1 +))
(apply (call/cc f) '(1 2))

or

(define (g cont2) 
        (cont2 '(1 2)))
(apply + (call/cc g))

or

(define (h cont3) 
        (cont3 apply))
((call/cc h) + '(1 2))

Rule 2. When a continuation is applied to an argument, the existing continuation is eliminated and the applied continuation is restored in its place, so that the program flow will continue at the point at which the continuation was captured and the argument of the continuation then becomes the "return value" of the call/cc invocation.[1]

The following example[2] illustrates this rule:

(define return #f) 
  
 (+ 1 (call/cc 
        (lambda (cont) 
          (set! return cont) 
          1))) 

>(return 22) 
 23

Let's return to the initial example.

Both functions (hefty-computation and superfluous-computation) have the same structure

...
(set! do-other-stuff (call/cc do-other-stuff))
...

Using the 1st rule we can rewrite it as

(do-other-stuff (lambda (c) ... (set! do-other-stuff c) ...))

or

(do-other-stuff continuation2)

;; where 
;;    continuation2 = (lambda (c) ... (set! do-other-stuff c) ...)

do-other-stuff is also a continuation, so we have

(continuation1 continuation2)

;; where 
;;    continuation1 = do-other-stuff

Now we can use the 2nd rule, so we return in the context of the previous function (i.e. continuation1) with the return value that is equal to the argument of the continuation (i.e. continuation2):

(set! do-other-stuff continuation2) 
...

Links

[1] https://en.wikipedia.org/wiki/Call-with-current-continuation

[2] http://community.schemewiki.org/?call-with-current-continuation

Scheme: how does a nested call/cc work for a coroutine?

2 Answers2

Back to your code