Meta-tracing

Compiler synthesis technique

Program execution
General concepts
Code Translation Compiler Compile time Optimizing compiler Linking Execution Runtime system Executable Interpreter Virtual machine Intermediate representation (IR)
Types of code
Source code Object code Bytecode Machine code Microcode
Compilation strategies
Ahead-of-time (AOT) Just-in-time (JIT) Tracing just-in-time Compile and go system Precompilation Transcompilation Recompilation Meta-tracing
Notable runtimes
Android Runtime (ART) BEAM (Erlang) Common Language Runtime (CLR) and Mono CPython and PyPy crt0 (C target-specific initializer) Java virtual machine (JVM) LuaJIT Objective-C and Swift's V8 and Node.js Zend Engine (PHP)
Notable compilers & toolchains
GNU Compiler Collection (GCC) LLVM and Clang MSVC Glasgow Haskell Compiler (GHC)
v t e

Meta-tracing is a mostly automatic transformation that takes an interpreter as input and produces a tracing just-in-time compiler as output. Since interpreters are usually easier to write than compilers, but run slower, this technique can make it easier to produce efficient implementations of programming languages.^[1]

The essence of the approach is based on the use of two levels of interpretation, in which a tracing interpreter is used to execute a second interpreter that interprets the target language for which a compiler is to be generated; the tracing interpreter then watches the second interpreter as it executes sequences of intstructions generated from the input program.^[2]

This approach is used by the PyPy project to create their Python compiler, by meta-tracing a Python interpreter written in RPython, a restricted version of the Python programming language.^[3] In the special case of RPython, the RPython language is itself interpreted by an interpreter written in the full Python language, symbolized by the PyPy project's logo of an ouroboros.

RPython has also been used to create an interpreter for the Scheme programming language.^[2]

Meta-tracing can be compared to the AST-guided partial evaluation approach for generating compilers, such as the Truffle/JS compiler for the JavaScript programming language.^[4] Both meta-tracing and AST-guided partial evaluation can be viewed as examples of Futamura projection.

References

[edit ]

^ Bolz, Carl Friedrich; Pape, Tobias; Siek, Jeremy; Tobin-Hochstadt, Sam (2014). "Meta-tracing makes a fast Racket" (PDF). Presented at the 8th Workshop on Dynamic Languages and Applications, June 2014 in Edinburgh, UK
^ ^a ^b Vandercammen, Maarten (June 2015). "The Essence of Meta-Tracing JIT Compilers" (PDF).
^ Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (2009年07月06日). "Tracing the meta-level: PyPy's tracing JIT compiler" . Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems. ICOOOLPS '09. New York, NY, USA: Association for Computing Machinery: 18–25. doi:10.1145/1565824.1565827. ISBN 978-1-60558-541-3.
^ Marr, Stefan; Ducasse, Stéphane (2015年10月23日). "Tracing vs. partial evaluation: comparing meta-compilation approaches for self-optimizing interpreters". Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications. OOPSLA 2015. New York, NY, USA: Association for Computing Machinery: 821–839. doi:10.1145/2814270.2814275. ISBN 978-1-4503-3689-5.

References

See also