Discussion :

[Pierre Cormault]

Bonjour !
J'ai parcouru (avec frustration) 3 ou 4 gros articles sur la Programmation Logique avec Contraintes (P.L.C). L'origine en est presque toujours universitaire, et le sujet la théorisation des moteurs de résolution.
Mais peu ou pas d'exemples concrets, le sempiternel SEND + MORE = MONEY revenant à chaque fois, mais toujours bien seul.

Aussi suis-je désarmé pour lever une difficulté qu'au départ je sous-estimais. Il s'agit d'expression de contraintes à satisfaire.
L'extrait de code ci-après devrait faire comprendre de quoi il s'agit à qui possède la maîtrise de la P.L.C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
%--------------------------------------------------------------------
% Explications liminaires
%--------------------------------------------------------------------
% On exprime l'existence de chacune des 52 cartes d'un jeu de cartes 
% par un prédicat carte/5 de structure:
%   carte(?Id, ?C, ?R, ?PH, ?Nm) avec:
%   Id: l'index de la carte (un entier compris entre 1 et 52)
%    C: l'indice de la couleur 
%      (1 = Pique, 2 = Coeur, 3 = Carreau, 4 = Trèfle)
%    R: le rang de la carte (de 1 pour un 2 à 13 pour un As) 
%   PH: la valeur en Points d'Honneur de la carte
%      (un As: 4, un Roi: 3, une Dame: 2, un Valet: 1, les autres: 0)
%   Nm: le nom de la carte (ex: 'AP', 'RK', '5T', ..) 
% 
% Exemple: l'As de pique
% carte(1,1,13,4,'AP')
%---------------------------------------------------------------------
%%----------------------------------------------------------------
%% Essai ultra-simple de satisfaction de contraintes
%% ---------------------------------------------------------------
%% But: Obtenir une main de 4 cartes,
%%      sans aucune contrainte sur chaque carte (pour le moment !)
%% ---------------------------------------------------------------
getmain :-
   Index = [I1,I2,I3,I4],    % les index de 4 cartes
   Index in 1..52,      % les 52 index de cartes
   Cs = [C1,C2,C3,C4],       % les codes-couleur de chaque carte 
   Cs in 1..4,               % 1 = pique, 2 = coeur, 3 = carreau, 4 = trefle
   get_c_ph(I1,C1,_),        % liens entre chaque index Ii 
   get_c_ph(I2,C2,_),        % et le code-couleur correspondant Ci
   get_c_ph(I3,C3,_),        % Exemples: As de pique:  I1 =  1,  C1 = 1
   get_c_ph(I4,C4,_),        %   2 de trèfle: I52 = 52, C52 = 4
   all_different(Index),     % unique contrainte appliquée
 
   label(Index),             % résolution des contraintes
 
   % --- affichage des résultats ----------
   printmain(Index),       
   nl, printlist(Cs),
     nombre_piques(Index, N1), nl, write(N1),
     nombre_coeurs(Index, N2), nl, write(N2),
   nombre_carreaux(Index, N3), nl, write(N3),
    nombre_trefles(Index, N4), nl, write(N4).
/* ------------------- Exécution sous SWI-PROLOG --------------------------
1 ?- 
library(clp/clp_events) compiled into clp_events 0.00 sec, 2,868 bytes
library(clp/bounds) compiled into bounds 0.03 sec, 83,492 bytes
d:/codes PLC/plc_5.pl compiled 0.03 sec, 94,276 bytes
1 ?- getmain.
AP RP DP VP    % les 4 cartes solution (on est passé de l'index au nom)
1 1 1 1        % les 4 code-couleur
4              % le nombre de piques
0              % le nombre de coeurs
0              % le nombre de carreaux
0              % le nombre de trèfles  
Yes
------------------------------------------------------------------------ */

On voit que, en l'absence de contrainte, le but assigné est atteint !
Question: comment obtenir une main satisfaisant à (quelques) contraintes ?

La première à surmonter (je n'y parviens pas):
Obtenir une main de 4 cartes avec au moins 2 coeurs ?

[Pierre Cormault]

Et bien voilà que je me réponds à moi-même:
J'ai revisité le concept d'implication de contraintes:

+P #=> +Q
(La contrainte P implique la contrainte Q)

que je n'avais pas réussi à appliquer correctement lors d'une première tentative. Et cette fois, cela a fonctionné (voir prédicat nb_coeurs/3):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
%-------------------------------------
nb_coeurs(List,Value,Count) :-
nb_coeurs(List,Value,0,Count).
nb_coeurs([],_,Count,Count).
nb_coeurs([X|Xs],Value,Acc,Count) :-
X #= Value #=> NAcc #= Acc + 1,
X #\= Value #=> NAcc #= Acc,
nb_coeurs(Xs,Value,NAcc,Count).
%-------------------------------------
%-------- Résolution -----------------
getmain(I1,I2,I3,I4) :-
Index = [I1,I2,I3,I4],
Index in 1..52,
Cs = [C1,C2,C3,C4],
Cs in 1..4,
 
get_c_ph(I1,C1,_),
get_c_ph(I2,C2,_),
get_c_ph(I3,C3,_),
get_c_ph(I4,C4,_),
 
nb_coeurs(Cs,2,Count),
Count #>= 2,
all_different(Index),
label(Index),
printmain(Index).
/* ------------------- Exécution sous SWI-PROLOG --------------------------
1 ?- 
% library(clp/clp_events) compiled into clp_events 0.00 sec, 2,868 bytes
% library(clp/bounds) compiled into bounds 0.02 sec, 83,492 bytes
% d:/codes PLC/plc_6.pl compiled 0.02 sec, 92,576 bytes
1 ?- getmain(A,B,C,D).
AP RP AC RC 
A = 1
B = 2
C = 14
D = 15 
Yes
------------------------------------------------------------------------ */

J'espère que ces tâtonnements qui m'appartiennent pourront être utiles à d'autres (en attendant que pcaboche nous publie les tutoriels qui font encore cruellement défaut dans ce domaine en pleine expansion).

[pcaboche]

Bonjour Pierre,

C'est très bien que tu aies pu résoudre ton problème par toi-même. Je n'en ai pris connaissance qu'en milieu d'après midi (vers 15h30) donc je n'ai pas pu beaucoup me pencher sur la question. Et demain, je ne suis pas là.

Personnellement, je n'aurait pas utilisé la PLC pour ce type de prolblème, mais bon, puique ça a l'air de te convenir...

J'espère que ces tâtonnements qui m'appartiennent pourront être utiles à d'autres (en attendant que pcaboche nous publie les tutoriels qui font encore cruellement défaut dans ce domaine en pleine expansion).

Pour ce qui est des tutoriels, si tu veux tu peux en proposer un que je me ferai un plaisir de lire, de corriger, avant de le soumettre à la responsable "Autre langages" (à savoir debug) ainsi qu'aux autres relecteurs, et ce en vu de t'intégrer à l'équipe de rédaction.

Vois-tu, je suis pour l'instant le seul rédacteur à se pencher sur le langage Prolog (ce qui est parfois sujet à certaines blagues). J'ai effectivement quelques articles en préparation, la plupart sur le langage Prolog (à part 1 ou 2) mais rien concernant la PLC pour le moment (même si, comme tu le fais remarquer, c'est un domaine en pleine expansion).

Mon but pour l'instant est de couvrir certains aspects du langage que je n'ai pas encore eu le temps d'aborder (ex: la recherche de solutions, qui se rapproche de la théorie des graphes). J'ai donc de quoi m'occuper...

[billynirvana]

La programmation par contrainte est encouragée! Elle diminue le temps de réponse en plus!

Avant de lancer tes prédicats, il faut contraindre tes variables non liées.

Dans l'exemple suivant, afin d'obtenir toutes les couleurs sauf le rouge, vert et gris, il vaut mieux écrire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
CouleursDispos(rose)->;
CouleursDispos(jaune)->;
...
 
Couleurs(x) ->
PasRouge(x)
PasVert(x)
PasGris(x)
CouleursDispos(x);

et non

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
CouleursDispos(rose)->;
CouleursDispos(jaune)->;
...
 
Couleurs(x) ->
CouleursDispos(x)
PasRouge(x)
PasVert(x)
PasGris(x);

Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
%- Verifie si une variable x n'est pas element d'une liste l -%
 
hors_de(x, nil)->;
hors_de(x, y.l)->
dif(x, y)
hors_de(x, l);

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
%- Verifie que tous les elements d'une liste l sont differents -%
 
tous_diff(nil)->;
tous_diff(x.l)->
hors_de(x, l)
tous_diff(l);

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
> hors_de(3, 1.2.3.nil);
> hors_de(0, 1.2.3.nil);
{}
> hors_de(x, 1.2.3.nil);
{x#1,x#2,x#3}
> tous_diff(7.8.9.nil);
{}
> tous_diff(7.8.9.8.nil);
> tous_diff(nil);
{}
>

[Pierre Cormault]

Avant de lancer tes prédicats, il faut contraindre tes variables non liées.

Merci de ton conseil. Je vais tenter de le mettre en pratique.
Dans l'immédiat, j'ai des problèmes de compréhension avec la syntaxe que tu utilises dans tes exemples.

Est-elle conforme à la version de Prolog que j'utilise ? Je ne l'ai pas reconnue dans le seul document dont je dispose en la matière:

SWI-Prolog 5.6 - Reference Manual
Chapter 7: CHR Constraint Handling Rules

Appartient-elle à une implémentation particulière disponible via une bibliothèque particulière telle que clp/bounds, ou clpqr ou encore une autre ?
Pardonne mon ignorance, mais c'est précisément pour y remédier que l'idée m'est venue de venir sur ce forum !

[pcaboche]

La programmation par contrainte est encouragée! Elle diminue le temps de réponse en plus!

Oui oui, tout à fait d'accord! La grosse difficulté est souvent d'exprimer certains problèmes à l'aide de contraintes.

Est-elle (la syntaxe) conforme à la version de Prolog que j'utilise ? Je ne l'ai pas reconnue dans le seul document dont je dispose en la matière

C'est la syntaxe de Marseille, me semble-t'il, et non celle d'Edimburgh.


Ouais, je suis content! Il y a de plus en plus de gens qui viennent sur DVP pour parler de Prolog!

[billynirvana]

Oui, effectivement, j'utilise la syntaxe ProLog de Marseille, l'originale.

J'ai en ma possession un document qui énumére les différences de syntaxe. Je ne sais pas si il est complet.

J'avais hésité de rédiger un document Prolog pour Dev.com concernant les analyseurs. Je vais voir si je me sens, car ce langage est fait à la base pour ça!

[pcaboche]

J'avais hésité de rédiger un document Prolog pour Dev.com concernant les analyseurs. Je vais voir si je me sens, car ce langage est fait à la base pour ça!

Ca serait super intéressant en effet! Ca interesserait énormément de personnes ici. N'hésite pas à me faire parvenir les éventuels brouillons (si tu as ne serait-ce que le plan de l'article, cela donnera déjà une bonne idée du contenu) et je demanderai que l'on t'intègre à l'équipe de rédaction, comme ça tu auras accès à nos différents outils de publication.

Si tu n'as pas le temps présentement de rédiger l'article, ce n'est pas grave. Par contre il serait extrêmement utile que l'on dispose de ce genre de ressource sur DVP. J'attends donc de tes nouvelles.

[billynirvana]

J'ai travaillé pendant 3 ans avec Prolog pour construire des analyseurs.
Je vais lire tes docs prolog, ca me donnera une idée sur les méthodes rédactionnelles.

Ce soir, je te passe le document sur les différences Marseille/Edimbourg

En effet, il serait interessant que je mette mes expériences dans ce domaine sur dev.com!


Voici un exemple tout bete:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
%%%%%%%%%%%%%%%%%%%%
%- GRAMMAIRE
%-
%- NB -> A B
%- A -> 0 A 1 | 0 1
%- B -> 2 B | 2
 
analyser_NB(<u, v>, a, b)->
analyser_A(<u, v1>, a)
analyser_B(<v1, v>, b);
 
analyser_A(<0.1.u, u>, 1)->;
analyser_A(<0.u, v>, a)->
analyser_A(<u, 1.v>, a')
val(a'+1, a);
 
analyser_B(<2.u, u>, 1)->;
analyser_B(<2.u, v>, b)->
analyser_B(<u, v>, b')
val(b'+1, b);
 
 
%- x et y comptent respectivement le nombre de 1 (equivalent a celui du nombre de 0) et le nombre de 2
 
/*
> analyser_NB(<0.1.2.nil, nil>, x, y);
{x=1,y=1}
> analyser_NB(<0.0.0.1.1.1.2.nil, nil>, x, y);
{x=3,y=1}
> analyser_NB(<0.0.0.1.1.2.nil, nil>, x, y);
*/

[pcaboche]

Ok, nickel !

Pour les analyseurs, la syntaxe me fait penser à celle du Caml dans ce domaine (exemple tiré de la dic Ocaml) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let rec parse_expr = parser
     [< e1 = parse_mult; e = parse_more_adds e1 >] -> e
 and parse_more_adds e1 = parser
     [< 'Kwd "+"; e2 = parse_mult; e = parse_more_adds (Sum(e1, e2)) >] -> e
   | [< 'Kwd "-"; e2 = parse_mult; e = parse_more_adds (Diff(e1, e2)) >] -> e
   | [< >] -> e1
 and parse_mult = parser
     [< e1 = parse_simple; e = parse_more_mults e1 >] -> e
 and parse_more_mults e1 = parser
     [< 'Kwd "*"; e2 = parse_simple; e = parse_more_mults (Prod(e1, e2)) >] -> e
   | [< 'Kwd "/"; e2 = parse_simple; e = parse_more_mults (Quot(e1, e2)) >] -> e
   | [< >] -> e1
 and parse_simple = parser
     [< 'Ident s >] -> Var s
   | [< 'Int i >] -> Const(float i)
   | [< 'Float f >] -> Const f
   | [< 'Kwd "("; e = parse_expr; 'Kwd ")" >] -> e;;