UP | HOME

Conception et implémentation des interfaces

Cf. le paquet session1.demo pour les exemples de code.

Table of Contents

1 Structure tri-partite des interfaces

Comment définir une interface I représentant un type abstrait de données ?

Exemple : interface Nat représentant les entiers naturels dans le paquet session1.demo.

Modèle : 

interface I extends Etat, Fabrique, Service { ... }

1.1 Composition à partir de trois types d'interfaces

Définir un type de données : la méthode

  • Cohésion forte de chaque interface élémentaire
  • Couplage faible entre elles
  • Dépendance des interfaces élémentaires (possiblement pour l'état, certainement pour la fabrique et le service) relativement à l'interface composée I

1.1.1 Etat : interface structurelle représentant les différents points de vue sur l'état

  • Premier pas pour l'application du patron Etat menant à la réification de l'état
  • Avantage : possibilité de modifier dynamiquement la représentation de l'état

Cf. l'interface générique NatSimple.

1.1.2 Fabrique : interface déclarant les méthodes de fabrication

  • Application du patron de conception Méthode de fabrication
  • Possibilité de réduire la dépendance vis-à-vis des classes d'implémentation aux seules méthodes de la fabrique

Cf. l'interface générique FabriqueNaturels.

1.1.3 Service : interface déclarant les opérations offertes par le type de données

  • Interface de plus haut niveau permettant de définir les opérations associées à l'interface composée I

Cf. l'interface générique SemiAnneauUnitaire.

1.2 Usage de la généricité : la prédicativité

Le couplage entre I et ses interfaces parentes (qui dépendent de I) correspond à une définition imprédicative (circulaire : I définie à partir d'interfaces dépendant de I). Possible en Java, une telle définition ne favorise pas la réutilisation.

Version 1 

interface Fabrique1 {
  ... I1 ...
}
interface Service1 {
  ... I1 ...
}
interface I1 extends Etat, Fabrique1, Service1 { ... }

Si on veut créer une nouvelle interface I2 proposant le service Service2 au lieu de Service1, on ne peut réutiliser Fabrique1.

Version 2 

interface Service2 {
  ... I2 ...
}
interface I2 extends Etat, Fabrique1, Service2 { ... } // IMPOSSIBLE

Solution : paramétrer Fabrique et Service par un type, l'interface à définir. La définition devient prédicative.

  • Slogan : interface = prédicat = concept
  • Exemples : Comparable, Iterable

Remarque : quelquefois un prédicat se dégrade en une proposition, un prédicat ne dépendant pas de son paramètre (cf. Serializable).

Cette méthode peut être appliquée de manière systématique. Elle produit alors une hiérarchie d'interfaces, organisée par la relation de sous-typage qui correspond à l'implication logique. 

interface Fabrique1<T> {
  ... T ...
}
interface Service1<T> {
  ... T ...
}
interface Service2<T> {
  ... T ...
}
interface I1 extends Etat, Fabrique1<I1>, Service1<I1> { ... }
interface I2 extends Etat, Fabrique1<I2>, Service1<I2> { ... }

Cf. l'exemple des entiers naturels.

1.3 Double usage des interfaces

On retiendra le double usage des interfaces.

  • Définition des types de données
  • Définition de propriétés

2 Modularité

Les architectures en couches - Méthodes de factorisation

2.1 Comment choisir ?

2.1.1 Premier critère : réutilisation

Scénario : \(B\) implémentations de bas niveau, \(H\) implémentations de haut niveau (utilisant le bas niveau, abstrait)

Objectif : obtenir \(B.H\) implémentations sans avoir à recopier des implémentations

  • Agrégation simple : recopie obligatoire
    • pour une implémentation de bas niveau : \(H\) copies
    • pour une implémentation de haut niveau : \(B\) copies
  • Héritage ascendant : recopie obligatoire
    • pour une implémentation de bas niveau : pas de recopie - factorisation réussie
    • pour une implémentation de haut niveau : \(B\) copies
  • Héritage descendant : recopie obligatoire
    • pour une implémentation de bas niveau : \(H\) copies
    • pour une implémentation de haut niveau : pas de recopie - factorisation réussie
  • Héritage multiple : pas de recopie
    • pour une implémentation de bas niveau : pas de recopie - factorisation réussie
    • pour une implémentation de haut niveau : pas de recopie - factorisation réussie
  • Agrégation avec délégation : pas de recopie
    • pour une implémentation de bas niveau : pas de recopie - factorisation réussie
    • pour une implémentation de haut niveau : pas de recopie - factorisation réussie

Conclusion : l'héritage multiple et l'agrégation avec délégation maximisent la réutilisation.

2.1.2 Second critère : dépendance statique ou dynamique

Une implémentation de haut niveau dépend de l'implémentation de bas niveau qu'elle utilise. Cette dépendance peut être

  • statique, c'est-à-dire fixée dès la compilation, ou
  • dynamique, c'est-à-dire fixée lors de l'exécution, et donc possiblement variable.

(Une dépendance dynamique peut s'avérer statique : il suffit que la valeur affectée lors de l'exécution à l'implémentation basse soit une constante, connue statiquement.)

Avec l'héritage (et l'agrégation simple), la dépendance est statique. Avec l'agrégation avec délégation, la dépendance est dynamique.

Conclusion : si la dépendance doit être dynamique, utiliser l'agrégation avec délégation. Sinon, utiliser n'importe quelle technique.

3 Immutabilité

3.1 Avantages

  1. Raisonnement : logique + localité. 
    x.equals(x.somme(un))

    Expression s'évaluant en true si la donnée x est mutable ! 

    f(x)

    La valeur de x avant et après l'appel est la même si la donnée est immutable.

  2. Concurrence : aucun contrôle de concurrence nécessaire (le problème venant des écritures).
  3. Compatibilité avec le hachage : utilisation de données immutables comme valeurs de hachage.

3.2 Désavantages

Efficacité lors d'une mise à jour (copie contre modification en place)

A nuancer

  1. Une pratique défensive souvent recommandée pour les données mutables consiste à passer les arguments par copie pour éviter tout effet de bord.
  2. Il est possible de maximiser le partage de données immutables pour améliorer l'efficacité : cf. patron "Poids plume".

Expérimentation : cf. StringVSStringBuilder.

Rapport de 1000 dans l'exécution ! Explication de cette différence très importante : la complexité n'est pas la même (linéaire versus quadratique).

3.3 Implémentation

3.3.1 Critères d'immutabilité

Type immutable ? Problème indécidable.

Voici quelques critères suffisants.

  • Les types primitifs sont immutables.
  • Un type est immutable si toutes les conditions suivantes sont vérifiées.
    • Type correspondant à une classe finale (sans sous-classe)
    • Attributs en lecture seulement (private final A x)
    • Initialisation des attributs dans le constructeur
    • Immutabilité des objets référencés par les attributs - Deux possibilités
      • Type immutable : pas de problème
      • Type non immutable : confinement de la référence dans du code contenant celui de la classe et absence d'appels de méthode pouvant muter l'état dans ce code

3.3.2 Définition

Implémenter des données immutables est simple pour des types non récursifs, compliqué sinon dès lors qu'on recherche l'efficacité.

Pour un point de vue général sur la question de l'implémentation de données immutables, voir l'ouvrage de Chris Okasaki : "Purely Functional Data Structures". Il s'avère que la complexité (logique) des implémentations efficaces est un frein à leur adoption. Actuellement, les bibliothèques de données immutables ne sont pas optimales et obligent à suivre la stratégie indiquée ci-dessous : passer à des données mutables dès lors que les calculs deviennent intensifs.

3.3.3 Deux exemples, du simple (les complexes) au compliqué (les files)

Pour représenter des complexes par un type immutable, aucune difficulté : pour chaque classe d'implémentation (finale),

  • initialiser l'état dans les constructeurs,
  • ne plus le modifier ensuite.

Pour des files respectant une discipline FIFO (first in, first out), c'est beaucoup plus difficile si on souhaite une implémentation efficace (c'est-à-dire avec la même complexité que l'implémentation mutable de référence). 

interface File {
  File ajout(E dernierDansFile);
  E tete();
  File retrait();
}
3.3.3.1 Implémentation mutable classique avec des listes doublement chaînées

Une file est implémentée par une enveloppe d'une liste doublement chaînée, enveloppe pointant sur les deux extrémités de la liste. Les modifications se font en place (mutabilité).

  • ajout(e) : temps constant (O(1))
    • On ajoute en queue de liste l'élément.
  • tete() : temps constant (O(1))
    • On lit la valeur en tête de liste.
  • retrait() : temps constant (O(1))
    • On retire l'élément en tête de liste.
3.3.3.2 Implémentation immutable avec des listes doublement chaînées

Une file est implémentée par une enveloppe d'une liste doublement chaînée, enveloppe pointant sur les deux extrémités de la liste. Les modifications se font sur de nouvelles versions de la file (immutabilité).

  • ajout(e) : temps linéaire (O(n), n étant la taille de la file)
    • Lorsqu'on ajoute en queue l'élément, on doit modifier le dernier élément de la file à cause du double chaînage.
    • Comme l'implémentation doit être immutable , on est obligé de réaliser une copie.
  • tete() : temps constant (O(1))
    • On renvoie la valeur de l'élément en tête de liste.
  • retrait() : temps linéaire (O(n))
    • Lorsqu'on retire en tête l'élément, on doit modifier le nouveau premier élément de la file à cause du double chaînage.
    • Comme l'implémentation doit être immutable , on est obligé de réaliser une copie.
  • retrait() : temps constant (O(1)) avec une astuce
    • Pour retirer l'élément en tête de liste, il suffit que la nouvelle enveloppe renvoyée pointe sur le second élément au lieu du premier. On évite donc le retrait.
    • Il reste un problème à résoudre : si le premier élément chaîné ne sert plus, c'est-à-dire n'est référencé (directement ou indirectement) par aucune enveloppe, on aimerait pouvoir le détruire. Cependant, à cause du double chaînage, il est toujours accessible par le second élément. Il faut donc indiquer au ramasse-miettes ("garbage collector") que seul le référencement via une enveloppe de la tête vers la queue doit être pris en compte ; le référencement de la queue vers la tête doit en revanche être ignoré. La solution est d'utiliser des références faibles (cf. la documentation de la classe WeakReference http://docs.oracle.com/javase/8/docs/api/java/lang/ref/WeakReference.html).

Conclusion : cette solution n'est pas satisfaisante puisqu'on veut éviter des complexités linéaires.

3.3.3.3 Implémentation immutable utilisant des listes simplement chaînées

Première tentative : une file est implémentée par une enveloppe d'une liste simplement chaînée.

  • ajout(e) : temps constant (O(1))
    • On renvoie une nouvelle enveloppe contenant une nouvelle liste avec l'élément ajouté en tête et le reste partagé.
  • tete() : temps linéaire (O(n))
    • On inverse la liste et renvoie le premier élément de la liste inversée.
  • retrait() : temps linéaire (O(n))
    • On inverse la liste, retire le premier élément, et renvoie une enveloppe contenant la liste modifiée, une nouvelle fois inversée.

Conclusion : cette solution n'est pas satisfaisante puisqu'on veut éviter des complexités linéaires.

Seconde tentative : une file est implémentée par une enveloppe de deux listes chaînées. La première représente la tête de la file, la seconde, la queue de la file. Elles sont en ordre inverse relativement aux temps d'arrivée dans la file. 

[1 2 3 4 5] représenté par ([1 2 3], [5 4]) (tête à gauche, queue à droite)
  • ajout(e) : temps constant (O(1))
    • On renvoie une nouvelle enveloppe contenant la liste de tête et une nouvelle liste de queue avec l'élément ajouté en tête.
  • tete() : temps constant (O(1))
    • On renvoie la valeur de l'élément en tête de la liste de tête.
  • retrait() : temps linéaire (O(1))
    • On renvoie une nouvelle enveloppe contenant pour liste de tête la sous-liste suivant le premier élément et la liste de queue.

A première vue, le pari est gagné. Cependant, il n'est possible de lire ou retirer la tête que si la liste de tête n'est pas vide. Lorsque la liste de tête est vide, on doit inverser la liste de queue pour la placer en liste de tête.

Exemple d'une succession de retraits 

   ([1 2 3], [5 4]) 

-> ([2 3], [5 4])

-> ([3], [5 4])

-> ([], [5 4]) ~ ([4 5], []) (inversion)

-> ([ 5], [])

Si l'inversion est en temps linéaire, il est cependant possible d'amortir le temps de l'inversion sur le temps des ajouts qui ont précédé l'inversion : l'exécution redevient en temps constant. Cet amortissement n'est possible que si la file n'est pas partagée.

Conclusion : cette solution est satisfaisante si la file n'est pas partagée.

  • Seconde tentative : voir la solution astucieuse apportée par Okasaki, section 8.4 de l'ouvrage cité plus haut.

Remarque : je proposerai comme sujet de PFE l'implémentation d'une bibliothèque de collections immutables, en suivant les méthodes et techniques développées par Okasaki.

3.4 Architecture

Recommandation :

  • Interfaces utilisant des types immutables
  • Implémentations convertissant si nécessaire (lors de calculs intensifs) les types immutables en types mutables

Modèle 

TypeImmutable f(TypeImmutable x){
  TypeMutableEquivalent y = conversion(x);
  ... // Algorithme coûteux
  return conversionInverse(resultatMutable);

Exemple de couple type immutable/type mutable : String*/*StringBuilder.

Last Updated 2015-11-02T13:30+0100. Comments or questions: Send a mail.