Reversible Representation and Manipulation of Constructor Terms in the Heap View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Holger Bock Axelsen , Robert Glück

ABSTRACT

We currently have limited understanding of how complex data (e.g. algebraic data types) can be represented and manipulated in reversible machine code, in particular without generating garbage. In this paper we present methods for representing and manipulating binary trees (constructor terms) in the heap of a reversible machine. We also give methods for enforcing the so-called first-match policy for a simplified version of the recent reversible functional language RFUN by Yokoyama et al., and simple methods to support let-calls via stack environments. More... »

PAGES

96-109

References to SciGraph publications

  • 2005-06-10. NREVERSAL of fortune — The thermodynamics of garbage collection in MEMORY MANAGEMENT
  • 2012. Towards a Reversible Functional Language in REVERSIBLE COMPUTATION
  • 2012. A Reversible Processor Architecture and Its Reversible Logic Design in REVERSIBLE COMPUTATION
  • 2011. What Do Reversible Programs Compute? in FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES
  • 2011. Clean Translation of an Imperative Reversible Programming Language in COMPILER CONSTRUCTION
  • 2013. Isomorphic Interpreters from Logically Reversible Abstract Machines in REVERSIBLE COMPUTATION
  • 2008. Reversible Flowchart Languages and the Structured Reversible Program Theorem in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2007. Reversible Machine Code and Its Abstract Processor Architecture in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2003. A Program Inverter for a Functional Language with Equality and Constructors in PROGRAMMING LANGUAGES AND SYSTEMS
  • Book

    TITLE

    Reversible Computation

    ISBN

    978-3-642-38985-6
    978-3-642-38986-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-38986-3_9

    DOI

    http://dx.doi.org/10.1007/978-3-642-38986-3_9

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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, Department of Computer Science, University of Copenhagen, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Axelsen", 
            "givenName": "Holger Bock", 
            "id": "sg:person.015546427711.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Copenhagen", 
              "id": "https://www.grid.ac/institutes/grid.5254.6", 
              "name": [
                "DIKU, Department of Computer Science, University of Copenhagen, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gl\u00fcck", 
            "givenName": "Robert", 
            "id": "sg:person.010754010217.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-29517-1_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000285532", 
              "https://doi.org/10.1007/978-3-642-29517-1_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-40018-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012065324", 
              "https://doi.org/10.1007/978-3-540-40018-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015349256", 
              "https://doi.org/10.1007/978-3-540-74510-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1366230.1366239", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018780610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70583-3_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022695518", 
              "https://doi.org/10.1007/978-3-540-70583-3_22"
            ], 
            "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": "sg:pub.10.1007/978-3-642-36315-3_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031090203", 
              "https://doi.org/10.1007/978-3-642-36315-3_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19805-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047299195", 
              "https://doi.org/10.1007/978-3-642-19805-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19805-2_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047299195", 
              "https://doi.org/10.1007/978-3-642-19805-2_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/142137.142162", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047903139"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-19861-8_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048833860", 
              "https://doi.org/10.1007/978-3-642-19861-8_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/367177.367199", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049543462"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.176.0525", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180324"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013", 
        "datePublishedReg": "2013-01-01", 
        "description": "We currently have limited understanding of how complex data (e.g. algebraic data types) can be represented and manipulated in reversible machine code, in particular without generating garbage. In this paper we present methods for representing and manipulating binary trees (constructor terms) in the heap of a reversible machine. We also give methods for enforcing the so-called first-match policy for a simplified version of the recent reversible functional language RFUN by Yokoyama et al., and simple methods to support let-calls via stack environments.", 
        "editor": [
          {
            "familyName": "Dueck", 
            "givenName": "Gerhard W.", 
            "type": "Person"
          }, 
          {
            "familyName": "Miller", 
            "givenName": "D. Michael", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-38986-3_9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-38985-6", 
            "978-3-642-38986-3"
          ], 
          "name": "Reversible Computation", 
          "type": "Book"
        }, 
        "name": "Reversible Representation and Manipulation of Constructor Terms in the Heap", 
        "pagination": "96-109", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-38986-3_9"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ae508f7bc8be9d663569a801bc86f0b8c6582d91e53fb9f2a48d37e035bc2982"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1036592869"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-38986-3_9", 
          "https://app.dimensions.ai/details/publication/pub.1036592869"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T23:53", 
        "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_8697_00000266.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-38986-3_9"
      }
    ]
     

    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-642-38986-3_9'

    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-642-38986-3_9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38986-3_9'

    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-642-38986-3_9'


     

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

    125 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-38986-3_9 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nf804422edfb0479b8e6f30098e911394
    4 schema:citation sg:pub.10.1007/978-3-540-40018-9_17
    5 sg:pub.10.1007/978-3-540-70583-3_22
    6 sg:pub.10.1007/978-3-540-74510-5_9
    7 sg:pub.10.1007/978-3-642-19805-2_4
    8 sg:pub.10.1007/978-3-642-19861-8_9
    9 sg:pub.10.1007/978-3-642-29517-1_2
    10 sg:pub.10.1007/978-3-642-29517-1_3
    11 sg:pub.10.1007/978-3-642-36315-3_5
    12 sg:pub.10.1007/bfb0017210
    13 https://doi.org/10.1145/1366230.1366239
    14 https://doi.org/10.1145/142137.142162
    15 https://doi.org/10.1145/367177.367199
    16 https://doi.org/10.1147/rd.176.0525
    17 schema:datePublished 2013
    18 schema:datePublishedReg 2013-01-01
    19 schema:description We currently have limited understanding of how complex data (e.g. algebraic data types) can be represented and manipulated in reversible machine code, in particular without generating garbage. In this paper we present methods for representing and manipulating binary trees (constructor terms) in the heap of a reversible machine. We also give methods for enforcing the so-called first-match policy for a simplified version of the recent reversible functional language RFUN by Yokoyama et al., and simple methods to support let-calls via stack environments.
    20 schema:editor N47fbe36447e44498a0765c01ff654c0f
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N20cb674ebfff468089604b5dfe7b1559
    25 schema:name Reversible Representation and Manipulation of Constructor Terms in the Heap
    26 schema:pagination 96-109
    27 schema:productId N05d0ee469ac14402a26a2e2b98ac7053
    28 Nc16768a4102b47f1b188a45c0e00fcaa
    29 Nec967faa81af49d9a08c2e7b2696d717
    30 schema:publisher N820cc07b5831442b9a66be7a0f43fa1b
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036592869
    32 https://doi.org/10.1007/978-3-642-38986-3_9
    33 schema:sdDatePublished 2019-04-15T23:53
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N56adab110a5740b49ce485418e98b0c1
    36 schema:url http://link.springer.com/10.1007/978-3-642-38986-3_9
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N05d0ee469ac14402a26a2e2b98ac7053 schema:name dimensions_id
    41 schema:value pub.1036592869
    42 rdf:type schema:PropertyValue
    43 N20cb674ebfff468089604b5dfe7b1559 schema:isbn 978-3-642-38985-6
    44 978-3-642-38986-3
    45 schema:name Reversible Computation
    46 rdf:type schema:Book
    47 N47fbe36447e44498a0765c01ff654c0f rdf:first N7f22838dece44289b3db55baa2624d56
    48 rdf:rest Nf46a113e818e42c78a75069450588646
    49 N4ec0793525354a9ebd103a687e631a66 schema:familyName Miller
    50 schema:givenName D. Michael
    51 rdf:type schema:Person
    52 N56adab110a5740b49ce485418e98b0c1 schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 N7aed031298b747dbb64e4fa415159d74 rdf:first sg:person.010754010217.31
    55 rdf:rest rdf:nil
    56 N7f22838dece44289b3db55baa2624d56 schema:familyName Dueck
    57 schema:givenName Gerhard W.
    58 rdf:type schema:Person
    59 N820cc07b5831442b9a66be7a0f43fa1b schema:location Berlin, Heidelberg
    60 schema:name Springer Berlin Heidelberg
    61 rdf:type schema:Organisation
    62 Nc16768a4102b47f1b188a45c0e00fcaa schema:name doi
    63 schema:value 10.1007/978-3-642-38986-3_9
    64 rdf:type schema:PropertyValue
    65 Nec967faa81af49d9a08c2e7b2696d717 schema:name readcube_id
    66 schema:value ae508f7bc8be9d663569a801bc86f0b8c6582d91e53fb9f2a48d37e035bc2982
    67 rdf:type schema:PropertyValue
    68 Nf46a113e818e42c78a75069450588646 rdf:first N4ec0793525354a9ebd103a687e631a66
    69 rdf:rest rdf:nil
    70 Nf804422edfb0479b8e6f30098e911394 rdf:first sg:person.015546427711.73
    71 rdf:rest N7aed031298b747dbb64e4fa415159d74
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Artificial Intelligence and Image Processing
    77 rdf:type schema:DefinedTerm
    78 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    79 schema:familyName Glück
    80 schema:givenName Robert
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
    82 rdf:type schema:Person
    83 sg:person.015546427711.73 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
    84 schema:familyName Axelsen
    85 schema:givenName Holger Bock
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73
    87 rdf:type schema:Person
    88 sg:pub.10.1007/978-3-540-40018-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012065324
    89 https://doi.org/10.1007/978-3-540-40018-9_17
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/978-3-540-70583-3_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022695518
    92 https://doi.org/10.1007/978-3-540-70583-3_22
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-540-74510-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015349256
    95 https://doi.org/10.1007/978-3-540-74510-5_9
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/978-3-642-19805-2_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047299195
    98 https://doi.org/10.1007/978-3-642-19805-2_4
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/978-3-642-19861-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048833860
    101 https://doi.org/10.1007/978-3-642-19861-8_9
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/978-3-642-29517-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029572889
    104 https://doi.org/10.1007/978-3-642-29517-1_2
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/978-3-642-29517-1_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285532
    107 https://doi.org/10.1007/978-3-642-29517-1_3
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-3-642-36315-3_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031090203
    110 https://doi.org/10.1007/978-3-642-36315-3_5
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/bfb0017210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791058
    113 https://doi.org/10.1007/bfb0017210
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/1366230.1366239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018780610
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/142137.142162 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047903139
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1145/367177.367199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049543462
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
    122 rdf:type schema:CreativeWork
    123 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
    124 schema:name DIKU, Department of Computer Science, University of Copenhagen, Denmark
    125 rdf:type schema:Organization
     




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


    ...