Programmation Logique

class: center
# Cours de programmation logique
# E.I.S.T.I. ING1 GI

---

# Sommaire
* Swi Prolog
* Historique
* Faits, règles, requêtes
* Syntaxe
* Liste
* Affichage
* Enigmes
---
###**Swi Prolog**
* Interpréteur Prolog gratuit et open source
	* Linux
	* Windows
	* Mac OS
	* En Ligne: Swish [https://swish.swi-prolog.org/]

---
###**Philosophie**: Programmer avec la logique
Différent des autres types de langages de programmation
	
* Déclaratif (comme html, make, sql, ...)
* Récursif (comme ocaml, haskell, scala, ...)
	* pas de boucles !
* Relationnel
	* pas de fonctions !!	
* Unification
	* pas de contrôle !!!
* Homoiconicité
	* meta à tous les étages: un programme est aussi une structure de données primitive
	* en prolog, il s'agit d'un *terme*
	* aspect réflexif

---
###**Historique**
* 1972: Alain Colmerauer et Philippe Roussel: premier interpréteur Prolog
* 1977: David H.D. Warren: implémentation du compilateur DEC10
* 1980: Pereira et Warren: implémentation des DCG (prolog pour traitement du langage naturel)
* 1980-1990: Japon et Europe: Croissance de Prolog (ordinateur de 5eme génération)
* 2005: Nasa: Interface en langage naturel pour ISS
* 2011: IBM: Partie Question/Réponse de Watson, IA pour Jeopardy
* 2017: Mort d'Alain Colmerauer

---
###**Prolog aujourd'hui**
* Avantages
	* Programmes souvent légers (en nombre de lignes de code)
	* Donc souvent bien écrits
	* Et faciles à maintenir
* En réalité:
	* Traitement automatique du langage (TALN ou NLP)
	* Intelligence Artificielle (IA, notamment programmation par contrainte)
	* Applications Web: REST API, Web semantique
	* Big Data: Datalog

---
###**Principes généraux**
* Décrire un problème (langage déclaratif)
* Poser une question ?
* Attendre que Prolog trouve la solution !

###**Conséquences**
* Penser déclaratif (quoi), pas procédurale (comment)
* Langage de haut niveau
	* moins efficace que C par exemple
	* très adapté au prototypage rapide
	* idéal pour IA

---
###**Base de connaissances**

Terme: type primitif de base du langage

* variables
	* chaîne alphanumérique commençant par une  majuscule
	* chaîne alphanumérique commençant par un sous_ligné (si on ne souhaite pas connaître sa valeur)
	* *exemples:* `Var`, `X`, `_1`, `_inutile`
* termes élémentaires
	* atome: chaîne alphanumérique commençant par une  minuscule ou chaîne alphanumérique entourée de simple quote 
	* *nombre:*  entiers ou flottants
	* *exemples:* `a`, `'Toto'`, `1`, `1.2`
* termes composés
	* `atome(terme,...,terme)`
	* *exemples:* `sommet(a)`, `nom('Toto')`, `succ(0)`, `succ(succ(0))`, `cons(a,cons(X,nil))`
	
---
###**Base de connaissances (suite)**
Relations (ou atome logique):

* Exprime une relation entre des termes
* Valeur vraie (`true`) ou faux (`false`)
* *Syntaxe:* `atome(terme,...,terme)`
* *Exemples:* 
	* `arc(a,b)` signifie qu'il y a une arête entre a et b
	* `pere_fils('Toto','Titi')` signifie que 'Toto' est le père de 'Titi'

---
###**Base de connaissances (fin)**
Clauses:

* Faits: connaissance non conditionnelle
	* *Syntaxe:* atome ou terme composé suivi de .
	* *Exemples:* `a.`  `arc(a,b,2).`
* Règles: connaissance conditionnelle
	* *Syntaxe:* `relation :- relation[,relation]*.`
	* et logique: ,
	* *Exemple:* ` grand_pere(X,Y) :- pere_fils(X,Z),pere_fils(Z,Y).`

---
###**Exemple complet pour finir !!!**

Recherche de chemin dans un graphe

```prolog
	arc(a,b,2).
	arc(a,g,6).
	arc(b,e,2).
	arc(b,c,7).
	arc(g,e,1).
	arc(g,h,4).
	arc(e,f,2).
	arc(f,c,3).
	arc(f,h,2).
	arc(c,d,3).
	arc(h,d,2).
	chemin(X,Y) :- arc(X,Y,_).
	chemin(X,Y) :- arc(X,Z,_),arc(Z,Y,_).
	chemin(X,Y) :- arc(X,Z,_),arc(Z,W,_),arc(W,Y,_).
	% ... commentaire
	% comment generaliser sans boucle ??
```

---
###**Exemple complet pour finir !!!**
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/p/evblBVqp.pl" 
  width="100%" height="600px" frameborder="0" allowfullscreen>
</iframe>

---
###**Exercices**

**Préambule:**

Vous avez 2 possibilités pour réaliser les exercices:

* En local sur votre PC
	* Editer une base de faits au format .pl avec votre éditeur préféré.
	* Lancer la commande prolog (ou swipl) dans un shell
	* Au prompt (?-), commencez par charger votre base de fait avec la commande [nom_fichier].
	* Vérifiez qu'il n'y a pas d'erreur de syntaxe ni de warning
	* Posez les questions à l'interpréteur et vérifiez les réponses obtenues
* A distance en utilisant Swish  [https://swish.swi-prolog.org/]
	* Créer un nouveau programme en cliquant sur Program dans la fenêtre de gauche.
	* Editer une base de faits dans cette fenêtre de gauche
	* Posez les questions à l'interpréteur  et vérifiez les réponses obtenues,
	fenêtre en bas à droite, contenant le prompt (?-).
---
###**Exercices**

**Exercice 1: Graphe (suite)**

Comment transformer le prédicat chemin de telle sorte qu'il puisse 
construire un chemin solution ?

---
###**Exercices**

**Exercice 2: Arbres binaires**

En prolog, on peut représenter un arbre vide par l'atome nil 
par exemple, et un arbre non vide par un terme t(X,L,R), 
où X est la racine et L et R les sous arbres gauche et droite.
 
Ecrire un prédicat qui vérifie si son argument est un arbre binaire:

```prolog
		?- istree(t(a,t(b,nil,nil),nil)).
		Yes
		?- istree(t(a,t(b,nil,nil))).
		No	
```

---
###**Exercices**

**Exercice 3: Arbres binaires (suite)**

Ecrire un prédicat qui vérifie si un arbre binaire est symétrique.
Cela signifie que l'on peut tracer une droite verticale depuis la racine 
et que le sous-arbre droit est le miroir du sous-arbre gauche 
(structurellement, on ne s'intéresse pas aux valeurs des noeuds).

---
###**Opérations de comparaison**
.pull-left[
* unification:

`=, \=`

* (in)égalité de termes:

`==, \==`

* (in)égalité numérique:

`=:=, =\=`

* opérateurs de comparaison:

`<,>,=<,>=`
]

.pull-right[
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="500px" height="500px" frameborder="0" allowfullscreen>
</iframe>
]

---
###**Affectation numérique**

* en utilisant la librairie `clpfd`
```
?- use_module(library(clpfd)).
?- X #= 1+3.
```

* en utilisant l'opérateur `is`
```
?- X is 1+3.
```

A priori identique sauf:
* `#=` ne fonctionne qu'avec les entiers
* `#=` est inversible (cf cours sur clpfd)
* `is` comme alternative sur les réels. Attention, non inversible.

---
###**Listes**

Une liste est une séquence finie d'éléments

Une liste peut contenir n'importe quel terme

La longueur d'une liste est son nombre d'éléments

Les éléments d'une liste sont entourés de crochets et séparés par des virgules:`[a,1,X,arc(a,b,2)]`

La liste vide s'écrit: `[]`

---
###**Listes**
Une liste non vide est composée de deux parties:
* La tête: premier élément de la liste
* Le reste: la liste privée de son premier élément

L'opérateur `|` permet de décomposer une liste en sa tête et son reste:
```
?- [H|T]=[a,1,X,arc(a,b,2)].
H = a,
T = [1, X, arc(a, b, 2)].
```
```
?- [H1,H2|T]=[a,1,X,arc(a,b,2)].
H1 = a,
H2 = 1,
T = [X, arc(a, b, 2)].
```

---
.pull-left[
**Listes: arrêt à la fin**
```
% longueur(L,N)
longueur([],0).
longueur([_X|L],N):-
	longueur(L,N1),
	N #= N1+1.
```
**Listes: arrêt à un élément**
```
% membre(X,L)
membre(X,[X|_L]).
membre(X,[_Y|L]):-
 membre(X,L).
```
**Listes: arrêt à une position**
```
% nieme(N,L,X)
nieme(1,[X|_L],X).
nieme(N,[_X|L],Elt):-
 N1 #= N-1,
 nieme(N1,L,Elt).
```
]
.pull-right[
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="500px" height="600px" frameborder="0" allowfullscreen>
</iframe>
]

---
.pull-left[
**Affichage:**
* Les prédicats `write\1`, `writeln\1` et `write_term\2` permettent d'afficher le terme passé en paramètre, ainsi que les éventuelles [options](https://www.swi-prolog.org/pldoc/man?section=termrw)
* Les prédicats `listing\1` et `listing\0` permettent
d'[afficher le code source](https://www.swi-prolog.org/pldoc/man?section=listing) des prédicats ajoutés à la base de connaissance
]
.pull-right[
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="500px" height="600px" frameborder="0" allowfullscreen>
</iframe>
]

---
**Exercice**: Tester les prédicats `longueur`, `membre` et `nieme`  puis avec les prédicats prédéfinis `length`, `member` , `nth0` et `nth1`. Comparez les résultats.

```
	?- longueur([],N).
	?- longueur(L,0).
	?- longueur([a,b,c],N).
	?- longueur(L,3).
	?- longueur(L,N).
```
```
	?- membre(a,[a,b,c]).
	?- membre(d,[a,b,c]).
	?- membre(b,[a,b,c,d,b,e]).
	?- membre(X,[a,b,c]).
	?- membre(X,[]).
	?- membre(X,L).
```
```
	?- nieme(1,[a,b,c],E).
	?- nieme(0,[a,b,c],E).
	?- nieme(I,[a,b,c],b).
	?- nieme(I,[a,b,c,d,b,e],b).
	?- nieme(I,[a,b,c],E).
	?- nieme(I,L,E).
```

---

**Exercice:** Réécrire le prédicat permettant de résoudre le problème `graphe` en utilisant une liste pour retourner le chemin résultat. 
Pour éviter de parcourir les cycles infinis, vous pourrez utiliser le prédicat length, qui permet d'énumérer les listes par tailles croissantes.
```
	?- chemin(a,f,Liste).
		 Liste = [a,b,e,f]	
```

---
###**Enigmes**

**Exemple:** Trois enfants font la course. A l'arrivée, Toto dit qu'il a terminé avant son camarade qui porte un maillot rouge. 
Lolo, qui porte un maillot jaune, dit qu'il est arrivé avant le garçon qui 
 porte un maillot vert. 
Etablir l'ordre d'arrivé des trois enfants.

```
pb(Struct):-createListe(Struct, 3,2),faits(Struct).

faits(Struct) :-
        avant3([toto,_],[_,rouge],Struct),
        avant3([lolo,jaune],[_,vert],Struct).

createListe(L,NbLst,NbElt):-length(L,NbLst), createListe(L,NbElt).
createListe([],_).
createListe([L1|R],NbElt):-length(L1,NbElt), createListe(R,NbElt).

avant3(X,Y,[X,Y,_]).
avant3(X,Y,[X,_,Y]).
avant3(X,Y,[_,X,Y]).
```
---
###**Exercice: Enigme d'Einstein**
Cinq maisons consécutives, de couleurs différentes, sont habitées par des hommes de différentes
nationalités. Ils possèdent tous un animal différent, ont chacun une boisson préférée différente et
fument des cigarettes différentes. **Qui boit de l'eau et qui possède un zèbre sachant que** :
* Le norvégien habite la première maison,
* La maison à  coté de celle du norvégien est bleue,
* L'habitant de la troisième maison boit du lait,
* L'anglais habite la maison rouge,
* L'habitant de la maison verte boit du café,
* L'habitant de la maison jaune fume des kool
* La maison blanche se trouve juste après la verte,
* L'espagnol a un chien,
* L'ukrainien boit du thé,
* Le japonais fume des craven
* Le fumeur de old gold a un escargot,
* Le fumeur de gitane boit du vin,
* Un voisin du fumeur de chesterfield a un renard,
* Un voisin du fumeur de kool a un cheval.

---
###**Opérations avancées sur les listes**
```
include(:Goal, +List1, ?List2)
```
Filtre les éléments pour lesquels le prédicat `Goal` est vrai (ie les éléments `Xi` de `List1` tels que `call(Goal,Xi)` retourne `true`)

---
###**Opérations avancées sur les listes**
```
exclude(:Goal, +List1, ?List2)
```
Filtre les éléments pour lesquels le prédicat `Goal` est faux (ie les éléments `Xi` de `List1` tels que `call(Goal,Xi)` retourne `false`)

---
###**Opérations avancées sur les listes**
```
partition(:Pred, +List, ?Included, ?Excluded)
```
Filtre les éléments selon le prédicat `Pred` (ie les éléments `Xi` de `List` tels que `call(Pred,Xi)` retourne `false` sont placés dans `?Excluded` et ceux tels que `call(Pred,Xi)` retourne `true` sont placés dans `?Included`)

---
###**Opérations avancées sur les listes**
```
maplist(:Goal, ?List1)
maplist(:Goal, ?List1, ?List2)
maplist(:Goal, ?List1, ?List2, ?List3)
maplist(:Goal, ?List1, ?List2, ?List3, ?List4)
```
Retourne `true` si le prédicat `Goal` peut être appliqué à tous les éléments des  `?ListI`

---
###**Opérations avancées sur les listes**

```
foldl(:Goal, +List, +V0, -V)
foldl(:Goal, +List1, +List2, +V0, -V)
foldl(:Goal, +List1, +List2, +List3, +V0, -V)
foldl(:Goal, +List1, +List2, +List3, +List4, +V0, -V)
```
Retourne `true` si la valeur `V` contient la valeur calculée selon le schéma suivant:
```
foldl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0, Vn) :-
      P(X11, ..., Xm1, V0, V1),
      ...
      P(X1n, ..., Xmn, V', Vn).
```
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="900px" height="200px" frameborder="0" allowfullscreen>
</iframe>

---
###**Opérations avancées sur les listes**
```prolog
scanl(:Goal, +List, +V0, -Values)
scanl(:Goal, +List1, +List2, +V0, -Values)
scanl(:Goal, +List1, +List2, +List3, +V0, -Values)
scanl(:Goal, +List1, +List2, +List3, +List4, +V0, -Values)
```
Retourne `true` si la valeur `V` contient la valeur calculée selon le schéma suivant:
```prolog
scanl(P, [X11,...,X1n], ..., [Xm1,...,Xmn], V0,
      [V0,V1,...,Vn]) :-
      P(X11, ..., Xm1, V0, V1),
      ...
      P(X1n, ..., Xmn, V', Vn).
```
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="900px" height="200px" frameborder="0" allowfullscreen>
</iframe>

---
###**Opérations avancées sur les listes**
```
findall(+Template, :Goal, -Bag)
```
Recherche toutes les solution du prédicats `Goal` et ajoute chaque `Template` trouvé dans la liste `Bag`, pouvant donc contenir des doublons. `Bag` est vide si `Goal` n'a pas de solution.

---
###**Opérations avancées sur les listes**
```
list_to_set(+List, ?Set)
```
Supprime les doublons de `List` en gardant l'ordre des éléments

---
###**Prédicats extralogiques**
.pull-left[
**Pourquoi contrôler l'exécution ?**
```
min(X,Y,X) :- X =< Y.
min(X,Y,Y) :- X > Y.
% 2 tests systématiques pour >
```

```
membre(X,[X|_L]).
membre(X,[_Y|L]) :-
	membre(X,L).
% réussit autant de fois que l'élément a d'occurrences
```
Utiliser le prédicat `time/1` pour évaluer le temps d'exécution des prédicats
]
.pull-right[
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="500px" height="500px" frameborder="0" allowfullscreen>
</iframe>
]

---
###**La coupure ! **
.pull-left[
**Contrôle ne s'exprimant pas en logique d'ordre 1: extralogique**
```
min(X,Y,X) :- X =< Y,!.
min(X,Y,Y).
% 1 seul test  pour > ou =<
```

```
membre(X,[X|_L]):-!.
membre(X,[_Y|L]) :-
	membre(X,L).
% réussit une seule fois 
% si l'élément est présent
```
]
.pull-right[
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="500px" height="500px" frameborder="0" allowfullscreen>
</iframe>
]

---
###**La coupure ! **
**Fonctionnement général**
```
p :- ...
p :- ...
p :- B1, B2, ... , Bk, !, ... , Bn.
p :- ...(2)...
p :- ...(3)...
```
* Le cut ! est évalué à vrai.
* Il bloque l'évaluation des `B1, B2, ..., Bk`.
* Il bloque également l'évaluation des règles `p :-...` situées après lui (2) et (3).

---
###**Prédicat différent**
```
different(X,X) :-!,fail.
different(X,Y).
```
<iframe style = "-webkit-transform: scale(0.8);" 
	src="https://swish.swi-prolog.org/" 
  width="900px" height="450px" frameborder="0" allowfullscreen>
</iframe>

---
###**Négation**
```
not(But) :- call(But),!,fail.
not(But).
```
On pourra écrire `\+` pour la négation, qui permet de bien se rappeler qu'en prolog, il s'agit de déterminer si un prédicat est non prouvable (`\` pour non et `+` pour prouvable), au lieu de la négation standard.

---
###**Lecture de fichiers**
```
open(+SrcDest, +Mode, --Stream, +Options)
```
Ouvre un flux `Stream` à partir de l'url `SrcDest` avec le mode `Mode` (read,write,append). 
Options est une liste d'options pouvant être vide [].

```
close(+Stream, +Options)
write(+Stream, +Term)
read(+Stream, -Term)
```

---
###**Lecture de fichiers**
```
csv_read_file(+File, -Rows, +Options)
```
Lit un fichier csv à partir de l'url `File` et retourne le résultat sous forme d'une liste de prédicats, ayant par défaut le nom `row`.
Options est une liste d'options pouvant être vide [].

---
###**Transormation Terme - Liste**
```
?Term =.. ?List
```
Transforme une liste en un terme dont le nom est le premier élément de la liste et les arguments les éléments suivants

---
###**Ajout/Suppression dynamique de faits ou règles**
```
asserta(+Term)
retract(+Term)
retractall(+Head)
```
Ajoute ou supprime dynamiquement des faits ou règles de la base de données.
`retractall` supprime tous les termes correspondant aux règles `Head` ou `Head :- ...`

---
###**Programmation par contraintes:**
```
:-use_module(library(clpfd))
```
```
Expr1 #= Expr2	Expr1 equals Expr2
Expr1 #\= Expr2	Expr1 is not equal to Expr2
Expr1 #>= Expr2	Expr1 is greater than or equal to Expr2
Expr1 #=< Expr2	Expr1 is less than or equal to Expr2
Expr1 #> Expr2	Expr1 is greater than Expr2
Expr1 #< Expr2	Expr1 is less than Expr2
```

---
###**Programmation par contraintes:**
```
-Expr	Unary minus
Expr + Expr	Addition
Expr * Expr	Multiplication
Expr - Expr	Subtraction
Expr ^ Expr	Exponentiation
min(Expr,Expr)	Minimum of two expressions
max(Expr,Expr)	Maximum of two expressions
Expr mod Expr	Modulo induced by floored division
Expr rem Expr	Modulo induced by truncated division
abs(Expr)	Absolute value
Expr // Expr	Truncated integer division
Expr div Expr	Floored integer division
```

---
###**Programmation par contraintes:**
```
#\ Q	True iff Q is false
P #\/ Q	True iff either P or Q
P #/\ Q	True iff both P and Q
P #\ Q	True iff either P or Q, but not both
P #<==> Q	True iff P and Q are equivalent
P #==> Q	True iff P implies Q
P #<== Q	True iff Q implies P
```

---
###**Programmation par contraintes:**
```
?Var in +Domain
+Vars ins +Domain
label(+Vars)
labeling(+Options, +Vars)
all_distinct(+Vars)

```