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

29

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

ΓM:T1ΓM:T2ΓM:T1T2(I)ΓM:(I)

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

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

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

ΓM:T1ΓM:T1T2(I1)ΓM:T2ΓM:T1T2(I2)

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

Жиль "ТАК - перестань быть злым"
источник
Интересный вопрос. Не могли бы вы сказать, что интерфейсы из ООП соответствуют этому?
Рафаэль
Может быть, вам может быть интересен этот cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…
Фабио Ф.

Ответы:

11

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

Γ,x:T1M:SΓ,x:T1T2M:S(E1)Γ,x:T2M:SΓ,x:T1T2M:S(E2)

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

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

Γ,x:T1M:SΓ,x:T2M:SΓ,x:T1T2M:S(E)Γ,x:M:S(E)

Для чего это стоит, эта система позволяет набирать (используя правило rule ), которое нельзя набирать простыми типами, которое имеет нормальную форму, но не сильно нормализует , E(λx.I)Ω:AAE


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

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

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

Упражнение: докажи, что я не прав.

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

Стефан Хименес
источник
Хорошие замечания по поводу правил подтипирования: они показывают, что типы объединения не так естественны, как пересечения (которые вводятся ортогонально стрелкам). О второй части мне нужно подумать еще немного.
Жиль "ТАК - перестань быть злым"
Я думаю, что отвечает на упражнение, если вы говорите о типах объединения. M=(λx.xx)(λy.y)
Джмад
О call / cc: ему нужно больше, чем просто лямбда-термины (например, лямбда-му-термины или другая структура), но системы типов являются более сложными, логическими системами, в которых типы объединения могут быть неактуальными.
Джмад
@jmad: Действительно, типы пересечений необходимы для того, чтобы ввести этот термин :-( Может быть, было бы интересно рассмотреть объединения и пересечения вместе?
Стефан Гименес
Я был бы заинтересован в λ-члене, который можно вводить с объединением типов (rs. С типами пересечений), но не с простыми типами (rs. С типами пересечений).
Джмад
16

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

M2M1M2M1

(λx.Mxx)NMNN

MNNN

M:T1T2T3N:T1N:T2
M:T1T2T1T2T3N:T1T2
(λx.Mxx):T1T2T3N:T1T2
(λx.Mxx)N можно набирать типами пересечений.

(λx.xx)(λy.y)λx.xxS,T1,

x:T1T2Tnxx:S
ix:Tixx:SS

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

jmad
источник