Les types sont-ils effacés dans Haskell?

13

Haskell a une notion de «fonctions génériques» qui a une certaine similitude apparente avec le lisp commun - n'ayant aucune expérience avec Haskell ni avec le lisp commun, je pourrais être très approximatif ici. Cela signifie que l'on peut définir une fonction générique to_stringpour définir une représentation sous forme de chaîne pour tous les types. Bien sûr, la facilité doit être définie dans les cas particuliers mais il existe une to_stringfonction dont la signature est α → string.

Les types sont-ils effacés dans Haskell, comme dans OCaml? Si oui, en quoi l'implémentation des «fonctions génériques» dans Haskell diffère-t-elle de celle du lisp commun, où les types sont dynamiques, et donc pas effacés?

Je comprends que les détails de l'implémentation sont spécifiques au compilateur, mais il existe probablement des dispositions communes à de nombreuses ou à toutes les implémentations.

user40989
la source
5
N'oubliez pas que vous ne pouvez probablement pas définir une fonction de type non triviale a -> String. Vous auriez plus probablement une contrainte de type, comme Show a => a -> String.
DJG

Réponses:

16

Jusqu'à présent, la réponse est trompeuse.

Il faut faire une distinction entre le polymorphisme "paramétrique" et "surcharge ad-hoc". Paramétrique signifie "se comporte uniformément pour tous les types a", tandis que "ad-hoc" - ce que Simon appelle polymorphe - modifie l'implémentation en fonction du type.

Des exemples des deux sont reverse :: [a] -> [a], qui est paramétrique et show :: Show a => a -> Stringqui est "ad-hoc" surchargé.

Si vous voulez plus d'une intuition abstraite, je pense que cela aide à considérer les classes de verbes en langage naturel qui "fonctionnent" pour tous les objets, comme "posséder" ou "penser" qui ne posent aucune contrainte à l'objet, mais " ouvrir "nécessite que ce dont nous parlons puisse être ouvert. Je peux «penser à une porte» et «ouvrir une porte», alors que cela n'a aucun sens, par exemple, «ouvrir un arbre». Pousser encore plus loin l'exemple «ouvrir» est «polymorphe ad hoc» car «ouvrir une fenêtre» et «ouvrir un ticket de réclamation auprès du service client» sont deux choses très différentes. Si cela semble forcé - oubliez-le! Ça marche pour moi.

Les deux sont cependant résolus au moment de la compilation et en fait "effacés". Modulo diverses extensions GHC et Template Haskell, etc. Les types sont en fait effacés au moment de la compilation et ne sont jamais inspectés au moment de l'exécution.

Les fonctions paramétriques polymorphes se comportent de manière identique pour tous les types, donc un seul morceau de code doit être généré, tandis que le compilateur décide au moment de la compilation quelle version d'une fonction "classée par type" doit être exécutée à un point de programme particulier. C'est aussi pourquoi la restriction d'une instance par type par classe de type et la solution de contournement "newtype" correspondante existent.

L'implémentation est détaillée dans le manuel SPJ et dans le document Wadler et Blotts sur les classes de types .

Kris
la source
Pensez-vous que je devrais supprimer ma réponse?
Simon Bergot
Non, ça va avec votre avertissement de ne pas frapper le vocabulaire exact :)
Kris
Pourriez-vous développer un peu pourquoi il est possible pour GHC d'effacer les types? Est-ce grâce au typage principal?
Simon Bergot
2
En général, au moment de l'exécution, les fonctions polymorphes paramétriques peuvent exister une seule fois et appeler les fonctions polymorphes ad hoc via une méthode d'envoi virtuel ou tout le code peut être généré pour chaque type séparément et les appels sont liés statiquement. L'une ou l'autre implémentation est correcte du point de vue du langage (notez que Haskell n'a pas de types polymorphes; une telle chose ne peut être créée qu'avec l' forallextension GHC ).
Jan Hudec
Existe-t-il une extension GHC qui ne permet pas d'effacer les types? La surcharge est statique et sans types entièrement dépendants, je ne pense à rien
Daniel Gratzer
1

avertissement: mes antécédents dans CS ne sont pas très solides, donc je ne pourrais pas toujours utiliser le vocabulaire correct, et je peux me tromper sur certains points. Quoi qu'il en soit, voici ma compréhension:

Je pense que vous confondez les génériques avec le polymorphisme.

Les types génériques tels que List<Foo>sont utilisés pour décrire les types qui prennent d'autres types en paramètre et permettent une vérification de type plus riche.

Une fonction générique dans haskell pourrait être count:: List a -> Int. Il accepte des listes de tout type et renvoie le nombre d'éléments. Il n'y a qu'une seule implémentation.

Habituellement, lors de la définition de List, vous ne pouvez rien supposer de T. Vous pouvez seulement le stocker et le rendre.

Votre to_stringfonction est une fonction polymorphe, ce qui signifie qu'elle se comportera différemment selon les circonstances. Dans haskell, cela se fait avec des classes de types, qui fonctionnent comme des adjectifs pour les types.

Vous avez une Showclasse de types, qui définit une show :: a -> Stringfonction.

Lorsqu'un type Fooimplémente la Showclasse de types, il doit fournir la définition de show. Ce type peut ensuite être utilisé dans des fonctions nécessitant le Showqualificatif (comme dans Show a => a -> whatever). Haskell ne peut pas effacer les types, car ces fonctions doivent trouver l'implémentation correcte de la showfonction.

Simon Bergot
la source
Dans le langage courant, les fonctions polymorphes sont appelées «fonctions génériques» IIRC et j'ai utilisé le même vocabulaire (déroutant). Votre réponse est utile et votre argument final assez convaincant. .-)
user40989
«Il n'y a qu'une seule implémentation» - une seule qui a du sens, bien sûr, mais il y en a infiniment de possibles. Une fonction de type a → b a | b | ^ | a | implémentations possibles (considérez le nombre de fonctions de type Bool → Bool), et les listes n'ont pas de limite de taille supérieure.
Jon Purdy