PROLOG II+

 

 

 

Version 4.7

 

 

 

 

 

 

 

 

Novembre 2000


Introduction

Standardisation

Performances

Modularité

Ouverture vers l'extérieur

Environnement de programmation

Interface graphique

Sur ce Manuel

Garantie et responsabilités

Droits d'auteur

0.    Débuter avec Prolog

0.1.  Leçon 1 :  Lancement de Prolog

0.2.  Leçon 2 :  Utilisation d'un programme d'exemple

0.3.  Leçon 3 :  L'Editeur

0.4.  Les erreurs les plus courantes

0.4.1.   Débordement de l'espace de code.

0.4.2.   Interruption.

0.4.3.   Erreurs détectées en cours d'insertion.

0.4.4.   Erreurs concernant les fichiers.

0.4.5.   Erreurs de syntaxe.

0.4.6.   Erreurs d'exécution.

1.    Eléments de base

1.1.  Notations utilisées

1.2.  Jeu de caractères

1.3.  Les variables

1.4.  Constantes

1.5.  Termes et arbres

1.6.  Les opérateurs

1.7.  Les règles et les assertions

1.8.  Les mécanismes de base de Prolog

1.9.  La syntaxe complète de Prolog II+

1.9.1.   Le niveau syntaxique

1.9.2.   Les opérateurs

1.9.3.   Le niveau lexical

1.9.4.   Les caractères

1.9.5.   Les caractères accentués

1.10.             Le macroprocesseur

2.    Le contrôle de l'effacement des buts

2.1.  Le contrôle

2.2.  Geler

2.3.  A propos des arbres infinis

2.4.  Quelques conseils pour la programmation récursive

2.5.  Les meta-structures

2.5.1.   Création

2.5.2.   Récupération

2.5.3.   Unification forcée

2.5.4.   Sorties

2.5.5.   Exemple

3.    Structuration des règles et modification

3.1.  Introduction

3.1.1.   Qualification des prédicats

3.1.2.   Qualification des foncteurs

3.1.3.   Simplification des notations

3.1.4.   Quelques règles simples d'utilisation

3.1.5.   Modules et préfixes standard

3.2.  Terminologie

3.3.  Syntaxe des identificateurs

3.3.1.   Paramétrage de l'écriture d'un identificateur complet

3.4.  Contexte de Lecture et Ecriture

3.4.1.   Lecture

3.4.2.   Ecriture

3.4.3.   Notation simplifiée de la suite d'identificateurs d'un contexte

3.4.4.   Notation en Prolog

3.4.5.   Primitives pour les contextes et les familles d'identificateurs

3.5.  Modules

3.5.1.   Définition d'un module

3.5.2.   Module source

3.5.3.   Module Objet

3.6.  Résumé ou Approche simplifiée des identificateurs,  contextes et modules

3.6.1.   Identificateurs

3.6.2.   Notation abrégée et contextes

3.6.3.   Modules

3.7.  Ajout, suppression et recherche de règles

3.8.  Manipulation des modules compilés

4.    Opérations prédéfinies sur les données

4.1.  Les tests de type

4.2.  Les opérations arithmétiques

4.3.  Affectation

4.4.  Opérations sur les chaînes

4.5.  Composition et décomposition d'objets

4.6.  Comparaison de termes quelconques

5.    Les entrées / sorties

5.0.  Généralités

5.1.  Entrées

5.1.1.   Règles pour l'entrée.

5.1.2.   Modification de l'unité d'entrée.

5.2.  Sorties

5.2.1.   Règles pour la sortie

5.2.2.   Modification de l'unité de sortie

5.3.  Chargement et adaptation du module de dessin

5.4.  Déclaration d'opérateurs

6.    L'environnement

6.1.  Comment sortir de Prolog

6.2.  Démarrage automatique d'un programme Prolog

6.3.  Edition de programmes

6.3.1.   Modifier des paquets de règles

6.3.2.   Editer et recompiler un module source

6.3.3.   Editer un fichier de texte quelconque

6.4.  Date, temps et mesures

6.5.  Lien avec le système

6.6.  Outil de mise au point de programmes

6.6.1.   Mode trace

Activation, désactivation

6.6.2.   Mode interactif

6.6.2.1. Points d'arrêt

6.6.2.2. Progression dans le code

6.6.2.3. Terminer l'exécution

6.6.2.4. Affichage des informations

6.6.2.5. Informations annexes sur l'exécution

6.6.2.6. Configuration

6.6.3.   Activation d'un mode de mise au point

6.6.4.   Gestion des points d'arrêt

6.6.5.   Commandes du mode interactif

6.6.6.   Exemple

6.7.  Modification et visualisation de l'état courant

6.8.  Gestion automatique des espaces et des piles

7. Extensions de Prolog avec des langages externes.

7.1.  Principes des fonctions de communication de données

7.2.  Fonctions de communication de données simples

7.2.1.   Test du type d'un argument

7.2.2.   Transfert de données simples de Prolog vers un autre langage.

7.2.3.   Transfert de données simples d'un langage externe vers Prolog

7.3.  Fonctions de communication de termes quelconques

7.3.1.   Au moyen de chaînes de caractères

7.3.2.   Au moyen de structures de tableaux

7.3.2.1. Description du codage d'un terme

7.3.2.2. Identificateurs

7.3.2.3. Description des fonctions de communication

7.4.  Principe de la méthode des descripteurs

7.4.1.   Eléments descriptifs

7.4.2.   Déclaration statique

Table de descripteurs

7.4.3.   Déclaration dynamique

7.5.  Données partagées

7.5.1.   Exemple de zone commune de données

7.6.  Ajout de fonctions externes

7.6.1.   Exemple de déclaration de règle prédéfinie

7.7.  Ajout de fonctions externes à appel direct

7.7.1.   Primitive CallC

7.7.2.   Conventions Prolog pour la communication des données

7.7.2.1. Convention pour des paramètres sans valeur de retour

7.7.2.2. Convention pour le retour de la fonction

7.7.2.3. Convention pour des paramètres avec valeur de retour

7.7.3.   Exemple : méthode simple pour appeler une fonction C

8. Lancement d'un but Prolog par un programme C

8.1.  Principes de base

8.2.  Initialisation et terminaison de Prolog

8.3.  Empilement d'un but Prolog

8.4.  Programmation

8.5.  Méthode simple d'appel d'un but Prolog

8.5.1.   Description

8.5.2.   Exemple

8.6.  Autres fonctions

9.    Interruptions

9.1.  Concepts

9.2.  Description des interfaces

Conventions pour l'appel de la fonction d'activation event_handler.

Prototypes des fonctions d'interface

9.3.  Exemple complet

10.  Extensions Edinburgh

10.1.  Syntaxe

10.1.1.  Généralités

10.1.2.  Les opérateurs

10.2.  Le contrôle

10.3.  Manipulation des règles

10.4.  Opérations prédéfinies sur les données

10.4.1.  Les tests de type

10.4.2.  Les opérations arithmétiques

10.4.3.  Composition et décomposition d'objets

10.4.3.  Comparaison de termes quelconques

10.5.  Les entrées / sorties

10.5.1.  Généralités

10.5.2.  Entrées

10.5.2.1. Interprétation des chaînes de caractères

10.5.2.2. Prédicats

10.5.3.  Sorties

10.6.  L'environnement

10.7.  Traduction de DCG

Avant-Propos

1. Guide d'installation sur UNIX

1.1.  Matériel et logiciel requis

1.2.  Contenu du kit d'installation

1.2.1.   Fichiers indispensables pour utiliser Prolog

1.2.2.   Fichiers annexes pour l'utilisation de Prolog

1.2.3.   Fichiers pour ajouter des extensions à Prolog

1.2.4.   Fichiers d'exemples

1.2.5.   Conventions pour les suffixes des fichiers

1.3.  Procédure d'installation

1.4.  Modification de l'environnement d'exécution

1.4.1    Variables d'environnement

1.4.2    Fichier de configuration graphique

2. Utilisation de Prolog II+ UNIX Standard

2.1. Lancement et arrêt de Prolog

2.1.1. Activation, fichiers par défaut

2.1.2. Arrêt de Prolog

2.2. Espaces et tailles par défaut

2.3. Syntaxe de la ligne de commande

2.4. Création et exécution d'un programme

2.5. Interruption d'un programme

2.6.  Construction et lancement de Prolog avec graphisme

2.7.  Compilation et édition de liens

prolink

3. Spécificités de Prolog II+ UNIX Standard

3.1. Valeurs extrêmes des constantes arithmétiques

3.2. Les caractères dans la syntaxe Prolog II+

3.3.  Chargement dynamique de programmes externes

4. Coprocessus

4.1.  Principe

4.2.  Utilisation en Prolog

4.3.  Exemple d'utilisation

5.    Primitives Graphiques

5.1.  Description du système graphique

5.1.1.   Evénements

5.1.2.   Objets graphiques

5.1.3.   Configuration du graphique Prolog II+ au démarrage

5.1.4.   Conventions utilisées dans ce chapitre

5.2.  Primitives de gestion des fenêtres

5.2.1.   Création, destruction d'une fenêtre

5.2.2.   Configuration, manipulation d'une fenêtre

5.2.3.   Rafraîchissement des zones graphiques

5.3.  Primitives élémentaires de gestion des objets attachés à une fenêtre

5.3.1.   Création, destruction d'objets

5.3.2.   Configuration d'objets

5.3.3.   Gestion des événements

5.4.  Primitives spécifiques pour la gestion de menu

5.4.1.   Sauvegarde et changement de la barre de menu

5.4.2.   Description d'un menu

5.5.  Mode de dessin et d'écriture

5.6.  Dessin et positionnement

5.7.  Position de la souris dans une zone graphique

5.8.  Primitives spéciales de saisie

5.8.1.   Simulation de boutons

5.8.2.   Affichage de message avec validation

5.8.3.   Saisie de texte

5.8.4.   Boites de choix

5.8.5.   Choix de fichier

5.8.6.   Choix d'un noeud d'un arbre

5.9.  Règles pour gérer des objets structurés

5.10. Envoi d'événements à Prolog depuis un objet externe

Annexe A Différences Prolog II+ / Norme

A.1  Niveau général

Portée de la coupure dans un méta-appel

Les chaînes de caractères

Préfixage des identificateurs

Vue logique et vue immédiate

Les n-uplets

A.2  Fonctionalités non implantées

A.3  Fonctionalités restreintes

Annexe B Liste des directives et prédicats prédéfinis

1      Directives de compilation

2      Prédicats

A

B

C

D

E

FGH

IK

L

MN

OPQ

R

S

TUVW

Autres

Annexe C              Quelques exemples

de programmes Prolog II+

C.1. Les grammaires

C.1.1.  Représentation de la grammaire en Prolog

C.1.2.  Mise en évidence de la structure profonde

C.2. Dérivation formelle

C.3. Les mutants

C.4. Interrogation par évaluation d'une formule logique

C.5. Un casse-tête

C.6. Construction d'un chemin

C.7. Les arbres infinis

Annexe D ajout de règles externes

(méthode des parasites)

D.1. Description générale

D.2. Règle Prolog réalisant l'interface

D.3. Appel du programme externe

D.4. Comment provoquer un backtracking ou renvoyer une erreur

Annexe E Prolog II+ et les caractères.

E.1.  Présentation

E.2.  Jeu ISO : avantages et inconvénients

E.3.  Jeu hôte : avantages et inconvénients

E.4.  Remarques

E.5.  Conventions pour le mode ISO

Annexe F Table ISO 8859-1




 

 

 

 

 

PROLOG II+

 

 

 

 

 

 

 

 

 

 

Manuel dE REFERENCE

 


Introduction

Les besoins des utilisateurs de l'Intelligence Artificielle évoluent. En devenant industriels, les programmes sont de plus en plus gros, manipulent d'importantes quantités de données, communiquent avec d'autres logiciels.

Pour répondre à cette demande, PrologIA propose un nouveau système PrologII+. Tout en conservant les caractéristiques qui ont fait le succès de Prolog II, les plus  offerts par ce produit sont:

 

                           performances

                           modularité

                           standardisation

                           ouverture vers l'extérieur

                           environnement de programmation

                           interface graphique

Standardisation

                 Choix d'un Mode standard s'inspirant fortement des dernières décisions des groupes de normalisation, pour la norme ISO-Prolog.

Performances

                 Compilation incrémentale parfaitement transparente, permettant de bénéficier de la vitesse d'un langage compilé sans avoir à renoncer à la souplesse d'un langage interpreté.

                 Optimisation de la récursivité terminale, permettant de programmer récursivement, c'est à dire de la manière la plus naturelle en Prolog, les processus itératifs, et cela sans débordement de la mémoire. 

                 Récupération dynamique de mémoire (garbage collector) dans les espaces de travail de Prolog (piles, code, dictionnaire). Une technique nouvelle nous permet une récupération plus performante.

                 Réallocation dynamique des espaces de travail de Prolog.

                 Compilation très optimisée de certaines règles prédéfinies et notam­ment des règles arithmétiques.

                 Entiers en précision infinie.

Modularité

                 Modularité: nouvelle notion, proposée pour le standard.

                 L'écriture de gros programmes est rendue possible grâce aux modules, compilés séparément, chargeables et déchargeables à volonté.

                 Run-time permettant de diffuser des applications autonomes.

Ouverture vers l'extérieur

                 Liens bidirectionnels avec les autres langages : possibilité d'appeler en Prolog des sous-programmes écrits dans d'autres langages. Possibilité d'appeler, depuis un programme quelconque, un programme écrit en Prolog (y compris avec l'obtention successive de différentes solutions). Tous les cas de figure d'appels croisés sont désormais pris en charge.

                 Communication avec d'autres applications.

                 Structures de données entièrement ouvertes, avec l'interface requis pour la communication inter-langage de tous les types de données, sans restriction sur la nature des termes (qui, par exemple, peuvent comporter y compris des varia­bles et des identificateurs). Possibilité de partager des zones communes (tableaux) avec d'autres programmes.

                 Interface SQL entre Prolog et les SGBD.

                 Manipulation de bases de faits conséquentes.

                 Données numériques (entiers et réels) homogènes avec les autres langages supportés par le système hôte, y compris pour leurs repré­sentations étendues.

Environnement de programmation

                 Manipulation de règles (assert, clause/rule, list  etc…) intégrée au compi­lateur et fonctionnant sur les règles compilées. 

                 Récupération d'interruptions asynchrones en Prolog II+ autorisant, par exemple, la gestion d'environ­nements fortement interactifs (souris, fenêtres, etc…). 

                 Debugger de haut niveau permettant une mise au point rapide des gros programmes.

                 Editeur intégré couplé avec la compilation incrémentale.

Interface graphique

                 Bibliothèque portable entre divers environnements.

                 Définition d'objets: fenêtres, menus, boutons, ….

                 Composition de dessins.

                 Gestion de dialogues.


Sur ce Manuel

La documentation concernant PROLOG II+ a été regroupée en deux manuels. Le premier, le Manuel de référence, décrit de manière précise le langage et son utilisation. Ce manuel est valable (en principe) pour toutes les implantations. Le second, le Manuel d'utilisation, décrit tout ce qui est dépendant d'un ordinateur et d'un système d'exploitation spécifique. Il y aura donc un manuel d'utilisation par matériel.

Pour installer le logiciel Prolog II+ et l'utiliser, voir les chapitres 1 et 2 du manuel utilisateur.

Le manuel de Référence commence par une introduction élémentaire à Prolog et son utilisation pratique. Dans le second chapitre, on présente de manière un peu plus théorique les bases de Prolog. Les chapitres suivants examinent les différentes règles prédéfinies concernant : le contrôle, la manipulation des règles, les opérations sur les données, les entrées-sorties, l'environnement, le debugger et l'éditeur. Les chapitres suivants concernent l'ouverture vers les autres langages : on décrit comment ajouter des règles prédéfinies écrites par l'utilisateur, faire des appels croisés ou déclarer des zones de données communes entre Prolog et d'autres langages, et intercepter des interruptions et déclencher un traitement Prolog. Enfin le dernier chapitre décrit la bibliothèque de primitives spécifiques à la syntaxe Edinburgh.

En plus de ce manuel, il y a une partie Annexe qui est valable pour toutes les implantations également. Elle détaille quelques points secondaires mentionnés dans le manuel de Référence. En particulier vous y trouverez les différences entre l'interpréteur Prolog II et le compilateur Prolog II+, ou bien quelques exemples de programmes pour illustrer l'utilisation de Prolog.

Le manuel d'Utilisation précise comment se réalisent de manière pratique sur votre ordinateur, certaines fonctions décrites dans le manuel de Référence. Cela concerne la structure des noms de fichiers, la gestion des états sauvés, l'utilisation de la mémoire et comment lancer Prolog. La seconde partie de ce manuel décrit ce qui est spécifique à cette version : ce qu'il y a en plus et en moins par rapport à la version de base, ainsi que les valeurs extrêmes des constantes.

 

Nous vous conseillons également de consulter les documents suivants :

Prolog

F. Giannnesini, H. Kanoui, R. Pasero, M. Van Caneghem,

InterEditions, Mars 1985.

Prolog, bases théoriques et développements actuels,

A. Colmerauer, H. Kanoui, M. Van Caneghem,

TSI vol 2, numéro 4, 1983.

Pour la programmation en syntaxe Edinburgh:

Prolog Programming for Artificial Intelligence.

Ivan Bratko, Addison-Wesley, International Computer Science Series, 1986.

 Garantie et responsabilités

PrologIA n'offre aucune garantie, expresse ou tacite, concernant ce manuel ou le logiciel qui y est décrit, ses qualités, ses perfor­mances ou sa capacité à satisfaire à quelque application que ce soit.

PrologIA ne pourra être tenue responsable des préjudices directs ou indirects, de quelque nature que ce soit, résultant d'une imperfection dans le programme ou le manuel, même si elle a été avi­sée de la possibilité que de tels préjudices se produisent. En particulier, elle ne pourra encourir aucune responsabilité du fait des données mémorisées ou exploitées, y compris pour les coûts de récupération ou de reproduction de ces données.

L'acheteur a toutefois droit à la garantie légale dans les cas et dans la mesure seulement où la garantie légale est applicable nonobstant toute exclusion ou limitation.

Droits d'auteur

Ce manuel et le logiciel qu'il décrit sont protégés par les droits d'auteur. Au terme de la législa­tion traitant de ces droits, ce manuel et ce logiciel ne peuvent être copiés ou adaptés, en tout ou en partie, sans le consentement écrit de PrologIA, sauf dans le cadre d'une utilisation normale ou pour faire une copie de sauvegarde. Ces exceptions n'autorisent cependant pas la confection de copies à l'intention d'un tiers, que ce soit ou non pour les vendre.

Prolog II est une marque déposée de PrologIA.





0.     Débuter avec Prolog

0.1.    Leçon 1 : Lancement de Prolog

0.2.    Leçon 2 : Utilisation d'un programme d'exemple

0.3.    Leçon 3 : L'Editeur

0.4.    Les erreurs les plus courantes

Dans les exemples de ce manuel, ce qui est écrit par l'utilisateur apparait en caractère penché, et tout ce qui est écrit par l'ordinateur apparait en caractère Télétype droit.

0.1.   Leçon 1 :  Lancement de Prolog

Lancez Prolog, ceci le fait démarrer à partir d'un état sauvé initial nommé initial.po. Le caractère ">" représente le prompt de Prolog. Les différentes possibilités de démarrage sont décrites dans le manuel d'Utilisation. Prolog affiche alors sur l'écran :

Prolog II+ Version...

Code : ... PrologIA

>

Le caractère ">" indique à l'utilisateur qu'il est sous Prolog et que le système est en attente de commande. Pour commencer, essayons une commande simple, imprimons le message "Hello World":

> out("Hello World") line;

"Hello World"

{}

>

Entrons maintenant un premier petit programme; pour cela on se met en mode insertion de règles (commande insert). Le système est alors prêt à lire des règles (ou des commentaires) et les enregistre en mémoire au fur et à mesure. Par exemple, on entre trois règles qui expriment que Pierre, Jean et Marie habitent respectivement à Paris, Marseille et Paris :

> insert;

habite_a(Pierre, Paris)->;

habite_a(Jean, Marseille)->;

habite_a(Marie, Paris)->;;

{}

>

Remarquez que chaque règle est terminée par le caractère ";" et que l'insertion se termine par un ";" supplémentaire. Les règles sont insérées dans l'ordre où on les a tapées. On s'en assure en tapant la commande  list (qui affiche les règles du module courant).

>list;

habite_a(Pierre, Paris)  -> ;

habite_a(Jean, Marseille) -> ;

habite_a(Marie, Paris) -> ;

 

{}

>

Faisons quelques essais avec ce programme : Où habite Pierre ? 

>habite_a(Pierre, x);

{x=Paris}

>

Qui habite à Paris ? 

>habite_a(x, Paris);

{x=Pierre}

{x=Marie}

>

Qui habite où ? 

>habite_a(x, y);

{x=Pierre, y=Paris}

{x=Jean, y=Marseille}

{x=Marie, y=Paris}

>

A chaque fois, la réponse du système est l'ensemble des valeurs à donner aux variables figurant dans la question pour que la relation correspondante soit satisfaite. Pour terminer la session, on tape la commande :

>quit;

Bye......

et on se retrouve sous l'interpréteur de commandes du système d'exploitation. 

0.2.   Leçon 2 :  Utilisation d'un programme d'exemple

Dans ce qui suit, on utilisera le programme menu.p2 qui se trouve décrit dans de nombreuses publications. Ce programme se trouve dans le répertoire d'exemples du Kit Prolog II+. Pour cette leçon, il vous faut au préalable recopier le fichier menu.p2 dans votre répertoire courant. Il suffit alors de lancer Prolog, puis insérer le fichier menu.p2 en tapant :

PROLOG II+ ...

> echo insert("menu.p2");

insert lit des règles sur le fichier spécifié et les insère dans le module courant. Lorsque le fichier d'entrée est épuisé, l'entrée courante bascule sur le clavier qui est l'unité d'entrée par défaut. La primitive echo réalise l'affichage à la console au fur et à mesure de la lecture du fichier:

" la carte "

hors_d_oeuvre(Artichauts_Mélanie) -> ;

hors_d_oeuvre(Truffes_sous_le_sel) -> ;

hors_d_oeuvre(Cresson_oeuf_poche) -> ;

viande(Grillade_de_boeuf) -> ;

viande(Poulet_au_tilleul) -> ;

poisson(Bar_aux_algues) -> ;

poisson(Chapon_farci) -> ;

dessert(Sorbet_aux_poires) -> ;

dessert(Fraises_chantilly) -> ;

dessert(Melon_en_surprise) -> ;

" plat de résistance"

plat(p) -> viande(p) ;

plat(p) -> poisson(p) ;

" composition d'un repas "

repas(e,p,d) -> hors_d_oeuvre(e) plat(p) dessert(d) ;

" valeur calorique pour une portion "

calories(Artichauts_Mélanie,150) -> ;

calories(Cresson_oeuf_poche,202) -> ;

calories(Truffes_sous_le_sel,212) -> ;

calories(Grillade_de_boeuf,532) -> ;

calories(Poulet_au_tilleul,400) -> ;

calories(Bar_aux_algues,292) -> ;

calories(Chapon_farci,254) -> ;

calories(Sorbet_aux_poires,223) -> ;

calories(Fraises_chantilly,289) -> ;

calories(Melon_en_surprise,122) -> ;

" valeur calorique d'un repas "

valeur(e,p,d,v)  ->

   calories(e,x)

   calories(p,y)

   calories(d,z)

   ajouter(x,y,z,v) ;

" repas équilibré "

repas_equilibre(e,p,d) ->

   repas(e,p,d)

   valeur(e,p,d,v)

   inferieur(v,800) ;

" divers"

ajouter(a,b,c,d) ->

   val(add(a,add(b,c)),d) ;

inferieur(x,y) -> val(inf(x,y),1) ;

{}

>

Faisons quelques essais avec ce programme. La question : «Quels sont les plats ?» se traduit par :

>plat(p);

{p=Grillade_de_boeuf}

{p=Poulet_au_tilleul}

{p=Bar_aux_algues}

{p=Chapon_farci}

Quels sont les hors-d'oeuvres ? 

>hors_d_oeuvre(x);

{x=Artichauts_Mélanie}

{x=Truffes_sous_le_sel}

{x=Cresson_oeuf_poche}

Cette leçon s'arrête là et on sauve le module courant "" (module avec le préfixe ""):

> save([""],"menu.mo") quit;

Bye........

Note: On peut utiliser également la commande exit: en sortant Prolog sauve l'état courant dans un fichier nommé par défaut prolog.po.

Le module sauvé nous servira dans la leçon suivante.

0.3.   Leçon 3 :  L'Editeur

Le but de cette leçon est de montrer une façon très simple de travailler avec l'éditeur intégré à Prolog, au niveau d'un paquet de règles. Sur les machines possédant un environnement fenêtrage et souris, l'utilisation de copier/coller peut être plus commode.

On commence par lancer Prolog et charger le module sauvé contenant le programme menu.p2 si l'on a sauvé avec save:

...

> load("menu.mo");

{}

>

Si l'on est sorti avec exit, on commence par lancer Prolog avec l'état sauvé prolog.po contenant le programme menu.p2 tel que nous l'avons laissé à la fin de la leçon précédente:

....

>

Supposons que l'on veuille changer notre menu, et remplacer les règles :

viande(Grillade_de_boeuf) -> ;

viande(Poulet_au_tilleul) -> ;

par :

viande(Veau_marengo) -> ;

viande(Poulet_roti) -> ;

Appeller l'éditeur par la commande :

> edit(viande/1);

où la notation viande/1 désigne le paquet de règles concernant la relation viande avec 1 argument.

L'éditeur est activé et montre les règles définissant la relation viande. Réaliser les modifications voulues, et sortir de l'éditeur normalement. Vérifiez que Prolog a bien relu les nouvelles définitions:

> list(viande/1);

viande(Veau_marengo) -> ;

viande(Poulet_roti) -> ;

{}

On exécute le programme modifié et on finit par quit puisqu'on ne désire pas conserver l'état courant.

> viande(p) ;

{p=Veau_Marengo}

{p=Poulet_roti}

> plat(p) ;

{p=Veau_Marengo}

{p=Poulet_roti}

{p=Bar_aux_algues}

{p=Chapon_farci}

> quit ;

Bye......

0.4.   Les erreurs les plus courantes

Voici quelques explications sur les erreurs les plus courantes qui peuvent se produire lors de l'utilisation de Prolog II+. 

0.4.1.  Débordement de l'espace de code.

•PAS ASSEZ DE PLACE POUR LE CODE
Il faut redémarrer Prolog avec un espace plus grand pour le code (option -c de la ligne de commande). Si le système de réallocation automatique n'est pas désactivé au démarrage de Prolog, un certain nombre de réallocations se produiront avant le débordement. Le code occupera alors toute la place disponible de la machine. Dans ce cas il faut, si c'est possible, augmenter la mémoire totale de Prolog ou bien vérifier le fonctionnement du programme, sans doute anormal.

0.4.2.  Interruption.

Un programme en cours d'exécution peut être interrompu à tout instant par un caractère d'interruption (<Control-C> <return> souvent).

> insert;

rr -> rr;;

{}

> rr;

<Ctrl-C>

INTERRUPTION UTILISATEUR

{}

>

0.4.3.  Erreurs détectées en cours d'insertion.

•REGLE DEJA DEFINIE      
Cette erreur provient du fait que l'utilisateur n'a pas respecté le principe suivant : Toutes les règles de même nom et de même arité doivent être consécutives (deux règles de même nom/arité ne peuvent être séparées ni par un commentaire, ni par une règle de nom/arité différent). Les configurations suivantes sont donc illégales ;

qq(x) -> ;

rr(y) -> ;

qq(z) -> ;

car la règle rr est mal placée.

ATTENTION: cette erreur ne se produira pas si vous utilisez les primitives reinsert ou insertz. En effet reinsert écrase le paquet de règles existant par sa nouvelle définition et insertz complète le paquet de règles. En particulier, en utilisant reinsert dans le cas décrit ci-dessus, il n'y aura aucune erreur et le paquet de règles d'accés qq contiendra une seule règle, la dernière.

0.4.4.  Erreurs concernant les fichiers.

•FIN DE FICHIER    
Ce message  signale que la lecture du fichier d'entrée est terminée. C'est plutôt un avertissement qu'un message d'erreur. L'entrée bascule alors automatiquement sur le clavier.

•ERREUR D'OUVERTURE DU FICHIER D'ENTREE

Ce message signale que le fichier n'existe pas, ou qu'il est inaccessible. Il suffit de refaire la commande après avoir apporté les corrections nécessaires.

0.4.5.  Erreurs de syntaxe.

La plupart des erreurs de syntaxe sont suffisamment explicites pour qu'on voit tout de suite de quoi il s'agit. Il suffit de se reporter à la syntaxe (Chapitre 1) pour avoir des explications complémentaires. Cependant, certaines d'entre elles méritent un commentaire :

•UNITE MAL PLACEE

> insert;

plat(x) -> viande(, boeuf) ;;

 

-> "," : UNITE MAL PLACEE

Cette erreur montre que la syntaxe n'a pas été respectée. Dans cet exemple, il manque un argument.

•IL MANQUE " A LA FIN DE LA CHAINE

> insert;

viande("boeuf)

 

-> MANQUE " A LA FIN DE LA CHAINE.

Une chaîne doit tenir sur une ligne, si la fin de ligne n'est pas masquée. On rappelle qu'une chaîne commence et finit sur le caractère("). Si le caractère fait partie de la chaîne, il doit être doublé.

•CE TERME NE PEUT PAS ETRE UNE TETE DE REGLE

> insert;

p(x) -> ;;

 

-> v41(v60) : CE TERME NE PEUT PAS ETRE UNE TETE DE REGLE

Le seul accès légal à une règle est un identificateur (il commençe par deux lettres en syntaxe Prolog II). En particulier, l'accès ne peut être une variable (dont le nom commence par une seule lettre en syntaxe Prolog II), ni un nombre, ni une chaîne.

On rappelle, pour la syntaxe Prolog II, qu'un nom de variable, de relation, ou de constante est une suite de mots séparés par un "_" et éventuellement suivie d'apostrophes. Un mot est constitué d'une ou plusieurs lettres éventuellement suivies de chiffres. Si le premier mot du nom commence par au moins deux lettres, on a affaire à un nom de relation ou de constante (ce qu'on appelle un identificateur), ce qui constitue un accès légal à une règle. Dans le cas contraire on a affaire à une variable. Par exemple :

x, x12, x_toto_a25, a', a12'', b_titi''

sont des noms de variables.

bonjour, xx'', qq_toto_25, comment_allez_vous, 'avec des blancs'

sont des noms de relations ou de constantes.

•LITTERAL INCORRECT

> insert;

humain(x) ->

  homme(x)

humain(x) -> femme(x);

 

-> LITTERAL INCORRECT

skipping:  femme(x);

Lorsqu'une telle erreur se produit au niveau de la flèche Prolog, il s'agit très souvent de l'oubli du ";" à la fin de la règle précédente.

0.4.6.  Erreurs d'exécution.

•CE TERME NE PEUT ETRE UN BUT

Voici un exemple qui utilise la règle :  exec(p)  -> p ;

> exec(outm("bonjour"));

bonjour{}

>

La variable p de la règle exec est remplacée par outm("bonjour") qui est effacé sans problème. En revanche :

> exec(x);

-> CE TERME NE PEUT ETRE UN BUT

 

>

provoque une erreur car la variable p reste libre au moment où on tente de l'effacer.

•ARGUMENT DE MAUVAIS TYPE

Cette erreur survient lorsque l'on essaie d'effacer une règle prédéfinie avec un des arguments qui n'est pas du type attendu. Généralement l'argument qui est en cause est affiché avec le message.

•APPEL A UNE REGLE NON DEFINIE

On essaye d'effacer une règle qui n'est pas définie alors qu'on est en mode erreur (flag uE). Notez que pour faire échouer volontairement l'exécution, il faut appeler la règle prédéfinie fail.

Il existe plusieurs comportement possibles, pilotés par un flag dans la commande de lancement de Prolog, pour l'effacement d'un prédicat non défini:

uW :         affiche un warning et continue l'exécution du programme,

uF : échoue,

uE : génère l'erreur.

 

Les autres erreurs d'exécution concernent principalement l'utilisation des primitives block, block_exit et de val. En général les diagnostics sont suffisamment explicites.

Il est conseillé de lancer Prolog avec l'option -f uE qui permet d'avoir un diagnostic précis lors de l'appel erroné d'une règle n'existant pas (à cause d'une faute de frappe par exemple). Lorsque l'on veut appeler une règle et avoir un échec lorsque celle-ci n'existe pas, tester d'abord sa présence avec current_predicate.



1.     Eléments de base

1.1.    Notations utilisées

1.2.    Jeu de caractères

1.3.    Les variables

1.4.    Constantes

1.5.    Termes et arbres

1.6.    Les opérateurs

1.7.    Les règles et les assertions

1.8.    Les mécanismes de base de Prolog

1.9.    La syntaxe complète de Prolog II+

1.10.  Le macroprocesseur

1.1.   Notations utilisées

Dans ce manuel nous utiliserons des règles hors contexte pour décrire la syntaxe de toutes les formules intervenant dans Prolog. La notation utilisée ici est la même que celle utilisée par la commission de normalisation de Prolog :

   Les symboles non terminaux sont représentés par des identificateurs et les terminaux sont entre doubles quotes "…".

   Le symbole "=" est choisi comme symbole de réécriture et une règle se termine par un ";". Les éléments d'un membre droit de règle sont séparés par des ",".

   Les accolades {…} représentent un nombre quelconque d'apparitions, éventuellement aucune, des éléments qu'elles encadrent.

   Les crochets […] signalent le caractère optionnel des éléments qu'ils encadrent.

   La barre verticale ...|... exprime l'alternative entre les éléments qu'elle sépare. Des parenthèses (...|...) sont utilisées lorsque le résultat de cette alternative apparaît dans une liste de symboles.

   Le signe "-" est utilisé pour représenter des exceptions.

   Certaines règles de réécriture dépendent des options de syntaxe sélectionnées : les règles dont le membre gauche est annoté par P ne sont actives que lorsque la syntaxe Prolog II est activée (par exemple separatorP). Les règles dont le membre gauche est annoté par E ne sont actives que lorsque la syntaxe Edinburgh est activée (par exemple graphic_charE).

   D'autres règles, annotées par une lettre, dépendent des options choisies au lancement de Prolog et ne sont valides que dans certains cas.

La totalité de la syntaxe de Prolog est donnée à la fin de ce chapitre. Des extraits plus ou moins simplifiés de cette syntaxe sont commentés dans les paragraphes suivants.

1.2.   Jeu de caractères

L'utilisateur peut choisir parmi deux jeux de caractères : celui défini par le code ISO 8859-1 (cf. Annexe), ou celui disponible sur la machine hôte (cf. Manuel Utilisateur). Dans ce manuel nous décrirons uniquement le jeu ISO. Le choix du jeu hôte aura pour effet de diminuer ou de grossir les sous-ensembles letter et graphic_char avec des caractères n'existant pas dans le jeu ISO (cf. U3-2).

Voici une description simplifiée (la description complète se trouve au paragraphe 1.9) du jeu de caractères nécessaires à Prolog :

letter = "A" | … | "Z" | "a" | … | "z"

             | "À" … "ß" - "¥" | "à" … "ÿ" - "÷"
letterI = "\", accent_escape ;

digit =   "0" | … | "9" ;
alpha = letter | digit | "_" ;

separator =                                  "("  |  ")"  |  "["  |  "]"  |  "{"  |  "}"  |
             "|"  |  "," ;

separatorP=                                 ";"  |  "."  |  "<"  |  ">"  ;

special_char=                              "%" | "'" | """ | "_" | "!" | "`" ;
special_charE=                             ";" ;

graphic_char =                            "#" | "$" | "&" | "*" | "+" | "-" | "/" | ":"
             | "=" | "?" | "\" | "@" | "^" |  "~"
             | NBSP[1] … "¿" | "¥" | "÷" ;
graphic_charE =                           "." | "<" | ">" ;

character =                                  letter | digit | separator |                                      graphic_char | special_char ;

Sans changer le sens de ce qui est écrit, on peut insérer des espaces n'importe où, sauf dans les constantes et les variables. On peut enlever des espaces n'importe où sauf dans les chaînes et sauf si cette suppression provoque la création de nouvelles constantes ou variables, par juxtaposition d'anciennes.

 

Il existe diverses manières d'introduire des commentaires dans les programmes. Du point de vue de la syntaxe, un commentaire équivaut à un blanc et peut figurer partout où un blanc est permis :

• Le caractère "%" indique le début d'un commentaire qui s'étend depuis le "%" jusqu'à la fin de la ligne où ce commentaire apparaît.

• Les symboles "|*", "*|" et "/*", "*/" servent aussi à définir des com­men­taires, constitués par ces symboles et la suite des caractères qu'ils encadrent.

On ne doit pas mélanger ces symboles : un commentaire commençant par "|*" doit se terminer par "*|" et un commentaire commençant par "/*" doit se terminer par "*/". D'autre part, on peut imbriquer de tels commentaires; par exemple, le texte suivant sera vu comme un unique commentaire :

|*  second com-  |*  premier commentaire  *|  mentaire  *|

• Une chaîne de caractères écrite au niveau supérieur, c'est-à-dire là où une règle est attendue, possède aussi la valeur d'un commentaire.

1.3.   Les variables

Les variables servent aussi bien à désigner des constantes que des entités plus complexes. En voici la syntaxe :

variable =                         "_" , {alpha} ;
variable =                         extended_var ;

extended_var P =              letter, [ (digit | "_"), {alpha} ] , { "'" } ;
extended_var E =              big_letter, [ {alpha} ] ;

Il y a donc, pour les variables, une syntaxe de base et une syntaxe étendue à choisir parmi deux : la syntaxe Prolog II et la syntaxe anglaise. On doit indiquer si l'on désire une syntaxe différente de la syntaxe étendue Prolog II, au moment du lancement de Prolog II+; de plus, puisque ces deux syntaxes de variables sont incompatibles[2], on ne peut pas avoir les deux extensions en même temps.

Voici quelques exemples de variables correctes :

Syntaxe Prolog II                                                      Syntaxe Edinburgh

x                                                                X

x'  X_12_plus

x' '                                                             Prix

x12                                                            _prix

p_rix                                                         X1Y2

y33'                                                           _33

y_en_a'

_prix

_123

et quelques exemples d'expressions qui ne sont pas des variables cor­rectes :

Syntaxe Prolog II                                                      Syntaxe Edinburgh

ph X'

xx x12

prix                                                           prix

1er_x                                                        y_en_a

1.4.   Constantes

Les données les plus simples sont des constantes. Elles peuvent être de quatre types : les identificateurs, les nombres entiers, les nombres réels, et les chaînes de caractères.

identifier =                                   prefix , prefix_limit , abbreviated_id ; 
identifier =                                   abbreviated_id ;

identifierE =                                  prefix , prefix_limit ,
                                                   "'", graphic_symbol, "'" ; 
identifierE =                                  graphic_symbol ;

abbreviated_id =                         name - extended_var ;
abbreviated_id =                         "'", { (character - "'") | "'""'" }, "'";

prefix_limit =                               ":" ;
prefix =                                       [ name , { prefix_limit , name } ] ;

name = letter , { alpha } ;

integer_number =                         digits ;
integer_number =                         "0b", binary_number ;
integer_number =                         "0o", octal_number ;
integer_number =                         "0x", hex_number ;
integer_number =                         "0'", character ;

real_number =                             digits, ".", digits, ("E"|"e"|"D"|"d"),
                                                   [ ["+"|"-"], digits];
real_numberS =                            digits, ".", digits, 
                                                   [ ("E"|"e"|"D"|"d"), [ ["+"|"-"],digits] ];

binary_number =                         binary_digit , { binary_digit } ;

octal_number =                           octal_digit , { octal_digit } ;

hex_number =                             hex_digit , { hex_digit } ;

digits =  digit , { digit } ;

string = """ , { quoted_char } , """ ;

quoted_char =                             character - ( """ | "\" | newline) | """" ;
quoted_chari0 =                           "\" ;
quoted_chari1 =                           "\", format_escape ;

format_escape =                          "b" | "f" | "n" | "r" | "t" | "\" | newline
                                                   | octal_digit, octal_digit, octal_digit
                                                   | ("x" | "X"), hex_digit, hex_digit ;

Identificateurs

Les identificateurs ont deux représentations externes : une représen­tation complète et une représentation abrégée. La première comporte un préfixe qui spécifie la famille dont l'identificateur fait partie; dans la représen­tation abrégée, le préfixe n'apparaît pas et il est supposé que certaines conventions de lecture-écriture précisent de manière non ambiguë quel est le préfixe de l'identificateur. Ces notions sont expliquées en détail au chapitre 3.

C'est la présence ou l'absence du caractère ":" qui distingue la représentation complète de la représentation abrégée d'un identificateur. Ce caractère peut être redéfini et remplacé par un caractère graphique, tel que le décrit le chapitre 3.

Les identificateurs complets suivants sont corrects et représentent tous des identificateurs différents:

data:peter                                   grammar:singular

x:peter                                         lexicon:name
sys:write                                      sys:env:files

:peter                                           grammar:plural

Note: La chaîne vide est un préfixe légal, l'identificateur :peter est donc correct syntaxiquement.

L'identificateur suivant n'est pas complet

peter

La syntaxe de la représentation abrégée des identifi­cateurs et celle des variables sont très voisines et, ensemble, définissent ce que dans beaucoup d'autres langages de pro­gram­mation on appelle «identificateur». Nous retiendrons que, dans la syntaxe Prolog II, les variables com­men­cent par une seule lettre ou par le caractère "_", tandis que les représentations abrégées d'identifi­cateurs commencent par au moins deux lettres. Dans la syntaxe Edinburgh, la différenciation se fait sur le premier caractère, qui doit être une lettre majuscule ou le caractère "_" pour représenter une variable ou bien une lettre minuscule pour représenter un identificateur en notation abrégée. Dans cette syntaxe, les représentations abrégées d'identifi­cateurs peuvent également être des suites de caractères graphiques.

Voici des exemples d'identificateurs abrégés corrects :

Syntaxe Prolog II                                                      Syntaxe Edinburgh

pomme                                                      i10

pomme'                                                     pomme

pomme12                                                  ***

                                                                  §

des exemples d'identificateurs incorrects :

Syntaxe Prolog II                                                      Syntaxe Edinburgh

x                                                                Pomme

1er_lapin                                                  1er_lapin

y_en_a                                                      pomme'

l'herbe

Nombres

La syntaxe des nombres en Prolog II+ est sensiblement la même que dans la plupart des langages de programmation.

Les nombres entiers sont signés et permettent de représenter, a priori, des valeurs quelconques. Plusieurs syntaxes d'entiers sont acceptées.

Un entier peut être exprimé dans les bases suivantes : 2, 8, 10, 16. Pour cela, la mantisse de l'entier sera préfixée respectivement par : 0b, 0o, 0, 0x. Par défaut une mantisse non préfixée sera considérée en base décimale. Les petits entiers, inférieurs à 256, pourront également être exprimés à l'aide du préfixe 0' suivi d'un caractère, la valeur de l'entier sera alors le code du caractère[3] . Par exemple, les expressions suivantes représentent des entiers :

Expression:                  Valeur:

0b110                         6

0o110                         72

0110                           110

0x110                         272

0'A                              65

On notera que, contrairement à d'autres langages, les nombres réels doivent comporter un exposant explicite : l'expression  -12.34  ne définit pas un nombre réel, mais une paire pointée formée des deux entiers -12 et 34. En revanche,
-12.34e0 est un réel correct. C'est le choix par défaut en syntaxe Prolog II, il est néanmoins possible, pour se ramener à une syntaxe standard, de le modifier par une option sur la ligne de commande au lancement de Prolog (cf. § 2.3 du manuel d'utilisation).

Les nombres réels sont codés en double précision, cela correspond au type double du standard IEEE 64 bits. La lettre introduisant l'exposant peut être une des suivantes : e, E, d ou D. On préférera toutefois e et E.

Chaînes de caractères

Les chaînes de caractères sont encadrées par des doubles quotes """. Tous les caractères imprimables peuvent figurer dans une chaîne sans précaution particulière, sauf le caractère """ qui doit être doublé et éventuellement le caractère "\" qui doit être doublé si l'interprétation de la lecture du "\" est active (cf. les options de comportement § U 2.3.); par exemple, la chaîne:

     "il faut traiter "" et \\ avec précaution"

est correcte.

De façon générale le caractère "\" ne doit pas forcément être doublé: lorsque l'interprétation de lecture du "\" est active (cf. § 2.3 du manuel d'utilisation), si avec les caractères qui le suivent, il forme une expression (séquence escape) représentant un autre caractère, il faut le doubler; dans tous les autres cas, il n'est pas utile de le doubler:

     "Utiliser \  suivi de RETURN pour ignorer une fin de ligne"

     "Les codes hexadécimaux doivent commencer par \\x"

Quand l'interprétation du "\" est active (règles annotées par i1), plusieurs expressions commençant par "\" permettent de représenter un caractère.

Les expressions suivantes permettent de spécifier certains caractères non imprimables dans la définition d'une chaîne :

\b  espace arrière (backspace)

\f  saut de page (form feed)

\n  saut à la ligne (newline). Lors de son écriture, ce caractère est, le cas échéant, remplacé par le(s) caractère(s) requis pour obtenir une nouvelle ligne sur l'unité de sortie.

\r  retour en début de ligne (carriage return)

\t  tabulation

D'autres expressions permettent de représenter des caractères qui n'existent pas sur la machine hôte (voir le paragraphe 1.9.5).

Au moyen du nombre qui est son code interne, tout caractère peut être spécifié dans une chaîne. Par exemple, les expressions "\033" et "\x1B" définissent toutes deux une chaîne composée de l'unique caractère dont le code est 27. Le caractère nul (i.e.: celui dont le codage interne est le nombre 0) ne doit pas figurer dans les chaînes de caractères.

Une chaîne de caractères peut s'étendre sur plusieurs lignes. Pour cela, le dernier caractère de chacune des lignes en question sauf la dernière doit être "\" ;  le "\" et le caractère de fin de ligne seront ignorés. Par exemple, l'expression

                        "ceci est une chaî\
                        ne sur deux lignes"

définit la même chaîne que "ceci est une chaîne sur deux lignes".

En Prolog, le type chaîne de caractère existe et une chaîne de caractères représente donc un objet de ce type. En syntaxe Edinburgh, une option de démarrage permet de définir l'interprétation syntaxique de cette unité lexicale, qui peut représenter un des termes suivants: un identificateur, une liste d'identificateurs d'une lettre, une liste d'entiers, une chaîne Prolog.

N.B. : En écrivant des programmes Prolog, il arrive qu'une donnée symbolique puisse être représentée soit par une chaîne de carac­tères, soit par un identificateur. Les identificateurs étant eux-mêmes codés sous forme d'entités atomiques, on admet généralement qu'ils constituent une représentation des objets symboliques plus efficace que les chaînes.

1.5.   Termes et arbres

Toutes les données manipulées en Prolog sont des arbres éventuellement infinis dont nous allons tout d'abord donner une description informelle. Ces arbres sont formés de nœuds étiquetés :

   soit par une constante et, dans ce cas, ils n'ont aucun fils,

   soit par le caractère "point" et, dans ce cas ils ont deux fils,

   soit par "<>" ou"<->" ou "<-->" ou "<--->" ou… et, dans ce cas, le nombre de traits d'union correspond au nombre de leurs fils.

La figure suivante présente deux exemples d'arbres finis : 

 

                             <--->            

  / \                        /  |  \           

"a"                     ___/   |   \___       

    / \                 /       |       \      

  "b"              plus      <--->      <---> 

      / \                     / | \      / | \ 

    "c"  nil              fois  5  8 fois  5  8

Figure 1.1

 

La figure 1.2 est un exemple d'arbre infini :

 

   <--->                                         

  /  |  \                                        

ou  "c"  <--->                                   

        /  |  \                                  

      et  "a"  <--->                             

              /  |  \                            

            et <---> "b"                         

              /  |  \                            

            ou  "c"  <--->                       

                    /  |  \                      

                  et  "a"  <--->                 

                          /  |  \                

                        et <---> "b"             

                          /  |  \                

                        ou  "c"  <--->           

                                /  |  \          

                              et  "a"  <--->     

                                      /  |  \    

                                    et <---> "b" 

                                      /  |  \    

Figure 1.2

 

Remarquons que le dessin des arbres peut être allégé comme le montre la figure 1.3.

 

 identificateur         au lieu de    <---  . . .   --->    

 /   |    |   \                       /   |    |    |   \    

x1   x2  ...   xn         identificateur   x1   x2  ...   xn  

Figure 1.3

 

Bien entendu cette simplification présuppose que n ne soit pas nul. Les deux derniers arbres peuvent alors être représentés sous la forme classique de :


 

      plus                 ou                 

     /    \               /  \                

 fois      fois        "c"    et              

 /  \      /  \              /  \             

5    8    5    8          "a"    et           

                                /  \          

                              ou    "b"       

                             /  \             

                          "c"    et           

                                /  \          

                             "a"    et        

                                   /  \       

                                 ou    "b"    

                                /  \          

                             "c"    et        

                                   /  \       

                                "a"    et     

                                      /  \    

                                    ou    "b" 

                                   /  \       

Figure 1.4

 

 

 

 

La notion d'arbre infini est suffisamment inhabituelle pour que nous nous étendions un peu dessus. Intuitivement un arbre est infini s'il possède une branche infinie. Nous nous intéresserons plus spécialement à la fraction des arbres infinis qui ensemble avec les arbres finis forme les arbres dits rationnels : c'est à dire les arbres qui ont un nombre fini de sous-arbres. Si nous reprenons les deux derniers exemples d'arbres l'ensemble de leurs sous-arbres est décrit dans la figure 1.5.

 

 

{     <--->        ,         <---> , plus , fois , 5 , 8 }

     /  |  \_____            / | \                        

    /   |        \       fois  5  8                       

plus  <--->       <--->                                   

      / | \       / | \                                   

  fois  5  8  fois  5  8                                  

 

{  <--->,            <--->,             <--->, ou, et, "a","b","c"}

  /  |  \           /  |  \            /  |  \                      

 ou "c" <--->      et "a" <--->       t <---> "b"                   

       /  |  \           /  |  \       /  |  \                      

      et "a" <--->     et <---> "b"   ou "c" <--->                  

            /  |  \      /  |  \            /  |  \                 

          et <---> "b"  ou "c" <--->       et "a" <--->             

            /  |  \           /  |  \            /  |  \            

           ou "c" <--->      et "a" <--->      et <---> "b"         

Figure 1.5

 

Ces ensembles étant finis, il s'agit donc d'arbres rationnels. Le fait qu'un arbre rationnel contienne un ensemble fini de sous-arbres donne un moyen immédiat de le représenter par un diagramme fini : il suffit de fusionner tous les nœuds d'où partent les mêmes sous-arbres (figure 1.6).

 

Figure 1.6

 

Si on ne fait pas toutes les fusions on obtient la figure 1.7.

 

Figure 1.7

 

Il faut donc se méfier du fait que des diagrammes différents puissent représenter le même arbre.

Pour représenter les arbres nous utiliserons des formules appelées termes. Nous introduirons tout d'abord la notion de terme strict :

 

strict_term =                   variable | identifier | constant 
                                      | "[ ]"

                                      | "< >" ;

strict_termP =                 "(", strict_term , "." , strict_term , ")" ;

strict_termE =                 "[", strict_term , "|" , strict_term , "]" ;

strict_termP =                 "<", strict_term , { "," , strict_term } , ">" ;

strict_termE =                 "<>(", strict_term , { "," , strict_term } , ")" ;

Les termes stricts sont les "vrais" termes. Cependant pour des raisons de commodité on étend la syntaxe des termes stricts (sans en altérer le sens) en permettant :

P  d'ajouter et d'enlever des parenthèses mais en convenant que:
     t1.t2. … .tn représente (t1.(t2.( … .tn) … ))) ;

E  d'ajouter et d'enlever des crochets mais en convenant que:
     [t1,t2,…,tn] représente [t1 |  [t2  | …[tn  |  [] ] ]] et          
     [t1,t2,…,tn| t]
représente [t1 | [t2 | …[tn | t] ]];

   d'écrire id(t1, t2, … , tn) au lieu de <id, t1, t2, … , tn> à condition que id soit un identificateur et que n soit différent de 0.

Ceci conduit à une notion plus générale de terme :

aiment(Pierre.Paul.Jean.nil, pere_de(x))

et le terme strict correspondant est :

<aiment, (Pierre.(Paul.(Jean.nil))), <pere_de, x>>

Pour transformer un terme en un arbre il faut affecter ses variables par des arbres, d'où la notion d'affectation sylvestre, qui est un ensemble X de la forme :

X = { x1 := r1, x2 := r2, … }

où les xi sont des variables distinctes et les ri des arbres. Nous introduirons aussi la notation suivante : si r1, r2 sont des arbres et si r1, r2, … , rn est une suite de n arbres alors (r1.r2) et <r1, r2, … , rn> représentent respectivement les arbres suivants :

 

  •          <-- ... ->   

 / \        /  |       \  

r1  r2     r1  r2       rn

Figure 1.8

 

Si t est un terme strict faisant intervenir un sous-ensemble de l'ensemble des variables de l'affectation sylvestre X = { x1 := r1, x2 := r2, … } alors l'expression t/X désignera l'arbre obtenu en remplaçant les variables xi par les arbres correspondants ri. Plus précisément :

- t/X = ri  si  t = xi ;

- t/X = valeur de k si t est la constante k ;

- t/X = (t1/X . t2/X) si t = (t1 . t2) ;

- t/X = [t1/X | t2/X)] si t = [t1 | t2] ;

- t/X =<t1/X, … , tn/X> si t = <t1, … , tn>.

- t/X =<>(t1/X, … , tn/X) si t = <>(t1, … , tn).

Si t1 et t2 sont des termes alors les formules t1 = t2 et t1 t2 sont respectivement une équation et une inéquation. Un ensemble S de telles formules est un système (d'équations et d'inéquations).

L'affectation sylvestre X est appelée solution du système :

S = {p1 := q1, p2 := q2, … }  »  {s1t1, s2t2, .  .  .  }

si X contient les mêmes variables que S et si X est telle que les arbres pi/X sont respectivement égaux aux arbres qi/X et que les arbres si/X  sont respectivement différents des arbres ti/X.

En utilisant ces notions il est possible de représenter le premier arbre de ce paragraphe par :

("a"."b"."c".nil) / {} ou ["a","b","c"] / {} suivant la syntaxe.

Le second arbre par :

plus(fois(l2, l1), fois(l2, l1)) / {} ou

plus(x, x) / X, avec X solution de {x = fois(l2, l1)}

et le troisième par :

x/X, avec X solution de { x = ou("c", et("a", et(x, "b"))) }

1.6.   Les opérateurs

Les opérateurs ont été intro­duits dans le compilateur Prolog II+, comme un moyen souple et clair d'exprimer certains arbres.

Par exemple, la représentation interne du terme mul(sub(5, 3),add(5, 3)) étant la même que celle du terme (5 - 3) * (5 + 3), la deuxième expression est certainement plus agréable à lire que la première.

La syntaxe des expressions écrites avec des opérateurs est donnée par:

exprn =  prefix_opn,d ,  exprd  ;
exprn =  exprg ,  postfix_opn,g ;
exprn =  exprg ,  infix_opn,g,d ,  exprd ;
exprn =  exprn-1 ;
expr0 =  pterm ;

prefix_opn,d =             identifier | graphic_symbol ;
postfix_opn,g =            identifier | graphic_symbol ;
infix_opn,g,d =               identifier | graphic_symbol ;

Voir la description complète au paragraphe 1.9.

1.7.   Les règles et les assertions

D'un point de vue théorique, un programme Prolog sert à définir un sous-ensemble A dans l'ensemble R de nos arbres. Les éléments de A sont appelés assertions et l'on peut généralement associer une phrase déclarative à chacun d'eux. La figure 1.9 montre quelques exemples de telles associations. L'ensemble A des assertions est généralement infini et constitue en quelque sorte une immense banque de données. Nous verrons plus loin que l'exécution d'un programme peut être vue comme une consultation d'une fraction de cette banque. Bien entendu cette banque ne peut être enregistrée sous une forme explicite. Elle doit être représentée à partir d'une information finie mais suffisante pour pouvoir déduire la totalité de l'information contenue dans la banque. Dans ce but, la définition de l'ensemble A des assertions est faite au moyen d'un ensemble fini de règles, chacune étant de la forme :

t0  ->  t1tn

n peut être nul et où les ti sont des termes.

 

   est_fils_de    pour « Jacques est le fils de Marie »   

     /     \   

Jacques   Marie

 

     plus   pour « 2 et 2 font 4 »

   /  |  \

suc  suc  suc

 |    |    |

suc  suc  suc

 |    |    |

 0    0   suc

           |

          suc

           |

           0

 

suite_infinie     pour « 1 1 1 ... est une suite infinie »

      |

     

     / \

    1  

       / \

      1  

         / \

        1   ...

Figure 1.9

 

Une syntaxe simplifiée[4] des règles est la suivante :

 

3.1        ruleE =                             term , "." ;
3.2        ruleE  =                            term , ":-" , term  { "," , term },
                                                   "." ;
3.3        ruleP =                             term , "->", { term }, ";" ;

Avec la contrainte fondamentale suivante :

Le terme qui est le membre gauche d'une règle doit être:

       -      soit un identificateur

       -      soit un tuple dont le premier argument est un identificateur

Par exemple, les termes :  go, pere_de(_x,_y) ou <pere_de, _x, _y> peuvent être des têtes de règle correctes, tandis que -contrairement à ce qui se passe pour Prolog II- des termes comme <<pere_de, _x>, _y> ou <masc.sing, x, y> ne peuvent pas l'être.

 

Pour le moment nous ferons abstraction de la notion de parasite, qui comme nous le verrons plus tard, est un moyen ad hoc d'appeler des sous-program­mes non écrits en Prolog.

Les règles de la forme :

t0 -> t1tn

induisent un ensemble, généralement infini, de règles particulières portant sur des arbres :

t0 / X t1 / Xtn / X

obtenues en considérant, pour chaque règle, toutes les affectations sylvestres possibles :

X = { x1 : = s1, … , xm : = sm }

qui font intervenir les variables de la règle en question.

Chacune de ces règles particulières :

r0 r1rn

peut s'interpréter de deux façons :

(1)     Comme une règle de réécriture :

                     r0 se réécrit dans la suite r1rn,

         et donc, lorsque n=0, comme :

                     r0 s'efface.

(2)     Comme une implication logique portant sur le sous-ensemble A d'arbres:

                     r1, r2, … , rn éléments de A, entraîne r0 élément de A.

         Dans ce cas, lorsque n = 0, l'implication se résume à :

                     r0 élément de A.

Suivant que l'on prend l'une ou l'autre des interprétations, les assertions se définissent par :

Définition 1 : les assertions sont les arbres que l'on peut effacer, en une ou en plusieurs étapes au moyen des règles de réécriture.

Définition 2 : les assertions forment le plus petit ensemble A d'arbres qui satisfait les implications logiques.

On peut démontrer l'existence du plus petit ensemble de la deux­ième définition et l'équivalence des deux définitions.

1.8.   Les mécanismes de base de Prolog

Nous venons de montrer quelle est l'information implicite contenue dans un programme Prolog, mais nous n'avons pas montré ce qu'est l'exécution d'un programme Prolog. Cette exécution vise à résoudre le problème suivant :

Etant donné un programme qui est une définition récursive d'un ensemble A d'assertions.

Etant donné une suite de termes T0 = t1tn et l'ensemble de ses variables { x1, . .  ., xm }.

Trouver toutes les affectations sylvestres X = { x1 := r1, … , xm = rm} qui sont telles que les arbres t1/X, .  .  ., tn/X soient des assertions.

Pour résoudre ce problème l'ordinateur doit produire toutes les dérivations de la forme :

(T0, S0) -> (T1, S1) -> (T2, S2) -> …  

Les Ti étant des suites de termes appelés buts et les Si étant des systèmes d'équations et d'inéquations ayant au moins une solution. S0 est le système vide : { }. On peut expliquer simplement la dérivation (Ti, Si) -> (Ti+1, Si+1) au moyen des trois lignes suivantes :

(1)     (q0 q1qn , S)

(2)     p0 -> p1pm

(3)     ( p1pm q1qn , S  » { q0 = p0 } )

La première ligne représente la forme que doit avoir le couple (Ti , Si), la seconde la règle utilisée et la troisième le résultat (Ti+1, Si+1). Avant d'utiliser une règle, il est nécessaire de renommer ses variables pour qu'aucune d'entre elles n'apparaisse dans (Ti ,Si). Il est aussi nécessaire de vérifier que le nouveau système Si+1 qui est obtenu en ajoutant l'équation {q0 = p0} à Si possède au moins une solution. Traditionnel­lement cette vérification est appelée unification de q0 avec p0.

Le but des dérivations précédentes est de trouver un couple (Tj, Sj) pour lequel la suite Tj est vide ; ce couple est donc dérivable de (T0, { }). On peut montrer que les affectations sylvestres X qui sont solution de Sj sont les réponses à notre problème. Le résultat imprimé par l'ordinateur est alors une forme simplifiée du système Sj dans laquelle les inéquations sont omises.

On peut également montrer que Prolog II+ vérifie parfaitement si un système d'équations et d'inéquations a au moins une solution.

D'un point de vue plus pratique, quand on lance Prolog, on se trouve dans une boucle qui lit une suite de buts T0 = t1tn, cherche à les effacer de toutes les manières possibles ((T0, { }) -> … -> (Tj, Sj) avec Tj vide), puis imprime les systèmes Sj correspondants. L'ordinateur écrit le caractère ">" quand il attend une suite de buts. De la même manière que nous avions une contrainte sur les règles, nous avons la contrainte suivante sur les buts :

A chaque étape, les arbres représentant le but qui va être effacé doivent avoir leur branche de gauche représentée par un identificateur.

 

Les parasites permettent l'utilisation de sous-programmes externes. Pour expliquer comment ces sous-programmes sont appelés, il faut se référer à la première des trois lignes qui décrit le mécanisme de base de Prolog : si q0 est un parasite, alors au lieu d'essayer d'utiliser une règle, Prolog exécute le sous-programme correspondant. Certains parasites appa­rais­sent dans les règles prédéfinies qui font l'interface entre des sous-programmes externes et des règles Prolog. Cet ensemble de règles prédéfinies constitue un environnement de programmation très complet permettant notamment :

   de contrôler et de modifier le déroulement d'un programme (cha­pitre 2 : “Le contrôle de l'effacement des buts”) ;

   de structurer et modifier l'ensemble de règles qui constituent le programme Prolog courant (chapitre 3 : “Structuration et modifi­cation des règles”) ;

   d'avoir accès aux fonctions classiques d'arithmétique et de traitement de chaînes (chapitre 4 : “Opérations prédéfinies sur les données”) ;

   de gérer les entrées-sorties (chapitre 5 : “Les entrées / sorties”);

   de communiquer avec le système hôte (chapitre 6 : “L'environnement”).

Il est également possible au programmeur averti d'introduire de nouvelles règles prédéfinies qui font référence à de nouveaux parasites qui seront écrits dans un autre langage que Prolog (C, Fortran, Pascal…). ( Voir chapitre 7 : "Extensions avec des langages externes" ou Annexe D : "Ajout de règles externes (méthode des parasites)").

Deux règles prédéfinies ont un lien étroit avec le mécanisme de base de Prolog II+: dif et eq.

La règle dif est la plus importante. C'est elle qui permet d'introduire les inéquations dans les systèmes d'équations et d'inéquations. Plus précisé­ment, l'exécution de dif(x,y) ajoute l'inéquation x ≠ y au système Si et vérifie que le nouveau système  Si+1 a au moins une solution.

De la même manière la règle eq introduit les équations.

         eq(x, x) -> ;

Les règles suivantes ne sont pas exactement des règles prédéfinies, mais tout se comporte comme si elles existaient. Elles sont utilisées pour transformer une liste de buts en un seul but.

         p.q ->  p q ;

         nil -> ;

1.9.   La syntaxe complète de Prolog II+

Nous rassemblons ici la syntaxe complète de Prolog II+ ainsi qu'un certain nombre d'exemples et de remarques additionnelles. Les notations utilisées sont celles de la commission de normalisation de Prolog (voir le premier paragraphe de ce chapitre).

1.9.1.  Le niveau syntaxique

1           program  =          { rule | directive } ;
2.10      directiveP =7         "->",  { pterm} ,  ";" ;
2.21      directiveE =7         ":-",   expr1199 ,  "." ;
3.10      ruleP =                 term , "->", { pterm }, ";" ;
3.21      ruleE =                 term, "." ;
4.1        termP =  expr1000  , [ "." , term ] ;
4.2        termE =  expr1200   ;

5           termlist =             expr999, { "," , expr999 } ;
6.12      exprn =  prefix_opn,d ,  exprd  ;
6.2        exprn =  exprg ,  postfix_opn,g ;
6.3        exprn =  exprg ,  infix_opn,g,d ,  exprd ;
6.42      exprn =  exprn-1 ;
6.5        expr0 =  pterm ;
7.1        pterm = ( identifier | variable ) , [ "(" , termlist , ")"];
7.23      pterm = ( identifier | variable ) , "[" , term , "]";
7.3        ptermP =              "<", termlist , ">" ;

7.44      pterm = "< >",  [ "(", termlist ,")" ];
7.55      pterm = "{", termlist , "}" ;
7.66      pterm = "[" , listexpr ,  "]" | "[ ]" ;
7.7        pterm = constant | "!" | "/?", integer_number ;
7.8        pterm = "(" , term , ")" ;
8.1        listexpr =             expr999, [ "," , listexpr ] ;
8.2        listexpr =             expr999, "|" , expr999;

 

Quand Prolog est lancé, la machine est prête à exécuter un programme, elle attend un term. Quand Prolog est passé dans un mode de compilation, c'est à dire un mode d'insertion de programme (cf. chapitre 3 de ce manuel), Prolog attend alors un program.

Notes:

0.  Définit la syntaxe en mode Prolog II.

1.  Définit la syntaxe en mode Edinburgh.

2.  exprn   représente la suite de règles expr1,...,expr1000 en syntaxe Prolog II, et expr1,...,expr1200 en syntaxe Edinburgh.

3.  La règle 7.2 exprime une syntaxe alternative pour les références aux composantes des tableaux, qui permet un accès optimisé. Par exemple, si table est le nom d'un tableau (défini par l'emploi de la règle prédéfinie def_array) alors les deux expressions table(10) et table[10] sont équivalentes. Cependant, le compilateur traduit la deuxième forme de manière plus efficace.

4.  Les règles 7.3 et 7.4 définissent deux syntaxes alternatives pour les tuples. En syntaxe Edinburgh seule la deuxième alternative est possible. On a donc les équivalences:

< x , y >                         ¤                  < > ( x , y )

5.  La règle 7.5 permet de décrire des grammaires non contextuelles (en vue d'écrire en Prolog des analyseurs syntaxiques).

6.  En syntaxe Prolog II, les règles 4 d'une part, et 7.6, 8.1 et 8.2 d'autre part définissent deux syntaxes alternatives pour la notation des listes. On a les équiva­len­ces suivantes :

[ a | b ]                           ¤                  a . b

[ a , b ]                           ¤                  a . b . nil

[ a , b , c , d ]                 ¤                  a . b . c . d . nil

[ a , b , c | d ]                 ¤                  a . b . c . d

[  ]                                 ¤                  nil

     En syntaxe Prolog II, les deux syntaxes de liste peuvent toujours être mélangées dans les programmes :

[ a , b | c.d.nil ]               ¤                  a . [b , c , d]

7.  Certains termes admis au titre de directives, ne sont pas des règles prédéfinies mais simplement des déclarations (par exemple module, end_module). Ils ne doivent pas dans ce cas être précédés de "->" ou ":-" comme il est dit dans les règles 2.1 et 2.2.

1.9.2.  Les opérateurs

Les opérateurs permettent d'étendre dynamiquement la syntaxe des termes. On distingue les opérateurs préfixés, postfixés, et infixés.

10         prefix_opn,d =          identifier | graphic_symbol ;
11         postfix_opn,g =         identifier | graphic_symbol ;
12         infix_opn,g,d =           identifier | graphic_symbol ;

On notera que dans la syntaxe Prolog II, les opérateurs ne sont pas autorisés au premier niveau des termes de la queue de règle, il faut parenthéser l'expression dans ce cas. En syntaxe Edinburgh, il n'y a pas de restriction.

Le type d'opérateur est indiqué par une convention permettant de définir la précédence des opérandes en fonction de la précédence n de l'opérateur:

type                  précédence      type opérateur       préc.opérande(s)       exemple

fx                     n                      opn,d                       d:= n-1                      -  (- 1)

fy                     n                      opn,d                       d:= n

xf                     n                      opn,g                       g:= n-1

yf                     n                      opn,g                       g:= n

xfx                    n                      opn,g ,d                     g:= n-1, d:= n-1         val(1'<'2,x)

xfy                    n                      opn,g ,d                     g:= n-1, d:= n            a,b,cE

yfx                    n                      opn,g ,d                     g:= n, d:= n-1            val(1/2/3,x)

Le tableau suivant décrit les opérateurs en syntaxe prolog II+. Le tableau indique pour chaque opérateur le terme syntaxique construit.

opérateur                        précédence            type              terme construit

 '<'                                 700                       xfx                   sys:inf(t1,t2)

 '=<'                               700                       xfx                   sys:infe(t1,t2)

 '>'                                 700                       xfx                   sys:sup(t1,t2)

 '>='                               700                       xfx                   sys:supe(t1,t2)

 =\=                               700                       xfx                   sys:'=\='(t1,t2)

 =:=                                700                       xfx                   sys:eql(t1,t2)

 +                                   500                       yfx                   sys:add(t1,t2)

 -                                   500                       yfx                   sys:sub(t1,t2)

 '/\'                                 500                       yfx                   sys:'/\'(t1,t2)

 '\/'                                 500                       yfx                   sys:'\/'(t1,t2)

 *                                   400                       yfx                   sys:mul(t1,t2)

 /                                    400                       yfx                   sys:div(t1,t2)

 mod                              400                       yfx                   sys:mod(t1,t2)

 rem                                400                      yfx                   sys:rem(t1,t2)

 '<<'                               400                       yfx                   sys:'<<'(t1,t2)

 '>>'                               400                       yfx                   sys:'>>'(t1,t2)

 ^                                   200                       xfy                   sys:'^'(t1,t2)

 **                                 200                       xfx                   sys:'**'(t1,t2)

 +1                                  200                       fx                     sys:add(t1)

 -1                                  200                       fx                     sys:sub(t1)

Note 1 :           Les arbres correspondant aux opérateurs unaires + et - sont évalués au moment de l'analyse si leur argument est une constante entière.

Note 2:            Les opérateurs peuvent être écrits avec des quotes simples. Celles-ci n'ont donc pas d'autre fonction, en Prolog II+, que d'étendre la syntaxe des identificateurs. Il n'est donc pas possible d'utiliser une notation fonctionnelle autre que celles des tuples pour un foncteur déclaré en opérateur. Lorsque l'on a un doute sur le terme construit, on peut toujours le tester en décomposant le terme:

> eq(F(X,Y),1'<'2);

{F=inf, X=1, Y=2}


1.9.3.  Le niveau lexical

Cette syntaxe définit les mêmes unités que celles reconnues par la primitive read_unit(x,y).

Notes :

1.  La règle L4 définit la syntaxe de base des variables; deux extensions de cette syntaxe sont données par les règles L5.P (syntaxe Prolog II) et L5.E (syntaxe Edinburgh). Dans les deux cas, le principe de l'extension est le même : un certain sous-ensemble des noms qui auraient été des représentations abrégées d'identifi­cateurs pour la syntaxe de base, est ajouté à l'ensemble des variables.

Ces deux extensions sont facultatives et incompatibles entre elles. C'est l'utilisateur qui, au démarrage de la session Prolog, choisit la syntaxe qu'il souhaite employer: se référer au Manuel d'Utilisation.

2.  Certaines combinaisons sont interdites comme "/*", "*/", "|*", "*|".

3.  Une option sur la ligne de commande permet de rendre l'exposant facultatif, au prix d'une ambiguïté avec les listes en syntaxe Prolog II: 1.2 est lu comme un réel en entrée. Cette règle n'est valide que si cette option est choisie. Voir le manuel d'utilisation, paragraphe 2.3.

4.  La règles L2.1 et L2.2 donnent la syntaxe de base des identificateurs. Une extension pour la syntaxe Edinburgh est donnée par les règles L2.3 et L2.4.

5.  La règle L2.3 est nécessaire pour exprimer le passage de l'identificateur abrégé représenté par un graphic_symbol à sa représentation complète. En effet le caractère qui délimite le préfixe de l'identificateur abrégé, étant lui-même un caractère graphique, une ambiguïté apparaîtrait si les quotes n'étaient pas ajoutées. Par exemple, sys::- est vu par l'analyseur d'unités lexicales comme: l'identificateur sys, immédiatement suivi de l'identificateur ::- et sys:':-' est vu comme: l'identificateur prédéfini :- de la famille sys.

 

L1        unit  =                             identifier | separator | variable

                                                   | constant |  graphic_symbol ;

L2.1     identifier =                       prefix , prefix_limit , abbreviated_id ; 
L2.2     identifier =                       abbreviated_id ;

L2.3E    identifier5 =                      prefix , prefix_limit ,
                                                   "'", graphic_symbol, "'" ; 
L2.4E    identifier4 =                      graphic_symbol ;

L3.1     abbreviated_id =             name - extended_var ;
L3.2     abbreviated_id =             "'", { (character - "'") | "'  '" }, "'" ;

L4        variable1 =                       "_" , {alpha} | extended_var ;

L5.P      extended_var =               letter, [ (digit | "_"), {alpha} ], { "'" } ;
L5.E      extended_var =               big_letter, [ {alpha} ] ;

L6        prefix =                           [ name , { prefix_limit , name } ] ;

L7        constant =                       integer_number | real_number | string ;   

L8.1     integer_number =            digits ;
L8.2     integer_number =            "0b", binary_number ;
L8.3     integer_number =            "0o", octal_number ;
L8.4     integer_number =            "0x", hex_number ;
L8.5     integer_number =            "0'", character ;

L9        real_number =                 digits, ".", digits,
                                                   ("E"|"e"|"D"|"d"), [ ["+"|"-"],digits];
L9.1S    real_number3 =                digits, ".", digits,
                                                   [ ("E"|"e"|"D"|"d"), [ ["+"|"-"],digits] ];

L10      string =                           """ , { string_char } , """ ;

L11      name =                           letter , { alpha } ;

L12      digits =                            digit , { digit } ;

L13.P    graphic_symbol2 =           "->" | graphic_c, { graphic_c | "." };
L13.E    graphic_symbol2 =           { graphic_c };

L14.1   comment =                      "|*", { character } , "*|" ;
L14.2   comment =                      "/*", { character } , "*/" ; 
L14.3   comment =                      "%", { character } , newline ;

 

1.9.4.  Les caractères

Les règles dont le membre gauche est annoté par I ne sont actives que lorsque le mode d'exécution de Prolog II+ est le mode ISO(cf. § U2.3). Les règles dont le membre gauche est annoté par H ne sont actives que lorsque le mode d'exécution de Prolog II+ est le mode hôte(cf. § U2.3).

Est désigné par host_letter, tout caractère du système hôte communément admis comme lettre et qui n'appartient pas au jeu ISO 8859-1; de la même façon, est désigné par host_graphic_char, tout caractère imprimable du système hôte n'étant ni un alpha, ni un separator, ni un special_char et inconnu du jeu ISO 8859-1.

Une description adaptée au jeu de caractères de la machine hôte sera donnée dans le manuel d'utilisation au paragraphe 3.2.

La règle C6.2 et les règles C7.2 et C8.1 représentent le même ensemble de caractères, mais elles ne sont pas valides simultanément. Celle annotée par P est valide en syntaxe Marseille, celles annotées par E sont valides en syntaxe Edinburgh. En changeant de syntaxe, ces caractères ne jouent plus le même rôle.

La règle C5 est valide, si le caractère qui délimite dans les identificateurs complets, le préfixe et le suffixe, n'a pas été redéfini. Il peut valoir alors, un des caractères graphiques.

 


C1        big_letter =                     "A" | … | "Z" ;
C2        letter =                            big_letter | "a" | … | "z"                                                   | "À" … "ß" - "¥" | "à" … "ÿ" - "÷";
C2.1     letterH=                           host_letter;
C2.21    letterI, i1  =  "\", accent_escape ;

C3.1     binary_digit =                  "0" | "1" ;
C3.2     octal_digit =                    "0" | … | "7" ;
C3.3     digit =                             "0" | … | "9" ;
C3.4     hex_digit =                      digit | "a" | "b" | "c" | "d" | "e" | "f"
                                                   | "A" | "B" | "C" | "D" | "E" | "F";

C4        alpha =                           letter | digit | "_";

C5        prefix_limit =                   ":" ;

C6.1     separator =                     "(" | ")" | "[" | "]" | "{" | "}" |
                                                   "|" | "," ;

C6.2     separatorP=                     ";" | "." | "<" | ">" ;

C7.1     special_char=                  "%" | "'" | """ | "_" | "!" | "`" ;
C7.2     special_charE=                ";" ;

C8        graphic_c =                     graphic_char ;

C8.1     graphic_charE =               "." | "<" | ">" ;
C8.2     graphic_char =                "#" | "$" | "&" | "*" | "+" | "-" | "/" | ":"

                                                   | "=" | "?" | "\" | "@" | "^" | "~"
                                                   | NBSP … "¿" | "¥" | "÷" ;
C8.3     graphic_charH =              host_graphic_char ;

C9        character =                     letter | digit | separator |
                                                   graphic_char | special_char ;

C10      string_char =                   character - ( """ | "\")  | """";

C10.1   string_chari0 =                 "\";
C10.2   string_chari1 =                 "\", format_escape ;
C10.31string_charI, i1  =                 "\", accent_escape ;

 


C111     accent_escape =             accent ,   accent_letter  | "~a"                              "~A""~n""~N" | "~o" 
                                                   | "~O" | "cc"| "CC" | "ae" | "AE"
                                                   | "BB""/o""/O"""y""'y""'Y"               | "-d"|"-D" | "pp" | "PP""oa"| "oA" ;

C123     accent =                          "`" | "'" | "^" | ":" ; 

C13      accent_letter =                "a" | "e" | "i" | "o" | "u"
                                                   | "A" | "E" | "I" | "O" | "U" ;          

C142     format_escape =             "b" | "f" | "n" | "r" | "t" | "\"
                                                   | newline
                                                   | octal_digit, octal_digit, octal_digit
                                                   | ("x" |"X"), hex_digit, hex_digit ;

1.9.5.  Les caractères accentués

Une option de comportement (cf. §2.3. du manuel d'utilisation) définit le mode de lecture du caractère "\". Lorsque l'interprétation du "\" est active, les règles sont annotées par i1, lorsqu'elle ne l'est pas les règles sont annotées par i0. Les règles ainsi annotées sont exclusives. Leur validité dépend de l'option choisie.

Les notes ci-après sont valides uniquement lorsque l'interprétation du "\" est active.

Notes :

1.  Il existe un mode d'exécution Prolog (cf. § U2.3.) dans lequel les accent_escape ne sont pas permis et sont remplacés par les format_escape; dans ce mode, ces règles(C2.2, C10.3, C11) ne sont pas valides. Sinon les accent_escape peuvent toujours être utilisés en entrée pour spécifier des caractères accentués. En sortie Prolog utilise un accent_escape pour les caractères accentués du jeu ISO 8859-1 n'existant pas dans le jeu de caractère du système hôte.

2.  De la même manière que pour les accent_escape, les format_escape peuvent toujours être utilisés en entrée pour spécifier un caractère. En sortie Prolog utilise un format_escape pour les caractères n'existant pas dans le jeu de caractère du système hôte, et ne pouvant être représentés par un accent_escape  (en mode hôte par exemple).

3.  Le caractère ":" dans un accent_escape représente le diacritique tréma:      cano\:e  <=>  canoë

128   144    160   176    192    208   224    240

    0                                            À           à       

    1                                             Á       Ñ       á        ñ

    2                                                    Ò       â        ò

    3                                            à     Ó      ã        ó

    4                                             Ä       Ô       ä        ô       

    5                                             Å       Õ       å        õ

    6                                            Æ      Ö      æ        ö

    7                                             Ç       ¥       ç        ÷

    8                                             È       Ø       è        ø

    9                                             É       Ù       é        ù

   10                                            Ê       Ú       ê        ú

   11                                            Ë       Û       ë        û

   12                                            ì        Ü       ì         ü

   13                                             í           í     

   14                                            î            î      

   15                                             ï        ß        ï         ÿ

Table 1 : les caractères accentués
dans le code ISO 8859-1

La table suivante donne la correspondance entre les caractères accentués et leur expression sous la forme de accent_escape .  On y apprend, par exemple, que les deux chaînes de caractères :

"tel maître, tel élève"   et   "tel ma\^itre, tel \'el\`eve"

sont équivalentes.

128   144    160   176    192    208   224    240

    0                                            `A      -D     `a       -d

    1                                             'A     ~N     'a       ~n

    2                                            ^A     `O     ^a       `o

    3                                           ~A     'O     ~a       'o

    4                                            :A     ^O     :a       ^o

    5                                            oA     ~O     oa      ~o

    6                                           AE     :O     ae       :o

    7                                           CC             cc       

    8                                            `E      /O      `e       /o

    9                                            'E      `U      'e       `u

   10                                           ^E     'U      ^e       'u

   11                                           :E      ^U     :e       ^u

   12                                           `I       :U      `i        :u

   13                                            'I       'Y      'i        'y

   14                                           ^I      PP     ^i       pp

   15                                            :I      BB      :i        :y

Table 2 : «accent_escape» utilisés par Prolog II+

1.10. Le macroprocesseur

Il est possible d'écrire en Prolog II+ quelques macros (ou alias) très simples afin d'augmenter la lisibilité des programmes. Cette fonctionnalité est réalisée au moyen d'une directive de compilation (et non un prédicat):

set_alias(i,t)

Définition d'un alias.

A partir du lieu et moment où cette directive est rencontrée, le lecteur remplace certaines (détails ci-dessous) occurrences de l'identificateur i  (appelé alias) par le terme t (appelé valeur). Cette définition est désactivée en fin de compilation de plus haut niveau d'imbrication.

La valeur t doit être de type entier, réel ou chaîne de caractères.

L'alias i doit être de type identificateur.

Seuls les identificateurs en position d'argument (pas les têtes de règle) et non préfixés explicitement dans le texte sont remplacés par la valeur de l'alias. Il est ainsi possible de conserver (en le préfixant explicitement dans le texte) un identificateur de même nom abrégé qu'un alias. Il est donc aussi logique que le préfixe de l'alias soit ignoré dans la directive. Néanmoins, dans le cas où celui-ci est déjà défini, la lecture d'une directive avec un alias explicitement préfixé dans le texte évitera sa substitution, et permettra donc une redéfinition (accompagnée d'un message d'avertissement). Le prédicat val/1 permet la définition d'un alias au moyen d'un autre alias.

Exemples commentés:

> insert;

set_alias(foo,44);

set_alias(foo,55);           Ici redéfinition de 44 en 55

-> set_alias(44,55) :    ARGUMENT DE MAUVAIS TYPE

 

> insert;

set_alias(macro1,22);

set_alias(aa:macro1,44);     Ici le préfixage est un moyen de redéfinition

WARNING: macro1 DEJA DEFINIE, NOUVELLE VALEUR PRISE EN COMPTE

rg1(macro1)->;

rg1(aa:macro1)->;

-> insert;                   Ici, 2ème niveau d'imbrication des compilations

set_alias(macro2,val(2 * macro1)); définition à partir d'une autre macro

rg2(macro2)->;

rg2(macro1)->;

;                            Ici, on revient au 1er niveau de compilation

macro1(macro2)->;       Ici protection automatique des têtes de règle

macro1(macro1)->;

;

{}

> rg1(I);

{I=44}                       Ici la nouvelle valeur est bien prise en compte

{I=aa:macro1}                Ici pas de substitution de l'identificateur préfixé

> rg2(I);

{I=88}

{I=44}                       La macro définie au 1er niveau de compilation a                                                                         été prise en compte dans le second niveau

> macro1(I);

{I=88}                       La macro définie au 2ème niveau de                                                                                              compilation a été prise en compte dans le                                                                                                    premier niveau

{I=44}

> insert;                                        Ici on démarre une nouvelle compilation

rg(macro1)->;

rg(macro2)->;

;

{}

> rg(I);

{I=macro1}                                       Les définitions ont bien été annulées

{I=macro2}

NB: Une macro apparaissant comme opérande gauche d'un opérateur infixé doit être parenthésée. Exemple:

?- insert.

set_alias(foo,44).

oper(X) :- foo >= X.

oper(X) :- (foo) >= X.

.

list.

oper(_345) :-

   val(foo,_348),

   _348 >= _345 .

oper(_345) :-

   44 >= _345 .

 




2.     Le contrôle
de l'effacement des buts

2.1.    Le contrôle

2.2.    Geler

2.3.    A propos des arbres infinis

2.4.    Quelques conseils pour la programmation récursive

2.5.    Les méta-structures

2.1.   Le contrôle

A chaque étape la machine Prolog doit faire deux choix :

(1)     L'un pour choisir un but dans une suite de buts à effacer. C'est le premier élément de la suite qui est toujours choisi. C'est à dire que pour effacer une suite de buts q0 q1qn, on efface d'abord q0 et ensuite q1qn.

(2)     L'autre pour choisir la règle qui sert à effacer un but b. C'est la première règle dont la tête s'unifie avec le but b qui est choisie.

Cela peut se résumer par le programme Prolog suivant :

effacer(nil) -> ;

effacer(t.l) -> rule(t, q) effacer(q) effacer(l) ;

rule(t,q) est une règle prédéfinie (voir le chapitre 3) qui donne par énumé­ration toutes les règles dont la tête s'unifie avec t et la queue avec q.

Le moyen de contrôle consiste à modifier ou à restreindre les deux choix précédents. La manière dont Prolog fait ces choix peut amener certains programmes à boucler et par conséquent à ne pas se comporter comme on pouvait l'espérer. Les deux exemples suivants illustrent ce phénomène.

Exemple 1 : Un cas typique est celui de la transitivité. Quand on cherche à effacer plus_grand(Jo,x) en utilisant  le programme suivant, on retrouve une instance de ce même but à effacer. Le programme se met alors à boucler et se termine par un débordement[5] de pile (ou par une interruption utilisateur!). La manière correcte d'écrire ce programme consiste à enlever la récursivité à gauche.

plus_grand(Jo, Max) -> ;

plus_grand(Max, Fred) -> ;

plus_grand(x, y) -> plus_grand(x, z) plus_grand(z, y);

> plus_grand(Jo, x);

{x=Max}

{x=Fred}

 

DEBORDEMENT 

"Une bonne solution"

plus_grand'(Jo, Max) -> ;

plus_grand'(Max, Fred) -> ;

plus_grand(x, z) -> plus_grand'(x, y) plus_grand_ou_egal(y, z);

plus_grand_ou_egal(x, x)  ->;

plus_grand_ou_egal(x, y)  -> plus_grand(x, y);

Exemple 2 : Cet exemple énumère toutes les listes construites avec 1. Avec le (mauvais) programme ci-dessous, c'est d'abord la liste infinie qui devrait être produite; bien entendu, la bonne solution s'obtient en permu­tant l'ordre des deux règles.

liste_de_un(1.x) -> liste_de_un(x) ;

liste_de_un(nil) -> ;

>liste_de_un(x);

DEBORDEMENT[6]

La coupure “!”

Normalement Prolog essaye d'effacer une suite de buts de toutes les manières possibles. Mais si on utilise une règle contenant un «!» (ou coupure) pour effacer un but q, l'effacement de ce «!» supprimera tous les choix de règles restant à faire pour effacer ce but q. Cela restreint la taille de l'espace de recherche : on peut dire que «!» fait «oublier» les autres manières possibles d'effacer q.

Le «!» ne peut apparaître que parmi les termes qui constituent le membre droit d'une règle. Les choix qui restent à examiner et que l'effacement du «!» fait «oublier» sont :

-   les autres règles ayant la même tête que celle où le «!» figure

-   les autres règles qui auraient pu être utilisées pour effacer les termes compris entre le début de la queue et le «!»

Cette question est illustrée par les exemples suivants :

couleur(rouge) ->;

couleur(bleu) ->;

taille(grand) ->;

taille(petit) ->;

choix1(x.y) -> couleur(x) taille(y);

choix1("c'est tout") ->;

choix2(x.y) -> ! couleur(x) taille(y);

choix2("c'est tout") ->;

choix3(x.y) -> couleur(x) ! taille(y);

choix3("c'est tout") ->;

choix4(x.y) -> couleur(x) taille(y) !;

choix4("c'est tout") ->;

>choix1(u);

{u=rouge.grand}

{u=rouge.petit}

{u=bleu.grand}

{u=bleu.petit}

{u="c'est tout"}

>choix2(u);

{u=rouge.grand}

{u=rouge.petit}

{u=bleu.grand}

{u=bleu.petit}

>choix3(u);

{u=rouge.grand}

{u=rouge.petit}

>choix4(u);

{u=rouge.grand}

>choix1(u) !;

{u=rouge.grand}

On peut considérer le «!» comme une annotation que l'on fait à un programme pour le rendre plus efficace; bien entendu, cela ne se justifie que si on ne s'intéresse qu'à la première solution fournie par ce programme.

Des utilisations classiques du «!» sont :

" Première solution uniquement "
premiere_solution_uniquement(b)  -> b !;

" Si Alors Sinon "        
si_alors_sinon(p,a,b) -> p ! a; 
si_alors_sinon(p,a,b) -> b;

" non "
non(p)  -> p ! fail;      
non(p)  -> ;

Dans le cas de non montré ci-dessus, il faut remarquer que l'on peut avoir des résultats inattendus si p contient des variables libres. C'est ce que montre le petit exemple suivant :

homme(Abélard) -> ;

femme(x) -> non(homme(x));

>femme(Eloïse);

{}

>femme(Abélard);

>femme(x) eq(x, Eloïse);

>

^(X,Y)

X doit être une variable et Y un terme quelconque.

^(X, Y) signifie: il existe X tel que Y soit vrai, et est équivalent à un appel de Y. L'utilisation de ce prédicat (qui est aussi un opérateur) n'a de sens que dans les prédicats bagof/3 et setof/3 , pour indiquer les variables existentielles et les retirer de l'ensemble des variables libres.

bagof(x, p, l)

Pour chaque instantiation différente de l'ensemble des variables libres du but p, non existentielles et n'apparaissant pas dans le terme x, unifie l avec la liste de toutes les solutions x lorsqu'on efface p. Chaque liste l est construite suivant l'ordre des solutions trouvées. Exemple:

aa(2,1) -> ;

aa(1,2) -> ;

aa(1,1) -> ;

aa(2,2) -> ;

aa(2,1) -> ;

>bagof(X, aa(X,Y),L);

{Y=1, L= 2.1.2.nil}

{Y=2, L= 1.2.nil}

> bagof(X,Y^aa(X,Y),L);

{L=2.1.1.2.2.nil}

>

block(e, b), block_exit(e)

block est une règle prédéfinie qui permet de terminer brutalement l'effacement d'un but b. Cette primitive est faite essentiellement pour la récupération des erreurs. On peut considérer que :

-   Pour effacer block(e, b) on efface b en ayant auparavant créé une paire de parenthèses fictives, étiquetées par e, autour du but b.

-   block_exit(e) provoque l'abandon immédiat de l'effacement de tous les buts inclus entre les parenthèses étiquetées par e et supprime tous les choix éventuels en attente pour ces buts. L'effacement continue ensuite normalement, après les parenthèses étiquetées par e.

De plus :

-   Une étiquette est un terme Prolog quelconque, et on considère que deux parenthèses étiquetées sont identiques si leurs étiquettes respectives sont unifiables.

-   S'il y a plusieurs parenthèses étiquetées par e, block_exit(e) s'arrête au couple de parenthèses le plus interne.

-   Si block_exit(e) ne rencontre pas de parenthèses e, alors on revient au niveau de commande avec le message d'erreur correspondant à e, si e est un entier, ou le message 'block_exit' SANS 'block' CORRESPONDANT, si e n'est pas un entier.

C'est ce même mécanisme qui est utilisé pour la gestion des erreurs dans Prolog. Une erreur rencontrée dans l'exécution de Prolog provoque l'effacement du but block_exit(i)i est un entier correspondant au numéro de l'erreur. De cette manière l'utilisateur peut récupérer toutes les erreurs de Prolog, pour pouvoir les traiter dans son application.

Lorsque les optimisations de compilation sont actives (option -f o1 au lancement de Prolog), la compilation de block est optimisée et la décompilation d'un tel but ne sera pas identique mais équivalente au but d'origine. Le but block(e,b) apparaissant dans une queue de règles, sera décompilé en block(e',_,b').

La règle prédéfinie quit génère un block_exit(14). Elle est définie ainsi :

quit -> block_exit(14);

quit(i) -> block_exit(14,i);

A titre d'illustration voici un programme qui lit une suite de commandes :

executer_commande ->

   block(fin_commande, toujours(lire_et_exec));

lire_et_exec -> outm("?") in_char'(k) exec(k);

exec("q")  -> block_exit(fin_commande) ;

exec("f")  -> block_exit(16) ;   /* Interruption */

exec("n")  -> ;

toujours(p)  -> repeter p fail ;

repeter -> ;

repeter -> repeter ;

Dans cet exemple, la commande "q" utilise block_exit pour retourner au niveau supérieur de executer_commande. La commande "f" simule une erreur Prolog et rend le contrôle au block qui traite les erreurs de Prolog (puisque 16 ne peut s'unifier avec fin_commande). S'il n'y a pas de block englobant, on revient au niveau supérieur de Prolog.

block(e, c, b), block_exit(e, c)

Fonctionnement analogue aux formes précédentes, avec deux «étiquettes» e et c à la place d'une seule. b est le but à effacer. block(e,c,b) lance l'effacement de b; l'effacement ultérieur de block_exit à deux arguments produira la recherche d'un block dont les deux premiers arguments s'unifient avec les deux arguments de block_exit.

Lorsque les optimisations de compilation sont actives (option -f o1 au lancement de Prolog), la compilation de block est optimisée et dans certains cas la décompilation d'un tel but ne sera pas identique mais équivalente au but d'origine. Le but block(e,c,b) apparaissant dans une queue de règles, sera décompilé en block(e',c',b').

Ensemble, ces deux règles prédéfinies constituent une sorte de raffinement du mécanisme de récupération des erreurs; en pratique, e correspond au type d'erreur guetté; c correspond à un «complément d'information» rendu par le mécanisme de détection.

Un grand nombre de règles prédéfinies utilisent cette deuxième étiquette comme complément d'erreur. C'est souvent l'argument, cause de l'erreur, qui y est transmis. En phase de mise au point de programmes, cela peut paraître encore insuffisant. Dans le kit, des modules objets : dbgbase.mo, dbggraph.mo et dbgedin.mo, sont fournis. Ils permettent, après recharge­ment, en cas d'erreur, d'avoir des messages encore plus complets. Le deuxième argument de block sera unifié avec un terme de la forme :

            prédicat d'appel ou < prédicat d'appel, complément d'erreur>

Lorsque block_exit(e,c) est effacé dans un environnement «parenthésé» par block(e',b), alors block_exit(e,c) se comporte comme block_exit(e). Inversement, lorsque block_exit(e) est effacé dans un environnement «parenthésé» par block(e',c',b) alors block_exit(e) se comporte comme block_exit(e,nil)   

Erreurs et sous-sessions Prolog

Tout ce qui est dit ci-dessus concernant le mécanisme d'erreur block / block_exit, est vrai à l'intérieur d'une même session Prolog. Lorsqu'il s'agit de transmettre une erreur à travers une ou plusieurs sous-sessions (par exemple lorsqu'un but est lancé par menu), deux restrictions sont à mentionner :

          - le deuxième argument de block_exit (souvent utilisé comme complé­ment d'erreur) n'est pas transmis. Il vaudra toujours nil.

          - le premier argument de block_exit est transmis uniquement s'il est de type entier. Dans le cas contraire c'est l'entier 317, pour l'erreur : 'block_exit' SANS 'block' CORRESPONDANT, qui est propagé.

Interruption

A tout instant un programme Prolog peut être interrompu au moyen d'une touche déterminée, dépendant du système utilisé (par exem­ple : <Ctrl-C>). Cette interruption est prise en compte par le mécanisme général des erreurs de Prolog et correspond à l'erreur 16. Cette erreur peut donc être récupérée par l'utilisateur. Sinon on revient au niveau de commande avec le message d'erreur suivant : INTERRUPTION UTILISATEUR.

bound(x)

bound(x) s'efface si x est lié. Une variable est considérée comme liée si elle a été unifiée contre :

- une constante (entier, réel, identificateur, chaîne),

- un terme de la forme t1.t2,

- un terme de la forme <t1, t2, … , tn> ou ff(t1, t2, … , tn).

dif(t1, t2)

La règle prédéfinie dif(t1, t2) est utilisée pour contraindre t1 et t2 à représenter toujours des objets différents. Dès que cette contrainte ne peut plus être satisfaite, on revient en arrière (backtracking). L'implan­­tation de dif utilise un mécanisme similaire à geler.

Voici deux primitives intéressantes que l'on peut écrire avec dif : hors_de(x, l) qui vérifie que x n'appartiendra jamais à la liste l; et tous_differents(l) qui vérifie que les composants de la liste l seront toujours différents deux à deux.

  hors_de(x, nil) -> ;

  hors_de(x, y.l) -> dif(x, y) hors_de(x, l);

  tous_differents(nil) -> ;

  tous_differents(x.l) -> hors_de(x, l)

   tous_differents(l);

Avec ces deux primitives on peut par exemple écrire un programme qui calcule des permutations : il suffit de dire que l'on a une liste d'entiers et que tous les éléments de cette liste sont différents deux à deux :

permutation(x1,x2,x3,x4)  ->

  tous_differents(x1.x2.x3.x4.nil)

  chiffre(x1) chiffre(x2) chiffre(x3) chiffre(x4);

chiffre(1) -> ;

chiffre(2) -> ;

chiffre(3) -> ;

chiffre(4) -> ;

Remarquons que dans cet exemple, Prolog met d'abord en place toutes les inégalités avant d'exécuter le programme non-déterministe classique. Ceci donne une programmation plus claire et plus efficace.

L'utilisation de dif permet également l' écriture de programmes qui auraient un comportement incorrect si l'on utilisait une définition utilisant la coupure. Par exemple la définition de la relation "x est élément de l à la valeur v" peut s'écrire :

élément(x,nil,false) ->;

élément(x,x.l,true) ->;

élément(x,y.l,v) -> dif(x,y) élément(x,l,v);

 

> élément(x,1.2.nil,v);

{x=1, v=true}

{x=2, v=true}

{x#1, x#2, v=false}

Si l'on définissait une telle relation en utilisant la primitive !, on introduirait de nombreux comportements anormaux :

élément(x,nil,false) ->;

élément(x,x.l,true) -> ! ;

élément(x,y.l,v) -> élément(x,l,v);

 

> élément(x,1.2.nil,v);

{x=1, v=true}              % une seule solution !!

> élément(2,4.2.3.nil,false);

{}                   % succès !!

default(t1, t2)

La règle prédéfinie default permet de réaliser le contrôle suivant: Si on peut effacer t1, alors on l'efface de toutes les manières possibles, sinon on efface t2. Il faut remarquer que contrairement à ce que l'on pourrait penser à première vue, cette primitive ne peut pas être réalisée avec '!'. Voyons sur un exemple une utilisation de cette règle:

répondre(p) -> default(p,outml("personne"));

homme(jean) ->;

homme(pierre) ->;

 

> répondre(homme(x));

{x=jean}

{x=pierre}

> répondre(femme(x));

personne

{}

eq(t1, t2)

Unification de t1 et t2 : correspond simplement à la règle :
eq(x,x) -> ; .

fail

Règle prédéfinie provoquant toujours un échec (backtracking).

findall(x, p, l)

Unifie l avec la liste de toutes les solutions x  lorsqu'on efface p.

free(x)

S'efface uniquement si x n'est pas lié.

list_of(x, y, p, l)

Fournit la liste triée, sans répétition, de tous les individus qui satisfont une certaine propriété.

x est une variable.

y est une liste de variables.

p est un terme Prolog contenant au moins toutes ces variables.

Pour chaque ensemble de valeurs de y, unifie l avec la liste des valeurs de x pour que p soit vraie (c'est à dire pour que p s'efface).

L'ordre de la liste l est identique à celui défini sur les termes (cf. term_cmp/3)

Exemple : Prolog contenant la base de règles suivante :

homme(grand, michel, 184) ->;

homme(grand, alain, 183) ->;

homme(grand, henry, 192) ->;

homme(petit, nicolas, 175) ->;

homme(petit, julien, 176) ->;

homme(petit, gilles, 120) ->;

> list_of(x,t.nil,homme(t,x,h),l);

{t=grand, l=alain.henry.michel.nil}

{t=petit, l=gilles.julien.nicolas.nil}

not(X)

Est décrit par les règles:

not(X) :- X,!,fail.

not(X).

repeat

Est décrit par les règles :

repeat ->;

repeat -> repeat;

setof(x, p, l)

Pour chaque instantiation différente de l'ensemble des variables libres du but p, non existentielles et n'apparaissant pas dans le terme x, unifie l avec la liste de toutes les solutions x lorsqu'on efface p. Chaque liste l est triée et sans répétition. L'ordre de la liste l est identique à celui défini sur les termes (cf. term_cmp/3).

Exemple : Prolog contenant la base de règles suivante :

aa(2,1) -> ;

aa(1,2) -> ;

aa(1,1) -> ;

aa(2,2) -> ;

aa(2,1) -> ;

> setof(X, aa(X,Y),L);

{Y=1, L= 1.2.nil}

{Y=2, L= 1.2.nil}

> setof(X,Y^aa(X,Y),L);

{L=1.2.nil}

>

or(x,y)

Définit un ou logique transparent à la coupure. Exemple:

> op(900,xfy,or);

{}

> enum(i,4) (eq(i,1) or eq(i,2));

{i=1}

{i=2}

> enum(i,4) ([eq(i,3),'!'] or [outl(no),fail]);

no

no

{i=3}

>

2.2.   Geler

Il s'agit de résoudre de manière efficace un problème qui se pose souvent en Prolog : retarder le plus possible certaines décisions. Ce qui revient à dire qu'il faut avoir suffisamment d'information avant de poursuivre l'exécution d'un programme, ou que certaines variables doivent avoir reçu une valeur pour pouvoir continuer. On profite alors des avantages de la programmation déclarative, tout en gardant une exécution efficace.

freeze(x, q)

Le but de cette règle prédéfinie est de retarder l'effacement de q tant que x est inconnu. Plus précisément :

(1)     Si x est libre, alors freeze(x, q) s'efface et l'effacement de q est mis en attente (on dit que q est gelé). L'effacement effectif de q sera déclenché au moment où x deviendra liée.

(2)     Si x est liée alors freeze lance l'effacement de q normalement.

C'est au programmeur de s'assurer qu'une variable gelée sera toujours dégelée dans le futur, pour que le but associé ne reste pas indéfiniment en attente. Ceci n'est pas vérifié par Prolog, et peut conduire à des solutions trop générales.

Remarque : Les impressions des variables d'une question sur lesquelles il reste des buts gelés se fait d'une manière spéciale :

> freeze(x,foo);

{x~foo.nil}

Voyons maintenant quelques exemples d'utilisation de freeze.

Exemple 1 : Evaluation de somme(x, y, z). On veut résoudre l'équation z = x + y seulement si les deux variables x et y sont connues.

somme(x, y, z) -> freeze(x, freeze(y, somme1(x, y, z))) ;

somme1(x, y, z) -> val(x+y, z);

Exemple 2 : Mais on peut faire mieux : On veut résoudre la même équation si deux au moins des variables x, y, z sont connues : 

somme (x, y, z) ->

   freeze(x, freeze(y, ou_bien(u, somme1(x, y, z))))

   freeze(y, freeze(z, ou_bien(u, somme2(x, y, z))))

   freeze(x, freeze(z, ou_bien(u, somme3(x, y, z))));

ou_bien(u, p) -> free(u) ! eq(u, Cst) p;

ou_bien(u, p) ->;

somme1(x, y, z) -> val(x+y, z);

somme2(x, y, z) -> val(z-y, x);

somme3(x, y, z) -> val(z-x, y);

Ci-dessus, la variable u, qui devient liée dès que l'une des additions est effectuée, sert à empêcher que les autres additions, redondantes, soient calculées.

Exemple 3 : Cet exemple montre comment utiliser une variable pour contrôler un programme de l'extérieur. La règle liste_de_un qui a été donnée dans un exemple précédent, bouclait. Pour empêcher cette boucle on utilise simplement une condition externe : longueur(l, n) qui vérifie que la longueur d'une liste l est inférieure ou égale à n.

  longueur(l,n) -> freeze(l,longueur'(l,n));

  longueur'(nil, n) ->;

  longueur'(e.l, n) ->
     dif(n,0) val(n-1, n') longueur(l, n');

  liste_de_un(1.x) -> liste_de_un(x);

  liste_de_un(nil) -> ;

  > longueur(l,5) liste_de_un(l);

  {l=1.1.1.1.1.nil}

  {l=1.1.1.1.nil}

  {l=1.1.1.nil}

  {l=1.nil}

  {l=nil}

Quand tous les buts ont été effacés, il se peut qu'il reste encore certains buts gelés sur des variables qui sont encore libres.

Remarque : Les optimisations de compilation ne permettent pas de déclencher les buts gelés dès l'unification de la tête de règle mais seulement sur le premier but de la queue non optimisé. En particulier, l'exemple suivant échouera :

> insert;

nombre(<i>) -> integer(i);

lier(<1>) ->;;

{}

> freeze(x, lier(x)) nombre(x);

>

En effet, les prédicats de test de type étant optimisés, le dégel de lier(<i>) ne se fera pas puisqu'il n'y a pas d'autres buts dans la queue de nombre/1.

2.3.   A propos des arbres infinis

Ce paragraphe donne quelques informations pratiques sur l'utilisation dans Prolog II des arbres infinis. Tout d'abord, il faut remarquer qu'un certain nombre de règles prédéfinies ne travaillent que sur des arbres finis. En particulier, in ne peut pas lire d'arbres infinis, et assert ne peut pas ajouter de règles contenant des arbres infinis.

infinite

no_infinite

Ces règles servent à définir le type d'impression de résultat utilisé: il faut avoir activé l'option infinite si l'on désire imprimer des solutions contenant des arbres infinis.

Voici un exemple qui utilise freeze et qui vérifie qu'un arbre est toujours fini. Ceci est un moyen indirect de faire le test dit d'occur_check. Ce programme vérifie que l'on n'a pas deux fois le même sous-arbre dans chaque branche de l'arbre.

arbre_fini(x) -> branche_finie(x, nil);

branche_finie(x, l)  -> freeze(x, branche_finie'(x, l));

branche_finie'(x, l)  ->

   hors_de(x, l) domine (x, l') branches_finies(l', x.l);

branches_finies(nil, l) -> ;

branches_finies(x.l', l) ->

   branche_finie (x, l) branches_finies (l', l) ;

domine(x1.x2, x1.x2.nil)  -> ! ;

domine(x, x') -> tuple(x) ! split(x, x') ;

domine(x, nil) -> ;

infinite_flag

Symbole dont la valeur (0 ou 1) indique si infinite ou no_infinite est actif. Cette valeur peut être testée par l'intermédiaire de la règle prédéfinie val.

equations(t, t', l)

Cette règle prédéfinie sert à transformer un arbre fini ou infini t en une liste d'équations l qui a comme solution t. t' indique la variable de l représentant la racine de l'arbre t. C'est cette primitive qui est utilisée pour imprimer les solutions lorsque l'option infinite est active. Regardons une utilisation sur l'exemple suivant :

> infinite eq(x,ff(ff(x))) equations(x,t',l) out(t') outm(" : ") outl(l) ;

v131 : eq(v131,ff(v131)).nil

{x=v131, v131=ff(v131), l=eq(t',ff(t')).nil}

> eq(x,ff(ff(x)));

{x=v120,v120=ff(v120)}

Mais une des utilisations principales de cette primitive est le fait de pouvoir ajouter des arbres infinis. Nous utilisons la primitive assert (chapitre suivant) qui permet d'ajouter une règle.

  ajout_infini(t) ->

   equations(t,t',l)

   assert(arbre(t'),l) ;

  > infinite eq(x, ff(ff(x))) ajout_infini(x) ;

  {x=v131, v131=ff(v131)}

  > list(arbre/1) ;

  arbre(x11) -> eq(x11, ff(x11)) ;

  {}

  > arbre(x) ;

  {x=v131, v131=ff(v131)}

2.4.   Quelques conseils pour la programmation récursive

Le système Prolog II+ comporte un récupérateur de mémoire (garbage collector) auto­matique. Ce "ramasse-miettes" est très performant et est capable de ne garder dans les piles que les données dont vous avez effectivement besoin; ceci permet d'utiliser à fond les définitions récursives de programmes. Malgré tout, certaines techniques de program­mation peuvent vous aider à récupérer encore plus d'espace. Pratiquement, il s'agit d'utiliser adroitement la coupure des points de choix ainsi que de tirer un maximum de profit de l'optimisation de récursion et d'appel terminal que fait le compilateur Prolog II+. L'utilisation de ces techniques permet l'écriture de programmes qui se rappellent eux-mêmes indéfiniment, sans jamais déborder.

Ceci sera plus clair à partir d'un exemple:

> insert;

répéter -> out(1) répéter ;;

{}

> répéter ;

11111111111111111111111...

est un programme tournant indéfiniment sans déborder, car la récursion se fait sur le dernier littéral de la règle. Par contre le programme suivant débordera, car la récursion accumule les littéraux à effacer (récursion non terminale):

répéter -> out(1) répéter out(2);

> répéter ;

11111111111111111111111...

-> DEBORDEMENT[7] PILE DE RECURSIVITE

>

de même le fait qu'il reste des choix à la règle exécutée accumule de l'information à garder. L'effacement du but avec la définition qui suit provoquera un débordement par accumulation de points de choix:

> insert;

répéter -> répéter ;

répéter ->;;

{}

> répéter fail;

-> DEBORDEMENT PILE DE RECURSIVITE

>

En revanche le programme suivant tournera indéfiniment (heureuse­ment on peut l'interrompre avec Control-C!):

répéter -> ;

répéter -> répéter ;

Le coupe-choix "!" permet au ramasse-miettes de récupérer davantage d'espace, en supprimant des points de choix. Il faut cependant remarquer que si on le place en fin de règle, on fait disparaître la propriété de récursion terminale:

répéter -> out(1) répéter !;

répéter ->;

Le programme ci-dessus provoquera un débordement (le "!" est un littéral à effacer), alors que le programme ci-dessous tournera indéfiniment:

répéter -> out(1) ! répéter ;

répéter ->;

2.5.   Les meta-structures

2.5.1.  Création

Il est possible en PrologII+ d'attacher à une variable une liste de termes. On parlera alors de méta-structure ou variable attribuée et de termes attribués.

La particularité de ces variables est que l'unification avec un terme connu ou bien avec une autre variable attribuée est rempla