CPS是函数式编程中一个非常常用的概念，将其用在并行程序/硬件设计中可能会起到意想不到的效果。
参考资料的那篇文章以后有时间再讲，这里仅仅介绍CPS的基础。
下面以Haskell的阶乘作为示例。首先是普通的递归。
-- not control statement, but piecewise function
fac :: Int -> Int
fac 1 = 1
fac n = n * fac (n-1)
-- fac 4
-- (4 * fac 3)
-- (4 * (3 * fac 2))
-- (4 * (3 * (2 * fac 1)))
-- (4 * (3 * (2 * 1)))
-- (4 * (3 * 2))
-- (4 * 6)
-- 24
高阶函数
-- higher-order function with lambda expression passed in
fac :: Int -> Int
fac n = foldl (\x xs -> x * xs) 1 [n,n-1..1]
-- fac 4
-- 1 [4,3,2,1]
-- 1 * 4 [3,2,1]
-- 4 * 3 [2,1]
-- 12 * 2 [1]
-- 24 = ((((1*4)*3)*2)*1)
CPS版本
fac :: a -> (a -> r) -> r
fac 1 k = k 1
fac n k = fac (n-1) (\ret -> k (ret * n))
-- fac 4 (\ret -> ret) -- identidy function
-- fac 3 (\ret -> ret * 4)
-- fac 3 (\ret -> (\ret -> ret) (ret * 4))
-- fac 2 (\ret -> ret * 12)
-- fac 1 (\ret -> ret * 24)
-- (\ret -> ret * 24) 1
-- 24
最后附一个C++的尾递归版本。其实尾递归就是CPS的一种类型。
// call fac_tail(n,1)
int fac_tail(int n, int k){
if (n == 1) return k;
else return fac_tail(n-1,n*k);
}
注意CPS整个过程都是正向传递，而且没有用到栈，这给硬件实施带来了极大的好处。