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

Question

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

• $ mathtt {true} $
• $ mathtt {false} $
• Если $ t_1, t_2, t_3 $ - это термины, то так же $ mathtt {if} : t_1 : mathtt {then} : t_2 : mathtt {else} : t_3 $

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

$$ begin {Gather*} dfrac {} { mathtt {if} : mathtt {true} : mathtt {there} : t_2 : mathtt {else} : t_3 to t_2} Text {[e-iftrue]} Quad dfrac {} { mathtt {if} : mathtt {false} : mathtt {there} : t_2 : mathtt {else} : t_3 to t_3 } text {[e-iffalse]} dfrac {t_1 to t_1 '} { mathtt {if} : t_1 : mathtt {there} : t_2 : mathtt {else} : t_3 to mathtt {if} : t_1 ': mathtt {there} : t_2 : mathtt {else} : t_3} text {[e-if]} end {Gather*} $ $

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

$$ 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 grightarrow u $.

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

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

1. $ r $ - это константе, нечего доказать, поскольку нормальная форма не оценивается ни на что.
2. $ r = $ if true, то $ r_2 $ else $ r_3 $. (а) Обе производные были сделаны с правилом e-iftrue. В этом случае $ s = t $, так что нечего доказать. (б) Одна деривиация была сделана с правилом e-iftrue, другой с правилом электронной фанаты. Предположим, что $ r rightarrow s $ была сделана с помощью e-iftrue, другой случай эквивалентно доказан. Теперь мы знаем, что $ s = r_2 $. Мы также знаем, что $ t = $ if true, то $ r'_2 $ else $ r_3 $, и что существует некоторая деривиация $ r_2 rightarrow r'_2 $ (предпосылка). Если мы сейчас выберем $ u = r'_2 $, мы завершим дело.
3. $ r = $ if false, то $ r_2 $ else $ r_3 $. Эквивалентно доказано, как указано выше.
4. $ r = $ if $ r_1 $, тогда $ r_2 $ else $ r_3 $ с $ r_1 neq $ true или false. (A) Обе производные были сделаны с правилом E-IF. Теперь мы знаем, что $ s = $ if $ r'_1 $, тогда $ r_2 $ else $ r_3 $ и $ t = $ if $ r '' _ 1 $, тогда $ r_2 $ else $ r_3 $. Мы также знаем, что существуют деривиции $ r_1 rightarrow r'_1 $ и $ r_1 rightarrow r '' _ 1 $ (помещение). Теперь мы можем использовать индукционную гипотезу, чтобы сказать, что существует какой -то термин $ r '' '' _ 1 $ такой, что $ r'_1 rightarrow r '' '_ 1 $ и $ r' '_ 1 rightarrow r' '' _ 1 $. Теперь мы завершаем дело, сказав $ u = $ if $ r '' '' _ 1 $, тогда $ r_2 $ else $ r_3 $ и заметив, что $ s rightarrow u $ и $ t rightarrow u $ по правилу e-if. (б) Один вывод был сделан правилом E-IF и одним правилом E-Funny.

Этот последний случай, когда один вывод был сделан E-IF, а один-E-Funny,-это то, что мне не хватает ... Я не могу использовать гипотезы.

Помощь будет очень оценена.

Answer 1

Итак, давайте рассмотрим случай, что $ r = mathtt {if} : t_1 : mathtt {there} : t_2 : mathtt {else} : t_3 $, $ s $ был получен путем применения E-IF Правило и $ T $ были получены путем применения правила E-Funny: SO $ 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 $ where $ $ t_2 rightarrow t'_2 $.

$ U $ Мы ищем $ u = mathtt {if} : t'_1 : mathtt {then} : t'_2 : mathtt {else} : t_3 $. $ s rightarrow u $ следует из правила e-funny и $ t rightarrow u $ следует из правила e-if.

Answer 2

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

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

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

$$ 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 & & rwarrow { small text {[e-if]}} & mathtt {if} : r_1 ': mathtt {then} : r_2' : mathtt {else} : r_3 & end {array} $$

¹ _{Иногда вы увидите типы и переписываетесь вместе, но по их сути они ортогональные концепции.}