Le langage Prolog

Cours n°3Cours n°3

Notion de coupureLes listes

Plan du cours

� Notion de coupure� Les structures de données

� les listes

Notion de coupure (1)

� La recherche systématique de toutes les solutions possibles est une caractéristique importante de Prolog.

� Mais elle constitue également son talon d’Achille � Mais elle constitue également son talon d’Achille car elle conduit parfois à une explosion combinatoire qu’il est nécessaire de couper si l’on veut voir son programme se terminer.

Notion de coupure (2)

� Différents noms utilisés: coupure , cut ou coupe choix

� Introduit un contrôle du programmeur sur l'exécution de ses programmesl'exécution de ses programmes� en élaguant les branches de l’arbre de recherche� rend les programmes plus simples et efficaces

� Notation: ! (ou / dans le prolog de Marseille)� Le coupe choix est un prédicat prédéfini qui

réussit toujours.

Notion de coupure (3)

� Le coupe choix permet de signifier à Prolog qu’on ne désire pas conserver les points de choix en attente

� Utile lors de la présence de clauses exclusives� Utile lors de la présence de clauses exclusivesExemple les 2 règles suivantes :

� humain(X) :- homme(X). s'écrit humain(X) :- homme(X), !. � humain(X) :- femme(X). s'écrit humain(X) :- femme(X), !.

Notion de coupure (4)

� Le coupe-choix permet :� d'éliminer des points de choix� d'éliminer des tests conditionnels que l’on sait inutiles ⇒

plus d'efficacité lors de l'exécution du programme⇒

� Quand Prolog démontre un coupe choix, il ignore toutes les règles du même prédicat, qui le suivent.� Un coupe choix élague toutes les solutions pour la

conjonction de buts qui apparaissent à sa gauche dans la règle

� En revanche il n’affecte nullement la conjonction de buts qui se trouve à sa droite

Notion de coupure (5)

� Exemples d’utilisation :� Pour prouver que x est un élément d’une liste, on peut s'arrêter

dès que la première occurrence de x a été trouvée.� Pour calculer min(a,b) :

min(A, B, A) :- A<B. min(A, B, A) :- A<B, !.min(A, B, A) :- A<B. min(A, B, A) :- A<B, !.min(A, B, B) :- A >=B. min(A, B, B) :- A >=B.

� Pour calculer la racine carrée entière d’un nombre, on utilise un générateur de nombres entiers entier(k). L’utilisation du coupe-choix est alors indispensable après le test K*K>N car la génération des entiers n’a pas de fin.

entier(0).entier(N1) :- entier(N), N1 is N+1.racine(N, R) :- entier(K), K*K >N, ! , R is K-1.

Notion de coupure (6)

� Repeat et fail :� Le prédicat fail/0 est un prédicat qui n’est jamais

démontrable, il provoque donc un échec de la démonstration où il figure.démonstration où il figure.

� Le prédicat repeat/0 est une prédicat prédéfini qui est toujours démontrable mais laisse systématiquement un point de choix derrière lui. Il a une infinité de solutions.

Notion de coupure (7)

� L’utilisation conjointe de repeat, fail et du coupe choix permet de réaliser des boucles.

Exemples :but1:- between(1,10,X), write(X), nl, fail.but1:- between(1,10,X), write(X), nl, fail.but1.

but2:- repeat, between(1,10,X), write(X), nl, fail.but2.

but3:- repeat, !, between(1,10,X), write(X), nl, fail.but3.

Notion de coupure (8)

� Dangers du coupe-choix : on peut perdre des solutions

� Considérez les programmes suivants :enfants(helene, 3). enfants(helene, 3) :- !.enfants(helene, 3). enfants(helene, 3) :- !.enfants(corinne, 1). enfants(corinne,1) :- !.enfants(X, 0). enfants(X, 0).

et l’interrogation enfant(helene, N).1) N=3 et N=02) N=3

Notion de coupure (fin)

� En résumé, les utilités du coupe-choix sont :� éliminer les points de choix menant à des échecs

certains� supprimer certains tests d’exclusion mutuelle dans � supprimer certains tests d’exclusion mutuelle dans

les clauses� permettre de n’obtenir que la première solution de

la démonstration� assurer la terminaison de certains programmes� contrôler et diriger la démonstration

Les Listes

� A une suite, ordonnée ou non, on associe la liste de ses éléments.� suite e1, e2, … est représentée en Prolog par la liste

[e1, e2, … ][e1, e2, … ]� Exemples :

� suite des variables X et Y est représentée par [X,Y]� suite fraises, tarte, glace par [fraises, tarte, glace]

� Liste vide : [ ]

Propriété fondamentale (1)

� La notation [X|Y] représente une liste dont la tête (le 1er élément) est X et la queue (le reste de la liste) est Y. � Cela constitue la base de l’utilisation des listes � Cela constitue la base de l’utilisation des listes

dans les programmes Prolog.� Cas général : [Tete | Queue]

≡ [Car | Cdr ] (cf. Scheme)� [a, b, c] ≡ [a | [b | [c | [ ] ] ] ]

Propriété fondamentale (2)

� Exemple de programme menu :entrees([sardine, pate, melon, avocat]).viandes([poulet, roti, steack]).poissons([merlan, colin, loup]).desserts(gateau, fruit, glace]).

� Et si on pose la question : entrees(E).

� L’effacement de ce but (synonyme de question) provoque l’affectation suivante : E= [sardine, pate, melon, avocat]

Propriété fondamentale (3)

� Nous savons donc affecter une liste à une variable.

� Nous avons aussi besoin de pouvoir considérer les éléments d’une liste de façon individuelle, par les éléments d’une liste de façon individuelle, par exemple pour récupérer un élément particulier.� Supposons que l’on dispose du prédicat :

element_de(X, L) capable d’extraire un objet X d’une liste L.

Propriété fondamentale (4)

� Nous avions :menu(X, Y, Z) :- entree(X), plat(Y), dessert(Z).plat(X) :- viande(X).plat(X) :- poisson(X).

Avec la nouvelle déclaration commune des entrées � Avec la nouvelle déclaration commune des entrées comme liste, ce programme échouera. Il faut donc le modifier.

� Pour cela nous allons construire une nouvelle définition du prédicat entree (ne pas confondre avec le prédicat entrees qui définit la liste des entrées).

Propriété fondamentale (5)

� On utilise la propriété suivante : si X est une entrée, alors X est un élément quelconque de la liste des entrées. On peut donc écrire :

entree(X) :- entrees(E), element-de(X, E).

� Et de façon analogue :viande(X) :- viandes(V), element-de(X, V).poisson(X) :- poissons(P), element-de(X, P).dessert(X) :- desserts(D), element-de(X, D).

Unification de listes

[T|Q] = [1, 2, 3, 4]. ?[X,Y] = [1, 2]. ?[X,Y] = [1, 2, 3]. ?[X,Y | Z] = [1, 2, 3]. ?[X,Y | Z] = [1, 2]. ?

Unification de listes

[T|Q] = [1, 2, 3, 4][X,Y] = [1, 2]

T = 1, Q = [2, 3, 4]X = 1, Y = 2

[X,Y] = [1, 2, 3][X,Y | Z] = [1, 2, 3][X,Y | Z] = [1, 2]

No (échec)X = 1, Y = 2, Z = [3] X = 1, Y = 2, Z = []

Accès aux éléments d’une liste� Il s’agit de rechercher les règles qui vont assurer le

fonctionnement du prédicat element-de(X, L) qui signifie que X est l’un des éléments de L.� On utilise la remarque selon laquelle toute liste peut se

décomposer simplement en deux parties, la tête et la décomposer simplement en deux parties, la tête et la queue de liste. Cela conduit à distinguer deux cas :� X est élément de L si X est la tête de L.� X est élément de L si X est élément de la queue de L.

� Ce qui se traduit directement en Prolog par :(R1) element-de(X, L) :- est-tete(X, L).(R2) element-de(X, L) :- element-de-la-queue(X,L).

R1 et R2 sont là en tant que repères et ne rentrent pas dans les règles.

Accès aux éléments d’une liste

� On sait que L peut toujours être représentée sous la forme [U|Y], ce qui nous donne :� Si X est en tête de [U|Y] alors X = U.� Si X est un élément de la queue de [U|Y] alors X est � Si X est un élément de la queue de [U|Y] alors X est

élément de Y.

� D’où la version :

(R1) element-de(X, [X|_]).

(R2) element-de(X, [U|Y]) :- X\=U, element-de(X, Y).

Accès aux éléments d’une liste

� On interprète ces deux règles de la façon suivante :� R1 : X est élément de toute liste qui commence par X.

(R1) element-de(X, [X|_]).(R2) element-de(X, [U|Y]) :- X\=U, element-de(X, Y).

� R1 : X est élément de toute liste qui commence par X.� R2 : X est élément de toute liste de queue Y, si la liste

ne commence pas par X.

� Il s’agit donc d’un appel récursif. La plupart des problèmes sur les listes ont des solutions mettant en jeu la récursivité.

Récursivité

� On observe deux types de règles et deux types d'arrêt :

Une ou plusieurs règles provoquent la récursivité,

(R1) element-de(X, [X|_]).(R2) element-de(X, [U|Y]) :- X\=U, element-de(X, Y).

� Une ou plusieurs règles provoquent la récursivité, généralement sur des données assez simples, et assurent le déroulement de l’itération. Dans notre exemple, il s’agit de la règle R2.

� Une ou plusieurs règles stoppent la séquence d’appels récursifs. Dans notre exemple, c’est R1 qui s’en charge.

� Sauf impératif contraire, les règles d'arrêt sont placées en tête.

Récursivité

� Il apparaît deux types d'arrêt :� Un arrêt explicite . Par exemple, dans R1, l'identité

entre l'élément cherché et la tête de la liste fournie, ce qu’exprime la notation X et [X|Y]

(R1) element-de(X, [X|_]).(R2) element-de(X, [U|Y]) :- X\=U, element-de(X, Y).

qu’exprime la notation X et [X|Y]� Un arrêt implicite . En particulier par la rencontre d’un

terme impossible à démontrer, par exemple:element-de(X,[]).

� Il existe cependant une forme d’erreur pour laquelle ces deux blocages se révèlent insuffisants, c’est la rencontre de listes infinies.

Construction d’une liste (1)� Nous avons vu comment parcourir une liste.� Voyons comment en construire une.

� Examinons le problème suivant : L une liste contenant un nombre pair d'éléments.contenant un nombre pair d'éléments.� Par exemple : L = [0,1,2,3,4,5]

� Cherchons à construire une nouvelle liste W en prenant les éléments de rang impair dans L.� Dans notre exemple cela donnerait : W = [0,2,4]

� Soit elements-rang-impair ce prédicat:elements-rang-impair([0,1,2,3,4,5], X).

X = [0,2,4]

Construction d’une liste (2)

� Relation de récurrence pour l’énumération des éléments de rang impair :

elements-rang-impair([X1, X2 | Y]) :- elements-rang-impair(Y).

� Règle d'arrêt : il faut s'arrêter si la liste vide :elements-rang-impair([]). elements-rang-impair([]).

� On modifie le programme de façon à construire la nouvelle liste à partir du parcours de l’ancienne. D’où le programme suivant:

(R1) elements-rang-impair([], []).

(R2) elements-rang-impair([X1, X2|Y], [X1|L]) :- elements-rang-impair(Y, L).

� Interprétation de ces deux règles : � R1 : prendre un élément sur deux de la liste vide donne la liste vide� R2 : prendre un élément sur deux dans la liste [X1, X2 |Y], donne la liste

[X1|L], si prendre un élément sur deux dans la liste Y donne la liste L.

Construction d’une liste (3)

� Ce programme est incomplet : elements-rang-impair([], []).

elements-rang-impair([X, _|Y], [X|L]) :- elements-rang-impair(Y, L).

� Exemples d’exécution :Exemples d’exécution :?- elements-rang-impair([a,b,c,d],L).L = [a, c]

?- elements-rang-impair([a,b,c],L).false

� Pourquoi cet échec ? : ⇒ Le cas des listes à nombre impair d’éléments n’est pas traité !

Construction d’une liste (4)� D’où le programme final suivant :

elements-rang-impair([], []).

elements-rang-impair([X], [X]).

elements-rang-impair([X, _|Y], [X|L]) :- elements-rang-impair(Y, L).

� Règle introduite : si une liste est formée d’un seul élément X, la liste résultat est cette liste [X].résultat est cette liste [X].

� Exemples d’exécution :?- elements-rang-impair([a,b,c,d],L).

L = [a, c]

?- elements-rang-impair([a,b,c],L).

L = [a, c]

� Remarque : les éléments dans la liste résultat sont rangés dans le même ordre que dans la liste initiale.

Construction d’une liste (5)� Construction d’une liste au moyen d’une liste

auxiliaire :Problème : Ecrire un prédicat inverser qui inverse l’ordre

des éléments d’une liste donnée. � Soit D une liste données, R est la liste D inversée. � On est dans une situation différente la précédente à cause de

l’ordre inverse des éléments. Nous allons introduire une liste auxiliaire pour y ranger les éléments énumérés au fur et à mesure de leur parcours.

� Le prédicat inverser aura donc 3 arguments:(1) la liste à inverser, (2) la liste auxiliaire, (3) la liste inversée

Construction d’une liste (6)� On obtient les règles suivantes :

inverser([], L, L).inverser([X|Y], L, R) :- inverser(Y, [X|L], R).

� Les 2 premiers arguments sont consultés, le troisième est élaboré� Au lancement, la liste auxiliaire est vide : inverser([a,b,c],[],R).� L’élément qui apparaît en tête de la liste est retiré et placé en tête � L’élément qui apparaît en tête de la liste est retiré et placé en tête

de la liste auxiliaire. Il y a donc inversion de l’ordre des éléments� Après le parcours de la liste donnée, L et R sont identiques.

� Interprétation de ces deux règles :� Inverser la liste vide, à partir de la liste auxiliaire L, donne la liste

résultat L.� Inverser la liste [X|Y], à partir de la liste auxiliaire L, donne la liste

résultat R, si inverser la liste Y, à partir de la liste auxiliaire [X|L], donne cette même liste R.

Construction d’une liste (7)

� Si l’on souhaite disposer d’un prédicat inverser/2 qui ne mentionne que les listes donnée et résultat, on peut introduire le prédicat suivant :

inverser(L,R) :- inverser(L,[],R).

inverser([], L, L).inverser([], L, L).inverser([X|Y], L, R) :- inverser(Y, [X|L], R).

� Exécution :?- inverser([a,b,c], [], R).R = [c, b, a]

?- inverser([a,b,c],R).R = [c, b, a]

Listes et sous-listes

� Dans certaines situations, il peut être intéressant de structurer une liste en sous-listes

� Exemple du programme menu :� Volonté de poursuivre le regroupement des données.� Liste unique qui regrouperait tous les mets du menu� Liste unique qui regrouperait tous les mets du menu

L= [sardine, poulet, … , glace]

� Cette représentation n’est pas adéquate car il n’y a pas de distinction entre entrée, plat ou dessert.

� Il est donc nécessaire de découper la liste en sous-listes qui rassembleront les entrées, plats et desserts.

� Cela nous donne la structure suivante :L = [ [sardines, pate, melon, celeri], [poulet, roti, steack],

[merlan, colin, loup], [fraises, tarte, glace] ]

L est de la forme : [Entrées, Viandes, Poissons, Desserts]

La sous-liste des plats est elle-même divisée en

Listes et sous-listes

� La sous-liste des plats est elle-même divisée en deux parties, les viandes et les poissons :

L = [ [sardines, pate, melon, celeri], [ [poulet, roti, steack], [merlan, colin, loup] ], [fraises, tarte, glace] ]

L est de la forme : [Entrées, Plats, Desserts]

Parcours d’une liste

� Cas de base :parcours([],v). v = valeur associée à la liste vide� Cas général :Parcours([T|Q],R):- parcours(Q,RI), R is f(RI,T).

R est calculé à partir de RI et de TExemple : somme des éléments d’une listesomme([], 0). somme([T|Q], S) :- somme(Q, Sq), S is T + Sq.

Construction d’une liste à partir d’une liste

Généralisation de l’exemple de l’inversion d’une liste

codeverslettres([],[]).codeverslettres([Code|L],[Lettre|R]):- name(Lettre,[Code]), codeverslettres([Code|L],[Lettre|R]):- name(Lettre,[Code]),

codeverslettres(L,R).

L’ordre des éléments de la liste produite correspond à l’ordredes éléments de la liste de départ.

Construction d’une liste à partir d’une liste : solution avec « accumulateur »

Principe: la liste est construite pendant les appels récursifs. Il s’agit d’introduire un argument supplémentaire correspondantà une liste « accumulatrice »

Nous avons déjà utilisé ce principe de construction pour Nous avons déjà utilisé ce principe de construction pour inverser une liste.� à l’appel initial, la liste accumulatrice vaut la liste vide: []

� à chaque appel récursif on ajoute des éléments à la liste construite

� en fin de parcours, la liste construite (« accumulée ») constitue le résultat du calcul.

Construction d’une liste à partir d’une liste : solution avec « accumulateur »Exemple : construire le prédicat chaine_invers_liste qui

transforme une chaine de caractères en sa liste de lettres inversée.

?- chaine_invers_liste("hello", L).L = [o, l, l, e, h].

Rappel: une chaine entre " est une liste de codes ascii :Rappel: une chaine entre " est une liste de codes ascii :?- L="hello".L = [104, 101, 108, 108, 111]

Prolog fournit le prédicat name/2 qui convertit une chaine (liste de codes) en atome ou inversement un atome en une liste de codes :

?- name(hello,L).

L = [104, 101, 108, 108, 111].

?- name(L,"hello").

L = hello.

Construction d’une liste à partir d’une liste : solution avec « accumulateur »

Nous allons utiliserRappel: une chaine entre " est une liste de codes ascii :

chaine_invers_liste(CH,L):- chaine_invers_liste(LC,[],L).

chaine_invers_liste([],LAcc,LAcc).

chaine_invers_liste([Code|L],LAcc,R):- name(Lettre,[Code]), chaine_invers_liste (L,[Lettre|LAcc],R).

Grâce à la liste auxiliaire, l’ordre des lettres est inversé

Quelques prédicats prédéfinis sur les listes� Dans la documentation Prolog :

- les arguments consultés sont précédés d'un +- les arguments élaborés sont précédés d'un -- les arguments qui peuvent être soit consultés, soit élaborés (suivant le sens de l'unification) soit élaborés (suivant le sens de l'unification) sont précédées d'un ?Exemple : numlist(+Min, +Max, -List).

?- numlist(2,8, L). L = [2, 3, 4, 5, 6, 7, 8]

Concaténation : append� append est le prédicat prédéfini pour la concaténation de

listes : append(?List1, ?List2, ?List3).?- append([a,b,c],[d,e],L).L = [a, b, c, d, e]

� append est complètement symétrique et peut donc être utilisé pour d’autres opérations :� Trouver tous les découpages d’une liste en 2 sous-listes:

?- append(L1,L2,[a,b,c,d]).L1 = [], L2 = [a, b, c, d] ;L1 = [a], L2 = [b, c, d] ;L1 = [a, b], L2 = [c, d] ;L1 = [a, b, c], L2 = [d] ;L1 = [a, b, c, d], L2 = []

append : autres utilisations possibles

� Trouver le dernier élément d’une liste :?- append(_,[X],[a,b,c,d]).X = d

� Couper une liste en sous-listes :?- append(L2,L3,[b,c,a,d,e]), append(L1,[a],L2).?- append(L2,L3,[b,c,a,d,e]), append(L1,[a],L2).L2 = [b, c, a]L3 = [d, e]L1 = [b, c]

Quelques prédicats prédéfinis sur les ensembles (listes sans doublons)

list_to_set(+List, -Set).transforme List en un ensemble Set (suppr doublons)

subset(+Subset, +Set).Subset ⊂ Set

intersection(+Set1, +Set2, -Set3).Set3 = Set1 ∩ Set2Set3 = Set1 ∩ Set2

union(+Set1, +Set2, -Set3).Set3 = Set1 ∪ Set2

subtract(+Set, +Delete, -Rest).Rest = Set - Delete

merge_set(+Set1, +Set2, -Set3). Set3 = fusion de Set1 et Set2

(Set1, Set2 et Set3 sont des ensembles triés)sort(+List, -SetTrié).

transforme List en un ensemble trié SetTrié

maplist : application d’un prédicat à tous les éléments d’une liste

Les prédicats maplist appliquent un prédicat sur tous les membres d'une liste ou jusqu'à ce que le prédicat échoue.

maplist(+Pred,+List). Pred est d’arité 1?- maplist( integer, [15,8,5,6,9,4] ).true

maplist(+Pred, ?List1, ?List2). Pred est d’arité 2maplist(+Pred, ?List1, ?List2). Pred est d’arité 2maplist( <(3), [15,8,5,6,9,4] ). true?- maplist(double, [3,4,6], L).L = [6, 8, 12] avec : double(X,D):- D is X*2.

maplist(+Pred, ?List1, ?List2, ?List3). Pred est d’arité 3maplist(plus, [0, 1, 2], [4, 8, 16], L). X = [4, 9, 18]avec : plus(?Int1, ?Int2, ?Int3) Int3 = Int2 + Int1

Liste des solutions d'un prédicat

� Les prédicats findall/3, bagof/3 et setof/3 permettent de faire la liste des solutions d'un prédicat.

� findall(+Motif, +But, -Liste).� Trouve toutes les solutions de But et en fait une Liste selon le

modèle Motifmodèle Motif

� bagof(+Motif, +But, -Liste).� Trouve toutes les solutions de But (par groupes), échoue si

But n'a pas de solution

� setof(+Motif, +But, -Liste).� Trouve toutes les solutions de But (par groupes), mais

supprime les doublons ; échoue si But n'a pas de solution

findall, bagof, setof : exemples (1)

� Soit le programme suivant :?- findall(C, foo(A,B,C), L). L = [c, f, d, f, f, e, g]

?- bagof(C, foo(A,B,C), L).

foo(a, b, c).foo(a, b, f).foo(a, b, d).foo(a, b, f).foo(b, c, f).foo(b, c, e).?- bagof(C, foo(A,B,C), L).

A = a, B = b, L = [c, f, d, f] ;A = b, B = c, L = [f, e] ;A = c, B = c, L = [g]

?- setof(C, foo(A,B,C), L).A = a, B = b, L = [c, d, f] ; L est ordonnéeA = b, B = c, L = [e, f] ;A = c, B = c, L = [g]

foo(b, c, e).foo(c, c, g).les variables A et B sont

unifiées. On a 3 solutions: une pour chaque couple (A,B) disctinct.

findall, bagof, setof : exemples (2)?- bagof(C, A^foo(A,B,C), L).

B = b, L = [c, f, d, f] ;

B = c, L = [f, e, g] ;

?- setof(C, A^foo(A,B,C), L).

B = b, L = [c, d, f] ;

A^ signifie “ne pas unifier A”

seule la variable B est unifiée, la variable A restant libre. On a 2 solutions: une par valeur de B différente. B = b, L = [c, d, f] ;

B = c, L = [e, f, g] ;

?- bagof(C, A^B^foo(A,B,C), L).L = [c, f, d, f, f, e, g]

?- setof(C, A^B^foo(A,B,C), L).L = [c, d, e, f, g]

foo(a, b, c).foo(a, b, f).foo(a, b, d).foo(a, b, f).foo(b, c, f).foo(b, c, e).foo(c, c, g).

de B différente.

les variables A et B ne sont pas unifiées. On n'a alors plus qu'une solution. (~ findall)