Re: Stack based-Register Based

"Jonathan Barker" <ucapjab@ucl.ac.uk> writes:
> However, I don't know that provably optimal (or even associative)
> optimisers exist.


There is a proof that an optimal optimiser doesn't exist.


Given any finite optimising compiler, C(x), there must be some
program P which does not halt, but for which C(P) is not ABORT.
(If C(P) = "ABORT" for every halting program P then you have solved
the Halting Problem!)


Then the new compiler:


C'(x) == IF x = P THEN RETURN("ABORT") ELSE C(x) FI


optimises better than C(x) on program P, and just as well as C(x)
on every other program.


Therefore C(x) is not optimal.


This is known as the "Full Employment Theorem for Compiler Writers":
for any optimising compiler there exists a better one.


I am sure you are all glad to know that :-)


Martin


Martin.Ward@durham.ac.uk http://www.dur.ac.uk/martin.ward/ Erdos number: 4
G.K.Chesterton web site: http://www.dur.ac.uk/martin.ward/gkc/

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