“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 107 — #117
i
i
i
i
i
i
i
i
3
• Techniques de programmation déclarative
107
nécessaire pour comprendre tout le programme est donc la somme de l’effort pour
comprendre le composant déclaratif et de l’effort pour comprendre le reste.
S’il y avait des interactions plus rapprochées entre le composant et le reste du
programme, alors ils ne pourraient pas être compris indépendamment. Ils devraient
être compris ensemble et l’effort nécessaire serait beaucoup plus grand. Par exemple,
il pourrait être proportionnel (grosso modo) au produit des efforts nécessaires pour
chaque partie. Pour un programme avec beaucoup de composants qui interagissent
souvent, l’effort total serait énorme (exponentiel dans le nombre de composants), ce
qui rend la compréhension difficile ou impossible. Un exemple d’un programme avec
des interactions rapprochées est un programme concurrent dont les fils se partagent un
état.
1
Des interactions plus rapprochées sont souvent nécessaires. Elles ne peuvent pas
être éliminées « par décret » en programmant dans un modèle qui ne les soutient pas.
Mais un principe important est qu’elles devraient être utilisées uniquement quand elles
sont nécessaires et pas autrement. Pour soutenir ce principe, autant de composants que
possible devraient être déclaratifs.
Le développement des programmes déclaratifs
La façon la plus simple d’écrire un programme déclaratif est d’utiliser le modèle du
chapitre 2. Toutes les opérations de base sur les types de base sont déclaratives. Il est
possible de combiner les opérations déclaratives pour faire de nouvelles opérations
déclaratives si on respecte certaines règles. La combinaison des opérations déclaratives
selon les opérations du modèle déclaratif donne toujours une nouvelle opération
déclarative (voir la section 3.1.3).
La règle standard en algèbre qui dit que « nous pouvons remplacer des égaux par
des égaux » est un autre exemple d’une combinaison déclarative. Dans les langages de
programmation, cette propriété s’appelle la transparence référentielle. Elle simplifie
énormément le raisonnement sur les programmes. Par exemple, si nous savons que
f (a) = a
2 , nous pourrons remplacer f (a) par a
2 partout où elle apparaît. L’équation
b = 7 f (a)
2 devient alors b = 7a
4 . C’est possible parce que f (a) est déclarative : elle
dépend uniquement de ses arguments et pas d’un autre état du calcul.
La technique de base pour écrire les programmes déclaratifs est de considérer le
programme comme un ensemble de fonctions récursives, en utilisant la programmation d’ordre supérieur pour simplifier la structure. Une fonction récursive est une
fonction dont le corps de la définition fait référence à la même fonction, directement
ou indirectement. La récursion directe veut dire que la fonction elle-même est utilisée
dans le corps. La récursion indirecte veut dire que la fonction référence une autre
1. Voir chapitre 8 de [97].
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3
• Techniques de programmation déclarative
107
nécessaire pour comprendre tout le programme est donc la somme de l’effort pour
comprendre le composant déclaratif et de l’effort pour comprendre le reste.
S’il y avait des interactions plus rapprochées entre le composant et le reste du
programme, alors ils ne pourraient pas être compris indépendamment. Ils devraient
être compris ensemble et l’effort nécessaire serait beaucoup plus grand. Par exemple,
il pourrait être proportionnel (grosso modo) au produit des efforts nécessaires pour
chaque partie. Pour un programme avec beaucoup de composants qui interagissent
souvent, l’effort total serait énorme (exponentiel dans le nombre de composants), ce
qui rend la compréhension difficile ou impossible. Un exemple d’un programme avec
des interactions rapprochées est un programme concurrent dont les fils se partagent un
état.
1
Des interactions plus rapprochées sont souvent nécessaires. Elles ne peuvent pas
être éliminées « par décret » en programmant dans un modèle qui ne les soutient pas.
Mais un principe important est qu’elles devraient être utilisées uniquement quand elles
sont nécessaires et pas autrement. Pour soutenir ce principe, autant de composants que
possible devraient être déclaratifs.
Le développement des programmes déclaratifs
La façon la plus simple d’écrire un programme déclaratif est d’utiliser le modèle du
chapitre 2. Toutes les opérations de base sur les types de base sont déclaratives. Il est
possible de combiner les opérations déclaratives pour faire de nouvelles opérations
déclaratives si on respecte certaines règles. La combinaison des opérations déclaratives
selon les opérations du modèle déclaratif donne toujours une nouvelle opération
déclarative (voir la section 3.1.3).
La règle standard en algèbre qui dit que « nous pouvons remplacer des égaux par
des égaux » est un autre exemple d’une combinaison déclarative. Dans les langages de
programmation, cette propriété s’appelle la transparence référentielle. Elle simplifie
énormément le raisonnement sur les programmes. Par exemple, si nous savons que
f (a) = a
2 , nous pourrons remplacer f (a) par a
2 partout où elle apparaît. L’équation
b = 7 f (a)
2 devient alors b = 7a
4 . C’est possible parce que f (a) est déclarative : elle
dépend uniquement de ses arguments et pas d’un autre état du calcul.
La technique de base pour écrire les programmes déclaratifs est de considérer le
programme comme un ensemble de fonctions récursives, en utilisant la programmation d’ordre supérieur pour simplifier la structure. Une fonction récursive est une
fonction dont le corps de la définition fait référence à la même fonction, directement
ou indirectement. La récursion directe veut dire que la fonction elle-même est utilisée
dans le corps. La récursion indirecte veut dire que la fonction référence une autre
1. Voir chapitre 8 de [97].
© Dunod – La photocopie non autorisée est un délit