Garbage Collection for Reversible Functional Languages
Garbage Collection for Reversible Functional Languages
复制标题
可逆函数式语言的垃圾收集
DOI：
10.1007/978-3-319-20860-2_5
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Torben Æ. Mogensen
中科院分区：
文献类型：
--
作者：
Torben Æ. Mogensen
可逆语言是所有程序都可以向前和向后运行的编程语言。已经提出了使用对称模式匹配和数据构造的可逆函数式语言。为了可逆，这些语言需要线性：每个变量必须只使用一次，所以没有引用被复制，所有引用都只跟随一次。值的复制必须使用深度复制。类似地，相等性测试需要对树进行深度比较。之前的一篇论文描述了引用计数的可逆处理，它允许在不进行深度复制的情况下共享结构，但也有局限性。将构造函数应用于参数会创建一个引用计数为1的新节点，因此模式匹配会对称地限制在引用计数为1的节点上。引入了一种不改变根节点引用计数的变体模式，以允许对共享数据进行操作。然而，共享和非共享数据有两种不同的模式，这给程序员增加了负担。我们观察到，如果我们也允许构造函数应用程序返回具有任意引用计数的节点，我们就可以允许对具有任意引用计数的节点进行模式匹配。我们通过使用最大共享来做到这一点：如果新构建的节点与现有节点相同，则我们返回指向现有节点的指针（增加其引用计数），而不是分配引用计数为1的新节点。为了避免在整个堆中搜索相同的节点，我们使用哈希计算将搜索限制在堆的一小部分。我们估计这个段需要多大，才能在堆不到一半满的情况下提供非常低的分配失败概率。实验上，我们发现重叠的部分比不相交的部分给出了更好的结果。
Reversible languages are programming languages where all programs can run both forwards and backwards. Reversible functional languages have been proposed that use symmetric pattern matching and data construction. To be reversible, these languages require linearity: Every variable must be used exactly once, so no references are copied and all references are followed exactly once. Copying of values must use deep copying. Similarly, equality testing requires deep comparison of trees.A previous paper describes reversible treatment of reference counts, which allows sharing of structures without deep copying, but there are limitations. Applying a constructor to arguments creates a new node with reference count 1, so pattern matching is by symmetry restricted to nodes with reference count 1. A variant pattern that does not change the reference count of the root node is introduced to allow manipulation of shared data. Having two distinct patterns for shared and unshared data, however, adds a burden on the programmer.We observe that we can allow pattern matching on nodes with arbitrary reference count if we also allow constructor application to return nodes with arbitrary reference counts. We do this by using maximal sharing: If a newly constructed node is identical to an already existing node, we return a pointer to the existing node (increasing its reference count) instead of allocating a new node with reference count 1.To avoid searching the entire heap for an identical node, we use hash-consing to restrict the search to a small segment of the heap. We estimate how large this segment needs to be to give a very low probability of allocation failure when the heap is less than half full. Experimentally, we find that overlapping segments gives dramatically better results than disjoint segments.