“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 142 — #152
i
i
i
i
i
i
i
i
142
3
• Techniques de programmation déclarative
ordonné est une condition globale sur l’arbre. Beaucoup d’arbres sont définis par des
conditions globales. Les algorithmes pour ces arbres sont compliqués parce qu’ils
doivent maintenir la condition globale. Le maintien d’une condition globale est un
exemple d’un calcul orienté but (« goal-oriented computation ») souvent utilisé dans
les techniques de l’intelligence artificielle. Les algorithmes sur les arbres sont plus
compliqués que les algorithmes sur les listes parce que la récursion doit combiner les
résultats de plusieurs problèmes plus petits au lieu d’un seul.
3.5 LES TYPES DE DONNÉES ABSTRAITS
Un type de données, ou simplement un type, est un ensemble de valeurs avec un
ensemble d’opérations sur ces valeurs. Notre modèle déclaratif a un ensemble prédéfini
de types, qui s’appellent les types de base (voir section 2.3). L’utilisateur peut aussi
définir de nouveaux types. Nous disons qu’un type est abstrait s’il est complètement
défini par l’ensemble de ses opérations, indépendamment de son implémentation. Le
terme « type de données abstrait » est souvent abrégé en ADT. L’utilisation d’un ADT
implique qu’il est possible de changer l’implémentation du type sans changer son
utilisation. Nous regardons comment l’utilisateur peut définir de nouveaux ADT.
Voici un exemple d’un nouveau type de données abstrait, une pile Stack T avec
des éléments de type T. Nous supposons que la pile a quatre opérations, avec les types
suivants :
fun {NewStack} : Stack T
fun {Push Stack T T} : Stack T
fun {Pop Stack T T} : Stack T
fun {IsEmpty Stack T} : Bool
Cet ensemble d’opérations et leurs types définit l’interface de l’ADT. Les opérations
satisfont certaines lois, par exemple :
– {IsEmpty {NewStack}}=true. Une nouvelle pile est toujours vide.
– Pour toutes E et S0, S1={Push S0 E} et S0={Pop S1 E} sont vraies.
Empilez un élément et puis dépilez un élément donne le même élément.
– Pour une E non liée, {Pop {EmptyStack} E} lève une erreur. Aucun élément ne peut être dépilé d’une pile vide.
Ces lois sont indépendantes de l’implémentation : toutes les implémentations doivent
les satisfaire. Voici une implémentation de la pile qui satisfait les lois :
fun {NewStack} nil end
fun {Push S E} E|S end
fun {Pop S E} case S of X|S1 then E=X S1 end end
fun {IsEmpty S} S==nil end
i
i
i
i
i
i
i
i
142
3
• Techniques de programmation déclarative
ordonné est une condition globale sur l’arbre. Beaucoup d’arbres sont définis par des
conditions globales. Les algorithmes pour ces arbres sont compliqués parce qu’ils
doivent maintenir la condition globale. Le maintien d’une condition globale est un
exemple d’un calcul orienté but (« goal-oriented computation ») souvent utilisé dans
les techniques de l’intelligence artificielle. Les algorithmes sur les arbres sont plus
compliqués que les algorithmes sur les listes parce que la récursion doit combiner les
résultats de plusieurs problèmes plus petits au lieu d’un seul.
3.5 LES TYPES DE DONNÉES ABSTRAITS
Un type de données, ou simplement un type, est un ensemble de valeurs avec un
ensemble d’opérations sur ces valeurs. Notre modèle déclaratif a un ensemble prédéfini
de types, qui s’appellent les types de base (voir section 2.3). L’utilisateur peut aussi
définir de nouveaux types. Nous disons qu’un type est abstrait s’il est complètement
défini par l’ensemble de ses opérations, indépendamment de son implémentation. Le
terme « type de données abstrait » est souvent abrégé en ADT. L’utilisation d’un ADT
implique qu’il est possible de changer l’implémentation du type sans changer son
utilisation. Nous regardons comment l’utilisateur peut définir de nouveaux ADT.
Voici un exemple d’un nouveau type de données abstrait, une pile Stack T avec
des éléments de type T. Nous supposons que la pile a quatre opérations, avec les types
suivants :
fun {NewStack} : Stack T
fun {Push Stack T T} : Stack T
fun {Pop Stack T T} : Stack T
fun {IsEmpty Stack T} : Bool
Cet ensemble d’opérations et leurs types définit l’interface de l’ADT. Les opérations
satisfont certaines lois, par exemple :
– {IsEmpty {NewStack}}=true. Une nouvelle pile est toujours vide.
– Pour toutes E et S0, S1={Push S0 E} et S0={Pop S1 E} sont vraies.
Empilez un élément et puis dépilez un élément donne le même élément.
– Pour une E non liée, {Pop {EmptyStack} E} lève une erreur. Aucun élément ne peut être dépilé d’une pile vide.
Ces lois sont indépendantes de l’implémentation : toutes les implémentations doivent
les satisfaire. Voici une implémentation de la pile qui satisfait les lois :
fun {NewStack} nil end
fun {Push S E} E|S end
fun {Pop S E} case S of X|S1 then E=X S1 end end
fun {IsEmpty S} S==nil end