Volle Vollständigkeit vs Volle Abstraktion einer Programmübersetzung

Bei der Überprüfung von Compilern geht es häufig darum, den Compiler als vollständig abstrakt zu beweisen: dass er (kontextbezogene) Äquivalenzen bewahrt und widerspiegelt.

Anstatt vollständige Abstraktionsnachweise zu liefern, wurden einige neuere (kategorienbasierte) Compiler-Verifikationsarbeiten von Hasegawa [ 1 , 2 ] und Egger et. al. [ 3 ] die vollständige Vollständigkeit verschiedener CPS-Übersetzungen nachweisen.

Frage: Was ist der Unterschied zwischen vollständiger und vollständiger Abstraktion?

Vollständigkeit erscheint mir nur als Äquivalenzreflexion für eine Übersetzung, und Fülle scheint eine Folge der Wahrung der Äquivalenz zu sein.

Anmerkung : Sowohl Curien [ 7 ] als auch Abramsky [ 8 ] untersuchen die Beziehung zwischen Definierbarkeit, vollständiger Abstraktion und teilweise vollständiger Vollständigkeit. Ich vermute, dass diese Ressourcen die Antwort auf meine Frage haben, aber nach einem Oberflächenlesevorgang muss ich dies noch bestätigen.

Hintergrund : Abramsky und Jagadeesan [ 4 ] haben den Begriff "vollständige Vollständigkeit" geprägt , um die Korrektheit eines spielsemantischen Modells der multiplikativen linearen Logik zu charakterisieren.

Blute [ 5 ] enthält die folgende Definition:

Sei $\mathcal{F}$ eine freie Kategorie. Wir sagen , dass ein grundsätzliches Modell $\mathcal{M}$ ist für vollständig abgeschlossen $\mathcal{F}$ oder dass wir volle Vollständigkeit von $\mathcal{F}$ in Bezug auf $\mathcal{M}$ , wenn in Bezug auf einige Auslegung der Generatoren, der einzigartige freie Funktors $[\![ - ]\!] : \mathcal{F} \rightarrow \mathcal{M}$ ist voll.

Soweit ich das beurteilen kann, ist Hasegawa in [ 6 ] der erste, der die vollständige Beschreibung einer Programmübersetzung anstelle eines kategorialen semantischen Modells anpasst. In diesem Fall die Girard-Übersetzung von einfach getipptem Lambda-Kalkül zu linearem Lambda-Kalkül. Später definiert er in [ 1 ] die vollständige Vollständigkeit der CPS-Übersetzung $(\cdot)^\circ$ als:

Wenn $\Gamma^{\circ};\emptyset \vdash N : (\sigma^\circ \rightarrow o) \multimap o$ ist im linearen Lambda-Kalkül ableitbar, dann existiert im rechnerischen Lambda-Kalkül, so dass gilt im linearen Lambda-Kalkül. $\Gamma \vdash M : \sigma$ $\Gamma^{\circ};\emptyset \vdash M^\circ = N : (\sigma^\circ \rightarrow o) \multimap o$

(wobei ein Basistyp im linearen Lambda-Kalkül (Zielsprache) ist, nicht jedoch im rechnerischen Lambda-Kalkül (Ausgangssprache).) $o$

Für mich scheint Hasegawas Definition eine Fülle zu sein und sollte wirklich mit Vollständigkeit kombiniert werden, um vollständige Vollständigkeit zu erreichen.

Egger et. al. [ 3 ] definiere die vollständige Vollständigkeit einer CPS-Übersetzung als eine Kombination von (1) Vollständigkeit und (2) Vollständigkeit: $(\cdot)^v$

(1): Wenn und dann $\Theta \vdash M,N : \tau$ $\Theta^v | - \vdash M^v =_{\beta\eta} N^v : !\tau^v$ $\Theta \vdash M =_{\lambda_c} N : \tau$

(2): Wenn existiert dann ein Term so dass $\Theta^v | - \vdash t : !\tau^v$ $\Theta \vdash M : \tau$ $\Theta^v | - \vdash M^v =_{\beta\eta} t : !\tau^v$

(wobei Moggis rechnerische Gleichungstheorie ist) $=_{\lambda_c}$

[1] " Linear verwendete Effekte: Monaden- und CPS-Transformationen in lineare Lambda-Rechnung ", Hasegawa 2002

[2] " Semantik der linearen Weitergabe in Call-by-Name ", Hasegawa 2004

[3] " Linear verwendbare CPS-Übersetzungen in der Enriched Effect Calculus ", Egger et. al. 2012

[4] " Spiele und volle Vollständigkeit für multiplikative lineare Logik ", Abramsky und Jagadeesan 1992

[5] " Kategorietheorie für lineare Logiker ", Blute 2003

[6] " Girard Translation and Logical Predicates ", Hasegawa 2000

[7] " Definierbarkeit und vollständige Abstraktion ", Curien 2007

[8] " Axiome für Definierbarkeit und Vollständigkeit ", Abramsky 1999

pl.programming-languages ct.category-theory semantics denotational-semantics program-verification Phillip Mates
quelle

Antworten:

Leider ist hier zu viel los. So ist es einfach, Dinge zu verwechseln. Die Verwendung von "vollständig" in "vollständiger" und "vollständiger Abstraktion" bezieht sich auf völlig unterschiedliche Vorstellungen von Fülle. Es gibt aber auch eine vage Verbindung zwischen ihnen. Das wird also eine komplizierte Antwort.

Volle Vollständigkeit : "Klang und Vollständigkeit" ist eine Eigenschaft, die eine traditionelle Logik in Bezug auf ihre Semantik haben soll. Solidität bedeutet, dass alles, was Sie in der Logik beweisen können, im semantischen Modell wahr ist. Vollständigkeit bedeutet, dass alles, was im semantischen Modell wahr ist, in der Logik beweisbar ist. Wir sagen, dass eine Logik für ein bestimmtes semantisches Modell solide und vollständig ist. Wenn wir zu konstruktiver Logik kommenWie bei der Martin-Lof-Typentheorie oder der linearen Logik geht es uns nicht nur darum, ob Formeln beweisbar sind, sondern auch darum, was ihre Beweise sind. Eine beweisbare Formel kann viele Beweise haben, und eine konstruktive Logik möchte sie auseinanderhalten. Eine Semantik für eine konstruktive Logik besteht also darin, nicht nur anzugeben, ob eine Formel wahr ist, sondern auch eine abstrakte semantische Vorstellung von "Beweis" ("evidence") für ihre Wahrheit. Abramsky und Kollegen haben den Begriff "vollständige Vollständigkeit" so geprägt, dass die Beweise in der Logik alle semantischen Beweise im Modell ausdrücken können. "Voll" bezieht sich hier also auf Beweise. Eine "vollständige" Logik kann alles beweisen, was sie braucht. Eine "vollständig" Logik hat alle Beweise, die sie haben muss. "Vollständigkeit" bedeutet also "konstruktive Vollständigkeit" oder "Beweisvollständigkeit". Das hat nichts mit vollständiger Abstraktion zu tun.

Vollständige Abstraktion : "Angemessen und vollständig abstrakt" ist eine Eigenschaft, die Sie für das semantische Modell einer Programmiersprache benötigen. (Beachten Sie den ersten Unterschied: Wir beschäftigen uns jetzt mit den Eigenschaften des semantischen Modells, nicht die Eigenschaften der Sprache!) Angemessenheit bedeutet, dass, wenn zwei Ausdrücke im semantischen Modell die gleiche Bedeutung haben, sie in der Programmiersprache (in Bezug auf einen Ausführungsbegriff) beobachtungsgleich sind. Vollständige Abstraktion bedeutet, dass zwei beobachtungsgleiche Begriffe im semantischen Modell dieselbe Bedeutung haben. Diese Ideen können sich auf Vollständigkeit und Vollständigkeit beziehen, aber auf eine etwas ausgeklügelte Weise. Wenn wir das semantische Modell einer Programmiersprache als "Logik" oder "Beweismethode" betrachten, um über Beobachtungsäquivalenz zu sprechen, bedeutet Angemessenheit, dass diese Beweismethode solide ist; Vollständige Abstraktion bedeutet, dass diese Beweismethode vollständig ist. Es gibt keine Vorstellung von "voller Vollständigkeit"Beweismethode. (Aber so etwas ist theoretisch möglich, und eines Tages könnte es jemand tun.)

In Ihrem Fall interessieren Sie sich eher für Übersetzungen als für semantische Modelle. Die Eigenschaften Angemessenheit und vollständige Abstraktion können erweitert werden, um Übersetzungen wie folgt zu behandeln. Sie verstehen die Zielsprache als Ihr "semantisches Modell", dh als einen Formalismus, den Sie irgendwie vollständig verstehen. Wenn ja, haben Sie eine Vorstellung von Äquivalenz dafür. Dann sagen wir, dass die Übersetzung angemessen ist, wenn die Übersetzungen von zwei Quellprogrammen in der Zielsprache äquivalent sind und sie in der Quellsprache beobachtungsmäßig äquivalent sind. Wir sagen, dass es völlig abstrakt ist, wenn immer zwei Quellprogramme in der Quellsprache beobachtungsmäßig äquivalent sind, ihre Übersetzungen in der Zielsprache äquivalent sind.

τ (M) ≅ τ (N) ⟹ M ≅ N

$\tau(M) \cong \tau(N) \Longrightarrow M \cong N$

M ≅ N ⟹ τ (M) ≅ τ (N)

$M \cong N \Longrightarrow \tau(M) \cong \tau(N)$

M ≅ N ⟺ τ (M) ≅ τ (N)

$M \cong N \iff \tau(M) \cong \tau(N)$

$A$ $A$

\forall N : τ (A) . \exists M : A . τ (M) = N

$\forall N : \tau(A).\; \exists M : A.\, \tau(M) = N$

Nun zum vagen Zusammenhang zwischen vollständiger Vollständigkeit und vollständiger Abstraktion. Zu beweisen, dass ein semantisches Modell oder eine Übersetzung vollständig abstrakt ist, erfordert oft eine gewisse Definierbarkeit. Dies liegt daran, dass unsere Sprachen im Allgemeinen eine höhere Ordnung haben. Wenn also das semantische Modell oder die Zielsprache zu viele "Kontexte" aufweist, kann es unsere Begriffe oder semantischen Bedeutungen in unerwünschter Weise verwenden und deren Äquivalenz beeinträchtigen. "Unerwünschte Wege" bedeutet auf eine Weise, dass die Programmiersprache sie nicht anstoßen kann. Um eine vollständige Abstraktion zu erhalten, müssen wir sicherstellen, dass die im semantischen Modell oder in der Zielsprache verfügbaren "Kontexte" in irgendeiner Form von denen in der Ausgangssprache stammen. Beachten Sie, dass dies die vollständige Vollständigkeit betrifft.

Warum wollen wir solche Eigenschaften? Es hat nichtsmit Compilern zu tun! Wir möchten, dass diese Eigenschaften behaupten, dass die Quellsprache in die Zielsprache eingebettet ist. Wenn wir mit einer bestimmten Zielsprache zufrieden sind (als sauber, verständlich, irgendwie grundlegend oder von Gott gegeben), können wir, wenn die Ausgangssprache darin eingebettet ist, behaupten, dass die Ausgangssprache nichts Neues enthält. Es ist nur ein Fragment der Zielsprache, die wir kennen und lieben. Es ist nur syntaktischer Zucker. Es werden also vollständig abstrakte Übersetzungen von Menschen gegeben, um festzustellen, dass bestimmte Zielsprachen großartig sind. Sie werden auch manchmal von Menschen gegeben, die mit einer großen oder komplizierten Sprache zu tun haben. Anstatt eine Semantik dafür direkt zu definieren, übersetzen sie sie in eine Kernsprache und geben der Kernsprache dann eine Semantik. Der Haskell-Bericht macht dies zum Beispiel. Die vollständige Abstraktion dieser Übersetzungen wird jedoch selten bewiesen, da die Ausgangssprachen groß und kompliziert sind. Die Leute glauben, dass die Übersetzung gut ist.

Dies hat wiederum nichts mit Compilern zu tun. Compiler sind selten ausreichend oder vollständig abstrakt. Und das müssen sie auch nicht sein! Alles, was ein Compiler tun muss, ist das Ausführungsverhalten vollständiger Programme beizubehalten. Die Zielsprache eines Compilers ist im Allgemeinen riesig, was bedeutet, dass es viele Kontexte gibt, die die Äquivalenz durcheinander bringen können. Daher sind äquivalente Programme in der Ausgangssprache beim Kompilieren praktisch nie kontextabhängig.

Uday Reddy
quelle

Was meinst du damit, dass es keine Sprachen gibt, die wir wirklich vollständig "verstehen"?

Martin Berger

Was bedeutet für Sie, dass noch niemand ein semantisches Modell erstellt hat, das eine konstruktive Beweismethode darstellt?

Martin Berger

Entschuldigung, aber die Implikationen für "Übersetzungen" scheinen mir im Vergleich zu Ihrem früheren Text in die falsche Richtung zu weisen. Vollständige Abstraktion für beispielsweise PCF verlangt M≅N≅τ (M) ≅τ (N) (wobei τ die Bezeichnungssemantik ist und die Notwendigkeit, Symbole zu ändern, ignoriert): Wie Sie sagen, bedeutet "Vollständige Abstraktion, wenn zwei begriffe sind beobachtungsgleich, sie haben im semantischen modell die gleiche bedeutung ". Aber Ihre Implikation ist umgekehrt (Sie schreiben nämlich τ (M) ≅τ (N) ⟹M⟹N)! Oder funktionieren Übersetzungen anders als die Denotationssemantik?

Blaisorblade

@Blaisorblade: Du hast absolut recht! Ich habe den Text meiner Antwort korrigiert.

Uday Reddy

Die vollständige Abstraktion ist auch für die Sicherheit auf Sprachebene und möglicherweise für die sprachübergreifende Integration von Interesse. Das heißt, es ist nützlich zu wissen, dass nichts in der Zielsprache Abstraktionen der Ausgangssprache verletzen kann.

Dmbarbour

Zusammenfassung: Vollständigkeit bedeutet, dass die Interpretationsfunktion nicht nur vollständig, sondern auch für Programme surjektiv ist. Für die vollständige Abstraktion ist keine Surjektivität erforderlich. $\newcommand{\semb}[1]{[\![ #1 ]\!]}$

$\semb{.}$

$A$ $\semb{A}$
$\Gamma$ $\semb{\Gamma}$
$\Gamma \vdash P : \alpha$ $\semb{\Gamma} \vdash \semb{P} : \semb{\alpha}$

$\semb{.}$

P ≅^{S} Q iff [[P]] ≅^{T} [[Q]]

$P \cong^S Q\ \ \ \ \ \text{iff}\ \ \ \ \ \semb{P} \cong^T \semb{Q}$

$P, Q$ $\cong^S$ $\cong^T$

P ≅_{Γ, α}^{S} Q iff [[P]] ≅_{[[Γ]], [[α]]}^{T} [[Q]]

$P \cong^S_{\Gamma, \alpha} Q\ \ \ \ \ \text{iff}\ \ \ \ \ \semb{P} \cong^T_{\semb{\Gamma}, \semb{\alpha}} \semb{Q}$

Γ, α, P, Q

$\Gamma, \alpha, P, Q$

[[.]]

$\semb{.}$

$\semb{.}$ $\semb{\Gamma} \vdash Q : \semb{\alpha}$ $\Gamma \vdash P : \alpha$ $Q = \semb{P}$ $\semb{.}$

Martin Berger
quelle