Tutoriel et Survol de Prolog IV

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

Les Bases de Prolog IV

Introduction

LE PREMIER PRINCIPE d’un langage tel que Prolog IV est d’être bâti sur une structure mathématique expressive dans laquelle on résout des contraintes complexes portant sur des éléments inconnus.
Le deuxième principe est d’avoir la liberté d’enrichir cette structure de nouvelles relations et de continuer à résoudre des contraintes dans la nouvelle structure obtenue.
Ces principes ne pouvant être respectés qu’à des degrés divers, un troisième principe de ce langage est d’être suffisamment bien conçu pour que ses insuffisances soient clairement perçues et donc mieux maîtrisées par l’utilisateur.

Explicitons ces trois principes

Premier principe : une structure de base expressive

A la base de notre langage se trouve la notion de contrainte et pour entrer dans le vif du sujet en voici une, peu commune, formulée avec des notations empruntées à la logique du premier ordre et plus généralement aux mathématiques
La seule variable qui a des occurrences libres dans cette formule est et donc cette contrainte exprime une propriété de sa valeur. Trouver cette valeur, c’est le rôle de Prolog IV.
Cet doit donc être plus grand ou égal 5 et de plus il faut qu’il existe des vecteurs et un réel tels que les 1er et 4ème éléments du vecteur soient égaux, les longueurs de et soient et le vecteur obtenu par concaténation de avec soit le même que celui obtenu par concaténation de avec , le réel soit plus grand ou égal à avec contraint à être égal à ou suivant que est ou n’est pas plus grand à , c’est-à-dire la partie entière de fois le premier élément du vecteur . Ouf ! Il n’y a qu’un seul qui satisfait à toute cette contrainte et c’est Comment se présentent les choses en Prolog IV? On lance le système qui signale qu’il attend une requête en affichant un double chevron fermant, on lui fournit la contrainte précédente dans une syntaxe adéquate, il la résout, fournit la réponse et affiche à nouveau le double chevron pour signaler qu’il est prêt à recommencer. Cela donne :
>> U ex V ex W ex X ex
le(Y,5),
V:1 = cos(V:4),
size(U) = 3,
size(V) = 10,
U o V = V o W,
ge(Y,2.+.(3.*.X)),
X = bgt(74,floor(100.*.V:1)).
Y = 5.
Rapidement quelques mots sur la syntaxe utilisée. Prolog IV se voulant conforme syntaxiquement à la norme Prolog ISO 1, toute expression se doit d’être un «terme » au sens de cette norme 2. Les termes au sens de la norme n’étant pas les termes comme on les connaît en logique, nous appellerons les premiers, termes-ISO. Ces termes-ISO sont essentiellement de l’une des trois formes
1 variable,
2 nombre ou identificateur,
3 identificateur(terme-ISO,. . . ,terme-ISO), avec des variations infixées, des notations spécifiques aux listes et la convention que les noms de variables commencent par des majuscules. Ces variations permettent d’écrire ici
X:I pour index(X,I),
X o Y pour conc(X,Y),
X.+.Y pour plus(X,Y),
X.*.Y pour times(X,Y),
les relations index/3, conc/3, plus/3, times/3 étant utilisées avec des notations fonctionnelles.
Passons à la sémantique de la contrainte. Le connecteur logique , noté ici par une virgule et la quantification existentielle notée ici ex ont leurs sens habituels, nous y reviendrons plus tard. Les variables représentent des élément inconnus pris dans un certain domaine et les autres symboles des relations et des opérations bien précises dans ce même domaine.
Ces opérations et relations dans un domaine précis font partie d’une structure plus complète, choisie une bonne fois pour toute, la structure de base . Ainsi que le laisse pressentir notre exemple de contrainte, il s’agit d’une structure particulièrement riche. Nous avons voulu à la fois pouvoir manipuler (1) des symboles, (2) des nombres et (3) des objets complexes construits à partir de ceux-ci. En ce qui concerne la partie numérique, nous nous sommes montré particulièrement ambitieux en introduisant une centaine de relations portant sur l’ensemble R des nombres réels (au sens mathématique), sur l’ensemble Q des nombres rationnels (les fractions), sur l’ensemble Z des nombres entiers relatifs et sur l’ensemble B des valeurs booléennes et , et ceci, tout en respectant les inclusions B Z Q R.

Deuxième principe : Une structure enrichissable

En écrivant un programme Prolog IV on définit de nouvelles relations qui complètent la structure de base . Cet enrichissement est plus d’ordre quantitatif que d’ordre qualitatif : essentiellement les nouvelles relations permettent d’exprimer en une seule contrainte la conjonction d’une multitude de contraintes atomiques exprimables dans . Par exemple le programme sigma permet de définir le lien qui existe entre une liste et la somme de ses éléments par une conjonction de contraintes portant sur le lien qui existe entre deux nombres et leur somme. Des conventions syntaxiques permettent d’écrire le programme sous forme d’un paquet de clauses plus habituel dans le monde
Prologien :
sigma(0,[]).
sigma(X,.(Yp,Lp)) :- plus(X,Yp,Xp), sigma(Xp,Lp).

Troisième principe : les insuffisances sont explicites

Prolog IV ne peut être parfait, il est hors de question de pouvoir résoudre parfaitement des contraintes dans une structure aussi riche que et il est encore moins question de laisser un usager enrichir sans aucune discipline et s’attendre à ce que miraculeusement la machine résolve toutes les contraintes exprimables dans cette nouvelle structure.
Ce que nous avons voulu c’est que Prolog IV soit parfait dans son imperfection ou plus exactement que ses imperfections soient explicites. Ceci passe par un fondement logique bien précis que l’on peut résumer en trois points.
(1) Syntaxiquement le langage Prolog IV est vu comme un langage du premier ordre avec égalité et les contraintes comme des formules positives, quantifiées existentiellement (partiellement).
(2) Sémantiquement et en l’absence de tout programme, le langage Prolog IV est vu comme une théorie du premier ordre avec égalité c’est-à-dire un ensemble d’axiomes exprimant des propriétés de la structure . C’est uniquement ces propriétés qui sont utilisées pour résoudre des contraintes,
mais ces propriétés sont utilisées au mieux. Lorsque le programmeur donne une contrainte à résoudre à Prolog IV il s’attend à ce que le système lui retourne une contrainte équivalente à dans la structure c’est-à-dire ayant les mêmes solutions que dans la structure mais dont les solutions sont plus «visibles ». Notamment il aimerait que Prolog IV retourne la contrainte false si n’a pas de solutions dans . En fait la contrainte retournée sera non seulement équivalente à dans la structure mais dans toutes les structures ayant les propriétés , ce qui s’écrit et ne sera false que si, non seulement elle n’a pas de solutions dans la structure , mais si en plus elle n’a de solutions dans aucune des autres structures qui ont les propriétés , c’est-à-dire si false (3) Sémantiquement et en présence d’un programme le langage Prolog IV est vu comme la théorie . Le programme est donc un ensemble d’axiomes supplémentaires que l’on ajoute à . Chacun de ces axiomes définit la propriété essentielle d’une nouvelle relation nommée et est de la forme où est une formule n’ayant pas d’autres occurrences libres de variables que celles . Bien entendu tout est limpide si ne fait que contenir des relations et des opération de , mais dans le cas ou fait intervenir d’autres nouvelles relations et surtout la relation elle-même, on a à faire à des définitions récursives. La résolution d’une contrainte doit alors être vue comme le calcul d’une contrainte équivalent à dans la théorie c’est-à-dire telle que Plan de l’exposé
Cette introduction constitue la partie 1 de notre exposé. La partie 2 est consacrée à des définitions purement logiques et notamment à ce que nous entendons par une contrainte, une structure, etc. C’est un petit cours de logique taillé sur mesure. La partie 3 décrit en détail la structure choisie . La partie 4 est consacrée à l’axiomatisation de cette structure. La partie 5 décrit la notion de programme et la machinerie Prolog IV. Enfin la partie 6 donne des exemples divers de programmes

Syntaxe et sémantique

Objets sémantiques

Les seuls objets sémantiques dont nous aurons besoin sont les relations et les opérations. Quelques définitions précises et quelques commentaires s’imposent ici. Soit un ensemble et un entier non négatif.
Une relation est un sous-ensemble quelconque de . On dit que est une relation d’arité dans. Du fait qu’une relation est vue comme un ensemble de -uplets, tous de même longueur, l’ensemble vide est une relation qui a pour arité n’importe quelle entier non négatif.
Une opération est une application de dans . On dit que est une opération d’arité dans. Il est commode de considérer les opérations comme des cas particuliers de relations ; pour ceci on confond l’opération -aire avec la relation -aire

Objets syntaxiques

Les seuls objets syntaxiques dont nous aurons besoin sont les termes et les formules. Les termes servent à représenter des éléments d’un domaine et les formules servent à représenter des propriétés de ces éléments.
On se donne une bonne fois pour toute un ensemble universel infini de symboles de variables 3 pour représenter des individus pris dans un domaine. On se donne en plus des ensembles de symboles d’opérations et de relations.
A chacun de ces symboles est associé un entier positif ou nul, son arité.
Les termes sont des expressions de l’une des deux formes :
avec , et d’arité et les des termes plus courts que ceux que l’on est train de définir. Les notations sont celles qui sont le plus couramment utilisées. Dans la colonne de droite nous donnons un aperçu de la notation Prolog IV de chaque forme.
3. Rappelons que la grande trouvaille de la norme ISO, à laquelle nous nous conformons dans la
syntaxe de Prolog IV, est de noter ces variables par des identificateurs commençant par une
lettre majuscule !
Les formules sont des expressions de l’une des 11 formes
1 true true
2 false false
3 , =
4 ( , , )
5 ( , )
6 ( ; )
7 ex
où les sont des termes, un symbole de d’arité et des formules plus courtes que celles que l’on est train de définir. Dans la colonne de droite nous donnons toujours, pour chaque forme, un aperçu de la notation Prolog IV, quand elle existe. Une occurrence de variable dans une formule est dite liée si elle se produit à l’intérieur d’une formule de la forme 7 ou 11 figurant dans . Une occurrence qui n’est pas liée est dite libre. Une formule qui ne contient aucune occurrence libre de variable est une proposition.
Nous réservons le mot contrainte pour désigner des formules existentielles positives, c’est-à-dire ne faisant intervenir que les 7 première formes. Une contrainte ou formule atomique est une formule de la forme 1, 2, 3 ou 4.

Liens entre objets syntaxiques et objets sémantiques

Si l’on donne une signification à chaque symbole qui figure dans un terme ou dans une formule on pourra systématiquement étendre ces significations pour attribuer une signification à tout le terme où toute la formule. C’est cette extension de signification que nous allons préciser. On appelle interprétation toute application qui fait correspondre
– à chaque variable , un élément d’un ensemble ,
– à chaque symbole d’opération d’arité , une opération -aire dans le même ensemble ,
– à chaque symbole de relation d’arité , une relation -aire dans le même ensemble .
L’ensemble commun est appelé domaine de et sera noté dom , l’ensemble des symboles d’opérations interprétés par est noté op et l’ensemble des symboles de relations interprété est noté rel L’interprétation est donc l’objet mathématique qui attribue une signification à chaque symbole de . Cette interprétation ce prolonge en une application qui attribue à chaque terme construit sur un élément de dom et à chaque formule construit sur une valeur de vérité prise dans vrai faux comme suit.

Introduction 
1 Tutoriel et Survol de Prolog IV 
1.1 Une session prolog sous Prolog IV
1.2 D’autres exemples, avec des contraintes !
1.3 L’environnement de programmation
1.4 De Prolog III à Prolog IV
2 Les Bases de Prolog IV
2.1 Introduction
2.2 Syntaxe et sémantique
2.3 La structure de base
2.4 Axiomatisation de
2.5 Structures enrichies
2.6 Exemples de programmes en Prolog IV
3 Relations Prolog IV
3.1 Introduction
3.2 Liste alphabétique
4 Prédicats prédéfinis Prolog IV 
4.1 Préliminaires
4.2 Liste alphabétique
5 Prédicats prédéfinis ISO 
5.1 Introduction
5.2 Préalables
5.3 Liste alphabétique
6 Syntaxe de Prolog IV 
6.1 Mini-glossaire
6.2 Les modes d’utilisation de Prolog IV
6.3 La logique dans Prolog
6.4 Les objets du langage
6.5 Lecture de règles et de requêtes
7 La syntaxe complète de Prolog ISO 
7.1 Notations
7.2 Textes et données Prolog
7.3 Termes
7.4 Unités lexicales
7.5 Caractères du processeur
7.6 Table des codes des caractères
7.7 Lexique
8 Environnement 
8.1 Les options de lancement
8.2 Interruption utilisateur
8.3 Compilation des règles
8.4 Le débogueur Prolog IV
9 L’environnement graphique de Prolog IV 
9.1 Lancement de Prolog IV
9.2 Configuration initiale
9.3 Le panneau principal
9.4 La console Prolog IV
9.5 La Console Tcl/Tk
9.6 Les Editeurs
9.7 Le Débogueur
9.8 Dialogues
9.9 Clavier et souris
9.10 Informations diverses
9.11 Primitives graphiques
9.12 Quelques Problèmes et limitations