TY - JOUR

T1 - Reversible Garbage Collection for Reversible Functional Languages

AU - Mogensen, Torben Aegidius

PY - 2018/7

Y1 - 2018/7

N2 - Reversible functional languages have been proposed that use patterns symmetrically for matching and building data: A pattern used on the left-hand side of a function rule takes apart a data structure, and a pattern used on the right-hand side of a rule builds a data structure. When calling a function in reverse, the meaning of patterns are reversed, so patterns on the right-hand side take apart data and patterns on the left-hand side build data. If using a pattern to build data creates a node with exactly one reference, a node that is taken apart must by symmetry also have exactly one reference. This implies linearity: A node that is built or taken apart has exactly one incoming reference. A recursive function can take apart one data structure while building two or more new copies, allowing multiple uses of values, but the new copies will also have one reference each. Linearity makes garbage collection simple: Whenever a node is taken apart by pattern matching, it is freed. The cost is that multiple uses of a value require deep copies. The reason for the linearity restriction is the symmetry between constructing and deconstructing nodes: Since constructing a node creates exactly one reference to this node, the inverse can only be applied if the reference count is exactly one. We can overcome this limitation if constructing a node can return a node with multiple references. We achieve this through 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 one. This allows multiple references to nodes while retaining the symmetry of pattern matching and construction, and it allows values to be used multiple times without making deep copies. 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 low probability of allocation failure with acceptable utilisation and support this estimate with experiments. We sketch how a functional program can be translated to use the memory manager, and we test the memory manager both with artificial test programs and a hand-compiled functional program.

AB - Reversible functional languages have been proposed that use patterns symmetrically for matching and building data: A pattern used on the left-hand side of a function rule takes apart a data structure, and a pattern used on the right-hand side of a rule builds a data structure. When calling a function in reverse, the meaning of patterns are reversed, so patterns on the right-hand side take apart data and patterns on the left-hand side build data. If using a pattern to build data creates a node with exactly one reference, a node that is taken apart must by symmetry also have exactly one reference. This implies linearity: A node that is built or taken apart has exactly one incoming reference. A recursive function can take apart one data structure while building two or more new copies, allowing multiple uses of values, but the new copies will also have one reference each. Linearity makes garbage collection simple: Whenever a node is taken apart by pattern matching, it is freed. The cost is that multiple uses of a value require deep copies. The reason for the linearity restriction is the symmetry between constructing and deconstructing nodes: Since constructing a node creates exactly one reference to this node, the inverse can only be applied if the reference count is exactly one. We can overcome this limitation if constructing a node can return a node with multiple references. We achieve this through 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 one. This allows multiple references to nodes while retaining the symmetry of pattern matching and construction, and it allows values to be used multiple times without making deep copies. 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 low probability of allocation failure with acceptable utilisation and support this estimate with experiments. We sketch how a functional program can be translated to use the memory manager, and we test the memory manager both with artificial test programs and a hand-compiled functional program.

KW - Memory management

KW - Reference counting

KW - Maximal sharing

KW - Hashing

KW - Reversible programming languages

KW - Functional programming languages

U2 - 10.1007/s00354-018-0037-3

DO - 10.1007/s00354-018-0037-3

M3 - Journal article

VL - 36

SP - 203

EP - 232

JO - New Generation Computing

JF - New Generation Computing

SN - 0288-3635

IS - 3

ER -