Shallow versus Deep Embeddings

Bei der Codierung einer Logik in einen Proof-Assistenten wie Coq oder Isabelle muss zwischen einer flachen und einer tiefen Einbettung gewählt werden. In einer flachen Einbettung werden logische Formeln direkt in die Logik des Theorembeweisers geschrieben, während in einer tiefen Einbettung logische Formeln als Datentyp dargestellt werden.

• Was sind die Vor- und Nachteile der verschiedenen Ansätze?
• Gibt es Richtlinien für die Bestimmung, welche verwendet werden sollen?
• Kann systematisch zwischen den beiden Darstellungen gewechselt werden?

Als Motivation möchte ich verschiedene sicherheitsbezogene Logiken in Coq kodieren und frage mich, was die Vor- und Nachteile der verschiedenen Ansätze sind.

Was sind die Vor- und Nachteile der verschiedenen Ansätze?

• Vorteile tiefer Einbettungen: Sie können Dinge durch Induktion auf die Struktur von Formeln beweisen und definieren. Beispiele für Interessen sind die Größe einer Formel.

• Nachteile tiefer Einbettungen: Sie haben sich explizit mit der Bindung von Variablen befasst. Das ist normalerweise sehr mühsam.

Gibt es Richtlinien zur Bestimmung der zu verwendenden Produkte?

Flache Einbettungen sind sehr nützlich, um in der Objektlogik nachgewiesene Ergebnisse zu importieren. Wenn Sie beispielsweise in einer kleinen Logik (z. B. Trennungslogik) einen Beweis erbracht haben, können flache Einbettungen ein Werkzeug der Wahl sein, um Ihr Ergebnis in Coq zu importieren.

Auf der anderen Seite ist eine tiefe Einbettung fast obligatorisch, wenn Sie Meta-Theoreme über die Objektlogik beweisen möchten (wie zum Beispiel das Ausschneiden).

Kann systematisch zwischen den beiden Darstellungen gewechselt werden?

Die Idee hinter der flachen Einbettung besteht darin, direkt in einem Modell der Objektformeln zu arbeiten. Normalerweise ordnet man eine Objektformel P direkt (unter Verwendung von Notationen oder durch manuelle Übersetzung) einem Bewohner von Prop zu. Natürlich gibt es Bewohner von Prop, die nicht durch Einbetten einer Formel der Objektlogik erhalten werden können. Sie verlieren dadurch an Vollständigkeit.

So ist es möglich, jedes in einer tiefen Einbettungsumgebung erhaltene Ergebnis über eine Interpretationsfunktion zu senden.

Hier ist ein kleines Beispiel:

Induktive Formel: Set: =
    Ftrue: Formel
  | Ffalse: Formel
  | Fand: Formel -> Formel -> Formel
  | Für: Formel -> Formel -> Formel.

Fixpunkt interpretieren (F: Formel): Prop: = F mit 
    Ftrue => True
  | Ffalse => False
  | Fand ab => (interpretiere a) / \ (interpretiere b)
  | Für ab => (interpretiere a) \ / (interpretiere b)
 Ende.

Induktiv ableitbar: Formel -> Prop: = 
    deep_axiom: ableitbares Ftrue
  | deep_and: forall ab, ableitbar a -> ableitbar b -> ableitbar (Fand ab)
  | deep_or1: für alle ab, ableitbar a -> ableitbar (für ab)
  | deep_or2: für alle ab, ableitbar b -> ableitbar (für ab).

Induktiv sderivable: Prop -> Prop: = 
    shallow_axiom: sderivable True 
  | shallow_and: forall ab, sderivable a -> sderivable b -> sderivable (a / \ b)
  | shallow_or1: forall ab, sderivable a -> sderivable (a \ / b)
  | shallow_or2: forall ab, sderivable b -> sderivable (a \ / b).

(* Sie können das folgende Lemma beweisen: *)
Lemma shallow_deep: 
   für alle F, ableitbar F -> ableitbar (interpretiere F).

(* Sie können das folgende Lemma NICHT beweisen: *)
Lemma t: 
   für alle P ist ableitbar P -> existiert F, interpretiere F = P.

Grob gesagt definieren Sie mit einer tiefen Einbettung einer Logik (1) einen Datentyp, der die Syntax für Ihre Logik darstellt, und (2) geben ein Modell der Syntax an und (3) beweisen, dass Axiome über Ihre Syntax in Bezug auf Respekt stimmen zum Modell. Bei einer flachen Einbettung überspringen Sie die Schritte (1) und (2) und beginnen einfach mit einem Modell und beweisen Verwicklungen zwischen Formeln. Dies bedeutet, dass flache Einbettungen normalerweise weniger Arbeit erfordern, um auf den Boden zu kommen, da sie Arbeit darstellen, die Sie normalerweise ohnehin mit einer tiefen Einbettung erledigen würden.

Bei einer tiefen Einbettung ist es jedoch in der Regel einfacher, reflektierende Entscheidungsverfahren zu schreiben, da Sie mit Formeln arbeiten, die tatsächlich eine Syntax haben, die Sie erneut verwenden können. Wenn Ihr Modell seltsam oder kompliziert ist, möchten Sie normalerweise nicht direkt mit der Semantik arbeiten. (Wenn Sie zum Beispiel Biorthogonalität verwenden, um das zulässige Schließen zu erzwingen, oder Modelle im Kripke-Stil verwenden, um Frame-Eigenschaften in Separationslogiken oder ähnlichen Spielen zu erzwingen.) Tiefe Einbettungen zwingen Sie jedoch mit ziemlicher Sicherheit dazu, viel über variable Bindungen und Substitutionen nachzudenken , die Ihr Herz mit Wut füllen wird, da dies (a) trivial und (b) eine nie endende Quelle der Belästigung ist.

Die richtige Reihenfolge, die Sie einhalten sollten, ist: (1) Versuchen Sie, mit einer flachen Einbettung auszukommen. (2) Wenn der Dampf ausgeht, versuchen Sie, die gewünschten Entscheidungsverfahren mithilfe von Taktiken und Zitaten durchzuführen. (3) Wenn Ihnen auch der Dampf ausgeht, geben Sie auf und verwenden Sie eine abhängig typisierte Syntax für Ihre tiefe Einbettung.

• Nehmen Sie sich für (3) ein paar Monate Zeit, wenn Sie zum ersten Mal ausgehen. Sie werden müssen vertraut machen mit der Phantasie des Beweis - Assistenten verfügt bleiben gesund. (Dies ist jedoch eine Investition, die sich im Allgemeinen auszahlt.)
• Wenn Ihr Proof-Assistent keine abhängigen Typen hat, bleiben Sie auf Stufe 2.
• Wenn Ihre Objektsprache selbst abhängig ist, bleiben Sie auf Stufe 2.

Versuchen Sie auch nicht, die Leiter allmählich nach oben zu klettern. Wenn Sie sich dazu entschließen, die Komplexitätsleiter zu erklimmen, gehen Sie jeweils einen Schritt weiter. Wenn Sie die Dinge Stück für Stück tun, erhalten Sie viele Sätze, die seltsam und unbrauchbar sind (z. B. erhalten Sie mehrere halbherzige Syntaxen und Sätze, die Syntax und Semantik auf seltsame Weise mischen) muss irgendwann rausschmeißen.

EDIT: Hier ist ein Kommentar, der erklärt, warum es so verlockend ist, nach und nach die Leiter hoch zu steigen und warum es (im Allgemeinen) zu Leiden führt.

$A \star B$$I$$A \star B \iff B \star A$$(A \star B) \star C \iff A \star (B \star C)$$(I \star A) \star (B \star C)$$A \star (B \star (C \star I))$

$\star$

Das ist wahr und funktioniert! Beachten Sie jedoch, dass die Konjunktion ebenso wie die Disjunktion ACUI ist. So werden Sie denselben Prozess in anderen Beweisen mit unterschiedlichen Listendatentypen durchlaufen, und dann werden Sie drei Syntaxen für unterschiedliche Fragmente der Trennungslogik haben, und Sie werden Metatheoreme für jedes von ihnen haben, die unvermeidlich unterschiedlich sein werden. und Sie werden feststellen, dass Sie nach einem Metatheorem suchen, das Sie für die Trennung von Konjunktion und Disjunktion bewiesen haben. Dann möchten Sie Syntaxen mischen und dann werden Sie verrückt.

Es ist besser, das größte Fragment auszuwählen, das Sie mit vertretbarem Aufwand handhaben können, und es einfach zu tun.

Es ist wichtig zu verstehen, dass es ein Spektrum von tief bis flach gibt. Sie modellieren tiefgehend die Teile Ihrer Sprache, die in irgendeiner Weise an einem induktiven Streit über deren Konstruktion beteiligt sein sollten. Der Rest bleibt besser im oberflächlichen Bereich der direkten Semantik des Substrats der Logik.

Wenn Sie beispielsweise über Hoare Logic nachdenken möchten, können Sie die Ausdruckssprache flach modellieren, aber der Umriss der Assign-If-While-Sprache sollte ein konkreter Datentyp sein. Sie müssen nicht die Struktur von x + y oder a <b eingeben, sondern müssen mit whileusw. arbeiten.

In den anderen Antworten gab es Anspielungen auf abhängige Typen. Dies erinnert an das alte Problem, Sprachen mit Bindemitteln auf vernünftige Weise so darzustellen, dass sie so flach wie möglich sind, aber dennoch einige induktive Argumente zulassen. Mein Eindruck ist, dass die Jury immer noch nicht über die verschiedenen Ansätze und Papiere urteilt, die sich in den letzten 10 bis 20 Jahren zu diesem Thema herausgebildet haben. In gewissem Maße ging es auch um die "POPLmark-Herausforderung" für die verschiedenen Proof-Assistenten-Communities.

Seltsamerweise funktionierte der HOL-Nominal-Ansatz von C. Urban in klassischem HOL ohne abhängige Typen recht gut für das flache Binden, obwohl er die kulturellen Veränderungen in diesen Gemeinschaften der programmiersprachlichen Formalisierung nicht aufholte.