research-article

Open access

Closure conversion is safe for space

Authors:

Zoe Paraskevopoulou,

Andrew W. AppelAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 3, Issue ICFP

Article No.: 83, Pages 1 - 29

https://doi.org/10.1145/3341687

Published: 26 July 2019 Publication History

Abstract

We formally prove that closure conversion with flat environments for CPS lambda calculus is correct (preserves semantics) and safe for time and space, meaning that produced code preserves the time and space required for the execution of the source program.

We give a cost model to pre- and post-closure-conversion code by formalizing profiling semantics that keep track of the time and space resources needed for the execution of a program, taking garbage collection into account. To show preservation of time and space we set up a general, "garbage-collection compatible", binary logical relation that establishes invariants on resource consumption of the related programs, along with functional correctness. Using this framework, we show semantics preservation and space and time safety for terminating source programs, and divergence preservation and space safety for diverging source programs.

We formally prove that closure conversion with flat environments for CPS lambda calculus is correct (preserves semantics) and safe for time and space, meaning that produced code preserves the time and space required for the execution of the source program.

We give a cost model to pre- and post-closure-conversion code by formalizing profiling semantics that keep track of the time and space resources needed for the execution of a program, taking garbage collection into account. To show preservation of time and space we set up a general, "garbage-collection compatible", binary logical relation that establishes invariants on resource consumption of the related programs, along with functional correctness. Using this framework, we show semantics preservation and space and time safety for terminating source programs, and divergence preservation and space safety for diverging source programs.

This is the first formal proof of space-safety of a closure-conversion transformation. The transformation and the proof are parts of the CertiCoq compiler pipeline from Coq (Gallina) through CompCert Clight to assembly language. Our results are mechanized in the Coq proof assistant.

Supplementary Material

WEBM File (a83-paraskevopoulou.webm)

Download
115.14 MB

References

[1]

Elvira Albert, Samir Genaim, and Miguel Gómez-Zamalloa. 2010. Parametric Inference of Memory Requirements for Garbage Collected Languages. In Proceedings of the 2010 International Symposium on Memory Management (ISMM ’10). ACM, New York, NY, USA, 121–130.

Digital Library

[2]

Roberto M. Amadio and Yann Régis-Gianas. 2012. Certifying and Reasoning on Cost Annotations of Functional Programs. In Proceedings of the Second International Conference on Foundational and Practical Aspects of Resource Analysis (FOPARA’11). Springer-Verlag, Berlin, Heidelberg, 72–89.

Digital Library

[3]

Abhishek Anand, Andrew W. Appel, John Gregory Morrisett, Zoe Paraskevopoulou, Randy Pollack, Olivier Savary Bélanger, Matthieu Sozeau, and Matthew Weaver. 2017. CertiCoq : A verified compiler for Coq. In CoqPL’17: The Third International Workshop on Coq for Programming Languages. 2.

[4]

Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press, New York.

Digital Library

[5]

Andrew W. Appel and Marcelo J. R. Gonçalves. 1993. Hash-consing garbage collection. Technical Report CS-TR-412-93. Princeton University Department of Computer Science.

[6]

Andrew W. Appel and Trevor Jim. 1989. Continuation-Passing, Closure-Passing Style. In 16th ACM Symp. on Principles of Programming Languages. ACM Press, New York, 293–302.

Digital Library

[7]

Andrew W. Appel and Zhong Shao. 1996. Empirical and Analytic Study of Stack Versus Heap Cost for Languages with Closures. J. Funct. Program. 6 (01 1996), 47–74.

[8]

Frédéric Besson, Sandrine Blazy, and Pierre Wilke. 2017. CompCertS: A Memory-Aware Verified C Compiler using Pointer as Integer Semantics. In ITP 2017 - 8th International Conference on Interactive Theorem Proving (ITP 2017: Interactive Theorem Proving), Vol. 10499. Springer, Brasilia, Brazil, 81–97.

[9]

Quentin Carbonneaux, Jan Hoffmann, Tahina Ramananandro, and Zhong Shao. 2014. End-to-end Verification of Stack-space Bounds for C Programs. SIGPLAN Not. 49, 6 (June 2014), 270–281.

Digital Library

[10]

Ezgi Çiçek, Gilles Barthe, Marco Gaboardi, Deepak Garg, and Jan Hoffmann. 2017. Relational Cost Analysis. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). ACM, New York, NY, USA, 316–329.

Digital Library

[11]

Ezgi Çiçek, Zoe Paraskevopoulou, and Deepak Garg. 2016. A Type Theory for Incremental Computational Complexity with Control Flow Changes. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). ACM, New York, NY, USA, 132–145.

Digital Library

[12]

Ezgi Çiçek, Deepak Garg, and Umut Acar. 2015. Refinement Types for Incremental Computational Complexity. In Programming Languages and Systems, Jan Vitek (Ed.). Springer, Heidelberg, 406–431.

[13]

Karl Crary and Stephanie Weirich. 2000. Resource Bound Certification. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’00). ACM, New York, NY, USA, 184–198.

Digital Library

[14]

Amer Diwan, Eliot Moss, and Richard Hudson. 1992. Compiler Support for Garbage Collection in a Statically Typed Language. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation (PLDI ’92). ACM, New York, NY, USA, 273–282.

Digital Library

[15]

Vyacheslav Egorov. 2012. Grokking V8 closures for fun (and profit?). https://mrale.ph/blog/2012/09/23/grokking- v8- closuresfor- fun.html/ .

[16]

David Glasser. 2013. An interesting kind of JavaScript memory leak. https://blog.meteor.com/an- interesting- kind- ofjavascript- memory- leak- 8b47d2e7f156/ .

[17]

Jörgen Gustavsson and David Sands. 1999. A Foundation for Space-Safe Transformations of Call-by-Need Programs. Electronic Notes in Theoretical Computer Science 26 (1999), 69 – 86.

[18]

Jörgen Gustavsson and David Sands. 2001. Possibilities and Limitations of Call-by-need Space Improvement. In Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP ’01). ACM, New York, NY, USA, 265–276.

Digital Library

[19]

Jan Hoffmann, Ankush Das, and Shu-Chun Weng. 2017. Towards Automatic Resource Bound Analysis for OCaml. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2017). ACM, New York, NY, USA, 359–373.

Digital Library

[20]

Chung-Kil Hur and Derek Dreyer. 2011. A Kripke Logical Relation Between ML and Assembly. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). ACM, New York, NY, USA, 133–146.

Digital Library

[21]

Chung-Kil Hur, Derek Dreyer, Georg Neis, and Viktor Vafeiadis. 2012. The Marriage of Bisimulations and Kripke Logical Relations. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’12). ACM, New York, NY, USA, 59–72.

Digital Library

[22]

Steffen Jost, Kevin Hammond, Hans-Wolfgang Loidl, and Martin Hofmann. 2010. Static Determination of Quantitative Resource Usage for Higher-order Programs. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’10). ACM, New York, NY, USA, 223–236.

Digital Library

[23]

Andrew W. Keep, Alex Hearn, and R. Kent Dybvig. 2012. Optimizing Closures in O(0) Time. In Proceedings of the 2012 Annual Workshop on Scheme and Functional Programming (Scheme ’12). ACM, New York, NY, USA, 30–35.

Digital Library

[24]

Richard Kelsey and Paul Hudak. 1989. Realistic Compilation by Program Transformation. In 16th ACM Symp. on Principles of Programming Languages. ACM Press, New York, 281–92.

Digital Library

[25]

Ramana Kumar, Magnus O Myreen, Michael Norrish, and Scott Owens. 2014. CakeML: A Verified Implementation of ML. In POPL’14: 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 179–191.

Digital Library

[26]

Xavier Leroy. 2009. A Formally Verified Compiler Back-end. Journal of Automated Reasoning 43, 4 (2009), 363–446.

Digital Library

[27]

Andrew McCreight, Tim Chevalier, and Andrew Tolmach. 2010. A Certified Framework for Compiling and Executing Garbagecollected Languages. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming (ICFP ’10). ACM, New York, NY, USA, 273–284.

Digital Library

[28]

Yasuhiko Minamide. 1999. Space-Profiling Semantics of the Call-by-Value Lambda Calculus and the CPS Transformation. Electr. Notes Theor. Comput. Sci. 26 (1999), 105–120.

[29]

Greg Morrisett and Robert Harper. 1997. Semantics of Memory Management for Polymorphic Languages. In Higher Order Operational Techniques in Semantics, Publications of the Newton Institute. Cambridge University Press, 175–226.

Digital Library

[30]

Georg Neis, Chung-Kil Hur, Jan-Oliver Kaiser, Craig McLaughlin, Derek Dreyer, and Viktor Vafeiadis. 2015. Pilsner: A Compositionally Verified Compiler for a Higher-order Imperative Language. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming (ICFP 2015). ACM, New York, NY, USA, 166–178.

Digital Library

[31]

David Sands. 1992. Operational Theories of Improvement in Functional Languages. In Functional Programming, Glasgow 1991, Rogardt Heldal, Carsten Kehler Holst, and Philip Wadler (Eds.). Springer London, London, 298–311.

Digital Library

[32]

David Sands. 1998. Improvement Theory and Its Applications. In Higher Order Operational Techniques in Semantics, Andrew D. Gordon and Andrew M. Pitts (Eds.). Cambridge University Press, New York, NY, USA, 275–306. http: //dl.acm.org/citation.cfm?id=309656.309672

Digital Library

[33]

Olivier Savary Bélanger and Andrew W. Appel. 2017. Shrink Fast Correctly!. In PPDP’17: International Symposium on Principles and Practice of Declarative Programming. ACM Press, 49–60.

Digital Library

[34]

Zhong Shao and Andrew W. Appel. 1994. Space-efficient Closure Representations. In Proceedings of the 1994 ACM Conference on LISP and Functional Programming (LFP ’94). ACM, New York, NY, USA, 150–161.

Digital Library

[35]

Zhong Shao and Andrew W. Appel. 2000. Efficient and Safe-for-space Closure Conversion. ACM Trans. Program. Lang. Syst. 22, 1 (Jan. 2000), 129–161.

Digital Library

[36]

Leena Unnikrishnan and Scott D. Stoller. 2009. Parametric Heap Usage Analysis for Functional Programs. In Proceedings of the 2009 International Symposium on Memory Management (ISMM ’09). ACM, New York, NY, USA, 139–148.

Digital Library

[37]

Peng Wang, Di Wang, and Adam Chlipala. 2017. TiML: A Functional Language for Practical Complexity Analysis with Invariants. Proc. ACM Program. Lang. 1, OOPSLA, Article 79 (Oct. 2017), 26 pages.

Digital Library

Cited By

Sullivan ZDownen PAriola Z(2023)Closure Conversion in Little PiecesProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610622(1-13)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610622
Huang YYallop J(2023)Defunctionalization with Dependent TypesProceedings of the ACM on Programming Languages10.1145/35912417:PLDI(516-538)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591241
Moine ACharguéraud APottier F(2023)A High-Level Separation Logic for Heap Space under Garbage CollectionProceedings of the ACM on Programming Languages10.1145/35712187:POPL(718-747)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571218
Show More Cited By

Index Terms

Closure conversion is safe for space
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

Compiling with continuations, correctly

In this paper we present a novel simulation relation for proving correctness of program transformations that combines syntactic simulations and logical relations. In particular, we establish a new kind of simulation diagram that uses a small-step or big-...
Coinductive big-step operational semantics

Using a call-by-value functional language as an example, this article illustrates the use of coinductive definitions and proofs in big-step operational semantics, enabling it to describe diverging evaluations in addition to terminating evaluations. We ...
A Formalization of Strong Normalization for Simply-Typed Lambda-Calculus and System F

We formalize in the logical framework ATS/LF a proof based on Tait's method that establishes the simply-typed lambda-calculus being strongly normalizing. In this formalization, we employ higher-order abstract syntax to encode lambda-terms and an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 3, Issue ICFP

August 2019

1054 pages

EISSN:2475-1421

DOI:10.1145/3352468

Issue’s Table of Contents

Copyright © 2019 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2019

Published in PACMPL Volume 3, Issue ICFP

Check for updates

Badges

Artifacts Evaluated & Functional

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
552
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)24

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sullivan ZDownen PAriola Z(2023)Closure Conversion in Little PiecesProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610622(1-13)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610622
Huang YYallop J(2023)Defunctionalization with Dependent TypesProceedings of the ACM on Programming Languages10.1145/35912417:PLDI(516-538)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591241
Moine ACharguéraud APottier F(2023)A High-Level Separation Logic for Heap Space under Garbage CollectionProceedings of the ACM on Programming Languages10.1145/35712187:POPL(718-747)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571218
Liu SWang Y(2023)Verified Transformation of Continuation-Passing Style into Static Single Assignment FormTheoretical Aspects of Software Engineering10.1007/978-3-031-35257-7_2(20-37)Online publication date: 27-Jun-2023
https://doi.org/10.1007/978-3-031-35257-7_2
Zúñiga ABel-Enguix G(2022)On Coevaluation Behavior and EquivalenceMathematics10.3390/math1020380010:20(3800)Online publication date: 14-Oct-2022
https://doi.org/10.3390/math10203800
Maillard KLennon-Bertrand MTabareau NTanter É(2022)A reasonably gradual type theoryProceedings of the ACM on Programming Languages10.1145/35476556:ICFP(931-959)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547655
Accattoli BDal Lago UVanoni G(2022)Multi types and reasonable spaceProceedings of the ACM on Programming Languages10.1145/35476506:ICFP(799-825)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547650
Jacobs JBalzer SKrebbers R(2022)Multiparty GV: functional multiparty session types with certified deadlock freedomProceedings of the ACM on Programming Languages10.1145/35476386:ICFP(466-495)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547638
Ostermann KBinder DSkupin ISüberkrüb TDownen P(2022)Introduction and elimination, left and rightProceedings of the ACM on Programming Languages10.1145/35476376:ICFP(438-465)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547637
van der Rest CSwierstra W(2022)A completely unique account of enumerationProceedings of the ACM on Programming Languages10.1145/35476366:ICFP(411-437)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547636
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents