Programmer en Prolog
Prolog est un langage de programmation déclaratif permettant de résoudre des problèmes logiques. Le nom Prolog est l'acronyme de PROgrammation LOGique. Le principe de la programmation logique est de décrire l'énnoncé d'un problème par un ensemble d'expressions et de liens logiques au lieu de définir pas à pas la succession d'instructions que doit exécuter l'ordinateur pour résoudre la problématique.
Plusieurs implémentations de Prolog existent, aussi bien sous Windows que sous Linux.
Parmi elle il y a SWI-Prolog qui est un interpréteur Prolog gratuit et disponible aussi bien sous Windows que sous Linux.
Pour installer SWI-Prolog sous Windows téléchargez la dernière version stable sur le site swi-prolog.org ou cliquez sur le lien suivant pour télécharger la version 6.2.2 datant de 2012 :
Télécharger SWI-Prolog 6.2.2 (version 2012) pour Windows
Pour installer SWI-Prolog sous Linux Ubuntu 10.04 LTS il faut installer le paquet swi-prolog :
apt-get install swi-prolog (ou utiliser l'interface graphique Synaptic d'apt-get).
Pour appeler l'interpréteur SWI-Prolog en ligne de commande sous Linux il faut lancer la commande swipl.
On peut également citer YAP et GNU Prolog sous Linux qui sont deux autres implémentations libres de Prolog.
Pour installer YAP sous Linux Ubuntu 10.04 LTS il faut installer le paquet yap :
apt-get install yap (ou utiliser l'interface graphique Synaptic d'apt-get).
Pour appeler l'interpréteur YAP en ligne de commande sous Linux il faut lancer la commande yap.
Pour installer GNU Prolog sous Linux Ubuntu 10.04 LTS il faut installer le paquet gprolog :
apt-get install gprolog (ou utiliser l'interface graphique Synaptic d'apt-get).
Pour appeler l'interpréteur gProlog en ligne de commande sous Linux il faut lancer la commande gprolog.
Contrairement aux langages de programmation impératifs (comme le Pascal, le langage C, le Java, Perl, Ruby, Python, etc.) on ne trouvera pas de boucles For, de test If, de "fonctions", etc. dans Prolog.
Bien que la tradition veuille que le premier programme de test affiche "Bonjour" à l'écran, pour une fois nous allons faire autre chose.
Editons un nouveau fichier texte nommé toto.pl (dans Gedit sous Linux ou dans le bloc note sous Windows) :
gedit toto.pl
Voici le code source en Prolog de ce premier programme qui se contente de déclarer un ensemble de faits :
animal(chien).
animal(chat).
prenom(paul).
prenom(pierre).
prenom(jean).
Voici les faits affirmés par notre programme :
Ouvrons le programme source toto.pl dans l'interpréteur Prolog :
consult(toto).
Remarques :
Nous n'allons pas maintenant "exécuter" le programme, mais nous allons poser à l'interpréteur Prolog un ensemble de questions pour lesquelles l'interpréteur consultera les faits et les règles inscrits dans le programme.
Première question : jean est-il un prénom ?
?- prenom(jean).
L'interpréteur nous répond true : jean est bien un prénom dans la base des faits inscrits dans le programme.
Deuxième question : vincent est-il un prénom ?
?- prenom(vincent).
L'interpréteur nous répond false : vincent n'est pas un prénom dans la base des faits inscrits dans le programme.
Autre question : quels sont tous les animaux ?
?- animal(X).
La variable X va prendre pour valeur chaque nom d'animal. Pour passer d'un valeur à une autre il faut appuyer sur la touche point-virgule. Une fois que la liste est terminée, Prolog la fini par un point. Le résultat est alors :
X = chien;
X = chat.
Autre question : quels sont tous les prenoms ?
?- prenom(X).
Cette fois la variable X va prendre pour valeur chaque prénom. Le point-virgule permet toujours de passer d'une réponse à la suivante. Le résultat final est alors :
X = paul;
X = pierre;
X = jean.
Autre question : existe-t-il des animaux ?
?- animal(_).
Cette fois l'expression animal(_) sera vraie chaque fois que Prolog rencontre un animal (peut importe lequel) dans la base des faits du programme. Comme Prolog rencontre 2 animaux, la réponse à notre question est :
true ;
true.
La commande listing permet d'afficher le code source de la base de faits du programme courant :
?- listing.
Enfin, la commande halt permet de sortir de l'interpréteur Prolog :
?- halt.
Les données du problème sont : Alice et Luc sont mariés. Luc est le père de Jean.
La problématique à résoudre est : Qui est la mère de Jean ?
Dans le code source nous indiquons que :
Puis nous indiquons à Prolog que si un père est mariè à une femme, alors cette dernière est la mère du fils :
% les faits :
epouse(alice,luc). % alice est l'épouse de luc
pere(luc,jean). % luc est le père de jean% les règles :
mere(M,E):-pere(P,E),epouse(M,P). % M est la mère de E si P est le père de E et si M est l'épouse de P
Remarque : en Prolog tout ce qui suit le caractère % sur une ligne est un commentaire.
Aprés avoir ouvert le programme dans l'interpréteur Prolog (par la commande consult), posons lui quelques questions :
Question 1 : qui est l'épouse de luc ?
?- epouse(X,luc).
Réponse :
X = alice.
Question 2 : qui est l'époux d'alice ? (qui a pour épouse alice)
?- epouse(alice,X).
Réponse :
X = luc.
Question 3 : qui est le père de jean ?
?- pere(X,jean).
Réponse :
X = luc.
Question 4 : qui est le fils de luc ? (qui a pour père luc)
?- pere(luc,X).
Réponse :
X = jean.
Question 5 : qui est la mere de jean ?
?- mere(X,jean).
Réponse :
X = alice.
Question 6 : qui est le fils d'alice ? (qui a pour mère alice)
?- mere(alice,X).
Réponse :
X = jean.
Question 7 : qui est le fils de jean ? (qui a pour père jean)
?- pere(jean,X).
Réponse :
false.
Question 8 : qui est le fils de lucienne ? (qui a pour mère lucienne)
?- mere(lucienne,X).
Réponse :
false.
Question 9 : qui est la mère de qui ?
?- mere(X,Y).
Réponse :
X = alice,
Y = jean.
Question 10 : combien de liens de parenté "mère/fils" existe-t-il ?
?- mere(_,_).
Réponse : 1 seul
true.
Question 11 : existe-t-il une personne qui est sa propre mère ?
?- mere(X,X).
Réponse : NON
false.
Les données du problème sont :
La problématique à résoudre est :
Le programme source en Prolog :
Demandons à l'interpréteur Prolog de résoudre le problème en proposant une valeur pour chacune des 4 inconnues :%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Réalisé par Jean-Christophe MICHEL
% Juillet 2011
% www.gecif.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%--------------------------------------------------------
% les faits :% les 3 maisons :
maison(chateau).
maison(studio).
maison(pavillon).% les 3 animaux :
animal(chat).
animal(poisson).
animal(cheval).%--------------------------------------------------------
% les règles :% le prédicat relation constitue la relation entre une personne, son animal et sa maison :
relation(max,M,chat):-maison(M).
relation(luc,studio,A):-animal(A),A\==cheval.
relation(eric,M,A):-maison(M),M\==pavillon,animal(A).% le prédicat different est vraie seulement si ses 3 paramètres sont différents :
different(X,X,_):-!,fail.
different(X,_,X):-!,fail.
different(_,X,X):-!,fail.
different(_,_,_).% le prédicat "resoudre" indique les 4 inconnues à retrouver :
resoudre(MM,ME,AE,AL):-relation(max,MM,chat),
relation(eric,ME,AE),
different(MM,ME,studio),
relation(luc,studio,AL),
different(AE,AL,chat).
resoudre(MM,ME,AE,AL).
Et la réponse immédiate est :
MM = pavillon,
ME = chateau,
AE = cheval,
AL = poisson .
Ce qui signifie en clair que :
La problématique à résoudre était :
Les tableaux tels qu'on les connaît dans les langages impératifs n'existent pas en Prolog. Ils sont remplacés par les listes.
Une liste en Prolog s'écrit entre crochets. Exemple : [a,b,c] est une liste contenant les 3 éléments a, b et c. A l'intérieur d'une liste les éléments sont séparés par une virgule losqu'ils sont énumérés un à un.
La liste vide est représentée par [].
L'opérateur | (barre verticale) permet de définir une liste constituée de :
[X|L] est une liste obtenue en ajoutant l'élément X au début de la liste L.
Par exemple les écritures suivantes sont toutes équivalentes : [a|[b,c]] = [a|[b|[c]]] = [a|[b|[c|[]]]] = [a,b,c]
Affichage de tous les éléments d'une liste
Le programme source est :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
Aprés avoir ouvert ce programme simple dans l'interpréteur Prolog (par la commande consult), utilisons la fonction afficher_liste :
Question :
?- afficher_liste([a,b,c]).
Réponse :
a
b
c
false.
Question :
?- afficher_liste([a|[b|[c|[]]]]).
Réponse :
a
b
c
false.
Test de l'appartenance à une liste
Le programme source est :
appartient_a(X,[X|_]).
appartient_a(X,[_|L]) :- appartient_a(X,L).
Aprés avoir ouvert ce programme simple dans l'interpréteur Prolog (par la commande consult), utilisons la fonction appartient_a :
Question :
?- appartient_a(a,[a,b,c]).
Réponse :
true
Question :
?- appartient_a(c,[a,b,c]).
Réponse :
true
Question :
?- appartient_a(e,[a,b,c]).
Réponse :
false
Les prédicats prédéfinis de SWI-Prolog pour la manipulation des listes
Voici 20 prédicats prédéfinis dans SWI-Prolog et bien pratiques pour la manipulation des listes sans devoir les ré-écrire. Le nombre de paramètres attendus par un prédicat est appelé son arité et il est précisé en suffixe après le / dans les noms des prédicats.
Exemple : member/2 signifie le prédicat member utilisant 2 paramètres (prédicat d'arité 2).
| |
|
|
|
| |
|||
| |
Exemple d'application : on désire obtenir une liste L composée de 50 sous-listes, chacune des 50 sous-listes devant contenir tous les entiers de 1 à 50 sauf un. La ligne suivante génère la liste L :
?- numlist(1,50,M),findall(Y,select(X,M,Y),L).
Demandons d'applanir la liste L pour créer une liste A :
?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A).
Demandons de supprimer les doublons dans la liste A pour créer une liste B :
?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A),list_to_set(A,B).
Enfin demandons à Prolog d'ordonner les éléments de la liste B pour créer la liste C :
?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A),list_to_set(A,B),sort(B,C).
On obtient alors naturellement au final pour la liste C une liste ordonnée des entiers de 1 à 50.
Cet exemple a montré comment enchaîner les différents prédicats afin d'affiner la génération d'une liste formatée.
Différences entre les prédicats sort/2, msort/2 et list_to_set/2 :
list_to_set/2 convertit une liste en ensemble, ce qui revient à supprimer les doublons sans trier :
?- list_to_set([4,2,3,4,1,2,2,1,3],L).
L = [4, 2, 3, 1].
msort/2 trie la liste sans supprimer les doublons :
?- msort([4,2,3,4,1,2,2,1,3],L).
L = [1, 1, 2, 2, 2, 3, 3, 4, 4].
Enfin sort/2 trie la liste et supprime les doublons :
sort([4,2,3,4,1,2,2,1,3],L).
L = [1, 2, 3, 4].
On retiendra que sort est équivalent à l'emploi consécutif de msort et de list_to_set :
?- list_to_set([4,2,3,4,1,2,2,1,3],L1),msort(L1,L).
L1 = [4, 2, 3, 1],
L = [1, 2, 3, 4].?- msort([4,2,3,4,1,2,2,1,3],L1),list_to_set(L1,L).
L1 = [1, 1, 2, 2, 2, 3, 3, 4, 4],
L = [1, 2, 3, 4].
Différences entre les prédicats findall/3 ("trouver tout"), bagof/3 ("sac de") et setof/3 ("ensemble de") :
Nous partons de l'ensembre de faits suivant donnant l'age de 6 personnes :
age(vincent, 23).
age(marie, 25).
age(alexis, 21).
age(laure, 23).
age(alice, 24).
age(paul, 21).
Nous voulons obtenir seulement la liste des ages.
Le prédicat findall/3 nous renvoie l'ensemble des ages dans une seule liste, contenant des doublons, que les noms soient en variable anonyme ou pas :
?- findall(X,age(_,X),L).
L = [23, 25, 21, 23, 24, 21].?- findall(X,age(Y,X),L).
L = [23, 25, 21, 23, 24, 21].
Le prédicat bagof/3 nous renvoie l'ensemble des ages dans des listes séparées :
?- bagof(X,age(_,X),L).
L = [21] ;
L = [24] ;
L = [23] ;
L = [25] ;
L = [21] ;
L = [23].
Si dans age les noms ne sont pas en variable anonyme, bagof/3 renvoie les noms (valeur de la variable Y) en plus des ages (valeur de la variable X enregistrée dans la liste L) :
?- bagof(X,age(Y,X),L).
Y = alexis,
L = [21] ;
Y = alice,
L = [24] ;
Y = laure,
L = [23] ;
Y = marie,
L = [25] ;
Y = paul,
L = [21] ;
Y = vincent,
L = [23].
Il est possible de demander à bagof/3 de ne pas renvoyer la valeur de la variable Y grâce à l'opérateur ^. Dans ce cas, bagof/3 renvoie tous les ages (variable X) dans une liste unique, mais contenant des doublons (exactement comme la liste renvoyée par findall/3) :
?- bagof(X,Y^age(Y,X),L).
L = [23, 25, 21, 23, 24, 21].
On peut également demander la liste des prénoms sans afficher les ages :
?- bagof(Y,X^age(Y,X),L).
L = [vincent, marie, alexis, laure, alice, paul].
Voyons maintenant ce que fait le prédicat setof/3 qui renvoie un ensemble et non une liste, sachant que par définition un ensemble ne contient pas de doublon.
Appelons le prédicat setof/3 avec une variable anonyme pour le nom : on obtient le même résultat qu'avec bagof/3
?- setof(X,age(_,X),L).
L = [21] ;
L = [24] ;
L = [23] ;
L = [25] ;
L = [21] ;
L = [23].
Appelons le prédicat setof/3 avec une variable non anonyme Y pour le nom : on obtient encore le même résultat qu'avec bagof/3
?- setof(X,age(Y,X),L).
Y = alexis,
L = [21] ;
Y = alice,
L = [24] ;
Y = laure,
L = [23] ;
Y = marie,
L = [25] ;
Y = paul,
L = [21] ;
Y = vincent,
L = [23].
Appelons maintenant le prédicat setof/3 avec une variable non anonyme Y pour le nom mais en lui demandant de ne pas donner la valeur de Y dans les résultats :
?- setof(X,Y^age(Y,X),L).
L = [21, 23, 24, 25].
On obtient cette fois une liste unique sans doublon, et avec les éléments ordonnées dans l'ordre croissant.
Si les atomes sont des mots et non des nombres on obtient une liste triée dans l'ordre alphabétique des atomes :
?- setof(Y,X^age(Y,X),L).
L = [alexis, alice, laure, marie, paul, vincent].
Remarque : si on trie la liste obtenue par findall/3 avec le prédicat sort/2 on obtient le même résultat qu'avec setof/3 :
?- findall(X,age(Y,X),L1),sort(L1,L2).
L1 = [23, 25, 21, 23, 24, 21],
L2 = [21, 23, 24, 25].
Le prédicat sort/2 trie la liste et supprime les doublons.
Le prédicat list_to_set/2 quant à lui supprime les doublons mais n'ordonne pas les éléments de la liste :
?- findall(X,age(Y,X),L1),list_to_set(L1,L2).
L1 = [23, 25, 21, 23, 24, 21],
L2 = [23, 25, 21, 24].
Si on veut une liste ordonnée après list_to_set/2, un trie supplémentaire est obligatoire :
?- findall(X,age(Y,X),L1),list_to_set(L1,L2),sort(L2,L3).
L1 = [23, 25, 21, 23, 24, 21],
L2 = [23, 25, 21, 24],
L3 = [21, 23, 24, 25].
Mais dans ce dernier cas le prédicat list_to_set/2 est inutile puisque sort/2 trie et supprime les doublons en même temps.
A retenir :
bagof/3 est similaire à findall/3 sauf qu'il peut fournir les résultats dans des listes séparées
setof/3 est similaire à bagof/3 sauf qu'il peut fournir une liste unique de résultats ordonnée et sans doublon
setof/3 est comparable à findall/3 suivi de sort/2
Exemple d'utilisation du prédicat maplist :
Le prédicat maplist(P,L) applique le prédicat P à chaque élément de la liste L. Si on veut afficher tous les éléments d'une liste L il faut appliquer le prédicat write à chaque élément de la liste. Le prédicat maplist/2 permet de la faire facilement sans devoir définir un nouveau prédicat récurcif afficher_liste :
?- L=[a,b,c,d],maplist(write,L).
abcd
L = [a, b, c, d].
On peut aussi remplacer write par writeln :
?- L=[a,b,c,d],maplist(writeln,L).
a
b
c
d
L = [a, b, c, d].
maplist passe chaque élément de la liste à write par un paramètre "invisible" (non écrit explicitement). Pour matérialiser ce paramètre unique passé à write on peut utiliser la syntaxe du module lambda (la variable X représente le paramètre que maplist passe à write) :
?- L=[a,b,c,d],maplist(\X^write(X),L).
abcd
L = [a, b, c, d].
Si on veut afficher des espaces entre les éléments de la liste on place un second write, et on met entre parenthèses l'ensemble des prédicats appelés afin qu'ils ne forment qu'un seul paramètre pour maplist :
?- L=[a,b,c,d],maplist(\X^(write(X),write(' ')),L).
a b c d
L = [a, b, c, d].
Le même exemple sans utiliser de variable L :
?- maplist(\X^(write(X),write(' ')),[a,b,c,d]).
a b c d
true.
Si on donne 2 listes à maplist/3, il appelle le prédicat en lui passant 2 paramètres : les éléments de même rang de chacune des listes :
maplist(\X^Y^(write(X),write(' et '),writeln(Y)),[a,b,c,d],[1,2,3,4]).
a et 1
b et 2
c et 3
d et 4
true.
Dans ce cas l'utilisation des paramètres lambda est indispensable pour écrire le prédicat appelé dans maplist/3. Ce prédicat doit être un prédicat l'arité 2.
Il existe également maplist/4, c'est-à-dire qui attend 4 paramètres : 1 prédicat d'arité 3 et 3 listes :
maplist(\X^Y^Z^(write(X),write(', '),write(Y),write(' et '),writeln(Z)),[a,b,c,d],[1,2,3,4],['A','B','C','D']).
a, 1 et A
b, 2 et B
c, 3 et C
d, 4 et D
true.
Pour connaître toutes les versions de maplist il suffit de lancer maplist. dans l'interpréteur Prolog. Comme maplist/0 n'existe pas, Prolog renvoie une erreur en précisant l'arité possible pour maplist :
?- maplist.
ERROR: Undefined procedure: maplist/0
ERROR: However, there are definitions for:
ERROR: maplist/2
ERROR: maplist/3
ERROR: maplist/4
ERROR: maplist/5
false.
On constate qu'il existe encore maplist/5, mais que maplist/6 n'existe pas.
Voyons comment utiliser maplist/5 sans utiliser les paramètres lambda. On commence par définir un nouveau prédicat afficher/4 d'arité 4. Ce prédicat attend 4 paramètres et les affiche sur une seule ligne en les séparant par un tiret :
afficher(A,B,C,D):-write(A),write('-'),write(B),write('-'),write(C),write('-'),writeln(D).
Exemple d'utilisation :
?- afficher(a,b,c,d).
a-b-c-d
true.
Ensuite on appelle maplist/5 en lui passant en paramètre le prédicat afficher/4 et 4 listes de même taille :
?- maplist(afficher,[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6]).
1-1-1-1
2-2-2-2
3-3-3-3
4-4-4-4
5-5-5-5
6-6-6-6
true.
Dans ce cas les 4 paramètres passés à afficher/4 sont "invisibles" (pas d'utilisation de variables clairement écrites). Si on veut les matérialiser on peut utiliser les paramètres lambda :
?- maplist(\W^X^Y^Z^(afficher(W,X,Y,Z)),[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6]).
1-1-1-1
2-2-2-2
3-3-3-3
4-4-4-4
5-5-5-5
6-6-6-6
true.
Il est possible de passer certains paramètres de manière "invisible", et de matérialiser seulement les autres par les paramètres lambda. Dans l'exemple suivant, afficher et toujours un prédicat d'arité 4, et maplist/5 passera toujours 4 paramètres à afficher/4. Or seulement 2 paramètres sont écrits en clair avec la syntaxe lambda : on en déduit que les 2 autres sont "invisibles" :
?- maplist(\W^X^(afficher(W,X)),[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6]).
1-1-1-1
2-2-2-2
3-3-3-3
4-4-4-4
5-5-5-5
6-6-6-6
true.
En utilisant les 20 prédicats prédéfinis ci-dessus de SWI-Prolog (bien qu'il en existe encore beaucoup d'autres) il est déjà possible de générer rapidement toutes sortes de listes formatées, simples ou composées, en écrivant un programme de quelques lignes seulement et sans perdre de temps à ré-écrire les prédicats élémentaires tels que afficher_liste, append ou member.
Exemples :
Affiche d'un coup toutes les permutations de la liste à 5 éléments [a,b,c,d,e] :
findall(X,permutation([a,b,c,d,e],X),L),maplist(writeln,L).
Affiche d'un coup toutes les permutations de la liste numérique à 8 éléments [1,2,3,4,5,6,7,8] :
numlist(1,8,L1),findall(X,permutation(L1,X),L),maplist(writeln,L).
Quelques nouveaux prédicats relatifs aux listes et disponibles dans SWI-Prolog 6.2.2 :
*****************************************
*** reverse pour inverser une liste : ***
?- reverse([a,b,c,d,e],X).
X = [e, d, c, b, a].
******************************************************
*** union et intersection appliqué à 2 ensembles : ***
?- union([1,2,3],[5,6,7],X).
X = [1, 2, 3, 5, 6, 7].?- intersection([1,2,3],[5,6,7],X).
X = [].?- union([1,2,3,4,5],[4,5,6,7],X).
X = [1, 2, 3, 4, 5, 6, 7].?- intersection([1,2,3,4,5],[4,5,6,7],X).
X = [4, 5].
*****************************************************************
*** subtract pour supprimer certains éléments d'un ensemble : ***
?- subtract([1,2,3,4,5,6,7,8],[2,3,5],X).
X = [1, 4, 6, 7, 8].
****************************************************************
*** prefix : donne tous les préfixes possibles d'une liste : ***
?- prefix(X,[a,b,c,d,e]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [a, b, c, d] ;
X = [a, b, c, d, e] ;
false.
Rappel : append donne à la fois les préfixes et les suffixes :
?- append(X,Y,[a,b,c,d,e]).
X = [],
Y = [a, b, c, d, e] ;
X = [a],
Y = [b, c, d, e] ;
X = [a, b],
Y = [c, d, e] ;
X = [a, b, c],
Y = [d, e] ;
X = [a, b, c, d],
Y = [e] ;
X = [a, b, c, d, e],
Y = [] ;
false.
append peut donner seulement les préfixes :
?- append(X,_,[a,b,c,d,e]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [a, b, c, d] ;
X = [a, b, c, d, e] ;
false.
append peut donner seulement les sufixes :
?- append(_,X,[a,b,c,d,e]).
X = [a, b, c, d, e] ;
X = [b, c, d, e] ;
X = [c, d, e] ;
X = [d, e] ;
X = [e] ;
X = [] ;
false.
*****************************************************
*** last renvoie le dernier élément d'une liste : ***
?- last([a,b,c,d,e],X).
X = e.
Rappel : pour obtenir le premier élément d'une liste une simple unification suffit sans utiliser de prédicat particuler :
?- [X|_]=[a,b,c,d,e].
X = a.
****************************************************************************************************
*** is_set : vrai si la liste est un ensemble, c'est-à-dire si elle ne contient pas de doublon : ***
?- is_set([1,2,3,4]).
true.?- is_set([1,2,3,4,2]).
false.
*********************************************************
*** Somme, minimum et maximum d'une liste numérique : ***
?- sum_list([1,2,3,4,5],X).
X = 15.?- min_member(X,[1,2,3,4,5]).
X = 1.?- max_member(X,[1,2,3,4,5]).
X = 5.?- min_list([1,2,3,4,5],X).
X = 1.?- max_list([1,2,3,4,5],X).
X = 5.
*******************************************************
*** merge : concatène 2 listes pour en créer une troisième : ***
?- merge([1,2,3,4],[5,6],L).
L = [1, 2, 3, 4, 5, 6].merge([1,2,3,4],[1,2,3,4],L).
L = [1, 1, 2, 2, 3, 3, 4, 4].Remarque : merge ne supprime pas les doublons
?- merge([1,2,3,4],[5,6],[1,2,3,4,5,6]).
true.?- merge(L,[5,6],[1,2,3,4,5,6]).
L = [1, 2, 3, 4].?- merge([1,2,3,4],L,[1,2,3,4,5,6]).
false.
Exemple d'application des listes : résolution d'un nouveau logigramme simple "Qui a le serpent ?"
Dans une rue 3 maisons voisines sont de couleurs différentes : rouge, bleue et verte. Des personnes de nationalités différentes vivent dans ces maisons et elles ont chacune un animal de compagnie différent.
Les données du problème sont :
La problématique à résoudre est :
Le programme source en Prolog ne contient qu'un seul prédicat serpent/1 :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème "Qui a le serpent ?" %
% Réalisé par Jean-Christophe MICHEL %
% Juin 2015 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%serpent(N) :-
% Rue est une liste de 3 maisons :
Rue=[Maison1,Maison2,Maison3],
% une maison est rouge :
member(maison(rouge,_,_),Rue),
% une maison est bleue :
member(maison(bleu,_,_),Rue),
% une maison est verte :
member(maison(vert,_,_),Rue),
% l'anglais est dans la maison rouge :
member(maison(rouge,anglais,_),Rue),
% l'espagnol possède le jaguar :
member(maison(_,espagnol,jaguar),Rue),
% le japonais ne possède pas l'escargot :
subset([maison(_,_,escargot),maison(_,japonais,_)],Rue),
% l'escargot n'est pas dans la maison bleue :
subset([maison(bleu,_,_),maison(_,_,escargot)],Rue),
% le troisième animal est un serpent :
member(maison(_,N,serpent),Rue).
Appelons le pédicat serpent/1 dans SWI-Prolog : il nous donne instantanément la nationalité du possesseur du serpent
?- serpent(X).
X = japonais
On en déduit alors une composition possible pour les maisons en utilisant les données de l'énoncé :
Maison 1 Maison 2 Maison 3 rouge
anglais
escargot
bleue
espagnol
jaguar
verte
japonais
serpent
Remarque : le fait "le japonais vit à droite de la maison du possesseur de l'escargot" dans l'énoncé indique seulement que le japonais ne possède pas l'escargot (écrit subset([maison(_,_,escargot),maison(_,japonais,_)],Rue) dans le programme). De même la condition "le possesseur de l'escargot vit à gauche de la maison bleue" indique que l'escargot n'est pas dans la maison bleue (noté subset([maison(bleu,_,_),maison(_,_,escargot)],Rue) dans le programme).
La position relative des maisons 2 et 3 n'a alors aucune importance, et la solution suivante pour la composition des maisons est également correcte :
anglais escargot |
japonais serpent |
espagnol jaguar |
Et si on demandait à Prolog de nous sortir toutes les compositions des maisons correspondantes à l'énoncé ? Ajoutons au prédicat serpent un second paramètre correspondant à la liste Rue :
serpent(N,Rue) :-
Rue=[Maison1,Maison2,Maison3],
member(maison(rouge,_,_),Rue),
member(maison(bleu,_,_),Rue),
member(maison(vert,_,_),Rue),
member(maison(rouge,anglais,_),Rue),
member(maison(_,espagnol,jaguar),Rue),
subset([maison(_,_,escargot),maison(_,japonais,_)],Rue),
subset([maison(_,_,escargot),maison(bleu,_,_)],Rue),
member(maison(_,N,serpent),Rue).
Appelons le nouveau prédicat serpent/2, et là ... surprise :
?- serpent(X,Y).
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(bleu, espagnol, jaguar), maison(vert, japonais, serpent)] ;
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(bleu, japonais, serpent), maison(vert, espagnol, jaguar)] ;
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(vert, espagnol, jaguar), maison(bleu, japonais, serpent)] ;
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(vert, japonais, serpent), maison(bleu, espagnol, jaguar)] ;
X = japonais,
Y = [maison(bleu, espagnol, jaguar), maison(rouge, anglais, escargot), maison(vert, japonais, serpent)] ;
X = anglais,
Y = [maison(bleu, japonais, escargot), maison(rouge, anglais, serpent), maison(vert, espagnol, jaguar)] ;
X = japonais,
Y = [maison(vert, espagnol, jaguar), maison(rouge, anglais, escargot), maison(bleu, japonais, serpent)] ;
X = anglais,
Y = [maison(vert, japonais, escargot), maison(rouge, anglais, serpent), maison(bleu, espagnol, jaguar)] ;
X = anglais,
Y = [maison(bleu, espagnol, jaguar), maison(vert, japonais, escargot), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(bleu, japonais, escargot), maison(vert, espagnol, jaguar), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(vert, espagnol, jaguar), maison(bleu, japonais, escargot), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(vert, japonais, escargot), maison(bleu, espagnol, jaguar), maison(rouge, anglais, serpent)] ;
false.
Prolog nous sort 12 compositions possibles des maisons mais sans notion d'ordre : il ne faut garder que les solutions correspondant aux conditions suivantes (l'escargot est à gauche du japonais et à gauche de la maison bleue) :
Il s'agit des 5 solutions en rouge ci-dessus.
Dans tous les cas on en déduit que c'est forcément le japonais qui possède le serpent, seule question posée par le problème qui ne demandait pas la composition complète des maisons.
Mais pour Prolog l'anglais aussi peut très bien posséder le serpent : l'énoncé n'est pas assez précis, la solution n'est pas unique, et la notion d'ordre n'a pas été indiquée à Prolog.
Cet exemple a montré comment résoudre un logigramme simple en Prolog en utilisant seulement les prédicats prédéfinis member/2 et subset/2 de SWI-Prolog, et sans écrire de nouveaux prédicats pour la manipulation des listes.
L'énnoncé du problème est le suivant :
Cinq hommes de nationalités et de professions différentes habitent des maisons de couleurs différentes et situés côte à côte dans le même alignement. Ils ont chacun un animal favori et une boisson préférée.
Les données du problème sont :
La problématique à résoudre est :
La difficulté est la suivante :
Le programme source en Prolog :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème "Qui a le zèbre ?" %
% Réalisé par Jean-Christophe MICHEL %
% Juillet 2011 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%--------------------------------------------------------
% les faits :% liste_des_maisons est une liste de 5 maisons.
% Chaque maison a 5 paramètres qui seront dans l'ordre :
% - couleur
% - nationalité
% - animal
% - boisson
% - profession
% exemple : maison(jaune,norvegien,renard,eau,diplomate)
liste_des_maisons([
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _)
]).%--------------------------------------------------------
% les règles :% afficher_liste(L) : affiche un à un les éléments de la liste L avec retour à la ligne (writeln)
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,[X|_]).
appartient_a(X,[_|L]) :- appartient_a(X,L).% est_a_droite_de(A,B,L) : vrai si A suit B dans la liste L
est_a_droite_de(A, B, [B, A | _]).
est_a_droite_de(A, B, [_ | Y]) :- est_a_droite_de(A, B, Y).% est_voisin_de(A,B,L) : vrai si A et B sont consécutifs dans la liste L
est_voisin_de(A, B, [A, B | _]).
est_voisin_de(A, B, [B, A | _]).
est_voisin_de(A, B, [_ | Y]) :- est_voisin_de(A, B, Y).% pour que le prédicat "resoudre" aboutisse il faut que toutes les conditions soient remplies :
resoudre :-% la seule variable du programme est MAISONS : il s'agit d'une liste de 5 éléments "maison" :
liste_des_maisons(MAISONS),% l'anglais habite la maison rouge :
appartient_a(maison(rouge, anglais, _, _, _), MAISONS),% l'espagnol a un chien :
appartient_a(maison(_,espagnol, chien,_,_), MAISONS),% dans la maison verte on boit du café :
appartient_a(maison(verte,_,_,cafe,_), MAISONS),% l'ukrainien boit du thé :
appartient_a(maison(_,ukrainien,_,the,_), MAISONS),% la maison verte est immédiatement à droite de la maison blanche :
est_a_droite_de(maison(verte,_,_,_,_), maison(blanche,_,_,_,_), MAISONS),% le sculpteur élève des escargots :
appartient_a(maison(_,_,escargots,_,sculpteur), MAISONS),% le diplomate habite la maison jaune :
appartient_a(maison(jaune, _, _, _, diplomate), MAISONS),% dans la maison du milieu on boit du lait :
MAISONS = [_, _, maison(_, _, _, lait, _), _,_],% le norvégien habite la première maison à gauche :
MAISONS = [maison(_, norvegien, _, _, _)|_],% le médecin habite une maison voisine de celle où demeure le propriétaire du renard :
est_voisin_de(maison(_,_,_,_,medecin), maison(_,_,renard,_,_), MAISONS),% la maison du diplomate est à côté de celle où il y a un cheval :
est_voisin_de(maison(_,_,_,_,diplomate), maison(_,_,cheval,_,_), MAISONS),% le violoniste boit du jus d'orange :
appartient_a(maison(_,_,_,jus,violoniste), MAISONS),% le japonais est acrobate :
appartient_a(maison(_,japonais,_,_,acrobate), MAISONS),% le norvégien habite à côté de la maison bleue :
est_voisin_de(maison(_,norvegien,_,_,_), maison(bleue,_,_,_,_), MAISONS),% on précise que dans une des maisons on boit de l'eau :
appartient_a(maison(_,_,_,eau,_), MAISONS),% on précise que dans une des maisons il y a un zèbre :
appartient_a(maison(_,_,zebre,_,_), MAISONS),% affiche la liste finale seulement si toutes les conditions précédentes sont remplies :
afficher_liste(MAISONS).
Demandons à l'interpréteur Prolog de résoudre le problème en affichant la composition de chaque maison :
resoudre.
Et la réponse immédiate est :
maison(jaune,norvegien,renard,eau,diplomate)
maison(bleue,ukrainien,cheval,the,medecin)
maison(rouge,anglais,escargots,lait,sculpteur)
maison(blanche,espagnol,chien,jus,violoniste)
maison(verte,japonais,zebre,cafe,acrobate)
false.
Ce qui signifie en clair que la composition des maisons est :
Maison 1 Maison 2 Maison 3 Maison 4 Maison 5 jaune
norvégien
renard
eau
diplomatebleue
ukrainien
cheval
thé
médecinrouge
anglais
escargots
lait
sculpteurblanche
espagnol
chien
jus d'orange
violonisteverte
japonais
zèbre
café
acrobate
La problématique à résoudre était :
Remarque : avec l'énnoncé complet la solution est unique. Si on supprime une des conditions dans l'énoncé, il y a alors plusieurs solutions. Pour le tester facilement il suffit de commenter une des conditions dans le prédicat resoudre en mettant un signe % en début de ligne puis de redemander à Prolog d'afficher la solution : il affichera alors toutes les solutions possibles.
En supprimant plusieurs conditions le nombre de solutions possibles devient vite très important. Pour avoir le temps de regarder chaque solution on pourra modifier la fonction afficher_liste en lui demandant d'afficher un séparateur à la fin de chaque liste :
% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([X]) :- writeln(X), writeln(-----------------------------------------------).
Avec cette nouvelle fonction afficher_liste il faudra appuyer sur la touche point-virgule pour passer à la solution suivante.
L'énnoncé du problème est le suivant :
Cinq sportifs sont dans la salle d'attente d'un médecin spécialisé.
Retrouvez grâce aux indications suivantes leur ordre d'arrivée, le sport pratiqué par chacun ainsi que la raison de leur présence.
La première difficulté par rapport au logigramme du zèbre sont les conditions de négation, du style "Christian ne pratique pas la gymnastique". Pour inclure ces conditions dans le prédicat resoudre nous allons nous inspirer du logigramme simple donné à l'exemple 2 ci-dessus en utilisant l'opérateur \== permettant d'indiquer qu'une variable n'est pas égale à telle valeur.
Pour résoudre la notion d'ordre dans des conditions du style "Grégoire est arrivé avant Laurent" nous allons utiliser les listes comme dans le logigramme du zèbre donné à l'exemple 3 ci-dessus. Mais contrairement au logigramme du zèbre on ne veut pas détecter ici deux éléments "voisins" (c'est-à-dire qui se suivent dans la liste). La condition "Grégoire est arrivé avant Laurent" ne signifie pas que Gégoire est arrivé juste avant Laurent. C'est la raison pour laquelle nous ne pouvons pas ré-utiliser directement les fonctions est_voisin_de ou est_a_droite_de données dans le logigramme du zèbre.
La seconde difficulté est donc de détecter l'ordre des éléments dans une liste. Pour détecter qu'un élément est avant un autre dans une liste nous allons utiliser la fonction append de Prolog :
append attend en paramètre 3 listes : append(L1,L2,L3)
append sera vrai si la liste L3 est la concaténation des listes L1 et L2
Exemple 1 : la liste [a,b] est-elle la concaténation des listes [a] et [b] :
?- append([a],[b],[a,b]).
true.
Exemple 2 : la concaténation des listes [a,b] et [c,d] donne-t-elle la liste [a,b,c,d,e] ?
?- append([a,b],[c,d],[a,b,c,d,e]).
false.
Exemple 3 : la liste [a,b,c] possède-t-elle une sous-liste commençant par [b] ?
?- append(_,[b|_],[a,b,c]).
true.
Exemple 4 : la liste [a,b,c] commence-t-elle par [b] : le premier élément de la liste est-il b ?
append([b],_,[a,b,c]).
false.
Exemple 5 : le dernier élément de la liste [a,b,c] est-il c ?
?- append(_,[c],[a,b,c]).
true.
Grâce à append, la fonction suivante permet de savoir si l'élément A est avant l'élément B dans la liste L, sans forcément que les éléments A et B soient consécutifs dans la liste :
% est_avant(A,B,L) : vrai si l'élément A est avant l'élément B dans la liste L
est_avant(A, B, L) :-
append(_, [A | X], L), % il existe une sous-liste de L qui commence par A
append(_, [B | _], X). % et il existe une sous-liste de X qui commence par B
Enfin, toujours grâce à append, il est possible de simplifier la fonction appartient_a :
% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,L) :- append(_,[X|_],L).
La solution de cet exemple 4 est donc "un mélange" des exemples 2 et 3 ci-dessus avec en plus l'utilisation de la fonction append.
Voici le programme source en Prolog de cet exemple 4 :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème des 5 sportifs %
% Réalisé par Jean-Christophe MICHEL %
% Novembre 2012 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
liste_des_sportifs([
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _)
]).% afficher_liste(L) : affiche un à un les éléments de la liste L avec retour à la ligne (writeln)
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,L) :- append(_,[X|_],L).
% est_arrive_avant(A,B,L) : vrai si l'élément A est avant l'élément B dans la liste L
est_arrive_avant(A, B, L) :-
append(_, [A | X], L), % il existe une sous-liste de L qui commence par A
append(_, [B | _], X). % et il existe une sous-liste de X qui commence par B
% pour que le prédicat "resoudre" aboutisse il faut que toutes les conditions soient remplies :
resoudre :-% la variable SPORTIFS est une liste ordonnée de 5 éléments "sportif" :
liste_des_sportifs(SPORTIFS),
% on précise les 2 sports qui ne sont pas utilisés dans les conditions ci-dessous :
appartient_a(sportif(_, basket, _), SPORTIFS),
appartient_a(sportif(_, rugby, _), SPORTIFS),% on précise les 3 motifs de consultation qui ne sont pas utilisés dans les conditions ci-dessous :
appartient_a(sportif(_, _, certificat), SPORTIFS),
appartient_a(sportif(_, _, renouvellement), SPORTIFS),
appartient_a(sportif(_, _, visite), SPORTIFS),% on précise le prénom qui n'est pas utilisé dans les conditions ci-dessous :
appartient_a(sportif(remi, _, _), SPORTIFS),
% jean est arrivé en dernier :
SPORTIFS = [_,_,_,_,sportif(jean, _, _)],% la variable SJ représente le Sport de Jean :
appartient_a(sportif(jean, SJ, _), SPORTIFS),
SJ\==gymnastique, % jean ne fait pas de gymnastique
SJ\==basket, % jean ne fait pas de basket% la variable MJ représente le Motif de consultation de Jean :
appartient_a(sportif(jean, _, MJ), SPORTIFS),
MJ\==certificat, % jean ne veut pas de certificat% la variable SC représente le Sport de Christian :
appartient_a(sportif(christian, SC, soin), SPORTIFS),
SC\==gymnastique, % christian, venu pour un soin, ne pratique pas la gymnastique% gregoire qui est arrivé avant laurent fait du patinage :
est_arrive_avant(sportif(gregoire, patinage, _), sportif(laurent, _, _), SPORTIFS),
% gregoire (qui fait du patinage) est arrivé après celui qui fait de la gymnastique :
est_arrive_avant(sportif(_, gymnastique, _), sportif(gregoire, patinage, _), SPORTIFS),
% la variable MG représente le Motif de consultation de Grégoire :
appartient_a(sportif(gregoire, _, MG), SPORTIFS),
MG\==certificat, % gregoire ne veut pas de certificat
MG\==renouvellement, % gregoire ne veut pas de renouvellement% celui qui pratique le football est arrivé le troisième. Il est venu chercher une dispense :
SPORTIFS = [_, _, sportif(_, football, dispense), _, _],
% celui qui pratique le football est arrivé avant Christian :
est_arrive_avant(sportif(_, football, _), sportif(christian, _, _), SPORTIFS),
% affiche la liste finale seulement si toutes les conditions précédentes sont remplies :
afficher_liste(SPORTIFS).
Demandons à l'interpréteur Prolog de résoudre le problème en affichant l'ordre d'arrivée, le prénom, le sport, et le motif de consultation de chaque sportif :
resoudre.
Et la réponse immédiate est une liste ordonnée et unique (il y a une seule solution au problème) des 5 sportifs :
sportif(remi,gymnastique,certificat)
sportif(gregoire,patinage,visite)
sportif(laurent,football,dispense)
sportif(christian,basket,soin)
sportif(jean,rugby,renouvellement)
false.
On en déduit que le premier arrivé est Rémi, puis Grégoire, puis Laurent, puis Christian, et enfin le dernier arrivé est Jean, et pour chaque sportif Prolog nous indique dans la liste le sport pratiqué et le motif de consultation.
Ce qui signifie en clair que la solution du problème est :
Ordre d'arrivée Prénom Sport Motif 1
2
3
4
5Rémi
Grégoire
Laurent
Christian
Jeangymnastique
patinage
football
basket
rugbycertificat
visite
dispense
soin
renouvellement
La coupure est un prédicat prédéfini très important qui a pour effet de stopper la recherche de Prolog dès qu'il aura trouvé une solution.
Ce prédicat permet de contrôler l'espace de recherche et d'économiser le travail de Prolog en limitant l'exploration de l'arbre de recherche.
La coupure se note ! (un point d'exclamation) dans la plupart des versions de Prolog.
Rappelons que le prédicat prédéfini is est l'opérateur d'affectation en Prolog : il affecte à la variable de gauche la valeur de l'expression de droite, après avoir évalué cette expression. Par exemple, X is A+2. évalue en un premier temps l'expression A+2 puis affecte le résultat à la variable X.
Exemple simple :
?- X is 2, Y is X+3.
X = 2,
Y = 5.
Passons à 3 exemples d'utilisation concrètes de la coupure en Prolog.
Exemple 1 de la coupure : affichage de tous les entiers de N à 1 dans l'ordre décroissant
L'idée de base est d'écrire un prédicat afficher(N) qui s'appelle récurcivement en passant en paramètre au prédicat appelé la valeur N-1 :
afficher(N):-writeln(N),K is N-1,afficher(K).
Le problème est que cet appel récurcif ne s'arrête jamais, et affiche toutes les valeurs négatives sans fin :
?- afficher(5).
5
4
3
2
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10
-11
-12
-13
-14
-15
-16
-17
-18
-19
etc. sans arrêt ...
Une solution pour arrêter l'affichage en dessous de zéro est de rajouter une condition dans le prédicat afficher(N) :
afficher(N):-N>0,writeln(N),K is N-1,afficher(K).
Cela stope en effet l'affichage à 1, mais Prolog répond alors par la négation (false) en sortant lorque N=0 car la condition N>0 n'est pas vérifiée :
?- afficher(5).
5
4
3
2
1
false.
La solution pour stopper l'affichage lorsque N=0 tout en répondant positivement (true) est d'utiliser la coupure : on stoppe positivement la recherche lorsque N=0, c'est-à-dire lorsque le prédicat afficher() reçoit 0 en paramètre :
afficher(0):-!. % ne fait rien et arrête la recherche en répondant true
afficher(N):-writeln(N),K is N-1,afficher(K). % appel récurcif du prédicat afficher()
Et le résultat est :
?- afficher(5).
5
4
3
2
1
true.
Exemple 2 de la coupure : affichage de tous les éléments d'une liste
L'idée de base est d'écrire un prédicat afficher([X|Y]) qui affiche le premier élément X puis qui appelle récurcivement le prédicat afficher en lui passant en paramètre le reste Y de la liste:
afficher([X|Y]):-writeln(X),afficher(Y).
Mais là encore Prolog répond par la négation (false) lorsqu'il n'y a plus rien à afficher, c'est-à-dire lorsque la liste reçue en paramètre par le prédicat afficher est vide :
?- afficher([a,b,c,d]).
a
b
c
d
false.
La solution consiste donc à préciser grâce à la coupure que si la liste reçue est vide, on arrête la recherche et on répond positivement :
Et le résultat est :afficher([]):-!. % arrête si la liste est vide
afficher([X|Y]):-writeln(X),afficher(Y). % appel récurcif si la liste n'est pas vide
?- afficher([a,b,c,d]).
a
b
c
d
true.
Exemple 3 de la coupure : répétition d'une proposition quelconque
Le prédicat repeter(N,P) suivant répètre N fois la proposition P :
Exemples d'utilisation :repeter(0,_):-!. % arrête si N=0 quelque soit la proposition P
repeter(N,P):-P,X is N-1,repeter(X,P). % exécute P puis appel récurcif
?- repeter(5,write('bonjour ')).
bonjour bonjour bonjour bonjour bonjour
true.?- repeter(5,repeter(3,writeln('gecif'))).
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
true.?- repeter(4,(write('prolog'),nl)).
prolog
prolog
prolog
prolog
true.
Remarques :
?- repeter(4,(write('prolog'),writeln(''))).
prolog
prolog
prolog
prolog
true.
Exemple 4 de la coupure : se limiter à la première réponse dans le cas de réponses multiples
Nous retrouvons un arbre généalogique très simple : jean est le père de 3 enfants :
pere(jean,luc). % jean est le père de luc
pere(jean,remi). % jean est le père de rémi
pere(jean,laurent). % jean est le père de laurent
Posons quelques questions à l'interpréteur avec ou sans coupure :
Qui est le père de laurent ? Réponse : jean :
?- pere(X,laurent).
X = jean.
Qui est le fils de jean (qui a pour père jean) ? Réponse : jean a 3 fils luc, rémi et laurent, il y a donc 3 solutions :
?- pere(jean,X).
X = luc ;
X = remi ;
X = laurent.
Rémi a-t-il un père ? Réponse : oui :
?- pere(_,remi).
true.
Jean est-il un père ? Et là encore la réponse est triple puisque l'interpréteur a trouvé 3 fois la réponse à la question :
?- pere(jean,_).
true ;
true ;
true.
Si on veut juste savoir si Jean est un père ou pas, peut importe le nombre de fils. Dans ce cas on va poser la question en utilisant la coupure afin de s'arrêter dès la premère réponse positive :
?- pere(jean,_),!.
true.
Ainsi l'interpréteur arrête sa recherche dès le premier fils trouvé, sans perdre de temps à se demander si jean a d'autres fils, ce qui n'a aucune importance pour répondre à la question "Jean est-il un père ?".
De même, si on pose la question "Qui sont les fils de jean ?" avec une coupure à la fin, l'interpréteur arrêtera la recherche dès la première solution trouvée :
?- pere(jean,X),!.
X = luc.
La question précédente peut alors se formuler ainsi : "Donnez-moi un fils de jean et un seul, peu importe lequel".
Exemple 5 de la coupure : afficher seulement les valeurs positives d'une liste
Le prédicat scan_list qui attend en paramètre une liste affiche la tête de la liste seulement s'il s'agit d'un nombre positif, puis est appelé récurcivement avec le reste de la liste jusqu'à ce qu'il reçoive une liste vide. Sur le deuxième ligne la coupure arrête le traitement si la tête de la liste n'est pas un nombre strictement positif.
# Programme réalisé le 29 janvier 2017
# Ce programme affiche seulement les valeur positives d'une liste
# En cas de valeur négative, la coupure empêche d'afficher
# la valeur et passe à l'élément suivant
scan_list([]).
scan_list([H|T]):-H>0,!,print(H),nl,scan_list(T).
scan_list([_|T]):-scan_list(T).
Exemple d'utilisation :
?- scan_list([1,-2,7,9,0,-1,14]).
1
7
9
14
true.
Seules les valeurs strictement positives de la liste ont été affichées.
Pour d'autres exemples utilisant la coupure voir ce cours en PDF page 8.
Le problème à résoudre (qui est réel ...) est le suivant :
Les 15 élèves sont identifiés chacun par une lettre unique (de A à O).
Voici un exemple de grille de roulement correspondant à ce problème (il ne s'agit que d'un exemple parmi un très grand nombre) :
J'ai obtenu le tableau ci-dessus en faisant tourner 3 disques cocentriques en carton, découpés chacun en 5 secteurs angulaires, et avec une lettre dans chacun des secteurs angulaires : un disque reste fixe, le second tourne dans un sens, et le troisième tourne dans l'autre sens. Malheureusemnet les 5 élèves inscrits sur le même disque ne se rencontreront jamais (A, B, C, D et E par exemple ne seront jamais ensemble : ils appartiennent toujours à la première colonne de lettre, et ce à chaque séance).
Mais l'objectif est ici de jeter les disques en carton (qui ne donnent même pas une solution satisfaisante comme décrit précédemment) et de généraliser le problème à une classe possédant un nombre quelconque d'élèves multiple de 3 (9, 12, 15, 18, 21, 24 ou 30 élèves).
Comment programmer en Prolog la génération d'une telle grille de roulement ?
Voici une première solution qui impose certaines conditions (mais même pas l'interdiction de recréer les mêmes groupes de 3). L'inconvénient d'un tel programme c'est qu'il faut plusieurs heures à Prolog pour sortir la première grille ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% Novembre 2012 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).app(X,L) :- append(_,[X|_],L).
complet(L):-app(a,L),
app(b,L),
app(c,L),
app(d,L),
app(e,L),
app(f,L),
app(g,L),
app(h,L),
app(i,L),
app(j,L),
app(k,L),
app(l,L),
app(m,L),
app(n,L),
app(o,L).resoudre :-
T1S1=[a,f,k],
T1S2=[e,g,m],
T1S3=[d,h,o],
T1S4=[c,i,l],
T1S5=[b,j,n],T2S1=[b,g,l],
T2S2=[_,_,_],
T2S3=[_,_,_],
T2S4=[_,_,_],
T2S5=[_,_,_],T3S1=[c,h,m],
T3S2=[_,_,_],
T3S3=[_,_,_],
T3S4=[_,_,_],
T3S5=[_,_,_],T4S1=[d,i,n],
T4S2=[_,_,_],
T4S3=[_,_,_],
T4S4=[_,_,_],
T4S5=[_,_,_],T5S1=[e,j,o],
T5S2=[_,_,_],
T5S3=[_,_,_],
T5S4=[_,_,_],
T5S5=[_,_,_],GRILLE = [TP1,TP2,TP3,TP4,TP5],
% on "met à plat" les 5 listes représentant les lignes du tableau :
flatten([T1S1,T1S2,T1S3,T1S4,T1S5], TP1),
flatten([T2S1,T2S2,T2S3,T2S4,T2S5], TP2),
flatten([T3S1,T3S2,T3S3,T3S4,T3S5], TP3),
flatten([T4S1,T4S2,T4S3,T4S4,T4S5], TP4),
flatten([T5S1,T5S2,T5S3,T5S4,T5S5], TP5),% on "met à plat" les 5 listes représentant les colonnes du tableau :
flatten([T1S1,T2S1,T3S1,T4S1,T5S1], SEANCE1),
flatten([T1S2,T2S2,T3S2,T4S2,T5S2], SEANCE2),
flatten([T1S3,T2S3,T3S3,T4S3,T5S3], SEANCE3),
flatten([T1S4,T2S4,T3S4,T4S4,T5S4], SEANCE4),
flatten([T1S5,T2S5,T3S5,T4S5,T5S5], SEANCE5),% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
complet(TP1),
complet(TP2),
complet(TP3),
complet(TP4),
complet(TP5),% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
complet(SEANCE1),
complet(SEANCE2),
complet(SEANCE3),
complet(SEANCE4),
complet(SEANCE5),afficher_liste(GRILLE),!.
Voici une variante utilisant le prédicat prédéfini permutation de swi-prolog à la place du prédicat complet :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% Novembre 2012 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
% put(7) à la fin permet de sonner dès la première solution trouvée
afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).
% pour limiter l'espace de recherche on a rempli au hasard le TP1 et la SEANCE1 :
resoudre :-
T1S1=[a,b,c],
T1S2=[d,n,j],
T1S3=[e,g,k],
T1S4=[f,h,l],
T1S5=[m,i,o],T2S1=[d,e,f],
T2S2=[_,_,_],
T2S3=[_,_,_],
T2S4=[_,_,_],
T2S5=[_,_,_],T3S1=[g,h,i],
T3S2=[_,_,_],
T3S3=[_,_,_],
T3S4=[_,_,_],
T3S5=[_,_,_],T4S1=[j,k,l],
T4S2=[_,_,_],
T4S3=[_,_,_],
T4S4=[_,_,_],
T4S5=[_,_,_],T5S1=[m,n,o],
T5S2=[_,_,_],
T5S3=[_,_,_],
T5S4=[_,_,_],
T5S5=[_,_,_],GRILLE = [TP1,TP2,TP3,TP4,TP5],
% on "met à plat" les 5 listes représentant les lignes du tableau :
flatten([T1S1,T1S2,T1S3,T1S4,T1S5], TP1),
flatten([T2S1,T2S2,T2S3,T2S4,T2S5], TP2),
flatten([T3S1,T3S2,T3S3,T3S4,T3S5], TP3),
flatten([T4S1,T4S2,T4S3,T4S4,T4S5], TP4),
flatten([T5S1,T5S2,T5S3,T5S4,T5S5], TP5),
% on "met à plat" les 5 listes représentant les colonnes du tableau : flatten([T1S1,T2S1,T2S1,T3S1,T4S1,T5S1], SEANCE1),
flatten([T1S2,T2S2,T2S2,T3S2,T4S2,T5S2], SEANCE2),
flatten([T1S3,T2S3,T2S3,T3S3,T4S3,T5S3], SEANCE3),
flatten([T1S4,T2S4,T2S4,T3S4,T4S4,T5S4], SEANCE4),
flatten([T1S5,T2S5,T2S5,T3S5,T4S5,T5S5], SEANCE5),% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
permutation(TP1, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP2, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP3, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP4, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP5, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
permutation(SEANCE1, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE2, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE3, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE4, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE5, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),afficher_liste(GRILLE).
Et voici une troisième solution (avec une classe de 9 élèves seulement pour accélérer la recherche) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% Novembre 2012 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).% app(X,L) est vrai si X appartient à la liste L
app(_,[]):-!,fail.
app(X,[X|_]).
app(X,[_|L]):-app(X,L).% diff(L1,L2,L3) est vrai si la liste L3 est la liste L1 privée des éléments présents dans L2
diff([],_,[]).
diff([X|L],M,R):- app(X,M),!,diff(L,M,R).
diff([X|L],M,[X|R]):- diff(L,M,R).
% egaux(L1,L2) est vrai si les deux listes L1 et L2 sont égale en tant qu'ensemble,
% c'est-à-dire sans tenir compte de l'ordre ou des répétitions
egaux(L,M):-diff(L,M,[]),diff(M,L,[]).% non(true) donne fail, et non(fail) donne true
non(P):-P,!,fail.
non(_).complet(L):-app(a,L),
app(b,L),
app(c,L),
app(d,L),
app(e,L),
app(f,L),
app(g,L),
app(h,L),
app(i,L).% pour limiter l'espace de recherche on a déjà rempli le TP1 :
resoudre :-
T1S1=[a,b,c],
T1S2=[d,e,f],
T1S3=[g,h,i],T2S1=[_,_,_],
T2S2=[_,_,_],
T2S3=[_,_,_],T3S1=[_,_,_],
T3S2=[_,_,_],
T3S3=[_,_,_],% aucun des 3 groupes du TP2 ne doit être égal à un des groupes du TP1
non(egaux(T2S1,T1S1)),
non(egaux(T2S1,T1S2)),
non(egaux(T2S1,T1S3)),non(egaux(T2S2,T1S1)),
non(egaux(T2S2,T1S2)),
non(egaux(T2S2,T1S3)),non(egaux(T2S3,T1S1)),
non(egaux(T2S3,T1S2)),
non(egaux(T2S3,T1S3)),GRILLE = [TP1,TP2,TP3],
% flatten met à plat la première liste composée dans la seconde
flatten([T1S1,T1S2,T1S3], TP1),
flatten([T2S1,T2S2,T2S3], TP2),
flatten([T3S1,T3S2,T3S3], TP3),flatten([T1S1,T2S1,T3S1], SEANCE1),
flatten([T1S2,T2S2,T3S2], SEANCE2),
flatten([T1S3,T2S3,T3S3], SEANCE3),% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
complet(TP1),
complet(TP2),
complet(TP3),% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
complet(SEANCE1),
complet(SEANCE2),
complet(SEANCE3),% la coupure à la fin permet de s'arrêter dès la première grille trouvée
afficher_liste(GRILLE),!.
Mais malheureusement aucune de ces 3 solutions n'est fonctionnelle puisqu'il faut plusieurs heures à Prolog pour trouver une solution, sans que l'on soit sûr qu'il ne va pas sortir false après un jour de calcul ou qu'il ne va pas répéter les mêmes groupes dans les 5 séances ...
Voici une autre solution pour 9 élèves imposant les contraintes dans SWI-Prolog en une seule ligne :
G11=[_,_,_],G12=[_,_,_],G13=[_,_,_],G21=[_,_,_],G22=[_,_,_],G23=[_,_,_],G31=[_,_,_],G32=[_,_,_],G33=[_,_,_], flatten([G11,G21,G31],S1),permutation(S1,[1,2,3,4,5,6,7,8,9]),flatten([G12,G22,G32],S2),permutation(S2,[1,2,3,4,5,6,7,8,9]), flatten([G13,G23,G33],S3),permutation(S3,[1,2,3,4,5,6,7,8,9]),flatten([T11,T12,T13],T1),permutation(T1,[1,2,3,4,5,6,7,8,9]), flatten([T21,T22,T23],T2),permutation(T2,[1,2,3,4,5,6,7,8,9]),flatten([T31,T32,T33],T3),permutation(T3,[1,2,3,4,5,6,7,8,9]),!.
La ligne ci-dessus a été générée grâce au programme Python suivant, facilement généralisable pour une classe de 12, 15 ou 18 élèves :
##################################################################
# Programme en Python générant une ligne de code Prolog complexe et répétitive
# Réalisé par Jean-Christophe MICHEL le 4 février 2017
# www.gecif.net
##################################################################
nombre_tp=3
# Les 9 groupes Gxy sont des listes à 3 éléments :
for s in range(1,nombre_tp+1):
for t in range(1,nombre_tp+1):
print('G',s,t,'=[_,_,_],')# pour chaque séance S1 S2 et S3 : 3 flatten et 3 permutation
for s in range(1,nombre_tp+1):
print('flatten([')
for t in range(1,nombre_tp+1):
print('G',t,s,',')
print('],S',s,'),')
print('permutation(S',s,',[1,2,3,4,5,6,7,8,9]),')# pour chaque TP T1 T2 et T3 : 3 flatten et 3 permutation
for t in range(1,nombre_tp+1):
print('flatten([')
for s in range(1,nombre_tp+1):
print('T',t,s,',')
print('],T',t,'),')
print('permutation(T',t,',[1,2,3,4,5,6,7,8,9]),')
Le programme en Python ci-dessus génère le texte suivant :
G 1 1 =[_,_,_],
G 1 2 =[_,_,_],
G 1 3 =[_,_,_],
G 2 1 =[_,_,_],
G 2 2 =[_,_,_],
G 2 3 =[_,_,_],
G 3 1 =[_,_,_],
G 3 2 =[_,_,_],
G 3 3 =[_,_,_],
flatten([
G 1 1 ,
G 2 1 ,
G 3 1 ,
],S 1 ),
permutation(S 1 ,[1,2,3,4,5,6,7,8,9]),
flatten([
G 1 2 ,
G 2 2 ,
G 3 2 ,
],S 2 ),
permutation(S 2 ,[1,2,3,4,5,6,7,8,9]),
flatten([
G 1 3 ,
G 2 3 ,
G 3 3 ,
],S 3 ),
permutation(S 3 ,[1,2,3,4,5,6,7,8,9]),
flatten([
T 1 1 ,
T 1 2 ,
T 1 3 ,
],T 1 ),
permutation(T 1 ,[1,2,3,4,5,6,7,8,9]),
flatten([
T 2 1 ,
T 2 2 ,
T 2 3 ,
],T 2 ),
permutation(T 2 ,[1,2,3,4,5,6,7,8,9]),
flatten([
T 3 1 ,
T 3 2 ,
T 3 3 ,
],T 3 ),
permutation(T 3 ,[1,2,3,4,5,6,7,8,9]),
Après avoir supprimé les espaces et les retours à la ligne on obtient :
G11=[_,_,_],G12=[_,_,_],G13=[_,_,_],G21=[_,_,_],G22=[_,_,_],G23=[_,_,_],G31=[_,_,_],G32=[_,_,_],G33=[_,_,_],flatten([G11,G21,G31,],S1),permutation(S1,[1,2,3,4,5,6,7,8,9]),flatten([G12,G22,G32,],S2),permutation(S2,[1,2,3,4,5,6,7,8,9]),flatten([G13,G23,G33,],S3),permutation(S3,[1,2,3,4,5,6,7,8,9]),flatten([T11,T12,T13,],T1),permutation(T1,[1,2,3,4,5,6,7,8,9]),flatten([T21,T22,T23,],T2),permutation(T2,[1,2,3,4,5,6,7,8,9]),flatten([T31,T32,T33,],T3),permutation(T3,[1,2,3,4,5,6,7,8,9]),
Il ne reste plus qu'à supprimer la virgule après G31, G32, G33, T13, T23 et T33 à la fin de la liste passée en premier paramètre à flatten afin d'obtenir une syntaxe correcte pour Prolog (et à ajouter la coupure ! pour s'arrêter à la première solution trouvée et le point final).
Mais malheureusement, et comme on pouvait s'y attendre, après plus de 2 heures de recherche SWI-Prolog n'a toujours pas sorti la première grille. La faute au prédicat permutation utilisé plusieurs fois et qui teste tous les cas possibles.
Et voici une première solution fonctionnelle utilisant les modules lambda et clpfd de Prolog et donnant une grille en moins de 2 minutes :
Télécharger le module lambda.pl qui n'est pas inclus dans SWI-Prolog (fichier à enregistrer dans le répertoire C:\Program Files\pl\library)
:- use_module(library(lambda)).
:- use_module(library(clpfd)).%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Janvier 2015 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% détails des séances
% 5 TP (donc 5 séances) avec 3 élèves à chaque TP
details(5, 3).solve :-
details(TP, PTP),% L est une liste de TP séances
% L = [Si]
% Chaque séance est une liste de TP TPs
% Si = [Tpi]
% Chaque TP est une liste de PTP élèves
% TPi = [Ei]% nombre d'élèves
% les elèves sont numérotés de 1 à Eleves
Eleves is TP * PTP,% le nombre de séances est le même que celui des TP
Se = TP,% on crée la liste des séances de longueur Se
length(L, Se),% on crée la liste des TP pour chaque séance
maplist(\X^T^(length(X, TP),
% chaque TP est une liste de PTP élèves
maplist(\Y^V^(length(Y, PTP),
% Les élèves sont choisis parmi Eleves élèves
Y ins 1..Eleves,
% ils sont évidemment différents
all_distinct(Y),
% Pour une lecture plus simple des résultats
% les élèves sont rangés par ordre de numéro
chain(Y, #<),
% ici on attribue des clés aux combinaisons d'élèves
% 2 élèves ne peuvent pas travailler 2 fois ensemble
calcule_cles(Y, [], V)),
X, T)),
L, D),
% on récupère la liste des clés
% et on déclare que toutes les clés sont différentes
flatten(D, FD),
all_distinct(FD),% il ne reste plus qu'à imposer les contraintes de participation aux séances de TP
contraintes_cours(L, TP),
flatten(L, FL),% on demande à SWI-Prolog de calculer les résultats
% on peut tester différentes combinaisons d'options de labeling
labeling([ffc, bisect], FL),% affichage des résultats
maplist(writeln, L).calcule_cles([], Lst, Lst).
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prédicat calcule_cles :
calcule_cles([H | T], Cur, Lst) :-
maplist(H +\X^Y^(Y #= 100 * H + X), T, R),
append(Cur, R, Cur1),
calcule_cles(T, Cur1, Lst).%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prédicat contraintes_cours(L,TP) :
contraintes_cours(L, TP) :-
% la contrainte sur les cours est que tous les elèves soient en TP
maplist(\X^(flatten(X, FX), all_distinct(FX)), L),
% tous les élèves doivent participer à tous les TP
numlist(1,TP, NL),
maplist(L +\Y^(foldl(\U^V^W^(nth1(Y, U, Row),
append(V, Row, W)),
L, [], TPS),
all_distinct(TPS)),
NL).
Voici la grille générée en 100 secondes seulement avec les options labeling([ffc, bisect], FL) :
3 ?- time(solve).
[[1,2,11],[3,4,12],[5,6,13],[7,8,14],[9,10,15]]
[[3,5,7],[13,14,15],[8,10,11],[2,9,12],[1,4,6]]
[[4,8,15],[5,9,11],[1,12,14],[3,6,10],[2,7,13]]
[[6,9,14],[1,7,10],[2,3,15],[4,11,13],[5,8,12]]
[[10,12,13],[2,6,8],[4,7,9],[1,5,15],[3,11,14]]
% 256,073,985 inferences, 97.922 CPU in 99.969 seconds (98% CPU, 2615085 Lips)
true
Et voici une autre grille générée cette fois avec les options labeling([ff, enum], FL) :
1 ?- time(solve).
[[1,6,11],[2,7,12],[3,8,13],[4,9,14],[5,10,15]]
[[2,3,4],[13,14,15],[9,10,11],[5,6,12],[1,7,8]]
[[5,8,14],[1,4,10],[2,6,15],[7,11,13],[3,9,12]]
[[7,9,15],[3,5,11],[1,12,14],[2,8,10],[4,6,13]]
[[10,12,13],[6,8,9],[4,5,7],[1,3,15],[2,11,14]]
% 416,780,793 inferences, 157.844 CPU in 160.906 seconds (98% CPU, 2640464 Lips)
true ;
Si on a un groupe de 12 élèves seulement travaillant toujours par 3 et qu'on a 4 TP à faire en 4 séances on configure details(4, 3) dans le programme puis Prolog nous sort la grille pour 12 élèves en moins de 30 secondes (avec les options labeling([ffc, bisect], FL)) :
1 ?- time(solve).
[[1,2,9],[3,4,10],[5,6,11],[7,8,12]]
[[3,5,7],[1,6,12],[2,8,10],[4,9,11]]
[[4,6,8],[2,7,11],[3,9,12],[1,5,10]]
[[10,11,12],[5,8,9],[1,4,7],[2,3,6]]
% 56,568,677 inferences, 21.531 CPU in 21.875 seconds (98% CPU, 2627283 Lips)
true
Et voici une autre grille générée cette fois avec les options labeling([ff, enum], FL) :
1 ?- time(solve).
[[1,5,9],[2,6,10],[3,7,11],[4,8,12]]
[[2,3,4],[1,7,12],[5,8,10],[6,9,11]]
[[6,7,8],[4,5,11],[2,9,12],[1,3,10]]
[[10,11,12],[3,8,9],[1,4,6],[2,5,7]]
% 37,017,359 inferences, 14.281 CPU in 14.563 seconds (98% CPU, 2592025 Lips)
true ;
Mais malheureusement le programme ci-dessus n'arrive pas à sortir une grille de roulement pour un groupe de 18 élèves travaillant par 3 durant 6 séances. Si on lance le programme avec details(6, 3) SWI-Prolog calcule durant des heures sans sortir de grille ni planter. Au bout de 12 heures de calcul avec details(6, 3) SWI-Prolog n'a toujours pas sorti de grille (alors qu'il met seulement 15 secondes pour 12 élèves et 100 secondes pour 15 élèves ...). L'objectif de généraliser le problème à tous les groupes d'élèves multiples de 3 n'est donc toujours pas atteint. Mais pourquoi ? Mystère ! :-)
Mais le programme ci-dessus nous permet tout de même de découvrir 10 nouveaux prédicats, principalement pour la manipulation des listes.
Explications concernant les 10 nouvelles fonctions (ou prédicats, ou opérateurs, ...) utilisées dans ce programme et qui n'ont jamais été utilisées dans les exemples précédents :
Les 5 fonctions natives de SWI-Prolog length, nth1, numlist, flatten et maplist :
length(L,N) retourne true si L est une liste composée de N éléments (donne à N la taille de L afin d'être vrai). Exemple :
1 ?- length([1,2,3,4,5],X).
X = 5.
nth1(N,L,X) retourne true si la liste L possède l'élément X à la position N. Exemple :
1 ?- nth1(2,[7,9,12,45],9).
true.2 ?- nth1(3,[7,9,12,45],9).
false.3 ?- nth1(1,L,9),nth1(2,L,8),nth1(3,L,7),length(L,3).
L = [9, 8, 7].
numlist(MIN,MAX, L) crée une liste numérique L composée des entiers allant de MIN à MAX. Exemple :
1 ?- numlist(2,9,L).
L = [2, 3, 4, 5, 6, 7, 8, 9].
flatten(L1,L2) applanit et unifie une liste composée L1. L1 peut contenir de nombreuses listes imbriquées récursivement. flatten extrait tous les éléments contenus dans L1 et stoque le résultat dans une liste "plane" L2 (à une seule dimension). Exemple :
1 ?- flatten([[1,[2],3], [[4,5],[6,7]]], L).
L = [1, 2, 3, 4, 5, 6, 7].2 ?- flatten([[1], [2,3,4,5]], L).
L = [1, 2, 3, 4, 5]
Remarque : flatten applanit une liste composée mais ne suprime pas les doublons :
3 ?- flatten([[1,[2],[1,3]], [[2,1],[1,2]]], L).
L = [1, 2, 1, 3, 2, 1, 1, 2].
maplist(P,L) applique le prédicat P sur chaque élément de la liste L. Exemple :
1 ?- maplist(writeln,[1,2,3,4,5]).
1
2
3
4
5
true.
Ci-dessous X prend à tour de rôle chacune des sous-listes de la liste composée, et le prédicat \X^(all_distinct(X)) répond true si tous les éléments de la sous-liste X sont différents :
2 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,4]]).
true.3 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,3]]).
false.4 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,2]]).
true.
De manière générale maplist(P,L) est true si le prédicat P est true pour chacun des éléments de la liste L. L'exemple suivant vérifie que tous les éléments d'une liste sont inférieurs à 5 :
5 ?- maplist(\X^(X#<5), [1,2,3,4]).
true.6 ?- maplist(\X^(X#<5), [1,2,3,6]).
false.
Et si on passe en paramètre 2 listes à maplist(P,L1,L2) le prédicat P reçoit à chaque appel 2 paramètres : les éléments de même rang pris dans les listes L1 et L2. Dans la syntaxe \X^Y^(...) du prédicat chaque paramètre est séparé des autres par un caractères ^ et le code du prédicat est écrit entre les paranthèses. Dans cet exemple les 2 paramètres reçu par le prédicat s'appellent X et Y, et le prédicat \X^Y^(write(X),write(' '),writeln(Y)) se contente de les afficher :
7 ?- maplist(\X^Y^(write(X),write(' '),writeln(Y)), [1,2,3,4],[5,6,7,8]).
1 5
2 6
3 7
4 8
true.
L'exemple suivant fabrique une liste L en multipliant par 3 chaque élément de la liste initiale :
8 ?- maplist(\X^Y^(Y is 3*X), [1,2,3,4],L).
L = [3, 6, 9, 12].
L'exemple suivant montre comment composer une 3ème liste à partir de deux autres : chaque élément de la liste L est la somme des 2 éléments de même rang dans les autres liste (ce qui peut correspondre au calcul de la somme de deux vecteurs). On passe en paramètre à maplist 3 listes, et les paramètres X Y et Z du prédicat représentent un élément de même rang dans chacune des listes à chaque appel :
9 ?- maplist(\X^Y^Z^(Z is X+Y), [1,2,3,4],[5,6,7,8],L).
L = [6, 8, 10, 12].
Et à partir des deux listes initiales précédentes l'exemple suivant génère 2 nouvelles listes : une "liste somme" L1 et une "liste produit" L2 :
10 ?- maplist(\W^X^Y^Z^(Y is W+X,Z is W*X), [1,2,3,4],[5,6,7,8],L1,L2).
L1 = [6, 8, 10, 12],
L2 = [5, 12, 21, 32].
On peut donc passer en paramètre à maplist autant de listes qu'on veut, et le prédicat appelé pour chaque élément de même rang des listes doit avoir autant de paramètres qu'il y a de listes.
Les 5 fonctions disponibles seulement après avoir inclus les modules lambda et clpfd : all_distinct, chain, ins, labeling et foldl :
:- use_module(library(lambda)).
:- use_module(library(clpfd)).
Le modules clpfd contient les prédicats suivants : all_distinct/1 chain/2 (ins)/2 et labeling/2
Par défaut SWI-Prolog contient les prédicats foldl/4 foldl/5 foldl/6 et foldl/7
Le modules lambda permet de définir directement des prédicats avec passage de paramètres en utilisant la syntaxe \X^Y^Z^(action)
all_distinct(L) retourne true si tous les éléments de la liste L sont différents. Exemple :
1 ?- all_distinct([1,2,3]).
true.2 ?- all_distinct([1,2,2]).
false.
chain(L, #<) retourne true si les nombres de la liste numérique L sont rangés dans l'ordre croissant. Exemple :
1 ?- chain([1,2,3],#<).
true.2 ?- chain([1,4,3],#<).
false.
L ins MIN..MAX retourne true si tous ses éléments de la liste numérique L sont compris dans l'intervale MIN..MAX. Exemples :
1 ?- [1,2,3] ins 1..3.
true.2 ?- [1,2,3] ins 1..8.
true.3 ?- [1,2,3] ins 5..8.
false.4 ?- [6,7] ins 5..8.
true.5 ?- [6,7,8] ins 7..9.
false.
labeling([ffc, bisect], L) : oriente Prolog vers une méthode ou une autres dans le choix des variables lorsque plusieurs solutions sont possibles. Exemple : labeling([ff, enum], L) ou labeling([], L)
foldl(P,L,A,B) : appelle le prédicat P autant de fois que le nombre d'éléments de la liste L en lui passant 3 paramètres, le premier paramètre étant à tour de rôle chaque élément de la liste L :
1 ?- foldl(\X^Y^Z^(write('X='),write(X),write(' Y='),write(Y),write(' Z='),writeln(Z)), [1,2,3],4,5).
X=1 Y=4 Z=_G4202
X=2 Y=_G4202 Z=_G4248
X=3 Y=_G4248 Z=_G4294
true.
L'exemple suivant montre comment calculer la somme de tous les éléments d'une liste grâce à foldl :
2 ?- foldl(\X^Y^Z^(Z is Y+X), [1,2,3,4], 0, R).
R = 10.
Voici pour l'exemple précédent l'évolution des 4 variables à chaque appel du prédicat (0 est la valeur initiale de Y et R est le résultat final) :
3 ?- foldl(\X^Y^Z^(write('X='),write(X),write(' Y='),write(Y),write(' Z='),write(Z),write(' R='),writeln(R),Z is Y+X), [1,2,3,4], 0, R).
X=1 Y=0 Z=_G2399 R=_G2432
X=2 Y=1 Z=_G2462 R=_G2495
X=3 Y=3 Z=_G2525 R=_G2558
X=4 Y=6 Z=_G2588 R=_G2621
R = 10.
Et voici un programme calculant la somme d'une liste grâce à foldl/4 mais sans la syntaxe du module lambda :
# Programme réalisé le 29 janvier 2017
# Ce programme montre comment calculer la somme d'une liste numérique
# en utilisant foldl/4 mais sans utiliser le module lambda et sa syntaxe# On définit un pédicat add/3 qui attend 3 paramètre X,Y et S tel qui S=X+Y
# puis foldl/4 appelle le prédicat add/3 en lui passant 3 paramètres : un
# élément de la liste L, 0, et Sadd(X,Y,S):- S is X+Y.
somme(L,S):- foldl(add,L,0,S).
Exemple d'utilisation :
?- somme([1,2,3,4],R).
R = 10.
Autres prédicats avancés de SWI-Prolog à voir en lien avec les listes : include/3, exclude/3, partition/4 et scanl/4.
Exemples d'utilisation de certains prédicats liés aux listes :
Test des prédicats foldl et scanl (fold = plier et scan = parcourir)
On commence par définir un prédicat afficher/3 attendant 3 paramètres, les affichant, et donnant comme valeur au 3ème la somme des deux autres :
% Février 2017
afficher(A,B,C):-write(A),write(B),writeln(C),C is A+B.
Appelons foldl :
?- foldl(afficher,[1,2,3],4,X).
14_L166
25_L166
37_L166
X = 10.
Il renvoie X=10 après 3 appels à afficher/3
A chaque appel, foldl passe 3 paramètres à afficher/3
Le premier paramètre est un élément de la liste qui seront tous utiliser à tour de role.
Au final la variable X vaut 10, soit 4+1+2+3
Appelons scanl :
?- scanl(afficher,[1,2,3],4,X).
14_G9536
25_G9542
37_G9548
X = [4, 5, 7, 10].
Comme pour foldl, scanl appelle 3 fois afficher/3, en lui passant 3 parmètres à chaque fois.
Le premier paramètre est un élément de la liste qui seront tous utiliser à tour de role.
Au final on constate que la variable X n'est pas un scalaire mais une liste contenant toutes les valeurs du deuxième paramètre (4, 5 et 7) ainsi que la valeur finale (10)
A retenir : foldl renvoie seulement la valeur finale alors que scanl renvoie une liste contenant toutes les valeurs intermédiaires (deuxième paramètre passé au prédicat appelé)
Application : quelle est la somme des 8 premiers entiers naturels ?
Réponse : 36 donné par foldl :
?- numlist(1,8,L),foldl(afficher,L,0,X).
L = [1, 2, 3, 4, 5, 6, 7, 8],
X = 36.
Quels sont les calculs intermédiaires ? Réponse donnée par scanl :
?- numlist(1,8,L),scanl(afficher,L,0,X).
L = [1, 2, 3, 4, 5, 6, 7, 8],
X = [0, 1, 3, 6, 10, 15, 21, 28, 36].
scanl nous indique que pour arriver à 36 foldl a effectuer les calculs suivants :
0+1=1, +1=2, +3=6, +4=10, +5=15, +6=21, +7=28, et +8=36
Si on veut seulement le résultat final sans afficher la valeur des 3 paramètres à chaque appel, le prédicat appelé se résume à faire une simple addition. Dans ce cas on peut le définir directement dans foldl en utilisant la syntaxe lambda, et sans écrire à part un nouveau prédicat afficher.
?- numlist(1,8,L),foldl(\X^Y^Z^(Z is X+Y),L,0,X).
L = [1, 2, 3, 4, 5, 6, 7, 8],
X = 36.
Application : combien vaut la factorielle de 8 ? Calculons le produit des 8 premiers entiers naturels grâce à foldl :
?- numlist(1,8,L),foldl(\X^Y^Z^(Z is X*Y),L,1,X).
L = [1, 2, 3, 4, 5, 6, 7, 8],
X = 40320.
Demandons les calculs intermédiaires à scanl :
?- numlist(1,8,L),scanl(\A^B^C^(C is A*B),L,1,X).
L = [1, 2, 3, 4, 5, 6, 7, 8],
X = [1, 1, 2, 6, 24, 120, 720, 5040, 40320].
Remarque : pour scanl la variable recherchée (X) ne doit pas avoir le même nom qu'un des paramètres lambda (d'où le renommage des paramètres en A B et C), mais pour foldl cela fonctionnait très bien.
Si on utilise X, Y et Z pour les paramètres lambda alors scanl répond simplement false, ce qui pourait faire croire que le problème est sans solution :
?- numlist(1,8,L),scanl(\X^Y^Z^(Z is X*Y),L,1,X).
false.
Application de foldl : inverser une liste :
?- L1=[a,b,c,d,e],foldl(\X^Y^Z^(Z=[X|[Y]]),L1,[],L2),flatten(L2,L).L1 = [a, b, c, d, e],
L2 = [e, [d, [c, [b, [a|...]]]]],
L = [e, d, c, b, a].
L1 est la liste de départ
L2 est la liste créée par foldl, contenant seulement 2 éléments, mais le second est une liste composée
L est la mise à plat de la liste composée L2 grâce à flatten : il s'agit de L1 avec l'ordre des éléments inversé.
Voici quelques programmes écrits dans d'autres langage que Prolog permettant de générer les grilles de roulement de TP :
Génération d'une grille pour 12 élèves en Perl en simulant la rotation des disques en carton :
# Permutations circulaires des valeurs dans un tableau :
# Génération d'une grille de roulement pour 12 élèves
# Programme réalisé le 10 février 2015# Configuration des 3 disques divisé chacun en 4 secteurs angulaires :
@t1=("A","B","C","D");
@t2=("E","F","G","H");
@t3=("I","J","K","L");for ($i=0;$i<4;$i++)
{
for ($j=0;$j<4;$j++)
{
printf "$t1[$j] $t2[$j] $t3[$j] ";
}
printf "\n";
# Rotation du disque 1 d'1 secteur dans le sens 1 :
($t1[0],$t1[1],$t1[2],$t1[3])=($t1[3],$t1[0],$t1[1],$t1[2]);
# Rotation du disque 2 d'1 secteur dans le sens 2 :
($t2[0],$t2[1],$t2[2],$t2[3])=($t2[1],$t2[2],$t2[3],$t2[0]);
# Rotation du disque 3 de 2 secteurs dans le sens 2 :
($t3[0],$t3[1],$t3[2],$t3[3])=($t3[2],$t3[3],$t3[0],$t3[1]);
}
Résultat obtenu :
A E I B F J C G K D H L
D F K A G L B H I C E J
C G I D H J A E K B F L
B H K C E L D F I A G J
Génération d'une grille pour 15 élèves en Perl en simulant la rotation des disques en carton :
# Permutations circulaires des valeurs dans un tableau :
# Génération d'une grille de roulement pour 15 élèves
# Programme réalisé le 10 février 2015# Configuration des 3 disques divisé chacun en 5 secteurs angulaires :
@t1=("A","B","C","D","E");
@t2=("F","G","H","I","J");
@t3=("K","L","M","N","O");for ($i=0;$i<5;$i++)
{
for ($j=0;$j<5;$j++)
{
printf "$t1[$j] $t2[$j] $t3[$j] ";
}
printf "\n";
# Rotation du disque 1 d'1 secteur dans le sens 1 :
($t1[0],$t1[1],$t1[2],$t1[3],$t1[4])=($t1[4],$t1[0],$t1[1],$t1[2],$t1[3]);
# Rotation du disque 2 d'1 secteur dans le sens 2 :
($t2[0],$t2[1],$t2[2],$t2[3],$t2[4])=($t2[1],$t2[2],$t2[3],$t2[4],$t2[0]);
# Rotation du disque 3 de 2 secteurs dans le sens 2 :
($t3[0],$t3[1],$t3[2],$t3[3],$t3[4])=($t3[2],$t3[3],$t3[4],$t3[0],$t3[1]);
}
Résultat obtenu :
A F K B G L C H M D I N E J O
E G M A H N B I O C J K D F L
D H O E I K A J L B F M C G N
C I L D J M E F N A G O B H K
B J N C F O D G K E H L A I M
Transformation du problème des grilles de roulement en un problème SAT
Génération d'une grille pour 18 élèves en Python en utilisant le SAT Solver minisat qui résoud des problèmes SAT (problème de satisfaisabilité booléenne modélisé par une équation logique à forme normale conjonctive : CNF en anglais pour Conjunctive Normal Form). Exemple d'équation logique CNF modélisant un problème SAT : (x1+x2+/x3).(x1+/x2).(/x1+x2+x3)
x1, x2 et x3 sont dans cet exemple les 3 variables booléennes du problème. Le rôle de minisat est de trouver une valeur (0 ou 1) pour chacune des 3 variables x1 x2 et x3 de telle sorte que l'équation CNF soit vraie (égale à 1).
Le programme en Python suivant ne résoud pas directement le problème des grilles de roulement : il génère un fichier texte nommé gen au format dimacs (description de l'équation logique CNF au format minisat) puis appelle le solver minisat qui trouve une solution et l'écrit dans le fichier nommé out. Ensuite le programme Pyton ouvre et interprète le fichier de sortie out produit par minisat pour présenter la grille de roulement sur sa sortie standard.
Le travail effectué par ce programme Python est de convertir le problème des grilles de roulement en un problème SAT en le modélisant sous la forme d'une équation logique à forme normale conjonctive (plusieurs termes en OU reliés par des ET).
# Génération d'une grille de roulement pour 18 élèves
# en utilisant le solver minisat
# Février 2015import itertools
import osPARSEOUTPUT=True
#There are 6 sessions, s in [1,6].
#There are 6 practicals, p in [1,6].
#There are 18 students, y in [1,18].
NSTUDENTS = 18
NPRACTICALS = 6
NSESSIONS = 6sessions = range(NSESSIONS)
practicals = range(NPRACTICALS)
students = range(NSTUDENTS)# setup different selections
ij_pairs = [(i,j) for i in students for j in range(i+1, NSTUDENTS)]
ijkl_tuples = [(i,j,l,k)
for i in students
for j in range(i+1, NSTUDENTS)
for k in range(j+1, NSTUDENTS)
for l in range(k+1, NSTUDENTS)]groups = [(s,p) for s in sessions for p in practicals]
practical_pairs = [(p,p_prime)
for p in practicals
for p_prime in range(p+1, NPRACTICALS)]
session_pairs = [(s,s_prime)
for s in sessions
for s_prime in range(s+1, NSESSIONS)]print( len(ij_pairs), len(ijkl_tuples), len(groups), len(practical_pairs), len(session_pairs))
# allocate all of the variables
variables=itertools.count(1,1)# In each session, a student is assigned into a practical.
# The set of students assigned into the same practical and session is a group.# x_{s,p,i} student i is in session s and practical p [648]
# y_{s,p,i,j} students i and j (i < j) is in session s and practical p [6426]xs = dict()
reverse_xs = dict()
for s in sessions:
for p in practicals:
for i in students:
xs[(s,p,i)] = variables.next()
reverse_xs[xs[(s,p,i)]] = (s,p,i)
def x(s,p,i):
return xs[(s,p,i)]
ys = dict()
reverse_ys = dict()
for s in sessions:
for p in practicals:
for i,j in ij_pairs:
ys[(s,p,i,j )] = variables.next()
reverse_ys[ys[(s,p,i,j)]] = (s,p,i,j)
def y(s,p,i,j):
return ys[(s,p,i,j)]numvariables = variables.next()
clauses = []
#% Define each y_{s,p,i,j} [6426, 2] [6426, 2], [6426, 3]
# forall_{s,p,i<j} y_{s,p,i,j} => x_{s,p,i}
# forall_{s,p,i<j} y_{s,p,i,j} => x_{s,p,j}
# forall_{s,p,i<j} or(~x_{s,p,i}, ~x_{s,p,j}, y_{s,p,i,j})
for s, p in groups:
for i,j in ij_pairs:
clauses.append( [-y(s,p,i,j), x(s,p,i)])
clauses.append( [-y(s,p,i,j), x(s,p,j)])
clauses.append( [-x(s,p,i), -x(s,p,j), y(s,p,i,j)])
print (len(clauses))# % Each group is >= 2 distinct students [36, 153]
# forall_{s,p} exists_{i < j} y_{s,p,i,j}
for s, p in groups:
c = [y(s,p,i,j) for (i,j) in ij_pairs]
clauses.append(c)print (len(clauses))
# % each group is >= 3 distinct students [5508, 16+1]
# forall_{s,p,i,j} y_{s,p,i,j} => exists_{k!=i and k!=j} x_{s,p,k}
for s, p in groups:
for i,j in ij_pairs:
c = [-y(s,p,i,j)]
for k in students:
if k != i and k != j:
c.append(x(s,p,k))
clauses.append(c)
print (len(clauses))# % each group is < 4 [110160, 4]
# forall_{s,p,i<j<k<l} not( and(x_{s,p,i},x_{s,p,j},x_{s,p,k},x_{s,p,l}))
for s,p in groups:
for i,j,k,l in ijkl_tuples:
c= [-x(s,p,i),-x(s,p,j),-x(s,p,k),-x(s,p,l) ]
clauses.append(c)print (len(clauses))
# % all the students must participate in every session [108, 6]
# forall_{s,i} exists_{p} x_{s,p,i}for s in sessions:
for i in students:
c = [x(s,p,i) for p in practicals]
clauses.append(c)
print (len(clauses))
# % all the students must participate in every practical [108, 6]
# forall_{p,i} exists_{s} x_{s,p,i}
for p in practicals:
for i in students:
c = [x(s,p,i) for s in sessions]
clauses.append(c)print (len(clauses))
# % no student participates in two practicals in the same session [1620, 2]
# forall_{i,s,p<p'} not(and(x_{s,p,i}, x_{s,p',i}))
for s in sessions:
for i in students:
for p,p_prime in practical_pairs:
c = [-x(s,p,i),-x(s,p_prime,i)]
clauses.append(c)print (len(clauses))
# % no student participates twice in the same practical in different sessions [1620, 2]
# forall_{i,p, s<s'} not(and(x_{s,p,i}, x_{s',p,i}))
for p in practicals:
for i in students:
for s,s_prime in session_pairs:
c= [-x(s,p,i),-x(s_prime,p,i)]
clauses.append(c)
print (len(clauses))
# % Two students are in the same group most once [34425, 2]
# forall_{s<s',p<p',i<j} (not y_{s,p,i,j} or not y_{s',p',i,j})
for i,j in ij_pairs:
for p,p_prime in practical_pairs:
for s,s_prime in session_pairs:
c= [-y(s,p,i,j), -y(s_prime,p_prime,i,j)]
clauses.append(c)
c= [-y(s_prime,p,i,j), -y(s,p_prime,i,j)]
clauses.append(c)print (len(clauses))
# prépare le fichier gen qui sera transmis à minisat :
print ('p cnf ', numvariables, len(clauses))
with open("gen", "w") as f:
f.write('p cnf ' + str( variables.next() ) +' '+ str( len(clauses))+'\n')
for c in clauses:
f.write( " ".join(map(lambda x: str(x),c)))
f.write( " 0\n")# execute
# minisat gen out
# Appel du solver minisat en lui passant en paramètre le fichier gen :
os.system('minisat gen out')
if PARSEOUTPUT:
# lit le fichier out généré par minisat :
with open("out", "r") as f:
lines = list(f)
assert len(lines) == 2
assert lines[0] == "SAT\n"
assignments = lines[1].split(" ")
positives = []
for literal in assignments:
lit = int(literal)
if lit in reverse_xs and lit > 0:
(s,p,i) = reverse_xs[lit]
positives.append((i,s,p))
for s in sessions :
chars = list()
for p in practicals :
for k in students :
if (k,s,p) in positives :
chars.append("%2d " %(k+1))
chars.append('\t')
print("".join(chars))
Résultat obtenu :
13 15 17 10 11 12 2 4 18 3 6 7 5 8 16 1 9 14
3 16 18 2 14 15 5 6 11 1 8 12 9 10 13 4 7 17
5 9 12 1 16 17 7 10 15 11 13 18 4 6 14 2 3 8
7 11 14 3 4 5 8 9 17 2 10 16 1 15 18 6 12 13
1 2 6 7 8 13 12 14 16 4 9 15 3 11 17 5 10 18
4 8 10 6 9 18 1 3 13 5 14 17 2 7 12 11 15 16
Et après mise en forme voici la grille de roulement pour 18 élèves travaillant par groupe de 3 sur 6 TP différents durant 6 séances. Les 18 élèves sont identifiés chacun par une lettre unique (de A à R) :
Pour obtenir d'autres grilles pour 18 élèves il suffit d'effectuer des permutations circulaires avec les 18 lettres sur cette grille de base qui peut alors donner instantanémant 17 autres variantes.
Le problème à résoudre est le suivant : on dispose d'une liste de N éléments, et on veut toutes les listes de K éléments pris dans la liste d'origine et sans notion d'ordre. Exemple :
On veut toutes les listes à 3 éléments pris dans la liste à 5 éléments [a, b, c, d, e]. La solution recherchée est :
[a, b, c]
[a, b, d]
[a, b, e]
[a, c, d]
[a, c, e]
[a, d, e]
[b, c, d]
[b, c, e]
[b, d, e]
[c, d, e]
Ces 10 listes sont bien uniques en considérant que [a, b, c] et [a, c, b] sont identiques : la liste [a, b, c] n'est pas suivi de toutes ses permutations.
Première solution simple : on demande toutes les permutations de la liste [a, b, c, d, e] et parmi toutes les permutations on n'affiche que les listes possédant 3 éléments. Le programme en Prolog possède alors une seule ligne :
afficher(X):-permutation(L,[a,b,c,d,e]),append(X,[_,_],L).
Appelons le prédicat afficher dans l'interpréteur SWI-Prolog :
?- afficher(X).
Et voici les solutions affichées (en appuyant sur ; pour passer d'une ligne à l'autre) :
X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, b] ;
X = [a, c, b] ;
X = [a, d, b] ;
X = [a, e, b] ;
X = [a, d, b] ;
X = [a, e, b] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, c] ;
X = [a, e, c] ;
X = [a, d, e] ;
X = [a, e, d] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, c] ;
X = [a, e, c] ;
X = [a, d, e] ;
X = [a, e, d] ;
X = [b, a, c] ;
X = [b, a, c] ;
X = [b, a, d] ;
X = [b, a, e] ;
X = [b, a, d] ;
X = [b, a, e] ;
X = [c, a, b] ;
X = [c, a, b] ;
X = [d, a, b] ;
X = [e, a, b] ;
X = [d, a, b] ;
X = [e, a, b] ;
X = [c, a, d] ;
X = [c, a, e] ;
X = [d, a, c] ;
X = [e, a, c] ;
X = [d, a, e] ;
X = [e, a, d] ;
X = [c, a, d] ;
X = [c, a, e] ;
X = [d, a, c] ;
X = [e, a, c] ;
X = [d, a, e] ;
X = [e, a, d] ;
X = [b, c, a] ;
X = [b, c, a] ;
X = [b, d, a] ;
X = [b, e, a] ;
X = [b, d, a] ;
X = [b, e, a] ;
X = [c, b, a] ;
X = [c, b, a] ;
X = [d, b, a] ;
X = [e, b, a] ;
X = [c, d, a] ;
X = [c, e, a] ;
X = [d, c, a] ;
X = [e, c, a] ;
X = [d, e, a] ;
X = [e, d, a] ;
X = [c, d, a] ;
X = [c, e, a] ;
X = [d, c, a] ;
X = [e, c, a] ;
X = [d, e, a] ;
X = [e, d, a] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, c] ;
X = [b, e, c] ;
X = [b, d, e] ;
X = [b, e, d] ;
X = [c, b, d] ;
X = [c, b, e] ;
X = [d, b, c] ;
X = [e, b, c] ;
X = [d, b, e] ;
X = [e, b, d] ;
X = [c, d, b] ;
X = [c, e, b] ;
X = [d, c, b] ;
X = [e, c, b] ;
X = [d, e, b] ;
X = [e, d, b] ;
X = [c, d, e] ;
X = [c, e, d] ;
X = [d, c, e] ;
X = [e, c, d] ;
X = [d, e, c] ;
X = [e, d, c] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, c] ;
X = [b, e, c] ;
X = [b, d, e] ;
X = [b, e, d] ;
X = [c, b, d] ;
X = [c, b, e] ;
X = [d, b, c] ;
X = [e, b, c] ;
X = [d, b, e] ;
X = [e, b, d] ;
X = [c, d, b] ;
X = [c, e, b] ;
X = [d, c, b] ;
X = [e, c, b] ;
X = [d, e, b] ;
X = [e, d, b] ;
X = [c, d, e] ;
X = [c, e, d] ;
X = [d, c, e] ;
X = [e, c, d] ;
X = [d, e, c] ;
X = [e, d, c] ;etc.
Le problème est qu'en prenant seulement les 3 premiers éléments des listes issues de toutes les permutations possibles de la liste d'origine on obtient inévitablement des doublons (plusieurs fois la même liste), ainsi que des permutations de chacune des listes à 3 éléments, c'est-à-dire exactement ce que l'on voulait éviter ...
Voici une autre solution, qui donne moins de réponses mais qui génère tout de même encore des doublons :
partie([X|E],P,[X|L]):-K is P-1,partie(E,K,L).
partie(E,P,[_|L]):-partie(E,P,L).
partie([],0,_).
Appelons le prédicat partie dans l'interpréteur SWI-Prolog :
?- partie(X,3,[a,b,c,d,e]).
La réponse est :
X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;
Remarque : l'emploi de la coupure dans le programme précédent devrait permettre de supprimer les doublons.
Et voici une première solution qui utilise seulement le prédicat prédéfini append/3 :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% Mars 2014 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
scinder(L, [], L).
scinder([T|Q], [T|L1], L2) :-
scinder(Q, L1, L2).
solution(0,L,[], L).
solution(N,L,[T|L3],R) :-
N>0,
scinder(L, L1, [T|L2]),
N1 is N-1,
solution(N1,L2,L3,L4),
append(L1,L4,R).
Appelons le prédicat solution dans l'interpétuer SWI-Prolog en lui passant en paramètre le nombre d'éléments voulu ainsi que la liste d'origine :
?- solution(3,[a,b,c,d,e],X,Y).
Et voici le résultat :
X = [a, b, c],
Y = [d, e] ;
X = [a, b, d],
Y = [c, e] ;
X = [a, b, e],
Y = [c, d] ;
X = [a, c, d],
Y = [b, e] ;
X = [a, c, e],
Y = [b, d] ;
X = [a, d, e],
Y = [b, c] ;
X = [b, c, d],
Y = [a, e] ;
X = [b, c, e],
Y = [a, d] ;
X = [b, d, e],
Y = [a, c] ;
X = [c, d, e],
Y = [a, b] ;
X est une liste à 3 éléments, Y est le reste de la liste (éléments de la liste d'origine n'appartenant pas à la liste X).
Si on veut seulement les listes à 3 éléments on ne spécifira pas de variable pour le dernier paramètre du prédicat solution :
?- solution(3,[a,b,c,d,e],X,_).
Et cette fois on obtient bien les 10 listes à 3 éléments pris dans la liste d'origine à 5 éléments, sans doublons de liste :
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;
Mais en utilisant les prédicats avancés disponibles dans SWI-Prolog pour la gestion des listes il est possible de générer d'un coup toutes les sous-listes d'une liste sans doublon et en utilisant une seule ligne de commande.
Voici la solution optimale :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% 17 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
L1=[a,b,c,d,e],
findall(L4,(permutation(L1,L2),append(_,L3,L2),length(L3,3),msort(L3,L4)),L5),
list_to_set(L5,L6),
maplist(writeln,L6),
length(L6,N).
Prolog nous renvoie instantanément les 10 sous-listes à 3 éléments issues de la liste [a,b,c,d,e] et sans doublon :
[c,d,e]
[b,d,e]
[b,c,e]
[b,c,d]
[a,d,e]
[a,c,e]
[a,c,d]
[a,b,e]
[a,b,d]
[a,b,c]
Application : on recherche toutes les sous-listes à k éléments prises dans une liste à n éléments (n>k) et sans doublon.
La ligne suivante trouve instantanément l'ensemble des listes recherchée en utilisant les prédicats findall, permutation, append, length, sort et maplist.
Exemple pour trouver toutes les listes à 3 éléments prises dans la liste numérique à 5 éléments [1,2,3,4,5] :
?- numlist(1,5,L1),
findall(L4,(permutation(L1,L2),append(_,L3,L2),length(L3,3),msort(L3,L4)),L5),
list_to_set(L5,L6),
maplist(writeln,L6),
length(L6,N).
Résultats obtenus :
[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
[2,3,5]
[2,4,5]
[3,4,5]
L1 = [1, 2, 3, 4, 5],
L5 = [[3, 4, 5], [3, 4, 5], [3, 4, 5], [3, 4, 5], [3, 4, 5], [3, 4, 5], [2, 4|...], [2|...], [...|...]|...],
L6 = [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3|...], [2|...], [...|...]|...],
N = 10.
Explications :
L1 est une liste numérique entre 1 et 5 : L1 = [1, 2, 3, 4, 5]
L2 représente toutes les permutations possibles de L1 (toujours à 5 éléments)
L3 représente toutes les sous-listes prises dans L2, entre 0 et 5 éléments, puis on garde pour L3 seulement les sous-listes à 3 éléments grâce à length(L3,3)
L4 est la liste L3 triée dans l'ordre croissant (sans supprimer les doublons, mais elle n'en avait pas) créée avec msort(L3,L4)
L5 représente toutes les solutions L4 trouvées : L5 est une liste de listes L4 contenant des doublons
L6 est la liste L5 sans doublon (sans la trier) créée avec list_to_set(L5,L6)
Enfin les éléments de L6 sont affichés et N représente le nombre de listes trouvées (taille de L6)
Exemple d'application : on recherche toutes les listes à 4 élements issues de la liste à 9 éléments [a,b,c,d,e,f,g,h,i] :
?- L1=[a,b,c,d,e,f,g,h,i],
findall(L4,(permutation(L1,L2),append(_,L3,L2),length(L3,4),msort(L3,L4)),L5),
list_to_set(L5,L6),
maplist(writeln,L6),
length(L6,N).
Prolog nous renvoie 126 listes à 4 éléments, chaque liste n'étant pas suivie par toutes ses permutations.
Application immédiate : la génération automatique de QCM contenant 1 bonne réponse et 3 mauvaises avec permutation des mauvaises réponses. Imaginons qu'on dispose de 10 questions sur les unités de mesure dont la réponse est unique : la bonne réponse à une question est considérée fausse pour les 9 autres. On désire obtenir tous les groupes de 4 réponses prises parmi les 10 et sans doublons quelque soit l'ordre. Le programme précédent en Prolog nous donne les 210 solutions possibles :
?- solution(4, [volt, ampère, coulomb, henry, weber, ohm, siemens, watt, joule, farad], X,_).
X = [volt, ampère, coulomb, henry] ;
X = [volt, ampère, coulomb, weber] ;
X = [volt, ampère, coulomb, ohm] ;
X = [volt, ampère, coulomb, siemens] ;
X = [volt, ampère, coulomb, watt] ;
X = [volt, ampère, coulomb, joule] ;
X = [volt, ampère, coulomb, farad] ;
X = [volt, ampère, henry, weber] ;
X = [volt, ampère, henry, ohm] ;
X = [volt, ampère, henry, siemens] ;
X = [volt, ampère, henry, watt] ;
X = [volt, ampère, henry, joule] ;
X = [volt, ampère, henry, farad] ;
X = [volt, ampère, weber, ohm] ;
X = [volt, ampère, weber, siemens] ;
X = [volt, ampère, weber, watt] ;
X = [volt, ampère, weber, joule] ;
X = [volt, ampère, weber, farad] ;
X = [volt, ampère, ohm, siemens] ;
X = [volt, ampère, ohm, watt] ;
X = [volt, ampère, ohm, joule] ;
X = [volt, ampère, ohm, farad] ;
X = [volt, ampère, siemens, watt] ;
X = [volt, ampère, siemens, joule] ;
X = [volt, ampère, siemens, farad] ;
X = [volt, ampère, watt, joule] ;
X = [volt, ampère, watt, farad] ;
X = [volt, ampère, joule, farad] ;
X = [volt, coulomb, henry, weber] ;
X = [volt, coulomb, henry, ohm] ;
X = [volt, coulomb, henry, siemens] ;
X = [volt, coulomb, henry, watt] ;
X = [volt, coulomb, henry, joule] ;
X = [volt, coulomb, henry, farad] ;
X = [volt, coulomb, weber, ohm] ;
X = [volt, coulomb, weber, siemens] ;
X = [volt, coulomb, weber, watt] ;
X = [volt, coulomb, weber, joule] ;
X = [volt, coulomb, weber, farad] ;
X = [volt, coulomb, ohm, siemens] ;
X = [volt, coulomb, ohm, watt] ;
X = [volt, coulomb, ohm, joule] ;
X = [volt, coulomb, ohm, farad] ;
X = [volt, coulomb, siemens, watt] ;
X = [volt, coulomb, siemens, joule] ;
X = [volt, coulomb, siemens, farad] ;
X = [volt, coulomb, watt, joule] ;
X = [volt, coulomb, watt, farad] ;
X = [volt, coulomb, joule, farad] ;
X = [volt, henry, weber, ohm] ;
X = [volt, henry, weber, siemens] ;
X = [volt, henry, weber, watt] ;
X = [volt, henry, weber, joule] ;
X = [volt, henry, weber, farad] ;
X = [volt, henry, ohm, siemens] ;
X = [volt, henry, ohm, watt] ;
X = [volt, henry, ohm, joule] ;
X = [volt, henry, ohm, farad] ;
X = [volt, henry, siemens, watt] ;
X = [volt, henry, siemens, joule] ;
X = [volt, henry, siemens, farad] ;
X = [volt, henry, watt, joule] ;
X = [volt, henry, watt, farad] ;
X = [volt, henry, joule, farad] ;
X = [volt, weber, ohm, siemens] ;
X = [volt, weber, ohm, watt] ;
X = [volt, weber, ohm, joule] ;
X = [volt, weber, ohm, farad] ;
X = [volt, weber, siemens, watt] ;
X = [volt, weber, siemens, joule] ;
X = [volt, weber, siemens, farad] ;
X = [volt, weber, watt, joule] ;
X = [volt, weber, watt, farad] ;
X = [volt, weber, joule, farad] ;
X = [volt, ohm, siemens, watt] ;
X = [volt, ohm, siemens, joule] ;
X = [volt, ohm, siemens, farad] ;
X = [volt, ohm, watt, joule] ;
X = [volt, ohm, watt, farad] ;
X = [volt, ohm, joule, farad] ;
X = [volt, siemens, watt, joule] ;
X = [volt, siemens, watt, farad] ;
X = [volt, siemens, joule, farad] ;
X = [volt, watt, joule, farad] ;
X = [ampère, coulomb, henry, weber] ;
X = [ampère, coulomb, henry, ohm] ;
X = [ampère, coulomb, henry, siemens] ;
X = [ampère, coulomb, henry, watt] ;
X = [ampère, coulomb, henry, joule] ;
X = [ampère, coulomb, henry, farad] ;
X = [ampère, coulomb, weber, ohm] ;
X = [ampère, coulomb, weber, siemens] ;
X = [ampère, coulomb, weber, watt] ;
X = [ampère, coulomb, weber, joule] ;
X = [ampère, coulomb, weber, farad] ;
X = [ampère, coulomb, ohm, siemens] ;
X = [ampère, coulomb, ohm, watt] ;
X = [ampère, coulomb, ohm, joule] ;
X = [ampère, coulomb, ohm, farad] ;
X = [ampère, coulomb, siemens, watt] ;
X = [ampère, coulomb, siemens, joule] ;
X = [ampère, coulomb, siemens, farad] ;
X = [ampère, coulomb, watt, joule] ;
X = [ampère, coulomb, watt, farad] ;
X = [ampère, coulomb, joule, farad] ;
X = [ampère, henry, weber, ohm] ;
X = [ampère, henry, weber, siemens] ;
X = [ampère, henry, weber, watt] ;
X = [ampère, henry, weber, joule] ;
X = [ampère, henry, weber, farad] ;
X = [ampère, henry, ohm, siemens] ;
X = [ampère, henry, ohm, watt] ;
X = [ampère, henry, ohm, joule] ;
X = [ampère, henry, ohm, farad] ;
X = [ampère, henry, siemens, watt] ;
X = [ampère, henry, siemens, joule] ;
X = [ampère, henry, siemens, farad] ;
X = [ampère, henry, watt, joule] ;
X = [ampère, henry, watt, farad] ;
X = [ampère, henry, joule, farad] ;
X = [ampère, weber, ohm, siemens] ;
X = [ampère, weber, ohm, watt] ;
X = [ampère, weber, ohm, joule] ;
X = [ampère, weber, ohm, farad] ;
X = [ampère, weber, siemens, watt] ;
X = [ampère, weber, siemens, joule] ;
X = [ampère, weber, siemens, farad] ;
X = [ampère, weber, watt, joule] ;
X = [ampère, weber, watt, farad] ;
X = [ampère, weber, joule, farad] ;
X = [ampère, ohm, siemens, watt] ;
X = [ampère, ohm, siemens, joule] ;
X = [ampère, ohm, siemens, farad] ;
X = [ampère, ohm, watt, joule] ;
X = [ampère, ohm, watt, farad] ;
X = [ampère, ohm, joule, farad] ;
X = [ampère, siemens, watt, joule] ;
X = [ampère, siemens, watt, farad] ;
X = [ampère, siemens, joule, farad] ;
X = [ampère, watt, joule, farad] ;
X = [coulomb, henry, weber, ohm] ;
X = [coulomb, henry, weber, siemens] ;
X = [coulomb, henry, weber, watt] ;
X = [coulomb, henry, weber, joule] ;
X = [coulomb, henry, weber, farad] ;
X = [coulomb, henry, ohm, siemens] ;
X = [coulomb, henry, ohm, watt] ;
X = [coulomb, henry, ohm, joule] ;
X = [coulomb, henry, ohm, farad] ;
X = [coulomb, henry, siemens, watt] ;
X = [coulomb, henry, siemens, joule] ;
X = [coulomb, henry, siemens, farad] ;
X = [coulomb, henry, watt, joule] ;
X = [coulomb, henry, watt, farad] ;
X = [coulomb, henry, joule, farad] ;
X = [coulomb, weber, ohm, siemens] ;
X = [coulomb, weber, ohm, watt] ;
X = [coulomb, weber, ohm, joule] ;
X = [coulomb, weber, ohm, farad] ;
X = [coulomb, weber, siemens, watt] ;
X = [coulomb, weber, siemens, joule] ;
X = [coulomb, weber, siemens, farad] ;
X = [coulomb, weber, watt, joule] ;
X = [coulomb, weber, watt, farad] ;
X = [coulomb, weber, joule, farad] ;
X = [coulomb, ohm, siemens, watt] ;
X = [coulomb, ohm, siemens, joule] ;
X = [coulomb, ohm, siemens, farad] ;
X = [coulomb, ohm, watt, joule] ;
X = [coulomb, ohm, watt, farad] ;
X = [coulomb, ohm, joule, farad] ;
X = [coulomb, siemens, watt, joule] ;
X = [coulomb, siemens, watt, farad] ;
X = [coulomb, siemens, joule, farad] ;
X = [coulomb, watt, joule, farad] ;
X = [henry, weber, ohm, siemens] ;
X = [henry, weber, ohm, watt] ;
X = [henry, weber, ohm, joule] ;
X = [henry, weber, ohm, farad] ;
X = [henry, weber, siemens, watt] ;
X = [henry, weber, siemens, joule] ;
X = [henry, weber, siemens, farad] ;
X = [henry, weber, watt, joule] ;
X = [henry, weber, watt, farad] ;
X = [henry, weber, joule, farad] ;
X = [henry, ohm, siemens, watt] ;
X = [henry, ohm, siemens, joule] ;
X = [henry, ohm, siemens, farad] ;
X = [henry, ohm, watt, joule] ;
X = [henry, ohm, watt, farad] ;
X = [henry, ohm, joule, farad] ;
X = [henry, siemens, watt, joule] ;
X = [henry, siemens, watt, farad] ;
X = [henry, siemens, joule, farad] ;
X = [henry, watt, joule, farad] ;
X = [weber, ohm, siemens, watt] ;
X = [weber, ohm, siemens, joule] ;
X = [weber, ohm, siemens, farad] ;
X = [weber, ohm, watt, joule] ;
X = [weber, ohm, watt, farad] ;
X = [weber, ohm, joule, farad] ;
X = [weber, siemens, watt, joule] ;
X = [weber, siemens, watt, farad] ;
X = [weber, siemens, joule, farad] ;
X = [weber, watt, joule, farad] ;
X = [ohm, siemens, watt, joule] ;
X = [ohm, siemens, watt, farad] ;
X = [ohm, siemens, joule, farad] ;
X = [ohm, watt, joule, farad] ;
X = [siemens, watt, joule, farad] ;
En traitant ce fichier texte par expressions régulières on convertit chaque ligne en question, avec le premier champ comme bonne réponse et les 3 autres comme mauvaises réponses, et sans la réponse "Aucune de ces propositions". Ceci n'est qu'un exemple montrant comment obtenir 210 questions de QCM instantanément grâce à Prolog.
Autre application, cette fois pour générer des QCM avec des cases à cocher : on dispose de 8 affirmations vraies et 8 affirmations fausses. Les 8 affirmations vraies sont notées v1 à v8, et les 8 affirmations fausses sont notées f1 à f8. On désire obtenir tous les ensembles de 4 affirmations prises parmi les 16, et sans répétitions des groupes.
Appelons encore le prédicat solution :
?- solution(4, [v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8], X,_).
Il nous donne tous les groupes (plusieurs centaines ...) de 4 affirmations parmi les 16 et sans doublons :
X = [v2, v5, f3, f5] ;
X = [v2, v5, f3, f6] ;
X = [v2, v5, f3, f7] ;
X = [v2, v5, f3, f8] ;
X = [v2, v5, f4, f5] ;
X = [v2, v5, f4, f6] ;
X = [v2, v5, f4, f7] ;
X = [v2, v5, f4, f8] ;
X = [v2, v5, f5, f6] ;
X = [v2, v5, f5, f7] ;
X = [v2, v5, f5, f8] ;
X = [v2, v5, f6, f7] ;
X = [v2, v5, f6, f8] ;
X = [v2, v5, f7, f8] ;
X = [v2, v6, v7, v8] ;
X = [v2, v6, v7, f1] ;
X = [v2, v6, v7, f2] ;
X = [v2, v6, v7, f3] ;
X = [v2, v6, v7, f4] ;
X = [v2, v6, v7, f5] ;
X = [v2, v6, v7, f6] ;
X = [v2, v6, v7, f7] ;
X = [v2, v6, v7, f8] ;
X = [v2, v6, v8, f1] ;
X = [v2, v6, v8, f2] ;
X = [v2, v6, v8, f3] ;
X = [v2, v6, v8, f4] ;
X = [v2, v6, v8, f5] ;
X = [v2, v6, v8, f6] ;
X = [v2, v6, v8, f7] ;
X = [v2, v6, v8, f8] ;
X = [v2, v6, f1, f2] ;
X = [v2, v6, f1, f3] ;
X = [v2, v6, f1, f4] ;
X = [v2, v6, f1, f5] ;
X = [v2, v6, f1, f6] ;
X = [v2, v6, f1, f7] ;
X = [v2, v6, f1, f8] ;
X = [v2, v6, f2, f3] ;
X = [v2, v6, f2, f4] ;
X = [v2, v6, f2, f5] ;
X = [v2, v6, f2, f6] ;etc.
Mais s'agissant de cases à cocher, il reste à retrouver toutes les questions ne possédant que des affirmations fausses afin d'y rajouter la case à cocher [x] Aucune de ces propositions. Et ce n'est pas en modifiant le programme en Prolog que nous allons détecter ces questions particulières, mais tout simplement avec l'expression régulière suivante qui détecte toutes les lignes possédant 4 réponses fausses (4 fois fn sur la même ligne, où n est un nombre) :
((.*f\d{1}){4}.*)
Le groupe $1 représentant toute la ligne, il suffit de la remplacer par exemple par $1 : TOUT FAUX dans Dreamweaver pour "marquer" la ligne correspondante.
Ensuite, toujours en utilisant les expressions régulières, chaque affirmation est remplacée par son intitulé, pour les lignes marquées on ajoute la case à cocher [x] Aucune de ces propositions, et pour toutes les lignes non marquées on ajoute la case à cocher [ ] Aucune de ces propositions. On obtient ainsi, grâce à Prolog et aux expressions régulières, plusieurs centaines de questions de type cases à cocher où la question est de la forme "Cochez toutes les affirmations vraies parmi les 4 suivantes".
Voici une autre solution pour obtenir toutes les listes à P éléments à partir d'une liste de N éléments et sans répétitions. Cette solution simple définit un seul prédicat liste et n'utilise pas le prédicat append de SWI-Prolog :
liste(0,_,[]).
liste(N,[X|T],[X|L]):-N>0,N1 is N-1,liste(N1,T,L).
liste(N,[_|T],L):-N>0,liste(N,T,L).
Et voici le résultat dans SWI-Prolog :
?- liste(3,[a,b,c,d,e],X).
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;
Mais le nombre de combinaisons obtenues peut vite devenir très important. Voici un programme en Prolog qui donne le nombre de combinaisons de P éléments pris dans un ensemble de N éléments :
comb(_,0,1).
comb(N,P,R):-N>0,M is N-1,Q is P-1,comb(M,Q,S),R is N*S/P.
Combien existe-t-il de liste à 3 éléments pris dans une liste à 5 éléments ?
?- comb(5,3,X).
X = 10 .
Réponse : 10 listes. Il s'agit des 10 listes ci-dessus obtenues en appelant liste(3,[a,b,c,d,e],X).
Et si maintenant on appelle liste(4,[v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8],X). combien de listes à 4 éléments obtient-on à partir de la liste à 16 éléments ? Demandons à Prolog :
?- comb(16,4,X).
X = 1820 .
Réponse : 1820 listes. Et on arrive à un nouveau problème : comment récupérer ces 1820 listes dans un fichier texte sans appuyer 1820 fois sur le touche point-virgule du clavier ? La solution consiste à créer une liste contenant toutes les solutions puis à afficher cette liste. Pour créer une liste contenant toutes les solutions fournies par un prédicat il existe le prédicat prédéfini findall. Par exemple en appelant findall(X,liste(3,[a,b,c,d,e],X),L) on obtient une liste L contenant toutes les valeurs de X issues du prédicat liste :
Il reste à afficher la liste L avec 1 élément par ligne. Pour cela on ré-utilise le prédicat afficher_liste donné plus haut :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
Et dans SWI-Prolog on lance la ligne de commande suivante :
?- findall(X,liste(3,[a,b,c,d,e],X),L),afficher_liste(L).
Ce qui nous donne d'un coup l'ensemble des solutions avec une liste par ligne sans afficher X = et sans devoir appuyer sur la touche point-virgule pour faire défiler les solutions :
[a,b,c]
[a,b,d]
[a,b,e]
[a,c,d]
[a,c,e]
[a,d,e]
[b,c,d]
[b,c,e]
[b,d,e]
[c,d,e]
Et de la même manière ?- findall(X,liste(4,[v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8],X),L),afficher_liste(L). nous donne instantanément les 1820 listes attendues.
Enfin, pour récupérer le résultat dans un fichier texte il suffit de rediriger la sortie standard. Pour cela :
On prépare le fichier liste.pl suivant contenant le programme en Prolog (il se résume aux 2 prédicats liste et afficher_liste) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Prolog %
% Réalisé par Jean-Christophe MICHEL %
% Mars 2014 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
liste(0,_,[]).
liste(N,[X|T],[X|L]):-N>0,N1 is N-1,liste(N1,T,L).
liste(N,[_|T],L):-N>0,liste(N,T,L).
On prépare le fichier entree.txt suivant contenant les commandes à taper dans l'interpréteur :
findall(X,liste(8,[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p],X),L),afficher_liste(L).
halt.
Puis on lance la commande suivante sur la ligne de commande de Windows XP en redirigeant l'entrée et la sortie standard :
swipl liste.pl < entree.txt > sortie.txt
On obtient alors instantanément dans le fichier sortie.txt l'ensemble des listes demandées (12870 listes dans l'exemple ci-dessus : ensemble de 8 éléments pris dans un ensemble de 16 éléments). Même en cas de plusieurs milliers de listes générées, le résultat arrive instantanément dans le fichier sortie.txt (ce qui n'est pas le cas dans la fenêtre graphique de SWI-Prolog).
ATTENTION : lorsque l'entrée standard de swipl est redirigée depuis un fichier, alors la sortie standard de swipl n'est plus redirigée vers l'écran : elle doit être également redirigée vers un fichier. La commande swipl liste.pl < entree.txt ne peut donc pas être testée en attendant la sortie sur l'écran : dans ce cas rien ne se passe, rien n'est affiché à l'écran, et swipl ne rend pas la main au shell. Seul un Ctrl-C sort de cette situation qui donne l'impression de swipl ne fonctionne pas, ne comprend pas le programme, ou ne lit pas l'entrée standard.
En utilisation non interactive seule la commande swipl liste.pl < entree.txt > sortie.txt permet de voir la sortie standard (dans le fichier sortie.txt).
Afin de diversifier les combinaisons des listes générées, voici un autre programme qui attend en paramètre une liste de liste, et qui renvoie en sortie toutes les combinaisons de listes qu'il est possible de faire en prenant 1 élément dans chacune des listes de départ :
% Retourne les combinaisons une par une
combi([L|Q], [Elem|R]) :- member(Elem, L),combi(Q, R).
combi([], []).% Retourne la liste de toutes les combinaisons
combinaisons(Listes, Combis) :- findall(C, combi(Listes, C), Combis).
Exemple : en partant de 3 listes on génère toutes les listes possibles à 3 éléments en prenant 1 élément dans chaque liste :
?- combinaisons([[a,b], [c,d,e], [f]], L).
L = [[a, c, f], [a, d, f], [a, e, f], [b, c, f], [b, d, f], [b, e, f]]
Autre exemple : en partant de 4 listes on génère toutes les listes possibles à 4 éléments :
?- combinaisons([[a,b], [c,d,e], [f,g,h], [i,j]], L),afficher_liste(L).
On obtient les 36 listes à 4 éléments suivantes :
[a,c,f,i]
[a,c,f,j]
[a,c,g,i]
[a,c,g,j]
[a,c,h,i]
[a,c,h,j]
[a,d,f,i]
[a,d,f,j]
[a,d,g,i]
[a,d,g,j]
[a,d,h,i]
[a,d,h,j]
[a,e,f,i]
[a,e,f,j]
[a,e,g,i]
[a,e,g,j]
[a,e,h,i]
[a,e,h,j]
[b,c,f,i]
[b,c,f,j]
[b,c,g,i]
[b,c,g,j]
[b,c,h,i]
[b,c,h,j]
[b,d,f,i]
[b,d,f,j]
[b,d,g,i]
[b,d,g,j]
[b,d,h,i]
[b,d,h,j]
[b,e,f,i]
[b,e,f,j]
[b,e,g,i]
[b,e,g,j]
[b,e,h,i]
[b,e,h,j]
Autre exemple de combinaisons de liste en utilisant la coupure
Avec SWI-Prolog il existe un grand nombre de prédicats prédéfinis et bien pratiques pour manipuler les listes, comme par exemple sort qui trie une liste en supprimant les doublons ou encore list_to_set qui convertit une liste en ensemble, c'est-à-dire encore en supprimant les doublons.
Exemples :
1 ?- sort([b,d,c,a],L).
L = [a, b, c, d].2 ?- sort([[a,b],[c,d],[a,b]],L).
L = [[a, b], [c, d]].3 ?- list_to_set([a,b,c,a,d,c,b],L).
L = [a, b, c, d].
flatten(L1,L2) applanit et unifie une liste composée L1. L1 peut contenir de nombreuses listes imbriquées récursivement. flatten extrait tous les éléments contenus dans L1 et stoque le résultat dans une liste "plane" L2 (à une seule dimension). Exemple :
1 ?- flatten([[1,[2],3], [[4,5],[6,7]]], L).
L = [1, 2, 3, 4, 5, 6, 7].2 ?- flatten([[1], [2,3,4,5]], L).
L = [1, 2, 3, 4, 5].
Avec select(X,L1,L2), X prend pour valeur chaque éléments de la liste L1, et la liste L2 est égale à L1 privée de l'élément X. Exemple :
1 ?- select(X, [1,2,3,4], L).
X = 1,
L = [2, 3, 4] ;
X = 2,
L = [1, 3, 4] ;
X = 3,
L = [1, 2, 4] ;
X = 4,
L = [1, 2, 3] ;
Dans tous les cas on retiendra qu'il est facile en Prolog de générer automatiquement toute sorte de listes répondant à certains critères, en utilisant des prédicats prédéfinis ou en s'inspirant des exemples donnés ci-dessus, et ce sans forcément "penser en Prolog" ou maîtriser la totalité du langage. Enfin, plus que jamais, il est totalement inutile de ré-inventer la roue en ré-écrivant les prédicats prédéfinis dans SWI-Prolog et qui ne demande qu'à être utilisés ...
Mais Prolog n'est pas le seul langage permettant de générer des combinaisons de listes. Python est particulièrement adapté et performant dans la manipulation et la génération de listes complexes. Grâce au module itertools de Python, la génération des combinaisons d'une liste sans doublons s'écrit sous forme d'une simple boucle for :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Python %
% Réalisé par Jean-Christophe MICHEL %
% Novembre 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%import itertools
for x in itertools.combinations(['a', 'b', 'c','d','e'], 3):
print(list(x))
Et voici le résultat obtenu : Python nous génère instantanément toutes les listes à 3 éléments pris dans la liste à 5 éléments [a, b, c, d, e] et sans doublons :
['a', 'b', 'c']
['a', 'b', 'd']
['a', 'b', 'e']
['a', 'c', 'd']
['a', 'c', 'e']
['a', 'd', 'e']
['b', 'c', 'd']
['b', 'c', 'e']
['b', 'd', 'e']
['c', 'd', 'e']
Les grammaires de clauses définies (DCG en anglais pour Definite Clause Grammar) permettent de définir très simplement dans Prolog la structure d'une grammaire (composition d'une phrase, position des différentes catégories de mots, etc.) afin de demander à Prolog d'analyser une phrase et de déterminer si elle est grammaticalement correcte ou pas. De plus, une fois la grammaire définie, Prolog peut générer automatiquement toutes les tournures de phrases correctes répondant à cette grammaire.
Les DCG permettent entre autre de :
Sachant que Prolog utilise les listes pour stocker en interne les différents mots d'une phrase et pour rechercher, construire et analyser les phrases, les grammaires de clauses définies peuvent être également vue comme une syntaxe simplifiée permettant la génération automatique de listes répondant à un critère complexe bien précis.
Un premier exemple de DCG avec une phrase simple
On désire obtenir des phrases simples composées dans l'ordre d'un sujet, d'un verbe et d'un complément.
Le sujet (noté s), le verbe (noté v) et le complément (noté c) peuvent prendre chacun 4 valeurs différentes : il existe donc 4*4*4=64 phrases différentes.
Voici comment construire et demander ces phrases à Prolog en utilisant les DCG :
Dans un fichier on écrit la description de la grammaire comme ceci (p représente une phrase) en utilisant la syntaxe de Prolog permettant de définir facilement une grammaire de clauses (opérateur -->) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de base de DCG %
% Réalisé le 31 janvier 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% structure de la phrase
p-->s,v,c.% toutes les valeurs du sujet :
s-->[je].
s-->[marie].
s-->[vincent].
s-->[il].% toutes les valeurs du verbe :
v-->[mange].
v-->[chante].
v-->[travaille].
v-->[parle].% toutes les valeurs du complément :
c-->[doucement].
c-->[jamais].
c-->[bien].
c-->[parfois].
Utilisation de cette grammaire :
Aprés avoir ouvert le programme dans l'interpréteur Prolog (par la commande consult), posons lui quelques questions :
La phrase "marie mange doucement" est-elle grammaticalement correcte ?
?- p([marie,mange,doucement],[]).
true.
Réponse : oui (car elle respecte la structure définie par la grammaire)
La phrase "il travaille bien" est-elle grammaticalement correcte ?
?- p([il,travaille,bien],[]).
true.
Réponse : oui (car elle respecte la structure définie par la grammaire)
La phrase "parfois chante vincent" est-elle grammaticalement correcte ?
?- p([parfois,chante,vincent],[]).
false.
Réponse : non (car les mots ne sont pas dans l'ordre)
La phrase "elle parle bien" est-elle grammaticalement correcte ?
?- p([elle,parle,bien],[]).
false.
Réponse : non (car le sujet "elle" n'est pas définie dans la grammaire)
Mais comment Prolog a-t-il codé en interne la grammaire de clauses définies ? Pour cela on dispose du prédicat listing qui nous donne le détail des éléments p, s, v et c de la grammaire :
Demandons le listing de la phrase p :
?- listing(p).
p(A, D) :-
s(A, B),
v(B, C),
c(C, D).
true.
Remarque : p est un prédicat qui attend 2 listes en paramètre, soit un prédicat d'arité 2 : p/2
Demandons le listing du sujet s :
?- listing(s).
s([je|A], A).
s([marie|A], A).
s([vincent|A], A).
s([il|A], A).
true.
Quel est le listing du verbe v ?
?- listing(v).
v([mange|A], A).
v([chante|A], A).
v([travaille|A], A).
v([parle|A], A).
true.
Et voici le listing du complément c :
?- listing(c).
c([doucement|A], A).
c([jamais|A], A).
c([bien|A], A).
c([parfois|A], A).
true.
Nous remarquons qu'en interne Prolog utilise les listes pour traduire notre grammaire dans la syntaxe de base Prolog. Nous ne rentrons pas ici dans les détails du codage interne des grammaires de clauses définies (qui repose sur le principe des différences de listes). Remarquons simplement qu'en décrivant rapidement une grammaire sur quelques lignes en utilisant une syntaxe simplifiée (utilisant l'opérateur -->), Prolog l'a converti en interne en utilisant des listes, et qu'écrire l'équivalent d'une grammaire en syntaxe de base Prolog serait beaucoup plus complexe.
Nous ne garderons des DCG que la syntaxe simplifieé (utilisant l'opérateur -->) permettant rapidement de décrire une structure de données complexe (phrase, liste, etc.) afin de demander à Prolog de nous générer les différents cas correspondant.
Demandons à Prolog de nous sortir les 64 phrases correspondant à notre grammaire de base. Pour cela on passe en paramètre au prédicat p/2 une variable X et la liste vide [] :
?- p(X,[]).
X = [je, mange, doucement] ;
X = [je, mange, jamais] ;
X = [je, mange, bien] ;
X = [je, mange, parfois] ;
X = [je, chante, doucement] ;
X = [je, chante, jamais] ;
X = [je, chante, bien] ;
X = [je, chante, parfois] ;
X = [je, travaille, doucement] ;
X = [je, travaille, jamais] ;
X = [je, travaille, bien] ;
X = [je, travaille, parfois] ;
X = [je, parle, doucement] ;
X = [je, parle, jamais] ;
X = [je, parle, bien] ;
X = [je, parle, parfois] ;
X = [marie, mange, doucement] ;
X = [marie, mange, jamais] ;
etc.
Prolog nous ressort alors toutes les possibilités pour unifier la variable X en utilisant la grammaire définie, soit les 64 phrases correspondant à notre grammaire.
Demandons maintenant à Prolog de nous ressortir seulement les phrases correspondant à une certaine structure :
Quels sont les sujets et les compléments des phrases ayant comme verbe chante ?
?- p([X,chante,Y],[]).
Voici les réponses trouvées par Prolog, avec X comme sujet et Y comme complément :
X = je,
Y = doucement ;
X = je,
Y = jamais ;
X = je,
Y = bien ;
X = je,
Y = parfois ;
X = marie,
Y = doucement ;
X = marie,
Y = jamais ;
X = marie,
Y = bien ;
X = marie,
Y = parfois ;
X = vincent,
Y = doucement ;
X = vincent,
Y = jamais ;
X = vincent,
Y = bien ;
X = vincent,
Y = parfois ;
etc.
Demandons à Prolog de nous sortir tous les verbes des phrases ayant comme complément bien, et ce quelque soit le sujet (qu'on ne veut pas connaître) :
?- p([_,X,bien],[]).
Voici les premières réponses (les 4 verbes qui reviennent cycliquement) :
X = mange ;
X = chante ;
X = travaille ;
X = parle ;
X = mange ;
X = chante ;
X = travaille ;
X = parle ;
X = mange ;
etc.
Enfin, demandons à Prolog toutes les valeurs de X répondant au critère logique suivant :
X prend la valeur :
p([je,X,bien],[]);p([marie,travaille,X],[]).
Et voici la liste exhaustive des valeurs de X trouvées par Prolog (il s'agit sans surprise des 4 verbes et des 4 compléments) :
X = mange ;
X = chante ;
X = travaille ;
X = parle ;
X = doucement ;
X = jamais ;
X = bien ;
X = parfois ;
Ce premier exemple a permis de montrer la syntaxe d'une DCG dans Prolog et les requêtes l'utilisant, mais notre grammaire est tellement simple que Prolog n'est pas vraiment justifier dans un pareil cas. En effet, pour analyser si une phrase correspond ou pas à une simple structure sujet, verbe, compléméent où chacun des 3 éléments ne prends que 4 valeurs, une simple expression régulière suffit. De plus, pour générer systématiquement tous les cas possibles d'une grammaire simple un langage impératif (Python, Perl, Ruby, etc.) avec 3 boucles FOR imbriquées aurait donné le même résultat (sans devoir apprendre une nouvelle syntaxe).
Les DCG en Prolog sont donc réservées aux cas plus complexes afin de laisser à Prolog le travail de trie ou de recherche des seules combinaisons utiles et impossibles à programmer simplement dans un langage impératif.
Un deuxième exemple de DCG avec une phrase composée
Nous allons cette fois décrire dans une grammaire la structure d'une phrase composée, contenant des éléments eux-même variables.
Une phrase simple est toujours composée d'un sujet, d'un verbe et d'un complément. Mais cette fois, le sujet est soit composé d'un simple pronom (je, il, elle), soit composé d'un simple prénom (vincent, marie, alexis), soit composé d'un animal (le chat, un chien, le lapin), et un animal est lui-même composé d'un article (un, le, ce) et d'un nom (chat, chien, lapin).
Enfin, une phrase composée est la concaténation de deux phrases simples séparées par une conjonction (et, ou, car, mais).
Rien qu'en lisant cette description on comprend bien que le nombre de combinaisons possibles va très vite augmenter, et que la génération de l'ensemble des phrases possibles serait très complexe à programmer dans un langage impératif.
Avant de donner le programme source décrivant cette grammaire en Prolog, définissons clairement le nom des prédicats utilisés ainsi qu'un ensemble fini de valeurs pour certains d'entres eux :
Vue la description de la grammaire et la liste des valeurs utilisées, la construction de toutes les phrases possibles est plus complexe que dans le premier exemple et justifie cette fois l'emploi de Prolog et de la syntaxe simplifiée des DCG.
Voici le prgramme en Prolog décrivant cette grammaire :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG pour générer des phrases composées %
% Réalisé le 31 janvier 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% structure d'une phrase simple
ph_simple-->sujet,verbe,complement.% structure d'une phrase composée
ph_compo-->ph_simple.
ph_compo-->ph_simple,conjonction,ph_simple.% strucure du sujet :
sujet-->pronom.
sujet-->prenom.
sujet-->animal.% structure d'un animal :
animal-->article,nom.% toutes les valeurs de l'article :
article-->[le].
article-->[un].
article-->[ce].% toutes les valeurs du nom d'un animal :
nom-->[chat].
nom-->[chien].
nom-->[lapin].% toutes les valeurs d'un pronom :
pronom-->[je].
pronom-->[il].
pronom-->[elle].% toutes les valeurs d'un prénom :
prenom-->[vincent].
prenom-->[marie].
prenom-->[alexis].% toutes les valeurs du verbe :
verbe-->[marche].
verbe-->[chante].
verbe-->[travaille].% toutes les valeurs du complément :
complement-->[vite].
complement-->[bien].
complement-->[parfois].% toutes les valeurs de la conjonction :
conjonction-->[et].
conjonction-->[ou].
conjonction-->[car].
conjonction-->[mais].
Demandons à Prolog toutes les phrases composées possibles (il y en a plusieurs milliers en tout) :
ph_compo(X,[]).
Et voici un extrait des réponses données par Prolog :
X = [je, marche, vite, et, ce, lapin, chante, bien] ;
X = [je, marche, vite, et, ce, lapin, chante, parfois] ;
X = [je, marche, vite, et, ce, lapin, travaille, vite] ;
X = [je, marche, vite, et, ce, lapin, travaille, bien] ;
X = [je, marche, vite, et, ce, lapin, travaille, parfois] ;
X = [je, marche, vite, ou, je, marche, vite] ;
X = [je, marche, vite, ou, je, marche, bien] ;
X = [je, marche, vite, ou, je, marche, parfois] ;
X = [je, marche, vite, ou, je, chante, vite] ;
X = [je, marche, vite, ou, je, chante, bien] ;
X = [je, marche, vite, ou, je, chante, parfois] ;
X = [je, marche, vite, ou, je, travaille, vite] ;
etc.
On peut également demander à Prolog seulement des phrases simples :
?- ph_simple(X,[]).
Voici quelques résultats :
X = [elle, chante, vite] ;
X = [elle, chante, bien] ;
X = [elle, chante, parfois] ;
X = [elle, travaille, vite] ;
X = [elle, travaille, bien] ;
X = [elle, travaille, parfois] ;
X = [vincent, marche, vite] ;
X = [vincent, marche, bien] ;
etc.
Enfin, si dans le programme on remplace ph_compo-->ph_simple,conjonction,ph_simple. par ph_compo-->ph_simple,conjonction,ph_compo. afin de définir récursivement une phrase composée comme étant la concaténation d'une phrase simple et d'une phrase composée séparées par une conjonction on obtient alors des phrases à ralonge : le nombre de combinaisons possibles devient alors infini et les phrases s'alongent à l'infini :
X = [je, marche, vite, et, ce, lapin, marche, parfois] ;
X = [je, marche, vite, et, ce, lapin, chante, vite] ;
X = [je, marche, vite, et, ce, lapin, chante, bien] ;
X = [je, marche, vite, et, ce, lapin, chante, parfois] ;
X = [je, marche, vite, et, ce, lapin, travaille, vite] ;
X = [je, marche, vite, et, ce, lapin, travaille, bien] ;
X = [je, marche, vite, et, ce, lapin, travaille, parfois] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, je|...] ;
X = [je, marche, vite, et, je, marche, vite, et, il|...] ;
X = [je, marche, vite, et, je, marche, vite, et, il|...] ;
X = [je, marche, vite, et, je, marche, vite, et, il|...] ;
X = [je, marche, vite, et, je, marche, vite, et, il|...] ;
X = [je, marche, vite, et, je, marche, vite, et, il|...] ;
etc.
Pour obtenir d'un seul coup l'ensemble des listes générées sans appuyer plusieurs fois sur la touche point-virgule il faut :
1 - ajouter la ligne afficher_liste([X|L]) :- writeln(X), afficher_liste(L). permettant d'afficher une liste dans le fichier source décrivant la DCG et recharger le fichier dans SWI-Prolog
2 - lancer la commande suivante dans SWI-Prolog : findall(X,ph_simple(X,[]),L),afficher_liste(L).
Rappel : le prédicat findall récupère dans la liste L toutes les valeurs de X retournées par le prédicat passé en deuxième paramètre (ici le prédicat ph_simple/2), ce qui correspond à l'ensemble des valeurs de X qu'on aurait obtenues en appuyant plusieurs fois sur la touche point-virgule.
On obtient alors instantanément l'ensemble des listes générées (ici toutes les phrases simples) dans la fenêtre de SWI-Prolog :
[je,marche,vite]
[je,marche,bien]
[je,marche,parfois]
[je,chante,vite]
[je,chante,bien]
[je,chante,parfois]
[je,travaille,vite]
[je,travaille,bien]
[je,travaille,parfois]
[il,marche,vite]
[il,marche,bien]
[il,marche,parfois]
[il,chante,vite]
[il,chante,bien]
[il,chante,parfois]
[il,travaille,vite]
[il,travaille,bien]
[il,travaille,parfois]
[elle,marche,vite]
[elle,marche,bien]
[elle,marche,parfois]
[elle,chante,vite]
[elle,chante,bien]
[elle,chante,parfois]
[elle,travaille,vite]
[elle,travaille,bien]
[elle,travaille,parfois]
[vincent,marche,vite]
[vincent,marche,bien]
[vincent,marche,parfois]
[vincent,chante,vite]
[vincent,chante,bien]
[vincent,chante,parfois]
[vincent,travaille,vite]
[vincent,travaille,bien]
[vincent,travaille,parfois]
[marie,marche,vite]
[marie,marche,bien]
[marie,marche,parfois]
[marie,chante,vite]
[marie,chante,bien]
[marie,chante,parfois]
[marie,travaille,vite]
[marie,travaille,bien]
[marie,travaille,parfois]
[alexis,marche,vite]
[alexis,marche,bien]
[alexis,marche,parfois]
[alexis,chante,vite]
[alexis,chante,bien]
[alexis,chante,parfois]
[alexis,travaille,vite]
[alexis,travaille,bien]
[alexis,travaille,parfois]
[le,chat,marche,vite]
[le,chat,marche,bien]
[le,chat,marche,parfois]
[le,chat,chante,vite]
[le,chat,chante,bien]
[le,chat,chante,parfois]
[le,chat,travaille,vite]
[le,chat,travaille,bien]
[le,chat,travaille,parfois]
[le,chien,marche,vite]
[le,chien,marche,bien]
[le,chien,marche,parfois]
[le,chien,chante,vite]
[le,chien,chante,bien]
[le,chien,chante,parfois]
[le,chien,travaille,vite]
[le,chien,travaille,bien]
[le,chien,travaille,parfois]
[le,lapin,marche,vite]
[le,lapin,marche,bien]
[le,lapin,marche,parfois]
[le,lapin,chante,vite]
[le,lapin,chante,bien]
[le,lapin,chante,parfois]
[le,lapin,travaille,vite]
[le,lapin,travaille,bien]
[le,lapin,travaille,parfois]
[un,chat,marche,vite]
[un,chat,marche,bien]
[un,chat,marche,parfois]
[un,chat,chante,vite]
[un,chat,chante,bien]
[un,chat,chante,parfois]
[un,chat,travaille,vite]
[un,chat,travaille,bien]
[un,chat,travaille,parfois]
[un,chien,marche,vite]
[un,chien,marche,bien]
[un,chien,marche,parfois]
[un,chien,chante,vite]
[un,chien,chante,bien]
[un,chien,chante,parfois]
[un,chien,travaille,vite]
[un,chien,travaille,bien]
[un,chien,travaille,parfois]
[un,lapin,marche,vite]
[un,lapin,marche,bien]
[un,lapin,marche,parfois]
[un,lapin,chante,vite]
[un,lapin,chante,bien]
[un,lapin,chante,parfois]
[un,lapin,travaille,vite]
[un,lapin,travaille,bien]
[un,lapin,travaille,parfois]
[ce,chat,marche,vite]
[ce,chat,marche,bien]
[ce,chat,marche,parfois]
[ce,chat,chante,vite]
[ce,chat,chante,bien]
[ce,chat,chante,parfois]
[ce,chat,travaille,vite]
[ce,chat,travaille,bien]
[ce,chat,travaille,parfois]
[ce,chien,marche,vite]
[ce,chien,marche,bien]
[ce,chien,marche,parfois]
[ce,chien,chante,vite]
[ce,chien,chante,bien]
[ce,chien,chante,parfois]
[ce,chien,travaille,vite]
[ce,chien,travaille,bien]
[ce,chien,travaille,parfois]
[ce,lapin,marche,vite]
[ce,lapin,marche,bien]
[ce,lapin,marche,parfois]
[ce,lapin,chante,vite]
[ce,lapin,chante,bien]
[ce,lapin,chante,parfois]
[ce,lapin,travaille,vite]
[ce,lapin,travaille,bien]
[ce,lapin,travaille,parfois]
Si on lance findall(X,ph_compo(X,[]),L),afficher_liste(L). avec une définition non récurcive des phrases composée (ph_compo-->ph_simple,conjonction,ph_simple.) on obtient plusieurs centaines de phrases composées correspondant à la grammaire définie. En voici certaines :
[marie,travaille,parfois,et,ce,chien,marche,vite]
[marie,travaille,parfois,et,ce,chien,marche,bien]
[marie,travaille,parfois,et,ce,chien,marche,parfois]
[marie,travaille,parfois,et,ce,chien,chante,vite]
[marie,travaille,parfois,et,ce,chien,chante,bien]
[marie,travaille,parfois,et,ce,chien,chante,parfois]
[marie,travaille,parfois,et,ce,chien,travaille,vite]
[marie,travaille,parfois,et,ce,chien,travaille,bien]
[marie,travaille,parfois,et,ce,chien,travaille,parfois]
[marie,travaille,parfois,et,ce,lapin,marche,vite]
[marie,travaille,parfois,et,ce,lapin,marche,bien]
[marie,travaille,parfois,et,ce,lapin,marche,parfois]
[marie,travaille,parfois,et,ce,lapin,chante,vite]
[marie,travaille,parfois,et,ce,lapin,chante,bien]
[marie,travaille,parfois,et,ce,lapin,chante,parfois]
[marie,travaille,parfois,et,ce,lapin,travaille,vite]
[marie,travaille,parfois,et,ce,lapin,travaille,bien]
[marie,travaille,parfois,et,ce,lapin,travaille,parfois]
[marie,travaille,parfois,ou,je,marche,vite]
[marie,travaille,parfois,ou,je,marche,bien]
[marie,travaille,parfois,ou,je,marche,parfois]
[marie,travaille,parfois,ou,je,chante,vite]
[marie,travaille,parfois,ou,je,chante,bien]
[marie,travaille,parfois,ou,je,chante,parfois]
[marie,travaille,parfois,ou,je,travaille,vite]
[marie,travaille,parfois,ou,je,travaille,bien]
[marie,travaille,parfois,ou,je,travaille,parfois]
[marie,travaille,parfois,ou,il,marche,vite]
[marie,travaille,parfois,ou,il,marche,bien]
[marie,travaille,parfois,ou,il,marche,parfois]
[marie,travaille,parfois,ou,il,chante,vite]
[marie,travaille,parfois,ou,il,chante,bien]
[marie,travaille,parfois,ou,il,chante,parfois]
[marie,travaille,parfois,ou,il,travaille,vite]
[marie,travaille,parfois,ou,il,travaille,bien]
[marie,travaille,parfois,ou,il,travaille,parfois]
[marie,travaille,parfois,ou,elle,marche,vite]
[marie,travaille,parfois,ou,elle,marche,bien]
etc.
Enfin, si on lance findall(X,ph_compo(X,[]),L),afficher_liste(L). avec une définition récurcive des phrases composées (ph_compo-->ph_simple,conjonction,ph_compo.), SWI-Prolog renvoie une erreur et ne sort aucune phrase car leur nombre est infini.
Récupérons maintenant l'ensemble des listes générées dans un fichier texte sortie.txt, en utilisant swipl en mode non interactif dans un shell Windows.
RAPPEL : lorsque l'entrée standard de swipl est redirigée depuis un fichier, alors la sortie standard de swipl n'est plus redirigée vers l'écran : elle doit être également redirigée vers un fichier. La commande swipl liste.pl < entree.txt ne peut donc pas être testée en attendant la sortie sur l'écran. En utilisation non interactive seule la commande swipl liste.pl < entree.txt > sortie.txt permet de voir la sortie standard (dans le fichier sortie.txt).
Pour obtenir d'un seul coup l'ensemble des listes générées dans un fichier texte sortie.txt il faut :
1 - préparer le fichier texte entree.txt contenant les commandes à taper dans l'interpréteur swipl :
findall(X,ph_simple(X,[]),L),afficher_liste(L).
halt.2 - lancer la commande suivante dans un shell Windows (le fichier dcg.pl contenant le prédicat afficher_liste sur une ligne en plus de la description de la grammaire de clauses) : swipl dcg.pl < entree.txt > sortie.txt
Voici le fichier sortie.txt obtenu instantanément et contenant les 135 phrases simples :
[je,marche,vite]
[je,marche,bien]
[je,marche,parfois]
[je,chante,vite]
[je,chante,bien]
[je,chante,parfois]
[je,travaille,vite]
[je,travaille,bien]
[je,travaille,parfois]
[il,marche,vite]
[il,marche,bien]
[il,marche,parfois]
[il,chante,vite]
[il,chante,bien]
[il,chante,parfois]
[il,travaille,vite]
[il,travaille,bien]
[il,travaille,parfois]
[elle,marche,vite]
[elle,marche,bien]
[elle,marche,parfois]
[elle,chante,vite]
[elle,chante,bien]
[elle,chante,parfois]
[elle,travaille,vite]
[elle,travaille,bien]
[elle,travaille,parfois]
[vincent,marche,vite]
[vincent,marche,bien]
[vincent,marche,parfois]
[vincent,chante,vite]
[vincent,chante,bien]
[vincent,chante,parfois]
[vincent,travaille,vite]
[vincent,travaille,bien]
[vincent,travaille,parfois]
[marie,marche,vite]
[marie,marche,bien]
[marie,marche,parfois]
[marie,chante,vite]
[marie,chante,bien]
[marie,chante,parfois]
[marie,travaille,vite]
[marie,travaille,bien]
[marie,travaille,parfois]
[alexis,marche,vite]
[alexis,marche,bien]
[alexis,marche,parfois]
[alexis,chante,vite]
[alexis,chante,bien]
[alexis,chante,parfois]
[alexis,travaille,vite]
[alexis,travaille,bien]
[alexis,travaille,parfois]
[le,chat,marche,vite]
[le,chat,marche,bien]
[le,chat,marche,parfois]
[le,chat,chante,vite]
[le,chat,chante,bien]
[le,chat,chante,parfois]
[le,chat,travaille,vite]
[le,chat,travaille,bien]
[le,chat,travaille,parfois]
[le,chien,marche,vite]
[le,chien,marche,bien]
[le,chien,marche,parfois]
[le,chien,chante,vite]
[le,chien,chante,bien]
[le,chien,chante,parfois]
[le,chien,travaille,vite]
[le,chien,travaille,bien]
[le,chien,travaille,parfois]
[le,lapin,marche,vite]
[le,lapin,marche,bien]
[le,lapin,marche,parfois]
[le,lapin,chante,vite]
[le,lapin,chante,bien]
[le,lapin,chante,parfois]
[le,lapin,travaille,vite]
[le,lapin,travaille,bien]
[le,lapin,travaille,parfois]
[un,chat,marche,vite]
[un,chat,marche,bien]
[un,chat,marche,parfois]
[un,chat,chante,vite]
[un,chat,chante,bien]
[un,chat,chante,parfois]
[un,chat,travaille,vite]
[un,chat,travaille,bien]
[un,chat,travaille,parfois]
[un,chien,marche,vite]
[un,chien,marche,bien]
[un,chien,marche,parfois]
[un,chien,chante,vite]
[un,chien,chante,bien]
[un,chien,chante,parfois]
[un,chien,travaille,vite]
[un,chien,travaille,bien]
[un,chien,travaille,parfois]
[un,lapin,marche,vite]
[un,lapin,marche,bien]
[un,lapin,marche,parfois]
[un,lapin,chante,vite]
[un,lapin,chante,bien]
[un,lapin,chante,parfois]
[un,lapin,travaille,vite]
[un,lapin,travaille,bien]
[un,lapin,travaille,parfois]
[ce,chat,marche,vite]
[ce,chat,marche,bien]
[ce,chat,marche,parfois]
[ce,chat,chante,vite]
[ce,chat,chante,bien]
[ce,chat,chante,parfois]
[ce,chat,travaille,vite]
[ce,chat,travaille,bien]
[ce,chat,travaille,parfois]
[ce,chien,marche,vite]
[ce,chien,marche,bien]
[ce,chien,marche,parfois]
[ce,chien,chante,vite]
[ce,chien,chante,bien]
[ce,chien,chante,parfois]
[ce,chien,travaille,vite]
[ce,chien,travaille,bien]
[ce,chien,travaille,parfois]
[ce,lapin,marche,vite]
[ce,lapin,marche,bien]
[ce,lapin,marche,parfois]
[ce,lapin,chante,vite]
[ce,lapin,chante,bien]
[ce,lapin,chante,parfois]
[ce,lapin,travaille,vite]
[ce,lapin,travaille,bien]
[ce,lapin,travaille,parfois]
Pour obtenir toutes les phrases composées il suffit de remplacer findall(X,ph_simple(X,[]),L),afficher_liste(L). par findall(X,ph_compo(X,[]),L),afficher_liste(L). dans le fichier entree.txt puis de relancer la commande swipl dcg.pl < entree.txt > sortie.txt dans le shell Windows.
On obtient alors instantanément dans le fichier sortie.txt les 73 035 phrases composées. En voici quelques-unes :
[ce,chien,travaille,bien,car,ce,chat,marche,bien]
[ce,chien,travaille,bien,car,ce,chat,marche,parfois]
[ce,chien,travaille,bien,car,ce,chat,chante,vite]
[ce,chien,travaille,bien,car,ce,chat,chante,bien]
[ce,chien,travaille,bien,car,ce,chat,chante,parfois]
[ce,chien,travaille,bien,car,ce,chat,travaille,vite]
[ce,chien,travaille,bien,car,ce,chat,travaille,bien]
[ce,chien,travaille,bien,car,ce,chat,travaille,parfois]
[ce,chien,travaille,bien,car,ce,chien,marche,vite]
[ce,chien,travaille,bien,car,ce,chien,marche,bien]
[ce,chien,travaille,bien,car,ce,chien,marche,parfois]
[ce,chien,travaille,bien,car,ce,chien,chante,vite]
[ce,chien,travaille,bien,car,ce,chien,chante,bien]
[ce,chien,travaille,bien,car,ce,chien,chante,parfois]
[ce,chien,travaille,bien,car,ce,chien,travaille,vite]
[ce,chien,travaille,bien,car,ce,chien,travaille,bien]
[ce,chien,travaille,bien,car,ce,chien,travaille,parfois]
[ce,chien,travaille,bien,car,ce,lapin,marche,vite]
[ce,chien,travaille,bien,car,ce,lapin,marche,bien]
[ce,chien,travaille,bien,car,ce,lapin,marche,parfois]
[ce,chien,travaille,bien,car,ce,lapin,chante,vite]
[ce,chien,travaille,bien,car,ce,lapin,chante,bien]
[ce,chien,travaille,bien,car,ce,lapin,chante,parfois]
[ce,chien,travaille,bien,car,ce,lapin,travaille,vite]
[ce,chien,travaille,bien,car,ce,lapin,travaille,bien]
[ce,chien,travaille,bien,car,ce,lapin,travaille,parfois]
[ce,chien,travaille,bien,mais,je,marche,vite]
[ce,chien,travaille,bien,mais,je,marche,bien]
[ce,chien,travaille,bien,mais,je,marche,parfois]
[ce,chien,travaille,bien,mais,je,chante,vite]
[ce,chien,travaille,bien,mais,je,chante,bien]
[ce,chien,travaille,bien,mais,je,chante,parfois]
[ce,chien,travaille,bien,mais,je,travaille,vite]
[ce,chien,travaille,bien,mais,je,travaille,bien]
[ce,chien,travaille,bien,mais,je,travaille,parfois]
[ce,chien,travaille,bien,mais,il,marche,vite]
[ce,chien,travaille,bien,mais,il,marche,bien]
[ce,chien,travaille,bien,mais,il,marche,parfois]
[ce,chien,travaille,bien,mais,il,chante,vite]
[ce,chien,travaille,bien,mais,il,chante,bien]
[ce,chien,travaille,bien,mais,il,chante,parfois]
[ce,chien,travaille,bien,mais,il,travaille,vite]
[ce,chien,travaille,bien,mais,il,travaille,bien]
[ce,chien,travaille,bien,mais,il,travaille,parfois]
[ce,chien,travaille,bien,mais,elle,marche,vite]
[ce,chien,travaille,bien,mais,elle,marche,bien]
[ce,chien,travaille,bien,mais,elle,marche,parfois]
[ce,chien,travaille,bien,mais,elle,chante,vite]
[ce,chien,travaille,bien,mais,elle,chante,bien]
[ce,chien,travaille,bien,mais,elle,chante,parfois]
[ce,chien,travaille,bien,mais,elle,travaille,vite]
[ce,chien,travaille,bien,mais,elle,travaille,bien]
[ce,chien,travaille,bien,mais,elle,travaille,parfois]
[ce,chien,travaille,bien,mais,vincent,marche,vite]
[ce,chien,travaille,bien,mais,vincent,marche,bien]
[ce,chien,travaille,bien,mais,vincent,marche,parfois]
etc.
Et enfin voici d'autres phrases composées prises parmi les 73035 phrases générées, mais après mise en forme (remplacement de la virgule par un espace et suppression des crochets ouvrant et fermant) :
alexis travaille parfois mais ce chat travaille bien
alexis travaille parfois mais ce chat travaille parfois
alexis travaille parfois mais ce chien marche vite
alexis travaille parfois mais ce chien marche bien
alexis travaille parfois mais ce chien marche parfois
alexis travaille parfois mais ce chien chante vite
alexis travaille parfois mais ce chien chante bien
alexis travaille parfois mais ce chien chante parfois
alexis travaille parfois mais ce chien travaille vite
alexis travaille parfois mais ce chien travaille bien
alexis travaille parfois mais ce chien travaille parfois
alexis travaille parfois mais ce lapin marche vite
alexis travaille parfois mais ce lapin marche bien
alexis travaille parfois mais ce lapin marche parfois
alexis travaille parfois mais ce lapin chante vite
alexis travaille parfois mais ce lapin chante bien
alexis travaille parfois mais ce lapin chante parfois
alexis travaille parfois mais ce lapin travaille vite
alexis travaille parfois mais ce lapin travaille bien
alexis travaille parfois mais ce lapin travaille parfois
le chat marche vite et je marche vite
le chat marche vite et je marche bien
le chat marche vite et je marche parfois
le chat marche vite et je chante vite
le chat marche vite et je chante bien
le chat marche vite et je chante parfois
le chat marche vite et je travaille vite
le chat marche vite et je travaille bien
le chat marche vite et je travaille parfois
le chat marche vite et il marche vite
le chat marche vite et il marche bien
le chat marche vite et il marche parfois
le chat marche vite et il chante vite
le chat marche vite et il chante bien
Cette introduction à l'utilisation des grammaires de clauses définies a montré comment obtenir instantanément 73035 listes à partir d'un programme source de 30 lignes décrivant la grammaire, et constitue désormais une nouvelle technique pour la génération automatique de listes complexes ou volumineuses. Mais le véritable intérêt des grammaires de clauses en Prolog va apparaître avec l'utilisation des paramètres comme illustré dans l'exemple suivant.
Un troisième exemple de DCG en utilisant des paramètres
Nous partons du programme de base suivant dans lequel le prédicat afficher_phrase/1 affiche une phrase mise en forme (mots séparés par un espace et point en fin de phrase) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG utilisant des paramètres %
% Réalisé le 01 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%afficher_phrase([]) :- writeln('.').
afficher_phrase([X|L]) :- write(' '), write(X), afficher_phrase(L).
afficher_liste([X|L]) :- afficher_phrase(X), afficher_liste(L).% structure de la phrase
p-->a,s,v.% toutes les valeurs de l'article :
a-->['Le'].
a-->['Un'].
a-->['La'].
a-->['Une'].% toutes les valeurs du sujet :
s-->[chat].
s-->[chien].
s-->[chouette].
s-->[tourterelle].% toutes les valeurs du verbe :
v-->[miaule].
v-->[aboie].
v-->[hulule].
v-->[roucoule].
Remarque : afin que les phrases générées commencent par une majuscule, la première lettre des articles a été écrite en majuscule dans la définition de la grammaire. Mais comme un élément commençant par une majuscule est considéré comme une variable pour Prolog, et non comme un atome (une constante alphanumérique), les articles ont été écrits entre simples quotes.
A retenir : pour utiliser des atomes commençant par une majuscule il faut les placer entre simples quotes. Exemples : 'Vincent', ou prenom-->['Marie']., etc.
Si on demande toutes les phrases possibles avec la commande findall(X,p(X,[]),L),afficher_liste(L). (le prédicat afficher_liste/1 appelant le prédicat afficher_phrase/1 afin que les phrases soient mises en forme directement sur la sortie standard sans traitement suplémentaire) on obtient les 64 phrases suivantes : trouvez l'erreur ??
Le chat miaule.
Le chat aboie.
Le chat hulule.
Le chat roucoule.
Le chien miaule.
Le chien aboie.
Le chien hulule.
Le chien roucoule.
Le chouette miaule.
Le chouette aboie.
Le chouette hulule.
Le chouette roucoule.
Le tourterelle miaule.
Le tourterelle aboie.
Le tourterelle hulule.
Le tourterelle roucoule.
Un chat miaule.
Un chat aboie.
Un chat hulule.
Un chat roucoule.
Un chien miaule.
Un chien aboie.
Un chien hulule.
Un chien roucoule.
Un chouette miaule.
Un chouette aboie.
Un chouette hulule.
Un chouette roucoule.
Un tourterelle miaule.
Un tourterelle aboie.
Un tourterelle hulule.
Un tourterelle roucoule.
La chat miaule.
La chat aboie.
La chat hulule.
La chat roucoule.
La chien miaule.
La chien aboie.
La chien hulule.
La chien roucoule.
La chouette miaule.
La chouette aboie.
La chouette hulule.
La chouette roucoule.
La tourterelle miaule.
La tourterelle aboie.
La tourterelle hulule.
La tourterelle roucoule.
Une chat miaule.
Une chat aboie.
Une chat hulule.
Une chat roucoule.
Une chien miaule.
Une chien aboie.
Une chien hulule.
Une chien roucoule.
Une chouette miaule.
Une chouette aboie.
Une chouette hulule.
Une chouette roucoule.
Une tourterelle miaule.
Une tourterelle aboie.
Une tourterelle hulule.
Une tourterelle roucoule.
Sauf si votre chat hulule ou si vous connaissez un chien qui roucoule, vous devez avoir constaté que la plupart de ces phrases sont fausses (exemple : Un chat hulule) ou mal construite (exemple : Une chien aboie). En fait cette fois chaque sujet (ici un nom d'animal) doit être associé à un verbe précis (et pas aux 3 autres), et en plus parmi les 4 animaux deux sont masculins et doivent être associés aux articles Le ou Un, et deux sont féminins et doivent être associés aux articles La ou Une.
Question : parmi les 64 phrases ci-dessus combien sont justes et bien construites ?
Réponse : seulement 8.
Le tableau suivant récapitule les seules associations possibles avec les mots de cette grammaire, ce qui fait seulement 8 phrases valables au final et non 64 comme l'a donné la totalité des combinaisons possibles :
| |
||
le ou un |
||
Mais comment préciser à Prolog ces seules associations autorisées ? La réponse se trouve dans l'utilisation des paramètres lors de l'écriture de la grammaire.
Commençons par mettre un paramètre à l'article et au sujet. Ce paramètre vaudra soit masculin soit feminin, et dans la structure de la phrase on précise que le paramètre doit être le même pour l'article et pour le sujet (variable X) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG utilisant des paramètres %
% Réalisé le 01 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% structure de la phrase avec un paramètre imposant que l'article et le sujet soient accordés
p-->a(X),s(X),v.% toutes les valeurs de l'article avec un paramètre :
a(masculin)-->['Le'].
a(masculin)-->['Un'].
a(feminin)-->['La'].
a(feminin)-->['Une'].% toutes les valeurs du sujet avec un paramètre :
s(masculin)-->[chat].
s(masculin)-->[chien].
s(feminin)-->[chouette].
s(feminin)-->[tourterelle].% toutes les valeurs du verbe :
v-->[miaule].
v-->[aboie].
v-->[hulule].
v-->[roucoule].
Si on demande de générer toutes les phrases correspondant à cette grammaire on obtient les 32 phrases suivantes (les problèmes de genre on été corrigés) :
Le chat miaule.
Le chat aboie.
Le chat hulule.
Le chat roucoule.
Le chien miaule.
Le chien aboie.
Le chien hulule.
Le chien roucoule.
Un chat miaule.
Un chat aboie.
Un chat hulule.
Un chat roucoule.
Un chien miaule.
Un chien aboie.
Un chien hulule.
Un chien roucoule.
La chouette miaule.
La chouette aboie.
La chouette hulule.
La chouette roucoule.
La tourterelle miaule.
La tourterelle aboie.
La tourterelle hulule.
La tourterelle roucoule.
Une chouette miaule.
Une chouette aboie.
Une chouette hulule.
Une chouette roucoule.
Une tourterelle miaule.
Une tourterelle aboie.
Une tourterelle hulule.
Une tourterelle roucoule.
Il reste à associer chaque verbe à un seul animal, et là encore ce sont les paramètres qui vont obliger Prolog à effectuer ces associations lors de l'unification. On ajoute un second paramètre à s et un paramètre à v en demandant qu'ils soient identiques dans la structure de la phrase (variable Y) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG utilisant des paramètres %
% Réalisé le 01 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% structure de la phrase avec des paramètres accordant article/sujet et sujet/verbe
p-->a(X),s(X,Y),v(Y).% toutes les valeurs de l'article avec un paramètre pour le lier au sujet :
a(masculin)-->['Le'].
a(masculin)-->['Un'].
a(feminin)-->['La'].
a(feminin)-->['Une'].% toutes les valeurs du sujet avec deux paramètres :
s(masculin,chat)-->[chat].
s(masculin,chien)-->[chien].
s(feminin,chouette)-->[chouette].
s(feminin,tourterelle)-->[tourterelle].% toutes les valeurs du verbe avec un paramètre pour le lier au sujet :
v(chat)-->[miaule].
v(chien)-->[aboie].
v(chouette)-->[hulule].
v(tourterelle)-->[roucoule].
Et voici les seules phrases obtenues, il s'agit bien des 8 phrases justes parmi les 64 phrases générées avec le premier programme :
Le chat miaule.
Le chien aboie.
Un chat miaule.
Un chien aboie.
La chouette hulule.
La tourterelle roucoule.
Une chouette hulule.
Une tourterelle roucoule.
Jusqu'ici les paramètres utilisés dans la définition de la grammaire étaient constants (masculin,feminin,chat,etc.). L'exemple suivant montre une grammaire où les paramètres sont désormais des variables, ce qui ouvre de nouvelles possibilités pour la génération de phrases paramétriques.
Un quatrième exemple de DCG en utilisant des paramètres variables
On veut générer ici des phrases simples composées d'un sujet et d'un verbe, mais qui doivent être accordés en genre (masculin et féminin) et en nombre (singulier et pluriel).
Nous partons du programme suivant où la grammaire est définie en utilisant 3 variables Type, Genre et Nombre aussi bien pour le sujet que pour le verbe. Un ensemble de faits appelés lexique permet de trouver un mot correspondant à ces 3 paramètres (Type, Genre et Nombre).
De plus dans ce programme un nouveau prédicat generer a été défini afin d'appeler directement la commande findall(X,p(X,[]),L),afficher_liste(L) :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG utilisant des paramètres %
% variables et un lexique pour les mots %
% Réalisé le 02 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Prédicats utiles pour générer les phrases mises en forme :
afficher_phrase([]) :- writeln('.').
afficher_phrase([X|L]) :- write(' '), write(X), afficher_phrase(L).
afficher_liste([X|L]) :- afficher_phrase(X), afficher_liste(L).
generer :- findall(X,p(X,[]),L),afficher_liste(L).%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Structure de la phrase et des éléments composant la phrase (sujet et forme verbale)
% contenant seulement des variables dans les paramètres :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p est une phrase composée d'un sujet et d'un verbe :
p --> sujet(Type,Genre,Nombre), verbe(Type,Genre,Nombre).% toutes les formes possibles du sujet :
sujet(_,Genre,Nombre) --> pronom(Genre,Nombre).
sujet(_,Genre,Nombre) --> prenom(Genre,Nombre).% toutes les formes possibles du verbe :
verbe(_,_,Nombre) --> verbe(Nombre).
verbe(_,Genre,Nombre) --> etre(Nombre),adjectif(Genre,Nombre).% lien avec le lexique en fonction du Nombre : 2 formes possibles pour chaque mot
verbe(Nombre) --> [Mot], {lexique(Mot, verbe, _, Nombre)}.
etre(Nombre) --> [Mot], {lexique(Mot, etre, _, Nombre)}.% lien avec le lexique en fonction du Genre et du Nombre : 4 formes possibles pour chaque mot
adjectif(Genre,Nombre) --> [Mot], {lexique(Mot, adjectif, Genre, Nombre)}.
pronom(Genre,Nombre) --> [Mot], {lexique(Mot, pronom, Genre, Nombre)}.
prenom(Genre,Nombre) --> [Mot], {lexique(Mot, prenom, Genre, Nombre)}.%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lexique contenant les constantes (le lexique est un ensemble de faits) :
% Le fait lexique possède 4 paramètres : le mot, le type de mot, son genre et son nombre
% Connaissant le type, le genre et le nombre le lexique renvoie le mot
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% pronom :
lexique('Il', pronom, masculin, singulier).
lexique('Elle', pronom, feminin, singulier).
lexique('Ils', pronom, masculin, pluriel).
lexique('Elles', pronom, feminin, pluriel).
% prenom :
lexique('Paul', prenom, masculin, singulier).
lexique('Marie', prenom, feminin, singulier).
lexique('Vincent et Paul', prenom, masculin, pluriel).
lexique('Marie et Julie', prenom, feminin, pluriel).
% verbe :
lexique(dort, verbe, _ , singulier).
lexique(dorment, verbe, _, pluriel).
lexique(travaille, verbe, _ , singulier).
lexique(travaillent, verbe, _, pluriel).
% etre :
lexique(est, etre, _, singulier).
lexique(sont, etre, _, pluriel).
% adjectif
lexique(beau, adjectif, masculin, singulier).
lexique(belle, adjectif, feminin, singulier).
lexique(beaux, adjectif, masculin, pluriel).
lexique(belles, adjectif, feminin, pluriel).
En appelant le prédicat generer on obtient instantanément les 24 phrases correspondant à la grammaire, bien constuites et mises en forme :
?- generer.
Il dort.
Il travaille.
Il est beau.
Elle dort.
Elle travaille.
Elle est belle.
Ils dorment.
Ils travaillent.
Ils sont beaux.
Elles dorment.
Elles travaillent.
Elles sont belles.
Paul dort.
Paul travaille.
Paul est beau.
Marie dort.
Marie travaille.
Marie est belle.
Vincent et Paul dorment.
Vincent et Paul travaillent.
Vincent et Paul sont beaux.
Marie et Julie dorment.
Marie et Julie travaillent.
Marie et Julie sont belles.
Diversifions le vocabulaire en ajoutant un animal comme nouvelle forme de sujet, un troisième verbe, des nouveaux prénoms ainsi qu'un nouvel adjectif au lexique :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Exemple de DCG utilisant des paramètres %
% variables et un lexique pour les mots %
% Programme lexique.pl %
% Réalisé le 02 février 2017 %
% www.gecif.net %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Prédicats utiles pour générer les phrases mises en forme :
afficher_phrase([]) :- writeln('.').
afficher_phrase([X|L]) :- write(' '), write(X), afficher_phrase(L).
afficher_liste([X|L]) :- afficher_phrase(X), afficher_liste(L).
generer :- findall(X,p(X,[]),L),afficher_liste(L).%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Structure de la phrase et des éléments composant la phrase (sujet et forme verbale)
% contenant seulement des variables dans les paramètres :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p est une phrase composée d'un sujet et d'un verbe :
p --> sujet(Type,Genre,Nombre), verbe(Type,Genre,Nombre).% toutes les structures du sujet :
sujet(_,Genre,Nombre) --> pronom(Genre,Nombre).
sujet(_,Genre,Nombre) --> prenom(Genre,Nombre).
sujet(_,Genre,Nombre) --> article(Genre,Nombre),animal(Genre,Nombre).% toutes les strutures du verbe :
verbe(_,_,Nombre) --> verbe(Nombre).
verbe(_,Genre,Nombre) --> etre(Nombre),adjectif(Genre,Nombre).% lien avec le lexique en fonction du Nombre : 2 formes possibles pour chaque mot
verbe(Nombre) --> [Mot], {lexique(Mot, verbe, _, Nombre)}.
etre(Nombre) --> [Mot], {lexique(Mot, etre, _, Nombre)}.% lien avec le lexique en fonction du Genre et du Nombre : 4 formes possibles pour chaque mot
adjectif(Genre,Nombre) --> [Mot], {lexique(Mot, adjectif, Genre, Nombre)}.
pronom(Genre,Nombre) --> [Mot], {lexique(Mot, pronom, Genre, Nombre)}.
prenom(Genre,Nombre) --> [Mot], {lexique(Mot, prenom, Genre, Nombre)}.
article(Genre,Nombre) --> [Mot], {lexique(Mot, article, Genre, Nombre)}.
animal(Genre,Nombre) --> [Mot], {lexique(Mot, animal, Genre, Nombre)}.%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lexique contenant les constantes (le lexique est un ensemble de faits) :
% Le fait lexique possède 4 paramètres : le mot, le type de mot, son genre et son nombre
% Connaissant le type, le genre et le nombre le lexique renvoie le mot par unification
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% article :
lexique('Le', article, masculin, singulier).
lexique('La', article, feminin, singulier).
lexique('Les', article, _, pluriel).
lexique('Un', article, masculin, singulier).
lexique('Une', article, feminin, singulier).
lexique('Des', article, _, pluriel).
% animal :
lexique(cheval, animal, masculin, singulier).
lexique(chien, animal, masculin, singulier).
lexique(colombe, animal, feminin, singulier).
lexique(chienne, animal, feminin, singulier).
lexique(chevaux, animal, masculin, pluriel).
lexique(chiens, animal, masculin, pluriel).
lexique(colombes, animal, feminin, pluriel).
lexique(chiennes, animal, feminin, pluriel).
% pronom :
lexique('Il', pronom, masculin, singulier).
lexique('Elle', pronom, feminin, singulier).
lexique('Ils', pronom, masculin, pluriel).
lexique('Elles', pronom, feminin, pluriel).
% prenom :
lexique('Paul', prenom, masculin, singulier).
lexique('Marie', prenom, feminin, singulier).
lexique('Alexis', prenom, masculin, singulier).
lexique('Laure', prenom, feminin, singulier).
lexique('Vincent et Paul', prenom, masculin, pluriel).
lexique('Marie et Julie', prenom, feminin, pluriel).
lexique('Laure et Alexis', prenom, masculin, pluriel).
lexique('Julie, Laure et Marie', prenom, feminin, pluriel).
% verbe :
lexique(dort, verbe, _ , singulier).
lexique(dorment, verbe, _, pluriel).
lexique(mange, verbe, _ , singulier).
lexique(mangent, verbe, _, pluriel).
lexique(marche, verbe, _ , singulier).
lexique(marchent, verbe, _, pluriel).
% etre :
lexique(est, etre, _, singulier).
lexique(sont, etre, _, pluriel).
% adjectif
lexique(beau, adjectif, masculin, singulier).
lexique(belle, adjectif, feminin, singulier).
lexique(beaux, adjectif, masculin, pluriel).
lexique(belles, adjectif, feminin, pluriel).
lexique(grand, adjectif, masculin, singulier).
lexique(grande, adjectif, feminin, singulier).
lexique(grands, adjectif, masculin, pluriel).
lexique(grandes, adjectif, feminin, pluriel).
Pour obtenir toutes les phrases d'un coup dans un fichier texte en redirigeant la sortie standard de swipl.exe dans un shell Windows on prépare cette fois un fichier entree.txt contenant seulement la ligne generer;halt.
Ensuite on lance la commande swipl lexique.pl < entree.txt > sortie.txt dans le shell Windows, et on récupère les 140 phrases générées et mises en forme dans le fichier sortie.txt :
Il dort.
Il mange.
Il marche.
Il est beau.
Il est grand.
Elle dort.
Elle mange.
Elle marche.
Elle est belle.
Elle est grande.
Ils dorment.
Ils mangent.
Ils marchent.
Ils sont beaux.
Ils sont grands.
Elles dorment.
Elles mangent.
Elles marchent.
Elles sont belles.
Elles sont grandes.
Paul dort.
Paul mange.
Paul marche.
Paul est beau.
Paul est grand.
Marie dort.
Marie mange.
Marie marche.
Marie est belle.
Marie est grande.
Alexis dort.
Alexis mange.
Alexis marche.
Alexis est beau.
Alexis est grand.
Laure dort.
Laure mange.
Laure marche.
Laure est belle.
Laure est grande.
Vincent et Paul dorment.
Vincent et Paul mangent.
Vincent et Paul marchent.
Vincent et Paul sont beaux.
Vincent et Paul sont grands.
Marie et Julie dorment.
Marie et Julie mangent.
Marie et Julie marchent.
Marie et Julie sont belles.
Marie et Julie sont grandes.
Laure et Alexis dorment.
Laure et Alexis mangent.
Laure et Alexis marchent.
Laure et Alexis sont beaux.
Laure et Alexis sont grands.
Julie, Laure et Marie dorment.
Julie, Laure et Marie mangent.
Julie, Laure et Marie marchent.
Julie, Laure et Marie sont belles.
Julie, Laure et Marie sont grandes.
Le cheval dort.
Le cheval mange.
Le cheval marche.
Le cheval est beau.
Le cheval est grand.
Le chien dort.
Le chien mange.
Le chien marche.
Le chien est beau.
Le chien est grand.
La colombe dort.
La colombe mange.
La colombe marche.
La colombe est belle.
La colombe est grande.
La chienne dort.
La chienne mange.
La chienne marche.
La chienne est belle.
La chienne est grande.
Les chevaux dorment.
Les chevaux mangent.
Les chevaux marchent.
Les chevaux sont beaux.
Les chevaux sont grands.
Les chiens dorment.
Les chiens mangent.
Les chiens marchent.
Les chiens sont beaux.
Les chiens sont grands.
Les colombes dorment.
Les colombes mangent.
Les colombes marchent.
Les colombes sont belles.
Les colombes sont grandes.
Les chiennes dorment.
Les chiennes mangent.
Les chiennes marchent.
Les chiennes sont belles.
Les chiennes sont grandes.
Un cheval dort.
Un cheval mange.
Un cheval marche.
Un cheval est beau.
Un cheval est grand.
Un chien dort.
Un chien mange.
Un chien marche.
Un chien est beau.
Un chien est grand.
Une colombe dort.
Une colombe mange.
Une colombe marche.
Une colombe est belle.
Une colombe est grande.
Une chienne dort.
Une chienne mange.
Une chienne marche.
Une chienne est belle.
Une chienne est grande.
Des chevaux dorment.
Des chevaux mangent.
Des chevaux marchent.
Des chevaux sont beaux.
Des chevaux sont grands.
Des chiens dorment.
Des chiens mangent.
Des chiens marchent.
Des chiens sont beaux.
Des chiens sont grands.
Des colombes dorment.
Des colombes mangent.
Des colombes marchent.
Des colombes sont belles.
Des colombes sont grandes.
Des chiennes dorment.
Des chiennes mangent.
Des chiennes marchent.
Des chiennes sont belles.
Des chiennes sont grandes.Conclusion
En utilisant les paramètres, la définition d'une grammaire dans Prolog est un moyen de générer facilement et avec une syntaxe simple une structure de données textuelle pouvant être complexe mais répondant à des critères bien précis. Cette "structure de données" peut être :
Le module clpfd de SWI-Prolog permet de programmer avec contraintes.
Un premier exemple : on recherche les nombres entiers supérieurs à 2 dans l'intervalle 1..5 :
Le code source (il charge le module clpfd puis définit les contraintes sur la variable X) :
:-use_module(library(clpfd)).
solution(L):-
L=[X],
X in 1..5,
X#>2,
labeling([],L).
Appelons le prédicat solution dans l'interpréteur Prolog :
?- solution(L).
L = [3] ;
L = [4] ;
L = [5].
Prolog nous ressort les 3 solutions du problèmes : les entiers 3, 4 et 5.
Ajoutons une nouvelle contraintes afin de limiter les solutions possibles :
:-use_module(library(clpfd)).
solution(L):-
L=[X],
X in 1..5,
X#>2,
X#=<3,
labeling([],L).
Cette fois il n'y a qu'une seule solution : X=3
?- solution(L).
L = [3].
Principe d'un programme logique avec contraites :
Le programme est composé d'un seul prédicat solution contenant 3 parties :
1 - la déclaration de toutes les variables du problème dans une liste L
2 - l'écriture des différentes contraintes liant toutes les variables
3 - l'appel du predicat labelling pour la recherche des solution
Application de la programmation logique avec contraintes : la résolution d'un système d'équation à 2 inconnues.
On cherche 2 entiers X et Y tels que 2X+4Y=20 et 7X+8Y=52. Les 2 variables à rechercher sont X et Y.
:-use_module(library(clpfd)).
solution(L):-
% liste des variables du problèmes
L=[X,Y],
% intervalle arbitraire sur une variable
X in -100..100,
% écriture des contraintes : il s'agit des 2 équations du système
2*X+4*Y#=20,
7*X+8*Y#=52,
% appel de labeling
labeling([],L).
Et en appelant le prédicat solution Prolog nous donne instantanément les deux solutions du système : X=4 et Y=3
?- solution(L).
L = [4, 3].
Autre application : recherche d'un carré magique
On cherche à placer les entiers de 1 à 9 dans un carré 3x3 de telle sorte que la somme des nombre de chaque ligne, chaque colonne et chaque diagonale soit égale à 15. Les 9 variables à trouver sont nomées X1 à X9 et représentent les 9 cases du carré magique :
Le programme source :
:-use_module(library(clpfd)).
solution(L):-
L=[X1,X2,X3,X4,X5,X6,X7,X8,X9],
L ins 1..9,
all_different(L),
X1+X2+X3#=15,
X4+X5+X6#=15,
X7+X8+X9#=15,
X1+X4+X7#=15,
X2+X5+X8#=15,
X3+X6+X9#=15,
X3+X5+X7#=15,
X1+X5+X9#=15,
labeling([],L).
Prolog sort instantanément 8 solutions correspondant à un même carré magique avec différentes orientations (rotation et symétrie) :
?- solution(L).
L = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
L = [2, 9, 4, 7, 5, 3, 6, 1, 8] ;
L = [4, 3, 8, 9, 5, 1, 2, 7, 6] ;
L = [4, 9, 2, 3, 5, 7, 8, 1, 6] ;
L = [6, 1, 8, 7, 5, 3, 2, 9, 4] ;
L = [6, 7, 2, 1, 5, 9, 8, 3, 4] ;
L = [8, 1, 6, 3, 5, 7, 4, 9, 2] ;
L = [8, 3, 4, 1, 5, 9, 6, 7, 2] ;
Remarque : in impose qu'une variable appartienne à un intervalle et ins impose que toutes les variables d'une liste appartiennent à un intervalle.
all_different(L) impose que toutes les valeurs de la liste L soient différentes.
Et voici le retour ... des grilles de routement de TP :
On cherche la grille de roulement pour 12 élèves :
Voici un exemple de problème qui doit sans doute se résoudre facilement grâce à la programmation avec contraintes, mais la solution simple en Prolog reste à trouver ...
Cette page vous a donné tous les éléments de base pour pouvoir commencer à programmer en Prolog. Pour aller plus loin on pourra commencer par aller voir tous les prédicats prédéfinis de SWI-Prolog, notamment pour la manipulation des listes, puis ensuite découvrir des exemples où la coupure est indispensable.