UP | HOME

Les structures algébriques - Une hiérarchie d'interfaces

Table of Contents

L'ensemble des entiers naturels peut être muni de deux opérations, l'addition et la multiplication. Ces opérations possèdent des propriétés remarquables :

Ainsi l'ensemble des entiers naturels devient un monoïde additif et un monoïde multiplicatif, deux structures algébriques remarquables.

Il en existe bien d'autres. Voici un panorama complet des structures algébriques classiques, des plus simples aux plus complexes.

Voici un schéma récapitulatif.

structuresAlgebriques.png

Figure 1: Une hiérarchie de structures algébriques

Question : comment reproduire en Java ou Typescript la hiérarchie des structures algébriques ? On utilise ci-dessous Java mais la solution en Typescript est analogue.

Les interfaces comme propriétés

On aimerait pouvoir dire que l'interface Nat correspond à deux monoïdes, l'un additif et l'autre multiplicatif. Elle doit alors déclarer quatre méthodes, correspondant aux deux opérations et aux deux éléments neutres, en plus des accesseurs.

public interface Nat {
  Nat somme(Nat x);
  Nat zero();
  Nat produit(Nat x);
  Nat un();
  // accesseurs 
  int getInt();
  int chiffre(int i);
  int taille();
}

Considérons une nouvelle interface Z utilisée pour décrire l'ensemble des entiers relatifs. Elle correspond à deux structures algébriques, un groupe additif et un monoïde multiplicatif.

public interface Z {
  Z somme(Z x);
  Z zero();
  Z oppose();
  Z produit(Z x);
  Z un();
  // accesseurs 
  // ...
}

On s'aperçoit que les deux interfaces partagent les mêmes méthodes, au type près. Est-il possible de factoriser la déclaration de ces méthodes ? La réponse est affirmative en utilisant

  • des interfaces, non plus pour définir des types, mais pour définir des propriétés,
  • l'héritage entre interfaces.

Comme chaque propriété doit dépendre du type en cours de définition (Nat ou Z ici), elle forme précisément un prédicat unaire (ayant un argument) : l'interface est dite générique. L'héritage sert à représenter la relation de vérification. Ainsi, étant donné une interface X et une interface générique P,

X extends P<X> (X hérite de P de X) s'interprète par : X vérifie la propriété P.

/*
 * Définition d'une interface représentant un prédicat unaire.
 * Lire "SemiAnneauUnitaire de E".  
 */
public interface SemiAnneauUnitaire<E> {
  E somme(E x);
  E zero();
  E produit(E x);
  E un();
}
/*
 * Définition de l'interface Nat.
 * Lire 
 * - (en Java) : "Nat héritant de SemiAnneauUnitaire de Nat",
 * - (en Français) : "Nat ayant la propriété d'être un semi-anneau unitaire".   
 */ 
public interface Nat extends SemiAnneauUnitaire<Nat> { 
  // accesseurs 
  // ... 
}
/*
 * Définition de l'interface Z.
 * Lire 
 * - (en Java) : "Z héritant de SemiAnneauUnitaire de Z",
 * - (en Français) : "Z ayant la propriété d'être un semi-anneau unitaire".   
 */ 
public interface Z extends SemiAnneauUnitaire<Z> {
  Z oppose();
  // accesseurs 
  // ...
}

La bibliothèque standard de Java (l'API pour "Application Programming Interface") utilise de nombreuses interfaces pour exprimer des propriétés. En voici deux exemples importants.

  • Iterable<T> : exprime le fait d'être itérable, ce qui implique que la notation for(T x : l){ … } est possible pour une itération sur l de type Iterable<T>.
  • Comparable<T>: exprime le fait que T est totalement ordonné, autrement dit que deux éléments de T sont comparables.

Il arrive que les interfaces utilisées pour exprimer des propriétés ne soient pas génériques : c'est le cas lorsqu'elles déclarent des méthodes qui ne font pas intervenir le type paramètre. Par exemple, l'interface Readable, qui qualifie les sources produisant des caractères lus par les programmes (comme le clavier), ne dépend pas d'un paramètre. De manière générale, on remarque qu'une convention de nommage s'applique : ces interfaces se terminent par "able", exprimant ainsi clairement une propriété.

Vers une hiérarchie d'interfaces

On peut considérer que l'interface SemiAnneauUnitaire réunit les méthodes de deux interfaces "naturelles" qu'on pourrait définir ainsi.

public interface MonoideAdditif<E> {
  E somme(E x);
  E zero();
} 
public interface MonoideMultiplicatif<E> {
  E produit(E x);
  E un();  
}

Est-il possible de définir l'interface SemiAnneauUnitaire sans avoir à reprendre les déclarations des quatre méthodes ? La réponse est affirmative, en utilisant l'héritage multiple entre interfaces.

public interface SemiAnneauUnitaire<E> extends MonoideAdditif<E>, MonoideMultiplicatif<E> {}

Cette définition peut se lire ainsi.

  • En Java : pour tout type E, l'interface SemiAnneauUnitaire de E hérite de MonoideAdditif de E et de MonoideMultiplicatif de E.
  • En Français : un semi-anneau unitaire est un monoïde additif et un monoïde multiplicatif.

L'effet d'une telle déclaration utilisant l'héritage est double.

  1. L'interface fille (ici SemiAnneauUnitaire) hérite des méthodes déclarées dans les interfaces parentes (ici MonoideAdditif et MonoideMultiplicatif)1.
  2. L'interface fille est un sous-type des interfaces parentes : pour tout type E, le type SemiAnneauUnitaire<E> est un sous-type des types MonoideAdditif<E> et MonoideMultiplicatif<E>.

Pour des interfaces exprimant des propriétés, la relation de sous-typage a une interprétation simple : elle correspond à l'inclusion ensembliste ou l'implication logique. Si pour tout type E, P<E> est un sous-type de Q<E>, alors :

  • suivant l'interprétation ensembliste, l'ensemble des E ayant la propriété P est inclus dans l'ensemble des E ayant la propriété Q,
  • suivant l'interprétation logique, la propriété P implique la propriété Q.

Dans notre exemple, on obtient les interprétations suivantes :

  • l'ensemble des semi-anneaux unitaires est inclus dans l'ensemble des monoïdes additifs et dans l'ensemble des monoïdes multiplicatifs,
  • le fait d'être un semi-anneau unitaire implique le fait d'être un monoïde additif et le fait d'être un monoïde multiplicatif.

Grâce à l'héritage multiple entre interfaces, il devient donc possible de représenter directement la hiérarchie des structures algébriques: chaque flèche du schéma, correspondant à une inclusion/implication, s'interprète en Java par la relation d'héritage.

Exercice : dans un paquet hierarchie, définir toutes les interfaces du schéma en utilisant l'héritage. Redéfinir les interfaces Nat et Z par héritage des bonnes structures. Correction : voir le diagramme.

Conclusion : la correspondance interface/héritage et propriété/implication ou inclusion

Les interfaces servent à définir non seulement des types mais aussi des propriétés. Dans ce cas, elles sont souvent paramétrées par des types : ce sont des interfaces génériques. Il est possible de faire hériter une interface de plusieurs interfaces parentes, ce qui permet de factoriser des déclarations de méthodes. La relation de sous-typage induite par l'héritage s'interprète par une implication logique entre propriétés ou une inclusion.

Footnotes:

1

Des conflits peuvent survenir lorsque des méthodes héritées sont semblables (même nom, mêmes types pour les arguments). Cf. la note consacrée à la résolution de ces conflits.

Author: Hervé Grall
Version history: v1: 2016-10-06; v2: 2017-09-26[+conflits]; v3: 2018-10-03[+Typescript].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.