将Scheme语言转换为延续传递风格

Question

我有点理解如何将基本函数（如算术）在Scheme中转换为延续传递风格。

然而，如果函数涉及递归怎么办？例如：

(define funname 
     (lambda (arg0 arg1)
                (and (some procedure)
                      (funname (- arg0 1) arg1))))

请给我一些建议。 提前感谢您。

- CosmicRabbitMediaInc

Answer 1

有一个很好的关于continuations和CPS的解释，就在Krishnamurthi的PLAI书中。相关部分（第VII部分）不依赖于书中的其他部分，因此您可以直接跳转到那里。具体来说，有一个将代码手动转换为CPS的扩展示例，并处理递归函数（第17章的第一部分）。

此外，我为我的课程写了一个扩展版本的文本，其中包含更多示例和更多有关主题的详细信息--您可能也会发现它很有用。除了PLAI文本外，我还涵盖了一些常见的continuations用途，例如实现生成器、模棱两可的运算符等。（但请注意，PLAI继续讨论实现策略，而我的文本没有涵盖。）

- Eli Barzilay

Answer 2

(define (func x y k)
  (some-procedure
   (lambda (ret)
     (if ret
         (- x 1
            (lambda (ret)
              (func ret y k)))
         (k #f))))

你缺少一个基本情况，这就是为什么唯一显式调用 continuation 的方法是 (k #f)。如果你有一个基本情况，那么你也会将基本情况的返回值传递给 continuation。例如：

(define (func x y k)
  (zero? x
         (lambda (ret)
           (if ret
               (k y)
               (some-procedure
                (lambda (ret)
                  (if ret
                      (- x 1
                         (lambda (ret)
                           (func ret y k)))
                      (k #f))))))))

- C. K. Young

Answer 3

这部分内容有点重复了Chris Jester-Young的回答，但是希望我能更好地解释一下 :-).

在CPS中，你要寻找的区别大致是这两种情况：

• 你可以调用一个过程，并将传递给你的延续作为参数。这相当于直接样式的优化尾调用。
• 或者，你可以调用一个过程，并将一个执行某些操作的新过程作为其延续传入其中，该过程将“返回值”传回你原始的延续。这相当于直接样式的堆栈调用。

后者就是Chris示例中的lambda所做的事情。基本上，评估一个lambda会创建一个closure——这些closures用于执行直接样式程序中堆栈帧的相同工作。在堆栈帧中的返回地址的位置，闭包包含一个连续函数的绑定，闭包的代码调用该绑定。

- Luis Casillas