博客元年

这个博客的目的本来是讨论数据（用\(\tau\)表示）和函数式编程/计算机科学(用\(\lambda\)表示)的两类主题的。但事实上，本博客还没写过任何关于函数式编程的内容，显得有些「名不副实」。而近几年在一些项目上和自己理论学习中的实践，对于函数式编程有了一些不大不小的洞识。希望能借由这个系列来给大家传递一些函数式编程非常有用的方法，以及更督促自己对这方面进行思考和学习。

当然，介绍函数式编程的不错的博客/文章或者书籍，但是，因为Python在函数式编程方面的支持不算是非常好的（比如递归加速之类），所以以Python实现函数式编程的例子往往基于functools、itertools以及一些递归概念的介绍。所以这个博客系列试图弥补这方面的不足，并且将视野扩大，让我们在哲学、范畴学等领域的内容加入进来，进一步「元」思考编程本身。

何为函数

当然，作为本系列的第一篇文章，我们要来讨论的是「无副作用」这个概念。

首先，我们要回到一个思考，就是Python的function(s)是一个什么概念。function讨论最好当然是分析哲学的先驱弗雷泽（具体可参考下面的引用）。但我们具体抽象出来，数学上的函数有个明确的定义，即「一个自变量映射到唯一一个因变量」。也就是说，函数反复带入同一个值，理应这个结果是一致的。比如我们举下面一个例子，无论我们带入几次 x = 1都可以返回2的结果。

def f(x):
    return x + 1

也有书中（例如引用中提到的Functional Programming in Scala）也将这种原则表示为「符号代换原则」，即我们完全可以用声明函数的等式代换到下面的式子中。这个也是一个引申而来的判断是否是函数的例子，譬如：

def f(x):
    return x + 1

def g(x):
    return f(x) ** 2

这个例子中，我们完全可以使用下面的代换原则来实现。这个是数学定义的函数的最佳例子。

def g(x):
    return (x + 1) ** 2

我们把上面这些明确符合数学定义的函数就叫做「无副作用」的，因为它们的计算只涉及到了计算自己的概念，并且所有符号，只是某一个值/函数的指示词，不带有别的意涵。

事实上Python中的函数

但是事实上Python中永远允许我们定义一些不符合上面规范，但是Python术语中还是叫函数的东西，比如下面一个全局变量的例子：

a = 1

def f(x):
    global a
    a += x
    return a

我们在两次带入x = 1时，结果第一次结果是2，第二次是3。这就不符合我们函数的定义了，而究其原因，它是改变了一个函数外的变量a，因此它除了计算之外，还改变了什么，我们于是说它是有「副作用」的。

第二个产生的原因涉及可变变量，其实上面的a也是一个可变变量的例子。但是更加突出的乃是list、dict之类的可变变量或者原地操作的值，例如下面一个例子：

def f(ls, a):
    ls.append(a)
    return ls

在这个例子里，没有涉及操作全局变量，但是当我们带入了ls = [1, 2, 3]以及a = 1后，我们依旧发现每一次带入的时候，返回值还是不一样的。我们也可以把这种对于ls的改变表述为产生了副作用。如果我们仅仅是想得到ls加了一个元素后的结果，那么这个问题将显得非常严重。

SCIP(Structure and Interpretation of Computer Programs)一书中，非常好的概述了这两种思路处理函数的不同。在前者「无副作用」的例子里，a、f之类的东西，仅仅具有指示一个值/函数的意义；但是对于有「副作用」概念的后者的函数里，我们必须得构造一个「环境」的概念。这个环境里，有一个个屋子（在计算机里可能就是内存/CPU缓存的概念），a和f指示的是屋子（但有的时候又是指屋子里放的东西），更可怕的是，屋子的大小也会变化；而「无副作用」的例子里，我们只要知道符号永远指的是一个东西就好了，一次指定后就不在变化，并不需要屋子的变化。

副作用的好和坏

现在，我们就来看「无副作用」和「副作用」到底好处和坏处是什么。

1. 回溯问题

如果一个函数，它对于一个确定的输入必定有一个确定的输出，这意味着，我们很容易找到问题、定位问题、以及复现问题。而如果一个程序包含有非常多的「副作用」，这意味着我们无法控制它在函数体外修改了什么，小到一个可变函数、大到计算机的环境变量。这也就导致为什么，很多程序的报错反馈，都要打印那么多的环境变量、计算机环境之类的概念。

而无副作用意味着非常强的「可测性」，我们在后面的文章中也会一一列举出来。此外，「基于性质的测试」也成为可能。也就意味着，我们能更加强势地控制我们的程序。甚至对于一个静态的函数式语言（可惜Python不是），编译阶段就能暴露和解决绝大部分的问题。

2. 无法和环境交互的程序其实大概率是没啥用的

单纯的使用函数式的概念，我们事实上构造的是一个逻辑符号运算系统，如果没有和外界环境交互，则它就是楼台的玩具。我们甚至使用print都是在产生一个函数外的屏幕的副作用。所以，无副作用也就意味着它的应用很难。当然，「单子」的概念、把副作用限缩在一个非常小的范围里，这些方法都可以让我们对自己的程序把握还是非常强，并且 又有一定的「交互自由」。这个也是我们这个系列要强调的编程思路

3. 效率

事实上，我们上面的举例中，已经可以看出，计算机(/图灵机)本身的概念就是基于环境或者说基于副作用的。而函数式编程在一个副作用机子上实现，本来就会效率下降。更何况，如果我们不使用类似append之类的原地操作，这就意味着更多空间，更多的值的复制的概念。这些都让程序的效率大打折扣。此外，Python对诸如递归等函数式的速度优化效果并不好，这也使得副作用可能更容易让人青睐。

不过，这个效率的概念可能还有一些更加暧昧的地方。如果更大视野地看待函数式编程，里面有各种属于自己的优化方案，我们将会在后面一一介绍。

4. 表达能力（新）

在上面关于「环境」和「代换」的讨论中，我们也发现，如果使用「环境」的概念我们将要多出很多概念，譬如「传值」、「传址」、「可变变量」、「全局变量」之类的概念，而且这些概念是必须内生在语言内的。一部分程度上，这是表达效率弱的体现。事实上，函数式编程仅仅靠值和函数两个概念，加上基本的类型、运算就能实现几乎所有的事（或者说图灵完全的）。而我们后面提的「递归」、「单子」等概念，某种程度上是「派生的」而不是「内生的」。这更有Top-down数学的特征（当然数学是否如此那又是另一个问题了）。

一个关于定义域的说明

最后，我们要提到一个关于「定义域」的小问题，我在上面的论述中没有提到，因为我们稍微用到类型/定义域的概念。譬如下面一个函数（我特意带上了类型注解）：

def f(x: int) -> int:
    if x > 0:
        return x + 1

这个例子中，其实\(x\)的取值范围只能是\(x > 0\)(虽然在例外的情况Python会输出None)，但事实上这种操作和数学中的函数还是有略微的区别，因为它在声明时的定义域为int事实上的定义域是\(x \in N\)。int里并非所有取值都没用到。

在诸如scala或者haskell等函数式支持较好的语言里，也称这种函数为Partial Function（注意和Curry化中的Partial Applied Function的区别），意思是并不是所有的定义域的自变量都声明过了，比如，scala中定义上述的函数f会用到PartialFunction：

val f: PartialFunction[Int, Int] = {
  case x if x > 0 => x + 1
}

但在实际运用情况下，我们更倾向于用「无副作用」表述函数式编程的基本特性和性质，所以这种细节层面的讨论在大多数场合都被忽略，但是注重数学表达的你应该值得留意一下。

References

  • 张翠媛. 浅谈弗雷格的 “函数和概念”. 现代交际 14 (2018).
  • Chiusano, Paul, and Runar Bjarnason. Functional Programming in Scala. Simon and Schuster, 2014.
  • Abelson, Harold, and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. The MIT Press, 1996.