H5W3
当前位置:H5W3 > 其他技术问题 > 正文

函数编程之CPS:Continuous Passing Style

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整个过程都是正向传递,而且没有用到栈,这给硬件实施带来了极大的好处。

参考资料

本文地址:H5W3 » 函数编程之CPS:Continuous Passing Style