Les méthodes de détection de réductions décrites
dans l'introduction présentent deux principaux défauts :
-
soit elles ne travaillent qu'à partir d'une représentation
approximative du programme initial (représentation par valeurs
symboliques, symbolic stores en anglais) ;
- soit elles n'effectuent pas de normalisation sur le programme
initial et donc nécessitent une phase de reconnaissance de formes
trop coûteuse.
Nous présentons donc une nouvelle méthode de détection de
réductions et de scans
1
basée sur une représentation des programmes
par un système d'équations récurrentes (SER).
En effet, sous des conditions usuelles, un programme écrit dans
un langage impératif peut être traduit en un SER. Cela permet
d'appliquer une normalisation à l'aide de substitutions à la Gauss,
c'est-à-dire en remplaçant certaines variables par leurs définitions.
Cette normalisation est efficace puisque la détection des récurrences
se réduit alors à un simple examen des expressions des
équations du SER. La reconnaissance de forme
est donc limitée à la vérification de l'associativité de la
fonction de propagation des récurrences détectées.
Cette partie montre comment le programme source peut être transformé
en SER. Les différentes stratégies de normalisation sont alors
présentées, ainsi que les différents algorithmes de normalisation.
Une fois les scans et les réductions détectés il faut encore
pouvoir les manipuler ; une forme condensée pour exprimer
ces récurrences particulières est définie. Il est montré comment
cette forme permet la détection de récurrences dont l'espace
d'accumulation est une ligne brisée : les scans multi-directionnels.
La méthode utilisée pour filtrer les scans et les réductions
dans l'ensemble des récurrences est présentée à la fin de la partie.
- 1
- Cette méthode peut s'étendre facilement à la
détection de récurrences générales.