Prolog : "crash course" (3)

Listes et le combinatoire, quelques algorithmes non-déterministes

Observons quand même que append utilisé comme concaténeur est un prédicat déterministe, une seule solution d'une requête "normale", mais évalué "à l'envers", devient non-déterministe, plusieurs scissions possibles.

Ici nous discuterons quelques algorithmes non-déterministes par excellence, utiles dans les problèmes combinatoires. Ils suggéreront comment Prolog peut être appliqué dans quelques problèmes du domaine d'intelligence artificielle (recherche, problèmes stratégiques, jeux).

Sélections, et groupement des solutions non-déterministes

Le prédicat suivant, extrêmement simple, permet de sélectionner un par un, tous les éléments d'une liste.
select([X|_],X).
select([_|P],X):-select(P,X).
Voici une requête :
 select([2,3,5],A).
A = 2 ;
A = 3 ;
A = 5 ;
false.
Ceci est un exemple comment "sérialiser dans le temps" une donnée composite. Mais l'opération inverse, le ramassage des solutions non-déterministes dans une liste, serait également utile, jusqu'à présent nous n'avons pas vu comment construire l'ensemble de toutes les solutions en Prolog. Il existe plusieurs outils pour cela, findall, bagof et setof. Les trois acceptent la même syntaxe, disons : findall(Var,Requete,Liste). La différence entre bagof et setof est que setof élimine toutes les solutions dupliquées, la liste finale est un ensemble de solutions ; elle est ordonnée.

Exemple :

32 ?- findall(X,ancetre(adam,X),L).
L = [abel, cain, henoch].

35 ?- setof(X,select([9,0,9,3,7,7,0],X),P).
P = [0, 3, 7, 9].
Le premier argument dénote une variable, qui normalement doit être présente dans le second, qui est une requête, un "Goal". Prolog lance cette requête et itère jusquà l'échec, en ramassant les valeurs de la variable dans une autre, une liste qui contiendra le résultat complet.

Ces prédicats sont plus riches que ça, et permettent des paramétrages supplémentaires, avec l'introduction des variables existentielles, etc., mais nous ne pouvons nous concentrer dessus. Il faut quand même apprivoiser les détails, afin de pouvoir traiter les cas où le nombre potentiel de solutions est infini.

Question : quelle serait la réaction du système si on lançait select(L,7) ? L sera unifié avec toute imaginable liste contenant le nombre 7. Il est évident que l'ensemble de solutions est infini, et un tel appel ne servira à rien. Mais des variantes plus restrictives peuvent être utiles.

Voici la sélection d'un élément d'une liste, qui laisse également la liste restante.

sel([X|P],X,P).
sel([Y|P],X,[Y|Q]):-sel(P,X,Q).
Ici l'"appel normal" fournit deux résultats, l'objet sélectionné, et le reste. Voici un appel qui ramasse tout. La forme s(...) n'a aucune sémantique, c'est une simple structure de données.
 findall(D,(sel([1,2,3,4],X,A),D=s(X,A)),L).
L = [s(1, [2, 3, 4]), s(2, [1, 3, 4]), s(3, [1, 2, 4]), s(4, [1, 2, 3])].
Ce prédicat est bien adapté à l'"appel inversé", il agira comme une insertion d'un élément dans une liste, mais une insertion non-déterministe, dans tous les endroits possibles.
 sel(L,1,[2,3,4]).
L = [1, 2, 3, 4] ;
L = [2, 1, 3, 4] ;
L = [2, 3, 1, 4] ;
L = [2, 3, 4, 1] ;
Nous utiliserons ce protocole d'appel de sel, afin de construire toutes les permutations d'une liste. L'algorithme non-déterministe sera vu comme : engendrer UNE permutation quelconque, depuis une liste donnée. Si la liste est vide, rien à faire la seule permutation des éléments dedans est la même liste vide. Si la liste ne contient qu'un seul élément – la même réponse, la liste source est le seul résultat possible. Mais si la liste est plus grande, on obtient une permutation "quelconque" en permutant la queue, et ensuite en insérant la tête dans cette permutation de la queue.

findall(P,perm([1,2,3,4],P),L).L = [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [1, 3, 2, 4], 
 [3, 1, 2, 4], [3, 2, 1, 4], [3, 2, 4, 1], [1, 3, 4, 2], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [1, 2, 4, 3], 
 [2, 1, 4, 3], [2, 4, 1, 3], [2, 4, 3, 1], [1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1], [1, 4, 3, 2], 
 [4, 1, 3, 2], [4, 3, 1, 2], [4, 3, 2, 1]].
Attention. Afin d'obtenir et afficher ce résultat il faut désactiver la protection qui empêche l'affichage des listes trop longues.
set_prolog_flag(toplevel_print_options,[quoted(true), portray(true), spacing(next_argument)]).
Ce qui a été effacé de l'argument, est la valeur par défaut : max_depth(10).

La solution présentée n'est pas unique, comme avec l'algorithme de tri par insertion, on peut le formuler de manière différente : au lieu de permuter la queue, d'abord on sélectionne un élément quelconque, et on permute le reste. Ensuite on remet l'élément sélectionné à la tête.

perm1([],[]).
perm1(L,[X|P]):-sel(L,X,Q),perm1(Q,P).
Notez que l'ordre de génération est différent par rapport au cas précédent.

Combinaisons.

Il s'agit de sélectionner un certain nombre, disons, M éléments d'une liste de N éléments (dans l'ordre). L'idée est la suivante. Si on a zéro éléments à choisir, le résultat est [] (et la liste restante est l'original). Si on choisit un élément, alors nous aurons sel. Si N : on choisit un élément, et du reste – N-1 (ou dans l'autre ordre, d'abord N-1, ensuite 1). Ceci demande un peu d'arithmétique !

Or, Prolog n'est pas un langage pour faire des calculs numériques, l'efficacité n'est pas bonne, car l'optimisation serait difficile, et la structure syntaxique du langage n'est pas excellente non plus. Mais les primitives pour des calculs numériques existent. Tout d'abord, on a des opérateurs, on peut unifier, par ex. X = 7+2, ou Y = X-1. Cependant, surprise !:

45 ?- X=7+2.
X = 7+2.
L'addition n'a pas été effectuée. L'opérateur '+' est formel, il construit un terme A+B, sans interpréter le plus. Afin d'effectuer l'opération (si possible), il faut utiliser un prédicat (en fait : une procédure non-logique) is, qui est également un opérateur.

 X is 7+2, Y is X-1.
X = 9,
Y = 8.
Voici les combinaisons. On n'utilisera pas directement le prédicat sel, mais une variante sera incorporée dans l'algorithme. Pour tout élément de la liste source, soit on sélectionne cet élément, soit non. S'il est sélectionné, il en reste N-1, sinon, toujours N.
comb(0,L,[],L).
comb(N,[X|P],[X|A],B):-N>0,N1 is N-1,comb(N1,P,A,B).
comb(N,[X|P],A,[X|B]):-N>0,comb(N,P,A,B).
On constate qu'ici, et dans plusieurs autres cas, la notation Prolog, avec des clauses multiples, possède une certaine redondance, des répétitions. Ceci est assez lisible, mais certains préfèrent "factoriser" le programme et utiliser des formes plus similaires à d'autres langages. Souvent deux clauses alternatives une après l'autre, peuvent être combinées en une seule, mais avec l'opérateur ';', qui est le OU logique.
comb1(0,L,[],L).
comb1(N,[X|P],A,B):-N>0,
      (N1 is N-1,A=[X|A1],B=B1; N1=N,A=A1,B=[X|B1]),
      comb1(N1,P,A1,B1).


Encore un usage de findall et d'autres prédicats similaires

Parfois les algorithmes combinatoires sont un peu pénibles à coder. Prolog dispose donc de plusieurs prédicats prédéfinis qui facilitent la manipulation des structures, notamment les listes. Par ex. on a un prédicat prédéfini member(X,L) qui vérifie si X fait partie de la liste L. On peut le facilement définir :
member(X,[X|_]).
member(X,[_|Q]):-member(X,Q).
Notez que ce prédicat est exactement identique à select, sauf pour l'ordre des arguments.

Passons à d'autres algorithmes combinatoires. Voici comment construire la différence ensembliste de deux listes : sub([2,3,8,9,4,1,2,5],[3,4,2],R) doit unifier R avec la liste de tous les éléments qui appartiennent au premier argument, mais sont absents dans le second, donc [8,9,1,5]. Voici la définition la plus courte :

sub(L1,L2,R):-findall(X,(member(X,L1),not(member(X,L2))),R).

Faire cela à la main est possible et court, mais demande quand même un peu de travail. Et on se faire piéger par le non-déterminisme :

sub1([],_,[]).
sub1([X|P],L,RR):-not(member(X,L)),sub1(P,L,R),RR=[X|R];sub1(P,L,RR).
Ceci produit la séquence de tous les sous-ensembles du premier argument, dont les éléments sont absents dans le second, ici 16 solutions au lieu d'une. Afin de "déterminiser" le prédicat, on peut introduire un cut après not(...).

Powerset

Voici un prédicat très classique, qui produit la liste de tous les sous-ensembles d'un ensemble, pour l'ensemble-source L, on le note comme 2L.
pset([],[]).
pset([X|P],L):-pset(P,L);pset(P,R),L=[X|R].
La stratégie est conceptuellement immédiate : soit on accepte un élément, soit non. Si on veut ramasser tout dans une liste de listes, on a le findall.

Introduction aux listes différentielles

Les "difference lists" du point de vue de la syntaxe Prolog n'ont rien de particulier, ce sont des paires de listes. Cependant, leur sémantique "conceptuelle" est assez forte. Ces paires doivent représenter la "différence entre deux listes", Si A-B représente une liste différentielle, alors A est une "liste totale", et B – son suffixe ; alors la structure représente la liste totale sans ce suffixe ; conceptuellement c'est le préfixe qui reste.

Exemple : [1,2,3,4,5]-[3,4,5] représente conceptuellement la "liste [1,2]". Le sens intuitif de cette construction est plus au moins : on peut ainsi opérer avec des fragments des listes, sans les détacher de leur contexte, sans leur construction explicite dans la mémeoire. Elles constituent un dispositif d'optimisation. Si on consomme une longue liste, fragment après fragment, si on arrive à travailler avec ces morceaux sans allouer la mémoire spécialement pour eux, on économise la mémoire et le temps !

Normalement on n'a pas besoin d'asembler les éléments de la paire en question en A-B ou autre chose, on remplace une liste dans un prédicat, par les deux constituants séparément. Ainsi la liste différentielle vide, c'est la paire L,L. Ceci est bien sûr ambigu, car L peut être quelconque. Mais d'autres contraintes limitent ces ambiguïtés. La forme différentielle conceptuellement équivalente à [a,b,c], serait [a,b,c|Q],Q. Si on veut, au lieu d'utiliser les paires, on peut écrire P-Q, car l'opérateur '-' n'a pas de sens arithmétique par définition, mais ceci est redondant.

La concaténation de deux listes différentielles n'a rien de trivial, c'est très contraignant. Si [a,b,c|Q],Q doit être concaténé avec quelque chose, cette "quelque chose" doit appartenir au suffixe Q, puisque c'est la "suite" de a,b,c,... En général, si le dessin ci-dessus représente la concaténation de deux listes différentielles symbolisées comme les deux segments à gauche, la structure globale est : (L-P) et (P-Q). Le résultat est évident. Nous pourrons écrire le prédicat de concaténation conc sous forme :

conc(L,P,P,Q,L,Q).

... et plus rien. Ceci ne "fait" rien, c'est une forme syntaxique pure. L'occurrence du conc dans d'autres prédicats serait redondante, on peut l'éliminer par l'identification de quelques variables.

Voici un exemple assez caractéristique de l'usage des listes différentielles, cet exemple doit être bien compris. Rappelons la procédure d'inversement d'une liste :

reverse([],[]).
reverse([X|Y],R):-reverse(Y,M),append(M,[X],R).
et essayons de construire une procédure capable de renverser une liste à l'aide des listes différentielles, en remplacant les individus par les paires, et append par conc. L'original sera une liste normale, ce dont nous avons besoin. Alors, la forme du prédicat en question, appelé revd sera :

revd([],R,R).
revd([X|Y],R,S):-revd(Y,M,P),conc(M,P,[X|L],L,R,S).
Mais à présent nous pourrons réduire conc : P=[X|L], L=S, M=R. Ceci produit le résultat final :
revd([],R,R).
revd([X|Y],R,S):-revd(Y,R,[X|S]).
... et nous avons reconstruit exactement l'algorithme optimisé, avec le tampon. La construction généralise le reverse standard, elle inverse la liste-source, et concatène le résultat à un tampon en principe arbitraire. Si on spécifie S=[] au début, on obtient l'inversion standard, un prédicat sans le troisième paramètre, figé à [].

Mais la généralisation peut être utile. Un cas assez typique, c'est l'implémentation fonctionnelle pure des files (ang. queues), des structures FIFO : first-in, first-out. Dans des langages impératifs, destructifs, une file est une liste, où on attache les éléments d'un bout, par exemple à la fin, et on récupère les éléments depuis le début. En Prolog il faut le coder de manière a sauvegarder toute information de manière unique, on ne modifie pas des structures de données instanciées. Codons les files comme des simples listes, et construisons deux procédures : enqueue qui insère un élément dans une file, et dequeue qui sépare la file en l'élément supprimé, et la file restante. Le prédicat dequeue est largement trivial.

dequeue([X|P],X,P).
enqueue(X,P,R):-append(P,[X],R).
Bien sûr, il serait utile d'avoir le prédicat qui vérifie si la file est vide, etc. Mais réalisons la même stratégie avec des listes différentielles. La file vide, est L-L.
deq([X|L],Q,X,L,Q).
% enq(X,L,Q,L1,Q1):-conc(L,Q,[X|S],S,L1,Q1).
enq(X,L,[X|S],L,S).
Voici un test, l'insertion d'un élément (1) dans la file vide, ensuite l'insertion d'une autre donnée (2) dans la file résultante, suivi par deux éliminations, de X et Y.
enq(1,L,L,A,B),enq(2,A,B,A1,B1),deq(A1,B1,X,A2,B2),deq(A2,B2,Y,A3,B3).
Le résultat est la combinaison des assignations :
L = A, A = A1, A1 = [1, 2|B3],
B = A2, A2 = [2|B3],
B1 = B2, B2 = A3, A3 = B3,
X = 1,
Y = 2.
On récupère la file vide : A3 = B3.

La manipulation des structures incomplètes, dont les Difference Lists sont une exemplification (mais il y en a d'autres), est difficile. En lisant la définition de enq, etc. on ne comprend pas le sens de la construction, et ceci est parfaitement normal. Il faut coder soi-même plusieurs exemples très différents pour "sentir" la stratégie.

En particulier, après avoir acquis une certaine expérience, on constate que les constructions ne sont pas optimales. Dans enq le deuxième et le quatrième paramètre sont toujours identiques (la liste "globale"). Dans deq, les deux suffixes, initial et final, sont également identiques. Mais on ne peut les brutalement éliminer des constructions ci-dessus, par contre, dans le programme qui les utilise, on pourra éliminer les prédicats enq et deq, comme on a éliminé conc.

Il faut faire attention. Contrairement aux listes normales, la procédure deq permet d'effacer un élément d'une file vide ! Le résultat est pathologique. Dans des langages classiques ceci serait tout simplement impossible, mais ici, cela marche.

 deq(L,L,X,A,B).
L = B, B = [X|A].
La pathologie est que le "suffixe" est plus grand, et contient la liste globale (non-instanciée). Une interprétation "magique" reste cependant implémentable, nous pouvons ajouter un objet à une telle "file négative" :
 deq(L,L,X,A,B),enq(42,A,B,Afin,Bfin).
L = B, B = [42|Bfin],
X = 42,
A = Afin, Afin = Bfin.
Alors, après l'insertion de 42, la file devient vide. La file "négative" se comporte comme si on avait "emprunté un objet du vide", du futur, et quand on l'insère, on restaure ce vide. C'est presque la physique quantique !


Suivant
Retour à l'index