Patrons de conception - Description et conception

Pour quelques patrons de conception utiles et très utilisés, on décrit les problèmes qu'ils résolvent en donnant des exemples. En passant, on aborde quelques points transversaux importants concernant la modularité.

La structure des patrons de conception consiste essentiellement en des variations d'une architecture en couches implémentée suivant la technique de l'agrégation avec délégation. Une implémentation alternative est possible, en utilisant l'héritage multiple.

En résumé

• Une structure commune pour les patrons de conception : l'architecture en couches
• Un parti pris : préférence pour l'agrégation avec délégation
  • Double factorisation pour la partie basse et celle haute (architecture à deux couches)
  • Injection dynamique des dépendances relatives aux classes d'implémentation
  • Existence d'une alternative pour l'implémentation : l'héritage multiple (classe et traits (interfaces avec des méthodes par défaut, ou interfaces concrètes) en Java) avec la même double factorisation mais une injection statique des dépendances

La classification ci-dessous s'appuie sur la structure en couches des classes.

L'architecture d'une application peut être modélisée comme un ensemble d'acteurs s'échangeant des données en communiquant par l'envoi de messages. Les acteurs sont plutôt en petit nombre et possèdent habituellement un état. A l'opposé, les données échangées peuvent être en grand nombre et sont plutôt immutables.

Par exemple, à la plus grande échelle, on peut considérer deux acteurs :

• la fonction principale (dite main en Java),
• le reste du programme, qu'on appellera le module adjoint.

Lors de l'exécution, la fonction principale appelle le module adjoint.

Très souvent, un acteur joue un des deux rôles suivants, duaux.

• Client : envoi de requêtes vers les serveurs, réception de réponses provenant des serveurs
• Serveur : réception des requêtes venant des clients, envoi des réponses aux clients

Dans le modèle client-serveur, initialement, les clients connaissent les serveurs auxquels ils s'adressent, alors que les serveurs ne connaissent pas les clients. Par exemple, la fonction principale est cliente de son module adjoint, le serveur connu de la fonction principale.

Cette interaction fondamentale peut être complexifiée aisément : il suffit au client de passer au serveur non seulement un canal de retour pour obtenir la réponse, mais une continuation, c'est-à-dire une fonction de retour ("call-back") que le serveur peut appeler quand il le souhaite.

Au total, un acteur peut être soit un client, soit un serveur, soit les deux à la fois, ce qui est le cas le plus général.

Supposons une architecture constituée d'un client et d'un serveur. Il est possible de définir une architecture duale, en inversant le contrôle, précisément en intervertissant les rôles entre le client et le serveur. Par cohérence avec le modèle client-serveur, la communication doit être complétée par une requête initiale : le nouveau client, ancien serveur, informe le nouveau serveur, ancien client, qu'il doit être le destinataire de son premier message, correspondant à la requête dans l'architecture initiale. C'est un exemple d'injection de dépendances.

Quand utiliser l'inversion du contrôle ? Elle est utilisée lorsqu'on constate que les clients partagent de nombreux points communs, qu'on cherche alors à factoriser dans un ou plusieurs services.

Voyons quelques exemples importants illustrant cette inversion du contrôle.

Il s'agit de définitions par récurrence. On considère souvent un sous-ensemble remarquable, les définitions par des grammaires dite sans contexte, pour lesquelles il existe une notation simple, dite de Backus-Naur.

Exemple : les listes

liste ::= Vide | Cons(element, liste) (notation de Backus-Naur)

Les types ainsi définis sont dits algébriques. Chaque définition engendre une algèbre particulière, dite algèbre des termes. On peut aisément définir des fonctions de domaine un type algébrique. Il suffit de procéder récursivement. Voici un exemple pour une liste.

• Si la liste \(l\) est vide, renvoyer une certaine valeur.
• Si la liste \(l\) est construite à partir d'un élément \(e\) et d'une liste \(k\), renvoyer une valeur calculée à partir de la liste \(l\) et de la valeur calculée en \(k\).

On réalise un filtrage sur la valeur du type algébrique, en traitant tous les cas de définition d'une manière exhaustive et en veillant à réaliser des appels récursifs uniquement sur des sous-termes de la valeur en entrée.

Au delà des types algébriques, on peut donner une définition inductive par un système d'inférence. Un système d'inférence est formé de règles, chaque règle étant composée d'un ensemble de prémisses et d'une conclusion. Une règle se représente ainsi, \(p_1\), …, \(p_n\) et \(c\) étant des jugements (des propositions logiques, au sens large).

La règle s'interprète ainsi :

si les prémisses \(p_1\), …, \(p_n\) sont valides, alors la conclusion \(c\) est valide.

Un axiome est une règle sans prémisse.

Un jugement est valide lorsqu'il peut être prouvé (démontré) dans le système d'inférence : c'est la conclusion d'une règle dont toutes les prémisses sont des jugements valides. Par exemple, la conclusion d'un axiome est valide.

On peut récrire la définition précédente des listes en utilisant un système d'inférence.

Ce système utilise des jugements de la forme \((x : X)\), exprimant que \(x\) appartient à \(X\). On suppose que les jugements \((e : \mathrm{Element})\) sont des axiomes.

On peut aussi représenter des relations, notamment fonctionnelles, avec un système d'inférence (ce qui est impossible avec une définition inductive utilisant la notation de Backus-Naur). En particulier, pour associer une valeur à un élément d'un type inductif, il suffit de reprendre les règles d'inférence de la définition inductive initiale pour définir les couples de la relation.

Exemple : le calcul de la taille d'une liste.

La relation définie est ici fonctionnelle : elle représente la fonction calculant la taille de la liste. En règle générale, la relation est fonctionnelle si tout jugement valide peut être prouvé d'une seule manière. Si ce n'est pas le cas, il est nécessaire de vérifier que toute preuve du même jugement aboutit à la même valeur.

Il existe des langages de programmation permettant de représenter directement des systèmes d'inférence.

• Langages logiques comme Prolog ou Datalog

  Ils permettent de définir des systèmes d'inférence dont les jugements appartiennent à des algèbres de termes.

• Langages fonctionnels évolués, utilisés dans les assistants à la démonstration comme Coq

  Ils permettent de définir des systèmes d'inférence et de démontrer, parfois automatiquement, la validité d'un jugement.

Les systèmes d'inférence sont intéressants parce qu'ils permettent de formaliser la définition de tout type de données et de tout calcul pour des termes : c'est un modèle universel de calcul.

Dans un langage à objets comme Java, on peut représenter les définitions inductives utilisant la notation de Backus-Naur. On associe à la définition une interface et à chaque cas de la définition une classe implémentant l'interface.

Exemple (cf. le paquet fonctions.induction.liste)

• interface Liste contenant les sélecteurs, destructeurs et constructeurs (ou fabriques) associés à la définition inductive
• deux classes d'implémentation : Vide et Cons

C'est le patron Composite.

Plus généralement, pour une définition inductive quelconque donnée par un système d'inférence, on peut appliquer le patron Composite pour représenter les preuves (démonstrations) dans le système d'inférence.

preuve ::= Axiome | Règle(preuve, ..., preuve)

Par exemple, avec la règle baptisée \(R\)

si on dispose de preuves \(P_1\), …, \(P_n\) des jugements \(p_1\), …, \(p_n\), on peut construire une preuve \(R(P_1, ..., P_n)\) de conclusion \(c\).

Il est ainsi possible de représenter les jugements valides d'un système d'inférence : ce sont les conclusions des preuves construites par la grammaire précédente. Il est important de noter qu'un même jugement peut être la conclusion de plusieurs preuves. Si c'est le cas, il est nécessaire de quotienter l'ensemble des preuves : deux preuves sont équivalentes si elles ont même conclusion. Pour implémenter cette relation d'équivalence, on utilise la méthode equals. Une bonne pratique, particulièrement utile pour calculer, est de définir pour chaque classe d'équivalence un représentant et d'associer à chaque jugement le représentant de sa classe.

Par exemple, supposons qu'on définisse un sous-ensemble \(P\) de l'ensemble des chaînes de caractères, comme le plus petit ensemble contenant un ensemble fixé \(M\) et fermé par concaténation. Voici le système d'inférence définissant cet ensemble \(P\).

Un jugement peut être prouvé de plusieurs manières, du fait de l'associativité de la concaténation : si \(a\), \(b\) et \(c\) appartiennent à \(M\), \(a.b.c\) peut être prouvé de deux manières au moins. On associe à ce système d'inférence une interface et pour chaque règle d'inférence, une classe d'implémentation. On définit dans l'interface

• les sélecteurs permettant de discriminer entre les deux règles,
• les destructeurs associés à chaque règle permettant d'obtenir les prémisses,
• les constructeurs (fabriques) associés à chaque règle.

La relation d'équivalence est définie de deux manières :

• par la méthode equals, en vérifiant l'égalité des conclusions des preuves,
• par la méthode représentant, qui calcule une forme canonique \(b_1.(b_2.(\ldots))\) (par association à droite).

Cf. le paquet fonctions.induction.mot, où on définit l'ensemble des chaînes de caractères de longueur un multiple non nul de 5.

Pour définir une fonction ayant pour domaine un type inductif, une méthode sûre est disponible : la récursivité. On implémente le filtrage par une suite d'alternatives.

Exemple : taille d'une liste (cf. fonctions.induction.liste.Test).

static int taille(Liste<E> l){
  // Récursion : cas de base
  if(l.estVide())
    return 0;
  // Récursion : cas construit
  return 1 + taille(l.reste());
}

Lorsqu'un quotient est nécessaire, on commence par calculer le représentant de la classe d'équivalence.

Exemple : miroir d'un mot (modulo les mots de cinq caractères) (cf. fonctions.induction.mot.Test).

static Mot miroir(Mot m){
  m = m.representant(); // Garantie du passage au quotient
  // Récursion : cas de base
  if(m.estBasique()){
    return m;
  }
  // Récursion : cas construit 
  return m.creerConcatenation(miroir(m.droite()), m.gauche());
}

Plutôt que de réaliser manuellement le filtrage, il est possible de produire une abstraction pour ce service, en se fondant sur la décomposition fournie par le patron Composite.

La solution la plus simple est d'ajouter une méthode à l'interface pour représenter la fonction. Elle doit alors être implémentée dans chaque classe d'implémentation, qui correspond à un cas de la définition inductive. C'est le patron Interpréteur.

Exemple des listes.

interface Liste<E> {
  ...
  // Patron interpréteur (interprétation triviale)
  int taille();
}
class Cons<E> implements Liste<E> {
  ...
  // Cas construit dans Cons
  @Override
  public int taille() { 
    return 1 + this.reste().taille();
  }
}
class Vide<E> implements Liste<E> {
  ...
  // Cas de base dans Vide
  @Override
  public int taille() {
    return 0;
  }
}

De manière générale, on utilise le patron Interpréteur lorsqu'on souhaite interpréter ou évaluer une définition inductive. On ajoute alors une méthode interpreter(Contexte c) dans l'interface du composite. Elle est implémentée par des appels récursifs dans les classes d'implémentation, qui couvrent tous les cas de la définition inductive. Le contexte contient tout ce qui est nécessaire à l'évaluation, une entrée ou les liaisons de variables avec des valeurs si le type inductif décrit des termes avec variables ; il peut être vide aussi, ce qui est souvent le cas.

Le patron Interpréteur est utilisable pour l'implémentation de quelques fonctions. Au delà d'un certain nombre, il risque d'encombrer l'interface avec des méthodes superflues. Le patron Visiteur permet d'éviter cet inconvénient. Il offre un service, la visite récursive de la définition inductive. Le client développe son propre visiteur, en implémentant les calculs correspondant à chaque cas de la définition.

Précisément, on étend l'interface avec une méthode générique permettant l'accueil du visiteur.

void accueillir(Visiteur v); // cas mutable
// ou
<T> T accueillir(Visiteur<T> v); // cas immutable

On implémente ensuite l'interface Visiteur. Elle déclare une méthode par cas de définition dans le composite. Précisément, un visiteur possède la même structure que l'ensemble inductif : si I est cet ensemble inductif, et si on dispose d'un constructeur k de type I x C dans I, alors l'interface Visiteur<T> possède une méthode k de T x C dans T.

I ::= ... | k(I, C) | ...

void k(T x, C c); // cas mutable
// ou
T k(T x, C c); // cas immutable

Remarque : il existe plusieurs variantes des visiteurs. Celle présentée au-dessus permet d'implémenter très simplement une version itérative. Elle s'appuie sur une notion générale d'algèbres utile en informatique.

Cf. l'unité de compilation EnsemblesIterablesAvecIterateurEtVisiteur. En particulier, différentes versions des visiteurs sont données :

• un visiteur dit itératif, programmé récursivement puis itérativement (méthodes accueillir),
• un visiteur dit récursif primitif, programmé récursivement puis itérativement de manière plus compliquée (méthodes filtrer).

Ces qualificatifs viennent de la théorie des fonctions récursives :

• une fonction h de l'ensemble Nat des entiers naturels dans un ensemble A est dite itérative si elle se définit par des équations de la forme suivante :
  • h(0) = c, pour une constance c de A,
  • h(n + 1) = f (h(n)), pour une fonction f de A dans A ;
• une fonction h de Nat dans un ensemble A est dite primitive récursive si elle se définit par des équations de la forme suivante :
  • h(0) = c, pour une constance c de A,
  • h(n + 1) = g(h(n), n), pour une fonction g de A x Nat dans A.

Les visiteurs sont définis ou bien par des classes séparées (première version de la méthode accueillir), ou bien par des fonctions, initialisées dans les tests par des lambda-expressions (secondes versions de la méthode accueillir, méthode filtrer). Ces dernières versions utilisant des lambda-expressions sont plus simples syntaxiquement : cf. le paragraphe suivant qui est consacré à ces expressions.

Les patrons Composite et Visiteur permettent d'obtenir les mêmes propriétés de modularité qu'en programmation fonctionnelle. On définit une grammaire, facilement extensible, puis séparément les fonctions récursives définies sur l'ensemble algébrique engendré par la grammaire. Le filtrage est contrôlé : on est obligé de traiter tous les cas de la définition récursive.

Il n'existe pas de valeurs représentant des fonctions en Java, avant la version 8. Il est cependant facile de réifier (transformer en objet) une fonction. Il suffit de définir une classe possédant une méthode appliquer, définissant le corps de la fonction.

Cette technique est utilisée dans deux patrons principalement.

• patron Commande

  Une fonction ou une procédure est traduite en un objet pour être passée en argument à une fonction ou une méthode. Celle-ci appelle en retour la commande : cette commande est alors une fonction de rappel ("call-back" en anglais). Exemple : Listener dans Swing.

• patron Stratégie

  Un algorithme, correspondant au corps d'une méthode ou d'une fonction, est réifié. Cette réification permet de changer dynamiquement d'algorithme.

Avec Java 8, il est maintenant possible de représenter directement des fonctions : ce sont les expressions dites lambda-expressions, encore appelées lambda-abstractions ou fermetures (closures en anglais). Par la suite, on utilise le symbole grec (\λ\) pour lambda, l'ancêtre du l.

Cf. l'unité de compilation fonctions.Lambda.

La notation \(\lambda\) est utilisée depuis les années 30 (et le logicien américain Church) pour introduire une abstraction relative à une variable. Par exemple, l'identité, la fonction qui à \(x\) associe \(x\), est notée \((\lambda x.x)\). Le \(\lambda\)-calcul, langage créé par Church, est un des plus petits langages de programmation au monde puisque sa grammaire contient trois règles.

\[ e \ ::=\ x \mid \lambda x.e \mid e e. \]

Une expression \(e\) est soit une variable \(x\), soit une abstraction représentant une fonction qui à \(x\) associe une expression \(e\), soit l'application \((e_1 e_2)\) d'une expression \(e_1\) (jouant le rôle d'une fonction) à une autre expression \(e_2\) (jouant le rôle de l'argument). La sémantique est définie par les deux règles suivantes d'inférence.

Une abstraction s'évalue en elle-même.

Pour évaluer une application \((e_1 e_2)\), on évalue \(e_1\) pour obtenir une abstraction \((\lambda x.e)\), puis on évalue \(e_2\) pour obtenir une valeur \(a\), l'argument de l'abstraction, enfin on évalue le corps \(e\) de l'abstraction après avoir remplacé la variable \(x\) par la valeur de l'argument, \(a\).

Le résultat remarquable est le suivant : toute fonction calculable peut être calculée par le \(\lambda\)-calcul.

Pour plus d'informations sur les λ-expressions, cf. le tutoriel en ligne : http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html.

Voici une brève présentation.

On utilise la notation -> pour représenter une \(\lambda\)-abstraction.

 x -> x
 (x, y) -> x + y
 x -> { 
   System.out.println("int : " + x);
   return x;
}

Une abstraction peut lier une ou plusieurs variables. Une variable doit être déclarée avec son type si le compilateur ne peut pas l'inférer.

(int x, int y) -> x + y

Son corps est soit une expression, dont la valeur est implicitement retournée (cf. supra les deux premiers cas), soit un bloc classique correspondant au corps d'une fonction (cf. supra le dernier cas). Le type d'une \(\lambda\)-abstraction est nécessairement une interface dite fonctionnelle. Ces interfaces peuvent être annotées par @FunctionalInterface, à titre informatif, ce qui est recommandé. Elles vérifient une propriété essentielle : elles possèdent une et une seule méthode abstraite, c'est-à-dire sans implémentation, qui représente l'application (de la fonction à un argument). Le paquet java.util.function contient une réserve de telles interfaces fonctionnelles, réserve suffisante en pratique ; il est aussi possible de créer ses propres interfaces fonctionnelles, comme dans l'exemple ci-dessous.

@FunctionalInterface
interface I {
  String f(int x);
}

A côté des \(\lambda\)-abstractions, il existe aussi des abstractions qui sont des constantes : ce sont les méthodes et les fonctions définies dans les classes.

I c = x -> Integer.toString(x);
c = Integer::toString; // Formulation équivalente

L'unique méthode abstraite d'une interface fonctionnelle permet de définir l'application : elle correspond à l'appel de cette méthode. Voici un exemple.

@FunctionalInterface
interface I {
  String f(int x);
}  
...
  I c = x -> Integer.toString(x);
  c.f(9)

Le corps d'une \(\lambda\)-abstraction peut contenir des variables libres, soit des variables locales soit des paramètres. Dans ce cas, ces variables doivent être des constantes (variables déclarées final, ou variables jamais modifiées après initialisation) : cette contrainte peut amener à introduire des variables uniquement pour la vérifier. C'est la même restriction que pour les classes internes. Ainsi, quand une \(\lambda\)-abstraction est créée, elle est fermée : toutes ces variables libres reçoivent la valeur constante qu'elles possèdent. C'est ce processus qui est à l'origine de l'autre nom des \(\lambda\)-abstractions : les fermetures. Enfin, cette fermeture ne s'applique pas aux attributs d'une classe englobante qui seraient utilisés dans le corps d'une \(\lambda\)-abstraction : les attributs ne sont pas des variables, mais plutôt des opérateurs de projection ou de sélection pour un objet. Ainsi, la mention de l'attribut x correspond en réalité à l'expression this.x, la sélection de l'attribut x de l'objet référencé par la constante this. Pour un exemple, cf. la méthode fermeture de la classe A dans l'unité Lambda.

Avec l'introduction des \(\lambda\)-expressions, Java 8 facilite la représentation des fonctions. Ainsi il devient possible de représenter des classes et des objets par leurs équivalents fonctionnels.

Par exemple, l'agrégation avec délégation peut devenir fonctionnelle. Ainsi une interface fonctionnelle exprime la délégation : elle représente une fonction qui prend pour argument une couche basse et renvoie une couche haute déléguant à la couche basse.

Cf. le paquet patrons.agregationFonctionnelle qui présente la version fonctionnelle des classes du paquet patrons.agregationDelegation.

Voici une présentation de cet exemple.

Délégation comme fonction

@FunctionalInterface
public interface Delegation {
  public AgentCommuniquant deleguer(Canal c);
}

Deux implémentations sont proposées : Decoupage et Encapsulation. Une alternative est de définir une fabrique prenant comme argument le corps de la méthode d'envoi, ce qui permet de factoriser la délégation.

public class FabriqueDelegation {
  static Delegation creer(BiConsumer<AgentCommuniquant, String> envoi) {
    return new Delegation() {
      @Override
      public AgentCommuniquant deleguer(Canal c) {
        return new AgentCommuniquant() {
          @Override
          public void envoyer(String msg) {
            envoi.accept(this, msg);
          }
          @Override
          public void emettre(String msg) {
            c.emettre(msg);
          }
        };
      }
    };
  }
}

Pour représenter une fonction qui renvoie void, on utilise l'interface Consumer ou BiConsumer, suivant le nombre d'arguments. Cette fabrique est l'équivalent de la classe abstraite AgentDeleguant.

Enfin, dans la classe de test, on peut initialiser une délégation de la manière suivante.

Delegation d = FabriqueDelegation.creer((agent, msg) -> {
                  ... // code de la méthode envoyer (agent remplaçant this)
               });

Avec cette approche fonctionnelle, on est incité à utiliser l'opération principale entre fonctions, celle de composition, qui existe sous deux formes :

• compose,
• andThen.

Il est aussi possible de définir un opérateur de point fixe, permettant la définition de fonctions récursives comme en Caml.

Cf. le paquet session3.fonctions.induction.java8.

En Caml

let rec factorielle = function
| 0 -> 1
| n -> n*factorielle(n-1);;
val factorielle : int -> int = <fun>

L'opérateur let rec se définit ainsi.

public class PointFixe<A, R> implements Function<A, R> {
  private Function<PointFixe<A, R>, Function<A, R>> def;
    public PointFixe(Function<PointFixe<A, R>, Function<A, R>> def) {
      super();
      this.def = def;
    }
    @Override
    public R apply(A a) {
      return def.apply(this).apply(a);
    }   
}

On l'utilise ainsi (dans l'unité de compilation Naturels).

Function<Integer, Integer> fact1 = 
  new PointFixe<>(fun -> ((Integer n) -> 
    (n == 0) ? 1 : fun.apply(n - 1) * n));

Le premier paramètre fun représente la fonction récursive qu'on définit par l'abstraction qui suit. Si le type est inductif, il est possible d'utiliser une définition par filtrage si le type propose une méthode de décomposition, permettant de traiter chaque cas de la définition.

Function<NatInductif, NatInductif> fact2 = 
  new PointFixe<>(fun -> (n -> n.decomposer(
    () -> n.zero().succ(), // 0 -> 1 
    pred -> fun.apply(pred).mult(pred.succ())) // Succ pred -> fact(pred)*(Succ pred)
  ));

La classe NatInductif représente le type inductif des entiers naturels, défini ainsi.

Nat ::= Zero | Succ Nat

Plutôt que les sélecteurs et les destructeurs d'une part, et un visiteur d'autre part, préconisés précédemment, le type propose une méthode correspondant au filtrage par cas (au "pattern matching") : la méthode decomposer, déclarée dans l'interface FiltreNat<T> de l'unité Naturels.

interface FiltreNat<T> {
  <R> R decomposer(Supplier<R> casZero, Function<T, R> casSucc);
}

A vrai dire, la méthode existe sous deux formes, la seconde permettant un calcul itératif, non récursif.

<R> R decomposerIter(Supplier<R> casZero, Function<T, Function<R, R>> casSucc);

Le cas pour un entier non nul prend un premier argument, le prédécesseur puis un second argument, la valeur calculée pour le prédécesseur, et calcule alors le résultat. Le sélecteur estNul() et le destructeur pred() sont aussi présents et sont implémentés en utilisant decomposer.

C'est une simplification appréciable, inspirée par une solution proposée par Rúnar Bjarnaso, auteur d'un ouvrage remarquable sur la programmation fonctionnelle en Scala. Ce devrait être la forme moderne des patrons Composite et Visiteur en Java.

• Composite
• Interpréteur, Visiteur
• Commande, Stratégie