Document Open Access Logo

What If We Don't Pop the Stack? The Return of 2nd-Class Values

Authors Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, Tiark Rompf

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2022.15.pdf
  • Filesize: 1.16 MB
  • 29 pages

Document Identifiers

Author Details

Anxhelo Xhebraj
  • Purdue University, West Lafayette, IN, USA
Oliver Bračevac
  • Purdue University, West Lafayette, IN, USA
Guannan Wei
  • Purdue University, West Lafayette, IN, USA
Tiark Rompf
  • Purdue University, West Lafayette, IN, USA

Funding

This work was supported in part by NSF awards 1553471, 1564207, 1918483, 1910216, and DOE award DE-SC0018050.

Acknowledgements

We thank the anonymous reviewers for their insightful comments.

Cite As Get BibTex

Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf. What If We Don't Pop the Stack? The Return of 2nd-Class Values. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 15:1-15:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECOOP.2022.15

Abstract

Using a stack for managing the local state of procedures as popularized by Algol is a simple but effective way to achieve a primitive form of automatic memory management. Hence, the call stack remains the backbone of most programming language runtimes to the present day. However, the appealing simplicity of the call stack model comes at the price of strictly enforced limitations: since every function return pops the stack, it is difficult to return stack-allocated data from a callee upwards to its caller - especially variable-size data such as closures.
This paper proposes a solution by introducing a small tweak to the usual stack semantics. We design a type system that tracks the underlying storage mode of values, and when a function returns a stack-allocated value, we just don't pop the stack! Instead, the stack frame is de-allocated together with a parent the next time a heap-allocated value or primitive is returned. We identify a range of use cases where this delayed-popping strategy is beneficial, ranging from closures to trait objects to other types of variable-size data. Our evaluation shows that this execution model reduces heap and GC pressure and recovers spatial locality of programs improving execution time between 10% and 25% with respect to standard execution.

Subject Classification

ACM Subject Classification
  • Software and its engineering → General programming languages
Keywords
  • Call stack
  • closures
  • stack allocation
  • memory management
  • 2nd-class values
  • capabilities
  • effects

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Mads Sig Ager, Dariusz Biernacki, Olivier Danvy, and Jan Midtgaard. A functional correspondence between evaluators and abstract machines. In PPDP, pages 8-19. ACM, 2003. URL: https://doi.org/10.1145/888251.888254.
  2. Nada Amin, Samuel Grütter, Martin Odersky, Tiark Rompf, and Sandro Stucki. The essence of dependent object types. In A List of Successes That Can Change the World, volume 9600 of Lecture Notes in Computer Science, pages 249-272. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-30936-1_14.
  3. Nada Amin and Tiark Rompf. Type soundness proofs with definitional interpreters. In POPL, pages 666-679. ACM, 2017. URL: https://doi.org/10.1145/3009837.3009866.
  4. Andrew W. Appel. Garbage collection can be faster than stack allocation. Inf. Process. Lett., 25(4):275-279, 1987. URL: https://doi.org/10.1016/0020-0190(87)90175-X.
  5. Andrew W. Appel and Zhong Shao. Empirical and analytic study of stack versus heap cost for languages with closures. J. Funct. Program., 6(1):47-74, 1996. URL: https://doi.org/10.1017/S095679680000157X.
  6. Apple Inc. Closures - The Swift Programming Language (Swift 5.4), May 2021. URL: https://web.archive.org/web/20220501162412/https://docs.swift.org/swift-book/LanguageGuide/Closures.html.
  7. Kenichi Asai and Chihiro Uehara. Selective CPS transformation for shift and reset. In PEPM, pages 40-52. ACM, 2018. URL: https://doi.org/10.1145/3162069.
  8. Henry G. Baker. CONS should not CONS its arguments, part II: Cheney on the M.T.A. ACM SIGPLAN Notices, 30(9):17-20, September 1995. URL: https://doi.org/10.1145/214448.214454.
  9. Anindya Banerjee and David A. Schmidt. Stackability in the simply-typed call-by-value lambda calculus. Sci. Comput. Program., 31(1):47-73, 1998. URL: https://doi.org/10.1016/S0167-6423(96)00040-8.
  10. Yuyan Bao, Guannan Wei, Oliver Bračevac, Yuxuan Jiang, Qiyang He, and Tiark Rompf. Reachability types: tracking aliasing and separation in higher-order functional programs. Proc. ACM Program. Lang., 5(OOPSLA):1-32, 2021. URL: https://doi.org/10.1145/3485516.
  11. Friedrich L. Bauer. The cellar principle of state transition and storage allocation. IEEE Ann. Hist. Comput., 12(1):41-49, 1990. URL: https://doi.org/10.1109/MAHC.1990.10004.
  12. Daniel M. Berry. Block structure: Retention or deletion? (extended abstract). In STOC, pages 86-100. ACM, 1971. URL: https://doi.org/10.1145/800157.805041.
  13. Malgorzata Biernacka and Olivier Danvy. A concrete framework for environment machines. ACM Trans. Comput. Log., 9(1):6, 2007. URL: https://doi.org/10.1145/1297658.1297664.
  14. Stephen M. Blackburn and Kathryn S. McKinley. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In PLDI, pages 22-32. ACM, 2008. URL: https://doi.org/10.1145/1375581.1375586.
  15. Aleksander Boruch-Gruszecki, Jonathan Immanuel Brachthäuser, Edward Lee, Ondrej Lhoták, and Martin Odersky. Tracking captured variables in types. CoRR, abs/2105.11896, 2021. URL: http://arxiv.org/abs/2105.11896.
  16. Jonathan Immanuel Brachthäuser, Philipp Schuster, Edward Lee, and Aleksander Boruch-Gruszecki. Effects, capabilities, and boxes: from scope-based reasoning to type-based reasoning and back. Proc. ACM Program. Lang., 6(OOPSLA):1-30, 2022. URL: https://doi.org/10.1145/3527320.
  17. Jonathan Immanuel Brachthäuser, Philipp Schuster, and Klaus Ostermann. Effects as capabilities: effect handlers and lightweight effect polymorphism. Proc. ACM Program. Lang., 4(OOPSLA):126:1-126:30, 2020. URL: https://doi.org/10.1145/3428194.
  18. Dave Clarke, Johan Östlund, Ilya Sergey, and Tobias Wrigstad. Ownership types: A survey. In Aliasing in Object-Oriented Programming, volume 7850 of Lecture Notes in Computer Science, pages 15-58. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36946-9_3.
  19. Youyou Cong, Leo Osvald, Grégory M. Essertel, and Tiark Rompf. Compiling with continuations, or without? whatever. Proc. ACM Program. Lang., 3(ICFP):79:1-79:28, 2019. URL: https://doi.org/10.1145/3341643.
  20. Olivier Danvy. Defunctionalized interpreters for programming languages. In ICFP, pages 131-142. ACM, 2008. URL: https://doi.org/10.1145/1411204.1411206.
  21. Olivier Danvy and Andrzej Filinski. Abstracting control. In LISP and Functional Programming, pages 151-160. ACM, 1990. URL: https://doi.org/10.1145/91556.91622.
  22. Olivier Danvy and Lasse R. Nielsen. Defunctionalization at work. In PPDP, pages 162-174. ACM, 2001. URL: https://doi.org/10.1145/773184.773202.
  23. Edsger W. Dijkstra. Recursive Programming. Numerische Mathematik, 2(1):312-318, December 1960. URL: https://doi.org/10.1007/BF01386232.
  24. Michael J. Fischer. Lambda calculus schemata. In Proving Assertions About Programs, pages 104-109. ACM, 1972. URL: https://doi.org/10.1145/800235.807077.
  25. Jeffrey S. Foster, Manuel Fähndrich, and Alexander Aiken. A theory of type qualifiers. In PLDI, pages 192-203. ACM, 1999. URL: https://doi.org/10.1145/301618.301665.
  26. Free Software Foundation, Inc. The GNU C Library-Obstacks, 2003. URL: https://web.archive.org/web/20220509075117/https://www.gnu.org/software/libc/manual/html_node/Obstacks.html/.
  27. Michael P. Georgeff. Transformations and reduction strategies for typed lambda expressions. ACM Trans. Program. Lang. Syst., 6(4):603-631, 1984. URL: https://doi.org/10.1145/1780.1803.
  28. Brendan Gregg. Linux Perf Examples, 2020. URL: https://web.archive.org/web/20220509003430/https://www.brendangregg.com/perf.html.
  29. Sten Henriksson. A brief history of the stack. In SIGCIS Workshop, 2009. Google Scholar
  30. Jane Street. Memory management, 2022. URL: https://web.archive.org/web/20220401080322/https://signalsandthreads.com/memory-management/.
  31. Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. RustBelt: securing the foundations of the rust programming language. Proc. ACM Program. Lang., 2(POPL):66:1-66:34, 2018. URL: https://doi.org/10.1145/3158154.
  32. Peter J. Landin. Correspondence between ALGOL 60 and Church’s Lambda-notation: part I. Commun. ACM, 8(2):89-101, 1965. URL: https://doi.org/10.1145/363744.363749.
  33. James R. Larus. Restructuring Symbolic Programs for Concurrent Execution on Multiprocessors. PhD thesis, California Univ., Berkeley, Dept. of Electrical Engineering and Computer Sciences, May 1989. Google Scholar
  34. Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75-88. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/CGO.2004.1281665.
  35. Daan Leijen and Erik Meijer. Domain specific embedded compilers. In DSL, pages 109-122. ACM, 1999. Google Scholar
  36. Microsoft. C♯ language reference - stackalloc expression, 2022. URL: https://web.archive.org/web/20220405070936/https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/stackalloc.
  37. James S. Miller and Guillermo Juan Rozas. Garbage collection is fast, but a stack is faster. Technical report, Massachusetts Institute of Technology, 1994. Google Scholar
  38. James H. Morris. A bonus from van Wijngaarden’s device. Commun. ACM, 15(8):773, August 1972. URL: https://doi.org/10.1145/361532.361558.
  39. Joel Moses. The function of FUNCTION in LISP, or why the FUNARG problem should be called the environment problem. Technical report, Massachusetts Institute of Technology, USA, 1970. URL: http://hdl.handle.net/1721.1/5854.
  40. Lasse R. Nielsen. A selective CPS transformation. In MFPS, volume 45 of Electronic Notes in Theoretical Computer Science, pages 311-331. Elsevier, 2001. URL: https://doi.org/10.1016/S1571-0661(04)80969-1.
  41. James Noble, Jan Vitek, and John Potter. Flexible alias protection. In ECOOP, volume 1445 of Lecture Notes in Computer Science, pages 158-185. Springer, 1998. URL: https://doi.org/10.1007/BFb0054091.
  42. OCaml Community. OCaml discourse: Add support for stack allocation, 2021. URL: https://web.archive.org/web/20210125181231/https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039.
  43. Martin Odersky, Aleksander Boruch-Gruszecki, Jonathan Immanuel Brachthäuser, Edward Lee, and Ondrej Lhoták. Safer exceptions for scala. In SCALA@SPLASH, pages 1-11. ACM, 2021. URL: https://doi.org/10.1145/3486610.3486893.
  44. Martin Odersky, Christoph Zenger, and Matthias Zenger. Colored local type inference. In POPL, pages 41-53. ACM, 2001. URL: https://doi.org/10.1145/360204.360207.
  45. Leo Osvald, Grégory M. Essertel, Xilun Wu, Lilliam I. González Alayón, and Tiark Rompf. Gentrification gone too far? affordable 2nd-class values for fun and (co-)effect. In OOPSLA, pages 234-251. ACM, 2016. URL: https://doi.org/10.1145/2983990.2984009.
  46. Leo Osvald and Tiark Rompf. Rust-like borrowing with 2nd-class values (short paper). In SCALA@SPLASH, pages 13-17. ACM, 2017. URL: https://doi.org/10.1145/3136000.3136010.
  47. John C. Reynolds. The discoveries of continuations. LISP and Symbolic Computation, 6(3):233-247, November 1993. URL: https://doi.org/10.1007/BF01019459.
  48. Tiark Rompf and Nada Amin. Type soundness for dependent object types (DOT). In OOPSLA, pages 624-641. ACM, 2016. URL: https://doi.org/10.1145/2983990.2984008.
  49. Tiark Rompf, Ingo Maier, and Martin Odersky. Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform. In ICFP, pages 317-328. ACM, 2009. URL: https://doi.org/10.1145/1596550.1596596.
  50. Denys Shabalin. Scala native, 2015. URL: https://web.archive.org/web/20220318165107/https://scala-native.readthedocs.io/en/latest/.
  51. Amir Shaikhha, Andrew W. Fitzgibbon, Simon Peyton Jones, and Dimitrios Vytiniotis. Destination-passing style for efficient memory management. In FHPC@ICFP, pages 12-23. ACM, 2017. URL: https://doi.org/10.1145/3122948.3122949.
  52. Jeremy Siek. Type Safety in Three Easy Lemmas, 2013. URL: https://web.archive.org/web/20220308042857/https://siek.blogspot.com/2013/05/type-safety-in-three-easy-lemmas.html.
  53. Swift Community. Use stack allocation for Swift closures #21933. URL: https://github.com/apple/swift/pull/21933/#issuecomment-454980737.
  54. Simon Tatham. Coroutines in C, 2000. URL: https://web.archive.org/web/20220428071140/https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html.
  55. Mads Tofte and Jean-Pierre Talpin. Implementation of the typed call-by-value λ-calculus using a stack of regions. In POPL, pages 188-201. ACM Press, 1994. URL: https://doi.org/10.1145/174675.177855.
  56. Mads Tofte and Jean-Pierre Talpin. Region-based memory management. Inf. Comput., 132(2):109-176, 1997. URL: https://doi.org/10.1006/inco.1996.2613.
  57. Fei Wang, James M. Decker, Xilun Wu, Grégory M. Essertel, and Tiark Rompf. Backpropagation with callbacks: Foundations for efficient and expressive differentiable programming. In NeurIPS, pages 10201-10212, 2018. Google Scholar
  58. Fei Wang, Daniel Zheng, James M. Decker, Xilun Wu, Grégory M. Essertel, and Tiark Rompf. Demystifying differentiable programming: shift/reset the penultimate backpropagator. Proc. ACM Program. Lang., 3(ICFP):96:1-96:31, 2019. URL: https://doi.org/10.1145/3341700.
  59. Aaron Weiss, Olek Gierczak, Daniel Patterson, Nicholas D. Matsakis, and Amal Ahmed. Oxide: The Essence of Rust. arXiv:1903.00982 [cs], August 2020. URL: http://arxiv.org/abs/1903.00982.
  60. Andrew K. Wright and Matthias Felleisen. A syntactic approach to type soundness. Inf. Comput., 115(1):38-94, 1994. URL: https://doi.org/10.1006/inco.1994.1093.
  61. Anxhelo Xhebraj, Oliver Bračevac, Guannan Wei, and Tiark Rompf. What if we don't pop the stack? The return of 2nd-class values (extended version). Technical report, Purdue University, 2022. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact