为什么函数式编程语言需要垃圾回收？

Question

根据维基百科，从λ演算到组合逻辑的转换是微不足道的。串联式编程语言可以仅依赖堆栈进行内存分配。

那么，GHC为什么不将Haskell转换为串联式编程语言，如组合逻辑，然后简单地为所有内容使用堆栈分配呢？

这种转换是否可行，从而消除对Haskell和OCaml等语言的垃圾回收？这样做有哪些缺点？

- grasevski

---

可能是Does Haskell require a garbage collector?的重复问题。 - Luka Rahne

我认为如果没有类似堆的东西，实现Haskell的图重写语义会相当困难。 - Benjamin Hodgson

Answer 1

假设我有一个生成某个大小的链表的函数。大小是函数参数。

问题是：我在哪里为列表分配内存？我不能在函数的堆栈上分配它，因为在函数退出后它就无效了。而且我也不能在调用者的堆栈上分配它，因为在函数调用之前我不知道需要分配多少内存。所以我需要在堆上分配它。

我认为可能会有可用的具有手动堆管理的 RAII，但我看不出如何完全消除堆分配。

---

编辑

我无法在评论中表达所有想法，所以我在这里写下它们。

基于堆栈的分配语言并没有什么神奇之处。你仍然需要知道何时你的数据是相关的，并在不需要它们时将其删除。

想象一下你有一个单独的堆栈，你的函数可以控制它推入和弹出数据。首先，现在没有自动内存管理了，即函数终止后数据不会被自动释放。其次，如果你的函数分配了一些内存，以支持例如列表计算等操作，那么所有这些东西都会与要返回的列表混杂在一起。你没有机会释放未使用的内存（其他列表、树等），因为你只有推入和弹出操作。如果你有其他操作，那么堆和堆栈有什么区别呢？

多个堆栈怎么样？

你需要在某个地方分配它们，管理它们的增长并有时将它们取回。那些堆栈是你需要手动管理的单独结构。没有自动内存管理。

基于堆栈的语言还好，但是忘记了大量使用“从某处获取内存”和“将内存放回”的概念发明的算法，例如哈希映射、红黑树和链表。当然，我们可以在堆栈上分配所有这些结构体，但如果它们不再需要，我们无法释放它们的部分。

那么“平凡”的λ演算转换成图灵机呢？

当然，如果你的资源是无限的，那就很平凡。数学理论并没有阐明这种转换的时间和内存复杂度，它只证明了这两个模型是等价的，我们可以用图灵机说出λ演算所能表达的一切，反之亦然。但不能保证它可以在现实生活中的限制下工作。

- a.yekimov

---

我的理解是，串联语言（通常只使用堆栈）原则上可以通过弹出和推入堆栈来返回可变数量的数据，例如每个函数基本上都有定义“void foo(stack *s)”。 - grasevski

每个函数都可以升高它自己的堆栈，但不会影响调用者的堆栈。在调用任何函数之前，调用者需要知道需要为返回值分配多少内存。 - a.yekimov

那么基于栈的编程语言是如何工作的呢？我认为它是通过为函数调用和数据分别实现一个单独的栈来实现的，因此这个问题永远不会出现。即像我提供的 C 声明一样。 - grasevski

堆分配的存在并不意味着垃圾回收的存在。特别要注意的是，编程语言C具有堆分配，但没有垃圾回收器。因此，这个答案完全忽略了问题，问题并不是询问是否需要堆，而是询问是否（或为什么）需要垃圾回收。 - Holger

我只是指出，无论你使用什么语言，都需要管理好内存。垃圾回收机制确实非常方便。同时，我也指出，你不能像问题的提问者所建议的那样，仅仅翻译你的lambda表达式而不需要手动或自动地管理内存。 - a.yekimov

Answer 2

一个连接式编程语言和函数式编程语言一样有可能出现内存耗尽的情况。垃圾回收的基本挑战是释放那些未被使用或未知是否被使用的内存，特别是在源代码中没有明确的终止对象生命周期的地方。如果你只将一个函数式语言转换为只使用堆栈分配的连接式语言，那么你最终会溢出堆栈。多年来确实有各种努力减少垃圾回收的需求。其中一个有趣（但非常复杂）的尝试是 ML Kit 中使用的区域推断系统。不幸的是，这对于包括我在内的大多数程序员来说都太过复杂了。我相信自那以后还有其他人在开发这种系统，但我不知道目前的技术水平如何。重点是，一些非常复杂的编译器机制、谨慎的程序员纪律和特殊注释有时可以减少或消除对垃圾回收的需要；没有简单的转换方法可以解决这个问题。

- dfeuer