Garbage Collection for Reversible Functional Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-06-20

AUTHORS

Torben Ægidius Mogensen

ABSTRACT

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

PAGES

79-94

Book

TITLE

Reversible Computation

ISBN

978-3-319-20859-6
978-3-319-20860-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-20860-2_5

DOI

http://dx.doi.org/10.1007/978-3-319-20860-2_5

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "DIKU, University of Copenhagen, Universitetsparken 5, DK-2100, Copenhagen O, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, University of Copenhagen, Universitetsparken 5, DK-2100, Copenhagen O, 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"
      }
    ], 
    "datePublished": "2015-06-20", 
    "datePublishedReg": "2015-06-20", 
    "description": "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.", 
    "editor": [
      {
        "familyName": "Krivine", 
        "givenName": "Jean", 
        "type": "Person"
      }, 
      {
        "familyName": "Stefani", 
        "givenName": "Jean-Bernard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-20860-2_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-20859-6", 
        "978-3-319-20860-2"
      ], 
      "name": "Reversible Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "functional language", 
      "pattern matching", 
      "reference counts", 
      "new nodes", 
      "reversible languages", 
      "language", 
      "programming language", 
      "matching", 
      "data construction", 
      "copying", 
      "equality testing", 
      "deep comparison", 
      "sharing", 
      "nodes", 
      "count 1", 
      "root node", 
      "unshared data", 
      "programmers", 
      "constructor applications", 
      "maximal sharing", 
      "entire heap", 
      "heap", 
      "identical nodes", 
      "allocation failure", 
      "good results", 
      "disjoint segments", 
      "garbage collection", 
      "program", 
      "forward", 
      "construction", 
      "reference", 
      "testing", 
      "trees", 
      "previous paper", 
      "reversible treatment", 
      "treatment", 
      "counts", 
      "limitations", 
      "constructors", 
      "variant patterns", 
      "patterns", 
      "manipulation", 
      "data", 
      "distinct patterns", 
      "burden", 
      "applications", 
      "pointers", 
      "avoids", 
      "search", 
      "small segment", 
      "segments", 
      "low probability", 
      "probability", 
      "failure", 
      "collection", 
      "linearity", 
      "variables", 
      "values", 
      "comparison", 
      "structure", 
      "argument", 
      "symmetry", 
      "results", 
      "reversible functional language", 
      "use symmetric pattern matching", 
      "symmetric pattern matching", 
      "deep copying", 
      "paper", 
      "sharing of structures", 
      "reference count 1", 
      "arbitrary reference count"
    ], 
    "name": "Garbage Collection for Reversible Functional Languages", 
    "pagination": "79-94", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004134457"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-20860-2_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-20860-2_5", 
      "https://app.dimensions.ai/details/publication/pub.1004134457"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_145.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-20860-2_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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/978-3-319-20860-2_5'

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/978-3-319-20860-2_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-20860-2_5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-20860-2_5'


 

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

136 TRIPLES      23 PREDICATES      96 URIs      89 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-20860-2_5 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nbe55cd76bf0f47bb88e6accf5b1de986
4 schema:datePublished 2015-06-20
5 schema:datePublishedReg 2015-06-20
6 schema:description 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.
7 schema:editor N2aaa4d85cbbb4cae98313613352480cd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N413dfe33bec84a5c92a438af9611beb5
12 schema:keywords allocation failure
13 applications
14 arbitrary reference count
15 argument
16 avoids
17 burden
18 collection
19 comparison
20 construction
21 constructor applications
22 constructors
23 copying
24 count 1
25 counts
26 data
27 data construction
28 deep comparison
29 deep copying
30 disjoint segments
31 distinct patterns
32 entire heap
33 equality testing
34 failure
35 forward
36 functional language
37 garbage collection
38 good results
39 heap
40 identical nodes
41 language
42 limitations
43 linearity
44 low probability
45 manipulation
46 matching
47 maximal sharing
48 new nodes
49 nodes
50 paper
51 pattern matching
52 patterns
53 pointers
54 previous paper
55 probability
56 program
57 programmers
58 programming language
59 reference
60 reference count 1
61 reference counts
62 results
63 reversible functional language
64 reversible languages
65 reversible treatment
66 root node
67 search
68 segments
69 sharing
70 sharing of structures
71 small segment
72 structure
73 symmetric pattern matching
74 symmetry
75 testing
76 treatment
77 trees
78 unshared data
79 use symmetric pattern matching
80 values
81 variables
82 variant patterns
83 schema:name Garbage Collection for Reversible Functional Languages
84 schema:pagination 79-94
85 schema:productId N2774b580b3e04fbeba84185f41c1f7cf
86 N6b4e1959a63e45b1ba69cf5d0cf6b45e
87 schema:publisher N9f5c7d033d3c44e6bde292dfe21f2e8e
88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004134457
89 https://doi.org/10.1007/978-3-319-20860-2_5
90 schema:sdDatePublished 2021-11-01T18:47
91 schema:sdLicense https://scigraph.springernature.com/explorer/license/
92 schema:sdPublisher N91c1b58470f64b8799e8dba7991c8756
93 schema:url https://doi.org/10.1007/978-3-319-20860-2_5
94 sgo:license sg:explorer/license/
95 sgo:sdDataset chapters
96 rdf:type schema:Chapter
97 N1f845e3c9d7f492e9b74b7890cbbad9a rdf:first N3f02c0521eb0470d9412956f2e2e1f98
98 rdf:rest rdf:nil
99 N2774b580b3e04fbeba84185f41c1f7cf schema:name dimensions_id
100 schema:value pub.1004134457
101 rdf:type schema:PropertyValue
102 N2aaa4d85cbbb4cae98313613352480cd rdf:first N3166bceeb5f542ff9e24df5a278084b3
103 rdf:rest N1f845e3c9d7f492e9b74b7890cbbad9a
104 N3166bceeb5f542ff9e24df5a278084b3 schema:familyName Krivine
105 schema:givenName Jean
106 rdf:type schema:Person
107 N3f02c0521eb0470d9412956f2e2e1f98 schema:familyName Stefani
108 schema:givenName Jean-Bernard
109 rdf:type schema:Person
110 N413dfe33bec84a5c92a438af9611beb5 schema:isbn 978-3-319-20859-6
111 978-3-319-20860-2
112 schema:name Reversible Computation
113 rdf:type schema:Book
114 N6b4e1959a63e45b1ba69cf5d0cf6b45e schema:name doi
115 schema:value 10.1007/978-3-319-20860-2_5
116 rdf:type schema:PropertyValue
117 N91c1b58470f64b8799e8dba7991c8756 schema:name Springer Nature - SN SciGraph project
118 rdf:type schema:Organization
119 N9f5c7d033d3c44e6bde292dfe21f2e8e schema:name Springer Nature
120 rdf:type schema:Organisation
121 Nbe55cd76bf0f47bb88e6accf5b1de986 rdf:first sg:person.016655503425.67
122 rdf:rest rdf:nil
123 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
124 schema:name Information and Computing Sciences
125 rdf:type schema:DefinedTerm
126 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
127 schema:name Data Format
128 rdf:type schema:DefinedTerm
129 sg:person.016655503425.67 schema:affiliation grid-institutes:grid.5254.6
130 schema:familyName Mogensen
131 schema:givenName Torben Ægidius
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
133 rdf:type schema:Person
134 grid-institutes:grid.5254.6 schema:alternateName DIKU, University of Copenhagen, Universitetsparken 5, DK-2100, Copenhagen O, Denmark
135 schema:name DIKU, University of Copenhagen, Universitetsparken 5, DK-2100, Copenhagen O, Denmark
136 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...