skip to main content
10.1145/1244381.1244404acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
Article

A reversible programming language and its invertible self-interpreter

Published: 15 January 2007 Publication History

Abstract

A reversible programming language supports deterministic forward and backward computation. We formalize the programming language Janus and prove its reversibility. We provide a program inverter for the language and implement a self-interpreter that achieves deterministic forward and backward interpretation of Janus programs without using a computation history. As the self-interpreter is implemented in a reversible language, it is invertible using local program inversion. Many physical phenomena are reversible and we demonstrate the power of Janus by implementing a reversible program for discrete simulation of the Schrödinger wave equation that can be inverted as well as run forward and backward.

References

[1]
S. M. Abramov and R. Glück. Combining semantics with non-standard interpreter hierarchies. In FST TCS, volume 1974 of LNCS, pages 201--213. Springer-Verlag, 2000.
[2]
H. G. Baker. NREVERSAL of fortune - the thermodynamics of garbage collection. In the Int'l Workshop on Memory Management, pages 507--524. Springer-Verlag, 1992.
[3]
C. H. Bennett. Logical reversibility of computation. IBM J. Res. Dev., 17(6):525--532, 1973.
[4]
C. H. Bennett. Notes on the history of reversible computation. IBM J. Res. Dev., 32(1):16--23, 1988.
[5]
C. D. Carothers, K. S. Perumalla, and R. M. Fujimoto. Efficient optimistic parallel simulations using reverse computation. ACM Trans. Model. Comput. Simul., 9(3):224--253, 1999.
[6]
A. De Vos and Y. Van Rentergem. Reversible computing: from mathematical group theory to electronical circuit experiment. In 2nd Conf. on Computing Frontiers, pages 35--44. ACM Press, 2005.
[7]
A. Di Pierro, C. Hankin, and H. Wiklicky. Reversible combinatory logic. Mathematical. Structures in Comp. Sci., 16(4):621--637, 2006.
[8]
J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bi-directional tree transformations: A linguistic approach to the view update problem. ACM Trans. Prog. Lang. Syst., 2006.
[9]
M. P. Frank. Reversibility for Efficient Computing. PhD thesis, EECS Dept, MIT, 1999.
[10]
M. P. Frank. Introduction to reversible computing: motivation, progress, and challenges. In 2nd Conf. on Computing Frontiers, pages 385--390. ACM Press, 2005.
[11]
E. Fredkin. Feynman, Barton and the reversible Schrödinger difference equation. In A. J. G. Hey, editor, Feynman and Computation: Exploring the Limits of Computers, pages 337--348. Perseus Books, 1999.
[12]
E. Fredkin and T. Toffoli. Conservative Logic. Internat. J. Theor. Phy., 21:219--253, 1982.
[13]
R. Glück and M. Kawabe. Derivation of deterministic inverse programs based on LR parsing. In FLOPS, pages 291--306, 2004.
[14]
R. Glück and M. Kawabe. Revisiting an automatic program inverter for Lisp. SIGPLAN Not., 40(5):8--17, 2005.
[15]
D. Gries. The Science of Programming, chapter 21 Inverting Programs. Texts and Monographs in Computer Science. Springer-Verlag, 1981.
[16]
J. S. Hall. A reversible instruction set architecture and algorithms. In Physics and Computation, pages 128--134. IEEE Press, 1994.
[17]
H. M. Hasan Babu and A. R. Chowdhury. Design of a compact reversible binary coded decimal adder circuit. J. Syst. Archit., 52(5):272--282, 2006.
[18]
Z. Hu, S.-C. Mu, and M. Takeichi. A programmable editor for developing structured documents based on bidirectional transformations. In PEPM, pages 178--189. ACM Press, 2004.
[19]
R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res. Dev., 5(3):183--91, 1961.
[20]
K.-J. Lange, P. McKenzie, and A. Tapp. Reversible space equals deterministic space. J. Comput. and Sys. Sci, 60(2):354--367, 2000.
[21]
R. Y. Levine and A. T. Sherman. A note on Bennett's time space tradeoff for reversible computation. SIAM J. Comput., 19(4):673--677, 1990.
[22]
S. Lombardy. On the construction of reversible automata for reversible languages. In Int'l Coll. Automata, Languages, and Programming, pages 170--182. Springer-Verlag, 2002.
[23]
C. Lutz. Janus: a time-reversible language. A letter to Landauer. http://www.cise.uf1.edu/~mpf/rc/janus. html, 1986.
[24]
A. B. Matos. Linear programs in a simple reversible language. Theor. Comput. Sci., 290(3):2063--2074, 2003.
[25]
J. McCarthy. The inversion of functions defined by Turing machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 177--181. Princeton University Press, 1956.
[26]
T. Æ. Mogensen. Semi-inversion of guarded equations. In GPCE, volume 3676 of LNCS, pages 189--204, 2005.
[27]
K. Morita, T. Ogiro, K. Tanaka, and H. Kato. Classification and universality of reversible logic elements with one-bit memory. In MCU, volume 3354 of LNCS, pages 245--256. Springer, 2004.
[28]
J.-E. Pin. On the language accepted by finite reversible automata. In Int'l Coll. Automata, Languages, and Programming, volume 267 of LNCS, pages 237--249. Springer-Verlag, 1987.
[29]
T. Toffoli. Computation and construction universality of reversible cellular automata. J. Comput. Sys. Sci., 15:213--231, 1977.
[30]
T. Toffoli. Reversible computing. In Int'l Coll. Automata, Languages, and Programming, pages 632--644. Springer-Verlag, 1980.
[31]
C. J. Vieri. Reversible computer engineering and architecture. PhD thesis, MIT, 1999.
[32]
P. Vitányi. Time, space, and energy in reversible computing. In 2nd Conf. on Computing Frontiers, pages 435--444. ACM Press, 2005.

Cited By

View all
  • (2024)A Reversible Debugger for MPI ApplicationsProceedings of the 2nd ACM International Workshop on Future Debugging Techniques10.1145/3678720.3685316(16-21)Online publication date: 13-Sep-2024
  • (2024)An Axiomatic Theory for Reversible ComputationACM Transactions on Computational Logic10.1145/364847425:2(1-40)Online publication date: 16-Apr-2024
  • (2024)Reversibility in Process Calculi with Nondeterminism and ProbabilitiesTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_15(251-271)Online publication date: 22-Nov-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PEPM '07: Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation
January 2007
180 pages
ISBN:9781595936202
DOI:10.1145/1244381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Janus
  2. non-standard interpreter hierarchy
  3. program inversion
  4. reversible computing
  5. reversible programming language
  6. self-interpreter

Qualifiers

  • Article

Conference

PEPM07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)69
  • Downloads (Last 6 weeks)4
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)A Reversible Debugger for MPI ApplicationsProceedings of the 2nd ACM International Workshop on Future Debugging Techniques10.1145/3678720.3685316(16-21)Online publication date: 13-Sep-2024
  • (2024)An Axiomatic Theory for Reversible ComputationACM Transactions on Computational Logic10.1145/364847425:2(1-40)Online publication date: 16-Apr-2024
  • (2024)Reversibility in Process Calculi with Nondeterminism and ProbabilitiesTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_15(251-271)Online publication date: 22-Nov-2024
  • (2024)Jeopardy: An Invertible Functional Programming LanguageReversible Computation10.1007/978-3-031-62076-8_9(124-141)Online publication date: 29-May-2024
  • (2024)A Small-Step Semantics for JanusReversible Computation10.1007/978-3-031-62076-8_8(105-123)Online publication date: 29-May-2024
  • (2024)Exploring the Energy Overhead of Reversible Programs Executed on Irreversible HardwareReversible Computation10.1007/978-3-031-62076-8_6(77-93)Online publication date: 4-Jul-2024
  • (2023)Virtual Time III, Part 1: Unified Virtual Time Synchronization for Parallel Discrete Event SimulationACM Transactions on Modeling and Computer Simulation10.1145/350524832:4(1-29)Online publication date: 11-Jan-2023
  • (2023)Reversible computing from a programming language perspectiveTheoretical Computer Science10.1016/j.tcs.2022.06.010953(113429)Online publication date: Apr-2023
  • (2023)Causal Reversibility for Timed Process Calculi with Lazy/Eager Durationless Actions and Time AdditivityFormal Modeling and Analysis of Timed Systems10.1007/978-3-031-42626-1_2(15-32)Online publication date: 29-Aug-2023
  • (2023)Towards a Dereversibilizer: Fewer Asserts, StaticallyReversible Computation10.1007/978-3-031-38100-3_8(106-114)Online publication date: 12-Jul-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media