Clean Translation of an Imperative Reversible Programming Language View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Holger Bock Axelsen

ABSTRACT

We describe the translation techniques used for the code generation in a compiler from the high-level reversible imperative programming language Janus to the low-level reversible assembly language PISA. Our translation is both semantics preserving (correct), in that target programs compute exactly the same functions as their source programs (cleanly, with no extraneous garbage output), and efficient, in that target programs conserve the complexities of source programs. In particular, target programs only require a constant amount of temporary garbage space.The given translation methods are generic, and should be applicable to any (imperative) reversible source language described with reversible flowcharts and reversible updates. To our knowledge, this is the first compiler between reversible languages where the source and target languages were independently developed; the first exhibiting both correctness and efficiency; and just the second compiler for reversible languages overall. More... »

PAGES

144-163

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "DIKU, Dept. of Computer Science, University of Copenhagen, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, Dept. 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"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We describe the translation techniques used for the code generation in a compiler from the high-level reversible imperative programming language Janus to the low-level reversible assembly language PISA. Our translation is both semantics preserving (correct), in that target programs compute exactly the same functions as their source programs (cleanly, with no extraneous garbage output), and efficient, in that target programs conserve the complexities of source programs. In particular, target programs only require a constant amount of temporary garbage space.The given translation methods are generic, and should be applicable to any (imperative) reversible source language described with reversible flowcharts and reversible updates. To our knowledge, this is the first compiler between reversible languages where the source and target languages were independently developed; the first exhibiting both correctness and efficiency; and just the second compiler for reversible languages overall.", 
    "editor": [
      {
        "familyName": "Knoop", 
        "givenName": "Jens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-19861-8_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-19860-1", 
        "978-3-642-19861-8"
      ], 
      "name": "Compiler Construction", 
      "type": "Book"
    }, 
    "keywords": [
      "reversible languages", 
      "target program", 
      "source program", 
      "reversible programming language", 
      "target language", 
      "source language", 
      "reversible updates", 
      "reversible flowcharts", 
      "language", 
      "translation techniques", 
      "translation method", 
      "code generation", 
      "programming language", 
      "second compiler", 
      "first compiler", 
      "compiler", 
      "translation", 
      "semantics", 
      "same function", 
      "correctness", 
      "complexity", 
      "update", 
      "space", 
      "flowchart", 
      "program", 
      "knowledge", 
      "technique", 
      "efficiency", 
      "constant amount", 
      "PISA", 
      "method", 
      "generation", 
      "Janus", 
      "source", 
      "amount", 
      "function", 
      "high-level reversible imperative programming language Janus", 
      "reversible imperative programming language Janus", 
      "imperative programming language Janus", 
      "programming language Janus", 
      "language Janus", 
      "low-level reversible assembly language PISA", 
      "reversible assembly language PISA", 
      "assembly language PISA", 
      "language PISA", 
      "temporary garbage space", 
      "garbage space", 
      "reversible source language", 
      "Clean Translation", 
      "Imperative Reversible Programming Language"
    ], 
    "name": "Clean Translation of an Imperative Reversible Programming Language", 
    "pagination": "144-163", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048833860"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-19861-8_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-19861-8_9", 
      "https://app.dimensions.ai/details/publication/pub.1048833860"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_187.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-19861-8_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-19861-8_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-19861-8_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-19861-8_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-19861-8_9'


 

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

118 TRIPLES      23 PREDICATES      78 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-19861-8_9 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 anzsrc-for:20
4 anzsrc-for:2004
5 schema:author N0ccf6355e67f449c8713179b57e2809a
6 schema:datePublished 2011
7 schema:datePublishedReg 2011-01-01
8 schema:description We describe the translation techniques used for the code generation in a compiler from the high-level reversible imperative programming language Janus to the low-level reversible assembly language PISA. Our translation is both semantics preserving (correct), in that target programs compute exactly the same functions as their source programs (cleanly, with no extraneous garbage output), and efficient, in that target programs conserve the complexities of source programs. In particular, target programs only require a constant amount of temporary garbage space.The given translation methods are generic, and should be applicable to any (imperative) reversible source language described with reversible flowcharts and reversible updates. To our knowledge, this is the first compiler between reversible languages where the source and target languages were independently developed; the first exhibiting both correctness and efficiency; and just the second compiler for reversible languages overall.
9 schema:editor N62e2a4913b334b35a4ab87353d896c4b
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf N9735a0403350452da1b44bcb507e8ec1
14 schema:keywords Clean Translation
15 Imperative Reversible Programming Language
16 Janus
17 PISA
18 amount
19 assembly language PISA
20 code generation
21 compiler
22 complexity
23 constant amount
24 correctness
25 efficiency
26 first compiler
27 flowchart
28 function
29 garbage space
30 generation
31 high-level reversible imperative programming language Janus
32 imperative programming language Janus
33 knowledge
34 language
35 language Janus
36 language PISA
37 low-level reversible assembly language PISA
38 method
39 program
40 programming language
41 programming language Janus
42 reversible assembly language PISA
43 reversible flowcharts
44 reversible imperative programming language Janus
45 reversible languages
46 reversible programming language
47 reversible source language
48 reversible updates
49 same function
50 second compiler
51 semantics
52 source
53 source language
54 source program
55 space
56 target language
57 target program
58 technique
59 temporary garbage space
60 translation
61 translation method
62 translation techniques
63 update
64 schema:name Clean Translation of an Imperative Reversible Programming Language
65 schema:pagination 144-163
66 schema:productId N737ac295323b4b85b683fde11b43cc2f
67 Nc2d4d7a7a7dd48db84532eaa181def3d
68 schema:publisher Nf70bccbd98b34f21b313f5d8dcd5a748
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048833860
70 https://doi.org/10.1007/978-3-642-19861-8_9
71 schema:sdDatePublished 2021-12-01T19:59
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher Nfe05d4d08f0f47c18395b45982f60735
74 schema:url https://doi.org/10.1007/978-3-642-19861-8_9
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N038312675c1545a0bb9c0955b2a63b98 schema:familyName Knoop
79 schema:givenName Jens
80 rdf:type schema:Person
81 N0ccf6355e67f449c8713179b57e2809a rdf:first sg:person.015546427711.73
82 rdf:rest rdf:nil
83 N62e2a4913b334b35a4ab87353d896c4b rdf:first N038312675c1545a0bb9c0955b2a63b98
84 rdf:rest rdf:nil
85 N737ac295323b4b85b683fde11b43cc2f schema:name dimensions_id
86 schema:value pub.1048833860
87 rdf:type schema:PropertyValue
88 N9735a0403350452da1b44bcb507e8ec1 schema:isbn 978-3-642-19860-1
89 978-3-642-19861-8
90 schema:name Compiler Construction
91 rdf:type schema:Book
92 Nc2d4d7a7a7dd48db84532eaa181def3d schema:name doi
93 schema:value 10.1007/978-3-642-19861-8_9
94 rdf:type schema:PropertyValue
95 Nf70bccbd98b34f21b313f5d8dcd5a748 schema:name Springer Nature
96 rdf:type schema:Organisation
97 Nfe05d4d08f0f47c18395b45982f60735 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computer Software
104 rdf:type schema:DefinedTerm
105 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
106 schema:name Language, Communication and Culture
107 rdf:type schema:DefinedTerm
108 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
109 schema:name Linguistics
110 rdf:type schema:DefinedTerm
111 sg:person.015546427711.73 schema:affiliation grid-institutes:grid.5254.6
112 schema:familyName Axelsen
113 schema:givenName Holger Bock
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015546427711.73
115 rdf:type schema:Person
116 grid-institutes:grid.5254.6 schema:alternateName DIKU, Dept. of Computer Science, University of Copenhagen, Denmark
117 schema:name DIKU, Dept. of Computer Science, University of Copenhagen, Denmark
118 rdf:type schema:Organization
 




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


...