A parallel virtual machine for efficient scheme compilation

ABSTRACT

Programs compiled by Gambit, our Scheme compiler, achieve performance as much as twice that of the fastest available Scheme compilers. Gambit is easily ported, while retaining its high performance, through the use of a simple virtual machine (PVM). PVM allows a wide variety of machine-independent optimizations and it supports parallel computation based on the future construct. PVM conveys high-level information bidirectionally between the machine-independent front end of the compiler and the machine-dependent back end, making it easy to implement a number of common back end optimizations that are difficult to achieve for other virtual machines. PVM is similar to many real computer architectures and has an option to efficiently gather dynamic measurements of virtual machine usage. These measurements can be used in performance prediction for ports to other architectures as well as design decisions related to proposed optimizations and object representations.

REFERENCES

• 2: Joel Bartlett. $chm~e->g a portable Scheme-to-C compiler. Technical Report 8911, Digital Equipment Corp. Western Research Lab., 1989.
• 3: John Befall, Edmund Goodhue, Chris Hanson, Howie Shrobe,. Richard M. Stallman, and Gerald Jay Sussman. The Scheme-81 architecture- system and chip. in Paul Penfield Jr., editor, Proc. of the MiT Confer. ence on Advanced Research in VLSi~ Dedham, Mass., 1982. Artech House.
• 4: William Campbell, A C interpreter for Scheme: an exercise in object-oriented design, Software Engineering Journal, v.6 n.4, p.130-136, July 1991
• 5: J6r6me Chailloux. La machine LLM3. Rapport interne du projet vlsi, INRIA, May 1984. Corresponds to LeLisp version 15.
• 6: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 7: Martin L. Griss and Anthony C. Hearn. A portable LISP compiler. Software Practice and Experience, 11:541-605, 1981.
• 8: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 9: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• 10: Jack Holloway, Guy Lewis Steele Jr., Gerald Jay Sussman, and Alan Bell. The Scheme-79 chip. Technical Report AI Memo 559, Mass. Inst. of Technology, Artificial intelligence Laboratory, 1980.
• 11: 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
• 12: Mass. inst. of Technology, Cambridge, MA. MIT Scheme Reference, Scheme Release 7, 1988.
• 13: James Miller. MtdtiScheme: A Parallel Processing System Based on MIT Scheme. PhD thesis, Mass. Inst. of Technology, August 1987. Available as MIT LCS/TR/402.
• 14: J. S. Miller, Implementing a scheme-based parallel processing system, International Journal of Parallel Programming, v.17 n.5, p.367-402, Oct. 1989 [doi>10.1007/BF01383881]
• 15: James Miller and Christopher Hanson. IEEE Draft Standard for the Programming Language Scheme. iEEE. forthcoming.
• 16: James S. Miller , Guillermo J. Rozas, Free variables and first-class environments, Lisp and Symbolic Computation, v.4 n.2, p.107-141, April 1991 [doi>10.1007/BF01813016]
• 17: Guillermo Rozas. Liar, an Algol-like compiler for Scheme. Bachelor's thesis, Mass. Inst. of Technology, 1984.
• 18: Guy Lewis Steele Jr. Rabbit: A compiler for Scheme. Master's thesis, Mass. Inst. of Technology, 1978.

INDEX TERMS

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

          Nouns: SCHEME

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Algorithms, Design, Languages, Measurement, Performance