Programmation Objet et induction : le patron de conception Composite

Les définitions inductives (ou récursives, ou par récurrence) sont fréquentes et utiles, car elles permettent de définir non seulement des ensembles (dits engendrés inductivement), mais aussi des fonctions (dites récursives) de domaine ces ensembles, par des relations de récurrence structurelle (récurrence au sens large, pas seulement sur l'ensemble des entiers naturels). De telles définitions se présentent sous la forme suivante :

• des cas de base, permettant d'amorcer la récurrence,
• des cas construits, utilisant ce qui a déjà été défini.

Par exemple, les démonstrations par récurrence rentrent dans ce cadre : on démontre la propriété en 0, puis en n + 1, en supposant la propriété vraie au rang n (hypothèse dite de récurrence). Le principe est donc de décomposer récursivement un cas construit en des sous-cas, jusqu'à obtenir des cas de base. Cette décomposition doit se faire en un nombre fini d'étapes : c'est un critère de bonne fondation. Voici quelques exemples d'ensembles engendrés inductivement :

• les listes : une liste est soit vide, soit formée d'un élément suivi d'une liste,
• les mots : un mot est soit le mot vide, soit une lettre suivie d'un mot,
• les arbres binaires : un arbre est soit vide, soit formé d'un élément, l'étiquette, et de deux arbres, les fils gauche et droit,
• les entiers naturels : un entier naturel est soit zéro, soit le successeur d'un entier naturel,
• les expressions arithmétiques : une expression arithmétique est soit un entier naturel, soit l'application d'une opération arithmétique à un ou deux entiers naturels
• les propositions logiques : une proposition est soit une proposition atomique, soit une conjonction, disjonction ou négation.

Il est facile de définir des fonctions récursives ayant pour domaine des ensembles engendrés inductivement. Il suffit de procéder par cas et de décomposer tout élément construit en des éléments plus simples. Cela donne, par exemple pour les listes, ce genre de définitions pour une fonction f prenant une liste l comme paramètre :

• si l est la liste vide, alors f(l) est égal à une certaine constante c,
• sinon, si l est une liste composée d'un premier élément suivi d'une sous-liste k, f(l) est égal à F(l,f(k)), où F est une fonction donnée.

Les constantes c et F paramètrent la définition récursive de f.

Comment rendre compte en Java des définitions inductives ?

Dans le cas d'une définition ne comportant que des cas de base, il est assez naturel d'utiliser une interface pour désigner l'ensemble défini et ses opérations, en un mot le type abstrait, et une classe d'implémentation pour chaque cas de base.

Par exemple, définissons une forme géométrique plane comme étant soit un cercle, soit un triangle, soit un carré ; les formes géométriques en général sont alors représentées par une interface, les cercles par une classe concrète d'implémentation, et de même pour les triangles et les rectangles. L'interface contiendra en plus des services des méthodes particulières, appelées sélecteurs, qui permettent de déterminer si une forme géométrique est un cercle, un triangle ou un rectangle respectivement.

Généralisons cette méthode, fondée sur la définition d'une interface pour l'ensemble engendré inductivement et de classes d'implémentation pour chaque cas de définition. Seule nouveauté, les champs des classes peuvent contenir des références à des objets ayant pour type l'interface en cours d'implémentation : c'est cet auto-référencement par chaînage qui traduit la récursivité des définitions inductives. A ces attributs correspondent des accesseurs déclarés dans l'interface, et appelés destructeurs.

En résumé, l'interface contient :

• les services offerts par le type abstrait de données,
• les sélecteurs, permettant de déterminer le cas de définition auquel correspond l'objet cible,
• les destructeurs, permettant de décomposer l'objet cible, lorsqu'il s'agit d'un cas construit.

Une classe d'implémentation correspond à un cas de définition, et implémente les services et les sélecteurs suivant ce cas, ainsi que les destructeurs propres à ce cas, les autres n'étant pas définis.

Cette méthode est si commune qu'elle porte un nom : le patron de conception Composite. Pour un exemple, voir le premier TP, une implémentation inductive des entiers naturels.