haskell - curry 语言的 CPS

Question

CPS如何像 lambda 演算或 Ocaml 这样的 curry 语言甚至有意义吗？从技术上讲，所有函数都有一个参数。假设我们有一个 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 中，相当于在 Cont 中进行 CPS 转换。 monad，它转换一个值 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')))

(>>=)运算符(读作“bind”)将 monad 中的计算链接在一起，在这种情况下实现为 \m f k -> m (\x -> f x k) .将绑定(bind)函数更改为前缀形式并替换为 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本身仍然采用 curry 风格的两个参数。这是明智的，因为它不直接使用延续，但不是必需的。否则，您需要首先在参数之间拆分函数:

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

然后像这样使用它:

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

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

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

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