理解 call-with-continuation 的实现

Question

我试图理解用 python 代码编写的方案过程：

def callcc(proc):
    "Call proc with current continuation; escape only"
    ball = RuntimeWarning("Sorry, can't continue this continuation any longer.")
    def throw(retval): ball.retval = retval; raise ball
    try:
        return proc(throw)
    except RuntimeWarning as w:
        if w is ball: return ball.retval
        else: raise w

它来自本教程：http : //norvig.com/lispy2.html。

以上是如何工作的？是什么ball意思，为什么 a proc(edure?) 被称为 athrow作为其参数值？评论“仅转义”是什么意思？

---

顺便说一句，这是我目前（可能是被误导的）对适用于 python 的延续的理解，这类似于传递一个带产量的函数：

def c(func, *args, **kwargs):
    # func must be a coroutine
    return func(*args, **kwargs)

def inc(x=0):
    while True:
        yield x
        x += 1

>>> ct=c(inc, 3)
>>> next(ct)
3
>>> next(ct)
4

Answer 1

[我不确定这个答案是否比另一个更有用：我在另一个之前开始它，然后分心了。]

您真正希望能够在任何语言中实现的是能够轻松地从某些上下文返回到给定点的能力。这显然是异常处理的基础，但它比这更通用。假设您有一些搜索程序：

(define (search-thing thing)
  (if (thing-is-interesting? thing)
      <return from search routine>
      (search-children (thing-children thing)))

(define (search-children children)
  ... (search-thing ...) ...)

有时你可以很自然地表达这一点，这样当你找到那个东西时，你就回来了，它一直向上渗透。有时这要困难得多。所以你想要的是某种方式能够说“这是程序中的一个地方，这是一台将返回到那个地方的小机器”。所以用一些假设的语言：

(block here
  ...
  (return-from here ...)
  ...)

这个block构造在这里建立了一个位置并return-from从一个块返回。

好吧，如果您想返回的块在词法上对您不可见，您会怎么做？您可以将 包装return-from在一个函数中：

(block here
  ...
  (my-search-function (lambda (v) (return-from here v)) ...
  ...)

这足以完成“转义到给定点”的事情：如果您在块的动态范围内调用此过程，它将立即从块中返回其参数。请注意，它不会做的就是以某种方式寻找调用堆栈寻找合适的地方，从回报：它只是直接进入块并返回一个值。

好吧，也许更自然的方法是取消所有这些制作块的事情，直接进入过程的事情：只需有一个过程，它将过程作为参数并调用它我上面做的这个逃生程序。那call/cc就是：

(call/cc (lambda (escape)
           (my-search-function escape ...))

现在，如果my-search-function 还是任何函数调用调用escape那么它将立即从返回它的参数call/cc表。

Python 没有真正像这样的构造（免责声明：我可能错了，因为我正在用更有趣的东西替换三年前我知道的 Python）。 return在Python总是从最内层词法函数返回：你不能说return-from从功能外词法返回最里面的一个（有没有像nonlocal对returnS）。但是您可以使用异常来模拟它，因为异常具有标识。因此，如果您抛出异常，那么您可以将其包装在一个函数中，该函数只会引发传递到您的代码中的异常。调用此函数只会引发该异常（不是同一类之一：该实际对象），并在其中存储一个值。然后你建立一个try ... except:检查刚刚捕获的异常是否是刚刚创建的异常的块，如果它是同一个对象，则返回它知道存储在那里的值。如果不是，它只是重新加注。

所以这是一个黑客，因为如果你有很多这样的东西嵌套，很多处理程序会查看它并拒绝它，直到它找到它所属的那个。但为此目的，这是一个可以接受的黑客攻击。特别是这意味着您可以将一个函数传递给另一个函数，如果它调用它，它将从您创建它的地方返回一个值，并放弃任何中间计算。

这个习语就像一个非常结构化的 GOTO 用法：你可以进行非本地控制转移，但只能在函数调用链中“高于”你的点（众所周知，调用堆栈总是向下增长：这是因为建造在张力下稳定的结构比压缩容易得多，并且结构故障也不会损坏故障上方的堆栈部分）。

这正是 Python 示例代码所做的：

1. 它创建了一个异常，ball；
2. 它创建了一个过程throw，该过程将一个值存储在其中ball，然后将其提升；
3. 然后它proc以这个throw过程作为它的参数调用，（proc在它返回的情况下返回调用的值），包裹在一个小块中try: ... except: ...，它检查向上通过它的这个特定异常，如果它发现它返回价值throw藏在其中。

所以你可以使用它，例如，像这样：

def search(thing):
    callcc(lambda escape: search_with_escape(escape, thing))

def search_with_escape(escape, thing):
    ...
    if all_done_now:
        escape(result)
    ...

这里search_with_escape实现了一些精细的搜索过程，可以通过调用escape.

但当然，这只是延续让您在 Scheme 中所做的事情的一半。因为一旦你得到了这个将从某处返回的过程对象，那么，它就是一个过程：它是一个可以返回的一流对象，如果你愿意，可以稍后再调用它。在我们的假设语言中，这应该做什么：

(let ((c (block foo (lambda (v) (return-from foo v)))))
  (funcall foo 3))

好吧，在我们假设的语言（如您所见，是 Lisp-2）中，这是一个运行时错误，因为控制通过block表单传出的那一刻return-from变得无效，所以尽管我有这个过程，但它不再是任何用。

但这太可怕了，对吧？我怎么知道我不能调用这个东西？我是否需要一些特殊的“可以在这里调用”谓词？为什么它不能做正确的事情？好吧，Scheme 的人正在感受他们的燕麦，他们做到了，所以 Scheme 等价物确实有效：

(let ((c (call/cc (lambda (cc) cc))))
  (c 3))

好吧，当我说“做工作”它仍然是一个运行时错误，但对于一个完全不同的理由：你是不准叫我把它叫做一个“逃逸过程”的事情，它会忠实地退出令它的形式返回一个值，无论在哪里。所以：

1. (call/cc (lambda (cc) cc)) 简单地返回延续对象；
2. (let ((c ...)) ...)将其绑定到c;
3. (c 3) 调用延续...
4. ...3从返回（再次）call/cc，其中 ...
5. ... 绑定c到 3；
6. 现在您尝试调用(c 3)这是一个错误。

您需要将这些运行时错误变成这样：

(let ((c (call/cc (lambda (cc) cc))))
  (c (lambda (x) 3)))

1. (call/cc ...) 像以前一样返回一个延续对象；
2. (let ... ...)将其绑定到c;
3. (c (lambda (x) 3) 调用延续...
4. ...(lambda (x) 3)从返回call/cc，其中 ...
5. ... 绑定c到(lambda (x) 3);
6. 现在你调用((lambda (x) 3) (lambda (x) 3))which 返回3.

最后

(let ((c (call/cc (lambda (cc) cc))))
  (c c))

我不打算解释。