Évaluation incrémentale

J'ai aussi développé une méthode originale d'évaluation incrémentale [Par87,Par88,JPJ90]. Quelques mots sur le problème à résoudre : soit un arbre complètement décoré par des attributs, tel que ceux-ci soient consistants vis-à-vis des règles sémantiques de la GA qui les définissent. Une modification syntaxique de l'arbre (comme on peut en faire avec un éditeur structurel tel que CENTAUR ) peut se ramener au remplacement d'un sous-arbre consistant par un autre sous-arbre extrait précédemment d'un autre arbre lui aussi consistant. Au point de modification cependant, les valeurs des attributs peuvent ne pas être consistantes. L'évaluation incrémentale a pour but de rétablir la consistance du nouvel arbre en ne recalculant que les instances d'attributs nécessaires. À la suite des travaux de T. REPS, ce thème de recherche a connu un grand succès. La plus grande difficulté consiste à trouver des algorithmes de réévaluation asymptotiquement optimaux, c'est-à-dire dont la complexité est proportionnelle au nombre d'instances d'attributs dont la valeur dans le nouvel arbre est différente de celle dans l'arbre initial. Le problème est que les dites instances ne sont pas connues au moment où l'algorithme commence. Dans la réévaluation incrémentale comme dans l'évaluation exhaustive, il s'agit de trouver le meilleur compromis entre l'efficacité et la puissance d'expression. Ma méthode, fondée sur des travaux de G. FILé [Fil86], utilise un évaluateur quasi-déterministe capable de commencer son évaluation en tout nud de l'arbre et de ``remonter'' si besoin est. Un tel évaluateur peut être construit pour toute grammaire doublement non circulaire (DNC). La classe DNC est intermédiaire entre la classe FNC et la classe l-ordonnée, mais notre transformation FNC-l-ordonnée (cf. la section 2.3) permet d'appliquer ma méthode à toute grammaire FNC. La réévaluation incrémentale s'obtient en ajoutant à cet évaluateur un contrôle sémantique, dont le rôle est de tester, avant de réévaluer une instance, si c'est effectivement nécessaire et, après avoir réévalué une instance, de comparer sa nouvelle valeur avec son ancienne, de façon à savoir s'il faut réévaluer ses descendants. J'ai pu tester notre méthode dans des conditions réalistes (cf. la section 3.3.2) dans d'un environment interactif comme le système CENTAUR . De plus la séparation entre le contrôle sémantique et la méthode de réévaluation proprement dite induit une très grande souplesse d'utilisation de cette méthode. En effet, le contrôle sémantique, en règle générale, dépend fortement du type de l'application décrite. Ainsi ce dernier peut être redéfini pour l'application en question (voir la section 3.3.2).