Reversible computing from a programming language perspective

Robert Glück; Tetsuo Yokoyama

doi:10.1016/j.tcs.2022.06.010

Reversible computing from a programming language perspective

Robert Glück, Tetsuo Yokoyama

Programming Languages and Theory of Computation

Research output: Contribution to journal › Journal article › Research › peer-review

19 Citations (Scopus)

225 Downloads (Pure)

Abstract

Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right.

Reversible computing is situated within programming languages in general, and the relevant concepts are elaborated, including computability, injectivization and reversibilization. Features representative for many reversible languages are presented, such as reversible updates, reversible iterations, and access to a program's inverse semantics. Metaprogramming methods of particular importance to reversible programming, are introduced, including program inversion and inverse interpretation. Our presentation is independent of a particular language, although primarily the reversible language, Janus, will be used in examples.

Original language	English
Article number	113429
Journal	Theoretical Computer Science
Volume	953
Number of pages	26
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2022.06.010
Publication status	Published - 2023

Bibliographical note

Funding Information:
The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year.

Funding Information:
Many thanks to Markus Holzer and Martin Kutrib for the opportunity to present the talk at RPLA, FM Week, Porto, 2019, and to prepare this written exposition. Special thanks to Keisuke Nakano, Antonina Nepeivoda, and the anonymous reviewers for their useful feedback. It is a pleasure to thank Sergei Abramov, Holger Bock Axelsen, Poul Clementsen, Alexis De Vos, Robin Kaarsgaard, Masahiko Kawabe, Andrei V. Klimov, Torben Mogensen, Kenji Moriyama, and Michael Kirkedal Thomsen for many years of fruitful discussions. The authors also wish to thank all their collaborators, including the students and participants of the “MicroPower” research project [14]. The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year.

Publisher Copyright:
© 2022 The Author(s)

Keywords

Compute-uncompute
Function injectivization
Inverse interpretation
Metacomputation
Program inversion
Program reversibilization
Reversible computing
Reversible programming

Access to Document

10.1016/j.tcs.2022.06.010Licence: CC BY

FulltextFinal published version, 757 KBLicence: CC BY

Library access?

Check availability at the Royal Danish Library

Cite this

@article{6482269b30734e0297ddddc666180164,

title = "Reversible computing from a programming language perspective",

abstract = "Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right.Reversible computing is situated within programming languages in general, and the relevant concepts are elaborated, including computability, injectivization and reversibilization. Features representative for many reversible languages are presented, such as reversible updates, reversible iterations, and access to a program's inverse semantics. Metaprogramming methods of particular importance to reversible programming, are introduced, including program inversion and inverse interpretation. Our presentation is independent of a particular language, although primarily the reversible language, Janus, will be used in examples.",

keywords = "Compute-uncompute, Function injectivization, Inverse interpretation, Metacomputation, Program inversion, Program reversibilization, Reversible computing, Reversible programming",

author = "Robert Gl{\"u}ck and Tetsuo Yokoyama",

note = "Funding Information: The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year. Funding Information: Many thanks to Markus Holzer and Martin Kutrib for the opportunity to present the talk at RPLA, FM Week, Porto, 2019, and to prepare this written exposition. Special thanks to Keisuke Nakano, Antonina Nepeivoda, and the anonymous reviewers for their useful feedback. It is a pleasure to thank Sergei Abramov, Holger Bock Axelsen, Poul Clementsen, Alexis De Vos, Robin Kaarsgaard, Masahiko Kawabe, Andrei V. Klimov, Torben Mogensen, Kenji Moriyama, and Michael Kirkedal Thomsen for many years of fruitful discussions. The authors also wish to thank all their collaborators, including the students and participants of the “MicroPower” research project [14]. The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year. Publisher Copyright: {\textcopyright} 2022 The Author(s)",

year = "2023",

doi = "10.1016/j.tcs.2022.06.010",

language = "English",

volume = "953",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Reversible computing from a programming language perspective

AU - Glück, Robert

AU - Yokoyama, Tetsuo

N1 - Funding Information: The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year. Funding Information: Many thanks to Markus Holzer and Martin Kutrib for the opportunity to present the talk at RPLA, FM Week, Porto, 2019, and to prepare this written exposition. Special thanks to Keisuke Nakano, Antonina Nepeivoda, and the anonymous reviewers for their useful feedback. It is a pleasure to thank Sergei Abramov, Holger Bock Axelsen, Poul Clementsen, Alexis De Vos, Robin Kaarsgaard, Masahiko Kawabe, Andrei V. Klimov, Torben Mogensen, Kenji Moriyama, and Michael Kirkedal Thomsen for many years of fruitful discussions. The authors also wish to thank all their collaborators, including the students and participants of the “MicroPower” research project [14]. The presentation has also benefited from the courses “Program Inversion and Reversible Computation” (PIRC) held in various ways since 2004 at the University of Copenhagen and “Special Lecture in Information Science and Technology VII” on reversible computation held 2016–2019 at the University of Tokyo by the first author. The first author would like to thank Yoshihiko Futamura, Masami Hagiya, Akihiko Takano, and Kanae Tsushima for their hospitality in Japan. The second author was supported by JSPS KAKENHI Grant No. 22K11983 and Nanzan University Pache Research Subsidy I-A-2 for the 2022 academic year. Publisher Copyright: © 2022 The Author(s)

PY - 2023

Y1 - 2023

N2 - Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right.Reversible computing is situated within programming languages in general, and the relevant concepts are elaborated, including computability, injectivization and reversibilization. Features representative for many reversible languages are presented, such as reversible updates, reversible iterations, and access to a program's inverse semantics. Metaprogramming methods of particular importance to reversible programming, are introduced, including program inversion and inverse interpretation. Our presentation is independent of a particular language, although primarily the reversible language, Janus, will be used in examples.

AB - Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right.Reversible computing is situated within programming languages in general, and the relevant concepts are elaborated, including computability, injectivization and reversibilization. Features representative for many reversible languages are presented, such as reversible updates, reversible iterations, and access to a program's inverse semantics. Metaprogramming methods of particular importance to reversible programming, are introduced, including program inversion and inverse interpretation. Our presentation is independent of a particular language, although primarily the reversible language, Janus, will be used in examples.

KW - Compute-uncompute

KW - Function injectivization

KW - Inverse interpretation

KW - Metacomputation

KW - Program inversion

KW - Program reversibilization

KW - Reversible computing

KW - Reversible programming

U2 - 10.1016/j.tcs.2022.06.010

DO - 10.1016/j.tcs.2022.06.010

M3 - Journal article

AN - SCOPUS:85150371889

SN - 0304-3975

VL - 953

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 113429

ER -