Les curseurs

Concept central d’ASTL, le curseur centralise les fonctions d’accès aux données et leur conversion au format standard qu’exigent les algorithmes. Il constitue avec l’itérateur la glu qui lie tous les autres composants logiciels entre eux. Le concept de curseur généralise celui d’itérateur : né de la nécessité de parcourir ou traverser des structures de données, un modèle de curseur est un accesseur, c’est-à-dire un objet représentant une position dans un automate et capable de lire la valeur s’y trouvant. La notion de position regroupe différents concepts selon les besoins algorithmiques : un état q, une transition (q, a, p) ou un chemin. C’est pourquoi la notion de curseur se divise en quatre sous-notions liées par des relations de sous-typage ou d’encapsulation et qui s’imbriquent à la manière des poupées gigognes (voir figure 4.1), l’itérateur classique apparaissant alors comme un cas particulier du curseur. En effet, un itérateur n’est rien d’autre qu’un curseur qui connaît l’enchaînement des transitions à suivre le long de l’automate puisque sur une séquence il n’y a jamais de décision à prendre lors de l’incrémentation. Un curseur muni d’une politique de parcours est un itérateur.

Par raffinements successifs du concept curseur simple (cursor) on en déduit les concepts curseur monodirectionnel (forward cursor), curseur pile ou file (stack/queue cursor) et curseur de parcours (depth-first cursor dans le cas du parcours en profondeur par exemple). Les curseurs simples et monodirectionnels constituent la base commune à tous les algorithmes de parcours implémentés dans les deux couches les plus externes. La puissance de ces concepts vient essentiellement de la facilité à modifier leur comportement standard pour étendre leurs fonctionnalités et leurs champs d’application grˆace aux adaptateurs. 

Notations

Les sections suivantes décrivent les concepts importants relatifs aux curseurs. Les modèles s’y conformant sont majoritairement des patrons de classes et les algorithmes des patrons de fonctions. Pour chaque concept, une description des paramètres d’instanciation est donnée, cependant, dans le but de clarifier l’exposé et partout o`u cela ne prˆetait pas à confusion, les exemples de codes ont été épurés de toute référence aux patrons, c’est-à-dire au mot clé template. Généralement, baptiser judicieusement les types et les noms de variables suffit à rendre le code assez clair pour pouvoir se focaliser sur les abstractions et masquer les détails  C Fig. 4.1 – Les concepts de curseur pour le parcours en profondeur d’implémentation. Pour une description technique plus détaillée et des exemples complets d’utilisation se reporter à l’annexe A.3. 

Motivations

A l’origine de l’introduction du concept de curseur il y a : 1. La nécessité de découpler au maximum l’algorithme de la structure de données. Les détails d’implémentation n’intéressent pas l’algorithme qui doit s’affranchir de tout type de représentation en mémoire en faisant un minimum de suppositions sur les objets. La communication s’établit à travers une interface standardisée imposant le moins de choses possible aux deux parties. Le masquage des données est fondamental en programmation générique. 2. Le besoin de factoriser les fonctionnalités communes les plus utilisées et de les placer hors de l’algorithme et de la structure de données afin de minimiser la quantité de code à écrire. Les fonctions de parcours sur les automates présentent des similitudes quels que soient les types d’automates, déterministes ou non, synchrones/asynchrones, etc., et quels que soient les algorithmes, copie, lecture sur flux, etc. Les curseurs « capturent » les propriétés les plus significatives et les plus partagées des traitements appliqués aux automates. 3. La lourdeur des techniques habituelles utilisées pour implémenter les parcours génériques, c’est-à-dire le patron de conception visiteur dont la mise en œuvre ne se justifie pas toujours, particulièrement dans les cas les plus simples o`u son utilisation aurait plutˆot tendance à compliquer l’écriture et la compréhension du code. On a souvent besoin d’un parcours classique en profondeur ou en largeur ne nécessitant pas de fonctionnalité particulière ; les curseurs permettent la réutilisation de ces algorithmes avec seulement 

Les excellents résultats obtenus par STL en utilisant un modèle à trois couches incitent fortement à généraliser cette technique (figure 4.2). 4.3 Le curseur simple Le curseur constitue le modèle de base dont découle toute la hiérarchie des accesseurs sur automate. Notation On notera C l’ensemble des curseurs et cq ∈ C un curseur pointant sur un état q ∈ Q de l’automate A(Σ, Q, i, F, ∆). 4.3.1 Définition Un curseur cq est un objet pointant sur un état q ∈ Q de l’automate A. Son rˆole consiste à garder la trace de l’état courant tout au long de l’algorithme. Il permet en outre d’implémenter un parcours simple le long d’un chemin. 4.3.2 Propriétés Un curseur : 1. Possède une valeur singulière lorsqu’il ne pointe sur aucun état ou lorsqu’il pointe sur l’état nul. 2. Est assignable, c’est-à-dire qu’il est possible d’affecter à c ∈ C la valeur d’un curseur c ′ . Il est également possible de lui affecter un état q ′ ∈ Q après quoi c = cq ′