Formale Semantik von OCaml in Coq

14

Die Semantik einer großen Teilmenge von OCaml namens OCamllight wurde vor einigen Jahren von Owens in HOL formalisiert. In jüngerer Zeit wurde in Nuprl eine typentheoretische Semantik einer kleineren Teilmenge von OCaml von Kreitz, Hayden und Hickey implementiert .

Gibt es eine ähnliche Entwicklung bei Coq?

coq program-verification ocaml Andrea Asperti
quelle
Sie könnten an CakeML interessiert sein: cakeml.org . Ich bin allerdings nicht OCaml-spezifisch.
Jmite

Antworten:

12

Haben Sie Arthur Charguérauds Doktorarbeit " Charakteristische Formeln für die Verifikation mechanisierter Programme" gesehen ?

Anstatt das Typensystem und die Kleinschritt-Semantik als induktive Beziehungen aufzubauen, gibt er eine Technik zum Umwandeln von Caml-Programmen in charakteristische Formeln an. Dies ist im Grunde eine Verallgemeinerung der Prädikattransformatorsemantik, um eine sehr große Teilmenge von Ocaml zu unterstützen - insbesondere unsichere Casts wie Obj.magic. Um aus seiner These zu zitieren:

Ich habe mich auf eine Teilmenge der OCaml-Programmiersprache konzentriert, bei der es sich um eine sequentielle Call-by-Value-Programmiersprache auf hoher Ebene handelt. Die aktuelle Implementierung von CFML unterstützt den Kern-λ-Kalkül, einschließlich Funktionen höherer Ordnung, Rekursion, gegenseitige Rekursion und polymorphe Rekursion. Es unterstützt Tupel, Datenkonstruktoren, Mustervergleiche, Referenzzellen, Datensätze und Arrays. Ich stelle eine zusätzliche Caml-Bibliothek zur Verfügung, die Unterstützung für Nullzeiger und starke Aktualisierungen hinzufügt.

Es ist ein sehr ansprechender Ansatz, wenn Sie beweisen möchten, dass ein bestimmtes Caml-Programm korrekt ist (weniger, wenn Sie jedoch an seiner Metatheorie interessiert sind).

Neel Krishnaswami
quelle
Wenn ich das richtig verstehe, ist die Spezifikation der Semantik von Ocaml in das System eingebettet. Ist es möglich, die charakteristische Formel (einer Schlüsselfunktion des) Systems als solche Spezifikation zu interpretieren? Außerdem gehe ich davon aus, dass das System in OCaml geschrieben ist. Ist es möglich, seine Richtigkeit im System selbst zu spezifizieren und nachzuweisen?
Andrea Asperti
Für ein gegebenes OCaml-Programm kann seine charakteristische Formel als Bezeichnungssemantik betrachtet werden, eine "am wenigsten allgemeine" Spezifikation, die verwendet werden kann, um alle wünschenswerten Eigenschaften des Programms zu beweisen. Wenn Sie von der "Korrektheit" der CFML selbst sprechen, lautet die Frage: In Bezug auf welche alternative formale Semantik?
Gasche
Seltsam, ein Programm zu haben, das Software zertifizieren soll und dessen Verhalten nicht spezifiziert werden kann :)
Andrea Asperti
@AndreaAsperti Was meinst du mit "eingebettet in das System"? Die Idee hinter charakteristischen Formeln (CFs) ist recht einfach: Ordnen Sie Programme logischen Formeln zu (normalerweise vor und nach der Bedingung), so dass die Formeln die Semantik der Programme genau beschreiben. Mit anderen Worten, zwei Programme erfüllen die gleichen CFs, wenn sie kontextuell nicht unterscheidbar sind. Die Zuordnung von Programm zu CF erfolgt durch Induktion der Programmstruktur und kann auf jede ausreichend aussagekräftige Logik abzielen. A. Die Coq-Logik des Charguéraud-Ziels, aber das ist eine zufällige Wahl.
Martin Berger
1
@MartinBerger: Die Veröffentlichung von Guéneau et al beweist nur Solidität, weil die abgeleiteten Pre / Posts die Programme, von denen sie stammen, nicht charakterisieren. Ihre CFs leiten sich von der untypisierten Semantik von CakeML ab, aber die typisierte Sprache hat eine andere Beobachtungsäquivalenz. (Für die praktische Überprüfung ist dies nicht sonderlich wichtig und einfacher.)
Neel Krishnaswami
8

Das könnte Sie interessieren: Jacques Garrigues A Certified Implementation of ML with Structural Polymorphism and Recursive Types , das die Solidität statischer und dynamischer Semantik und Eigenschaften von Typinferenz für eine ML-Sprache mit (Rekursions- und) Strukturpolymorphismus festlegt und damit einen der folgenden formalisiert fortgeschrittenere Ecken von OCaml (polymorphe Varianten und Objekttypen).

Das heißt, diese Arbeit zielt mehr darauf ab, die Solidität fortgeschrittener Teile des Typsystems zu überprüfen, als den Funktionsumfang bestehender OCaml-Programme abzudecken. Ich denke, dass CFML eine bessere Wahl ist, um die Korrektheit eines vorhandenen OCaml-Programms zu beweisen.

gasche
quelle