Prototyping-Tool für Programmiersprachen-Semantik

11

Gibt es ein Tool zum Prototyping einer Programmiersprachen-Semantik und eines Typsystems, das auch eine Art Modellprüfung von Standardeigenschaften wie der Typensicherheit ermöglicht?

Ich frage dies, weil ich ein Buch über Legierung lese und es genau die Funktionalität bietet, die ich möchte, aber für Modelle, die mit relationaler Logik ausgedrückt werden.

Ich kenne Ott , aber es verfügt nicht über diese Art der "Modellprüfung", da es sich auf die Generierung von Code für Proof-Assistant-Systeme konzentriert.

Jeder Hinweis auf eine solche Tool-Existenz wäre nett.

reference-request programming-languages semantics model-checking Rodrigo Ribeiro
quelle
1
Ott ist Schritt eins, dann überprüfen Sie das Modell in Ihrem bevorzugten Proof-Assistenten.
Gilles 'SO - hör auf böse zu sein'
@ Gilles: Ok, aber ein Punkt eines Modellprüfwerkzeugs ist, dass es eine ganze Reihe von Elementen einer bestimmten Größe generiert, um zu überprüfen, ob die Eigenschaft tatsächlich für sie gültig ist. Auf diese Weise muss ich diesen Generierungsteil für jede definierte Sprache codieren. Wussten Sie, ob es eine Möglichkeit gibt, diesen Generierungsschritt zu automatisieren?
Rodrigo Ribeiro
Technisch gesehen können Sie dies in einem Proof-Assistenten tun (zumindest in einem wie Coq), aber es wird wahrscheinlich sehr langsam sein. Proof-Assistenten sind auf von Menschen unterstützte Proofs ausgerichtet, anstatt automatisch Millionen von Möglichkeiten auszuprobieren, um das Problem zu lösen. Wenn Sie Ott wiederverwenden möchten, können Sie ein Backend für Ihren Lieblingsmodellprüfer hinzufügen.
Gilles 'SO - hör auf böse zu sein'

Antworten:

8

Obwohl es Frameworks gibt, die speziell für das Prototyping von Programmiersprachen erstellt wurden (einschließlich ihrer Semantik, Typsysteme, Auswertung sowie Überprüfung ihrer Eigenschaften), hängt die beste Wahl von Ihrem speziellen Fall und Ihren spezifischen Anforderungen ab.

Trotzdem gibt es mehrere (vielleicht nicht so unterschiedliche) Alternativen, die Sie wählen könnten (einschließlich der bereits erwähnten):

  • Verwenden einer bestimmten Sprache / eines bestimmten Frameworks zum Erstellen und Prototyping neuer Sprachen: Beispiel: Redex [1], eine in Racket eingebettete domänenspezifische Sprache zum Spezifizieren und Überprüfen der (betrieblichen) Semantik von Programmiersprachen, die eine Definition von a Sprache, bietet eine einfache Handhabung von Aufgaben wie Satz (in Latex), Überprüfung von Reduktionsspuren, Komponententests und Zufallstests (z. B. zur Überprüfung der Eingabe)
  • Verwendung allgemeiner Modellierungssprachen, mit denen bestimmte Analysen einfach definiert und durchgeführt werden können, sofern sie die jeweilige Sprache im erforderlichen Umfang erfassen können; Alloy [2] ist ein Beispiel für einen solchen Ansatz: Obwohl Sprachen ziemlich allgemein und flexibel sind, können Sprachen als Beziehungen zwischen Zuständen modelliert werden, während die Unterstützung für die Modellprüfung (z. B. Bewertung innerhalb einer solchen Sprache) kostenlos ist, nachdem die Semantik mit a ausgedrückt wurde Beziehungsmodell (zB einige Ideen zur Modellierung der Semantik einer Sprache finden Sie in [3])
  • Einbetten der Sprache, um ihre Eigenschaften mit einem Theorembeweiser zu überprüfen; Ein Beispiel wäre die Definition der Sprache sowie ihrer Semantik durch Einbettung in ein Beweissystem wie Coq [4] (weitere Einzelheiten zu diesem Ansatz sowie die Diskussion und Demonstration des Unterschieds zwischen tiefer und flacher Einbettung in Coq finden Sie in [ 5])
  • Verwendung von Ott (wie bereits erwähnt, mit ähnlichem Geist wie Redex, aber Bereitstellung einer neuen Definitionssprache, anstatt eingebettet zu sein); Mit Ott können Sie die Programmiersprache in einer praktischen Notation definieren und Sätze und Definitionen in einem Proof-System (normalerweise mit tiefer Einbettung) erstellen, in dem die meisten Überprüfungen (dh Proofs) manuell durchgeführt werden müssen
  • Entwicklung der Sprache und ihrer Semantik sowie entsprechende Überprüfungen (z. B. als Tests) "von Grund auf" in einer universellen Programmiersprache und gegebenenfalls Übersetzung in andere Systeme zu Überprüfungszwecken (einige Sprachen wie Leon [6], Integrierte Verifizierer enthalten, mit denen bestimmte Eigenschaften automatisch überprüft werden können, und die diesen Ansatz der Einbettung in ein Proofsystem ähneln.

Beachten Sie, dass es einen Kompromiss zwischen der einfachen Verwendung des Frameworks / Tools (z. B. so einfach wie das Auslegen der Definition auf Papier oder in Latex) und der Leistungsfähigkeit der Mechanismen zum Überprüfen der Eigenschaften der Sprache (z. B. Einbetten der Die Sprache in einem Theorembeweiser kann es ermöglichen, sehr ausgefeilte Eigenschaften zu überprüfen.

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt und Robert Bruce Findler. Führen Sie Ihre Forschung durch: Über die Wirksamkeit der Leichtbau-Mechanisierung. POPL, 2012.

[2] Daniel Jackson. Legierung: Eine leichte Objektmodellierungsnotation. TOSEM, 2002.

[3] Greg Dennis, Felix Chang und Daniel Jackson. Modulare Codeüberprüfung mit SAT. ISSTA, 2006

[4] Coq Formal Proof Management System

[5] Formale Argumentation zu Programmen. Adam Chlipala, 2016

[6] Leon automatisiertes System zur Überprüfung, Reparatur und Synthese funktionaler Scala-Programme

ivcha
quelle