Konfluenznachweis für ein einfaches Umschreibesystem

14

Angenommen, wir haben eine einfache Sprache, die aus folgenden Begriffen besteht:

  • t r u etrue
  • f a l s efalse
  • Wenn Terme sind, ist dies aucht 1 , t 2 , t 3 t1,t2,t3i ft 1t h e nt 2e l s et 3ift1thent2elset3

Nehmen wir nun folgende logische Auswertungsregeln an:

ich ft r u et h e nt 2e l s et 3t 2 [E-IfTrue]ich ff a l s et h e nt 2e l s et 3t 3 [E-IfFalse]t1t ' 1ich ft 1t h e nt 2e l s et 3i ft ' 1t h e nt 2e l s et 3 [E-If]

iftruethent2elset3t2[E-IfTrue]iffalsethent2elset3t3[E-IfFalse]t1t1ift1thent2elset3ift1thent2elset3[E-If]

Angenommen, wir fügen auch die folgende Funky-Regel hinzu:

t 2t ' 2ich ft 1t h e nt 2e l s et 3i ft 1t h e nt ' 2e l s et 3 [E-IfFunny]

t2t2ift1thent2elset3ift1thent2elset3[E-IfFunny]

Für diese einfache Sprache mit den gegebenen Bewertungsregeln möchte ich folgendes beweisen:

Theorem: Wenn und r \ rightarrow t, dann gibt es einen Ausdruck u, so dass s \ rightarrow u und t \ rightarrow u .rsrsrtrtuususututu

Ich beweise dies durch Induktion auf die Struktur von rr . Hier ist mein bisheriger Beweis, es hat alles gut geklappt, aber ich stecke im allerletzten Fall fest. Es scheint, als würde eine Induktion der Struktur von rr nicht ausreichen. Kann mir jemand helfen?

Beweis. Durch Induktion von rr trennen wir alle Formen, die rr annehmen kann:

  1. rr ist eine Konstante, nichts zu beweisen, da eine normale Form nichts wertet.
  2. r=r= wenn dann sonst . (a) Beide Ableitungen wurden mit der E-IfTrue-Regel durchgeführt. In diesem Fall ist , es gibt also nichts zu beweisen. (b) Eine Ableitung wurde mit der E-IfTrue-Regel durchgeführt, die andere mit der E-Funny-Regel. Angenommen mit E-iftrue, der andere Fall ist äquivalent bewiesen gemacht wurde. Wir wissen jetzt, dass . Wir wissen auch, dass wenn wahr, dann sonst und dass es eine Ableitung (die Voraussetzung) gibt. Wenn wir nun wählen , schließen wir den Fall ab.r2r2r3r3s=ts=trsrss=r2s=r2t=t=r2r2r3r3r2r2r2r2u=r2u=r2
  3. r=r= wenn falsch dann sonst . Äquivalent wie oben bewiesen.r2r2r3r3
  4. r=r= wenn dann sonst mit wahr oder falsch. (a) Beide Ableitungen wurden mit der E-If-Regel durchgeführt. Wir wissen jetzt, dass wenn dann sonst und wenn dann sonst . Wir wissen auch, dass es die Ableitungen und (die Prämissen) gibt. Wir können jetzt die Induktionshypothese verwenden, um zu sagen, dass es einen Term so dassr1r1r2r2r3r3r1r1s=s=r1r1r2r2r3r3t=t=r1r′′1r2r2r3r3r1r1r1r1r1r1r1r′′1r1r′′′1r1r1r1r′′′1und . Wir schließen den Fall nun mit wenn dann sonst und bemerken, dass und durch die E-If-Regel sind. (b) Eine Ableitung wurde durch die E-If-Regel und eine durch die E-Funny-Regel durchgeführt.r1r1r′′1r′′′1u=u=r1r′′′1r2r2r3r3susututu

Letzterer Fall, in dem eine Ableitung von E-If und eine von E-Funny vorgenommen wurde, ist der Fall, den ich vermisse ... Ich kann die Hypothesen anscheinend nicht verwenden.

Hilfe wird sehr geschätzt.

codd
quelle
@Gilles sehr gut gemacht mit der Bearbeitung. Ich wusste nicht, dass die TeX-Engine von SE all das kann ... :-)
codd
Liege ich falsch oder stammt diese Übung von Pierce "Types and Programming Languages"?
Fabio F.
@FabioF. Es ist in der Tat aus Pierces Buch Types and Programming Languages. Er liefert einen Beweis, den ich aufgrund der Art und Weise, wie er die Induktion durchführt, unklar finde. Deshalb habe ich versucht, es selbst durch Induktion an der Struktur zu beweisen. Ich dachte darüber nach, zu erwähnen, dass es aus dem Buch stamme, aber ich dachte, das wäre ziemlich irrelevant. Aber gut aufgefallen!
Codd

Antworten:

7

, , wurde der E-If-Regel abgeleitet und wurde durch Anwendung der E-Funny-Regel abgeleitet: Also wobei und Dabei ist .r=ift1thent2elset3r=ift1thent2elset3sstts=ift1thent2elset3s=ift1thent2elset3t1t1t1t1t=ift1thent2elset3t=ift1thent2elset3t2t2t2t2

Die wir suchen ist . folgt aus der Regel E-Funny und folgt aus der Regel E-If.uuu=ift1thent2elset3u=ift1thent2elset3susututu

sepp2k
quelle
Schlagen Sie mich zu. Gut gemacht.
Patrick87
Meine Güte, ich habe wirklich zu weit geschaut ... Danke!
Codd
Du hast sie allerdings vertauscht, folgt aus E-Funny. Oder sehe ich etwas falsch? susu
Codd
@Jeroen Du hast Recht - ich habe sie durcheinander gebracht. Jetzt behoben.
sepp2k
8

Ein wenig Terminologie kann helfen , wenn Sie diese bis suchen wollen: Diese Regeln sind Umschreiben Regeln , sie haben nichts mit Typ systems¹ zu tun. Die Eigenschaft, die Sie nachweisen möchten, heißt Zusammenfluss . Insbesondere ist es eine starke Konfluenz : Wenn ein Begriff in einem Schritt auf unterschiedliche Weise reduziert werden kann, können sie im nächsten Schritt wieder zusammenlaufen. Im Allgemeinen erlaubt die Konfluenz, dass es eine beliebige Anzahl von Schritten gibt und nicht nur einen: Wenn r s und r t, dann gibt es u so, dass s u und t ursrtusutu - Wenn ein Begriff auf unterschiedliche Weise gekürzt werden kann, unabhängig davon, wie weit sie auseinander gegangen sind, können sie schließlich wieder zusammenlaufen.

Der beste Weg, eine Eigenschaft derartiger induktiv definierter Umschreibregeln zu beweisen, besteht in der Induktion über die Struktur der Herleitung der Reduktion und nicht über die Struktur des reduzierten Terms. Hier funktioniert beides, weil die Regeln der Struktur des linken Ausdrucks folgen, aber die Begründung der Regeln ist einfacher. Anstatt in den Begriff einzutauchen, nehmen Sie alle Regelpaare und sehen, welcher Begriff für beide eine linke Seite sein könnte. In diesem Beispiel erhalten Sie am Ende die gleichen Fälle, jedoch etwas schneller.

In dem Fall, dass Sie Schwierigkeiten haben, reduziert eine Seite den "Wenn" -Teil und die andere Seite den "Dann" -Teil. Es gibt keine Überlappung zwischen den beiden Teilen, die sich ändern ( t 1 in [E-If], t 2 in [E-IfFunny]), und es gibt keine Einschränkung für t 2 in [E-If] oder für t 1 in [E- IfFunny]. Also, wenn Sie einen Begriff haben, für den beide Regeln gelten - die müssen von der Form i f seint1t2t2t1r 1t h e nr 2e l s er 3 können Sie die Regeln in beliebiger Reihenfolge anwenden:ifr1thenr2elser3

ich fr 1t h e nr 2e l s er 3[E-If][E-IfFunny] i fr ' 1t h e nr 2e l s er 3ich fr 1t h e nr ' 2e l s er 3 [E-IfFunny][E-If]ich fr ' 1t h e nr ' 2e l s er 3

[E-If]ifr1thenr2elser3[E-IfFunny]ifr1thenr2elser3ifr1thenr2elser3[E-IfFunny]ifr1thenr2elser3[E-If]

¹ Manchmal sieht man Typen und Umschreiben zusammen, aber im Kern handelt es sich um orthogonale Konzepte.

Gilles 'SO - hör auf böse zu sein'
quelle