库里语言中的CPS

Question

像lambda演算或Ocaml这样的curried语言中的CPS是如何理解的呢？从技术上讲，所有函数都有一个参数。因此，假设我们有这样一种语言的addition的CPS版本：

cps-add k n m = k ((+) n m)

我们这样称呼它

(cps-add random-continuation 1 2)

这与以下内容相同：

(((cps-add random-continuation) 1) 2)

我已经看到了两个不是尾部调用的调用，实际上是一个复杂的嵌套表达式，(cps-add random-continuation)返回一个值，即一个消耗数字的函数，然后返回一个函数，该函数消耗另一个数字，然后将两者的和传递给那个random-continuation。但我们不能通过简单地将其再次转换为CPS来解决这个值返回问题，因为我们只能为每个函数提供一个参数。我们需要至少有两个参数，以便为延续和“实际”参数腾出空间。

还是我完全漏掉了什么？

Answer 1

既然您已经用Haskell对其进行了标记，我将从这方面回答:在Haskell中，进行CPS转换相当于在Cont monad中工作，它将一个值x转换为一个高阶函数，该函数接受一个参数并将其应用于x。

因此，首先，这里是常规Haskell：(1 + 2)中的1+2，这里是延续单数：

contAdd x y = do x' <- x
                 y' <- y
                 return $ x' + y'

...not的信息量非常大。为了看看到底是怎么回事，让我们来分解一下monad。首先，删除do表示法：

contAdd x y = x >>= (\x' -> y >>= (\y' -> return $ x' + y'))

return函数将一个值提升到monad中，在本例中，它被实现为\x k -> k x，或者使用中缀运算符节来实现为\x -> ($ x)。

contAdd x y = x >>= (\x' -> y >>= (\y' -> ($ x' + y')))

绑定操作符(读作“(>>=)”)将monad中的计算链接在一起，在本例中被实现为\m f k -> m (\x -> f x k)。将绑定函数更改为前缀形式，并在lambda中进行替换，另外为清楚起见还进行了一些重命名：

contAdd x y = (\m1 f1 k1 -> m1 (\a1 -> f1 a1 k1)) x (\x' -> (\m2 f2 k2 -> m2 (\a2 -> f2 a2 k2)) y (\y' -> ($ x' + y')))

减少一些函数应用：

contAdd x y = (\k1 -> x (\a1 -> (\x' -> (\k2 -> y (\a2 -> (\y' -> ($ x' + y')) a2 k2))) a1 k1))

contAdd x y = (\k1 -> x (\a1 -> y (\a2 -> ($ a1 + a2) k1)))

以及一些最终的重新排列和重命名：

contAdd x y = \k -> x (\x' -> y (\y' -> k $ x' + y'))

换句话说:函数的参数已经从数字更改为接受数字并返回整个表达式的最终结果的函数，正如您所预期的那样。

编辑：一位评论者指出，contAdd本身仍然以curried样式接受两个参数。这是合理的，因为它不直接使用continuation，但不是必需的。要做到这一点，首先需要在两个参数之间拆分函数：

contAdd x = x >>= (\x' -> return (\y -> y >>= (\y' -> return $ x' + y')))

然后像这样使用它：

foo = do f <- contAdd (return 1)
         r <- f (return 2)
         return r

请注意，这实际上与早期版本没有什么不同；它只是将每个部分应用程序的结果打包为一个延续，而不仅仅是最终结果。由于函数是第一类值，因此包含数字的CPS表达式与包含函数的CPS表达式之间没有显著差异。

请记住，我在这里以非常冗长的方式写出了内容，以使某些内容处于延续传递样式的所有步骤都是明确的。

附录:您可能会注意到，最终表达式看起来与一元表达式的去糖版本非常相似。

Answer 2

简而言之:当然这是有意义的，你可以直接应用CPS转换，你只会有很多的麻烦，因为正如你所注意到的，每个参数都有它自己的附加延续。

在您的示例中，我将考虑有一个+(x,y) uncurried原语，并且您要询问的是

let add x y = +(x,y)

(这个add忠实地代表了OCaml的(+)运算符)

add在语法上等同于

let add = fun x -> (fun y -> +(x, y))

因此，您可以应用CPS变换?并获得

let add_cps = fun x kx -> kx (fun y ky -> ky +(x,y))

如果您希望转换后的代码看起来更像您心甘情愿地编写的代码，那么您可以设计一种更精细的转换，将已知函数视为非curried函数，并将所有参数作为一个整体进行处理(就像您在非curried语言中所做的那样，而且出于明显的性能原因，函数编译器已经这样做了)。

²：我写了“一个CPS转换”，因为没有“一个真正的CPS转换”。已经设计了不同的翻译，或多或少产生了与延续相关的垃圾。正式的CPS转换通常是直接在lambda演算上定义的，所以我想您的脑海中应该有一个不那么正式、更手工的CPS转换。

CPS (作为一种程序所尊重的风格，而不是这种风格的具体转换)的良好特性是，计算顺序是完全明确的，并且所有调用都是尾部调用。只要你尊重这些，你就可以相对自由地做你能做的事情。因此，专门处理货币化函数是非常好的。

备注:如果你假设编译器检测到并优化了cps-add实际上总是带3个参数，并且不构建中间闭包，那么你的(cps-add k 1 2)版本也可以被认为是尾递归的。这可能看起来很牵强，但这与我们在那些语言中对非CPS程序中的尾部调用进行推理时所使用的假设完全相同。

Answer 3

是的，从技术上讲，所有的函数都可以用一种方法分解成函数，然而，当你想使用CPS时，你唯一要做的就是在某个计算点上运行continuation方法。

使用您的示例，让我们来看看。为了让事情简单一点，让我们解构cps-add到它的标准形式，它是一个只接受一个参数的函数。

(cps-add k) -> n -> m=k ((+) n m)

注意，在这一点上，续集k没有被计算(这会是您感到困惑的地方吗？)。

这里我们有一个名为cps-add k的方法，它接收一个函数作为参数，然后返回一个接受另一个参数n的函数。

((cps-add k) n) -> m=k ((+) n m)

现在我们有了一个接受参数m的函数。

所以我想我想要指出的是，trying不会妨碍CPS风格的编程。希望这能在某种程度上有所帮助。