Résumé
Le probléme du parcours de graphe d'objets est omniprésent dans l'algorithmique des langages orienté-objets qu'ils soient dynamiquement ou statiquement typés : étant donné un graphe d'objets de différents types, comment parcourir ce graphe et appliquer un traitement à chaque noeud qui dépende du type de l'objet constituant ce noeud, et ce d'une manière qui soit efficace, simple et ouverte ?
Nous proposons dans cet article une solution inspirée d'une approche de ce même problème pour le langage fonctionnel Haskell. Cette approche s'appuie sur deux techniques : une version simplifiée et efficace de polymorphisme paramétrique et des multi-méthodes ; la construction d'itérateurs spécifique à chaque type parcouru. Ces deux techniques sont ensuite utilisées sous la formes de combinateurs extensibles permettant de personnaliser simplement les actions et les stratégies de parcours d'un graphe d'objet. L'exposition s'appuie sur une implantation en langage Java de ces techniques et exemples d'applications significatifs.
Nous démontrons l'intérêt de notre approche en la comparant à d'autres solutions plus classiques selon plusieurs critères: simplicité, efficacité, expressivité, ouverture. Par ailleurs, nous ouvrons des perspectives plus larges en argumentant pour la prise en compte dans le domaine des langages et technologies objets des avancées récentes dans les langages fonctionnels.
Introduction
Problème
Les instances d'objets manipulés par un programme écrit dans un langage orienté-objet forment évidemment un graphe dirigé dont les sommets sont les objets eux-mêmes et les arcs les références entre objets stockées dans leurs champs ou attributs. Ce graphe est par ailleurs étiqueté : tous les arcs ont une étiquette qui l'identifiant utilisé dans la source pour se référer à la cible ; et typé : chaque objet posséde un type, un type pouvant être attribué à plusieurs objets simultanément.
Cette structure, le plus souvent dans l'ombre du point de vue du programmeur, apparaît explicitement lorsque l'on souhaite réaliser des opérations qui agissent sur un ensemble d'objets structurellement reliés entre eux: transformations de la structure elle-même, transformation vers une autre structure, extraction d'une partie de la structure (requêtes). Un exemple classique est celui de l'évaluation d'expressions ou de la compilation d'un arbre syntaxique abstrait issu d'une analyse syntaxique: la sémantique du langage considéré définit pour chaque objet, en fonction de son contexte (parent) et de sa structure (enfants) le résultat de cette évaluation ou compilation. Un autre exemple est celui du filtrage d'objets dans une structure par application d'une contrainte, permettant de récupérer un ensemble d'objets selon certains critères. Un dernier exemple d'application concerne le refactoring de structures d'objets, par exemple de modèles dans le cadre d'outils de transformation de modèles.
Un problème supplémentaire des langages orienté-objets et plus généralement des systèmes ouverts est celui de la prise en compte des modifications et extensions. Celles-ci peuvent être réalisées par le mécanisme d'héritage usuel en conservant une relation entre les types, ou par composition sans relation entre les types. Une exemple de ce problème (et une des motivations originelles de notre contribution) est celui du partage et de l'enrichissement d'information dans les applications utilisant intensivement des techniques de greffons (eg. le mécanisme de génération de rapports de l'outil de construction maven). La collecte et le partage d'informations entre différents greffons qui ne se connaissent pas impose de relâcher les contraintes de typage statique et/ou d'utiliser des solutions génériques externes, par exemple des graphes RDF ou des fichiers XML.
La réalisation de ces opérations entraîne la prolifération de ce qu'il est convenu d'appeler du boilerplate code pour parcourir le graphe d'objets : du code nécessaire mais répétitif, fastidieux à écrire, source d'erreurs et de problèmes difficiles à identifier. Du point de vue du programmeur qui définit une opération de transformation ou de requête sur un telle graphe, il serait souhaitable de :
- se contenter de définir le code de traitement propre à chacun des types d'objets :
- pouvoir guider le parcours dans le graphe lorsque celui-ci est complexe ;
- éviter des opérations de transtypages ou la manipulation de types trop génériques et abstraits ;
- limiter l'extraction coûteuse d'informations de types dynamiques (RTTI) ;
- ne pas devoir apprendre un nouveau langage et modifier sa plateforme de développement.
Solutions existantes
Le patron de conceptionVisiteur (Design Patterns) constitue la solution la plus classique et la plus utilisée au problème très général du parcours typé de graphes d'objets. Cette solution a pourtant un certain nombre de défauts bien connus (The Essence of the Visitor Pattern) depuis longtemps: elle est verbeuse et produit du code lourd et peu évolutif. Le Visiteur est en fait une solution ad hoc des langages statiquement typés et un cas particulier de la technique du double aiguillage (double dispatching). Dans l'article cité, l'auteur propose de remplacer le Visiteur par un Baladeur (Walkabout) utilisant les mécanismes de réflexion du langage Java pour sélectionner les actions à réaliser sur les objets parcourus. Cette solution présente l'inconvénient d'un recours massif à l`API de réflexion, notoirement inefficace.
Le patron de conception Chaîne de responsabilité est une variante simple sur le thème des patrons, mais qui présente l'inconvénient d'être inefficace : le traitement a réaliser sur un objet est délégué d'objet en objet jusqu'à ce qu'un responsable soit trouvé. Le coût du parcours systématique de listes de processeurs peut se révéler prohibitif sur un graphe de grande taille.
Autour de la norme XML existent un certain nombres de langages et d'outils qui permettent d'exprimer ce type de parcours. XPath est un langage simple permettant de décrire un ensemble de noeuds d'un document XML respectant certaines contraintes. JXPath est un outil permettant d'évaluer sur un graphe d'objets arbitrairement complexe une expression XPath. Ceci permet d'exprimer très simplement et trés abstraitement des requêtes mais pas des transformations. Pour ces dernières, il existe XSLT mais ce langage, exprimé en XML, est particulièrement verbeux et ne s'applique qu'à des documents XML.
Spoon (Spoon) est un outil permettant de réaliser des transformations de code source Java5 par réflexion à la compilation et manipulation de modèles fortement typés. Cet outil utilise les annotations pour permettre au programmeur de définir des cibles et paramètres de transformations. Celles-ci sont exprimées sous la forme d'une API de manipulation d'un méta-modèle du langage Java. Un ensemble de processeurs attachés à un mécanisme de Visiteur (!) permettent de réaliser ces transformations par précompilation des sources et instrumentation du code-octet. Spoon permettrait d'implanter les techniques présentées dans cet article, mais le pilotage par annotations implique que l'utilisation d'un type dans un parcours soit exprimé à la compilation ce qui n'est pas souhaitable: on souhaite pouvoir manipuler dans un graphe des objets qui n'ont pas nécessairement été prévus pour cela.
TOM A Pattern Matching Compiler for Multiple Target Languages est une extension du langage Java (et d'autres langages non orienté-objet) permettant d'utiliser le filtrage de motif sur la structure des objets manipulés. Inspiré par les langages fonctionnels qui offrent depuis longtemps cette facilité syntaxique, TOM permet de définir clairement et efficacement (ie. de manière statique) des transformations de termes ou d'arbres dans des langages où ce mécanisme n'existe pas. Le filtrage de motif sur la structure des objets est une solution au problème du typage fort des traitements de noeuds dans les graphes. Mais outre qu'il nécessite une extension au langage, ce mécanisme n'offre aucune solution a la généricité du parcours de graphes.
La notion de matching de graphes typés et de réécritures de graphes est au centre de diverse approches de transformations de modéles telles qu'implantées par exemple dans ATL ou Fujaba. De telles techniques peuvent être utilisées pour effectuer les transformations sur des graphes, au prix toutefois d'une certaine complexité de manipulation. Ces approches, intéressantes dans le cadre d'ateliers de modélisationd ou de réingénierie, nous paraissent difficiles à appliquer telles quelles dans des activités de programmation usuelles.
La solution la plus complète au problème posée est fournie par le paradigme de programmation adaptative implantée dans le cadre de Demeter et plus précisément par la spécification de stratégies de parcours de graphes (Traversals of object structures).
TO BE CONTINUED
Plan
Cet article est organisé comme suit. Dans la section suivante, nous présentons l'approche Scrap Your Boilerplate telle quelle est proposée originellement dans les articles de Ralf Lämmel et Simon Peyton-Jones. Nous relions cette solution au contexte des langages orienté-objets statiquement typés et présentons un exemple d'application possible pour la manipulation de termes d'expressions arithmétiques. Deux implantations du patron Visiteur réalisant une évaluation d'un terme quelconque sont présentées. La deuxième section est consacrée à la présentation de notre solution au problème du parcours paramétrique de graphes d'objets. Nous détaillons les différents composants nécessaires et une implantation pour la plateforme Java5 de cette approche. La troisième section est consacrée à une comparaison empirique entre cette solution et d'autres techniques: Visiteur bien sûr, évaluation par requêtes XPath, approches dynamiques. Nous évaluons notre approche pour résoudre différents problèmes de parcours typiques. Enfin, nous concluons par les perspectives ouvertes par ce travail.
Signalons que le code source complet Java utilisé pour valider cette approche est disponible à l'adresse http://www.oqube.com/projects/object-traversal. Seules des fragments significatifs nécessaires à la compréhension du sujet sont inclus dans le corps de cet article.