Luke Maurer
Paul Downen
Simon Peyton Jones
ABSTRACT
Many 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. We show that adding join points to a direct-style functional intermediate language is a simple but powerful change that allows new optimizations to be performed, including a significant improvement to list fusion. Finally, we report on recent work on adding join points to the intermediate language of the Glasgow Haskell Compiler.
- A. W. Appel. Compiling with Continuations. Cambridge University Press, 1992. ISBN 0-521-41695-7. Google Scholar
Digital Library
- A. W. Appel. SSA is functional programming. SIGPLAN Notices, 33(4):17–20, 1998. Google ScholarDigital Library
- C. A. Baker-Finch, K. Glynn, and S. L. Peyton Jones. Constructed product result analysis for Haskell. J. Funct. Program., 14(2):211–245, 2004. Google ScholarDigital Library
- N. Benton, A. Kennedy, S. Lindley, and C. V. Russo. Shrinking reductions in SML.NET. In Implementation and Application of Functional Languages, 16th International Workshop, IFL 2004, Lübeck, Germany, September 8-10, 2004, Revised Selected Papers, pages 142–159, 2004. Google ScholarDigital Library
- M. M. T. Chakravarty, G. Keller, and P. Zadarnowski. A functional perspective on SSA optimisation algorithms. Electr. Notes Theor. Comput. Sci., 82(2):347–361, 2003.Google ScholarCross Ref
- D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: from lists to streams to nothing at all. In ACM SIGPLAN International Conference on Functional Programming (ICFP’07), Freiburg, Germany, Oct. 2007. ACM. Google ScholarDigital Library
- R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451–490, 1991. Google ScholarDigital Library
- P. Downen, L. Maurer, Z. M. Ariola, and S. Peyton Jones. Sequent calculus as a compiler intermediate language. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016, Nara, Japan, September 18-22, 2016, pages 74–88, 2016. Google ScholarDigital Library
- M. Felleisen and R. Hieb. A revised report on the syntactic theories of sequential control and state. Theoretical Computer Science, 103(2):235–271, 1992. Google ScholarDigital Library
- C. Flanagan, A. Sabry, B. F. Duba, and M. Felleisen. The essence of compiling with continuations. In Proceedings of the ACM SIGPLAN’93 Conference on Programming Language Design and Implementation (PLDI), Albuquerque, New Mexico, USA, June 23-25, 1993, pages 237–247, 1993. Google ScholarDigital Library
- M. Fluet and S. Weeks. Contification using dominators. In Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP ’01), Firenze (Florence), Italy, September 3-5, 2001., pages 2–13, 2001. Google ScholarDigital Library
- A. Gill and G. Hutton. The worker/wrapper transformation. J. Funct. Program., 19(2):227–251, 2009. Google ScholarDigital Library
- J.-Y. Girard, P. Taylor, and Y. Lafont. Proofs and types, volume 7. Cambridge University Press Cambridge, 1989. Google ScholarDigital Library
- J. Groff and C. Lattner. Swift intermediate language. LLVM Developers Meeting http://www.llvm.org/ devmtg/2015-10/, 2015.Google Scholar
- A. Keep, A. Hearn, and R. Dybvig. Optimizing closures in O(0) time. In Annual Workshop on Scheme and Functional Programming. ACM, 2012. Google ScholarDigital Library
- A. Kennedy. Compiling with continuations, continued. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Freiburg, Germany, October 1-3, 2007, pages 177–190, 2007. Google ScholarDigital Library
- S. Lindley. Normalisation by evaluation in the compilation of typed functional programming languages. PhD thesis, University of Edinburgh, College of Science and Engineering, School of Informatics, 2005.Google Scholar
- C. Okasaki, P. Lee, and D. Tarditi. Call-by-need and continuation-passing style. Lisp and Symbolic Computation, 7 (1):57–82, 1994. Google ScholarDigital Library
- S. Peyton Jones and A. Santos. A transformation-based optimiser for Haskell. Science of Computer Programming, 32(1-3):3–47, Sept. 1998. Google ScholarDigital Library
- S. Peyton Jones, W. Partain, and A. Santos. Let-floating: moving bindings to give faster programs. In ACM SIGPLAN International Conference on Functional Programming (ICFP’96), Philadelphia, May 1996. ACM. Google ScholarDigital Library
- S. L. Peyton Jones. Call-pattern specialisation for Haskell programs. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Freiburg, Germany, October 1-3, 2007, pages 327–337, 2007. Google ScholarDigital Library
- S. L. Peyton Jones, A. Tolmach, and T. Hoare. Playing by the rules: rewriting as a practical optimisation technique in GHC. In R. Hinze, editor, 2001 Haskell Workshop. ACM, September 2001.Google Scholar
- J. H. Reppy. Optimizing nested loops using local CPS conversion. Higher-Order and Symbolic Computation, 15(2-3): 161–180, 2002. Google ScholarDigital Library
- G. L. Steele, Jr. RABBIT: A compiler for SCHEME. Technical Report AITR-474, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, 1978. Google ScholarDigital Library
- M. Sulzmann, M. Chakravarty, S. P. Jones, and K. Donnelly. System F with type equality coercions. In ACM SIGPLAN International Workshop on Types in Language Design and Implementation (TLDI’07), pages 53–66. ACM, January 2007. Google ScholarDigital Library
- ISBN 1-59593-393-X.Google Scholar
- J. Svenningsson. Shortcut fusion for accumulating parameters & zip-like functions. In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP ’02), Pittsburgh, Pennsylvania, USA, October 4-6, 2002., pages 124–132, 2002. Google ScholarDigital Library
- A. P. Tolmach and D. Oliva. From ML to Ada: Stronglytyped language interoperability via source translation. J. Funct. Program., 8(4):367–412, 1998. Google ScholarDigital Library
Recommendations
Compiling with continuations, or without? whatever.
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 ...
The essence of compiling with continuations
PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementationIn order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this ...
The essence of compiling with continuations
In order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this ...
Comments