编程范式

函数式编程是一种编程范式，我们常见的编程范式有命令式编程、函数式编程、逻辑式编程，常见的面向对象编程是一种命令式编程。

命令式编程

命令式编程是面向计算机硬件的抽象，有变量（对应存储单元），赋值语句（获取，存储指令），表达式（内存引用和算术运算）和控制语句（跳转指令），命令式程序就是一个冯诺依曼的指令序列。

函数式编程（FP）

函数式编程是面向数学的抽象，将计算描述为一种表达式求值，函数式程序就是一个表达式。

函数式编程中的函数这个术语不是指计算机中的函数，而是指数学中的函数，即自变量的映射。也就是说一个函数的值仅决定于函数参数的值，不依赖于其他状态。比如sqrt(x)函数计算x的平方根，只要x不变，不论什么时候调用，调用几次，值都是不变的。

由于函数式编程是面向数学的抽象，更接近人的语言。函数式编程更关注结果，相对的命令式编程关注解决问题的步骤。使用函数式编程，代码会比较简洁，也容易被理解。

函数式编程的本质

一等公民

函数式编程中，函数与其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。

高阶函数

函数式编程中高阶函数是至少满足下列一个条件的函数：

接受一个或多个函数作为输入
输出一个函数

高阶函数范例：
这是一个Python script的例子，其中函式g()有一引数以及回传一函数.这个例子会打印100 ( g(f,7)= (7+3)×(7+3) ).

def f(x):
    return x + 3

def g(function, x):
    return function(x) * function(x)

print g(f, 7)

范例代码来自于：维基百科

不修改状态

不变性是函数式编程的基石，面向对象的编程通过封装可变动的部分来构造能够让人读懂的代码，函数式编程则是通过最大程度地减少可变动的部分来构造出可让人读懂的代码。

函数式编程语言中的变量不是命令式编程语言中的变量，即存储状态的单元，而是代数中的变量，即一个值的名称。变量的值是不可变的，意味着状态不能保存在变量中。函数式编程使用参数保存状态，最好的例子就是递归。
由于命令式编程语言也可以通过类似于函数指针的方式来实现高阶函数，函数式编程的优势主要是不可变性带来的。没有可变状态，函数就是引用透明、没有副作用的，也是线程安全的。

引用透明

引用透明，指的是函数的运行不依赖于外部变量或“状态”，只依赖于输入的参数，即如果提供同样的输入，那么函数总是返回同样的结果。

无“副作用”

副作用，指的是函数内部与外部互动，产生预算以外的其他结果。（最典型的情况是修改全局变量的值）。
函数式编程强调无“副作用”，意味着函数要保持独立，所有功能就是计算返回一个新的值，没有其他行为，即，纯函数。

更易调试

函数不依赖外部状态也不修改外部状态，函数调用的结果不依赖调用的时间和位置，这样写的代码更容易进行推理，不容易出错。这使得单元测试和调试都更容易。

易于并发编程

不可变性带来的另一个好处是：函数式编程不需要考虑”死锁”（deadlock），因为它不修改变量，所以根本不存在”锁”线程的问题。不必担心一个线程的数据，被另一个线程修改，所以可以很放心地把工作分摊到多个线程，部署”并发编程”（concurrency）。
除此之外，就算某个函数式程序本身只是单线程的，编译器也可以将其优化成可以在多CPU上运行的并发程序。以下面程序为例：

1
2
3

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

由于s1和s2互不干扰，不会修改变量，谁先执行是无所谓的，所以可以放心地增加线程，把它们分配在两个线程上完成。其他类型的语言就做不到这一点，因为s1可能会修改系统状态，而s2可能会用到这些状态，所以必须保证s2在s1之后运行，自然也就不能部署到其他线程上了。

多核CPU是将来的潮流，所以函数式编程的这个特性非常重要。

只用“表达式”，不用“语句”

严格意义上的函数式编程意味着不适用可变的变量，赋值，循环和其他命令式控制结构进行编程。

“表达式”是一个单纯的运算过程，总是有返回值；“语句”是执行某种操作，没有返回值。函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。

函数式编程的如条件语句、循环语句也不是命令式编程语言中的控制语句，而是函数的语法糖，比如在Scala语言中，if else不是语句而是三元运算符，是有返回值的。

惰性求值

惰性求值（尽可能延迟表达式求值），表达式不会在它被绑定到变量之后就立即求值，而是在该值被取用的时候求值。

由于函数是引用透明的以及函数式编程不像命令式编程那样关注执行步骤，这就为系统提供了优化函数式程序的空间，如惰性求值。惰性求值使得代码具备了巨大的优化潜能。支持惰性求值的编译器会像数学家看待代数表达式那样看待函数式程序：抵消相同项从而避免执行无谓的代码，安排代码执行顺序从而实现更高的执行效率甚至减少错误。

惰性求值有如下有点：

首先，你可以用它们来创建无限序列这样一种数据类型。因为直到需要时才会计算值，这样就可以使用惰性集合模拟无限序列。例如存储一个Fibonacci数列数字的列表。
第二，减少了存储空间。因为在真正需要时才会发生计算。所以，节约了不必要的存储空间。
第三，减少计算量，产生更高效的代码。因为在真正需要时才会发生计算。例如，寻找数组中第一个符合某个条件的值。

Continuation Passing Style (CPS)

惰性求值的不足

惰性求值当然也有其缺点。其中最大的一个就是，嗯，惰性。现实生活中很多问题还是需要严格求值、严格的执行顺序的。比如下面例子：

1 2	System.out.println("Please enter your name"); System.in.readLine();

由于这两行代码并不存在依赖关系，在惰性语言中没人能保证第一行会在第二行之前执行！这也就意味着我们不能处理IO，不能调用系统函数做任何事情，也就是说不能和外界交互了！
函数式编程中我们可以通过Continuation Passing Style 来保证代码按一定的顺序执行。

CPS

CPS把函数调用完之后接下来要执行的代码通过闭包包裹并作为函数参数调用要执行的函数。方便理解我们先看一个例子

举个栗子

1 2	int i = add(5, 10); int j = square(i);

add这个函数将返回15然后这个值会赋给i，这也是add被调用的地方。接下来i的值又会被用于调用square。请注意支持惰性求值的编译器不能打乱这段代码的执行顺序，因为第二个函数的执行依赖于第一个函数的执行结果。这段代码可以用CPS技术重写，这样一来add的返回值就不是传递给其调用者，而是直接传到square里去了。

1	int j = add(5, 10, square);

在上例中，add多了一个参数：一个函数，add必须在完成自己的计算后，调用这个函数并把结果传给它。

同样我们以CPS技术重写上述IO代码，编译器就必须顺序执行了，因为重写后的代码建立了依赖关系：

1	System.out.println("Please enter your name: ", System.in.readLine);

CPS & 传统函数调用

传统函数调用

传统函数调用的程序需要额外的函数调用栈才能运行。

栈里面存放的是参数还有一个供函数运行结束后返回的程序指针，以支持函数返回后程序的继续运行。

CPS风格函数调用

用CPS风格写出来的程序不需要栈，但是每次调用函数的时候都会要多加一个参数。

在这里完全没有函数需要做传统意义上的“返回”操作，函数执行完后仅需要接着调用另外一个函数就可以了。也完全不需要保留原来的参数：因为这种程序里的函数都不返回，所以它们不会被用第二次！

在CPS风格下的函数式编程，函数就是一个管道（pipe）。这头进去一个值另一头出来一个新的值并进入下一个管道，没有其他作用。

ReactiveCocoa------函数式编程初探