“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 119 — #129
i
i
i
i
i
i
i
i
3.3 Le calcul récursif
119
fun {Iterate S IsDone Transform}
if {IsDone S} then S
else S1 in
S1={Transform S}
{Iterate S1 IsDone Transform}
end
end
Pour utiliser cette abstraction de contrôle, il faut passer des fonctions d’un argument
à IsDone et Transform. C’est un exemple de programmation d’ordre supérieur.
Iterate se comportera exactement comme SqrtIter si on passe les fonctions
GoodEnough et Improve :
fun {Sqrt X}
{Iterate
1.0
fun {$ G} {Abs X-G * G}/X<0.00001 end
fun {$ G} (G+X/G)/2.0 end}
end
Il y a deux valeurs fonctionnelles comme arguments à l’abstraction de contrôle. C’est
une technique puissante pour la structuration des programmes parce qu’elle fait une
séparation entre l’ordre des opérations et la définition des opérations. La programmation d’ordre supérieur est particulièrement utile pour cette structuration. Si l’abstraction de contrôle est utilisée souvent, l’étape suivante pourra être d’en faire une
abstraction linguistique.
3.3 LE CALCUL RÉCURSIF
Le calcul itératif est un cas spécial d’un calcul plus général qui s’appelle le calcul
récursif. Rappelez-vous qu’un calcul itératif peut être considéré comme une boucle
dans laquelle une action est répétée un certain nombre de fois. La section 3.2 l’implémente dans le modèle déclaratif avec une abstraction de contrôle, la fonction
Iterate. La fonction teste d’abord une condition. Si la condition est fausse, elle
fera une action et s’appellera elle-même.
La récursion est plus générale. Une fonction récursive peut s’appeler elle-même à
tout endroit dans son corps et même plusieurs fois. La récursion est importante pour
les fonctions mais aussi pour les types de données. Un type de données récursif est
défini par rapport à lui-même. Par exemple, le type liste est défini en utilisant le type
liste : une liste est une liste vide ou un élément suivi par une liste. Les deux formes de
récursion sont fortement apparentées parce que les fonctions récursives peuvent être
utilisées pour calculer avec les types de données récursifs.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.3 Le calcul récursif
119
fun {Iterate S IsDone Transform}
if {IsDone S} then S
else S1 in
S1={Transform S}
{Iterate S1 IsDone Transform}
end
end
Pour utiliser cette abstraction de contrôle, il faut passer des fonctions d’un argument
à IsDone et Transform. C’est un exemple de programmation d’ordre supérieur.
Iterate se comportera exactement comme SqrtIter si on passe les fonctions
GoodEnough et Improve :
fun {Sqrt X}
{Iterate
1.0
fun {$ G} {Abs X-G * G}/X<0.00001 end
fun {$ G} (G+X/G)/2.0 end}
end
Il y a deux valeurs fonctionnelles comme arguments à l’abstraction de contrôle. C’est
une technique puissante pour la structuration des programmes parce qu’elle fait une
séparation entre l’ordre des opérations et la définition des opérations. La programmation d’ordre supérieur est particulièrement utile pour cette structuration. Si l’abstraction de contrôle est utilisée souvent, l’étape suivante pourra être d’en faire une
abstraction linguistique.
3.3 LE CALCUL RÉCURSIF
Le calcul itératif est un cas spécial d’un calcul plus général qui s’appelle le calcul
récursif. Rappelez-vous qu’un calcul itératif peut être considéré comme une boucle
dans laquelle une action est répétée un certain nombre de fois. La section 3.2 l’implémente dans le modèle déclaratif avec une abstraction de contrôle, la fonction
Iterate. La fonction teste d’abord une condition. Si la condition est fausse, elle
fera une action et s’appellera elle-même.
La récursion est plus générale. Une fonction récursive peut s’appeler elle-même à
tout endroit dans son corps et même plusieurs fois. La récursion est importante pour
les fonctions mais aussi pour les types de données. Un type de données récursif est
défini par rapport à lui-même. Par exemple, le type liste est défini en utilisant le type
liste : une liste est une liste vide ou un élément suivi par une liste. Les deux formes de
récursion sont fortement apparentées parce que les fonctions récursives peuvent être
utilisées pour calculer avec les types de données récursifs.
© Dunod – La photocopie non autorisée est un délit