Haskell需要垃圾回收器吗？

Question

Haskell需要垃圾回收器吗？

haskellgarbage-collection

131

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

在纯函数式语言中，我想不出需要使用GC的情况。这只是一种优化以减少复制，还是确实有必要？

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

- Pubby

15

你可能会觉得这个系列很有启发性；它涵盖了垃圾是如何产生（以及随后被收集）的：http://blog.ezyang.com/2011/04/the-haskell-heap/ - Tom Crockett

6

在纯语言中到处都有引用！只是没有可变引用。 - Tom Crockett

1

@pelotom 不可变数据或不可变引用的引用？ - Pubby

3

数据是不可变的这个事实源于所有引用都是不可变的，一直到最底层。 - Tom Crockett

4

当涉及内存分配时，将停机问题的推理应用于其中，有助于理解为什么在一般情况下无法静态预测解除分配。但是，有某些程序可以预测解除分配，就像有某些程序可以在不实际运行它们的情况下知道其是否终止。 - Paul R

显示剩余8条评论

8个回答

33

让我们来看一个简单的例子。给定如下：

f (x, y)

在调用f之前，您需要在某处分配一对 (x, y)。那么什么时候才能解除该对的分配？你不知道。它不能在f返回时被释放，因为f可能已经将该对放入数据结构中（例如，f p = [p]），因此该对的寿命可能比从f返回的时间更长。现在，假设该对被放在了列表中，那么取出列表的任何人都不能释放该对。因为该对可能是共享的（例如，let p = (x, y) in (f p, p)）。因此很难确定何时可以释放该对。

对于Haskell中的几乎所有分配，情况都是如此。也就是说，有一种分析方法（区域分析）可以给出生命周期的上限。在严格语言中，这种方法运行得相当不错，但在惰性语言中效果较差（惰性语言在实现中往往会进行更多的变异）。

所以我想反过来问一个问题。您认为为什么Haskell不需要垃圾回收？您建议如何进行内存分配？

- augustss

21

你的直觉是正确的，这与纯度有关。

Haskell被认为是纯的部分原因在于函数的副作用在类型签名中得到了考虑。因此，如果一个函数具有打印某些内容的副作用，则其返回类型中必须存在IO。

但是，在Haskell中隐式使用的函数存在，而其类型签名并没有考虑到在某种意义上的副作用。也就是说，这个函数复制一些数据并将其给您两个版本。在底层，这可以通过在内存中复制数据或“虚拟地”增加需要稍后偿还的债务来实现。

设计更严格的类型系统（纯“线性”类型）的语言是可能的，这些类型系统不允许复制功能。从这样一种语言的程序员的角度来看，Haskell看起来有点不纯。

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

在这个领域有很多研究，如果你搜索足够的话，你会找到一些不需要垃圾回收的纯线性代码示例。你会发现各种类型系统可以向编译器发出信号，告诉编译器可能使用哪些内存，从而消除一些GC。

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

将其与Forth(或其他基于堆栈的语言)进行比较，后者具有明确的DUP操作，可以清楚地显示何时发生了复制。

另一种(更抽象的)思考方式是注意到Haskell是从简单类型的lambda演算构建起来的，该演算基于笛卡尔闭范畴理论，并且这样的范畴配备了一个对角函数diag :: X -> (X, X)。基于另一类范畴的语言可能没有这样的函数。

但总的来说，纯线性编程过于困难，无法实用，所以我们只能使用GC。

- sigfpe

3

自从我写下这个答案以来，Rust编程语言的受欢迎程度大大提高。因此，值得一提的是，Rust使用类似线性的类型系统来控制对内存的访问，如果你想看到我提到的思想在实践中的应用，那么了解一下Rust是值得的。 - sigfpe

15

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

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

- ehird

2

它们从不改变先前的值：您可以查看http://www.haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011/Takano，这是关于一种实验性的GHC扩展，它重用内存。 - gfour

11

如果一个语言（任何语言）允许您动态分配对象，则有三种实用的处理内存管理的方式：

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

唯一的其他选择是永远不回收动态分配的存储。这对于执行小计算的小程序以外的实际解决方案不可行。

将此应用于Haskell，该语言没有1的限制，并且没有手动释放操作，如2所述。因此，为了用于非平凡的事情，Haskell实现需要包括垃圾回收器。

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

您可能是指纯函数式语言。

答案是需要在幕后使用GC来回收该语言必须创建的堆对象。例如，

纯函数需要创建堆对象，因为在某些情况下它必须返回它们。这意味着它们不能分配在堆栈上。
事实上可以存在循环（例如由let rec导致），这意味着引用计数方法对堆对象不起作用。

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

我正在寻找如果没有GC将会发生泄漏的示例代码。

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

- Stephen C

2

你为什么认为你的选项列表是详尽无遗的？Objective C中的ARC、MLKit和DDC中的区域推断以及Mercury中的编译时垃圾回收 - 它们都不适合这个列表。 - Dee Mon

@DeeMon - 它们都属于这些类别之一。如果你认为它们不属于任何一个类别，那是因为你把类别的边界划分得太严格了。当我说“某种形式的垃圾回收”时，我指的是任何一种自动回收存储空间的机制。 - Stephen C

1

C++11 使用智能指针。基本上它采用引用计数。它是确定性和自动的。我很想看到一个实现 Haskell 使用这种方法。 - intrepidis

2

@ChrisNash - 1) 这样做行不通。如果存在循环引用，基于引用计数的回收会泄漏数据...除非您可以依赖应用程序代码来打破这些循环。2) 众所周知（对于研究这些事情的人来说），与现代（真正的）垃圾收集器相比，引用计数的性能表现较差。 - Stephen C

@DeeMon - 此外，可以看看Reinerp的回答，了解为什么在Haskell中使用区域推断不太实际。 - Stephen C

8

如果您拥有足够的内存，则不需要垃圾收集器。但实际上，我们没有无限的内存，因此需要一些方法来回收不再需要的内存。在像C这样的非纯语言中，您可以显式地声明您已完成了某些内存以释放它 - 但这是一种变异操作（您刚刚释放的内存不再安全可读），因此您不能在纯语言中使用此方法。因此，要么静态分析可以释放内存的位置（在一般情况下可能不可能），要么像漏斗一样泄漏内存（直到用尽为止），或者使用垃圾收集器。

- bdonlan

这解答了为什么通常情况下不需要垃圾回收，但我更感兴趣的是 Haskell。 - Pubby

11

如果在一般情况下理论上不需要垃圾回收，那么显然对于Haskell来说，它也是理论上不需要的。 - ehird

@ehird 我的意思是必要的，我想我的拼写检查器把意思搞反了。 - Pubby

1

Ehird 的评论仍然适用 :-) - Paul R

2

在纯函数式编程语言中，垃圾回收（GC）是必不可少的。为什么呢？因为操作alloc和free是不纯的！另一个原因是，不可变递归数据结构需要GC才能存在，因为反向链接会创建深奥且难以维护的结构，超出人类思维范畴。当然，反向链接是一种福音，因为使用它的结构的复制非常便宜。

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

编辑：我忘了。在没有GC的情况下，惰性求值是地狱。不相信我吗？只需在例如C++中尝试一下没有GC的情况。你会看到...事情

- dev1223

“没有垃圾回收机制，懒惰编程简直是地狱。” 你能解释一下为什么吗？我在考虑 Rust 编程语言，在那里似乎有很多懒惰编程，但绝对没有垃圾回收机制。 - user8866053

1

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

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

- gfour

1

在某些情况下，静态分析可以将释放某些数据的代码插入到这些thunk中，在thunk被评估后进行解除分配。解除分配将在运行时发生，但不是GC。这类似于C++中引用计数智能指针的概念。对象生命周期的推理发生在运行时，但不使用GC。 - Dee Mon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rp123 · Accepted Answer

正如其他人已经指出的那样，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]必须保留在内存中，直到用户输入“清除”为止；因此，这个列表的生命周期需要动态确定，这就是动态内存管理的必要性所在。

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

然而...

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

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

我们希望编译器能够检测到当 x2 安全释放时（而不是等待垃圾回收器释放 x2），当 f 返回时。实质上，我们要求编译器执行逃逸分析，在可能的情况下将堆上的分配转换为栈上的分配。

这并不是一个过分苛求的要求：jhc Haskell 编译器可以做到这一点，尽管 GHC 不能。Simon Marlow 表示，GHC 的分代垃圾收集器使得逃逸分析大部分都是不必要的。

实际上，jhc 使用了一种称为区域推断的复杂逃逸分析形式。考虑以下例子。

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和Simon Peyton Jones的评论）。例如，请考虑：

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

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

在1990年代和2000年代初，对于严格函数语言ML进行了广泛的区域推断工作。Mads Tofte、Lars Birkedal、Martin Elsman、Niels Hallenberg在他们的区域推断工作中写了一篇相当易读的retrospective，其中大部分被整合到了MLKit compiler中。他们尝试了纯基于区域的内存管理（即没有垃圾收集器），以及混合的基于区域的/垃圾收集的内存管理，并报告说他们的测试程序运行速度比纯垃圾收集版本快了“10倍到4倍不等”。