Consignes

La collaboration orale est encouragée, mais le partage de code et le copier/coller (via Discord, github, etc.) n'est pas autorisé et pourra être pénalisé.

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 "|".

Vous pouvez quitter l'interpréteur avec Control-d pour fermer l'entrée standard.

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 = f(banane).
X = f(banane).
?- f(banane) = Y.
Y = f(banane).
?- f(X) = f(banane).
X = banane.
?- f(X) = g(Y).
false.

Quelques exercices faciles

Le fichier test-genealogie.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-genealogie.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-genealogie.pl
...
?- X = pere(theophile, louise).
?????
?- pere(theophile, louise) = X.
?????

Testez ces requêtes !

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-genealogie.pl) et vérifiez qu'elles donnent le même résultat.

Profitez on pour corriger le bug suivant : 

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

N'utilisez pas l'opérateur "OU" de Prolog (|) pour résoudre le problème. Vous pouvez le faire simplement en ajoutant des règles.

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-genealogie.pl, une première définition de la relation fratrie/2 (pour "frère ou sœur") pourrait être 

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

Cela fonctionne 

swipl TP3/test-genealogie.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 sœur !

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).

Testez les requêtes suivantes 

?- fratrie(edith, edith).
...
?- fratrie(X, edith).
...
?- fratrie(edith, X).
...

Qu'en pensez-vous ?

Expliquez ce phénomène et proposez 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).

Testez le prédicat contient/2 pour comprendre son comportement.

Dans un fichier listes-NOM.pl :

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

  2. Écrivez un prédicat voisins/3 dont le sens est X et Y sont 2 éléments consécutifs de L (dans n'importe quel ordre).

  3. É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([_|L],A) :- contient1(L,A).

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

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

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

  1. Comparez les sur des requête du style 

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

  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 ? (Attention, l'ordre des arguments de member/2 est inversé par rapport à celui de contient/2.)

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/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.

  • Attention, utilisez une version de contient/2 sans coupure !

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,_,_)),

  • Attention, utilisez une version de contient/2 sans coupure !

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 sœur 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)

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 sœur 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.

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.)

Quelques détails

Le non respect des consignes suivantes entrainera automatiquement un retrait de points de votre note finale !

  1. Le chargement de votre jeux ne devra pas provoquer d'erreur ou de warning de la part de SWI-prolog.

  2. Votre fichier devra comporter une commande jouer. qui permet de lancer la partie. Si votre jeu est paramétrable, documentez le dans votre fichier README, et la commande jouer. devra utiliser des valeurs par défaut raisonnables.

  3. Ma première impression de votre jeu va se faire en lançant la commande jouer., avant même de lire votre fichier README. L'ergonomie de votre jeu est donc un facteur important.

    • Fournissez des raccourcis pour les commandes courantes (n/0 pour nord/0, r/0 pour regarder/0, etc.).

    • Il faut pouvoir obtenir la liste des commandes existantes facilement (instructions/0).

    • Affichez les déplacements possibles (sauf éventuellement pour les passages secrets).

    • N'imposez pas de contrainte inutile. Par exemple, si vous avez une commande combiner/2, il faut que combiner(pile, lampe). et combiner(lampe, pile) soient équivalentes.

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

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

  6. En plus du fichier MON_JEU.pl, vous devez fournir un fichier MON_JEU.sol contenant une solution. Ce fichier contiendra une suite des commandes (une par ligne) pour terminer votre jeux. (Regardez le fichier le_talisman_perdu.sol.)

    Je testerais avec la commande 

    $ swipl MON_JEU.pl < MON_JEU.sol

    N'hésitez pas à fournir plusieurs fichiers solution si vous souhaitez illustrer plusieurs fins (succès, échec, fin alternative, etc.)

  7. Votre jeu devra comporter plusieurs fonctionnalités "avancées" (voir plus bas).

    Les fonctionnalités implémentées doivent être listées dans votre fichier README. Pour chacune d'entre elles, vous devez également fournir quelques explications et fournir une suite de commandes pour que je puisse les tester facilement.

    Voici un extrait possible d'un fichier README : 

        ### Gestion des objets cachés

    Certains objets peuvent satisfaire un prédicat "hidden/1". Par exemple, la
    clé du coffre, dans le bureau, est déclarée avec

      position(cle, bureau).
      hidden(cle).

    L'action "fouiller/0" utilise le prédicat Prolog "retract/1" pour rendre
    un objet visible. Il sera donc ensuite affiché.

    Exemple :
      jouer.
      n.
      prendre lampe.
      o.
      % On est dans le bureau.
      regarder.
      % La clé n'est pas listée.
      fouiller.
      % On a le message "Vous trouvez une clé cachée derrière le bibelot,
      % sur la cheminée."
      regarder.
      % La clé est maintenant listée.

    ...

Fonctionnalités avancées

Plusieurs points du barème sont réservés à l'implémentation de quelques fonctionnalités "avancées". Toutes n'ont pas la même difficulté, et je vous conseille d'en choisir au moins 3 si vous souhaitez avoir les points associés.

Je vous rappelle que vous devez lister et décrire chacune des fonctionnalités implémentées dans votre fichier README.

Voici quelques exemples de telles fonctionnalités. La liste suivante n'est pas exhaustive. N'hésitez pas à faire d'autres choses !

présence d'objets cachés

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.

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.

présence d'aléatoire

Attention, dans ce cas, votre fichier solution devra initialiser la graine du générateur (avec setrand/1) pour pouvoir fonctionner !

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.

Attention, il faut que le jeu reste fluide. Il est très frustrant d'avoir une interaction comme 

  ?- boire(potion).
  Vous n'avez pas potion.
  true.
  ?- prendre_dans_main(potion).
  Votre main contient déjà :
    épée
  true.
  ?- poser(épée).
  épée est maintenant par terre.
  true.
  ?- prendre_dans_main(potion).
  Vous avez potion en main.
  true.
  ?- boire(potion).
  Vous devenez invisible.
  true.
  ?- prendre(épée).
  Vous ramasser épée.
  true.
  ?- prendre_dans_main(épée).
  Vous avez épée en main.
  true.
raccourcis

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 en langue naturelle

voir parsing du langage naturel.

...