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é.

liste ::= Vide | Cons(e, liste)

public enum Singleton{
  SINGLETON;
  // méthodes
}

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) 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).

\[\small \begin{array}{c} p_1 \ldots p_n \\ \hline c \\ \end{array} \]

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.

\[\small \begin{array}{c} \emptyset \\ \hline c \\ \end{array} \]

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.

\[\small \begin{array}{ccc} \begin{array}{c} \emptyset \\ \hline (\mathrm{Vide} : \mathrm{Liste}) \end{array} & \quad & \begin{array}{c} (e : \mathrm{Element}) \quad (l : \mathrm{Liste})\\ \hline (\mathrm{Cons}(e, l) : \mathrm{Liste}) \end{array} \end{array} \]

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.

\[\small \begin{array}{ccc} \begin{array}{c} \emptyset \\ \hline (\mathrm{Vide} \mapsto 0) \end{array} & \quad & \begin{array}{c} (e : \mathrm{Element}) \quad (l \mapsto s)\\ \hline (\mathrm{Cons}(e, l) \mapsto (1 + s)) \end{array} \end{array} \]

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\) \[\small \begin{array}{c} p_1 \ldots p_n \\ \hline c \end{array} \] 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\).

\[\small \begin{array}{ccc} \begin{array}{c} (m : M) \\ \hline (m : P) \end{array} & \quad & \begin{array}{c} (m_1 : P) \quad (m_2 : P)\\ \hline (m_1.m_2 : P) \end{array} \end{array} \]

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.

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
Visiteur accueillir(Visiteur v); // cas immutable

On implémente ensuite l'interface Visiteur. Elle déclare une méthode par cas de définition dans le composite. Les implémentations réalisent la visite du composite passé en argument.

void visiterX(Composite c); // cas mutable
// ou
Visiteur visiterX(Composite c); // cas immutable

Cf. l'unité de compilation EnsemblesIterablesAvecIterateurEtVisiteur.

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).

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

La notation \(\lambda\) (la lettre grecque 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 voici sa grammaire.

\[ 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.

\[\small \begin{array}{c} \emptyset \\ \hline \lambda x.e \rightarrow \lambda x.e \end{array} \]

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\).

\[\small \begin{array}{c} (e_1 \rightarrow \lambda x.e) \quad (e_2 \rightarrow a) \quad (e[a/x] \rightarrow r) \\ \hline (e_1 e_2) \rightarrow r \end{array} \]

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 posséder 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. 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.

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