在内存方面，FRP是如何处理的？

Question

阅读有关FRP（Functional Reactive Programming）的内容后，与标准命令式方法相比，我对其直观性和逻辑性感到惊讶，但有一件事情让我感到困惑...计算机如何不会立即耗尽内存？

从[这里]收集的信息显示，在FRP中，值的更改的完整历史记录（过去、现在和未来）是头等的。如果它用于不立即从内存中清除值的环境中，这个概念立即在我的脑海中触发了一个警报，说明它必须非常快地消耗掉你的内存。

阅读[Fran]时，我注意到一些示例具有递归定义的函数而没有终止条件。如果函数永远不能终止并将其值返回给调用它的函数，那么它将如何完成任何工作？或者说，它不会在一段时间后爆栈吗？即使是像Haskell这样的惰性语言也会遇到堆栈溢出的问题。

对于这些问题的解释将非常感激，因为它完全让我困惑了。

- Electric Coffee

Answer 1

这种方法适用于简单情况并不奇怪：由于Haskell的惰性和垃圾回收，我们已经可以轻松使用无限数据结构。只要你的最终结果不依赖于一次获得所有值，它们可以在进行过程中被收集或者根本不需要被强制获取。

这就是为什么这个经典的斐波那契例子在常数¹空间中运行：一旦下两个条目被计算出来，列表中的先前条目就不再需要了，因此它们会随着进行而被收集——只要您没有任何其他指向该列表的指针。

fib n = fibs !! n
  where fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

尝试使用不同的输入运行此函数，并查看内存使用情况。（使用+RTS -s运行。）

（如果您想要更详细的解释和图表，请查看我写的this post。）

重点是，即使程序员可以获得无限量的信息，如果没有其他依赖于它，我们仍然可以对大部分信息进行垃圾回收。

完全相同的逻辑可以用于有效地实现FRP程序。

当然，一切都不是那么简单。在fibs示例中，如果我们有一个指向fibs列表开头的活动指针，内存使用量将会大幅上升。如果您有一个依赖于过多历史数据的计算，FRP也会发生同样的情况：这被称为时间泄漏。

处理时间泄漏是实现高效、良好行为的FRP框架的未解决问题之一。提供表达力强的FRP抽象很困难，同时又不允许出现内存使用不当甚至灾难性的情况。我认为目前大多数方法都会提供抽象的FRP类型以及一组较不容易引起此类泄漏的操作；其中一种特别极端的形式是箭头化FRP，它完全没有提供行为/信号类型，而是用信号之间的变换（作为箭头）来表达所有内容。

我从未尝试过自己实现一个好的 FRP 系统，因此无法详细解释其中的问题。如果您对此主题更详细的内容感兴趣，一个很好的查找地点是 Conal Elliott 的博客， this post 是一个很好的起点。您还可以查看他写的一些论文，比如 "Push-Pull Functional Reactive Programming" 以及其他关于这个主题的论文，包括一些关于箭头化 FRP 的论文，例如 "Functional Reactive Programming, Continued"（几乎随机选择）。

脚注：

¹ 这不是真正的常数空间，因为中间结果本身会变得更大。但它应该保持恒定数量的列表单元格在内存中。

- Tikhon Jelvis

---

但是如果完整的历史记录是一个一等公民，肯定有办法回到开头的方式，对吧？就像在以FRP为基础构建的Elm语言中，它甚至有一个"时间旅行调试器"，允许您随意浏览程序的时间线。这肯定会导致某种时间泄漏，不是吗？ - Electric Coffee

重点是，只有在你实际上需要从一开始就使用数据的情况下，才会导致内存泄漏——这种类型的泄漏确实会发生。但是，如果你的程序编写方式不使用所有这些数据，它可以被安全地垃圾回收。 - Tikhon Jelvis

我相信 Elm 的调试器必须在内存中存储很多东西，因为没有其他办法。但是一个普通的 Elm 程序可以收集其中大部分内容，从而使内存使用合理。 - Tikhon Jelvis

@ElectricCoffee：这些函数之所以有效，是因为它们的返回值始终是惰性构造函数：一种数据结构，它捆绑了代码，说明如何计算字段的值。从更低层次的角度来看，为这样的递归函数生成的对象代码不会调用自身；相反，它返回一个具有指向函数本身的指针的结构体。返回的结构体的使用者通过访问字段或不这样做来选择递归调用实际发生的时间和方式。 - Luis Casillas

我想提一下，时间泄漏问题在近年来已经得到解决。旧博客文章描述了这个问题和可能的解决方案。最近的文章描述了在reactive-banana的最新版本中的解决方案。 - Heinrich Apfelmus

Answer 2

关于您提出的时间泄漏问题：这确实是实施FRP的主要挑战之一。然而，FRP研究人员和实现者已经找到了几种避免它们的方法。

这完全取决于您为信号提供的精确API。主要问题是是否提供高阶FRP。这通常采用“单子结合”原语来表示信号：一种将信号转换为信号的方式，或者换句话说，是一种API，用于生成在多个其他信号之间动态切换的信号。这种API非常强大，但可能会引入潜在的时间泄漏问题，即您所问的问题：需要在内存中保留信号的所有先前值。然而，正如Heinrich Apfelmus在对以前答案的评论中提到的那样，有一些通过限制某些高阶API的方式来解决这个问题的方法，使用类型系统或其他方式。请参阅该评论以获取进一步的说明链接。

许多FRP库简单地没有提供高阶API，因此（非常容易地）避免了时间泄漏的问题。您提到了Elm，在这种情况下，如此处所述，信号在Elm中不是单子。这的确会带来表达能力上的代价，因为没有提供强大的单子API，但并不是每个人都认为在FRP框架/库中需要这种API的一般能力。

最后，我建议看一下Elm的主要作者Evan Czaplicki的一次有趣的演讲，他非常好地解释了这些问题并提供了可能解决它们的概述。他将FRP方法根据它们如何解决这些问题进行分类。

- Dominique Devriese