第十一章函数式编程

函数式编程（Functional Programming，FP）是一种全新的编程范式。编程范式分为截然不同的两大类，一类是第三章开头提到的“命令式编程”，另一类就是函数式编程所归属的“声明式编程”（Declarative programming）。

函数式编程的出发点是一切皆函数。它源自美国数学家阿隆佐·邱奇（Alonzo Church）提出的 λ-演算体系：在这个体系中，生成元就是函数，从函数的复合、绑定、替换等一系列规则推导出一个和图灵机等价的计算模型。LISP 系的编程语言大多实现了纯粹的 λ-演算，其中某些语言还广泛地应用于工业生产。

函数式编程的“函数”一词更倾向于数学上的函数而非计算机上的函数。在数学上，函数是从自变量到因变量的映射关系，而函数式编程就是通过定义这些映射关系编写出最终的程序。

值计算与副作用

作为例子，对于下面的 C++ 函数 f：

int a{1};

int f(int x) {
    a *= 2;
    return x + 1;
}

从计算机角度的函数出发，f 这个“子程序”执行了两件事：

为全局变量 a 赋值；
计算 x + 1 的值，然后作为 f(x) 表达式的值。

其中，第 2 件事——也就是计算函数调用表达式的值——反映了函数 f 作为映射关系的意义。而第 1 件事则与映射意义没有任何联系，只是单纯地让执行了这条语句而已。以此，可以将函数调用时的各种行为分成两大类：值计算（Value computation）与副作用（Side effect）。

“值计算”是指直接影响了函数调用表达式的最终结果的行为，即对函数返回值的求值过程。“副作用”则是与函数调用表达式结果无关的各种行为，包括但不限于修改变量、进行输入输出、调用包含副作用的函数等等。

正如之前所说，函数式编程的重点在于映射关系，所以函数式编程会尽可能地使用值计算，尽可能地避免副作用。所有副作用中，输入输出是很难避免的；但可以做到限制变量修改。这就是函数式编程最大的特点：无状态性，或者说不可变性。

举第三章提到过的一个例子：计算一个正整数的阶乘。那么，有两种写法：

int fact(int n) {
    int res{1};
    for (int i{2}; i <= n; i++) {
        res *= i;
    }
    return res;
}

int fact(int n) {
    return n == 1 ? 1 : n * fact(n - 1);
}

第一种写法中使用了一个循环，变量 i 和变量 res 在每一次循环后的值都不断发生变化。最终的 return 语句反而没有进行太多额外的计算。所以可以说，第一种写法的副作用很多但值计算很少。而第二种写法中，没有变量发生改变（甚至没有变量），整个函数只进行了一次值计算（就是 return 语句中的条件表达式）。所以，第二种写法是纯值计算而不带副作用的。

这里，不必担心第二种写法的递归开销较大：编译器会将这种形式的递归优化为循环指令。这种优化称为尾递归优化。

函数式编程大多使用第二种风格的写法。在许多函数式编程语言中：

不存在语句（因为语句是为了引入副作用的，而值计算只需 return 语句中的表达式即可）；
不存在分支语句（使用条件表达式）、更不存在循环语句（使用递归调用）；
除形参外，不存在局部变量（可被修改的局部变量不是无状态的，只读的局部变量可以形参替换）；
……

回到 C++ 的语境，这些性质都很难做到。不过不用担心，我们先从最基础的语法部分讲起——这一部分并不会涉及太多的函数式思想。

# 第十一章 函数式编程

# 值计算与副作用

第十一章函数式编程

值计算与副作用