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 N8e5a1557249b4574bca032a5bafbc95c
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 Nad2c3c928e4a4da4857db41a2975409b
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree true
13 schema:isPartOf N858e8c61e82e4dfdb6a8410fa3c87bdd
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 N79f781ac4967446cafd2bd11198a8806
67 N8abcf9b04d994ab79306c3e464b8fd67
68 schema:publisher N3697d98dee2a47b19ec94689776c5a32
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 Na2e9dbcb67c24eaf8cebd5cc203df73f
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 N3697d98dee2a47b19ec94689776c5a32 schema:name Springer Nature
79 rdf:type schema:Organisation
80 N6051137b744c4e76bc7f324808f6c054 schema:familyName Knoop
81 schema:givenName Jens
82 rdf:type schema:Person
83 N79f781ac4967446cafd2bd11198a8806 schema:name doi
84 schema:value 10.1007/978-3-642-19861-8_9
85 rdf:type schema:PropertyValue
86 N858e8c61e82e4dfdb6a8410fa3c87bdd schema:isbn 978-3-642-19860-1
87 978-3-642-19861-8
88 schema:name Compiler Construction
89 rdf:type schema:Book
90 N8abcf9b04d994ab79306c3e464b8fd67 schema:name dimensions_id
91 schema:value pub.1048833860
92 rdf:type schema:PropertyValue
93 N8e5a1557249b4574bca032a5bafbc95c rdf:first sg:person.015546427711.73
94 rdf:rest rdf:nil
95 Na2e9dbcb67c24eaf8cebd5cc203df73f schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 Nad2c3c928e4a4da4857db41a2975409b rdf:first N6051137b744c4e76bc7f324808f6c054
98 rdf:rest rdf:nil
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)


...