À 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 :
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_siEt voici sa structure :
predicat(parametres) :-
conditon_1, !,
action_1.
predicat(parametres) :-
conditon_2, !,
action_2.
...Dans notre 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 :
% 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) :
enum(X, [T|_], (X,T) ).
enum(X, [_|Q], R) :- enum(X, Q, R).Execution :
| ?- enum(1, [1,2,3,4], R).
R = 1,1 ? ;
R = 1,2 ? ;
R = 1,3 ? ;
R = 1,4 ? ;
NoUtilisation▲
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 ) :-
|
|
pattern2 ::= |
nomPredicat ( parametres ) :- |
|
pattern3 ::= |
nomPredicat ( parametres ) :- |
|
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 :
- Écrire un prédicat qui retourne les éléments de la liste 1 par 1 (pattern 3) ;
- É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).|?- 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+ |
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.