Classes de types et surcharge

Il existe une dernière caractéristique du système de types de Haskell le distinguant des autres langages de programmation. Le type de polymorphisme dont nous avons parlé jusqu'à présent est communément appelé polymorphisme paramétrique. Il existe un autre type appelé polymorphisme ad hoc, plus connu sous le nom de surcharge. Voici quelques exemples de polymorphisme ad hoc :

• Les littéraux 1, 2,... sont souvent utilisés pour représenter des entiers à précision fixe et arbitraire.
• Les opérateurs numériques tels que + sont souvent définis pour fonctionner sur de nombreux types de nombres différents.
• L'opérateur d'égalité (== en Haskell) fonctionne généralement sur des nombres et sur de nombreux autres types (mais pas tous).

Notez que ces comportements surchargés sont différents pour chaque type (en fait, le comportement est parfois indéfini ou erroné), alors que dans le polymorphisme paramétrique, le type n'a vraiment pas d'importance (fringe, par exemple, ne se soucie pas vraiment du type d'éléments trouvés dans les feuilles d'un arbre). En Haskell, les classes de types fournissent un moyen structuré de contrôler le polymorphisme ad hoc, ou surcharge.

Commençons par un exemple simple, mais important : l'égalité. Il existe de nombreux types pour lesquels nous aimerions définir l'égalité, mais certains pour lesquels nous ne le ferions pas. Par exemple, la comparaison de l'égalité des fonctions est généralement considérée comme intraitable sur le plan informatique, alors que nous voulons souvent comparer deux listes pour l'égalité. (Le type d'égalité auquel nous faisons référence ici est «l'égalité des valeurs», et s'oppose à «l'égalité des pointeurs» trouvée, par exemple, avec == de Java. L'égalité des pointeurs n'est pas transparente sur le plan référentiel et ne convient donc pas à un langage purement fonctionnel.) Pour mettre en évidence le problème, considérons cette définition de la fonction elem testant l'appartenance à une liste :

[Pour la raison stylistique que nous avons discutée dans la section, nous avons choisi de définir elem sous forme infixe. == et || sont les opérateurs infixes pour l'égalité et le ou logique, respectivement.]

Intuitivement parlant, le type d'elem "devrait" être : a->[a]->Bool. Mais cela impliquerait que == a le type a->a->Bool, même si nous venons de dire que nous ne nous attendons pas à ce que == soit défini pour tous les types.

De plus, comme nous l'avons noté précédemment, même si == était défini sur tous les types, comparer deux listes pour l'égalité est très différent de comparer deux entiers. En ce sens, nous nous attendons à ce que == soit surchargé pour effectuer ces diverses tâches.

Les classes de types résolvent facilement ces deux problèmes. Elles nous permettent de déclarer quels types sont des instances de quelle classe, et de fournir des définitions des opérations surchargées associées à une classe. Par exemple, définissons une classe de types contenant un opérateur d'égalité :

Ici, Eq est le nom de la classe définie et == est l'opération unique de la classe. Cette déclaration peut être lue comme suit : «un type a est une instance de la classe Eq s'il existe une opération (surchargée) ==, du type approprié, définie sur elle». (Notez que == n'est défini que sur des paires d'objets du même type.)

La contrainte selon laquelle un type a doit être une instance de la classe Eq s'écrit Eq a. Ainsi, Eq a n'est pas une expression de type, mais exprime plutôt une contrainte sur un type et est appelé un contexte. Les contextes sont placés au début des expressions de type. Par exemple, l'effet de la déclaration de classe ci-dessus est d'assigner le type suivant à == :

Cela devrait se lire ainsi : «Pour chaque type a étant une instance de la classe Eq, == a le type a->a->Bool». C'est le type étant utilisé pour == dans l'exemple elem, et en effet la contrainte imposée par le contexte se propage au type principal pour elem :

Cela se lit comme suit : «Pour chaque type a qui est une instance de la classe Eq, elem a le type a->[a]->Bool». C'est exactement ce que nous voulons : cela exprime le fait que elem n'est pas défini sur tous les types, seulement sur ceux pour lesquels nous savons comparer les éléments pour l'égalité.

Jusqu'ici tout va bien. Mais comment spécifier quels types sont des instances de la classe Eq, et le comportement réel de == sur chacun de ces types ? Cela se fait avec une déclaration d'instance. Par exemple :

La définition de == est appelée une méthode. La fonction integerEq se trouve être la fonction primitive comparant les entiers pour l'égalité, mais en général, toute expression valide est autorisée sur le côté droit, comme pour toute autre définition de fonction. La déclaration globale dit essentiellement : «Le type Integer est une instance de la classe Eq, et voici la définition de la méthode correspondant à l'opération ==.» Étant donné cette déclaration, nous pouvons maintenant comparer des entiers à précision fixe pour l'égalité en utilisant ==. De même :

permet de comparer des nombres à virgule flottante en utilisant ==.

Les types récursifs tels que Tree définis précédemment peuvent également être gérés :

Notez le contexte Eq a dans la première ligne --- cela est nécessaire car les éléments dans les feuilles (de type a) sont comparés pour l'égalité dans la deuxième ligne. La contrainte supplémentaire dit essentiellement que nous pouvons comparer les arbres de a pour l'égalité tant que nous savons comment comparer les a pour l'égalité. Si le contexte était omis de la déclaration d'instance, une erreur de type statique en résulterait.

Le rapport Haskell, en particulier le prélude, contient une multitude d'exemples utiles de classes de types. En effet, une classe Eq est définie qui est légèrement plus grande que celle définie précédemment :

Ceci est un exemple d'une classe avec deux opérations, l'une pour l'égalité, l'autre pour l'inégalité. Il montre également l'utilisation d'une méthode par défaut, dans ce cas pour l'opération d'inégalité /=. Si une méthode pour une opération particulière est omise dans une déclaration d'instance, alors la méthode par défaut définie dans la déclaration de classe, si elle existe, est utilisée à la place. Par exemple, les trois instances de Eq définies précédemment fonctionneront parfaitement avec la déclaration de classe ci-dessus, produisant exactement la bonne définition de l'inégalité que nous voulons : la négation logique de l'égalité.

Haskell prend également en charge une notion d'extension de classe. Par exemple, nous pouvons souhaiter définir une classe Ord héritant de toutes les opérations de Eq, mais possédant en plus un ensemble d'opérations de comparaison et de fonctions minimum et maximum :

Notez le contexte dans la déclaration de classe. Nous disons que Eq est une super-classe de Ord (inversement, Ord est une sous-classe de Eq), et tout type étant une instance de Ord doit également être une instance de Eq. (Dans la section suivante, nous donnons une définition plus complète de Ord tirée du Prelude.)

L'un des avantages de telles inclusions de classe est la réduction des contextes : une expression de type pour une fonction utilisant des opérations des classes Eq et Ord peut utiliser le contexte (Ord a), plutôt que (Eq a, Ord a), car Ord «implique» Eq. Plus important encore, les méthodes pour les opérations de sous-classe peuvent supposer l'existence de méthodes pour les opérations de super-classe. Par exemple, la déclaration Ord dans le Prélude Standard contient cette méthode par défaut pour (<) :

À titre d'exemple d'utilisation de Ord, le typage principal de quicksort défini dans la page Classes de types et surcharge est :

En d'autres termes, quicksort ne fonctionne que sur des listes de valeurs de types ordonnés. Ce typage pour quicksort est dû à l'utilisation des opérateurs de comparaison < et >= dans sa définition.

Haskell permet également l'héritage multiple, puisque les classes peuvent avoir plus d'une superclasse. Par exemple, la déclaration :

crée une classe C héritant des opérations de Eq et Show.

Les méthodes de classe sont traitées comme des déclarations de niveau supérieur dans Haskell. Elles partagent le même espace de noms que les variables ordinaires ; un nom ne peut pas être utilisé pour désigner à la fois une méthode de classe et une variable ou des méthodes de classes différentes.

Les contextes sont également autorisés dans les déclarations de données.

Les méthodes de classe peuvent avoir des contraintes de classe supplémentaires sur toute variable de type, à l'exception de celle définissant la classe actuelle. Par exemple, dans cette classe :

la méthode m requiert que le type b soit dans la classe Show. Cependant, la méthode m ne pouvait pas placer de contraintes de classe supplémentaires sur le type a. Celles-ci devraient plutôt faire partie du contexte dans la déclaration de classe.

Jusqu'à présent, nous avons utilisé des types de «premier ordre». Par exemple, le constructeur de type Tree a jusqu'à présent toujours été associé à un paramètre, comme dans Tree Integer (un arbre contenant des valeurs Integer) ou Tree a (représentant la famille d'arbres contenant des valeurs a). Mais Tree en soi est un constructeur de type, et en tant que tel prend un type comme paramètre et renvoie un type comme résultat. Il n'y a pas de valeurs dans Haskell ayant ce type, mais de tels types «d'ordre supérieur» peuvent être utilisés dans les déclarations de classe.

Pour commencer, considérons la classe Functor suivante (extraite du Prélude) :

La fonction fmap généralise la fonction map utilisée précédemment. Notez que la variable de type f est appliquée à d'autres types dans f a et f b. Ainsi, nous nous attendrions à ce qu'elle soit liée à un type tel que Tree pouvant être appliqué à un paramètre. Une instance de Functor pour le type Tree serait :

Cette déclaration d'instance déclare que Tree, plutôt que Tree a, est une instance de Functor. Cette capacité est très utile et démontre ici la capacité à décrire des types de «conteneurs» génériques, permettant à des fonctions telles que fmap de fonctionner uniformément sur des arbres, des listes et d'autres types de données arbitraires.

[Les applications de type sont écrites de la même manière que les applications de fonction. Le type T a b est analysé comme (T a) b. Les types tels que les tuples utilisant une syntaxe spéciale peuvent être écrits dans un style alternatif permettant le curry. Pour les fonctions, (->) est un constructeur de type; les types f -> g et (->) f g sont les mêmes. De même, les types [a] et [] a sont les mêmes. Pour les tuples, les constructeurs de type (ainsi que les constructeurs de données) sont (,), (,,),...]

Comme nous le savons, le système de types détecte les erreurs de frappe dans les expressions. Mais qu'en est-il des erreurs dues aux expressions de type mal formées ? L'expression (+) 1 2 3 génère une erreur de type puisque (+) ne prend que deux paramètres. De même, le type Tree Int Int devrait produire une sorte d'erreur puisque le type Tree ne prend qu'un seul argument. Alors, comment Haskell détecte-t-il les expressions de type mal formées ? La réponse est un deuxième système de types garantissant l'exactitude des types ! Chaque type a un genre associé qui garantit que le type est utilisé correctement.

Les expressions de type sont classées en différents genres qui prennent l'une des deux formes possibles :

• Le symbole * représente le genre de type associé aux objets de données concrets. Autrement dit, si la valeur v est de type t, le genre de v doit être *.
• Si k1 et k2 sont des genres, alors k1->k2 est le genre de types qui prennent un type de genre k1 et renvoient un type de genre k2.

Le constructeur de type Tree est de genre *->* ; le type Tree Int est de genre *. Les membres de la classe Functor doivent tous être de genre *->* ; une erreur de genre résulterait d'une déclaration telle que :

puisque Integer a le genre *.

Les genres n'apparaissent pas directement dans les programmes Haskell. Le compilateur déduit les genres avant de procéder à la vérification de type sans avoir besoin de «déclarations de genre». Les genres restent en arrière-plan d'un programme Haskell sauf lorsqu'une signature de type erronée conduit à une erreur de genre. Les genres sont suffisamment simples pour que les compilateurs soient capables de fournir des messages d'erreur descriptifs lorsque des conflits de genre se produisent.

Une perspective différente.

Avant de passer à d'autres exemples d'utilisation des classes de types, il convient de souligner deux autres points de vue sur les classes de types de Haskell. Le premier est par analogie avec la programmation orientée objet (POO). Dans l'énoncé général suivant sur la programmation orientée objet, le simple remplacement de classe par type et de type par objet donne un résumé valide du mécanisme de classe de type de Haskell :

«Les classes capturent des ensembles communs d'opérations. Un objet particulier peut être une instance d'une classe et aura une méthode correspondant à chaque opération. Les classes peuvent être organisées de manière hiérarchique, formant des notions de superclasses et de sous-classes et permettant l'héritage d'opérations/méthodes. Une méthode par défaut peut également être associée à une opération.»

Contrairement à la programmation orientée objet, il doit être clair que les types ne sont pas des objets et, en particulier, il n'existe aucune notion d'état mutable interne d'un objet ou d'un type. Un avantage par rapport à certains langages de programmation orientée objet est que les méthodes de Haskell sont totalement sûres en termes de type : toute tentative d'appliquer une méthode à une valeur dont le type n'est pas dans la classe requise sera détectée au moment de la compilation plutôt qu'au moment de l'exécution. En d'autres termes, les méthodes ne sont pas «recherchées» au moment de l'exécution mais sont simplement transmises en tant que fonctions d'ordre supérieur.

Une perspective différente peut être obtenue en considérant la relation entre le polymorphisme paramétrique et le polymorphisme ad hoc. Nous avons montré comment le polymorphisme paramétrique est utile pour définir des familles de types en quantifiant universellement tous les types. Parfois, cependant, cette quantification universelle est trop large : nous souhaitons quantifier sur un ensemble plus petit de types, tels que les types dont les éléments peuvent être comparés pour l'égalité. Les classes de types peuvent être considérées comme fournissant un moyen structuré de faire exactement cela. En fait, nous pouvons aussi considérer le polymorphisme paramétrique comme une sorte de surcharge ! C'est juste que la surcharge se produit implicitement sur tous les types au lieu d'un ensemble contraint de types (c'est-à-dire une classe de types).

Comparaison avec d'autres langages.

Les classes utilisées par Haskell sont similaires à celles utilisées dans d'autres langages orientés objet tels que C++ et Java. Cependant, il existe quelques différences significatives :

• Haskell sépare la définition d'un type de la définition des méthodes associées à ce type. Une classe en C++ ou Java définit généralement à la fois une structure de données (les variables membres) et les fonctions associées à la structure (les méthodes). En Haskell, ces définitions sont séparées.
• Les méthodes de classe définies par une classe Haskell correspondent aux fonctions virtuelles d'une classe C++. Chaque instance d'une classe fournit sa propre définition pour chaque méthode ; les valeurs par défaut de la classe correspondent aux définitions par défaut d'une fonction virtuelle dans la classe de base.
• Les classes Haskell sont à peu près similaires à une interface Java. Comme une déclaration d'interface, une déclaration de classe Haskell définit un protocole pour l'utilisation d'un objet plutôt que de définir un objet lui-même.
• Haskell ne prend pas en charge le style de surcharge C++ dans lequel les fonctions de types différents partagent un nom commun.
• Le type d'un objet Haskell ne peut pas être implicitement contraint ; il n'existe pas de classe de base universelle telle que Object dans laquelle des valeurs peuvent être projetées ou hors de celle-ci.
• C++ et Java attachent des informations d'identification (comme une VTable) à la représentation d'exécution d'un objet. En Haskell, ces informations sont attachées logiquement plutôt que physiquement aux valeurs, via le système de types.
• Il n'existe aucun contrôle d'accès (comme des composants de classe publics ou privés) intégré au système de classes Haskell. Au lieu de cela, le système de modules doit être utilisé pour masquer ou révéler les composants d'une classe.