Reference Counting for Reversible Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Torben Ægidius Mogensen

ABSTRACT

Modern programming languages and operating systems use heap memory that allows allocation and deallocation of memory to be decoupled, so they don’t follow a stack discipline. Axelsen and Glück have presented a reversible heap manager where allocation and deallocation are each other’s logical inverses: Freeing a block of memory is done by running the allocation procedure backwards. Axelsen and Glück use this heap manager to sketch implementation of a simple reversible functional language where pattern matching a constructor is the inverse of construction, so pattern-matching implies deallocation. This requires the language to be linear: A pointer can not be copied and it can only be eliminated by deallocating the node to which it points. We overcome this limitation by adding reference counts to nodes: Copying a pointer to a node increases the reference count of the node and eliminating a pointer decreases the reference count. We show reversible implementations of operations on nodes with reference counts. We then show these operations can be used when implementing a reversible functional language RCFUN to the reversible imperative language Janus. More... »

PAGES

82-94

References to SciGraph publications

Book

TITLE

Reversible Computation

ISBN

978-3-319-08493-0
978-3-319-08494-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-08494-7_7

DOI

http://dx.doi.org/10.1007/978-3-319-08494-7_7

DIMENSIONS

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


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, University of Copenhagen, Universitetsparken 5, DK-2100\u00a0Copenhagen 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"
      }
    ], 
    "citation": [
      {
        "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/1366230.1366239", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018780610"
        ], 
        "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-540-70881-0_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032904132", 
          "https://doi.org/10.1007/978-3-540-70881-0_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-70881-0_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032904132", 
          "https://doi.org/10.1007/978-3-540-70881-0_28"
        ], 
        "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/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"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "Modern programming languages and operating systems use heap memory that allows allocation and deallocation of memory to be decoupled, so they don\u2019t follow a stack discipline. Axelsen and Gl\u00fcck have presented a reversible heap manager where allocation and deallocation are each other\u2019s logical inverses: Freeing a block of memory is done by running the allocation procedure backwards. Axelsen and Gl\u00fcck use this heap manager to sketch implementation of a simple reversible functional language where pattern matching a constructor is the inverse of construction, so pattern-matching implies deallocation. This requires the language to be linear: A pointer can not be copied and it can only be eliminated by deallocating the node to which it points. We overcome this limitation by adding reference counts to nodes: Copying a pointer to a node increases the reference count of the node and eliminating a pointer decreases the reference count. We show reversible implementations of operations on nodes with reference counts. We then show these operations can be used when implementing a reversible functional language RCFUN to the reversible imperative language Janus.", 
    "editor": [
      {
        "familyName": "Yamashita", 
        "givenName": "Shigeru", 
        "type": "Person"
      }, 
      {
        "familyName": "Minato", 
        "givenName": "Shin-ichi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-08494-7_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-08493-0", 
        "978-3-319-08494-7"
      ], 
      "name": "Reversible Computation", 
      "type": "Book"
    }, 
    "name": "Reference Counting for Reversible Languages", 
    "pagination": "82-94", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-08494-7_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e6e935bfda23d04e535e1f035004ea88e053a1ab64be182b7de33059c6890b97"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048471805"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-08494-7_7", 
      "https://app.dimensions.ai/details/publication/pub.1048471805"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:37", 
    "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_8660_00000273.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-08494-7_7"
  }
]
 

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-08494-7_7'

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-08494-7_7'

Turtle is a human-readable linked data format.

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

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-08494-7_7'


 

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

97 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-08494-7_7 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N9012699ac0ab4f8bb341ce688bfd2aca
4 schema:citation sg:pub.10.1007/978-3-540-70881-0_28
5 sg:pub.10.1007/978-3-642-19861-8_9
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.1145/1366230.1366239
11 schema:datePublished 2014
12 schema:datePublishedReg 2014-01-01
13 schema:description Modern programming languages and operating systems use heap memory that allows allocation and deallocation of memory to be decoupled, so they don’t follow a stack discipline. Axelsen and Glück have presented a reversible heap manager where allocation and deallocation are each other’s logical inverses: Freeing a block of memory is done by running the allocation procedure backwards. Axelsen and Glück use this heap manager to sketch implementation of a simple reversible functional language where pattern matching a constructor is the inverse of construction, so pattern-matching implies deallocation. This requires the language to be linear: A pointer can not be copied and it can only be eliminated by deallocating the node to which it points. We overcome this limitation by adding reference counts to nodes: Copying a pointer to a node increases the reference count of the node and eliminating a pointer decreases the reference count. We show reversible implementations of operations on nodes with reference counts. We then show these operations can be used when implementing a reversible functional language RCFUN to the reversible imperative language Janus.
14 schema:editor N0014125a175c49a39c94f44397208524
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N59351b15fa4642e68ed35a7c300eeffc
19 schema:name Reference Counting for Reversible Languages
20 schema:pagination 82-94
21 schema:productId Nb138c2012f744277aa0defd8f115a209
22 Nc555ea54194748b8a4a9bbe5f2654bb0
23 Nfb9b055c1a8246e9bc9a98437b07673d
24 schema:publisher N4cc1043b44e941259b9615d369bd8434
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048471805
26 https://doi.org/10.1007/978-3-319-08494-7_7
27 schema:sdDatePublished 2019-04-15T11:37
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher N937de908440a4bc49307f94155fa514a
30 schema:url http://link.springer.com/10.1007/978-3-319-08494-7_7
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N0014125a175c49a39c94f44397208524 rdf:first Nc83137f9d7844d58aecafee3f38a6733
35 rdf:rest N92df0b73d62b4329b7789f4752f6920a
36 N4cc1043b44e941259b9615d369bd8434 schema:location Cham
37 schema:name Springer International Publishing
38 rdf:type schema:Organisation
39 N59351b15fa4642e68ed35a7c300eeffc schema:isbn 978-3-319-08493-0
40 978-3-319-08494-7
41 schema:name Reversible Computation
42 rdf:type schema:Book
43 N9012699ac0ab4f8bb341ce688bfd2aca rdf:first sg:person.016655503425.67
44 rdf:rest rdf:nil
45 N92df0b73d62b4329b7789f4752f6920a rdf:first Nf5dc91234a9e42609e8ff80c4bdb2b4c
46 rdf:rest rdf:nil
47 N937de908440a4bc49307f94155fa514a schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 Nb138c2012f744277aa0defd8f115a209 schema:name doi
50 schema:value 10.1007/978-3-319-08494-7_7
51 rdf:type schema:PropertyValue
52 Nc555ea54194748b8a4a9bbe5f2654bb0 schema:name dimensions_id
53 schema:value pub.1048471805
54 rdf:type schema:PropertyValue
55 Nc83137f9d7844d58aecafee3f38a6733 schema:familyName Yamashita
56 schema:givenName Shigeru
57 rdf:type schema:Person
58 Nf5dc91234a9e42609e8ff80c4bdb2b4c schema:familyName Minato
59 schema:givenName Shin-ichi
60 rdf:type schema:Person
61 Nfb9b055c1a8246e9bc9a98437b07673d schema:name readcube_id
62 schema:value e6e935bfda23d04e535e1f035004ea88e053a1ab64be182b7de33059c6890b97
63 rdf:type schema:PropertyValue
64 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
65 schema:name Language, Communication and Culture
66 rdf:type schema:DefinedTerm
67 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
68 schema:name Linguistics
69 rdf:type schema:DefinedTerm
70 sg:person.016655503425.67 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
71 schema:familyName Mogensen
72 schema:givenName Torben Ægidius
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
74 rdf:type schema:Person
75 sg:pub.10.1007/978-3-540-70881-0_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032904132
76 https://doi.org/10.1007/978-3-540-70881-0_28
77 rdf:type schema:CreativeWork
78 sg:pub.10.1007/978-3-642-19861-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048833860
79 https://doi.org/10.1007/978-3-642-19861-8_9
80 rdf:type schema:CreativeWork
81 sg:pub.10.1007/978-3-642-29517-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029572889
82 https://doi.org/10.1007/978-3-642-29517-1_2
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/978-3-642-29709-0_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011121976
85 https://doi.org/10.1007/978-3-642-29709-0_25
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/978-3-642-38986-3_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036592869
88 https://doi.org/10.1007/978-3-642-38986-3_9
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/bfb0017210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030791058
91 https://doi.org/10.1007/bfb0017210
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1145/1366230.1366239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018780610
94 rdf:type schema:CreativeWork
95 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
96 schema:name DIKU, University of Copenhagen, Universitetsparken 5, DK-2100 Copenhagen O, Denmark
97 rdf:type schema:Organization
 




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


...