“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 124 — #134
i
i
i
i
i
i
i
i
124
3
• Techniques de programmation déclarative
programmes, nous introduisons une notation simple pour définir des listes, des arbres
et d’autres sous-ensembles des enregistrements. Cela nous aidera pour écrire des
fonctions sur ces types.
Une liste Xs est définie comme étant soit nil soit X|Xr où Xr est une liste. Un
arbre binaire peut être défini comme étant soit un nœud feuille leaf soit un nœud
non feuille tree(key:K value:V left:LT right:RT) où LT et RT sont
des arbres binaires. Pour écrire ces définitions de façon claire et précise, nous proposons une notation simple basée sur les grammaires hors-contexte. Les non terminaux
représentent des types ou des valeurs. Nous utilisons la hiérarchie des types de la
figure 2.16 comme base : tous les types de cette hiérarchie seront disponibles comme
non terminaux prédéfinis. Ainsi Value et Record existent tous les deux, et comme
ils sont des ensembles de valeurs, nous pouvons dire Record ⊂ ⊂Value. Maintenant
nous pouvons définir le type de liste :
List : := nil
| |Value ´|´ List
Une valeur sera dans l’ensemble List si elle est l’atome nil ou si elle est X|Xr où
X est dans Value et Xr est dans List. C’est une définition récursive de List. On
peut prouver qu’il y a un ensemble unique qui est le plus petit ensemble qui satisfait
cette définition. La preuve est hors de notre portée, mais on peut la trouver dans tous
les livres introductifs sur la sémantique, comme par exemple [99]. Nous prenons ce
plus petit ensemble comme la valeur de List. Intuitivement, List peut être construit
en commençant avec nil et en répétant la règle de grammaire pour construire des
ensembles de listes de plus en plus grands, jusqu’à obtenir un point fixe.
Nous pouvons aussi définir les listes dont les éléments sont d’un type donné :
List T : := nil
| T ´|´ List T
Ici T est une variable de type et List T est une fonction de type. Appliquer la fonction
de type à un type quelconque renvoie le type d’une liste de ce type. Par exemple,
List Int est le type d’une liste d’entiers. Remarquez que List Value est équivalent
à List (parce qu’ils ont la même définition).
Nous pouvons définir un arbre binaire avec des littéraux comme clés et qui contient
d’éléments de type T :
BTree T : := leaf
| tree(key: Literal value: T
left: BTree T right: BTree T)
Le type d’une procédure est proc {$ T 1 · · · T n }, où T 1 , . . . , T n sont les types
de ses arguments. Le type de la procédure est appelé la signature de la procédure. Le type d’une fonction est fun {$ T 1 · · · T n } : T, qui est équivalent à
i
i
i
i
i
i
i
i
124
3
• Techniques de programmation déclarative
programmes, nous introduisons une notation simple pour définir des listes, des arbres
et d’autres sous-ensembles des enregistrements. Cela nous aidera pour écrire des
fonctions sur ces types.
Une liste Xs est définie comme étant soit nil soit X|Xr où Xr est une liste. Un
arbre binaire peut être défini comme étant soit un nœud feuille leaf soit un nœud
non feuille tree(key:K value:V left:LT right:RT) où LT et RT sont
des arbres binaires. Pour écrire ces définitions de façon claire et précise, nous proposons une notation simple basée sur les grammaires hors-contexte. Les non terminaux
représentent des types ou des valeurs. Nous utilisons la hiérarchie des types de la
figure 2.16 comme base : tous les types de cette hiérarchie seront disponibles comme
non terminaux prédéfinis. Ainsi Value et Record existent tous les deux, et comme
ils sont des ensembles de valeurs, nous pouvons dire Record ⊂ ⊂Value. Maintenant
nous pouvons définir le type de liste :
List : := nil
| |Value ´|´ List
Une valeur sera dans l’ensemble List si elle est l’atome nil ou si elle est X|Xr où
X est dans Value et Xr est dans List. C’est une définition récursive de List. On
peut prouver qu’il y a un ensemble unique qui est le plus petit ensemble qui satisfait
cette définition. La preuve est hors de notre portée, mais on peut la trouver dans tous
les livres introductifs sur la sémantique, comme par exemple [99]. Nous prenons ce
plus petit ensemble comme la valeur de List. Intuitivement, List peut être construit
en commençant avec nil et en répétant la règle de grammaire pour construire des
ensembles de listes de plus en plus grands, jusqu’à obtenir un point fixe.
Nous pouvons aussi définir les listes dont les éléments sont d’un type donné :
List T : := nil
| T ´|´ List T
Ici T est une variable de type et List T est une fonction de type. Appliquer la fonction
de type à un type quelconque renvoie le type d’une liste de ce type. Par exemple,
List Int est le type d’une liste d’entiers. Remarquez que List Value est équivalent
à List (parce qu’ils ont la même définition).
Nous pouvons définir un arbre binaire avec des littéraux comme clés et qui contient
d’éléments de type T :
BTree T : := leaf
| tree(key: Literal value: T
left: BTree T right: BTree T)
Le type d’une procédure est proc {$ T 1 · · · T n }, où T 1 , . . . , T n sont les types
de ses arguments. Le type de la procédure est appelé la signature de la procédure. Le type d’une fonction est fun {$ T 1 · · · T n } : T, qui est équivalent à