Concepts de base

Que trouve-t-on dans ce chapitre ?
Quels sont les concepts fondamentaux de Prolog III ? Quels objets le langage manipule-t-il ? Quelle est la nature des contraintes qui pèseront sur ces objets ? Qu’est-ce qu’un programme Prolog III signifie pour le programmeur ? Comment la machine l’exécute-t-elle ? Selon quelle syntaxe ces objets et contraintes doivent-ils être exprimés ?
Il y a une différence de nature, et non de degré, entre la plupart des autres langages de programmation et Prolog III. On ne peut aborder ce dernier sans examiner auparavant un certain nombre de concepts originaux à la base du langage, indispen-sables pour une utilisation optimale, parfois même une utilisation tout-court, de celui-ci.
Ce chapitre présente l’ensemble des spécifications de Prolog III, d’une manière assez informelle, accessible quel que soit le degré de familiarité que vous entretenez déjà avec la programmation logique.
Nous y définissons les objets manipulés par le langage, puis les opérations et les relations qui permettent d’établir des contraintes sur ces objets. Ensuite, nous présentons ce qu’est un programme Prolog III, ainsi que la manière dont il est exécuté.

Arbres

Quelle est la nature des objets manipulés ? » C’est une des premières questions auxquelles il nous faut répondre pour expliquer Prolog III. Le langage est tout-à-fait cohérent et uniforme :
TOUS LES OBJETS MANIPULéS PAR PROLOG III SONT DES ARBRES
Certains sont très complexes, voire infinis, tandis que d’autres sont réduits à un unique nœud. Certains ont une dénomination particulière, alors que d’autres ne peuvent être designés qu’au moyen d’une opération qui les construit ou d’un système de contraintes dont ils sont solution.
N’ayant pas à reproduire les démonstrations formelles qui justifient les algorithmes du cœur de Prolog III, nous ne donnerons pas ici de définition rigoureuse des arbres. La notion intuitive habituelle, qui assimile le concept d’arbre à celui d’ensemble organisé hiérarchiquement nous suffira amplement.
Cette hiérarchie est incarnée dans un ensemble de positions, ou nœuds, et un ensemble de flèches reliant ces positions. On dit que les nœuds auxquels aboutit une flèche issue d’un nœud n sont les fils de n. L’ensemble des fils d’un nœud donné est toujours ordonné, ne serait-ce que par l’ordre dans lequel ces nœuds sont pratiquement représentés. Le nœud qui est au sommet de la hiérarchie s’appelle la racine, ou nœud initial de l’arbre.
Chaque nœud d’un arbre est à son tour racine d’un arbre, appelé sous-arbre de l’arbre initial, défini par ce nœud, ses fils, les fils de ses fils, etc… ainsi que les flèches qui émanent de tous ces nœuds.
UN ARBRE COMPORTE UNE éTIQUETTE ET UNE SUITE FINIE DE SOUS-ARBRES.
A chaque nœud d’un arbre Prolog III est associée une étiquette. Les étiquettes possibles sont :
les identificateurs
les caractères
les valeurs booléennes 0′ et 1′
les nombres
le double signe <>
Voici un arbre de Prolog III :
nom_marie_poids
<> 1′ 755/10
`D` `u` `p` `o` `n` `t`
Le nombre des fils d’un nœud est toujours fini et indépendant de la nature de son étiquette. Bien entendu, la sémantique de cette dernière, ce qu’elle signifie pour le programmeur, peut faire qu’un nœud n’ait de sens qu’assorti d’un nombre déterminé de fils, mais cela n’est pas connu des mécanismes de base de Prolog III.
Le nombre des fils d’un nœud peut être nul : un arbre réduit à un seul nœud est appelé une feuille. Prolog III ne fait pas de distinction entre une feuille et l’étiquette qu’elle porte. Par conséquent, les identificateurs, les caractères, les valeurs booléennes et les nombres sont considérés comme des cas particuliers d’arbres.
Tous ces éléments peuvent servir à étiqueter un nœud, un cas particulièrement fréquent étant celui où l’étiquette est un identificateur, comme dans l’exemple dessiné ci-dessus. Fort souvent de tels arbres représentent des relations. Pour l’arbre dont nous parlons, ce pourrait être « s’appelle Dupont, est marié et pèse 75,5 Kg ».
Un autre cas fréquent est celui où l’étiquette du nœud initial de l’arbre n’a aucune signification pour le programmeur, qui ne s’intéresse donc qu’à la suite des fils. Prolog III permet d’utiliser alors pour étiquette le double signe conventionnel <>. De tels arbres sont appelés PIII-tuples ou, plus simplement, tuples, et ils implantent donc la notion de suite finie d’arbres. Dans cet esprit, l’arbre réduit au symbole <> représente la suite vide. Les tuples sont expliqués plus en détail au chapitre « Arbres, tuples, chaînes et listes »
Grâce au puissant opérateur dont ils sont munis, qui traduit l’opération de concaténation des suites finies, les tuples constituent un outil souple et puissant pour la définition de nombreuses structures de données, alliant la généralité des listes et l’efficacité des vecteurs. Ils peuvent donc avantageusement remplacer la notion habituelle de liste, comme elle existe en Lisp ou dans d’autres Prolog.
Cependant ces listes classiques, définies à partir de la notion de paire pointée, peuvent être aussi utilisées en Prolog III, y compris à travers leur syntaxe habituelle, dite d’Edimbourg.
Dans les programmes Prolog III, les arbres sont représentés par des formules appelées termes. La syntaxe des termes apparaîtra progressivement tout au long des paragraphes suivants ; elle est résumée au chapitre « Les syntaxes de Prolog III ».
Les arbres et les termes ne sont pas la même chose : les éléments du domaine de Prolog III sont des arbres, les entités syntaxiques qui les représentent sont des termes. Or, dans l’explication de Prolog III il ne sera guère question que de ces derniers, car ils sont la seule expression écrite des arbres en accord avec la syntaxe du langage. Ceci semble encourager une certaine confusion des deux notions. Nous ne saurions trop mettre en garde le lecteur contre une telle confusion, car elle présente de nombreux inconvénients et notamment celui d’empêcher la compréhension de notions parmi les plus importantes.
Cela étant dit, il y a un cas dans lequel on confond un arbre et le terme qui le représente : il s’agit des constantes, qui sont par définition les arbres représentés par des termes simples, dont l’expression ne fait pas intervenir d’opérateur, ainsi que l’explique le paragraphe suivant.

Constantes

Parmi les éléments du domaine de Prolog III, c’est-à-dire les arbres, les constantes désignent ceux qui ont reçu une dénomination particulière. Comme nous l’avons dit, nous ne ferons pas de distinction entre une constante et le terme qui la représente.
Il ne suffit pas d’être une feuille pour être une constante : un arbre réduit à un unique nombre fractionnaire, comme 755/10, est une feuille, mais il ne possède pas de nom spécifique et il ne peut être exprimé qu’à travers la division dont il est le résultat. Bien entendu, 151/2 est une autre manière de spécifier le même nombre rationnel.
Inversement, toutes les constantes ne représentent pas nécessairement des feuilles. Ainsi une suite de caractères comme
< >
`D` `u` `p` `o` `n` `t`
n’est certainement pas atomique ; cependant, Prolog III la considérera com-me une constante, dès lors que l’on utilisera la notation particulière des chaînes, « Dupont ». Bien entendu, vous pouvez représenter le même arbre par le terme <`D`,`u`,`p`,`o`,`n`,`t`>.
Les constantes connues sont :
Les identificateurs
Les identificateurs sont les constantes symboliques, comme
pierre
repas_leger
calcul12
Un identificateur est une suite de lettres, de chiffres et des deux caractères apostrophe ( ‘ ) et blanc souligné ( _ ) qui n’a pas la syntaxe d’un nom de variable, c’est-à-dire qui commence par au moins deux lettres. Une description plus précise de la syntaxe des identificateurs est donnée au chapitre « Les syntaxes de Prolog III ».
En réalité la syntaxe des identificateurs est bien plus complexe que celle des exemples montrés ici, puisque la notation complète d’un identificateur comporte un qualifieur (ou préfixe) qui indique le module auquel l’identificateur appartient. L’ensemble des modules intervenant dans un programme Prolog III réalise une partition de l’espace des noms, lui permettant d’être gigantesque tout en restant facile à appréhender par le programmeur. Cependant, l’existence par ailleurs d’un contexte de lecture-écriture permet le plus souvent de n’utiliser que des notations simplifiées pour les identificateurs.
Les notions de module, de qualifieur et de contexte de lecture-écriture sont expliquées au chapitre « Le contrôle et l’environnement des programmes »
Tous les caractères disponibles sur votre machine peuvent être utilisés dans un programme Prolog III. Les caractères imprimables peuvent être exprimés en les encadrant par des « anti-apostrophes » : `A`, `a`, `<`
Les caractères non imprimables et ceux ayant un rôle spécial peuvent être indiqués au moyen du caractère d’échappement anti-slash ( \ ), selon une convention proche de celle utilisée dans la communauté UNIX. Par exemple :
`\«  indique le caractère `
`\n` indique le caractère “nouvelle ligne”
`\x41` indique le caractère A (de code ASCII 41 en
hexadécimal)
`\101` indique le caractère A (de code ASCII 101 en octal)
`\\` indique le caractère \ lui-même
La syntaxe complète des caractères est donnée au chapitre « Les syntaxes de Prolog III ».
Les valeurs booléennes
Les valeurs booléennes sont les deux éléments du domaine de l’algèbre de
Boole classique :
Nous ne les interpréterons pas en termes de vrai ou de faux, réservant ces mots pour parler des contraintes (nous dirons qu’une contrainte est vraie ou fausse, pour indiquer qu’elle est ou n’est pas satisfaite). Les contraintes sont expliquées ci-dessous, au § 7.
Les nombres entiers non négatifs
0
1
2
1991
815915283247897734345611269596115894272000000000
On notera que les entiers négatifs ne sont pas considérés comme des constantes, puisqu’on peut les exprimer comme résultat d’une opération, le changement de signe, appliquée à un entier positif ou nul. De la même manière, les nombres fractionnaires ne sont pas des constantes non plus, ils sont représentés à l’aide des opérations de division et de changement de signe, appliquées à des entiers.
Les nombres rationnels sont représentés dans la machine en précision parfaite, c’est-à-dire avec autant de chiffres que leur expression exacte le requiert. A la condition, bien entendu, que cela ne dépasse pas la taille de la mémoire de votre machine.
Les nombres flottants non négatifs
Exemples :
12.345
0 . 5
314.15926535e-2
1.2E12
La représentation interne, et donc la précision et l’étendue des nombres flottants, sont déterminés par les particularités de votre machine. Leur syntaxe coïncide avec celle utilisée dans la plupart des langages qui connaissent ce type de données numériques. Elle est donnée en détail au chapitre « Les syntaxes de Prolog III ».
Le tuple vide < >
Le double signe <> est un symbole conventionnel destiné à servir d’étiquette aux arbres qui, d’un point de vue sémantique, n’en ont pas. Ces arbres se réduisent donc à la suite de leurs fils : ils implantent en Prolog III la notion de suite finie d’arbres, qu’on appelle des tuples.
Comme nous le verrons, les tuples se notent <a1, … an> ; le tuple vide se note donc tout naturellement <>. Ceci justifie le nom donné à ce signe.
Les chaînes de caractères
La notation courante des chaînes de caractères, à l’aide de guillemets :
« Et oui »
est en réalité une deuxième notation pour l’arbre
< > `E` `t` ` ` `o` `u` `i`
En Prolog III, une chaîne de caractères est toujours structurée, puisque c’est un tuple de caractères. Les chaînes ne sont des entités atomiques qu’en tant qu’objets syntaxiques, et encore à la condition d’utiliser la notation des constantes-chaînes, « Et oui ».
Cas particulier, le tuple vide et la chaîne vide sont la même chose ; les deux notations «  » et <> sont donc équivalentes.
Pour désigner des arbres qui ne sont pas des constantes vous devez écrire des formules qui combinent des constantes et des opérateurs, selon une syntaxe que nous indiquerons progressivement. Une telle formule exprime le résultat d’une opération. Une opération est définie sur un ensemble de n-uplets d’arbres ; à chacun elle associe un arbre1 :
f : (a1, … an) f (a1, … an)
L’ensemble des n-uplets d’arbres pour lesquels une opération donnée est définie n’est pas obligatoirement égal à l’ensemble de tous les n-uplets ; on dit que l’opération est partielle. Spécifier le sous-ensemble des n-uplets sur lesquels l’opération est définie fait partie de la définition de l’opération en question.
On dispose de trois types d’opérations : les opérations booléennes, les opérations arithmétiques et les opérations de construction d’arbres. Avec une précision importante: les opérations booléennes et arithmétiques ont leur signification mathématique habituelle.
Cette remarque peut surprendre mais elle mérite d’être faite, notamment à l’intention des utilisateurs des Prolog précédents. Dans ces langages, des opérations notées +, *, &, etc… sont définies ou pourraient l’être ; cependant, elles n’y ont pas leur signification mathématique courante, elles ne sont que des opérations de construction d’arbres. Ainsi, en Prolog II, la formule 2 + 3 désigne l’arbre dont l’étiquette est + et les fils 2 et 3. Un prédicat prédéfini peut ensuite interpréter cet arbre et en extraire le nombre 5, mais cela est étranger au cœur de Prolog II, qui n’effectue aucun traitement spécifique des booléens ou des nombres.
Dans le jargon mathématique, une opération est donc une application
En Prolog III, au contraire, les opérations booléennes et arithmétiques sont connues en tant que telles du cœur du langage, qui leur donne leur signification logique ou arithmétique habituelle. Il en découle que l’arbre représenté par la formule 2 + 3 n’est autre que la feuille réduite au nombre 5, résultat de l’opération indiquée.
Cette remarque aura encore plus d’intérêt quand nous considérerons les termes avec des variables. Comme pour l’addition précédente, la formule 2 X ne désignera pas un quelconque arbre non atomique mais bel et bien le nombre (inconnu) résultat de l’addition de 2 et du nombre inconnu X.

Introduction
Débuter avec Prolog III
1. Démarrer une session Prolog III.
2. Utilisation d’un programme d’exemple
3. Quelques petits exemples
Concepts de base
1. Arbres
2. Constantes.
3. Opérations
4. Variables
5. Termes
6. Relations
7. Contraintes
8. Résolution des systèmes de contraintes
9. Règles et requêtes
Arbres, tuples, chaînes et listes
1. Introduction
2. Les arbres
3. Les tuples
4. Règles prédéfinies sur les tuples
5. Les listes
6. Les chaînes
7. Exemples
Les contraintes numériques
1. Introduction
2. Généralités
3. Règles prédéfinies et procédures externes spécifiques
4. Retardement des contraintes non-linéaires.
5. Formats d’entrée-sortie
6. Exemples de programmes
Les contraintes booléennes
1. Introduction
2. Quelques définitions et remarques
3. Premiers exemples de programmes
4. D’autres exemples
Retardements
1. Introduction
2. Termes connus
3. Retardement de l’exécution d’un but
4. Contraintes retardées
Le contrôle et l’environnement des programmes
1. Le contrôle
2. Expressions, variables statiques, tableaux
3. Structuration, saisie et modification des règles
4. Entrées / sorties
5. Autres éléments de l’environnement
Règles prédéfinies et procédures externes
1. Introduction
Les syntaxes de Prolog III
1. Introduction
2. Syntaxe de base
3. Syntaxe d’Edimbourg
4. Remarques générales
Primitives Graphiques
1. Introduction et conventions
2. Primitives de gestion des fenêtres
3. Dessin et positionnement
4. Usage de la souris
5. Modes de dessin et d’écriture
6. Primitives spéciales de lecture et d’écriture
7. Primitive de description de menus
8. Gestion des boîtes de dialogue
9. Boutons actifs
10. Primitives de manipulation de fichiers
Annexes
A. Liste des messages d’erreur de Prolog III
B. Liste des règles prédéfinies par catégorie
C. Quelques programmes Prolog III en syntaxe Edimbourg
Index Général