Travaux pratiques Prolog (15 et 22 novembre 2004)

Découverte de GNU-prolog, unification

On considère les prédicats suivants :

	parent(X,Y) = X a pour parent Y
    femme(X) = X est une femme 
    homme(X) = X est un homme

Définir les prédicats familiaux suivants

	   fille(X,Y) = X a pour fille Y 
       fils(X,Y) = X a pour fils Y  
       enfant(X,Y) = X a pour enfant Y 
       mère(X,Y) = X a pour mère Y 
       père(X,Y) = X a pour père Y 
       grand_mère(X,Y) = X a pour grand-mère Y 
       grand_père(X,Y) = X a pour grand-père Y 
       grand_parent(X,Y) = X a pour grand-parent Y 
       soeur(X,Y) = X a pour soeur Y 
       frère(X,Y) = X a pour frère Y 
       cousine(X,Y) = X a pour cousine Y 
       cousin(X,Y) = X a pour cousin Y 
       tante(X,Y) = X a pour tante Y 
       oncle(X,Y) = X a pour oncle Y 
       ancêtre(X,Y) = X a pour ancêtre Y

On pourra utiliser l'arbre disponible à http://gperilhous.free.fr/Logique/Solgenealogie.html comme source d'inspiration familiale.

Utilisation basique de prolog : structure de données + requêtes.

On considère la base de données suivante, qui décrit les employés d'une entreprise (par exemple, pour la première clause, antoine est dans le département des ventes, a une fonction de secrétaire, est dans l'entreprise depuis 6 ans, gagne 10000 € par an, et a pour chef xavier). 

chef(employe(antoine,ventes,secretaire,6,10000),xavier). 
chef(employe(xavier,ventes,directeur,2,15000),boss).    
chef(employe(boss,direction,president,12,30000),boss). 
chef(employe(lucie,achats,direction,1,14000),boss).    
chef(employe(anne,achats,secretaire,11,10000),lucie).
chef(employe(jerome,achats,secretaire,11,10000),lucie).
chef(employe(etienne,achats,stagiaire,1,2000),anne).

Ecrivez des règles Prolog pour répondre aux questions suivantes :

  1. departement/2 : trouver le département dans lequel une personne travaille.
  2. directeur/2 : étant donné le nom d'une personne, trouver qui est le directeur du département dans lequel elle travaille.
  3. employe_valide/1 : la structure de l'entreprise étant hiérarchique, on doit pouvoir remonter depuis n'importe quel employé vers le boss. Le prédicat employe_valide permettra de vérifier qu'un employé est bien sous les ordres du boss en remontant la chaine hiérachique..
  4. salaire/2 : donne le salaire d'un employé
  5. salaire_reel/2 : donne le salaire d'un employé en ajoutant au salaire de base un bonus, en utilisant les règles suivantes : 1/ tous les employés présents depuis 5 ans ou plus ont un bonus de 5000€. 2/ Aucune personne ne peut gagner plus que son chef (attention le cas du boss est évidemment spécial).

Un peu de mathématiques et de récursion

    1. Définir un prédicat factorielle/2 qui calcule la factorielle de N (fact(0)=1, fact(n) = n*fact(n-1), pour n>0).
    2. Définir un prédicat fibonnaci/2 qui calcule la suite de Fibonnaci de N (fib(0) = 1, fib(1) = 1, fib(n) = fib(n-1)+fib(n-2), pour n>1).

(on utilisera la fonction is pour réaliser les calculs, par exemple N is N+1)

Coupure

  1. Supposons qu'on ait les faits suivants dans un programme Prolog :

    2. p(a). q(a,1). r(1,1). r(3,5).
    p(b). q(a,2). r(1,2). r(3,6).
    q(b,3). r(2,3). r(4,7).
    q(b,4). r(2,4). r(4,8).

    Quels sont les résultats des requêtes suivantes ?

     

  2. On considère le programme suivant, qui définit le troisième argument (numérique) comme le maximum des deux premiers.

    max(X,Y,X) :- X >= Y, !.
    max(X,Y,Y).

    La requête max(7,5,5). répond Yes !, déterminez pourquoi et corrigez la définition de max.

Complément cours : négation

La négation en prolog est appelée "négation par l'échec".

La façon standard de représenter le not est ainsi de la forme (fail renvoyant un échec) : 

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

Attention, cette négation n'est pas une négation logique standard, et peut fonctionner étrangement du fait de son mécanisme.

Un prolog comme GNU-prolog (et d'autres) propose le prédicat \+ pour signifier la négation.

Complément cours : If-then-else

Il est possible ne Prolog de mimer le "if-then-else" des langages informatiques standards?

Pour cela, on peut définir une expression de la forme : 

S :- P, !, Q.   /* si P s'unifie, on essaie d'unifier Q */
S :- R 			/* sinon, on unifie R */

Un Prolog comme GNU-prolog (et d'autres) permet de représenter une structure if-then-else sous la forme suivante 

S :- (P -> Q ; R)

Manipulations de listes

  1. Définir un prédicat renverse/2, tel que renverse(L1,L2)est vrai si L2 et la liste inverse de L1.
  2. Définir un prédicat sousens/2, tel que sousens(L1,L2)est vrai si L1 est un sous-ensemble de L2.
  3. Définir un prédicat average/2, tel que average(L, N) est vrai si N est la moyenne des entiers de N, ou 0 si la somme est 0
  4. Définir un prédicat sommecarres/2, tel que sommecarres(L, N) est vrai si N est la somme des carrés des nombres de L.
  5. Définir un prédicat maxlist/2, tel que maxlist(L, N) est vrai si N est le plus grand élément de L.
  6. Définir un prédicat moinsder/2, tel que moinsder(L1, L2) est vrai si si L2 est L1 moins le dernier élément.
  7. Définir un prédicat debut/3, tel que debut(L1,N,L2) est vrai si L2 contient les N premiers éléments de L1.
  8. Définir un prédicat pairs/2, tel que pairs(L1,L2) est vrai si L2 contient les éléments de L1 pairs, dans le même ordre.

Utilisation de asserta, retract, retractall, findall, clause ; affichages variés (write)

Reprendre la base familiale du premier exercice. En utilisant les clauses ci-dessus, créer un programme proposant interactivement d'ajouter des enfants à la famille (sexe, parent), d'en enlever (on ne peut enlever que des enfants), de lister puis d'afficher l'ensemble des femmes de la famille. Créer enfin un programme pour afficher l'ensemble des prédicats familiaux qu'on a défini.

Remerciements

http://www.cs.may.ie/~jpower/Courses/PROLOG/ a été source d'inspiration pour quelques exercices.