有没有人能详细讲解一下cps

yk2009

rt,我在看yath看蒙了。

izhier

cps 是啥

chenzengjie

是不是关乎continuation?

这玩意可真难理解， 我觉的要想掌握得要点编译器或解释器实现方面的知识

MMMIX

原帖由 izhier 于 2009-4-29 11:55 发表
cps 是啥

Continuation passing style

MMMIX

原帖由 chenzengjie 于 2009-4-29 13:24 发表
是不是关乎continuation?

这玩意可真难理解， 我觉的要想掌握得要点编译器或解释器实现方面的知识

倒也没有必要，continuation 多看点例子就理解了，Lisp，例如 Scheme，里面这个用的比较多。Haskell 曾经用 CPS 实现 I/O，不过后来换 monad 了。

izhier

点击
以下是网上搜的：

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 编辑 ]

izhier

Continuation passing style 在 Haskell 中是高阶函数的一种应用吧 ？

leaveye

YAHT 里说了 CPS 是为了优化栈空间使用而诞生的。

比如：

1. fac (n+1) = (n+1) * fac n
   
2. fac 0 = 1

复制代码

在调用 fac n 的时候，会把刚求出来的 n+1 与 (*) 运算压栈；求出 fac n 后，再结合到出栈后的表达式中，计算结果。
而 cps 就是把要压栈的这些计算、逻辑、操作，统统地交给内部调用函数去做，这样可以直接返回结果，节省了这些栈空间。

我试着写一个 cps 版本的 fac 如下：

1. fac' n = faccps n id
   
2.   where
   
3.     faccps (n+1) f = faccps n (f . (*) (n+1))
   
4.     faccps 0 f = f 1

复制代码

MMMIX

原帖由 leaveye 于 2009-4-29 17:56 发表
YAHT 里说了 CPS 是为了优化栈空间使用而诞生的。

具体什么地方？

leaveye

我去翻查了一遍，看来是我记错了，不是在 YAHT 中。当然也许是我看得不够仔细。不管如何，出处不是那么重要。

读某本资料中提到过类似于下面内容的文字：

过程式函数调用操作是将返回点地址压栈，跳转到相应函数；函数完成后，从栈中取出下一步代码（返回点）的地址，继续执行。CPS 式的函数调用可以由程序员指定压栈的返回点，而不产生任何额外负担。

根据这个思路继续考虑这样一个简单的操作过程：
如果某函数 A ，运行产生数据 a0，a1 ；再调用函数 B，将 a1 作为参数求出返回值 b1；最后将 b1 与 a0 联合运算得到结果。

普通的过程式调用需要将 a0 压栈，等到 b1 得到后才能使用并消耗掉它。
如果 a0 数据非常庞大则数据流或计算流会被严重打断。而且 GC 无法释放这部分资源。
而 CPS 方式可以省去出入栈的操作，再与 lazy 机制适当结合，完全可能仅仅在计算 a0 与 b1 时才存在这样一个庞大的数据。
这是程序员编写更合理、更高质量的程序的一条捷径。

[ 本帖最后由 leaveye 于 2009-4-29 18:40 编辑 ]