Time Machine Control Flow with Call/CC

This post explains call/cc, which is a control flow operator that works like a time machine. Although call/cc is native to the Scheme family of languages, I explain it here with the more widely-accessible TypeScript syntax.

call/cc is particularly unusual because you can use it to implement things like return. Think about this: it's not obvious what kind of primitive you would need to build return. But you can do it with call/cc!

Fundamentally, call/cc similar to goto. The difference is that, while goto jumps to a place in the program, call/cc jumps to a previous state of the program's call stack. In this way, it's sort of like a time machine.

It's easiest to see with an example. Here, we use call/cc to implement a plus-two function.

const add = (a: number) => (
  a + /* save point */ callcc((done) => { 
    let two = 1 + 1;
    done(two); // jump to /* save point */ with callcc() => 2.
  })
)

console.log("sum is", add(4)) // => prints "sum is 6"

Let's trace the execution of this program.

We call add(4), which returns 4 plus the result of call/cc.
We evaluate call/cc.
call/cc immediately invokes its argument, which is a function (done) => {}.
That function computes 1+1, and then calls done(2).
done resets the state of the program to /* save point */, replacing call/cc with the value 2.
add returns and we print "sum is 6."

The main thing to take away here is that call/cc evaluates to whatever eventually gets passed into done.

Now, let's adjust add so it works exactly the same as above, except it also saves done to a global variable, _done.

let _done;

const add = (a: number) => (
  a + /* save point */ callcc((done) => { 
    _done = done;
    done(2);
  })
)

console.log("sum is", add(4)) // => prints "sum is 6"
_done(5) // => prints "sum is 9"

What happens when we call _done at the bottom? Remember, _done is the function that resets the program state to /* save point */. Last time we passed /* save point */, we were just about to console.log the sum of 4 and something (where something is the result of call/cc). So _done(5) jumps back to that moment, sets something to 5, adds 4, and then console.logs 9.

This where the notion of time machine control flow comes in: every time it's called, done snaps the state of the program (more precisely, of the call stack) back to how it was when the corresponding call/cc was invoked.

One gotcha: call/cc makes the program forget whatever else it was doing. Take the following example, where mult multiplies its argument by the result of _done.

const mult = (a: number) => a * _done(7)

console.log("product is", mult(8)) // => prints "sum is 11"
console.log("product is", mult(100)) // => prints "sum is 11"

We call mult with 8, then mult calls _done, _done resets the program to "add was just about to return 4 + something," and continues executing from there. It totally forgets the fact that it was originally in mult, and instead prints "sum is 11."

This makes sense if you imagine the implementation of call/cc as saving the current stack, and restoring that old stack when done is called. In this case, _done replaces the stack from the moment when we were inside mult with a stack from the moment when we were inside add.

Notice that this fact allows us to use call/cc to implement control flow operators like return, break, goto, continue, etc. But we haven't even scratched the surface yet!

call/cc can be used to implement coroutines. In this example, we have two functions, computeSum and writeLogs, which want to pass control back and forth without losing their state.

const computeSum = (alternate1: Function) => {
  let total = 0;
  for (let i = 0; i < 100; i++) {
    total += i;
    console.log(`total so far: ${total}`)
    alternate1 = /* save point 1 */ callcc(done1 => alternate1(done1))
  }
}

const writeLogs = (alternate2: Function) => {
  for (let i = 100; i >= 0; i--) {
    console.log(`${i} numbers to go!`)
    alternate2 = /* save point 2 */ callcc(done2 => alternate2(done2))
  }
}

computeSum(writeLogs)

This is a bit tricky to wrap your mind around. Let's trace a full loop.

Start by calling computeSum(writeLogs).
computeSum adds a number, and then calls callcc(done1 => writeLogs(done1)).
callcc immediately invokes writeLogs(done1).
writeLogs writes a log, and then calls callcc(done2 => done1(done2)).
call/cc immediately invokes done1(done2).
done1(done2) jumps back to save point 1 and sets alternate1 = done2.
computeSum adds another number, and then calls callcc(done1 => done2(done1)).
done2(done1) jumps back to save point 2 and puts alternate2 = done1
...

All of the extra syntax masks the underlying symmetry, which is quite beautiful:

const doA = (alt: Function) => {
  while (true) {
    // work
    alt = callcc(alt)
  }
}

const doB = (alt: Function) => {
  while (true) {
    // work
    alt = callcc(alt)
  }
}

doA(doB)

That's a coroutine built out of call/cc!

Now we've seen how call/cc can implement standard control flow, like return, break, continue, and goto, as well as features like coroutines and generators.

But that's not all. call/cc is also a natural implementation for try/catch, as well as some more esoteric and powerful control flow operators, like McCarthy's amb, and plenty of others you can dream up. Go forth and call/cc!

Notes & Sources

This post owes a large debt to the other resources explaining call/cc, as well as to GJS, in whose class the author first grappled with Scheme and call/cc. In no particular order: