“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 120 — #130
i
i
i
i
i
i
i
i
120
3
• Techniques de programmation déclarative
Nous avons vu qu’un calcul itératif a une taille de pile constante à cause de l’optimisation terminale. Ce n’est pas toujours le cas pour un calcul récursif. La taille de
sa pile peut grandir quand l’entrée grandit. Parfois c’est inévitable, par exemple en
faisant des calculs avec des arbres, comme nous le verrons plus loin. En d’autres cas,
on peut l’éviter. Un aspect important de la programmation déclarative est d’éviter une
pile grandissante quand c’est possible. Cette section donne un exemple qui montre
comment on peut faire. Nous prenons un cas typique d’un calcul récursif qui n’est pas
itératif, la définition naïve de la fonction factorielle. La définition mathématique est :
0! = 1
n! = n · (n − 1)! if n > 0
C’est une équation de récurrence. La factorielle n! est définie par rapport à une
factorielle avec un argument plus petit, (n −1)!. Le programme naïf suit cette définition
mathématique. Pour calculer {Fact N} il y a deux possibilités, N=0 ou N>0. Dans le
premier cas, il renvoie 1. Dans le deuxième cas, il calcule {Fact N-1}, le multiplie
par N et renvoie le résultat. Voici le programme :
fun {Fact N}
if N==0 then 1
elseif N>0 then N * {Fact N-1}
else raise domainError end end
end
Ce programme définit la factorielle d’un grand nombre en utilisant la factorielle d’un
nombre plus petit. Puisque tous les nombres sont non négatifs, tôt ou tard on s’arrêtera
à zéro et l’exécution se terminera.
Remarquez que la factorielle est une fonctionne partielle sur les entiers. Elle n’est
pas définie pour N négatif. Le programme indique cela en levant une exception pour N
négatif. La définition du chapitre 1 a une erreur puisque pour N négatif elle fait une
boucle infinie.
Nous avons fait deux choses pour écrire Fact. D’abord, nous avons suivi la définition mathématique pour obtenir une définition correcte. Ensuite, nous avons raisonné
sur la terminaison. Nous avons montré que le programme se termine pour tous arguments légaux, dans le domaine de la fonction.
3.3.1 La taille grandissante de la pile
Cette définition de la factorielle définit un calcul dont la taille maximale de la pile est
proportionnelle à l’argument N. Nous pouvons le vérifier avec la sémantique. D’abord,
traduisons Fact en langage noyau :
i
i
i
i
i
i
i
i
120
3
• Techniques de programmation déclarative
Nous avons vu qu’un calcul itératif a une taille de pile constante à cause de l’optimisation terminale. Ce n’est pas toujours le cas pour un calcul récursif. La taille de
sa pile peut grandir quand l’entrée grandit. Parfois c’est inévitable, par exemple en
faisant des calculs avec des arbres, comme nous le verrons plus loin. En d’autres cas,
on peut l’éviter. Un aspect important de la programmation déclarative est d’éviter une
pile grandissante quand c’est possible. Cette section donne un exemple qui montre
comment on peut faire. Nous prenons un cas typique d’un calcul récursif qui n’est pas
itératif, la définition naïve de la fonction factorielle. La définition mathématique est :
0! = 1
n! = n · (n − 1)! if n > 0
C’est une équation de récurrence. La factorielle n! est définie par rapport à une
factorielle avec un argument plus petit, (n −1)!. Le programme naïf suit cette définition
mathématique. Pour calculer {Fact N} il y a deux possibilités, N=0 ou N>0. Dans le
premier cas, il renvoie 1. Dans le deuxième cas, il calcule {Fact N-1}, le multiplie
par N et renvoie le résultat. Voici le programme :
fun {Fact N}
if N==0 then 1
elseif N>0 then N * {Fact N-1}
else raise domainError end end
end
Ce programme définit la factorielle d’un grand nombre en utilisant la factorielle d’un
nombre plus petit. Puisque tous les nombres sont non négatifs, tôt ou tard on s’arrêtera
à zéro et l’exécution se terminera.
Remarquez que la factorielle est une fonctionne partielle sur les entiers. Elle n’est
pas définie pour N négatif. Le programme indique cela en levant une exception pour N
négatif. La définition du chapitre 1 a une erreur puisque pour N négatif elle fait une
boucle infinie.
Nous avons fait deux choses pour écrire Fact. D’abord, nous avons suivi la définition mathématique pour obtenir une définition correcte. Ensuite, nous avons raisonné
sur la terminaison. Nous avons montré que le programme se termine pour tous arguments légaux, dans le domaine de la fonction.
3.3.1 La taille grandissante de la pile
Cette définition de la factorielle définit un calcul dont la taille maximale de la pile est
proportionnelle à l’argument N. Nous pouvons le vérifier avec la sémantique. D’abord,
traduisons Fact en langage noyau :