It is possible for me to build my own Interpreter that could then be transformed into a compiler? If yes, how do I go about building it?
- 6Could you elaborate on that a bit? Which language are you referring to? How would "an interpreter that can function as a compiler" be different from a compiler?Syntactic– Syntactic2010-04-14 12:28:43 +00:00Commented Apr 14, 2010 at 12:28
- stackoverflow.com/questions/1669/learning-to-write-a-compileranon– anon2010-04-14 12:33:27 +00:00Commented Apr 14, 2010 at 12:33
- 1@Syntactic: It wouldn't be different, that's the whole point. But you wouldn't have to write a compiler. The PyPy project uses this, for example. You only have to write a very straightforward, simple interpreter for your language and the PyPy framework automatically generates a native code JIT compiler for you.Jörg W Mittag– Jörg W Mittag2010-04-14 12:56:17 +00:00Commented Apr 14, 2010 at 12:56
Add a comment |
3 Answers
This is called the Second Futamura Projection. It was first described by Prof. Yoshihiko Futamura in his 1971 paper Partial Evaluation of Computation Process – An approach to a Compiler-Compiler (Japanese), an English version of which was republished 28 years later.
It uses Partial Evaluation, by partially evaluating the partial evaluator itself with respect to the interpreter, thus yielding a compiler.
So, you need two ingredients: an interpreter for your target language, written in some host language (which may or may not be the same as the target language) and a partial evaluator capable of evaluating both the interpreter and itself, in other words it needs to partially evaluate the host language and it needs to itself be written in the host language it can evaluate.
1 Comment
kibibu
My pop-culture addled brain automatically read that as the Second Futurama Projection
An already mentioned partial evaluation is one of the possible methods (a very computationally intensive one, but quite generic on the other hand). Another approach is metaprogramming: if an interpreter of a language is implemented in a form of a simple translator which targets another interpreted language, it is very easy to re-target it later to some compiled language, or replace the target interpreter with a compiler.
Comments
Apart from Futaruma projections, another approach is meta-tracing jit. Meta-tracing jit doesn't directly trace or jit your programs, but indirectly, through the interpreter. RPython is a cool meta-tracing framework. You write an interpreter in a restricted version of python, and RPython turns it into a jit compiler in C.
