Garbage Collection for Reversible Functional Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015

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

References to SciGraph publications

  • 2012. Partial Evaluation of Janus Part 2: Assertions and Procedures in PERSPECTIVES OF SYSTEMS INFORMATICS
  • 2012. Towards a Reversible Functional Language in REVERSIBLE COMPUTATION
  • 2013. Reversible Representation and Manipulation of Constructor Terms in the Heap in REVERSIBLE COMPUTATION
  • 2009. 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit in ALGORITHMS - ESA 2009
  • 2005-06-10. NREVERSAL of fortune — The thermodynamics of garbage collection in MEMORY MANAGEMENT
  • 1998. “Balls into Bins” — A Simple and Tight Analysis in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE
  • Book

    TITLE

    Reversible Computation

    ISBN

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

    Author Affiliations

    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, University of Copenhagen"
              ], 
              "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-642-04128-0_60", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007761444", 
              "https://doi.org/10.1007/978-3-642-04128-0_60"
            ], 
            "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/978-3-642-29517-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029572889", 
              "https://doi.org/10.1007/978-3-642-29517-1_2"
            ], 
            "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/978-3-642-38986-3_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036592869", 
              "https://doi.org/10.1007/978-3-642-38986-3_9"
            ], 
            "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"
          }
        ], 
        "datePublished": "2015", 
        "datePublishedReg": "2015-01-01", 
        "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"
        }, 
        "name": "Garbage Collection for Reversible Functional Languages", 
        "pagination": "79-94", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-20860-2_5"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "13b38b2605775f4416db3313432663d06001106560373d7d20ab1dad0d679f5e"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1004134457"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "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": "2019-04-15T21:55", 
        "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/0000000001_0000000264/records_8693_00000245.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/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.

    100 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 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 N972b6260015c4bbb952ceb20e5936b67
    4 schema:citation sg:pub.10.1007/3-540-49543-6_13
    5 sg:pub.10.1007/978-3-642-04128-0_60
    6 sg:pub.10.1007/978-3-642-29517-1_2
    7 sg:pub.10.1007/978-3-642-29709-0_25
    8 sg:pub.10.1007/978-3-642-38986-3_9
    9 sg:pub.10.1007/bfb0017210
    10 https://doi.org/10.1016/j.jalgor.2003.12.002
    11 https://doi.org/10.1145/368892.368907
    12 schema:datePublished 2015
    13 schema:datePublishedReg 2015-01-01
    14 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.
    15 schema:editor N31203a6371a94a0ca30bee5863f5ef9d
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N5c11fb5e348f4f98bf8cbc2b792c0fdb
    20 schema:name Garbage Collection for Reversible Functional Languages
    21 schema:pagination 79-94
    22 schema:productId Nd6744f079d6d49399dc289c8c445c8e1
    23 Nddaec867afb84aa9be730fe0c7f04189
    24 Nf063a79222644c6682b197ed1e24681c
    25 schema:publisher N5f785457561c4f55907a97a4a70aaddc
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004134457
    27 https://doi.org/10.1007/978-3-319-20860-2_5
    28 schema:sdDatePublished 2019-04-15T21:55
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N3efbbd6b01e44843b8a5943551216aad
    31 schema:url http://link.springer.com/10.1007/978-3-319-20860-2_5
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N31203a6371a94a0ca30bee5863f5ef9d rdf:first N65826820ae2845678e5f7dca4af22fbc
    36 rdf:rest Nafb5166ca64e427ca07b9c078964b471
    37 N3efbbd6b01e44843b8a5943551216aad schema:name Springer Nature - SN SciGraph project
    38 rdf:type schema:Organization
    39 N5c11fb5e348f4f98bf8cbc2b792c0fdb schema:isbn 978-3-319-20859-6
    40 978-3-319-20860-2
    41 schema:name Reversible Computation
    42 rdf:type schema:Book
    43 N5f785457561c4f55907a97a4a70aaddc schema:location Cham
    44 schema:name Springer International Publishing
    45 rdf:type schema:Organisation
    46 N65826820ae2845678e5f7dca4af22fbc schema:familyName Krivine
    47 schema:givenName Jean
    48 rdf:type schema:Person
    49 N972b6260015c4bbb952ceb20e5936b67 rdf:first sg:person.016655503425.67
    50 rdf:rest rdf:nil
    51 Nafb5166ca64e427ca07b9c078964b471 rdf:first Ne0c539b5835e45baa31b04e997410e36
    52 rdf:rest rdf:nil
    53 Nd6744f079d6d49399dc289c8c445c8e1 schema:name dimensions_id
    54 schema:value pub.1004134457
    55 rdf:type schema:PropertyValue
    56 Nddaec867afb84aa9be730fe0c7f04189 schema:name readcube_id
    57 schema:value 13b38b2605775f4416db3313432663d06001106560373d7d20ab1dad0d679f5e
    58 rdf:type schema:PropertyValue
    59 Ne0c539b5835e45baa31b04e997410e36 schema:familyName Stefani
    60 schema:givenName Jean-Bernard
    61 rdf:type schema:Person
    62 Nf063a79222644c6682b197ed1e24681c schema:name doi
    63 schema:value 10.1007/978-3-319-20860-2_5
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Information and Computing Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Data Format
    70 rdf:type schema:DefinedTerm
    71 sg:person.016655503425.67 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    72 schema:familyName Mogensen
    73 schema:givenName Torben Ægidius
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
    75 rdf:type schema:Person
    76 sg:pub.10.1007/3-540-49543-6_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038366427
    77 https://doi.org/10.1007/3-540-49543-6_13
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/978-3-642-04128-0_60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007761444
    80 https://doi.org/10.1007/978-3-642-04128-0_60
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/978-3-642-29517-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029572889
    83 https://doi.org/10.1007/978-3-642-29517-1_2
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/978-3-642-29709-0_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011121976
    86 https://doi.org/10.1007/978-3-642-29709-0_25
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/978-3-642-38986-3_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036592869
    89 https://doi.org/10.1007/978-3-642-38986-3_9
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bfb0017210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791058
    92 https://doi.org/10.1007/bfb0017210
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/j.jalgor.2003.12.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034279703
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1145/368892.368907 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020648049
    97 rdf:type schema:CreativeWork
    98 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    99 schema:name DIKU, University of Copenhagen
    100 rdf:type schema:Organization
     




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


    ...