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))。

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

这是从应用程序以外的所有内容中剥离出来的转换版本（完整版本可以在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 '()))))

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

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

上述改造将在函数体中的应用程序转换(return 2)成类似(return (lambda (g13) ...) 2)。连续作为第一个参数传递，值2作为第二个参数传递。如果return是普通函数，那会很好。但是，return应该是连续的，只需要一个参数。

我看不到各个部分如何组合在一起。转换如何将延续表示为lambda形式，但不特别考虑其应用？

Answer 1

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

在没有CPS的情况下实现连续性需要在虚拟机级别上使用一些方法，例如使用“意大利面条堆栈”：在堆分配的框架中分配词法变量，这些框架需要进行垃圾回收。捕获延续则意味着获取环境指针，该指针指向意大利面条堆栈中的词汇框架。

CPS 从封口中构建事实上的意大利面条堆栈。闭包将词法绑定捕获到具有不确定生存期的对象中。在CPS下，所有闭包均捕获隐藏变量k。也就是说ķ服务于意大利面条堆父帧指针的作用; 它将瓶盖扣在一起。

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

难题中缺少的一个方面是CPS依赖于尾号。尾调用确保我们没有使用真实的堆栈。所有有趣的事情都是在封闭环境中进行的。

（但是，甚至连严格的尾部调用也不是必须的，正如在Chicken Scheme中体现的Henry Baker的方法告诉我们的那样。我们经过CPS转换的代码可以使用消耗堆栈的实际调用，但永远不会返回。每隔一段时间我们就可以移动从堆栈到堆栈的可访问环境框架（以及所有或有对象），然后倒回堆栈指针。）

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

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

如果我们手动将其转换为CPS，或者使用机械地进行转换的编译器，则它将变为CPS。

但是，return应该是连续的，只需要一个参数。

因此，return只需要一个参数，因为我们正在研究尚未经过CPS转换的应用程序源代码。

应用程序级的延续只有一个参数。

像所有功能一样，CPS实现级别的延续将具有隐藏的k参数。

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

对于Scheme中的CPS，很容易感到困惑，因为源语言和目标语言都是Scheme。