CPS变换

CPS变换

为什么函数调用需要保存状态?

add(1,2) mul(3,4) 这种调用明显不需要保存状态
而add(1,mul(1,2)) 这种计算是需要保存1级函数add的变量,再计算2级函数mul返回值和保存相加最终返回

得出一个结论:函数处在参数位置上,调用后需要返回的函数调用才需要保存状态
而什么是尾调用?无需返回的函数调用
一个简单的判定原则 即函数不在参数位置上

如何避免函数调用时保存状态?

  • Inline函数
    编译器将函数就地展开,本质上是没有函数,只是代码片段的重复
  • 尾调用
    在函数返回的时候调用,这样主函数该做的都做完了,无需返回,只是将指针跳转,计算结果就是子函数的入参,无需额外变量的保存,函数调用过程可以参考文章 函数调用
尾递归实例
1
2
3
4
5
6
7
8
// fact_iter(n-1, mcc * n) 不处在任何函数的参数位置上
@annotaion.tailrec //确保是尾递归否则编译器会报错
def fact_iter(n: Int, mcc: Int): Int = {
if (n==0)
mcc
else
fact_iter(n-1, mcc * n)
}
非尾递归实例

而下面的例子不是尾递归,因为他处在函数”*“的第二个参数位置上, + - * / 实际上都是函数

1
2
3
4
5
6
7
8
// fact_rec(n-1) 在函数乘"\*"的第二个参数位置上
fact_rec = x => x==1 ? 1 : x * fact_rec(x-1)
def fact_rec(n: Int): Int = {
if (n==0)
1
else
n * fact_rec(n - 1)
}

循环实现

因为尾递归无需返回,结果只跟出入的参数有关,因此只需要少量变量记录入参的变化,就能轻易改写成循环形式,因此尾递归和循环是等价的。改写循环:

1
2
3
4
5
function fact_loop(x) {
var r = 1
while (x >= 1) { r *= x; x--; }
return r
}
CPS变换实现

我们把CPS(Continuation Passing Style)的continuation函数按发音简称kont函数

kont函数在后面讲到扮演的是个随从角色,我们也叫kont随从函数

1
2
3
4
5
6
7
@annotation.tailrec
def fact_ite(n: Int, kont: Int => Int): Int = {
if (n==0)
kont(1)
else
fact_ite(n - 1, x => kont(x * n))
}

x => kont(x * n)是一个新函数,把保存的脏活交给了这个函数,主函数只负责进入,并不返回
所以无需压栈保存,kont函数像个随从,主函数丢一个n给他,他负责保管
保管的方式就是n*(n-1)*(n-2)... 直到最终返回他自己

n*fact_iter(n-1)
n*(n-1) *fact_iter(n-2)
n*(n-1)*(n-2) *fact_iter(n-2)
n*(n-1)*(n-2)*(n-3) *fact_iter(n-2)
...........................*fact_iter(0)
n*(n-1)*(n-2)*(n-3)* ......*1

为什么不用循环实现,要搞这么复杂CPS变换实现的目的是什么?

我们知道函数式编程里面实际上不用循环,循环是有副作用的, 仰仗于函数式编程强大的计算力,循环归类到低等公民

函数式编程的重要思想是描述问题,而不是如何执行求解问题的过程。求解的问题依赖于程序或者编译器,会大量的用到递归,而不加处理的递归会有栈开销的问题,为了避免递归的栈开销甚至爆栈缺点,CPS变换可以使得递归能被良好的使用

Fibonacci CPS变化实例

对于斐波那契函数常规的递归实现

1
2
3
4
5
6
def fib0(n: Int): Int = {
n match {
case 0 => 1
case 2 => 1
case _ => fib0(n-1) + fib0(n-2)
}

一般的尾递归优化实现

1
2
3
4
5
6
7
8
@annotation.tailrec
def fibtail(n:Int, nxt: Int, res: Int): Int = {
n match {
case 0 => res
case _ => fibtail(n - 1, nxt + res, nxt )
}
}
val a3 = fibtail(9, 1, 0)

对于有两个递归进入的函数怎么构造CPS的kont随从函数?
2个函数进入,这就要求kont函数接纳2个结果入参,而kont函数要求只能接纳1个参数,请问怎么办?
2个参数怎么变成1个参数的函数?如果你还有印象,那就是闭包

1
2
3
4
5
6
7
8
9
@annotation.tailrec
def fib2(n: Int, kont: (Int) => Int): Int = {
n match{
case 0 => kont(1)
case 1 => kont(1)
case _ => fib2(n-1, x => fib2(n-2 , y=> kont(x + y)))
//第二个kont参数本质是携带第一个参数的闭包
}
}

但是编译发现,会报错,SCALA编译器并不能将其优化成尾递归函数,不加检查时能正常执行。
为什么没有尾递归优化?实际上scala只做了一些简单的tailrec优化,这种复杂的嵌套优化需要一写技巧,那就是:
Trampoline技法
需要手动的强制弹出下一层调用函数,禁止解释器压栈的行为

举一反三

构造一个这样的序列f(n) = f(n-3)*f(n-2)*f(n-1), 看看如何使用CPS变换
其中初始值f(0)=1,f(1)=1,f(2)=2

1
2
3
4
5
6
def inter(n: Int): Int = {
if (n == 0) 1
else if( n== 1 ) 1
else if( n== 2 ) 2
else inter(n-3) * inter(n-2) * inter(n-1)
}

CPS变化

1
2
3
4
5
6
@annotation.tailrec
def inter(n: Int, kont:(Int)=>Int): Int = {
if (n == 0) kont(1)
else if( n== 1 ) kont(1)
else if( n== 2 ) kont(2)
else inter(n-3, x=>inter(n-2,y=>inter(n-1, z=>kont(x*y*z))))

通过3级闭包函数实现,将3个参数携带进去

CPS变化

参考文献:
基于CPS变换的尾递归转换算法

评论