Zertifizierter Compiler und Optimierungen in Coq / Agda

9

Ich interessiere mich für verifizierte Compiler, die in der Martin-Löf-Typentheorie formalisiert sind, dh Coq / Agda. Im Moment habe ich ein kleines Spielzeugbeispiel geschrieben. Damit kann ich beweisen, dass meine Optimierungen korrekt sind. Zum Beispiel können Additionen mit Null eliminiert werden, dh Ausdrücke wie "x + 0".

Gibt es Optimierungen, die mit einem regulären Compiler schwer durchzuführen sind und als gutes Beispiel dienen? Ist es möglich, bestimmte Eigenschaften eines Programms zu beweisen, die Optimierungen ermöglichen, die mit einem regulären Compiler nicht möglich sind? (dh ohne die Folgerung, die mit einem Theorembeweiser möglich ist)

Ich würde mich für Ideen oder Beispiele und auch Referenzen zum Thema interessieren.

Eine verwandte Frage: Compiler-Korrektheitsnachweise

edit: Wie Tsuyoshi es schön in den Kommentaren formulierte: Ich suche nach Optimierungstechniken, die schwierig zu implementieren sind, wenn ein Compiler in (sagen wir) C geschrieben ist, aber einfacher zu implementieren sind, wenn ein Compiler in (sagen wir) Coq geschrieben ist. Während Agda nach C kompiliert (über Haskell), ist es möglich, alles, was in Agda möglich ist, auch in C zu tun. Der einzige Vorteil von Theoremprüfern wie Coq / Agda besteht wahrscheinlich darin, dass der Compiler und die Optimierungen verifiziert werden können.

edit2: Wie von Vijay DI vorgeschlagen, schreibe, was ich bisher gelesen habe. Ich habe mich hauptsächlich auf Xavier Leroy und das CompCert-Projekt bei INRIA konzentriert (es gibt ein 80-seitiges Papier, das meiner Meinung nach gut gelesen werden kann). Ein zweites Interesse galt der Arbeit von Anton Setzer an interaktiven Programmen. Ich dachte, dass seine Arbeit vielleicht verwendet werden könnte, um Eigenschaften von IO-Programmen und die Bisimulation von IO-Programmen zu beweisen. Vielen Dank, dass Sie Sewell erwähnt haben. Ich habe seinen Vortrag "Geschichten aus dem Dschungel" am ICFP gehört und vielleicht 2-3 seiner Papiere gelesen. Aber ich habe seine Arbeit und die seiner Mitautoren nicht speziell betrachtet.
Ich habe noch nicht herausgefunden, wo ich anfangen soll, oder nach Artikeln zur Optimierung von Compilern gesucht. zB, welche Optimierungen in der Einstellung eines verifizierten Compilers interessant wären.

mrsteve
quelle
1
„Gibt es Optimierungen, die mit einem normalen Compiler schwer durchzuführen sind?“: Ist das nicht unmöglich? Wenn ich einen Korrektheitsnachweis von einem verifizierten Compiler entferne, bekomme ich einen regulären Compiler. Daher kann alles, was ein verifizierter Compiler tun kann, auch von einem regulären Compiler ausgeführt werden. Der Punkt eines verifizierten Compilers ist, dass er keine falsche Optimierung durchführen kann . (Mein Wissen über Compiler und Programmüberprüfung ist minimal. Entschuldigen Sie, wenn ich den Punkt verpasse.)
Tsuyoshi Ito
@ Tsuyoshi danke für deinen Kommentar. Ich meinte: Kann ich bestimmte Eigenschaften (die garantiert gültig sind) für ein Programm nachweisen (z. B. eine Unterroutine ist nicht eintretend und kann sich niemals selbst aufrufen), die es ermöglichen, Optimierungen durchzuführen, die normalerweise nicht möglich sind. Einige Invarianten sind für ein Programm möglicherweise schwer zu überprüfen, und möglicherweise werden diese Optimierungen nicht von häufig verwendeten Compilern durchgeführt. Aber vielleicht irre ich mich völlig.
Herr Steve
1
Sprechen Sie über einen in Coq / Agda geschriebenen Compiler oder einen Compiler für Coq / Agda? Ich dachte, Ihre Frage bezog sich auf einen in Coq / Agda geschriebenen Compiler, aber ich glaube nicht, dass ein in Coq / Agda geschriebener Compiler mehr Eigenschaften über Zielprogramme beweisen kann als ein in C geschriebener Compiler.
Tsuyoshi Ito
2
Es wäre gut, der Frage hinzuzufügen, was Sie gelesen haben. Kennen Sie die Arbeit an verifizierter Zusammenstellung - zum Beispiel die von Xavier Leroy? Oder das von Peter Sewell und Mitarbeitern?
Vijay D
1
Es gibt keine derartigen Optimierungen, es sei denn, Sie schränken Ihre Frage weiter ein. Im Extremfall kann der C-Compiler einen Theorembeweiser heimlich in seinen Darm implementieren (und die meisten tun dies tatsächlich in begrenztem Umfang). Ich denke, es ist unklar, was Sie unter "regulärem Compiler" verstehen.
Andrej Bauer

Antworten:

5

Dieses Papier von Yves Bertot, Benjamin Gr´egoire und Xavier Leroy erstellt einen optimierenden Compiler für eine C-ähnliche Sprache, der ausschließlich auf der Coq-Spezifikation basiert. Ein Teil dieser Technologie wird offenbar im CompCert C-Compiler verwendet .

Ein strukturierter Ansatz zum Nachweis von Compiler-Optimierungen basierend auf Datenflussanalysen

Es wird die Richtigkeit von zwei Optimierungen berücksichtigt, der konstanten Ausbreitung (CP) und der gemeinsamen Eliminierung von Unterausdrücken (CSE), Abschnitt 4. Diese Optimierungen sind weiter fortgeschritten als diejenigen, die den nicht Coq-basierten Compilern für dieselbe Sprache zugeordnet sind. siehe zB dieses Benchmark-Diagramm im Vergleich zu gcc. (Der Coq-basierte Compiler ist vermutlich langsamer zu kompilieren, obwohl dies selten erwähnt wird!)

Ein ursprünglicher Aspekt von ConCert ist, dass der größte Teil des Compilers in einem rein funktionalen Stil direkt in der Coq-Spezifikationssprache geschrieben ist. Der ausführbare Compiler wird durch automatisches Extrahieren von Caml-Code aus dieser Spezifikation erhalten.

Am Ende des Dokuments wird jedoch darauf hingewiesen, dass es in realen Compilern einige Compiler-Optimierungen gibt, die in ihrem Framework nicht modelliert werden können.

Eine verbesserte Optimierung ist hier nicht das einzige zu berücksichtigende Element. Ein weiterer Aspekt ist, dass die Compiler-Optimierungslogik aufgrund ihrer Komplexität subtilen Fehlern unterliegen kann. Im Laufe der Jahre wurde festgestellt, dass gcc Fehler in seinen zahlreichen Optimierungslogikroutinen aufweist. zB gcc bug?

vzn
quelle
3

Kann ich bestimmte Eigenschaften (die garantiert gültig sind) für ein Programm nachweisen (z. B. eine Unterroutine ist nicht eingegeben und kann sich niemals selbst aufrufen), die es ermöglichen, Optimierungen durchzuführen, die normalerweise nicht möglich sind.

Dies entspricht der Erweiterung des Typecheckers, um dem Optimierer einige Eigenschaften eines Programms bereitzustellen. Ich glaube, Tsuyoshi Ito hat Recht und Sie sind vielleicht ein wenig irregeführt in Bezug auf Coq. Es ist ein großartiges Tool für die Bereitstellung eines fehlerfreien Compilers, aber in dem von Ihnen beschriebenen Fall bietet es den statischen Analysen keine größere Leistung.

Das einzige, was ich über die Stärkung statischer Analysen mit Coq nachdenken kann, ist, Ihre Sprache mit Behauptungen auszustatten, die einige vom Benutzer geschriebene Beweise enthalten. - Wenn der Compiler selbst in eine Sprache übersetzt würde, die eine Feder für die dynamische Typüberprüfung enthält, und wenn die vom Benutzer geschriebenen Proofs in Funktionen konvertierbar wären, könnten diese Funktionen als erforderliche Eigenschaften für einige Untertypisierungen oder Optimierungen angewendet werden. - Dies würde dem Compiler tatsächlich mehr Leistung bringen.

Soweit ich jedoch sehen kann, wäre es ziemlich nützlich, um die Subtypisierung zu verstärken. - Es ist schwierig, einen Programmierer wissen zu lassen, welche Eigenschaft an welcher Stelle für den Optimierer hilfreich wäre.

Nummer47
quelle