UP | HOME

Coupures - Une généralisation des itérateurs

Table of Contents

1 Consignes - Remarques préalables

  • Langage : Java 9 au moins

Organisation du travail et rendu

  • Développer le code dans un nouveau projet,
  • Des importations seront faites progressivement à partir du dépôt Git.

Remarques préliminaires

  • Une fonction sans paramètre et renvoyant un A a pour type
    • Supplier<A> (du paquet javal.util.function).
  • Une fonction de paramètre un A et renvoyant un B a pour type
    • Function<A, B> (du paquet javal.util.function).
  • Une fonction de paramètres un A et un B, et renvoyant un C, a pour type
    • BiFunction<A, B, C> (du paquet javal.util.function).
  • Une fonction de paramètres un A, un B et un C, et renvoyant un D, a pour type
    • Fonction3<A, B, C, D> (du paquet eval.sujetGSI).
  • Une fonction peut être définie par une lambda-expression. Il est généralement inutile de typer les paramètres. Le corps est soit une expression soit un bloc se terminant par un return (renvoi d'un résultat) ou un throw (déclenchement d'une exception). Voici quelques exemples.
    () -> { return 0; } // Supplier<Integer>
    () -> 0 // Supplier<Integer>
    (c) -> { throw new UnsupportedOperationException();} // Function<A, B> (A et B inférés)
    (a, b, c) -> ... // Function3<A, B, C, D> (A, B, C et D inférés)
    
  • Les interfaces peuvent définir des méthodes : celles-ci doivent être précédées du qualificatif default.

2 Itérateur comme coupure

Un itérateur permet de parcourir une collection de valeurs comme une liste. C'est un patron de conception utile, et de fait utilisé en Java sous la forme d'une interface Iterable<E>, paramétrée par le type des valeurs contenues dans la collection. Lorsqu'un type T est un sous type de Iterable<E>, il est possible de réaliser une itération simplifiée ainsi.

T l;
...
for(E e : l){
  ... // Itération sur tous les éléments de l
}

L'interface Iterable<E> déclare une méthode Iterator<E> iterator(), qui renvoie un itérateur mutable. Un itérateur définit deux méthodes :

  • boolean hasNext() : teste s'il existe encore une valeur à parcourir,
  • E next() : renvoie l'élément suivant à parcourir et le retire de l'ensemble des éléments à parcourir. La boucle for précédente est en fait équivalente à la boucle while suivante.
Iterator<E> iter = l.iterator()
while(iter.hasNext()){
  E e = iter.next();
  ...
}

Un itérateur peut être vu comme une coupure de la liste à parcourir. Il suffit d'imaginer les éléments de la liste reliés par des arcs. Un itérateur est alors un curseur placé sur un arc, et réalisant une bipartition en coupant la liste en deux parties : celle du curseur au premier élément et celle du curseur au dernier élément. L'itérateur se déplace alors d'arc en arc, en visitant un élément à chaque déplacement : voir le schéma ci-dessous où le curseur est marqué par le signe .

-∧-> e0 ---> e1 ---> e2 ... ---> en --->
---> e0 -∧-> e1 ---> e2 ... ---> en --->
---> e0 ---> e1 -∧-> e2 ... ---> en --->
...
---> e0 ---> e1 ---> e2 ... -∧-> en --->
---> e0 ---> e1 ---> e2 ... ---> en -∧->

Dans le cas d'une liste, il est intéressant de noter que la coupure produit deux listes. Par exemple, dans le schéma ci dessus, on obtient successivement les couples suivants :

- (vide, e0 :: e1 :: e2 :: ... :: en :: vide)
- (e0 :: vide, e1 :: e2 :: ... :: en :: vide)
- (e1 :: e0 :: vide, e2 :: ... :: en :: vide)
- ...
- (... :: e2 :: e1 :: e0 :: vide, en :: vide)
- (en :: ... :: e2 :: e1 :: e0 :: vide, vide)

(Notation : vide pour la liste vide, t :: r pour la liste de tête t et de reste la liste r.)

Cette notion de coupure peut se généraliser à d'autres structures de données que les listes, par exemple à des arbres. Elle permet de définir des itérateurs parcourant ces structures, en suivant des arcs reliant les éléments de la structure et en coupant les arcs pour obtenir une bipartition.

Le but du TP est d'implémenter de telles coupures pour des listes puis des arbres binaires. Il s'agit de structures immutables, permettant également des transformations locales en temps constant. Le sujet s'inspire directement des zippers (des fermetures Eclair, par une ressemblance graphique).

3 Coupure de listes

Une interface Liste<E> pour les listes immutables est fournie. Elle correspond à une définition inductive d'une liste avec deux implémentations anonymes, correspondant aux listes vides et aux listes construites respectivement.

  • Bien l'étudier puisqu'elle est utilisée par la suite.
  • Compléter la classe CoupureListe<E> en suivant les commentaires. Elle possède deux attributs, deux listes, représentant la bipartition induite par la coupure.
  • Dans la classe TestListes, compléter la fonction tester(CoupureListe<E>) de manière à réaliser une itération en utilisant la coupure et une boucle while. Le corps de la boucle affiche l'élément courant de la liste et un espace, sans passage à la ligne.

4 Un itérateur par adaptation d'une coupure

Plutôt que réaliser une telle itération, il serait préférable d'utiliser la forme élégante utilisant une boucle for.

  • Définir une classe IterateurListe<E> implémentant Iterator<E> et réalisant l'adaptation à cette interface. Elle possède un attribut de type CoupureListe<E> et un constructeur acceptant une liste de type Liste<E>.
  • Modifier l'interface Liste<E> de manière à étendre Iterable<E>.
  • Implémenter la méthode iterator() dans l'interface Liste<E> en utilisant IterateurListe<E>.
  • Dans la classe TestListes, compléter la fonction tester(Liste<E>) de manière à réaliser une itération en utilisant une boucle for. Le corps de la boucle affiche l'élément courant de la liste et un espace, sans passage à la ligne.

5 Coupure d'expressions

Une interface Expression<C, Op> pour des expressions immutables est fournie. Définie par induction, une expression est :

  • soit une constante de type C,
  • soit une opération de type Op avec deux expressions pour arguments.

L'interface possède une seul méthode de filtrage.

public <R> 
  R filtrage(Function<C, R> casConstante, 
             Fonction3<Op, Expression<C, Op>, Expression<C, Op>, R> casOperation);

Cette méthode permet pour tout type R de produire un R,à partir de deux fonctions traitant les deux cas de la définition inductive :

  • une fonction associant à une constante C un R,
  • une fonction associant à un opérateur Op et deux expressions un R.

Par exemple, on procède ainsi pour calculer la hauteur d'une expression.

private static <C, Op> int hauteur(Expression<C, Op> exp) {
  return exp.filtrage(
    (c) -> 1, 
    (op, g, d) -> 1 + Integer.max(hauteur(g), hauteur(d))
  );
}

La coupure d'une expression produit un chemin et une sous-expression. Défini inductivement, un chemin est :

  • soit un chemin vide,
  • soit un chemin à gauche, formé d'un chemin parent, d'un opérateur et d'une expression à droite,
  • soit un chemin à droite, formé d'un chemin parent, d'un opérateur et d'une expression à gauche.

Chemins

Représentation arborescente

  0         parent            parent
	      |                 |
	      op                op 
	      /\                /\
	   > /  \              /  \ <
	    /    \            /    \
		 exp         exp

Représentation linéaire

  0   parent.(op ? exp)   parent.(op exp ?)

6 Implémentation des coupures d'expressions

  • Étudier l'interface fournie Expression<C, Op> et les deux classes anonymes l'implémentant.
  • Définir l'interface Chemin<C, Op> en suivant la spécification suivante.
    • Déclarer une méthode de filtrage, avec trois paramètres, correspondant aux trois cas de la définition inductive. Indication : utiliser un Supplier pour le cas vide, une Fonction3 pour les deux autres cas.
    • Définir trois fabriques (méthodes static) de chemins, vide, gauche et droite, en implémentant trois classes anonymes correspondant aux trois cas de la définition inductive. Redéfinir à chaque fois la méthode toString() de manière à produire la représentation linéaire décrite ci-dessus.
  • Définir une classe CoupureExpression<C, Op> en suivant la spécification suivante.
    • Déclarer deux attributs, un chemin et une expression, formant la coupure notée (ch, exp) par la suite.
    • Définir un constructeur permettant d'initialiser ces attributs par les paramètres du constructeur.
    • Définir la méthode haut() renvoyant à partir de la coupure (ch, exp) la coupure définie par filtrage sur le chemin ch ainsi :
      • ch égal à 0 : exception de type UnsupportedOperationException,
      • ch égal à parent.(op ? expD) : (parent, (op exp expD)),
      • ch égal à parent.(op expG ?) : (parent, (op expG exp)).
    • Définir la méthode boolean aUneConstante() testant si la coupure a une constante comme expression, par filtrage sur l'expression exp.
    • Définir la méthode gauche() renvoyant à partir de la coupure (ch, exp) la coupure définie par filtrage sur l'expression exp ainsi :
      • exp égal à la constante c : exception de type UnsupportedOperationException,
      • exp égal à (op expG expD) : (ch.(op ? expD), expG).
    • Définir la méthode droite() renvoyant à partir de la coupure (ch, exp) la coupure définie par filtrage sur l'expression exp ainsi :
      • exp égal à la constante c : exception de type UnsupportedOperationException,
      • exp égal à (op expG expD) : (ch.(op expG ?), expD).
    • Redéfinir la méthode toString() de manière à représenter la coupure (chemin, expression) par la chaîne @chemin : expression.
  • Compléter la fonction principale de la classe TestExpressions ainsi puis tester.
    CoupureExpression<Integer, OpArith> coupure = new CoupureExpression<>(Chemin.vide(), exp);
    System.out.println("[@0 : (* (+ 5 3) (+ 12 15))] : [" + coupure + "]"); 
    coupure = coupure.droite();
    System.out.println("[@0.(* (+ 5 3) ?) : (+ 12 15)] : [" + coupure + "]");
    coupure = coupure.gauche();
    System.out.println("[@0.(* (+ 5 3) ?).(+ ? 15) : 12] : [" + coupure + "]");
    coupure = coupure.haut();
    System.out.println("[@0.(* (+ 5 3) ?) : (+ 12 15)] : [" + coupure + "]");
    

    Remarque : la classe utilise une énumération OpArith permettant de représenter les opérateurs, Plus et Mult.

  • Définir une fonction réalisant récursivement un parcours en profondeur d'une expression et renvoyant une chaîne de caractères concaténant les représentations des coupures terminales, celles ayant pour expression une constante. Par exemple, pour l'expression (∗ (+ 5 3) (+ 12 15)), la fonction renverra la concaténation des quatre coupures suivantes :
    • @0.(∗ ? (+ 12 15)).(+ ? 3) : 5,
    • @0.(∗ ? (+ 12 15)).(+ 5 ?) : 3,
    • @0.(∗ (+ 5 3) ?).(+ ? 15) : 12,
    • @0.(∗ (+ 5 3) ?).(+ 12 ?) : 15.

    Cette fonction prendra pour paramètre une coupure d'expression. La tester.

7 Généralisation - Bonus

Proposer une généralisation en définissant

  • un type et une implémentation de structures de données,
  • un type et une implémentation des coupures associées.

La généralisation pourra s'obtenir par la méthode utilisée, qu'on décrira dans un fichier readme, ou par le caractère générique des structures de données.

Exemples

  • méthode générale appliquée à un type d'objets quelconques, muni de méthodes de décomposition et de discrimination, que ce soit un type inductif (comme les arbres) ou non (comme un graphe)
  • une structure générique de données, comme des arbres, soit vides, soit associant à toute valeur d'un type paramètre un sous-arbre
    a ::= vide                  # arbre vide
        | f (a_x)_{x ∈ A}       # arbre d'étiquette f et de sous-arbre a_x pour tout x dans A
    

8 Modularité

Le but de cette partie est de réaliser une architecture modulaire en couches, à partir de l'exemple des listes et de ses coupures.

  • Réaliser un premier module, dans un projet configuré pour Maven, correspondant à la couche basse.
    • Définir deux paquets, un public pour les interfaces et les fabriques, un privé pour les implémentations.
    • Reprendre l'interface des listes, qui était fournie, dans le paquet public.
    • Réaliser deux implémentations de l'interface dans le paquet privé.
      • Reprendre l'implémentation des listes suivant le patron Composite (ou Inductif).
      • Définir une seconde implémentation par adaptation des listes de la bibliothèque "Eclipse Collections" (qu'on importera préalablement en utilisant Maven).
    • Définir une fabrique de listes dans le paquet public.
    • Configurer le module pour exporter le paquet public.
  • Réaliser un second module, dans un projet configuré pour Maven, correspondant à la couche haute, qui utilise la couche basse.
    • Définir deux paquets, un public pour les interfaces et les fabriques, un privé pour les implémentations.
    • Importer le module des listes, d'une manière transitive.
    • Définir une interface pour les coupures de listes dans le paquet public.
    • Réaliser deux implémentations des coupures de listes dans le paquet privé. La première utilisera deux attributs de type Liste (voir ci-dessus), la seconde utilisera le patron de conception Etat. Le patron de conception Etat s'appuie sur une abstraction de l'état (formé de deux listes) : l'état sera décrit par un seul attribut, formé d'un couple de listes.
    • Définir une fabrique de coupures de listes dans le paquet public.
    • Configurer le module pour exporter le paquet public.
  • Tester dans un troisième projet.

9 Bibliographie

Author: grall
Version history: v1: 2019-30-10; v2: 2020-03-03; v3: 2020-03-19 [+generalization, +modules].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.