你为什么不纯粹的功能语言使用的参考数？

StackOverflow https://stackoverflow.com/questions/791437

题

在纯粹的功能性的语言，数据是不可改变的。参照数，创造一个参考周期需要改变已经创建的数据。这似乎是纯粹的功能的语言可以使用的参考计数，而不用担心的可能性循环。我是对的？如果是这样，他们为什么不?

我的理解是，参考计数低于GC在许多情况下，但至少它减少了暂停时间。它将是不错的选择使用基准数的情况下暂停时间都是不好的。

有帮助吗？

解决方案

您的问题是基于一个错误的假设。这是完全可能有循环引用和不可改变的数据。考虑其使用不可改变的数据以创建一个循环引用下面的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

不需要的突变。

其他提示

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

引用计数从根本上与这种分配策略不兼容。引用计数将对象放入空闲列表并再次将其删除。当创建新对象时，引用计数还需要大量的开销来更新引用计数（如上所述，纯函数式语言确实很疯狂）。

引用计数在以下情况下往往表现得非常好：

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

要了解当今最好的高性能引用计数系统如何工作，请查阅 大卫·培根 和 埃雷兹·佩特兰克.

我认为有几件事。

  • 那里 是 周期:许多语言中的“let rec”确实允许创建“循环”结构。除此之外，不变性通常意味着没有循环，但这打破了规则。
  • 列表中的引用计数很糟糕:我不知道引用计数集合是否适用于例如您在 FP 中经常看到的长单链表结构（例如慢，需要确保尾递归，...）
  • 其他策略也有好处:正如您所提到的，其他 GC 策略通常仍然更适合内存局部性

（曾几何时，我想我可能真的“知道”这一点，但现在我正在努力记住/推测，所以不要将此视为任何权威。）

考虑 这个寓言 告诉关于 大卫月, 一的发明者 口齿不清的机器:

有一天一个学生来到月亮说："我了解如何做一个更好的垃圾收集器。我们必须保持一个参考数为指针每一个缺点"。

月亮耐心地告诉学生的下列故事：

"有一天，一个学生来到月亮说：'我了解如何做一个更好的垃圾回收...

  

Am进行正确？

不太。你可以简单地在同一时间定义相互递归值创建使用纯粹的函数式编程循环数据结构。例如，在OCaml的：

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

然而，可以定义语言，使得它不可能通过设计创建的环状结构。结果被称为单向堆和它的主要优点是，垃圾收集可以是如参考计数一样简单。

  

如果是这样，为什么不？

某些语言不禁止周期和使用引用计数。 Erlang和数学是实例。

例如，在数学当引用的值你对它如此突变原本并不突变拷贝的深层副本：

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}

引用计数法是要比GC慢，因为它是不利于CPU。和GC大部分时间可以等待的空闲时间，也GC可能是并发的（在另一个线程）。所以，这就是问题所在 - GC至少是邪恶和大量的尝试表明，

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top