Re: Are there "compiler generators"?

On 28/05/2022 23:27, Roger L Costello wrote:
> There are lexer generators. Flex is a lexer generator.
>
> There are parser generators. Bison is a parser generator.
>
> Are there compiler generators?


Suppose a program F(x, y) takes two inputs and produces
an output. Suppose input x is known at compile time.
Then we can optimise the program F(x, .) by precomputing
all the computations that depend on x to give a program
G(.) which can be applied to y to produce the output F(x, y):


G(y) = F(x, y)


This optimisation process is called "partial evaluation"
or "specialisation".


An interpreter is a program F(p, d) which takes
a program p and some input data d and produces
the result of executing p on d.


In theory a partial evaluator (a "specialiser") can be applied
to an interpreter and the source code for a program to give
an executable which is a specialised version of the interpreter
which only runs the given source code, does not require
the source code to be applied and runs faster than
the original combination of interpreter and source code.


To take this to the next level: specialising the specialiser
for the interpreter generates a compiler for the interpreted
language. So this is a type of "compiler generator".


Finally, specialising the specialiser for itself gives a tool
that can convert any interpreter into an equivalent compiler.


https://en.wikipedia.org/wiki/Partial_evaluation


Futamura, Y. (1999). "Partial Evaluation of Computation Process—An
Approach to a Compiler-Compiler". Higher-Order and Symbolic Computation.
12 (4): 381–391. CiteSeerX 10.1.1.10.2747. doi:10.1023/A:1010095604496.
S2CID 12673078.


In practice, there is a lot more to writing a compiler than just
partially evaluating an interpreter.


(The difference between theory and practice is that in theory there
is no difference between theory and practice, but in practice there is.)


--
Martin


Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

Return to the comp.compilers page.
Search the comp.compilers archives again.