“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 122 — #132
i
i
i
i
i
i
i
i
122
3
• Techniques de programmation déclarative
comme cela que la machine abstraite est réalisée sur un ordinateur. Mais l’approche
n’est pas très agréable pour le calcul à la main.
Nous pouvons faire une modification simple à la machine abstraite pour faciliter
son utilisation pour le calcul à la main. L’idée est de remplacer les identificateurs dans
les instructions par les entités en mémoire correspondantes. Cette opération s’appelle
une substitution. Par exemple, l’instruction R=N * R1 devient r 2 = 3 ∗ r 3 quand on
fait la substitution selon {R → r 2 , N → 3, R1 → r 3 }.
La machine abstraite basée sur les substitutions n’a pas d’environnements. Elle
substitue directement dans chaque instruction les identificateurs par les entités en
mémoire. Pour l’exemple de factorielle récursive, cela donne :
– La pile sémantique initiale est [{Fact 5 r 0 }].
– Au premier appel récursif : [{Fact 4 r 1 }, r 0 =5 * r 1 ].
– Au deuxième appel récursif : [{Fact 3 r 2 }, r 1 =4 * r 2 , r 0 =5 * r 1 ].
– Au troisième appel récursif : [{Fact 2 r 3 }, r 2 =3 * r 3 , r 1 =4 * r 2 , r 0 =5 * r 1 ].
Nous voyons de nouveau que la pile grandit d’une instruction par appel. Nous résumons les différences entre les deux variantes de la machine abstraite :
– La machine abstraite basée sur les environnements est fidèle à l’implémentation
sur un ordinateur qui utilise des environnements. Cependant, les environnements
introduisent un niveau supplémentaire d’indirection, ce qui les rend difficiles
pour le calcul à la main.
– La machine abstraite basée sur les substitutions est plus facile pour le calcul à la
main parce qu’il y a beaucoup moins de symboles à manipuler. Cependant, les
substitutions sont plus coûteuses à implémenter, elles ne sont donc généralement
pas utilisées dans une implémentation pratique.
Les deux variantes font les mêmes liens en mémoire et les mêmes manipulations de la
pile sémantique.
3.3.3 La conversion d’un calcul récursif en calcul itératif
La factorielle est suffisamment simple pour que l’on puisse la rendre itérative. Plus
loin, nous donnerons une méthode systématique pour définir des calculs itératifs. Pour
l’instant, nous allons montrer une technique pour transformer la factorielle en calcul
itératif. Dans le calcul que l’on vient de voir :
R=(5 * (4 * (3 * (2 * (1 * 1)))))
il suffit de changer l’ordre des calculs :
R=(((((1 * 5) * 4) * 3) * 2) * 1)
i
i
i
i
i
i
i
i
122
3
• Techniques de programmation déclarative
comme cela que la machine abstraite est réalisée sur un ordinateur. Mais l’approche
n’est pas très agréable pour le calcul à la main.
Nous pouvons faire une modification simple à la machine abstraite pour faciliter
son utilisation pour le calcul à la main. L’idée est de remplacer les identificateurs dans
les instructions par les entités en mémoire correspondantes. Cette opération s’appelle
une substitution. Par exemple, l’instruction R=N * R1 devient r 2 = 3 ∗ r 3 quand on
fait la substitution selon {R → r 2 , N → 3, R1 → r 3 }.
La machine abstraite basée sur les substitutions n’a pas d’environnements. Elle
substitue directement dans chaque instruction les identificateurs par les entités en
mémoire. Pour l’exemple de factorielle récursive, cela donne :
– La pile sémantique initiale est [{Fact 5 r 0 }].
– Au premier appel récursif : [{Fact 4 r 1 }, r 0 =5 * r 1 ].
– Au deuxième appel récursif : [{Fact 3 r 2 }, r 1 =4 * r 2 , r 0 =5 * r 1 ].
– Au troisième appel récursif : [{Fact 2 r 3 }, r 2 =3 * r 3 , r 1 =4 * r 2 , r 0 =5 * r 1 ].
Nous voyons de nouveau que la pile grandit d’une instruction par appel. Nous résumons les différences entre les deux variantes de la machine abstraite :
– La machine abstraite basée sur les environnements est fidèle à l’implémentation
sur un ordinateur qui utilise des environnements. Cependant, les environnements
introduisent un niveau supplémentaire d’indirection, ce qui les rend difficiles
pour le calcul à la main.
– La machine abstraite basée sur les substitutions est plus facile pour le calcul à la
main parce qu’il y a beaucoup moins de symboles à manipuler. Cependant, les
substitutions sont plus coûteuses à implémenter, elles ne sont donc généralement
pas utilisées dans une implémentation pratique.
Les deux variantes font les mêmes liens en mémoire et les mêmes manipulations de la
pile sémantique.
3.3.3 La conversion d’un calcul récursif en calcul itératif
La factorielle est suffisamment simple pour que l’on puisse la rendre itérative. Plus
loin, nous donnerons une méthode systématique pour définir des calculs itératifs. Pour
l’instant, nous allons montrer une technique pour transformer la factorielle en calcul
itératif. Dans le calcul que l’on vient de voir :
R=(5 * (4 * (3 * (2 * (1 * 1)))))
il suffit de changer l’ordre des calculs :
R=(((((1 * 5) * 4) * 3) * 2) * 1)