Previous Contents Next
Chapter 7 Préambule
Les méthodes de détection de réductions décrites dans l'introduction présentent deux principaux défauts : 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.

Previous Contents Next