CPS用咖喱语言

Question

如果像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来解决这个值,因为我们只能给每个函数一个参数.我们需要至少有两个为继续和"实际"论证腾出空间.

还是我完全错过了什么？

Answer 1

既然你已经用Haskell标记了这个,我将在这方面回答:在Haskell中,相当于执行CPS转换的工作在Contmonad中,它将一个值x转换为一个高阶函数,该函数接受一个参数并应用它到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')))

的(>>=)操作者(读"绑定")链一起计算在单子,并且在这种情况下被实现为\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表达式的向内嵌套性质使它们能够根据先前的值改变计算结构,这与继续传递风格密切相关; 在这两种情况下,你在某种意义上都有一种因果关系的概念.

Answer 2

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

用你的例子，让我们看一下。为了让事情变得更简单，让我们将 cps-add 解构为其正常形式，其中它是一个仅采用一个参数的函数。

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

请注意，此时未对延续 k 进行求值（这可能是您的困惑点吗？）。

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

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

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

所以我想我想指出的是柯里化并不会妨碍 CPS 风格的编程。希望能以某种方式有所帮助。