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

29

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):

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

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.je
  • Un lambda-term admet un type ne contenant pas ssi il a une forme normale.

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

ΓM:T1ΓM:T1T2(je1)ΓM:T2ΓM:T1T2(je2)

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?

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:

11

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

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

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:

Γ,X:T1M:SΓ,X:T2M:SΓ,X:T1T2M:S(E)Γ,X: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.je)Ω:UNEUNEE


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)MMNNδ
  • un terme λ peut être typé sans utiliser la règle si est fortement normalisant pour tous fortement normalisés .MEMNN

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 ?UNE(UNE)

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.XX)(λ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
16

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 M 1M 2 alors je peux taper M 1 ". Ce n'est souvent pas vrai dans les types sans intersection car un terme peut être dupliqué:M2M1M2M1

(λX.MXX)NMNN

puis taper signifie que vous pouvez taper les deux occurrences de N mais pas avec le même type, par exemple M : T 1T 2T 3MNNN Avec les types d'intersection, vous pouvez transformer ceci en: M : T 1T 2T 1T 2T 3

M:T1T2T3N:T1N:T2
, puis l'étape cruciale est maintenant vraiment facile: ( λ x . M x x ) : T 1T 2T 3
M:T1T2T1T2T3N:T1T2
donc ( λ x . M x x ) N peut être tapé avec des types d'intersection.
(λX.MXX):T1T2T3N:T1T2
(λX.MXX)N

(λX.XX)(λy.y)λX.XXS,T1,

X:T1T2TnXX:S
jeX:TjeXX:SS

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