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

Question

在纯函数式语言中,数据是不可变的.通过引用计数,创建引用周期需要更改已创建的数据.似乎纯函数式语言可以使用引用计数而不必担心循环的可能性.我是对的？如果是这样,他们为什么不呢？

我知道在许多情况下引用计数比GC慢,但至少它减少了暂停时间.如果暂停时间不好,可以选择使用引用计数.

Answer 1

相对于Java和C#等其他托管语言,纯粹的函数式语言就像疯了一样分配.他们还分配不同大小的对象.已知最快的分配策略是从连续的可用空间(有时称为"托儿所")进行分配,并保留硬件寄存器以指向下一个可用空闲空间.堆中的分配变得与堆栈中的分配一样快.

引用计数从根本上与此分配策略不兼容.引用计数将对象放在空闲列表中并再次取消它们.在创建新对象时,引用计数也需要大量的开销来更新引用计数(如上所述,纯函数式语言就像疯了一样).

在这样的情况下,引用计数往往表现得非常好:

• 几乎所有堆内存都用于保存活动对象.
• 分配和指针分配相对于其他操作来说并不常见.
• 可以在另一个处理器或计算机上管理引用.

要了解当今最好的高性能计数系统如何工作,请查看David Bacon和Erez Petrank的工作.

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

不需要突变.

Answer 3

我想有几件事.

• 有有周期:"让REC"在许多语言中也允许创建"循环"结构.除此之外,不变性通常意味着没有周期,但这违反了规则.
• 列表中的引用计数很糟糕:我不知道引用计数集合适用于您经常在FP中找到的长单链表结构(例如,缓慢,需要确保尾递归,...)
• 其他策略也有好处:正如您所提到的,其他GC策略通常对内存局部性更好

(曾几何时,我想我可能真的'知道'这个,但现在我正在努力记住/推测,所以不要把它视为任何权威.)

Answer 4

考虑一下这个寓言,讲述了Lisp机器的发明者David Moon:

有一天,一名学生来到Moon并说道:"我理解如何建立一个更好的垃圾收集器.我们必须保留对每个缺点的指针的引用计数."

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

"有一天,一个学生来到Moon说:'我明白如何制作一个更好的垃圾收集器......

Answer 5

我是对的？

不完全的.您可以使用纯函数式编程创建循环数据结构,只需同时定义相互递归的值即可.例如,在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}