Was war der größte Durchbruch zwischen der Hoare-Floyd-Logik und der Scott-Strachey-Semantik?

Ich lese gerade einen Kommentar zu Milners "Der Einsatz von Maschinen zur Unterstützung strenger Beweise" von Mike Gordon durch. In diesem Artikel erklärt er, wie LCF aus den Ideen der Denotationssemantik von Dana Scott und Strachey geboren wurde.

Es scheint mir, dass die Floyd-Hoare-Logik nicht ausreichte, um LCF zu entwickeln, aber ich bin mir nicht sicher, warum dies der Fall ist. Am Ende beschäftigen wir uns in der Hoare-Logik mit Programmzuständen, die einige Voraussetzungen erfüllen $P$ und das durch eine Beziehung $r$ einer gewissen Nachbedingung entsprechen $Q$ und ich kann eine Formel dafür bereitstellen. Wikipedia behauptet, dass die Bezeichnungssemantik:

ist ein Ansatz zur Formalisierung der Bedeutungen von Programmiersprachen durch Konstruktion mathematischer Objekte (Bezeichnungen genannt), die die Bedeutungen von Ausdrücken aus den Sprachen beschreiben.

Ich kenne einige Intuitionen darüber, wie beispielsweise Rekursion in diesem Ansatz als fester Punkt einer Beziehung modelliert wird, während ich mich in der Hoare-Logik nicht wirklich daran erinnerte, mich mit Rekursion befasst zu haben. Dennoch scheinen beide Ansätze zu versuchen, Beziehungen zwischen Ein- und Ausgängen unter Verwendung mathematischer Beziehungen zu beschreiben.

Frage

Was hat also den Unterschied zwischen Hoare-Logik und Denotationssemantik ausgemacht? Verwaltet die Denotationssemantik einige Komplexitäten von Programmen besser? Wenn ja, veranschaulichen Sie dies bitte anhand eines Beispiels.

Vielleicht ist das folgende Zitat von Milner, das sich auf die Denotationssemantik bezieht, interessant, um Ihre Antwort zu leiten:

Ich könnte die Syntax einer Programmiersprache in dieser Logik aufschreiben und die Semantik in die Logik schreiben.

hoare-logic automated-theorem-proving denotational-semantics Rodrigo
quelle

Ich denke, in der funktionalen Welt ist der Denotationsansatz ganz natürlich. Es ist schön kompositorisch, im Gegensatz zur operativen Semantik (besonders wenn es sich um kleine Schritte handelt). Ich muss gestehen, dass ich noch nie eine Hoare-Logik für funktionale Programme gesehen habe - ich vermute, dass eine, falls vorhanden, umständlich sein könnte, da es in reinem FP kein "Update-the-State" -Konstrukt wie die Zuweisung in der imperativen Programmierung gibt.

Chi

@chi Sicher gibt es viele Hoare-Logiken für FPs. Die Pionierarbeit war eine kompositorische Programmlogik für polymorphe Funktionen höherer Ordnung von Honda / Yoshida. Diese wurde erweitert in z. B. * Eine beobachtungsvoll vollständige Programmlogik für imperative Funktionen höherer Ordnung. "Sie wurde auf verschiedene Weise erweitert.

Martin Berger

@ MartinBerger Ah, interessant. Danke für den Hinweis.

Chi

Ich finde die Verweise auf FP ablenkend vom Hauptpunkt der Frage. Der Unterschied zwischen Hoare-Logik und Denotationssemantik besteht darin, dass sich die erstere mit der syntaktischen Zuordnung von Eigenschaften von Programmen befasst (wiederum syntaktisch gegeben), während die letztere mit der Zuordnung von Programmen zu mathematischen Objekten befasst ist, die ihrer Bedeutung ähneln. Mit anderen Worten, die beiden sind sehr unterschiedlich.

Kai

Ich weiß nicht, warum die Leute früher keine Hoare-Logik für Lambda-Kalküle entwickelt haben. Die erste Arbeit, um dies richtig zu machen, war die von Honda et al

Eine Kompositionsprogrammlogik für polymorphe Funktionen höherer Ordnung

Zuvor gab es einige frühere Versuche, aber sie haben das Problem nicht ganz gelöst, zum Beispiel: Wie bezeichnen Sie den Wert eines Funktionsprogramms? Welche Syntax entspricht dem Funktionsraumkonstruktor? Es gibt ein paar kleine Dinge, die richtig gemacht werden müssen.

Lassen Sie mich spekulieren: Vielleicht war das Hauptproblem, dass sich die Hoare-Logik normalerweise mit der Zustandsberechnung befasste. Wenn Sie Statusfunktionen und Funktionen höherer Ordnung kombinieren, müssen Sie sich sofort mit Aliasing befassen, z. B. mit Programmen wie

λ x^{R. e f (N. ein t)} . λ y^{R. e f (N. ein t)} . (x : =! x + 1;; y : =! y + 1),

$\lambda x^{\mathsf{Ref(Nat)}}.\lambda y^{\mathsf{Ref(Nat)}}.(x := !x+1; y := !y+1),$ sowie lokales Geschäft und Rekursion durch das Geschäft. Diese wurden erst in den frühen 2000er Jahren in Werken wie Eine beobachtungsvoll vollständige Programmlogik für imperative Funktionen höherer Ordnung (Rekursion durch den Speicher) gelöst ; Eine logische Analyse des Aliasing in imperativen Funktionen höherer Ordnung (Aliasing), logisches Denken für Funktionen höherer Ordnung mit lokalem Status (vollständiger lokaler Speicher). Gleichzeitig ging die Trennungslogik das Aliasing-Problem aus einem anderen Blickwinkel an.

Diese Arbeit wurde von A. Charguéraud in Coq in seiner Arbeit implementiert und wird jetzt auch in der Javascript-Semantik verwendet.

Martin Berger
quelle

Was war der größte Durchbruch zwischen der Hoare-Floyd-Logik und der Scott-Strachey-Semantik?

Antworten: