haskell - curry 语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来解决此值返回问题，因为我们只能为每个函数提供一个参数。我们至少需要有两个空间来为延续和“实际”论证腾出空间。

还是我完全错过了什么？

最佳答案

既然您已经用Haskell对此进行了标记，那么我将在这方面回答:在Haskell中，相当于CPS转换的工作在Cont 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表达式与拥有函数的CPS表达式之间没有显着差异。

请记住，我在这里以非常冗长的方式编写内容，以明确显示连续传递样式中的所有步骤。

附录:您可能会注意到，最终表达式看起来与单子(monad)表达式的减糖版本非常相似。这不是巧合，因为单子(monad)表达式的向内嵌套性质使它们能够基于先前的值更改计算的结构与延续传递样式密切相关；在这两种情况下，您都在某种程度上证实了因果关系的概念。

关于haskell - curry 语CPS，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4511472/