Compiling with continuations, or without? whatever.

Abstract

What makes a good compiler IR? In the context of functional languages, there has been an extensive debate on the advantages and disadvantages of continuation-passing-style (CPS). The consensus seems to be that some form of explicit continuations is necessary to model jumps in a functional style, but that they should have a 2nd-class status, separate from regular functions, to ensure efficient code generation. Building on this observation, a recent study from PLDI 2017 proposed a direct-style IR with explicit join points, which essentially represent local continuations, i.e., functions that do not return or escape. While this IR can work well in practice, as evidenced by the implementation of join points in the Glasgow Haskell Compiler (GHC), there still seems to be room for improvement, especially with regard to the way continuations are handled in the course of optimization.

In this paper, we contribute to the CPS debate by developing a novel IR with the following features. First, we integrate a control operator that resembles Felleisen’s C, eliminating certain redundant rewrites observed in the previous study. Second, we treat the non-returning and non-escaping aspects of continuations separately, allowing efficient compilation of well-behaved functions defined by the user. Third, we define a selective CPS translation of our IR, which erases control operators while preserving the meaning and typing of programs. These features enable optimizations in both direct style and full CPS, as well as in any intermediate style with selectively exposed continuations. Thus, we change the spectrum of available options from “CPS yes or no” to “as much or as little CPS as you want, when you want it”.

References

1. Keith Adams, Jason Evans, Bertrand Maher, Guilherme Ottoni, Andrew Paroski, Brett Simmers, Edwin Smith, and Owen Yamauchi. 2014. The HipHop Virtual Machine. In Proceedings of the 29th ACM International Conference on ObjectOriented Programming Systems Languages, and Applications (OOPSLA ’14). ACM, New York, NY, USA, 777–790.
2. Andrew W. Appel. 1992. Compiling with Continuations. Cambridge University Press.
3. Andrew W. Appel. 1998. SSA is Functional Programming. SIGPLAN Notices 33, 4 (1998), 17–20.
4. Kenichi Asai and Chihiro Uehara. 2018. Selective CPS transformation for shift and reset. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. ACM, 40–52.
5. Nick Benton, Andrew Kennedy, and George Russell. 1998. Compiling Standard ML to Java Bytecodes. In ICFP. ACM, 129–140.
6. Peter Nicholas Benton. 1993. Strictness Analysis of Lazy Functional Programs. Ph.D. Dissertation. University of Cambridge.
7. Cliff Click. 1995. Global code motion/global value numbering. ACM Sigplan Notices 30, 6 (1995), 246–257.
8. Oliver Danvy and Andrzex Filinski. 1992. Representing control: A study of the CPS transformation. Mathematical structures in computer science 2, 4 (1992), 361–391.
9. Paul Downen, Luke Maurer, Zena M. Ariola, and Simon Peyton Jones. 2016. Sequent calculus as a compiler intermediate language. In ICFP. ACM, 74–88.
10. Andrei P. Ershov. 1958. On programming of arithmetic operations. Commun. ACM 1, 8 (1958), 3–6.
11. Matthias Felleisen, Daniel P Friedman, Eugene Kohlbecker, and Bruce Duba. 1987. A syntactic theory of sequential control. Theoretical computer science 52, 3 (1987), 205–237.
12. Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The Essence of Compiling with Continuations. In PLDI. ACM, 237–247.
13. Prodromos Gerakios, Nikolaos Papaspyrou, and Konstantinos Sagonas. 2014. Static safety guarantees for a low-level multithreaded language with regions. Science of Computer Programming 80 (2014), 223–263.
14. Jean-Yves Girard, Paul Taylor, and Yves Lafont. 1989. Proofs and types. Vol. 7. Cambridge University Press.
15. Tomas Kalibera, Petr Maj, Floréal Morandat, and Jan Vitek. 2014. A fast abstract syntax tree interpreter for R. In Proceedings of the 10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE ’14). ACM, New York, NY, USA, 89–102.
16. Richard Kelsey. 1995. A Correspondence between Continuation Passing Style and Static Single Assignment Form. In Intermediate Representations Workshop. ACM, 13–23.
17. Andrew Kennedy. 2007. Compiling with continuations, continued. In ICFP. ACM, 177–190.
18. David A. Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak, and James Philbin. 1986a. ORBIT: an optimizing compiler for scheme. In SIGPLAN Symposium on Compiler Construction. ACM, 219–233.
19. David A. Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak, James Philbin, and Norman Adams. 1986b. Orbit: an optimizing compiler for scheme (with retrospective). In Best of PLDI. ACM, 175–191.
20. Luke Maurer, Paul Downen, Zena M. Ariola, and Simon L. Peyton Jones. 2017. Compiling without continuations. In PLDI. ACM, 482–494.
21. Floréal Morandat, Brandon Hill, Leo Osvald, and Jan Vitek. 2012. Evaluating the Design of the R Language: Objects and Functions for Data Analysis. In ECOOP 2012 — Object-Oriented Programming: 26th European Conference. Proceedings (Lecture Notes in Computer Science). Springer Berlin Heidelberg, Germany, 104–131.
22. Lasse R Nielsen et al. 2001. A selective CPS transformation. Electronic Notes in Theoretical Computer Science 45 (2001), 311–331.
23. Chris Okasaki, Peter Lee, and David Tarditi. 1994. Call-by-need and continuation-passing style. Lisp and Symbolic Computation 7, 1 (1994), 57–81.
24. Leo Osvald, Grégory M. Essertel, Xilun Wu, Lilliam I. González Alayón, and Tiark Rompf. 2016. Gentrification gone too far? affordable 2nd-class values for fun and (co-)effect. In OOPSLA. ACM, 234–251.
25. Simon L. Peyton Jones and Simon Marlow. 2002. Secrets of the Glasgow Haskell Compiler inliner. J. Funct. Program. 12, 4&5 (2002), 393–433.
26. Jose M. Redondo and Francisco Ortin. 2013. Efficient support of dynamic inheritance for class- and prototype-based languages. Journal of Systems and Software 86, 2 (2013), 278–301.
27. John Reppy. 2001. Local CPS conversion in a direct-style compiler. In Proceedings of the Third ACM SIGPLAN Workshop on Continuations (CW ’01). 13–22.
28. Tiark Rompf. 2012. Lightweight Modular Staging and Embedded Compilers: Abstraction Without Regret for High-Level High-Performance Programming. Ph.D. Dissertation. EPFL.
29. Tiark Rompf. 2016. The Essence of Multi-stage Evaluation in LMS. In A List of Successes That Can Change the World (Lecture Notes in Computer Science), Vol. 9600. Springer, 318–335.
30. Tiark Rompf, Ingo Maier, and Martin Odersky. 2009. Implementing first-class polymorphic delimited continuations by a type-directed selective CPS-transform. In ACM Sigplan Notices, Vol. 44. ACM, 317–328.
31. Tiark Rompf and Martin Odersky. 2010. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. In Conference on Generative programming and component engineering (GPCE). 127–136.
32. Tiark Rompf, Arvind K. Sujeeth, Nada Amin, Kevin Brown, Vojin Jovanovic, HyoukJoong Lee, Manohar Jonnalagedda, Kunle Olukotun, and Martin Odersky. 2013. Optimizing Data Structures in High-Level Programs (POPL).
33. Guy L. Steele, Jr. 1978. Rabbit: A compiler for Scheme. Technical Report. Massachusetts Institute of Technology.
34. Andrew K Wright and Matthias Felleisen. 1994. A syntactic approach to type soundness. Information and computation 115, 1 (1994), 38–94.

Index Terms

• Hardware

  • Electronic design automation

    • Hardware description languages and compilation

• Theory of computation

  • Semantics and reasoning

    • Program constructs

      • Control primitives

      • Functional constructs