Caracterización de lambda-términos que tienen tipos de unión

Question

Muchos libros de texto cubren intersección tipos en el cálculo lambda. Las reglas de escritura para intersección se pueden definir como sigue (en la parte superior de la lambda-cálculo simplemente mecanografiado con subtipificación):

$$ \ Dfrac {\ Gamma \ vdash M: T_1 \ quad \ Gamma \ vdash M: T_2} {\ Gamma \ vdash M: T_1 \ wedge} T_2 (\ Wedge I) \ Qquad \ qquad \ {} Dfrac {\ Gamma \ vdash M: \ superior} (\ I arriba) $$

tipos de intersecciones tienen propiedades interesantes con respecto a la normalización:

• Una lambda plazo se puede escribir sin utilizar el $ \ $ regla superior I si y sólo si es fuertemente normalizando.
• Una lambda plazo admite un tipo que no contiene $ \ $ si y sólo si la parte superior tiene una forma normal.

¿Qué pasa si en lugar de añadir intersecciones, añadimos los sindicatos?

$$ \ Dfrac {\ Gamma \ vdash M: T_1} {\ Gamma \ vdash M: T_1 \ vee T_2} (\ Vee I_1) \ Qquad \ qquad \ Dfrac {\ Gamma \ vdash M: T_2} {\ Gamma \ vdash M: T_1 \ vee T_2} (\ Vee I_2) $$

¿Tiene el lambda-cálculo con tipos simples, subtipificación y los sindicatos tienen ninguna propiedad similar interesante? ¿Cómo pueden los términos tipificable con la unión caracterizarse?

Answer 1

En el primer sistema de lo que se llama subtipificación son estas dos reglas:

$$ \ dfrac {gamma, X: T_1 \ vdash M: S} {gamma, x: T_1 ? T_2 \ vdash M: S} (?E_1) \ quad \ dfrac {G, x: T_2 \ vdash M : S} {G, x: T_1 ? T_2 \ vdash M: S} (?E_2) $$

Se corresponden con reglas de eliminación de $ ? $; sin ellos el $ $ conjuntivo ? es más o menos inútil.

En el segundo sistema (con conectivas $ ? $ y $ ? $, ??a la que también podríamos añadir un $ ? $), lo anterior normas de tipificación son irrelevantes, y creo que las reglas que acompañan que tenía en mente son los siguientes :

$$ \ dfrac {G, x: T_1 \ vdash M: S \ quad G, x: T_2 \ vdash M: S} {gamma, x: T_1 ? T_2 \ vdash M: S} (?E) \ quad \ dfrac {} {G, x: {?} \ vdash M: S} ({?} E) $$

Por lo que vale, este sistema permite que escribir $ O (?x I.): A ? A $ (utilizando la $ {?} E $ regla), que no se puede escribir con sólo tipos simples, que tiene una normalidad la forma, pero no es fuertemente normalizando.

---

Pensamientos al azar: (tal vez esto vale la pena preguntar sobre TCS)

Esto me lleva a la conjetura de que las propiedades relacionadas son algo como:

• a ? plazo $ M $ admite un tipo que no contiene $ ? $ iff $ MN $ tiene una forma normal para todos $ N $ que tiene una forma normal. ($ ? $ falla ambas pruebas, pero lo anterior ? plazo pase ellos)
• ? un plazo $ M $ se puede escribir sin utilizar el $ {} $ ? regla E si y sólo si $ MN $ es firmemente la normalización para todos $ fuertemente normalizando N $.

Ejercicio:. demostrar que estoy equivocado

También parece ser un caso degenerado, tal vez deberíamos considerar la adición de este chico en la imagen. Por lo que yo recuerdo, que permitiría obtener $ A ? (A ? {?}) $?

Answer 2

Sólo quiero explicar por qué tipos de intersección son muy adecuados para caracterizar las clases de normalización (fuerte, la cabeza o débil), mientras que otros sistemas de tipo no puede. (Simplemente-tecleado o sistema F).

La diferencia clave es que usted tiene que decir: "si puedo escribir $ M_2 $ y $ M_1 ? $ M_2 entonces puedo escribir $ M_1 $". Esto a menudo no es cierto en los tipos no intersección debido a que un término puede ser duplicado:

$$ (\ lambda x.Mxx) N ? MNN $$

y escribiendo $ $ MNN medios que puede escribir dos apariciones de $ N $ pero no con el mismo tipo, por ejemplo, $$ M: T_1 ? T_2 ? T_3 \ qquad N: T_1 \ qquad N: T_2 $$ Con los tipos de intersección se puede transformar esto en: $$ M: T_1 \ wedge T_2 ? T_1 \ wedge T_2 ? T_3 \ qquad N: T_1 \ wedge T_2 $$ y luego el paso crucial es ahora muy fácil: $$ (\ lambda x.Mxx): T_1 \ wedge T_2 ? T_3 \ qquad N: T_1 \ wedge T_2 $$ por lo que $ (\ lambda x.Mxx) N $ puede por escrito con los tipos de intersección.

Ahora sobre tipos de unión: supongamos que puede escribir $ (\ lambda x, xx) (\ lambda aa) $ con algún tipo de unión, a continuación, también puede escribir $ \ lambda $ x, xx y luego para algunos tipos $ S, T_1, \ dots $ $$ x: T_1 \ vee T_2 \ vee \ puntos \ vee T_n ?xx: S $$ Pero todavía tiene que demostrar que por cada $ i $, $ x: T_i?xx: S $ que parece imposible, incluso es $ S $ es un tipo de unión.

Esta es la razón por la que no creo que es una caracterización sencilla sobre la normalización de tipos de unión.