2. La modification du programme
Dans cette seconde partie, on s'intéresse à la modification du programme. La modification d'un programme se justifie pour deux raisons :
- soit le programme était faux : on corrige l'erreur ;
- soit le programme est correct, mais alors on veut le faire évoluer, pour accroître ses performances ou l'adapter à un nouveau « milieu », ou encore faire varier ses fonctionnalités.
La question qu'on doit se poser est de savoir si la modification préserve la sémantique du programme. Dans le premier cas, il est à souhaiter que la réponse soit non ; dans le second cas, on aimerait répondre par l'affirmative, et si possible d'une façon automatique. L'automatisation d'un tel contrôle est un problème résolument complexe, elle n'est pas supportée par l'outil qu'on propose. Dans la suite, on montre certaines difficultés qu'elle pose – sur la très simple fonction de calcul d'une racine carrée – en présentant deux outils qui pourraient en faciliter la résolution.
2.1. position du problème
La fonction précédemment construite est :
(de sqrt (num)
(prog (result)
(setq result 1)
LP (cond ((< (abs (- (* result result) num)) 0.001) (return result)))
(setq result (/ (+ result (/ num result)) 2))
(go LP)))
On aimerait éviter la redondance du calcul multiplicatif – multiplication ou division – dans le test et l'approximation de l'algorithme. Pour ce faire on effectue le regroupement en deux étapes.
(1) | remplacer (- (* result result) num)par (- result (/ num result)) |
(2) | regrouper les deux termes (/ num result)par l'utilisation d'une variable auxiliaire X |
2.2. la modification locale
R. Dybvig et B. Smith présentent dans [DyS 85] un « éditeur sémantique ». L'éditeur travaille sur une forme "lispienne" du langage FP défini par J. Backus [Bac 78] :
- il connaît la syntaxe FP – représentée par des fonctions Lisp ;
- il connaît un certain nombre de règles d'équivalence entre les termes de FP.
L'outil permet la saisie d'un terme de FP, puis sa transformation, via les règles d'équivalence orientées en règles de réécriture, à sémantique constante.
Une des originalités de l'approche est de gérer la relation d'équivalence que définissent ces règles : un programme conserve dans sa Représentation Interne les classes d'équivalence des termes qui le composent. On a donc deux interactions possibles sous l'éditeur :
- soit visualiser le programme : on voit la forme décompilée correspondant au « chemin sélectionné » dans le graphe de congruence ;
- soit modifier le chemin, par ajout d'un nouveau lien de congruence entre les termes ou par le choix d'un nouveau chemin du graphe construit.
Pour éclairer le propos, on a par exemple la règle d'équivalence :
(construct (compose f g) (compose f h))
≡ (apply-to-all f (construct g h))
(construct, apply-to-all, compose sont des opérateurs du langage FP).
Le programme est alors représenté par le graphe :
La flèche représente l'instanciation classique d'un nœud d'opérateur par un terme tel qu'on le trouve dans un arbre syntaxique.
Le pointillé symbolise la relation d'équivalence entre les termes.
Un « chemin sélectionné » sera par exemple le sous-graphe (orienté) :
|
|
qui est un programme sémantiquement équivalent au sous-graphe dans la "racine" est apply-to-all.
L'exemple
On veut remplacer le test :
(< (abs (- (* result result) num)) 0.001)
par le test :
(< (abs (- result (/ num result))) 0.001)
dont on "remarque" qu'il a une sémantique voisine.
En adoptant les notations mathématiques plus concises et en élargissant le problème, on veut remplacer :
|r1×r2-n| < ε
par le test :
|r2-n/r1| < ε
On transforme le premier terme (entre crochets on indique quelles règles d'équivalence on utilise) :
|r1×r2-n| < ε | | ||
|r1×((r1×r2)/r1-n/r1)| < ε | [ x-y ≡ z×(x/z-y/z) ] | ||
|r1×((r1/r1)×r2-n/r1)| < ε | [ (x×y)/z ≡ (x/z)×y ] | ||
|r1×(1×r2-n/r1)| < ε | [ x/x ≡ 1 ] | ||
|r1×(r2-n/r1)| < ε | [ 1×x ≡ x ] | ||
|r1|×|r2-n/r1| < ε | [ |x×y| ≡ |x|×|y| ] | ||
|r2-n/r1| < ε/|r1| | [ x×y<z ≡ y<z/x si x>0 ] |
On s'arrête ici, parce qu'on ne peut plus transformer le terme dans la direction qu'on suit. Or celui-ci est intuitivement équivalent à :
|r2-n/r1| < ε
En effet dans le cadre qui nous intéresse la majoration est « paramétrée » par un ε assez petit, donc si l'on suppose que |r1| est minoré alors majorer par ε/|r1| ou majorer par ε est à peu près équivalent. Il faudrait ici appliquer une règle de réécriture dépendante du problème (« problem dependant ») : dans l'absolu elle serait sémantiquement fausse, mais pour ce qui nous concerne elle serait presque vraie.
Le cas pose problème : si l'on s'impose des transformations à sémantique constante, on est arrêté à cette étape ; si l'on s'autorise des approximations, la relation de congruence sur les termes devient obsolète.
2.3. la modification globale
R. Walter présente un autre éditeur sémantique, « l'Apprenti du Programmeur » [Wat 82] [Wat 86]. Comme tout bon Apprenti, celui-ci se charge des « basses besognes » en laissant la « partie noble » du travail à la charge du Programmeur.
Le système fonctionne à plusieurs niveaux :
- L'interface utilisateur cherche à faciliter le travail de saisie du programmeur :
- les commandes sont entrées en pseudo-anglais,
- chaque commande retourne immédiatement en écho le texte du programme en Lisp.
- Pour la construction d'un algorithme, l'utilisateur invoque des schémas prédéfinis (« clichés ») ; pour les points de détail du programme il peut directement entrer du code Lisp.
- Le système quant à lui sa place en amont du programme Lisp : il travaille sur un graphe de flot de données (data-flow) et assure la correspondance entre ce graphe, les instructions de l'utilisateur et l'écho en langage Lisp.
Par nature, le système ne garantit aucune conservation de la sémantique du programme lors d'une transformation : l'Apprenti n'est pas là pour enseigner au Programmeur les bonnes règles de la programmation mais pour bénéficier de la connaissance experte de ce dernier. Sa tâche est plutôt de contrôler que le Programmeur n'introduit pas de contradictions notoires, et tout particulièrement pour ce qui concerne les variables :
- leur zone de visibilité (syntaxe) : il assure la déclaration des variables, ou encore sait reconnaître les variables libres d'une fonction (l'occurrence d'utilisation d'une variable globale) ;
- leurs zones de pertinence (sémantique) : il peut connaître les zones du programme où la variable a une valeur pertinente ou même constante.
L'exemple
Par une "transformation syntaxique", on a transformé le programme en :
(de sqrt (num)
(prog (result)
(setq result 1)
LP (cond ((< (abs (- result (/ num result))) 0.001) (return result)))
(setq result (/ (+ result (/ num result)) 2))
(go LP)))
A l'étape suivante, on regroupe les deux divisions (/ num result) par l'emploi d'une variable locale ; cette seule formulation d'« expression de besoin » par l'utilisateur fournit alors le programme :
(de sqrt (num)
(prog (result X)
(setq result 1)
LP (setq X (/ num result))
(cond ((< (abs (- result X)) 0.001) (return result)))
(setq result (/ (+ result X) 2))
(go LP)))
Que garantit le système ?
- il assure la déclaration de la variable locale
X– ce qu'on peut vérifier de visu grâce à l'écho rendu ; - il vérifie que les deux divisions de départ se calculent bien sur les mêmes données – et donc qu'on peut bien les regrouper ;
- il place l'affection de la variable auxiliaire
X"au bon endroit" – ici, à l'entrée de la boucle d'itération.
Les deux derniers points sont deux aspects intéressants du système. Ils sont le fait de la Représentation Interne du programme par un graphe de flot de données : on n'a pas la vue séquentielle habituelle d'un langage de programmation qui rend très ardue la réalisation des vérifications présentées. Une limitation sévère du système en est la conséquence : à chaque "bout de programme algorithmiquement significatif" doit être associé un graphe de flot de données ; si ce "bout" est dans la bibliothèque des objets prédéfinis on réutilise le graphe associé ; autrement il faut le définir, ce qui alourdit beaucoup l'étape de programmation.
2.4. le graphe de flot de données
En s'affranchissant de la question des déclarations de variable, on veut résoudre le problème suivant :
On part d'un « texte troué » sur lequel on a reconnu qu'à deux points distincts on élaborait le même calcul :
Les deux « trous » sont donc remplis par le même texte qui réalise le calcul.
On veut savoir si l'on peut remplacer ce texte par le suivant :
- On introduit une variable auxiliaire
X. - On affecte la valeur du calcul élaboré à cette variable.
- On effectue ensuite le traitement, et les élaborations du calcul sont remplacées par l'élaboration de la valeur de la variable
X.
Pour réaliser une telle transformation en toute quiétude il faut donc démontrer qu'à nul point du « texte troué » on n'affecte des objets susceptibles d'affecter l'élaboration du calcul : un problème non simple.
La représentation « textuelle » qu'on propose de sait pas répondre à la question. En revanche les graphes de flot de données semblent assez bien adaptés à la situation. L'exemple précédent se réalise par les considérations qui suivent.
La fonction sqrt, de paramètre num, n'affecte pas la valeur du paramètre : num est globalement constant dans le corps de la fonction.
 | : zone de valeur pertinente et constante de num |
val | : valeur du paramètre effectif à l'appel de sqrt |
res | : valeur résultat de l'appel de sqrt |
Le CORPS est construit avec le schéma prédéfini succ-approx :
| : zone de valeur pertinente et constante de result à l'initialisation ou à l'itération de la boucle |
 | : zone d'intersection |
Pour le regroupement des deux divisions, on observe les points suivants :
- elles sont syntaxiquement égales, préliminaire indispensable ;
- elles apparaissent dans les "boîtes" TST et APPROX ;
- elles utilisent les valeurs des variables num et result.
L'intersection des « zones de valeur pertinente et constante » des variables num et result fournit la nouvelle "boîte" :
qui contient justement les "boîtes" TST et APPROX.
Il suffit alors de placer l'affectation de X en tête de cette "boîte" :
| : zone de valeur pertinente et constante de X |
div | : la division |
(et on remplace TST et APPROX dans l'élaboration de la division par l'accès à la valeur de X).