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整个过程都是正向传递，而且没有用到栈，这给硬件实施带来了极大的好处。
参考资料
- Tao Chen, Shreesha Srinath, Christopher Batten, and G. Edward Suh, An Architectural Framework for Accelerating Dynamic Parallel Algorithms on Reconfigurable Hardware, MICRO, 2018
- Haskell: problems fully defining factorial in Continuation Passing Style, https://stackoverflow.com/questions/4773738/haskell-problems-fully-defining-factorial-in-continuation-passing-style
- 尾递归、CPS等几种求阶乘的算法, https://www.xuebuyuan.com/1661988.html
- 漫谈递归：尾递归与CPS, http://www.nowamagic.net/librarys/veda/detail/2331
- 函数式编程与Continuation/CPS, http://www.nowamagic.net/academy/detail/1220553
