Abstract
Abstract garbage collection and the use of pushdown systems each enhance the precision of control-flow analysis (CFA). However, their respective needs conflict: abstract garbage collection requires the stack but pushdown systems obscure it. Though several existing techniques address this conflict, none take full advantage of the underlying interplay. In this paper, we dissolve this conflict with a technique which exploits the precision of pushdown systems to decompose the heap across the continuation.This technique liberates abstract garbage collection from the stack, increasing its effectiveness and the compositionality of its host analysis. We generalize our approach to apply compositional treatment to abstract timestamps which induces the context abstraction of m-CFA, an abstraction more precise than k-CFA’s for many common programming patterns.
Chapter PDF
Similar content being viewed by others
References
Darais, D., Labich, N., Nguyen, P.C., Van Horn, D.: Abstracting definitional interpreters (functional pearl). Proceedings of the ACM on Programming Languages 1(ICFP), 12:1–12:25 (Aug 2017). https://doi.org/10.1145/3110256
Dillig, I., Dillig, T., Aiken, A., Sagiv, M.: Precise and compact modular procedure summaries for heap manipulating programs. In: Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 567–577. PLDI ’11, ACM, New York, NY, USA (2011). https://doi.org/10.1145/1993498.1993565
Earl, C., Might, M., Van Horn, D.: Pushdown control-flow analysis of higher order programs. Workshop on Scheme and Functional Programming (2010)
Earl, C., Sergey, I., Might, M., Van Horn, D.: Introspective pushdown analysis of higher-order programs. In: Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming. pp. 177–188. ICFP ’12, ACM, New York, NY, USA (Sep 2012). https://doi.org/10.1145/2364527.2364576
Flanagan, C., Sabry, A., Duba, B.F., Felleisen, M.: The essence of compiling with continuations. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. pp. 237–247. PLDI ’93, ACM, New York, NY, USA (1993). https://doi.org/10.1145/155090.155113
Gilray, T., Lyde, S., Adams, M.D., Might, M., Van Horn, D.: Pushdown control-flow analysis for free. In: Proceedings of the 43rd Annual ACMSIGPLAN-SIGACT Symposium on Principles of Programming Languages. pp.691–704. POPL ’16, ACM, New York, NY, USA (Jan 2016). https://doi.org/10.1145/2837614.2837631
Johnson, J.I., Sergey, I., Earl, C., Might, M., Van Horn, D.: Pushdown flow analysis with abstract garbage collection. Journal of Functional Programming 24, 218–283 (May 2014). https://doi.org/10.1017/s0956796814000100
Johnson, J.I., Van Horn, D.: Abstracting abstract control. In: Proceedings of the 10th ACM Symposium on Dynamic Languages. pp. 11–22. DLS ’14, ACM, New York, NY, USA (Oct 2014). https://doi.org/10.1145/2661088.2661098
Jones, N.D.: Flow analysis of lambda expressions. In: International Colloquium on Automata, Languages, and Programming. pp. 114–128. Springer (1981)Jones, N.D.: Flow analysis of lambda expressions. In: International Colloquium on Automata, Languages, and Programming. pp. 114–128. Springer (1981)
Might, M., Shivers, O.: Improving flow analyses via \(\varGamma \)CFA: abstract garbage collection and counting. In: Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming. pp. 13–25. ICFP ’06, ACM, New York, NY, USA (Sep 2006). https://doi.org/10.1145/1159803.1159807
Might, M., Smaragdakis, Y., Van Horn, D.: Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis. In: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 305–315. PLDI ’10, ACM, New York, NY, USA (Jun 2010). https://doi.org/10.1145/1806596.1806631
Peng, F.: \(h\)-CFA: A simplified approach for pushdown control flow analysis. Master’s thesis, The University of Wisconsin-Milwaukee (2016)
Reynolds, J.C.: Definitional interpreters for Higher-Order programming languages. Higher-Order and Symbolic Computation 11(4), 363–397(1998)
Shivers, O.: Control-Flow Analysis of Higher-Order Languages. Ph.D. thesis,Carnegie Mellon University, Pittsburgh, PA, USA (1991)
Van Horn, D., Might, M.: Abstracting abstract machines. In: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming. pp. 51–62. ICFP ’10, ACM, New York, NY, USA (Sep 2010). https://doi.org/10.1145/1863543.1863553
Vardoulakis, D., Shivers, O.: CFA2: A context-free approach to control-flow analysis. In: Gordon, A.D. (ed.) Programming Languages and Systems. pp. 570–589. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)
Vardoulakis, D., Shivers, O.: CFA2: a context-free approach to control-flow analysis. Logical Methods in Computer Science 7(2) (2011). https://doi.org/10.2168/LMCS-7(2:3)2011
Wei, G., Decker, J., Rompf, T.: Refunctionalization of abstract abstract machines: bridging the gap between abstract abstract machines and abstract definitional interpreters (functional pearl). Proceedings of the ACM on Programming Languages 2(ICFP), 105:1–105:28 (Jul 2018). https://doi.org/10.1145/3236800
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Germane, K., Adams, M.D. (2020). Liberate Abstract Garbage Collection from the Stack by Decomposing the Heap. In: Müller, P. (eds) Programming Languages and Systems. ESOP 2020. Lecture Notes in Computer Science(), vol 12075. Springer, Cham. https://doi.org/10.1007/978-3-030-44914-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-44914-8_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44913-1
Online ISBN: 978-3-030-44914-8
eBook Packages: Computer ScienceComputer Science (R0)