“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 180 — #190
i
i
i
i
i
i
i
i
180
3
• Techniques de programmation déclarative
fun {Append Ls Ms}
case Ms of nil then Ls
[] X|Mr then {Append {Append Ls [X]} Mr} end
end
Ce programme est-il correct ? Termine-t-il ? Pourquoi oui ou pourquoi non ?
➤ Exercice 7 — Une Append itérative
Cet exercice explore la puissance d’expression des variables dataflow. Dans le
modèle déclaratif, la définition suivante d’Append est itérative :
fun {Append Xs Ys}
case Xs of nil then Ys
[] X|Xr then X|{Append Xr Ys} end
end
Nous pouvons vérifier cela en regardant l’expansion :
proc {Append Xs Ys ?Zs}
case Xs of nil then Zs=Ys
[] X|Xr then Zr in Zs=X|Zr {Append Xr Ys Zr} end
end
Cette définition fait une récursion terminale parce que la variable non liée Zr
peut être placée dans la paire X|Zr et liée après. Restreignons maintenant le
modèle de calcul pour utiliser uniquement des valeurs. Comment pouvons-nous
écrire une Append itérative ? Une approche est de définir deux fonctions : (1)
une fonction itérative qui inverse une liste et (2) une fonction itérative qui fait
la concaténation de l’inverse d’une liste avec une autre liste. Définissez une
Append itérative avec cette approche.
➤ Exercice 8 — Les calculs itératifs et les variables dataflow
L’exercice précédent montre que l’utilisation des variables dataflow peut simplifier la définition des fonctions itératives sur les listes. Pour toute opération
itérative définie avec des variables dataflow, est-il possible de définir une autre
définition itérative de la même opération qui n’utilise pas les variables dataflow ?
➤ Exercice 9 — Le test de paire de liste
La section 3.4.3 définit une fonction LengthL qui calcule le nombre d’éléments
dans une liste imbriquée. Pour voir si X est une paire de liste ou pas, LengthL
utilise la fonction IsCons :
fun {IsCons X}
case X of _|_ then false else true end end
Que se passe-t-il si nous utilisons la définition suivante :
fun {IsCons X} X\=(_|_) end
Pourquoi cette version de IsCons ne fonctionne-t-elle pas ?
i
i
i
i
i
i
i
i
180
3
• Techniques de programmation déclarative
fun {Append Ls Ms}
case Ms of nil then Ls
[] X|Mr then {Append {Append Ls [X]} Mr} end
end
Ce programme est-il correct ? Termine-t-il ? Pourquoi oui ou pourquoi non ?
➤ Exercice 7 — Une Append itérative
Cet exercice explore la puissance d’expression des variables dataflow. Dans le
modèle déclaratif, la définition suivante d’Append est itérative :
fun {Append Xs Ys}
case Xs of nil then Ys
[] X|Xr then X|{Append Xr Ys} end
end
Nous pouvons vérifier cela en regardant l’expansion :
proc {Append Xs Ys ?Zs}
case Xs of nil then Zs=Ys
[] X|Xr then Zr in Zs=X|Zr {Append Xr Ys Zr} end
end
Cette définition fait une récursion terminale parce que la variable non liée Zr
peut être placée dans la paire X|Zr et liée après. Restreignons maintenant le
modèle de calcul pour utiliser uniquement des valeurs. Comment pouvons-nous
écrire une Append itérative ? Une approche est de définir deux fonctions : (1)
une fonction itérative qui inverse une liste et (2) une fonction itérative qui fait
la concaténation de l’inverse d’une liste avec une autre liste. Définissez une
Append itérative avec cette approche.
➤ Exercice 8 — Les calculs itératifs et les variables dataflow
L’exercice précédent montre que l’utilisation des variables dataflow peut simplifier la définition des fonctions itératives sur les listes. Pour toute opération
itérative définie avec des variables dataflow, est-il possible de définir une autre
définition itérative de la même opération qui n’utilise pas les variables dataflow ?
➤ Exercice 9 — Le test de paire de liste
La section 3.4.3 définit une fonction LengthL qui calcule le nombre d’éléments
dans une liste imbriquée. Pour voir si X est une paire de liste ou pas, LengthL
utilise la fonction IsCons :
fun {IsCons X}
case X of _|_ then false else true end end
Que se passe-t-il si nous utilisons la définition suivante :
fun {IsCons X} X\=(_|_) end
Pourquoi cette version de IsCons ne fonctionne-t-elle pas ?