haskell - Haskell 需要垃圾收集器吗？

Question

我很好奇为什么 Haskell 实现使用 GC。

我想不出在纯语言中需要 GC 的情况。这只是为了减少复制而进行的优化，还是确实有必要？

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

Answer 1

正如其他人已经指出的那样，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

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

这个要求并不是太不合理:jhc haskell compiler这样做，尽管 GHC 不这样做。西蒙·马洛 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必须分配在垃圾收集堆上。另一方面，区域推断能够检测到 x2可以在 g 时释放返回；这里的想法是 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) 内存。

在 20 世纪 90 年代和 2000 年代初，针对严格函数式语言 ML 的区域推理进行了大量工作。 Mads Tofte、Lars Birkedal、Martin Elsman、Niels Hallenberg 写了一篇相当可读的 retrospective关于他们在区域推理方面的工作，他们将其中大部分集成到 MLKit compiler 中。他们尝试了纯粹基于区域的内存管理(即没有垃圾收集器)以及混合基于区域/垃圾收集的内存管理，并报告说他们的测试程序比纯垃圾运行“快 10 倍到慢 4 倍”。收集版本。