Consignes

Le rendu de ce TP se fera uniquement par TPLab et consistera en une archive (zip, tar, etc.) contenant un répertoire TP3-NOM avec :

Vous aurez compris que NOM devra être remplacé par votre nom (ou vos noms en cas de binômes) !

Tous vos fichiers doivent comporter une entête avec votre noms et votre groupe de TP.

Tout non respect d'une ou plusieurs de ces consignes entrainera automatiquement un retrait de points sur votre note !

Liens utiles

Si SWI-Prolog n'est pas installe dans votre salle (et seulement dans ce cas), vous pouvez utiliser l'interpréteur SWI-Prolog en ligne.

Préliminaires : Prolog

Utilisation de l'interpréteur

Nous allons utiliser SWI Prolog, une distribution libre et gratuite du langage de programmation Prolog.

Vous pouvez l'installer sous Ubuntu (paquet swi-prolog) et même (il parait) sous Windows ou Mac.

Le plus simple est d'utiliser un éditeur de texte pour écrire des fichiers Prolog (extension .pl). Vous pouvez ensuite lancer l'interpréteur avec le nom d'un fichier en argument : 

$ swipl test.pl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.0.2)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?-

Le prompt "?-" indique que l'interpréteur attend une requête de votre part. Toute requête doit se terminer par un point "." et un retour charriot. Lorsqu'une requête occupe plusieurs lignes, le prompt devient "|".

Un exemple simple

Le fichier suivant contient l'exemple standard : 

% pour montrer qu'un "truc" est mortel, il suffit de montrer que c'est un humain
% Autrement dit "tous les humains sont mortels"
mortel(X) :- humain(X).

% pour montrer qu'un "truc" est un humain, il suffit de montrer que c'est un philosophe
% Autrement dit "tous les philosophes sont des humains"
humain(X) :- philosophe(X).

% Louis XIV est un humain
humain(louis_XIV).

% Socrate est un philosophe
philosophe(socrate).

% Milou est un chien !
chien(milou).

Quelques points importants

  1. Les variables commencent par une majuscule.

  2. Les constantes, fonctions, prédicats et relations commencent par une minuscule. (Il est possible d'avoir des noms de prédicats plus généraux si on les écrit entre apostrophes simples : 'Louis XIV').

  3. Les commentaires sont donnés en commençant une ligne par un symbole "%". (On peut aussi avoir des commentaires sur plusieurs lignes avec /* ... */. À la différence du C, il est possible d'imbriquer ces commentaires.)

Téléchargez le fichier de test et lancez l'interpréteur dessus.

  1. Vérifiez que milou est un chien avec la requête 

    ?- chien(milou).

  2. Vérifiez que louis_XIV est mortel avec la requête 

    ?- mortel(louis_XIV).

  3. Quelles sont les réponses aux requêtes suivantes ? 

    ?- chien(socrate).
?- chien(toto).
?- souris(milou).

  4. Cherchez tous les atomes qui satisfont le prédicat mortel avec la requête 

    ?- mortel(X).

    • vous pouvez arrêter la recherche des solutions suivantes avec "Entrée", et demander d'autres solutions avec "Espace"

    • pour une requête comme celle ci, le choix de la variable X n'est pas important. (Testez avec Une_autre_variable...)

    Le point important est que bien qu'aucun atome ne soit explicitement déclaré mortel, Prolog arrive à inférer cette information.

Vocabulaire

fait

c'est une ligne de la forme 

quelque_chose(..., ...).

C'est une manière d'affirmer que quelque chose est vrai. Cela permet d'ajouter une formule dans la base de connaissances.

Les ... sont des termes (éventuellement zéro) qui peuvent contenir des variables (elles sont quantifiées universellement) et des atomes (comme dans chien(milou).).

règle

c'est un morceau du fichier de la forme 

quelque_chose(..., ...) :-
   autre_chose(..., ...),
   et_autre_chose(..., ...),
   ...
   un_dernier_truc(..., ...).

Le symbole :- peut se lire "si". La règle énonce des conditions pour que quelque_chose(..., ...) soit vrai. Les virgules "," dans le corps de la règle sont des conjonctions.

prédicat (ou relation)

c'est une séquence de faits et règles consécutives portant sur le même nom (quelque_chose dans les exemples précédents.)

atome

c'est une constante (comme socrate dans l'exemple).

terme

ce sont les arguments d'un prédicat / relation. Ils sont constitués de variables, d'atomes et de symboles fonctions.

Unification

Le symbole = en Prolog est utilisé pour l'unification, c'est à dire la recherche de valeurs pour les variables qui permettent de rendre 2 choses égales.

Cette action est symétrique : on peut toujours inverser la droite et la gauche d'une unification. 

?- X = fruit(banane).
X = fruit(banane).
?- fruit(banane) = Y.
Y = fruit(banane).
?- fruit(X) = fruit(banane).
X = banane.
?- fruit(X) = legume(Y).
false.

Quelques exercices faciles

Le fichier test-002.pl contient un morceau d'arbre généalogique. Ce fichier définit 2 relations pere/2 et mere/2 avec des lignes de la forme 

pere(theophile, louise).
mere(eugenie, louise).

pere(theophile, jean_francois).
mere(eugenie, jean_francois).

...

Nous avons donc : 

swipl TP3/test-002.pl
...
?- pere(theophile, louise).
true

(Attention, une fois que Prolog a trouvé que la relation était vérifiée, il continue de chercher d'autres justifications...)

L'arbre généalogique est également donné de manière "graphique" en haut du fichier.

À votre avis, quel sera le résultat de 

swipl TP3/test-002.pl
...
?- X = pere(theophile, louise).
?????
?- pere(theophile, louise) = X.
?????

L'unification permet d'imposer des "égalités". On peut par exemple écrire une relation grand_pere/2 avec 

grand_pere(GP, PF) :-
    pere(GP, P1),
    pere(P2, PF),
    P1 = P2.

Il est en général plus élégant de faire les unifications de manière implicite en réutilisant des variables : 

grand_pere(GP, PF) :-
    pere(GP, P),
    pere(P, PF).

Testez les deux définitions de grand_pere/2 (en les ajoutant dans le fichier test-002.pl) et vérifiez qu'elles donnent le même résultat.

Profitez on pour corriger le bug suivant : 

swipl TP3/test-002.pl
...
?- grand_pere(theophile, thomas).
false.

L'unification Prolog ne fait pas de "occur check" (test d'apparition). Normalement, il n'est pas possible d'unifier X avec f(X) ou tout autre terme contenant X. Ce test est assez couteux et Prolog ne le fait pas pour gagner du temps.

En pratique, cela ne pose pas de problème, mais formellement parlant, l'unification n'est pas toujours correcte.

La négation

Prolog a un concept de négation :

Toujours avec le fichier test-002.pl, une première définition de la relation fratrie/2 (pour "frère ou soeur") pourrait être 

fratrie(X, Y) :-
    mere(P, X),
    mere(P, Y).

Cela fonctionne 

swipl TP3/test-002.pl
...
?- fratrie(edith, louise).
true.
?- fratrie(edith, jean_francois).
true.
?- fratrie(edith, pierre).
false.

... presque 

?- fratrie(edith, X).
X = edith ;
X = louise ;
X = jean_francois.

On trouve que edith est sa propre soeur !

Utiliser la négation permet de s'en sortir.

Testez la définition suivante qui ajoute la contrainte que X et Y ne sont pas unifiables. 

fratrie(X, Y) :-
    \+ X = Y,
    pere(P, X),
    pere(P, Y).

Qu'en pensez-vous ? Proposez une explication et une solution.

on peut écrire X \= Y à la place de \+ X = Y.

Récursion et listes

Prolog a un type de données listes, assez similaire au type liste de Caml.

On peut utiliser l'unification pour définir des prédicats. Voici par exemple un prédicat deuxieme/2 dont le sens est X est le deuxième élément de la liste L : 

deuxieme(X, []) :- fail.
deuxieme(X, [Y]) :- fail.
deuxieme(X, [Y, Z | L]) :- X = Z.

Une manière beaucoup plus concise et élégante de définir le même prédicat est 

deuxieme(X, [_, X | _]).

Bien que l'on définisse des relations, le mécanisme de recherche de solution de Prolog permet de faire des calculs : il suffit de mettre une variable à la place de l'argument que l'on cherche : 

?- deuxieme(X, [17, -1, 42]).
X = -1.

Testez les 2 définitions de deuxieme/2.

Plus intéressant, on peut définir des prédicats récursifs. Voici le prédicat contient/2 : 

contient([X | _], X).
contient([_ | L], X) :- contient(L, X).

En utilisant un fichier listes-NOM.pl :

  1. Testez le prédicat contient/2 et décrivez son comportement.

  2. Écrivez un prédicat dernier/2 dont le sens est X est le dernier élément de la liste L.

  3. Écrivez un prédicat voisins/3 dont le sens est X et Y sont 2 éléments consécutifs de L.

  4. Écrivez un prédicat devant/3 dont le sens est X apparait avant Y dans L, mais X et Y ne sont pas forcément consécutifs.

Fonctionnalités "extra-logiques"

Affichage

Prolog possède également des "prédicats" qui n'ont pas de sens logique. Par exemple, 

test(X) :-
    write("La valeur de X est "), write(X), nl.

write/1 est un prédicat qui affiche quelque chose à l'écran, et qui réussi toujours. nl/0 est un prédicat qui va à la ligne ("nl" = "new line").

Prédicats dynamiques

Deux autres prédicats non logiques sont :

Ces fonctionnalités seront très utiles dans la deuxième partie du TP !

SWI Prolog impose de déclarer les prédicats dynamiques. Il faut donc inclure une ligne 

:- dynamic(mere/2).

avant la définition de mere.

Comme write/1, les prédicats assert/1 et retract/1 ne sont pas "défaits" lors du backtracking.

Il est donc important de ne les faire qu'au dernier moment !

La coupure

Le symbole ! s'appelle la coupure. Il permet de dire au moteur Prolog de ne pas faire de backtracking à ce niveau là : la coupure bloque le backtracking.

L'utilisation de la coupure permet parfois d'améliorer l'efficacité, mais son utilisation n'est pas toujours facile.

Voici 4 versions du prédicat contient/2 : 

contient1(A,[A|_]).
contient1(A,[_|L]) :- contient1(A,L).

contient2(A,[_|L]) :- contient2(A,L).
contient2(A,[A|_]).

contient3(A,[A|_]) :- !.
contient3(A,[_|L]) :- contient3(A,L).

contient4(A,[_|L]) :- contient4(A,L).
contient4(A,[A|_]) :- !.

  1. Comparez les sur des requête du style 

    ?- contient(2, [1,2,3]).
?- contient(X, [1,2,3]).
?- contient(2, L).

  2. Quels sont les avantages et les inconvénients des versions avec coupure ?

  3. La bibliothèque standard de Prolog contient un prédicat member/2. À quelle version correspond il ?

1. Problèmes logiques

1.1. Le problème des as

On peut résoudre le problème des as du TP1 en Prolog.

  1. Écrivez, dans un fichier cartes-NOM.pl un prédicat solution_as/1 qui donne la solution au problème des as.

    Votre prédicat pourra par exemple ressembler à 

    solution(L) :-
    L = [_,_,_,_],            % la solution contient 4 éléments

    contient(L, pique),       % la solution contient les 4 as
    contient(L, coeur),       % ...
    contient(L, trefle),      % ...
    contient(L, carreau),     % ...

    % en position 2, il n'y a ni l'as de trefle, ni l'as de pique
    ...

    % l'as de trefle est plus a droite que l'as de carreau
    ...

    % l'as de carreau et l'as de coeur ne sont pas voisins
    ...

  2. Vérifiez que Prolog ne trouve qu'une seule solution, et qu'elle est bien identique à celle que vous aviez trouvé au TP1.

Vous pouvez redéfinir les prédicats voisins/3 ou devant/3 pour les utiliser.

1.2. Le problème de Einstein

  1. Dans un fichier zebra-NOM.pl, écrivez un prédicat solution/1 qui recherche une solution au problème de Einstein du TP1.

  2. Vérifiez que Prolog ne trouve qu'une seule solution, et qu'elle est bien identique à celle que vous aviez trouvé au TP1.

    Attention, la version donnée au TP1 contenait un bug volontaire et avait 2 solutions quasi identiques. (Le propriétaire du zèbre était en particulier le même dans ces 2 solutions.)

  • Comme pour le problème des as, votre prédicat peut commencer par 

    solution(L) :-
    L = [_, _, _, _, _],              % il y a 5 maisons

    ...

  • Chaque élément de la solution représente un type de maison, avec un métier, un animal, un style de musique et une boisson. On peut représenter un tel élément en utilisant un symbole de fonction : maison(Type, Metier, Animal, Musique, Boisson).

    On peut par exemple modéliser le premier indice "Le musicien a une tortue." par 

        contient(L, maison(_,musicien,tortue,_,_)),

2. Un jeu d'aventure en Prolog

L'objectif de ce TP est maintenant d'écrire un jeu d'aventure textuel en Prolog. Le prototype de ce type de jeux est Colossal Cave Adventure, dont les premières versions datent de 1975.

Voila un exemple typique d'interaction 

You are standing at the end of a road before a small brick building. Around
you is a forest. A small stream flows out of the building and down a gully.

>go building

Inside Building
You are inside a building, a well house for a large spring.

There are some keys on the ground here.

There is tasty food here.

There is a shiny brass lamp nearby.

There is an empty bottle here.

>take lamp
Taken.

>light lamp
You switch the brass lantern on.

>...

Les versions originales du jeu étaient écrites en Fortran, et les jeux d'aventure textuels modernes sont souvent écrits en utilisant des langages de descriptions spécifiques (Z-machine ou Glulx).

En utilisant les concepts de base de Prolog, il est assez facile de créer un petit jeu d'aventure de ce style. Pour ceux que ça intéresse, vous trouverez de nombreux détails dans le livre de Dennis Merritt Adventure in Prolog.

2.1. Un exemple

Téléchargez le fichier le_talisman_perdu.pl et lancez le jeu : 

$ swipl le_talisman_perdu.pl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.0.2)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- jouer.

Les commandes doivent être données avec la syntaxe Prolog habituelle.
Les commandes existantes sont :
jouer.                   -- pour commencer une partie.
n.  s.  e.  o.           -- pour aller dans cette direction (nord / sud / est / ouest).
aller(direction)         -- pour aller dans cette direction.
prendre(objet).          -- pour prendre un objet.
lacher(objet).           -- pour lacher un objet en votre possession.
regarder.                -- pour regarder autour de vous.
instructions.            -- pour revoir ce message !.
fin.                     -- pour terminer la partie et quitter.

Vous êtes à l'entrée de la grotte.
À l'est se trouve la salle de vie commune où les membres du clan se réchauffent..
À l'ouest se trouve un petit passage sombre.
Tout droit, au nord, la grotte s'enfonce dans la montagne.
Votre grande soeur est là. Elle doit remplacer le shaman, emporté par une maladie.
Elle n'ose pas rejoindre le reste clan, car elle n'a toujours pas trouvé le cailloux scintillant,
talisman de la tribu.


true.

?-

Si vous devez utiliser l'interpréteur en ligne de SWI-prolog, vous devrez :

Passez quelques minutes à jouer pour vous familiariser avec le style de jeux. (Indice: la solution est donnée dans le fichier le_talisman_perdu.sol)

Cette question n'est pas notée !

Le fichier le_talisman_perdu.pl contient environ 200 lignes de code, et la plupart sont des descriptions. En voici un extrait : 

decrire(espace_de_vie) :-
    write("Cette grande salle est éclairée par un grand feu."), nl,
    write("Tout le clan est présent et les chasseurs préparent une sortie."), nl,
    write("Votre grande soeur est absente."), nl,
    write("La sortie se trouve à l'ouest."), nl.

2.2. À vous !

Écrivez votre propre jeu d'aventure en Prolog !

Vous pouvez partir du fichier mon_jeu.pl, mais ce n'est pas obligatoire.

Quelques détails cependant :

  1. Votre jeu devra comporter une commande jouer. qui permet de lancer une nouvelle partie.

  2. Votre jeu devra comporter plusieurs des éléments suivants :

    • présence d'objet caché (une clé dans un pot de fleurs, un document dans un coffre fort, un code dans une boule de cristal, etc.)

    • présence d'objets incomplets (un stylo auquel il faut ajouter une cartouche d'encre, une radio sans pile, un arc sans flèches, etc.)

    • existence de passages secrets (une trappe sous un tapis, une porte derrière une armoire, etc.)

    • présence de personnages non joueurs (un dragon qu'il faut tuer, une voyante qu'il faut interroger, etc.)

    • gestion des objets plus sophistiquée : distinction entre les objets en main, et les autres (dans un sac à dos, une poche ventrale, etc.) ; commande inventaire, etc.

    • un mécanisme de ressources (un nombre de pièces d'or à trouver, des points de vie qui diminuent, un décompte avant une explosion, etc.)

      Il vous faudra probablement rechercher comment gérer les expressions arithmétiques en Prolog pour faire ceci.

    • possibilité de se déplacer aux endroits déjà visités en une seule commande : aller(chambre) pour retourner dans la chambre en passant par les emplacements intermédiaires.

      (Bien entendu, les contraintes de déplacement doivent être vérifiées comme lors de déplacement "atomiques".)

    • définir une petite interface de parsing du langage naturel.

    • ...

  3. Votre fichier README devra fournir quelques explications sur chacune des fonctionnalités implémentées : une description fonctionnelle et quelques détails d'implémentation.

  4. Ce TP est très fortement inspiré du livre - Adventure in Prolog, de Dennis Merritt et d'un TP de David Matuszek

    N'hésitez pas à vous en inspirer, sans pour autant copier ce que vous trouvez.

    Un autre jeu d'aventure en Prolog (un peu plus complexe) du même type se trouve ici : Jolly Roger (Lancez le prédicat play/0 pour commencer la partie.)

  5. L'intérêt de votre jeu aura un impact sur la note. Soyez originaux.

  6. Le formatage de votre code aura un impact sur la note. Ne soyez pas trop originaux.

  7. Votre fichier devra avoir un nom de la forme mon_jeu.pl, et vous devez fournir un fichier mon_jeu.sol contenant une solution. Ce second fichier contiendra une suite des commandes (une par ligne) pour terminer votre jeux.

    Vous pouvez tester avec 

    $ swipl mon_jeu.pl < mon_jeu.sol

    (Attention, il faut remplacer "mon_jeu" par une description minimaliste de votre jeu !)