UP | HOME

Des types de données immutables et génériques avec variance

Table of Contents

Session 3 - Travaux pratiques - A rendre pour le 25 novembre 2016, 12h00 28 novembre, 20h00

Ce TP initie à la généricité et à la notion de variance. Il s'agit de développer des types de données non seulement génériques mais aussi variants, covariants ou contravariants : des listes et des fonctions partielles (qui ne sont pas partout définies).

En introduction, on commence par un exercice sur les règles de variance dans le système de types de Java.

Variance

On s'intéresse au système de types de Java, et particulièrement à la relation entre la généricité et le sous-typage, précisément à la variance. Pour cet exercice, compléter l'unité de compilation session4.tp.Variance.

Le but de l'exercice est de montrer que l'absence de variance pour les types génériques en Java est justifiée. Si la variance était présente, le système de types ne serait pas sûr.

Typage et variance

On considère l'interface générique List du paquet java.util. Dans le système de types de Java, les deux règles suivantes ne sont pas valides.

Règle de covariance (non valide)

Si B est un sous-type de A, alors List<B> est un sous-type de List<A>.

Règle de contravariance (non valide)

Si B est un sous-type de A, alors List<A> est un sous-type de List<B>.

Compléter les fonctions erreurCovariance et erreurContravariance de manière à produire une erreur à l'exécution. Dans la fonction erreurCovariance, l'erreur doit provenir de l'application de la règle de covariance, simulée par l'application de la fonction covariance ; dans la fonction erreurContravariance, l'erreur doit provenir de l'application de la règle de contravariance, simulée par l'application de la fonction contravariance.

Noter que les deux fonctions covariance et contravariance sont à la fois bien typées et exemptes d'erreurs à l'exécution. Elles exploitent une faille dans le système de types pour réaliser la conversion interdite : voir la fonction session4.genericite.limitations.SureteTypage.convertir. Pour les types génériques, il est toujours possible de réaliser une telle conversion : il suffit d'utiliser le joker ainsi. 

List<A> covariance(List<B> l) {
  return (List<A>) (List<?>) l; 
}

Un simple avertissement est signalé. Aucune erreur à l'exécution ne se produira, du fait de l'effacement des paramètres des types génériques lors de la compilation.

Indication. Les erreurs doivent se produire lors de l'application de la méthode f à un objet de type réel A et de type déclaré B. Pour les produire, utiliser les instructions suivantes, dans le bon ordre :

  • initialisation d'une liste chaînée,
  • ajout d'un élément à la liste,
  • récupération de l'élément placé dans la liste,
  • conversion par variance, obtenue en appelant les fonctions covariance ou contravariance,
  • appel de la méthode f.

Versions génériques

Définir les versions génériques covarianceG et contravarianceG de covariance et contravariance. Elles seront paramétrées par un type, et un seul, et utiliseront le joker (noté ?) exactement une fois. Compléter les fonctions correspondantes erreurCovarianceG et erreurContravarianceG, variantes de erreurCovariance et erreurContravariance utilisant respectivement covarianceG et contravarianceG.

Listes

On va construire un type générique Liste<E> pour représenter des listes génériques immutables. Ces listes sont covariantes : en particulier, l'exemple précédent ne peut pas s'appliquer car il est impossible de modifier une liste.

Pour obtenir la covariance, on utilisera systématiquement le type Liste<? extends E> au lieu de Liste<E>. Plus précisément, tout se passe comme si on marquait le type E : toute occurrence de E comme paramètre de type doit alors être remplacée par ? extends E.

Cette substitution est motivée par la règle de typage suivante, qui est valide en Java.

Si B est un sous-type de A, alors Liste<? extends B> est un sous-type de Liste<? extends A>.

L'interprétation ensembliste par une union paramétrée par un type ici majoré, justifie cette règle. Voir le cours pour des détails. 

(Union T <= B.List<T>) <= (Union T <= A.List<T>) 
  car (B <= A).

Pour cette partie, développer dans le paquet session4.tp.listes.

Interface

Définir l'interface ainsi. 

public interface Liste<E> {
  int taille();
  default boolean estVide(){
    return false;
  }
  default E tete(){
    throw new UnsupportedOperationException();
  }
  default Liste<? extends E> reste(){
    throw new UnsupportedOperationException();
  }
}

Fabrique

Définir dans la classe Fabrique les quatre fonctions (méthodes statiques) de fabrication des listes. Ne pas utiliser de récursivité : l'objectif est d'obtenir des listes passant à l'échelle. 

public class Fabrique {
  public static <E> Liste<? extends E> vide() {
    return new Liste<E>() {
      ...
    };
  }
  public static <E> Liste<? extends E> vide(Class<E> type){
    ... 
  }
  public static <E> Liste<? extends E> cons(E t, Liste<? extends E> r) {
    ...
  }

  public static <E> Liste<? extends E> liste(@SuppressWarnings("unchecked") E... elts) {
    ...
  }
}

On remarquera qu'on évite ainsi la définition de classes d'implémentation : il suffit d'utiliser l'expression new Liste<E>(){…} et de compléter les implémentations des méthodes entre les accolades. Cette expression produit à la compilation des classes dites anonymes.

Module

Définir dans la classe Module les fonctions utiles dédiées aux listes. Ne pas utiliser la récursivité. 

public class Module {

  public static <E> int taille(Liste<? extends E> l) {
    ...
  }
  public static <E> boolean estVide(Liste<? extends E> l) {
    ...
  }
  public static <E> E tete(Liste<? extends E> l) {
    ...
  }
  public static <E> Liste<? extends E> reste(Liste<? extends E> l) {
    ...
  }
  public static <E> boolean egal(Liste<? extends E> k, Liste<? extends E> l) {
    ...
  }
  public static <E> String rep(Liste<? extends E> l) {
    ...
  }
  public static <E> Liste<? extends E> miroir(Liste<? extends E> l) {
    ...
  }
  public static <E> Liste<? extends E> concat(Liste<? extends E> g, Liste<? extends E> d) {
    ...
  }
  // Covariance :
  public static <A, B extends A> Liste<? extends A> conversion(Liste<? extends B> l) {
    ...
  }
  // Application de la fonction à chaque élément de la liste
  public static <A, B> Liste<? extends B> application(Function<A, B> f, Liste<? extends A> l) {
    ...
  }
  // Filtrage des éléments de la liste
  public static <E> Liste<? extends E> selection(Liste<? extends E> l, Predicate<E> filtre){
    ...
  }
  // Réduction des éléments de la liste : (neutre op e0 op e1 op ... op en)
  public static <E, R> R reduction(Liste<? extends E> l, R neutre, BiFunction<R, E, R> op) {
    ...
  }
}

Test

Tester votre implémentation des listes. 

public class Test {
  class A {}
  class B extends A {}
  public static void main(String[] args) {
    Liste<? extends B> lB = vide(B.class);
    Liste<? extends A> lA = application((A x) -> x, lB);
    System.out.println("[] : " + lA);

    Liste<? extends Integer> l = vide(Integer.class);
    System.out.println("vide : " + l);
    for (int i = 0; i < 10; i++) {
      l = cons(i, l);
    }
    System.out.println("9, ..., 0 : " + l);
    System.out.println("9, ..., 0 : " + rep(l));
    System.out.println("0, ..., 9 : " + rep(miroir(l)));

    System.out.println("true : " + l.equals(l));
    System.out.println("true : " + egal(l, l));
    System.out.println("false : " + l.equals(vide(Integer.class)));
    l = application((x -> x * 2), l);
    System.out.println("18, ..., 0 : " + l);
    l = selection(l, x -> (x >= 10));
    System.out.println("18, ..., 10 : " + l);
    l = liste(5, 7, 9, 11);
    System.out.println("5, ..., 11 : " + l);
    System.out.println("4 : " + reduction(application(x -> 1, l), 0, (x , e) -> x + 1));
  }
}

Noter les importations statiques du module et de la fabrique : cf. le tutoriel d'Oracle à ce sujet.

Compléter les tests de manière à tester toute méthode ou fonction.

Performances

Comparer les performances de votre implémentation avec celle des listes chaînées de l'API, en utilisant TestPerformance et LinkedListTest. Vérifier que les deux fonctions de test réalisent les mêmes calculs. Faire varier les paramètre dans TestConstantes pour comparer.

Fonctions

Souvent on rencontre des fonctions définies partiellement : certains éléments de leur domaine n'ont pas d'image. On peut représenter ces fonctions en remplaçant l'ensemble d'arrivée B par Optional<B>, soit l'ensemble B enrichi par une valeur exprimant la non-définition.

On va construire un type générique FonctionPartielle<A, B> pour représenter des fonctions partielles immutables. Ces fonctions partielles sont covariantes pour l'ensemble d'arrivée B et contravariantes pour le domaine A.

Pour obtenir la double variance, on utilisera systématiquement le type FonctionPartielle<? super A, ? extends B> au lieu de FonctionPartielle<A, B>.

Cette substitution est motivée par la règle de typage suivante, qui est valide en Java.

Si

  • C est un sous-type de A et
  • B est un sous type de D,

alors

  • FonctionPartielle<? super A, ? extends B> est un sous-type de FonctionPartielle<? super C, ? extends D>.

Comme pour les listes, l'interprétation ensembliste par une union paramétrée ici doublement, par un premier type minoré et par un second majoré, justifie cette règle. 

(Union S >= A, T <= B. FP<S, T>) <= (Union S >= C, T <= D. FP<S, T>) 
  car (A >= C) et (B <= D).

Pour cette partie, développer dans la classe session4.tp.fonctions.Partielles.

Interface fonctionnelle

Définir une interface fonctionnelle pour les fonctions partielles à partir de ce squelette. 

@FunctionalInterface
public static interface FonctionPartielle<A, B> {
  Optional<? extends B> appliquer(A x);
  // Composition fonctionnelle
  default <E> FonctionPartielle<? super E, ? extends B> composer(FonctionPartielle<? super E, ? extends A> g){
    ...
  }
}

Plongement

Plonger l'identité, toute fonction totale et tout prédicat dans l'espace des fonctions partielles. Précisément, définir trois fonctions génériques identite, plongementF et plongementP dans la classe Partielles. 

public static <E>  FonctionPartielle<? super E, ? extends E> identite(){
  ...
}
public static <A, B> FonctionPartielle<? super A, ? extends B> plongementF(Function<A, B> f){
  ...
}
public static <E> FonctionPartielle<? super E, ? extends E> plongementP(Predicate<E> p){
  ...
}

Test

Tester votre implémentation. 

public class Test {
  public static <A, B extends A, R, S extends R> 
   FonctionPartielle<? super B, ? extends R> conversion(FonctionPartielle<? super A, ? extends S> f) {
    return f;
  }
  public static void main(String[] args) {
    FonctionPartielle<? super Integer, ? extends Integer> f = plongementF(x -> x + 2);
    FonctionPartielle<? super Integer, ? extends Integer> g = plongementF(x -> x + 3);
    f = f.composer(g);
    System.out.println("7 : " + f.appliquer(2));
    FonctionPartielle<? super Integer, ? extends Integer> p = x -> (x > 2) ? Optional.empty() : Optional.of(x);
    f = f.composer(p);
    System.out.println("7 : " + f.appliquer(2));
    System.out.println("non défini : " + f.appliquer(3));
    p = plongementP(x -> (x > 0));
    f = f.composer(p);
    System.out.println("non défini : " + f.appliquer(0));
    System.out.println("6 : " + f.appliquer(1));
    System.out.println("7 : " + f.appliquer(2));
    System.out.println("non défini : " + f.appliquer(3));
  }
}

Ajouter un test par méthode et par fonction.

Conclusion

Il est donc possible de définir des types génériques avec des propriétés de variance en Java. A partir des exemples précédents, proposer des règles portant sur les occurrences des types pouvant varier : celles-ci doivent être respectées pour permettre la définition d'un type générique présentant de la variance.

Version history: v1: 2016-11-21.
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.