debut.gif (172 octets) boutprec.gif (153 octets) boutsuiv.gif (154 octets)

5.1 Notion d'évaluation récursive

Revenons sur un exemple d'expression composée vu dans un chapitre précédent pour calculer (b2-4ac)/2a avec a=2, b=3 et c=5 :


 

(/             ;; 92 $[\mathcal{A}]$97
 (- (* 3 3)
    (* 4 2 5))
 (* 2 2))

Nous avons donné un modèle de la procédure suivie par l'interprète pour évaluer cette expression, le modèle d'évaluation par substitution. Ce modèle est le suivant :

 

 

 

Remarquons que dans ce modèle la règle d'évaluation d'une expression comporte l'invocation de la règle d'évaluation, c'est à dire d'elle-même. La règle d'évaluation est dite récursive.

Notons qu'une telle description récursive est assez commode : si nous devions donner une description non récursive de l'expression $[\mathcal{A}]$, elle serait plus verbeuse, moins générale, moins élégante, en un mot moins puissante. Le prix à payer pour cette élégance est qu'une procédure ainsi définie risque de ne jamais se terminer, ce qui, le premier chapitre nous l'a appris, est la marque d'un programme faux. L'assurance de la terminaison de l'évaluation, on le sent bien, a à voir avec la syntaxe, notamment le bon équilibre des parenthèses imbriquées, mais aussi avec la sémantique des objets invoqués. L'art de l'évaluation, et donc de la programmation, réside pour une bonne part dans la réduction d'expressions à la sémantique compliquée en expressions plus simples dont la seule syntaxe nous garantisse la correction, parce que la vérification de la syntaxe est une tâche plus à la portée d'un programme d'ordinateur que la vérification de la sémantique.

L'expression $[\mathcal{A}]$ page [*] semble bien près de nous offrir cette garantie, à ceci près que les opérations arithmétiques soient numériquement calculables : pas de division par zéro ni de résultat intermédiaire excédant la capacité des nombres de notre ordinateur.

Juste parce que c'est une représentation bien adaptée aux structures récursives, ainsi qu'aux structures syntaxiques (spécialement quand elles sont parenthésées), nous pouvons représenter l'expression $[\mathcal{A}]$ sous la forme d'un arbre :

 

 

Figure: Arbre d'évaluation
\includegraphics{../Images/Processus/arbre-eval.epsi}59

 

Cette représentation place aux feuilles les plus profondes de l'arbre les opérateurs et les opérandes des sous-expressions les plus intérieures (celles dont la parenthèse ouvrante est la plus à droite dans une écriture indentée du programme). Les résultats des évaluations intermédiaires s'accumulent aux n\oeuds, comme si les valeurs des opérandes placés aux feuilles « remontaient » le long des branches de l'arbre au fur et à mesure du calcul. La valeur du résultat apparaît finalement à la racine.

La représentation arborescente présente une vision suggestive de l'application récursive de la règle a] et de sa terminaison lorsque l'on arrive aux feuilles, où se trouvent des expressions primitives dont nous savons trouver les valeurs grâce à l'environnement ou parce qu'elles sont auto-évaluantes.

Nous avons dit que la valeur d'un opérateur était une procédure, susceptible d'être retrouvée dans l'environnement par une liaison : il s'agit d'une valeur un peu particulière, mais nous verrons qu'en Scheme cette façon de parler est tout à fait justifiée. Les procédures y sont des objets de même nature que les autres. C'est une qualité de ce langage et une bonne raison de l'utiliser.

 


5.2 Variables libres ou liées, variables globales

Supposons que pour fabriquer avec une machine pilotée par ordinateur un jeu de construction à l'usage de petits enfants nous soyons amenés à entreprendre de nombreux calculs concernant des formes géométriques telles que des cercles, des sphères, des cylindres et des cônes. Il ne serait pas déraisonnable de rédiger une bonne fois des procédures pour calculer les surfaces, les volumes et les circonférences de ces figures, ainsi que les carrés et les cubes, et de définir symboliquement la constante $\pi$ dont nous savons que nous allons avoir souvent besoin.

 

1:=> (define pi 3.14159)

1:=> (define (carre x) (* x x))

1:=> (define (surface-cercle rayon) ;; 92 $[\mathcal{B}]$97
        (* pi (carre rayon)))
1:=> (surface-cercle 4)             ;; 92 $[\mathcal{C}]$97
50.2654400000

Lorsqu'il est invoqué au Top-level (en réponse à l'invite de l'interprète lorsqu'on utilise un interprète, ou, de façon plus générale, dans une parenthèse incluse dans aucune autre parenthèse), ce qui est la façon normale de l'invoquer, define crée dans l'environnement global des objets qui sont connus en tout point du programme5.1.

La ligne $[\mathcal{B}]$ crée une procédure surface-cercle avec un paramètre, rayon. Le paramètre rayon est inéluctablement voué à n'être que le fantôme formel de l'argument qui sera soumis à surface-cercle lorsque nous l'appellerons. Même si nous définissons dans l'environnement global un objet qui s'appelle rayon, surface-cercle n'en tiendra aucun compte :

 

1:=> (define rayon 2)

1:=> (define l-argument-rayon 1)

1:=> (surface-cercle l-argument-rayon)
3.14159000000

On voit que surface-cercle a cruellement négligé la variable nommée rayon pour associer à son paramètre nommé rayon l'argument à elle soumis, le bien nommé l-argument-rayon. On dit que l'objet rayon qui apparaît comme paramètre dans la définition de la procédure est une variable liée dans surface-cercle.

Ceci suggère que ce qui existe à l'extérieur de la procédure ne peut avoir aucune influence sur la valeur liée au paramètre, sauf par l'intermédiaire du mécanisme de passage d'argument. Ceci suggère aussi que ce qui est défini de façon interne à une procédure est créé dans un environnement privé, propre à la procédure : en effet, clairement, le symbole rayon ne désigne pas la même chose à l'intérieur et à l'extérieur de surface-cercle. Tout ceci sera précisé ultérieurement.

Qu'en est-il au contraire de la variable pi ? Nous aurions pu la définir comme un paramètre de chaque procédure de calcul de nos surfaces, volumes et autres circonférences, ce qui nous aurait amenés à la passer en argument à chaque appel. Comme nous savons que nous en aurons souvent besoin et qu'elle ne change pas souvent de valeur, nous l'avons définie au Top-level. Mais alors :

 

1:=> (define pi 3.14159)

1:=> (surface-cercle l-argument-rayon)
3.14159000000


1:=> (define pi 3.14)
*** WARNING:bigloo:eval
redefinition of variable - PI
PI

1:=> (surface-cercle l-argument-rayon)
3.14000000000

Nous constatons que si nous redéfinissons pi au Top-level nous affectons le comportement de surface-cercle, qui dépend de la valeur de pi dans l'environnement global. Nous dirons que pi est une variable libre dans surface-cercle.

On peut considérer la liberté de la variable pi dans notre procédure surface-cercle comme une circonstance très agréable, de nature à introduire un peu d'imprévu dans nos calculs. Mais les programmeurs ont plus souvent tendance à se méfier des variables libres, parce qu'il suffit qu'un autre passage du programme les redéfinisse pour que le comportement de la procédure concernée devienne difficile à prévoir. Les variables libres peuvent aussi se laisser capturer à l'insu du chasseur, un peu comme on attrape un virus, et modifier le comportement d'un programme.

Une variable définie au Top-level comme pi est aussi caractérisée comme une variable globale, ce qui signifie qu'elle est visible de tout le programme. Les variables globales peuvent être très utiles mais doivent être utilisées avec parcimonie et prudence. Les bons usages de Scheme conseillent de leur donner des noms commençant et finissant par des * : *pi*, ou mieux *PI*, pour éviter qu'elles ne passent inaperçues.

Rappelons que, par opposition aux variables globales, les variables locales sont par exemple celles définies par un let.

Les variables libres dans une procédure que nous pouvons imaginer sont des variables globales. De même, si nous avons deux blocs let imbriqués, les variables du bloc englobant qui n'ont pas d'homonymes dans le bloc englobé sont libres dans le bloc englobé et peuvent donc y être capturées par une expression.

 

5.3 Construction de procédures

 


5.3.1 Définition de procédure récursive

Nous disposons maintenant de l'outillage minimum qui nous permet de construire de vrais programmes. Le premier exemple que nous en exposerons (pas particulièrement original mais bien adapté à l'explication, et de ce fait devenu rituel) est celui du calcul de la fonction factorielle. Rappelons la définition de cette fonction :

n étant un entier naturel, on note n ! (que l'on énonce « factorielle n »), l'entier naturel défini par :

$0\,! = 1$ 92 $[\mathcal{D}]$97

et pour $n \ge 1$ :

$n\,! = (n-1) \,! \cdot n$

Donc pour $n \ge 1$ : $n\,! = 1 \cdot 2 \cdot 3 \ldots n$. 92 $[\mathcal{E}]$97

Nous pouvons écrire le programme qui calcule cette fonction en recopiant naïvement la définition $[\mathcal{D}]$ dans la syntaxe de Scheme :

 

1:=> (define (fact n)              ;; 92 $[\mathcal{F}]$97
       (if (zero? n)              ;; 92 $[\mathcal{G}]$97
            1                      ;; 92 $[\mathcal{H}]$97
           (* n (fact (- n 1))))) ;; 92 $[\mathcal{I}]$97

1:=> (fact 0)
1
1:=> (fact 1)
1
1:=> (fact 2)
2
1:=> (fact 5)
120
1:=> (fact 6)
720

La procédure définie en $[\mathcal{F}]$ est une procédure récursive, parce qu'elle s'appelle elle-même. L'endroit où elle commet ceci, en $[\mathcal{I}]$, se nomme « l'appel récursif », parce que cette expression comporte l'appel de fact.

Les définitions mathématiques par récurrence, telles qu'en $[\mathcal{D}]$, ne nous choquent pas, parce qu'il s'agit uniquement d'idées, mais la notion d'une procédure effective récursive peut sembler hasardeuse. Elle engendre en effet la crainte d'une récursion infinie : on pense à la boîte de « Vache qui rit » sur l'étiquette de laquelle figure une boîte de « Vache qui rit » sur l'étiquette de laquelle figure une boîte de « Vache qui rit » sur l'étiquette de laquelle...  etc.

Si ce programme est juste (se termine), c'est pour les raisons suivantes :

 

Le cas où la condition de fin de récursion est vraie est appelé cas de base de la récursion.

Retenons une bonne règle pour écrire une fonction récursive : il faut commencer par tester si l'on a atteint le cas de base de la récursion, et le plus souvent il correspond à la nullité de la variable sur laquelle se fait la récursion si c'est un nombre, à la liste vide si c'est une liste, à la chaîne nulle si c'est une chaîne.

 


5.3.2 Mécanisme effectif de la récursion

Reprenons l'exemple du paragraphe 5.3.1 pour « faire tourner le programme à la main », une expression imagée pour signifier que notre cerveau va jouer le rôle du processeur et le papier celui de la mémoire. Nous voulons calculer 6 ! et nous appliquons le modèle d'évaluation par substitution que nous avons exposé en 2.5.2 :

 

(fact 6)                      ;; 92 $[\mathcal{J}]$97
(* 6 (fact 5))
(* 6 (* 5 (fact 4)))
(* 6 (* 5 (* 4 (fact 3))))
(* 6 (* 5 (* 4 (* 3 (fact 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (fact 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (fact 0)))))))
(* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

L'examen de cette « trace d'exécution » montre les appels récursifs successifs, la réalisation de la condition de terminaison et le fait qu'après avoir atteint cette condition les calculs qui restent à faire ne mettent en jeu que des expressions primitives.

 


5.3.3 Procédures itératives

 

5.3.3.1 Une autre façon de calculer une factorielle

Plutôt que de partir de la définition de la fonction factorielle, nous aurions pu écrire notre programme en nous inspirant de l'illustration qui en est donnée en $[\mathcal{E}]$ et en décrivant en Scheme nos actions successives. C'est à dire qu'il faut multiplier les uns aux autres les entiers successifs et s'arrêter lorsqu'on arrive à n. Il faut pour cela garder à la mémoire la valeur de n lors de la multiplication précédente, ce qui sera fait grâce à une variable compteur, et le résultat de la multiplication précédente, ce qui sera fait par une variable produit. Ces opérations de mécanique calculatoire seront réalisées par une procédure auxiliaire fact-aux, appelée par la procédure principale fact. 


(define (fact-aux produit compteur n)     ;æomarqueur£Kߣß
   (if (> compteur n)
       produit
       (fact-aux (* compteur produit)     ;æomarqueur£Lߣß
                 (+ compteur 1)
                 n)))

(define (fact n)
   (fact-aux 1 1 n))

Cette rédaction est nettement plus laborieuse et moins élégante que $[\mathcal{G}]$. Nous allons voir qu'elle présente néanmoins beaucoup d'intérêt.

La procédure principale fact ne fait presque rien : elle appelle fact-aux avec les valeurs initiales des variables du calcul et retourne le résultat5.2 retourné par fact-aux.

fact-aux est une procédure récursive, avec un appel récursif à la ligne $[\mathcal{L}]$. Chaque appel récursif fait croître de 1 le second argument (compteur) qui est celui sur lequel est effectué le test de fin de récursion, nous sommes donc assurés de la terminaison de ce programme.

 

5.3.3.2 Procédure itérative et style impératif

Bien que répondant à la définition formelle de procédure récursive, fact-aux correspond à un autre modèle de calcul que la procédure fact définie en $[\mathcal{F}]$ § 5.3.1. Le calcul procède ici en modifiant l'état des variables produit et compteur à chaque passage d'une étape à l'autre selon la règle suivante :

 

Le procédé qui consiste à définir ainsi explicitement les changements d'état de l'environnement (de la mémoire) à chaque étape du processus caractérise les processus dits itératifs. Le style de programmation qui emploie des processus itératifs est le style impératif.

Par contre, la procédure fact définie en $[\mathcal{F}]$ repose entièrement sur le mécanisme de l'appel récursif pour assurer l'enchaînement des opérations du calcul. Elle décrit un processus récursif « vrai » (au sens de « irréductible à un processus itératif »), associé au style de programmation fonctionnel.

Analysons l'exécution du programme défini en $[\mathcal{K}]$ comme nous l'avons fait pour le précédent :

 

(fact 6)                     ;; 92 $[\mathcal{JK}]$97
(fact-aux 1 1 6)
(fact-aux 1 2 6)
(fact-aux 2 3 6)
(fact-aux 6 4 6)
(fact-aux 24 5 6)
(fact-aux 120 6 6)
(fact-aux 720 7 6)
720

La comparaison des traces d'exécution $[\mathcal{J}]$ et $[\mathcal{JK}]$ met en lumière les comportements nettement différents des deux programmes, ce que nous allons étudier au paragraphe suivant.

 


5.3.3.3 Comparaison des processus récursifs et itératifs

Pour le premier programme ($[\mathcal{J}]$) :

 

Tant que le programme n'a pas atteint le cas de base, il « empile » les multiplications inachevées en gardant leurs opérandes successifs en mémoire. Cette conservation en mémoire est illustrée par la succession de parenthèses imbriquées de notre trace.

Remarquons que le nombre de lignes de la trace d'exécution correspond au nombre d'appels de procédure, donc grosso modo au temps de calcul nécessaire à l'obtention du résultat. La longueur de chaque ligne correspond au nombre de parenthèses imbriquées, soit au nombre de multiplications inachevées en attente dont on garde les opérandes en mémoire « en attendant », donc grosso modo à l'encombrement causé par notre programme dans la mémoire de l'ordinateur.

On imagine que le calcul de n ! avec n un peu grand pourrait excéder la capacité de notre page vers la droite. C'est exactement ce qui va se passer avec un ordinateur réel : le programme $[\mathcal{F}]$ dont la trace se trouve en $[\mathcal{J}]$, si nous lui soumettons de trop grandes valeurs de n, va rencontrer une limite technique du côté de la taille mémoire.

Pour le second programme ( $[\mathcal{JK}]$) :

 

Cette procédure est récursive par sa forme syntaxique ; lors de son exécution il n'y a rien à garder d'un appel à l'autre en dehors de variables explicitement passées en argument ; elle décrit en fait un processus itératif.

Une procédure dont l'appel récursif ne laisse aucun calcul en suspens est dite « procédure récursive terminale ». Nous avons vu que c'était une qualité souhaitable. Comment reconnaît-on qu'un appel de procédure récursif est terminal ? À ce que dans l'expression qui réalise l'appel récursif le nom de la procédure appelée ne figure pas en argument d'un appel à une autre procédure5.3.

Ainsi, l'appel récursif défini en $[\mathcal{I}]$ n'est pas terminal parce qu'il est l'argument d'un appel à la procédure de multiplication. Celui défini en $[\mathcal{L}]$ est terminal (rappelons que if n'est pas une procédure mais une forme spéciale). Les interprètes et compilateurs Scheme sont conçus pour traiter efficacement les appels récursifs terminaux comme des processus itératifs.

 

5.3.3.4 Morale de la comparaison

Pour résumer les impressions retirées de cette comparaison : la procédure $[\mathcal{F}]$ qui réalise un processus récursif est élégante, concise, proche de la définition formelle de la fonction souhaitée. Mais les conditions de réalisation du processus laissent craindre une certaine inefficacité qui conduira à en rendre l'usage impossible.

La procédure $[\mathcal{K}]$ qui réalise un processus itératif est plus rébarbative, elle nous oblige à donner plus de détails techniques dans la spécification. Mais elle sera plus efficace dans l'utilisation pratique.

En bref, les processus récursifs sont plus agréables pour les êtres humains et les processus itératifs pour les ordinateurs. Le rêve serait d'écrire des procédures récursives et de disposer de domestiques qui les transformeraient ensuite en procédures itératives équivalentes. Le mieux serait que la transformation en question soit définie par une procédure effective, ce qui permettrait de la faire réaliser par un programme d'ordinateur : ce n'est pas toujours possible.

 

5.4 Traitement des erreurs, notion d'exception

 

5.4.1 Les erreurs existent

Il y a bien sûr des erreurs de programmation, mais un programme peut aussi se terminer anormalement ou ne pas se terminer du fait de l'environnement (au sens large) et notamment des données qui lui sont soumises. Un programme peut aussi échouer par défaut des ressources nécessaires à son exécution (mémoire, place sur disque). En toute rigueur la détermination des ressources nécessaires à l'exécution relève de la sémantique du programme, et donc de la responsabilité du programmeur. Pensons aux programmes embarqués à bord d'astronefs.

La qualité d'un programme dépend énormément du traitement qu'il réserve aux cas d'erreurs, notamment du fait de données inappropriées au traitement prévu. Les programmes donnés ici comme exemples sont souvent dépourvus de traitement d'erreur pour atteindre la concision indispensable à la clarté de l'exposé, mais ceux que vous écrirez pour traiter des problèmes réels (surtout s'ils doivent être utilisés par d'autres que vous-même) devront se prémunir contre les divisions par zéro, l'extraction de racines carrées réelles de nombres négatifs, les opérations numériques sur des chaînes de caractères, et tous autres cas d'erreurs susceptibles d'être introduits par des données venant de l'intérieur ou de l'extérieur du programme et qui n'appartiendraient pas au bon domaine. Ainsi, le programme 2.11 se termine en erreur si nous lui fournissons un nombre négatif.

Une autre cause d'erreur à prévoir procède des demandes de ressources au système d'exploitation. Lorsque notre programme veut lire des données sur un support externe, il suppose que le système d'exploitation est en mesure de le faire pour lui. Si pour une raison ou une autre ce n'est pas le cas (fichier inexistant par exemple), le système d'exploitation provoquera une erreur qu'il vaudra mieux être capable de récupérer.

Récupérer une erreur, ce n'est pas forcément la corriger, mais terminer le programme dans une situation aussi bien caractérisée que possible, en donnant des informations utiles sur sa cause probable.

Le moyen le plus rudimentaire de traiter les erreurs consiste à tester tous les cas prévisibles de données inadéquates et de résultats pathologiques. Les langages modernes comme Ada ou Java proposent un mécanisme de plus haut niveau pour le traitement des erreurs, les exceptions. Ceci n'existe pas en standard dans Scheme, mais Bigloo propose une solution apparentée à celle de Java ou de C++.

 

5.4.2 Exceptions

Une exception indique un état inhabituel ou une erreur. Lorsque le système de programmation détecte qu'une exception est survenue, le contrôle du programme est transféré à une procédure particulière, le traitant de l'exception (handler en anglais). À la charge du programmeur d'écrire le traitant.  Ainsi, dans le texte du programme, le code destiné à la gestion d'erreur est clairement isolé du reste.

Il faut aussi fournir au programmeur la possibilité de décider lui-même que telle situation est une erreur, et de lever une exception.

Bigloo procure ces fonctions avec la procédure error et la forme syntaxique try.

 

5.4.2.1 error

(error proc msg obj)

Cette procédure lève une exception (ce qui signifie que le programmeur décide que la situation est erronée, qu'il faut déclencher une erreur) et appelle le traitant courant en lui passant les arguments proc, msg et obj auxquels le programmeur aura donné les valeurs appropriées (en principe le nom de la procédure, un message explicatif et la valeur de l'objet concerné, voir le programme 5.4.2.2 pour un exemple).

La première chose à faire pour traiter convenablement les cas d'erreur dans un programme c'est d'introduire la procédure error aux endroits critiques, où risquent de survenir les erreurs, comme ici : 


(define (sqrt x)
   (cond
      ((fixnum? x)
       (sqrtfl (fixnum->flonum x)))
      ((flonum? x)
       (sqrtfl x))
      (else
       (error "sqrt" "not a number" x))))

 

5.4.2.2 try

Ensuite, lorsque nous voulons effectuer le calcul qui risque de provoquer l'erreur, au lieu d'écrire directement l'expression exp qui exprime le calcul, ce qui serait présomptueux, nous l'emballerons dans la forme spéciale try, qui dit bien ce qu'elle veut dire et exprime notre humilité :

(try exp traitant)

 

1.
exp est l'expression qui risque de provoquer l'erreur ;
2.
traitant le nom du traitant.

Le traitant doit être une procédure qui reçoit quatre arguments :

 

1.
le nom de la continuation de l'expression passée à try, qui est une expression de la forme :

(k E)

où k est un identifiant (le nom de la continuation) et E une expression à évaluer après l'expression passée à try ;

2.
proc tel qu'émis par error (en général le nom de la procédure à la source de l'erreur) ;
3.
msg tel qu'émis par error (le message d'erreur du système) ;
4.
obj tel qu'émis par error (la valeur de l'objet incriminé).

Voir par exemple le programme 5.4.2.2 :

Une exception et son traitant

(define (traitant echappe proc mess obj)
  (print "***ERROR: " proc ": "
         mess " -- " obj)
  (echappe #f))

(define (racine)
  (print "Entrez le nombre dont vous voulez calculer")
  (display "la racine carrée (ou 0 pour finir) : ")
  (let ((n (read)))
    (if (zero? n)
        (display "Au revoir")
        (begin
          (print "La racine carrée de " n " est "
                 (try (sqrt n) traitant))
          (racine)))))

74

Ici error sera émis par sqrt. Cela donnera à l'exécution la trace 5.4.2.2.

À l'exécution :

1:=> (racine)
Entrez le nombre dont vous voulez calculer
la racine carrée (ou 0 pour finir) : 7
La racine carrée de 7 est 2.64575131106
Entrez le nombre dont vous voulez calculer
la racine carrée (ou 0 pour finir) : -9
***ERROR: sqrt: Domain error -- -9.00000000000
La racine carrée de -9 est #f
Entrez le nombre dont vous voulez calculer
la racine carrée (ou 0 pour finir) : 0
Au revoir#unspecified

74

À titre d'illustration et pour élucider, on donne la procédure sqrtfl de Bigloo (programme 5.4.2.2).

sqrtfl de Bigloo

(define-inline (sqrtfl r)
   (if (<fl r 0.0)
       (error "sqrt" "Domain error" r)
       (c-sqrt r)))

74

L'usage des exceptions est une pratique recommandée du génie logiciel.

 

debut.gif (172 octets) boutprec.gif (153 octets) boutsuiv.gif (154 octets)
Laurent Bloch bloch@pasteur.fr
1999-03-15