Partial evaluation means to fix some variables in the given code before execution. With a traditional implementation of a compiler or an interpreter, all variables are replaced with its value on each evaluation of that variable. This is because a variable can change at any timing. This is, however, not always true in actual applications. Almost all of large applications has setting variables and data variables. The former is set statically by command-line arguments or setting files, so they does not change on running.
Partial evaluation is formalized as follows. Take an source code s
and the set of variables v in s. v can be split into two set
of variables. One is Vc, whose element has a fixed corresponding
value (c) before execution. The other is Vs, whose value cannot be
defined statically, vary on the each execution of that part of the
code. Partial evaluating function mix has the following type.
mix :: source -> constants, configured values -> s*
The output s* is a function from data which fix on execution to the
result.
The basic idea of Futamura projection is to see an interpreter and a
source code as input of mix [1]. A source code is a string. An
interpreter is taken as a 2-ary function. mix takes a 2-ary
operator and some kind of data.
Let's introduce the notion of the universal evaluator to understand Futamura projection. The most generalized form of evaluation is what takes an interpreter of a language, a source code written in the language, and input data, then outputs the result. With this evaluator, one can run any source code if he has an interpreter for its language (you may think it is obvious, but this characteristic is useful in application. See the next section).
univEval :: interpreter -> source -> input -> output
Futamura projection is equal to partial application on this univEval
using mix defined in the previous section. There are 3 kinds of
Futamura projection. The first projection,
mix int s (int: interpreter, s: source)
corresponds to
univEval int s.
The return value is a function with type input -> output. This is an "executable".
The second is
mix mix int
which corresponds to
univEval int.
The type of the return value is source -> input -> output, the same as a "compiler".
The third
mix mix1 mix2 (mix2 is for interpreter, from #2).
is univEval itself. This is an universal compiler generator.
Here, an executable and a compiler is a bit different from usual
meaning. An executable is not necessarily written in native code.
It just takes data, then outputs. A compiler does not necessarily
generates a native code from a source code. It takes an source code
and input and outputs the result.
The merit of this approach is that writing an interpreter is usually easier then writing a compiler from scratch, or using compiler-compiler with a translator description language [2].
The speed of generated programs is a different question. It is obvious that a native code binary is faster than its interpreter version. However, as mentioned above, Futamura projection is nothing to do with the kind of a generated code. It is up to the implementation. In order to see this point in detail, we will see PyPy, or the RPython toolchain in the next section.
PyPy used to have two meanings. Recently, however, the RPython toolchain refers to the translation toolchain for RPython script, and PyPy refers to only the interpreter written in RPython using the toolchain. In this section, I will cover the RPython toolchain, and take PyPy as the example.
The RPython toolchain is practical implementation of univEval. "The
job of the translation toolchain is to translate RPython programs into
an efficient version of that program for one of various target
platforms"[3]. What it does is the second Futamura projection. In
our definition, this generates a "compiler" from an interpreter, but
usually the generated program is called as an interpreter, because it
needs a source and data at the same time.
Note that the RPython toolchain can also be used to make an executable,
like a compiler. In this case, the input program is an
ordinal program. Such operation corresponds to the first Futamura
projection. See /pypy/pypy/translator/goal/targetnopstandalone.py
for a hello-world example.
One benefit of this is that one can generate many binaries and byte-codes from a single interpreter implementation, thanks to rich libraries of the toolchain[4]. Currently, C, llvm, JVM and CLI are supported. Moreover, RPython, a reduced Python, is rich enough for fun programming experience. No one want to write enormous C programs, are you?
Another point is that PyPy is faster (about 2 to 5 times) than CPython, the Python implementation in C. These two are interpreters of python, and have almost the same features. The secret is in JIT compiling. Usually, JIT compiler is needed for each interpreter and each platform. The RPython toolchain has only one JIT compiler, but it is applied to the interpreter (written in RPython)[5]. Moreover, RPython offers easy ways to configure JIT compilation[6]. By the way, JIT compilation is also an implementation of the first Futamura projection. It takes a byte-code and generate a native code, that is, an executable.
Futamura projection is an abstract notion, so it seems to be difficult
at first glance. However, I found PyPy. It is a widely-used
production-ready mix tool. Partial evaluation is easier in
functional languages, because a pure function is free from the
problem of variables' sudden mutation. A strict type system is also
help for compilation into native codes. But Python is a dynamic,
object oriented language. Cool.
I told about Python, but I am not a pythonista. I believe I am a rubyist. However, the JIT / AOT compiling support is miserable for ruby. Especially rails is said to be heavy, memory hungry. Rails is just an web framework. What he does is just to accept a HTTP request, to gather data, then to return something. I am sure that it can be compiled on deployment to be much faster and resource effective.
- Yoshihiko Futamura, "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler", Higher-Order and Symbolic Computation 12, 381–391 (1999)
- Yoshihiko Futamura, "EL1 Partial Evaluator (Progress Report)"
- PyPy - The RPython Toolchain — PyPy 1.9 documentation
- PyPy - RPython toolchain — pypyja 1.7 documentation
- Motivating JIT Compiler Generation — pypyja 1.7 documentation
- 流行りのJITコンパイラは嫌いですか? — PyPy Advent Calendar 2011 v1.0 documentation