CPS变换

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

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

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

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

Inline函数
编译器将函数就地展开，本质上是没有函数，只是代码片段的重复
尾调用
在函数返回的时候调用，这样主函数该做的都做完了,无需返回,只是将指针跳转,计算结果就是子函数的入参,无需额外变量的保存,函数调用过程可以参考文章函数调用

尾递归实例

// 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)
  }

非尾递归实例

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

// 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) 
  }

循环实现

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

function fact_loop(x) {
    var r = 1          
    while (x >= 1) { r *= x; x--; }
    return r 
}

CPS变换实现

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

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

@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变化实例

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

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

一般的尾递归优化实现

@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个参数的函数？如果你还有印象，那就是闭包

@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

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变化

@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))))