Continuation-passing, closure-passing style

ABSTRACT

We implemented a continuation-passing style (CPS) code generator for ML. Our CPS language is represented as an ML datatype in which all functions are named and most kinds of ill-formed expressions are impossible. We separate the code generation into phases that rewrite this representation into ever-simpler forms. Closures are represented explicitly as records, so that closure strategies can be communicated from one phase to another. No stack is used. Our benchmark data shows that the new method is an improvement over our previous, abstract-machine based code generator.

REFERENCES

• 1: Andrew W. Appel , David B. MacQueen, A standard ML compiler, Proc. of a conference on Functional programming languages and computer architecture, p.301-324, October 1987, Portland, Oregon, United States
• 2: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 3: 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
• 4: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• 5: Andrew W. Appel, Christopher W. Fraser, David R. Hanson, and Arthur H. Watson, "Generating code for the Case statement," in preparation.
• 6: V. Vyssotsky and P. Wegner, A graph theoretical Fortran source language analyzer, AT&T Bell Laboratories, Murray Hill, NJ, 1963.
• 7: G. Cousineau , P. L. Curien , M. Mauny, The categorical abstract machine, Proc. of a conference on Functional programming languages and computer architecture, p.50-64, January 1985, Nancy, France
• 8: Andrew W. Appel and Trevor Jim, "Optimizing closure environment representations," CS-TR- 168-88, Princeton University, 1988.
• 9: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 10: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X ]
• 11: D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.4 Processors
          Subjects: Code generation; Compilers

General Terms:
Algorithms, Languages