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

作者|马修巴特埃里克

译者|新月

| csdn (ID: csdnnews)

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

然而,随着项目规模的增加,我遇到了两个反复出现的问题,这与函数式编程的通常做法相冲突:我将它们称为大对象问题和父子问题。

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

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

函数式编程简介

函数式编程的核心原理是程序由函数组成,而这些函数又是极其独立的:

输入:函数需要的所有信息都应该作为参数列表传入。函数不应该依赖于状态,即函数外部维护的数据,如全局变量。

输出:函数不应修改作为输入接收的参数,也不应有任何影响函数外部的副作用。相反,函数应该返回一个包含新数据的值。例如,如果一个列表包含五个元素,而一个函数需要修改第三个元素,那么它应该返回一个新构造的列表。它不会修改现有列表,也不提供返回值。

很明显,函数式编程本身没有先天优势。(虽然这些独立函数也被称为纯函数。虽然这种方式和数学思维是一样的,但是计算机硬件的运行机制并不是这样。与命令式编程相比,函数式编程不擅长表达底层计算(指处理机械特性的部分),但在表达高层计算(指建模思想的部分)方面有着出色的表现。

实际上,函数式编程代表了一种风格。因为函数的输入和输出是完全独立的,所以更容易推理每个函数的行为。然后,把几个功能组合起来,形成一个程序。随着程序复杂度的增加,这个函数的整洁性优势越来越突出。

大物体的问题

函数式编程教程一般只介绍一些常见的小值,比如数字、字符串以及由它们组成的简单列表。有时候,我们也能看到用树形数据结构实现的递归。看起来很华丽,但只是列表包含了其他列表。本质上没太大区别。

如果想写处理简单数据的脚本,掌握这些简单的函数式编程技术就足够了。所以这些教程一般都会戛然而止,为你鼓掌,向你告别。很明显,后续内容涉及很多细节。

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

由于我习惯于函数式编程,所以我设计了bf实现的第一个版本。每条指令都会把已有的字节复制到一个新的数组中,然后修改相应的字节,返回这个新的数组,扔掉旧的数组(最终会被垃圾回收)。

这个实现可行吗?是可行的。它跑得快吗?不,这就是问题所在。我仔细想了一会儿,突然脑子里闪过一个想法:是不是因为我一直复制删除30K字节数组?所以,我重构了代码,让程序每次运行时创建一个只有一个字节(全局变量)的数组,并根据需要修改数组中的每个字节。结果如何?速度大大提高。我觉得奇怪吗?不,一点也不奇怪。但我感到很沮丧,因为为了提高程序的运行速度,我抛弃了函数式编程的核心思想。

艾伦珀利斯(第一届图灵奖获得者,发表《编程警句》,被广泛引用)曾说过,“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那样将“原子”变成可更改的,就像本文中的“中介”一样。

END

标签: 函数式编程  编程语言  字节 

标签

发表评论