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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Appel, A.W.: Modern Compiler Implementation in ML. Camb. Uni. Press, New York (1998)
Axelsen, H.B., Glück, R.: What do reversible programs compute? In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol. 6604, pp. 42–56. Springer, Heidelberg (2011)
Axelsen, H.B., Glück, R., Yokoyama, T.: Reversible machine code and its abstract processor architecture. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 56–69. Springer, Heidelberg (2007)
Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development 17, 525–532 (1973)
De Vos, A.: Reversible Computing: Fundamentals, Quantum Computing and Applications. WILEY-VCH, Weinheim (2010)
Frank, M.P.: Reversibility for Efficient Computing. PhD thesis, MIT (1999)
Landauer, R.: Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5(3), 183–191 (1961)
Lecerf, Y.: Machines de Turing réversibles. Récursive insolubilité en n ε N de l’équation u = θ n u, oú θ est un “isomorphisme de codes”. Comptes Rendus Hebdomadaires 257, 2597–2600 (1963)
Lutz, C.: Janus: a time-reversible language. Letter written to R. Landauer (1986), http://tetsuo.jp/ref/janus.html
Mu, S.-C., Hu, Z., Takeichi, M.: An algebraic approach to bi-directional updating. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 2–20. Springer, Heidelberg (2004)
Schellekens, M.: MOQA; unlocking the potential of compositional static average-case analysis. Journal of Logic and Algebraic Programming 79(1), 61–83 (2010)
Thomsen, M.K., Axelsen, H.B.: Parallelization of reversible ripple-carry adders. Parallel Processing Letters 19(2), 205–222 (2009)
Thomsen, M.K., Glück, R., Axelsen, H.B.: Towards designing a reversible processor architecture (work-in-progress). In: Reversible Computation. Preliminary Proceedings, pp. 46–50 (2009)
Thomsen, M.K., Glück, R., Axelsen, H.B.: Reversible arithmetic logic unit for quantum arithmetic. J. of Phys. A: Math. and Theor. 42(38), 2002 (2010)
van de Snepscheut, J.L.A.: What computing is all about. Springer, Heidelberg (1993)
Vieri, C.J.: Reversible Computer Engineering and Architecture. PhD thesis, MIT (1999)
Yokoyama, T., Axelsen, H.B., Glück, R.: Principles of a reversible programming language. In: Proceedings of Computing Frontiers, pp. 43–54. ACM Press, New York (2008)
Yokoyama, T., Axelsen, H.B., Glück, R.: Reversible flowchart languages and the structured reversible program theorem. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 258–270. Springer, Heidelberg (2008)
Yokoyama, T., Glück, R.: A reversible programming language and its invertible self-interpreter. In: Proceedings of Partial Evaluation and Program Manipulation, pp. 144–153. ACM Press, New York (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Axelsen, H.B. (2011). Clean Translation of an Imperative Reversible Programming Language. In: Knoop, J. (eds) Compiler Construction. CC 2011. Lecture Notes in Computer Science, vol 6601. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19861-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-19861-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19860-1
Online ISBN: 978-3-642-19861-8
eBook Packages: Computer ScienceComputer Science (R0)