Характеристика лямбда-терминов, имеющих типы объединения

Question

Многие учебники описывают типы пересечений в лямбда-исчислении.Правила типизации для пересечения могут быть определены следующим образом (поверх просто типизированного лямбда-исчисления с подтипом):

$$ \dfrac{\Гамма \vdash M :T_1 \quad \Gamma \vdash M :T_2} {\Гамма \vdash M :T_1 \клин T_2} (\клин I) \qquad\qquad \dfrac{} {\Гамма \vdash M : op} ( op I) $$

Типы пересечений обладают интересными свойствами в отношении нормализации:

• Лямбда-терм может быть введен без использования правила $ \ top I $, если оно сильно нормализуется.
• Лямбда-термин допускает тип, не содержащий $\ top$, если он имеет обычную форму.

Что, если вместо добавления пересечений мы добавим объединения?

$$ \dfrac{\Гамма \vdash M :T_1} {\Гамма \vdash M :T_1 \vee T_2} (\vee I_1) \qquad\qquad \dfrac{\Гамма \vdash M :T_2} {\Гамма \vdash M :T_1 \vee T_2} (\vee I_2) $$

Обладает ли лямбда-исчисление с простыми типами, подтипами и объединениями каким-либо интересным подобным свойством?Как можно охарактеризовать термины, типизируемые с помощью объединения?

Answer 1

В первой системе то, что вы называете подтипом, - это следующие два правила:

$$\dfrac{Γ, x: T_1 \vdash M: S}{Γ, x: T_1 ∧ T_2 \vdash M: S}(∧E_1)\quad\dfrac{Γ, x: T_2 \vdash M: S}{Γ, x: T_1 ∧ T_2 \vdash M: S}(∧E_2)$$

Они соответствуют правилам исключения для $∧$;без них соединительная $∧ $ более или менее бесполезна.

Во второй системе (со связками $∨ $ и $ → $, к которым мы также могли бы добавить $⊥ $) приведенные выше правила подтипирования не имеют значения, и я думаю, что сопутствующие правила, которые вы имели в виду, следующие:

$$\dfrac{Γ, x:T_1 \vdash M:S\quad Γ, x: T_2 \vdash M:S}{Γ, x: T_1 ∨ T_2 \vdash M: S}(∨E)\quad\dfrac{}{Γ, x:{⊥} \vdash M:S}({⊥}E)$$

Как бы то ни было, эта система позволяет ввести $(λx.I) Ω: A → A $ (используя правило $ {⊥} E $), которое нельзя вводить только простыми типами, которое имеет нормальную форму, но не сильно нормализуется.

---

Случайные мысли:(возможно, об этом стоит спросить в TCS)

Это наводит меня на предположение, что связанные свойства представляют собой что-то вроде:

• λ-член $ M $ допускает тип, не содержащий $⊥$, если $ MN $ имеет нормальную форму для всех $ N $, которые имеют нормальную форму.($ δ$ не проходит оба теста, но приведенный выше λ-член проходит их)
• λ-член $ M $ может быть введен без использования правила $ {⊥} E $, если $ MN $ является сильно нормализующим для всех сильно нормализующих $ N $.

Упражнение: докажи, что я ошибаюсь.

Кроме того, это, кажется, вырожденный случай, возможно, нам следует рассмотреть возможность добавления этот парень войди в картину.Насколько я помню, это позволило бы получить $A ∨ (A → {⊥}) $?

Answer 2

Я просто хочу объяснить, почему типы пересечений хорошо подходят для характеристики классов нормализации (сильная, голова или слабая), тогда как другие системы не могут. (простой или система f).

Ключевое отличие состоит в том, что вы должны сказать: «Если я могу ввести $ m_2 $ и $ m_1 → m_2 $, тогда я могу ввести $ m_1 $». Это часто не относится к типам неинтерекции, потому что термин может быть продублирован:

$$ ( lambda x.mxx) n → mnn $$

и затем набрать $ mnn $ означает, что вы можете напечатать оба вхождения $ n $, но не с одним и тем же типом, например, $$ M: T_1 → T_2 → T_3 Qquad N: T_1 Qquad N: T_2 $$ с типами пересечения Вы можете преобразовать это в: $$ M: T_1 Wedge T_2 → T_1 Wedge T_2 → T_3 QQQUAD N: T_1 WELGE T_2 $$, а затем важный шаг теперь действительно прост: $$ ( lambda x.mxx) : T_1 wedge t_2 → t_3 qquad n: t_1 wedge t_2 $$, так что $ ( lambda x.mxx) n $ can может напечатать с типами пересечения.

Теперь о типах профсоюзов: предположим, что вы можете ввести $ ( lambda x.xx) ( lambda yy) $ с некоторым типом профсоюза, тогда вы также можете ввести $ lambda x.xx $, а затем получить для некоторых типов $ s, t_1 , dots $ $$ x: t_1 vee t_2 vee dots vee t_n ⊢xx: s $$, но вы все равно должны доказать, что на каждую $ i $, $ x: t_i⊢xx: s $, который кажется невозможным Даже $ s $ - это тип профсоюза.

Вот почему я не думаю, что есть легкая характеристика нормализации для типов союзов.