Arbres immuables et fantaisies associées
Laurent Caillette
Voici une petite découverte programmatique autour des arbres et de
l'immuabilité. Après un survol de l'algorithmique j'évoque une
utilisation possible dans de l'informatique de gestion.
Considérons la structure de données représentant un arbre. La
représentation la plus simple consiste en une séquence de sous-arbres
"fils".
public class Tree {
private final Tree[] children ;
public Tree( Tree[] children ) {
this.children = children.clone() ;
}
public int getChildCount() {
return children.length ;
}
public Tree getChild( int index ) {
return children[ index ] ;
}
}
Disons que dans une application du monde réel on aurait tendance à
ajouter un champ pour représenter une valeur quelconque, mais le code
est plus lisible en l'état.
Avec la définition ci-dessus, il n'est plus possible de modifier une
instance de Tree après sa création (si, avec de la réflexion et en
tapant dans le tableau mais j'utilise un tableau pour la brièveté, je
pourrais blinder l'implem avec une liste immuable maison). Notons
aussi l'absence de "backpointer" sur un éventuel parent. En
conséquence, non seulement notre Tree est protégé contre tout effet de
bord, mais une instance de Tree peut également être partagée par
plusieurs autres Tree dont elle serait un des fils. Jusque là, c'est
magnifique !
Le problème des objets immuables, c'est, comme dirait l'autre, qu'ils
sont immuables et que des fois on aimerait bien changer leur état. Si
la solution est évidente avec des objets comme la String qui ne
référence rien en dehors de son contenu, c'est plus délicat quand il y
a des références qui sortent de partout.
Considérons une fonction qui aplatit le contenu d'un Tree (ça pourrait
être n'importe quoi du moment qu'elle en affecte la structure) :
public static Tree flatten( Tree tree ) { ... }
Si nous avons un arbre comme suit :
t0
/ | \
t1 t2 t3
/ \
t4 t5
|
t6
En appliquant notre fonction 'flatten' à t3 on obtient :
t3'
/ | \
t4 t5' t6
Notons que la nouvelle instance de t3 notée t3' référence une nouvelle
version de t5 notée t5'. t5' est maintenant dépourvu d'enfants. t4 et
t6 ne sont pas affectés.
On constate que t0 demeure inchangé et "non averti" des modifications
de t3 et compagnie. Bon je l'ai bien cherché. Comment faire pour
propager de telles modifications sans perdre les propriétés vues plus
haut ?
La solution consiste à contextualiser toute modification en passant
non plus seulement l'arbre à faire évoluer à une fonction mais toute
la parenté que ça concerne.
Définissons une structure Treepath qui représente un Tree en tant que
membre d'un autre Tree.
public class Treepath {
private final Treepath parent ;
private final Tree tree ;
public Treepath( Treepath parent, Tree tree ) {
this.parent = parent ;
this.tree = tree ;
}
}
Remarquons tout de suite qu'une telle structure est elle aussi
immuable. Avec, on représente la position de t3 au sein de t0 comme
suit :
Treepath p3_0 = new Treepath( new Treepath( null, t0 ), t3 ) ;
En mémoire on a quelque chose comme :
t0 <- p0 <--+
/ | \ |
t1 t2 t3 <- p3_0
/ \
t4 t5
/ \
t6 t7
Une limitation acceptable est de se baser sur l'unicité des objets
Tree en mémoire ; par exemple la même instance ne peut être référencée
plusieurs fois au sein du même arbre (sous peine de faire cafouiller
tous les algorithmes). Autrement on peut se baser sur des indices mais
c'est beaucoup moins joli.
Maintenant on peut changer la signature de notre fonction flatten comme suit :
public static Tree flatten( Treepath treepath ) { ... }
Et si on applique notre fonction :
final Treepath p3_0_flat = flatten( p3_0 ) ;
Voici la valeur retournée :
t0' <- p0' <--+
/ | \ |
t1 t2 t3' <- p3_0_flat
/ | | \
t4 t5' t6 t7
Et on a bien une version modifiée de tout l'arbre, avec une fonction
qui n'en touche qu'à une sous-partie !
Si c'est vraiment incompréhensible je conseille de copier-coller tout
le texte dans un éditeur avec une police non-proportionnelle !
Alors, quelles sont les utilisations possibles ? Je me souviens d'un
projet (IDEA/EProm chez SG) où tous les objets business se
construisaient à coup de builders avant d'être délivrés dans des
versions immuables. Les structures correspondaient en général à des
arbres et le problème à celui décrit ci-dessus : il manquait une
méthode générique pour la reconstruction d'un contexte modifié et la
bonne intention s'est vite transformée en souffrance à grande échelle.
D'accord dans mon cas c'est facile : les Tree ne sont pas typés donc
la généricité vient automatiquement. Mais sans laisser de côté de
typage, on peut le voir comme une façon d'habiller des données brutes
contenues dans les Tree et Treepath.
public class Root {
public Root( Treepath treepath ) { ... }
public int getThingCount() { ... }
public Thing getThing( int index ) { ... }
}
public class Thing {
public Thing( Treepath treepath ) { ... }
public Root getRoot() { ... }
String getName() { ... }
Thing setName( String newName ) { ... }
}
L'astuce consiste à faire reposer tout l'état de Root et Thing sur un
Treepath. Maintenant si on veut modifier l'état d'un Thing :
public static Root updateAllThings( Root root, String newName ) {
for( int i = 0 ; i < root.getThingCount() ; i++ ) {
final Thing modified = updateOneThing( thing, newName ) ;
root = modified.getRoot() ; // Legal!
}
}
public static Thing updateOneThing( Thing thing, String newName ) {
return thing.setName( newName ) ;
}
}
On remarque que la boucle pour obtenir tous les Thing est un peu
laborieuse car on ne peut plus accéder aux objets par référence : le
root change à chaque modification ! Sans ça on aurait plein d'objets
Root avec chacun une seule Thing modifiée, immédiatement
garbage-collectables. Ce petit hack permet bien d'obtenir ce qu'on
voulait : une méthode 'updateOneThing' qui produit une version
modifiée d'un objet immuable sans avoir à se soucier de qui le
référence.
Pour cet article je me suis basé sur une implémentation valide du Tree
/ Treepath décrits mais je n'ai rien de concret pour mieux comprendre
comment instancier des objets business à partir d'un Treepath. Restent
aussi les aspects tels que la persistance et la sérialisation... Mais
je crois en d'heureuses simplications toujours grâce aux objets
immuables.
Enjoy !
c.
Annexe :
La première implémentation de Treepath qui me soit passée sous les yeux :
http://java.sun.com/j2se/1.5.0/docs/api/javax/swing/tree/TreePath.html