了解 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 是什么意思，为什么要用 throw 作为参数值来调用 proc(edure?)？注释“仅转义”是什么意思？

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

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

你明白什么是延续吗？ callcc(proc) 表示调用函数 proc 时使用一个称为“延续”的参数。如果在你的代码后面的某个地方，你用一个参数调用这个延续，它会 return 这个延续被调用的任何值返回给任何调用 callcc.

的人

throw 就是那个延续。当您使用参数调用延续时，它会引发异常，然后弹出堆栈，直到它找到对创建它的 callcc 的精确调用。然后 returns 一个值。

callcc的真正实现实际上可以做很多这个实现做不到的事情。延续比堆栈长。但这是一个好的开始。

Answer 2

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

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

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

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

有时您可以自然地表达这一点，这样当您找到东西时，您就可以 return 并且它会一直向上渗透。有时这要困难得多。所以你想要的是某种能够说 'here is a place in the program and here is a little machine which will return to that place' 的方式。所以在一些假设的语言中：

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

这里 block 构造建立了一个位置和 return-from return 来自一个块。

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

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

这足以完成 'escape to a given point' 事情：如果您在块的动态范围内调用此过程，它将立即从块中 return 它的参数。请注意，它不会做的是以某种方式搜索调用堆栈，寻找 return 的正确位置：它直接进入块和 return是它的一个值。

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

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

现在如果 my-search-function 或它调用的任何函数 调用 escape 那么它将立即 return 它的参数来自 call/cc表格。

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

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

这个惯用语就像一个非常结构化的 GOTO 用法：你可以进行非本地控制转移，但只能转移到一个点 'above' 你在函数调用链中（众所周知的调用堆栈总是向下生长：这是因为建造在张力下稳定的结构比在压力下更容易建造，而且结构失效也不会损坏失效上方的堆栈部分。

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

它创建一个异常，ball；
它创建了一个过程 throw，它在 ball 中存储一个值，然后引发它；
然后它调用 proc 并将此 throw 过程作为其参数，（return调用 proc 的值，如果它 return), 包裹在一个小 try: ... except: ... 块中，该块检查向上传递的这个特定异常，如果找到它 return 则将值 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 中延续功能的一半。因为一旦你从某个地方得到了这个过程对象return，那么，它就是一个过程：它是一个第一个class对象，你可以return然后稍后调用如果你要。在我们假设的语言中，这应该做什么：

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

好吧，在我们假设的语言（如您所见，它是 Lisp-2）中，这是一个运行时间错误，因为力矩控制通过 block 形式传递出去return-from 变得无效，所以虽然我有这个程序，但它不再有任何用处。

但这很可怕，对吧？我怎么知道我不能调用这个东西？我需要一些特殊的 'it is OK to call this here' 谓词吗？为什么它不能做正确的事？好吧，Scheme 的人们感到很欣慰，他们做到了，所以 Scheme 的等价物确实起作用了：

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

好吧，当我说 'does work' 时，它仍然是一个运行时间错误，但出于完全不同的原因：你允许调用这个东西我称之为 'escape procedure'，它会尽职尽责地 return 从形成它的形式中获得一个值，无论它在哪里。所以：

(call/cc (lambda (cc) cc)) 只是 return 继续对象；
(let ((c ...)) ...) 绑定到 c;
(c 3) 调用延续...
...returns（再次）3 来自 call/cc，其中...
... 将 c 绑定到 3;
现在您尝试调用 (c 3)这是一个错误。

这些运行你需要把它变成这样的时间错误：

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

(call/cc ...) return像以前一样是一个延续对象；
(let ... ...) 绑定到 c;
(c (lambda (x) 3) 调用延续...
...returns (lambda (x) 3) 来自 call/cc，其中...
... 将 c 绑定到 (lambda (x) 3)；
现在您调用 ((lambda (x) 3) (lambda (x) 3))，其中 return 是 3。

最后

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

我不打算解释。

Answer 3

其他问题更正确，但我在 python 中发布了一个可用于测试的工作示例：

def callcc(function):
    bail = RuntimeWarning("My custom bail.")
    def escape_function(retval): 
        bail.retval = retval; # adding our functions return value into the exception itself
        raise bail
    try:
        # this will call the function and the escape function RAISES bail 
        # so it'll never return
        return function(escape_function)
    except RuntimeWarning as w:
        if w is bail: 
            retval = bail.retval
            print("About to return value of %s..." % retval)
            return retval
        else: 
            raise w

def countdown(n):
    # the function we are passing to callcc is `countdown_with_escape`
    # countdown_with_escape will later be called by callcc with the 'throw' as the escape function
    return callcc(lambda escape_function: countdown_with_escape(escape_function, n))


def countdown_with_escape(escape_function, n):
    while True:
        print (n)
        if n == 9:
            escape_function(n) # this passes '9' as the retval to the escape function
        n -= 1

和运行它：

x = countdown(20)
print ('Done with value: %s' % x)

20
19
18
17
16
15
14
13
12
11
10
9
About to return value of 9...
Done with value: 9

了解 call-with-continuation 的实现

Understanding Implementation of call-with-continuation

lisp

python

scheme

continuations

callcc