用咖喱语言的CPS

如果像lambda演算或Ocaml这样的curry语言中的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来解决这个值，因为我们只能给每个函数一个参数。我们需要至少有两个为继续和“实际”论证腾出空间。还是我完全错过了什么？

已邀请:

3 个回复

肉簧咸缮

既然你已经用Haskell标记了这个，我将在这方面回答：在Haskell中，相当于进行CPS变换的工作在Contmonad中，它将值ѭ6trans转换为带有一个参数的高阶函数，适用于x。所以，首先，这里是常规Haskell中的1 + 2：(1 + 2)这里是继续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')))

(>>=)运算符（读“绑定”）将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表达式与持有函数的CPS表达式之间没有显着差异。请记住，我在这里以非常冗长的方式写出来，以明确表示某些事物处于延续传递风格的所有步骤。附录：您可能会注意到最终表达式与monadic表达式的脱糖版本非常相似。这不是巧合，因为monadic表达式的向内嵌套性质使它们能够根据先前的值改变计算结构，这与继续传递风格密切相关;在这两种情况下，你在某种意义上都有一种因果关系的概念。

谦响局豢报

简短的回答：当然有道理，你可以直接应用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))

如果你想要一个看起来更像是你愿意写的东西的翻译代码，你可以设计一个更精细的转换，实际上将已知的arity函数视为非curried函数，并将所有参数作为一个整体进行处理（就像你在非咖喱语言，以及功能编译器已经出于明显的性能原因而已。 ¹：我写了“CPS变换”，因为没有“真正的CPS翻译”。已经设计了不同的翻译，产生或多或少与延续相关的垃圾。正式的CPS翻译通常直接在lambda演算上定义，所以我想你在考虑一个不太正式，更加手工制作的CPS变换。 CPS的良好属性（作为一种程序方面的风格，而不是对此风格的特定转换）是评估的顺序是完全明确的，并且所有调用都是尾调用。只要你尊重这些，你就可以做得相对自由。因此，专门处理curryfied功能是完全正确的。备注：如果您假设编译器检测并优化cps-add实际上总是需要3个参数，并且不构建中间闭包，那么您的(cps-add k 1 2)版本也可以被认为是尾递归的。这可能看起来很牵强，但在使用这些语言推理非CPS程序中的尾部调用时，我们使用的假设完全相同。

冲汉

是的，从技术上讲，所有函数都可以用一种方法分解为函数，但是，当你想使用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。所以我想我想要指出的是，currying不会妨碍CPS风格的编程。希望在某种程度上有所帮助。

要回复问题请先登录或注册

用咖喱语言的CPS

3 个回复

发起人

continuation_passing

问题状态

用咖喱语言的CPS

与内容相关的链接

3 个回复

发起人

continuation_passing

问题状态