Recent advances in computer science since 2010?

Deriving fast JIT compilers from interpreters. It has long been known, that, in principle, compilers can be derived from interpreters in a mechanical way. This is a special case of partial evaluation, sometimes called Futamura projection [1]. The textbook [2] explains the state-of-the-art at the end of the 1990s. The core problem is that it has been difficult to get compilers derived by partial evaluation to match the performance of handwritten compilers ("O, Partial Evaluator, Where Art Thou?" L. Augustsson, 2010). In a parallel development, (tracing) JIT compilers emerged, their convoluted development might have started with [3]. The core problem with (tracing) JIT compilers is that they are complex, and expensive to develop.

Over the last few years, the situation changed.

• Meta-tracing was developed [4] which turns an annotated interpreter into a tracing JIT compiler. This is the basis of PyPy [5] which is widely used [9].

• In a parallel development, Oracle's new approach to Java compilation, Graal/Truffle [6, 7, 8], is based on partial evaluation, and indeed uses Futamura projections to convert an interpreter into a compiler (Graal is a conventional JIT and Truffle does the Futamura projection). It has been claimed that this is the first time that partial evaluation Futamura projection has led to a performant compiler.

There is clearly some family resemblance between meta-tracing and partial evaluation, but the exact relationship, the shared abstraction, is not fully understood.

---

_{[1] Y. Futamura, Partial Evaluation of Computation Process - An Approach to a Compiler-Compiler.}

_{[2] J. Jones, C. K. Gormand, P. Sestoft, Partial Evaluation and Automatic Program Generation.}

_{[3] J. G. Mitchell, The design and construction of flexible and efficient interactive programming systems.}

_{[4] C. F. Bolz, A. Cuni, M. Fijalkowski, A. Rigo, Tracing the Meta-Level: PyPy's Tracing JIT Compiler.}

_{[5] https://www.pypy.org/}

_{[6] T. Würthinger, C. Wimmer, C. Humer, A. Wöß, L. Stadler, C. Seaton, G. Duboscq, D. Simon, M. Grimmer, Practical partial evaluation for high-performance dynamic language runtimes. https://chrisseaton.com/truffleruby/pldi17-truffle/pldi17-truffle.pdf}

_{[7] https://github.com/oracle/graal/tree/master}

_{[8] https://github.com/oracle/graal/tree/master/truffle}

_{[9] https://news.ycombinator.com/item?id=36940871}

from Hacker News https://ift.tt/hOjQqe2