UP | HOME

Patrons de conception - Description et conception

Table of Contents

1 Patron de conception : une solution à un problème d'architecture logicielle

Un patron de conception

  • possède un nom évocateur,
  • résout un problème d'architecture logicielle, avec des avantages et des inconvénients.

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.

  • Point de vue descriptif : description des patrons, en reliant leur nom au problème qu'il résout.
  • Point de vue explicatif : conception des patrons, en expliquant leur structure par des principes généraux.

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

2 Une langue véhiculaire

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

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

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

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

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

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

2.1.5 Adaptateur (Adapter)

  • Comment adapter des objets à une interface (par exemple, des points du plan devenant des complexes, ou encore l'envoi de messages avec en-têtes en utilisant des messages sans en-têtes) ?
    • En utilisant un adaptateur.

Cf. le paquet patrons.adaptateur pour un exemple.

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

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

2.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. aussi le paquet patrons.decorateur pour un autre exemple.

2.1.9 Proxy

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

2.1.10 Façade

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

2.1.11 Médiateur (Mediator)

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

2.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. aussi le paquet patrons.observateur pour un autre exemple.

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

2.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, 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.

Sorry, your browser does not support SVG.

Figure 1: Couches d'une classe d'implémentation

2.2.1 Etat

Slogan principal :

  • état = couche basse
  • couche haute = interface enrichie permettant de mieux gérer l'état (partage, sauvegarde, réification)

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

2.2.2 Constructeur

Slogan principal :

  • construction des objets = une couche haute dédiée
  • couche basse = les constructeurs

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

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

Patterns_AggregationDelegation.png

Figure 2: 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, des interfaces concrètes, pourrait-on dire.

Cf. le paquet patrons.heritageMultiple.

Patterns_MultipleInheritance.png

Figure 3: Héritage multiple - Double factorisation

2.2.3.2 Factorisation par héritage descendant
  • Un patron de conception représentant cette approche : Guide de méthode (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.

Patterns_TopDownInheritance.png

Figure 4: Héritage - Approche descendante - Factorisation de la couche haute

2.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)
2.2.4.1 Simple délégation, deux couches distinctes
  • Adaptateur (Adapter)
  • Etat (State)
  • Stratégie (Strategy)
  • Itérateur (Iterator)

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

2.2.4.2 Simple délégation, une interface commune pour les deux couches
  • Décorateur (Decorator)
  • Procuration (Proxy)

  • 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, il devient impossible d'utiliser la solution par héritage multiple. En effet, un conflit de noms apparaît.

Cf. le paquet patrons.decorateur pour un exemple.

2.2.4.3 Agrégations multiples avec différents protocoles de communication
  • Façade
  • Médiateur (Mediator)
  • Observateur (Observer)
  • Chaîne de responsabilités (Chain of Responsibility)

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

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

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

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

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

Exemple : Adaptateur

  • Couche basse : service existant avec une interface à adapter
  • Couche haute : nouveau service avec une interface adaptée, client du service existant

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.

Exemple : dual du patron Adaptateur, variante du patron Stratégie pour l'adaptation

  • Couche haute : service existant réalisant l'adaptation
  • Couche basse : nouveau client définissant l'adapté qui est injecté dans la couche haute

Cf. dans le paquet patrons.adaptateur :

  • l'interface NouvelAgent,
  • l'adaptateur AgentAdaptateur,
  • son dual, DualAgentAdaptateur.

Patterns_AdapterDual.png

Figure 5: Adaptateur et son dual

Cf. aussi le cours sur l'injection de dépendances.

2.3.3 Des patrons construits par dualité

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

2.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 Guide de méthode ("Method template") s'obtient par dualité.

Héritage - Approche ascendante

  • Serveur : couche basse
  • Client : couche haute obtenue par héritage de la couche basse

Héritage - Approche descendante

  • Serveur : couche haute
  • Client : couche basse complétant l'implémentation de la couche haute par héritage

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

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

Patterns_BottomUpInheritance.png

Figure 6: Héritage - Approche ascendante - Factorisation de la couche basse

Patterns_TopDownInheritance.png

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

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

2.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 à partir de la collection sous-jacente une nouvelle valeur (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.

Exemple : la méthode forEach de l'interface Iterable (depuis la version 8 de Java)

  • Elle attend comme argument le code de l'itéré, sous la forme d'un consommateur de type Consumer : c'est l'injection de dépendance.
  • Elle réalise en interne l'énumération, en appelant l'itérateur sous-jacent et l'itéré passé en argument. Cette énumération peut être optimisée, par exemple réalisée en parallèle.

Cf. l'exemple du paquet session2.demo.patrons.iteration.

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

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

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

3.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, 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.

3.4 Les lambda-expressions (à partir de Java 8)

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.

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

3.5 Vers une approche fonctionnelle

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 :

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 session2.demo.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.

3.6 Récapitulatif des patrons fonctionnels

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

Version history: v1: 2015-11-02; v2:2016-09-01[*text]; v3:2016-10-24[update]; v4: 2016-11-04[*text].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.