Für welche Sprachen gibt es bereits eine Theorie der Beobachtungsäquivalenz?

Für einen Korrektheitsnachweis suche ich nach einem brauchbaren Begriff der Programmäquivalenz für Barendregts reine Typsysteme (PTS); Fehlt das, für genügend spezifische Typsysteme. Mein Ziel ist es einfach, den Begriff zu verwenden und ihn nicht um seiner selbst willen zu untersuchen. $\cong$

Dieser Begriff sollte " extensional " sein - insbesondere um zu beweisen, dass , sollte es ausreichen, um zu beweisen, dass $t_1 \cong t_2$ für alle Werte des entsprechenden Typs. $t_1\; v \cong t_2\; v$ $v$

Denotationsäquivalenz

Die Denotationsäquivalenz erfüllt leicht alle richtigen Deckspelzen, aber eine Denotationssemantik für willkürliches PTS scheint ziemlich herausfordernd zu sein - es würde für System F bereits schwierig erscheinen.

Kontext- / Beobachtungsäquivalenz

Die offensichtliche Alternative sind dann verschiedene Formen der kontextuellen Äquivalenz (zwei Begriffe sind äquivalent, wenn kein Grundkontext sie unterscheiden kann), aber ihre Definition ist nicht sofort verwendbar; Die verschiedenen Deckspelzen sind nicht trivial zu beweisen. Wurden sie für PTS nachgewiesen? Wäre die Theorie alternativ eine "offensichtliche Erweiterung", oder gibt es Grund zu der Annahme, dass die Theorie signifikant anders wäre?

EDIT: Ich habe nicht gesagt, was oben schwer ist.

Einfacher Teil: die Definition

Die Definition der Äquivalenz ist nicht allzu schwierig, und die Definition erscheint in vielen Veröffentlichungen (zumindest ausgehend von Plotkin 1975 über PCF, wenn nicht früher - die Quelle könnte Morris 'Doktorarbeit von 1968 sein). Uns , wenn für alle Böden Kontexte , - das heißt, und gibt das gleiche Ergebnis $t_1 \cong t_2$ $C$ $C[t_1] \simeq C[t_2]$ $C[t_1]$ $C[t_2]$ . Sie haben hier einige Möglichkeiten mit vielen Alternativen: Wenn Sie beispielsweise in einer stark normalisierenden Sprache einen Grundtyp von Naturmenschen haben, können Sie sagen, dass Grundkontexte diejenigen sind, die Naturtöne zurückgeben, und dann bedeutet , dass und auf die gleiche Zahl auswerten. Bei Nichtterminierung reicht es für vernünftige Sprachen aus, "X-Terminierungen" als Beobachtung zu verwenden, denn wenn zwei Programme bei der Beobachtung der Terminierung gleichwertig sind, sind sie auch bei der Beobachtung des Ergebnisses gleichwertig. $a \simeq b$ $a$ $b$

Schwieriger Teil: die Beweise

Diese Artikel erklären jedoch oft nicht, wie schwierig es ist, diese Definition tatsächlich zu verwenden. Alle folgenden Referenzen zeigen, wie man mit diesem Problem umgeht, aber die benötigte Theorie ist schwieriger als man denkt. Wie beweisen wir, dass ? Führen wir tatsächlich Fallanalysen und Einführungen in Kontexte durch? Das willst du nicht. $t_1 \cong t_2$

Wie Martin Berger betont, möchten Sie stattdessen entweder eine Bisimulation (wie von Pitts durchgeführt) oder eine logische Äquivalenzbeziehung (die Harper einfach "logische Äquivalenz" nennt) verwenden.

Wie beweisen Sie schließlich die oben definierte Extensionalität?

Harper löst diese Fragen auf 10 Seiten für System T durch beträchtliche Klugheit und logische Beziehungen. Pitts braucht mehr. Einige Sprachen sind noch komplexer.

Wie man damit umgeht

Ich bin tatsächlich versucht, meine Beweise von einer vermuteten Äquivalenztheorie für PTS abhängig zu machen, aber die tatsächlichen Theorien erfordern nicht triviale Argumente, daher bin ich mir nicht sicher, wie wahrscheinlich eine solche Vermutung sein würde.

Mir sind (wenn auch nicht im Detail) folgende Arbeiten bekannt:

Andrew Pitts (zum Beispiel in ATTAPL für ein erweitertes System F und in einigen Veröffentlichungen, wie beispielsweise der 58-seitigen "Operational-Based Theories of Program Equivalence").
Praktische Grundlagen von Programmiersprachen (Kapitel 47-48), die von Pitts inspiriert sind (aber behaupten, einfachere Beweise zu haben).
Eine logische Untersuchung der Programmäquivalenz . Ich kann kein englisches Abstract finden, aber es scheint viel Aufwand für Nebenwirkungen (Referenzen) aufzuwenden, was eine orthogonale Komplikation zu sein scheint.

pl.programming-languages type-theory operational-semantics Blaisorblade
quelle

⇓

$\Downarrow$

P ≅ Q

$P \cong Q$

C [\cdot]

$C[\cdot]$

C [P] ⇓

$C[P] \Downarrow$

C [Q] ⇓

$C[Q] \Downarrow$

@MartinBerger: Das ist die Idee, auf die ich hinweise, aber es ist überraschend schwierig, sie direkt zu beweisen, da Sie Beweise für alle C machen müssen (das werde ich in der Frage besser erklären). Wenn alle Programme beendet werden, identifiziert die von Ihnen verwendete Definition alle Programme.

Blaisorblade

β η

$\beta\eta$

C [P] ⇓ t r u e

$C[P] \Downarrow true$

C [Q] ⇓ t r u e

$C[Q] \Downarrow true$

≅

$\cong$ und (2) leicht zu handhaben, z. B. eine Vorstellung von Bisimilarität oder eine logische Beziehung. Kommt auf die Anwendung an.

Martin Berger

@Blaisorblade Wahrscheinlich. Parallelitätstheoretiker tun dies seit langer Zeit intensiv, da bei gleichzeitigen Prozessen viel weniger klar ist, welcher Begriff der Äquivalenz zu verwenden ist. Dies hat zu einer Arbeitsteilung geführt: Verwenden Sie eine reduktionsbasierte Semantik mit Quantifizierung über Kontexte, um den Begriff der Äquivalenz zu definieren, und verwenden Sie dann Bisimulationen oder Spuren über markierten Übergängen, um die Äquivalenz (oder deren Fehlen) zu beweisen. Eine große offene Forschungsfrage in der Parallelitätstheorie ist, wie man algorithmisch von der ersteren zur letzteren übergeht.

Martin Berger

Antworten:

$[\![ {-} ]\!]$

[[t_{1}]] = [[t_{2}]] ⟹ t_{1} ≅ t_{2} .

$[\![ t_1 ]\!] = [\![ t_2 ]\!] \implies t_1 \cong t_2.$

Andrej Bauer
quelle

≅

$\cong$

Vielen Dank für die Antwort, aber -1: Obwohl ich damit einverstanden bin, werden in der Frage reine Typsysteme erwähnt - AFAICS, eine Denotationssemantik für reine Typsysteme, ist ein offenes Problem, daher denke ich, dass eine Antwort auf eine Denotationssemantik verweisen sollte. (Wenn ich eine Denotationssemantik hätte, würde ich auf die operative Semantik insgesamt verzichten, wie in der Frage erwähnt). (Aber entschuldigen Sie die zu lange Frage.)

Blaisorblade

@ MartinBerger, ich verstehe deine Kritik nicht. Das OP fragt nach Methoden zum Nachweis der Beobachtungsäquivalenz, ich erwähne eine gemeinsame, und dann beanstanden Sie, dass es andere Wege gibt, die die Methode vermeiden?

Andrej Bauer

@Blaisorblade, dann müssen Sie nur noch eine Denotationssemantik für reine Typsysteme erfinden, nicht wahr? :-) Aber im Ernst, ich werde Alex Simpson fragen, er würde besser über die Denotationssemantik für solche Dinge Bescheid wissen.

Andrej Bauer

@AndrejBauer Es war keine Kritik, sondern ein Nachtrag.

Martin Berger

$\eta$

Cody
quelle

Ich glaube nicht, dass es bei Streichers Doktorarbeit um PTS geht. Es geht um die Semantik der Konstruktionsrechnung und die Ergebnisse der Unabhängigkeit über die Zuverlässigkeitssemantik. Siehe hier .

Martin Berger

Danke für die Klarstellung! Ich fürchte, der Link ist defekt (und mit dem minimierten Link schwer zu beheben).

Cody

Der Link war zum Inhaltsverzeichnis des Buches hier . Ich hoffe das funktioniert besser.

Martin Berger

λ^{*}

$\lambda^*$

@ MartinBerger: Meinst du Realisierbarkeitssemantik?

Dominique Devriese

Diese Antwort schlägt eine Herangehensweise an das Problem vor. (Feedback ist willkommen).

In Kapitel 49 der PFPL werden sofort die äquivalenten Begriffe Beobachtungsäquivalenz und logische Äquivalenz erörtert. Die logische Äquivalenz ist dieselbe Beziehung, die zur Angabe der Parametrizität verwendet wird. Der Kern des Kapitels ist daher ein Beweis der Parametrizität für System F.

Die Arbeiten zur Parametrizität für PTS, AFAICT, diskutieren nicht den Zusammenhang mit der Beobachtungsäquivalenz. Um die Beobachtungsäquivalenz überhaupt zu definieren, benötigen Sie einen positiven Bodentyp (Naturwerte, Boolesche Werte), den Sie für Beobachtungen verwenden können, es sei denn, Sie haben keine Terminierung.

Der Schlüsselsatz (PFPL 47.6, 48.3, 49.2) zur Beziehung der beiden Beziehungen ist jedoch unabhängig von der jeweiligen Sprache bewiesen:

Beobachtungsäquivalenz ist die gröbste konsistente Kongruenz bei Ausdrücken.

Um zu zeigen, dass logische Äquivalenz Beobachtungsäquivalenz impliziert, muss man nur zeigen, dass logische Äquivalenz eine konsistente Kongruenz ist. Die andere Richtung erfordert jedoch etwas mehr Arbeit: Um insbesondere zu zeigen, dass logische Äquivalenz eine Kongruenz ist, wird durch Induktion von Kontexten vorgegangen.

n + 1 = 1 + nVecN nnVecNVecN $n + 1 = 1 + n$ Vec (n + 1)Vec (1 + n)n + 11 + n

Blaisorblade
quelle