CallCC是goto的改进版本吗？

Question

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

下面是GNU中跳转到函数中的代码。

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;
}

返回语句在label_as_result函数中做什么？p在主中是否将堆栈帧存储在堆中&停止它的指令行？跳转回函数意味着再次创建堆栈框架，并从我们离开的地方继续吗？

在这段代码下面有一段

，但在一种具有一流函数和callCC的语言中，这种实现限制并不适用。与C中的标签一样，我们可以从函数中返回callCC引入的延续，以便跳转到函数中。当我们使用goto执行此操作时，堆栈被破坏，但是使用callCC，函数就会再次返回。考虑以下功能

λ()。callCC(λk.λx.掷k(λY.x))

作为结果的一部分返回延续k，大致类似于将标签返回为C中的结果。

堆栈被砸了什么，他的意思是，如果使用goto，堆栈溢出会发生吗？callCC是如何使用蹦床来解决这个问题的？

正如许多人说的那样，callCC给了早期返回语义，这意味着它是类似于python还是Javascript的收益率？是否可以使用产率在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是一个返回延续的函数，但所有其他函数都采用连续。延续就像未来需要执行的未定代码，但callCC就像预定义的代码，需要在未来执行吗？(我是从框架和用户代码的角度来讨论的)

Answer 1

返回语句在label_as_result函数中做什么？

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

是否在主目录中将堆栈帧存储在堆中&停止它的指令行？

不，它存储L标签所在的指令行。这就是它所储存的一切。

跳转回函数意味着再次创建堆栈框架，并从我们离开的地方继续吗？

不，它意味着一次跳转，没有别的-没有堆栈操作。控制流跳转到标记为L的行，但其他任何更改都不会发生。堆栈保持不变。

堆栈被破坏了什么，他的意思是，如果使用goto，堆栈溢出会发生吗？

实际上是下流。当调用label_as_result时，会将一个框架推送到堆栈中。当它返回时，就会弹出该帧。然后我们跳到L，执行printf，然后到达函数的末尾，这将再次弹出堆栈。因此，最终堆栈被弹出的频率比被推的要高。

callCC是如何解决这个问题的

通过实际执行您假设的C代码所做的事情:保存和还原堆栈，而不是跳转到代码行，同时保持堆栈不变。

正如许多人所说的那样，

给出了早期返回语义，这意味着它是类似于python还是Javascript的收益率？

它们在某种意义上是相似的，因为它们都能给你一种早期的回报，而且它们可以被用来做一些相同的事情。您可以将yield看作是一个更专门的工具，目的是提供一种更简单的方法来实现callCC的一些用例。

是否可以用收益率在Javascript中编写callCC？

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

我是如何在Javascript中构思上述代码的

实际的C代码不是您可以在JavaScript中复制的东西(除了通过构建一个带有自己的堆栈的mini)，因为JavaScript不允许您那样销毁堆栈。

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

，这意味着callCC是一个返回延续的函数。

callCC是一个函数，它用当前的延续调用另一个函数。它可以用于返回延续。

延续就像未来需要执行的尚未确定的代码一样。

当然，不过我不会在这里说“需要”。您不必调用延续(甚至可以不止一次调用它)。

，但callCC就像预定义的代码，需要在将来执行吗？

不太清楚你在这里的意思，但听起来不太对。callCC是一个函数，它允许您访问当前的延续。

Answer 2

尝试，抛出，抓住

callcc可以直接使用try-catch实现。重要的一点是，在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

早期返回

给出一个数字列表，让我们把它们都乘以。作为人类，我们知道如果一个单一的0存在，产品必须是0。short-circuiting允许我们对相同的callcc行为进行编码。在下面的演示中，我们使用了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

粗略基准

在一次过的度量中，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实现的。阅读更多的信息和例子。