Les entiers naturels - Une interface, plusieurs implémentations
Table of Contents
Session 1 - Travaux dirigés - A étudier pour le 12 octobre 2016, 8h00
Ce TD initie à la conception des interfaces et des classes d'implémentation. Partant d'un type abstrait de données représentant des entiers naturels, nous réaliserons deux implémentations, correspondant respectivement à une restriction du type primitif int et à une définition récursive. Nous continuerons par des manipulations de ce type de données. Finalement, nous définirons une nouvelle implémentation, une variante utilisant la récursion de manière intensive.
Nous chercherons à rendre le code réutilisable, en le rendant le plus possible indépendant de la classe d'implémentation, précisément de ses constructeurs et de la représentation de l'état. C'est une illustration de la méthode recommandée pour la conception d'une classe d'implémentation.
Une interface pour les entiers naturels
Notre intérêt pour les entiers naturels est de nature algébrique puisqu'un des objectifs des TP est de définir une bibliothèque de structures algébriques, la plus générale possible. L'ensemble des entiers naturels \(\{ 0, 1, \ldots \}\) peut être considéré comme un semi-anneau unitaire, soit un monoïde additif et un monoïde multiplicatif, une fois muni de l'addition et de la multiplication.
Nous allons représenter le type de données correspondant aux entiers naturels par une interface qu'on appellera Nat. Comment définir l'interface Nat ?
- Comme le type vérifie des propriétés algébriques, l'interface Nat héritera d'interfaces génériques spécifiant ces propriétés. On utilisera les interfaces du paquet hierarchie fourni dans l'archive.
- Le type doit aussi permettre d'accéder à la valeur d'un entier naturel, suivant les deux points de vue considérés, correspondant chacun à un mode de construction particulier. D'une part, un entier naturel est aussi un entier relatif, représenté par un int en Java. D'autre part, un entier naturel peut se définir inductivement (par récurrence) ainsi : il est soit nul soit le successeur d'un entier naturel. Ainsi, l'interface Nat déclarera les accesseurs correspondant à ces points de vue.
- Un objet de type Nat est immutable, en lecture seulement donc : il ne peut pas être modifié après construction. Cette propriété permet de l'utiliser comme une valeur d'un type numérique primitif (int ou double), comme vous pourrez l'expérimenter. C'est la raison pour laquelle les accesseurs ne permettent pas de modifier l'état d'un entier naturel : ils ne comportent que des "getters", et aucun "setter". L'immutabilité a aussi pour conséquence la nécessité de construire de nouveaux entiers naturels lors de chaque calcul. Plutôt que d'utiliser un appel à un constructeur, on préfère appeler des méthodes particulières, les fabriques : elles permettent de s'affranchir de la dépendance vis-à-vis des classes d'implémentation. L'ensemble de ces fabriques sera déclaré dans une interface dont héritera l'interface Nat. Cette interface exprimant une propriété, la capacité à construire des entiers naturels, elle sera générique.
Accesseurs
Les accesseurs permettent d'observer un entier naturel suivant les deux points de vue, celui de la restriction d'une part, de la définition récursive d'autre part.
int val()
Méthode renvoyant l'entier relatif égal à l'entier naturel.
boolean estNul()
Méthode permettant de tester si l'entier naturel est nul.
Nat predecesseur()
Méthode renvoyant le prédécesseur de l'entier naturel si cet entier naturel est non nul, lançant une exception java.lang.UnsupportedOperationException sinon.
Services universels
Ces deux méthodes sont déclarées dans la classe mère Object.
String toString()
Méthode permettant d'obtenir une représentation de l'entier naturel, en base dix.
boolean equals(Object o)
Méthode testant l'égalité entre l'objet cible et l'objet o passé en argument ; renvoie true si o pointe vers un entier naturel n et si l'entier naturel cible et n sont égaux (au sens mathématique), renvoie false sinon.
Interfaces parentes
Toutes ces interfaces sont génériques car elles expriment des propriétés.
FabriqueNat<T>
Cette interface déclare les fabriques qu'on souhaite utiliser.
T creerNatAvecValeur(int val)
Méthode renvoyant un entier naturel de valeur l'argument val si val est positif ou nul, lançant une exception java.lang.IllegalArgumentException sinon.
T creerZero()
Méthode renvoyant un entier naturel de valeur nulle.
T creerSuccesseur(T predecesseur)
Méthode renvoyant le successeur de l'argument predecesseur.
SemiAnneauUnitaire<T>
Cette interface déclare (par héritage) les services correspondant aux constantes et aux opérations unaires ou binaires qu'on souhaite utiliser avec les entiers naturels. Notez que chaque opération est représentée par une méthode qui possède un paramètre implicite, l'entier naturel cible référencé par this.
T somme(T n)
Méthode renvoyant un nouvel entier naturel de valeur la somme de l'entier naturel cible et de l'argument n.
T zero()
Méthode renvoyant l'élément neutre de l'addition, soit zéro.
T produit(T n)
Méthode renvoyant un nouvel entier naturel de valeur le produit de l'entier naturel cible et de l'argument n.
T un()
Méthode renvoyant l'élément neutre de la multiplication, soit un.
Une première implémentation
La classe NatParInt implémente l'interface Nat en suivant le premier point de vue. Cette classe est une enveloppe des entiers relatifs de type int, vérifiant une propriété restreignant leur domaine : les entiers naturels sont des entiers relatifs positifs ou nuls. Nous imposons que tout objet de la classe NatParInt est immutable, en lecture seulement : il ne peut pas être modifié après construction. Précisément, les constructeurs initialisent les attributs que les méthodes, ensuite, ne modifient plus. Voici une spécification de cette classe.
Etat
int val
Attribut privé ayant pour valeur un entier relatif positif ou nul.
Constructeur
NatParInt(int val)
Constructeur public initialisant l'attribut à l'argument val si val est positif ou nul, lançant une exception java.lang.IllegalArgumentException sinon.
Une seconde implémentation
Pour la seconde implémentation, on adopte un point de vue récursif, correspondant à la définition récursive déjà donnée : un entier naturel est soit nul soit le successeur d'un entier naturel. On utilise le patron de conception Composite, qui traduit directement la définition inductive : voir la note dédiée aux définitions inductives. Ainsi, on définit deux classes d'implémentation de l'interface Nat,
- Zero, une classe représentant l'entier naturel zéro, et
- Succ, une classe représentant les entiers naturels successeurs, autrement dit ayant un prédécesseur.
Etats
Classe Zero
- Pas d'état.
Classe Succ
- Un attribut privé de type Nat représentant le prédécesseur de cet entier naturel.
Constructeurs
Zero()
Constructeur public ne faisant rien.
Succ(Nat predecesseur)
Constructeur public initialisant l'attribut avec l'argument.
Travail à faire
Dans le projet dédié au développement, recopier le paquet hierarchie du projet dédié aux corrections : ce paquet contient les interfaces décrivant les structures algébriques. Créer un nouveau paquet session1.tp dans le projet de développement. Les développements suivants seront réalisés dans ce paquet. Voici en résumé le diagramme des types à obtenir.
Définition de l'interface Nat
Définir l'interface Nat.
Première implémentation de l'interface Nat
Pour la première implémentation, on procède par restriction. Implémenter l'interface Nat par la classe NatParInt, en procédant suivant la méthode rappelée ci-dessous.
- Définir l'état.
- Implémenter les constructeurs en accédant directement aux attributs de l'objet cible pointé par this.
- Implémenter les accesseurs en accédant aux attributs de l'objet cible pointé par this directement ou indirectement via d'autres accesseurs.
- Implémenter les fabriques en accédant aux constructeurs directement ou indirectement via d'autres fabriques.
- Implémenter les services en utilisant les seuls accesseurs et fabriques. Précisément, les implémenter en utilisant l'accesseur val() et la fabrique creerNatAvecValeur(int), autrement dit en ramenant les calculs sur les entiers naturels à des calculs sur des int.
Seconde implémentation de l'interface Nat
Pour la seconde implémentation, on utilise le patron Composite. On cherche aussi à favoriser la réutilisation de code. Implémenter l'interface Nat par les deux classes adjointes Zero et Succ. Procéder ainsi pour chaque classe.
- Définir l'état.
- Implémenter les constructeurs en accédant directement aux attributs de l'objet cible pointé par this.
- Implémenter les accesseurs en accédant aux attributs de l'objet cible pointé par this directement ou indirectement via d'autres accesseurs.
- Implémenter les fabriques en accédant aux constructeurs directement ou indirectement via d'autres fabriques.
- Réutiliser les services définis dans la classe NatParInt, en les recopiant textuellement.
Test
Les tests sont à placer dans la fonction principale main d'une classe appelée Test. Pour chaque test, il est demandé d'afficher tout d'abord le résultat que vous prévoyez, appelé oracle, puis effectivement le résultat calculé, sur le modèle suivant.
... // Calcul du résultat : rep // Résultat prévu : oracle System.out.println("oracle ? " + rep);
Remarque - Si rep est un objet, un appel implicite à la méthode toString() a lieu dans l'expression "oracle ? " + rep, équivalente à "oracle ? " + rep.toString(). La méthode toString() étant très pratique, tout objet en possède une. Par défaut, la méthode toString() renvoie une représentation de l'adresse de l'objet en mémoire.
- Déclarer une fonction void test(FabriqueNat<Nat> fab) prenant en argument une fabrique d'entiers naturels de type Nat.
- Implémenter dans la fonction test le scénario suivant.
- Créer l'entier zéro à partir de la fabrique et l'affecter à une variable zero.
- Afficher sa valeur.
- Tester l'égalité entre zero et zero.zero().
- Créer l'entier un à partir de la fabrique et l'affecter à une variable un.
- Afficher sa valeur.
- Tester l'égalité entre un et un.un().
- Créer l'entier cinq à partir de la fabrique et l'affecter à une variable cinq.
- Afficher sa valeur.
- Créer l'entier six à partir de la fabrique et l'affecter à une variable six.
- Calculer la somme de cinq et six et afficher le résultat.
- Calculer le produit de cinq et six et afficher le résultat.
- Compléter la fonction principale en appelant la fonction test trois fois, avec des fabriques de type dynamique NatParInt, Zero et Succ respectivement.
Troisième implémentation de l'interface Nat : une variante fondée sur la récursion
Les classes Zero et Succ réutilisent les services définis dans la classe NatParInt, implémentés en ramenant les différents calculs à des calculs sur des int. Il est cependant possible de définir les services suivant l'autre point de vue, celui récursif. C'est la méthode de choix lorsqu'on utilise le patron Composite.
Créer deux sous-classes ZeroRec et SuccRec des classes Zero et Succ respectivement.
- Redéfinir les méthodes somme, produit et equals d'une manière récursive. On définira le cas de base (rang 0) dans la classe Zero et le cas récursif (rang n + 1 en fonction du rang n) dans la classe Succ.
- Definir les constructeurs.
- Redéfinir les fabriques de manière à n'appeler que les contructeurs des nouvelles classes ZeroRec et SuccRec.
- Tester comme précédemment ces deux nouvelles classes.