Bukti pertemuan untuk sistem penulisan ulang yang sederhana

14

Asumsikan kita memiliki bahasa sederhana yang terdiri dari istilah:

$\mathtt{true}$
$\mathtt{false}$
jika adalah suku maka demikian juga $t_1,t_2,t_3$ $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$

Sekarang asumsikan aturan evaluasi logis berikut:

\begin{matrix} \frac{}{i f t r u e t h e n t_{2} e l s e t_{3} \to t_{2}} [E-IfTrue] \frac{}{i f f a l s e t h e n t_{2} e l s e t_{3} \to t_{3}} [E-IfFalse] \\ \frac{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] \end{matrix}

$\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*}$

Misalkan kita juga menambahkan aturan funky berikut:

\frac{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]}$

Untuk bahasa sederhana ini dengan aturan evaluasi yang diberikan, saya ingin membuktikan yang berikut:

Teorema: Jika dan maka ada beberapa istilah sehingga dan $r \rightarrow s$ $r \rightarrow t$ $u$ $s \rightarrow u$ $t \rightarrow u$ .

Saya membuktikan ini dengan induksi pada struktur . Inilah bukti saya sejauh ini, semuanya bekerja dengan baik, tetapi saya terjebak pada kasus terakhir. Sepertinya induksi pada struktur $r$ $r$ tidak mencukupi, adakah yang bisa membantu saya?

Bukti. Dengan induksi pada , kami akan memisahkan semua bentuk yang dapat diambil : $r$ $r$

adalah konstanta, tidak ada yang perlu dibuktikan karena bentuk normal tidak mengevaluasi apa pun. $r$
jika benar maka lain . (a) kedua derivasi dilakukan dengan aturan E-IfTrue. Dalam hal ini , jadi tidak ada yang bisa dibuktikan. (B) satu deriviasi dilakukan dengan aturan E-IfTrue, yang lain dengan aturan E-Funny. Asumsikan dilakukan dengan E-IfTrue, kasus lain terbukti setara. Kita sekarang tahu bahwa . Kita juga tahu bahwa jika benar maka yang lain dan bahwa ada beberapa deriviation $r=$ $r_2$ $r_3$ $s=t$ $r \rightarrow s$ $s = r_2$ $t =$ $r'_2$ $r_3$ (premis). Jika sekarang kita memilih $r_2 \rightarrow r'_2$ $u = r'_2$ , kami menyimpulkan kasusnya.
jika salah maka lain $r=$ $r_2$ $r_3$ . Terbukti sama seperti di atas.
jika maka lain dengan benar atau salah. (a) kedua deriviasi dilakukan dengan aturan E-If. Kita sekarang tahu bahwa jika maka lagi dan jika maka lagi . Kita juga tahu bahwa ada deriviasi $r=$ $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$ dan (premis). Kita sekarang dapat menggunakan hipotesis induksi untuk mengatakan bahwa ada beberapa istilah sehingga dan . Kami sekarang menyimpulkan kasus dengan mengatakan jika maka lain dan memperhatikan bahwa dan $r_1 \rightarrow r''_1$ $r'''_1$ $r'_1 \rightarrow r'''_1$ $r''_1 \rightarrow r'''_1$ $u =$ $r'''_1$ $r_2$ $r_3$ $s \rightarrow u$ $t \rightarrow u$ oleh aturan E-If. (B) satu derivasi dilakukan oleh aturan E-If dan satu derivasi oleh aturan E-Funny.

Kasus terakhir ini, di mana satu derivasi dilakukan oleh E-If dan satu oleh E-Funny adalah kasus yang saya lewatkan ... Saya sepertinya tidak bisa menggunakan hipotesis.

Bantuan akan sangat dihargai.

logic semantics proof-techniques term-rewriting codd
sumber

@Gilles melakukan pengeditan dengan sangat baik. Saya tidak tahu bahwa mesin TeX SE mampu melakukan semua itu ... :-)

codd

Apakah saya salah atau latihan ini diambil dari Pierce "Jenis dan Bahasa Pemrograman"?

Fabio F.

@FabioF. Ini memang dari buku Jenis dan Bahasa Pemrograman Pierce. Dia memberikan bukti yang saya temukan tidak jelas, karena cara dia melakukan induksi. Itu sebabnya saya mencoba membuktikannya sendiri melalui induksi pada struktur. Saya berpikir untuk menyebutkan bahwa itu dari buku, tetapi saya pikir itu tidak relevan. Namun, sangat diperhatikan!

codd

7

Oke, jadi mari kita perhatikan kasus yang , telah diturunkan dengan menerapkan aturan E-If dan telah diturunkan dengan menerapkan aturan E-Funny: Jadi $r = \mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ $s$ $t$ mana dan $s = \mathtt{if}\: t'_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ $t_1 \rightarrow t'_1$ mana . $t = \mathtt{if}\: t_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ $t_2 \rightarrow t'_2$

The kita cari adalah $u$ $u = \mathtt{if}\: t'_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ . $s \rightarrow u$ follows from rule E-Funny and $t \rightarrow u$ follows from rule E-If.

sepp2k
sumber

Beat me to it. Nice job.

Patrick87

Gosh, I was really looking too far... Thanks!

codd

Anda mencampuradukkannya,

mengikuti dari E-Funny. Atau saya melihat sesuatu yang salah?

s \to u

$s \rightarrow u$

codd

@ Joen Kamu benar - aku mencampuradukkannya. Diperbaiki sekarang

sepp2k

8

$r\to^*s$ $r\to^*t$ $u$ $s\to^*u$ $t\to^*u$ - jika suatu istilah dapat dikurangi dengan cara yang berbeda, tidak peduli seberapa jauh mereka telah menyimpang, mereka akhirnya dapat bertemu kembali.

Cara terbaik untuk membuktikan sifat aturan penulisan ulang yang terdefinisi secara induktif adalah dengan menginduksi struktur derivasi reduksi, daripada struktur term yang dikurangi. Di sini, keduanya berfungsi, karena aturan mengikuti struktur istilah sebelah kiri, tetapi alasan pada aturan itu lebih sederhana. Alih-alih menyelam ke dalam istilah, Anda mengambil semua pasangan aturan, dan melihat istilah apa yang bisa menjadi sisi kiri untuk keduanya. Dalam contoh ini, Anda akan mendapatkan kasus yang sama pada akhirnya, tetapi sedikit lebih cepat.

$t1$ $t_2$ $t_2$ in [E-If] or on $t_1$ in [E-IfFunny]. So when you have a term to which both rules apply — which must be of the form $\mathtt{if}\: r_1 \:\mathtt{then}\: r_2 \:\mathtt{else}\: r_3$ , you can choose to apply the rules in either order:

\begin{array}{rcl} i f r_{1} t h e n r_{2} e l s e r_{3} \\ [E-If] ↙ & ↘ [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] ↘ & ↙ [E-If] \\ i f r_{1}^{'} t h e n r_{2}^{'} e l s e r_{3} \end{array}

$\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}$

¹ _{You'll sometimes see types and rewriting together, but at their core they're orthogonal concepts.}

Gilles 'SO- stop being evil'
sumber

Bukti pertemuan untuk sistem penulisan ulang yang sederhana

Jawaban: