Abstract
We study in this paper the cost of making a concurrent programming language reversible. More specifically, we take an abstract machine for a fragment of the Oz programming language and make it reversible. We show that the overhead of the reversible machine with respect to the original one in terms of space is at most linear in the number of execution steps. We also show that this bound is tight since some programs cannot be made reversible without storing a commensurate amount of information.
This work has been partially supported by the French National Research Agency (ANR), project REVER n. ANR 11 INSE 007.
Chapter PDF
Similar content being viewed by others
References
Altenkirch, T., Grattage, J.: A functional quantum programming language. In: Proc. of LICS 2005 (2005)
Axelsen, H.B.: Clean Translation of an Imperative Reversible Programming Language. In: Knoop, J. (ed.) CC 2011. LNCS, vol. 6601, pp. 144–163. 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.: Notes on the history of reversible computation. IBM Journal of Research and Development 32(1) (1988)
Brown, A.B., Patterson, D.A.: Undo for operators: Building an undoable e-mail store. In: USENIX Annual Technical Conference, General Track. USENIX (2003)
Buhrman, H., Tromp, J., Vitányi, P.M.B.: Time and Space Bounds for Reversible Simulation. In: Yu, Y., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 1017–1027. Springer, Heidelberg (2001)
Danos, V., Krivine, J.: Reversible Communicating Systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004)
Danos, V., Regnier, L.: Reversible, irreversible and optimal lambda-machines. Theor. Comput. Sci. 227(1-2) (1999)
Field, J., Varela, C.A.: Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments. In: Proc. of POPL 2005. ACM (2005)
Frank, M.P.: Introduction to reversible computing: motivation, progress, and challenges. In: 2nd Conference on Computing Frontiers. ACM (2005)
Lanese, I., Mezzina, C.A., Schmitt, A., Stefani, J.B.: Controlling Reversibility in Higher-Order Pi. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011 – Concurrency Theory. LNCS, vol. 6901, pp. 297–311. Springer, Heidelberg (2011)
Lanese, I., Mezzina, C.A., Stefani, J.B.: Reversing Higher-Order Pi. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 478–493. Springer, Heidelberg (2010)
Leeman, G.B.: A formal approach to undo operations in programming languages. ACM Trans. Program. Lang. Syst. 8(1) (1986)
Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer (2008)
Ringenburg, M.F., Grossman, D.: AtomCaml: first-class atomicity via rollback. In: Proc. of ICFP 2005. ACM (2005)
Van Roy, P., Haridi, S.: Concepts, Techniques and Models of Computer Programming. MIT Press (2004)
Vitányi, P.M.B.: Time, space, and energy in reversible computing. In: 2nd Conference on Computing Frontiers. ACM (2005)
Yokoyama, T.: Reversible computation and reversible programming languages. Electr. Notes Theor. Comput. Sci. 253(6) (2010)
Yokoyama, T., Glück, R.: A reversible programming language and its invertible self-interpreter. In: Proc. of PEPM 2007. ACM (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Lienhardt, M., Lanese, I., Mezzina, C.A., Stefani, JB. (2012). A Reversible Abstract Machine and Its Space Overhead. In: Giese, H., Rosu, G. (eds) Formal Techniques for Distributed Systems. FMOODS FORTE 2012 2012. Lecture Notes in Computer Science, vol 7273. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30793-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-30793-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30792-8
Online ISBN: 978-3-642-30793-5
eBook Packages: Computer ScienceComputer Science (R0)