L'exemple qu'on traite est le programme Lisp qui implante les fonctions de modification incrémentale de la syntaxe abstraite (cf. Chapitre 5.5, « Construction de la Syntaxe Abstraite »). Deux remarques s'imposent :
- Le choix de l'exemple n'est pas innocent : c'est une partie du programme écrit dot la rédaction a été particulièrement soignée ; c'est-à-dire que l'homogénéité du programme est à la mesure de l'effort de spécification-conception préliminaire. Cette constatation n'est pas une surprise : si l'on veut obtenir des programmes bien construits le prix à payer est un supplément de travail non négligeable dans les premières étapes du développement – définition du problème et définition de la solution.
- Le type de problème abordé est purement algorithmique ; le modèle mathématique sous-jacent est presque apparent dans le programme. Les symétries qu'on observe dans le programme sont donc à rapprocher de celles qu'on trouve très fréquemment en mathématiques.
Je ne pense pas qu'il faille en conclure que l'exemple est mal choisi : on n'a pas toujours de répétition dans le texte source d'un programme ; mais quand on en a, et c'est le cas spécialement dans les parties algorithmiques, il me semble intéressant de les mettre en relief. C'est la situation dans laquelle on se place.
Pour terminer ce préambule, je voudrais juste signaler que le programme n'a pas été remanié pour étayer l'argumentation. S'il présente de nombreuses symétries c'est parce qu'elles se sont imposées d'une façon naturelle à la rédaction du programme.
1. Présentation générale
2. Les données
3. Les traitements
1. Présentation générale
L'analyse du problème conduit à décomposer le programme en deux niveaux :
- en haut : les « fonctions utilisateurs »
put | = placer |
rem | = supprimer |
get | = obtenir des informations |
- en bas : les « types de données »
PHYL | = phylum |
OPER | = opérateur |
DRAP | = drapeau : phylum × opérateur |
L'implantation présentée diffère légèrement de celle qu'on trouve formellement définie dans la partie Technique (cf. ibid.) : on n'introduit pas de matrice des phyla, et à chaque phylum on attache alors la liste des phyla pères. Ceci permet de n'avoir qu'une seule structure de données, ce qui simplifie la présentation.
Note :
Relativement au coût des algorithmes, on perd en efficacité sur la fonction ascendance : celle-ci construit l'ascendance d'un phylum donné en parcourant le graphe comme s'il s'agissait d'un arbre. Elle passera donc plusieurs fois sur les mêmes nœuds si deux chemins différents y conduisent.
Pour la syntaxe initiale, la seule situation où on passe deux fois sur un même nœud est celle (1) où le nœud d'origine est le phylum LSP et (2) où le nœud doublement visité est le phylum SEX. Du fait de la faible connexité du graphe, l'algorithme en pratique est donc plus efficace – quoiqu'en théorie il le soit moins.