为什么函数式编程至关重要

函数式程序的特点

函数式编程不包含任何赋值语句（也就是没有变量），所有的值从一开始就确定了
函数式编程不包含副作用，除了计数它本身的值以外不产生任何副作用，这一特性消灭了bug的一个主要来源
函数式编程值是一定的，那么执行顺序就不在重要，所以它可以在任何时候被执行，这一过程将程序员从控制流中解放
由于在任意时候求值，程序员可以随性所欲的用变量值来代替变量表达式，反之也可以用变量表达式代替变量的值。程序是引用透明，可以更容易的数学化控制
函数是一等公民，函数式编程中努力用函数来表达所有的概念，完成所有的操作
变量的不变性，赋值操作低人一等。简单将在scala函数是编程中只用val，不用var

函数式编程比传统编程代码更简洁，很大程度上是由于传统是编程90%的事情都是在干赋值的事，函数式编程这些都可以忽略。
这仅仅是它的一个好处，不是说它就是函数式编程语言强大的原因

假如有两个函数g,f, 对于输入参数x假设是一个很长的序列, 要计算 g(f(x))
传统的解决方法是先计算f(x)储存到临时文件中，这种方法临时文件可能占用很大的空间。
函数式语言的解决方案是，程序g,f严格同步执行，只有当g需要数的时候它才会触发f，f从x取一个数计算返回给g，直到g试图获取下一个值。f的启动和终止取决于g，f甚至不会自行终止程序，因为当g运行结束时，f也会强制终止，这是的终止条件和循环体分离。
这种求值方式按需求值，无需不求值，尽可能的减少运行，因此被称之为惰性求值。
它使得将程序模块化为一个能产生大量可能解的生成器以及一个恰当的选择器变的可行。

惰性求值跟函数式编程的关系

惰性求值有什么好处？

优化，有显著的优化潜力，函数可以消消乐而不必都要求值运算
抽象控制结构，普通的判断语句有了宏的能力
if(condition)
```
function_code ;
```
condition是个待求的值，惰性求值中，如果condition最后的值为false时
function_code根本不会被求值，而在迫切求值过程中，condition的值依赖于当前的实时值
那么function_code就有可能被计算
无穷的数据结构
g(f(x)), f(x), x 都可以是个无穷序列，他的终止仅仅依赖于g函数的终止条件，具备这种能力的
原因就是惰性求值，每当计算一个g(f(x))时，g会访问f，f访问x 用多少取多少，不用不取，不必
讲所有的f(x) 都求好缓存，然后再计算g

无穷长数据的列表有什么好处？为什么要用无穷长列表？待补充，

惰性求值有什么缺点：

不能保证执行顺序

1 2	system.out.println("Please enter file name:") system.in.readfile(fileinput)

现实中很多问题是需要严格的执行顺序(也就是有状态)，比如IO输入输出操作, 也就是所谓的副作用
如果为了允许特定执行顺序，又将失去诸多函数式数学推理的诸多好处

幸运的是，结果并没那么坏，数学家为此开发除了许多技巧来保证在一定函数式设置下代码能特定顺序执行。
这样就赢得了两个世界，既可以利用无副作用函数式编程的好处，同样可以和外部环境打交道。
这些技术包括continuation, monad uniqueness typing .

理解CPS

函数式编程与Continuation/CPS
探索c#之递归APS和CPS
CPS是一种书写方式

我们对函数的了解是：函数只能将结果返回到他的调用端, 实际上函数不必返回到其调用端
而是可以返回到程序的任何地方。只要我们把CPS作为参数传给一个函数，那么他就决定了这个
函数返回的位置。
举例：

static int Times3(int x) {
    return x * 3;
}
Console.WriteLine(Times3(5));

CPS实现, Times3 不再显示的返回了，它的结果被传递给了一个叫k的函数，返回类型由这个函数决定

static void Times3(int x, action<int> k) {
    k(x * 3)
}
Times3(5,(n) => Console.WriteLine(n))

k 是一个匿名函数(n) => Console.WriteLine(n)

例2，假如有3个函数Main, F, G, Main函数调用F, F调用G

Console.WriteLine(F(1) + 1);
static int F(int n) {
    return G(n + 1) + 1;
}
static int G(int n) {
    return n + 1;
}

转换成CPS风格

F(1, (x)=> Console.WriteLine(x + 1))
static void F(int n, action<int> k){
    G(n + 1, (x) => k(x + 1))  //G(n+1) + 1 G外面的1 要在传参的时候+ , 否则没法实现
}
static void G(int n, action<int> k){
    k(n + 1)
}

例3， CPS尾递归

static int Factorial(int n){
    if(n==0)
        return 1;
    else 
        return n * Factorial(n-1) ;
}

CPS风格

C# 实现

static int Factorial(int n, action<int> k){
  if(n==0)
    k(1)
  else 
    Factorial(n - 1, x => k(x*n))
}

Factorial(10, (x) => x )

python 实现

def Factorial(n, func):
    if(n==0): 
        func(1) 
    else :
        Factorial(n - 1, lambda x:func(n*x))

a = Factorial(0, lambda x:x)

python的实现这种写法执行的时候会返回None，好像CPS并没有发生，原因是什么？可能跟python的实现有关

scala 实现

object testMain extends App{
  def Factorial(n: Int, f: Int => Int): Int = {
    if(n==0) f(1)
    else Factorial(n-1, x => f(x * n)) 
  }
  val a = Factorial(5, x => x)
  println(a)
}

Factorial函数本身不会返回，它把返回的事交给top定义的 x => x 匿名函数来返回
对于这种尾递归的函数，天然的不需要保存栈，因为中间结果就是下一次调用的入口参数
放到汇编指令上看，直接将PC指针跳转，参数根本就不需要传递，因为上一次跟下一次
用的现场是一样的，所以也不存在入栈出栈保存恢复现场的问题。就像把参数连续的传递一样，
也就是CPS(continuation passing style)的出处。
所以我们不用考虑压栈的问题,天然的就被编译成了循环迭代执行的样子，不需要空间上的开销

什么是尾递归

尾递归的外在表现，返回值是他本身例如，Factotrial(n-1, balabala.. )
Factorial(n-1, balabal..) * n或Iterfunc(n-1,balabala..) + somthing就不是尾递归，有些值必须得缓存
而尾递归不许要考虑压栈，仅仅是携带一个新的确定的参数继续执行罢了

为什么要CPS

我认为CPS变换最大的用途就在于它可以把任意的递归函数改写成尾递归
本身递归的应用非常广泛，尤其是程序解析，树的解析都会用到递归
为了避免递归爆栈的问题，CPS变换以continuation链的形式，避免栈空间的开辟
下一次递归传递的仅仅是参数而已 (尾递归只能降低空间开销，但并不能降低时间开销)
使得递归以尾递归的方式真正的被得以应用

基于CPS变换的尾递归转换算法

另外CPS最常见的用法就是回调函数，回调是显示传递的延续，回调是在函数结束时才调用
UI框架使用CPS来保持UI的响应，同时允许非线性程序交互，等上一个动画结束再执行下一给，形成链式效果
Web服务器使用CPS允许页面之间异步响应

模式匹配跟函数式编程的连系

函数式语言中的模式匹配是什么stackoverflow
模式匹配是编译器帮你处理了匹配判断分支的杂活。
模式匹配的写法：

f(0, 0) = NaN;
f(x, 0) | x > 0 = Infinity;
        | else  = -Infinity;
f(x, y) = (double)x / y;

一般的写法，或者编译器最后编译等价的代码：

double f(int x, int y) {
  if (y == 0) {
    if (x == 0)
      return NaN;
    else if (x > 0)
      return Infinity;
    else
      return -Infinity;
  } else
     return (double)x / y;
}