函数式编程介绍

梦里梦外; 2022-06-01 03:51 159阅读 0赞

# 历史来源 #

**讲述历史来源，不喜欢的可以跳过。但是我个人认为这对理解有帮助。**

在计算机的世界中，有两位巨擘对问题的**可计算性**做了模型化描述\[4\]。

一位是阿兰.图灵（Alan Turing），他提出的图灵机。计算机系的各种学科中都充斥着这个概念，假设有一个纸带和一个打孔机，然后有一套指令，能够控制打孔机在纸带上移动、能够读取当前位置是否打了孔、能够在当前位置打一个孔，这就是一个图灵机，假设一个问题能够靠这个纸带+打孔机+指令的方式解决，那就说明这个问题是“可计算的”。

另外一个位巨擘，是阿隆佐·邱奇（Alonzo Church）。邱奇是个数学家，他提出了Lambda演算(Lambda Calculus)的概念，用函数组合的方式来描述计算过程，换句话来说，如果一个问题能够用一套函数组合的算法来表达，那就说明这个问题是可计算的。

我个人对这两种计算过程的模型是这样理解的，**不一定对**：

1.  图灵机是通过一系列指令和状态来完成某种过程的，即，在某种状态下使用怎样的指令转移到某种状态。
2.  Lambda演算是通过一个函数来解决这个问题，而这个函数又是由一系列别的函数组成，这样递归下去，最终达到常量。有些类似动态规划那种一个问题由多个子问题组成，子问题又有自己的子问题，最后到达一些已知解的问题。
3.  不是全部的Lambda演算思想都可以运用到实际中，因Lambda演算在设计的时候就不是为了在各种现实世界中的限制下工作的。

# 编程范式 #

编程语言主要有三种类型\[3\]：

1.  命令式编程（Imperative Programming）: 专注于”如何去做”，这样不管”做什么”，都会按照你的命令去做。解决某一问题的具体算法实现。
2.  函数式编程（Functional Programming）：把运算过程尽量写成一系列嵌套的函数调用。
3.  逻辑式编程（Logical Programming）：它设定答案须符合的规则来解决问题，而非设定步骤来解决问题。过程是事实+规则=结果。

> 关于这个问题也有一些争议，有人把函数式归结为声明式的子集，还有一些别的七七八八的东西，这里就不做阐述了。  
> 声明式编程：专注于”做什么”而不是”如何去做”。在更高层面写代码，更关心的是目标，而不是底层算法实现的过程。  
> 如， css, 正则表达式，sql 语句，html，xml…  
>

在这儿来对比一下命令式和函数式的一些区别。

## 命令式编程 ##

命令式编程是通过[赋值][Link 1]（由表达式和变量组成，assignment，我觉得翻译成**任务**有点奇怪，也不懂翻译成赋值行不行）以及控制结构（如，条件分支、循环语句等）来修改可修改的变量。

它的运作方式具有图灵机特性，且和[冯诺依曼体系][Link 2]的对应关系非常密切。甚至可以说，命令式程序就是一个冯诺依曼机的指令序列：

1.  变量 → 内存
2.  变量引用 → 输入设备
3.  变量赋值 → 输出设备
4.  控制结构 → 跳转操作

我们知道的，冯诺依曼结构需要用总线来传输数据，我们只能一个字节一个字节处理。

这也就形成了运行的瓶颈。程序执行的效率取决于执行命令的数量，因此才会出现大O表示法等等表示时间空间复杂度的符号。

## 函数式编程 ##

相比于命令式编程关心解决问题的步骤，函数式编程是面向数学的抽象，关心数据（代数结构）之间的映射关系。函数式编程将计算描述为一种表达式求值。

在狭义上，函数式编程意味着没有可变变量，赋值，循环和其他的命令式控制结构。即，纯函数式编程语言。

*  Pure Lisp, XSLT, XPath, XQuery, FP
 *  Haskell (without I/O Monad or UnsafPerformIO)

在广义上，函数式编程意味着专注于函数

*  Lisp, Scheme, Racket, Clojure
 *  SML, Ocaml, F\#
 *  Haskell (full language)
 *  Scala
 *  Smalltalk, Ruby

### 函数 ###

函数式编程中的函数，这个术语不是指命令式编程中的函数（我们可以认为C++程序中的函数本质是一段子程序Subroutine），而是指数学中的函数，即自变量的映射（一种东西和另一种东西之间的对应关系）。也就是说，一个函数的值仅决定于函数参数的值，不依赖其他状态。

在函数式语言中，函数被称为[一等函数][Link 3]（First-class function），与其他数据类型一样，作为一等公民，处于平等地位，可以在任何地方定义，在函数内或函数外；可以赋值给其他变量；可以作为参数，传入另一个函数，或者作为别的函数的返回值。

#### 纯函数 ####

[纯函数][Link 4]是这样一种函数，即相同的输入，永远会得到相同的输出，而且没有任何可观察的副作用。

*  不依赖外部状态
 *  不改变外部状态

比如Javascript里`slice`和`splice`，这两个函数的作用相似\[5\]。  
`slice`符合纯函数的定义是因为对相同的输入它保证能返回相同的输出。  
`splice`却会嚼烂调用它的那个数组，然后再吐出来；这就会产生可观察到的副作用，即这个数组永久地改变了。

var xs = [1,2,3,4,5];
    
    // 纯的
    xs.slice(0,3);
    //=> [1,2,3]
    xs.slice(0,3);
    //=> [1,2,3]
    xs.slice(0,3);
    //=> [1,2,3]
    
    
    // 不纯的
    xs.splice(0,3);
    //=> [1,2,3]
    xs.splice(0,3);
    //=> [4,5]
    xs.splice(0,3);
    //=> []

在函数式编程中，我们讨厌这种会改变数据的笨函数。我们追求的是那种可靠的，每次都能返回同样结果的函数，而不是像`splice`这样每次调用后都把数据弄得一团糟的函数，这不是我们想要的。

来看看另一个例子。

// 不纯的
    var minimum = 21;
    
    var checkAge = function(age) { 
      return age >= minimum;
    };
    
    
    // 纯的
    var checkAge = function(age) { 
      var minimum = 21;
      return age >= minimum;
    };

在不纯的版本中，`checkAge`的结果将取决于`minimum`这个可变变量的值。换句话说，它取决于系统状态（system state）。

除了输入值之外的因素能够左右`checkAge`的返回值，不仅让它变得不纯，而且会增加程序的认知难度（cognitive load），使我们理解整个程序的时候都非常痛苦。甚至，这种依赖状态会影响系统的复杂度（[http://www.curtclifton.net/storage/papers/MoseleyMarks06a.pdf][http_www.curtclifton.net_storage_papers_MoseleyMarks06a.pdf]）。

#### 函数与方法 ####

当然在现在很多（非纯）函数式编程语言中也有方法和函数的区别。比如scala\[1\]：

scala> def m(x:Int) = 2*x   //定义一个方法
    m: (x: Int)Int
    
    scala> m    //方法不能作为最终表达式出现
    <console>:9: error: missing arguments for method m;
    follow this method with '_' if you want to treat it as a partially applied function
                  m
                  ^    
    
    scala> val f = (x:Int) => 2*x   //定义一个函数
    f: Int => Int = <function1>
    
    scala> f    //函数可以作为最终表达式出现
    res9: Int => Int = <function1>

方法就是命令式编程中的函数，而函数则是函数式编程中的函数。

### 变量与表达式 ###

纯函数式编程语言中的变量也不是命令式编程语言中的变量（存储状态的内存单元），而是数学代数中的变量，即一个值的名称。

变量的值是不可变的（immutable），也就是说不允许像命令式编程语言中那样能够多次给一个变量赋值。比如说在命令式编程语言我们写`x = x + 1`。

函数式语言中的条件语句，循环语句等也不是命令式编程语言中的控制语句，而是一种表达式。

*  “表达式”（expression）是一个单纯的运算过程，总是有返回值；
 *  “语句”（statement）是执行某种操作(更多的是逻辑语句。)，没有返回值。

函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。比如在Scala语言中，if else不是语句而是三元运算符，是有返回值的。

严格意义上的函数式编程意味着不使用可变的变量，赋值，循环和其他命令式控制结构进行编程。 当然，很多所谓的函数式编程语言并没有严格遵循这一类的准则，只有某些纯函数式编程语言，如Haskell等才是完完全全地依照这种准则设计的。

### 状态 ###

首先要意识到，我们的程序是拥有“状态”的。 想一想我们调试C++程序的时候，经常会在某处设置一个断点。程序执行断点就暂停了，也就是说程序停留在了某一个状态上。

![Image 1][]

**这个状态包括了当前定义的全部变量，以及一些当前系统的状态，比如打开的文件、网络的连接、申请的内存等等。**具体保存的信息和语言有关系。

比如使用过Matlab、R之类的科学计算语言的朋友会知道，在退出程序的时候它会让你选择是否要保存当前的session，如果保存了，下次打开时候它会从这个session开始继续执行，而不是清空一切重来。你之前定义了一个变量`x = 1`，现在这个`x`还在那里，值也没变。

这个状态就是图灵机的纸带。有了状态，我们的程序才能不断往前推进，一步步向目标靠拢的。

函数式编程不一样。函数式编程强调无状态，不是不保存状态，而是强调将状态锁定在函数的内部，不依赖于外部的任何状态。更准确一点，它是通过函数创建新的参数或返回值来保存程序的状态的。

**状态完全存在栈上。**

函数一层层的叠加起来，其中每个函数的参数（是参数，不是变量）或返回结果来代表了程序的一个中间状态。如果你需要保存一个状态一段时间并且时不时的修改它，那么你可以编写一个递归函数。

举个例子，试着写一个计算斐波那契数的函数：

// C++
    int fab(int n) {
      return n == 1 || n == 2 ? 1 : fab(n - 1) + fab(n - 2);
    }

-- Haskell
    fab :: (Num a) => a -> a
    fab n = if n == 1 || n == 2 then 1 else fab(n - 1) + fab(n - 2)

对于C++而言，调用fab(5)的过程是：

fab(5) → fab(4) → fab(3) → fab(2)  
　　　　　　　　　　      → fab(1)  
　　　　　        → fab(2)  
          → fab(3) → fab(2)  
　　　　　        → fab(1)

我们看到，fab(3)被求值了两遍。为了计算fab(5)，我们实际执行了8次函数调用。

对于Haskell而言，如果没有使用尾递归，那么情况和C++的调用方式相同。如果使用了[尾递归优化][Link 5]，调用fab(5)的过程是：

fab(5) → fab(4) → fab(3) → fab(2)  
　　　　　　　　　　      → fab(1)  
　　　　　        → fab(2)  
          → fab(3)

总共只有6次应用。注意我说的是应用而不是调用。因为函数式语言里的函数本意并不是命令式语言里面的“调用”或者“执行子程序”的语义，而是“函数与函数之间的关系”的意思。比如fab函数中出现的两次fab的应用，实际上说明要计算fab函数，必须先计算后续的两个fab函数。这并不存在调用的过程。因为所有的计算都是静态的。Haskell可以认为所有的fab都是已知的。因此实际上所有遇到的fab函数，Haskell只是实际地计算一次，然后就缓存了结果。

# 函数式编程的特性 #

*  高阶函数（Higher-order function）
 *  偏应用函数（Partially Applied Functions）
 *  柯里化（Currying）
 *  闭包（Closure）

## 高阶函数 ##

[高阶函数][Link 6]就是参数为函数或返回值为函数的函数。

有了高阶函数，就可以将复用的粒度降低到函数级别。相对于面向对象语言，高阶函数的复用粒度更低。

举例来说，假设有如下的三个函数，

def sumInts(a: Int, b: Int): Int =
      if (a > b) 0 else a + sumInts(a + 1, b)
    
    def sumCubes(a: Int, b: Int): Int =
      if (a > b) 0 else cube(a) + sumCubes(a + 1, b)
    
    def sumFactorials(a: Int, b: Int): Int =
      if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)

分别是求a到b之间整数之和，求a到b之间整数的立方和，求a到b之间整数的阶乘和。

其实这三个函数都是以下公式的特殊情况

∑n=abf(n)

三个函数不同的只是其中的f不同，那么是否可以抽象出一个共同的模式呢？

我们可以定义一个高阶函数sum：

def sum(f: Int => Int, a: Int, b: Int): Int =
      if (a > b) 0
      else f(a) + sum(f, a + 1, b)

其中参数f是一个函数，在函数中调用f函数进行计算，并进行求和。

然后就可以写如下的函数

def sumInts(a: Int, b: Int) = sum(id, a, b)
    def sumCubs(a: Int, b: Int) = sum(cube, a, b)
    def sumFactorials(a: Int, b: Int) = sum(fact, a, b)
    
    def id(x: Int): Int = x
    def cube(x: Int): Int = x * x * x
    def fact(x: Int): Int = if (x == 0) 1 else fact(x - 1)

这样就可以重用sum函数来实现三个函数中的求和逻辑\[8\]。

高阶函数提供了一种函数级别上的依赖注入（或反转控制）机制，在上面的例子里，sum函数的逻辑依赖于注入进来的函数的逻辑。很多GoF设计模式都可以用高阶函数来实现，如Visitor，Strategy，Decorator等。比如Visitor模式就可以用集合类的map()或foreach()高阶函数来替代。

函数式语言通常提供非常强大的集合类（Collection），提供很多高阶函数，因此使用非常方便。

比如说，我们想对一个列表中的每个整数乘2，在命令式编程中需要通过循环，然后对每一个元素乘2，但是在函数式编程中，我们不需要使用循环，只需要使用如下代码：

scala> val numbers = List(1, 2, 3, 4)
    numbers: List[Int] = List(1, 2, 3, 4)
    
    scala> numbers.map(x=>x*2)
    res3: List[Int] = List(2, 4, 6, 8)

其中x=>x\*2是一个匿名函数，接收一个参数x，输出x\*2。这里也可以看出来函数式编程关注做什么（x\*2），而不关注怎么做（使用循环控制结构）。程序员完全不关心，列表中的元素是从前到后依次计算的，还是从后到前依次计算的，是顺序计算的，还是并行进行的计算，如Scala的并行集合（Parallel collection）。

使用集合类的方法，可以使对一些处理更简单，例如上面提到的求阶乘的函数，如果使用集合类，就可以写成：

def fact(n: Int): Int = (1 to n).reduceLeft((acc,k)=>acc*k)

其中(1 to n)生成一个整数序列，而reduceLeft()高阶函数通过调用匿名函数将序列化简。

那么，在大数据处理框架Spark中，一个RDD就是一个集合。以词频统计的为例代码如下：

val file = spark.textFile("hdfs://...")
    val counts = file.flatMap(line => line.split(" "))
                     .map(word => (word, 1))
                     .reduceByKey(_ + _)
    counts.saveAsTextFile("hdfs://...")

示例里的flatMap()，map()，和集合类中的同名方法是一致的，这里的map方法的参数也是一个匿名函数，将单词变成一个元组。写这个函数的人不用关心函数是怎么调度的，而实际上，Spark框架会在多台计算机组成的分布式集群上完成这个计算。

## 闭包 ##

[闭包][Link 7]的基础是一等函数（First-class function）。

闭包在形式上就是一个函数内部定义另一个函数，函数的堆栈在在函数返回后并不释放，我们也可以理解为这些函数堆栈并不在栈上分配而是在堆上分配\[9\]。

### 访问权限控制 ###

面向对象语言如Java、C++都会有private、public关键字，不允许从类外部直接访问特定成员变量，需要通过成员函数来访问，这是一个很普遍、很合理的需求。

先复习一下JS的变量作用域。  
函数内部可以访问全局变量：

var n=1;
    function print(){ 
         console.log(n);
    };
    print(); // 1

但是从函数外部不能访问函数内部变量：

function fun() { 
         var a = 0; 
    };
    console.log(a); // error

于是闭包派上用场了：

function outer() { 
         var n = 2;
         function inner() { 
           return n; 
         };
         return inner();
    }
    var result = outer();
    console.log(result); // 2

### 延长变量生命周期 ###

在面向对象语言里，函数内的变量都是在栈上分配的，函数调用完成后，栈销毁，变量的生命周期结束。而对象是在堆分配的，会常驻内存，除非被手动或自动回收掉。

闭包再次救场：

function createCounter() { 
         var counter = 0;
         function increment() { 
           counter = counter + 1;
           console.log("Number of events: " + counter);
         }
         return increment;
    }
    var incr = createCounter();
    incr(); // 1
    incr(); // 2
    incr(); // 3

# 函数式编程的好处 #

由于命令式编程语言也可以通过类似函数指针的方式来实现高阶函数，函数式的最主要的好处主要是不变性带来的。

## 引用透明（Referential transparency） ##

引用透明（Referential transparency），指的是函数的运行不依赖于外部变量或”状态”，只依赖于输入的参数，任何时候只要参数相同，引用函数所得到的返回值总是相同的。

其他类型的语言，函数的返回值往往与系统状态有关，不同的状态之下，返回值是不一样的。这就叫”引用不透明”，很不利于观察和理解程序的行为。

没有可变的状态，函数就是引用透明（Referential transparency）

## 没有副作用（No Side Effect）。 ##

副作用（side effect），指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。

函数式编程强调没有”副作用”，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。

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

还有一个好处是，由于函数式语言是面向数学的抽象，更接近人的语言，而不是机器语言，代码会比较简洁，也更容易被理解。

## 优化处理 ##

由以上两点，由衍生出了更多的特性。

### 无锁并发 ###

没有副作用使得函数式编程各个独立的部分的执行顺序可以随意打乱，（多个线程之间）不共享状态，不会造成资源争用(Race condition)，也就不需要用锁来保护可变状态，也就不会出现死锁，这样可以更好地进行无锁（lock-free）的并发操作。

尤其是在对称多处理器（SMP）架构下能够更好地利用多个处理器（核）提供的并行处理能力。

### 惰性求值 ###

惰性求值\[7\]（lazy evaluation，也称作call-by-need）是这样一种技术：是在将表达式赋值给变量（或称作绑定）时并不计算表达式的值，而在变量第一次被使用时才进行计算。

这样就可以通过避免不必要的求值提升性能。

在Scala里，通过lazy val来指定一个变量是惰性求值的，如下面的示例所示：

scala> val x = { println("x"); 15 }
    x
    x: Int = 15
    
    scala> lazy val y = { println("y"); 13 }
    y: Int = <lazy>
    
    scala> y
    y
    res3: Int = 13
    
    scala> y
    res4: Int = 13

可以看到，在Scala的解释器中，当定义了x变量时就打印出了“x”，而定义变量y时并没有打印出”y“，而是在第一次引用变量y时才打印出来。

## 参考资料 ##

1.  [scala中方法和函数的区别][scala]
2.  [什么是函数式编程思维？][Link 8]
3.  [编程语言的主要类型，声明式编程，命令式编程和函数式编程的区别][Link 9]
4.  [React世界的函数式编程][React]
5.  [纯函数的好处][Link 10]
6.  [函数式编程（Functional Programming）简介][Functional Programming]
7.  [惰性编程和惰性求值][Link 11]
8.  [Higher-Order Functions][]
9.  [闭包其实很简单][Link 12]

[Link 1]: https://en.wikipedia.org/wiki/Assignment_%28computer_science%29
[Link 2]: https://zh.wikipedia.org/wiki/%E5%86%AF%C2%B7%E8%AF%BA%E4%BC%8A%E6%9B%BC%E7%BB%93%E6%9E%84
[Link 3]: https://en.wikipedia.org/wiki/First-class_function
[Link 4]: https://zh.wikipedia.org/wiki/%E7%BA%AF%E5%87%BD%E6%95%B0
[http_www.curtclifton.net_storage_papers_MoseleyMarks06a.pdf]: http://www.curtclifton.net/storage/papers/MoseleyMarks06a.pdf
[Image 1]: 
[Link 5]: https://baike.baidu.com/item/%E5%B0%BE%E9%80%92%E5%BD%92/554682?fr=aladdin
[Link 6]: https://en.wikipedia.org/wiki/Higher-order_function
[Link 7]: https://en.wikipedia.org/wiki/Closure_%28computer_programming%29
[scala]: https://www.cnblogs.com/fangwencai/p/4859662.html
[Link 8]: https://hcyue.me/2016/05/14/%E4%BB%80%E4%B9%88%E6%98%AF%E5%87%BD%E6%95%B0%E5%BC%8F%E7%BC%96%E7%A8%8B%E6%80%9D%E7%BB%B4/
[Link 9]: http://blog.csdn.net/xuqinggangsls/article/details/53726170
[React]: https://zhuanlan.zhihu.com/p/26174525
[Link 10]: https://llh911001.gitbooks.io/mostly-adequate-guide-chinese/content/ch3.html#%E8%BF%BD%E6%B1%82%E2%80%9C%E7%BA%AF%E2%80%9D%E7%9A%84%E7%90%86%E7%94%B1
[Functional Programming]: http://janfan.cn/chinese/2015/05/18/functional-programming.html
[Link 11]: https://www.ibm.com/developerworks/cn/linux/l-lazyprog.html
[Higher-Order Functions]: https://d396qusza40orc.cloudfront.net/progfun/lecture_slides/week2-2.pdf
[Link 12]: https://www.jianshu.com/p/755597a60629