Is CallCC an improved version of goto?

Question

My background is Javascript, Python & a bit of Haskell. I am trying to understand callCC, there are many explanations but I can't find them trivial & I came across this https://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf and I felt like I almost got it but I need some help to understand C code.

Below is the Code for Jumping back into a function in GNU C.

void *label_as_result() {
     return &&L;
  L: printf("Jumped back into the function. \n");
}

main () {
    void *p;
    p = label_as_result();
    printf("The function returned; now jump back into it.\n");
    goto *p;
}

What does return statement do in label_as_result function? Does p in main store the stack frame in heap & the instruction line where it is stopped? Jump back to function means create a stack frame again and continue from where we left?

Below this code there is paragraph

But in a language with first-class functions and callCC, no such implementation restrictions apply. Just as with the label as a result in C, we can return a continuation introduced by callCC from a function so as to jump back into the function. When we did this with goto, the stack was smashed, but with callCC the function just returns again. Consider the following function

 λ(). callCC(λk. λx. throw k (λy. x))

The continuation k is returned as part of the result, roughly analogous to returning a label as the result in C.

What does stack was smashed, he meant stackoverflow can happen if you use goto? How callCC is getting around this problem using trampolining?

As many say callCC gives Early return semantics that means is it like yield in python or Javascript? Is it possible to write callCC in Javascript using yield?

How I conceive the above code in Javascript

function* label_as_result() {
    yield () => console.log("Jumped back into the function.");
}

p = label_as_result().next().value;
console.log("The function returned; now jump back into it.");
p();

It can even simple be written without any generators concept as

function label_as_result() {
    return () => console.log("Jumped back into the function.");
}

p = label_as_result();
console.log("The function returned; now jump back into it.");
p();

That means callCC is a function that returns a continuation but all other functions take continuations. Continuations are like Undecided code that need to be performed in future but callCC is like predefined code that needs to be performed in Future? (I am talking in perspective of a framework and the user's code)

Answer 1

What does return statement do in label_as_result function?

It returns the address of the instruction labelled L. That is, it returns the address of where the code the compiler generated for printf("Jumped back into the function. \n"); is stored in memory.

Does p in main store the stack frame in heap & the instruction line where it is stopped?

No, it stores the instruction line where the L label is. That's all it stores.

Jump back to function means create a stack frame again and continue from where we left?

No, it means a single jump and nothing else - no stack manipulation. The control flow jumps to the line labelled L, but nothing else changes. The stack remains unchanged.

What does stack was smashed, he meant stackoverflow can happen if you use goto?

Underflow, actually. When label_as_result is called, a frame is pushed to the stack. When it returns, that frame is popped. Then we jump to L, execute printf and then reach the end of the function, which will pop the stack again. So in the end the stack was popped more often than it was pushed.

How callCC is getting around this problem

By actually doing what you assumed the C code was doing: Saving and restoring the stack instead of just jumping to a code line while keeping the stack the same.

As many say callCC gives Early return semantics that means is it like yield in python or Javascript?

They're alike in the sense that they both give you a type of early return and they can be used for some of the same things. You can think of yield as a more specialized tool meant to provide a simpler way to achieve some of the use cases of callCC.

Is it possible to write callCC in Javascript using yield?

No, but it's possible to write yield in Scheme using callCC. callCC is strictly the more powerful of the two.

How I conceive the above code in Javascript

The actual C code isn't something that you can replicate in JavaScript (other than by building a mini-VM with its own stack) because JavaScript doesn't allow you to destroy the stack like that.

A non-broken version that doesn't destroy the stack could be accomplished by returning a function from label_as_result as you do in your second code sample.

That means callCC is a function that returns a continuation

callCC is a function that calls another function with the current continuation. That can be used to return the continuation.

Continuations are like Undecided code that need to be performed in future

Sure, except I wouldn't say "need" here. You don't have to invoke the continuation (or you could invoke it more than once even).

but callCC is like predefined code that needs to be performed in Future?

Not quite sure what you mean here, but that doesn't sound right. callCC is a function that gives you access to the current continuation.

Answer 2

try, throw, catch

callcc can be implemented in direct style using try-catch. The important bit is that the continuation must "box" the return value and "unbox" it in catch to avoid swallowing real errors. Here is a straightforward implementation in JavaScript -

const callcc = f => {
  class Box { constructor(v) { this.unbox = v } }
  try { return f(value => { throw new Box(value) }) }
  catch (e) { if (e instanceof Box) return e.unbox; throw e  }
}

console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { exit(10); throw Error("test failed") }))

try {
  console.log(5 + callcc(exit => { throw Error("test passed!") }))
}
catch (e) {
  console.error(e)
}

.as-console-wrapper { min-height: 100%; top: 0; }

35                     ? 5 + 10 * 3
8                      ? 5 + 3
15                     ? 5 + 10
15                     ? 5 + 10
Error: test passed!    ? Errors are not swallowed

early return

Given a list of numbers, let's multiply all of them. As humans we know if a single 0 is present, the product must be 0. callcc allows us to encode that same short-circuiting behavior. In the demo below mult(a,b) is used so we can see when actual work is happening. In a real program it could be replaced with a * b -

const callcc = f => {
  class Box { constructor(v) { this.unbox = v } }
  try { return f(value => { throw new Box(value) }) }
  catch (e) { if (e instanceof Box) return e.unbox; throw e  }
}

const apply = (x, f) => f(x)

const mult = (a, b) => {
  console.log("multiplying", a, b)
  return a * b
}

console.log("== without callcc ==")
console.log(
  apply([1,2,3,0,4], function recur(a) {
    if (a.length == 0) return 1
    return mult(a[0], recur(a.slice(1)))
  })
)

console.log("== with callcc ==")
console.log(
  callcc(exit =>
    apply([1,2,3,0,4], function recur(a) {
      if (a.length == 0) return 1
      if (a[0] == 0) exit(0) // ?
      return mult(a[0], recur(a.slice(1)))
    })
  )
)

.as-console-wrapper { min-height: 100%; top: 0; }

== without callcc ==
multiplying 4 1
multiplying 0 4 ? here we know the answer must be zero but recursion continues
multiplying 3 0
multiplying 2 0
multiplying 1 0
0
== with callcc ==
0 ? the answer is calculated without performing any unnecessary work

cursory benchmark

In a one-off metric, callcc performs at least 50-500 times faster on a list of 20,000 numbers ranging from 0-100 -

const callcc = f => {
  class Box { constructor(v) { this.unbox = v } }
  try { return f(value => { throw new Box(value) }) }
  catch (e) { if (e instanceof Box) return e.unbox; throw e  }
}

const apply = (x, f) => f(x)

const A = Array.from(Array(20000), _ => 0 | Math.random() * 100)

console.time("== without callcc ==")
console.log(
  apply(A, function recur(a) {
    if (a.length == 0) return 1n
    return BigInt(a[0]) * recur(a.slice(1))
  }).toString()
)
console.timeEnd("== without callcc ==")

console.time("== with callcc ==")
console.log(
  callcc(exit =>
    apply(A, function recur(a) {
      if (a.length == 0) return 1n
      if (a[0] == 0) exit(0) // ?
      return BigInt(a[0]) * recur(a.slice(1))
    })
  ).toString()
)
console.timeEnd("== with callcc ==")

.as-console-wrapper { min-height: 100%; top: 0; }

0
== without callcc ==: 466.000ms
0
== with callcc ==: 1.000ms

read on

callcc was originally implemented in this Q&A. Read on for additional info and examples.