累加器引发的一点思考

趁着最近肺炎，在家修养生息：看看剧，看看电影，偶尔也会学习一下。最近在学习 Elixir 这门语言，由于其实在太小众，只能抱着一本英文书啃（第一次看英文书籍，也没想象中那么难，就是看得比较慢），在看到 Elixir 实现累加器（就是《黑客与画家》里介绍的累加器）的时候，突发兴趣研究了一下，便有了本文。

累加器是什么

Paul Graham 在《黑客与画家》中是这么描述累加器（函数）的：

我们需要写一个函数，它能够生成累加器，即这个函数接受一个参数 n，然后返回另一个函数，后者接受参数 i，然后返回 n 增加（increment）了 i 之后的值。「这里说的是增加，而不是 n 和 i 的相加（plus）。累加器就是应该完成 n 的累加。」

比如说，这个函数是 foo，那么它应该具备以下行为：

acc = foo(2)
acc(6)  // result = 8
acc(7)  // result = 15

想了一下，如果某语言可以比较舒服的实现这个函数，则该语言需要具备两个特性：

1. 对词法变量的完全支持；
2. 函数是一等公民（即函数可以作为返回值）。

图灵等价

Common Lisp 的实现：

(defun foo(n)
  (lambda (i) (incf n i)))

虽然根据图灵等价来说，所有的语言在功能上都是相同的，但这没有意义：因为题目要求的并不只是实现一个（累加器）功能，还对具体的实现有额外的要求（必须使用函数来实现），因此你没有办法使用 Java 来实现（因为 Java 无法把函数作为另一个函数的返回值）。

举一个更一般的例子，比如有个问题：要求计算 167564386575724718662 的平方，但不得自行编写处理整数溢出的函数。在这个问题中：计算一个数的平方是功能，而不得自行编写处理整数溢出函数则是额外的要求。

如果只是针对功能来说，确实所有图灵完备的语言都可以实现，只需要处理一下溢出的整数就好，但这类问题狡猾在对具体的实现还有额外的要求，因此，整数会溢出的语言便无法解决这个问题。

Python 的实现

在书中，Paul Graham 给出了 Python 的一种（累加器）实现：

def foo(n):
    s = [n]
    def bar(i):
        s[0] += i
        return s[0]
    return bar

之所以需要这么写，而不能直接使用 lambda 返回的原因有两点：

1. Python 中的 lambda 无法使用赋值（=）符号；
2. Python 中对词法变量并非完全支持。

有关第一点，《流畅的 Python》一书中提到，因为 Guido 不想让 Python 变得太函数化，因此极大地限制了 lambda 的使用。

而第二点，则是因为 Python 不支持对词法变量「重新赋值」的缘故：

def foo(n):
    def bar(i):
        n = n + i
        return n
    return bar

在 foo 内部的 bar 函数中，n = n + i 语句会在当前词法作用域新建一个变量 n（当前作用域不存在 n 而且有「=」符号），因此这个写法是错误的，运行会得到 UnboundLocalError 的错误，除非在 bar 函数中显式声明：nonlocal n，表示 n 使用上一层词法作用域的值。

那么为什么书中的实现没有声明 nonlocal 也可以呢？注意我刚刚提到的，Python 虽然不支持对词法变量的「重新赋值」，但是支持对已存在的词法变量「修改」：对于 s 来说，s[0] += i 这个操作，并没有把 s 重新赋值，而只是把 s 的其中一个元素修改了，换句话说 s 本身的地址是没有变的：

>>> a = [0]
>>> id(a)
4438808928
>>> a[0] = 1
>>> id(a)
4438808928

同理，其他可变的数据类型（class、dict）也都可以实现这个功能：

以下是使用 dict + lambda 实现的：

def foo(n):
    d = dict(r=n)
    return lambda i: d.update(r=i+d['r']) or d['r']

看起来虽然简洁了不少，但我觉得这远不如使用 nonlocal 来得优雅，而且这种方式也降低了可读性。

Elixir 的实现

数据不可变

我学习 Elixir 也有二十来天了（从这一次提交开始），虽然早就预见数据不可变会给我的编程习惯带来一定影响，但是没想到影响会这么大。

还是拿累加器举例子。更近一步地说，要实现这个累加器（函数），只需要保证闭包内部的词法作用域能修改外部作用域的变量就可以了。

iex(1)> outside_var = 5
5
iex(2)> lambda = fn -> IO.puts(outside_var) end
iex(3)> lambda.()
5
iex(4)> outside_var = 6
iex(5)> lambda.()
5

但由于 Elixir 的数据是不可变的，定义 lambda 时，内部词法作用域保存的 outside_var 的引用地址的值是 5，定义完毕后，lambda 内部引用地址的值便无法被修改了。

这里虽然对 outside_var 绑定了两次值（5 和 6），但第二次绑定并不是修改内存地址的值，而是重新申请一块内存赋值为 6，再将其绑定给 outside_var。

也就是说，虽然 Elixir 对词法变量完全支持（不会像 Python 一样报错）：

iex(6)> foo = fn n ->
          fn i ->
            n = n + i
          end
        end
warning: variable "n" is unused
iex(7)> f = foo.(7)
iex(8)> f.(8)
15  # 首次调用，符合预期
iex(9)> f.(8)
15  # 这里我们期待值为 23

但这种写法得到了不符合我们预期的行为，它同样会在内部匿名函数的词法作用域中添加 n 变量（由于 n 没有使用，所以解释器报 warning 了），并不会对外部作用域的 n 变量进行修改。且 Elixir 并没有 Python 那样的 trick（使用 list、dict 等可变类型），毕竟 Elixir 里的数据是不可变的（无论是什么数据类型）。

那么问题来了，Elixir 该怎么修改并保存变量呢，更一般地说，Elixir 如何保存进程的状态呢？

消息传递

由于 Elixir 里的进程（这里的进程，有别于操作系统的进程，更类似于 Go 或者 Python 里的「协程」）都是完全孤立的，进程间无法通过共享内存来通信，因此 Elixir 采用消息传递（message passing）的方式进行进程之间的通信，也是通过它，我们可以构建出保存状态的进程。

比如这里的累加器函数，在每次调用累加器时，需要做两件事：

1. 从消息信箱中获取上一次累加的结果；
2. 更新这个结果，并将结果发送给消息信箱。

foo = fn n -> send(self(), n)
  fn i -> result = 
    receive do
      num -> num
    end
    send(self(), result + i)
  end
end

值得注意的是，虽然 receive 语句是阻塞的，但是能保证每次开始调用累加器时，消息信箱中总是有数据的（来自于上一次累加发送的消息），因此进程并不会阻塞住。

iex(1)> f = foo.(2)
iex(2)> f.(2)
4
iex(3)> f.(2)
6

不过，由于这种方法涉及进程之间的通信，因此耗费的时间远比原生支持修改外部作用域变量的语言要多（大约是 Python 的实现方式的 10 倍左右）。

结尾

其实有些纠结是否应该发这类文章，主要是纠结其内容是否有价值，后来想了想，当然是有价值的，价值的名字叫做「独立思考」。

参考：

• 黑客与画家
• Elixir in Action 2nd