Zhong Shao
Andrew W. Appel
ABSTRACT
Compile-time type information should be valuable in efficient compilation of statically typed functional languages such as Standard ML. But how should type-directed compilation work in real compilers, and how much performance gain will type-based optimizations yield? In order to support more efficient data representations and gain more experience about type-directed compilation, we have implemented a new type-based middle end and back end for the Standard ML of New Jersey compiler. We describe the basic design of the new compiler, identify a number of practical issues, and then compare the performance of our new compiler with the old non-type-based compiler. Our measurement shows that a combination of several simple type-based optimizations reduces heap allocation by 36%; and improves the already-efficient code generated by the old non-type-based compiler by about 19% on a DECstation 500.
- 1.William E. Aitken and John H. Reppy. Abstract value constructors: Symbolic constants for Standard ML. Technical Report TR 92-1290, Department of Computer Science, Cotnell University, June 1992. A shorter version appears in the proceedings of the "ACM SIGPLAN Workshop on ML and its Applications," 1992.Google Scholar
- 2.Andrew W. Appel. A runtlme system. Lisp and Symbolic Computation, 3(4):343-80, 1990. Google ScholarDigital Library
- 3.Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992. Google ScholarDigital Library
- 4.Andrew W. Appel and Trevor Jim. Continuation-passing, closure-passing style. In Sixteenth A CM Syrup. on Principles of Programming Languages, pages 293-302, New York, 1989. ACM Press. Google Scholar
- 5.Andrew W. Appel and David B. MacQueen. Standard ML of New Jersey. In Martin Wirsing, editor, Third Int'I Syrup. on Prog. Lang. Implementation and Logic Programming, pages 1-13, New York, August 1991. Springer-Verlag.Google Scholar
- 6.Andrew W. Appel and Zhong Shao. Callee-save registers in continuation-passing style. Lisp and Symbolic Cornputatton, 5:189-219, September 1992. Google ScholarDigital Library
- 7.Nikolaj S. Bjorner. Minimial typing derivations. In A CM SIGPLAN Workshop on ML and its Applications, pages 120- 126, June 1994.Google Scholar
- 8.Craig Chambers. The Design and bnplementation of the SELF Compiler, an Optimizbzg Compiler for Object-Orielzted Programming Languages. PhD thesis, Stanford University, Stanford,California, March 1992. Tech Report STAN-CS- 92-1420. Google ScholarDigital Library
- 9.Craig Chambers and David Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In Proc. ACM SIG- PLAN '89 Conf. on Prog. Lang. Design and hnplementati~n' pages I46-160, New York, July 1989. ACM Press. Google ScholarDigital Library
- 10.Luis Damas and Robin Milner. Principal type-schemes for functional programs. In Ninth A CM Symposium on Principles of Programming Languages, pages 207-12, New York, 1982. ACM Press. Google ScholarDigital Library
- 11.Robert Harper and Mark Lillibridge. A type-theoretic approach to higher-order modules with sharing. In %t'enn' First AnnltalACM S3,mp. on Principles of Prog. Langttages, pages 123-137, New York, Jan 1994. ACM Press. Google ScholarDigital Library
- 12.Robert Harper and Greg Morrisett. Compiling polymorphlsm using intenslonal type analysis. In T~ventv-second Annlta{ A CM &'mp. on Prtnciples of Prog. La,~lguages, pages 130- 141, New York, Jan 1995. ACM Press. Google Scholar
- 13.Fritz Henglein and Jesper Jorgensen. Formally optimal boxing. In Proc. 21st Annual A CM SIGPLAN-SIGA CT &'rap. on Principles of Programming Languages, pages 213-226. ACM Press, 1994. Google ScholarDigital Library
- 14.David Kranz. ORBIT.' An opttmtzing compiler for Scheme. PhD thesis, Yale University, New Haw~n, CT, I987. Google ScholarDigital Library
- 15.Xavier Leroy. Unboxed objects and polymorphic typing. In Nineteenth Annual A CM ~'rap. on Prit,lciples of Prog. Languages, pages 177-188, New York, January I992. ACM Press. Google Scholar
- 16.Xavier Leroy. Manifest types, modules, and separate compilation. In TweJzt~' First Annual A CM Syrup. ot~ Principles of Prog. Languages, pages 109-122, New York, Jan 1994. ACM Press. Google Scholar
- 17.Dawd B. MacQueen and Mads Tofte. A semantics for higher-order functors. In Proc. Ettropea~'z Symposium on Programmhlg (ESOP'94), pages 409-423, April 1994. Google ScholarDigital Library
- 18.Robin Milner and Mads Torte. Commentary on Standard ML. MIT Press, Cambridge, Massachusetts, 1991. Google ScholarDigital Library
- 19.Robin Milner, Mads Tofte, and Robert Harper. The Definition of Standard ML. MIT Press, Cambridge, MA, 1990. Google ScholarDigital Library
- 20.Simon L. Peyton Jones and John Launchbury. Unboxed values as first class cit;zens in a non-strict functional language. In The Fifth International Conference on Functional Programming Languages and Computer A~vhitecture, pages 636-666, New York, August 1991. ACM Press. Google ScholarDigital Library
- 21.Eigil Poulsen, Representation analysis for efficient implementation of polymorph~sm. Master's thes~s, DiKU, University of Copenhagen, 1993.Google Scholar
- 22.Zhong Shao. Compiling Standard ML for Efficient Execution on Modern Machines. PhD thesis, Princeton University, Princeton, NJ, November 1994. Tech Report CS-TR-475-94. Google ScholarDigital Library
- 23.Zhong Shao and Andrew W. Appel. Space-efficient closure representations. In Proc. 1994 A CM Conf on Lisp and Ftmctional Programming, pages 150-16 I. ACM Press, 1994. Google ScholarDigital Library
- 24.Guy L. Steele. Rabbit: a compiler for Scheme. Technical Report AI-TR-474, MIT, Cambridge. MA, 1978. Google ScholarDigital Library
- 25.Mads Torte. Prlnc~pal signatures t br higher-order program modules. In Nineteenth Annual A CM &vmp. on Principles of Prog. Languages, pages 189-199, New York, Jan 1992. ACM Press. Google Scholar
- 26.David M. Ungar. The Design and Evaluation of a High Performance Smatttalk System. MIT Press., Cambridge, MA, 1986. Google ScholarDigital Library
Index Terms
- A type-based compiler for standard ML
Recommendations
A type-based compiler for standard ML
Compile-time type information should be valuable in efficient compilation of statically typed functional languages such as Standard ML. But how should type-directed compilation work in real compilers, and how much performance gain will type-based ...
Compiling standard ML to Java bytecodes
ICFP '98: Proceedings of the third ACM SIGPLAN international conference on Functional programmingMLJ compiles SML'97 into verifier-compliant Java byte-codes. Its features include type-checked interlanguage working extensions which allow ML and Java code to call each other, automatic recompilation management, compact compiled code and runtime ...
An action compiler targeting Standard ML
We present an action compiler that can be used in connection with an action semantics based compiler generator. Our action compiler produces code with faster execution times than code produced by other action compilers, and for some nontrivial test ...
Comments