No assembly required: compiling standard ML to C

ABSTRACT

C has been used as a portable target language for implementing languages like Standard ML and Scheme. Previous efforts at compiling these languages to C have produced efficient code, but have compromised on portability and proper tail recursion. We show how to compile Standard ML to C wihout making such compromises. The compilation technique is based on converting Standard ML to a continuation-passing style &lgr;-calculus intermediate language and then compiling this language to C. The code generated by this compiler achieves an execution speed that is about a factor of two slower than that generated by a native code compiler. The compiler generates highly portable code, yet still supports advanced features like garbage collection and first-class continuations. We analyze the performance and determine the aspects of the compilation method that lead to the observed slowdown. We also suggest changes to C compilers that would better support such compilation methods.

REFERENCES

• 1: ACHARYA, A., AND KALP, D. Release notes for CParaOPS5 5.3 and ParaOPS5 4.4. Available with the CParaOPS5 release from School of Computer Science, Carnegie-Mellon Univ. Pittsburgh, Pa., May 1990.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 4: APPEL, A.W. Compihng with Contmuatwns. Cambridge University Press, New York, 1992.
• 5: A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75303]
• 6: 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
• 7: R. Atkinson , A. Demers , C. Hauser , C. Jacobi , P. Kessler , M. Weiser, Experiences creating a portable cedar, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.322-329, June 19-23, 1989, Portland, Oregon, United States
• 8: BARTLETT, J.F. SCHEME --~ C: A portable Scheme-to-C compiler. Tech. Rep., DEC Western Research Laboratory, Palo Alto, Calif., Jan. 1989.
• 9: COOPER, E. C., AND MORRISETT, J.G. Adding threads to Standard ML. Tech. Rep. CMU-CS- 90-186, School of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., Dec. 1990.
• 10: Bruce Duba , Robert Harper , David MacQueen, Typing first-class continuations in ML, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99608]
• 11: FELDMAN, S., GAY, D., MAIMONE, M. W., AND SCHYER, N. A Fortran-to-C converter. Comput. Sci. Tech. Rep. 149, AT & T Bell Laboratories, Murray Hill, N.J., May 1990.
• 12: GILLESPIE, D. The p2c translator. Available by anonymous ftp from csvax.cs.caltech.edu under the GNUcopyleft, 1989.
• 13: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
• 14: Lorenz Huelsbergen , James R. Larus, Dynamic program parallelization, Proceedings of the 1992 ACM conference on LISP and functional programming, p.311-323, June 22-24, 1992, San Francisco, California, United States
• 15: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 16: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• 17: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 18: MARTIN, M. Entwurfund Implementierung eines bersetzers von Modula-2 nach C. Master's thesis, Faklutt fur Informatik, Univ. of Karlsruhe, Germany, Feb. 1990.
• 19: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 20: J. G Morrisett , Andrew Tolmach, A Portable Multiprocessor Interface for Standard ML of New Jersey, Carnegie Mellon University, Pittsburgh, PA, 1992
• 21: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 22: John H. Reppy, Asynchronous Signals is Standard ML, Cornell University, Ithaca, NY, 1990
• 23: Vatsa Santhanam , Daryl Odnert, Register allocation across procedure and module boundaries, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.28-39, June 1990, White Plains, New York, United States
• 24: STALLMAN, R.M. Using and porting GNU CC. GNU CC is a widely available C compiler developed by the Free Software Foundation, Cambridge, Mass., Sept. 1989.
• 25: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 26: TARDITI, D., ACHARYA, A., AND LEE, P. No assembly required: Compiling Standard ML to C. Tech. Rep. CMU-CS-90-187, School of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., Nov. 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

          Nouns: Standard ML; C
      D.3.4 Processors
          Subjects: Code generation

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Design, Languages, Performance, Theory

Keywords:
compilation to C, continuation-passing style, scheme, standard ML