Approche algébrique du typage d’un langage à la ML avec objets

La plupart des langages de programmation modernes définissent une notion de typage : l’association d’un type à chaque donnée manipulée par le programme permet de vérifier si une opération est bien définie sur les données auxquelles elle est appliquée. On évite ainsi toute une classe d’erreurs de programmation, comme par exemple l’addition d’une chaîne de caractères à un entier, ou bien la concaténation deux entiers. Ces opérations incorrectes peuvent compromettre des propriétés essentielles attendues du programme : correction, portabilité, stabilité ou sécurité. Le typage contribue donc à améliorer la qualité du logiciel.

Le typage est dit statique quand il est réalisé avant même l’exécution du programme, lors de la compilation, de l’édition de lien ou bien lors de l’activation du programme. Quand le typage est statique, les erreurs peuvent être détectées indépendamment du chemin d’exécution effectivement emprunté par le programme, ce qui offre un niveau de sûreté supérieur au typage dynamique. Cela permet aussi de réaliser des gains de performance en temps et en espace par rapport au typage dynamique où l’exécution de chaque opération doit vérifier le type des arguments et où la représentation en mémoire de chaque objet manipulé doit transporter une information de type.

En contrepartie de ces avantages, le typage statique est généralement complexe à mettre en œuvre : il faut en effet procéder à une analyse abstraite du programme suivant un ensemble de règles logiques appelé système de types qui aboutit à accepter ou rejeter un programme. L’une des propriétés essentielles d’un système de types est sa correction : aucun programme ne doit être accepté s’il peut mener à une opération invalide, c’est-à-dire non définie. Cependant, les contraintes d’implémentation (décidabilité, performances) amènent souvent à rejeter des programmes en fait corrects, mais trop complexes pour être analysés comme tel. Cette limitation conduit à rechercher des système de types toujours plus expressifs, c’est-à-dire qui rejettent de moins en moins de programmes qu’on juge utile de pouvoir exprimer.

Dans cette recherche d’expressivité, le polymorphisme paramétrique [Str67, Str00, Hin69, Mil78] a marqué une étape importante en autorisant l’écriture de fonctions génériques opérant sur des données de différents types. Une fonction polymorphe peut ainsi manipuler certaines données comme des boîtes noires seulement susceptibles d’être transférées d’une structure de données à une autre (tuple, liste, arbre) ou bien d’être passées en argument à d’autres fonctions. On peut alors donner à une telle fonction un schéma de types incluant des paramètres, chaque paramètres pouvant varier indépendamment dans l’ensemble de tous les types possibles. Par exemple, un algorithme de tri, écrit une fois pour toute, peut s’appliquer à une liste de n’importe quel type pourvu qu’une fonction de comparaison soit fournie. Le polymorphisme paramétrique s’adapte ainsi particulièrement bien aux langages où les fonctions sont des données comme les autres, c’est-à-dire les langages applicatifs d’ordre supérieur, notamment de la famille de ML.

Il existe cependant d’autres formes de polymorphisme. Le polymorphisme dit « ad hoc » permet à une même fonction d’être définie sur plusieurs types tout en ayant un comportement différent sur chaque type. Un exemple typique concerne les opérateurs arithmétiques. Selon la nature des opérandes (entiers, flottants), l’opérateur d’addition par exemple s’exécute ainsi :si ses deux arguments sont deux entiers, on calcule l’addition entière ; pour deux flottants, on calcule l’addition flottante ; enfin, si l’un des argument est entier et l’autre flottant, on doit convertir l’argument entier en flottant puis retourner la somme flottante avec l’autre argument.

Un autre genre de polymorphisme est présent dans les langages de programmation centrés sur la notion d’« objet », comme C++ [Str91], Eiffel [Mey92] ou Java [GJSB00]. Dans la tradition impérative de ces langages, on considère qu’un objet est une sorte d’automate, doté d’un état interne (les « champs ») et de fonctions de transition modifiant cet état (les « méthodes »). Un objet est construit sur le modèle d’une « classe » spécifiant le nom des champs et le corps des méthodes. L’une des grandes forces des langages à objets est qu’ils permettent aux classes d’être définies par héritage, c’est-à-dire en étendant d’autres classes écrites précédemment et en en redéfinissant certaines de leurs méthodes. On peut ainsi écrire du code générique qui manipule des objets sans connaître leur type précis, mais en sachant qu’ils dérivent d’une classe donnée et savent répondre aux méthodes de cette classe. Cette forme de polymorphisme est particulièrement utile dans les systèmes logiciels construits incrémentalement à partir d’un noyau générique et soumis à des changements fréquents. On pense par exemple aux interfaces graphiques où les différents objets graphiques (menus, fenêtres, boutons, etc.) peuvent tous dériver d’une classe de base définissant un petit nombre de méthodes (retourner la taille, se réafficher sur une portion de l’écran, etc.), ce qui permet de coder une fois pour toute la gestion de l’affichage tout en autorisant l’ajout ultérieur d’objets graphiques variés. Plus généralement, l’expérience montre que tout gros système logiciel subit nécessairement des changements constants et qu’il est important de pouvoir s’appuyer sur des classes génériques et réutilisables, ce qui explique que les objets se sont imposés comme un outil incontournable de génie logiciel.

Pour refléter les polymorphismes ad-hoc et d’héritage, un système de types statique doit disposer d’une notion de sous-typage. Partout où un objet d’un certain type est attendu, on autorise ainsi la substitution par un objet d’un sous-type. Comparés au typage des langages comme ML, les systèmes de types des langages à objets sont généralement assez frustres (pas d’inférence, ordre 1). Parfois, ils ne sont même pas corrects et supposent que des vérifications dynamiques ont lieu à l’exécution. Mais ils intègrent tous cette notion de sous-typage.

Combiner à la fois les polymorphismes paramétriques et ad-hoc, le sous-typage, les objets et les fonctions dans un même système supérieurement expressif a motivé de nombreux travaux de recherche [Mit84, FM88, FM89, AC93, Rém94, Pot98]. La plupart de ces travaux étudient les objets en les codant sous la forme d’enregistrements extensibles, les méthodes étant contenues dans ces enregistrements sous la forme de fonction ordinaires prenant en argument l’objet lui même. Les systèmes de types résultant présentent souvent une grande complexité technique (types récursifs ou d’ordre supérieur, contraintes de sous-typage, etc.). De plus, il ne parviennent qu’imparfaitement à traiter un problème parfois très important : les méthodes binaires [BCC+95].