continuation passing风格转换规则是什么？

Question

我正在尝试了解延续传递样式转换。

我正在尝试构建一个 Scheme to C 编译器，我想使用连续传递样式。 continuation passing style 是否是正确的方法，你们能解释一下转换规则吗？

例如，这是 Gambit Scheme 的创建者 Marc Feeley 的 presentation。

我会总结一下他给出的continuation passing style规则，但是注意：我不理解它们。特别是我不明白C是什么。

这里是符号：

[E]
 C

表示延续C中表达式E的延续传递式转换

因此，例如，一个转换规则是：

[c] 
 C
==>
(C c) ;; application of C to c

表示continuation C中常量c的CPS转换

C是什么？我无法理解 C 是什么。就像魔术一样。

另一个规则是：

[(if E1 E2 E3)]
     C

==>

    [E1]
(lambda (r1)
  (if r1 [E2] [E3]))
          C    C

其中 E1 传递给 r1。

但 C 是什么？

你们能解释一下吗？

谢谢。

Answer 1

如果您在文章中向上滚动到第 7 页，您会找到什么是延续的定义，这对于理解转换为 continuation-passing 样式的规则是必要的。给出的例子是

 > (sqrt (+ (read) 1))

它指出 (read) 的延续是

a computation that takes a value, adds 1 to it, computes its square-root, prints the result and goes to the next REPL interaction.

所以表达式 E 的延续 C 是“无论这个表达式的值发生什么”。第 20 页重申了这一点，示例

(let ((square (lambda (x) (* x x))))
  (write (+ (square 10) 1)))

(square 10) 的延续是

(lambda (r) (write (+ r 1)))

因此，当您递归地将程序转换为 CPS 样式时，延续 C 将随着您对表达式的深入而增长。请注意，每个翻译规则 [E]|C 都会导致较小的 un-translated E，如果 E 足够简单，则可能为空，而翻译后的 C 会更大。

Answer 2

当您在 CPS 中转换代码时，您实际上在评估中引入了严格的纪律。

当您写 (+ x y z) 时，不清楚您计算 +、x、y、z 中每一个的顺序。如果您使用的语言明确定义了一个顺序，您就会知道会发生什么。但是如果语言没有插入顺序，你可以通过将代码写入 in/converting 来定义你想要的顺序 CPS，在我建议你写的例子中：

(eval + (lambda (+)
  (eval x (lambda(x)
   (eval y (lambda (y)
    (eval z (lambda (z)
             (+ x y z))))

如果您想要 left-right 评价。

如果您在 CPS 中编写代码，这就像在汇编程序中编写代码一样，因为每段代码都可以与一条指令相关联，而该指令在非常低的编程中具有相应的指令。如果在 CPS 中转换某些代码，则需要对变量进行唯一重命名以避免冲突。在创建C语言的时候，我认为没有明确定义CPS变换；这就是 inline 说明符拒绝递归调用的原因。可以通过重写 C 代码并使用 CPS 转换将递归函数转换为 goto-loop，但标准 C 不想这样做。

将代码转换为CPS的方法有很多种。例如，在 Mit-scheme 中，输入代码并没有明确地以 CPS 形式重写，但是评估过程使用 goto 语句和蹦床调用的组合来模拟它（这是你在学校学到的一种方式大约，但它在实践中使用）。

递归的CPS代码可以直接转化为迭代循环（这就是scheme->C翻译器先做转化的原因）解决尾递归。 Dan Friedman 的 EPL 第一版对其进行了详细说明。弗里德曼也有一篇关于此的文章。如果你找不到，我会尽力帮你找。

continuation passing风格转换规则是什么？

What are the continuation passing style conversion rules?

lisp

scheme

continuation-passing