Polymorphisme et génériques

Le polymorphisme permet à un seul morceau de code de fonctionner uniformément sur plusieurs types, avec le polymorphisme paramétrique (génériques), le polymorphisme ad hoc (surcharge et classes de types) et le polymorphisme de sous-typage comme formes principales.

Definition

Le polymorphisme est la propriété par laquelle une seule fonction, un seul type ou une seule opération peut s'appliquer à des valeurs de plus d'un type ; le polymorphisme paramétrique le fait uniformément via des paramètres de type (génériques), tandis que le polymorphisme ad hoc distribue vers des implémentations spécifiques au type.

Scope

Ce sujet couvre les principaux types de polymorphisme : le polymorphisme paramétrique réalisé par les génériques et le Système F, le polymorphisme ad hoc via la surcharge et les classes de types, et le polymorphisme d'inclusion (de sous-typage). Il aborde la paramétricité et les principes de raisonnement rigoureux qu'elle engendre, ainsi que la manière dont les abstractions génériques sont compilées et contraintes.

Core questions

• Comment les génériques permettent-ils la réutilisation sans sacrifier la sûreté des types ?
• Qu'est-ce que la paramétricité et quelles garanties offre-t-elle gratuitement ?
• Comment les classes de types systématisent-elles la surcharge ad hoc ?
• Comment les définitions génériques sont-elles compilées, et quelles contraintes peuvent lier les paramètres de type ?

Key theories

Paramétricité (théorème d'abstraction)

Le théorème d'abstraction de Reynolds montre que les fonctions polymorphes paramétriques se comportent uniformément à travers les types, une propriété qui contraint leur comportement possible indépendamment de l'instanciation de type concrète.

Théorèmes gratuits

Wadler a montré que le type d'une fonction polymorphe paramétrique implique à lui seul des théorèmes gratuits sur son comportement, une conséquence directe et pratique de la paramétricité.

Classes de types pour une surcharge structurée

Wadler et Blott ont introduit les classes de types, donnant au polymorphisme ad hoc une base théorique des types cohérente où les opérations surchargées sont résolues en passant des dictionnaires implicites d'implémentations de méthodes.

Clinical relevance

Les génériques et le polymorphisme sont essentiels à la conception de bibliothèques réutilisables et de frameworks de collections dans les langages modernes. Les classes de types et leurs analogues (traits, concepts, protocoles) offrent une surcharge structurée et sûre en termes de types, tandis que la paramétricité soutient le raisonnement sur la correction et les optimisations du compilateur.

History

Le Système F, qui capture le polymorphisme paramétrique, a été découvert indépendamment par Girard et Reynolds au début des années 1970. ML a mis en pratique le polymorphisme avec inférence. L'étude de Cardelli et Wegner de 1985 a classifié les formes de polymorphisme, Reynolds a formalisé la paramétricité en 1983, et les classes de types de Wadler et Blott de 1989 ont façonné la surcharge en Haskell et influencé les traits et concepts ailleurs.

Debates

Effacement contre génériques réifiés

Les implémenteurs de langages débattent de la compilation des génériques par effacement de type, ce qui est simple mais perd les informations de type à l'exécution, contre la réification des paramètres de type à l'exécution, ce qui permet l'introspection au prix d'une complexité et d'une taille de code accrues.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

Quelle est la différence entre le polymorphisme paramétrique et ad hoc ?

Le polymorphisme paramétrique applique une implémentation uniforme à tous les arguments de type (comme avec les génériques), tandis que le polymorphisme ad hoc sélectionne une implémentation spécifique au type, comme avec la surcharge ou les classes de types.

Que nous apporte la paramétricité ?

La paramétricité garantit qu'une fonction générique traite toutes les instances de type uniformément, ce qui produit des « théorèmes gratuits » sur son comportement, dérivables de sa seule signature de type.