PyPy's approach to virtual machine construction

ABSTRACT

The PyPy project seeks to prove both on a research and a practical level the feasibility of constructing a virtual machine (VM) for a dynamic language in a dynamic language - in this case, Python. The aim is to translate (i.e. compile) the VM to arbitrary target environments, ranging in level from C/Posix to Smalltalk/Squeak via Java and CLI/.NET, while still being of reasonable efficiency within these environments.A key tool to achieve this goal is the systematic reuse of the Python language as a system programming language at various levels of our architecture and translation process. For each level, we design a corresponding type system and apply a generic type inference engine - for example, the garbage collector is written in a style that manipulates simulated pointer and address objects, and when translated to C these operations become C-level pointer and address instructions.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: C. S. Ananian. The static single information form. Master's thesis, Massachusetts Institute of Technology, September 1999.
• 3: M. Arnold, S. Fink, D. Grove, M. Hind, and P. F. Sweeney. Architecture and policy for adaptive optimization in virtual machines. Technical Report 23429, IBM Research, November 2004.
• 4: AT&T. Graphviz - graph visualization software. http://www.graphviz.org/.
• 5: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 6: H. Boehm. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/.
• 7: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 8: G. Bracha. Pluggable type systems. In OOPSLA04 Workshop on Revival of Dynamic Languages, October 2004.
• 9: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 10: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 11: Dan Ingalls , Ted Kaehler , John Maloney , Scott Wallace , Alan Kay, Back to the future: the story of Squeak, a practical Smalltalk written in itself, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.318-326, October 05-09, 1997, Atlanta, Georgia, United States
• 12: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 13: R. Kelsey. Pre-scheme: A scheme dialect for systems programming.
• 14: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 15: R. Milner. A theory of type polymorphism in programming. J. Comput. Syst. Sci., 17(3):348--375, 1978.
• 16: PyPy Team. PyPy - Architecture Overview. Web page. http://codespeak.net/pypy/dist/pypy/doc/archi-tecture.html.
• 17: PyPy Team. PyPy - Translation. Web page, in-progress. http://codespeak.net/pypy/dist/pypy/doc/trans-lation.html.
• 18: PyPy Team. Complete python implementation running on top of cpython. Technical report, PyPy Consortium, 2005. http://codespeak.net/svn/pypy/extradoc/eu-report/.
• 19: Armin Rigo, Representation-based just-in-time specialization and the psyco prototype for python, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.15-26, August 24-25, 2004, Verona, Italy [doi>10.1145/1014007.1014010]
• 20: A. Rigo, M. Hudson, and S. Pedroni. Compiling dynamic language implementations. Technical report, PyPy Consortium, 2005. http://codespeak.net/svn/pypy/extradoc/eu-report/.
• 21: David Ungar , Adam Spitz , Alex Ausch, Constructing a metacircular Virtual machine in an exploratory programming environment, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA [doi>10.1145/1094855.1094865]
• 22: G. van Rossum et al. CPython 2.4.3, March 2006. http://www.python.org/download/releases/2.4.3/.
• 23: Tiejun Wang , Scott F. Smith, Precise Constraint-Based Type Inference for Java, Proceedings of the 15th European Conference on Object-Oriented Programming, p.99-117, June 18-22, 2001
• 24: R. P. Weicker, Dhrystone benchmark: rationale for version 2 and measurement rules, ACM SIGPLAN Notices, v.23 n.8, p.49-62, August 1988 [doi>10.1145/47907.47911]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters; Run-time environments

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Experimentation, Languages, Performance

Keywords:
Python, metacircularity, retargettable code generation, type inference, virtual machine