Re: Are there "compiler generators"?

From	Martin Ward <martin@gkc.org.uk>
Newsgroups	comp.compilers
Subject	Re: Are there "compiler generators"?
Date	2022-05-29 12:00 +0100
Organization	Compilers Central
Message-ID	<22-05-059@comp.compilers> (permalink)
References	<22-05-054@comp.compilers>

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Are there "compiler generators"? Roger L Costello <costello@mitre.org> - 2022-05-28 22:27 +0000
  Re: Are there "compiler generators"? "Robin Vowels" <robin51@dodo.com.au> - 2022-05-29 13:34 +1000
  Re: Are there "compiler generators"? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-05-28 23:52 -0700
  Re: Are there "compiler generators"? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-05-29 06:45 +0000
  Re: Are there "compiler generators"? Thomas Koenig <tkoenig@netcologne.de> - 2022-05-29 09:14 +0000
    Re: Are there "compiler generators"? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-05-30 14:53 +0200
      Re: Are there "compiler generators"? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-05-31 12:57 +0200
        Re: Are there "compiler generators"? gah4 <gah4@u.washington.edu> - 2022-05-31 16:55 -0700
          RE: Are there compiler generators? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-06-01 14:07 +0300
  Re: Are there "compiler generators"? Martin Ward <martin@gkc.org.uk> - 2022-05-29 12:00 +0100
    Re: Are there "compiler generators"? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-05-30 07:35 +0000
  Re: Are there "compiler generators"? Fernando <pronesto@gmail.com> - 2022-05-29 05:00 -0700
  Re: Are there "compiler generators"? gah4 <gah4@u.washington.edu> - 2022-05-29 23:29 -0700
    Re: Are there "compiler generators"? mac <acolvin@efunct.com> - 2022-06-09 14:12 +0000
  Re: Are there "compiler generators"? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-05-30 20:20 +0000

csiph-web