CPS以咖喱语言

Question

CPS如何使用lambda微积分或Ocaml等口头语言更有意义？从技术上讲，所有功能都有一个参数。所以说，我们在一个这样的语言有另外的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

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

用你的例子，让我们看看。为了使事情变得容易一点，我们将cps-add解构成它的正常形式，它只是一个只有一个参数的函数。

（CPS-添加K） - > N - > M = K（（+）纳米）在这一点上的延续，K，没有被评估（

注意这会是混乱的点为你？）。

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

（（CPS-添加k）的N） - > M = K（（+）n×m个）

现在，我们有一个函数，它的参数，米。

所以我想我要指出的是，咖喱没有得到CPS风格编程的方式。希望在某种程度上有所帮助。

Answer 2

简短的回答：当然，这是有道理的，你可以申请一个CPS-直接转化，你只会有大量的冗余代码，因为每个参数都会有，因为你注意到没有，自己的附加延续

在你的榜样，我认为有一个+(x,y) uncurried原始的，而且你问什么是

let add x y = +(x,y) 

翻译（这add忠实代表OCaml中的(+)运营商）

add是syntaxically相当于

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

所以你申请一个CPStransform¹并获得

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

如果你想翻译的代码看起来更像是一些你可能会心甘情愿地写，你就可以设计出更细转换实际上将已知函数看作非curry函数，并将所有参数作为一个整体进行调整（就像您使用非curry语言以及功能性编译器已经出于显而易见的性能原因所做的那样）。

¹：我写了“a CPS变换”，因为没有“一个真正的CPS翻译”。已经设计了不同的翻译，产生或多或少的与连续相关的垃圾。正式的CPS翻译通常是直接在lambda演算中定义的，所以我想你正在考虑一个不太正式的，更手工的CPS转换。

CPS的良好属性（作为编程方面的风格，而不是对此风格的具体转换）是评估的顺序是完全明确的，并且所有调用都是尾调用。只要你尊重这些，你就可以做到相对自由。因此特别处理curryfied功能非常好。

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

Answer 3

既然你已经标记此哈斯克尔，我会在这方面的回答：在Haskell，做CPS变换相当于在Cont单子，其转换价值x成高阶函数工作是采用一个参数并将其应用于x。

所以，首先，这里是1 + 2规则哈斯克尔：(1 + 2)这里，它是在延续单子：

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

...不是非常翔实。为了看看发生了什么，让我们拆开monad。首先，除去do符号：

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

的return函数升降机一个值到单子，并且在这种情况下被实施为\x k -> k x，或使用中缀运算符截面\x -> ($ x)。

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

的(>>=)操作（读“绑定”）链一起计算在单子，并且在这种情况下被实现为\m f k -> m (\x -> f x k)。更改绑定功能，以前缀的形式，并在拉姆达取代，再加上一些重命名为清楚：

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表达式与保持函数的CPS表达式之间没有显着差异。

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

---

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