| Authors: | Kenneth Lee |
|---|---|
| Version: | 1.1 |
| Date: | 2024-01-16 |
| Status: | Released |
有一种说法：要通过学习另一种语言来理解你自己的语言。所以这一章，我们介绍一下和 C/C++很不一样的编程逻辑，以便让本书读者更明白到底C/C++的独特之处是什么。
本文用OCaml语法作为例子，但我这里不是要介绍OCaml这种语言，我会解释例子中的具体 语法，以便你可以和C/C++作对比，从而发现C/C++这种所谓“命令式编程”的特点是什么。
如果你去找函数式编程的介绍，你会发现一般的解释是这样的：函数式编程是一种把函数 作为First-Class Citizen的编程方法。
如果你不知道函数式编程是什么，这个解释等于没有解释。我们还是直接看它的语法特征， 比如下面这是一组“名称”的定义：:
let f a b = a + b let g a = f a 3 let h = g 4
我解释一下：这里let是关键字，表示定义一个“名字”，这个名字有两个参数，a和b，f的 语义是：a+b。这我们一般可以理解为，f是一个函数。对不对？
那么g又是什么呢？g是“算了一半的函数”，我们给f输入了一个参数3，但我们没有算完， 在存储上，我们可以认为g记住了一个函数，一个算了一半的位置，以及算了一半的一些 状态（比如这里这个3）。在函数编程里面把这个东西叫一个“闭包”（Closure）。这是不 是很像C++里面的类？它有函数，也有变量。但它又不完全是类（毕竟类不会算了一半）。
最后就是h了，h其实是个常数，它就是7。我们把4输入到算了一半的g上面，根据f最初的 定义，我们就知道要算4+3，这个结果就是7啰。
所以，现在你明白了吧？在函数式编程中，常数和闭包是一个地位，都是函数。这个函数 不是我们在C/C++里面那个概念，而是数学上的概念：常数就相当数轴上的一个点，带一 个变量的闭包就是二维平面上的一条曲线，带两个变量就是三维空间上的一个立体空间。 给某个函数的变量确定的值，就只是缩维，缩到只剩下一个点，函数就变成变量。
这就是前面说函数是一等公民的概念，因为所有“名字”，都表示函数。定义名字和函数的 具体内容的关系，就称为一个binding（绑定）。bingding缩维的过程，称为“咖喱化” [1]。咖喱化的终点，就是一个点，最后变成常数。
| [1] | Currying，主流翻译为柯里化，“咖喱化”是我调侃的说法。为什么叫这个名字我 也不知道，反正这东西也没有什么好的名字可以叫，也许就是随便弄个名字。 |
我推荐你看这类语言，就是让你看到C/C++对冯诺依曼计算的定义有多大的关联。我们在 第一章专门介绍过冯诺依曼计算机：它是有一组存储，然后有一个纸带，算一次更新一次 存储，然后再算一次，再更新一次状态，我们在C/C++中写程序，是定义一组“变量”代表 存储，然后通过一条条指令改变这些“变量”的状态，从而靠循环来得到我们要的计算结果 的。
而函数式编程完全不是这个思路，它根本没有状态，你给进来一些参数，它拿这些参数做 计算，告诉你计算结果而已，没有改变状态一说。只有每个函数的咖喱化的过程。
所以它也没有循环这种概念[2]，想想循环是个什么概念：:
int sum(int n) {
int s = 0;
for (int i = 0; i < n; i++)
s += i;
return s;
}
| [2] | 实际上，作为OCaml本身，它是支持循环和状态变量的（称为mutable variable）。这说明其实纯粹的函数式编程有很多实际问题都解决不了。我们这里不 是讲怎么用OCaml，而是对比函数式编程，所以我们不深入讲那部分的内容。 |
这里我们先设置了两个状态，s=0, i=0。然后我们一步步更新i和s的状态，最后得到结果。 这就是一种典型的冯诺依曼计算机的思路：状态和对状态下命令。
那么在数学定义上，你会怎么定义这个东西？你的数学书会怎么定义这个东西呢？
数学书通常是用数学归纳法的，我们拿这段OCaml的代码给你解释：:
let rec sum n = match n with | 1 -> 1 | _ -> n + sum(n-1)
这里let sum n = xx作了一点点扩展，sum前面加了一个rec（recursive），表示这是个 递归定义。递归的方法是这样的：
- 如果n是1，那么结果就是1。
- 如果n是x，那么结果就是x+sum(x-1)。（定义中我们直接用n表示x了，反正其实就是 一样的）
这才是数学的定义，对不对？这个定义中，没有任何“变量”在被一步步更新，也没有先做 什么再做什么的概念。这定义的是你原始的数学要求，而不是你的计算机怎么用。
所以这种语言特别不适合写直接给计算下命令的程序（比如写操作系统），它更适合就用 来做算法，用来做数学计算，它的定义就特别严密，因为它本来就是数学的语言。
所以，我们一般的调试手段也通常不能用来调试这种程序。你想想，所谓调试，其实你不 就是先走一个步骤，然后看看变量变成多少，然后再走一个步骤吗？这玩意儿根本就没有 变量，也没有明确的针对这些变量的“一步”的概念。它的计算要求是“数据有了就算下一 步”，谁先谁后无所谓。
Note
实际每种具体的函数式编程语言还是有一些表示顺序的东西的，但那些不是函数式编 程的原始特征。）
当然它还是有计算步骤的概念，但那只是计算行为表达，不是冯诺依曼状态机的概念。两 者的区别在于，这些步骤只是说明了数据依赖关系，不在乎你是否提前计算，甚至你可以 让它在编译阶段就完成计算，而冯诺依曼的概念写下去的时候，就是希望它是最终执行的 时候运行的。函数式编程教材把这个冯诺依曼的形式叫做“命令式编程”（Imperative Programing）。
相应地，函数式编程的IO也很难处理，因为也没有这个概念。IO是一个时间概念，需要稳 定在某个状态才有IO的语义的，但它其实没有。IO不是一种计算，计算只有结果和计算间 依赖的概念，并没有“算到中间某一步系统的状态”的概念。你算出一个结果a，然后要求 输出到IO上，这个IO没有输出，影响计算结果吗？没有啊。这就是问题。
但递归会制造大量的临时闭包，这在实现在冯诺依曼计算机上的时候，有很高的存储成本。 所以函数式编程很注重把头递归转化为尾递归。所谓尾递归，就是递归的时候，递归的上 一级已经没有遗留的计算要做了。比如上面这个循环，算sum(n-1)的时候，sum(n)这一级 的堆栈还不能释放，因为还需要等着计算n+sum(n-1)呢，如果这个最后一步只有sum，没 有其他计算，这就不需要留着sum(n)的堆栈了，这就叫尾递归。头递归总是可以变成尾递 归的：把剩下的计算塞到下一级计算就可以了。比如上面的循环，这样做就可以了：:
let sum n =
let rec tail_sum n m = match n with
1 -> 1+m
| _ -> tail_sum n-1 n+m
in tail_sum n 0
这个语法这样理解：首先sum n被定义成in后面的语句：tail_sum n 0。后面这个0是我加 进去用做传递统计结果的参数的。单看这一段，含义就是：
sum n定义为n到1的连加，先定义为tail_sum n 0，第一个参数是n的连加，第二个参数 是把连加的结果再加一个0。
这个地方是自洽的，也没有递归。所以let sum前面现在没有递归的声明了。
现在就是这个tail_sum n m怎么定义了。这个定义在let sum和in的中间，表示仅仅在这 个上下文中有效。它的定义是：
- 如果n是1，那么结果就是1+m。
- 如果n是n，结果是tail_sum n-1 n+m。
这个数学归纳法定义也合理吧？n-1这一层得到了之前的统计结果，算出n-1的连加以后加 到m上，就符合tail_sum的计算了。而n这一层，调用tail_sum(n-1, n+m)是它调用的最后 一个函数了，调用的时候，它自己的堆栈就不需要保留了。
理解一下这样的编程思路，也许能让C/C++的学习者真正理解我们说冯诺依曼计算机的时 候，到底在说什么。