\chapter{Enter PyPy}
\label{cha:pypy}

\section{What is PyPy?}

The \emph{PyPy} project\footnote{\texttt{http://codespeak.net/pypy/}}
\cite{RigoPedroni06} was initially conceived to develop an implementation of
Python which could be easily portable and extensible without renouncing
efficiency.  To achieve these aims, the PyPy implementation is based on a
highly modular design which allows high-level aspects to be separated from
lower-level implementation details.  The abstract semantics of Python is
defined by an interpreter written in a high-level language, called RPython
\cite{rpython}, which is in fact a subset of Python where some dynamic
features have been sacrificed to allow an efficient translation of the
interpreter to low-level code.

Compilation of the interpreter is implemented as a stepwise refinement by
means of a translation toolchain which performs type analysis, code
optimizations and several transformations aiming at incrementally providing
implementation details such as memory management or the threading model.  The
different kinds of intermediate codes which are refined during the translation
process are all represented by a collection of control flow graphs, at several
levels of abstractions.

Finally, the low-level control flow-graphs produced by the toolchain can be
translated to executable code for a specific platform by a corresponding
backend.  Currently, three fully developed backends are available to produce
executable C/POSIX code, Java and CLI/.NET bytecode.

Although it has been specifically developed for Python, the PyPy infrastructure
can in fact be used for implementing other languages. Indeed, there were
successful experiments of using PyPy to implement several other languages such
as Smalltalk \cite{BolzEtAl08}, JavaScript, Scheme and Prolog \cite{BolzLR09}.

\section{Architecture overview}
\label{sec:pypy-architecture}

PyPy is composed of two independent subsystems: the \emph{standard
  interpreter} and the \emph{translation toolchain}.

The \textbf{standard interpreter} is the subsystem implementing the Python
language, starting from the parser ending to the bytecode interpreter. It is
written in RPython, a language which can be easily be translated into
lower-level and more efficient executables.

RPython is \emph{statically typed}, and the types are deduced by type
inference.  The main restrictions compared to Python comes from the fact that
the type system has been carefully designed in a way that the programs can be
efficiently translated to C, JVM or CLI.  For example, it is forbidden to mix
integers with strings in any way, and similarly it is forbidden to change the
layout of classes at runtime, such as adding or removing methods and
attributes\footnotemark.  RPython is a proper subset of Python, in the sense
that if a Python program is RPython, it is guaranteed to have the same
semantics both when translated and when interpreted by a standard Python
interpreter.

\footnotetext{Note that, although RPython is a limited subset of Python, it is
  only used internally as the implementation language of the standard
  interpreter, which in turn fully supports the whole Python semantics.}

Because of this, the standard interpreter can also be directly executed on top
of any implementation of the language, e.g. CPython or PyPy itself: this is
immensely useful during the development, because debugging a Python program is
much easier than debugging the equivalent written in C.  Obviously, the
standard interpreter is very slow when executed this way, because of the huge
overhead of the double interpretation.

Thus, we can think of the standard interpreter as an \emph{high-level,
  executable and testable specification} of the language.

Moreover, since RPython is a high-level language, the standard interpreter is
free of the many low-level aspects that are usually hard coded into the other
Python implementations, such as e.g. garbage collection strategy or threading
model.

These aspects are woven in at \emph{translation time} by the
\textbf{translation toolchain}, whose job is to turn the high-level
specification into an efficient executable.  Thus, the translation toolchain
is much more than a compiler as we usual think of it: not only it translates
the RPython source code to the target language, but it also implements the
runtime system needed to execute a full-fledged virtual machine.

The target platforms are divided into two big categories: \emph{lltype} and
\emph{ootype} (respectively for \textbf{l}ow \textbf{l}evel and
\textbf{o}bject \textbf{o}riented \textbf{type}system).  The choice of the
type system determines the internal representation of the programs being
translated. They mainly differ in their primitives: on the one hand the
building blocks of \emph{lltype} are structures and pointers, on the other
hand \emph{ootype} is about classes, methods and objects.

Finally, the translation toolchain transfers the control to one its
\emph{backends}, which are responsible to actually generate the final
executable.  Throughout the text, we will refer to \lstinline{pypy-xxx} to
indicate the executable produced by the backend \emph{xxx}.  At the moment of
writing, there are three maintained backends:

\begin{itemize}
\item The \textbf{C backend} is based on \emph{lltype} and emits C source
  code, which is in turn compiled by either \lstinline{gcc} or \emph{Visual
    C++}\footnotemark.  The produced executable is equivalent to CPython, as
  it is a native executable for the target platform, which currently can be
  \emph{Linux}, \emph{Mac OS X} or \emph{Microsoft Windows}.

  \footnotetext{The generated code is \emph{ANSI C}, but makes optionally
    use of some specific compiler extension depending on the exact compiler we
    are using.}

\item The \textbf{CLI backend} \cite{cuni2006} \cite{rpython} is based on
  \emph{ootype} and emits IL code for the CLI, i.e. the virtual machine, at
  the core of the \emph{.NET Framework}.  Currently, both \emph{Mono} and
  \emph{Microsoft CLR} are supported.  The produced executable is roughly the
  counterpart of \emph{IronPython}, although the latter is much better
  integrated with the hosting platform.

\item The \textbf{JVM backend} \cite{rpython} is also based on \emph{ootype}
  and emits bytecode for the JVM.  Although the backend is complete, the
  resulting \lstinline{pypy-jvm} is of little practical use because it still
  cannot access the hosting Java environment.  It aims to be the equivalent of
  \emph{Jython}, a Python implementation written in Java and fully integrated
  with the JVM.

\end{itemize}


\section{JIT compiler generator}
\label{sec:jit-generator-overview}

One of the most interesting components of the translation toolchain optionally
generates a \emph{JIT compiler} from the source code of the interpreter, in an
automated way.

From the end user point of view, the presence of the JIT compiler is
completely transparent\footnote{Actually, there are hooks that the end user
  can call to tune the various parameters of the JIT, even though this it is
  not strictly necessary.}.  The executable contains both the original
interpreter and the generated JIT compiler: the code starts being interpreted,
then the JIT automatically compiles the so called \emph{hot spots}, i.e. the
parts of the program that are executed more often and thus are most useful to
optimize.  The generated compiler is a \emph{tracing JIT}: Chapter
\ref{cha:tracing-jits} describes the general idea behind it, and the current
state of the art.

From the language implementor point of view, the generation of the JIT
compiler is also mostly transparent: the programmer only needs to annotate the
source code of the interpreter with few \emph{hints} to drive the JIT compiler
generator.  These hints will be covered in details in Chapter
\ref{cha:pypy-jit}.

The JIT compiler generator is divided into a \emph{frontend} and several
\emph{backends}: to avoid confusion with the translation backends described
above, we will refer to these as \emph{JIT backends}.

The frontend contains all the architecture independent code: its job is to
analyze the interpreted running program, find the hotspots, and optimize them.
Its final result is a low level architecture independent representation of the
program to compile: the actual generation of the executable machine code is
done by the JIT backend.  At the moment of writing, there are two maintained
JIT backends:

\begin{itemize}
\item the \textbf{x86} JIT backend, which generates code for the \emph{IA-32}
  architecture, i.e. for all the common 32 bit Intel-compatible processors
  around.  In the future, there will probably be an \emph{x86\_64} JIT backend
  to exploit the new instruction set of the 64 bit processors

\item the \textbf{CLI} JIT backend, which emits bytecode for the CLI virtual
  machine of the .NET Framework.  The generated bytecode will in turn be
  translated into machine code by the .NET's own JIT compiler (see Section
  \ref{sec:jit-layering} for details).
\end{itemize}

It is obvious that the choice of the JIT backend is dependent on the choice of
the translation backend: in particular, the x86 JIT backend is usable only in
conjunction with the C translation backend, and the same for the CLI JIT
backend and its homonym translation backend.

From an implementation point of view, the CLI JIT backend represent one of the
major contributions of this thesis, and will be described in detail in Chapter
\ref{cha:cli-backend}.


\section{Why choosing PyPy}

In summary, we think that PyPy is a very good choice for the kind of research
we are interested in.  First of all, it is a mature project with an already
working infrastructure and a vibrant (although not so large) development
community, which is ideal to develop new ideas and solutions.

Moreover, the architecture and the modularity of the codebase allows us to
concentrate on the main issues we are interested in: in particular, we do not
have to worry about the complex semantics of Python, or to implement all the
well known compilation techniques that form the starting point for the
``interesting'' work.  In addition, by reusing PyPy we can apply the JIT
compilation techniques described in this thesis to a real language, making the
evaluation much more trustworthy than if we applied them to e.g. a toy
language.

Last but not least, by working on a meta level the final result is more than
just a fast implementation of Python: by providing a multiplatform JIT
compiler generator, PyPy may become a very appealing framework to implement in
a simple way all kinds of fast and portable dynamic languages: see for example
\cite{BolzEtAl08} for a description of the implementation of Smalltalk and
in PyPy, and \cite{Bruni09} for a description of PyGirl, a Gambeboy emulator.

% LocalWords:  PyPy bytecode backend backends toolchain Prolog executables CLI
% LocalWords:  RPython CPython runtime hotspots frontend multiplatform