Programmation PrologDate de publication : 11 Avril 2006
Par
pcaboche (autres articles)
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 4,
mais adaptés à la programmation en Prolog).
A qui s'adresse cet article?
Introduction
1. Motifs de base
Pattern 1 : Elimination des cas d'erreur
Pattern 2 : Exécution dirigée
Pattern 3 : Enumération de solutions
Utilisation
2. Autre motif
Pattern 4: Génération de listes
|
Cet article est dédié à la mémoire de John Vlissides (1961-2005).
|
A 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-objets
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 fondammentale 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:
- 3 motifs "de base", permettant d'écrire quasiment
n'importe quel programme Prolog
- 1 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.
| "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." |
:-)
1. Motifs de base
La programmation en Prolog peut s'articuler autour de 3
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
3 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 : Elimination 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 le 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 !
|
Au final, à 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 : Enumé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 solution(s). 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.
2. Autre motif
Pattern 4: Génération de listes
Applicabilité :
Ecrire un prédicat qui retourne une liste d'éléments
Implémentation :
- Ecrire un prédicat qui retourne les éléments de la liste
1 par 1 (pattern 3)
- Ecrire 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épendemment
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.
 
|
