“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 104 — #114
i
i
i
i
i
i
i
i
104
2
• La programmation déclarative
➤ Exercice 9 — La traduction en langage noyau
Prenez la fonction SMerge suivante qui fusionne deux listes triées :
fun {SMerge Xs Ys}
case Xs#Ys of nil#Ys then Ys
[] Xs#nil then Xs
[] (X|Xr)#(Y|Yr) then
if X=
end
end
Traduisez SMerge en syntaxe noyau. Remarquez que X#Y est un tuple de deux
arguments qui peut être écrit ´#´(X Y). La procédure qui résulte devrait être
récursive terminale si vous suivez correctement les règles de la section 2.6.2.
➤ Exercice 10 — La récursion mutuelle
L’optimisation terminale est importante pour bien plus que les appels récursifs.
Prenez cette définition mutuellement récursive des fonctions IsOdd et IsEven :
fun {IsEven X}
if X==0 then true else {IsOdd X-1} end
end
fun {IsOdd X}
if X==0 then false else {IsEven X-1} end
end
On dit que ces fonctions sont mutuellement récursives parce que chaque fonction appelle l’autre. La récursion mutuelle peut être généralisée à un nombre
quelconque de fonctions. Un ensemble de fonctions sera mutuellement récursif
si on peut les mettre dans une séquence telle que chaque fonction appelle la
suivante et la dernière appelle la première. Pour cet exercice, montrez que les
appels {IsOdd N} et {IsEven N} s’exécutent avec une taille constante de
la pile et ce pour tous les N zéro ou positifs. En général, si chaque fonction dans
un ensemble mutuellement récursif n’a qu’un appel de fonction dans son corps
et que cet appel est un dernier appel, alors toutes les fonctions dans l’ensemble
s’exécuteront avec la taille de leur pile bornée par une constante.
➤ Exercice 11 — Les exceptions avec une clause finally
La section 2.7 montre comment définir l’instruction try/finally par une
traduction en une instruction try/catch. Pour cet exercice, définissez une
autre traduction de
try s 1 finally s 2 end
dans laquelle s 1 et s 2 n’apparaissent qu’une seule fois.
Indice : Il faut une variable booléenne.
i
i
i
i
i
i
i
i
104
2
• La programmation déclarative
➤ Exercice 9 — La traduction en langage noyau
Prenez la fonction SMerge suivante qui fusionne deux listes triées :
fun {SMerge Xs Ys}
case Xs#Ys of nil#Ys then Ys
[] Xs#nil then Xs
[] (X|Xr)#(Y|Yr) then
if X=
end
end
Traduisez SMerge en syntaxe noyau. Remarquez que X#Y est un tuple de deux
arguments qui peut être écrit ´#´(X Y). La procédure qui résulte devrait être
récursive terminale si vous suivez correctement les règles de la section 2.6.2.
➤ Exercice 10 — La récursion mutuelle
L’optimisation terminale est importante pour bien plus que les appels récursifs.
Prenez cette définition mutuellement récursive des fonctions IsOdd et IsEven :
fun {IsEven X}
if X==0 then true else {IsOdd X-1} end
end
fun {IsOdd X}
if X==0 then false else {IsEven X-1} end
end
On dit que ces fonctions sont mutuellement récursives parce que chaque fonction appelle l’autre. La récursion mutuelle peut être généralisée à un nombre
quelconque de fonctions. Un ensemble de fonctions sera mutuellement récursif
si on peut les mettre dans une séquence telle que chaque fonction appelle la
suivante et la dernière appelle la première. Pour cet exercice, montrez que les
appels {IsOdd N} et {IsEven N} s’exécutent avec une taille constante de
la pile et ce pour tous les N zéro ou positifs. En général, si chaque fonction dans
un ensemble mutuellement récursif n’a qu’un appel de fonction dans son corps
et que cet appel est un dernier appel, alors toutes les fonctions dans l’ensemble
s’exécuteront avec la taille de leur pile bornée par une constante.
➤ Exercice 11 — Les exceptions avec une clause finally
La section 2.7 montre comment définir l’instruction try/finally par une
traduction en une instruction try/catch. Pour cet exercice, définissez une
autre traduction de
try s 1 finally s 2 end
dans laquelle s 1 et s 2 n’apparaissent qu’une seule fois.
Indice : Il faut une variable booléenne.