Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Introduction aux macros de Scheme
Instrumentation de programme : KMP
Article mis en ligne le 7 juin 2006
dernière modification le 3 janvier 2007

par Laurent Bloch

"http://www.w3.org/TR/REC-html40/loose.dtd">

Analyse de programme par instrumentation

Analyse de programme par instrumentation

Laurent Bloch

Le 7 juin 2006


Cet article est la suite de celui consacré, entre autres, à
l’algorithme de Knuth-Morris-Pratt. Signalons aussi
l’excellent article de Wikipedia, en
français
.





1. KMP, le traitement du motif



L'idée de l'algorithme est simple: lorsque nous ne réussissons plus à faire progresser l'indice j vers la droite, en fait nous faisons progresser l'indice i mais dans ce cas nous réexaminons à nouveau des caractères du texte. Puisque nous les avons déjà vus ne pourrions nous pas nous en passer?

La deuxième idée est que puisque les caractères du texte que nous avons examinés sont les « bons » en fait ce sont les caractères de la sous-chaîne que nous avons vus : nous pouvons savoir ce qui nous arrivera d'avance uniquement en examinant d'abord les caractères de la sous chaine.





Figure 1:



La fonction qui construit la table des préfixes est écrite selon la méthode suivante. La chaîne Motif = atataga est comparée à un texte Texte tel que les q = 5 premiers caractères concordent. En ne nous servant que de notre connaissance des 5 caractères concordants, on peut déduire qu'un décalage de s0+1 est invalide, mais qu'un décalage de s1=s0+2 est cohérent avec ce que nous savons jusque là du texte, et donc potentiellement valide.

Les informations utiles pour ces déductions peuvent être pré-calculées en comparant le motif avec lui-même. ici, on voit que le plus long préfixe de Motif qui est aussi un suffixe de Motif-5 est Motif-3. Cette information est pré-calculée et représentée dans le tableau Table-prefixes, de sorte que Table-prefixes[5]=3. Sachant que q caractères ont été appariés avec succès au décalage s0, le prochain décalage potentiellement valide est :

s1=s0 + (q -Table-prefixes[q])

Algorithme : kmp-pretraite Donnée : Motif ; une chaîne Résultat : Table-prefixes ; un tableau des adresses des ; plus longs préfixes propres identiques ; à un suffixe de chacun des préfixes. Soit L-motif <- longueur de Motif pour k allant de 0 à L-motif - 1 faire i <- k-1 tant que i != -1 et Motif[Table-prefixes[i] + 1] != Motif[k] faire i <- Table-prefixes[i] fait si i = -1 alors Table-prefixes[k] <- -1 sinon Table-prefixes[k] <- i fait




2. Étendre la syntaxe pour observer un programme



Nous allons reprendre le programme de pré-traitement de l'algorithme, mais pour en observer le comportement nous allons l'instrumenter, c'est-à-dire y insérer des expressions dont l'évaluation va écrire sur la sortie standard (par exemple) les résultats d'observations.

Pour ce faire nous allons introduire un nouveau moyen d'étendre notre langage, les macro-instructions.

Macro-instructions



Pour mesurer le fonctionnement de notre programme nous pourrions en modifier le texte pour y introduire des manipulations de compteurs ou des commandes d'impression, mais cette technique est inélégante, source d'erreurs et de difficultés de gestion du code source. Il est plus approprié de faire modifier le texte du programme... par un programme, évidemment, en l'occurrence le compilateur, qui est justement un logiciel adapté à ce genre de travail.

Le moyen qui permet de réaliser des modifications du texte d'un programme est la macro. Le principe en est de générer un texte Scheme qui sera ensuite évalué.

La forme spéciale define-macro permet de décrire le texte à générer1. La syntaxe en est analogue à celle de define :
(define-macro (<nom de la macro> p1 p2 ... pk)
         <corps de la macro>)
L'usage de notre nouvelle macro se fait ainsi :
(<nom de la macro> a1 a2 ... ak)
ce qui s'évalue en deux étapes selon la règle suivante :
  1. Macro-expansion : les paramètres formels p1 p2 ... pk sont liés aux arguments a1 a2 ... ak sans évaluation de ceux-ci, puis le <corps de la macro> est évalué dans cet environnement. L'expression qui résulte de cette évaluation est appelée expansion de la macro.
  2. L'expansion obtenue à l'étape précédente est évaluée dans l'environnement courant de l'appel.
L'étape 1 (expansion) construit un texte Scheme, qui est évalué à l'étape 2.

La difficulté est de rédiger le corps de la macro de sorte que son expansion donne le résultat voulu. Les formes spéciales quasiquote (qui s'abrège en </CODE>, cf. <A HREF="#sec:arobas">??</A>), <CODE>unquote</CODE> (qui s'abrège en <CODE>,</CODE>) et <CODE>unquote-splicing</CODE> (qui s'abrège en <CODE>,@</CODE>) sont généralement mises à contribution à cet effet.<BR> <BR> Ils faut considérer les actions effectuées par les macros comme s'il s'agissait d'opérations réalisées avec un éditeur de texte : elles doivent précéder physiquement la compilation du programme et <EM>a fortiori</EM> son exécution. En particulier, le texte de définition d'une macro doit précéder son invocation ; une macro n'est pas exportable d'un module à l'autre.<BR> <BR> Il est possible avec des macros de modifier une procédure (même du standard) pour lui incorporer un compteur, ainsi pour Fibonnaci d'un cours précédent :<BR> <BR> <DIV CLASS="lstlisting"><TT>(<B>define</B> (compte-fonction compteur fonction)</TT><TT> </TT><TT>   (<B>lambda</B> L-param</TT><TT> </TT><TT>      (compteur 'inc)</TT><TT> </TT><TT>      (<B>apply</B> fonction L-param)))</TT></DIV><BR> <BR> Nous proposons pour ce faire :<BR> <BR> <DIV CLASS="lstlisting"><TT>(<B>define-macro</B> (compte compteur fonction)</TT><TT> </TT><TT>(set! ,fonction (compte-fonction ,compteur ,fonction)))


utilisé ainsi :

(compte compteur-fib fib)




3. Instrumentation de KMP



En Scheme :



On rappelle le texte Scheme de KMP, qu'ici on a également instrumenté pour compter le nombre d'itérations :



Voici le résultat de l'exécution de ce programme :

Motif : atatag Texte : atatattagggatttagtatatttatatatattataatatag Tableau : #(-1 0 0 1 2 3 0) Longueur du texte : 42 Compteur de boucle KMP : 56 36


En moyenne cet algorithme s'exécute en un temps moyen de qui croît comme O(n).


1
La forme define-macro n'est pas dans la norme et il existe d'autre syntaxes pour créer des macros. Celle-ci nous a semblé la plus simple et la plus élégante.

This document was translated from LATEX by HEVEA.