Relation entre le système d'attribution de type (TA) et le système Hindley-Milner

Récemment, j'ai commencé mes études en théorie des types / systèmes de types et Lambda Calculus.

J'ai déjà lu sur le calcul lambda simple typé dans le style Church and Curry. Le dernier est également connu sous le nom de système d'attribution de type (TA).

Je pense aux relations entre TA et Hindley-Milner (HM), le système dans des langues comme ML et Haskell.

Le livre Lambda-Calculus and Combinators: An Introduction (Hindley) dit que TA est polymorphe (pag. 119). Est-ce le même sens du polymorphisme dans des systèmes comme HM et System-F?

Le TA aurait la forte propriété de normalisation, il n'est donc pas complet. Les langages utilisant le système HM sont complets, Haskell par exemple. Il doit donc en être ainsi que le système HM autorise des termes comme la boucle infinie $\Omega$ pour recevoir un type. Est-ce correct ou il me manque quelque chose?

Quoi qu'il en soit, j'aimerais connaître la relation entre TA et HM.

type-theory type-checking type-inference Rafael Castro
la source

Je n'ai jamais entendu parler du système d'affectation typée auparavant. Je l'ai googlé et j'ai obtenu cette question comme troisième réponse, ce qui signifie qu'elle doit être très niche. Pouvez-vous expliquer ce que c'est? De plus, qu'est-ce qu'une "boucle infinie"? Voulez-vous dire un calcul sans interruption?

gardenhead

L'attribution de type est une version du calcul lambda simple typé créé par Curry. Vous devriez chercher cela dans le livre mentionné. Et oui,

Ω

$\Omega$ est la boucle infinie par défaut

λ

$\lambda$ calcul ou le programme sans interruption.

Rafael Castro

Je pense que je devrais poser cette question dans un autre échange de pile plus théorique / mathématique. Devrais-je?

Rafael Castro

Tu pourrais essayer. Donnez une chance à cstheory et mathoverflow. Cependant, vous avez dit que vous "aviez récemment commencé vos études", donc je serais surpris si votre question était si avancée. Je pense que vous utilisez simplement une terminologie inhabituelle pour décrire des concepts simples (pourrait être faux cependant). Par exemple, la boucle infinie est généralement appelée le type inférieur (si je vous comprends bien).

gardenhead

Certainement ma question n'est pas au niveau de la recherche. Ma question est plus comme "hé, je comprends les concepts de base, n'est-ce pas?". Mais je vais essayer, peut-être que j'obtiens une réponse.

Rafael Castro

Réponses:

Le système F et son sous-système HM ont un ancien type pour la quantification universelle:

τ ::= \forall x . τ | . . .

$\tau \quad::=\quad \forall x.\tau \ |\ ...$

que le système de Hindley / Seldin n'a pas. Voilà la principale différence.

Désormais, le système F n'a pas d'inférence de type décidable, et HM est un moyen de combiner l'inférence de type avec un polymorphisme paramétrique raisonnablement expressif. HM y parvient en autorisant uniquement la quantification universelle la plus externe, c'est-à-dire que tous les types sont de la forme

\forall x_{1} \forall x_{2} . . . \forall x_{n} . τ

$\forall x_1 \forall x_2 ... \forall x_n.\tau$

où $\tau$ est sans quantificateur (et $n \geq 0$ ). HM propose un système de règles garantissant que seuls les programmes pouvant être saisis de cette manière sont admissibles. Ceci est réalisé par "let-polymorphisme". Le système de Hindley / Seldin ne fait rien de tout cela. Plus tard, dans le chapitre 13, Hindley / Seldin présente des systèmes de type pur (PTS), dont le système F est un cas spécial. Je ne sais pas si HM peut être exprimé en PTS.

La question d'une forte normalisation est orthogonale. Les systèmes F et HM normalisent fortement, mais cela peut facilement être résolu en introduisant des combinateurs à point fixe ou similaire. L'article principal Schémas de type pour les programmes fonctionnels par L. Damas et R. Milner déclare même ceci: " Par exemple, la récursivité est omise car elle peut être introduite en ajoutant simplement l'opérateur polymorphe à point fixe ... " L'introduction des points fixes , rendant le système Turing complet, ne pose aucun problème du point de vue de l'inférence de type.

Martin Berger
la source

Serait-il correct de penser HM = TA + "let-polymorphism"? Le livre Lambda-Calculus and Combinators (Hindley), jusqu'à présent, n'a rien dit sur la quantification universelle des types. TA utilise des variables de type, mais je ne sais rien de la gamme de ces types. Pour être clair, je n'ai pas encore étudié le système HM, mais je sais à quoi ça sert.

Rafael Castro

@RafaelCastro Si vous plissez les yeux ... Si vous avez un arrière-plan CS, le livre TAPL de Pierce est probablement une explication beaucoup plus accessible de HM et des systèmes de frappe en général. Le document Damas / Milner auquel j'ai fait référence est très facile à lire, si vous pouvez voir au-delà de la mise en page à l'ancienne. Je le donne à mes débutants en doctorat. Lisez-le! Hindley / Seldin est un peu formel.

Martin Berger

@RafaelCastro Les variables de type s'étendent sur les types. Tous les types. C'est pourquoi le système F est imprédicatif.

Martin Berger

Je vous remercie. Oui, je suis un étudiant de premier cycle en CS, donc je vais essayer le livre TAPL de Pierce.

Rafael Castro

@RafaelCastro Il n'y a probablement pas de meilleure façon d'apprendre sur les types que de lire TAPL et d'implémenter les systèmes de frappe qui y sont discutés.

Martin Berger