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 n
ud 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).