CPS is a style of programming in which every user function f takes an extra argument c known as a continuation. Whenever f would normally return a result r to its caller, it instead returns of applying the continuation to r. The continuation thus represents the whole of the rest of the computation.
CPS 是一种编程风格，在 CPS 中，每个函数都需要一个额外的参数 c （也就是 continuation，是一个函数）。 任何时候，如果函数 f 通常是返回一个结果 r 给调用者的话， 在 CPS 中，f 返回的将是以 r 为参数调用 c 后的结果。f 之后的运算完全地转化到 c 函数中了。
--normal square x = x * x (square 3) + 1
-- CPS square x c = c (x * x) square 3 (s -> s + 1)
cfold' h z [] = z cfold' h z (x : xs) = h x z (y -> cfold' h y xs)
cfold f z l = cfold' (x t g -> f x (g t)) z l
先不要看 cfold 这个包装。普通的 foldr 或 foldl 中 f 接受两个参数，而 cfold’ 中由于 h 则多了一个参数，为一个函数，我们这里用 k 表示，这就是 continuation。从第二行代码中可以看出，k 为 y -> cfold’ f y xs，它对 xs 进行 cfold’，这和递归比较相似。 再来看 cfold，此时 h 为 x t g -> f x (g t)，观察后可以得出，一般 z 为累加器的，但这里它在每次 cfold’ 的调用中没有变化，一直为初始值不变。 实际上以上过程和 foldr 差不多。 将上面两个函数合并为一个，这样可能会清晰一点。
cfold f z [] = z cfold f z (x : xs) = (x t k -> f x (k t)) x z (y -> cfold f y xs)
最后贴上习题 4.12 我做的答案。
cmap f [] = [] cmap f (x : xs) = (x k -> f x : k) x (cmap f xs)
cfilter p [] = [] cfilter p (x : xs) = (x k -> if p x then x : k else k) x (cfilter p xs)
发布评论
评论（9）
我去翻查了一遍，看来是我记错了，不是在 YAHT 中。当然也许是我看得不够仔细。不管如何，出处不是那么重要。
读某本资料中提到过类似于下面内容的文字：
根据这个思路继续考虑这样一个简单的操作过程：
如果某函数 A ，运行产生数据 a0，a1 ；再调用函数 B，将 a1 作为参数求出返回值 b1；最后将 b1 与 a0 联合运算得到结果。
普通的过程式调用需要将 a0 压栈，等到 b1 得到后才能使用并消耗掉它。
如果 a0 数据非常庞大则数据流或计算流会被严重打断。而且 GC 无法释放这部分资源。
而 CPS 方式可以省去出入栈的操作，再与 lazy 机制适当结合，完全可能仅仅在计算 a0 与 b1 时才存在这样一个庞大的数据。
这是程序员编写更合理、更高质量的程序的一条捷径。
[ 本帖最后由 leaveye 于 2009-4-29 18:40 编辑 ]
具体什么地方？
YAHT 里说了 CPS 是为了优化栈空间使用而诞生的。
比如：
复制代码
在调用 fac n 的时候，会把刚求出来的 n+1 与 (*) 运算压栈；求出 fac n 后，再结合到出栈后的表达式中，计算结果。
而 cps 就是把要压栈的这些计算、逻辑、操作，统统地交给内部调用函数去做，这样可以直接返回结果，节省了这些栈空间。
我试着写一个 cps 版本的 fac 如下：
复制代码
Continuation passing style 在 Haskell 中是高阶函数的一种应用吧 ？
点击
以下是网上搜的：
CPS is a style of programming in which every user function f takes an
extra argument c known as a continuation. Whenever f would normally
return a result r to its caller, it instead returns of applying the
continuation to r. The continuation thus represents the whole of the
rest of the computation.
CPS 是一种编程风格，在 CPS 中，每个函数都需要一个额外的参数 c （也就是 continuation，是一个函数）。
任何时候，如果函数 f 通常是返回一个结果 r 给调用者的话，
在 CPS 中，f 返回的将是以 r 为参数调用 c 后的结果。f 之后的运算完全地转化到 c 函数中了。
--normal
square x = x * x
(square 3) + 1
-- CPS
square x c = c (x * x)
square 3 (s -> s + 1)
现在再来看 YAHT 的那个 CPS 版 fold。为了清晰，我将 cfold’ 中的 f 统一改为 h。
cfold' h z [] = z
cfold' h z (x : xs) = h x z (y -> cfold' h y xs)
cfold f z l = cfold' (x t g -> f x (g t)) z l
先不要看 cfold 这个包装。普通的 foldr 或 foldl 中 f 接受两个参数，而 cfold’ 中由于 h 则多了一个参数，为一个函数，我们这里用 k 表示，这就是 continuation。从第二行代码中可以看出，k 为 y -> cfold’ f y xs，它对 xs 进行 cfold’，这和递归比较相似。
再来看 cfold，此时 h 为 x t g -> f x (g t)，观察后可以得出，一般 z 为累加器的，但这里它在每次 cfold’ 的调用中没有变化，一直为初始值不变。
实际上以上过程和 foldr 差不多。
将上面两个函数合并为一个，这样可能会清晰一点。
cfold f z [] = z
cfold f z (x : xs) = (x t k -> f x (k t)) x z (y -> cfold f y xs)
最后贴上习题 4.12 我做的答案。
cmap f [] = []
cmap f (x : xs) = (x k -> f x : k) x (cmap f xs)
cfilter p [] = []
cfilter p (x : xs) = (x k -> if p x then x : k else k) x (cfilter p xs)
怎么有感觉不像 CPS 了呢？（主要是我还不知道在 Haskell 中怎么写没有参数的匿名函数呢！还是根本没有这概念？
）
[ 本帖最后由 izhier 于 2009-4-29 14:30 编辑 ]
倒也没有必要，continuation 多看点例子就理解了，Lisp，例如 Scheme，里面这个用的比较多。Haskell 曾经用 CPS 实现 I/O，不过后来换 monad 了。
Continuation passing style
是不是关乎continuation?
这玩意可真难理解， 我觉的要想掌握得要点编译器或解释器实现方面的知识
cps 是啥