Question «Quelle partie de Hindley-Milner ne comprends-tu pas?


je jurer il y avait un T-shirt à vendre avec les mots immortels:


Quelle partie de

Hindley-Milner

le faites vous ne pas comprendre?


Dans mon cas, la réponse serait ... tout ça!

En particulier, je vois souvent une telle notation dans les papiers Haskell, mais je n'ai aucune idée de ce que cela veut dire. Je n'ai aucune idée de quelle branche de mathématiques il est censé être.

Je reconnais bien sûr les lettres de l'alphabet grec et des symboles tels que "∉" (ce qui signifie généralement que quelque chose n'est pas un élément d'un ensemble).

D'un autre côté, je n'ai jamais vu "⊢" avant (Wikipedia prétend que cela pourrait signifier "partition"). Je ne suis pas familier avec l'utilisation du vinculum ici. (Habituellement, il dénote une fraction, mais cela ne apparaître être le cas ici.)

Si quelqu'un pouvait au moins me dire par où commencer à chercher à comprendre ce que signifie cette mer de symboles, cela serait utile.


750
2017-09-21 14:29


origine


Réponses:


  • le barre horizontale signifie que "[ci-dessus] implique [au dessous de]".
  • S'il y a plusieurs expressions dans [ci-dessus], alors considérez-les anded ensemble; tous les [ci-dessus] doivent être vrais afin de garantir le [ci-dessous].
  • : veux dire a type
  •  veux dire est dans. (Également  signifie "n'est pas dans".)
  • Γ est habituellement utilisé pour se référer à un environnement ou contexte; dans ce cas, il peut être considéré comme un ensemble d'annotations de type, en appariant un identifiant avec son type. Donc x : σ ∈ Γ signifie que l'environnement Γ comprend le fait que x a type σ.
  •  peut être lu comme prouve ou détermine. Γ ⊢ x : σ signifie que l'environnement Γ détermine que x a type σ.
  • , est un moyen de comprenant hypothèses supplémentaires spécifiques dans un environnement Γ.
    Donc, Γ, x : τ ⊢ e : τ' signifie que l'environnement Γ, avec l'hypothèse supplémentaire, primordiale x a type τ, prouve que e a type τ'.

560
2017-09-21 17:28



Cette syntaxe, même si elle peut sembler compliquée, est en fait assez simple. L'idée de base vient de la logique: l'expression entière est une implication avec la moitié supérieure étant les hypothèses et la moitié inférieure étant le résultat. C'est-à-dire, si vous savez que les expressions supérieures sont vraies, vous pouvez conclure que les expressions du bas sont également vraies.

Symboles

Une autre chose à garder à l'esprit est que certaines lettres ont des significations traditionnelles; en particulier, Γ représente le «contexte» dans lequel vous vous trouvez, c'est-à-dire les types d'autres choses que vous avez vues. Donc quelque chose comme Γ ⊢ ... signifie "l'expression ... quand vous connaissez les types de chaque expression dans Γ.

le  symbole signifie essentiellement que vous pouvez prouver quelque chose. Alors Γ ⊢ ... est une déclaration disant "je peux prouver ... dans un contexte Γ. Ces déclarations sont également appelées jugements de type.

Une autre chose à garder à l'esprit: en mathématiques, tout comme ML et Scala, x : σ signifie que x a type σ. Vous pouvez le lire comme Haskell x :: σ.

Ce que signifie chaque règle

Donc, sachant cela, la première expression devient facile à comprendre: si nous savons que x : σ ∈ Γ (C'est, x a un certain type σ dans un certain contexte Γ), alors nous savons que Γ ⊢ x : σ (C'est dedans Γ, x a type σ). Donc, vraiment, cela ne vous dit rien de super intéressant; cela vous dit juste comment utiliser votre contexte.

Les autres règles sont aussi simples. Par exemple, prenez [App]. Cette règle a deux conditions: e₀ est une fonction d'un certain type τ à un certain type τ' et e₁ est une valeur de type τ. Maintenant vous savez quel type vous obtiendrez en appliquant e₀ à e₁! J'espère que ce n'est pas une surprise :).

La règle suivante a une nouvelle syntaxe plus récente. Particulièrement, Γ, x : τ signifie simplement le contexte composé de Γ et le jugement x : τ. Donc, si nous savons que la variable x a un type de τ et l'expression e a un type τ', nous connaissons aussi le type d'une fonction qui prend x et retourne e. Cela nous dit juste quoi faire si nous avons compris quel type de fonction prend et quel type il retourne, donc cela ne devrait pas être surprenant non plus.

Le prochain vous dit juste comment gérer let déclarations. Si vous connaissez cette expression e₁ a un type τ aussi longtemps que x a un type σ, puis un let expression qui lie localement x à une valeur de type σ fera e₁ avoir un type τ. Vraiment, cela vous dit simplement qu'une instruction let vous permet essentiellement d'étendre le contexte avec une nouvelle liaison - qui est exactement ce que let Est-ce que!

le [Inst] la règle traite du sous-typage. Il dit que si vous avez une valeur de type σ' et c'est un sous-type de σ ( représente une relation d'ordre partielle) alors cette expression est aussi de type σ.

La règle finale traite des types généralisants. Un petit aparté: une variable libre est une variable qui n'est pas introduite par une instruction let ou lambda dans une expression; cette expression dépend maintenant de la valeur de la variable libre de son contexte. La règle dit que s'il y a une variable α lequel est ne pas "libre" dans tout ce qui est dans votre contexte, alors il est prudent de dire que toute expression dont vous connaissez le type e : σ aura ce type pour tout valeur de α.

Comment utiliser les règles

Donc, maintenant que vous comprenez les symboles, que faites-vous avec ces règles? Eh bien, vous pouvez utiliser ces règles pour déterminer le type de différentes valeurs. Pour ce faire, regardez votre expression (par exemple f x y) et trouvez une règle qui a une conclusion (la partie inférieure) qui correspond à votre déclaration. Appelons la chose que vous essayez de trouver votre "objectif". Dans ce cas, vous regardez la règle qui se termine par e₀ e₁. Lorsque vous avez trouvé cela, vous devez maintenant trouver des règles prouvant tout au-dessus de la ligne de cette règle. Ces choses correspondent généralement aux types de sous-expressions, donc vous êtes essentiellement récursif sur des parties de l'expression. Vous faites juste cela jusqu'à ce que vous finissiez votre arbre de preuve, ce qui vous donne une preuve du type de votre expression.

Toutes ces règles spécifient donc exactement - et dans le détail mathématiquement pédant habituel: P - comment comprendre les types d'expressions.

Maintenant, cela devrait vous sembler familier si vous avez déjà utilisé Prolog - vous devez essentiellement calculer l'arbre de preuve comme un interprète Prolog humain. Il y a une raison pour laquelle Prolog est appelé "programmation logique"! Ceci est également important car la première façon dont j'ai été introduit dans l'algorithme d'inférence H-M était de l'implémenter dans Prolog. C'est en fait étonnamment simple et rend ce qui se passe clairement. Vous devriez certainement l'essayer.

Note: J'ai probablement fait quelques erreurs dans cette explication et je l'adorerais si quelqu'un les signalait. Je vais couvrir ça en classe dans quelques semaines, donc je serai plus confiant alors: P.


301
2017-09-21 16:49



si quelqu'un pouvait au moins me dire où commencer à chercher à comprendre ce que signifie cette mer de symboles

Voir "Fondements pratiques des langages de programmation.", chapitres 2 et 3, sur le style de la logique à travers les jugements et les dérivations. maintenant disponible sur Amazon.

Chapitre 2

Définitions inductives

Les définitions inductives sont un outil indispensable dans l'étude des langages de programmation. Dans ce chapitre, nous développerons le cadre de base des définitions inductives et donnerons quelques exemples de leur utilisation. Une définition inductive consiste en un ensemble de règles pour dériver jugements, ou assertions, d'une variété de formes. Les jugements sont des déclarations concernant un ou plusieurs objets syntaxiques d'un tri spécifié. Les règles spécifient les conditions nécessaires et suffisantes pour la validité d'un jugement, et déterminent donc pleinement sa signification.

2.1 Jugements

Nous commençons avec la notion de jugement, ou affirmation à propos d'un objet syntaxique. Nous utiliserons de nombreuses formes de jugement, y compris des exemples tels que ceux-ci:

  • n  nat - n est un nombre naturel
  • n = n1 + n2 - n est la somme de n1 et n2
  • τ  type - τ est un type
  • e : τ - expression e a type τ
  • e ⇓ v - expression e a de la valeur v

Un jugement stipule qu'un ou plusieurs objets syntaxiques ont une propriété ou sont en relation les uns avec les autres. La propriété ou la relation elle-même est appelée formulaire de jugement, et le jugement qu'un objet ou des objets ont cette propriété ou se tiennent dans cette relation est dit être un exemple de cette forme de jugement. Un formulaire de jugement est également appelé prédicatet les objets constituant une instance sont ses sujets. Nous écrivons une  J pour le jugement affirmant que J prises de une. Quand il n'est pas important de souligner le sujet du jugement, (le texte est coupé ici)


69
2017-09-21 15:24



La notation vient de déduction naturelle.

Le symbole est appelé tourniquet.

Les 6 règles sont très faciles.

Var rule est une règle plutôt triviale - il dit que si type for identifier est déjà présent dans votre environnement de type, alors pour inférer le type, vous le prenez simplement dans l'environnement tel quel.

App règle dit que si vous avez deux identifiants e0 et e1 et peut déduire leurs types, alors vous pouvez en déduire le type d'application e0 e1. La règle se lit comme ceci si vous savez que e0 :: t0 -> t1 et e1 :: t0 (le même t0!), alors l'application est bien typée et le type est t1.

Abs et Let sont des règles pour inférer des types pour lambda-abstraction et let-in.

Inst règle dit que vous pouvez substituer un type moins général.


44
2017-09-21 16:21



Comment est-ce que je comprends les règles de Hindley-Milner?

Hindley-Milner est un ensemble de règles sous la forme de calcul séquentiel (non déduction naturelle) qui dit que vous pouvez déduire le type (le plus général) d'un programme de la construction du programme sans déclarations de type explicites.

Les symboles et la notation

D'abord, expliquons les symboles

  • 𝑥 est un identifiant (de manière informelle, un nom de variable).
  • : means est un type de (informellement, une instance de, ou "is-a").
  • σ (sigma) est une expression qui est soit une variable ou une fonction.
  • ∈ signifie est un élément de
  • Γ (Gamma) est un environnement.
  •  (le signe d'assertion) signifie affirme (ou prouve, mais contextuellement "affirme" lit mieux.)
  • Γ⊦ 𝑥  :  σ est donc lu Γ affirme 𝑥, un σ
  • 𝑒 est une occurrence réelle (élément) de type σ.
  • τ (tau) est un type: soit basique, variable (α), fonctionnel τ → τ 'ou produit τ × τ '
  • τ → τ ' est un type fonctionnel où τ et τ ' sont des types.
  • λ𝑥.𝑒 veux dire λ (lambda) est une fonction anonyme qui prend un argument, 𝑥et renvoie une expression, 𝑒.
  • laisser  𝑥  = 𝑒₀  dans  𝑒₁ signifie dans l'expression, 𝑒₁, substitut 𝑒₀ partout où 𝑥 apparaît.
  •  signifie que l'élément précédent est un sous-type (informellement - sous-classe) de ce dernier élément.
  • α est une variable de type.
  • α.σ est un type, ∀ (pour tous) les variables d'argument, α, retour σ expression
  • gratuit (Γ) signifie pas un élément des variables de type libre de Γ définies dans le contexte externe. (Les variables liées sont substituables.)

Tout ce qui est au-dessus de la ligne est la prémisse, tout ce qui est ci-dessous est la conclusion (Per Martin-Löf)

Ce qui suit ici sont des interprétations anglaises des énoncés logiques, suivies d'une explication.

Variable

VAR Logic Diagram

Étant donné que 𝑥 est un type de σ (sigma), un élément de Γ (Gamma),
conclure Γ affirme 𝑥 est un σ.

C'est fondamentalement une tautologie - un nom d'identifiant est une variable ou une fonction.

Application de fonction

APP Logic Diagram

Étant donné que Γ affirme 𝑒₀ est un type fonctionnel et Γ affirme 𝑒₁ est un τ
conclure Γ affirme appliquer la fonction 𝑒₀ à 𝑒₁ est un type τ '

Cela signifie que si nous savons qu'une fonction renvoie un type, et que nous l'appliquons à un argument, le résultat sera une instance du type que nous savons qu'elle renvoie.

Abstraction de fonction

ABS Logic Diagram

Étant donné que Γ et 𝑥 du type τ assert 𝑒 est un type, τ '
conclure Γ affirme une fonction anonyme, λ de 𝑥 expression de retour, 𝑒 est de type τ → τ '.

Cela signifie que si l'on sait que 𝑥 est de type τ et qu'une expression 𝑒 est de type τ ', alors une fonction de 𝑥 renvoyant l'expression 𝑒 est de type τ → τ'.

Laisser la déclaration variable

LET Logic Diagram

Étant donné Γ affirme 𝑒₀, de type σ, et Γ et 𝑥, de type σ, affirme 𝑒₁ de type τ
conclure Γ affirme let 𝑥 = 𝑒₀ in 𝑒₁ de type τ

Cela signifie que si nous avons une expression 𝑒₀ qui est un σ (étant une variable ou une fonction), et un nom, 𝑥, aussi un σ, et une expression 𝑒₁ de type τ, alors nous pouvons substituer 𝑒₀ pour 𝑥 partout où il apparaît de 𝑒₁.

Instanciation

INST Logic Diagram

Étant donné que Γ affirme 𝑒 de type σ 'et σ' est un sous-type de σ
conclure Γ affirme 𝑒 est de type σ

C'est dire que si une instance est d'un type qui est un sous-type d'un autre type, c'est aussi une instance de ce super-type.

Cela nous permet d'utiliser l'instanciation de type dans le sens plus général qu'une expression peut renvoyer un type plus spécifique.

Généralisation

GEN Logic Diagram

Étant donné que Γ affirme 𝑒 est un σ et α n'est pas un élément des variables libres de Γ,
conclure Γ affirme 𝑒, tape pour toutes les expressions d'arguments α retourne une expression σ

Cela signifie que nous pouvons généraliser un programme pour accepter tous les types d'arguments qui ne sont pas déjà liés dans la portée conteneur (variables qui ne sont pas non-locales). Ces variables liées sont substituables.

Conclusion

Ces règles combinées nous permettent de prouver le type le plus général d'un programme affirmé, sans nécessiter d'annotations de type, ce qui permet d'accepter correctement différents types d'entrées (polymorphisme paramétrique).


23
2018-02-03 23:01



Il y a deux façons de penser à e: σ. L'un est "l'expression e a le type σ", l'autre est "la paire ordonnée de l'expression e et le type σ".

Voir Γ comme la connaissance sur les types d'expressions, mis en œuvre comme un ensemble de paires d'expression et de type, e: σ.

Le tourniquet ⊢ signifie qu'à partir de la connaissance sur la gauche, on peut déduire ce qui est à droite.

La première règle [Var] peut donc être lue:
Si notre connaissance Γ contient la paire e: σ, alors nous pouvons déduire de Γ que e a le type σ.

La deuxième règle [App] peut être lue:
Si nous pouvons déduire que e_0 a le type τ → τ ', et que nous pouvons déduire que e_1 a le type τ, alors nous pouvons déduire que e_0 e_1 a le type τ'.

Il est courant d'écrire Γ, e: σ au lieu de Γ ∪ {e: σ}.

La troisième règle [Abs] peut donc être lue:
Si nous partons de Γ étendu avec x: τ peut déduire que e a le type τ ', alors nous pouvons déduire que λx.e a le type τ → τ'.

La quatrième règle [Let] est laissée en exercice. :-)

La cinquième règle [Inst] peut être lue:
Si nous pouvons déduire que e a le type σ ', et σ' est un sous-type de σ, alors nous pouvons déduire que e a le type σ.

La sixième et dernière règle [Gen] peut être lue:
Si nous pouvons déduire que e a le type σ, et que α n'est pas une variable de type libre dans l'un des types de Γ, alors nous pouvons en déduire que e a le type ∀α σ.


16
2018-04-25 14:55