\documentclass[a4paper,twoside,openright,BCOR18mm]{scrreprt} \usepackage[utf8]{inputenc} \usepackage[cyr]{aeguill} \usepackage[francais]{babel} \usepackage{xspace} \usepackage{graphicx} \usepackage{listings} \usepackage{tabularx} \usepackage{slashbox} \bibliographystyle{alpha} \lstset { language=XML, basicstyle=\scriptsize\ttfamily, showstringspaces=false, %numbers=left, numberstyle=\tiny, stepnumber=2, numbersep=5pt, % how far the line-numbers are from the code showspaces=false, % show spaces within strings adding particular underscores showtabs=false, % show tabs within strings adding particular underscores frame=single, % adds a frame around the code tabsize=2, % sets default tabsize to 2 spaces captionpos=b, % sets the caption-position to bottom breaklines=true, % sets automatic line breaking breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace } \author{Guillaume Libersat } \titlehead{ \begin{description} \item[Université] USTL - Lille I \item[Laboratoire] LIFL - INRIA \item[Lieu] Lille, France \item[Équipe] RMoD/Adam \item[Maître de stage] Stéphane \bsc{Ducasse} \item[Jury] Jean-Luc \bsc{Dekeyser} et Christophe \bsc{Chaillou} \end{description} } \subject{Mémoire de Master Recherche} \title{Vers une traitification des Collections} \date{Février à Juin 2008\\-\\\textit{Soutenu le 16 Juin 2008}} %\publishers{\textbf{Keywords.} Object-oriented programming, % Refactoring, Restructuration, Traits, Inheritance.\\ \publishers{ \vspace{10em} {\begin{figure} \centering % \includegraphics[width=3cm]{figures/ustl.png} \includegraphics[width=3cm]{figures/lifl.jpg} \includegraphics[width=3cm]{figures/logo.png} \includegraphics[width=4cm]{figures/inria.png} \end{figure} } } \pagestyle{headings} \begin{document} \maketitle \newpage \thispagestyle{empty} \setcounter{page}{0} \mbox{} \newpage \thispagestyle{empty} \setcounter{page}{0} \mbox{} \chapter*{Remerciements} \pagenumbering{roman} \setcounter{page}{1} %\thispagestyle{empty} %\setcounter{page}{0} Je remercie Stéphane \bsc{Ducasse} pour m'avoir encadré pendant ce travail et pour m'avoir guidé sur la découverte de nouveaux domaines. Je tiens à remercier particulièrement Mathieu \bsc{Suen} pour son aide et ses conseils tout au long du stage. Merci aussi à Alexandre \bsc{Bergel} pour toujours avoir été volontaire pour les relectures. J'adresse aussi des remerciements spéciaux aux joyeux lurons du bureau 223 ainsi qu'à A.F. \bsc{Le Meur} qui m'ont aidé à garder le moral dans les moments difficiles, chacun à leur manière. Je tiens aussi à remercier Pierre \bsc{Tramo}, J2EE lead architect, pour ses remarques pertinentes sur les collections java. Enfin, je me vois obligé de remercier Alban pour toutes les soirées passées à hanter l'INRIA, rythmées au chant de \og léon, si t'es champion, appui sur l'champignon\fg. \newpage \mbox{} \tableofcontents \chapter{Introduction} \pagenumbering{arabic} \setcounter{page}{1} \section{Environnement} Ces travaux ont été réalisés dans le cadre de mon Master 2 recherche, spécialité \og Systèmes Embarqués et distribués, Image et Génie Logiciel\fg. Il s'agit d'un stage de fin d'études d'une durée de cinq mois qui a pour but d'initier les étudiants à la recherche en informatique. \paragraph{Cadre.} La formation doctorale est rattachée au LIFL, ou \og Laboratoire d'Informatique Fondamentale de Lille\fg. Il s'agit d'un laboratoire universitaire dépendant de l'Université de Lille1. Le stage s'est cependant déroulé à l'INRIA (\og Institut National de Recherche en Informatique et Automatique\fg) Lille - Nord Europe. Cet organisme a pour mission la recherche fondamentale et appliquée dans le domaine des sciences et technologies de l'information et de la communication. \paragraph{Équipe.} L'équipe \og RMoD\fg, dans laquelle ce stage a été réalisé, est une équipe INRIA en cours de création qui est actuellement rattachée à l'équipe-projet \og Adam\fg. \og RMoD\fg se pose comme objectif général la question suivante : \og Comment aider les équipes de développement à maintenir et faire évoluer leurs logiciels ?\fg. Cet objectif est réalisé à travers deux objectifs complémentaires : la remodularisation et les constructions modulaires. L'équipe est menée par Stéphane \bsc{Ducasse}. \section{Contexte} \subsection{Problématique} Récemment, les traits~\cite{Scha03a,Berg07e,Duca07b} ont proposé une solution aux problèmes liés à l'héritage multiple~\cite{Meye88b,Keen89a,Stro86b}. Les traits sont des entités à granularité fine qui permettent de factoriser du comportement pour les classes. Dans ce modèle, l'avantage indéniable est que l'entité composante dispose de tout le contrôle de la composition. Nous les présentons à la section \ref{sec:traits}. Des recherches précédentes ont permis de valider l'utilité des traits en refactorisant des bibliothèques existantes de collections et de streams. Ces refactorisations ont montré une maturation du modèle des traits avec l'expérience acquise dans le domaine. En effet, la première refactorisation des collections a consisté à une traitification des classes sans aller plus loin. Les dernières refactorisations réalisées à l'aide des traits, elles, s'intéressent à la réécriture complète afin de donner un aspect plus modulaire et de tirer vraiment parti des possibilités offertes par les traits. Aucune hiérarchie importante n'a vraiment, à ce jour, était refactorisée avec comme objectif de tirer au maximum parti des traits. Refactoriser avec les traits des hiérarchies où de nombreuses classes hétérogènes sont présentes reste donc, à ce jour, un terrain encore non exploré. \subsection{Objectifs et réalisations} \paragraph{Buts.} Le but de ce travail est de mettre les traits à l'épreuve et de prouver expérimentalement qu'ils peuvent s'adapter ainsi qu'être un atout pour la refactorisation des grandes bibliothèques. Plus spécifiquement, nous souhaitons répondre aux questions suivantes : \begin{itemize} \item Comment est-il possible de proposer une hiérarchie de traits pouvant s'adapter à la diversité d'éléments ? \item Par quels processus peut on s'assurer que la hiérarchie pourra s'adapter aux besoins futurs ? \item Comment s'assurer que cette hiérarchie restera consistante ? \item Quelle est la granularité idéale des traits qui favorise la réutilisation ? \item Jusqu'à quel point pouvons nous corriger les problèmes que nous identifierons dans la bibliothèque des collections existante ? \item Quelles sont les limites et les contraintes que nous rencontrerons lors de l'utilisation des traits ? \end{itemize} \paragraph{Solution.} Nous avons décidé de prendre la bibliothèque de collections de Smalltalk comme terrain d'expérimentation. Le choix des collections s'est fait pour plusieurs raisons : i/ elles posent des problèmes lors de leur implémentation avec héritage simple ; ii/ il s'agit d'une bibliothèque très conséquente ; iii/ elles proposent une diversité importante de structures de données, ce qui est représentatif des grandes hiérarchies ; iv/ d'autres travaux impliquant les collections et les traits ont déjà été réalisés ce qui nous permettra une comparaison ; v/ les collections sont une bibliothèque importante des langages de programmation ; vi/ des contraintes sont imposées par les spécifications ANSI Smalltalk et par les implémentations existantes. \paragraph{Contributions.} Les contributions de ce travail sont donc : \begin{enumerate} \item L'analyse des collections existantes de Smalltalk et Java ainsi que la définition par le standard Smalltalk ANSI ; \item L'identification des problèmes des bibliothèques de collections existantes ; \item La proposition d'un design pour une nouvelle hiérarchie de collections, composée d'éléments réutilisables. Il faut bien noter qu'il s'agit d'une proposition et non d'une implantation ; \item La proposition d'une extension aux traits afin de permettre l'utilisation de contrats ; \item L'évaluation des traits en tant qu'éléments réutilisables pour définir des bibliothèques et la vérification de l'obtention d'un design plus clair et plus modulaire ; \item Une identification des problèmes qui surviennent lors de l'utilisation des traits (par exemple, comment choisir la granularité ?). \end{enumerate} \section{Outillage pour la réalisation} \paragraph{Héritage et traits.} Afin de réaliser notre proposition, nous disposons d'un large éventail de solutions permettant de composer du comportement. Nous les présentons dans le chapitre \ref{sec:etat-art}. Nous basons cependant notre travail sur le modèle de composition le plus abouti, c'est à dire les traits. En effet, ce modèle est beaucoup moins limité que l'héritage, évite la copie ou le wrapping ; ce qui est partie intégrante de notre objectif. Trois modèles principaux des traits sont disponibles ; c'est pourquoi nous les analyserons afin de déterminer quel est le modèle qui semble le plus approprié pour nous aider à réaliser notre proposition. En effet, les traits sont parties intégrantes de notre travail car il s'agit d'un outil crucial pour la réussite de celui-ci. \paragraph{Les collections.} Une bibliothèque de collections permet de stocker des ensembles de données sous différentes formes. Cette diversité de formes permet de s'adapter aux besoins des programmes et de les rendre plus efficaces en proposant des version optimisées. Les collections sont essentielles pour un langage de programmation. Il s'agit d'ailleurs d'un très bon cas concret pour notre expérimentation. En effet, celles-ci exposent une hiérarchie très complexe et disposent très souvent de problèmes de conceptions. Nous les décrivons dans la section \ref{sect:ana-coll}. Nous nous baserons donc sur les collections de Smalltalk-80 pour réaliser nos travaux, mais étudierons tout de même d'autres collections comme celles de Java afin d'obtenir un panel plus représentatif. \paragraph{Smalltalk.} Smalltalk~\cite{ANSI98a} est un langage de programmation dynamique typé principalement inspiré de Lisp et Simula, où le seul moyen d'activer un objet est d'envoyer un message. Il a été créé dans les années 80 par un groupe de chercheurs du Xerox PARC (Palo Alto Research Center). Parmi ceux-ci, on compte notamment Alan Kay (Turing Award 2002) qui s'est chargé de la majeure partie du design. Une des particularités du design ce langage est que tout est objet et qu'un objet est toujours une instance de classe. Il n'y a pas de types primitifs comme on peut le rencontrer en Java par exemple. Ainsi, les classes elles-mêmes sont des objets, instances de leurs méta-classes. Smalltalk a aussi l'originalité d'être le plus réflexif (structurellement et comportementalement) et d'être implanté en lui-même. On peut donc le voir comme un petit système d'exploitation. Smalltalk peut être considéré comme un langage modèle dans le sens où il essaye de minimiser sa syntaxe\footnote{Une synthèse de sa syntaxe est disponible en annexe \ref{sec:la-syntaxe-smalltalk}} tout en essayant d'être le plus consistent possible. Il n'en reste pas moins puissant et a été remarqué dès ses premières versions par le milieu académique. C'est ainsi que via ce langage, les premiers outils comme les navigateurs de classes ou de code sont nés. Il a d'ailleurs été, depuis sa création, terrain d'expérimentation pour les chercheurs et industriels. Il a ainsi inspiré de nombreux concepts comme la programmation par passage de messages (pour l'informatique répartie par exemple), les interfaces graphiques modernes ou encore les méta-modèles que l'on retrouve dans les langages modernes (Perl, Java, Python, ...). La dernière version de Smalltalk a été normalisée AINSI en 1998 et est actuellement utilisable sous plusieurs incarnations. On retrouve notamment VisualWorks, Squeak ou encore GNU Smalltalk. \paragraph{Squeak.} Squeak~\cite{Squeak} est une implantation de Smalltalk, dérivée de standard 80. Elle a été initiée par une équipe d'Apple Computer incluant des membres de la communauté originelle de Smalltalk-80. Elle a ensuite été reprise et améliorée par les studios Walt Disney Imagineering qui l'ont utilisée à des fins internes. Elle est maintenant activement maintenue et développée par une communauté internationale. Cette implémentation fournit une machine virtuelle et une image. Cette première est écrite en elle-même, ce qui la rend entre autres très facilement portable. L'image quant à elle consiste en un cache de bytecode. Ceci permet d'avoir un ensemble de données indépendantes de la machine cible et utilisable sur n'importe quelle architecture du moment qu'une machine virtuelle Squeak est disponible. Squeak a été récemment sélectionné pour le projet OLPC (One Laptop Per Child~\cite{Benjie}) afin de fournir l'environnement Etoys, résultat des travaux de recherche de l'équipe d'Alan Kay. \chapter{Etat de l'art : Composition de comportement et refactorisations} \label{sec:etat-art} Dans cette section, nous présentons les principales méthodes de composition de comportement proposées jusqu'à ce jour pour la programmation orientée-objet Nous commencerons par étudier les types d'héritages encore actuellement très largement utilisés, c'est à dire l'héritage simple et l'héritage multiple. Nous continuerons ensuite sur des propositions plus récentes tels que les Mixins ou les Traits. Enfin, nous nous introduirons dans un premier temps le concept des Traits, puis nous présenterons quelques refactorisations significatives qui ont pu être faites autour des Collections. \section{Composition de comportement en orienté-objet} \subsection{L'héritage} \label{sec:l-heritage} L'héritage en programmation orienté-objet est un moyen bien connu permettant de créer de nouvelles classes en composant d'autres classes déjà présentes dans le système. Un des avantages de l'héritage est qu'il permet de réutiliser du code efficacement lorsque les classes partagent suffisamment d'éléments communs. Ceci permet entre autres de réduire la complexité des programmes ainsi que de faciliter la compréhension du programmeur. %[\textbf{FIXME}(Alex): Pas uniquement, la notion de spécialisation est %fondamentale] On associe aussi à l'héritage la notion de polymorphisme qui indique qu'un élément de comportement (par exemple, une méthode) peut disposer de plusieurs implantations sous-jacentes. Ce mécanisme peut être utilisé dans le but d'obtenir plusieurs résultats. On peut regrouper ces utilisations sous trois catégories. \paragraph{Spécialisation.} La spécialisation est une des raisons essentielles de l'utilisation de l'héritage. On créé ainsi des classes spécialisées à partir de classes plus abstraites. Le mécanisme est théoriquement réitérable à volonté ; on appelle cette utilisation de l'héritage le sous-typage. Avec la classe spécialisée, les instances disposeront des données et de comportement qui n'étaient pas prévues dans la classe mère, tout en profitant de ceux de cette dernière. Prenons comme exemple la classe \textit{Point} qui dispose d'un champ \textit{x} et d'un champ \textit{y}. Supposons maintenant que nous souhaitons obtenir un point coloré : \textit{ColoredPoint}. Celui-ci va alors être un sous-type de \textit{Point} et donc disposer des attributs de celui-ci tout en ajoutant la notion de couleur (via un autre champ et/ou une méthode). Il existe aussi un autre type de spécialisation qui fait appel à la notion de classes abstraites. Ces dernières sont des classes où certaines méthodes ne sont pas implantées. Lorsqu'une classe concrète souhaite spécialiser une classe abstraite, elle doit alors donner un comportement aux méthodes requises. Le fait de donner du comportement par un sous-classage est connu sous le nom d'implantation. \paragraph{Redéfinition.} La plupart des langages orientés-objet permet aux classes de redéfinir l'implantation d'un aspect qui est hérité. Ce processus est appelé redéfinition. La redéfinition introduit alors un problème : quelle version du comportement une instance doit-elle utiliser ? L'objet pourrait en effet appeler le comportement de sa propre classe ou celui de la classe héritée. Il n'y a pas de réponse unanime à ce problème. En effet, les langages de programmation y répondent de manières différentes et certains langages permettent même de spécifier qu'un comportement particulier ne pourra pas être redéfini. \paragraph{Réutilisation.} Une des motivations initiales de l'héritage était de permettre qu'une nouvelle classe puisse réutiliser le code déjà existant d'une autre classe. Cette pratique est appelée sous-classage ou héritage d'implantation. Cependant, dans la plupart des communautées, le sous-classage ayant pour unique but de réutiliser le code est considéré comme une mauvaise pratique. La première raison est que cette utilisation ne garantie en aucun cas un polymorphisme fiable, ce qui implique qu'on ne peut pas substituer fiablement une implantation par une de ses sous-classes. Il est pourtant possible d'arriver au même but par une autre technique qu'on appelle délégation. Elle a pour avantage d'éviter de tromper l'utilisateur en évitant d'offrir une impression de polymorphisme. On notera cependant qu'elle nécessite plus d'efforts de la part du programmeur. \bigskip Dans la suite de cette section, nous présenterons les deux principales formes d'héritage : l'héritage simple et l'héritage multiple. \subsubsection{Héritage simple} \label{subsec:herit-simple} L'héritage simple est actuellement utilisé dans de nombreux langages de programmation. En effet, depuis sa création avec Simula 67, cette idée a eu énormément de succès de part sa simplicité et de sa révolution. Sa puissance en a fait un concept très prisé et est en autre à la base du succès de Smalltalk et Java. L'héritage simple force la hiérarchie de classes à être linéaire en imposant un seul parent à chaque héritier. Ceci permet donc de réduire le nombre de problèmes qui pourraient surgir avec des hiérachies plus complexes, mais limite aussi certaines possibilités. \paragraph{Duplication de code.} La première conséquence de ces limitations est la duplication de code. Ce problème est le plus fréquemment rencontré avec ce type d'héritage. En effet, il n'est pas rare que dans les programmes l'un veuille composer deux comportements orthogonaux. Dans ce cas, à moins de réorganiser totalement la hiérarchie quand celà s'avère possible, le problème se résoudra souvent par une duplication de code. L'exemple de la figure \ref{fig:dup_code_single_herit} illustre ce problème. Prenons le cas où nous avons une hiérarchie de véhicules. Comme on peut le voir, nous avons \textit{WheeledVehicule} en tant que racine de la hiérarchie ; cette dernière étant spéciliasée vers des véhicules motorisés ou non. Nous aimerions donc partager le code de motorisation (\textit{MotorisedVehicule}) pour tous les véhicules motorisés. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/Fig21.pdf} \caption{Duplication de code avec le mécanisme d'héritage simple} \label{fig:dup_code_single_herit} \end{figure} L'héritage simple ici ne nous permet pas de réaliser cette opération. En effet, le seul moyen de partager le comportement serait de l'inclure dans un des ancêtres communs des classes intéressées. Cependant, ceci impliquerait que les autres sous-classes seraient aussi motorisées, ce qui est faux. Voici donc une limitation de l'héritage simple où la seule alternative est la duplication de code : il sera nécessaire de doter \textit{Car} et \textit{MotorBike} du même code. Le concept d'interfaces peut alors être utilisé afin de garantir que les implantations seront compatibles, mais ceci ne résoud en rien le problème initial car elles ne peuvent pas contenir de code. \paragraph{Mauvaise conception par défaut.} Un autre exemple que l'on peut rapprocher au précédent problème est la difficulté d'obtenir des objets parfaitement uniformes lorsqu'un système grossit. Prenons l'exemple de la classe \textit{RectangleMorph} dans Squeak. Cette classe représente un bloc de couleur à l'écran que l'on peut manipuler. Celle-ci est une sous-classe des différents composants de Morph, le système de fenêtrage de Squeak, et profite donc de tous les comportements généralistes que la hiérarchie de Morph offre. Cependant, Squeak propose aussi dans son système une classe appelée \textit{Rectangle}, sous-classe d'\textit{Object}. Or, \textit{RectangleMorph} n'est pas une sous-classe de \textit{Rectangle}, alors qu'il est évident que ce premier est intraséquement un Rectangle. \textit{RectangleMorph} n'implante donc pas tous les messages de \textit{Rectangle} et ne peut donc être utilisé comme tel. Ce qui est encore plus remarquable est que la classe \textit{RectangleMorph} dispose d'un champ interne qui pointe sur un \textit{Rectangle}. Un programmeur qui souhaiterait résoudre ce problème est alors contraint à choisir parmi quelques alternatives non satisfaisantes d'un point de vue génie logiciel. Sa première option est de copier toutes les méthodes de \textit{Rectangle} vers \textit{RectangleMorph}, mais ceci violerait le principe de DRY (Don't Repeat Yourself). Une autre alternative est d'offrir une méthode de conversion, comme \og \textit{RectangleMorph}$>>$asRectangle\fg et de supposer que le développeur utilisera cette méthode quand il nécessitera d'envoyer des messages au rectangle. Enfin, une troisième option est de déléguer les opératinons de \textit{Rectangle}. Une manière simple de faire ceci est d'implanter toutes les méthodes de \textit{Rectangle} sous forme d'une simple méthode au niveau de \textit{RectangleMorph}. En voici un exemple : \begin{lstlisting} RectangleMorph>>area ^ self asRectangle area \end{lstlisting} Il s'agit certainement de la manière la plus intuitive de faire pour l'utilisateur, mais ceci augmente fortement la taille de l'objet et ajoute un nombre non négligeable de méthodes inutiles, rendant la classe plus difficile à comprendre. \paragraph{Conclusion.} Il est donc clair ici que l'héritage simple, bien que proposant un mécanisme simple et fonctionnel, ne couvre pas tous les cas d'utilisations et peut parfois conduire à des concessions non désirées en terme de génie logiciel. \subsubsection{Héritage multiple} L'héritage multiple propose le même mécanisme que l'héritage simple mais ajoute la possibilité aux héritiers de disposer de plusieurs parents. Avec l'héritage multiple, il est donc possible d'exprimer beaucoup plus efficacement les compositions de comportements voulues. Cependant, comme on peut l'intuiter, ceci apporte aussi son lot d'ambiguïtés et donc de problèmes liés à ce mécanisme. Nous y reviendrons dans la suite de l'analyse. Depuis les années 80, il y a eu un nombre significatif de travaux autour de l'héritage multiple mais aucun d'eux n'a jamais été réellement satisfaisant. Certaines personnes en sont même venues à la conclusion suivante : \begin{quote} \textit{``Multiple inheritance is good, but there is no good way to do it''} -- Steve Cook~\cite{Cook87a} \end{quote} En effet, les propositions d'héritages multiples ont souvent amenées plus de problèmes qu'elles n'en résolvaient. On peut d'ailleurs ressentir que la tendance revient actuellement à la simplicité avec les langages récents (Java, C\#, ...). En effet, il semblerait que les concepteurs aient jugé que la complexité introduite par l'héritage multiple était trop importante comparée à l'apport réel de ce mécanisme. Dans la suite de cette section, nous proposons d'étudier les principaux problèmes de l'héritage multiple. \paragraph{Conflits de composition.} Reprenons l'exemple proposé dans la section précédente : le \textit{Rectangle} et le \textit{RectangleMorph}. Le problème était qu'un \textit{RectangleMorph} est en soit un rectangle mais qu'il ne sous-type pas \textit{Rectangle}, résultat des contraintes de l'héritage simple. Avec l'outillage de l'héritage multiple, nous pouvons désormais faire qu'un \textit{RectangleMorph} hérite aussi de \textit{Rectangle}. Nous composerions ainsi cette dernière et \textit{BorderedMorph}, la super-classe de \textit{RectangleMorph} qui est un élément graphique rectangulaire dans l'environnement Squeak. Cette classe hériterait alors de deux ensembles distincts d'état et de méthodes ayant le même but : la gestion d'un rectangle (sa position par exemple). On a donc clairement ici un problème de composition que l'on peut difficilement résoudre sans outillage de la part du langage. \paragraph{Le problème du Diamant.} \label{diamand_pb} Un autre problème bien connu de l'héritage multiple est le fait qu'il introduit des hiérarchies d'héritage non linéaires. Ceci implique plusieurs choses : d'abord une difficulté d'implantation de la part des développeurs du langage, ensuite des problèmes au niveau conceptuel. La difficulté principale liée à la non-linéarité est qu'il faut réussir à ordonnancer cette hiérarchie afin de la rendre exécutable. Dans la plupart des cas, c'est le compilateur qui va réaliser cette tâche et qui livrera une hiérarchie difficilement prévisible lors de l'écriture du code. On voit ici que nous avons un problème de prédictabilité. En effet, si on introduit des changements dans la hiérarchie, il est possible que l'algorithme produise un autre ordre d'exécution qui pourrait modifier le comportement final. Un des cas flagrant de problème de linérisation est appelée le \textit{Problème du Diamant} ou \textit{Fork-Join Problem}. Nous l'illustrons par l'exemple qui suit en nous appuyant sur la figure \ref{fig:mult_inherit_pb}. Prenons une classe mère appelée \textit{Vehicle} qui possède une méthode \textit{engine\_start()}. Cette classe possède deux héritiers, à savoir \textit{Boat} et \textit{Car} qui surchargent la méthode précédemment citée. \begin{figure}[here] \centering \includegraphics[width=10cm]{figures/Fig22.pdf} \caption{Problème comportementale lié à la composition via le mécanisme d'héritage multiple} \label{fig:mult_inherit_pb} \end{figure} On souhaite alors composer ces deux classes vers un nouveau véhicule : \textit{AmphibiousCar}. Nous nous trouvons alors face à un problème : quelle méthode \textit{engine\_start()} doit-on appeler ? Celle de \textit{Boat} ou celle de \textit{Car} ? De nombreux travaux ont à ce propos été effectués et plusieurs langages ont alors proposé des solutions plus ou moins partielles à ce défaut : \begin{itemize} \item Perl et Python utilisent une liste de classes ordonnée depuis lesquelles hériter. Le compilateur utilise alors la première méthode qu'il trouve en effectuant une recherche en profondeur dans la liste des super-classes. \item C++ quant-à lui, demande au programmeur d'expliciter de quel parent l'élément attendu provient. On aura donc des références aux éléments telles que ``Car::Vehicle.Name'' ; \item Eiffel permet aux programmeurs d'expliciter les éléments qui seront fusionnés ou non lors de la composition. Il fusionnera aussi automatiquement les éléments ayant le même nom et la même implantation. Eiffel permet aussi de renommer les éléments hérités afin de les distinguer ; \item CLOS donne au programmeur la possibilité de contrôler la combinaison des méthodes et même de changer la couche réflexive via son Protocole Méta-Objets (MOP) dans le cas où il souhaiterait redéfinir la notion d'héritage, de dispatch ou encore d'instanciation. \end{itemize} Cependant, on notera qu'aucune des solutions citées ci-dessus n'est réellement satisfaisante car elles ne couvrent jamais tous les cas d'utilisations d'une manière générique. \paragraph{Hiérarchie fragiles.} Comme des méthodes ayant le même nom peuvent être héritées depuis la même classe, le fait de n'avoir qu'un mot clé \og super\fg pour exprimer l'accès aux méthodes de classes héritées n'est pas suffisant. C'est pourquoi, en C++, par exemple, le langage impose d'explicitement référencer la méthode redéfinie avec son nom de super-classe. Ceci induit donc des références aux classes dans le code source et rend ainsi le code vulnérable aux changements de structures dans la hiérarchie de classes. D'autres langages imposent une hiérarchie linéaire pour les super-classes. Cependant, une telle linéarisation mène souvent à des comportements innatendus. \subsection{Les mixins} A la suite des problèmes qu'apportait l'héritage multiple, des travaux connexes ont commencé à émerger afin de résoudre les problèmes de hiérarchie d'une autre manière. On a d'abord vu apparaître les \fg Flavors\og, introduites comme une extension de Lisp. On peut les considérer comme la première forme de Mixins. Les Mixins sont des classes utilitaires qui regroupent des fonctionnalités Hériter d'un Mixin n'a pas un but de spécialisation, mais il s'agit est un moyen efficace de collecter des fonctionnalités (groupes de méthodes). Les Mixins qui vont être utilisés par une classe vont alors être intégrés à la hiérarchie. La figure \ref{fig:mixins} illustre ce mécanisme. Nous avons ici une classe nommée \textit{AmphibiousCar} qui va composer les deux mixins \textit{Car} et \textit{Boat}. Les mixins seront donc intégrés à la hiérarchie \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/Fig4Mixin.pdf} \caption{Intégration des mixins dans la hiérarchie de classes.} \label{fig:mixins} \end{figure} Le but des Mixins est donc qu'ils soient hérités pour la réutilisation de code et non pas instanciés en tant que classes indépendantes. Le mécanisme de Mixins permet de résoudre la plupart des problèmes engendrés par l'héritage multiple. Cependant, il introduit à son tour des problèmes d'implantations tout aussi complexes ce qui, en fait, ne fait que déplacer la difficulté. Parmi ces problèmes, on remarquera particulièrement les problèmes d'ordonnancements qui se rapprochent des problèmes liés à l'héritage multiple. On peut d'ailleurs le voir sur la figure précédente : comment connaître le mixin qui précédera directement \textit{AmphibiousCar} dans la hiérarchie une fois la linéarisation effectuée ? De nombreux langages utilisent cependant les Mixins. On peut citer Perl, Python, D, Ruby ou encore StrongTalk. D'autres langages comme Java ou C\# n'implémentent pas les Mixins, mais offrent un mécanisme qui dispose d'une partie de leurs fonctionnalités : les interfaces. Ces dernières permettent non pas la réutilisation de code (car, contrairement aux Mixins, elles ne peuvent contenir du comportement), mais autorisent ainsi du polymorphisme. \subsection{Les traits} \label{sec:traits} Dans cette section, nous proposons d'introduire les traits en commençant par présenter les motivations à travers les défauts des techniques actuelles, puis nous introduirons l'idée générale des traits et finirons sur une présentation plus détaillée des modèles proposés jusqu'alors. \medskip Le mécanisme des traits est un moyen assez récent permettant de composer du comportement de manière flexible dans les langages à héritage simple. Les traits partent du constat que les classes disposent de trop de responsabilités. En effet, on peut voir que ces dernières sont utilisées à la fois pour i/ la cration d'objets, ii/ la réutilisation de code. Ces deux rôles sont en fait assez conflictuels. Tout d'abord, dans le premier cas on aimerait avoir des classes fournies tandis que dans le second, on aimerait avoir une granularité assez fine. Ensuite, la génération d'instances nécessite que chaque classe ait une unique place dans la hiérarchie tandis que les unités de réutilisation devraient être utilisables à n'importe quel endroit. On voit bien ici que ces deux rôles se composent assez difficilement. Les traits utilisent donc un modèle qui permet de séparer les préoccupations et ainsi permettent de résoudre une bonne partie des problèmes jusqu'alors rencontrés avec l'héritage multiple ou les Mixins. Ainsi, les traits souhaitent décomposer les classes en briques de bases destinées à être réutilisées, en proposant une représentation de première classe des aspects comportementaux d'une classe. En partie grâce à ceci, les traits disposent de bonnes propriétés comme la réutilisation de code efficace, la suppression des indirections, une meilleure modularité ou encore une amélioration de la compréhension des hiérarchies de classes. Les traits permettent aussi de doter le programmeur d'outils permettant de régler la plupart des problèmes récurrents liés aux méthodes usuelles. Ainsi, les compositions conflictuelles ou encore le problème du diamant peuvent être évités. Plusieurs modèles de traits ont été proposés depuis 2002. Dans les paragraphes suivants, nous introduisons donc ces différents modèles, en parcourant les concepts en détail dans leur première incarnation, puis nous nous focaliserons sur les différences vis à vis de la proposition initiale lors de la description des modèles qui ont suivis. \subsubsection{Traits sans état} Les traits sans état~\cite{Scha03a} prennent l'approche de ne s'occuper que du comportement et non de l'état en supposant que celui-ci sera ajouté lors de la composition vers les classes. Cette version impose donc qu'aucun n'état ne soit déclaré dans les traits et que tous les accès à l'état soient indirects. On devra donc écrire des accesseurs si l'ont souhaite référer à l'état. Aussi, on notera qu'un trait ne dispose pas de super-classe et que si le mot-clé ``super'' est utilisé, il restera indéfini jusqu'à la composition vers une classe. \paragraph{Structure.} Les traits sont une collection de méthodes de première classe. Ces méthodes doivent être du comportement pur et ne peuvent référencer une variable d'instance directement. On observe deux types de méthodes dans un trait comme illustré sur la figure \ref{fig:un_trait} : \begin{itemize} \item Les \textit{méthodes fournies} : Ce sont les méthodes qui se trouvent dans le trait et qui pourront être utilisées par les compositeurs\footnote{On définit compositeur par une classe ou un trait qui compose d'autres traits. Le terme \textit{composant} n'est pas utilisé pour éviter l'amalgame avec la programmation logiciel orientée composants.} ; \item Les \textit{méthodes requires} : Ces méthodes sont des méthodes qui sont nécessaires au fonctionnement des méthodes fournies. Elles pourront être résolues lors de la composition vers un autre trait ou vers une classe. \end{itemize} \begin{figure}[here] \centering \includegraphics[width=6cm]{figures/simpleTrait.pdf} \caption{Un trait avec ses méthodes fournies (gauche) et ses méthodes requises (droite). Le formalisme utilisé est une extension d'UML.} \label{fig:un_trait} \end{figure} \paragraph{Propriétés fondamentales.} Une propriété à la base des traits est l'applatissement. En effet, celle-ci énonce que la sémantique d'une classe définie avec les traits est exactement la même que celle d'une classe construite sans. Ainsi, si une classe A est définie en utilisant le trait T, et que T définit les méthodes a et b ; alors la sémantique de A sera la même que si A définissait directement a et b. De plus, cette propriété implique que le mot clé \textbf{super} n'a pas de signification particulière pour les traits et qu'il indique simplement que la résolution des méthodes commencera à la super-classe de la classe qui utilise le trait. Une autre propriété, elle aussi très importante, est que l'ordre de composition n'est pas significatif. Ainsi, les conflits de méthodes des traits doivent être résolus au premier niveau de composition. On utilise alors les règles suivantes pour définir la précédence : \begin{enumerate} \item Les méthodes de la classe ont précédence sur les méthodes des traits ; \item Les méthodes des traits ont précédence sur les méthodes de la super-classe (suivant la propriété d'applatissement). \end{enumerate} \paragraph{Composition de classes.} \label{sec:comp_classes} Bien que les traits semblent être très proches des Mixins, ils se différencient par le fait qu'ils n'utilisent pas l'opérateur d'héritage pour réaliser la composition. Ils restent cependant totalement rétro-compatibles avec l'héritage simple en préférant lui être complémentaire que substitutif. L'héritage est alors utilisé pour dériver une classe vers une autre tandis que les traits sont utilisés dans un but structurel. On peut résumer ces relations par l'équation suivante : \begin{center} \textit{Classe = Super-classe + Etat + Traits + Ciment} \end{center} On va ainsi créer une classe à partir d'une super-classe, de nouvelles variables d'instances (si nécessaire), d'un ensemble de traits et de méthodes ciment. Ces dernières sont utilisées pour connecter les différents traits et accéder aux variables d'instances. On dit alors qu'une classe est \textit{complète} lorsque toutes les méthodes requises sont satisfaites. On observe aussi plusieurs cas récurrents de composition des traits. On notera particulièrement la somme, la redéfinition ou encore l'héritage comme décrit sur la figure \ref{fig:op_traits} \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/trait_ops.png} \caption{Les opérations principales des traits : somme, redéfinition, héritage.} \label{fig:op_traits} \end{figure} On notera qu'il est donc possible aussi de composer les traits entre eux et de réaliser ce qu'on appelle des traits composites. Ces derniers, contrairement aux classes sont souvent incomplets (i.e. des méthodes sont requises) mais gardent exactement les mêmes propriétés qu'un trait grâce à la propriété d'applatissement. \paragraph{Résolution de conflits.} Les traits se démarquent de l'existant dans le sens où la méthode veut que le programmeur ait le maximum de contrôle, et ce, le plus finement possible, lors de la composition. Ceci est extrêmement important car ces cas de conflits arrivent fréquemment et il est nécessaire d'expliciter comment les résoudre pour éviter les suppositions automatiques comme nous l'avons expliqué dans les sections précédentes. La composition des traits garantit que la résolution de conflits se fera au niveau du composite et non dans un sous-trait ; rendant ainsi la composition associative comme commutative. Afin de permettre ces résolutions, on dispose des opérateurs suivants : \begin{itemize} \item \textbf{Aliasing} : L'Aliasing permet de spécifier un nom différent pour une méthode lors de la composition du trait auquel elle appartient. Ce n'est pas du renommage dans le sens où les autres méthodes restent inchangées (les méthodes utilisant l'ancien nom continue de le faire). Ceci se révèle très pratique lorsque, par exemple, on souhaite utiliser deux méthodes ayant le même noms, mais fournies par deux traits différents ; \item \textbf{Exclusion} : Avec cet opérateur, il est possible d'exclure une ou plusieurs méthodes des traits composés. Ainsi, il est possible de choisir quelle méthode sera utilisée lorsque plusieurs traits proposent deux méthodes de même nom ; \end{itemize} Ces deux opérations sont illustrées sur la figure \ref{fig:trait_res_conf} \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/FigResConfTraits.pdf} \caption{Aliasing et Exclusion avec les traits.} \label{fig:trait_res_conf} \end{figure} \subsubsection{Traits avec état} Bien que les traits sans état soient tout à fait utilisables en pratique, il s'avère que dans certains cas l'introduction d'état semble réduire l'effort de programmation. Nous caractériserons tout d'abord les défauts qui ont menés à l'élaboration de ce nouveau modèle, puis nous introduirons les nouveaux concepts de ces traits et en viendront pour finir aux problèmes qu'ils induisent. \paragraph{Défauts des traits sans état.} Tout d'abord, les classes utilisant des traits sans état peuvent contenir beaucoup de code ciment lors de la composition de multiples traits (comme expliqué dans la section \ref{sec:comp_classes}). Deuxièmement, il très fréquent de voir des traits {artificiellement} incomplets à cause des nombreux accesseurs non définis. Ceci a pour désavantage majeur de polluer les interfaces avec des informations inutiles et donc de dégrader la compréhension. Ensuite, l'introduction d'un nouvel état (et donc d'accesseurs) dans un trait propage automatiquement la nécessité d'implémenter cet accesseur dans toutes les classes utilisatrices. La figure \ref{fig:trait_lock_var} illustre ce problème : le trait \textit{TSyncReadWrite} a besoin d'accéder à un verrou (\og lock\fg) et on voit bien ici que les accesseurs ont besoin d'être dupliqués dans SyncFile, SyncStream et SyncSocket. \begin{figure}[here] \centering \includegraphics[width=10cm]{figures/lock_var_dup.pdf} \caption{La variable \og lock\fg et les méthodes \og lock\fg et \og lock:\fg sont dupliquées au sein des utilisateurs du trait \textit{TSyncReadWrite}} \label{fig:trait_lock_var} \end{figure} Pour finir, le fait de devoir ajouter des accesseurs pour chaque variable d'instance, à la base privée, viole le principe d'encapsulation de la classe. Les traits avec état (\og Stateful Traits\fg~\cite{Berg07e}) proposent donc une évolution des traits sans état, plus satisfaisante d'un point de vue génie logiciel, en introduisant la possibilité d'avoir des variables d'instance. Cette évolution se veut la plus minimaliste possible et la plus proche de la philosophie d'origine, à savoir que le compositeur garde le maximum de contrôle sur la composition. \paragraph{Nouveaux mécanismes.} Les variables d'instance ainsi introduites ont alors une portée uniquement locale au trait auquel elles appartiennent. Il est cependant possible d'étendre la visibilité et d'exposer ces variables, mais uniquement sur demande explicite du compositeur. Pour ce faire, l'utilisateur du trait peut donner l'accès à une variable du trait en la nommant. Ceci fonctionne comme l'aliasing des traits sans état : il ne s'agit pas de renommage et les méthodes du trait continuent d'utiliser l'ancien nom de variable. Il est possible aussi de réunir deux variables qui ont la même sémantique. Ainsi, grâce à une nouvelle opération, l' \og Union \fg, le compositeur peut spécifier ces cas. Un exemple d'union est disponible sur la figure \ref{fig:sf_merge_var} où l'utilisateur, C, unifie \textit{x} et \textit{y} respectivement de T1 et T2 vers une variable d'instance \textit{w}. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/sf_merge_var.pdf} \caption{Un exemple d'union de variables. Ici, \textit{x} et \textit{y} deviennent \textit{w} pour C.} \label{fig:sf_merge_var} \end{figure} \paragraph{Renaissance de problèmes.} L'introduction d'état dans les traits a été réalisée de manière à respecter au maximum les propriétés des traits sans état. Cependant, un problème récurent des langages utilisant l'héritage multiple réapparaît avec les traits à état. En effet, les traits étant partagés entre plusieurs classes, il n'est donc plus possible d'accéder aux variables d'instance de manière linéaire (c'est à dire par position). On en revient donc à des problèmes de linéarisation comme décrits dans la section \ref{diamand_pb} qui ne sont pas triviaux à résoudre. Afin de palier à ce problème, les traits a état utilisent la méthode de \textit{copy down}. Plus de détails sont disponibles dans le papier original. \paragraph{Bénéfices et observations.} Il a été observé par expérimentations que les traits avec état permettent de i/ préserver l'encapsulation, ii/ réduire le nombre de méthodes définies et ii/ réduire le nombre de méthodes requises (à corréler avec les accesseurs). On notera cependant qu'ils introduisent une complexité non négligeable qui n'était pas présente dans les traits sans état. Utiliser les traits à état à la place des traits sans état n'est donc pas systématiquement au vu de la complexité introduite. \subsubsection{Freezable Traits} \label{subsec:freezable} Le modèle des traits gelables (\og Freezable Traits\fg~\cite{Duca07b}) est le dernier modèle de la famille des traits a avoir été proposé. Il part du constat que tous les conflits de compositions ne peuvent pas être réglés à l'aide des modèles précédants sans une réécriture partielle des méthodes conflictuelles. Celui-ci propose donc de modifier légèrement le modèle original des traits en ajoutant quelques concepts. Tout d'abord, il considère que le langage dispose de deux modificateurs d'accès : \textit{private} et \textit{public}, ce qui n'était pas le cas dans les versions précédentes. Ensuite, les traits gelables ajoutent deux opérateurs de composition qui permettent de modifier cette visiblité lors de l'étape de composition. \paragraph{Visibilité par défaut.} Avec les traits gelables, le développeur doit alors spécifier une visibilité par défaut pour chaque méthode. Ces opérateurs de visibilité sont équivalents à ceux que l'on trouve avec Java ou C++ par exemple. La sémantique de ces opérateurs de visibilité est la suivante : \begin{itemize} \item \textit{Private} : une méthode dite privée ne sera accessible qu'à l'intérieur du trait auquel elle appartient. C'est pourquoi, la méthode est liée au trait dès sa définition et n'est pas visible en dehors. Les autres méthodes qui réfèrent cette méthode appelleront toujours cette dernière, même s'il y a composition avec d'autres classes ou traits. \item \textit{Public} : une méthode dite publique est visible au niveau du compositeur et est liée tardivement, comme dans le modèle original des traits. La méthode peut être redéfinie dans l'élément compositeur et les appels à cette méthode depuis d'autres méthodes résulteront à l'appel de la méthode redéfinie. \end{itemize} \paragraph{Visibilité dynamique.} Là où les traits gelables se démarquent des fonctionnalités des langages proposant du contrôle de visibilité est qu'il est possible de modifier cette visiblité lors de la composition grâce à deux nouveaux opérateurs : \textit{freeze} et \textit{defrost}. Le premier change la visibilité d'une méthode publique à privée tandis que le second effectue l'opération inverse. La figure \ref{fig:freeze_defrost} illustre la sémantique de ces deux opérateurs : \begin{itemize} \item Sur (a), les deux méthodes publiques \textit{x} entrent en conflit. Pour éviter cette situation, le compositeur décide de geler le \textit{x} de \textit{T1}. Ainsi, \textit{T1 foo} devient précocément liée à \textit{T1 x}, ce qui signifie que c'est cette dernière qui sera toujours appelée. \item Avec (b), les deux méthodes publiques \textit{x} entrent aussi en conflit et le compositeur décide de geler les deux. Ainsi, l'invocation de \textit{x} depuis \textit{T1 foo} est liée à \textit{T1 x} et celui dans \textit{T2 bar} à \textit{T1 x}. \item Sur (c), les deux méthodes \textit{x} sont privées. Le compositeur décide de dégeler les deux méthodes \textit{x}. Ceci génère un conflit de composition qui est résolu en définissant une nouvelle méthode \textit{x} dans la classe \textit{Composer}. Ainsi, les invocations sont tardivement liées et appelleront donc la nouvelle méthode. \item Enfin, sur (d), la méthode \textit{T1 x} est privée tandis que \textit{T2 x} ne l'est pas. Le compositeur décide alors de geler \textit{T2 x} et de dégeler \textit{T1 x}. Ainsi, on se retrouve exactement dans le schéma inverse de (a). \end{itemize} \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/freeze_defrost.png} \caption{La sémantique des opérateurs freeze et defrost} \label{fig:freeze_defrost} \end{figure} \paragraph{Différentes vues.} Le fait que le compositeur décide de la visibilité finale des méthodes lors de composition implique qu'un même trait peut être vu de manière différente. Par exemple, la figure \ref{fig:diff_visib} illustre comment le trait \textit{TSyncReadWrite} peut être utilisé par deux classes, \textit{SyncStream} et \textit{SequenceableStream}. Dans les deux cas, les classes n'ont pas les mêmes éléments gelés et donc pas la même vue sur le trait. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/diff_views.png} \caption{Différentes vues d'un même trait} \label{fig:diff_visib} \end{figure} \subsection{Synthèse} \label{sec:synthese} Nous avons ici exposés les principales catégories de mécanismes de composition de comportement en programmation orientée-objet. Les types d'héritages basiques remontent aux débuts de l'orienté-objet mais perdurent toujours, même dans les langages actuels. En effet, ces mécanismes sont extrêmement éprouvés et les développeurs y sont grandement habitués. Cependant, ils ne sont pas exempts de défauts, comme nous avons pu le démontrer. Des deux modèles principaux (simple et multiple), les concepteurs de langages ont encore un choix cornélien à faire entre simplicité et expressivité. Des initiatives ayant pour but de résoudre ces concessions ont alors vu le jour, comme les Mixins. Ces derniers permettent de résoudre certains problèmes liés à l'héritage multiple, en autorisant des hiérarchies parallèles dans les langages à héritage simple, mais sont loin d'être réellement efficaces en pratiques. De plus, ils introduisent leur ensemble de défauts, ce qui implique une complexité non négligeable. D'autres propositions, comme les traits ont plus récemment fait leur apparition. Ils différent de leurs prédécesseurs dans le sens où les compositions peuvent être réellement contrôlées, ce qui permet d'éviter un nombre important de défauts lors de l'utilisation de l'héritage multiple. En effet, les traits prennent l'initiative de non pas remplacer l'opérateur d'héritage mais de venir le compléter avec d'autres opérations. Pour résumer, nous avons donc à notre disposition un panel d'outils intéressants nous permettant d'avoir plusieurs approches vis à vis de la composition de comportement. Cependant, les traits se démarquent des autres solutions dans le sens où nous atteignons un niveau d'expressivité idéal en échange d'une faible contrepartie. Ils se combinent de plus très élégamment avec les langages à héritage simple, ce qui en fait un élément idéal pour la composition de comportement. \section{Refactorisations autour des traits et des collections} \subsection{Interfaces and specifications for the Smalltalk-80 Collection Classes} \label{sec:interf-specs-st} Cette méthode de refactorisation~\cite{Cook92a} part du constat que les hiérarchies de classes doivent être utilisées dans un but structurel et dans un but d'amélioration de la compréhension de la bibliothèque. Ainsi, l'héritage est réellement un mécanisme de production qui n'a pas de rapport avec l'utilisation de ces classes par les clients. Le but est alors ici d'extraire des protocoles (= un ensemble de messages) plus intelligents à l'aide d'un programme qui prendra en compte tous les défauts de l'implantation existante. Ces protocoles seront compilés dans une hiérarchie. Les défauts pris en compte sont les suivants : méthodes annulées dans les sous-classes et méthodes supprimées dans les sous-classes. En effet, il est possible de trouver des méthodes comme la classe \textit{Interval}, qui ne permet pas d'ajouter un élément, mais qui pourtant dispose d'une méthode \textit{add} : \begin{lstlisting} add: newObject "Provide an error notification that adding to an Interval is not allowed" self shouldNotImplement \end{lstlisting} \paragraph{Hiérarchie de protocoles.} La méthode propose un outil qui permet d'extraire une hiérarchie d'interfaces. Cette dernière est une représentation partiellement ordonnée qui permet d'organiser les interfaces partagées entre les classes d'une bibliothèque. L'extraction est réalisée grâce à l'ordre partiel des protocoles en prenant en compte les relations de conformance. La conformance est définie par la règle suivante : \begin{quote} \textit{Une interface B se conforme à une interface A si chaque objet satisfiant B satisfait aussi A.} \end{quote} Par exemple, si nous avons : \begin{quote} \textbf{A} = \{ isEmpty, at: \}\\ \textbf{B} = \{ isEmpty, at:, add:, remove: \} \end{quote} Alors, \textbf{B} se conforme à \textbf{A} car les méthodes de \textbf{B} incluent les méthodes de \textbf{A}. Ceci signifie que les objets supportant les méthodes de \textbf{B} peuvent être substitués lorsqu'un objet de type \textbf{A} est requis. L'algorithme introduit aussi la notion de \textit{protocole abstrait} qui sont une représentation des messages partagés par deux protocoles. On va donc obtenir des représentations comme illustré sur la figure \ref{fig:hierar_is}. \begin{figure}[here] \centering \includegraphics[width=3cm]{figures/abstract_proto.png} \caption{Un exemple de hiérarchie de protocoles. Ici \textbf{X} et \textbf{Y} sont deux \textit{protocoles abstraits}.} \label{fig:hierar_is} \end{figure} Ces protocoles sont appelés abstraits car ils ne sont pas implantés explicitement par des classes. Cependant, ils s'avèrent très utiles pour faire ressortir les similitudes. \paragraph{Spécification des classes.} Une analyse plus poussée est alors utilisée pour réussir à appréhender plus finement les problèmes de conception. Il s'agit d'une analyse basée sur la spécification de comportement des classes et méthodes. Chaque méthode est alors aussi annotée avec des pre et post conditions comme l'ont fait les concepteurs des bibliothèques d'Eiffel. Ceci met en lumière les problèmes suivants : \begin{itemize} \item Des méthodes sont héritées alors qu'elles devraient être annulées car elles violent l'invariant des sous-classes ; \item Des classes utilisent des méthodes ayant le même nom à des fins différentes : des noms différents devraient être utilisés ; \item Deux méthodes ayant des noms différents peuvent en fait réaliser la même chose : elles devraient donc être fusionnées. \end{itemize} \paragraph{Résultats.} Le résultat de cette expérience est une hiérarchie d'interfaces très complexe (cf figure \ref{fig:result_is}), même si Smalltalk est pourtant un langage à héritage simple. Il est donc clair que la hiérarchie actuelle est très restrictive comparée à la granularité attendue des différentes classes. De plus, les concepts partagés sont souvent orthogonaux, d'où la difficulté de créer une hiérarchie avec de l'héritage simple. \begin{figure}[!here] \includegraphics[width=\linewidth]{figures/corrected_st80_col.png} \caption{Résultat de refactorisation par l'extraction d'interfaces} \label{fig:result_is} \end{figure} Aussi, un nombre d'erreurs ont pu être mises en évidences par la visualisation du graphe. Des opérations basiques ont ainsi été remontées dans la hiérarchie, la granularité s'est affinée pour améliorer la modularité (certains protocoles n'ont qu'un ou deux messages) et on voit l'apparition de protocoles abstraits (dus à la suppression des méthodes lors de l'héritage). Il est à noter aussi que la hiérarchie s'est rapprochée sur certains points de la structure de la bibliothèque d'Eiffel. Cependant, cette méthode a aussi montré que de nombreuses questions restent encore en suspend, même après la refactorisation. En effet, des incohérences conceptuelles se trouvent toujours facilement et un travail encore plus poussé serait nécessaire pour les effacer. De plus, la comparaison de l'arbre d'héritage avec la hiérarchie de protocoles met bien en évidence le fait qu'il y a une grande disparité entre les deux modèles et qu'il est techniquement impossible, avec l'héritage simple, de réussir à calquer l'un sur l'autre. \subsection{Applying Traits to the Smalltalk Collection classes} Ces travaux~\cite{Blac03a} ont été réalisés dans le cadre de la création du modèle des traits, dans un but de preuve d'efficacité de ces derniers. Ils proposent d'évaluer la hiérarchie de Collections de Smalltalk-80 à travers l'implantation Squeak et de la refactoriser à l'aider des traits sans état. Une description de cette hiérarchie est disponible dans la section \ref{sec:coll_st}. Les travaux caractérisent tout d'abord les problèmes de la hiérarchie pour ensuite proposer un modèle qui permet de les résoudre. \paragraph{Héritage inutile.} \label{sec:heritage-inutile} Tout d'abord, le nombre de chaînes d'héritages dans lesquelles une méthode est redéfinie au moins trois fois a été comptabilisé. Bien que le fait de redéfinir une méthode n'est pas un mal (le mécanisme d'héritage ayant été en parti créé pour ceci à la base), la plupart des utilisations de ce mécanismes ne font en fait pas appel à la super-classe. Ceci indique que ces classes ne paramétrisent pas une méthode plus générique mais corrigent en fait l'implantation, au lieu d'enrichir le comportement comme elles devraient le faire. Ainsi, 164 méthodes ont été identifiées et donc autant de cas où un héritage n'était pas nécessaire. Ceci n'est pas problématique en terme d'exécution mais indique une perte de temps lors du développement. En effet, l'héritage est considéré comme étant un mécanisme d'aide à la compréhension dans le sens où le programmeur n'a qu'à comprendre les différences entre un parent et sa classe fille pour saisir l'objectif de cette dernière. Si l'héritage est utilisé de manière incorrecte, il va donc remplir son rôle inverse : gêner la compréhension. \paragraph{Duplication de code.} \label{sec:duplication-de-code} Les travaux mettent aussi en avant des problèmes liés à la rigidité de l'héritage simple. En effet, dans certains cas, des classes aimeraient réutiliser des méthodes de classes existantes mais, à défaut, sont contraintes de dupliquer le code. C'est le cas par exemple de \textit{PluggableDictionary} et \textit{PluggableSet} qui partagent plusieurs méthodes ayant le même but, mais qui pourtant ne peuvent avoir un ancêtre commun. \textit{PluggableDictionary} est une sous-classe de \textit{Dictionary} et \textit{PluggableSet} est une sous-classe de \textit{Set}. Nous observons donc qu'il n'y a alors aucune possibilité d'ancêtre commun car \textit{Set} et \textit{Dictionary} n'ont pas de points communs. \paragraph{Défauts conceptuels.} \label{sec:defauts-conceptuels} L'auteur de cette publication met aussi en avant cinq défauts conceptuels majeurs : \begin{enumerate} \item Beaucoup de collections sont présentes dans la bibliothèque car les concepteurs ont essayé de compenser le fait que les classes sont difficiles à réutiliser en fournissant toutes les combinaisons possibles de fonctionnalités ; \item L'immutabilité n'est pas présente dans la hiérarchie des collections de Smalltalk-80 à l'exception de deux cas : \textit{Symbols} et \textit{Intervals}. Celle-ci pourrait pourtant être très utile dans de nombreux cas ; \item Des classes présentent des préoccupations très orthogonales (read/write, binary/text) qu'il n'est donc pas forcément évident de composer. Les combinaisons sont alors exprimées en dupliquant du code. De plus, toutes les combinaisons ne sont pas disponibles ; \item Certaines classes ne sont pas celles qui sont attendues (comme l'avait montré Cook~\cite{Cook92a}) car elles n'implantent pas toutes les méthodes ; \item Enfin, l'auteur souligne le fait qu'il existe des classes auquelles on souhaiterait donner un comportement de type collection, bien qu'elles n'en soient pas à première vue. Ca pourrait être le cas par exemple d'un Chemin qui représente une suite de points ; ce qu'on peut facilement associer à un type de collection. \end{enumerate} \paragraph{Résultats.} \label{sec:resultat} La refactorisation s'est concrétisée via 29 classes (dont 6 abstraites) et 52 traits. En moyenne, le nombre de traits utilisés pour construire une classe est de 5 ; le maximum étant 22. La hiérarchie résultante de ces travaux peut être consultée sur la figure \ref{fig:refact_apb}. \begin{figure}[!h] \centering \includegraphics[width=\linewidth]{figures/traits_coll_refact.png} \caption{Résultat de la refactorisation de la hiérarchie des collections de Smalltalk-80 avec les traits.} \label{fig:refact_apb} \end{figure} La méthode utilisée pour arriver à cette hiérarchie a consisté par tout d'abord refactoriser 13 classes concrètes. Cette phase a permis de mettre en place la structure basique des traits fonctionnels et des traits d'implantation ; totalisant 46 traits. \paragraph{Deux types de traits.} \label{sec:deux-types-de} Des traits fonctionnels et des traits d'implantations ont été utilisés pour réaliser la hiérarchie. Ces premiers sont la matérialisation des caractéristiques des collections de la hiérarchie originale (ex: être ordonné). Ainsi, il est possible de combiner ces traits pour obtenir la combinaison voulue. Ces combinaisons sont disponibles sous deux formes : des traits composites ou des super-classes destinées à être héritées. La granularité a été aussi fortement affinée, même si cela n'était pas forcément nécessaire, de manière à assurer une ouverture du système et rendre ces éléments aisément modifiables. Aussi, les auteurs insistent sur le fait que ceci rend la compréhensible de la hiérarchie plus simple. Afin d'identifier la nature de ces traits fonctionnels, ces derniers utilisent une convention de nommage où sont suffixées les lettres \textit{S}, \textit{U}, \textit{M} ou \textit{I}. \textit{S} ou \textit{U} indique que l'implantation doit être respectivement séquencielle ou non ; \textit{M} indique la mutabilité, \textit{I} l'inverse. Les traits d'implantation quant à eux combinent les différentes fonctionnalités des traits fonctionnels avec les implantations compatibles (par exemple, une version implanté avec des vecteurs). Ainsi, par exemple, le comportement pour créer des nouvelles instances sera collecté dans un trait nommé \textit{TInstanceCreationImpl} et sera utilisé par \textit{TOrderedImpl} et d'autres traits d'implantation. L'utilisation conjointe de ces deux types de traits est donnée en exemple sur la figure \ref{fig:impl_func_traits} \begin{figure}[here] \centering \includegraphics[width=5cm]{figures/func_impl_traits.png} \caption{Un exemple d'utilisation conjointe des traits fonctionnels et d'implantation.} \label{fig:impl_func_traits} \end{figure} Enfin, les auteurs en concluent que les traits simplifient grandement la refactorisation et que les outils sont importants. En effet, ils ont remarqué que les outils de Smalltalk les ont aidé dans la démarche de refactorisation et que le fait d'avoir développé une extension de ces outils étant capables de comprendre les traits leur a aussi été bénéfique. \subsection{Nile} Bien que Nile~\cite{Cass07a} ne soit pas un travail autour des collections, il est intéressant d'étudier la réalisation de cette bibliothèque. Nile est le résultat du travail d'une reconception de la bibliothèque des streams à l'aide des traits sans état. Le but de ces travaux était d'évaluer à quel niveau les traits permettent la réutilisation de code mais surtout d'étudier les problèmes émergents lors de la conception d'une nouvelle bibliothèque avec les traits. \paragraph{Identification des problèmes.} A travers l'analyse de l'ancienne hiérarchie de streams, l'auteur met en avant plusieurs défauts de conception liés à l'utilisation de l'héritage simple. En voici les principaux : \begin{itemize} \item \textbf{Méthodes implantées trop hautes} : une technique répandue permettant d'éviter la duplication de code est d'implanter des méthodes dans la super-classe commune aux classes qui nécessitent cet élément. Cependant, cette technique pollue les interfaces car certaines classes qui héritent de cette super-classe (souvent indirectement) n'ont pas besoin de ces méthodes. Nous aurons alors des méthodes annulées ; \item \textbf{État de super-classe inutilisé} : Dans certains cas, il arrive que des classes qui héritent d'une super-classe ne fassent jamais référence à l'état de cette dernière. Ceci n'est pas en soit un problème mais peut indiquer que la sous-classe n'utilise pas le code fournit par sa classe mère ; \item \textbf{Simulation d'héritage multiple} : Même avec les langages à héritage simple, il est fréquent d'avoir besoin de mélanger plusieurs concepts orthogonaux afin de composer une nouvelle classe. Dans ce cas de figure, la seule solution est la duplication de code pour simuler cet héritage multiple car les classes ne partagent pas la même hiérarchie. \end{itemize} Bien que ces problèmes soient mis en avant par l'analyse des streams, on peut tout à fait les généraliser à la plupart des bibliothèques existantes, dont les collections. \paragraph{Nile, le résultat.} Nile propose un ensemble de traits formant le noyau de la bibliothèque. Les auteurs se sont basés sur le standard Smalltalk-ANSI pour ce noyau. Il consiste en six traits, comme l'illustre la figure \ref{fig:nile-core}. \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/nile-core.pdf} \caption{Les six traits composant le noyau de Nile.} \label{fig:nile-core} \end{figure} Un premier trait, \textit{TStream} permet de regrouper toutes les fonctionnalités communes aux streams. La hiérarchie est ensuite divisée selon les éléments nécessitant une lecture (\textit{TGettableStream}) ou une écriture (\textit{TPuttableStream}). On notera aussi que les auteurs ont différencié le cas des streams nécessitant un positionnement absolu (\textit{TPositionableStream}). Les traits les plus bas de la hiérarchie permettent principalement de combiner les fonctionnalités précédemment citées. Nile construit ensuite son implantation des streams autour de ce noyau, mais nous estimons que leur analyse n'est pas pertinente dans le cadre de notre étude car spécifique aux streams. \paragraph{Preuve de modularité.} Afin de démontrer la modularité introduite grâce aux traits, les auteurs ont implanté deux bibliothèques supplémentaires à l'aide du noyau de Nile. La première permet de gérer un historique (telle que celui trouvé dans les navigateurs web), tandis que la seconde réimplante la bibliothèque originale de Smalltalk afin de rendre Nile rétro-compatible. \paragraph{Évaluation des traits.} Le choix de la granularité des traits s'est faite de manière intuitive en gardant en tête que les traits ne doivent pas être de trop fine granularité et que leur but n'est pas seulement de grouper des méthodes. Ainsi, des abstractions cohérentes, regroupées par trait, sont proposées. Le fait d'avoir identifié les concepts orthogonaux et de grouper les autres permet d'obtenir de bonnes combinaisons et donc de maximiser la réutilisabilité. Une discussion intéressante menée au cours de ces travaux est la suivante : quelle décision doit-on prendre entre la création d'une classe et l'ajout d'un ensemble de traits ? L'auteur en déduit qu'un bonne manière de décider est de se poser la question suivante : \og est-ce que les futurs clients auront besoin de bénéficier de ces fonctionnalités ? \fg. Si oui, il faudra alors privilégier la création de traits. Les traits ont permis une réduction de 40\% de code ainsi que la suppression des problèmes d'annulations de méthodes. Il faut aussi noter que la nouvelle hiérarchie de streams a été évaluée en terme de performance et qu'aucune perte de vitesse n'a été constatée. Ceci démontre donc bien que les traits permettent une décomposition idéale et naturelle d'une hiérarchie de classes, tout en assurant un maintient des performances originales. \subsection{Synthèse} \label{sec:synthese-refact} Les deux refactorisations effectuées avec les traits ont permis de montrer qu'ils sont des éléments idéaux pour modulariser une hiérarchie. En effet, la duplication de code a été supprimée, l'annulation de méthodes a été écartée et les possibilités de composition ont été étendues. Le gain d'expressivité de composition est beaucoup plus important pour Nile que pour la première refactorisation des collections. En effet, avec Nile, la refactorisation s'est faite de manière moins systématique, ce qui a résulté d'une hiérarchie beaucoup plus extensible. On peut voir aussi que la manière d'utiliser les traits a évolué au cours du temps : les refactorisations récentes ont plus de recul sur la manière d'utiliser les traits pour refactoriser une hiérarchie. La première refactorisation des collections a permis de mettre en avant les problèmes de conceptions (méthodes annulées, implantées trop hautes, ...) des hiérarchies. Nile confirme ces problèmes avec son analyse des streams bien qu'il s'intéresse plutôt à trouver un design intéressant et évolutif plutôt de recréer l'existant avec les traits. A ce propos, Nile a commencé à s'intéresser à la cohérence avec la hiérarchie de protocoles de Smalltalk-ANSI. Quant à Cook, il tente par ses travaux d'améliorer ces protocoles afin de les rendre plus proches de la réalité d'implantation. Il regrette d'ailleurs de ne pas disposer de plus d'expressivité au niveau de l'héritage afin de pouvoir encore mieux rapprocher l'implantation. Dans ces analyses, il a donc été très intéressant de voir comment les traits peuvent être habillement utilisés pour résoudre les problèmes habituels. De plus, il est clair que les traits peuvent apporter un complément très intéressant aux propositions qui, au moment de leur écriture, ne pouvaient pas tirer parti d'un tel mécanisme. \chapter{Analyse des bibliothèques de collections existantes} Cette chapitre propose tout d'abord de présenter les Collections de manière générale puis d'analyser deux cas concrets d'implantation des collections : Java puis Smalltalk. Ensuite, nous rapprochons ces deux implantations afin d'en faire ressortir les éléments communs et divergents. Enfin, nous conclurons en synthétisant les bonnes propriétés et nous caractériserons les problèmes posés par les collections afin de pouvoir mieux appréhender la difficulté. \section{Analyse des Collections} \label{sect:ana-coll} On peut définir les collections comme un ensemble de structures de données permettant le groupement et la manipulation d'éléments. Avoir à disposition une bibliothèque de Collections dans un langage est essentiel et procure de nombreux avantages pour le développement d'applications. Tout d'abord, ceci permet d'éviter la duplication de code dans le sens où les Collections sont très souvent utilisées. Nous évitons donc que chaque développeur réécrive sa propre implantation. Ensuite, les Collections proposent un ensemble cohérent de classes, ce qui permet : \begin{itemize} \item Une réduction du temps d'apprentissage de la part du programmeur ; \item Une réduction du temps d'implantation de nouvelles structures, par réutilisation des briques de base existantes ; \item Une flexibilité des programmes, dans le sens où le programmeur peut aisément changer les structures de données utilisées sans effets de bords (et ainsi tester et améliorer les performances du programme). \end{itemize} Enfin, chaque implantation permet de capitaliser les connaissances du domaine et donc de fournir une version hautement optimisée et exempte de bogues. Aussi, on trouve une variété importante de structures dans les Collections. En effet, chaque collection est propre à son cas d'utilisation et n'offre pas les mêmes propriétés à la fois sur le plan ensembliste que sur les aspects de performance. On peut par ailleurs catégoriser les principaux types de collections comme suit. \subsection{Les classes de collections} \label{sec:classes_coll} Dans cette section, nous présenterons un panorama des classes de Collections existantes. Cette présentation ne se veut pas exhaustive, mais représentative de la diversité des Collections usuelles. \paragraph{Sets.} Les \textit{Sets} sont des ensembles non ordonnés où chaque élément est unique. Ils sont une implantation directe des ensembles mathématiques. Nous pouvons le définir comme suit : \medskip Soit $S$ un Set, $a$ un élément\\ \textit{Invariant} : $\forall a \in S$, $\not \exists b \in S\setminus a$ t.q. $b = a$ \medskip Ils sont idéaux pour donner un accès rapide aux données et fournissent des opérations utiles telles que l'union, l'intersection, etc... Les \textit{Sets} peuvent être implantés de diverses manières : \begin{enumerate} \item Un arbre binaire équilibré, conférant une complexité $O(n)$ pour la plupart des opérations ; \item Une table de Hachage, travaillant dans le pire des cas en $O(n)$ ; \item Un tableau, utilisant une implantation simple et travaillant en $O(n)$. \end{enumerate} \paragraph{Bags.} Les \textit{Bags}, ou \textit{Multisets} se comportent comme les \textit{Sets} à l'exception qu'ils peuvent accueillir plusieurs fois le même élément. On les définit comme les Sets, à l'exception de la condition d'unicité. On obtient de ces \emph{Bags} la notion de multiplicité (le nombre d'occurrences d'un élément). \paragraph{Lists.} Les listes sont des collections de données où l'ordre des éléments est significatif Avec cette structure, il est possible d'accéder aux éléments par index, de les parcourir dans l'ordre croissant/décroissant d'index, d'insérer ou de supprimer des éléments ou encore de mettre à jour un de ces derniers. Les deux implantations courantes sont sous forme de listes chaînées ou sous forme de tableaux à taille variable. Dans le premier cas, les éléments sont généralement accessible en temps $O(n)$ tandis que dans le second, nous obtenons une complexité en $O(1)$. \paragraph{Arrays.} Les tableaux sont des structures de données de taille fixe. Leurs éléments sont indexables par des entiers et sont donc ordonnés. Ceci n'implique pas nécessairement qu'ils sont triés. Les tableaux sont très répandus dans les langages et sont donc extrêmement utilisés par les programmeurs. Pour la plupart des implémentations, on accède les éléments en temps constant, c'est à dire en $O(1)$. \paragraph{Graphs.} Le graphe est une structure de données non-hiérarchique, directement associée à la notion de graphe mathématique. Cette structure, bien que peu courante dans la plupart des langages généraux, reste très intéressante. Un graphe est composé d'un ensemble de noeuds reliés par des arêtes qui établissent des relations entre ces premiers. On les définit comme suit : \medskip Soit $G$ un graphe, $V$ l'ensemble des sommets, $E$ l'ensemble des arêtes. $G = (V, E, \varphi)$ où $\varphi$ est une fonction $\phi : E \rightarrow V \times V$ \medskip Ces structures sont parfaitement adaptées pour représenter des données qui sont interconnectées de manière complexe entre elles. On réalise souvent des opérations comme trouver un lien entre deux noeuds ou trouver la distance la plus courte d'un point à un autre à l'aide d'algorithmes comme celui de Dijkstra. Encore une fois, cette structure peut être implantée de différentes manières : une liste d'adjacence ou encore une matrice d'adjacence. \paragraph{Trees.} Les arbres sont une spécialisation des graphes dans le sens où ce sont des graphes acycliques connexes. Il est aussi communément admis que leurs arêtes ne doivent pas être dirigées ni se voir affecter des poids. On considère qu'il y a un noeud primaire, appelé ``racine'' et des noeuds terminaux, appelés ``feuilles'', en analogie avec les végétaux. On effectue des opérations comme le parcours pre ou post fixé, la recherche d'éléments ou encore la section d'une branche. Cependant, bien qu'ils soient directement une spécialisation des graphes, on notera que les structures de données utilisées pour représenter ces premiers ne sont pas du tout les mêmes que celles utilisées pour les graphes. La plupart des implantations utilisent des structures comme un ``\textit{Binary Space partitionning}'', une pile ou encore des tableaux. \subsection{Les collections en Java} Cette section propose de présenter rapidement les Collections en Java. Bien que les travaux de ce rapport ne portent pas sur le langage Java, nous avons jugés intéressant d'analyser d'autres bibliothèques afin de pouvoir évaluer différentes implantations de Collections. Il existe par ailleurs plusieurs implantations de Collections en Java. Nous nous focaliserons sur l'implantation officielle, c'est-à-dire celle inclue avec Java 5.0 : le \textit{Java Collections Framework}\footnote{http://java.sun.com/j2se/1.5.0/docs/guide/collections/} (JCF). Le JCF a été conçu avec deux objectifs principaux : une taille assez réduite ainsi qu'une prise en main rapide pour le programmeur. Ainsi, les Collections du JCF essaient de n'implanter que les méthodes les plus nécessaires, soit parce qu'elles sont essentielles, soit parce qu'elles permettent d'améliorer considérablement les performances. Cependant, la plupart des structures de données citées dans la section précédente sont proposées par le JCF ; à l'exception des structures très spécialisées comme les Graphes. Enfin, le JCF permet d'assurer que les différentes collections puissent travailler ensemble efficacement. \paragraph{Organisation et composition.} La figure \ref{fig:java_coll} présente la partie essentielle de la hiérarchie du \textit{Java Collections Framework}. Seules 9 interfaces composent le noyau des Collections, parmi lesquelles on retrouve \textit{Set}, \textit{List} ou encore \textit{Queue}. On peut remarquer que les \textit{Map}s ne sont pas considérées comme des \textit{Collection}s. En effet, les auteurs l'expliquent par le fait qu'ils considèrent qu'il s'agit de deux concepts orthogonaux : \begin{quote} \textit{ ``This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa).''} -- Java Collections API Design FAQ\footnote{http://java.sun.com/j2se/1.5.0/docs/guide/collections/designfaq.html}. \end{quote} On dispose ainsi de deux racines, \textit{Collection} et \textit{Map}, qui forment les Collections à elles deux. Le \textit{JCF} permet alors la conversion de l'un à l'autre sous forme de vues. Il est donc possible d'utiliser les \textit{Collection}s en tant que \textit{Map}s et inversement. \begin{figure}[here] \centering \includegraphics[width=12cm]{figures/java_col.png} \caption{Hiérarchie des Collections en Java 5} \label{fig:java_coll} \end{figure} Enfin, le framework est principalement composé des éléments suivants : \begin{itemize} \item \textbf{Interfaces} : Le noyau du framework, représentant les types usuels ; \item \textbf{General Purpose implementations} : les implémentations génériques, réutilisables ; \item \textbf{Legacy implementations} : Les implantations de compatibilité avec les anciennes versions de Java ; \item \textbf{Concurrent implementations} : Des implantations spécifiques, dédiées à être accédées de manière hautement concurrentes ; \item \textbf{Wrapper implementations} : des implantations permettant d'ajouter des fonctionnalités, comme la synchronisation ou d'autres responsabilités ; \item \textbf{Algorithms} : Un ensemble de méthodes statiques permettant de réaliser des opérations tel que le tri ; \end{itemize} Ces implantations sont réalisées en fonctions des interfaces précédemment décrites. La figure \ref{fig:impl_itf_java} indique comment les interfaces usuelles sont utilisées. %[\textbf{FIXME}(Alex): Introduire la figure \ref{fig:impl_itf_java}] \begin{figure}[here] \centering \begin{tabular}{|l|c|c|c|c|c|c|} \hline \backslashbox{Itf}{Impl} & HashTable & ResizableArray& BalancedTree & LinkedList& HashT.+LL. \\ \hline Set& HashSet& $\emptyset$ & TreeSet& $\emptyset$ & LinkedHashSet \\ \hline List& $\emptyset$ & ArrayList& $\emptyset$ & LinkedList & $\emptyset$ \\ \hline Map& HashMap & $\emptyset$ & TreeMap & $\emptyset$ & LinkedHashMap \\ \hline \end{tabular} \caption{Utilisation des interfaces dans les implantations usuelles. A la verticale, les interfaces ; à l'horizontale, les implantations.} \label{fig:impl_itf_java} \end{figure} \paragraph{Opérations non supportées.} Le nombre d'interfaces du noyau étant volontairement assez réduit (dans le sens où il n'essaye pas de capturer tous les besoins), les développeurs ont donc choisi de proposer des méthodes optionnelles. Avec ces méthodes optionnelles, il est possible de générer une \textit{UnsupportedOperationException} permettant d'indiquer que l'implémentation ne supporte pas cette opération. La figure \ref{fig:java_colitf} décrit en UML les opérations possibles sur l'interface \og Collection\fg, racine de la hiérarchie. On peut clairement remarquer que toutes les opérations ne pourront pas être supportées dans tous les cas. \begin{figure}[here] \centering \includegraphics[width=5cm]{figures/colljava.pdf} \caption{L'interface Collection de Java 5. Des méthodes comme ``add'' seront annulées dans certains cas.} \label{fig:java_colitf} \end{figure} Comme la spécification est alors faite au niveau de la documentation, vu qu'il faut indiquer quelles sont les opérations implantées, on classifie alors les types de Collections selon les termes suivants : \begin{itemize} \item \textbf{Unmodifiable} : Les Collections qui ne peuvent pas changer ; \item \textbf{Immutable} : Ceci indique qu'en plus d'être non modifiable, l'état des objets de la Collection ne changera pas ; \item \textbf{Fixed-size} : Les Collections qui ont une taille fixe ; \item \textbf{Random Access} : On regroupe sous ce terme les Collections qui ont un temps d'accès rapide (i.e. en temps constant). Ceci permet aux algorithmes de pouvoir s'adapter en fonction du type de Collection à traiter. \end{itemize} \paragraph{Le cas des tableaux.} Une des spécificité de Java est de ne pas proposer de type \textit{Array} dans sa bibliothèque de Collections. Cela s'explique par le fait que les tableaux se trouvent dans le langage (sous forme d'un type primitif) depuis le début et qu'il est donc impossible de les déplacer dans le \textit{JCF}. Ceci casse bien entendu le contrat de compatibilité entre les différentes classes du \textit{JCF} ; c'est pourquoi ce framework propose une classe utilitaire, appelée ``Arrays'' qui permet de transformer les tableaux natifs Java en Listes. \paragraph{Découplage.} Afin de contourner les problèmes de couplage fort à cause du typage statique, le \textit{JCF} propose la notion d'\textit{Iterator}. Ceci permet d'obtenir un couplage faible et donc de pouvoir changer rapidement d'implantation de Collection. Voici un exemple d'utilisation : \begin{lstlisting} Collection list; Iterator elements = list.iterator(); while (elements.hasNext() ) System.out.println( elements.next() ); \end{lstlisting} Ainsi, dans ce code, nous pourrions avoir n'importe quel type de Collection au niveau de \og list\fg : nous ne sommes donc plus couplés à un type particulier. \medskip Un tour d'horizon plus détaillé du \textit{Java Colletions Framework} peut être obtenu sur le site officiel de Java\footnote{http://java.sun.com/j2se/1.5.0/docs/guide/collections/overview.html}. \subsection{Les collections en Smalltalk} \label{sec:coll_st} En Smalltalk-80, les classes de collections désignent à la fois un ensemble de \og Collections\fg et de \og Streams\fg. Dans le cadre de ce mémoire, nous ne nous intéresserons qu'aux \og Collections\fg. On se référera à l'analyse de Damien Cassou dans Nile~\cite{Cass07a} en ce qui concerne les \og Streams\fg. Bien que le standard Smalltalk-80 définisse 17 classes pour Smalltalk, Squeak a été enrichi au cours des années et compte actuellement plus de 98 classes. Ces 28 classes originelles ont été maintes fois refactorisées jusqu'à obtenir le standard cité. On les considère d'ailleurs aujourd'hui comme un exemple de design orienté-objet. Cependant, parmi les 98 classes de Squeak, beaucoup sont en fait des spécialisations (Bitmap par exemple). Il est possible de réduire le coeur de ces dernières à un total de 37 classes qui ne répondent à pas moins de 800 messages et définissent plus de 1000 méthodes. Dans ces classes essentielles, on compte un certain nombre de classes abstraites, avec notamment \textit{Collection}, \textit{SequenceableCollection}, \textit{ArrayedCollection} et \textit{Integer Array}. Ainsi, les Collections de Squeak sont donc actuellement très riches comme le décrit la figure \ref{fig:hierar_col_squeak}. Il est possible d'extraire les classes les plus fondamentales pour obtenir l'arbre représenté sur la figure \ref{fig:fund_col_squeak}. \begin{figure}[h] \centering \includegraphics[width=\linewidth]{figures/CollectionHierarchy.pdf} \caption{Organisation des collections clés dans Squeak} \label{fig:fund_col_squeak} \end{figure} \begin{figure} \centering \includegraphics[width=9cm]{figures/CollectionHierarchyList.pdf} \caption{Listing des collections de Squeak. L'indentation indique un sous-classage tandis que l'italique signifie qu'il s'agit d'une classe abstraite.} \label{fig:hierar_col_squeak} \end{figure} \paragraph{Les opérations itératives.} Suivant son héritage, Smalltalk a donc été inspiré par des langages comme Lisp. C'est pourquoi, les Collections ont été pensées pour être utilisées dans cet esprit. On ne va donc par exemple pas parcourir ces collections sous forme de boucles ; l'utilisation d'opérations comme \og map\fg ou \og apply\fg seront privilégiées. Suivant cette idée, nous allons ainsi trouver des messages comme \og select\fg ou \og collect\fg qui permettent d'exprimer efficacement des opérations sur l'ensemble d'une Collection. Voici un exemple qui sélectionne tous les éléments ayant un prix inférieur à 10 dans la Collection \textit{aCollection} : \begin{lstlisting} aCollection select: [ :anItem | anItem price < 10 ] \end{lstlisting} Au delà de la concision, ceci permet aussi d'exprimer une requête uniforme. En effet, il n'est pas nécessaire de connaître l'implantation sous-jacente : ceci fonctionnerait aussi bien sur une \textit{LinkedList} qu'un \textit{Array} dû au fait que toutes les sous-classes de \textit{Collection} comprennent le message \og select\fg. \paragraph{Les protocoles.} Afin de tirer parti de la puissance de cette uniformité, il est donc nécessaire que toutes les Collections définissent les mêmes messages. C'est ainsi que l'utilisation des protocoles permet d'assurer que si nous manipulons une Collection, alors nous disposons d'un ensemble de fonctionnalités de-facto. On sait donc qu'un objet d'une collection va forcément être testable (\og isEmpty\fg par exemple) ou encore donner la possibilité d'accéder à leurs propriétés (méthode \og size\fg). La plupart des protocoles des Collections de Smalltalk est regroupé dans la figure \ref{fig:col_st_protocols}. Les méthodes définies dans ces protocoles sont alors définies, redéfinies ou encore optimisées selon les implantations nécessaires. Il est à noter qu'elles sont parfois aussi annulées lors de sous-classages. %:FIGURE -- Standard collection protocols \begin{figure} \begin{center} \begin{tabular}{|l|p{10cm}|} \hline {\bf Protocole} & {\bf Méthodes}\\ \hline \textit{accessing} & size, capacity, at: \emph{anIndex}, at: \emph{anIndex} put: \emph{anElement} \\ \hline \textit{testing} & isEmpty, includes: \emph{anElement}, contains: \emph{aBlock}, \\ & occurrencesOf: \emph{anElement} \\ \hline \textit{adding} & add: \emph{anElement}, addAll: \emph{aCollection} \\ \hline \textit{removing} & remove: \emph{anElement}, remove: \emph{anElement} ifAbsent: \emph{aBlock}, removeAll: \emph{aCollection} \\ \hline \textit{enumerating} & do: \emph{aBlock}, collect: \emph{aBlock}, select: \emph{aBlock}, reject: \emph{aBlock}, detect: \emph{aBlock}, detect: \emph{aBlock} ifNone: \emph{aNoneBlock}, \\ & inject: \emph{aValue} into: \emph{aBinaryBlock} \\ \hline \textit{converting} & asBag, asSet, asOrderedCollection, asSortedCollection, \\ & asArray, asSortedCollection: \emph{aBlock} \\ \hline \textit{creation} & with: \emph{anElement}, with:with:, with:with:with:, \\ & with:with:with:with:, withAll: \emph{aCollection} \\ \hline \end{tabular} \caption{Quelques protocoles standards des Collections \label{fig:col_st_protocols}} \end{center} \end{figure} \paragraph{Cohérence.} Smalltalk propose une grande cohérence que ce soit au niveau de son langage ou de ses bibliothèques. Les Collections n'échappent pas à la règle. Tout d'abord, les méthodes de créations restent les mêmes quelle que soit la nature de la Collection. Nous en disposons de quatre : \begin{enumerate} \item utilisation d'une collection constante. Ce sont des collections disponibles dans tout le système et accessibles depuis n'importe quel endroit ; \item création par copie ; \item conversion depuis une autre collection ; \item création explicite. \end{enumerate} \paragraph{Uniformité apparente.} Bien que les Collections suivent les mêmes protocoles, l'uniformité n'est qu'apparente. En effet, les classes de Collections peuvent n'implanter que certains protocoles ou, comme indiqué sur la figure \ref{fig:byimpl_st}, être implantées à l'aide de diverses structures et donc exposer des codes métiers différents. \begin{figure}[here] \centering \includegraphics[width=12cm]{figures/CollectionsByImpl.pdf} \caption{Des exemples de classes réparties selon leur implantation} \label{fig:byimpl_st} \end{figure} Voici une liste des critères sur lesquels nous pouvons différencier les sous-classes de \textit{Collection} : \begin{itemize} \item \textbf{Séquencialité} : Bien que toutes les sous-classes de \textit{SequenceableCollection} traitent leurs éléments dans un ordre défini, les classes \textbf{Set}, \textbf{Bag} et \textbf{Dictionary} n'ont pas de notion de suite. Ces deux types de classes sont synthétisées dans la figure \ref{fig:suite_st} ; \begin{figure}[here] \centering \includegraphics[width=12cm]{figures/CollectionsBySeq.pdf} \caption{Critère de séquencialité des classes de collections de Smalltalk.} \label{fig:suite_st} \end{figure} \item \textbf{Triable} : Seules certaines Collections maintiennent un ordre particulier, défini par l'utilisateur, au sein de leurs éléments ; \item \textbf{Indexable} : Certaines Collections, comme les \textit{Array}s sont indexables, c'est à dire qu'ils est possible de référencer leurs éléments via un index (i.e., un entier). Des structures telles que \textit{LinkedList} ne permettent pas ce genre d'accès ; \item \textbf{Accesible par clé} : Seuls \textit{Dictionary} et ses sous-classes sont accessibles via une clé ; \item \textbf{Modifiable} : Toutes les Collections ne sont pas modifiables, bien que la plupart le soit. \textit{Symbol} ou \textit{Interval} ne le sont pas par exemple. \item \textbf{Taille variable} : Les collections telles que \textit{Array} sont de taille fixe, il n'est donc pas possible de changer le nombre d'éléments au cours du temps sans recréer une nouvelle instance. D'autres sont capables de s'adapter à la demande ; \item \textbf{Multiplicité} : Il est possible que certaines collections acceptent des éléments dupliqués alors que d'autres non (respectivement \textit{Bag} et \textit{Set}) ; \item \textbf{Hétérogénéité} : La plupart des Collections vont pouvoir comporter des éléments de nature différentes. D'autres, telles que \textit{String}, ne pourront quant à elles comporter que des \textit{Character}s. \end{itemize} Pour plus de précisions, on se référera aux chapitres \og Collections\fg des livres \og Squeak by Example\fg~\cite{Blac07a} et \og Inside Smalltalk : Volume 1\fg~\cite{LaLo90a}. \section{Synthèse et identification des problèmes} Le but de cette section est de synthétiser les informations autour des collections afin i/ d'extraire les problèmes auxquels nous devrons faire face et ii/ d'extraire des modèles existants les bonnes et mauvaises pratiques. Nous commençons, dans un premier temps, par énoncer les généralités conceptuelles des collections. Dans un second temps, nous rapprochons nos deux cas d'étude, à savoir Java et Smalltalk puis nous terminons par exposer les différences fondamentales de leurs deux hiérarchies de collections. \subsection{Généralités conceptuelles} \label{sec:gener-conc} \paragraph{Hétérogénéité de classes.} \label{sec:un-grand-nombre} Une des propriétés remarquables des collections est que les classes partagent un rôle semblable, c'est à dire maintenir un ensemble d'éléments, mais qu'elles sont très diversifiées quant à leur manière de le faire. Nous avons donc très souvent affaire à de nombreuses classes différentes. Ces classes combinent et partagent cependant de nombreuses caractéristiques, comme la séquencialité ou encore l'ordre. Il est aussi à noter que ces classes de collections peuvent très souvent être implantées à l'aide de plusieurs structures de données. L'hétérogénéité est donc elle aussi présente au niveau de l'implantation. \paragraph{Utilisation cohérente.} Bien que nous ayons un grand nombre de disparités dans les classes, une bibliothèque de collections essaye toujours de masquer au maximum ces différences aux yeux de l'utilisateur. Tout d'abord, ceci apporte une manière cohérente de manipuler ces classes, réduisant ainsi le temps d'apprentissage. Ensuite, disposer d'interfaces consistantes permet d'assurer un bon polymorphisme au sein du système. Il est donc alors possible d'écrire plus facilement du code générique et d'améliorer l'évolutivité des programmes. \subsection{Similitudes} \label{sec:similitudes} Bien que Java et Smalltalk soient deux langages assez éloignés, il est intéressant d'analyser les similitudes qu'ils présentent au niveau de leurs bibliothèques de collections. \paragraph{Caractéristiques similaires.} \label{sec:propr-simil} Les collections, au delà de leurs implantations, exposent très souvent des caractéristiques similaires qui peuvent être catégorisées. A l'exception de quelques catégories, nous avons pu assimiler les notions de Smalltalk à celles de Java assez facilement. Il en résulte donc que les caractéristiques attendues de la part d'une bibliothèque de collections, bien que nombreuses, semblent faire consensus. \paragraph{Annulation de méthodes.} \label{sec:annul-de-meth} Un défaut commun des deux bibliothèques que nous pouvons relever est l'annulation de méthodes (le terme \og méthodes optionnelles\fg est utilisé en Java) . Ceci est dû au fait que les deux langages utilisent l'héritage simple. A cause de cette contrainte, les concepteurs ont du remonter des méthodes dans la hiérarchie de classes afin d'éviter la duplication de code et rendre l'ensemble plus polymorphique. Cependant, annuler une méthode n'est pas anodin : l'interface affichée par la classe n'est plus représentative des fonctionnalités qu'elle fournit. \subsection{Divergences} \label{sec:differences} De part leur nature différente, il est évident aussi que les bibliothèques de Java et Smalltalk proposent des hiérarchies ayant des différences notoires. Nous exposons ici ces différences et évaluons les deux implantions le cas échéant. \paragraph{Unicité de hiérarchie.} \label{sec:unic-de-hier} Java a pris la décision de diviser la hiérarchie des collections en deux : nous avons alors une racine pour les \og maps\fg et une pour les autres collections. La justification apportée par les concepteurs reste assez floue, même si on peut la comprendre en partie. Il est possible de faire le parallèle avec l'opération d'itération de Smalltalk, \#do:. Comment celle-ci doit-il réagir lorsqu'il s'agit d'une map ? Doit-on parcourir les clés, les valeurs ou le couple des deux ? Java propose alors des conversions à l'aide de vues afin de résoudre le problème de polymorphisme. Avoir une seule hiérarchie permet cependant de garder un système homogène. \paragraph{Caractéristiques spécifiques.} \label{sec:caract-spec} Java propose des caractéristiques qui ne sont pas disponibles dans Smalltalk comme par exemple, \og Immutable\fg. Cette propriété est intéressante, mais très difficile à fournir, surtout dans un système hautement réflexif comme Smalltalk. Java résout ce problème en proposant une vue. Java propose aussi des implantations spécifiées, comme des versions des collections hautement concurrentes. \paragraph{Types primitifs.} \label{sec:types-primitifs} Java propose des types primitifs pour certaines de ses collections. Ainsi que le type \og Array\fg n'entre pas dans la hiérarchie des collections. Ceci a le double désavantage de ne pas pouvoir profiter des propriétés polymorphiques ni de pouvoir le manipuler en tant qu'objet. Pour apporter une solution à ce dernier point, les concepteurs ont introduit une classe utilitaire permettant de manipuler les tableaux à travers des méthodes statiques. Cependant, ces classes utilitaires ont du mal à trouver leur place au sein de la hiérarchie des collections et il s'agit ici clairement d'un défaut de conception à éviter. \paragraph{Protocoles.} Smalltalk, contrairement à Java, définit une hiérarchie de protocoles en plus de sa hiérarchie de classes. Ceci permet de standardiser le comportement des méthodes et de clairement définir les caractéristiques. Ces protocoles sont définis dans la norme ANSI. \paragraph{Iterators.} \label{sec:iterators} Une grande différence au niveau des classes de collections entre Java et Smalltalk est que le polymorphisme en Java est assuré au travers des itérateurs. Smalltalk, lui, utilise les messages de type \#do: comme structures de contrôle. C'est pourquoi, l'approche est ici radicalement différente. Cependant, les itérateurs ont le défaut de violer l'encapsulation car ils accèdent directement aux objets de la collection. \subsection{Conclusion} \label{sec:conclusion} De part cette analyse, nous pouvons déduire qu'une bonne hiérarchie de collections assure un polymorphisme généralisé, une bonne capacité d'expression vis à vis de la combinaison des caractéristiques et s'assure de minimiser le nombre de concepts. Ceci doit se réaliser en évitant tout d'abord les problèmes singuliers à l'héritage simple (annulation, duplication) ; en prenant en compte l'orthogonalité des caractéristiques et enfin ; en assurant une prise en compte de l'hétérogénéité des structures de données. \chapter{Des traits-protocoles pour les Collections} \section{Une hiérarchie complexe et hétérogène} Notre travail consiste donc à proposer une hiérarchie de collections idéale à base de traits en s'appuyant sur les collections de Smalltalk-80 ainsi que d'évaluer les traits lors de ce processus de refactorisation. \paragraph{Protocoles.} Comme nous l'avons précédemment expliqué, les collections sont des structures qui nécessitent très souvent d'utiliser et de composer des concepts orthogonaux. Elles ont donc très souvent tendance à inciter la composition de plusieurs éléments, ce qui n'est pas réalisable dans les langages à héritage simple, comme nous l'avons montré dans la section \ref{subsec:herit-simple}. C'est d'ailleurs pour cette raison que les spécifications proposent ce qu'on appelle des \og protocoles\fg, où il est possible d'exprimer cette composition n-aire. Ceci permet alors de spécifier une bibliothèque plus finement, mais introduit deux vues dans la hiérarchie : la vue \og hiérarchie de protocoles\fg et la vue \og hiérarchie de classes\fg ; comme la figure \ref{fig:dualite} l'illustre. \begin{figure}[here] \centering \includegraphics[width=8cm]{figures/hierar_proto_itf.png} \caption{Différences notoires entre protocoles (traits en pointillés) et implantations (traits pleins)~\cite{Cook92a}.} \label{fig:dualite} \end{figure} Nous proposons donc tout d'abord de supprimer cette dualité. \paragraph{Structures de données hétérogènes.} L'approche de Nile vis à vis des traits démontre que ces derniers sont capables de générer des hiérarchies de classes où la réutilisation et la structuration sont optimales. En effet, la hiérarchie proposée identifie clairement des traits pour chaque caractéristique des Streams et permet une composition de ceux-ci afin d'exprimer tous les besoins nécessaires. Cependant, la refactorisation des Collections se démarque vis à vis des Streams. En effet, dans ces derniers, la plupart des objets manipulés disposent de la même implantation sous-jacente, ce qui facilite la composition des traits. Ce problème est en fait une des difficultés majeures lors de la refactorisation de bibliothèques disposant de nombreux éléments hétérogènes, comme les collections. Même si le développeur réussi à identifier les traits idéaux d'un point de vue modularité, il n'est en rien assuré que ceux-ci seront fonctionnels une fois composés. Nous illustrons ce problème sur la figure \ref{fig:comp_impl}. Supposons que nous avons deux types de collections : une liste chaînée (\textit{LinkedList}) et un tableau triable (\textit{SortableArray}). \textit{LinkedList} fait usage d'un trait nommé \textit{TGrowable} qui indique qu'il est possible de faire grossir cette collection ; \textit{SortableArray} d'un trait nommé \textit{TSortable} qui se charge de trier les éléments. \begin{figure}[here] \centering \includegraphics[width=8cm]{figures/Fig42.pdf} \caption{La composition repose sur l'hypothèse que les implantations sont compatibles. Ainsi, le trait TGrowable utilisant un structure de tableau et le trait TSortable, utilisant une structure de liste chaînée ne peuvent produire une composition consistante.} \label{fig:comp_impl} \end{figure} L'implantation de \og \textit{TGrowable}$>>$add\fg sera donc la suivante : \begin{lstlisting} TGrowable>>add: anElement self elements last append: (LLNode with: anElement) \end{lstlisting} Et l'implantation de \og \textit{TSortable}$>>$sort\fg ressemblera à quelque chose comme : \begin{lstlisting} TSortable>>sort Quiksort onArray: self elements \end{lstlisting} On remarque donc que ces deux implantions sont propres aux structures de données sous-jacentes. Par exemple, dans le premier cas, afin de faire grossir la structure de données, nous ajoutons explicitement un \textit{LLNode} en fin de liste. Si nous devions travailler sur un tableau, cette fonction échouerait. Ainsi, lorsque nous allons, par exemple, vouloir créer une liste chaînée triable (\textit{SortableLinkedList}), nous allons naturellement vouloir composer \textit{TGrowable} et \textit{TSortable}, ceci s'inscrivant parfaitement dans la logique d'utilisation traits. Il est cependant évident que ces deux traits ne s'accordent pas car les structures de données qu'ils manipulent sont différentes. Ils sont donc incompatibles alors que leurs rôles, eux, ne le sont pas. Il est donc clair que dans de grandes hiérachies où les éléments reposent sur des implantations différentes, un trait par caractéristique n'est pas suffisant. Nous proposons donc un ensemble de procédés permettant de faire face à ce problème d'hétérogénéité en nous attachant à la consistance polymorphique et comportementale. \paragraph{Pollution d'interfaces.} Au cours de l'analyse des classes des collections, nous avons fait le constat d'une pollution d'interfaces de ces classes. En effet, les opérations de conversions sont en bonne partie responsable du bruit introduit. Nous proposons donc un moyen d'éviter cette pollution en réutilisant le concept de protocoles afin d'introduire des méthodes génériques. \paragraph{Affinage des protocoles.} La hiérarchie de protocoles des collections de Smalltalk-ANSI, bien qu'utilisée actuellement dans la plupart des implantations de Smalltalk, ne permet de fournir toutes les classes de collections dont nous aimerions bénéficier. Ceci est principalement dû au fait que la granularité des protocoles n'est pas assez fine. Avec les propositions que nous avons fait précédemment, nous introduisons donc un exemple d'une nouvelle hiérarchie maintenant réalisable qu'il sera intéressant de prendre comme référence pour une étude de cas complet. \section{Unifier les vues structurelles} William Cook, dans sa publication \og Interfaces and Specifications for the Smalltalk-80 Collection Classes\fg (cf. section \ref{sec:interf-specs-st}) regrette le fait de ne pas avoir accès à l'héritage multiple pour pouvoir exprimer la hiérarchie de protocoles des collections plus fidèlement : \begin{quote} ... \textit{\og to express this structure more directly, Smalltalk would need multiple inheritance or mixins.\fg} --~\cite{Cook92a}, Section 6 : Interfaces Versus Inheritance. \end{quote} Bien que la plupart des langages actuels utilisent l'héritage simple (pour les raisons évoquées en section \ref{subsec:herit-simple}), nous disposons maintenant des traits qui nous permettent d'exprimer des compositions venant de plusieurs éléments ; ceci en évitant la plupart des problèmes de l'héritage multiple. Il est donc maintenant possible de combler le fossé entre protocoles et hiérarchie de classes grâce aux outils dont nous disposons. Nous nous basons donc sur la hiérarchie de protocoles originale de Smalltalk-ANSI~\cite{ANSI98a}, qui exprime des compositions n-aires de protocoles, comme point de départ pour une nouvelle hiérarchie de traits. Chaque protocole devient donc un trait (par exemple, \og Updatable Collection\fg deviendra \textit{TUpdatable}) et il est donc possible d'obtenir une vue unique. Ceci a de multiples avantages ; en voici trois significatifs : \begin{enumerate} \item Nous pouvons désormais implanter les protocoles de manière fidèle et nous y conformer ; \item Nous évitons les problèmes exprimés précédemment comme la duplication de code ou l'annulation de méthodes ; \item Le développeur peut obtenir une compréhension du système par simple lecture de la spécification, sans devoir s'adapter aux compromis d'implantation. \end{enumerate} \section{Faire face à l'hétérogénéité} \subsection{Vers des implantations spécifiques} Le fait de devoir manipuler le même concept sous différentes formes pour une même caractéristique nous amène alors à déduire qu'il est nécessaire de disposer de plusieurs implantations pour chaque caractéristique. Ces implantations différentes nécessitent donc d'être spécifiques à chaque structure de données sous-jacente. Si nous avons alors une implantation pour chaque caractéristique, nous pourrons donc aisément composer les différents traits compatibles afin de créer l'ensemble des classes de collections. Bien que ceci semble idéal, l'introduction de plusieurs implantations pour une même caractéristique soulève aussi plusieurs questions. En voici une liste non exhaustive : \begin{itemize} \item Comment assurer que ces implantations seront conformes au même protocole ? \item Comment assurer que ces implantations offriront une même sémantique, bien que manipulant des structures de données différentes ? \item Comment permettre aux développeurs souhaitant étendre ces hiérarchies de facilement connaître les traits compatibles ? \item Comment proposer une vue facile à appréhender à l'utilisateur des collections. En effet, y a t-il un intérêt à ce que ce denier connaisse l'existence des traits spécifiques aux structures de données ? \end{itemize} \subsection{La nécessité des protocoles} Permettre d'avoir plusieurs implantations partageant un même rôle dans un système induit qu'il est nécessaire que ces premières respectent le même ensemble de messages. En effet, ce n'est pas parce qu'une implantation va utiliser telle ou telle structure de données qu'elle doit réagir à des messages différents. Si les implantations étaient différentes, il ne serait pas possible de demander un tri sur un tableau triable de la même manière qu'on le ferait sur une liste chaînée triable. Or, lorsque nous souhaitons réaliser cette opération de tri, nous n'avons pas envie de nous occuper de l'implantation sous-jacente. La suite de cette section décrit les bénéfices de cette abstraction. \paragraph{Assurer un polymorphisme.} En premier lieu, connaître le message correspondant à une opération donnée permet de créer des méthodes génériques et donc d'assurer un bon polymorphisme entre les différentes classes de collections. Ainsi, nous pouvons écrire l'expression suivante sans nous soucier de la nature sous-jacente de aSortableCollection : \begin{lstlisting} aSortableCollection sort \end{lstlisting} Nous ne nous devons de connaître qu'une seule information : la collection qui est traitée implante effectivement le protocole associé à la notion de tri. \paragraph{Améliorer la compréhension.} En deuxième lieu, définir un protocole unifié pour toutes les classes remplissant le même rôle rend le système consistant. En effet, comme nous allons devoir implanter une classe pour chaque type de structure de données, le nombre de classes présentes dans le système peut vite croître comme le montre le calcul suivante : Nombre Classes $=$ Nombre de structures de données $*$ Nombre de caractéristiques Définir un protocole donne donc de bonnes propriétés d'utilisation : une courbe d'apprentissage plus douce pour l'utilisateur de la bibliothèque ainsi qu'une maintenance plus aisée. \paragraph{Se préparer aux nouvelles collections.} Troisième point non négligeable, connaître à l'avance les messages qui doivent être supportés permet de créer des extensions plus efficacement et surtout plus fiablement. Dans le cas où nous n'avons pas de consensus défini sur un protocole, si nous devons ajouter une implantation de la caractéristique \og Growable\fg pour les structures de type ``Arbre'', comment allons nous procéder ? Avec plusieurs implantations déjà existantes dans le système, la seule solution est d'aller inspecter ces classes pour en déduire les messages qu'il faut implanter. Ceci suppose deux choses de la classe que nous prenons comme exemple : \begin{enumerate} \item Qu'elle ait effectivement bien implanté tous les messages nécessaires ; \item Qu'elle n'ait pas ajouté des méthodes propres à son utilisation, auquel cas nous pourrions en venir à considérer trop de messages. \end{enumerate} Avec un protocole bien défini, nous pouvons donc combler le manque de spécification. En effet, pour connaître les messages à implanter afin de développer notre trait \textit{TGrowable} dédié aux arbres, il nous suffit alors de nous référer au protocole \og Growable\fg. \subsection{Matérialisation des protocoles} Comme nous l'avons soutenu, les protocoles sont réellement nécessaires pour faire cohabiter plusieurs implantations partageant un même rôle. Ceci combiné avec le fait que nous avons unifié la hiérarchie des protocoles avec celle d'implantation (grâce aux traits), il nous est alors possible de donner corps aux protocoles. Nous les matérialisons donc à l'aide de traits définissant pour chaque message du protocole associé, une méthode portant le nom de ce message. Nous appelons ces traits des \og traits-protocole\fg et nous décidons par convention de préfixer leurs noms par \og TP\fg. La figure \ref{fig:tp_growable} présente un exemple de trait-protocole. \begin{figure}[here] \centering \includegraphics[width=10cm]{figures/Fig44.pdf} \caption{Un exemple de trait-protocole pour le protocole Growable.} \label{fig:tp_growable} \end{figure} \paragraph{Détails d'un trait-protocole.} Un trait-protocole, dans sa forme la plus simple, est donc composé de deux éléments : des méthodes et de la documentation. Tout d'abord, les méthodes sont nommées suivants les noms des messages du protocole. Ces méthodes ne définissent pas de comportement lié au message qu'elles représentent. Elles ont cependant la contrainte de devoir lever une exception de type \og Nécessité d'implantation\fg (\textit{explicitRequirement}). Lever cette exception permet de faciliter la détection d'erreurs d'implantation. En effet, dans le cas où un trait souhaite implanter un trait-protocole et qu'il oublie de redéfinir une méthode, une exception sera levée, indiquant clairement qu'un oubli d'implantation a été commis. Ce comportement est essentiel afin de ne pas provoquer des exécutions silencieuses, mais faussées. Nous pourrons alors traquer facilement l'erreur afin de la corriger. %(FIXME: Illustrer ?) Ensuite, la classe, ainsi que chacune de ses méthodes, dispose d'une documentation définissant respectivement l'objet du protocole et la fonctionnalité réalisée par la méthode. Posséder la documentation à ce niveau est particulièrement intéressant car elle sera ainsi automatiquement propagée (via la composition) aux implanteurs du trait-protocole. Ceci réduit donc le nombre de classes non documentées. \paragraph{Remplacement des conventions.} Lors de la première refactorisation des Collections avec les traits, une convention de nommage été proposée (cf. section \ref{sec:deux-types-de}) afin de classifier les traits (par exemple, \textit{S} pour Séquenciel, ...). Bien qu'il s'agisse en effet d'une méthode fonctionnelle, elle n'est pas idéale car elle implique que le programmeur connaisse et respecte cette convention. Avec la méthode que nous proposons, nous n'utilisons que les mécanismes du langage pour caractériser la nature de nos traits, ce qui ne demande pas une connaissance préalable des symboles. \paragraph{Extensions particulières.} Bien entendu, une implantation particulière est libre d'étendre la liste des messages compréhensibles pour un protocole. Il est en effet probable que des méthodes à utilisation principalement interne soient définies lors de l'établissement de traits d'implantation. Cependant, nous n'encourageons pas cette pratique dans le sens où l'utilisateur pourrait supposer que ces messages font partis du protocole, ce qui dégraderait les possibilités polymorphiques. \section{Améliorer la consistance par les contrats} Le fait de donner corps aux protocoles nous permet donc de rendre la diversité d'implantations consistante. Nous pouvons donc maintenant affirmer qu'un bon polymorphisme est garanti. Cependant, même si les méthodes sont effectivement uniformisées, nous n'avons pas de garanties au niveau comportementale. Lorsqu'un trait va implanter un protocole, celui-ci va composer le trait-protocole et donc redéfinir les méthodes attendues. La classe qui utilisera ce trait pourra donc répondre aux messages attendus, mais rien n'empêche le développeur d'implanter incorrectement ces deniers. En effet, même si nous souhaitons que ces méthodes soient documentées, le langage naturel n'est pas toujours le mieux adapté pour décrire un comportement. Ce dernier n'est en rien formel, il est donc soumis à interprétation et un développeur n'ayant pas une parfaite maîtrise de la langue dans laquelle la documentation a été rédigée peut ne pas en saisir toute la subtilité. Ainsi, nous souhaitons enrichir les traits-protocoles avec des contrats afin de i/ améliorer la consistance comportementale de la bibliothèque et ii/ rendre la tâche de développement plus balisée. \subsection{Définition des contrats} Afin de mettre en place ce mécanisme, deux types de contrats doivent être mis en place pour assurer une bonne spécification. \paragraph{Comportement des méthodes.} Tout d'abord, nous devons disposer de contrats au niveau des messages du protocole, afin de spécifier le comportement même de ceux-ci. Lorsqu'un trait va implanter les messages du trait-protocole en question, ce premier va donc redéfinir les méthodes. Ce que nous voulons, c'est que lorsqu'un trait implante un trait-protocol, il soit soumis aux exigences du protocole. Les contrats définis pour les méthodes du trait-protocole seront donc appliqués aux méthodes redéfinies du trait implanteur. \paragraph{Invariants de traits et classes.} Ensuite, appliquer un invariant de classe pour les traits se révèle être d'une grande aide pour la consistance et le bon assemblage des traits. En effet, à travers des invariants, il est possible d'exprimer des propriétés de compositions intéressantes. Dans les sections précédentes, nous avons présenté un moyen de régler les problèmes de compositions de traits ayant des implantations sous-jacentes différentes, mais il est toujours possible de composer des traits non compatibles. Supposons que nous voulons créer une collection qui se trie automatiquement. Nous allons alors utiliser le protocole \og Sorting\fg, qui permet le tri automatique. Ce trait disposera d'un invariant qui vérifie que les éléments sont bien triés à tout instant de l'existence de la collection. En voulant bien faire, nous aimerions aussi ajouter le tri explicite. Le protocole \og Sortable\fg sera alors lui aussi utilisé. Cependant, ce dernier permet d'utiliser un critère de comparaison personnalisé pour trier les éléments. On se rend donc compte que ces deux traits sont en fait incompatibles car ils entrent en conflit en agissant sur les mêmes propriétés de la collection. L'état \og trié\fg assuré par le protocole \og Sorting\fg ne sera donc plus maintenant, car \og Sortable\fg fait qu'il est possible d'altérer cette propriété de tri. Ceci peut être révélé très rapidement (à la première utilisation de notre classe) grâce à la prise en compte de tous les contrats des traits composés dans la classe. Cette prise en compte sera réalisée pendant l'étape de composition des traits. Il nous suffira donc d'ajouter au composeur tous les invariants des traits, comme l'illustre la figure \ref{fig:comp_inv}. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/Fig45.pdf} \caption{La probabilité de composer des traits incompatibles est reduite à l'aide des invariants.} \label{fig:comp_inv} \end{figure} Fusionner les contrats lors de la composition des traits permet donc d'assurer que des traits incompatibles ne sont pas composés entre eux. \subsection{Supports d'exécution} Maintenant que nous avons décrit comment enrichir les traits-protocoles avec des contrats pour améliorer la consistance du système, il est intéressant d'étudier comment cette solution s'intègre aux outils existants. \subsubsection{Smalltalk} Smalltalk, au moins dans sa version Squeak, ne propose pas de support des contrats. Seule une publication \og Design by Contract in Smalltalk\fg (DbCS)~\cite{Carr96a} propose une extension de l'environnement Smalltalk pour y inclure les contrats. Nous présentons les éléments essentiels de cette méthode. \paragraph{Invariants.} En ce qui concerne les invariants de classes, le modèle DbCS propose d'ajouter un champ \og classInvariant\fg lors de la définition d'une classe. Ce champ contient une chaîne de caractères représentant un bloc exprimant les conditions de l'invariant, comme le présente l'exemple suivant : \begin{lstlisting} Object subclass: #BankAccount instanceVariableNames: 'balance owner' ... classInvariant: '[(balance > 0) and: [owner nationality = 'spanish']]' \end{lstlisting} Cet invariant sera injecté au début et à la fin de chaque méthode. \paragraph{Pre et post-conditions.} Pour la gestion des conditions de pre et post-conditions, cette méthode implique de faire des appels aux méthodes \og require\fg et \og ensure\fg comme suit : \begin{lstlisting} withdrawal:anAmount personalCode:code "Withdraws money from the account if the code is right" self require: [balance>=0]. self ensure: [(personalCode <> code) & self noChange) or: [(self old) balance = (balance + anAmount)]]. \end{lstlisting} L'appel à \og require\fg sera appelé au début de la méthode, tandis que \og ensure\fg sera inséré avant chaque retour de méthode. La méthode finale aura donc cette structure : \begin{lstlisting} methodName: args "comment" |temporaries| checkInvClass self require: ... < statements > self ensure: ... checkInvClass ^ return_value \end{lstlisting} Nous disposons donc d'un moyen complet, efficace et dans l'esprit de Smalltalk (\textit{\og every action in the system is a consequence of sending a message to an object\fg}) capable d'exprimer des invariants de classes et des conditions de méthodes. \subsubsection{Les traits} Étant donné que les traits ne gèrent pas les contrats, nous proposons une extension à ceux-ci afin de supporter cette fonctionnalité. Cette extension se base sur le modèle des traits sans état et nous nous appuyons sur le modèle d'implantation des contrats cité dans le paragraphe précédent. \paragraph{Invariants.} Tout d'abord, il est nécessaire de s'intéresser aux invariants de classes/traits. Lorsqu'une classe A hérite d'une classe B, elle hérite de l'invariant de la classe A et peut soit garder le même invariant ou le raffiner (mais jamais l'étendre). Bien que la composition de trait ne soit pas la même opération qu'un héritage, nous pouvons voir que la composition de trait doit respecter la même contrainte : c'est à dire garder ou renforcer le contrat mais ne jamais l'affaiblir. Lorsqu'un trait ou une classe compose des traits, nous allons donc aussi composer les invariants des traits utilisés. Selon la propriété que nous venons d'énoncer, nous les composerons donc à l'aide de l'opérateur logique \og AND\fg. Nous obtenons alors la formule suivante : \begin{center} $invariant_{final} = (invariant_{trait 1} \land ... \land invariant_{trait n}) \land invariant_{composeur}$ \end{center} Par exemple, nous avons sur la figure \ref{fig:inv_traits} la classe \textit{C} qui vient composer \textit{T1} et \textit{T2}. \textit{T1} a comme invariant ``[self total > 2]'' et \textit{T2} ``[(self total > 10) and: [self total < 100]]''. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/Fig46.pdf} \caption{Les invariants lors de la composition de traits sont fusionnés à l'aide de l'opérateur \og AND\fg.} \label{fig:inv_traits} \end{figure} Quand nous composerons ces deux traits nous obtiendrons donc comme invariant : \begin{lstlisting} [[self total > 2] value and: [(self total > 10) and: [self total < 100]]] \end{lstlisting} ce qui pourrait se réduire en : \begin{lstlisting} [(self total > 10) and: [self total < 100]] \end{lstlisting} \paragraph{Pre et post-conditions.} \label{par:pre-post-cond} Ensuite, nous devons traiter le cas des pre et post-conditions. On peut distinguer deux cas de composition de méthodes avec les traits : i/ l'utilisation d'une méthode de trait dans une classe ou ii/ la redéfinition d'une méthode d'un trait dans l'entité composante. \subparagraph{Sans redéfinition.} Dans le premier cas (figure \ref{fig:comp_cont_ok}), notre composition va faire pointer les méthodes directement vers les méthodes des traits d'origine. Nous n'avons donc rien à faire car les conditions seront les mêmes que lorsque la méthode était définie dans le trait. \begin{figure}[here] \centering \includegraphics[width=8cm]{figures/Fig47.pdf} \caption{Composition d'un trait sans redéfinition : aucun mécanisme n'est à rajouter.} \label{fig:comp_cont_ok} \end{figure} \subparagraph{Avec redéfinition.} Le second cas, où de la redéfinition est introduite, est plus problématique. Nous l'étudions en deux sous-cas, le premier étant plus simple. Le premier se destine à caractériser le comportement à adopter lorsque nous allons redéfinir une méthode venant d'un seul trait. En effet, dans la spécification des traits, il est indiqué qu'une méthode définie dans l'élément compositeur prend précédence sur celle provenant du trait. Nous ne remettons bien entendu pas en cause cette propriété, mais nous proposons cependant de dupliquer le contrat de la méthode redéfinie et de l'intégrer à la méthode de l'élément compositeur. Ceci est illustré sur la figure \ref{fig:trait_cont_redef}. \begin{figure}[here] \centering \includegraphics[width=8cm]{figures/Fig48.pdf} \caption{Lors qu'un trait est utilisé et qu'une méthode est redéfinie, son contrat est ajouté à celui de la nouvelle implantation.} \label{fig:trait_cont_redef} \end{figure} Nous faisons ce choix car les méthodes du trait qui utilisent cette méthode redéfinie n'ont pas conscience qu'il s'agit d'une méthode différente. Le comportement qu'elles attendent est donc bien celui de la méthode interne au trait. C'est pourquoi, nous sommes convaincus qu'il est nécessaire d'imposer, dans ce cas, le contrat à la méthode qui redéfinit. Le deuxième cas s'intéresse à la situation où nous redéfinissons une méthode venant de plusieurs traits. Il s'agit d'une version un peu plus complexe que le cas précédent, en effet, comment devons nous gérer les contrats des différents traits ? Il est très certainement probable que même si les méthodes portent le même nom dans les différents traits, leur sémantique soit différente car ces traits n'ont pas forcément été conçus pour travailler ensemble. Cependant, la remarque faite dans le premier cas reste tout à fait valable : les méthodes attendent le même comportement que celui d'origine. C'est pourquoi, nous avançons que les contrats de tous les traits doivent être pris en compte afin d'assurer le bon fonctionnement des méthodes. Ceci implique la possibilité que le contrat résultant soit insatisfiable. Si la composition implique ce cas de figure, ceci indiquera simplement que les traits ne peuvent fonctionner ensemble. Si nous avions décidé de ne pas agir ainsi, la seule chose résultante aurait été une composition non consistante. Les deux cas de figure sont illustrés sur la figure \ref{fig:trait_cont_clash}. \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/Fig49.pdf} \caption{Deux cas de figures lors de la composition et redéfinition de méthodes venant de plusieurs traits. Si nous prenons en compte les contrats des méthodes redéfinies, nous assurons la détection des inconsistances.} \label{fig:trait_cont_clash} \end{figure} Il est intéressant de noter vis à vis de ce problème, que le modèle des traits gelables (cf section \ref{subsec:freezable}) permet de palier à ce problème. En effet, s'il est possible de rendre une méthode précocement liée aux autres méthodes du trait, la question de redéfinition peut être écartée. Un dernier élément important est de considérer l'opérateur d'exclusion des traits (le \og-\fg). Celui permet de ne pas considérer une méthode d'un trait lors de la composition. Nous considérons que la situation résultante est la même que celle du deuxième sous-cas de figure. Il est donc aussi nécessaire de fusionner le contrat avec l'implantation qui va prendre précédence. Enfin, deux tous les cas, il aussi nécessaire de pouvoir affiner les pre et post conditions au niveau de la nouvelle implantation. Suivant les règles de la programmation par contrat, nous n'autorisons que l'affaiblissement de la pré-condition et le renforcement de la post-condition. Nous résumons donc le comportement à adopter vis à vis des pre et post-conditions lors de la composition des traits avec les formules suivantes : \begin{center} $precond_{finale} = (precond_{trait 1} \lor ... \lor precond_{trait n}) \lor precond_{composeur}$ $postcond_{finale} = (postcond_{trait 1} \land ... \land postcond_{trait n}) \land postcond_{composeur}$ \end{center} \section{Garder un système ouvert} Dans la hiérarchie des collections, il est fréquent de constater que les classes proposent de convertir leur structure de données vers d'autres. Par exemple, nous pouvons avoir envie de transformer une liste chaînée vers un tableau. Il est aussi intéressant de noter que des classes comme \textit{String} proposent des adaptateurs comme \#asPostscript ou encore \#utf8toIso. Ces méthodes, bien que toutes remplissant le rôle de convertisseurs, sont nombreuses et souvent nommées sans réelle convention. Ceci a plusieurs désavantages : \begin{enumerate} \item L'interface des classes est polluée dans le sens où nous avons de nombreuses méthodes de conversion alors que nous aimerions plutôt nous focaliser sur les méthodes métier ; \item Le développeur qui souhaite ajouter un convertisseur doit ajouter une méthode, donc encore ajouter du bruit aux interfaces ; \item L'utilisation n'est pas facilitée et il est pénible de devoir chercher une méthode parmi une liste importante. \end{enumerate} \paragraph{Deux types de convertisseurs.} Nous caractérisons les convertisseurs en deux catégories : \begin{enumerate} \item Les convertisseurs de conteneur : ceux-ci sont destinés aux conversions impliquant un changement de structure de données. On inlcuera par exemple \#asArray ou encore \#convertToAGivenStructure. Dans tous les cas, les données ne sont pas altérées : seule leur forme de stockage est changée ; \item Les convertisseurs de contenu, qui permettent de modifier la représentation des données. C'est le cas par exemple d'un encodeur Utf-8 vers Iso, pour les \textit{Strings} ou encore Ogg vers Wav pour des données audio. \end{enumerate} \paragraph{Méthodes génériques.} Nous allons alors introduire deux méthodes génériques aux collections permettant les deux types de conversions précédemment citées : \#convertWith et \#encodeWith pour respectivement convertir le conteneur et convertir le contenu. Ainsi lorsque nous souhaiterons par exemple encoder un texte en UTF-8, nous pourrons effectuer ceci : \begin{lstlisting} aString encodeWith: UTF8Encoder \end{lstlisting} Ceci retournera alors un string encodé en UTF-8. Afin de donner les informations nécessaires aux objets qui doivent réaliser l'encodage, nous proposons alors d'utiliser un double dispatch~\cite{DDispatch}. Ainsi, si \textit{aString} était encodé en \og iso8859\fg, nous obtiendrons cette suite d'appels : \begin{lstlisting} 1. aString encodeWith: UTF8Encoder 2. UT8Encoder fromIso8859: aString \end{lstlisting} Nous aurons alors donc toutes les informations nécessaires pour réaliser la conversion : \og un String encodé en Iso8859 doit être converti vers un String encodé en UTF-8\fg. Cependant, on peut se poser des questions quant aux objets qui peuvent être passés en arguments à ces méthodes de conversion. Tout d'abord, comment être certain que la conversion est possible ? Ensuite, comment permettre l'écriture de nouveaux convertisseurs conformes ? \paragraph{Protocoles utilisateurs.} Nous répondons à la question en proposant de créer une hiérarchie de protocoles parallèle que nous appelons \og Protocoles utilisateurs\fg. Cet ensemble de protocoles regroupe les actions qui peuvent être utilisées par la hiérarchie de protocoles de la bibliothèque. Un exemple de hiérarchie de protocoles utilisateurs peut être consulté sur la figure \ref{fig:proto-user}. \begin{figure}[here] \centering \includegraphics[width=8cm]{figures/userproto} \caption{Un exemple de hiérarchie de protocoles utilisateurs.} \label{fig:proto-user} \end{figure} Ainsi, nous aurons aurons par exemple le protocole \og StringEncoder \fg qui sera capable de répondre aux messages comme \#fromIso8859. Nous matérialisons aussi ce protocole via des traits-protocoles et adoptons le même processus qu'avec les hiérarchies de protocoles présentées dans les sections précédentes. Nous pouvons alors, par exemple, créer deux encodeurs respectant le protocole \og StringEncoder\fg : \textit{TUTF8Encoder} ou \textit{TIso8859Encoder}. La figure \ref{fig:rel_proto_user} donne un exemple d'utilisation de hiérarchie de protocoles utilisateurs par une classe la hiérarchie des protocoles principaux. \begin{figure}[here] \centering \includegraphics[width=9cm]{figures/Fig410.pdf} \caption{Un exemple d'utilisation des protocoles utilisateurs.} \label{fig:rel_proto_user} \end{figure} \paragraph{Utilisation des convertisseurs.} Afin de s'assurer que la conversion est possible, il nous suffira alors d'utiliser un trait qui implante le protocole requis. Une question reste cependant en suspend : comment spécifier le protocole qui est requis ? Nous répondons à ceci en appliquant une convention de nommage, comme Smalltalk a l'habitude de le faire. Ainsi, si nous avons un message d'un protocole qui prend en paramètre un convertisseur de type \og WavEncoder\fg, nous le déclarerons de la manière suivante : \begin{lstlisting} Wav8File>>convert: aWavEncoder ^ aWavEncoder from8bit: self \end{lstlisting} \paragraph{Amélioration de l'utilisation.} Bien que nous ayons maintenant les éléments nécessaires pour implanter et utiliser des protocoles utilisateurs, il est intéressant de se poser la question de simplicité d'utilisation d'un point de vue des développeurs. Lorsqu'un développeur va vouloir utiliser le \#convert, il va alors pouvoir regarder la signature et se rendre compte qu'il s'agit d'un \textit{WavEncoder} qui est attendu. Cependant, comment connaître tous les encodeurs disponibles ? Nous répondons à ceci en ajoutant une extension à l'IDE (Squeak dans notre cas) et permettant d'obtenir facilement une liste d'utilisateurs d'un trait donné. Ainsi, il suffira au développeur de sélectionner \og WavEncoder\fg et demander à afficher tous les implanteurs de ce protocole afin d'en choisir un dans la liste. Une implantation de référence pour OBBrowser, l'outil de navigation de classes de Squeak, est disponible en annexe \ref{ann:traitusers}. \section{Améliorer l'expressivité des protocoles} \label{sec:amel-expr-proto} Maintenant que nous disposons d'outils suffisamment adaptés à la gestion des grandes hiérarchies de traits-protocoles, il est intéressant de se poser la question de la flexibilité des protocoles actuels. En effet, la hiérarchie de protocoles de Smalltalk-80, même révisée (cf. figure \ref{fig:result_is}), permet difficilement d'exprimer tous les cas. Comme la composition des traits ne se révèle pas coûteuse en terme de temps d'exécution~\cite{Blac03a,Cass07a}, nous pouvons aisément proposer un ensemble de protocoles à plus fin grain, comme celui présenté sur la figure \ref{fig:protos_new}. \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/proto.png} \caption{Un exemple de hiérarchie de protocoles à plus fin grain. Les messages les plus essentiels sont détaillés.} \label{fig:protos_new} \end{figure} Cette nouvelle hiérarchie ne se veut pas exhaustive, mais représentative des possibilités. Ainsi, nous ne couvrons pas toutes les classes de collection mais exposons une hiérarchie capable d'exprimer la plupart des besoins courants. Il est intéressant de noter que cette hiérarchie de protocoles permet de proposer des combinaisons au préalable impossible à exprimer. Ainsi, il est par exemple possible de créer un tableau immuable (\textit{ImmutableArray}) en composant simplement \textit{Indexable} et \textit{Ordered}. Ces protocoles peuvent bien entendu être révisés au niveau de leur granularité mais nous estimons que la proposition est un bon compromis entre modularité et complexité. La méthode employée pour obtenir ce résultat peut être consultée en section \ref{sec:methodo-granu}. La suite de cette section donne une description succinte des protocoles. \paragraph{Collection.} Nous avons regroupé dans ce protocole les caractéristiques suivantes : \begin{itemize} \item Conversion : la capacité à être converti vers une autre forme de collection. Il a été supposé, pour cette version, que toutes les collections peuvent être transformées vers d'autres ; \item Sérializable : la capacité de se représenter sous une forme textuelle. Ceci permet entre autres la possibilité de transiter sur un réseau ou de réaliser de la persistance ; \item Taille : la capacité à garder des informations sur sa capacité et son nombre d'éléments ; \item Copie : la possibilité de copier la structure de données vers une nouvelle instance ; \end{itemize} \paragraph{Indexable.} \label{sec:indexable} \og Indexable\fg signifie qu'il est possible d'adresser les éléments selon une clé. Ainsi, un message comme \#at: permet de récupérer l'élément à l'indice fourni. Ce protocole ne permet que d'effectuer des opérations de lecture sur la collection. Son pendant permettant l'écriture sur les collection se nomme \og Updatable\fg. \paragraph{Iterable.} \label{sec:iterable} Le protocole \og Iterable\fg indique que la collection peut être itérée. Il a été externalisé de \og Collection\fg car nous pouvons imaginer qu'une collection puisse stocker des éléments en aveugle et ne puisse pas itérer sur toutes ses valeurs. \paragraph{Ordered.} \label{sec:ordered} \og Ordered\fg indique que les éléments de la collection ont un ordre de stockage défini. Ce protocole ne doit pas être confondu avec le protocole de tri \og Sortable\fg. \paragraph{Uniqueness.} Ce protocole implique qu'un élément ne peut figurer deux fois dans une même collection. \paragraph{Shrinkable, Growable.} Ces deux protocoles permettent respectivement de réduire et d'agrandir la capacité de la collection. On peut les utiliser pour créer des tableaux dynamiques ou encore des listes chaînées. Étant souvent utilisés conjointement, nous les avons regroupés dans une protocole appelé \og Reziable\fg qui combine ces deux caractéristiques. \paragraph{Poppable, Pushable.} Ces caractéristiques expriment respectivement le fait qu'il est possible de retirer et d'ajouter un élément à l'extrémité d'une collection. On les utilise souvent pour réaliser des structures comme les piles (\textit{Stacks}). \paragraph{Quelques collections.} Afin d'illustrer la composabilité des protocoles, nous avons intégré des protocoles terminaux (qui peuvent être utilisés directement par les utilisateurs de la bibliothèque) comme \textit{Stack}, \textit{Bag} ou encore \textit{Array}. Ces exemples ne sont pas exhaustifs et on pourrait facilement créer d'autres collections moins usuelles comme un \textit{DynamicArray} en composant \textit{Array} et \textit{Resizable}. \chapter{Évaluation et méthodologie} Un des objectifs de nos travaux était d'évaluer les traits dans un contexte de grandes hiérarchies. Nous effectuons donc ici une revue de notre proposition en mettant en avant les aspects propres aux traits (granularité, type de traits utilisés, ...). Nous continuons ensuite sur une comparaison avec les travaux connexes puis nous terminons par les perspectives d'évolutions de notre proposition. %%- tests : foirage à cause des implems != \section{Evaluation} \subsection{Granularité des protocoles} \label{sec:methodo-granu} Nous avons présenté un exemple de hiérarchie de protocoles en section \ref{sec:amel-expr-proto}. Nous estimons que cette hiérarchie est un bon équilibre entre expressivité et concision. Elle permet d'exprimer toutes les structures de données dont nous avons besoin, peut être raisonnablement étendue en combinant ses protocoles et permet une implantation rétro-compatible de la norme Smalltalk-ANSI. Une des interrogations cruciales lors de l'utilisation des traits est la granularité idéale à adopter. En effet, bien que les traits permettent de décomposer les classes en de nombreux éléments sans impacter les performances, il est tout de même déconseillé de créer trop de traits car la hiérarchie devient alors très complexe à saisir. Nous présentons ici la méthode qui nous a permis d'obtenir la hiérarchie présentée dans l'exemple. Nous estimons qu'elle peut être efficace pour atteindre un bon équilibre entre ces deux critères. Celle-ci est en partie automatisée, mais nécessite tout de même que le développeur soit capable d'analyser la bibliothèque. Nous apportons cependant un outil qui permet d'exécuter une phase difficilement calculable par un Homme et qui permet d'élaborer la hiérarchie finale à partir de son résultat. Cette méthode peut être scindée en trois parties majeures : i/ l'identification des caractéristiques des classes, ii/ la génération d'une hiérarchie minimale grâce à ces informations et iii/ le raffinement manuel de cette hiérarchie. \paragraph{Identifier les caractéristiques.} \label{sec:ident-les-caract} La première étape consiste à prendre en compte toutes les classes qui vont être implantées. Nous passons alors en revue chacune de ces classes en notant leurs caractéristiques comme \og Extensible\fg, \og Iterable\fg, etc. Lors de cette étape, nous conseillons au développeur de privilégier une forte décomposition des classes, quitte à générer trop de caractéristiques. Nous obtenons à la fin de cette revue un ensemble de caractéristiques que nous pouvons alors associer aux classes. Nous passons alors en revue ces classes une deuxième fois, associons à chacune d'elle les caractéristiques correspondantes et obtenons alors à la fin de cette étape un tableau comme celui proposé en figure \ref{fig:tab-assoc-caract}. \begin{figure}[here] \centering \begin{tabular}{|l|c|c|c|c|c|} \hline \backslashbox{Carac.}{Classe} & Array & String & Stack & Set & ... \\ \hline Iterable & $\surd$ & $\surd$ & $\surd$ & $\surd$ & ...\\ \hline Growable & ~ & ~ & ~ & $\surd$ & ...\\ \hline Indexable & $\surd$ & $\surd$ & $\surd$ & ~ & ...\\ \hline Poppable & ~ & ~ & $\surd$ & ~ & ...\\ \hline ... & ... & ... & ... & ... & ... \\ \hline \end{tabular} \caption{Un exemple de tableau d'association classes/caractéristiques.} \label{fig:tab-assoc-caract} \end{figure} \paragraph{Générer une hiérarchie minimale.} \label{sec:minim-la-hier} Maintenant que nous disposons d'un ensemble d'associations, nous pouvons introduire le calcul de la hiérarchie de protocoles à l'aide de notre outil. Celui-ci prend en entrée un ensemble d'associations et produit la hiérarchie de protocoles la plus minimaliste possible. Chaque caractéristique sera alors représentée par un protocole. Par minimaliste, nous entendons qu'il regroupe les caractéristiques utilisées conjointement en une seule, afin de diminuer le nombre de protocoles. L'algorithme va aussi trouver la hiérarchie logique pour ces caractéristiques, selon l'analyse d'utilisation de ces dernières par les classes. Cet algorithme se déroule en quatre étapes : \begin{enumerate} \item Chercher les associations qui peuvent être assimilées comme identiques, c'est à dire celles qui sont utilisées exactement par les mêmes classes ; \item Générer une liste de protocoles en se basant sur la liste d' associations. On obtient alors un dictionnaire de protocoles ayant comme valeur un ensemble vide ; \item Ordonner les protocoles selon leur relation de couverture. Un protocole couvre un autre quand nous avons la relation suivante :\\ Soit $\prec$ cette relation, $p$ un protocole et un ensemble $E_n$ définit par $\{$ Classe $|$ Classe utilise $n$ $\}$ \\ $p$ $\prec$ $p'$ ssi $E_p$ $\subset$ $E_{p'}$ %$P \subset P' \Leftrightarrow \forall c (c \in Classes_P \Rightarrow c \in %Classes_{P'})$; \item Pour chaque protocole, on supprime les liens directs si un lien indirecte existe. Par exemple, si \og A pointe vers B\fg, \og A pointe vers C\fg et \og B pointe vers C\fg, on supprimera le lien \og A pointe vers C\fg. \end{enumerate} Nous obtenons alors une hiérarchie comme décrit sur la figure \ref{fig:hierar-proto-gen}. \begin{figure}[here] \includegraphics[width=\linewidth]{figures/gen_proto.png} \caption{La hiérarchie de protocoles générée à l'aide de l'outil. La flèche symbolise la couverture ($\prec$).} \label{fig:hierar-proto-gen} \end{figure} \paragraph{Analyser et améliorer.} \label{sec:analys-et-amel} Nous avons obtenu une hiérarchie minimaliste extraite des associations que nous avons entrées. Cette hiérarchie, bien que fonctionnelle, n'est cependant pas satisfaisante pour obtenir un système ouvert et destiné à recevoir de nouvelles classes. Nous pouvons voir par exemple que l'algorithme a regroupé les éléments \og Growable\fg et \og Shrinkable\fg en un seul protocole. C'est à ce moment que l'analyse du concepteur est importante. Nous devons porter un oeil critique sur la hiérarchie de protocoles minimaliste afin de décider si effectivement nous pensons que ces protocoles regroupés ne seront jamais utilisés de manière disjointe. Dans le cas de \og ShrinkableGrowable\fg, il est clair que nous souhaitons diviser ces deux préoccupations. Cependant, l'algorithme nous ayant fait remarqué que ces deux protocoles sont souvent utilisés conjointement, il est pertinent de proposer un sous-protocole regroupant ces deux caractéristiques. Nous avons appelé ce protocole \og Resizable\fg sur l'exemple de hiérarchie (cf. section \ref{sec:amel-expr-proto}). C'est pourquoi, nous insistons sur le fait que l'utilisation d'outils ne peuvent pas, dans l'état actuel, remplacer l'expérience du concepteur. Cependant, les outils restent cruciaux dans le sens où ils permettent de guider le concepteur dans sa démarche ainsi que de mettre en avant des propriétés qui ne sont pas aisément remarquables à cause d'un grand nombre d'informations. \subsection{Factorisation de code} Nous avons présenté le concept de traits-protocoles permettant de présenter une hiérarchie de protocole sans se soucier de l'hétérogénéité des implantations sous-jacentes. Dans notre proposition, nous indiquons que les méthodes des traits-protocoles doivent nécessairement lever une exception afin de forcer l'implanteur à redéfinir cette méthode. Un des avantages des traits est qu'ils permettent aussi de contenir du code. C'est pourquoi, même si nous ne l'avons pas mis en avant, nous sommes convaincus qu'il est possible de trouver des cas où une factorisation de code est possible au niveau de ces traits-protocoles. Ceci permettrait ainsi d'éviter la duplication de code dans les traits d'implantation. Cependant, cette opération nécessite une attention particulière car il n'est pas évident de s'assurer que le code fourni sera compatible avec toutes les implantations. Il serait néanmoins possible d'introduire des comportements qui couvrent la plupart des cas et de les redéfinir dans les cas particuliers. Ce travail nécessite donc à la fois une réflexion a priori, afin d'en tirer de bonnes abstractions et très certainement une amélioration a posteriori via des retours d'expériences. \subsection{Comparaison avec la refactorisation précédente} Notre solution diffère sensiblement du modèle obtenu lors de la première refactorisation. En effet, celle-ci est partie du principe qu'il fallait modulariser les classes existantes et a proposé un modèle constitué de traits permettant d'exprimer la hiérarchie en place. Notre démarche considère que la hiérarchie actuelle n'est pas une finalité. En effet, même si notre méthode propose d'extraire les caractéristiques existantes, nous mettons l'accent sur l'ouverture du système en le préparant à de futures extensions. Nous pouvons ainsi avoir une bien meilleure expressivité des combinaisons de caractéristiques et donner la possibilité de créer des classes préalablement impossible à composer. Notre proposition se démarque aussi en insistant sur la consistance du système. En effet, là où une convention de nommage servait à spécifier la nature des traits, nous lui préférons le concept de traits-protocoles. De plus, nous lui ajoutons des contrats, ce qui permet de garantir une certaine garantie vis à vis des comportements implantés. \subsection{Modèles de traits} \label{sec:modeles-de-traits} Une des interrogations liée aux traits est d'essayer de déterminer quel modèle est le plus intéressant en pratique. Les refactorisations qui ont été faites jusqu'à présent ont utilisé le modèle sans état. Dans notre cas, le modèle des traits sans état s'adapte parfaitement car nous ne référençons jamais réellement d'état. Cependant, nous avons tout de même remarqué que le modèle des traits gelables pourrait résoudre le problème lié aux contrats (section \ref{par:pre-post-cond}). Nous pensons, vis à vis de l'expérience acquise à travers cet exercice de refactorisation, que le seul réel problème des traits sans état est la violation de l'encapsulation (et donc la pollution d'interface) à travers l'exposition d'accesseurs. Les autres modèles de traits, bien qu'apportant d'autres fonctionnalités intéressantes, induisent une complexité qui ne justifie pas les avantages qu'ils apportent. Notre conclusion est donc que l'idéal est certainement un modèle avec état qui conserve la simplicité du modèle sans état, mais qu'à défaut, les traits sans état restent le meilleur compromis. \section{Perspectives} \paragraph{Fondations pour une refactorisation.} \label{sec:fondations-pour-une} Tout au long de ce document, nous avons proposé des éléments cruciaux pour réaliser une refactorisation avec les traits sur des grandes hiérarchies. Il serait donc maintenant intéressant de mettre en action ces concepts afin de les valider à travers une mise en pratique sur les collections. Il s'agit d'un gros travail d'ingénierie qui pourrait être réalisé dans le cadre d'une évaluation poussée des traits afin d'obtenir un retour scientifique important sur ces derniers et d'éventuellement faire évoluer le modèle si le besoin se fait ressentir. \paragraph{Patrons identifiables.} \label{sec:patr-ident} Les outils que nous avons proposés pour refactoriser la hiérarchie des collections, bien qu'appliqués à cette dernière dans notre cas, ne sont très certainement pas limités aux collections. En effet, nous pensons que les traits-protocoles peuvent être réutilisés dans toutes les hiérarchies assez importantes car ils procurent de bonnes propriétés pour régler les problèmes d'hétérogénéité. Ainsi, il est très certainement possible de généraliser une grande partie des travaux proposés dans ce document et d'en tirer des bonnes pratiques pour les grandes refactorisations à l'aide des traits. \paragraph{Traits dynamiques.} \label{sec:traits-dynamiques} Une fonctionnalité intéressante que nous aurions aimé disposer pendant la refactorisation est la possibilité d'ajouter ou supprimer des protocoles à la volée. Ainsi, nous aurions pu ajouter et supprimer des fonctionnalités pendant l'existence de la collection. Par exemple, un cas intéressant est celui où nous souhaitons communiquer une collection à une classe tierce, mais nous aimerions nous assurer que cette classe ne fera pas de modification dessus. Nous pourrions alors lui fournir une version (ou vue) diminuée de cette collection en supprimant le protocole \og Updatable\fg. Cependant, bien qu'introduire ce genre de fonctionnalités permet d'accéder à de nombreuses possibilités, tout un ensemble de problèmes complexes viennent eux aussi s'ajouter. Nous pouvons citer comme exemple la garantie de consistance lorsque qu'un trait incompatible est ajouté. Le comportement à adopter n'est alors pas évident : le système pourrait tout aussi bien refuser le trait comme supprimer tous les traits incompatibles. Nous pensons donc que cette voie peut être très enrichissante mais qu'elle nécessite un effort de conception important, dépassant même le cadre des traits et des refactorisations. \chapter{Conclusion} Notre travail a donc consisté à proposer un modèle utilisant les traits qui permet de refactoriser les collections en leur donnant de bonnes propriétés telles que la consistance, l'extensibilité et la modularité. Nous avons commencé par proposer une vue hiérarchique à base de traits se calquant sur la hiérarchie de protocoles de Smalltalk-ANSI. Ceci a permis d'éliminer les multiples vues hiérarchiques afin d'éviter les duplications de code, les concessions de conceptions et d'améliorer la compréhension. Nous avons ensuite introduit la notion de traits-protocoles permettant de faire face à la grande hétérogénéité des structures de données des collections. Grâce à ce concept, nous pouvons désormais implanter les protocoles sous plusieurs formes et grandement améliorer les combinaisons possibles. Afin d'assurer une meilleure cohérence, nous avons aussi proposé une extension au modèle des traits sans état afin de permettre l'utilisation des contrats avec celui-ci. Utiliser les traits avec des contrats nous permet d'améliorer la consistance au sein de la hiérarchie des collections en i/ accélérant la détection des compositions inconsistantes et ii/ en s'assurant que les implantations spécifiques des traits-protocoles respectent le protocole associé. Un exemple d'une nouvelle hiérarchie de protocoles a ensuite été proposée afin de prouver que, grâce à nos propositions, nous pouvons améliorer l'expressivité de la hiérarchie. Ceci nous a permis d'étendre les catégories de collections et de proposer des collections qui n'étaient pas réalisables auparavant avec la norme ANSI. Nous avons d'ailleurs introduit une méthode outillée permettant d'obtenir une granularité intéressante pour les hiérarchies de traits/protocoles. En ce qui concerne les pollutions d'interfaces, nous avons brièvement présenté une solution permettant de les réduire. Nous nous sommes basés sur le fait que la plupart des messages polluants étaient de la même nature : les conversions. A travers cette démarche, nous avons montré que les traits s'adaptent parfaitement aux grandes hiérarchies de classes et qu'ils permettent de doter ces dernières des propriétés idéalement recherchées (maintenabilité, extensibilité, ...). Cette proposition reste donc maintenant à être appliquée et éprouvée à travers une refactorisation en profondeur des collections afin d'être améliorée et d'éventuellement en tirer des patrons de conceptions pour les traits. \bibliography{rapport} \appendix \chapter{La syntaxe Smalltalk} \label{sec:la-syntaxe-smalltalk} Le tableau \ref{tab:syntaxe-base} montre les éléments de base de la syntaxe Smalltalk. \begin{table}[h!t] \centering \begin{tabularx}{\linewidth}{lX} \textbf{.} & le point sépare les instructions.\\ \textbf{:=} & le symbole \textbf{:=} sert à l'affectation.\\ \textbf{\^} & L'accent circonflexe sert à retourner des valeurs à la méthode appelante.\\ \textbf{'chaîne de caractères'} & les simples quotes délimitent les chaînes de caractères.\\ \textbf{[ bloc ]} & les crochets délimitent les closures, appelées bloc en Smalltalk.\\ \textbf{[:arg1 :arg2 | bloc]} & les blocs peuvent prendre des arguments.\\ \textbf{|tmpVar1 tmpVar2|} & les pipes servent à déclarer des variables temporaires. Leur durée de vie et leur portée est limitée à la méthode.\\ \textbf{"commentaire"} & les commentaires sont entre guillemets.\\ \textbf{\$a} & représente le caractère a, instance de la classe \textit{Character}.\\ \textbf{\#symb} & représente un symbole instance de \textit{ByteSymbol}. \\ \textbf{\#(a b)} & représente un tableau instance de la classe \textit{Array} qui contient deux élément a et b. \\ \end{tabularx} \caption{Éléments de base de la syntaxe} \label{tab:syntaxe-base} \end{table} En Smalltalk, il existe six pseudo variables. Elles sont données dans le table \ref{tab:pseudo-variables}. \begin{table}[h!t] \centering \begin{tabular}{ll} \textbf{true} et \textbf{false} & ces constantes sont des instances des classes \textit{True} et \textit{False}.\\ \textbf{nil} & \textbf{nil} est la valeur par défaut de toute variable.\\ \textbf{self} & \textbf{self} représente l'objet courant. Il est équivalent au \textbf{this} de Java.\\ \textbf{super} & indique que le lookup doit se faire à partir de la super classe.\\ \textbf{thisContext} & \textbf{thisContext} représente la pile d'exécution en cours.\\ \end{tabular} \caption{Les pseudo variables} \label{tab:pseudo-variables} \end{table} Il n'y a pas de fonction en Smalltalk, seulement des méthodes que l'on exécute sur des objets. Il y a trois types de méthodes: \paragraph{Les méthodes unaires.} Les méthodes unaires n'ont pas d'argument. \begin{lstlisting} "Appel de la methode removeAll sur l'objet uneCollection :" uneCollection removeAll. \end{lstlisting} \paragraph{Les méthodes binaires.} Les méthodes binaires prennent un argument et leurs noms est composé de symboles ('.' ',' '+' '-'\dots). \begin{lstlisting} "Appel de la methode + sur l'objet 1 avec le parametre 3 :" 1 + 3 \end{lstlisting} \paragraph{Les méthodes à mots-clés.} Enfin, les méthodes à mots-clés possèdent un nombre illimité de paramètres. Leurs noms sont composés de plusieurs groupes de caractères (autant qu'il y a d'arguments) se terminant chacun par le caractère '\string:'. Les arguments se placent après chaque caractère '\string:'. \begin{lstlisting} "Appel de la methode replaceFrom:to:with: qui prend 3 arguments sur l'objet uneCollection :" uneCollection replaceFrom: 1 to: 6 with: uneAutreCollection. "L'equivalent java serait :" uneCollection.replaceFromToWith(1, 6, uneAutreCollection); \end{lstlisting} \paragraph{Priorité des messages.} Lors de la lecture d'une expression les messages sont évalués dans l'ordre suivant : \begin{enumerate} \item Méthodes unaires ; \item Méthodes binaires ; \item Méthodes à mots-clés. \end{enumerate} Par exemple: \begin{lstlisting} 5 factorial + 5 gcd: 5 \end{lstlisting} Doit être lu de la manière suivante: \begin{lstlisting} ((5 factorial) + 5) gcd: 5 \end{lstlisting} Il n'y a donc pas de priorité pour les opérateurs mathématiques. Ainsi \textbf{3 + 4 * 3} vaut 21 et non pas 15. Il faut donc écrire \textbf{3 + (4 * 3)} si l'on veut que la multiplication prenne précédence sur l'addition. \paragraph{Les cascades.} Il est possible et très fréquent en Smalltalk d'envoyer plusieurs messages au même objet. Cela se fait grâce à l'opérateur '\string;'. \begin{lstlisting} uneCollection add: unObjet; add: unAutreObject; add: unTroisiemeObjet. \end{lstlisting} La définition d'une nouvelle méthode se fait de la façon suivante : \begin{lstlisting} String>>lineCount "Compte le nombre de lignes dans le receveur (une chaine de caracteres). Chaque carriage return (cr) compte pour une nouvelle ligne." | count | count := 1. self do: [:c | (c == Character cr) ifTrue: [count := count + 1]]. ^ count \end{lstlisting} Le morceaux de code précédent doit s'interpréter de la façon suivante : \begin{enumerate} \item une nouvelle méthode appelée \textbf{lineCount} est définie dans la classe \textit{String}. \item un commentaire explique le but de cette méthode. \item une variable temporaire \textbf{count} est déclarée puis initialisée à 1. \item la méthode \textit{do:} est exécutée sur l'objet en cours (\textbf{self}). Cette méthode prend un argument de type bloc, et le bloc doit avoir un argument. Le bloc sera évalué pour chaque caractère de la chaîne. La méthode \textit{do:} est équivalent à une boucle \textbf{foreach} ou a une fonction \textbf{mapcar} en Common Lisp. \item Le bloc définit un argument appelé \textbf{c}. Cet argument sera remplacé par chaque caractère de la chaîne, l'un après l'autre. \item Le corps du bloc commence par comparer le caractère en cours avec le caractère de fin de ligne. Le caractère de fin de ligne s'obtient avec \textbf{'\textbackslash n'} en C et en appelant la méthode \textit{cr} sur la classe \textit{Character} en Smalltalk. \item Le résultat de la comparaison est un booléen : soit \textbf{true} soit \textbf{false}. \item Sur ce booléen, la méthode \textit{ifTrue:} est appelée. Cette méthode prend un bloc en paramètre et n'évalue ce bloc que si le receveur est \textbf{true}. \item Si le booléen est \textbf{true}, le bloc est exécuté et on ajoute 1 à la variable \textbf{count}. \item Quand la méthode \textit{do:} a fini d'itérer sur tous les caractères, elle se termine puis la valeur de la variable \textbf{count} est retournée. \end{enumerate} \chapter{Trait Users pour OBBrowser} \label{ann:traitusers} Dans cet annexe, nous présentons une implantation d'un outil d'aide à la recherche des implanteurs d'un trait. Avec cet extension d'OBBrowser, il est donc maintenant possible de parcourir rapidement les implanteurs des protocoles. Ceci est particulièrement utile lors de l'utilisation des traits-protocoles. Pour réaliser l'opération, il suffit de sélectionner un trait et d'indiquer \og browse trait users\fg\ref{fig:obbrows-menu}. \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/ob_query.png} \caption{Sélection d'un trait avec OBBrowser pour afficher ses implanteurs.} \label{fig:obbrows-menu} \end{figure} Le résultat de cette commande sera consultable sous la forme d'une navigateur de traits, comme le montre la figure \ref{fig:obbrows-users}. \begin{figure}[here] \centering \includegraphics[width=\linewidth]{figures/ob_result.png} \caption{Parcours de implanteurs des traits.} \label{fig:obbrows-users} \end{figure} \medskip Voici le code de référence permettant la collecte des implanteurs : \begin{lstlisting} showUsersOf: aTrait ClassListBrowser browseClassesSatisfying: [:class | class traitComposition traits includes: aTrait ] title: 'Users of ', aTrait name \end{lstlisting} \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: