Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator?
Whenever the Futamura projections are described, it's always at a conceptual level, in general terms. Reading a blog post like this one, I'm always left to wonder (a) why does this not end with a link to a github implementation of a general partial evaluator and (b) why is it the case that none of the compilers I use were produced with these techniques?
There must be some set of tradeoffs preventing this approach from living up to the "compilers for free" promise, but I haven't found anyone with a real explanation. Either there must be hard challenges which make implementing a general partial evaluator very difficult, or the results that we'd get from using such a partial evaluator are poorer than what we get through other means right?
Perhaps the greatest success in this direction is PyPy. At some level the RPython toolchain is general enough that people have used it to produce JITted versions of ruby, php and a few other languages. But these are a handful of alternative implementations to existing languages, where the predominant implementation doesn't use this toolset. And PyPy's own docs note that the JIT compiler needs some amount of hinting from the interpreter; you can't just throw any interpreter (written in RPython) at it.
If you're interested in looking into some active research in the area of partial evaluation, you should look at Truffle [1] and Graal [2] from my team at Oracle Labs. Graal is a new JIT compiler for HotSpot written in Java, with an API to interact with the compiler from Java. Truffle is a toolkit for implementing programming languages as self-optimizing AST interpreters. Truffle uses the Graal hooks to perform partial evaluation of Truffle-based interpreters to generate highly optimized native code.
The partial evaluator doesn't know anything about the language being compiled, save for a few annotations that Truffle provides to control inline caches and such. We're using this approach to create new optimizing runtimes for Ruby (TruffleRuby), JavaScript (Graal.js), R (FastR), Python (GraalPython), and even LLVM bitcode (Sulong). There are languages being implemented outside of Oracle Labs as well [3]. So, it's being stressed by a wide range of language semantics.
As for performance... I work mostly on TruffleRuby. There we're seeing considerable performance advantages against other Ruby implementations across a wide array of benchmarks and workloads. We really do get the JIT for free by virtue of being a Truffle-based language implementation. It's quite liberating as the compiler technology is free to evolve separately from our Ruby implementation, in contrast to the tight coupling you'd have with a language-specific JIT.
Fair enough. You could date the project back to the Maxine days as well :-)
Joking aside, the Java-Level JVM Compiler Interface [1] was only added about a year ago, in Java 9. This is what allows using Graal with a stock JVM. So, for many people this is the point at which Graal became available.
Graal has a history going through Maxine, to HotSpot C1. It's been evolving for years, yes, but its application as a partial evaluator only goes back to 2012. TruffleRuby was started in 2013.
> Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator?
I think the rationale for abandoning partial evaluation for PyPy [1] explains most complications with it. Or put in different words, PE-based compilers don't have all necessary knobs that real compilers need.
> Why is it that [...] when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator?
As far as I know, it has been tried numerous times and has been an area of active research in the past, but results turned out unsuccessful. Mainly because error reporting and performance, both compile-time and run-time, is hard to achieve.
It's a little bit like pure functional programming. Super elegant in principle, hard to get right and usable in practice.
> As far as I know, it has been tried numerous times and has been an area of active research in the past, but results turned out unsuccessful.
TruffleRuby is a Ruby implementation that works exactly by writing an interpreting and passing it through a general partial evaluator. It's successful enough to pass almost all the Ruby spec and to run real Ruby applications including their C extensions.
> Mainly because error reporting and performance, both compile-time and run-time, is hard to achieve.
Do you have more information on the error reporting bit? Is it due to losing important metadata during compilation? If so, couldn't a different, more metadata-rich representation than the basic AST most of us are familiar with help here?
wild guess, maybe it's like yacc vs hand made recursive descent parsers.. the former doesn't allow enough control so people prefer doing the effort so they can change bits here and there
Whenever the Futamura projections are described, it's always at a conceptual level, in general terms. Reading a blog post like this one, I'm always left to wonder (a) why does this not end with a link to a github implementation of a general partial evaluator and (b) why is it the case that none of the compilers I use were produced with these techniques?
There must be some set of tradeoffs preventing this approach from living up to the "compilers for free" promise, but I haven't found anyone with a real explanation. Either there must be hard challenges which make implementing a general partial evaluator very difficult, or the results that we'd get from using such a partial evaluator are poorer than what we get through other means right?
Perhaps the greatest success in this direction is PyPy. At some level the RPython toolchain is general enough that people have used it to produce JITted versions of ruby, php and a few other languages. But these are a handful of alternative implementations to existing languages, where the predominant implementation doesn't use this toolset. And PyPy's own docs note that the JIT compiler needs some amount of hinting from the interpreter; you can't just throw any interpreter (written in RPython) at it.