UP | HOME

Les entiers naturels - Une interface, plusieurs implémentations

Table of Contents

On s'intéresse aux entiers naturels : 0, 1, 2, etc.. L'objectif est de proposer plusieurs implémentations de ce type de données et de permettre leur utilisation simultanée. Autrement dit, ces implémentations doivent être interopérables.

Les exemples ci-dessous utilisent Java. Ils peuvent cependant facilement être programmés en Typescript. Lorsque des différences notables apparaissent, elles sont mentionnées.

Comment définir les entiers naturels

Deux points de vue sont possibles :

  • un point de vue interne, lié à la construction, et
  • un point de vue externe, lié à l'utilisation.

Point de vue externe : comment les utiliser ?

Plusieurs utilisations sont possibles :

  • compter,
  • calculer (additionner, multiplier, etc.),

Le point de vue externe correspond à celui d'un utilisateur souhaitant utiliser des entiers naturels. Celui-ci s'intéresse à l'interface que lui présentent les entiers. Cette notion d'interface se retrouve dans de nombreux langages de programmation, notamment en Java et Typescript. Une interface définit un contrat établi entre un utilisateur et un type de données.

Point de vue interne : comment les construire ?

Plusieurs constructions sont possibles.

  • Par récurrence : un entier naturel est ou bien nul, ou bien le successeur d'un entier naturel. \[\small n \ ::=\ 0 \mid \mathtt{S} n \]
  • Par restriction de l'ensemble des entiers relatifs (int) : un entier naturel est un entier relatif positif. \[\small n \in \mathbb{Z} \mid n \geq 0 \]
  • Par une représentation particulière, par exemple décimale (en base 10) : un entier est une suite finie de chiffres compris entre 0 et 9.

    \[\small \begin{array}{rcl} c & ::= & 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9\\ d & ::= & 0 \mid c \\ n & ::= & 0 \mid c\,d^* \end{array} \]
  • Par un ensemble : un entier est l'ensemble vide, ou l'ensemble de ses prédécesseurs.

    \[\small n \ ::=\ \emptyset \mid n \cup \{ n \} \]

  • Etc.

Une première implémentation simple : restriction de int aux valeurs positives

  • Créer une nouvelle classe NatParInt dans un paquet session1.demo1.v1.
  • Commencer par définir la méthode NatParInt somme(NatParInt x) en utilisant un accesseur public, la méthode int getInt() donnant la valeur du int associé.
  • En la définissant, utiliser les corrections proposées par Eclipse pour compléter la définition de la classe.
  • Veiller à garantir qu'un entier naturel est toujours construit avec un int positif.
  • Tester votre classe dans la fonction principale main d'une classe Test.
  • Peut-on additionner deux milliards à lui-même ? Pourquoi n'est-ce pas possible ?

On cherche à résoudre ce problème de dépassement en construisant une nouvelle classe.

Remarque : en Typescript (comme en Javascript), il existe un seul type numérique, number, correspondant à des nombres à virgule flottante.

Solution plus élaborée : restriction de String aux représentations décimales

  • Créer une nouvelle classe NatDecimal dans le paquet session1.demo1.v1.
  • Définir la méthode NatDecimal somme(NatDecimal x) en utilisant deux accesseurs publics,
    • la méthode int chiffre(int i) donnant la valeur du chiffre en position i dans la représentation décimale (0 pour les unités, 1 pour les dizaines, etc.) et
    • la méthode int taille() donnant le nombre total de chiffres dans la représentation (aucun 0 superflu n'étant supposé en tête).
  • Compléter la définition : définir l'état formé d'une chaîne de caractères (de type String) formée des chiffres décimaux représentant l'entier naturel, ses accesseurs et les constructeurs utiles.
  • Veiller à garantir que la chaîne de caractères utilisée pour la représentation ne contient que des chiffres décimaux.
  • Tester votre classe.
  • Peut-on additionner deux milliards à lui-même ?

Les différentes couches d'une implémentation

A partir de ces deux constructions de classes, on peut mettre en évidence leur structure commune :

  • un état formé d'attributs,
  • des constructeurs initialisant les attributs et garantissant des propriétés sur l'état (appelées des invariants),
  • des accesseurs permettant d'observer l'état,
  • des services, méthodes utilisant les constructeurs et les accesseurs.
attributs
accesseurs constructeurs
services

En Typescript, plutôt que d'utiliser un état formé de plusieurs attributs, il est possible d'utiliser un état formé d'un unique attribut, correspondant à une structure en JSON. C'est très utile lorsque des données sont échangées, par exemple dans des applications réparties à base de services Web.

Problème de l'interopérabilité

Peut-on additionner un NatParInt et un NatDecimal ? La réponse est négative : il manque un type commun qui serait la réunion de ces deux types.

En Java, la solution est de définir les deux classes comme des classes d'implémentation d'une interface commune.

  • Créer un nouveau paquet session1.demo1.v2 dans lequel on travaille par la suite.
  • Créer une nouvelle interface Nat contenant une méthode Nat somme(Nat x) ainsi que les accesseurs publics de NatParInt et de NatDecimal.
  • Préciser que les classes NatParInt et NatDecimal implémentent Nat.
  • Compléter ces classes.
  • Récrire les tests de manière à utiliser le type Nat. Réaliser l'addition de deux entiers naturels de classe différente.

En Typescript, en plus de la solution précédente, on peut définir un type égal à la réunion (ou l'union) de NatParInt et de NatDecimal. Un attribut (éventuellement fonctionnel) appartient à la réunion s'il est commun à chaque type réuni : bref, une union entre types se traduit par une intersection pour les ensembles associés d'attributs. De manière duale, l'intersection entre types se traduit par une réunion pour les ensembles associés d'attributs. Les méthodes étant identifiées par leur nom et leur arité (nombre d'arguments), si elles diffèrent par leur type de retour, ces types de retour sont réunis, de même si elles diffèrent par le type de leurs paramètres, ces types sont intersectés.

Exemple - Cf. session1/demo1/v2/testNaturels.ts.

  • Notamment : le typage de somme : (NatParInt & NatDecimal) => (NatParInt | NatDecimal), par fusion de somme : NatParInt => NatParInt et de somme : NatParDecimal => NatParDecimal.
type Nat = NatParInt | NatDecimal;
// Calculs sur les types réalisés par le compilateur de Typescript
// Pour examiner le type attribué à n, taper 'n' pour observer son type.
// Voir les commentaires.
let n: Nat = unD; // n : NatDecimal
n = un; // n : NatParInt
n = unD; // n : NatDecimal
let z = 3;
if (z < 4) {
    n = un; // n : NatParInt
} else {
    n = unD; // n : NatDecimal
}
// n : Nat
// n = n.somme(n) // Erreur car somme a le type (NatParInt & NatDecimal) => Nat.
console.log(n.representationJSON());
// n.representationJSON() : FormatNatParInt | FormatNatDecimal
if (n instanceof NatParInt) {
    console.log(n.representationJSON()); // n : NatParInt
} else {
    console.log(n.representationJSON()); // n : NatDecimal
}

Factorisation des tests

Avec plusieurs classes à tester, on constate de nombreuses répétitions : les tests ne diffèrent que par le nom de la classe apparaissant lors des invocations de constructeurs.

Il est possible d'abstraire la construction des objets, en utilisant des fabriques. Une fabrique est un objet particulier dont le rôle est de construire des objets : précisément, elle contient des méthodes dont l'implémentation se réduit à l'invocation d'un constructeur. Une bonne pratique de programmation est de n'utiliser les constructeurs que dans les fabriques et de construire les objets hors fabriques uniquement via les fabriques. Ainsi il suffit de changer la valeur d'une fabrique pour changer de constructeurs.

  • Créer une nouvelle interface FabriqueNat contenant les méthodes suivantes :
    • Nat creerNatAvecValeur(int x),
    • Nat creerNatAvecRepresentation(String repDecimale),
  • Créer deux classes de fabriques implémentant cette interface, FabriqueNatParInt et FabriqueNatDecimal.
  • Modifier la fonction principale de manière à factoriser les tests dans trois fonctions prenant comme arguments des fabriques :
    • void testerCourt(FabriqueNat fab) : test sur des petits entiers,
    • void testerGrand(FabriqueNat fab) : test sur des grands entiers,
    • void testerInteroperabilite(FabriqueNat fab1, FabriqueNat fab2) : test de l'interopérabilité.
  • Tester.

Utilisation de fabriques

Il est aussi possible d'utiliser une fabrique pour rendre le code d'un service indépendant de la classe d'implémentation. En effet, si le code d'un service utilise des constructeurs en plus des accesseurs, il devient alors dépendant de la classe d'implémentation. En agrégeant une fabrique ou plus simplement les méthodes déclarées dans celle-ci, on peut remplacer toute invocation d'un constructeur par l'appel d'une méthode de fabrication. Seules les méthodes de fabrication invoquent directememnt les constructeurs : elles seules dépendent de la classe d'implémentation. Voir la synthèse présentant la méthode générale de conception d'un type de données. Dans notre exemple, on peut récrire la somme ainsi dans NatParInt, en utilisant la fabrique creer.

NatParInt

public Nat somme(Nat x){
  return this.creer(this.getInt() + x.getInt());
}

Ce code, devenu indépendant de la classe d'implémentation, peut être factorisé dans l'interface Nat.

Nat

default Nat somme(Nat x){
  return this.creer(this.getInt() + x.getInt());
}

Cf. le premier TD.

Bonus : une nouvelle implémentation par récurrence (ou induction).

Un entier naturel peut être défini par récurrence (ou induction) de la manière suivante : un entier naturel est soit nul, soit le successeur d'un entier naturel. On peut implémenter facilement de telles définitions inductives en Java : l'ensemble défini se traduit par une interface alors que chaque cas de définition se traduit par une classe implémentant cette interface.

Cf. le premier TD.

Conclusion : interfaces comme types essentiels, classes comme modèles concrets de données

A la lumière des exemples précédents, on peut tirer quelques conclusions.

  • Une interface sert à définir un type utilisable ensuite dans un programme. Elle définit le contrat réalisé par les données de ce type, un contrat étant l'ensemble des méthodes auxquelles répondent ces données.
Interface
type de retour
nom type des arguments
méthode 1
... ... ...
méthode 2
... ... ...
etc. ... ... ...
  • Une classe sert à définir une implémentation d'une interface1 : elle réalise le contrat déclaré par l'interface, en définissant un modèle concret de données, à partir d'attributs, de constructeurs et de méthodes, dont celles déclarées dans l'interface. Elle est utilisée pour construire des objets, en qualifiant l'opérateur new, ce qui a pour effet d'appeler un constructeur de la classe. Pour réduire la dépendance relativement aux classes d'implémentation, une bonne pratique est de restreindre l'usage des constructeurs à des méthodes ou des classes particulières, appelées fabriques.
attributs
accesseurs constructeurs
fabriques
services

Footnotes:

1

A vrai dire, une classe peut implémenter une ou plusieurs interfaces simultanément.

Author: Hervé Grall
Version history: v1: 2015-09-30; v2: 2016-10-06[update]; v3: 2018-10-04[+Typescript, +default]; v4: 2019-09-30[update].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.