Re: Are there "compiler generators"?

Martin Ward <>
Sun, 29 May 2022 12:00:12 +0100

          From comp.compilers

Related articles
Are there "compiler generators"? (Roger L Costello) (2022-05-28)
Re: Are there "compiler generators"? (Robin Vowels) (2022-05-29)
Re: Are there "compiler generators"? (Jan Ziak) (2022-05-28)
Re: Are there "compiler generators"? (2022-05-29)
Re: Are there "compiler generators"? (Thomas Koenig) (2022-05-29)
Re: Are there "compiler generators"? (Martin Ward) (2022-05-29)
Re: Are there "compiler generators"? (Fernando) (2022-05-29)
Re: Are there "compiler generators"? (gah4) (2022-05-29)
Re: Are there "compiler generators"? (2022-05-30)
Re: Are there "compiler generators"? (Hans-Peter Diettrich) (2022-05-30)
Re: Are there "compiler generators"? (Kaz Kylheku) (2022-05-30)
Re: Are there "compiler generators"? (Hans-Peter Diettrich) (2022-05-31)
[7 later articles]
| List of all articles for this month |

From: Martin Ward <>
Newsgroups: comp.compilers
Date: Sun, 29 May 2022 12:00:12 +0100
Organization: Compilers Central
References: 22-05-054
Injection-Info:; posting-host=""; logging-data="54404"; mail-complaints-to=""
Keywords: tools, theory
Posted-Date: 29 May 2022 18:16:48 EDT
In-Reply-To: 22-05-054
Content-Language: en-GB

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.

Futamura, Y. (1999). "Partial Evaluation of Computation Process—An
Approach to a Compiler-Compiler". Higher-Order and Symbolic Computation.
12 (4): 381–391. CiteSeerX 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.)


Dr Martin Ward | Email: |
G.K.Chesterton site: | Erdos number: 4

Post a followup to this message

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