L'inférence Hindley-Milner pourrait-elle fonctionner pour la langue Go?

22

J'ai lu que Hindley-Milner ne fonctionne pas avec les systèmes de types qui ont des sous-classes, et il existe d'autres fonctionnalités de système de types qui ne fonctionnent pas bien avec. Go n'a actuellement qu'une inférence de type très limitée dans l' :=opérateur. Mais Go n'a pas de sous-classes au sens traditionnel, seulement des interfaces qui ressemblent beaucoup aux classes de types de Haskell qui fonctionnent bien avec l'inférence Hindley-Milner.

Ainsi, l'inférence Hindley-Milner pourrait-elle fonctionner en principe pour Go de la même manière que pour Haskell? Ou Go a-t-il d'autres fonctionnalités qui le cassent? (D'un autre côté, Haskell possède également certaines fonctionnalités qui ne fonctionnent pas avec Hindly-Milner, si vous utilisez celles que vous devez saisir manuellement ces parties de votre programme.)

JanKanis
la source

Réponses:

35

L'inférence de type Hindley-Milner est utilisée pour les systèmes de type Hindley-Milner, une restriction des systèmes de type System-F. La caractéristique intéressante des systèmes de type HM est qu'ils ont un polymorphisme paramétrique (alias génériques). C'est la plus grande fonctionnalité de système de type que Golang refuse d'avoir.

Avec cette restriction frustrante, l'inférence de type HM est impossible. Regardons le code non typé:

func f(a) {
  return a.method()
}

Quel est le type de f? On peut remarquer que adoit avoir une méthode, afin que nous puissions utiliser une interface anonyme: func f(a interface { method() ??? }) ???. Cependant, nous n'avons aucune idée du type de retour. Avec les variables de type, nous pourrions déclarer le type comme

func f[T](a interface{ method() T }) T

Cependant, Go n'a pas de variables de type, donc cela ne fonctionnera pas. Alors que les interfaces implicites facilitent certains aspects de l'inférence de type, nous n'avons désormais aucun moyen de trouver le type de retour d'un appel de fonction. Le système HM exige que toutes les fonctions soient déclarées plutôt qu'impliquées, et chaque nom ne peut avoir qu'un seul type (alors que les méthodes de Go peuvent avoir différents types dans différentes interfaces).

Au lieu de cela, Go requiert que les fonctions soient toujours entièrement déclarées, mais autorise les variables à utiliser l'inférence de type. Cela est possible car le côté droit d'une affectation a variable := expressiondéjà un type connu à ce point du programme. Ce type d'inférence de type est simple, correct et linéaire.

  • Le type d'une variable est immédiatement connu au moment de la déclaration, tandis que l'inférence HM doit potentiellement d'abord vérifier le type de tout le programme. Cela a également un impact notable sur la qualité des messages d'erreur.
  • L'approche d'inférence de type de Go sélectionnera toujours le type le plus spécifique pour une variable, contrairement à HM qui choisit le type le plus général. Cela fonctionne proprement avec le sous-typage, même avec les interfaces implicites de Go.
amon
la source
24
@bishop C'est "raisonné" pour des valeurs infiniment petites de "raison".
hobbs
18
@bishop Après avoir fait du compilateur dans des langages avec des génériques, je peux certainement être d'accord: c'est difficile à implémenter sans compliquer considérablement l'implémentation. J'irais même jusqu'à remplacer "difficile" par "impossible". Cependant, ce n'est pas le point; le point est, vaut-il la complication supplémentaire? Et la réponse, à toute personne qui a travaillé avec et sans génériques, est évidemment "oui, définitivement!" Je serais tout à fait d'accord avec l'affirmation selon laquelle refuser de mettre en œuvre des génériques parce que "oh non, la complexité" est idiot.
Mason Wheeler
18
C'est aussi pourquoi les développeurs de Go prétendent que la FP de toutes sortes est mauvaise; Go a des fonctions de première classe avec fermeture lexical, et que la capacité de créer des fonctions d'ordre supérieur, mais il est impossible de les mettre à un bon usage , car les types de ces fonctions de base comme map, filteret reducesont tous inexprimable dans les Go très limité système de type.
hobbs
9
@hobbs And Go pourrait être un langage vraiment sympa si cela était corrigé, mais à la place, les gens doivent écrire des bibliothèques de génération générique comme gengenetgonerics
cat
14
@cat C'est dommage. Au début, Go semble être un grand langage plein de bonnes idées, mais ensuite vous vous rendez compte qu'il n'a pas d'héritage et de polymorphisme, donc vous ne pouvez pas bien faire la POO, et il n'a pas de génériques, donc vous ne pouvez pas bien faire la FP, et vous 'reste à regarder fixement l'écran en demandant "alors comment êtes-vous censé utiliser exactement cette langue?!?"
Mason Wheeler