Pourquoi avons-nous besoin d’une notation distincte pour les types P ?

Question

Principal

Je ne comprends pas la motivation derrière la nécessité d'une notation distincte pour les types P, que vous pouvez trouver dans les systèmes de types à partir de λ2.La réponse est généralement la suivante : réfléchissez à la façon dont on peut représenter une signature de fonction d'identité ; cela peut être λa:type.λx:a.x ou λb:type.λx:b.x.Ce qui est subtil, disent-ils, c'est que ces deux signatures non seulement not equal, ils ne sont pas équivalents alpha en tant que variables de type a et b sont des variables libres à l'intérieur de leurs abstractions correspondantes.Donc, pour surmonter ce problème syntaxique embêtant, nous présentons П binder qui joue bien avec la conversion alpha.

Alors la question :pourquoi donc?Pourquoi ne pas simplement corriger la notion d'équivalence alpha ?

MISE À JOUR z :

Oh, c'est idiot de ma part, λa:type.λx:a.x et λb:type.λx:b.x sont équivalents alpha.Mais pourquoi a:type -> a -> a et b:type -> b -> b ne le sont pas alors.

MISE À JOUR comme suit :

Aha, intéressant, je suppose que c'est un exemple parfait de cécité sélective =D

je suis en train de lire le livre Théorie des types et preuve formelle, et dans le chapitre sur lambda2, l'auteur motive l'existence de П en utilisant exactement ce genre d'argumentation - on ne peut pas dire que \t:*.\v:t.v : * -> t -> t parce que cela fait deux termes alpha-équivalents\t:*.\v:t.v et \g:*.\v:g.v ont des types différents, car les types correspondants ne sont pas équivalents en alpha, où des types comme t:* -> t -> t sont en fait alpha-invariants. Attention à la différence entre t:* -> t -> t et * -> t -> t.Mais cela ne rend-il pas cet argument un peu trivial, et est-ce même quelque chose de significatif de parler de type a -> b où a et b ne sont liés par aucune variable de quantificateur.Andrej Bauer souligné dans les commentaires que П Cela ressemble en effet à une abstraction lambda avec quelques cloches et sifflets supplémentaires.

Dans l’ensemble, j’en ai fini avec celui-là, merci les gars.

Answer 1

Je pense que nous devons juste mettre les choses au clair ici :

1. Dans l'expression $\lambda a :\mathsf{type} .\lambda x :un .x$ la variable $un$ est attaché (par l'extérieur $\lambda$).Les expressions $\lambda a :\mathsf{type} .\lambda x :un .x$ et $\lambda b :\mathsf{type} .\lambda x :b.x$ sont $\alpha$-égal.
2. L'expression $\lambda a :\mathsf{type} .\lambda x :un .x$ est la fonction d'identité, c'est pas la « signature de la fonction identitaire ».
3. Si par « signature de la fonction d'identité » vous entendez « le type de la fonction d'identité », alors ce serait quelque chose comme $\Pi_{a :\mathsf{type}} .(une \à une)$, ou si vous souhaitez uniquement des types de produits, alors c'est $\Pi_{a :\mathsf{type}} \Pi_{x :un} un$.

Y a-t-il encore une question ?

Peut-être que ceci aidera :

• le type de la fonction d'identité $\lambdax :un .x$ est $a \à a$
• le type de la fonction d'identité $\lambda y :b.y$ est $b \à b$
• les fonctions $\lambdax :un .x$ et $\lambda y :b.y$ sont différents
• les genres $a \à a$ et $b \à b$ sont différents
• le type de polymorphe fonction d'identité $\lambda c :\mathsf{type} .\lambda z :c.z$ est $\Pi_{c :\mathsf{type}} .c \à c$.
• les fonctions $\lambda a :\mathsf{type} .\lambda x :un .x$ et $\lambda c :\mathsf{type} .\lambda z :c.z$ sont $\alpha$-égal
• les genres $\Pi_{a :\mathsf{type}} .un \à un$ et $\Pi_{c :\mathsf{type}} .c \à c$ sont $\alpha$-égal.

Supplémentaire : Après avoir discuté avec Alex Simpson autour d'une tasse de thé, je peux encore dire une chose.Nous ne le faisons pas besoin séparé $\lambda$ et $\Pi$ constructeurs, car ils ont tous deux exactement la même forme syntaxique (prendre deux arguments, lier une variable).En fait, si ma mémoire est bonne, Automate utilisé la même notation pour $\lambda$-des abstractions et $\Pi$-les types.Mais le fait est que nous vouloir utiliser deux constructeurs différents car ils désignent différentes notions.