9

像 lambda calculus 或 Ocaml 这样的柯里化语言中的CPS有什么意义？从技术上讲，所有函数都有一个参数。假设我们有一个 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 来解决这个返回值，因为我们只能给每个函数一个参数。我们需要至少有两个来为延续和“实际”论证腾出空间。

还是我完全错过了什么？

4

3 回答 3

10

既然你已经用 Haskell 标记了这个，我会在这方面回答：在 Haskell 中，相当于在Contmonad 中进行 CPS 转换，它将一个值x转换为一个接受一个参数并应用它的高阶函数到x.

所以，首先，这里是常规 Haskell 中的 1 + 2：(1 + 2)这里是 continuation monad：

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

...信息量不大。为了看看发生了什么，让我们拆解 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')))

运算符（读作“bind”）将(>>=)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本身仍然采用咖喱风格的两个论点。这是明智的，因为它不直接使用延续，但不是必需的。否则，您需要首先在参数之间拆分函数：

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

然后像这样使用它：

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

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

请记住，我在这里以非常冗长的方式写出东西，以明确所有步骤，其中某些东西处于延续传递风格。

附录：您可能会注意到最终表达式看起来与单子表达式的脱糖版本非常相似。这不是巧合，因为单子表达式的内嵌特性允许它们根据先前的值改变计算结构，这与延续传递风格密切相关。在这两种情况下，你在某种意义上都具体化了因果关系的概念。

于 2010-12-22T18:06:56.857 回答
2

简短的回答：当然是有道理的，你可以直接应用 CPS 变换，你只会有很多麻烦，因为每个参数都会有，正如你所注意到的，它自己的附加延续

在您的示例中，我将考虑有一个+(x,y)未咖喱的原语，并且您要问的翻译是什么

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

如果您想要一个看起来更像您愿意编写的代码的翻译代码，您可以设计一个更精细的转换，实际上将 known-arity 函数视为非柯里化函数，并将所有参数作为一个整体进行处理（就像您在 non-柯里化语言，并且由于明显的性能原因，函数式编译器已经这样做了）。

¹：我写了“一个CPS 转换”，因为没有“一个真正的 CPS 转换”。已经设计了不同的翻译，产生或多或少与延续相关的垃圾。正式的 CPS 转换通常直接在 lambda-calculus 上定义，所以我想你有一个不太正式、更手工制作的 CPS 转换。

CPS 的良好特性（作为程序尊重的一种风格，而不是对该风格的特定转换）是评估顺序是完全明确的，并且所有调用都是尾调用。只要你尊重这些，你就可以相对自由地做你能做的事。因此，专门处理 curryfied 函数非常好。

备注：(cps-add k 1 2)如果您假设编译器检测并优化 cps-add 实际上总是采用 3 个参数，并且不构建中间闭包，那么您的版本也可以被视为尾递归。这似乎有些牵强，但这与我们在推理非 CPS 程序中的尾调用时使用的假设完全相同，在这些语言中。

于 2010-12-22T17:43:11.530 回答
0

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

使用您的示例，让我们看看。为了让事情更容易一些，让我们将 cps-add 解构为它的正常形式，它是一个只接受一个参数的函数。

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

请注意，在这一点上，没有对延续 k 进行评估（这可能是您的困惑点吗？）。

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

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

现在我们有了一个带参数的函数，m。

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

于 2010-12-22T17:00:01.127 回答