Clean translation of an imperative reversible programming language

Holger Bock Axelsen

doi:10.1007/978-3-642-19861-8_9

Clean translation of an imperative reversible programming language

Holger Bock Axelsen

Datalogisk Institut

20 Citationer (Scopus)

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.

Originalsprog	Engelsk
Titel	Compiler Construction : 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings
Redaktører	Jens Knoop
Antal sider	20
Forlag	Springer
Publikationsdato	2011
Sider	144-163
ISBN (Trykt)	978-3-642-19860-1
ISBN (Elektronisk)	978-3-642-19861-8
DOI	https://doi.org/10.1007/978-3-642-19861-8_9
Status	Udgivet - 2011
Begivenhed	20th International Conference on Compiler Construction - Saarbrücken, Tyskland Varighed: 26 mar. 2011 → 3 apr. 2011 Konferencens nummer: 20

Konference

Konference	20th International Conference on Compiler Construction
Nummer	20
Land/Område	Tyskland
By	Saarbrücken
Periode	26/03/2011 → 03/04/2011

Navn	Lecture notes in computer science
Vol/bind	6601
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-19861-8_9

10.1007%2F978-3-642-19861-8_9.pdfForlagets udgivne version, 283 KB

Citationsformater

Axelsen, H. B. (2011). Clean translation of an imperative reversible programming language. I J. Knoop (red.), Compiler Construction: 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings (s. 144-163). Springer. Lecture notes in computer science Bind 6601 https://doi.org/10.1007/978-3-642-19861-8_9

Clean translation of an imperative reversible programming language. / Axelsen, Holger Bock.

Compiler Construction: 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings. red. / Jens Knoop. Springer, 2011. s. 144-163 (Lecture notes in computer science, Bind 6601).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Axelsen, HB 2011, Clean translation of an imperative reversible programming language. i J Knoop (red.), Compiler Construction: 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings. Springer, Lecture notes in computer science, bind 6601, s. 144-163, 20th International Conference on Compiler Construction, Saarbrücken, Tyskland, 26/03/2011. https://doi.org/10.1007/978-3-642-19861-8_9

Axelsen HB. Clean translation of an imperative reversible programming language. I Knoop J, red., Compiler Construction: 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings. Springer. 2011. s. 144-163. (Lecture notes in computer science, Bind 6601). doi: 10.1007/978-3-642-19861-8_9

Axelsen, Holger Bock. / Clean translation of an imperative reversible programming language. Compiler Construction: 20th International Conference, CC 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbrücken, Germany, March 26–April 3, 2011. Proceedings. red. / Jens Knoop. Springer, 2011. s. 144-163 (Lecture notes in computer science, Bind 6601).

@inproceedings{c750ba42625448bda27a21935cb3513d,

title = "Clean translation of an imperative reversible programming language",

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.",

author = "Axelsen, {Holger Bock}",

year = "2011",

doi = "10.1007/978-3-642-19861-8_9",

language = "English",

isbn = "978-3-642-19860-1",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "144--163",

editor = "Jens Knoop",

booktitle = "Compiler Construction",

note = "20th International Conference on Compiler Construction, CC 2011 ; Conference date: 26-03-2011 Through 03-04-2011",

}

TY - GEN

T1 - Clean translation of an imperative reversible programming language

AU - Axelsen, Holger Bock

N1 - Conference code: 20

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-19861-8_9

DO - 10.1007/978-3-642-19861-8_9

M3 - Article in proceedings

SN - 978-3-642-19860-1

T3 - Lecture notes in computer science

SP - 144

EP - 163

BT - Compiler Construction

A2 - Knoop, Jens

PB - Springer

T2 - 20th International Conference on Compiler Construction

Y2 - 26 March 2011 through 3 April 2011

ER -

Clean translation of an imperative reversible programming language

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater