Доказательство слияния для простой системы переписывания

Предположим, у нас есть простой язык, который состоит из терминов:

$\mathtt{true}$
$\mathtt{false}$
если являются терминами, то $t_1,t_2,t_3$ $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$

Теперь предположим следующие логические правила оценки:

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

Предположим, мы также добавили следующее веселое правило:

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

Для этого простого языка с данными правилами оценки я хочу доказать следующее:

Теорема: если и то существует некоторый член такой, что и . $r \rightarrow s$ $r \rightarrow t$ $u$ $s \rightarrow u$ $t \rightarrow u$

Я доказываю это индукцией по структуре . Вот мое доказательство до сих пор, все сработало хорошо, но я застрял в самом последнем случае. Кажется, что индукции на структуру не достаточно, кто-нибудь может мне помочь? $r$ $r$

Доказательство. Индукцией по мы отделим все формы, которые может принимать : $r$ $r$

$r$ - это константа, доказывать нечего, так как нормальная форма ничего не оценивает.
$r=$ если истина, то иначе . (а) оба вывода были сделаны с помощью правила E-IfTrue. В этом случае , поэтому доказывать нечего. (б) один вывод был сделан с помощью правила E-IfTrue, другой - с помощью правила E-Funny. Предположим, что было сделано с E-IfTrue, другой случай эквивалентно доказан. Теперь мы знаем, что . Мы также знаем, что если true, то иначе и что существует некоторый дифференциал (предпосылка). Если мы теперь выберем , мы завершаем дело. $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=$ если ложь, то иначе . Эквивалентно доказано как выше. $r_2$ $r_3$
$r=$ если то иначе с true или false. (а) оба вывода были сделаны с правилом E-If. Теперь мы знаем, что если то иначе и если то иначе . Мы также знаем, что существуют дифференциации и (предпосылки). Теперь мы можем использовать гипотезу индукции, чтобы сказать, что существует некоторый термин такой что $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$ и . Теперь мы завершим случай, сказав if тогда иначе и заметив, что и по правилу E-If. (б) один вывод был произведен по правилу E-If, а другой - по правилу E-Funny. $r''_1 \rightarrow r'''_1$ $u =$ $r'''_1$ $r_2$ $r_3$ $s \rightarrow u$ $t \rightarrow u$

В последнем случае, когда один вывод был сделан E-If, а другой - E-Funny, это случай, которого я пропускаю ... Кажется, я не могу использовать гипотезы.

Помощь будет высоко ценится.

logic semantics proof-techniques term-rewriting Кодда
источник

@ Жиль очень хорошо с редактированием. Я не знал, что движок SE TeX способен на все это ... :-)

codd

Я не прав или это упражнение взято у Пирса "Типы и языки программирования"?

Фабио Ф.

@FabioF. Это действительно из книги Пирса «Типы и языки программирования». Он предоставляет доказательства, которые я нахожу неясными, из-за того, как он выполняет индукцию. Вот почему я попытался доказать это сам посредством наведения на структуру. Я думал упомянуть, что это из книги, но я подумал, что это будет довольно неактуально. Хорошо заметили, однако!

codd

Ответы:

Хорошо, давайте рассмотрим случай, когда , было получено путем применения правила E-If, а было получено путем применения правила E-Funny: So $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$

которого мы ищем является $u$ . следует из правила E-Funny, а следует из правила E-If. $u = \mathtt{if}\: t'_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ $s \rightarrow u$ $t \rightarrow u$

sepp2k
источник

Ударь меня к этому. Хорошая работа.

Patrick87

Черт возьми, я действительно смотрел слишком далеко ... Спасибо!

codd

Вы их перепутали, хотя

следует из E-Funny. Или я вижу что-то не так?

s \to u

$s \rightarrow u$

codd

@Jeroen Ты прав - я их перепутал. Исправлено сейчас.

sepp2k

Небольшая терминология может помочь, если вы хотите посмотреть это: эти правила переписывают правила , они не имеют ничего общего с системами типов¹. Свойство, которое вы пытаетесь доказать, называется слиянием ; более конкретно, это сильное слияние : если термин может быть сокращен различными способами за один шаг, они могут сходиться обратно на следующем шаге. В общем случае слияние допускает любое количество шагов, а не один: если и то существует такой, что и $r\to^*s$ $r\to^*t$ $u$ $s\to^*u$ $t\to^*u$ - если термин может быть сокращен по-разному, независимо от того, насколько далеко они разошлись, они могут в конечном итоге вернуться назад.

Лучший способ доказать свойство таких индуктивно определенных правил переписывания - это индукция по структуре производного сокращения, а не по структуре сокращенного члена. Здесь либо работает, потому что правила следуют структуре левого термина, но рассуждение о правилах проще. Вместо того, чтобы углубляться в термин, вы берете все пары правил и смотрите, какой термин может быть левой стороной для обоих. В этом примере вы получите те же случаи в конце, но немного быстрее.

В случае, если это доставляет вам неприятности, одна сторона уменьшает часть «если», а другая сторона уменьшает часть «тогда». Там нет перекрытия между двумя частями, которые изменяются ( в [E-If], в [E-IfFunny]), и нет никаких ограничений на в [E-If] или на в [E- IfFunny]. Поэтому , когда у вас есть термин , к которому оба правила применения - которые должны иметь вид $t1$ $t_2$ $t_2$ $t_1$ , вы можете применить правила в любом порядке: $\mathtt{if}\: r_1 \:\mathtt{then}\: r_2 \:\mathtt{else}\: r_3$

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

Sometimes _{Иногда вы будете видеть типы и переписывать вместе, но по своей сути они являются ортогональными понятиями.}

Жиль "ТАК - перестань быть злым"
источник