“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 137 — #147
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
137
Des programmes plus compliqués ont souvent besoin de plus d’accumulateurs. Dans
certains grands programmes déclaratifs, nous avons utilisé jusquà dix accumulateurs.
Le compilateur Aquarius Prolog a été écrit dans ce style [96, 94]. Certaines de ses
procédures ont jusqu’à douze accumulateurs, ce qui veut dire 24 arguments supplémentaires ! Il est difficile d’utiliser autant d’arguments sans une assistance automatisée.
Nous avons utilisé un préprocesseur DCG
6 étendu qui prend des déclarations d’accumulateurs et qui ajoute les arguments nécessaires [48].
Nous ne programmons plus dans ce style ; nous trouvons que la programmation
avec l’état explicite est plus simple et plus efficace (voir chapitre 5). Il est raisonnable
d’utiliser quelques accumulateurs dans un programme déclaratif ; en fait il est rare
qu’un programme déclaratif n’en ait pas besoin. Par contre, l’utilisation d’un grand
nombre d’accumulateurs est un signe qu’il faut mieux utiliser l’état explicite.
3.4.4 Les arbres
À côté des structures de données linéaires comme les listes, les arbres sont la structure
de données récursive la plus importante dans la boîte à outils d’un programmeur. Un
arbre est soit un nœud feuille soit un nœud non feuille qui contient un ou plusieurs
arbres. Un nœud feuille s’appelle aussi un nœud externe ; un nœud non feuille s’appelle
aussi un nœud interne. Nous nous intéressons aux arbres finis, qui ont un nombre fini
de nœuds. Les nœuds peuvent porter des informations supplémentaires. Voici une
définition d’un arbre :
Tree : := leaf
| tree(Value Tree 1 · · · ·Tree n )
La différence majeure entre une liste et un arbre réside dans la bifurcation : une liste
a toujours une structure linéaire mais un arbre peut avoir une structure bifurquante.
Une liste non vide a toujours un élément suivi par exactement une liste plus petite. Un
arbre non vide a un nœud suivi par un nombre d’arbres plus petits. Ce nombre peut
être tout nombre naturel : zéro pour les nœuds feuilles et tout nombre positif pour les
nœuds non feuilles.
Il existe différentes sortes d’arbres, avec des branchements et des contenus différents.
Par exemple, une liste est un arbre dans lequel les nœuds non feuilles ont toujours
un unique sous-arbre (on peut l’appeler un arbre unaire). Dans un arbre binaire, les
nœuds non feuilles ont exactement deux sous-arbres. Dans un arbre ternaire, ils ont
exactement trois sous-arbres. Dans un arbre équilibré, tous les sous-arbres du même
nœud ont la même taille (le même nombre de nœuds) ou approximativement la même
taille.
6. DCG (« Definite Clause Grammar ») est une notation de grammaire pour Prolog qui est utilisée pour
cacher l’enfilage explicite d’un accumulateur.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
137
Des programmes plus compliqués ont souvent besoin de plus d’accumulateurs. Dans
certains grands programmes déclaratifs, nous avons utilisé jusquà dix accumulateurs.
Le compilateur Aquarius Prolog a été écrit dans ce style [96, 94]. Certaines de ses
procédures ont jusqu’à douze accumulateurs, ce qui veut dire 24 arguments supplémentaires ! Il est difficile d’utiliser autant d’arguments sans une assistance automatisée.
Nous avons utilisé un préprocesseur DCG
6 étendu qui prend des déclarations d’accumulateurs et qui ajoute les arguments nécessaires [48].
Nous ne programmons plus dans ce style ; nous trouvons que la programmation
avec l’état explicite est plus simple et plus efficace (voir chapitre 5). Il est raisonnable
d’utiliser quelques accumulateurs dans un programme déclaratif ; en fait il est rare
qu’un programme déclaratif n’en ait pas besoin. Par contre, l’utilisation d’un grand
nombre d’accumulateurs est un signe qu’il faut mieux utiliser l’état explicite.
3.4.4 Les arbres
À côté des structures de données linéaires comme les listes, les arbres sont la structure
de données récursive la plus importante dans la boîte à outils d’un programmeur. Un
arbre est soit un nœud feuille soit un nœud non feuille qui contient un ou plusieurs
arbres. Un nœud feuille s’appelle aussi un nœud externe ; un nœud non feuille s’appelle
aussi un nœud interne. Nous nous intéressons aux arbres finis, qui ont un nombre fini
de nœuds. Les nœuds peuvent porter des informations supplémentaires. Voici une
définition d’un arbre :
Tree : := leaf
| tree(Value Tree 1 · · · ·Tree n )
La différence majeure entre une liste et un arbre réside dans la bifurcation : une liste
a toujours une structure linéaire mais un arbre peut avoir une structure bifurquante.
Une liste non vide a toujours un élément suivi par exactement une liste plus petite. Un
arbre non vide a un nœud suivi par un nombre d’arbres plus petits. Ce nombre peut
être tout nombre naturel : zéro pour les nœuds feuilles et tout nombre positif pour les
nœuds non feuilles.
Il existe différentes sortes d’arbres, avec des branchements et des contenus différents.
Par exemple, une liste est un arbre dans lequel les nœuds non feuilles ont toujours
un unique sous-arbre (on peut l’appeler un arbre unaire). Dans un arbre binaire, les
nœuds non feuilles ont exactement deux sous-arbres. Dans un arbre ternaire, ils ont
exactement trois sous-arbres. Dans un arbre équilibré, tous les sous-arbres du même
nœud ont la même taille (le même nombre de nœuds) ou approximativement la même
taille.
6. DCG (« Definite Clause Grammar ») est une notation de grammaire pour Prolog qui est utilisée pour
cacher l’enfilage explicite d’un accumulateur.
© Dunod – La photocopie non autorisée est un délit