La récursivité, Les listes, la coupure : Notre prochain exemple de programme en Prolog vise essentiellement à approfondir notre

compréhension de la récursivité et de son emploi dans l'exploration des listes.

Ce programme s'appelle LIBRARY et se présente effectivement comme une petite bibliothèque de

prédicats utilitaires.

Avant de nous pencher plus en détail sur certains des prédicats définis dans LIBRARY, nous allons

tous les explorés, en indiquant ce qu'ils sont censés faire.

DELETE : enlève son premier argument de la liste donnée en second argument pour renvoyer en

troisième argument la liste ainsi privée d'un élément.

APPEND : concatène ses deux premiers arguments (des listes) pour former son troisième argument

(une liste aussi, bien sûr).

MEMBER : recherche si son premier argument est un élément de son second, qui est une liste.

LAST : renvoie dans son premier argument le dernier élément de son second argument, qui est une

liste.

ORDER : réussit si son premier argument précède son second dans l'ordre lexicographique, ou lui est

identique.

CARD : renvoie dans son second argument le nombre d'éléments de son premier, qui est une liste.

SPLIT : fragmente son deuxième argument, qui est une liste, en son troisième et quatrième

arguments, qui sont également tous deux des listes. La fragmentation s'opère de telle manière que tous les

éléments qui précèdent le premier argument dans l'ordre lexicographique (ou lui sont identiques) se

retrouvent dans le troisième argument, alors que tous les autres éléments se retrouvent dans le quatrième

argument.

QUISORT : trie la liste donnée en premier argument et la renvoie dans son second argument.

NTHMEMBER : renvoie dans son dernier argument le membre de son second argument (une liste),

dont la position dans la liste est donnée en premier argument.

ADD : ajoute son premier argument à son second (une liste) pour donner son troisième. L'ajout ne se

fait toutefois pas si la liste donnée en second argument contient déjà l'élément donné en premier argument.

REMDUP : enlève tous les duplicata dans son premier argument (une liste) pour donner son second

(une liste également).

Toutes ces définitions souffrent d'un grave défaut: elles sont toutes procédurales, et ne rendent pas

justice à Prolog, qui ne force pas le concepteur à déterminer à l'avance quelles seront les variables

instanciées lors de l'appel d'un prédicat.

Nous pouvons illustrer ici à l'aide du prédicat member ceci :

member(paul,[pierre,pul,jean,jacques]) renvoie true.

member(X,[pierre,paul,jean,jacques]) renvoie les solutions:

X = pierre,X = paul, X = jean, X = jacques.

MEMBER peut donc être utilisé pour tester l'appartenance d'un élément à une liste (comme le faisait

comprendre la définition que nous en avions donnée), mais également pour obtenir un à un tous les éléments

d'une liste.

De même, CARD peut être utilisé pour obtenir ou pour vérifier la longueur d'une liste:

card([pierre, paul,jean],3) renvoie true.

card([pierre,paul,jean],Longueur) renvoie Longueur = 3.

Cette grande souplesse des prédicats ne peut pas toujours être maintenue. Elle est détruite par

l'emploi de la coupure (coupe-choix, CUT), que l'on indique par un point d'exclamation (!), et qui peut

s'avérer très utile. L'effet de la coupure est d'empêcher la remontée (retour-arrière, BACKTRACKING) au-

delà (à gauche) du point marqué par la coupure. Nous allons voir comment.

On sait que l'on peut demander à Prolog de rechercher TOUTES les solutions possibles, toutes les

valeurs des variables qui satisfont un prédicat donné en but. Comment Prolog procède-t-il?

Dès qu'il a trouvé une solution, Prolog est prêt à forcer l'échec du prédicat, et à réessayer de le

satisfaire d'une autre manière. Pour ce faire, il se reporte à la dernière unification qu'il a réalisée, la défaite

(il rend libres les variables que cette unification l'avait amené à lier) et essaye d'unifier autrement (par

exemple, en considérant la clause suivante d'un prédicat donné). Pour pouvoir se reporter à cette dernière

unification, ne pas réessayer plusieurs fois les mêmes valeurs, et ne pas tomber plusieurs fois sur les mêmes

solutions, Prolog maintient un pointeur à l'endroit auquel il est arrivé dans sa lecture des clauses (qu'il

accomplit, on le sait, de haut en bas et de gauche à droite). Lorsqu'il force l'échec, Prolog REMONTE (de bas

en haut, de droite à gauche) dans son exploration des clauses, et c'est ce mécanisme qu'on appelle

REMONTEE en français et BACKTRACKING en anglais (revenir sur ses pas). Lorsque toutes les valeurs

ont été essayées, le but échoue, mais dans l'entretemps les valeurs qui satisfont le but ont été communiquées

à l'utilisateur.

Le rôle de la coupure est d'empêcher la remontée au-delà (à gauche) de la coupure. Pourquoi faire cela?

Pour diverses raisons, notamment pour empêcher Prolog de chercher des solutions qui ne nous intéressent

pas.

Considérons la définition du prédicat DELETE.

delete(_,[],[]).

delete(X,[X|R],R):-!.

delete(X,[Y|R],[Y|R2]):- delete(X,R,R2).

La première clause est la clause d'arrêt: peu importe ce que j'enlève à une liste vide, j'ai toujours une

liste vide.

La deuxième : nous dit que si l'élément à enlever est en tête de liste, il suffit de renvoyer la queue de la

liste, et le tour est joué. Pour que Prolog s'arrête de chercher des solutions, on donne comme corps à la règle

la seule coupure. Le prédicat coupure est un prédéfini. Comme but, il réussit immédiatement, et empêche la

machine abstraite de considérer d'autres solutions pour le but parent de la coupure, dans notre exemple

DELETE. La machine abstraite n'essayera plus de satisfaire d'une autre manière le but DELETE, et ne

renverra donc qu'une solution.

La troisième clause : ne sera donc essayée que si la seconde a échoué (car l'item à enlever n'était pas

en tête de liste). Dans ce cas, on maintient la tête de liste, et on essaye d'enlever l'élément de la queue de

liste, ce qui se fait en utilisant DELETE.

Donc, grâce à la coupure, seule la première occurrence de l'élément dans la liste sera retranchée. Sans

la coupure, DELETE renverrait autant de solutions qu'il y a d'occurrences de l'élément dans la liste. Chaque

nouvelle solution serait découverte lors de la remontée, lorsque Prolog essaie de re-satisfaire l'appel au

prédicat DELETE.

La coupure est assez délicate à utiliser. Il suffit de retenir que c'est un moyen d'augmenter l'efficacité

du programme, mais souvent au détriment de sa lisibilité, et de la souplesse d'emploi des prédicats qui

contiennent des coupures.

MEMBER est très souvent le premier prédicat récursif auquel on soumet le débutant en Prolog. Sa

définition est en effet extrêmement simple. Examinons-la un instant.

La première clause, qui est la clause d'arrêt, nous dit qu'un élément est membre d'une liste si c'est la

tête de cette liste. Cette propriété peut être communiquée sous forme de fait, puisque nous disposons d'un

opérateur qui divise la liste en deux parties, tête et queue. On a donc :

member(Head,[Head|Tail]).

Si l'élément n'est pas la tête, il est peut-être dans la queue. Comment explorer la queue, sinon à l'aide

de member lui-même:

member(Element,[_|Tail]) :- member(Element,Tail).

On peut rendre ce prédicat déterministe (c'est-à-dire à une seule solution) en utilisant la coupure. Il

suffit que la machine abstraite s'arrête de chercher des solutions dès qu'elle a trouvé l'élément dans la liste.

On placera donc une coupure dans la première clause, qui devient dès lors une règle:

detmember(Head,[Head|Tail]):-!. (Ne pas oublier le point après la coupure)

Detmember ne pourra pas, contrairement à member, être utilisé pour obtenir un à un tous les

éléments d'une liste, puisque la coupure empêchera la remontée dès que le premier élément aura été trouvé.

La coupure apporte donc ici un gain d'efficacité si on veut utiliser member pour tester

l'appartenance d'un élément à une liste. Mais ce gain se paie par une perte de souplesse, le prédicat ne

pouvant plus être utilisé comme générateur d'éléments de liste.

APPEND est aussi un bel exemple de prédicat récursif. On remarquera surtout le 'transfert' de la

tête de la première liste en tête de la troisième, transfert qui garantit, grâce à la récursivité, le passage

complet de la première liste en tête de la troisième. La première clause assurera le transfert de la deuxième

liste lorsque la première liste aura été entièrement parcourue.

append([],X,X).

append([U|X],Y,[U|Z]):-append(X,Y,Z).

QUISORT est la programmation en Prolog d'un des meilleurs algorithmes de tri, QUICKSORT,

algorithme dû à Hoare.

Le principe de QUICKSORT est très simple. Pour trier une liste, divisez-la en deux sous-listes, de

telle manière que la première contienne tous les éléments qui sont égaux à ou plus petits qu'un élément

arbitraire de la liste (dans quisort, on prend tout simplement l'élément de la liste auquel on a le plus

facilement accès, à savoir la tête), et la deuxième tous les éléments qui sont plus grands. Triez ensuite ces

sous-listes à l'aide de QUICKSORT. Arrêtez-vous lorsque les listes sont dégénérées au point de ne plus

contenir qu'un seul élément, ou rien du tout.

quisort([H|T],S):-

split(H,T,A,B),

quisort(A,A1),

quisort(B,B1),

append(A1,[H|B1],S),!.

quisort([],[]).

quisort([X],[X]).

split(H,[A|X],[A|Y],Z):- order(A,H),split(H,X,Y,Z).

split(H,[A|X],Y,[A|Z]):- order(H,A),split(H,X,Y,Z).

split(_,[],[],[]).

Cet algorithme est fondamentalement récursif, et sa programmation en Prolog est donc assez simple.

Voyons d'abord les clauses d'arrêt, les cas des listes dégénérées:

quisort([X],[X]).: une liste d'un seul élément est triée.

quisort([],[]).: une liste vide est également triée.

Le prédicat split accomplit la division de la liste en deux sous-listes, conformément aux conditions

exposées ci-dessus. L'élément en tête de liste est transféré vers la liste des "petits", ou vers la liste des

"grands", selon le résultat de la comparaison avec le guide de tri (la tête de la liste à trier par QUISORT).

QUISORT s'applique récursivement aux deux listes renvoyées par split, la liste des petits et la liste

des grands.

Ensuite, la liste triée est recomposée par un appel au prédicat append.

Voici à présent le programme LIBRARY dans son intégralité.