CallCC是goto的改进版吗？

Question

我的背景是 Javascript、Python 和一点点 Haskell。我试图理解 callCC，有很多解释，但我找不到它们是微不足道的，我遇到了这个 https://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf，我觉得我几乎明白了，但我需要一些帮助来理解 C 代码。

下面是在 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;
}

return语句在label_as_result函数中的作用是什么？ p in main 是否将堆栈帧存储在堆中及其停止的指令行中？跳回函数意味着再次创建堆栈帧并从我们离开的地方继续？

这段代码下面有一段

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.

stack was smashed是什么意思，他的意思是用goto会出现Whosebug？ callCC 如何使用蹦床解决这个问题？

正如许多人所说，callCC 提供了 早期 return 语义，这意味着它像 python 或 Javascript 中的 yield 吗？是否可以使用 yield 在 Javascript 中编写 callCC？

上面的代码我是怎么构思的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();

它甚至可以在没有任何生成器概念的情况下简单地写成

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();

这意味着 callCC 是一个 return 延续的函数，但所有其他函数都采用延续。 Continuations 就像未决定的代码，需要在未来执行，但 callCC 就像预定义的代码，需要在 Future? （我是从框架和用户代码的角度讲的）

Answer 1

What does return statement do in label_as_result function?

它return是标记为L的指令的地址。也就是说，它 return 是编译器为 printf("Jumped back into the function. \n"); 生成的代码存储在内存中的地址。

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

不，它存储L标签所在的指令行。这就是它存储的全部内容。

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

不，这意味着一次跳转，仅此而已 - 没有堆栈操作。控制流跳转到标记为 L 的行，但没有其他任何变化。堆栈保持不变。

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

实际上是下溢。当 label_as_result 被调用时，一个帧被压入堆栈。当它 returns 时，弹出该帧。然后我们跳转到L，执行printf然后到达函数末尾，会再次出栈。所以最后出栈的次数比压栈的次数多。

How callCC is getting around this problem

通过实际执行您假设 C 代码正在执行的操作：保存和恢复堆栈，而不是在保持堆栈不变的同时跳转到代码行。

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

它们的相似之处在于它们都为您提供了一种早期 return 并且它们可以用于某些相同的事情。您可以将 yield 视为一种更专业的工具，旨在提供一种更简单的方法来实现 callCC.

的一些用例

Is it possible to write callCC in Javascript using yield?

不，但是可以使用 callCC 在 Scheme 中编写 yield。 callCC 严格来说是两者中更强大的一个。

How I conceive the above code in Javascript

实际的 C 代码不是您可以在 JavaScript 中复制的东西（除了构建一个带有自己的堆栈的小型 VM 之外）因为 JavaScript 不允许您破坏像这样的堆栈。

一个不破坏堆栈的完整版本可以通过 return 从 label_as_result 中调用一个函数来实现，就像你在第二个代码示例中所做的那样。

That means callCC is a function that returns a continuation

callCC 是调用另一个函数和当前延续的函数。那可以用来return继续

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

当然可以，但我不会在这里说 "need"。您没有来调用延续（或者您甚至可以多次调用它）。

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

不太清楚你的意思，但这听起来不对。 callCC 是一个使您可以访问当前延续的函数。

Answer 2

试、扔、接

callcc 可以使用 try-catch 以直接方式实现。重要的一点是延续必须“装箱” return 值并将其“拆箱”在 catch 中以避免吞下真正的错误。这是 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

早return

给定一个数字列表，让我们将所有数字相乘。作为人类，我们知道如果存在单个 0，则乘积必须为 0。callcc 允许我们对相同的 short-circuiting 行为进行编码。在下面的演示中，使用 mult(a,b) 以便我们可以看到实际工作何时发生。在实际程序中，它可以替换为 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

粗略基准测试

在 one-off 指标中，callcc 在 0-100 -

范围内的 20,000 个数字列表中的执行速度至少快 50-500 倍

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

继续阅读

callcc 最初是在 this Q&A 中实现的。继续阅读以获取更多信息和示例。

CallCC是goto的改进版吗？

Is CallCC an improved version of goto?

javascript

c

scheme

continuations

callcc