7

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?

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
wantoknow
  • 573
  • 1
  • 6
  • 15
  • 6
    Could 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 Apr 14 '10 at 12:28
  • http://stackoverflow.com/questions/1669/learning-to-write-a-compiler –  Apr 14 '10 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 Apr 14 '10 at 12:56

3 Answers3

11

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.

Community
  • 1
  • 1
Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653
0

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.

SK-logic
  • 9,605
  • 1
  • 23
  • 35
0

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.

Matty
  • 1