TY - GEN

T1 - Garbage collection for reversible functional languages

AU - Mogensen, Torben Ægidius

N1 - Conference code: 7

PY - 2015

Y1 - 2015

N2 - Reversible languages are programming languages where all programs canrun both forwards and backwards. Reversible functional languages havebeen proposed that use symmetric pattern matching and dataconstruction. To be reversible, these languages require linearity:Every variable must be used exactly once, so no references are copiedand all references are followed exactly once. Copying of values mustuse deep copying. Similarly, equality testing requires deepcomparison of trees.A previous paper describes reversible treatment of reference counts,which allows sharing of structures without deep copying, but there arelimitations. Applying a constructor to arguments creates a new nodewith reference count 1, so pattern matching is by symmetry restrictedto nodes with reference count 1. A variant pattern that does notchange the reference count of the root node is introduced to allowmanipulation of shared data. Having two distinct patterns for sharedand unshared data, however, adds a burden on the programmer.We observe that we can allow pattern matching on nodes with arbitraryreference count if we also allow constructor application to returnnodes with arbitrary reference counts. We do this by using maximalsharing: If a newly constructed node is identical to an alreadyexisting node, we return a pointer to the existing node (increasingits reference count) instead of allocating a new node with referencecount 1.To avoid searching the entire heap for an identical node, we usehash-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 lowprobability of allocation failure when the heap is less than halffull. Experimentally, we find that overlapping segments givesdramatically better results than disjoint segments.

AB - Reversible languages are programming languages where all programs canrun both forwards and backwards. Reversible functional languages havebeen proposed that use symmetric pattern matching and dataconstruction. To be reversible, these languages require linearity:Every variable must be used exactly once, so no references are copiedand all references are followed exactly once. Copying of values mustuse deep copying. Similarly, equality testing requires deepcomparison of trees.A previous paper describes reversible treatment of reference counts,which allows sharing of structures without deep copying, but there arelimitations. Applying a constructor to arguments creates a new nodewith reference count 1, so pattern matching is by symmetry restrictedto nodes with reference count 1. A variant pattern that does notchange the reference count of the root node is introduced to allowmanipulation of shared data. Having two distinct patterns for sharedand unshared data, however, adds a burden on the programmer.We observe that we can allow pattern matching on nodes with arbitraryreference count if we also allow constructor application to returnnodes with arbitrary reference counts. We do this by using maximalsharing: If a newly constructed node is identical to an alreadyexisting node, we return a pointer to the existing node (increasingits reference count) instead of allocating a new node with referencecount 1.To avoid searching the entire heap for an identical node, we usehash-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 lowprobability of allocation failure when the heap is less than halffull. Experimentally, we find that overlapping segments givesdramatically better results than disjoint segments.

U2 - 10.1007/978-3-319-20860-2_5

DO - 10.1007/978-3-319-20860-2_5

M3 - Article in proceedings

SN - 978-3-319-20859-6

T3 - Lecture notes in computer science

SP - 79

EP - 94

BT - Reversible computation

A2 - Krivine, Jean

A2 - Stefani, Jean-Bernard

PB - Springer

Y2 - 16 July 2015 through 17 July 2015

ER -