Compiling without continuations

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.

  1. A. W. Appel. Compiling with Continuations. Cambridge University Press, 1992. ISBN 0-521-41695-7. Google Scholar
  2. A. W. Appel. SSA is functional programming. SIGPLAN Notices, 33(4):17–20, 1998. Google Scholar
  3. 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 Scholar
  4. 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 Scholar
  5. 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 Scholar
  6. 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 Scholar
  7. 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 Scholar
  8. 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 Scholar
  9. 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 Scholar
  10. 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 Scholar
  11. 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 Scholar
  12. A. Gill and G. Hutton. The worker/wrapper transformation. J. Funct. Program., 19(2):227–251, 2009. Google Scholar
  13. J.-Y. Girard, P. Taylor, and Y. Lafont. Proofs and types, volume 7. Cambridge University Press Cambridge, 1989. Google Scholar
  14. J. Groff and C. Lattner. Swift intermediate language. LLVM Developers Meeting devmtg/2015-10/, 2015.Google Scholar
  15. A. Keep, A. Hearn, and R. Dybvig. Optimizing closures in O(0) time. In Annual Workshop on Scheme and Functional Programming. ACM, 2012. Google Scholar
  16. 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 Scholar
  17. 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
  18. C. Okasaki, P. Lee, and D. Tarditi. Call-by-need and continuation-passing style. Lisp and Symbolic Computation, 7 (1):57–82, 1994. Google Scholar
  19. S. Peyton Jones and A. Santos. A transformation-based optimiser for Haskell. Science of Computer Programming, 32(1-3):3–47, Sept. 1998. Google Scholar
  20. 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 Scholar
  21. 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 Scholar
  22. 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
  23. J. H. Reppy. Optimizing nested loops using local CPS conversion. Higher-Order and Symbolic Computation, 15(2-3): 161–180, 2002. Google Scholar
  24. G. L. Steele, Jr. RABBIT: A compiler for SCHEME. Technical Report AITR-474, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, 1978. Google Scholar
  25. 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 Scholar
  26. ISBN 1-59593-393-X.Google Scholar
  27. 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 Scholar
  28. 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 Scholar