“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 113 — #123
i
i
i
i
i
i
i
i
3.2 Le calcul itératif
113
Ces opérations permettent de construire des instructions en utilisant d’autres
instructions. Toutes ces manières de combiner des instructions sont déterministes
(si les instructions qui les composent sont déterministes, elles le sont aussi) et
elles ne dépendent pas d’un quelconque contexte.
3.2 LE CALCUL ITÉRATIF
Nous commençons la présentation des techniques de programmation par une technique
simple, le calcul itératif. C’est une boucle dont la taille de la pile est bornée par une
constante, indépendamment du nombre d’itérations. Le calcul itératif est un outil de
base. Comme il n’est pas toujours évident de savoir quand un programme est itératif,
nous allons donner un schéma général avec lequel nous pouvons construire des calculs
itératifs.
3.2.1 Un schéma général
Une classe importante de calculs itératifs commence avec un état initial S 0 et transforme cet état en pas successifs jusqu’à l’état final S final :
S 0 → S 1 → · · · → S final
Un calcul itératif de cette classe peut être fait avec le schéma suivant :
fun {Iterate S i }
if {IsDone S i } then S i
else S i+1 in
S i+1 ={Transform S i }
{Iterate S i+1 }
end
end
Pour utiliser ce schéma il faut donner des définitions pour les fonctions IsDone et
Transform. Nous prouvons que tout programme qui suit ce schéma est itératif. Il
suffit de démontrer que la taille de la pile ne grandit pas pendant l’exécution de Iterate. Pour la clarté, nous donnons simplement les instructions sur la pile sémantique
et nous omettons les environnements et la mémoire :
– Prenons la pile sémantique initiale [R={Iterate S 0 }].
– Supposons que {IsDone S 0 } renvoie false. Juste après l’exécution du if,
la pile sémantique est [S 1 ={Transform S 0 }, R={Iterate S 1 }].
– Après l’exécution de {Transform S 0 }, la pile sémantique est [R={Iterate S 1 }].
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.2 Le calcul itératif
113
Ces opérations permettent de construire des instructions en utilisant d’autres
instructions. Toutes ces manières de combiner des instructions sont déterministes
(si les instructions qui les composent sont déterministes, elles le sont aussi) et
elles ne dépendent pas d’un quelconque contexte.
3.2 LE CALCUL ITÉRATIF
Nous commençons la présentation des techniques de programmation par une technique
simple, le calcul itératif. C’est une boucle dont la taille de la pile est bornée par une
constante, indépendamment du nombre d’itérations. Le calcul itératif est un outil de
base. Comme il n’est pas toujours évident de savoir quand un programme est itératif,
nous allons donner un schéma général avec lequel nous pouvons construire des calculs
itératifs.
3.2.1 Un schéma général
Une classe importante de calculs itératifs commence avec un état initial S 0 et transforme cet état en pas successifs jusqu’à l’état final S final :
S 0 → S 1 → · · · → S final
Un calcul itératif de cette classe peut être fait avec le schéma suivant :
fun {Iterate S i }
if {IsDone S i } then S i
else S i+1 in
S i+1 ={Transform S i }
{Iterate S i+1 }
end
end
Pour utiliser ce schéma il faut donner des définitions pour les fonctions IsDone et
Transform. Nous prouvons que tout programme qui suit ce schéma est itératif. Il
suffit de démontrer que la taille de la pile ne grandit pas pendant l’exécution de Iterate. Pour la clarté, nous donnons simplement les instructions sur la pile sémantique
et nous omettons les environnements et la mémoire :
– Prenons la pile sémantique initiale [R={Iterate S 0 }].
– Supposons que {IsDone S 0 } renvoie false. Juste après l’exécution du if,
la pile sémantique est [S 1 ={Transform S 0 }, R={Iterate S 1 }].
– Après l’exécution de {Transform S 0 }, la pile sémantique est [R={Iterate S 1 }].
© Dunod – La photocopie non autorisée est un délit