Data Structures and Dynamic Memory Management in Reversible Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-22

AUTHORS

Martin Holm Cservenka , Robert Glück , Tue Haulund , Torben Ægidius Mogensen

ABSTRACT

We present a method for reversible dynamic memory management based on a reversible version of the Buddy Memory system. This method supports decoupled allocation and deallocation of variable-sized records and can be applied to any reversible language with heap storage. We demonstrate how these new capabilities allow for the direct realization of commonplace data structures such as trees, heaps and queues which until now has not been practical in a reversible language. Finally, we provide a definition of our method in the high-level reversible language Janus as well as a description of its fragmentation and garbage-generation characteristics. The reversible memory management system has been fully implemented and tested in a compiler for a reversible object-oriented programming language targeting the reversible assembly language PISA. More... »

PAGES

269-285

Book

TITLE

Reversible Computation

ISBN

978-3-319-99497-0
978-3-319-99498-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_19

DOI

http://dx.doi.org/10.1007/978-3-319-99498-7_19

DIMENSIONS

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


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/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "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, Copenhagen, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cservenka", 
        "givenName": "Martin Holm", 
        "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, 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"
      }, 
      {
        "affiliation": {
          "name": [
            "Falcon.io ApS, 1553, Copenhagen, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Haulund", 
        "givenName": "Tue", 
        "id": "sg:person.011664310520.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011664310520.75"
        ], 
        "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, 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": "https://doi.org/10.1145/1244381.1244404", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006492707"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/365813.365819", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013518028"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00236-004-0159-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019734030", 
          "https://doi.org/10.1007/s00236-004-0159-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-40578-0_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028587049", 
          "https://doi.org/10.1007/978-3-319-40578-0_10"
        ], 
        "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/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": "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.1587/transinf.2016edp7274", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085100497"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-59936-6_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086393504", 
          "https://doi.org/10.1007/978-3-319-59936-6_5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-08-22", 
    "datePublishedReg": "2018-08-22", 
    "description": "We present a method for reversible dynamic memory management based on a reversible version of the Buddy Memory system. This method supports decoupled allocation and deallocation of variable-sized records and can be applied to any reversible language with heap storage. We demonstrate how these new capabilities allow for the direct realization of commonplace data structures such as trees, heaps and queues which until now has not been practical in a reversible language. Finally, we provide a definition of our method in the high-level reversible language Janus as well as a description of its fragmentation and garbage-generation characteristics. The reversible memory management system has been fully implemented and tested in a compiler for a reversible object-oriented programming language targeting the reversible assembly language PISA.", 
    "editor": [
      {
        "familyName": "Kari", 
        "givenName": "Jarkko", 
        "type": "Person"
      }, 
      {
        "familyName": "Ulidowski", 
        "givenName": "Irek", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-99498-7_19", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-99497-0", 
        "978-3-319-99498-7"
      ], 
      "name": "Reversible Computation", 
      "type": "Book"
    }, 
    "name": "Data Structures and Dynamic Memory Management in Reversible Languages", 
    "pagination": "269-285", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-99498-7_19"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5498f06c9d0f338d2635a45a07807e3754168fc44401ef2ab251ec7a84e91486"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106294867"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-99498-7_19", 
      "https://app.dimensions.ai/details/publication/pub.1106294867"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T04:59", 
    "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/0000000325_0000000325/records_100779_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-319-99498-7_19"
  }
]
 

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-99498-7_19'

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-99498-7_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_19'

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-99498-7_19'


 

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

132 TRIPLES      23 PREDICATES      37 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-99498-7_19 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N9df9144723c6434fbe7c8ccbfcb3e618
4 schema:citation sg:pub.10.1007/978-3-319-08494-7_7
5 sg:pub.10.1007/978-3-319-20860-2_5
6 sg:pub.10.1007/978-3-319-40578-0_10
7 sg:pub.10.1007/978-3-319-59936-6_5
8 sg:pub.10.1007/978-3-642-29517-1_2
9 sg:pub.10.1007/978-3-642-38986-3_9
10 sg:pub.10.1007/s00236-004-0159-6
11 https://doi.org/10.1145/1244381.1244404
12 https://doi.org/10.1145/365628.365655
13 https://doi.org/10.1145/365813.365819
14 https://doi.org/10.1587/transinf.2016edp7274
15 schema:datePublished 2018-08-22
16 schema:datePublishedReg 2018-08-22
17 schema:description We present a method for reversible dynamic memory management based on a reversible version of the Buddy Memory system. This method supports decoupled allocation and deallocation of variable-sized records and can be applied to any reversible language with heap storage. We demonstrate how these new capabilities allow for the direct realization of commonplace data structures such as trees, heaps and queues which until now has not been practical in a reversible language. Finally, we provide a definition of our method in the high-level reversible language Janus as well as a description of its fragmentation and garbage-generation characteristics. The reversible memory management system has been fully implemented and tested in a compiler for a reversible object-oriented programming language targeting the reversible assembly language PISA.
18 schema:editor N81ec43e374724f38b16660408f4b0c67
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf Neacc08c6b0094937959b642261d0e4c3
23 schema:name Data Structures and Dynamic Memory Management in Reversible Languages
24 schema:pagination 269-285
25 schema:productId N012120412398415792370b64c595035c
26 N6814c462816f47a08efa2130a5a867b9
27 Nef7b758c9e284086b7ce45c6876b7850
28 schema:publisher N68ea02b28d4241f3b2e35c75a2314cd5
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106294867
30 https://doi.org/10.1007/978-3-319-99498-7_19
31 schema:sdDatePublished 2019-04-16T04:59
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Nb5c33a5d67ef41aa8ab125c260075607
34 schema:url https://link.springer.com/10.1007%2F978-3-319-99498-7_19
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N012120412398415792370b64c595035c schema:name dimensions_id
39 schema:value pub.1106294867
40 rdf:type schema:PropertyValue
41 N2469f51a52fc45f483d1b1f955395a4e schema:affiliation https://www.grid.ac/institutes/grid.5254.6
42 schema:familyName Cservenka
43 schema:givenName Martin Holm
44 rdf:type schema:Person
45 N3476cef128234e41bd146480633f8fbb schema:familyName Ulidowski
46 schema:givenName Irek
47 rdf:type schema:Person
48 N56b8679903654f10ad74d1874948f1c9 rdf:first sg:person.011664310520.75
49 rdf:rest N95b675c6eaf24b6188f4769349a7c9f9
50 N6814c462816f47a08efa2130a5a867b9 schema:name doi
51 schema:value 10.1007/978-3-319-99498-7_19
52 rdf:type schema:PropertyValue
53 N68ea02b28d4241f3b2e35c75a2314cd5 schema:location Cham
54 schema:name Springer International Publishing
55 rdf:type schema:Organisation
56 N81ec43e374724f38b16660408f4b0c67 rdf:first N892f2dce15a8495c88a42709f0c0c2a5
57 rdf:rest Nfe0aaa966e4d45939e3d8f9d2604176a
58 N892f2dce15a8495c88a42709f0c0c2a5 schema:familyName Kari
59 schema:givenName Jarkko
60 rdf:type schema:Person
61 N95b675c6eaf24b6188f4769349a7c9f9 rdf:first sg:person.016655503425.67
62 rdf:rest rdf:nil
63 N9df9144723c6434fbe7c8ccbfcb3e618 rdf:first N2469f51a52fc45f483d1b1f955395a4e
64 rdf:rest N9e12eb541f654f7787516a186889a123
65 N9e12eb541f654f7787516a186889a123 rdf:first sg:person.010754010217.31
66 rdf:rest N56b8679903654f10ad74d1874948f1c9
67 Nb5c33a5d67ef41aa8ab125c260075607 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 Nd96ea9bcd5b742f8a78a20ae13901ca2 schema:name Falcon.io ApS, 1553, Copenhagen, Denmark
70 rdf:type schema:Organization
71 Neacc08c6b0094937959b642261d0e4c3 schema:isbn 978-3-319-99497-0
72 978-3-319-99498-7
73 schema:name Reversible Computation
74 rdf:type schema:Book
75 Nef7b758c9e284086b7ce45c6876b7850 schema:name readcube_id
76 schema:value 5498f06c9d0f338d2635a45a07807e3754168fc44401ef2ab251ec7a84e91486
77 rdf:type schema:PropertyValue
78 Nfe0aaa966e4d45939e3d8f9d2604176a rdf:first N3476cef128234e41bd146480633f8fbb
79 rdf:rest rdf:nil
80 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
81 schema:name Language, Communication and Culture
82 rdf:type schema:DefinedTerm
83 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
84 schema:name Linguistics
85 rdf:type schema:DefinedTerm
86 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
87 schema:familyName Glück
88 schema:givenName Robert
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
90 rdf:type schema:Person
91 sg:person.011664310520.75 schema:affiliation Nd96ea9bcd5b742f8a78a20ae13901ca2
92 schema:familyName Haulund
93 schema:givenName Tue
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011664310520.75
95 rdf:type schema:Person
96 sg:person.016655503425.67 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
97 schema:familyName Mogensen
98 schema:givenName Torben Ægidius
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
100 rdf:type schema:Person
101 sg:pub.10.1007/978-3-319-08494-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048471805
102 https://doi.org/10.1007/978-3-319-08494-7_7
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/978-3-319-20860-2_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004134457
105 https://doi.org/10.1007/978-3-319-20860-2_5
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/978-3-319-40578-0_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028587049
108 https://doi.org/10.1007/978-3-319-40578-0_10
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/978-3-319-59936-6_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086393504
111 https://doi.org/10.1007/978-3-319-59936-6_5
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/978-3-642-29517-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029572889
114 https://doi.org/10.1007/978-3-642-29517-1_2
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/978-3-642-38986-3_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036592869
117 https://doi.org/10.1007/978-3-642-38986-3_9
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/s00236-004-0159-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019734030
120 https://doi.org/10.1007/s00236-004-0159-6
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1244381.1244404 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006492707
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/365628.365655 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045610264
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/365813.365819 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013518028
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1587/transinf.2016edp7274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085100497
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
131 schema:name DIKU, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
132 rdf:type schema:Organization
 




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


...