UP | HOME

Immutabilité - Un choix important pour les implémentations

Table of Contents

Revenons aux entiers naturels. On a vu deux implémentations qui partagent une propriété commune, celle de définir des objets dits immutables : une fois créés, les entiers naturels conservent leur état initial, si bien que chaque calcul se traduit par la création d'un nouvel objet pour stocker le résultat.

// Implémentation de NatParInt
public Nat somme(Nat x){
  return new NatParInt(this.getInt() + x.getInt());
}
// Implémentation de NatDecimal
public Nat somme(Nat x){
  ...
  ... this.chiffre(i) ... x.chiffre(i) ...
  ...
  return new NatDecimal(...);
}

On peut imaginer des implémentations alternatives, qui modifient en place les entiers naturels sans créer de nouveaux objets à chaque calcul : l'état peut alors varier après la construction. On dit alors que les objets sont mutables.

Réalisation d'une implémentation mutable

  • Dans un paquet session1.mutabilite, créer une nouvelle classe NatParInt implémentant l'interface Nat.

    Rappel : l'interface Nat

    public interface Nat {
          Nat somme(Nat x);
          int getInt();
          int chiffre(int i);
          int taille();
    }
    
  • Récupérer le code de la classe NatParInt définissant des entiers naturels immutables.
  • Ajouter un accesseur privé en écriture void setInt(int i).
  • Modifier la méthode somme de manière à modifier en place l'objet cible (celui référencé par this).
  • Réaliser une transformation analogue pour l'autre implémentation, en définissant une nouvelle classe NatDecimal. Pour cela, récupérer le code de la classe NatDecimal définissant des entiers naturels immutables, y ajouter un accesseur en écriture et modifier la méthode somme.
  • Définir deux fabriques, une par classe d'implémentation. Chaque fabrique implémente l'interface FabriqueNat, rappelée ci-dessous.

    public interface FabriqueNat {
      Nat creerNatAvecValeur(int x);
      Nat creerNatAvecRepresentation(String repDecimale);
    }
    

Immutabilité contre mutabilité : comment choisir

  • En préalable, pour pouvoir comparer les entiers naturels, définir dans toutes les classes d'implémentation de Nat une méthode equals spécifiée ainsi : si l'argument n'est pas de type Nat, renvoyer false, sinon tester l'égalité des Nat en comparant les int associés. Réutiliser le même code dans toutes les classes.
  • Créer une classe de test dans le paquet session1.mutabilite.
  • Réaliser le test suivant dans une fonction void comparerMutabilite(FabriqueNat fab).
    • En utilisant la fabrique fab, créer un entier naturel n7 de valeur 7 et un entier naturel n1 de valeur 1.
    • Comparer n7 à n7.somme(n1) en utilisant la méthode equals, et afficher le résultat de la comparaison.
  • Appeler la fonction comparerMutabilite avec les quatre fabriques, celles permettant de créer des entiers immutables et celles permettant de créer des entiers mutables. Qu'observe-t-on lors de l'exécution ?
  • Analyser les résultats.

Une synthèse

Bien se rappeler la définition.

  • Donnée mutable = donnée dont l'état peut changer
  • Donnée immutable = donnée non mutable

La forme d'une interface, précisément le typage des opérations, peut permettre de déterminer la mutabilité des données associées.

void somme(Nat x) mutable
Nat somme(Nat x) immutable ou mutable

Dans le second cas, la documentation de l'interface doit préciser s'il s'agit de données mutables ou non.

Les langages Typescript et Java ne permettent de désigner l'immutabilité que de manière parcellaire : voir readonly ou final. En l'absence de marqueurs syntaxiques de la mutabilité plus complets, des conventions de nommage peuvent aussi permettre de déterminer simplement la mutabilité. Par exemple, on peut utiliser des noms pour les opérations dans le cas immutable, des verbes dans le cas mutable.

void sommer(Nat x);
// ou
Nat sommer(Nat c);
// contre 
Nat somme(Nat x)

D'un point de vue logique, seules les données immutables permettent de raisonner correctement. Comme on l'a vu, avec des données mutables, on obtient des incohérences, rédhibitoires pour le raisonnement.

Les données immutables possèdent ainsi une propriété importante, la transparence référentielle. Leur adresse en mémoire importe peu : elle ne sert qu'à se référer à la donnée dont seul l'état, permanent, est significatif. On peut donc imaginer pour un programme une situation où une donnée particulière est représentée par un unique objet en mémoire : elle sera donc manipulée par une unique référence, qui sera partagée par tous les utilisateurs de cette donnée. A l'opposé, on peut imaginer une situation où cette même donnée est représentée par de nombreux objets en mémoire : elle sera donc manipulée par de nombreuses références. Conséquence de la transparence référentielle, ces situations sont équivalentes. En revanche, avec des données mutables, ces situations ne le sont pas : le partage d'une référence est un point crucial, aux conséquences importantes. Pour raisonner avec des données mutables, il est donc nécessaire de prendre en compte non seulement les états des objets mais aussi leurs références (c'est-à-dire leurs adresses en mémoire).

Les données immutables possèdent également la propriété de persistance. Elles persistent après un usage, si bien que la valeur avant l'usage peut être accessible comme celle après usage. Si on représente les dépendances entre les données, on obtient une arborescence lorsque les données sont immutables. Lorsque les données sont mutables, on obtient une ligne.

Sorry, your browser does not support SVG.

Figure 1: Evolution des versions de données immutables

Sorry, your browser does not support SVG.

Figure 2: Evolution des versions de données mutables

(Ces arbres unaires ou binaires représentent les différentes versions des données, un arc reliant une version avant l'opération à une version après l'opération. Dans le cas de données mutables, seule la nouvelle version est accessible. Avec des données immutables, deux versions peuvent être accessibles : la nouvelle et possiblement l'ancienne.)

La propriété de persistance est importante dans le cas de définitions récursives, avec des appels multiples.

R F(A x) {
  ... F(d1(x)) ... F(d2(x)) ... F(d3(x)) ...
  return ...
}

Lorsque le type A est mutable, si les fonctions de décomposition d1, d2, d3, etc. modifient en place l'argument x, alors le calcul devient faux sans précautions : il devient nécessaire ou bien de passer des copies de x lors des appels récursifs, ou bien de modifier à la sortie de chaque appel récursif l'effet provoqué par l'appel des fonctions de décomposition. Lorsque le type A est immutable, aucune précaution n'est nécessaire.

Si les données mutables n'ont pas de bonnes propriétés logiques, elles se révèlent en revanche efficaces. A titre d'exemple, on pourra exécuter la fonction principale de la classe session1.demo2.StringVSStringBuilder. Celle-ci utilise pour un même algorithme deux implémentations de chaînes de caractères, celle immutable, définie par la classe String, et celle mutable, définie par la classe StringBuilder. On observe un rapport de mille dans l'exécution : c'est que la complexité n'est pas la même (linéaire contre quadratique), à cause de la création de nouveaux objets pour chaque calcul dans le cas des String, ici l'ajout d'un caractère à la chaîne.

Ce cas est un peu extrême, par son changement de complexité, et ne doit pas donner une fausse impression : il est en effet simple d'implémenter des données immutables ayant la même complexité que des données mutables, lorsqu'elles sont utilisées sans persister (d'une manière linéaire). Par exemple, dans l'exemple précédent, il faudrait disposer de chaînes de caractères pour lesquelles l'ajout d'un caractère, à gauche ou à droite, se fait en temps constant. C'est possible en utilisant deux listes de caractères, correspondant au début et à la fin du mot. Si cette technique est simple, elle est cependant méconnue. Elle présente une difficulté pour l'estimation de la complexité en temps : elle repose sur l'amortissement. Lorsqu'une telle structure de données est utilisée d'une manière non linéaire, l'amortissement peut devenir impossible : la complexité se dégrade. Des solutions existent, mais deviennent sophistiquées. Remarquons que l'équivalent mutable d'une telle solution est une structure de données dont la copie se fait en temps constant : c'est un problème difficile également. On pourra lire à ce sujet la thèse d'Okasaki, intitulée "Purely Functional Data Structures".

Recommandation finale : utiliser des données immutables quand on peut, des données mutables sinon.

En pratique, un programme s'organise souvent à partir de types qu'on peut classer en deux catégories :

  • des acteurs, peu nombreux, qui organisent le flot des données, et sont plutôt mutables,
  • des données, plus nombreuses, que s'échangent les acteurs et qui sont immutables.

Lorsque le fait d'utiliser des données immutables pénalise les performances du programme, les données immutables peuvent être localement converties en données mutables suivant le schéma ci-dessous.

public String fonctionPenalisante(String s){
  String res = ...;
  // nombreux calculs concernant s et res
  ... s ... res ... 
  return res;
}
// Passage de String à StringBuilder 
// tout en préservant l'interface   
public String fonctionPlusEfficace(String s){
  // Coercition de l'argument
  StringBuilder ms = new StringBuilder(s);
  StringBuilder mres = ... ;
  // nombreux calculs concernant ms et mres
  ... ms ... mres ...
  // Conversion explicite du résultat
  return new String(mres);
}

Résultat : non seulement l'utilisateur de la fonction peut raisonner logiquement puisque l'interface utilise des données immutables, mais aussi la fonction s'exécute plus efficacement (d'une manière plus rapide et plus économe pour la mémoire).

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