The essence of compiling with continuations

ABSTRACT

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 intermediate form is that all procedures take an argument that represents the rest of the computation (the "continuation"). Since the naïve CPS transformation considerably increases the size of programs, CPS compilers perform reductions to produce a more compact intermediate representation. Although often implemented as a part of the CPS transformation, this step is conceptually a second phase. Finally, code generators for typical CPS compilers treat continuations specially in order to optimize the interpretation of continuation parameters.A thorough analysis of the abstract machine for CPS terms shows that the actions of the code generator invert the naïve CPS translation step. Put differently, the combined effect of the three phases is equivalent to a source-to-source transformation that simulates the compaction phase. Thus, fully developed CPS compilers do not need to employ the CPS transformation but can achieve the same results with a simple source-level transformation.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: Andrew W. Appel, SSA is functional programming, ACM SIGPLAN Notices, v.33 n.4, p.17-20, April 1998 [doi>10.1145/278283.278285]
• 3: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In J. Maluszyński and M. Wirsing, editors, Proceedings of the 3rd Int. Symposium on Programming Language Implementation and Logic Programming, PLILP91, Passau, Germany, Lecture Notes in Computer Science, pages 1--13. Springer-Verlag, August 1991.
• 4: Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. Technical Report TR-329-91, Princeton University, Computer Science Department, June 1991.
• 5: Matthias Blume , Andrew W. Appel, Lambda-splitting: a higher-order approach to cross-module optimizations, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.112-124, June 09-11, 1997, Amsterdam, The Netherlands
• 6: M. Felleisen and D. P. Friedman. Control operators, the SECD-machine, and the λ-calculus, pages 193--217. North-Holland, 1986.
• 7: Matthias Felleisen, &lgr;-V-CS: an extended &lgr;-calculus for scheme, Proceedings of the 1988 ACM conference on LISP and functional programming, p.72-85, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62686]
• 8: Matthias Felleisen, Daniel P. Friedman, Eugene Kohlbecker, and Bruce Duba. Reasoning with continuations. In Proc. of 1st Ann. IEEE Symp. on Logic in Computer Science, LICS'86, Cambridge, MA, USA, 16--18 June 1986, pages 131--141. IEEE Computer Society Press, Washington, DC, 1986.
• 9: Matthias Felleisen , Robert Hieb, The revised report on the syntactic theories of sequential control and state, Theoretical Computer Science, v.103 n.2, p.235-271, 14 Sept. 1992 [doi>10.1016/0304-3975(92)90014-7]
• 10: Matthew Fluet , Stephen Weeks, Contification using dominators, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 11: John Hatcliff , Olivier Danvy, A computational formalization for partial evaluation, Mathematical Structures in Computer Science, v.7 n.5, p.507-541, October 1997 [doi>10.1017/S0960129597002405]
• 12: Richard A. Kelsey, A correspondence between continuation passing style and static single assignment form, ACM SIGPLAN Notices, v.30 n.3, p.13-22, March 1993
• 13: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 14: Xavier Leroy. A syntactic theory of type generativity and sharing. Journal of Functional Programming, 6(5):667--698, September 1996.
• 15: G. Plotkin. Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science, 1(2):125--159, 1975.
• 16: John Reppy. Local CPS conversion in a direct-style compiler. In Proceedings of the Third ACM SIGPLAN Workshop on Continuations (CW'01), pages 13--22, January 2001.
• 17: Amr Sabry , Matthias Felleisen, Reasoning about programs in continuation-passing style., Proceedings of the 1992 ACM conference on LISP and functional programming, p.288-298, June 22-24, 1992, San Francisco, California, United States
• 18: Amr Sabry , Matthias Felleisen, Reasoning about programs in continuation-passing style, Lisp and Symbolic Computation, v.6 n.3-4, p.289-360, Nov. 1993 [doi>10.1007/BF01019462]
• 19: Amr Sabry , Matthias Felleisen, Is continuation-passing useful for data flow analysis?, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.1-12, June 20-24, 1994, Orlando, Florida, United States
• 20: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 21: D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.181-192, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 22: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 23: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 24: BARENDREGT, H. The Lambda Calculus: Its Syntax and Semantics, revised ed. Studies in Logic and the Foundations of Mathematics 103. North-Holland, 1984.
• 25: Hans-Juergen Boehm , Alan Demers, Implementing RUSSELL, ACM SIGPLAN Notices, v.21 n.7, p.186-195, July 1986
• 26: Anders Bondorf, Improving binding times without explicit CPS-conversion, Proceedings of the 1992 ACM conference on LISP and functional programming, p.1-10, June 22-24, 1992, San Francisco, California, United States
• 27: William Clinger, The scheme 311 compiler an exercise in denotational semantics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.356-364, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802052]
• 28: Olivier Danvy, Back to direct style, Symposium proceedings on 4th European symposium on programming, p.130-150, January 1992, Rennes, France
• 29: DANVY, O. Three steps for the CPS transformation. Tech. Rep. CIS-92-2, Kansas State University, 1992.
• 30: DANVY, O., AND FILINSKI, A. Representing control: A study of the CPS transformation. Mathematical Structures in Computer Science, 4 (1992), 361--391.
• 31: FELLEISEN, M., AND FRIEDMAN, D. Control operators, the SECD-machine, and the λ-calculus. In Formal Description of Programming Concepts III (Amsterdam, 1986), M. Wirsing, Ed., Elsevier Science Publishers B.V. (North-Holland), pp. 193--217.
• 32: FESSENDEN, C., CLINGER, W., FRIEDMAN, D. P., AND HAYNES, C. T. Scheme 311 version 4 reference manual. Computer Science Technical Report 137, Indiana University, Bloomington, Indiana, Feb. 1983.
• 33: Michael J. Fischer, Lambda calculus schemata, ACM SIGPLAN Notices, v.7 n.1, p.104-109, January 1972
• 34: R. Kelsey , P. Hudak, Realistic compilation by program transformation (detailed summary), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-292, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75302]
• 35: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, ACM SIGPLAN Notices, v.21 n.7, p.219-233, July 1986
• 36: LEROY, X. The Zinc experiment: An economical implementation of the ML language. Tech. Rep. 117, INRIA, 1990.
• 37: PLOTKIN, G. Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science 1 (1975), 125--159.
• 38: Amr Sabry , Matthias Felleisen, Reasoning about programs in continuation-passing style., Proceedings of the 1992 ACM conference on LISP and functional programming, p.288-298, June 22-24, 1992, San Francisco, California, United States
• 39: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 40: STEELE, G. L. RABBIT: A compiler for Scheme. MIT AI Memo 474, Massachusetts Institute of Technology, Cambridge, Mass., May 1978.
• 41: Mitchell Wand, Correctness of Procedure Representations in Higher-Order Assembly Language, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.294-311, March 25-28, 1991
• 42: WEISE, D. Advanced compiling techniques. Course Notes at Stanford University, 1990.