为什么纯函数式语言不使用引用计数？

Question

在纯函数式语言中，数据是不可变的。使用引用计数时，创建一个引用循环需要更改已经创建的数据。看起来纯函数式语言可以使用引用计数而不必担心可能会出现循环引用。这是对的吗？如果是，为什么它们没有使用引用计数？

我知道在许多情况下，引用计数比GC慢，但至少它减少了暂停时间。在暂停时间较长的情况下，有选择地使用引用计数将是不错的选择。

- Zifre

---

引用计数实际上是一种垃圾回收算法，因此RC与GC之间没有任何意义。引用计数与标记清除或压缩收集器相比较才是更好的问题。 - Luke Quinane

正如Brian和JaredPar所说，循环结构可以在不使用可变性的情况下创建。事实上，我会说它们在Haskell中比其他任何语言更常见，这要归功于处理它们的便利性（懒惰编程的好处）。JaredPar的回答中已经添加了示例。 - ephemient

@Luke Quinane：当我说GC时，大多数人不会想到RC。通常认为GC是指类似于标记-清除的策略。 - Zifre

当你说“垃圾回收”时，大多数人会想到来收集他们垃圾的卡车。我认为从人群普及度的角度来看并不是与主题相关的论点。 - chaos

@chaos，毫无疑问，相关人口群体是非常重要的。 - Nicholas Wilson

Answer 1

相对于Java和C＃等其他托管语言，纯函数式语言的分配极其频繁，它们还会分配不同大小的对象。已知最快的分配策略是从连续的空闲空间（有时称为“幼儿园”）中进行分配，并保留一个硬件寄存器以指向下一个可用的空闲空间。从堆中进行分配的速度就像从堆栈中进行分配一样快。

引用计数基本上与这种分配策略不兼容。引用计数将对象放在自由列表上并将其移除。引用计数还需要大量的开销来更新引用计数，因为新对象被创建时（如上所述，纯函数式语言会频繁地创建对象）需要这样做。

引用计数在以下情况下往往效果很好：

- 几乎所有堆内存都用于保存活动对象。 - 相对于其他操作，分配和指针赋值是不频繁的。 - 引用可以在另一个处理器或计算机上管理。

要了解当今最佳高性能引用计数系统的工作原理，请查看David Bacon和Erez Petrank的工作。

- Norman Ramsey

---

实际上，可以将托管引用计数器与保育室相结合：http://cs.anu.edu.au/~Steve.Blackburn/pubs/papers/urc-oopsla-2003.pdf - Luke Quinane

混合收集器绝对是未来的趋势，如果有人能够实现这一点，那一定是 Steve Blackburn（尤其是在有 Perry Cheng 的帮助下）。话虽如此，我不确定是否愿意将他们在 Java 上的结果推广到现代的函数式语言。Java 对内存系统的压力并不是很大。 - Norman Ramsey

Answer 2

您的问题基于错误的假设。具有循环引用和不可变数据是完全可能的。请看下面这个使用不可变数据创建循环引用的C#示例。

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

这种技巧在很多函数式语言中都能实现，因此任何集合机制都必须处理可能存在的循环引用。我并不是说循环引用不能使用引用计数机制，只是必须处理好它。

由ephemient编辑

回应评论... 在Haskell中这很简单。

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

在SML中几乎不需要更多的努力。

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

无需进行变异。

- JaredPar

---

你的例子仍然依赖于修改已经创建的数据（尽管是在构造函数中）。我不知道这在任何纯函数式语言中是否可能。如果可能的话，你能否给出一个Haskell的简单例子？ - Zifre

你的例子仍然依赖于修改已经创建的数据（尽管是在构造函数中）。...这是错误的说法。在那个例子中仍然没有发生任何变异。 - Thomas Eding

数据持久性可以防止循环引用...你在Haskell中的例子是无限递归。只需将其反汇编，您就会看到...开始思考函数式编程，停止传播错误信息... - dev1223

@Zifre 可能在暗示的是，如果将不可变性与强初始化语义结合起来，那么对于尚未完全初始化的数据结构实例的引用是被禁止的，这将不允许循环引用。 - awdz9nld

实际上，当创建对象是产生循环引用的唯一方式时，引用计数就能够正常工作。对象只需要被创建为带有共享引用计数器。 - OCTAGRAM

Answer 3

我是正确的吗？

不完全正确。你可以使用纯函数式编程创建循环数据结构，只需同时定义相互递归的值即可。例如，在OCaml中：

let rec xs = 0::ys and ys = 1::xs

然而，设计成不可能创建循环结构的语言是有可能的。这种结果被称为单向堆，其主要优点在于垃圾收集可以像引用计数一样简单。

如果是这样，为什么其他编程语言没有这样做呢？

有些语言禁止使用循环结构并使用引用计数。例如Erlang和Mathematica。

例如，在Mathematica中，当您引用一个值时，会对其进行深拷贝，因此更改原始值不会更改副本：

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

- J D

---

+1 如果说“单向堆”。这是你需要在谷歌上搜索以了解更多关于这个主题的内容。 :) - pauldoo

Answer 4

我认为有几件事情需要注意。

• 存在循环引用：在许多语言中，“let rec”允许创建“循环”的结构。除此之外，不可变性通常意味着没有循环引用，但这会打破规则。
• 引用计数对于列表来说并不好：我不知道引用计数集合是否能够很好地处理函数式编程中经常遇到的长单向链表结构（例如慢速、需要确保尾递归等）。
• 其他策略具有优点：正如你所提到的，其他垃圾回收策略通常更适用于内存本地性。

（曾经我可能真的“知道”这些，但现在我正在试图回忆或推测，因此不要将其视为任何权威意见。）

- Brian

---

只要你懒惰地进行引用计数，使用列表时引用计数就能正常工作：当对象的引用计数归零时，它将进入空闲列表，但直到它离开空闲列表之前，你才会减少其指向的内容的引用计数。这样，每个操作都是常数时间（受最大对象大小限制，而不是最长列表长度的影响）。 - Norman Ramsey

let rec 是一个精确的地方，用于引入共享引用计数器。 - OCTAGRAM

@OCTAGRAM 你是指共享，像C++的std::shared_ptr，还是弱引用，像C++的std::weak_ptr？ - Max Barraclough

@MaxBarraclough 计数器在对象之间共享，而不仅仅是在引用之间共享。更像是TAggregatedObject将AddRef和Release重定向到其主对象。 - OCTAGRAM

Answer 5

考虑这个寓言，它是关于Lisp机器的发明家David Moon的故事:

一天，一名学生来找Moon并说：“我知道如何制作更好的垃圾收集器。我们必须保留对每个cons指针的引用计数。”

Moon耐心地告诉学生以下故事：

一天，一名学生来找Moon并说：“我知道如何制作更好的垃圾收集器...

- Crashworks

Answer 6

引用计数比垃圾回收慢得多，因为它对CPU不利。而垃圾回收大部分时间可以等待空闲时间，而且垃圾回收可以是并发的（在另一个线程上）。所以这就是问题所在——垃圾回收是最小的恶，很多尝试都表明了这一点。

- Mash