Programmation Prolog

Cet article est dédié à la mémoire de John Vlissides (1961-2005).

pcaboche

Dans cet article, nous présentons la programmation en Prolog à l'aide de motifs de programmation (sur le principe que les « Design Patterns » du Gang des Quatre, mais adaptés à la programmation en Prolog). ♪

- Titre : Programmation Prolog

- Auteur : pcaboche

- Parution : 11 avril 2006

- Licence : Copyright ® 2006 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- À qui s'adresse cet article ?

- Introduction

- I. Motifs de base

- Pattern 1 : Élimination des cas d'erreur

- Pattern 2 : Exécution dirigée

- Pattern 3 : Énumération de solutions

- Utilisation

- II. Autre motif

- Pattern 4 : Génération de listes

À qui s'adresse cet article ?

Cet article s'adresse :

- aux débutants, voulant apprendre rapidement certaines techniques de programmation en Prolog ;

- aux personnes plus expérimentées, souhaitant découvrir de nouvelles techniques et une nouvelle approche de la programmation en Prolog.

Introduction

Aux alentours de 1994, Erich Gamma, Richard Helm, Ralph Johnson et John Vlissides publient le livre Design Patterns: Elements of Reusable Object-Oriented Software (aussi connu sous le nom de Gang of Four book). Ce livre fut à l'origine d'une petite révolution dans le domaine de la programmation orientée objet puisqu'il présentait une manière de concevoir des logiciels au moyen de « Design Patterns » (motifs de conception): des diagrammes de classes que l'on peut combiner entre eux de manière à obtenir une application cohérente.

L'idée fondamentale derrière les Design Patterns est la réutilisation des techniques de conception ayant fait leurs preuves. Ainsi, chaque Pattern est accompagné d'une description, d'une discussion sur les cas favorables à son utilisation, de plusieurs exemples d'implémentation, etc.

C'est ce principe qui est repris ici, mais adapté à la programmation Prolog. Le but de donner aux programmeurs Prolog des idées sur la manière d'écrire un programme Prolog (et de concevoir les différents prédicats).

Les Designs Patterns du GoF (Gang of Four) étaient au départ au nombre de 23. Depuis, de nombreux autres motifs sont apparus dans le domaine de la programmation Orientée-Objets. Les Design Patterns ont également donné naissance à d'autres « langages de motifs » (Pattern Languages) dans des domaines différents (dont celui-ci, sur la programmation en Prolog). Historiquement, les Design Patterns eux-mêmes ont été inspirés par les travaux de Christopher Alexander dans le domaine de l'architecture…

Les motifs de programmation Prolog sont (pour l'instant) au nombre de 4. Pourquoi si peu de motifs, vous demandez-vous? Parce que nous ne présentons que des motifs réellement utilisés (et réutilisables) au sein de projets Prolog. Nous ne « fabriquons » pas de motifs pour « faire du remplissage » (ou faire parler de nous). Ce n'est qu'avec le temps et au travers de divers projets que de nouveaux motifs peuvent émerger.

Ces motifs sont classés comme suit :

- trois motifs « de base », permettant d'écrire quasiment n'importe quel programme Prolog ;

- un autre motif, facilitant l'écriture de certains prédicats.

Puisque la mode en informatique, c'est de donner des noms rigolos à tout ce que l'on invente, j'ai décidé de nommer ces motifs les PPPP ou 4P (prononcez « four Pea », pour faire plus classe) : Pcaboche Prolog Programming Patterns.

Comme disait Donald Knuth :

« The most important thing in the programming language is the name. A language will not succeed without a good name. I have recently invented a very good name and now I am looking for a suitable language. »

:-)

I - Motifs de base

La programmation en Prolog peut s'articuler autour de trois Patterns de base, décrits dans cette section.

Ces patterns ont pour but de répondre à plusieurs questions :

- comment écrire un programme même sans connaissance approfondie du langage Prolog ?

- comment structurer un programme Prolog ?

- comment utiliser le symbole « ! » ? (et comprendre au passage à quoi il sert) ;

- en résumé : apprendre à programmer en Prolog.

La plupart des programmes Prolog sont une combinaison des trois Patterns de base (sauf cas très particuliers).

Pour comprendre les deux premiers Patterns, nous allons chercher à écrire un prédicat qui génère une liste de longueur N remplie de 0.

Pattern 1 : Élimination des cas d'erreur

Le premier pattern nous permet de dire « en cas de paramètres incorrects, le prédicat échoue ».

Il se présente sous cette forme :

predicat(parametres) :-
conditon_echec,
!, fail.

Dans notre cas, la liste générée ne peut pas être de longueur négative :

Exemple

genereListeZeros(N, _) :-
N<0,
!, fail.

Ce pattern apparaît donc toujours en premier. Répétez ce pattern autant de fois que nécessaire, pour chaque cas d'erreur.

Pattern 2 : Exécution dirigée

Ce pattern va nous permettre d'exprimer des expressions du genre :

si condition_1 alors
action_1
sinon si condition_2 alors
action_2
sinon
...
fin_si

Et voici sa structure :

predicat(parametres) :-
conditon_1, !,
action_1.

predicat(parametres) :-
conditon_2, !,
action_2.

...

Dans notre exemple :

Exemple

genereListeZeros(N, []) :-
N==0,
!.

genereListeZeros(N, [0|Q]) :-
!,
N1 is N-1,
genereListeZeros(N1, Q).

Avec ce pattern, on dirige l'exécution dans une et une seule direction (pas d'énumération de plusieurs solutions), c'est pourquoi je l'ai appelé « exécution dirigée ».

On remarque ici que, comme pour tout autre langage fonctionnel, les conditions d'arrêt sont placées en premier (ici, on s'arrête dès que N=0).

Astuce d'optimisation

Lorsque vous utilisez ce pattern, pensez à mettre des cuts ( ! ) dans toutes les clauses. En effet, lorsque vous utilisez un cut, vous ne laissez pas de point de choix, donc Prolog n'est pas obligé de garder en mémoire les informations de retour-arrière, donc le programme utilise moins de mémoire !

Finalement, à l'aide des patterns 1 et 2, on obtient le prédicat suivant :

Programme final

% Elimination des cas d'erreur
genereListeZeros(N, _) :-     % Cas N<0
N<0,  !, fail.

% Execution dirigée
genereListeZeros(N, []) :-    % Cas N=0
N==0,
!.

genereListeZeros(N, [0|Q]) :-   % Les autres cas (N>0)
!,
N1 is N-1,
genereListeZeros(N1, Q).

Pattern 3 : Énumération de solutions

Le troisième pattern est utile pour l'énumération des solutions.

Sa structure est la suivante :

predicat(Entrees, Sorties) :-
...
Sorties = solution1.

predicat(Entrees, Sorties) :-
...
Sorties = solution2.

...

Pour illustrer ce pattern, nous allons vous présenter une fonction qui énumère les combinaisons possibles entre un entier et une liste (sous forme de tuples) :

Exemple

enum(X, [T|_], (X,T) ).
enum(X, [_|Q], R) :- enum(X, Q, R).

Execution :

Execution

| ?- enum(1, [1,2,3,4], R).
R = 1,1 ? ;
R = 1,2 ? ;
R = 1,3 ? ;
R = 1,4 ? ;

No

Utilisation

Lorsque l'on rédige un prédicat, on commence toujours par éliminer les cas d'erreur, s'il y en a. Ensuite, on utilise soit le Pattern 2 soit le Pattern 3 selon que le prédicat doit renvoyer une ou plusieurs solutions. Suivant ce principe, la syntaxe d'un prédicat Prolog devient :

predicat ::= pattern1* (pattern2+ | pattern3+)

Voici donc la grammaire correspondante (hautement simplifiée !) :

predicat ::=

pattern1* (pattern2+ | pattern3+)

pattern1 ::=

nomPredicat ( parametres ) :-
conditions_echec
, !, fail.

pattern2 ::=

nomPredicat ( parametres ) :-
conditions
, !,
instructions .

pattern3 ::=

nomPredicat ( parametres ) :-
instructions .

conditions_echec ::=

condition+

conditions ::=

condition*

Ces différents Patterns nous ont par ailleurs permis d'apprendre la bonne utilisation du Cut (!) et du fail.

II - Autre motif

Pattern 4 : Génération de listes

Applicabilité :

Écrire un prédicat qui retourne une liste d'éléments

Implémentation :

1. Écrire un prédicat qui retourne les éléments de la liste 1 par 1 (pattern 3) ;

2. Écrire un prédicat qui effectue un findall/3 sur le prédicat précédent.

Exemple

Le prédicat suivant (combinaisons/2) prend comme paramètre une liste de listes et retourne comme résultat la liste de toutes les combinaisons qu'il est possible d'obtenir en prenant un élément de chacune de ces listes.

%%
% Retourne les combinaisons une par une
%
combi([L|Q], [Elem|R]) :-
member(Elem, L),
combi(Q, R).

combi([], []).

%%
% Retourne la liste de toutes les combinaisons
%
combinaisons(Listes, Combis) :-
findall(C, combi(Listes, C), Combis).

Exécution

|?- combinaisons([[a,b], [c,d,e], [f]], Combis).

Combis = [[a, c, f], [a, d, f], [a, e, f], [b, c, f], [b, d, f], [b, e, f]]

Le pattern 4 est très intéressant, car il se base sur le pattern 3, ce qui lui confère une grande modularité.

Grammaire

pattern4 ::=

pattern3+

predicat_liste(Param, L) :-
findall(X, predicat(Param, X), L).

Avantages

- Prédicats très simples à écrire.

- Solution très simple à comprendre et à maintenir.

- Très modulable (les prédicats sont utilisables indépendamment l'un de l'autre, suivant le contexte).

Inconvénient

- Légèrement moins rapide qu'une solution sans findall/3 (ne devient un problème que si le prédicat utilisé dans le findall fait un usage intensif de la pile).

Conclusion

Cette implémentation se révèle extrêmement pratique dans de nombreux cas portant sur les listes et simplifie l'implémentation, la compréhension et la maintenance.