函数式编程中的两个棘手问题

作者 | Matthew Butt­erick

译者 | 弯月

出品 | CSDN（ID：CSDNnews）

大约从十年前，我开始使用Lisp编程语言，后来我喜欢上了函数式编程。每当使用非Lisp语言（比如JavaScript、Python、Swift）时，我也会带着这些编程习惯。在我掌握map、forEach 或 filter的使用后，就不再使用命令式风格编写循环了。

然而，随着项目规模的增大，我遇到了两个反复出现的问题，这两个问题与函数式编程的惯用做法产生了矛盾：我称之为大对象问题和父与子问题。

有趣的是，这两个问题的原因都是函数式编程模型不符合计算机的底层硬件现实。

函数式编程简介

函数式编程的核心原则是，程序由函数构成，而这些函数都极其独立： 

● 输入：函数需要的所有信息都应作为参数列表传入。函数不应该依赖状态，也就是函数外部维护的数据，比如全局变量。

● 输出：函数不应该修改作为输入接收的参数，也不应该有任何影响到函数外部的副作用。相反，函数应该返回一个包含新数据的值。例如，一个列表包含5个元素，而某个函数需要修改第3个元素，则它应该返回一个新构造的列表。它不会采用修改现有列表且不提供返回值的做法。

需要明确的是，函数式编程本身并没有什么天生的优越之处。（尽管这些独立函数也被称为纯函数。）尽管这种方式与数学思维相同，但计算机硬件的运行机制并不是这样的。与命令式编程相比，函数式编程在表示底层计算（指的是处理机械特性的部分）方面做得较差，但在表示高层计算（指的是建模思想的部分）方面有出色的表现。

在实践中，函数式编程代表的是一种风格。由于函数的输入和输出完全独立，因此更容易推理每个函数的行为。然后，再将多个函数组合起来构成程序。随着程序复杂性的增加，这种函数的整洁性带来的优势也越来越突出。

大对象的问题

函数式编程的教程一般只会介绍一些常见的小值，比如数字、字符串以及由它们构成的简单列表。有时，也能看到利用树形数据结构实现的递归。看起来很绚烂，但也不过是列表中包含了其他列表。本质上并没有太大不同。

如果想编写处理简单数据的脚本，那么掌握这些简单的函数式编程技术就够了。因此，这些教程通常会在此处戛然而止，并为你鼓掌，跟你告别。很显然，后续内容涉及大量细节。

在开始尝试更复杂的项目时，比如在为我的书《Beautiful Racket》编写 bf 语言教程时，我第一次感受到了失望。在 bf 中，每个程序都会初始化一个 30K 字节的数组。bf 中的所有指令都会操作数组中的一个字节。

由于已经习惯了函数式编程，因此我设计了第一版的 bf 实现，每条指令都会将现有字节复制到一个新数组中，然后修改相应的字节，返回这个新数组，并扔掉旧数组（最终会被垃圾收集）。

这个实现可行吗？可行。运行速度快吗？不快，这就是问题所在。我认真琢磨了一段时间，突然我的脑海中闪过一个念头：难道是因为不断复制和删除 30K 字节的数组？于是，我重构了代码，让程序在每次运行时只创建一个字节的数组（一个全局变量），并根据需要修改数组中的各个字节。结果如何？速度大幅提高。我感到奇怪吗？不，一点都不奇怪。但我感到很失落，因为为了提高程序的运行速度，我抛弃了函数式编程的核心思想。

Alan Perlis（第一位图灵奖得主，曾发表《编程警句》，被广泛引用）曾说过：“LISP程序员只看到所有东西的价值，却对要付出的代价一无所知。”我正是犯了这个错误。我被函数式编程散发出的魅力所吸引，却在不经意期间创建并销毁数十亿次 30K 的内存块。原因就在于函数式编程允许我避免状态和修改数据。但是分配和销毁内存不是免费的。因此，最后的成本远远超出了我的承受能力。

事实上，Perlis 的警句指出了所有编程语言中的一个终极矛盾：如何将人类的思想与计算机的实现连起来。可以说，编程语言唯一的目的就是将我们与这些细节隔离开来，让我们自然地表达自己。但是我们离机器的现实越远，使用计算机资源的效率就越低。

这是大对象问题的核心。大而复杂的程序往往会创建大而复杂的数据结构来表示现实的某个部分。然而，函数式编程建议我们想尽各种办法创建并销毁这些结构。但是内存操作从来都不是免费的。因此，遇到需要耗费大量内存的结果，函数式编程的原则就会造成不必要的浪费。

例如，我有一款应用Archetype，它是一个图形界面的字体编辑器（用 Swift 编写）。从基本结构来说，字体是一种小型图形：不仅有文字的形状，还有间距数据、布局说明以及许多其他复杂的字段。总的来说，字体数据结构可能高达数兆字节。在修改某个字形的宽度（一个整数）时，丢弃整个字体结构并创建一个新结构是不合理的。

因此，在实现该应用时，遇到一些“小处理”（即处理简单的值或小结构），我采用了函数式编程；而遇到“大处理”，我就会采用直接修改的方式。

将函数式编程融入 GUI 应用程序还有一个问题：GUI 本身是一种可变、全局状态的形式。在我的应用中，大多数的字体修改都会导致GUI的变更。同样，在用户通过GUI修改字体时，也会触发底层字体数据的更新。我不能随便丢弃字体数据结构并重新生成一个，因为屏幕上的显示依赖于这些结构。

说到这里，我不得不提及另一个令我烦恼的问题……

父与子问题

许多编程语言都提供了多种创建自定义数据结构的方法，它们将这些方法称为结构或对象等。但这些方法都源自一个相同的思路：我们可以将事物的集合当成一个事物在程序中传递。

然而，这种抽象的代价是我们需要建立一个间接层。简单来说，语言为这些结构（及其事物的集合）分配一块内存并返回对该结构的引用。这样，我们就可以将结构当作一个事物在程序中来回传递。每个引用都指向一个特定的内存块。

但是，这个结构引用的行为不同于程序中的其他值。作为程序员，我们早已习惯了区分“值”与“引用”的语义，就像呼吸一样自然。

在拥有大量的结构后，我们就会发现，我们需要创建一个结构去引用其他结构，即父子关系。

例如，在我的应用Archetype中，每种字体都包含一个字形数组；而每个字形又都包含一个轮廓数组；而每个轮廓又包含一个点数组；等等。这个例子包含多层结构。但即使在最简单的引用结构中，即一个结构引用另一个结构，也会遇到类似的问题。

假设，在我的应用中，我想按照函数式编程的风格，定义一个字形的操作。我该怎么做？很简单，编写一个函数，输入接收一个字形，然后创建一个具有新特征的新字形，并将其作为结果返回。而旧字形则从内存中释放。

如果一个字形与其他事物没有任何关系，那么这种实现方法没问题。但在我的应用中，每个字形都是字体的子代。当我针对子字形调用这个更新功能时，就能获得一个返回的新字形，但父字体仍然持有指向旧字形的引用。

本质上，这个父字体变成了依赖子字形的外部状态。为了更新子字形，我们必须更新父字体引用的字形。也就是说，我们需要在内部添加一些额外的处理。

有人可能会建议：重新定义子操作，将父与子都作为输入，然后同时修改两者。但这种方法仍有两个问题：

1. 这样会导致子结构的操作不得不将父结构也卷进去。尽管我们可以容忍这种代码上的混乱。

2. 更深层次的问题在于，可能还有其他结构持有指向旧字形的引用。在上述更新之后，它们都将保留旧字形的引用。也就是说，这里我们所说的“父与子问题”可能是一个子结构被多个父结构引用。无论我们对子结构进行任何操作，所有父结构都必须更新。

对于这个问题，函数式编程没有解决方案。所以，最终我们不得不采用以下三种模式之一：

1. 父子链接变成双向的。这样，当子结构被更新时，它可以追溯到所有的父结构，并更新它们。这种方式非常糟糕，因为本应互相分离的结构之间产生了更多的纠缠。

2. 子结构可以发出通知事件。就像是程序发射信号枪一样，其他结构可以采取适当的行动。虽然这种方式比第一种更好，因为子结构无需在意或关心父结构。但这仍然需要在程序中引入新的控制机制。而且这也背离了函数式编程的思想，因为每个通知事件都会触发难以推理的副作用。

我的应用就采用了通知事件。我不得不构建一个表示通知事件流的图形，这个图形与数据图相似，但又不完全相同，而且还需要随着数据的变化保持同步。

3. 或者，只需要放弃子结构的不可变性，就可以从根本上避免所有这些复杂性。父结构保留现有的引用，但当它们访问结构的引用时，就会得到更新的版本。

根据我的经验，选择第三种方式更合适，因为这种方式既简单又确保了独立性。尽管随着这种模式的应用越来越多，我们与函数式编程也渐行渐远。

父与子问题如何解决？

我认为最佳解决方法是（我们还没有广泛采用），引入一个代理，我称之为“可变的中介”。每个子结构都有一个中介。父结构不要直接指向子结构，而是指向中介，然后再由中介指向子结构。

当子结构发生变化时，中介更新为指向新的子结构。但是，所有父结构仍然可以指向同一个中介。这样，下次它们引用子结构（通过中介）时，就会得到新的子结构。总的来说，这个解决方法的思路是，如果某些结构的变更是不可避免的，那么至少我们可以集中和简化变更逻辑。

此外，中介也不会拒绝对子结构的修改，也就是说任何父结构都可以通过中介访问子结构并修改子结构。每个持有指向该中介的引用的父结构都会立即看到变化。

为什么我没有采用这种方式？在理想情况下，父结构并不需要在意是直接访问子结构，还是通过中介访问子结构。这只是一个实现细节。但这意味着，中介需要提供与子结构相同的API。说起来容易做起来难，尤其是我们不想创建大量的中介，不想针对每个子结构创建一个中介，因为这会产生大量的样板包装函数。

在我看来，可变中介本质上是一个指向指针的指针（也就是二级指针），它属于较低级别的内存管理。因此，应该放到语言编译器中处理，并作为语言特性公开，或者只是存储和访问用户定义的数据结构的默认方式。

看到这里，可能有人会说：“某些语言中可变结构和不可变结构的实现的区别就在于此啊。”可能吧。但据我所知，可变结构一旦创建，就永远不会被视为不可变。一旦我们做了选择，就只能一直坚持下去。相比之下，可变中介的模式允许某个结构有时可变，而有时又不可变，也就是说具有双重性。

我不是 Rust 用户，但我明白借用检查器可以让你使用可变或不可变引用“签出”内存对象。如果是这样，那么上述建议也不是太糟糕，因为优秀的程序员也想出了双重性的思路：同时维持可变与不可变。但是，不知道 Rust 借用检查器是否解决了父与子问题。我猜并没有。借用检查器是为了确保内存安全（保证一次只能循环一个可变引用）。根据坎宁安定律（如果想在互联网上得到优秀的答案，最佳方法不是提问，而是发布一个错误的答案），如果我这里给出了错误的答案，那么相信很快就能得到正确答案。

大对象问题如何解决？

我不知道。如前面所述，我们看到函数式编程中的一个概念是，如果占用内存不多，则我们可以随意分配内存或销毁对象，几乎没有太大代价。然而在实践中，占用的内存很容易超过我们预期的阈值。

最有效的方法是，将大对象分解成接近阈值的小对象。也就是说，我们不能创建一个百万字节的blob，而是应该将其分解成一百万个可以单独更新的小对象。

这种情况似乎听起来很熟悉，没错，我们只是将大对象问题转化成了父与子问题。所以解决父与子问题才是关键。

用户评论

评论1：

在我看来，这两个问题都有一个简单的答案。 

在函数式编程中，通常我们不会直接操作状态，而是将操作状态的函数组合成更复杂的函数。（例如，在 Haskell 中，这种组合通常是通过 monad 完成的。）最终，你就会得到一个代表整个程序的函数。

这在某种程度上与命令式编程很相似，它更像是一种参照系的转变。我们可以拿工厂的装配线做个类比。命令式编程就像你站在工厂车间里，观察每一台工厂车间里的机器（过程程序），接收一个东西（输入），做一些处理，然后输出。而函数式编程就像你从一个东西的角度去观察，它流经工厂里的整条流水线，在自己的引用框架内完成所有的处理。这样你看到的并不是东西（数据）被传递，而是看到一件东西流过不同的机器（函数），这是完全相反的方向，因此，你看到的不是我们将东西（数据）传来传去，我们传递的实际上是执行处理的机器（函数）。

评论2：

这些问题有许多已有的解决方案。

对于大对象问题，可以采用路径复制来持久化数据结构。将多个小修改打包成一个大修改（在内部使用不会泄露到外部的更改）。使用类型系统来判断何时复制是不必要的（一些新的语言在实验这一方法）。围绕一个可变的“数据存储”来实现程序结构。

对于“引用”问题，可以显式表示引用，比如通过ID来表示。或者像Clojure那样将“原子”变成可更改的，就像本文中的“中介”一样。

原文链接：https://matthewbutterick.com/chron/two-vexing-problems-in-functional-progamming.html

END

— 推荐阅读 —
☞苹果知名开发者怒“怼”：GitHub 不可信，俄罗斯开发者贡献的项目遭毁灭性打击！
☞25% 的开发者认为 Rust 是最佳替代！最新 Go 开发者调查报告出炉
☞C++之父Bjarne Stroustrup：程序员在数学上付出的努力，永远也不会白费

—点这里↓↓↓记得关注标星哦~— 

一键三连 「分享」「点赞」「在看」

成就一亿技术人