Concaténation de listes

Le prochain exemple est la concaténation de listes, représentée par le prédicat append en Prolog. Le principe est le suivant :
1. Isoler le premier élément de la liste.
2. Résoudre récursivement le prédicat pour concaténer le reste de la liste avec la seconde liste.
3. Ajouter au début de la liste résultante l’élément qui avait été isolé à la première étape.
Traduit en Prolog, le programme obtenu est le suivant :
append([],X,X).
append([X|Xs],Y,[X|Zs]):- append(Xs,Y,Zs).
Ce qui est intéressant avec ce programme est que l’unification, puisqu’elle ne fait pas de distinction entre les données et les résultats, permet différents usages du même programme :
?- append([a,b,c],[d,e],R).
R = [a,b,c,d,e]
?- append(X,[d,e],[a,b,c,d,e]).
X = [a,b,c]
?- append(X,Y,[a,b,c]).
X = []
Y = [a,b,c] ;
X = [a]
Y = [b,c] ;
X = [a,b]
Y = [c] ;
X = [a,b,c]
Y = [] ;
No
La figure 8 montre les détails de la résolution de la dernière requête. La figure 9 montre la situation au moment du premier retour arrière. Finalement, la figure 10 montre l’état au second retour arrière.

FIG. 8 – Résolution de append(X,Y,[a,b,c])
Aussi étrange que cela puisse paraître, on peut même utiliser le prédicat append avec des variables non instanciées pour les deux derniers arguments :

FIG. 9 – Résolution de append(X,Y,[a,b,c])

FIG. 10 – Résolution de append(X,Y,[a,b,c])
?- append([1,2],X,Y).
X = K
Y = [1,2|K]

6.4 Exercices
6.1 Soit les faits suivants :
suivant(a,b).
suivant(b,c).
suivant(c,d).
...
suivant(y,z).
suivant(z,a).
Écrivez un programme Prolog qui utilise ces faits pour encoder un nom en suivant l’algorithme suivant. Soit n la position d’une lettre dans l’alphabet. Chaque lettre du nom est substituée par la lettre qui est à la position n + x dans l’alphabet, où x est spécifié dans l’appel du programme. Par exemple, si x = 3, la lettre d sera substituée par la lettre g, et la lettre z par la lettre c. Le programme reçoit une liste de lettres qui représente le nom et retourne une liste de lettres qui représente le nom encodé :
?- encoder([m,i,c,h,e,l],3,X).
X = [p,l,f,k,h,o]

6.2 Soit le programme suivant :
mystere(N,Res):- magique(N,[],L), reverse(L,L2), append(L,[N|L2],Res).
magique(1,L,L).
magique(N,A,L):- N2 is N-1, magique(N2,[N2|A],L)).
a) Quel sera le résultat retourné pour la requête suivante :
?- mystere(4,L).
b) Quel sera le résultat si on demande une seconde solution ?
c) Modifiez le programme de manière à ce qu’il ne puisse pas retourner plus d’une solution.

6.3 Soit le programme suivant :
mystere(X,Y,Z):- myst1(X,Y,Z).
myst1([ ],[ ],[ ]).
myst1([X|Reste],[X|R1],R2):- myst2(Reste,R1,R2).
myst2([ ],[ ],[ ]).
myst2([X|Reste],R1,[X|R2]):- myst1(Reste,R1,R2).
a) Quel sera le résultat retourné pour la requête suivante :
?- mystere([t,b,u,e,d,m,o],X,Y).
b) Quel sera le résultat retourné pour la requête suivante :
?- mystere(X,[1],Z),
c) Quel sera le résultat si on demande une seconde solution pour la requête de b) ?
6.4 On représente une matrice n × n par une liste de listes, où chaque liste correspond à une rangée de la matrice. Soit par exemple la matrice suivante :

Voici la représentation de cette matrice :
[ [a, b, c],
[d, e, f],
[g, h, i] ]
La position d’un élément de la matrice est représentée par une paire (x, y), où (0, 0) désigne le coin supérieur gauche et (n, n) le coin inférieur droit. Dans l’exemple, les éléments aux positions (0, 0) et (3, 3) sont a e i, respectivement.
Définissez en Prolog le prédicat chercher(X,Y,Matrice,Elem), qui instancie Elem avec l’élément qui se trouve à la position (X,Y) dans la matrice :
?- chercher(2,2,[[a,b,c],[d,e,f],[g,h,i]],Z).
Z = e
6.5 Soit le programme suivant :
p(X,[],[X]).
p(X,[Y|L],[X,Y|L]):-
X < Y.
p(X,[Y|L],[Y|R]):-
p(X,L,R).
a) Quel sera le résultat retourné pour la requête suivante :
?- p(5,[2,3,9],Z).
b) Quel sera le résultat si on demande une seconde solution ?

6.6 Soit l’arbre généalogique suivant :

Une manière de représenter cet arbre est une liste de termes formés par les foncteurs pere et mere.
Définissez un prédicat descendant_communqui reçoit trois arguments. Les deux premiers sont les noms de deux personnes. Le troisième est un arbre généalogique qui est représenté par une liste qui contient toutes les relations de parenté, en utilisant les foncteurs pere et mere. Par exemple :
?- descendant_commun(ana,leo,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
Yes
?- descendant_commun(pedro,jorge,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
Yes
?- descendant_commun(pedro,luis,
[pere(jorge,maria), mere(maria,leo),
mere(maria,luis), pere(pedro,ana),
mere(ana,rui), pere(leo,rui)]).
No

6.7 Supposons une représentation en Prolog d’une base de connaissances en logique propositionnelle, qui utilise les opérateurs ∧, ∨ et ¬. Ces opérateurs sont représentés par les termes fonctionnels and et or, qui prennent deux arguments, et neg, qui n’en prend qu’un seul. Un argument peut être une proposition ou une expression. Par exemple, supposons la base de connaissances suivante :
P
¬S ∧ Q
P ∨ ¬(T ∧ R)
Cette base serait représentée par la liste suivante :
[p, and(neg(s),q), or(p,neg(and(t,r)))]
Définissez un prédicat verif(F,I), où F est la liste qui représente la base de connaissances et I une interprétation, c’est-à-dire la liste des propositions vraies. La résolution doit retourner avec succès si la base est vraie selon l’interprétation I. Si une proposition se trouve dans la liste I, elle est vraie, sinon elle est considérée fausse. Voici des exemples d’exécution qui montrent comment doit se comporter le programme :
?- verif([p, and(neg(s),q), or(p,neg(and(t,r)))],[p,q]).

Yes
?- verif([p, and(neg(s),q), or(p,neg(and(t,r)))],[p,s,q]).
No

7 Interprétations déclarative et procédurale
En Prolog, il y a deux manières d’analyser un programme. La première est une interprétation déclarative, où les règles représentent un état du monde. Elles sont utilisées pour déterminer si une situation est vraie ou fausse. Le prédicat member défini auparavant est perçu de manière déclarative quand on fait une requête du type member(2, [1,2,3,4]). L’interprétation déclarative, dans ce cas, est la suivante : un élément est membre d’une liste s’il est le premier ou s’il est membre du reste de la liste.
L’autre interprétation, dite procédurale, considère les règles comme des recettes pour atteindre un certain objectif. Une règle du type A :- B,C. est comprise de la manière suivante : pour résoudre A, il faut résoudre B et ensuite C. Par exemple, le prédicat append(L1,L2,L3)suggère naturellement une interprétation procédurale : pour concaténer L1 e L2, on doit d’abord concaténer la queue de L1 avec L2, ajouter le premier élément de L1 à la tête du résultat obtenu et unifier le tout avec L3. En résumé, on a une interprétation procédurale quand on tient compte de l’algorithme de résolution de Prolog pour comprendre le programme. Entre autres, on doit alors tenir compte de l’ordre d’apparition des buts durant la résolution. D’un autre côté, on a une interprétation déclarative quand on peut comprendre un programme en faisant complètement abstraction de l’algorithme de résolution. Pour mieux comprendre ces concepts, nous allons étudier quelques exemples.
Soit le programme suivant :
plus(0,X,X).
plus(suc(X),Y,suc(Z)):-
plus(X,Y,Z).
Dans une interprétation déclarative, il est vu comme un programme qui détermine si la somme des deux premiers arguments est égale au troisième :
?- plus(suc(suc(0)),suc(suc(0)), suc(suc(suc(suc(0))))).
Yes
?- plus(suc(suc(0)),suc(suc(0)), suc(suc(0))).
No
Dans une interprétation procédurale, il peut être utilisé pour calculer la somme de deux nombres :
?- plus(suc(suc(0)),suc(suc(0)), X).
X = suc(suc(suc(suc(0))))
Étant donné qu’un clause en Prolog ne distingue pas les entrées des sorties, elle peut avoir plusieurs interprétations différentes. Par exemple, le prédicat plus peut être utilisé pour réaliser une addition, tout comme une soustraction :
?- plus(suc(suc(0)),X , suc(suc(suc(suc(0))))).
X = suc(suc(0))
Considérons maintenant le programme factoriel présenté antérieurement :
factoriel(0,1).
factoriel(X,F):- Y is X-1,factoriel(Y,Fy), F is Fy * X.
Nous avons déjà utilisé ce programme avec une interprétation procédurale. Apparemment, il permet aussi une interprétation déclarative, puisqu’il peut être utilisé pour vérifier si 4! = 24 :
?- factoriel(4,24).
Yes
Mais cela est une illusion, puisqu’en fait, dans les cas où il devrait échouer, avec la requête factoriel(3,24) par exemple, il entrera plutôt dans une boucle infinie (pourquoi ?). Pour résoudre ce problème, il faut ajouter un autre test dans la dernière clause :
factoriel(0,1).
factoriel(X,F):- X > 0, Y is X-1, factoriel(Y,Fy), F is Fy * X.
Remarquez que cette nouvelle version n’accepte pas toutes les possibilités de requête. Par exemple, on ne peut pas l’utiliser pour identifier le nombre x tel que
x! = 24 :
?- factoriel(X,24).
ERROR: Arguments are not sufficiently instantiated
^ Exception: (7) _G311 is _G239-1 ?
Le problème ici est que l’opérateur is exige qu’il n’y ait aucune variable libre à sa droite. Pour obtenir un programme qui fonctionne correctement, il faut ajouter une clause dans la définition et ajouter des tests pour déterminer si le premier argument est une variable libre :
factoriel(0,1).
factoriel(X,Y):- var(X), proc_fact(0,Y,X).
factoriel(X,F):- nonvar(X), X > 0, Y is X-1, factoriel(Y,Fy), F is Fy * X.
proc_fact(X,Y,X):- factoriel(X,Y).
proc_fact(X,Y,R):- X2 is X+1, X2 =< Y, proc_fact(X2,Y,R).
Remarquons que la seconde clause utilise un prédicat intermédiaire proc_fact, qui calcule itérativement le factoriel de tous les nombres à partir de 0, jusqu’à ce que l’on tombe sur une valeur qui correspond à l’entrée Y ou qu’on dépasse cette valeur (dans ce dernier cas, il aura échec). Pour terminer cette discussion, voyons un dernier exemple qui permet lui aussi les deux interprétations. Il s’agit du prédicat next(X,L,Y), qui réussit si Y suit immédiatement X dans la liste L. Voici le programme :
next(X,[X,N|_],N).
next(X,[_|Reste],N):- next(X,Reste,N).
On peut facilement vérifier que ce programme permet l’interprétation déclarative pour déterminer si deux éléments sont voisins dans une liste :
?- next(2,[1,2,3,4],3).
Yes
?- next(2,[1,2,3,4],4).
No
Il permet aussi toutes les combinaisons possibles d’instances pour les variables X et Y :
?- next(2,[1,2,3,4],X).
X = 3
?- next(X,[1,2,3,4],4).
X = 3
?- next(X,[1,2,3,4],Y).
X = 1
Y = 2 ;
X = 2
Y = 3 ;
X = 3
Y = 4 ;
No
Notons que les programmes n’ont pas tous une interprétation déclarative. Un bon exemple est le prédicat liste_femmes, que nous avons présenté antérieurement. L’utilisation des prédicats write et fail forcent une interprétation procédurale du programme.

8 Construction de nouvelles structures
8.1 Appariement
Un appariement entre une structure donnée et une structure produite permet la construction de cette dernière parallèlement au parcours de la structure donnée. L’idée est la suivante : pour chaque élément de la structure donnée en entrée, on produit un élément qui se retrouvera à la position correspondante dans la structure qui sera retournée comme résultat. On peut éventuellement avoir des cas où un item traité dans la structure d’entrée n’a aucun correspondant dans la structure de sortie. Il se peut aussi que l’item ait plusieurs valeurs qui lui correspondent dans la structure de sortie. L’important ici est qu’il doit y avoir un parallélisme entre les éléments de la structure d’entrée et ceux de la structure de sortie.
Exemples :
Programme pour extraire d’une liste les nombres inférieurs à une valeur fixée :
filtrer([],_,[]).
filtrer([X|R],Max,[X|R2]):- X < Max, filtrer(R,Max,R2).
filtrer([X|R],Max,R2):- X > Max, filtrer(R,Max,R2).
?- filtrer([4,10,5,0,7,3], 5, L).
L = [4,5,0,3]
Programme pour éliminer tous les nombre répétés d’une liste :
eliminer_rep([],[]).
eliminer_rep([X,X|R],L):-
eliminer_rep([X|R],L).
eliminer_rep([X|R],[X|R2]):-
eliminer_rep(R,R2).
?- eliminer_rep([1,2,2,2,3,6,7,7,10],L).
L = [1,2,3,6,7,10]
?- eliminer_rep([1,2,2,2,3,6,2,2,2,7,7,10],L).
L = [1,2,3,6,2,7,10]
Attention : voici une autre définition du prédicat eliminer_rep qui apparemment fonctionne bien mais qui est incorrecte si on veut éliminer uniquement les répétitions consécutives :
eliminer_rep([],[]).
eliminer_rep([X|R],L):- member(X,R), eliminer_rep(R,L).
eliminer_rep([X|R],[X|L]):- eliminer_rep(R,L).
Défini ainsi, le programme retirera toutes les répétitions, qu’elles soient consécutives ou non :
?- eliminer_rep([1,2,2,2,3,6,7,7,10],L).
L = [1,2,3,6,7,10]
?- eliminer_rep([1,2,2,2,3,6,2,2,2,7,7,10],L).
L = [1,2,3,6,7,10]
Programme pour construire une expression arithmétique :
const_exp(Liste,Exp):- const(Liste,Exp,[]).
const([’(’|Liste],exp(A1,Op,A2),Reste):- chercher_arg(Liste,A1,[Op|R1]),
chercher_arg(R1,A2,[’)’|Reste]).
chercher_arg([X|Reste],X,Reste):- X \= ’(’.
chercher_arg([’(’|Reste],Exp,R2):- const([’(’|Reste],Exp,R2).
?- const_exp([’(’,3,*, ’(’,4,-,a,’)’,’)’],Exp).
Exp = exp(3,*,exp(4,-,a))

8.2 Utilisation d’un accumulateur :
On utilise un accumulateur quand on ne peut pas construire une nouvelle structure parallèlement à la structure fournie en entrée, ou encore pour obtenir une récursivité plus efficace. À chaque pas, on mémorise une structure intermédiaire que l’on construit graduellement. Le programme retourne la structure construite quand il arrive à la fin du processus récursif.
Exemples :
Exemple classique de l’inversion d’une liste :
inverser(X,L):- inv(X,[],L).
inv([],L,L).
inv([X|R],L,L2):- inv(R,[X|L],L2).
?- inverser([5,4,3,2],X).
X = [2,3,4,5]
Tri par insertion :
inserer([],X,[X]).
inserer([X|R],Y,[Y,X|R]):- Y < X.
inserer([X|R],Y,[X|R2]):- Y > X,inserer(R,Y,R2).
trier(L,Lord):-tri_ins(L,[],Lord).
tri_ins([],L,L).
tri_ins([X|R],L,Lord):-inserer(L,X,L2),tri_ins(R,L2,Lord).
?- trier([3,7,5,9,10,2],X).
X = [2,3,5,7,9,10]

8.3 Autres exemples :
Évaluation d’une expression arithmétique :
eval(X,_,X):-number(X).
eval(X,Env,Val):-atom(X),
member([X,Val],Env).
eval(exp(X,Op,Y),Env,Val):-eval(X,Env,X1),
49
eval(Y,Env,Y1),
apply(Op,X1,Y1,Val).
apply(+,X,Y,Val):- Val is X+Y.
apply(-,X,Y,Val):- Val is X-Y.
apply(*,X,Y,Val):- Val is X*Y.
apply(/,X,Y,Val):- Val is X/Y.
?- eval(exp(3,*,exp(4,-,a)),[[a,2],[b,8]],X).
X = 6
Pour évaluer une expression, le programme reçoit deux structures. L’une est l’expression, qui peut contenir des constantes qui ne sont pas des nombres mais qui représentent plutôt des variables (ne pas confondre avec des variables Prolog). L’autre est une liste qui indique la valeur associée à chaque "variable" que contient l’expression.
Remarque : Dans cet exemple, on utilise les prédicat pré-définis (voir la section 15, qui décrit ces prédicats) number(X) et atom(X).
Voici un programme pour extraire d’une liste les éléments qui suivent immédiatement un élément spécifié :
sousliste_apres(X, [X|Reste], Reste).
sousliste_apres(X,[_|Reste], R):-
sousliste_apres(X,Reste,R).
?- sousliste_apres(4,[1,2,3,4,5,3,2,1],L).
L= [5,3,2,1]
Le problème avec ce programme est que si un élément apparaît deux fois, nous aimerions que la liste retournée soit celle qui suit la dernière occurrence de cet élément :
?- sousliste_apres(3,[1,2,3,4,5,3,2,1],L).
L= [2,1]
Pour obtenir ce comportement, il faut modifier le programme, en utilisant le prédicat pré-défini \+, qui représente la négation (voir la section 12.3) :
sousliste_apres(X, [X|Reste], Reste):- \+ member(X,Reste).
sousliste_apres(X,[_|Reste], R):- sousliste_apres(X,Reste,R).

8.4 Exercices
8.1 Écrivez un programme pour dupliquer les éléments d’une liste :
?- dupliquer([a,c,f],X).
X = [a,a,c,c,f,f]
8.2 Soit un programme pour calculer la somme d’une liste de nombres :
?- somme([3,7,9],X).
X = 19
a) Écrivez une version récursive de ce programme qui n’utilise pas la technique de l’accumulateur.
b) Écrivez une nouvelle version qui utilise la technique de l’accumulateur.
8.3 Écrivez un programme qui reçoit une valeur et partitionne une liste, retournant une liste qui contient toutes les items qui sont inférieurs ou égaux a cette valeur, et une autre liste qui contient les nombres supérieurs à cette valeur :
?- partition([3,24,0,10,12],8,X,Y).
X = [3,0]
Y = [24,10,12]
8.4 Écrivez un programme qui détermine si une liste est une sous-liste d’une autre
liste :
?- sousliste([a,f],[w,z,a,f,u]).
Yes
?- sousliste([a,u],[w,z,a,f,u]).
No
8.5 Écrivez un programme qui détermine si tous les éléments d’une liste sont inclus dans une autre liste :
?- inclus([a,u],[w,z,a,f,u,h]).
Yes
?- inclus([a,k],[w,z,a,f,u,h]).
No
8.6 Écrivez un programme qui traduit en français une liste de mots en anglais et vice-versa :
?- traduire([i,eat,an,orange],P).
P = [je,mange,une,orange]
?- traduire(E,[je,suis,ici]).
E = [i,am,here]
*8.7 Modifiez le programme précédent pour traiter les cas où un mot correspond à plus d’un mot dans l’autre langue :
?- traduire2([paul,will,go,to,montréal],F).
P = [paul,ira,à,montréal]
?- traduire2([paul,talked,to,robert],F).
P = [paul,a,parle,à,robert]
?- traduire2(E,[je,cherche,la,salle,de,bain]).
E = [i,am,looking,for,the, bathroom]
8.8 Écrivez une programme qui concatène une liste de listes :
?- concatener([[a,b],[c,d,e],[f,g]],L).
L = [a,b,c,d,e,f,g]
?- concatener([[],[1,2]],L).
L = [1,2]
?- concatener([[],[]],L).
L = []
?- concatener([],L).
L = []
*8.9 Écrivez un programme qui effectue un tri par sélection.
8.10 Écrivez un programme qui reçoit une liste et qui retourne une liste ne contenant que les éléments qui se retrouvent plus d’une fois dans la liste fournie :
?- elem_repetes([a,b],L).
L = []
?- elem_repetes([a,a,b],L).
L = [a]
?- elem_repetes([a,b,c,c,d,e,c,d,d,k,l,e],L).
L = [c,d,e]
8.11 Écrivez un programme qui intercale les éléments de deux listes. Si elles sont de tailles différentes, on complète avec les items restants dans la liste de plus grande taille.
?- intercaler([],[], L).
L = []
?- intercaler([a],[], L).
L = [a]
?- intercaler([],[1,2], L).
L = [1,2]
?- intercaler([1,2],[], L).
L = [1,2]
?- intercaler([a,b],[1,2,3,4], L).
L = [a,1,b,2,3,4]
?- intercaler([a,b,c,d],[1,2,3,4], L).
L = [a,1,b,2,c,3,d,4]
8.12 Écrivez un programme qui aplatit une liste pouvant contenir un nombre indéfini de listes imbriquées. (essayez d’écrire une version efficace qui n’utilise pas le prédicat append) :
?- aplatir([1,2,[3,4],5],L).
L = [1,2,3,4,5]
?- aplatir([1,2,[],[2,[6,7,[10]]]], L).
L = [1,2,2,6,7,10]
?- aplatir([[[]]], L).
L = []
8.13 Écrivez un programme qui reçoit une liste et qui retourne une liste de paires, où chaque paire indique le nombre de fois qu’un élément apparaît dans la liste. (indice : essayez d’utiliser un accumulateur et le prédicat num_occ de la section 9) :
?- num_app([a,b,a,d,c,c,a,d],L).
L = [[c,2],[d,2],[b,1],[a,3]]
8.14 Modifiez le programme de l’exercice 3.2 pour obtenir le chemin qui permet de sortir d’une salle :
connexe(salle1,salle2).
connexe(salle2,salle4).
connexe(salle4,exterieur).
connexe(salle5,salle1).
connexe(salle5,exterieur).
connexe(salle6,salle3).
connexe(salle3,salle7).
connexe(salle7,salle6).
?- sortir(salle1,Chemin).
Chemin = [salle1, salle2, salle4]
?- sortir(salle3,Chemin).
No
8.15 Transformez le programme factoriel de la section 6 en utilisant la technique de l’accumulateur.
8.16 Soit un programme qui retourne la valeur maximale d’une liste de nombres.
a) Écrivez une version récursive de ce programme qui n’utilise pas la technique de l’accumulateur.
b) Écrivez une version qui utilise la technique de l’accumulateur.

9 Ordre des clauses
Un aspect important à ne pas oublier, quand on programme en Prolog, est l’ordre des clauses. Cet ordre détermine quelle sera la première solution retournée. Voyons, par exemple, l’utilisation de member avec une variable libre comme premier argument :
member(X,[X|_]).
member(X,[_|Y]):-
member(X,Y).
?- member(Z,[a,b,c]).
Z = a ;
Z = b ;
Z = c ;
No
Si on inverse l’ordre des clauses, l’ordre des solutions retournées est aussi inversé :
member(X,[_|Y]):-
member(X,Y).
member(X,[X|_]).
?- member(Z,[a,b,c]).
Z = c ;
Z = b ;
Z = a ;
No
Dans d’autres cas, l’ordre peut faire en sorte que le processus récursif ne s’arrête jamais :
append([X|Xs],Y,[X|Zs]):-
append(Xs,Y,Zs).
append([],X,X).
?- append(X,[1,2],Y).
... (boucle infinie)
Finalement, si l’ordre est incorrect, on peut obtenir des réponses erronées. Supposons que nous voulons écrire un programme qui calcule le nombre de fois qu’un élément apparaît dans une liste. Le programme correct est le suivant :
num_occ(_,[],0).
num_occ(X,[X|Reste],Num):-
num_occ(X,Reste,N),
Num is N + 1.
num_occ(X,[_|Reste],Num):-
num_occ(X,Reste,Num).
?- num_occ(b,[a,b,f,b,f,k,b,a],X).
X = 3
La première classe traite le cas de la liste vide. La seconde traite le cas où l’élément recherché est le premier de la liste. Dans ce cas, on résout récursivement le prédicat avec le reste de la liste et on retourne le résultat obtenu + 1. Finalement, si on n’a affaire à aucun de ces cas, on résout récursivement le prédicat et on retourne la valeur obtenue.
Voyons maintenant le même programme, mais avec les deux dernières clauses inversées :
num_occ(_,[],0).
num_occ(X,[_|Reste],Num):- num_occ(X,Reste,Num).
num_occ(X,[X|Reste],Num):-num_occ(X,Reste,N),Num is N + 1.
Si on se limite à une interprétation déclarative, les deux programmes sont équivalents. Par contre, ce n’est pas du tout le cas, si on considère l’interprétation procédurale, où l’ordre des clauses est pris en compte. On obtient tout simplement une réponse erronée :
?- num_occ(b,[a,b,f,b,f,k,b,a],X).
X = 0
La raison de ce comportement est que la seconde clause réussit toujours lorsque la liste n’est pas vide. Alors, le processus récursif se poursuit toujours avec la deuxième clause, jusqu’à qu’on atteigne la condition d’arrêt représentée par la première clause.
Remarque : Le programme, même avec l’ordre correct des clauses, retourne de nouvelles solutions erronées, si on force le retour arrière :
?- num_occ(b,[a,b,f,b],X).
X = 2 ;
X = 1 ;
X = 1 ;
X = 0 ;
No
Essayons de comprendre pourquoi on obtient ces réponses erronées. D’abord, voici la situation lorsque la première solution est retournée (les points de choix sont toujours indiqués en italique) :

Pour fournir la seconde solution, l’interpréteur Prolog recule au dernier point de choix : le but num_occ(b,[b],Num2), qui peut être unifié avec la dernière clause. La suite de la résolution nous amène donc au résultat suivant :

Svp je veux la correction de ces exercices