“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 125 — #135
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
125
proc {$ T 1 · · · T n T}. Par exemple, le type fun {$ List List} : List est
une fonction qui prend deux listes et qui renvoie une liste.
Les limites de la notation
Cette notation pour définir des types est utile pour définir beaucoup d’ensembles
de valeurs, mais son expressivité est certainement limitée. Voici quelques cas où la
notation ne suffit pas :
– La notation ne peut pas définir les entiers strictement positifs, à savoir le sousensemble de Int avec seulement les éléments plus grands que zéro.
– La notation ne peut pas définir des ensembles de valeurs partielles. Par exemple,
les flots ne peuvent pas être définis.
Nous pouvons étendre la notation pour couvrir le premier cas, par exemple en ajoutant
des conditions booléennes.
5 Dans les exemples suivants, nous ajouterons ces conditions dans le texte quand nous en aurons besoin. Cela veut dire que la notation des
types est descriptive : elle donne des assertions logiques sur l’ensemble des valeurs
qu’une variable peut avoir. On ne pourrait sans doute pas vérifier ces types dans un
compilateur. Même les types qui sont simples à spécifier, comme les entiers strictement
positifs, ne peuvent généralement pas être vérifiés.
3.4.2 La programmation avec les listes
Les valeurs de liste sont faciles à créer et à décomposer, cependant elles sont assez
puissantes pour coder toutes sortes de structures de données complexes. Le langage
Lisp tire beaucoup de sa puissance de cette idée [63]. À cause de la structure simple
des listes, la programmation déclarative avec elles est facile et puissante. Cette section
montre les techniques de base pour programmer avec des listes :
– Penser récursivement. L’idée est de résoudre un problème en utilisant des versions plus petites du problème.
– Convertir des calculs récursifs en calculs itératifs. Un programme naïf sur les
listes est souvent inefficace parce que la taille de sa pile grandit avec la taille
de l’entrée. Nous montrons comment utiliser les transformations d’état pour
convertir ces programmes en programmes itératifs.
– Raisonner sur l’exactitude des calculs itératifs. Une façon de raisonner sur les
calculs itératifs est l’utilisation des invariants d’état.
5. Cela ressemble à la manière dont on a défini la syntaxe du langage dans la section 2.1.1 : une notation
hors-contexte supplémentée par des conditions quand on en a besoin.
© 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
125
proc {$ T 1 · · · T n T}. Par exemple, le type fun {$ List List} : List est
une fonction qui prend deux listes et qui renvoie une liste.
Les limites de la notation
Cette notation pour définir des types est utile pour définir beaucoup d’ensembles
de valeurs, mais son expressivité est certainement limitée. Voici quelques cas où la
notation ne suffit pas :
– La notation ne peut pas définir les entiers strictement positifs, à savoir le sousensemble de Int avec seulement les éléments plus grands que zéro.
– La notation ne peut pas définir des ensembles de valeurs partielles. Par exemple,
les flots ne peuvent pas être définis.
Nous pouvons étendre la notation pour couvrir le premier cas, par exemple en ajoutant
des conditions booléennes.
5 Dans les exemples suivants, nous ajouterons ces conditions dans le texte quand nous en aurons besoin. Cela veut dire que la notation des
types est descriptive : elle donne des assertions logiques sur l’ensemble des valeurs
qu’une variable peut avoir. On ne pourrait sans doute pas vérifier ces types dans un
compilateur. Même les types qui sont simples à spécifier, comme les entiers strictement
positifs, ne peuvent généralement pas être vérifiés.
3.4.2 La programmation avec les listes
Les valeurs de liste sont faciles à créer et à décomposer, cependant elles sont assez
puissantes pour coder toutes sortes de structures de données complexes. Le langage
Lisp tire beaucoup de sa puissance de cette idée [63]. À cause de la structure simple
des listes, la programmation déclarative avec elles est facile et puissante. Cette section
montre les techniques de base pour programmer avec des listes :
– Penser récursivement. L’idée est de résoudre un problème en utilisant des versions plus petites du problème.
– Convertir des calculs récursifs en calculs itératifs. Un programme naïf sur les
listes est souvent inefficace parce que la taille de sa pile grandit avec la taille
de l’entrée. Nous montrons comment utiliser les transformations d’état pour
convertir ces programmes en programmes itératifs.
– Raisonner sur l’exactitude des calculs itératifs. Une façon de raisonner sur les
calculs itératifs est l’utilisation des invariants d’état.
5. Cela ressemble à la manière dont on a défini la syntaxe du langage dans la section 2.1.1 : une notation
hors-contexte supplémentée par des conditions quand on en a besoin.
© Dunod – La photocopie non autorisée est un délit