Le blog de SpiceGuid

Un article de SpiceGuid    1 Commentaire

Il y a deux approches quant à la conception de l’interface d’un type container.

La première, dont Bertrand Meyer s’est fait le champion, est fondée sur les types abstraits de donnés.
L’idée directrice c’est que ce sont les données qui inspirent les opérations.
Considérant le TAD, on fait une liste de toutes les opérations associées.
Éventuellement on place ce TAD dans une classification qui pourra elle-même suggérer quelques opérations complémentaires afin de rendre le TAD compatible ou interchangeable avec ses parents ou ses cousins.

La seconde approche, initiée par Ivar Jacobson, est fondée sur les cas d’utilisation (use cases).
Ici l’idée directrice c’est qu’il faut d’abord être utilisable avant de prétendre à être réutilisable.
Par conséquent on liste les opérations dont on a besoin immédiatement, dans le cadre d’un premier développement.
On les complètera par la suite si elles se révèlent insuffisantes lors d’une future réutilisation.

Mon expérience malheureuse des deux côtés de la frontière m’incite à penser qu’aucune de ces deux approches n’est réellement complète et qu’en fait les deux sont autant nécessaires l’une que l’autre.

Illustration sur un exemple.

Le type abstrait de données

Dans le cas qui m’occupe il s’agit d’explorer un espace de recherche pour un jeu abstrait combinatoire du genre Dames, Échecs ou Rubik’s Cube.

Plusieurs séquences de coups peuvent éventuellement aboutir à une même configuration du jeu.
Il me faut donc une table de transposition pour stocker les configurations de jeu déjà explorées.
Dans le cas contraire il y aurait redite et l’espace à explorer pourrait apparaître encore plus vaste qu’il ne l’est déjà naturellement. D’où une spectaculaire chute de performance.

Qu’est-ce-qui pourrait bien implémenter une table de transposition ?
En fait tout ce qui m’intéresse c’est de savoir si une position de jeu est déjà dans la table, c’est-à-dire interroger la présence/absence d’un certain élément. Un module Set devrait faire l’affaire puisque ma préoccupation est principalement ensembliste. De plus Objective-Caml possède dans sa librairie standard un module Set dont on ne fait que vanter la performance. C’est l’occasion de l’utiliser.

Pour être plus précis, mon exploration de l’espace de recherche n’est pas totalement quelconque, en particulier j’aimerais bien pouvoir rechercher le chemin vers une position spécifique du jeu, c’est nécessaire par exemple pour résoudre le Rubik’s Cube. Pour diminuer la profondeur de l’espace je procède à une recherche bidirectionnelle. C’est-à-dire que je mange la banane par les deux bouts, j’explore à partir de la position initiale et en même temps j’explore (à rebours) à partir de la position finale. Quand les deux explorations se rejoignent j’ai trouvé une solution.

Du coup j’ai deux tables de transposition, une pour l’exploration à partir de la position initiale et une autre pour l’exploration à partir de la position finale. L’exploration s’arrêtera lorsque l’intersection des deux tables est non vide. Ça ne pose pas de problème puisque le module Set d’Objective-Caml est réputé pour son implémentation basée sur une variante d’arbres AVL qui permet entre autres le calcul efficace de l’intersection.

Le cas d’utilisation

En théorie tout va bien, mon TAD est un classique fourni en standard, il est performant et il possède les bonnes opérations.

Sauf que… il ne joint pas les deux bouts.

Je m’explique.
Les configurations du jeu ne sont pas stokées toute seules, elles sont associées à la suite des coups qui y mènent.
L’idée de la recherche bidirectionnelle c’est que, à l’endroit où les deux explorations se rejoignent, la solution complète est la concaténation du chemin depuis la position initiale et du chemin vers la position finale. Au moment de la jonction chaque table contient une moitié du chemin complet.

Pour réaliser la concaténation j’ai besoin des deux moitiées.
Or la sémantique du module Set est purement ensembliste, quand il rencontre deux éléments identiques l’intersection ne retiendra que l’un ou l’autre de ces deux éléments (puisque ce sont les mêmes).
En fait ce dont j’ai besoin ce n’est pas vraiment d’une opération d’intersection, c’est plutôt d’une fonction zipper qui devra traverser cette intersection et qui pour chacun des couples va concaténer les deux moitiées de chemin et me renvoyer une liste des solutions.
Techniquement, les éléments de mon ensemble sont des couples (coups,position). Je veux que la comparaison se fasse sur les positions mais quant au résultat seuls les coups m’intéressent. Je n’ai que faire de savoir où s’arrête la recherche bidirectionnelle, seules les solutions sont à retenir.

L’opération dont j’ai besoin (zipper une intersection) m’apparaît légitime à figurer dans l’interface d’un module Set.
Si elle n’est pas présente en standard c’est parce que la Caml Team :

• a pensé aux ensembles en général, sans voir comment les opérations pouvaient se spécialiser pour le cas (important en pratique) où les éléments sont des associations (clé,valeur)
• s’est investie (avec succès) sur la question de la qualité et du paradigme fonctionnel comme une alternative aux solutions impératives habituelles
• s’est concentrée sur la question de l’algorithme et des performances en développant une variante exotique des arbres AVL
• a été plus motivée par l’intérêt de fournir un exemple de higher-order module que par les exigences d’applications qui utiliseraient le module Set

Conclusion

En résumé, comme c’est souvent le cas avec les développements difficiles et innovants, la Caml Team avait plusieurs objectifs ambitieux à atteindre. Et aucun d’eux ne réclamait une approche par cas d’utilisation. On voit les limites de cette façon de penser au container sans penser aux éléments. Pour anticiper les bonnes opérations il faut imaginer les types d’élément les plus courants afin d’en percevoir les éventuelles retombées sémantiques. On découvrira alors que certains paramètres additionnels sont nécessaires pour le traitement de certains types composites. Des paramètres qui, pour le type général, se camouflaient sous la forme innocente (et surtout implicite) d’une projection triviale.

Un simple cas d’utilisation suffit souvent à révéler toute la richesse d’une interface qu’on aurait pas pu soupçonner vu du TAD ou de la théorie des ensembles.
Ne vous enfermez pas dans l’idéologie selon laquelle le type des éléments n’aurait aucune incidence sur le type des opérations. Ce sera vrai… dès que vous aurez explicité toutes ces incidences.