scheme - call/cc 如何处理来自 "Lisp in Small Pieces"的 CPS 转换？

Question

Lisp in Small Pieces 一书展示了从 Scheme 到连续传递风格的转变(第 5.9.1 章，对于那些可以访问该书的人)。转换表示 lambda 形式的延续，call/cc 应该等同于简单的 (lambda (k f) (f k k))。

我不明白这是如何工作的，因为函数的应用和延续之间没有区别。

这是一个从除应用程序以外的所有内容中删除的转换版本(完整版本可以在 this gist 中找到):

(define (cps e)
  (if (pair? e)
      (case (car e)
        ; ...
        (else (cps-application e)))
      (lambda (k) (k `,e))))

(define (cps-application e)
  (lambda (k)
    ((cps-terms e)
     (lambda (t*)
       (let ((d (gensym)))
         `(,(car t*) (lambda (,d) ,(k d))
                     . ,(cdr t*)))))))

(define (cps-terms e*)
  (if (pair? e*)
      (lambda (k)
        ((cps (car e*))
         (lambda (a)
           ((cps-terms (cdr e*))
            (lambda (a*)
              (k (cons a a*)))))))
      (lambda (k) (k '()))))

现在考虑来自 Wikipedia 的 CPS 示例:

(define (f return)
  (return 2)
  3)

上述转换会将函数体 (return 2) 中的应用程序转换为类似 (return (lambda (g13) ...) 2) 的内容。延续作为第一个参数传递，值 2 作为第二个参数传递。如果 return 是一个普通函数，这会很好。然而，return 应该是一个延续，它只接受一个参数。

我不明白这些部分是如何组合在一起的。转换如何将延续表示为 lambda 形式而不特别考虑它们的应用？

Answer 1

I do not understand how this can work because there is no distinction between application of functions and continuations.

在没有 CPS 的情况下实现延续需要虚拟机级别的方法，例如使用“意大利面条堆栈”:在受垃圾收集影响的堆分配帧中分配词法变量。捕获延续意味着获取指向意大利面条堆栈中词汇框架的环境指针。

CPS 从闭包中构建了一个事实上的意大利面条堆栈。闭包将词法绑定(bind)捕获到具有不确定生命周期的对象中。在 CPS 下，所有闭包都捕获隐藏变量 k。 k 充当意大利面条堆栈中父帧指针的角色；它将闭包链接在一起。

因为整个程序始终是 CPS 转换的，所以到处都有一个 k 参数，它指向一个动态链接的封闭环境链，相当于一个事实上 可以恢复执行的堆栈。

拼图中缺少的一 block 是 CPS 取决于尾调用。尾调用确保我们没有使用真正的堆栈；一切有趣的事情都在封闭的环境中。

(然而，即使是尾调用也不是严格要求的，正如 Henry Baker 的方法，体现在 Chicken Scheme 中，教导我们。我们的 CPS 转换代码可以使用消耗堆栈但从不返回的真实调用。每隔一段时间我们可以将可到达的环境帧(和所有偶然对象)从堆栈移动到堆中，并倒回堆栈指针。)

Now consider the CPS example from Wikipedia:

啊，但这不是 CPS 示例；这是一个应用程序代码示例，它使用可通过 call/cc 以某种方式获得的延续。

如果我们手动将其转换为 CPS，或者使用机械地执行此操作的编译器，它就会成为 CPS。

However, return is supposed to be a continuation, which only takes a single argument.

因此，return 只接受一个参数，因为我们正在查看尚未经过 CPS 转换的应用程序源代码。

应用程序级延续采用一个参数。

与所有函数一样，CPS 实现级延续将具有隐藏的 k 参数。

k 参数类似于一段机器上下文，如堆栈或帧指针。当使用常规语言并调用 print("hello") 时，您不会问，为什么只有一个参数？ print 不需要接收堆栈指针以便知道参数在哪里吗？当然，当 print 被编译时，编译后的代码有一种方法可以将该上下文从一个函数传递到另一个函数，这对高级语言是不可见的。

对于Scheme中的CPS，很容易混淆，因为源语言和目标语言都是Scheme。