Ist semantische Bewahrung Solidität (oder Korrektheit) oder Vollständigkeit

7

Bei der Transformation von Begriffen von einer Sprache in eine andere ist die intuitiv gewünschte Eigenschaft die Beibehaltung der Semantik (wie sie beispielsweise hier für eine CPS-Transformation verwendet wird):

svc(s)c(v)

Ich bin jedoch ein wenig beunruhigt, wenn ich dies mit den klassischen Begriffen Korrektheit (oder Solidität) und Vollständigkeit von Logiksystemen in Einklang bringe . Normalerweise würde ich die obige Aussage als Vollständigkeitseigenschaft von betrachtenc (und umgekehrt die Definition von Korrektheit).

Intuitiv sollte ein Compiler jedoch eher korrekt als vollständig sein (da beispielsweise eine Typprüfung häufig korrekte Programme ausschließt). Die Umkehrung der obigen Aussage ist nur wahr, wennc ist injektiv: Wenn die Ausgangssprache beispielsweise Boolesche Werte und Operationen enthält und die Kompilierung sie über die Church-Codierung ersetzt, kann die Zielsprache boolesche Operationen anhand von Begriffen aus booleschen Literalen und Lambda-Abstraktionen auswerten, die die Ausgangssprache nicht auswerten kann.

  1. Bin ich zu Recht davon ausgegangen, dass die obige Aussage die Vollständigkeitseigenschaft von ist c (Die intuitive Anforderung hat also tatsächlich einen kontraintuitiven Namen)?
  2. Habe ich auch Recht mit meiner Schlussfolgerung, dass ein nicht injektiver Compiler dann normalerweise nicht korrekt ist?
Cheger
quelle

Antworten:

3

Dies ist wirklich eine Frage zum Begriff der operativen Korrespondenz .

Das Papier Auf dem Weg zu einem einheitlichen Ansatz für Kodierungs- und Trennungsergebnisse für Prozesskalküle von Daniele Gorla ( http://wwwusers.di.uniroma1.it/~gorla/papers/G-CONCUR08.pdf ) befasst sich mit Korrektheitskriterien für Übersetzungen zwischen Prozessen Steine.

In seiner Arbeit führt Gorla einen Begriff der Verhaltensäquivalenz ein; Ich werde es hier weglassen, um die Erklärung nicht zu komplizieren.

Lassen [[]] sei eine Kodierung, lass 1 sei die für die Ausgangssprache definierte Übergangsrelation und lass 2sei die für die Zielsprache definierte Übergangsbeziehung. Wenn wir das haben

  • Wenn S1S dann [[S]]2[[S]]sagen wir, dass die Kodierung abgeschlossen ist
  • Wenn [[S]]2T, dann gibt es eine S so dass S1S' und T.2[[S.']]]]sagen wir, dass die Kodierung Ton ist .

Ja, der in den Fragen erwähnte Begriff ist in der Tat der der Vollständigkeit. Der Begriff der Solidität wird durch die Tatsache geprägt, dass die Zielsprache häufig reicher als die Zielsprache ist oder syntaktische Konstrukte enthält, deren Verhalten nichts in der Ausgangssprache entspricht. Dies erklärt, warum wir von der Zwischenkonfiguration sprechenT. in der Definition, anstatt Injektivität zu erfordern.

Hans Hüttel
quelle
Sind Sie sich über die Ein-Schritt-Ableitung sicher? S.1S.'Ich habe gerade das Papier ausgegraben, und nach einem kurzen Blick scheinen sie die mehrstufige Ableitung zu verwenden. Dies macht auch die Solidität verwirrend: Warum muss in dieser Eigenschaft genau ein Schritt von S nach S 'vorhanden sein?
Cheger
Nein, es sollte tatsächlich eine Reduktionssequenz bei der Definition von Solidität geben. Die beabsichtigte Interpretation ist, dass die Codierung[[S.]]]] kann die ursprüngliche Aussage getreu simulieren S.;; wann immer[[S.]]]] eine Reduktionssequenz durchführt, kann diese so abgeschlossen werden, dass die Ergebnisse einer Simulation einer Reduktionssequenz von entsprechen S.. Ich habe meine Antwort aktualisiert.
Hans Hüttel
2

Intuitiv ausgedrückt besagt die Korrektheitseigenschaft für eine Transformation über eine Sprache, für die ein Bewertungsbegriff definiert ist, dass, wenn ein Begriff eine bestimmte Semantik hat, das Bild des Begriffs durch diese Transformation zum Bild dieser Semantik ausgewertet wird. Mit anderen Worten, ein korrekter Compiler wandelt ein Programm in ein anderes Programm mit demselben Verhalten um (ausgedrückt in der Zielsprache).

Hier schließe ich aus Ihren Notizen, dass die Ausgangssprache eine Sprache der Begriffe ist s mit einem Begriff der Bewertung :: sv bedeutet, dass s reduziert (in beliebig vielen Schritten) auf den Wert v. Ein korrekter Compilerc ist eine, die jedes Programm transformiert s in ein kompiliertes Programm c(s) Dies ergibt den entsprechenden Compilerwert c(v).

Dies entspricht der Definition auf Wikipedia, wenn Werte zu sich selbst kompiliert werden: ifs hat die Eigenschaft v dann auch c(s).

Ein Sound-Compiler muss nicht injektiv sein: Es ist möglich und äußerst häufig, dass verschiedene Quellprogramme mit derselben Semantik zu demselben kompilierten Programm kompiliert werden.

Compiler sind im Allgemeinen nicht vollständig : Wie Sie bemerken, ist es üblich, Begriffe in der kompilierten Sprache zu haben, die nicht die Ausgabe des Compilers sein können, dh der Compiler ist nicht surjektiv.

Gilles 'SO - hör auf böse zu sein'
quelle
Sie sagen also das genaue Gegenteil von Hans 'Antwort? Das ist interessant. Ihre Interpretation meiner Notation ist richtig, aber um die Dinge explizit zu machen: Sie betrachten die Aussage der Korrektheit (und damit wäre das Gegenteil Vollständigkeit)?
Cheger
@choeger Genau genommen würde ich Korrektheit als „für alle“ definieren s und v, wenn c(s) existiert und sv dann c(v) existiert und sc(v)”. Angesichts der Tatsache, dass die Ausgangssprache die Semantik definiert, sehe ich keine Möglichkeit zur Quantifizierungsvc(s)c(v)um es zu einer Vollständigkeitseigenschaft zu machen.
Gilles 'SO - hör auf böse zu sein'