命令式编程与函数式编程

一直以来，对编程范式最直观的理解，可能就是用“命令式”和“函数式”来区分了。最近重新琢磨了一下，突然对这两者的本质区别有了更深的理解。

所谓命令式编程，本质上就是向机器下指令——一行行命令，让机器按部就班地执行。机器执行的效率，直接取决于它执行了多少条命令。正因如此，才诞生了大O表示法这类时间复杂度、空间复杂度的符号，目的就是衡量“命令数量”带来的影响。

而函数式语言，其实并不是表面上理解的“通过函数的变换来编程”。纯粹的函数式语言里，根本没有变量这种东西——你定义了一个东西，它就永远不变了。那问题来了：既然所有东西都不能变，我们还能怎么编程？

实际上，函数式编程的核心在于构建实体与实体之间的关系。从这个角度看，Lisp虽然不算纯粹的函数式语言，但也算得上是函数式编程的一员。按照这个定义，很多提供原生List支持的脚本语言，也多少混合了函数式特性。但话说回来，这不是精髓。知其然，还要知其所以然。既然我们已经有了精确自然的命令式编程，为什么还要费劲学函数式？

我们来看个小例子。

这是一段C语言写的斐波那契数列求第N项的程序：

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语言是标准的命令式编程语言，它对你写下的每一行语句都机械地执行。想提高效率，你得自己去分析程序，人工减少语句数量。具体到这个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次函数调用。

那函数式语言呢？前面说过，函数式语言里没有变量，所有东西都是不变的。所以在执行fab(5)的时候，过程是这样的：

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

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

本质上，这代表了我们提供给函数式语言的程序，其实不是一行一行的“命令”，而只是对数据变换的说明。这样，函数式语言就可以深入这些说明中，寻找冗余的共性，从而进行优化。这就是函数式语言不需要精心设计，就能比命令式语言高效的秘密。命令式语言当然也可以进行这种优化，但因为命令式语言有边界效应，而且大部分情况下都是利用边界效应进行计算，所以很难推广这种优化，只有少数窥孔优化能取得效果。

放到这个例子上，因为本质上两次的fab应用是重叠的，Haskell发现了这个特点，于是将两次fab的结果缓存下来（注意，能缓存结果的必要条件是这个函数返回的值不会变，而这是函数式语言的主要特性）。如果后续计算需要用到这两次的结果，就不需要重复计算，直接提取结果就行了。这就是上面两个几乎完全一样的程序，效率相差如此之大的主要原因。

函数式语言有优势，那有没有缺陷呢？当然有。函数式语言不如命令式语言那么纯粹，和机器一一对应，在某些情形下会导致更差的效率和更低的开发效率。不过，对计算模型不断深入的了解，会逐渐缩短这两者之间的差距。然而，必须警惕的是，命令式语言植根于冯·诺依曼体系，一旦新的体系发生了革命性改变，命令式语言就不再适用，只能通过模拟的方式执行。到那个时候，函数式语言和命令式语言的地位就会完全颠倒过来。当然，这目前还不是我们需要考虑的问题，但在现在稍微了解一点函数式编程的思想，是十分重要的。

日常生活中的函数式编程

- C++模板元编程
- C/C++预处理元编程
- M4宏编程
- Python/Perl/Ruby的列表操作
- Vimscript的某些操作