Konfluenznachweis für ein einfaches Umschreibesystem

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

$\mathtt{true}$
$\mathtt{false}$
Wenn Terme sind, ist dies auch $t_1,t_2,t_3$ $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$

Nehmen wir nun folgende logische Auswertungsregeln an:

i f t r u e t h e n t 2 e l s e t 3 \to t 2 [E-IfTrue] i f f a l s e t h e n t 2 e l s e t 3 \to t 3 [E-IfFalse] t 1 \to t ' 1 i f t 1 t h e n t 2 e l s e t 3 \to i f t ' 1 t h e n t 2 e l s e t 3 [E-If]

$\begin{gather*} \dfrac{} {\mathtt{if}\: \mathtt{true} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_2} \text{[E-IfTrue]} \quad \dfrac{} {\mathtt{if}\: \mathtt{false} \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to t_3} \text{[E-IfFalse]} \\ \dfrac{t_1 \to t_1'} {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1' \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3} \text{[E-If]} \\ \end{gather*}$

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

t 2 \to t ' 2 i f t 1 t h e n t 2 e l s e t 3 \to i f t 1 t h e n t ' 2 e l s e t 3 [E-IfFunny]

$\dfrac{t_2 \to t_2'} {\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3 \to \mathtt{if}\: t_1 \:\mathtt{then}\: t_2' \:\mathtt{else}\: t_3} \text{[E-IfFunny]}$

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

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

Ich beweise dies durch Induktion auf die Struktur von $r$ . 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 $r$ nicht ausreichen. Kann mir jemand helfen?

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

$r$ ist eine Konstante, nichts zu beweisen, da eine normale Form nichts wertet.
$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. $r_2$ $r_3$ $s=t$ $r \rightarrow s$ $s = r_2$ $t =$ $r'_2$ $r_3$ $r_2 \rightarrow r'_2$ $u = r'_2$
$r=$ wenn falsch dann sonst . Äquivalent wie oben bewiesen. $r_2$ $r_3$
$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 dass $r_1$ $r_2$ $r_3$ $r_1 \neq$ $s =$ $r'_1$ $r_2$ $r_3$ $t =$ $r''_1$ $r_2$ $r_3$ $r_1 \rightarrow r'_1$ $r_1 \rightarrow r''_1$ $r'''_1$ $r'_1 \rightarrow r'''_1$ und . 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. $r''_1 \rightarrow r'''_1$ $u =$ $r'''_1$ $r_2$ $r_3$ $s \rightarrow u$ $t \rightarrow u$

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.

logic semantics proof-techniques term-rewriting 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:

, , wurde der E-If-Regel abgeleitet und wurde durch Anwendung der E-Funny-Regel abgeleitet: Also wobei und Dabei ist . $r = \mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ $s$ $t$ $s = \mathtt{if}\: t'_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ $t_1 \rightarrow t'_1$ $t = \mathtt{if}\: t_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ $t_2 \rightarrow t'_2$

Die wir suchen ist . folgt aus der Regel E-Funny und folgt aus der Regel E-If. $u$ $u = \mathtt{if}\: t'_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ $s \rightarrow u$ $t \rightarrow u$

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?

s→u $s \rightarrow u$

Codd

@Jeroen Du hast Recht - ich habe sie durcheinander gebracht. Jetzt behoben.

sepp2k

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 und dann gibt es so, dass und $r\to^*s$ $r\to^*t$ $u$ $s\to^*u$ $t\to^*u$ - 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 ( in [E-If], in [E-IfFunny]), und es gibt keine Einschränkung für in [E-If] oder für in [E- IfFunny]. Also, wenn Sie einen Begriff haben, für den beide Regeln gelten - die müssen von der Form $t1$ $t_2$ $t_2$ $t_1$ können Sie die Regeln in beliebiger Reihenfolge anwenden: $\mathtt{if}\: r_1 \:\mathtt{then}\: r_2 \:\mathtt{else}\: r_3$

[E-If] ↙ i f r' 1 t h e n r 2 e l s e r 3 [E-IfFunny] ↘ i f r 1 t h e n r 2 e l s e r 3 i f r' 1 t h e n r' 2 e l s e r 3 ↘ [E-IfFunny] i f r 1 t h e n r' 2 e l s e r 3 ↙ [E-If]

$\begin{array}{rcl} & \mathtt{if}\: r_1 \:\mathtt{then}\: r_2 \:\mathtt{else}\: r_3 & \\ {\small \text{[E-If]}} \swarrow & & \searrow {\small \text{[E-IfFunny]}} \\ \mathtt{if}\: r_1' \:\mathtt{then}\: r_2 \:\mathtt{else}\: r_3 & & \mathtt{if}\: r_1 \:\mathtt{then}\: r_2' \:\mathtt{else}\: r_3 \\ {\small \text{[E-IfFunny]}} \searrow & & \swarrow {\small \text{[E-If]}} \\ & \mathtt{if}\: r_1' \:\mathtt{then}\: r_2' \:\mathtt{else}\: r_3 & \\ \end{array}$

¹ _{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