# Reversible Garbage Collection for Reversible Functional Languages

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2018-07

AUTHORS ABSTRACT

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. More... »

PAGES

203-232

### References to SciGraph publications

• 2015. Garbage Collection for Reversible Functional Languages in REVERSIBLE COMPUTATION
• 2012. Partial Evaluation of Janus Part 2: Assertions and Procedures in PERSPECTIVES OF SYSTEMS INFORMATICS
• 1998. “Balls into Bins” — A Simple and Tight Analysis in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
• 2014. Reference Counting for Reversible Languages in REVERSIBLE COMPUTATION
• 2005-06-10. NREVERSAL of fortune — The thermodynamics of garbage collection in MEMORY MANAGEMENT
• ### Journal

TITLE

New Generation Computing

ISSUE

3

VOLUME

36

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00354-018-0037-3

DOI

http://dx.doi.org/10.1007/s00354-018-0037-3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1105977560

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

``````[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1109",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Neurosciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Medical and Health Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "University of Copenhagen",
"id": "https://www.grid.ac/institutes/grid.5254.6",
"name": [
"DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark"
],
"type": "Organization"
},
"familyName": "Mogensen",
"givenName": "Torben \u00c6gidius",
"id": "sg:person.016655503425.67",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-319-20860-2_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004134457",
"https://doi.org/10.1007/978-3-319-20860-2_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-29709-0_25",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011121976",
"https://doi.org/10.1007/978-3-642-29709-0_25"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/368892.368907",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020648049"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0017210",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030791058",
"https://doi.org/10.1007/bfb0017210"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0017210",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030791058",
"https://doi.org/10.1007/bfb0017210"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jalgor.2003.12.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034279703"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-49543-6_13",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038366427",
"https://doi.org/10.1007/3-540-49543-6_13"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/365628.365655",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045610264"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-08494-7_7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048471805",
"https://doi.org/10.1007/978-3-319-08494-7_7"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/secon.1991.147887",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1086349214"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/infcom.2001.916641",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095771337"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/9780470148778",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1098661414"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/9780470148778",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1098661414"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/9780470148778",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1098661414"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-07",
"datePublishedReg": "2018-07-01",
"description": "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.",
"genre": "research_article",
"id": "sg:pub.10.1007/s00354-018-0037-3",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1053619",
"issn": [
"0288-3635",
"1882-7055"
],
"name": "New Generation Computing",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"name": "Reversible Garbage Collection for Reversible Functional Languages",
"pagination": "203-232",
"productId": [
{
"type": "PropertyValue",
"value": [
"8748879b04f585dc987e2a319028f4876ffe931c8dcb2d9530a71de572e090ca"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00354-018-0037-3"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1105977560"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00354-018-0037-3",
"https://app.dimensions.ai/details/publication/pub.1105977560"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T10:18",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000348_0000000348/records_54313_00000001.jsonl",
"type": "ScholarlyArticle",
}
]``````

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

`curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0037-3'`

N-Triples is a line-based linked data format ideal for batch operations.

`curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0037-3'`

`curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0037-3'`

RDF/XML is a standard XML format for linked data.

`curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0037-3'`

This table displays all metadata directly associated to this object as RDF triples.

99 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1109
3 schema:author N4cf04e83085744159b069f25c5b0cce7
4 schema:citation sg:pub.10.1007/3-540-49543-6_13
5 sg:pub.10.1007/978-3-319-08494-7_7
6 sg:pub.10.1007/978-3-319-20860-2_5
7 sg:pub.10.1007/978-3-642-29709-0_25
8 sg:pub.10.1007/bfb0017210
9 https://doi.org/10.1002/9780470148778
10 https://doi.org/10.1016/j.jalgor.2003.12.002
11 https://doi.org/10.1109/infcom.2001.916641
12 https://doi.org/10.1109/secon.1991.147887
13 https://doi.org/10.1145/365628.365655
14 https://doi.org/10.1145/368892.368907
15 schema:datePublished 2018-07
16 schema:datePublishedReg 2018-07-01
17 schema:description 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.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf Nb848498763b94178ac7f9fe0241bf2f4
22 Nc3fc6571cb964a29b051df2b06d37e01
23 sg:journal.1053619
24 schema:name Reversible Garbage Collection for Reversible Functional Languages
25 schema:pagination 203-232
26 schema:productId N5b0f49367807468e90a3642a804c0282
27 Nc2ffa64073014887b78f24dbfab12e1e
28 Ncf060377fcde4d8d94e9be455e51f9e0
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105977560
30 https://doi.org/10.1007/s00354-018-0037-3
31 schema:sdDatePublished 2019-04-11T10:18
33 schema:sdPublisher Nb54f93ea219b42e3bd183c4f6f9bb3d7
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N4cf04e83085744159b069f25c5b0cce7 rdf:first sg:person.016655503425.67
39 rdf:rest rdf:nil
40 N5b0f49367807468e90a3642a804c0282 schema:name dimensions_id
41 schema:value pub.1105977560
42 rdf:type schema:PropertyValue
43 Nb54f93ea219b42e3bd183c4f6f9bb3d7 schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
46 rdf:type schema:PublicationVolume
47 Nc2ffa64073014887b78f24dbfab12e1e schema:name doi
48 schema:value 10.1007/s00354-018-0037-3
49 rdf:type schema:PropertyValue
50 Nc3fc6571cb964a29b051df2b06d37e01 schema:issueNumber 3
51 rdf:type schema:PublicationIssue
53 schema:value 8748879b04f585dc987e2a319028f4876ffe931c8dcb2d9530a71de572e090ca
54 rdf:type schema:PropertyValue
55 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
56 schema:name Medical and Health Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:1109 schema:inDefinedTermSet anzsrc-for:
59 schema:name Neurosciences
60 rdf:type schema:DefinedTerm
61 sg:journal.1053619 schema:issn 0288-3635
62 1882-7055
63 schema:name New Generation Computing
64 rdf:type schema:Periodical
65 sg:person.016655503425.67 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
66 schema:familyName Mogensen
67 schema:givenName Torben Ægidius
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
69 rdf:type schema:Person
70 sg:pub.10.1007/3-540-49543-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038366427
71 https://doi.org/10.1007/3-540-49543-6_13
72 rdf:type schema:CreativeWork
73 sg:pub.10.1007/978-3-319-08494-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048471805
74 https://doi.org/10.1007/978-3-319-08494-7_7
75 rdf:type schema:CreativeWork
76 sg:pub.10.1007/978-3-319-20860-2_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004134457
77 https://doi.org/10.1007/978-3-319-20860-2_5
78 rdf:type schema:CreativeWork
79 sg:pub.10.1007/978-3-642-29709-0_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011121976
80 https://doi.org/10.1007/978-3-642-29709-0_25
81 rdf:type schema:CreativeWork
82 sg:pub.10.1007/bfb0017210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791058
83 https://doi.org/10.1007/bfb0017210
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1002/9780470148778 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098661414
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1016/j.jalgor.2003.12.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034279703
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1109/infcom.2001.916641 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095771337
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1109/secon.1991.147887 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086349214
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/365628.365655 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045610264
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1145/368892.368907 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020648049
96 rdf:type schema:CreativeWork
97 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
98 schema:name DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen, Denmark
99 rdf:type schema:Organization