Pub*_*bby 113 garbage-collection haskell
我很好奇为什么Haskell实现使用GC.
我想不出一个纯语言需要GC的情况.它只是减少复制的优化,还是实际上是必要的？
我正在寻找在GC不存在时会泄漏的示例代码.
rei*_*erp 215
正如其他人已经指出的那样,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).本质上,我们要求编译器执行转义分析,以便尽可能将分配转换为垃圾收集堆到堆栈上的分配.
这要求不是太不合理: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区域.
虽然如上所述,区域推理在某些情况下是有帮助的,但似乎很难有效地与懒惰评估相协调(参见Edward Kmett和Simon Peyton Jones的评论).例如,考虑一下
f :: Integer -> Integer
f n = product [1..n]
有人可能会想要[1..n]在堆栈上分配列表并在f返回后释放它,但这将是灾难性的:它会f从使用O(1)内存(在垃圾收集下)变为O(n)内存.
在20世纪90年代和21世纪初,在严格的功能语言ML的区域推断方面进行了大量的工作.Mads Tofte,Lars Birkedal,Martin Elsman,Niels Hallenberg撰写了一篇关于区域推理工作的可读性回顾展,其中很多都集成到了MLKit编译器中.他们尝试了纯粹的基于区域的内存管理(即没有垃圾收集器)以及基于混合区域/垃圾收集的内存管理,并报告说他们的测试程序比纯垃圾运行"快10倍,慢4倍" - 收集版本.
aug*_*tss 26
让我们举一个小例子.鉴于这种
f (x, y)
你需要(x, y)在调用之前在某处分配对f.你什么时候能解除那对？你不知道.它在f返回时不能被释放,因为f可能将该对放在数据结构中(例如f p = [p]),因此该对的生命周期可能必须长于返回f.现在,假设这对被列入一个列表中,那么将该列表分开的人可以取消分配该对吗？不,因为这对可能是共享的(例如let p = (x, y) in (f p, p)).所以很难判断这对货币何时可以解除分配.
对于Haskell中的几乎所有分配都是如此.也就是说,有可能进行分析(区域分析),给出生命周期的上限.这在严格的语言中工作得相当好,但在懒惰的语言中效果较差(在实现中,懒惰的语言往往比严格的语言做更多的突变).
所以我想转过身来.为什么你认为Haskell不需要GC.您如何建议完成内存分配？
sig*_*fpe 16
你认为这与纯洁有关的直觉有一些道理.
Haskell被认为是纯粹的,部分原因是函数的副作用在类型签名中被考虑.因此,如果函数具有打印内容的副作用,则IO其返回类型中必须存在某个位置.
但是在Haskell中有一个隐式使用的函数,其类型签名没有考虑,在某种意义上,它是一个副作用.即复制某些数据并返回两个版本的函数.在引擎盖下,这可以通过复制内存中的数据来实现,或通过增加需要稍后偿还的债务来"虚拟".
设计具有更严格的类型系统(纯粹的"线性"系统)的语言是不可能的,这些系统不允许复制功能.从这种语言的程序员的角度来看,Haskell看起来有点不纯洁.
实际上,Clean是Haskell的一个亲戚,它具有线性(更严格地说:唯一)类型,并且可以让人知道禁止复制的内容.但Clean仍允许复制"非唯一"类型.
这个领域有很多研究,如果你足够Google,你会发现纯线性代码的例子,不需要垃圾回收.您可以找到各种类型的系统,它们可以向编译器发出可能使用的内存信号,从而允许编译器消除某些GC.
有一种感觉,量子算法也是纯线性的.每个操作都是可逆的,因此不能创建,复制或销毁任何数据.(它们在通常的数学意义上也是线性的.)
与Forth(或其他基于堆栈的语言)进行比较也很有意思,它们具有明确的DUP操作,可以在发生重复时明确.
另一种(更抽象的)思考方式是注意Haskell是由简单的类型化的lambda演算构建的,它基于笛卡尔闭合类别的理论,并且这些类别具有对角函数diag :: X -> (X, X).基于另一类别的语言可能没有这样的东西.
但总的来说,纯线性编程太难用了,所以我们选择GC.
ehi*_*ird 14
应用于Haskell的标准实现技术实际上需要GC比大多数其他语言更多,因为它们从不改变先前的值,而是基于先前的值创建新的修改值.由于这意味着程序不断分配和使用更多内存,因此随着时间的推移将丢弃大量值.
这就是GHC程序往往具有如此高的总分配数据(从千兆字节到太字节)的原因:它们不断分配内存,而且只有高效的GC才能在耗尽之前回收它.
Ste*_*n C 11
如果一种语言(任何语言)允许您动态分配对象,那么有三种实用的方法来处理内存管理:
该语言只允许您在堆栈上或启动时分配内存.但是这些限制严重限制了程序可以执行的计算类型.(在实践中.理论上,你可以通过在一个大数组中表示它们来模拟(比如说)Fortran中的动态数据结构.它是可怕的......并且与这个讨论无关.)
该语言可以提供明确的free或dispose机制.但这依赖于程序员才能做到正确.存储管理中的任何错误都可能导致内存泄漏......或者更糟.
语言(或更严格地说,语言实现)可以为动态分配的存储提供自动存储管理器; 即某种形式的垃圾收集器.
唯一的另一种选择是永远不会回收动态分配的存储.除了执行小型计算的小程序之外,这不是一个实用的解决方案.
将此应用于Haskell,该语言没有1.的限制,并且没有按照2的手动解除分配操作.因此,为了可用于非平凡的事情,Haskell实现需要包含垃圾收集器.
我想不出一个纯语言需要GC的情况.
大概你的意思是一种纯粹的功能语言.
答案是需要一个GC来回收语言必须创建的堆对象.例如.
纯函数需要创建堆对象,因为在某些情况下它必须返回它们.这意味着它们不能在堆栈上分配.
可能存在循环(let rec例如由此产生)的事实意味着引用计数方法不适用于堆对象.
然后有函数闭包...它们也不能在堆栈上分配,因为它们的生命周期(通常)独立于创建它们的堆栈帧.
我正在寻找在GC不存在时会泄漏的示例代码.
几乎任何涉及闭包或图形数据结构的例子都会在这些条件下泄漏.
如果您有足够的内存,则永远不需要垃圾收集器.但是,实际上,我们没有无限的内存,所以我们需要一些方法来回收不再需要的内存.在像C这样的不纯语言中,你可以明确地声明你已经完成了一些内存来释放它 - 但这是一个变异操作(你刚刚释放的内存不再是安全的读取),所以你不能使用这种方法一种纯粹的语言.因此,它可以以某种方式静态分析您可以释放内存的位置(在一般情况下可能是不可能的),像筛子一样泄漏内存(在用完之前效果很好),或者使用GC.