Fundamentals of reversible flowchart languages
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Fundamentals of reversible flowchart languages. / Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert.
In: Theoretical Computer Science, Vol. 611, 2016, p. 87-115.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Fundamentals of reversible flowchart languages
AU - Yokoyama, Tetsuo
AU - Axelsen, Holger Bock
AU - Glück, Robert
PY - 2016
Y1 - 2016
N2 - Abstract This paper presents the fundamentals of reversible flowcharts. They are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model, in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression. Despite these constraints, we show that reversible flowcharts are both expressive and robust: reversible flowcharts can simulate irreversible ones, by adapting reversibilization techniques to the flowchart model. Thus, reversible flowcharts are r-Turing-complete, meaning that they can compute exactly all injective computable functions. Furthermore, structured reversible flowcharts are as expressive as unstructured ones, as shown by a reversible version of the classic Structured Program Theorem. We illustrate how reversible flowcharts can be concretized with two example programming languages, complete with syntax and semantics: a low-level unstructured language and a high-level structured language. We introduce concrete tools such as program inverters and translators for both languages, which follow the structure suggested by the flowchart model. To further illustrate the different concepts and tools brought together in this paper, we present two major worked examples: a reversible permutation-to-code algorithm due to Dijkstra, and a simulation scheme for reversible Turing machines. By exhibiting a wide range of uses we hope that this paper can serve as a springboard for further theoretical research in reversible computing.
AB - Abstract This paper presents the fundamentals of reversible flowcharts. They are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model, in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression. Despite these constraints, we show that reversible flowcharts are both expressive and robust: reversible flowcharts can simulate irreversible ones, by adapting reversibilization techniques to the flowchart model. Thus, reversible flowcharts are r-Turing-complete, meaning that they can compute exactly all injective computable functions. Furthermore, structured reversible flowcharts are as expressive as unstructured ones, as shown by a reversible version of the classic Structured Program Theorem. We illustrate how reversible flowcharts can be concretized with two example programming languages, complete with syntax and semantics: a low-level unstructured language and a high-level structured language. We introduce concrete tools such as program inverters and translators for both languages, which follow the structure suggested by the flowchart model. To further illustrate the different concepts and tools brought together in this paper, we present two major worked examples: a reversible permutation-to-code algorithm due to Dijkstra, and a simulation scheme for reversible Turing machines. By exhibiting a wide range of uses we hope that this paper can serve as a springboard for further theoretical research in reversible computing.
KW - r-Turing-completeness
U2 - 10.1016/j.tcs.2015.07.046
DO - 10.1016/j.tcs.2015.07.046
M3 - Journal article
VL - 611
SP - 87
EP - 115
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
ID: 142941386