2

The parameter of call/cc is a procedure taking as its argument a continuation. Is the procedure written in CPS?

4

2 回答 2

5

不。

CPS 风格的函数期望其他普通函数作为它们的参数，并且可以在尾部位置调用它们。这些函数在 Scheme 白话中被混淆地称为“延续”。我更喜欢“突发事件”，以消除歧义。

参数函数call/cc期望一个实际的未定界延续作为它的参数。那个实际的延续不是一个函数。用一个值调用它会将该值返回到该延续的返回上下文中，从而与延续一起保存——这是一个简单函数闻所未闻的壮举。

尾调用函数将其结果返回到其调用函数的调用者的上下文中。

被调用的延续将提供的值返回到其创建call/cc调用的上下文。因此它不是一个函数。因此使用它的函数不是用 CPS 编写的。

于 2019-08-09T23:16:58.830 回答
1

首先，什么是CPS？延续传递风格是一种将依赖延续（即使用call/cc运算符）的程序编译成不支持延续，但支持词法闭包和尾调用（或尾调用的一些复制品，如当堆栈与实际调用帧太深时回滚堆栈的能力）。

用 CPS 转换的程序本身不是用 continuation-passing 风格编写的。不必如此；它有一个call/cc由 CPS 翻译器提供的操作符，可以在任何需要的地方访问当前的延续。

由于 CPS 主要是源到源的转换，因此使用手写的、明确的 CPS 进行说明和教学。很多时候，Scheme 语言用于此目的。Scheme 语言已经有了call/cc，但是在尝试显式的手写 CPS 时，我们不得不假装它call/cc不存在。在 CPS 范式下，我们当然可以提供一个 operator my-call/cc，它建立在我们的 CPS 之上，与底层 Scheme 的call/cc.

在 CPS 编译的语言实现中，每个过程都有一个延续参数（宿主语言库中的过程除外）。的函数参数call/cc，即接收延续的函数，也不例外。作为 CPS 世界中的过程，它必须具有延续参数，以便它与传递该参数的过程调用兼容。

的论证过程call/cc实际上可以使用那个延续论证，维基百科的第一个例子就证明了这一点。这是该示例的副本，其中我将return参数重命名为c，以减少混淆：

(define (f c)       ;; function used for capturing continuation
  (c 2)             ;; invoke continuation
  3)                ;; if continuation returns, return 3.

(display (f (lambda (x) x))) ; displays 3

(display (call/cc f)) ; displays 2

过程f的c论点不必是延续；在第一次调用中，它只是虚拟函数(lambda (x) x)。f调用它，该函数返回，然后控制权落入 3.

在 CPS 下，f 有一个隐藏的参数，我们可以用手写的 CPS 来揭示：

(define (f c k)
  (c 2 k)
  (k 3 k))

返回时3，是因为调用了隐藏的延续。既然程序可以做到这一点，f就必须有一个。

请注意c和k是不同的延续！也许这就是混淆的地方。c延续是调用者的当前传递call/cc，并且是 的显式语义的一部分call/cc。k是 CPS 变压器添加的隐藏的。是自己的f延续。在 CPS 转换的世界中，每个功能都有一个。在 CPS 范式下，如果希望返回，它会调用（这就是我重命名为的原因）。如果希望继续暂停，则调用。fkreturncfcall/ccc

顺便说一句，在自动 CPS 下，k不会直接称为k，因为这样不卫生：程序可以自由绑定k符号。它必须是机器生成的符号（gensym），或者接受其他形式的卫生处理。

唯一必须在 CPS 下特殊处理以便它们没有连续参数的函数是宿主语言/VM 中的库函数，这些函数可用于 CPS 翻译的语言。当 CPS 翻译的语言调用(display obj)打印一个对象时，该display函数要么必须是一个重命名的包装器，它可以接受延续参数（然后忽略它并在display没有它的情况下调用真正的函数），否则调用display必须特别由 CPS 翻译器处理以省略延续参数。

最后，为什么 CPS 可以在本身不提供它们的语言/VM 中实现延续？原因是 CPS 转换程序中的所有函数调用都是尾调用，因此永远不会返回。实现延续的棘手部分是捕获整个调用堆栈，以便在恢复延续时，它可以返回。这样的功能只能在语言实现级别添加。在 1970 年代，InterLisp 使用“意大利面条堆栈”来实现这一点：堆栈帧是垃圾收集的堆对象，指向父帧。但是如果函数不做返回之类的事情呢？然后在实现中添加意大利面条堆栈的需要就消失了。请注意，意大利面条堆栈并没有完全消失：我们在 CPS 下有一些等效的东西，即捕获的词汇环境链。k参数，它本身是一个捕获其父参数的 lambda ， ...k等等：它是一个环境链，类似于堆栈帧，其中隐藏的k参数是帧指针。但是宿主语言已经为我们提供了词法捕获 lambda。我们刚刚利用这些 lambda实际上代表了连续意大利面条堆栈，因此我们不必深入到实现级别来做任何事情。

于 2019-08-21T20:18:06.477 回答