调用/抄送是如何处理从"Lisp in Pieces“到CPS的转换的？

Question

图书Lisp的小部分演示了从Scheme到延续传递风格的转换(第5.9.1章，对于那些能够访问这本书的人来说)。转换表示由lambda窗体进行的延续，而call/cc被认为是等效于一个简单的(lambda (k f) (f k k))。

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

下面是从应用程序以外的所有内容中删除的转换版本(完整版本可以在这个要旨中找到)：

(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 '()))))

现在考虑来自维基百科的CPS示例

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

上面的转换将把函数体(return 2)中的应用程序转换为类似于(return (lambda (g13) ...) 2)的东西。延续作为第一个参数传递，值2作为第二个参数传递。如果return是一个普通的函数，这将是很好的。然而，return应该是一个延续，它只需要一个参数。

我看不出这两块是怎么拼在一起的。转换如何将连续表示为lambda表单，而不特别考虑它们的应用？

Answer 1

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

在没有CPS的情况下实现连续需要虚拟机级的方法，例如使用“意大利面堆栈”：在堆分配的帧中分配受垃圾收集影响的词法变量。捕获一个延续就意味着获得一个环境指针，它引用了意大利面堆栈中的一个词法框架。

CPS通过闭包构建一个事实上的意大利面堆栈。闭包将词法绑定捕获到具有无限生存期的对象中。在CPS下，所有闭包都捕获隐藏变量k。该k在意大利面堆栈中充当父帧指针的角色；它将闭包链接在一起。

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

拼图中缺少的一个部分是CPS依赖于尾调用。尾调用确保我们没有使用真正的堆栈；所有有趣的东西都在关闭的环境中。

(然而，即使是尾部呼叫也不是严格要求的，正如亨利·贝克( Henry )在“鸡计划”中所体现的那样，它教会了我们。我们的CPS转换代码可以使用使用堆栈的真正调用，但永远不会返回。每隔一段时间，我们就可以将可访问的环境帧(和所有偶然对象)从堆栈移到堆中，并将堆栈指针倒转。)

现在考虑维基百科中的CPS示例：

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

如果我们手动将它转换为CPS，或者使用机械的编译器，它就变成了CPS。

然而，返回应该是一个延续，它只需要一个参数。

因此，返回只使用一个参数，因为我们正在查看尚未被CPS转换的应用程序源代码。

应用程序级的连续使用一个参数。

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

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

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