Caractérisation des termes lambda qui ont des types d'union

De nombreux manuels couvrent les types d'intersection dans le lambda-calcul. Les règles de typage pour l'intersection peuvent être définies comme suit (en plus du lambda-calcul simplement tapé avec sous-typage):

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

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

Les types d'intersection ont des propriétés intéressantes par rapport à la normalisation:

Un lambda-term peut être saisi sans utiliser la règle si elle est fortement normalisée. $\top I$
Un lambda-term admet un type ne contenant pas ssi il a une forme normale. $\top$

Et si au lieu d'ajouter des intersections, nous ajoutons des unions?

\frac{Γ ⊢ M : T_{1}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor {je}_{1}) \frac{Γ ⊢ M : T_{2}}{Γ ⊢ M : T_{1} \lor T_{2}} (\lor {je}_{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)$

Le lambda-calcul avec des types simples, des sous-types et des unions a-t-il une propriété similaire intéressante? Comment caractériser les termes typables avec union?

lambda-calculus type-theory logic Gilles 'SO- arrête d'être méchant'
la source

Question interessante. Pourriez-vous dire que les interfaces de la POO correspondent à cela?

Raphael

Peut-être que vous pourriez être intéressé par ce cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…

Fabio F.

Réponses:

Dans le premier système, ce que vous appelez le sous-typage sont les deux règles suivantes:

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

Ils correspondent aux règles d'élimination pour ; sans eux, le conjonctif est plus ou moins inutile. $∧$ $∧$

Dans le deuxième système (avec les connecteurs et , auxquels nous pourrions également ajouter un ), les règles de sous-typage ci-dessus ne sont pas pertinentes, et je pense que les règles d'accompagnement que vous aviez en tête sont les suivantes: $∨$ $→$ $⊥$

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

Pour ce que ça vaut, ce système permet de taper (en utilisant la règle ), qui ne peut pas être tapé avec seulement des types simples, qui a une forme normale, mais qui ne normalise pas fortement . $(λx. I)Ω:A→A$ ${⊥}E$

Pensées aléatoires: (peut-être que cela vaut la peine de demander sur TCS)

Cela m'amène à conjecturer que les propriétés associées sont quelque chose comme:

un terme λ admet un type ne contenant pas ssi a une forme normale pour tout qui a une forme normale. ( échoue aux deux tests, mais le terme λ ci-dessus les réussit) $M$ $⊥$ $MN$ $N$ $δ$
un terme λ peut être typé sans utiliser la règle si est fortement normalisant pour tous fortement normalisés . $M$ ${⊥}E$ $MN$ $N$

Exercice: prouve-moi le contraire.

De plus, il semble que ce soit un cas dégénéré, nous devrions peut-être envisager d'ajouter ce type à l'image. Pour autant que je m'en souvienne, cela permettrait d'obtenir ? $A ∨ (A → {⊥})$

Stéphane Gimenez
la source

Bon point sur les règles de sous-typage, elles montrent que les types d'unions ne sont pas aussi naturels que les intersections (qui sont typées orthogonalement aux flèches). À propos de la deuxième partie, je dois réfléchir davantage.

Gilles 'SO- arrête d'être méchant'

Je pense que

répond à l'exercice, si vous parlez de types d'unions.

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

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

jmad

À propos de call / cc: il a besoin de plus que de simples termes lambda (comme les termes lambda-mu ou un autre framework) mais les systèmes de types sont des systèmes logiques plus complexes, dans lesquels les types d'unions peuvent ne pas être pertinents.

jmad

@jmad: En effet, les types d'intersections sont nécessaires pour saisir ce terme :-( Peut-être que considérer les unions et les intersections ensemble serait intéressant?

Stéphane Gimenez

Je serais intéressé par un terme λ que l'on peut taper avec des types d'union (rs. Avec des types d'intersection) mais pas avec des types simples (rs. Avec des types d'intersection).

jmad

Je veux juste expliquer pourquoi les types d'intersection sont bien adaptés pour caractériser les classes de normalisation (fort, tête ou faible), alors que d'autres systèmes de types ne le peuvent pas. (simplement tapé ou système F).

La principale différence est que vous devez dire: "si je peux taper et alors je peux taper ". Ce n'est souvent pas vrai dans les types sans intersection car un terme peut être dupliqué: $M_2$ $M_1→M_2$ $M_1$

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

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

puis taper signifie que vous pouvez taper les deux occurrences de mais pas avec le même type, par exemple $MNN$ $N$ Avec les types d'intersection, vous pouvez transformer ceci en:

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$

, puis l'étape cruciale est maintenant vraiment facile:

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$

donc

peut être tapé avec des types d'intersection.

(λ 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$

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

C'est pourquoi je ne pense pas qu'il existe une caractérisation facile de la normalisation pour les types d'union.

jmad
la source