Cours Prolog IV, tutoriel & guide de travaux pratiques en pdf.

La structure de base

Domaine de la structure choisie 4

Le domaine dom( 4) de la structure choisie est l’ensemble des arbres dont les nœuds, qui forment un ensemble éventuellement infini, sont étiquetés
1. soit par des identificateurs Prolog- ISO (complétés d’une arité),
2. soit par des nombres réels (considérés comme des étiquettes d’arité nulle),
On ne distingue pas les arbres ayant un seul nœud de l’étiquette portée par ce nœud. Les identificateurs et les réels sont donc assimilés à des arbres d’un nœud étiquetés par des identificateurs et par de réels. Plusieurs sous-ensembles de notre domaine jouent un rôle particulier, passons les en revue.
Ensemble des nombres rationnels Ce sont les nombres réels de la forme pq où q est un entier positif et p un entier positif ou nul. On les écrira tout simplement sous la forme p/q avec éventuellement un signe devant.
Ensemble des nombres rationnels décimaux Ce sont des nombres rationnels de la forme p 10 q, où p et q sont des entiers positifs ou nuls. On les note d’une façon classique avec éventuellement un point décimal et une partie exposant introduite par la lettre E. Remarquons que les nombres entiers sont un cas particulier des nombres décimaux.
virgule flottante, conformes à la norme forme Ce sont des nombres binaires, à IEEE simple précision4. Ils sont de la p 2q avec 0 p 224,1 et ,149 q 104, où p et q sont des entiers. Il y en a 2n + 1 avec n = 231,223,1, c’est-à-dire en tout et pour tout 2 139 095 039. Si on les numérote de, n à n et que l’on désigne parqi le nombre numéroi alors l’entier jij écrit en binaire sur 31 bits et précédé d’un bit pour indiquer le signe deiconstitue le codage IEEE de qi. Ce codage est sans redondances sauf le nombre 0 qui est codé avec le signe plus ou le signe moins.
Les rationnels IEEE sont des cas particuliers des rationnels décimaux5 et peu-vent donc être notés sous forme décimale avec beaucoup de chiffres. Cepen-dant afin de disposer d’une notation plus compacte on écrit `<x` et `>x` pour désigner les rationnelsIEEE qui précèdent et suivent immédiatement le nombre décimal sans signex.
Intervalle IEEE C’est un intervalle dont les bornes inférieurea et supérieure b, si elles existent, sont des nombres rationnels IEEE. On remarquera que l’en-semble des intervalles IEEE a pour éléments l’ensemble vide et l’ensemble des réels et est fermé pour toute intersection finie ou infinie de ses éléments. Le tout dernier point découle du fait que l’ensemble des nombres rationnelsIEEE est fini.
Union d’intervalles IEEE C’est un ensemble de réels de la formaE1 [ [ En, où les Ei sont des intervalles IEEE.
Ensemble des arbres rationnels Ce sont les arbres qui ont un ensemble fini de sous-arbres. Rappelons qu’il existe des arbres ayant un ensemble infini de nœuds mais un nombre fini de sous-arbres (non isomorphes).
Ensemble des arbres doublement rationnels Ce sont les arbres rationnels qui ne font pas intervenir d’autres nombres que des nombres rationnels.
où les ai sont des arbres quelconques. Une telle liste a est notée[a1; : : : ; an] et on désigne parjaj sa taille éventuellement nullen. La concaténation de deux listes, de tailles éventuellement nulles, est définie et notée par[a1; : : : ; am]
[am+1; : : : ; an] = [a1; : : : ; an].

Sous-domaines privilégiés

Tout le mécanisme de résolution approché de contraintes de Prolog IV repose sur le fait qu’à chaque variable est attribué un sous-ensemble de l’ensemble dom( 4) d’arbres et que constamment on essaye
1. de «réduire» ces sous-ensembles en tenant compte de leurs interactions avec chaque contrainte prise séparément et
2. de « globaliser » toute contrainte locale c’est-à-dire de la remplacer par une contrainte plus basique que l’on sait résoudre globalement.
Ces sous-ensembles ne sont pas quelconques, ce sont les sous-domaines privilégiés.Ils sont obtenus par intersections multiples des 15 formes de bases du tableau 2.1 qui représentent des sous-ensembles pas toujours disjoints. Une TAB. 2.1 – Sous-domaines privilégiés
Formes de base
1 l’ensemble des arbres
2 l’ensemble des arbres finis
3 l’ensemble des arbres infinis
4 l’ensemble des arbres qui sont des listes
5 l’ensemble des arbres qui ne sont pas des listes pour chaque entier n positif ou nul,
6 l’ensemble des arbres qui sont des listes de taille n pour chaque n-uplet A1; : : : ; An d’intervalles IEEE,
7 l’ensemble des listes de la forme [a1; : : : ; an], avec ai 2 Ai
8 l’ensemble des arbres ayant un seul nœud
9 l’ensemble des arbres ayant plus d’un seul nœud
10 l’ensemble des identificateurs
11 l’ensemble des arbres qui ne sont pas un simple identificateur
12 pour chaque intervalle IEEE A, l’ensemble A
13 l’ensemble des arbres qui ne sont pas un simple nombre réel
14 pour chaque arbre a doublement rationnel, l’ensemble fag
15 l’ensemble vide variante possible pour les formes 7 et 12 est donnée dans le tableau 2.2. Les modalités pour utiliser cette variante sont décrites dans la partie 9 de ce docu-ment : environnement général.
Chaque sous-domaine privilégié est de catégorie (a), de catégorie (b) ou à la fois de catégorie (a) et (b). Les sous-domaines de catégorie (a) interviennent dans le processus de réduction des sous-domaines et ceux de catégorie (b) dans le processus de globalisation des contraintes.
– Sont de catégorie (a) tous les sous-domaines privilégiés, à l’exception de ceux qui sont de la forme 14, lorsque a est un nombre, qui n’est pas un rationnel IEEE.
– Sont de catégorie (b) tous les sous-domaines privilégiés, à l’exception de ceux qui sont de la forme 7 ou 12, lorsque un Ai ou A est autre que l’ensemble vide ou l’ensemble R de tous les réels.
On remarquera que l’ensemble des sous-domaines privilégiés de catégorie (a) est fermé par intersections finis ou infinies et a pour élément l’ensemble de tous les arbres. De ceci il s’ensuit que, pour tout sous-ensemble A du domaine dom( 4), le plus petit (au sens de l’inclusion) sous-domaine privilégié de ca-tégorie (a) qui contiennentA existe toujours.
En effet cet ensemble est égal à l’intersection de tous les sous-domaines privi-légiés de catégorie (a) qui contiennentA, sous-domaines parmi lesquels figure au moins dom( 4).
Dans le tableau 2.3 on trouvera des exemples de notation Prolog IV pour ex-primer que X appartient à l’une des 15 formes possible de sous-domaines pri-vilégiés avec les deux variantes. Tous ces exemples sont présentés sous forme d’une disjonction multiple formant une requête.
TAB. 2.3 – Exemples d’appartenances à des sous-domaines privilégiés de base
>> X ~ tree; % 1
X ~ finite; % 2
X ~ infinite; % 3
X ~ list; % 4
X ~ nlist; % 5
X ~ [tree,tree,tree]; % 6
X ~ [cc(1,2),co(4,8.1),gt(`>9.1`),real]; % 7
X ~ [cc(1,2) u co(4,8), gt(9), real]; % 7 variante
X ~ leaf; % 8
X ~ nleaf; % 9
X ~ ident; % 10
X ~ nident; % 11
X ~ oc(`<2.1`,9); % 12
X ~ oc(2.1,3) u cc(3,5) u gt(5); % 12 variante
X ~ nreal; % 13
Y ex X = trio(X,Y,6), Y = duo(X,Y); % 14
X ~ ntree. % 15

Opérations de la structure 4

L’ensemble op( 4) des symboles d’opérations f est constitué de
– tout identificateur avec arité, id/ n, qui n’est pas un identificateur réservé du tableau 2.4,
– toute constante représentant un nombre rationnel.