Principles of a reversible programming language
Authors:
Open Access
- 5 May 2008
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 43-54
Abstract
The principles of reversible programming languages are explicated and illustrated with reference to the design of a high-level imperative language, Janus. The fundamental properties for such languages include backward as well as forward determinism and reversible updates of data. The unique design features of the language include explicit post-condition assertions, direct access to an inverse semantics and the possibility of clean ({\ie}, garbage-free) computation of injective functions. We suggest the clean simulation of reversible Turing machines as a criterion for computing strength of reversible languages, and demonstrate this for Janus. We show the practicality of the language by implementation of a reversible fast Fourier transform. Our results indicate that the reversible programming paradigm has fundamental properties that are relevant to many different areas of computer science.Keywords
This publication has 20 references indexed in Scilit:
- Combinators for bidirectional tree transformationsACM Transactions on Programming Languages and Systems, 2007
- The decomposition of an arbitrary reversible logic circuitJournal of Physics A: General Physics, 2006
- Integer fast Fourier transformIEEE Transactions on Signal Processing, 2002
- Molecular dynamics and time reversibilityJournal of Statistical Physics, 1993
- Reversible Turing Machines and Polynomial Time Reversibly Computable FunctionsSIAM Journal on Discrete Mathematics, 1990
- Time/Space Trade-Offs for Reversible ComputationSIAM Journal on Computing, 1989
- Conservative logicInternational Journal of Theoretical Physics, 1982
- Computation and construction universality of reversible cellular automataJournal of Computer and System Sciences, 1977
- Inversion of the Helmholtz (or Laplace-Poisson) operator for slab geometryJournal of Computational Physics, 1973
- On reversible subroutines and computers that run backwardsCommunications of the ACM, 1965