Garbage collection for reversible functional languages
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Garbage collection for reversible functional languages. / Mogensen, Torben Ægidius.
Reversible computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings. ed. / Jean Krivine; Jean-Bernard Stefani. Springer, 2015. p. 79-94 (Lecture notes in computer science, Vol. 9138).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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 -
ID: 149085263