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.
- 1.Andrew W. Appel and David B. Mac- Queen, "A Standard ML compiler," in Functional Programming Languages and Computer Architecture (LNCS 274), pp. 301-324, Springer-Verlag, 1987. Google ScholarDigital Library
- 2.Guy L. Steele, "Rabbit: a compiler for Scheme," AI-TR-474, MIT, 1978. Google ScholarDigital Library
- 3.D. Kranz, R. Kelsey, J. Rees, P. Hudak, J. Philbin, and N. Adams, "ORBIT: An optimizing compiler for Scheme," Proc. Sigplan '86 Syrup. on Compiler Construction, vol. 21 (Sigplan Notices), no. 7, pp. 219-233, July 1986. Google ScholarDigital Library
- 4.David Kranz, "ORBIT: An Optimizing Compiler for Scheme," PhD Thesis, Yale University, 1987. Google ScholarDigital Library
- 5.Andrew W. Appel, Christopher W. Fraser, David R. Hanson, and Arthur H. Watson, "Generating code for the Case statement," in preparation.Google Scholar
- 6.V. Vyssotsky and P. Wegner, A graph theoretical Fortran source language analyzer, AT&T Bell Laboratories, Murray Hill, NJ, 1963.Google Scholar
- 7.G. Cousineau, P. L. Curien, and M. Mauny, "The Categorical Abstract Machine," in Functional Programming Languages and Computer Architecture, LNCS Vol 201, ed. J. P. Jouannaud, pp. 50-64, Springer- Verlag, 1985. Google ScholarDigital Library
- 8.Andrew W. Appel and Trevor Jim, "Optimizing closure environment representations," CS-TR- 168-88, Princeton University, 1988.Google Scholar
- 9.David Ungar, "Generation scavenging: a non-disruptive high performance storage reclamation algorithm," SIGPLAN Notices (Proc. ACM SIGSOFTISIGPLAN Software Eng. Syrup. on Practical Software Development Environments), vol. 19, no. 5, pp. 157-167, ACM, 1984. Google ScholarDigital Library
- 10.A.W. Appel, "Garbage collection can be faster than stack allocation," Information Processing Letters, vol. 25, no. 4, pp. 275- 279, 1987. Google ScholarDigital Library
- 11.David R. Chase, "Safety considerations for storage allocation optimizations," SIG- PLAN '88 Conf. on Prog. Lang. Design and Implementation, pp. 1-10, ACM, 1988. Google ScholarDigital Library
Index Terms
- Continuation-passing, closure-passing style
Recommendations
Reasoning about programs in continuation-passing style.
Plotkin's λ-value calculus is sound but incomplete for reasoning about βeegr;-transformations on programs in continuation-passing style (CPS). To find a complete extension, we define a new, compactifying CPS transformation and an “inverse”mapping, un-...
Reasoning about programs in continuation-passing style.
LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programmingPlotkin's λ-value calculus is sound but incomplete for reasoning about βeegr;-transformations on programs in continuation-passing style (CPS). To find a complete extension, we define a new, compactifying CPS transformation and an “inverse”mapping, un-...
Reasoning about programs in continuation-passing style
Special issue on continuations—part I
Comments