UP | HOME

Patrons de conception - Description et conception

Un patron de conception

Les patrons de conception fournissent le vocabulaire d'une langue véhiculaire pour les développeurs : celle-ci peut alors servir à communiquer des informations pertinentes pour une architecture logicielle. Certains patrons de conception sont idiomatiques : particuliers à la programmation à objets, ils servent à exprimer des patrons naturels dans d'autres paradigmes de programmation, comme celui de la programmation fonctionnelle. Dans la suite, on adopte deux points de vue.

Remarque : le code développé se trouve dans le paquet session3.demo.

Table of Contents

1 Une langue véhiculaire

Par langue véhiculaire, on entend une langue permettant la communication, indépendamment du langage de programmation utilisé.

1.1 Motivations

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

1.1.1 Poids plume (Flyweight)

Programmation d'un traitement de texte

  • Comment représenter de manière économe des caractères avec des informations sur la fonte ?
    • En utilisant le partage.

Complément - Données immutables : intérêt du partage

1.1.2 Souvenir (Memento)

Programmation d'un éditeur

  • Comment gérer les versions d'un texte ?
    • En réalisant des sauvegardes.

La sauvegarde d'un état peut être intégrale ou incrémentale. Habituellement, on fait régulièrement des sauvegardes intégrales, mais avec une période importante, et on fait sinon des sauvegardes incrémentales, qui ne mémorisent que les différences. Les sauvegardes sont déclenchées à chaque modification de l'état à sauvegarder.

1.1.3 Etat (State)

Les entiers naturels

  • Comment passer d'une représentation à l'autre ?
    • En réifiant l'état.

Ce patron correspond à une agrégation avec délégation dans le cas d'une architecture où l'état forme la couche basse. Lorsqu'on passe d'une agrégation simple à une agrégation avec délégation, les attributs du simple agrégat se transforment en les attributs de l'objet agrégé.

// Agrégation simple
class NatParInt implements Nat {
  private int val; // Un attribut formant l'état
  ...
}
// Agrégation avec délégation
class NatDeleguantEtat implements Nat {
  private EtatNaturelPur etat; // Réification de l'état
  ...
}

1.1.4 Singleton (Singleton)

  • Comment représenter les constantes d'un type abstrait (comme une liste vide) ?
    • Par un singleton.

Pour les définitions inductives des types abstraits, on utilise la notation de Backus-Naur, comme ci-dessous.

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

Pour représenter le cas constant (Vide), on utilise un singleton. En Java, la forme moderne de l'implémentation d'un singleton est une classe enum (énumération).

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

Elle implique que la classe n'est pas générique. Si elle est générique et que pour tout type, on souhaite obtenir un objet singleton, on utilise une table associant à une représentation de type (de type Class<?>) le singleton.

1.1.5 Adaptateur (Adapter)

  • Comment adapter des objets à une interface (par exemple, des points du plan devenant des complexes) ?
    • En utilisant un adaptateur.

Cf. le paquet session3.demo.patrons.adaptateur.

1.1.6 Stratégie (Strategy)

  • Comment changer d'algorithme de calcul ?
    • En réifiant l'algorithme pour permettre ainsi de changer de stratégie de résolution.
// Calcul avec une stratégie particulière
public Nat somme(Nat x) {
  return this.creerNatAvecValeur(this.val() + x.val());
}
// Calcul avec une stratégie variable
private StrategieCalculSomme calculSomme;
public Nat somme(Nat x) {
  return this.calculSomme.appliquer(this, x);
}

1.1.7 Itérateur (Iterator)

  • Comment parcourir une structure de données ?
    • En utilisant un itérateur, qui permet de décomposer la structure en un élément suivi du reste de la structure.

Complément - Impact de la définition d'une interface sur l'itération

1.1.8 Décorateur (Decorator)

  • Comment ajouter un tampon à un flux ?
    • En le décorant

Cf. l'exemple des flux d'entrée et de sortie (java.io.OutputStream et java.io.BufferedOutputStream).

Cf. le paquet session3.demo.patrons.decorateur.

1.1.9 Proxy

  • Comment contrôler l'accès à une ressource ?
    • En intercalant un proxy.

1.1.10 Façade

  • Comment accéder simultanément à Flickr et Picasa (services de gestions de photographies) ?
    • En intercalant une façade permettant de s'interfacer avec Flickr et Picasa d'une manière simplifiée.

1.1.11 Médiateur (Mediator)

  • Comment coordonner plusieurs activités ?
    • En passant par un médiateur.

1.1.12 Observateur (Observer)

  • Comment être notifié d'un évènement qu'on souhaite observer ?
    • En diffusant l'événement aux observateurs enregistrés.

Cf. java.util.Observer et Observable.

Cf. le paquet session3.demo.patrons.observateur.

1.1.13 Chaîne de responsabilité (Chain of responsibility)

  • Comment prononcer une syllabe ?
    • En appliquant une série de règles de transformations, permettant de passer d'une syllabe à des phonèmes.

1.2 Principes de conception

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.

../../../images/progMod15_classeImplem-couches.svg

Couches d'une classe d'implémentation

1.2.1 Etat

Slogan principal : état = couche basse

  • Rappel : données mutables vs données immutables
  • Partage de données immutables : Poids plume (Flyweight)
    • Application de la transparence référentielle pour diminuer la consommation mémoire
  • Sauvegarde et restauration pour la partie mutable d'un état : Memento
    • Possibilité de mécanismes transactionnels
  • Réification de l'état : Etat (State)
    • Possibilité de changer la représentation de l'état (sans changer d'état)

1.2.2 Constructeur

Slogan principal : construction des objets = une couche dédiée

  • Fabriques : Méthode de fabrication (Factory Method), Fabrique abstraite (Abstract Factory)
    • Méthode dédiée
      • Cas particuliers : clonage avec Prototype, décomposition fonctionnelle avec Assemblage (Builder)
    • Classe dédiée
  • Remplacement de l'appel direct du constructeur par l'appel d'une abstraction
    • Cas particulier : Singleton
  • Effet recherché : dépendance relativement aux classes d'implémentation restreinte aux fabriques (appels des constructeurs)

1.2.3 Architecture en couches - Factorisation

Les patrons de conception peuvent se classer suivant leur capacité de factorisation des couches haute et basse.

  • Deux couches avec deux interfaces
    • Une couche haute ou externe implémentée en utilisant la couche basse ou interne
    • Une couche basse servant la couche haute
1.2.3.1 Factorisation des implémentations des deux couches

Il existe un patron de conception pour la solution par agrégation avec délégation : le patron Pont (Bridge). Ce nom est plutôt mal choisi : le pont, qui relie la couche haute à la couche basse, exprime la relation d'utilisation entre la couche haute et celle basse, relation qui n'est pas symétrique. De plus, comme l'agrégation avec délégation est la solution architecturale retenue pour (quasiment) tous les patrons de conception, il ne s'agit pas véritablement d'un patron mais plutôt d'un principe architectural général. Il reste que la motivation pour ce patron (ou ce principe) est la double factorisation obtenue.

Voici un exemple typique d'une telle architecture.

  • Couche haute : interface Agent avec une méthode envoyer
  • Couche basse : interface Canal avec une méthode emettre
  • Implémentation de la méthode envoyer en utilisant la méthode emettre
  • Plusieurs implémentations de la méthode envoyer (émission par paquets, émission en un bloc, etc.)
  • Plusieurs implémentations de la méthode emettre (utilisation de différents protocoles de communication, etc.)

Cf. le paquet patrons.agregationDelegation.

medias/Patterns_AggregationDelegation.png

Agrégation avec délégation - Double factorisation

Il existe une autre solution permettant d'obtenir la double factorisation : l'héritage multiple, possible en Java en utilisant une (et une seule classe) et un ou plusieurs traits, soit des interfaces avec des méthodes par défaut.

Cf. le paquet patrons.heritageMultiple.

medias/Patterns_MultipleInheritance.png

Héritage multiple - Double factorisation

1.2.3.2 Factorisation par héritage descendant
  • Un patron de conception représentant cette approche : Méthode modèle (Template Method)
    • Une classe abstraite (ou une interface en Java 8) implémentant la couche haute, la couche basse étant abstraite
    • Une classe concrète héritant de la classe abstraite et implémentant la couche basse

Cf. le paquet patrons.heritageDescendant.

medias/Patterns_TopDownInheritance.png

Héritage - Approche descendante - Factorisation de la couche haute

1.2.4 Architecture en couches - Communication

Les patrons de conception peuvent se classer suivant la complexité du protocole de communication entre la couche haute et celle basse : de la simple délégation à un dialogue complexe.

  • Deux couches avec deux interfaces
    • Une couche haute ou externe implémentée en utilisant la couche basse ou interne
    • Une couche basse servant la couche haute
  • Utilisation de l'agrégation avec délégation pour factoriser
  • Généralement, alternative possible utilisant l'héritage multiple (exception lorsqu'une dépendance dynamique est requise)
1.2.4.1 Simple délégation, deux couches distinctes

Patrons

  • Adaptateur (Adapter)
  • Etat (State)
  • Stratégie (Strategy)
  • Itérateur (Iterator)

Propriétés

  • Protocole simple : l'agrégat appelle l'agrégé pour une délégation.
  • Des interfaces distinctes pour les deux couches
  • Problèmes résolus
    • Conversion : Adaptateur
    • Réification
      • Etat et accesseurs (Etat, Iterator)
      • Algorithme interne (Stratégie)

Cf. le paquet patrons.adaptateur pour un exemple.

1.2.4.2 Simple délégation, une interface commune pour les deux couches

Patrons

  • Décorateur (Decorator)
  • Procuration (Proxy)

Propriétés

  • Protocole simple : l'agrégat appelle l'agrégé pour une délégation.
  • Même interface pour les deux couches
  • Différence : le rôle (décoration contre contrôle d'accès)

Remarque : lorsque les deux interfaces sont identiques, l'héritage multiple devient impossible. En effet, un conflit de noms apparaît. Seul un héritage simple est possible, avec une factorisation simple soit de la couche basse (héritage ascendant) soit de la couche haute (héritage descendant).

Cf. le paquet patrons.decorateur pour un exemple.

1.2.4.3 Agrégations multiples avec différents protocoles de communication

Patrons

  • Façade
  • Médiateur (Mediator)
  • Observateur (Observer)
  • Chaîne de responsabilités (Chain of Responsibility)

Propriétés

  • Agrégat possédant plusieurs objets agrégés
  • Protocole pouvant être complexe

Détail

  • Façade : plusieurs objets agrégés (avec des interfaces différentes)
  • Médiateur : plusieurs objets agrégés collaborant ensemble via le médiateur (avec des interfaces différentes)
  • Observateur : plusieurs objets agrégés notifiés par l'agrégat puis observant l'agrégat
  • Chaîne de responsabilité : chaîne d'objets agrégés, présentant la même interface, traitant successivement les requêtes

Cf. le paquet patrons.observateur pour un exemple.

1.3 Dualité par inversion du contrôle

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.

1.3.1 Bibliothèques et frameworks

Reprenons l'architecture élémentaire formée de la fonction principale et du module adjoint.

Premier scénario : application utilisant une bibliothèque

  • Client : fonction principale
  • Serveur : module adjoint

Le module adjoint est alors appelé une bibliothèque.

Second scénario : instanciation d'un framework

  • Client : module adjoint
  • Serveur : fonction principale

La fonction principale est alors appelée un framework (ou cadriciel, d'usage plutôt rare). Le module adjoint s'enregistre d'abord auprès du framework, autrement dit une dépendance relativement au module adjoint est injectée dans le framework. Après cette injection, le framework peut appeler le module. C'est une application du principe dit d'Hollywood, par référence aux pratiques des producteurs face aux acteurs candidats à un rôle : "do not call us, we will call you".

Conclusion : un framework est le dual d'une bibliothèque.

Exemples

  • Bibliothèque : collections de l'API standard
  • Framework : Swing (interface graphique)

1.3.2 Architecture en couches et injection de dépendances

Les patrons de conception correspondent très majoritairement à une architecture en couches. On peut interpréter une telle architecture de la manière suivante.

  • Serveur : couche basse
  • Client : couche haute

Un patron de conception correspond alors à la définition d'un client, étant donné un service existant. Ce client définit lui-même un nouveau service, dont le nom est celui du patron de conception.

L'architecture duale se définit ainsi.

  • Serveur : couche haute
  • Client : couche basse

Pour être cohérent avec le modèle client-serveur, il est nécessaire que le client, l'ancien serveur, s'agrège au serveur, l'ancien client : c'est l'injection d'une dépendance, associée à une inversion de contrôle.

1.3.3 Des patrons construits par dualité

On peut définir par dualité des patrons de conception à partir d'architectures existantes.

1.3.3.1 Dualité dans l'héritage : approches descendante et ascendante

Les deux techniques d'héritage, bottom-up ou ascendante et top-down ou descendante, utilisées pour factoriser respectivement les couches basse et haute dans les architectures en couches, présentent aussi une dualité. Autrement dit, le patron de conception Méthode modèle s'obtient par dualité.

Héritage - Approche ascendante

  • Serveur : couche basse
  • Client : couche haute

Héritage - Approche descendante

  • Serveur : couche haute
  • Client : couche basse

L'injection de dépendance se fait statiquement (lors de la compilation).

Cf. les paquets patrons.heritageDescendant et patrons.heritageAscendant.

medias/Patterns_BottomUpInheritance.png

Héritage - Approche ascendante - Factorisation de la couche basse

medias/Patterns_TopDownInheritance.png

Héritage - Approche duale descendante - Factorisation de la couche haute

1.3.3.2 Observateur

Considérons le scénario suivant : un client avertit un serveur d'un événement significatif. Il peut s'agir d'une simple notification, ce qui laisse la latitude au serveur de rappeler le client pour avoir des informations concernant l'événement, ou d'une diffusion de l'événement : on parle de mode de communication "pull" (en traction pour le serveur) ou "push" (en poussée pour le client) respectivement.

L'architecture duale correspond au patron Observateur. Le client, l'observateur, s'enregistre auprès du serveur, l'observable. Le serveur avertit les clients enregistrés de tout événement significatif. Deux modes de communication sont possibles, "push" ou "pull" : poussée des informations par le serveur ou traction des informations par le client.

Cf. le paquet patrons.observateur qui propose une version générique des types Observable et Observer de l'API du langage Java. Les interfaces Observable et Observateur sont paramétrées par trois types : le type du serveur, le type des clients et le type des événements échangés.

1.3.3.3 Itérateur et itéré

Revenons au patron Itérateur. Lorsqu'on l'utilise, on peut distinguer trois acteurs.

  • Itérateur (Iterator) : un serveur permettant de réaliser une itération en produisant une nouvelle valeur de la collection sous-jacente (s'il en existe encore)
  • Itéré (Iteratee) : un serveur permettant de réaliser une action à chaque itération, bref de réaliser une action itérée, ou répétée
  • Enumérateur (Enumerator) : un client qui appelle l'itérateur pour obtenir une nouvelle valeur puis l'itéré pour obtenir le traitement de cette valeur

Il est possible d'inverser le contrôle entre l'énumérateur et l'itéré.

  • Client : l'itéré
  • Serveur : l'énumérateur utilisant l'itérateur

Avec cette architecture, l'itéré joue le rôle d'un transducteur (un automate réalisant des traductions à chaque transition) : il reçoit successivement les valeurs de l'énumérateur pour les traduire, par l'action qu'il réalise sur chacune d'elles. Cette architecture duale correspond à un patron appelé Itéré (Iteratee), qu'on pourrait appeler aussi Transducteur. On utilise ce patron pour factoriser l'énumération et se concentrer sur la définition des itérés.

2 Des patrons idiomatiques

Par idiomatique, on entend ici ce qui est propre au style de programmation objet. Un des aspects originaux des patrons de conception dans les langages à objets comme Java concerne la traduction de patrons de conception propres à la programmation fonctionnelle.

Une alternative à l'usage de patrons de conception serait d'utiliser un autre langage de programmation, plus étendu (par exemple, Scala au lieu de Java), qui intégrerait des constructions syntaxiques permettant d'exprimer directement les patrons de conception.

2.1 Définitions inductives

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.

2.2 Représentation des définitions inductives

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.

2.3 Représentation des fonctions récursives

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 session3.demo.ensembles.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.

2.4 Les lambda-expressions

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.

2.5 Récapitulatif des patrons fonctionnels

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

Last Updated 2016-01-25T13:27+0100. Comments or questions: Send a mail.