Haskell 需要垃圾收集器吗？

正如其他人已经指出的那样，Haskell 需要自动的、动态的内存管理：自动内存管理是必要的，因为手动内存管理是不安全的；动态内存管理是必要的，因为对于某些程序，对象的生命周期只能在运行时确定。

例如，考虑以下程序：

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

在这个程序中，列表 [1..1000] 必须保存在内存中，直到用户键入“clear”；所以这个必须的生命周期是动态确定的，这就是为什么动态内存管理是必要的。

所以从这个意义上说，自动动态内存分配是必要的，实际上这意味着：是的，Haskell 需要一个垃圾收集器，因为垃圾收集是性能最高的自动动态内存管理器。

然而...

尽管垃圾收集器是必要的，但我们可能会尝试找到一些特殊情况，编译器可以使用比垃圾收集更便宜的内存管理方案。例如，给定

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

我们可能希望编译器检测到当 f 返回时可以安全地释放 x2（而不是等待垃圾收集器释放 x2）。本质上，我们要求编译器执行 escape analysis 以尽可能将分配转换为垃圾收集堆到 allocations on the stack。

这不是太不合理的要求：jhc haskell compiler 这样做，尽管 GHC 没有。 Simon Marlow says 认为 GHC 的分代垃圾收集器使得逃逸分析几乎是不必要的。

jhc 实际上使用称为 region inference 的复杂形式的转义分析。考虑

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

在这种情况下，简单的逃逸分析会得出结论，x2 从 f 逃逸（因为它在元组中返回），因此 x2 必须分配在垃圾收集堆上。另一方面，区域推断能够检测到当 g 返回时可以释放 x2；这里的想法是 x2 应该分配在 g 的区域而不是 f 的区域。

超越 Haskell

虽然区域推断在上述某些情况下很有帮助，但似乎很难与惰性求值有效协调（参见 Edward Kmett's 和 Simon Peyton Jones' 评论）。例如，考虑

f :: Integer -> Integer
f n = product [1..n]

人们可能想在堆栈上分配列表 [1..n] 并在 f 返回后将其释放，但这将是灾难性的：它会将 f 从使用 O(1) 内存（在垃圾回收下）更改为 O( n) 记忆。

在 1990 年代和 2000 年代初期，针对 strict 功能语言 ML 的区域推断进行了大量工作。 Mads Tofte、Lars Birkedal、Martin Elsman、Niels Hallenberg 就他们在区域推断方面的工作写了一篇可读性很强的 retrospective，其中大部分内容都集成到了 MLKit compiler 中。他们试验了纯基于区域的内存管理（即没有垃圾收集器）以及混合的基于区域/垃圾收集的内存管理，并报告说他们的测试程序比纯垃圾运行“快 10 倍和慢 4 倍”-收集的版本。

---

让我们举一个简单的例子。鉴于这种

f (x, y)

在调用 f 之前，您需要在某处分配对 (x, y)。你什么时候可以解除分配那对？你不知道。当 f 返回时，它不能被释放，因为 f 可能已将该对放入数据结构中（例如，f p = [p]），因此该对的生命周期可能必须比从 f 返回的时间长。现在，假设这对被放在一个列表中，谁把列表拆开可以释放这对吗？不，因为这对可能是共享的（例如，let p = (x, y) in (f p, p)）。所以很难判断何时可以解除分配。

Haskell 中几乎所有的分配也是如此。也就是说，可能有一个分析（区域分析）给出了寿命的上限。这在严格语言中工作得相当好，但在惰性语言中则不太有效（在实现中，惰性语言往往比严格语言做更多的突变）。

所以我想把这个问题转过来。为什么你认为 Haskell 不需要 GC。您建议如何进行内存分配？

---

你认为这与纯洁有关的直觉是有道理的。

Haskell 被认为是纯的，部分原因是函数的副作用在类型签名中被考虑在内。因此，如果一个函数有打印某些东西的副作用，那么它的返回类型中一定有一个 IO。

但是有一个函数在 Haskell 的任何地方都隐式使用，它的类型签名没有考虑到，在某种意义上，它是一个副作用。即复制一些数据并返回两个版本的功能。在幕后，这可以通过复制内存中的数据来实现字面意义，也可以通过增加以后需要偿还的债务来“虚拟地”发挥作用。

可以设计具有更多限制类型系统（纯“线性”系统）的语言，这些系统不允许复制功能。从使用这种语言的程序员的角度来看，Haskell 看起来有点不纯洁。

事实上，Clean 是 Haskell 的一个亲戚，具有线性（更严格地说：唯一）类型，这可以让您了解禁止复制会是什么样子。但是 Clean 仍然允许复制“非唯一”类型。

这方面有很多research，如果您用足够的 Google 搜索，您会找到不需要垃圾收集的纯线性代码示例。您会发现各种类型系统可以向编译器发出信号，表明可能使用哪些内存，从而允许编译器消除一些 GC。

从某种意义上说，量子算法也是纯线性的。每个操作都是可逆的，因此不能创建、copied 或销毁任何数据。 （它们在通常的数学意义上也是线性的。）

与具有显式 DUP 操作的 Forth（或其他基于堆栈的语言）进行比较也很有趣，这些操作可以明确何时发生重复。

另一种（更抽象的）思考方式是注意 Haskell 是由简单类型的 lambda 演算构成的，该演算基于笛卡尔封闭类别理论，并且此类类别配备了对角函数 diag :: X -> (X, X)。基于另一类类别的语言可能没有这样的东西。

但总的来说，纯线性编程太难用了，所以我们选择了 GC。

---

应用于 Haskell 的标准实现技术实际上比大多数其他语言更需要 GC，因为它们从不改变以前的值，而是根据以前的值创建新的、修改过的值。由于这意味着程序不断地分配和使用更多的内存，随着时间的推移，大量的值将被丢弃。

这就是为什么 GHC 程序往往具有如此高的总分配数字（从 GB 到 TB）：它们不断地分配内存，而且只有高效的 GC 才能在用完之前回收它。

---

如果一种语言（任何语言）允许你动态分配对象，那么有三种实用的方法来处理内存的管理：

该语言只能允许您在堆栈上或在启动时分配内存。但是这些限制严重限制了程序可以执行的计算类型。 （在实践中。理论上，您可以通过在一个大数组中表示它们来模拟（例如）Fortran 中的动态数据结构。这太可怕了......与本次讨论无关。）该语言可以提供明确的免费或处置机制.但这取决于程序员是否正确。存储管理中的任何错误都可能导致内存泄漏......或更糟。语言（或更严格地说，语言实现）可以为动态分配的存储提供自动存储管理器；即某种形式的垃圾收集器。

唯一的其他选择是永远不要回收动态分配的存储。这不是一个实用的解决方案，除了执行小计算的小程序。

将此应用于 Haskell，该语言没有 1. 的限制，并且没有按照 2. 的手动释放操作。因此，为了可用于不平凡的事情，Haskell 实现需要包含垃圾收集器.

我想不出在纯语言中需要 GC 的情况。

大概您的意思是纯函数式语言。

答案是在底层需要 GC 来回收该语言必须创建的堆对象。例如。

纯函数需要创建堆对象，因为在某些情况下它必须返回它们。这意味着它们不能在堆栈上分配。

可能存在循环的事实（例如，由 let rec 产生）意味着引用计数方法不适用于堆对象。

然后是函数闭包......也不能在堆栈上分配，因为它们的生命周期（通常）独立于创建它们的堆栈帧。

我正在寻找如果不存在 GC 会泄漏的示例代码。

几乎任何涉及闭包或图形数据结构的示例都会在这些条件下泄漏。

---

只要您有足够的内存，就不需要垃圾收集器。然而，实际上，我们并没有无限的内存，所以我们需要一些方法来回收不再需要的内存。在像 C 这样的不纯语言中，你可以明确声明你已经完成了一些内存来释放它 - 但这是一个变异操作（你刚刚释放的内存不再安全读取），所以你不能使用这种方法一种纯粹的语言。所以它要么以某种方式静态分析你可以在哪里释放内存（在一般情况下可能是不可能的），像筛子一样泄漏内存（在你用完之前很好用），或者使用 GC。

---

GC 是纯 FP 语言中的“必备”。为什么？操作 alloc 和 free 是不纯的！第二个原因是，不可变的递归数据结构需要 GC 才能存在，因为反向链接为人类思维创造了深奥且不可维护的结构。当然，反向链接是一件好事，因为复制使用它的结构非常便宜。

无论如何，如果您不相信我，只需尝试实现 FP 语言，您就会发现我是对的。

编辑：我忘了。没有 GC，懒惰是地狱。不相信我？只需在不使用 GC 的情况下尝试它，例如 C++。你会看到……东西

---

Haskell 是一种非严格的编程语言，但大多数实现使用按需调用（惰性）来实现非严格性。在按需调用中，您仅在运行时使用“thunk”机制（等待评估然后覆盖自身的表达式，保持可见以在需要时重用其值）来评估内容。

因此，如果您使用 thunk 懒惰地实现您的语言，您将所有关于对象生命周期的推理推迟到最后一刻，即运行时。由于您现在对生命周期一无所知，因此您唯一可以合理地做的就是垃圾收集......

---