Cours gratuits » Cours informatique » Cours programmation » Cours Prolog » Introduction à ProLog : les variables et Récursivité

Introduction à ProLog : les variables et Récursivité


Télécharger



★★★★★★★★★★3 étoiles sur 5 basé sur 1 votes.
3 stars
1 votes

Votez ce document:

Introduction à ProLog : les variables et Récursivité

...

Les faits et les règles forment une base de connaissance.

=> Valider des questions à partir des faits et des règles, soit les questions sont des faits qui se trouvent explicitement explicitement explicitement dans la base de connaissance, soit Prolog peut valider la question à partir des faits et des règles à l‘aide de la résolution résolution. résolution

Prolog - Syntaxe Prolog - Syntaxe

Exemple : parle(X) :- humain(X), not bebe(X).

fy;">signifie x (humain(x)  ¬ bebe(x) => parle(x))

,  conjonction

; v disjonction

:- <= implication

not ¬ négation

Les différents termes :

Constantes (atomes, nombres)

Variables

Termes complexes

Prolog est „case sensitive“ „case sensitive“. „case sensitive“ Les mots qui commencent avec un caractère majuscule sont considérés comme des variables, les mots qui commencent avec un caractère minuscule sont des constantes.

Il ne faut jamais mettre des espaces entre un nom d‘un terme et les „()“.

Prolog - Variables Prolog - Variables

Exemple :

aime(othello,desdemona).

aime(desdemona,jago).

aime(romeo,julia).

aime(julia,romeo).

jaloux(X,Y) :- aime(X,Z), aime(Z,Y).

?- jaloux(othello,P).

Est-ce qu‘il existe un individu P tel que Othello est jaloux ?

Est-ce qu‘il existe des autres individus qui sont jaloux ?

Prolog - Récursivité Prolog - Récursivité

Exemple :

enfant(alfred,jean-marie).

enfant(jan,alfred).

enfant(jonathan,jan).

On va définir la relation „descendant“ :

descendant(X,Y) :-

enfant(X,Y).

descendant(X,Y) :-

enfant(X,Z),

enfant(Z,Y).

descendant(X,Y) :-

enfant(X,Z),

enfant(Z,A),

enfant(A,Z).

Prolog - Récursivité (cont.) Prolog - Récursivité (cont.)

enfant(alfred,jean-marie).

enfant(jan,alfred).

enfant(jonathan,jan).

descendant(X,Y) :- (1)

enfant(X,Y).

descendant(X,Y) :- (2)

enfant(X,Z),

descendant(Z,Y).

?- descendant(jonathan,jean-marie).

Tout d‘abord, Prolog essaie à appliquer la première règle, mais cette information ne se trouve pas dans la base de connaissance. Donc, Prolog essaie la deuxième règle. On continue jusqu‘on trouve une information mise explicitement dans la base de connaissance qui valide la première règle.

Il faut au moins deux clauses : Une clause de base qui peut valider la Il faut au moins deux clauses : Une clause de base qui peut valider la récursivité (terminer le boucle) et une clause qui contient la récursivité. récursivité (terminer le boucle) et une clause qui contient la récursivité. récursivité (terminer le boucle) et une clause qui contient la récursivité.

Prolog - Récursivité (cont.) Prolog - Récursivité (cont.)

enfant(alfred,jean-marie).

enfant(jan,alfred).

enfant(jonathan,jan).

descendant(X,Y) :- (1)

enfant(X,Y).

descendant(X,Y) :- (2)

enfant(X,Z),

descendant(Z,Y).

?- descendant(jonathan,jean-marie).

descendant(jonathan,jean-marie) :- (2)

enfant(jonathan,jan),

descendant(jan,jean-marie).

descendant(jan,jean-marie) :- (2)

enfant(jan,alfred),

descendant(alfred,jean-marie).

enfant(alfred,jean-marie). (1)

Prolog - Implémentations Prolog - Implémentations

Les implémentations „libres“ :

SWI-Prolog : (University of Amsterdam, www.swi-prolog.org)

Eclipse-Prolog (/eclipse)

Open Prolog (/open-prolog) pour Apple Macintosh

PROPLOG

Les implémentations commerciales :

SICSTUS-Prolog ()

Quintus-Prolog ()

Prolog - Implémentaions (cont.) Prolog - Implémentaions (cont.)

Créer un projet („home folder“ où les fichiers avec le code sont stockés).

Le code s‘écrit dans un éditeur de texte et est mis dans un fichier. GNU

Emacs va permettre d‘écrire et compiler le code et aussi d‘effectuer des queries (avec SWI-Prolog). Open Prolog inclut un éditeur de texte.

Charger un programme (compilation du code).

Faire des requêtes (queries).

„Trace“ et „Dubug“ les requêtes („step-by-step“). Avec ces fonctions, on peut observer la résolution et corriger les erreurs dans le code. trace(descendant(jonathan,jean-marie)).

On peut aussi stocker la charge des programmes et les requêtes pour une utilisation future.

On peut mettre plusieurs programmes Prolog dans un seul fichier.

Prolog - Exemple variables Prolog - Exemple variables

Prolog - Exemple récursivité Prolog - Exemple récursivité

Série d‘exercices n Série d‘exercices n° 6

3 Modélisation

  1. c) Etablissez une liste d‘axiomes pour décrire les contraintes physiques de ce système. Par exemple :

x ¬(Cube(x)  Sphere(x))

Série d‘exercices n Série d‘exercices n° 6 (cont.) 6 (cont.)

„x n‘est pas à droite de x“ :

x ¬ADroite(x,x)

xy (ADroite(x,y) => ¬Egal(x,y))

xy (ADroite(x,y) => AGauche(y,x))

xy (AGauche(x,y)  AGauche(y,z) => AGauche(x,z))

„Si x est un cube, x n‘est pas une sphère“ :

x ¬(Cube(x)  Sphere(x))

x (¬Cube(x) v ¬Sphere(x)) (De Morgan)

x (Cube(x) => ¬Sphère(x)) (Implication-ou)

En Prolog :

not aGauche(X,X). not aDroite(X,X).

not egal(X,Y) :- aDroite(X,Y).

aGauche(Y,X) :- aDroite(X,Y).

aGauche(X,Z) :- aGauche(X,Y), aGauche(Y,Z).

sphere(X) :- not(cube(X)).

Récursivité: Example Récursivité: Example

Plan d‘études avec pré-requis

pre_requis(cours_1,cours_2).

pre_requis(cours_1,cours_3).

pre_requis(cours_3,cours_4).

pre_requis(cours_3,cours_5).

pre_requis(cours_5,cours_6).

pre_requis(cours_2,cours_6).

pri(X,Y) :- pre_requis(X,Y).

pri(X,Y) :-

pre_requis(X,Z),

pri(Z,Y).

?- pri(X,cours_6).

(1) X = cours_5 ; (4) X = cours_1 ;

(2) X = cours_2 ; (5) X = cours_3 ;

(3) X = cours_1 ; (6) no

Récursivité: Example (cont.) Récursivité: Example (cont.)

Plan d‘études avec pré-requis

peut(X,C) :- not interdit(X,C).

interdit(X,C) :- pre_requis(C,D), not reussi(X,D).

… .. …

1- Planification dynamique en Prolog :

Le but du mini-projet est d'explorer les aspects "dynamiques" de Prolog via l'application classique de la planification d'actions dans le "monde des blocs".

2- Déclarer des faits dynamiques :

Le "monde des blocs" est constitué d'objets élémentaires (boîtes, cubes, boules, pyramides...) disposés dans un espace plan. On va réaliser des actions dans ce monde (déplacer un objet d'un endroit à un autre). Par exemple, on va passer de la situation 1 à la situation 2 :                                     

                                                    situation 1                        situation 2

Cela signifie que des faits vrais à un certain moment (le fait que le bloc a soit sur le bloc b), deviennent faux à d'autres. Pour déclarer de tels faits, on déclare certains prédicats comme "dynamiques".

:- dynamic(sur/2).

sur(a,b).

sur(b,c).

sur(c,table).

On ne peut déplacer qu'un objet qui est "libre", c'est-à-dire en haut d'une pile, et on ne peut le mettre que sur la table (qui est supposée toujours "libre") ou en haut d'une autre pile. En réalisant ce déplacement, on retire de l'ensemble des faits l'ancien positionnement du bloc déplacé, et on ajoute son nouveau positionnement. On peut donc définir l'action de déplacement avec les prédicats suivants :

libre(table).

libre(a).

met_sur(X,Y) :-

        X \== table,

        X \== Y,

        libre(X),

        libre(Y),

        sur(X,Z),

        retract(sur(X,Z)),

        assert(sur(X,Y)),

        assert(deplace(X,Y)).  /*ajoute le déplacement comme fait*/

Dans ce code, le méta prédicat "retract(...)" retire de la base de faits ce qui ne doit plus être considéré comme vrai, tandis que "assert(...)", lui, ajoute un nouveau fait devenu vrai. L'action de déplacement elle-même est stockée dans le terme "deplace(X,Y)". Une fois ce code chargé, on peut réaliser les opérations suivantes, où le méta prédicat listing(Predicat) donne toutes les instances vraies de Predicat :

| ?- listing(libre).

libre(table).

libre(a).

true

| ?- listing(sur). 

sur(a,b).

sur(b,c).

sur(c,table).

true

| ?- met_sur(a,table).

true

| ?- listing(sur).   

sur(a,table).

sur(b,c).

sur(c,table).

true

| ?- listing(deplace).

deplace(a,table).

true

| ?- listing(libre). 

libre(table).

libre(a).

3- Planification récursive :

Faire de la planification consiste à créer des plans, c'est-à-dire des suites d'actions, permettant de passer d'un état à un autre. Ici, notre plan sera constitué de l'ensemble des actions de déplacement effectuées, on le visualisera donc par l'instruction listind(deplace). Chaque action dans un plan doit être définie en 3 étapes :

  1. les préconditions : ensemble des faits qui doivent être vrais pour que l'action puisse être réalisée
  2. la suppression des faits devenus faux après l'action
  3. l'ajout des nouveaux faits vrais, y compris de l'action réalisée

 Dans l’exemple précédent, vous pouvez vérifier que si les pré conditions ne sont pas remplies, l’action n’est pas effectuée:

| ?- met_sur(c,a).

false

Évidemment, pour que les pré conditions soient vérifiées, il suffit de réaliser des actions qui les rendent vraies, ce qui peut amener à définir des actions récursives. Ecrire une version récursive de met_sur en définissant un prédicat libere qui rend vraie la pré condition libre en réalisant une action si besoin. Cette version récursive devrait permettre de mettre le bloc b sur le bloc a en passant par plusieurs étapes intermédiaires.

4- Environnement de test et d'exécution :

on a utilisé l'interpréteur et EDI “SWI-Prolog” .

5- Le code entier :

/* prolog  Actions et plans */

:- dynamic sur/2.

sur(a,b).   

sur(b,c).   

sur(c,table).

met_sur(A,B) :-

     A \== table,

     A \== B,

     sur(A,X),

     libre(A),

     libre(B),

     retract(sur(A,X)),

     assert(sur(A,B)),

     assert(deplace(A,X,B)).

libre(table).

libre(B) :-

     not(sur(_X,B)).

/* ----------------------------------------------*/

r_met_sur(A,B) :-

     sur(A,B).

r_met_sur(A,B) :-

     not(sur(A,B)),

     A \== table,

     A \== B,

     libere(A),        /*  "action" utilisé comme pré condiction */

     libere(B),

     sur(A,X),

     retract(sur(A,X)),         /*enlève un fait qui n est plus jugé comme vrai*/

     assert(sur(A,B)),          /*ajoute un fait qui est considéré comme vrai*/  

     assert(deplace(A,X,B)).

libere(table).    /* c’est à dire il ya un vide sur la table */

libere(A) :-      /* c’est à dire déja libre */

     not(sur(_X,A)).

libere(A) :-

     A \== table,

     sur(X,A),

     libere(X),      /*  recursion */

     retract(sur(X,A)),

     assert(sur(X,table)),

     assert(deplace(X,A,table)).

do(Blist) :-      

      do_all(Blist,Blist).

do_all([B|R],Allgoals) :-          /* déjà vrai  */

     call(B),

     do_all(R,Allgoals),!.         /* continuer avec le reste des buts */

do_all([B|_],Allgoals) :-          /* il faut le traiter */

     achieve(B),

     do_all(Allgoals,Allgoals).    /* revenir en arrière et vérifier les anciens buts */

do_all([],_Allgoals).              /* finis */

achieve(sur(A,B)) :-

     r_met_sur(A,B).

6- Exemple d’exécution :

?-  do([sur(a,table),sur(b,a),sur(c,b)]).

true.

?- listing(deplace).

:- dynamic deplace/3.

deplace(a, b, table).

deplace(b, c, a).

deplace(c, table, b).

true.

?-

On peut améliorer notre monde des blocs en ajoutant des formes nouvelles :

  • des pyramides, qui peuvent se poser sur la table mais sur lesquelles on ne peut rien poser
  • des boules qui peuvent être mises dans des boîtes, quand elles sont vides (si les cubes sont en fait des boîtes) mais sur lesquelles on ne peut rien poser
  • des blocs allongés plus grands que les cubes, qu'on peut empiler les uns sur les autres et sur lesquels on peut mettre des cubes ou des boîtes, mais qu'il vaut mieux ne pas poser eux-mêmes sur des cubes ou des boîtes.

387