\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 <glibersat@sigill.org>}

\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: 
