Abstract
This paper presents FCore: a JVM implementation of System F with support for full tail-call elimination (TCE). Our compilation technique for FCore is innovative in two respects: it uses a new representation for first-class functions called imperative functional objects; and it provides a way to do TCE on the JVM using constant space.
Unlike conventional TCE techniques on the JVM, allocated function objects are reused in chains of tail calls. Thus, programs written in FCore can use idiomatic functional programming styles, relying on TCE, and perform well without worrying about the JVM limitations. Our empirical results show that programs which use tail calls can run in constant space and with low execution time overhead when compiled with FCore.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
FCore code repository: https://github.com/hkuplg/fcore.
References
Abelson, H., Dybvig, R., Haynes, C., Rozas, G., Adams, N.I.I., Friedman, D., Kohlbecker, E., Steele, G.L., Bartley, D., Halstead, R., Oxley, D., Sussman, G., Brooks, G., Hanson, C., Pitman, K., Wand, M.: Revised\(^{5}\) report on the algorithmic language scheme. High.-Order Symbolic Comput. 11(1), 7–105 (1998)
Armstrong, J.: Programming Erlang: Software for a Concurrent World, p. 536. Pragmatic Bookshelf, Raleigh (2007)
Baker, H.G.: CONS should not CONS its arguments, part II. ACM SIGPLAN Not. 30(9), 17–20 (1995)
Benton, N., Kennedy, A., Russell, G.: Compiling Standard ML to Java Bytecodes. In: Proceedings of the 3rd ACM SIGPLAN International Conference on Functional Programming (1998)
Bogdanas, D., Roşu, G.: K-Java: a complete semantics of Java. In: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 445–456. POPL 2015, ACM, New York, NY, USA (2015)
Choi, K., Lim, H., Han, T.: Compiling lazy functional programs based on the spineless tagless G-machine for the java virtual machine. In: Kuchen, H., Ueda, K. (eds.) FLOPS 2001. LNCS, vol. 2024, pp. 92–107. Springer, Heidelberg (2001)
Clements, J., Felleisen, M.: A tail-recursive machine with stack inspection. ACM Transactions on Programming Languages and Systems 26(6), 1029–1052 (2004)
Friberg, S., Shipilev, A., Astrand, A., Kuksenko, S., Loef, H.: OpenJDK: JMH (2014). openjdk.java.net/projects/code-tools/jmh/
Girard, J.Y.: Interprétation fonctionnelle et élimination des coupures de l’arithmétique d’ordre supérieur. Ph.D. thesis, Université Paris VII (1972)
Hickey, R.: The Clojure programming language. In: Proceedings of the 2008 Symposium on Dynamic Languages (2008)
Hickey, R.: Recur construct, Clojure documentation (2014). clojuredocs.org/clojure.core/recur
Kennedy, A., Syme, D.: Transposing F to C#: expressivity of parametric polymorphism in an object-oriented language. Concurrency Comput. Pract. Experience 16(7), 707–733 (2004)
Krishnamurthi, S.: Educational pearl: automata via macros. J. Funct. Program. 16(3), 253–267 (2006)
League, C., Trifonov, V., Shao, Z.: Functional java bytecode. Proceedings 5th World Conference on Systemics, Cybernetics, and Informatics (2001)
Minamide, Y.: Selective tail call elimination. In: Proceedings of the 10th International Conference on Static Analysis (2003)
Odersky, M.: The scala language specification, Version 2.9. École Polytechnique Fédérale de Lausanne (2014)
O’Hair, K.: HPROF: a Heap/CPU profiling tool in J2SE 5.0. Sun Developer Network, Developer Technical Articles & Tips (2004)
Reynolds, J.C.: Towards a theory of type structure. In: Symposium on Programming (1974)
Schinz, M., Odersky, M.: Tail call elimination on the Java Virtual Machine. Electron. Notes Theor. Comput. Sci. 59(1), 158–171 (2001)
Schwaighofer, A.: Tail Call Optimization in the Java HotSpot™VM, master Thesis, Johannes Kepler Universität Linz (2009)
Shao, Z., Appel, A.W.: Space-efficient closure representations. ACM SIGPLAN Lisp Pointers 7(3), 150–161 (1994)
Steele, G.L.: Debunking the “Expensive Procedure Call” myth or, procedure call implementations considered harmful or, LAMDBA: the ultimate GOTO. In: Proceedings of the 1977 Annual Conference (1977)
Steele, G.L.: Rabbit: a compiler for scheme. Technical report, Massachusetts Institute of Technology (1978)
Tismer, C.: Continuations and stackless Python. In: Proceedings of the 8th International Python Conference, vol. 1 (2000)
Tullsen, M.: Compiling Haskell to Java. Technical Report YALEU/DCS/RR-1204, Yale University (1996)
Wadsworth, C.: Semantics and Pragmatics of the Lambda-Calculus. Ph.D. thesis, University of Oxford (1971)
Wakeling, D.: Compiling lazy functional programs for the Java Virtual Machine. J. Funct. Program. 9(6), 579–603 (1999)
Wechsung, I.: Frege (2014). github.com/Frege/frege
Würthinger, T., Wimmer, C., Wöß, A., Stadler, L., Duboscq, G., Humer, C., Richards, G., Simon, D., Wolczko, M.: One VM to rule them all. In: Proceedings of the 2013 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software (2013)
Acknowledgments
We would like to thank T. H. Tse, C.-L. Wang, Vlad Urechte, Rúnar Bjarnason, and FCore contributors for help and valuable feedback on previous drafts of this work. We also thank the anonymous reviewers for their helpful suggestions. The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. HKU 27200514).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Tauber, T. et al. (2015). Memory-Efficient Tail Calls in the JVM with Imperative Functional Objects. In: Feng, X., Park, S. (eds) Programming Languages and Systems. APLAS 2015. Lecture Notes in Computer Science(), vol 9458. Springer, Cham. https://doi.org/10.1007/978-3-319-26529-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-26529-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26528-5
Online ISBN: 978-3-319-26529-2
eBook Packages: Computer ScienceComputer Science (R0)