La racine carrée

L'exemple peut être vu selon deux jours :

• on construit progressivement le programme, en utilisant des unités prédéfinies de bibliothèque ;
• on modifie le programme construit : la question est de savoir si la sémantique est conservée après les modifications.

1. Construction progressive

2. La modification du programme

1. Construction progressive

Le langage cible est le langage Lisp.

On veut définir la fonction sqrt qui calcule la racine carrée d'un entier par la méthode classique : on construit une suite (a_n) telle que :
a_n+1 = 1/2 ( a_n + N/a_n )
(qui calcule la racine carrée de N).

On utilise d'abord le schéma des fonctions Lisp, le texte programme :

(def programme ()
   ("(de {NOM} ({PARAM})
        {CORPS})"))

Pour construire son programme, on définit donc un nouveau texte, PGME, qui utilise le schéma prédéfini de déclaration d'une fonction programme. On donne dans la suite pour les premières étapes de construction les deux formes :
- textuelle : les textes qu'on définit ;
- visuelle : ce qu'on voit (à l'écran).

La construction

(def PGME
   ()
   ("{programme}"))

(de {NOM} ({PARAM})
   {CORPS})

(def PGME
   ((def NOM () ("sqrt"))
    (def PARAM () ("num")))
   ("{programme}"))

(de sqrt (num)
   {CORPS})

(def PGME
   ((def NOM () ("sqrt"))
    (def PARAM () ("num"))
    (def CORPS
       ()
       ("{succ-approx}")))
   ("{programme}"))

(de sqrt (num)
   (prog (result)
         (setq result {INITIALISATION})
      LP (cond ({TEST} (return result)))
         (setq result {APPROXIMATION})
         (go LP)))

On développe ensuite dans le corps chaque paramètre :

(1) INITIALISATION : égale 1

(2) TEST : on utilise « l'égalité à epsilon près » :

(def egal-epsilon ()
   ("(< (abs (- {ARG1} {ARG2})) {EPSILON})"))

On construit donc le texte :

(def TEST
   ((def ARG1 () ("(* result result)"))
    (def ARG2 () ("num"))
    (def EPSILON () ("0.001")))
   ("{egal-epsilon}"))

qui donne :

(< (abs (- (* result result) num)) 0.001)

(3) APPROXIMATION : on utilise le schéma de la moyenne :

(def moyenne ()
   ("(/ (+ {ARG1} {ARG2}) 2)"))

On construit alors :

(def APPROXIMATION
   ((def ARG1 () ("result"))
    (def ARG2 () ("(/ num result)")))
   ("{moyenne}"))

qui donne :

(/ (+ result (/ num result)) 2)

On donne à la fin du paragraphe une vue synthétique de la bibliothèque des unités prédéfinies et du programme construit.

Conclusion

La construction progressive présente deux avantages :

Dans une démarche descendante, elle facilite l'écriture du programme. L'utilisateur en effet n'a pas à « réinventer la science » chaque fois qu'il écrit un programme : il réutilise un élément prédéfini de la bibliothèque. On gagne donc sur le plan de l'effort de développement demandé au programmeur ; on gagne surtout en fiabilité du programme – les éléments prédéfinis peuvent avoir été dûment validés, alors que le programme construit ne le sera vraisemblablement pas. Par exemple, si l'on regarde le texte succ-approx d'approximation successive :

• la définition des paramètres permet d'isoler les éléments dont on se servira pour prouver la terminaison de la boucle ;
• plus modestement le schéma aide le programmeur ; sans ce schéma il aurait pu oublier par exemple d'initialiser la variable de boucle ; avec le texte prédéfini qui lui est rendu, il est nécessairement porté à s'interroger sur la valeur à donner à l'initialisation.

Dans une démarche ascendante, elle facilite la relecture du programme. Si l'on s'éloigne de la « situation idéale » présentée précédemment où tous les besoins exprimés sont satisfaits dans la bibliothèque, on peut néanmoins offrir à l'utilisateur la possibilité de se replacer dans cette situation. Il s'agira alors pour lui :

• d'écrire son programme,
• puis de définir les "bouts de programme" qu'il reconnaît comme formant des "bouts d'algorithme" qui gagnent à être identifiés.

Si l'utilisateur est placé dans un "environnement nu" – sans bibliothèque prédéfinie – son programme n'est alors pas « le fichier de texte fic.ll » qui contient la totalité de l'information mais une collection structurée de « textes » qu'il utilise simultanément. L'intérêt d'une telle approche est de permettre à l'utilisateur d'écrire son programme (il n'est pas arrêté dans l'affinage du programme parce que telle unité serait introuvable dans la bibliothèque) tout en lui donnant le moyen d'exprimer, dans le texte source, sa démarche de conception d'une solution.

La bibliothèque

(def programme ()
   ("(de {NOM} ({PARAM})
        {CORPS})"))

(def succ-aprox ()
   ("(prog (result)
           (setq result {INITIALISATION})
        LP (cond ({TEST} (return result)))
           (setq result {APPROXIMATION})
           (go LP)))"))

(def egal-epsilon ()
   ("(< (abs (- {ARG1} {ARG2})) {EPSILON})"))

(def moyenne ()
   ("(/ (+ {ARG1} {ARG2}) 2)"))

La forme « textuelle » du programme

(def PGME
   ((def NOM () ("sqrt"))
    (def PARAM () ("num"))
    (def CORPS
       ((def INITIALISATION () ("1"))
        (def TEST
           ((def ARG1 () ("(* result result)"))
            (def ARG2 () ("num"))
            (def EPSILON () ("0.001")))
           ("{egal-epsilon}"))
        (def APPROXIMATION
           ((def ARG1 () ("result"))
            (def ARG2 () ("(/ num result)")))
           ("{moyenne}")))
       ("{succ-approx}")))
   ("{programme}"))

La forme « visuelle » du programme

(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)))