Reversible Garbage Collection for Reversible Functional Languages View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

Torben Ægidius Mogensen

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

    Author Affiliations

    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: 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/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", 
            "volumeNumber": "36"
          }
        ], 
        "name": "Reversible Garbage Collection for Reversible Functional Languages", 
        "pagination": "203-232", 
        "productId": [
          {
            "name": "readcube_id", 
            "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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", 
        "url": "https://link.springer.com/10.1007%2Fs00354-018-0037-3"
      }
    ]
     

    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/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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00354-018-0037-3 schema:about anzsrc-for:11
    2 anzsrc-for:1109
    3 schema:author Nae6ba5ca26ad472281312d7df30c57c5
    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 N48f0fd03631649bd9e811ab27cc06f5d
    22 Ne16d83e271c84e02b9322c6cef207571
    23 sg:journal.1053619
    24 schema:name Reversible Garbage Collection for Reversible Functional Languages
    25 schema:pagination 203-232
    26 schema:productId N129db3ab7c1945bab0d08da8552a646f
    27 N67cae2d197204116bf9766411624d927
    28 Ne778f539adf040e396aff6b5d98f8031
    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
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher Naf9110052b094a6094a0d841172c3009
    34 schema:url https://link.springer.com/10.1007%2Fs00354-018-0037-3
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset articles
    37 rdf:type schema:ScholarlyArticle
    38 N129db3ab7c1945bab0d08da8552a646f schema:name doi
    39 schema:value 10.1007/s00354-018-0037-3
    40 rdf:type schema:PropertyValue
    41 N48f0fd03631649bd9e811ab27cc06f5d schema:issueNumber 3
    42 rdf:type schema:PublicationIssue
    43 N67cae2d197204116bf9766411624d927 schema:name dimensions_id
    44 schema:value pub.1105977560
    45 rdf:type schema:PropertyValue
    46 Nae6ba5ca26ad472281312d7df30c57c5 rdf:first sg:person.016655503425.67
    47 rdf:rest rdf:nil
    48 Naf9110052b094a6094a0d841172c3009 schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 Ne16d83e271c84e02b9322c6cef207571 schema:volumeNumber 36
    51 rdf:type schema:PublicationVolume
    52 Ne778f539adf040e396aff6b5d98f8031 schema:name readcube_id
    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
     




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


    ...