13
$\begingroup$

The Futamura projections are a series of three transformations that can be performed on interpreters, compilers, and compiler-compilers respectively. These transformations rely on a specializer which performs partial evaluation. In The Book (Partial Evaluation - Practice and Theory (1998) from DIKU, DOI, PDF), there is a slogan which is reused several times: if the specializer is any good, then its residue will be, too. (The outputs of specializers are called "residues," or "residual programs.")

The first Futamura projection says that we may specialize an interpreter with respect to a given program, resulting in a native executable which runs on the same machine as the interpreter but implements the given program. That sounds like a compiler! So, we could turn interpreters into compilers. This is one version of the mantra: if the interpreter and specializer are any good, then the residual program will be, too.

Okay, but in practice, why is it so difficult to implement the first Futamura projection? Specifically, since writing an interpreter is well-understood at this point, why is it so difficult to write a specializer which can be used as a compiler?

This question is a generalization of that question, which asks about constant expression evaluation in C and C relatives; note that I'm using "difficult" instead of hard. See also that answer of mine on CS SE where I make an analogy with emulators, which are also difficult to write.

$\endgroup$
4
  • 1
    $\begingroup$ Somebody else can ask about the second projection. I think that the answers will be different. Also, can we get "jit" and "futamura" tags, please? Note that I can answer my own question in a few days, but I genuinely want to build an interdisciplinary knowledge base here, so please consider answering! $\endgroup$
    – Corbin
    Commented Jul 4, 2023 at 4:05
  • 1
    $\begingroup$ We already have just-in-time, so I've added it to your post for you. $\endgroup$
    – Bbrk24
    Commented Jul 4, 2023 at 4:07
  • $\begingroup$ Is there any reason why Graal and PyPy not mentioned anywhere? $\endgroup$
    – FloriOn
    Commented Oct 26, 2023 at 7:59
  • $\begingroup$ @FloriOn: They aren't directly relevant. I agree that the underlying toolkits, Truffle and RPython respectively, were difficult to implement. This question is about why such toolkits are difficult to create in the first place. $\endgroup$
    – Corbin
    Commented Oct 26, 2023 at 18:03

2 Answers 2

5
$\begingroup$

If the question is "why isn't this used in practice", I think the answer is twofold:

First, specializers are complex tools. It's likely that you'll need to refactor the interpreter at least a little bit to turn it into something that the specializer can work with. Or you might need to come up with a custom specializer for your interpreter.

Second, the resulting performance might not be that great. For example, last time I specialized the interpreter we noticed it was good for optimizing control but not that good at optimizing data representation. The specializer could get rid of bytecode dispatching turn the jump instructions into gotos, exposing the control flow graph. However, we still stored the local variables remained in the heap, as the interpreter did. If we were to write a compiler from scratch it would be desirable to store things in machine registers when possible.

$\endgroup$
1
$\begingroup$

Why is it difficult? It is not difficult at all. Refal implementations do it in quite a straightforward way. I implemented it for a few toy languages quite easily. All you need is to crank up the aggressive inlining, partial specialisation and constant folding in your compiler, and make sure constant folding works with complex data structures as well, such as hash maps or associative lists you may use as symbol tables in an interpreter you're specialising against a code.

Having said that, I don't see that much practical value in this - writing an interpreter is significantly more complicated than writing a compiler, so there's no point in doing such a resource intensive specialisation just to turn your interpreter into a compiler - just write a compiler instead, it's much easier and more maintainable than any interpreter.

There is some practical value in aggressive specialisation, as there is often some ad hoc interpretation that is not even recognised as such - e.g., handling configuration files, or interpreting dynamic data structures (think of how most of the widget libraries work, constructing trees of widgets dynamically). Some of such cases can benefit from an aggressive specialisation indeed, but it's not that practical in cases where you can just write a compiler.

EDIT: to elaborate on a point of why compiler is always simpler than an interpreter:

  • Compilation can be as easy as a sequence of tree rewrites. You don't even need a Turing-complete language for it
  • Every complex tree rewrite pass can be broken down into a sequence of simpler passes
  • There is no need to maintain any complex state in between passes, and, if needed, everything can be encoded in the tree itself, so passes are isolated. It makes the complexity of the compiler no higher than the complexity of the most complex pass, while for the interpreter complexity is the sum of complexity of all its components
$\endgroup$
28
  • 11
    $\begingroup$ I strongly disagree that a compiler is ever easier to write than a interpreter $\endgroup$
    – mousetail
    Commented Jul 4, 2023 at 9:03
  • 5
    $\begingroup$ In a interpreter you first parse the code, then just loop over the lines and run each one. A simple recursive approach is very easy to implement. Writing a compiler required knowledge of the target platform and the exact instruction set. The higher level constructs will not map easily to machine code or even to something like LLVM IR. There are a lot of edge cases you can get wrong. Also you will need to implement any runtime features in machine code instead of your preferred hosting language. $\endgroup$
    – mousetail
    Commented Jul 4, 2023 at 9:56
  • 1
    $\begingroup$ @mousetail this "just loop" is exactly where all the complexity is. It is not "easy to implement", as you need to think of the name lookup semantics (and it's hard to get it right). It's hard to ensure correctness of interpretation. Hard to make your interpreter easy to read and to maintain, as the entire language semantics is unavoidably entangled into a single code path, inside this "just loop" thing. You cannot split it into smaller parts. With a compiler - it's just a sequence of tree rewrites. You can write as many rewrite steps as you want, with each as simple as possible. $\endgroup$
    – SK-logic
    Commented Jul 4, 2023 at 9:59
  • 2
    $\begingroup$ In general my main argument is: If you compile, you need to implement every operation in machine code. If you interpret, you can implement all of them in a higher level language $\endgroup$
    – mousetail
    Commented Jul 4, 2023 at 10:03
  • 4
    $\begingroup$ @mousetail I'd rather avoid using this pointless term "transpiling", it makes zero sense. Compilation is compilation. Is Clang a "transpiler" from C++ to LLVM IR? Is gcc a "transpiler" from C++ to GIMPLE? $\endgroup$
    – SK-logic
    Commented Jul 4, 2023 at 11:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .