将函数更改为 CPS，不使用 call/cc

Question

我想了解如何在没有 call/cc.

的情况下实现 coroutines

我从这个小例子开始了解如何修改代码以便我可以在没有 call/cc:

的情况下使用它

(define x 0)

( + 2 (call-with-current-continuation
  (lambda (cont)
    (set! x cont)
  3)))

(x 4)

当我用 call/cc 执行函数时，它会给我 5，然后 6 当我执行 (x 4).

我用这个函数来代替 call/cc :

(define (call/cc-cps f continuation)
   (f continuation continuation))

我尝试将此函数更改为 CPS（连续传递样式）：

(call/cc-cps
  (lambda (exit cont)
   (set! x cont)
   3)
(lambda (value)
  (+ value 2)))

但是当我执行它时，我得到的不是 5，而是 3。但是我确实得到 6 和 (x 4).

你能告诉我哪里出了问题吗？谢谢

Answer 1

使用 CPS，您没有顶级延续提示，因此为了进行比较，您需要将代码放在一个空的 let 中，如下所示：

(let ()
  (define x 0)
  (+ 2 (call-with-current-continuation
         (lambda (cont)
           (set! x cont)
           3))) ; ==> 5
  (x 4))
  ; ==> 6
  ; ==> 6
  ; ==> 6
  ; ... forever

这变成了一个无限循环，因为你每次在求和之后调用 (x 4)。

;; CPS-version of +
(define (+& a b continuation)
  (continuation (+ a b)))

注意 &。它用于指示该函数接受一个额外的参数，即延续。在 CPS 中，您可以这样定义 call/cc：

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

请注意，它与您的版本完全不同。它将退出函数传递给 f&，而不是使用传递的 actual-continuation 来完成所有剩余的计算，而是将其传递给 call/cc& 的延续。

现在我们可以将您的程序改写成这样：

((lambda (x& halt-continuation) 
  (call/cc& (lambda (cont continuation)
              ((lambda (ingnored-undefined-value) (continuation 3))
               (set! x& cont)))
            (lambda (three)
              (+& 2 three (lambda (ignored-result)
                      (x& 4 halt-continuation))))))
 0 values)

ignored-result 是 5 第一次和无限次它用 4 计算它 ignored-result 是 6，就像在非let.

的 CPS 版本

我使用 DrRacket，它有一个非常好的调试器，你可以一步一步地看到到底发生了什么。我在 +& 调用处添加了一个断点并按下 |> 并看到变量 three 首先是 3 然后 4 无限次。

CPS 并不容易。 call/cc 为我们提供了 CPS 的好处，同时又不使代码更难阅读。在没有 call/cc 的情况下实现协同程序对我来说是一个挑战，因为我开始时使用 call/cc 来实现它是相当复杂的，特别是因为如果你不小心的话你会有一个无限循环。

将函数更改为 CPS，不使用 call/cc

Change a function into CPS, to not use call/cc

scheme

coroutine

continuations

continuation-passing

callcc