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

Muchos libros de texto cubren los tipos de intersección en el cálculo lambda. Las reglas de tipeo para la intersección se pueden definir de la siguiente manera (además del cálculo lambda simplemente tipado con subtipado):

\frac{Γ ⊢ M : T_{1} Γ ⊢ M : T_{2}}{Γ ⊢ M : T_{1} \land T_{2}} (\land I) \frac{}{Γ ⊢ M : ⊤} (⊤ I)

$\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 : \top} (\top I)$

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

Un término lambda se puede escribir sin usar la regla $\top I$ si se está normalizando fuertemente.
Un término lambda admite un tipo que no contiene $\top$ si tiene una forma normal.

¿Qué pasa si en lugar de agregar intersecciones, agregamos uniones?

\frac{Γ ⊢ M : T_{1}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor I_{1}) \frac{Γ ⊢ M : T_{2}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor I_{2})

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

¿El cálculo lambda con tipos simples, subtipos y uniones tiene alguna propiedad similar interesante? ¿Cómo pueden caracterizarse los términos tipificables con unión?

lambda-calculus type-theory logic Gilles 'SO- deja de ser malvado'
fuente

Interesante pregunta. ¿Podría decir que las interfaces de OOP corresponden a esto?

Raphael

Quizás te pueda interesar este cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…

Fabio F.

Respuestas:

En el primer sistema, lo que llama subtipo son estas dos reglas:

\frac{Γ, x : T_{1} ⊢ M : S}{Γ, x : T_{1} \land T_{2} ⊢ M : S} (\land E_{1}) \frac{Γ, x : T_{2} ⊢ M : S}{Γ, x : T_{1} \land T_{2} ⊢ M : S} (\land E_{2})

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

Corresponden a reglas de eliminación para ; sin ellos, el conectivo es más o menos inútil. $∧$ $∧$

En el segundo sistema (con las conectivas y , a las que también podríamos agregar un ), las reglas de subtipo anteriores son irrelevantes, y creo que las reglas que tenía en mente son las siguientes: $∨$ $→$ $⊥$

\frac{Γ, x : T_{1} ⊢ M : S Γ, x : T_{2} ⊢ M : S}{Γ, x : T_{1} \lor T_{2} ⊢ M : S} (\lor E) \frac{}{Γ, x : ⊥ ⊢ M : S} (⊥ E)

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

Por lo que vale, este sistema permite escribir (usando la regla ), que no se puede escribir solo con tipos simples, que tiene una forma normal, pero no se normaliza fuertemente . $(λx. I)Ω:A→A$ ${⊥}E$

Pensamientos aleatorios: (quizás valga la pena preguntar esto en TCS)

Esto me lleva a conjeturar que las propiedades relacionadas son algo así como:

un término λ admite un tipo que no contiene si tiene una forma normal para todo que tiene una forma normal. ( falla ambas pruebas, pero el término λ anterior las pasa) $M$ $⊥$ $MN$ $N$ $δ$
Se puede escribir un término λ sin utilizar la regla si f se normaliza fuertemente para todos los fuertemente normalizadores . $M$ ${⊥}E$ $MN$ $N$

Ejercicio: prueba que estoy equivocado.

También parece ser un caso degenerado, tal vez deberíamos considerar agregar a este tipo en la imagen. Por lo que recuerdo, ¿permitiría obtener ? $A ∨ (A → {⊥})$

Stéphane Gimenez
fuente

Un buen punto sobre las reglas de subtipo, muestran que los tipos de unión no son tan naturales como las intersecciones (que se escriben ortogonalmente a flechas). Sobre la segunda parte, necesito pensar un poco más.

Gilles 'SO- deja de ser malvado'

Creo que responde el ejercicio, si estás hablando de tipos de unión.

M = (λ x . x x) (λ y . y)

$M=(\lambda x.xx)(\lambda y.y)$

jmad

Acerca de call / cc: necesita más que solo términos lambda (como términos lambda-mu u otro marco), pero los sistemas de tipos son sistemas lógicos más complejos, en los que los tipos de unión pueden ser irrelevantes.

jmad

@jmad: De hecho, se necesitan tipos de intersección para escribir este término :-( ¿Quizás sería interesante considerar uniones e intersecciones juntas?

Stéphane Gimenez

Me interesaría un término λ que se pueda escribir con tipos de unión (rs. Con tipos de intersección) pero no con tipos simples (rs. Con tipos de intersección).

jmad

Solo quiero explicar por qué los tipos de intersección son adecuados para caracterizar clases de normalización (fuerte, cabeza o débil), mientras que otros sistemas de tipos no pueden. (de tipo simple o sistema F).

La diferencia clave es que debe decir: "si puedo escribir y entonces puedo escribir ". Esto a menudo no es cierto en los tipos sin intersección porque un término puede duplicarse: $M_2$ $M_1→M_2$ $M_1$

(λ x . M x x) N \to M N N

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

y luego escribir significa que puede escribir ambas apariciones de pero no con el mismo tipo, por ejemplo Con los tipos de intersección puede transformar esto en: y el paso crucial ahora es realmente fácil: so puede con tipos de intersección $MNN$ $N$

M : T_{1} \to T_{2} \to T_{3} N : T_{1} N : T_{2}

$M:T_1→T_2→T_3 \qquad N:T_1 \qquad N:T_2$

M : T_{1} \land T_{2} \to T_{1} \land T_{2} \to T_{3} N : T_{1} \land T_{2}

$M:T_1\wedge T_2→T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$

(λ x . M x x) : T_{1} \land T_{2} \to T_{3} N : T_{1} \land T_{2}

$(\lambda x.Mxx):T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$

(λ x . M x x) N

$(\lambda x.Mxx)N$

Ahora sobre los tipos de unión: suponga que puede escribir con algún tipo de unión, luego también puede escribir y luego obtener algunos tipos Pero todavía tienes que demostrar que por cada , que parece imposible, incluso si es un tipo de unión. $(\lambda x.xx)(\lambda y.y)$ $\lambda x.xx$ $S, T_1, \dots$

x : T_{1} \lor T_{2} \lor \dots \lor T_{n} ⊢ x x : S

$x : T_1\vee T_2 \vee \dots \vee T_n ⊢xx:S$

i

$i$

x : T_{i} ⊢ x x : S

$x:T_i⊢xx:S$

S

$S$

Es por eso que no creo que haya una caracterización fácil sobre la normalización para los tipos de unión.

jmad
fuente