Andrew Kennedy
ABSTRACT
We present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the benefits most clearly: in ANF-based languages, inlining involves a re-normalization step that rearranges let expressions and possibly introduces a new 'join point' function, and in monadic languages, commuting conversions must be applied; in contrast, inlining in our CPS language is a simple substitution of variables for variables.
We present a contification transformation implemented by simple rewrites on the intermediate language. Exceptions are modelled using so-called 'double-barrelled' CPS. Subtyping on exception constructors then gives a very straightforward effect analysis for exceptions. We also show how a graph-based representation of CPS terms can be implemented extremely efficiently, with linear-time term simplification.
- Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992. Google Scholar
Digital Library
- Andrew W. Appel. SSA is functional programming. SIGPLAN Notices, 33 (4): 17--20, 1998. Google ScholarDigital Library
- Andrew W. Appel and Trevor Jim. Shrinking lambda expressions in linear time. Journal of Functional Programming, 7 (5): 515--540, 1997. Google ScholarDigital Library
- Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1998. Google ScholarDigital Library
- Nick Benton and Peter Buchlovsky. Semantics of an effect analysis for exceptions. In ACM SIGPLAN International Workshop on Types in Language Design and Implementation (TLDI), pages 15--26, 2007. Google ScholarDigital Library
- Nick Benton and Andrew Kennedy. Exceptional syntax. Journal of Functional Programming, 11 (4): 395--410, 2001. Google ScholarDigital Library
- Nick Benton, Andrew Kennedy, and George Russell. Compiling Standard ML to Java bytecodes. In 3rd ACM SIGPLAN International Conference on Functional Programming. ACM Press, September 1998. Google ScholarDigital Library
- Nick Benton, Andrew Kennedy, Sam Lindley, and Claudio Russo. Shrinking reductions in SML.NET. In 16th International Workshop on Implementation and Application of Functional Languages (IFL), 2004. Google ScholarDigital Library
- Nick Benton, Andrew Kennedy, and Claudio Russo. Adventures in interoperability: The SML.NET experience. In 6th International Conference on Principles and Practice of Declarative Programming (PPDP), 2004. Google ScholarDigital Library
- Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, second edition, 2001. Google ScholarDigital Library
- Olivier Danvy. A new one-pass transformation into monadic normal form. In 12th International Conference on Compiler Construction (CC'03), 2003. Google ScholarDigital Library
- Olivier Danvy and Andrzej Filinski. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science, 2 (4): 361--391, 1992.Google ScholarCross Ref
- Olivier Danvy and Lasse R. Nielsen. A first-order one-pass CPS transformation. Theor. Comput. Sci., 308 (1-3): 239--257, 2003. Google ScholarDigital Library
- Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. The essence of compiling with continuations (with retrospective). In McKinley (2004), pages 502--514.Google Scholar
- Matthew Fluet and Stephen Weeks. Contification using dominators. In ICFP'01: Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming, pages 2--13. ACM Press, September 2001. Google ScholarDigital Library
- John Hatcliff and Olivier Danvy. A generic account of continuation-passing styles. In Principles of Programming Languages (POPL), pages 458--471, 1994. Google ScholarDigital Library
- Haim Kaplan, Nira Shafrir, and Robert E. Tarjan. Union-find with deletions. In SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 19--28, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. ISBN 0-89871-513-X. Google ScholarDigital Library
- Richard Kelsey. A correspondence between continuation passing style and static single assignment form. In Intermediate Representations Workshop, pages 13--23, 1995. Google ScholarDigital Library
- Richard A. Kelsey and Paul Hudak. Realistic compilation by program transformation. In Principles of Programming Languages (POPL). ACM, January 1989. Google ScholarDigital Library
- Jung-taek Kim, Kwangkeun Yi, and Olivier Danvy. Assessing the overhead of ML exceptions by selective CPS transformation. In ACM SIGPLAN Workshop on ML, pages 112--119, 1998. Also appears as BRICS technical report RS-98-15.Google Scholar
- David A. Kranz, Richard A. Kelsey, Jonathan A. Rees, Paul Hudak, and James Philbin. ORBIT: an optimizing compiler for scheme. In Proceedings of the ACM SIGPLAN symposium on Compiler Construction, pages 219--233, June 1986. Google ScholarDigital Library
- Sam Lindley. Normalisation by evaluation in the compilation of typed functional programming languages. PhD thesis, University of Edinburgh, 2005.Google Scholar
- Kathryn S. McKinley, editor. 20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979--1999, A Selection, 2004. ACM.Google Scholar
- Eugenio Moggi. Notions of computation and monads. Information and Computation, 93: 55--92, 1991. Google ScholarDigital Library
- A. M. Pitts. Typed operational reasoning. In B. C. Pierce, editor, Advanced Topics in Types and Programming Languages, chapter 7, pages 245--289. The MIT Press, 2005.Google Scholar
- Amr Sabry and Philip Wadler. A reflection on call-by-value. ACM Transactions on Programming Languages and Systems (TOPLAS), 19 (6): 916--941, November 1997. ISSN 0164-0925. Google ScholarDigital Library
- Zhong Shao and Andrew W. Appel. A type-based compiler for Standard ML. In Proc. 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 116--129, La Jolla, CA, Jun 1995. Google ScholarDigital Library
- Olin Shivers. Higher-order control-flow analysis in retrospect: lessons learned, lessons abandoned (with retrospective). In McKinley (2004), pages 257--269.Google ScholarDigital Library
- Olin Shivers and Mitchell Wand. Bottom-up β-reduction: Uplinks and λ-DAGs. In European Symposium on Programming (ESOP), pages 217--232, 2005. Google ScholarDigital Library
- Guy L. Steele. RABBIT: A compiler for SCHEME. Technical Report AI-TR-474, MIT, May 1978. Google ScholarDigital Library
- Hayo Thielecke. Comparing control constructs by double-barrelled CPS. Higher-Order and Symbolic Computation, 15 (2/3): 141--160, 2002. Google ScholarDigital Library
- Andrew P. Tolmach and Dino Oliva. From ML to Ada: Strongly-typed language interoperability via source translation. Journal of Functional Programming, 8 (4): 367--412, 1998. Google ScholarDigital Library
- Philip Wadler and Peter Thiemann. The marriage of effects and monads. In ACM SIGPLAN International Conference on Functional Programming (ICFP), 1998. Google ScholarDigital Library
Index Terms
- Compiling with continuations, continued
Recommendations
Compiling without continuations
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationMany fields of study in compilers give rise to the concept of a join point—a place where different execution paths come together. Join points are often treated as functions or continuations, but we believe it is time to study them in their own right. ...
Compiling with continuations, continued
Proceedings of the ICFP '07 conferenceWe present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the ...
Comments