CPS样式的` `call/cc`可以写成假设的非CPS样式的` `cc'`吗？

Question

在支持延续的语言中，例如Scheme、Ruby和Haskell，假设有一个函数cc'不带参数并返回当前的延续，这样通过调用cc'获得延续的调用者就可以随时随地调用延续。

通过将标识函数作为参数传递给call/cc，可以按照CPS样式的call/cc编写cc'。

相反，可以按照非CPS样式的cc'编写CPS样式的call/cc吗

Answer 1

这是我的尝试(警告:我是一个缺乏经验的阴谋家)。假设get-cc是返回当前延续的函数。

(define (get-cc)
  (call-with-current-continuation (lambda (k) k)))

然后，我们可以定义：

(define (callCC f)
  (let ((w (get-cc)))
    (if (pair? w)
      (car w)
      (f (lambda (x) (w (cons x '())))))))

第一次调用此函数时，w被绑定到当前continuation。因此，(pair? w)为false，我们调用带有延续(lambda (x) (w (cons x '()))的f。

当通过f (带参数(cons x '()))调用w时，将再次输入let的主体，其中w现在绑定到(cons x '())。现在，(pair? w)为真，我们可以返回为x的(car w)。

对包装器用于区分什么是“f的延续”和“f的结果”，也就是说。

快速测试表明这是有效的，但我并不完全有信心它的正确性。

您可能已经注意到，w绑定到不同类型的值。这就是为什么我求助于无类型语言，比如Scheme而不是Haskell。