Gibt es vollständig optimierte Compiler zum Beenden von Programmen?

In Andrew W. Appels Buch Modern Compiler Implementation in ML sagt er unter Kapitel 17, dass die Computability-Theorie zeigen wird, dass es immer möglich sein wird, neue Optimierungstransformationen zu erfinden, und fährt fort, um zu beweisen, dass ein vollständig optimierter Compiler das Halteproblem lösen wird: Ein Programm Q , das keine Ausgabe erzeugt und niemals anhält, kann leicht durch seine optimale Darstellung ersetzt werden, wobei Opt (Q) "L: goto L" ist. Ein vollständig optimierter Compiler kann also das Problem des Anhaltens lösen.

Meine Frage lautet also: Gibt es einen vollständig optimierenden Compiler zum Beenden von Programmen? Meine einzigen Gedanken sind die folgenden: Obwohl ein Programm garantiert terminiert, kann es immer noch beliebig komplex sein, und für jeden konkreten Optimierungs-Compiler, C, könnte man vielleicht ein Programm konstruieren, das C als Eingabe nimmt und irgendwie ein schlechteres Programm erzeugt als eine Art Eckkoffer.

Auch Was sind die Auswirkungen der Beschränkung selbst Programme beendet?

computability compilers program-optimization Simon 'Reinstate Monica' Shine
quelle

Es ist schwierig, die optimale Befehlssequenz für einen einzelnen Codeblock ohne Kontrollfluss überhaupt zu finden. Der Superoptimierungsartikel auf Wikipedia bietet ein gutes Intro (mit Zitaten.)

Wandering Logic

In dem Wikipedia-Artikel wird erwähnt, dass sich die Superoptimierung mit schleifenfreien Befehlsfolgen befasst. Ich nehme an, es ist eine andere Art zu sagen, dass es endet, wenn es keine Schleifen gibt. Wenn man sich die verfügbaren Referenzen kurz ansieht, scheint dies möglich, aber äußerst kostspielig zu sein.

Simon 'Reinstate Monica' Shine

Was bedeutet hier "optimieren"? Kleinere Laufzeit? Wenn ja, welche: Worst-Case, Average-Case, Every-Case, Some-Case, ...?

Raphael

Antworten:

Ich gehe davon aus, dass Sie an der Optimierung der Laufzeit interessiert sind. Wie ich in meinem Kommentar geschrieben habe, gibt das das Ziel nicht ausreichend vor: Reduziert eine Optimierung die Laufzeit für jede Eingabe, für jede Eingabe, für alle Eingaben im ungünstigsten Fall oder sogar für den Durchschnitt ?

Ich werde zeigen, dass sie alle unmöglich sind. Der Beweis erstreckt sich auf die Optimierung der Länge des Programms.

Denken Sie daran, dass das folgende Problem nicht berechenbar ist:

Bei einer kontextfreien Grammatik mit Terminalalphabet , entscheiden , ob . $G$ $\Sigma$ $\mathcal{L}(G) = \Sigma^*$

Beachten Sie außerdem, dass wir bei einer kontextfreien Grammatik den CYK-Algorithmus für diese eine Grammatik fest codieren können; bezeichnen diesen Algorithmus durch . Wir beobachten , dass für alle Eingänge endet (von ). $G$ $\mathrm{CYK}_G$ $\mathrm{CYK}_G$ $\Sigma^*$

Es sei nun angenommen, dass es einen Optimierer , der bei einem immer abschließenden Algorithmus einen ergebnisäquivalenten Algorithmus ausgibt, der in Bezug auf die Laufzeit optimal ist. Deutlich, $\operatorname{Opt}$ $A$

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^*$

und so haben wir einen Entscheider für ein unberechenbares Problem konstruiert, der der Annahme widerspricht.

Raphael
quelle

Vielen Dank für dieses Argument. Ein paar klärende Fragen: Was ist

? Ich gehe davon aus, dass

die Sprache ist, die durch die Grammatik

erzeugt wird .

Σ *

$\Sigma*$

L (G)

$\mathcal{L}(G)$

G

$G$

Simon 'Reinstate Monica' Shine

Σ^{*}

$\Sigma^{\ast}$

M

$M$

P_{M} (i)

$\mathrm{P}_M(i)$

M

$M$

i

$i$

OPT (P_{M})

$\operatorname{OPT}(\mathrm{P}_M)$

' r e t u r n f a l s e;'

$\text{'}\mathtt{return\ false;}\text{'}$

M

$M$

sdcvvc