“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 74 — #84
i
i
i
i
i
i
i
i
74
2
• La programmation déclarative
L’appel {Loop10 0} affiche les entiers successifs de 0 jusqu’à 9. Voici l’exécution
de cet appel.
– L’état initial est :
( [({Loop10 0}, E 0 )],
s )
où E 0 est l’environnement à l’appel et s la mémoire initiale.
– Après l’exécution de l’instruction if, l’état devient :
( [({Browse I}, {I → i 0 }) ({Loop10 I+1}, {I → i 0 })],
{i 0 = 0} ∪ s )
– Après l’exécution du Browse, nous arrivons au premier appel récursif :
( [({Loop10 I+1}, {I → i 0 })],
{i 0 = 0} ∪ s )
– Après l’exécution de l’instruction if dans l’appel récursif, nous avons :
( [({Browse I}, {I → i 1 }) ({Loop10 I+1}, {I → i 1 })],
{i 0 = 0, i 1 = 1} ∪ s )
– Après l’exécution du Browse à nouveau, nous arrivons au deuxième appel
récursif :
( [({Loop10 I+1}, {I → i 1 })],
{i 0 = 0, i 1 = 1} ∪ s )
Il est clair que la pile au k-ième appel récursif a toujours la forme :
[({Loop10 I+1}, {I → i k−1 })]
Il n’y a qu’une instruction sémantique et son environnement a une taille constante. Cela
s’appelle l’optimisation terminale. La manière efficace de programmer une boucle dans
le modèle déclaratif est de la programmer comme une procédure récursive-terminale.
Nous pouvons aussi voir que les tailles de la pile sémantique et la mémoire ont des
évolutions différentes. La pile sémantique est bornée par une taille constante. Mais la
mémoire grandit à chaque appel. Au k-ième appel récursif, la mémoire a le contenu :
{i 0 = 0, i 1 = 1, . . . , i k−1 = k − 1} ∪ s
La taille de la mémoire est proportionnelle au nombre d’appels récursifs. Nous verrons
que cette croissance n’est pas un problème en pratique. Regardez bien la pile sémantique du k-ième appel récursif. Elle n’a pas besoin des variables {i 0 , i 1 , . . . , i k−2 }. La
seule variable dont elle a besoin est i k−1 . Nous pouvons donc enlever de la mémoire
les variables dont nous n’avons pas besoin sans changer les résultats du calcul. La
mémoire devient alors plus petite :
i
i
i
i
i
i
i
i
74
2
• La programmation déclarative
L’appel {Loop10 0} affiche les entiers successifs de 0 jusqu’à 9. Voici l’exécution
de cet appel.
– L’état initial est :
( [({Loop10 0}, E 0 )],
s )
où E 0 est l’environnement à l’appel et s la mémoire initiale.
– Après l’exécution de l’instruction if, l’état devient :
( [({Browse I}, {I → i 0 }) ({Loop10 I+1}, {I → i 0 })],
{i 0 = 0} ∪ s )
– Après l’exécution du Browse, nous arrivons au premier appel récursif :
( [({Loop10 I+1}, {I → i 0 })],
{i 0 = 0} ∪ s )
– Après l’exécution de l’instruction if dans l’appel récursif, nous avons :
( [({Browse I}, {I → i 1 }) ({Loop10 I+1}, {I → i 1 })],
{i 0 = 0, i 1 = 1} ∪ s )
– Après l’exécution du Browse à nouveau, nous arrivons au deuxième appel
récursif :
( [({Loop10 I+1}, {I → i 1 })],
{i 0 = 0, i 1 = 1} ∪ s )
Il est clair que la pile au k-ième appel récursif a toujours la forme :
[({Loop10 I+1}, {I → i k−1 })]
Il n’y a qu’une instruction sémantique et son environnement a une taille constante. Cela
s’appelle l’optimisation terminale. La manière efficace de programmer une boucle dans
le modèle déclaratif est de la programmer comme une procédure récursive-terminale.
Nous pouvons aussi voir que les tailles de la pile sémantique et la mémoire ont des
évolutions différentes. La pile sémantique est bornée par une taille constante. Mais la
mémoire grandit à chaque appel. Au k-ième appel récursif, la mémoire a le contenu :
{i 0 = 0, i 1 = 1, . . . , i k−1 = k − 1} ∪ s
La taille de la mémoire est proportionnelle au nombre d’appels récursifs. Nous verrons
que cette croissance n’est pas un problème en pratique. Regardez bien la pile sémantique du k-ième appel récursif. Elle n’a pas besoin des variables {i 0 , i 1 , . . . , i k−2 }. La
seule variable dont elle a besoin est i k−1 . Nous pouvons donc enlever de la mémoire
les variables dont nous n’avons pas besoin sans changer les résultats du calcul. La
mémoire devient alors plus petite :