Le langage Prolog

pcaboche

Cet article a pour objectif l'apprentissage des bases du langage Prolog, nécessaires pour un apprentissage plus approfondi. Il est le point de départ de toute une série d'articles sur le langage Prolog. ♪

- Titre : Le langage Prolog

- Auteur : pcaboche

- Parution : 9 janvier 2006

- Mise à jour : 17 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

- Remerciements

- Introduction

- I. Préambule

- Où se procurer Prolog ?

- Comment installer Prolog ?

- Comment éditer un programme Prolog ?

- Comment exécuter un programme Prolog ?

- Exemples de programmes Prolog

- II. Les bases du langage

- Les commentaires

- Les variables

- Constantes et atomes

- Prédicats

- Anatomie d'un prédicat Prolog

- Unification

- Arithmétique

- Listes

- Les tuples

- Le caractère _

- Le coupe-choix, ou Cut (« ! »)

- III. Fonctionnement d'un programme Prolog

- Absence de structures itératives

- Exécution d'un prédicat Prolog

- Motifs de programmation en Prolog

- IV. Conseils pratiques

- … sur le langage

- Unification et variables libres

- L'opérateur Not (\+)

- Prédicats dynamiques et records

- L'instruction findall

- Les opérateurs en Prolog

- … sur l'environnement de développement

- Les modules

- Le danger des « consult » successifs

- V. Articles connexes

Remerciements

Je tiens à remercier les personnes suivantes: Trap D, PRomu@ld, Xo, et Pouic pour leurs remarques constructives, mais aussi et surtout à Debug pour son aide à la mise en ligne.

Introduction

Prolog est un langage utilisé dans les domaines de l'Intelligence Artificielle et la Programmation Logique avec Contraintes. Sa syntaxe et son principe de fonctionnement sont radicalement différents de langages impératifs tels que C ou Java. Le raisonnement se rapproche plus de langages fonctionnels tels que Caml ou Lisp. Pourtant, Prolog n'est pas un langage fonctionnel. Prolog est le premier langage de programmation logique.

Ne trouvant pas de didacticiel à la fois abordable pour le débutant et suffisamment avancé afin d'acquérir de bonnes bases en programmation Prolog, j'ai décidé d'en écrire un moi-même.

Dans ce didacticiel, j'ai souhaité mettre l'accent sur la programmation en Prolog proprement dite (section 3). Avant cela, nous présenterons le langage ainsi que les bases de Prolog (sections 1 et 2). Enfin, certaines notions importantes du langage seront abordées en section 4.

Le plan de ce didacticiel se présente donc ainsi :

- la première section de ce didacticiel vous présente le langage (outils, exemples de programmes) ;

- la deuxième section de ce didacticiel vous permet d'acquérir les bases du langage, notamment au niveau de la syntaxe ;

- la troisième section est la plus importante, car elle vous permettra d'apprendre réellement à programmer en Prolog, et ce à l'aide de trois patterns extrêmement simples et faciles à se rappeler ;

- la dernière section sert à approfondir les bases et à éviter certaines erreurs courantes.

I - Préambule

Où se procurer Prolog ?

Il existe différents outils pour vous permettre de programmer en Prolog.

- SWI Prolog
Possède un débogueur graphique ainsi que plusieurs solveurs de contraintes
www.swi-prolog.org

- GNU Prolog
Propose un solveur de contraintes sur domaine fini
http://gnu-prolog.inria.fr

- Sicstus Prolog (payant)
Possède des extensions en plus, dont plusieurs solveurs de contraintes
www.sics.se/sicstus

Comment installer Prolog ?

C'est simple :

apt-get install swi-prolog

apt-get install gprolog

- Sous Windows :
télécharger l'un des programmes mentionnés précédemment et l'installer.

- Sous Debian/Ubuntu : en root : apt-get install swi-prologou bien :apt-get install gprolog

- Autres distributions Linux : voir la gestion des packages pour votre distribution (RPM, emerge…) ou pour compiler à partir des sources.

Comment éditer un programme Prolog ?

C'est simple: avec votre éditeur de texte préféré !

Comment exécuter un programme Prolog ?

Lancez votre interpréteur Prolog :

swi-prolog

Chargez votre programme grâce à la commande consult :

Exécution

| ?-  consult('le_nom_de_votre_programme.pro').

Exemples de programmes Prolog

Voici quelques exemples de programmes Prolog, pour vous donner une idée :

- Hello world !

printHelloWorld :-
write('Hello world !'),
nl.

Exécution :

Exécution

| ?- printHelloWorld.
Hello world !

yes

- Somme des éléments d'une liste :

sum([], 0) :- !.
sum([T|Q], Somme) :-
sum(Q, S),
Somme is T + S.

writeSum :-
sum([1,2,3,4,5,6], S),
write(S), nl.

Exécution :

Exécution

| ?- writeSum.
21

yes

- Programmation logique :

plusGros('rhinocéros','cheval').
plusGros('cheval', 'chien').
plusGros('chien', 'chat').
plusGros('chat', 'hamster').

estPlusGros(X, Y) :-
plusGros(X, Y).

estPlusGros(X, Z) :-
plusGros(X, Y),
estPlusGros(Y, Z).

phrase(_) :-
plusGros(X, Y),
write('Le '), write(X), write(' est plus gros que le '), write(Y), nl.

phrase(_) :-
nl,
write('Donc: '), nl.

phrase(_) :-
estPlusGros(X, Y),
\+plusGros(X, Y),
write('Le '), write(X), write(' est plus gros que le '), write(Y), nl.

phrases :-
findall(X, phrase(X), _).

Exécution :

Exécution

| ?- phrases.
Le rhinocéros est plus gros que le cheval
Le cheval est plus gros que le chien
Le chien est plus gros que le chat
Le chat est plus gros que le hamster

Donc:
Le rhinocéros est plus gros que le chien
Le rhinocéros est plus gros que le chat
Le rhinocéros est plus gros que le hamster
Le cheval est plus gros que le chat
Le cheval est plus gros que le hamster
Le chien est plus gros que le hamster

yes

Bravo, vous avez installé Prolog et exécuté vos premiers programmes !
Maintenant, nous allons apprendre les bases du langage…

II - Les bases du langage

Cette section vous permet d'acquérir les bases du langage, nécessaires pour comprendre la section suivante (la programmation).

Les commentaires

Les commentaires en Prolog se présentent sous deux formes :

- les commentaires multilignes, comme en C, compris entre /* et */

/* Ceci est un commentaire sur
plusieurs lignes */

- les commentaires sur une seule ligne, introduits par le symbole %

% Un commentaire en fin de ligne

Les variables

En Prolog, les variables sont représentées par un identificateur commençant par une lettre majuscule (exemple: X, Machin, Liste…).

Tant qu'on n'affecte pas de valeur à une variable, on parle de « variable libre ». Une fois qu'une valeur est affectée, on parle de « variable liée ». On affecte une valeur une variable par ce que l'on appelle le principe d'« unification ».

En Prolog, une fois qu'une valeur est affectée à une variable, on ne peut plus en changer (sauf dans le cas des mutables, mais nous n'en parlerons pas ici). Pour effectuer de nouvelles opérations, il faut déclarer une nouvelle variable et lui affecter une nouvelle valeur.

Constantes et atomes

Une constante commence toujours par une lettre minuscule (ex. : jean, belfort, celibataire…). Il est également possible de définir des chaînes de caractères en les entourant de guillemets simples (ex. : 'Le lièvre et la tortue', 'Le Seigneur des Anneaux'…). Constantes et chaînes constituent des atomes.

Prédicats

En Prolog, on ne parle pas de fonction, mais de « prédicat ». Un prédicat s'organise en « clauses ».

Une clause ne retourne pas de valeur: soit elle s'exécute, soit elle échoue. On affecte les valeurs des variables passées en paramètres par « unification ». Par convention, les variables en entrée sont placées à gauche et les variables en sortie sont placées à droite, mais l'unification peut se faire dans les deux sens.

Voici un exemple de prédicat (1 clause) :

habite(jean, belfort).

Cette clause exprime la phrase « Jean habite à Belfort ».

L'opération :

Exécution

| ?- habite(jean, Ville).

nous renvoie :

Ville = belfort ?

Inversement, l'opération :

Exécution

| ?- habite(Personne, belfort).

nous renvoie :

Personne = jean ?

Comme vous avez pu le remarquer, l'unification peut se faire dans les 2 sens. Après exécution d'une clause (réussie ou non), Prolog revient dans l'état précédent l'exécution de la clause et évalue la clause suivante, si elle existe (mécanisme de « backtracking », ou « retour sur trace » en français). Ce mécanisme permet l'énumération de solutions. Exemple (5 clauses) :

habite(jean, belfort).
habite(lucie, paris).
habite(christian, toulouse).
habite(adeline, paris).
habite(nicolas, paris).

L'opération :

Exécution

| ?-  habite(Qui, paris).

Retourne :

Qui = lucie ? ;
Qui = adeline ? ;
Qui = nicolas ? ;

No

(il faut appuyer sur la touche ';' pour passer d'une solution à l'autre)

Maintenant, on force l'échec de la clause habite(adeline, paris). par l'utilisation du mot-clef fail. :

habite(jean, belfort).
habite(lucie, paris).
habite(christian, toulouse).
habite(adeline, paris) :- fail.
habite(nicolas, paris).

L'opération :

Exécution

| ?-  habite(Qui, paris).

Retourne :

Qui = lucie ? ;
Qui = nicolas ? ;

No

Une clause est généralement composée de plusieurs buts, séparés par des virgules (qui constituent ce que l'on appelle le « corps » de la clause) :

memeVille(X, Y) :-
habite(X, VilleX),
habite(Y, VilleY),
X \= Y,
VilleX == VilleY.

Si l'un des buts échoue, la clause échoue et les buts suivants ne sont pas évalués. Si l'exécution se fait jusqu'au bout, la clause réussit et le prédicat renvoie une solution (par unification).

Un prédicat est identifié à la fois par son nom et par le nombre de ses arguments. Ainsi, le prédicat predicat/2 (2 arguments) est fondamentalement différent du prédicat predicat/3 (3 arguments). Le nombre d'arguments s'appelle l'« arité ».

Anatomie d'un prédicat Prolog

Le diagramme suivant résume ce qui a été dit précédemment :

Voici un récapitulatif des définitions importantes :

- un prédicat est caractérisé par son nom et son arité, représenté par la notation prédicat/arité ;

- l'arité est le nombre de paramètres que compte un prédicat ;

- un prédicat est généralement composé d'une tête et d'un corps ;

- la tête est l'ensemble des paramètres du prédicat ;

- le corps est composé de buts ;

- les buts sont le plus souvent séparés par des virgules (opérateur de conjonction entre les buts).

Bon à savoir

Dans la documentation Prolog :
- les paramètres en entrée sont précédés d'un + ;
- les paramètres en sortie sont précédés d'un - ;
- les paramètres qui peuvent être soit en entrée, soit en sortie (suivant le sens de l'unification) sont précédés d'un ?

Unification

L'unification peut se faire de plusieurs manières :

- à l'aide de l'opérateur =

habite(jean, Lieu) :- Lieu = belfort.

- au niveau des noms de variables (peut poser problème avec les variables libres, nous y reviendrons plus tard) :

memeVille(X, Y) :-
habite(X, VilleX),
habite(Y, VilleX),
X \= Y.

Arithmétique

L'opérateur = sert exclusivement à l'unification. Pour effectuer des opérations arithmétiques, il faut utiliser l'opérateur is. Les variables à droite du is doivent avoir été unifiées.

N1 is N - 1.

Les principaux opérateurs arithmétiques sont listés en fin de didacticiel.

Listes

En Prolog, on ne connait que deux choses d'une liste :

- son premier élément (la tête, ou head) ;

- le reste de la liste (la queue, ou tail).

Le parcours d'une liste se fait de manière récursive sur la queue.

La liste vide se note: [].

Une liste constituée d'au moins un élément se note [T|Q]. Ici, T représente la tête et Q représente la queue. C'est aussi grâce à [T|Q] que l'on ajoute un élément en début de liste (par unification).

Les tuples

En Prolog, il est possible d'utiliser des tuples. Un tuple est un ensemble de champs, réunis dans une seule variable. On construit un tuple de cette manière :

Jean = (jean, 25, belfort, celibataire).

Les tuples sont donc pratiques pour organiser ses données en structures, que l'on peut alors facilement passer en paramètre à un prédicat :

retourneAge( (_, Age, _, _), Age ).

Le caractère _

Lorsque, dans le corps d'une clause, on n'a pas besoin de faire référence à l'un des paramètres, on remplace celui-ci par le caractère _ .

De même, si dans une liste ou un tuple on n'a pas besoin de faire référence à l'un des éléments, on remplace celui-ci par le caractère _ .

Ce mécanisme est extrêmement intéressant, car il nous évite d'introduire des variables qui ne seront pas unifiées. En effet, l'interpréteur/compilateur Prolog signalera par des warnings toute variable du programme qui ne sera pas unifiée. De tels messages d'avertissements sont généralement le signe annonciateur d'erreurs dans le programme (faute de frappe, erreur de copier/coller), il est donc important de faire attention à de tels messages.

Si toutefois vous désirez préciser que la variable ne sera pas unifiée tout en donnant le nom du paramètre auquel elle correspond, il suffit de concaténer ce nom au caractère _ (ex. : _Liste, _Ville, etc.).

Le coupe-choix, ou Cut (« ! »)

Le coupe-choix est un mécanisme fondamental de la programmation en Prolog. Il permet, lors de l'évaluation d'une clause, d'indiquer que l'on ne souhaite pas évaluer les autres clauses pour ne garder que la clause courante. Vous comprendrez l'intérêt du Cut, et apprendrez à l'utiliser correctement dans la section suivante.

Bravo, à ce stade vous maîtrisez toutes les bases qui feront de vous un programmeur Prolog !

III - Fonctionnement d'un programme Prolog

Dans cette section, nous allons décrire les mécanismes qui régissent l'exécution d'un programme Prolog.

Absence de structures itératives

En Prolog, il n'y a pas de structures itératives telles que for, while, do … while, qui sont propres aux langages impératifs.

Par conséquent, en Prolog, toutes les fonctionnalités sont programmées de manière récursive. Ainsi, pour parcourir une liste, on examine le premier élément de la liste, puis on effectue le traitement approprié sur cet élément avant d'appeler récursivement le prédicat sur le reste de la liste. C'est de cette façon que l'on construit la liste résultat.

Si vous êtes habitué à des langages impératifs tels que C, C++, Java, Delphi ou autres, ceci est assez déroutant au début et nécessite un petit temps d'adaptation. En tout état de cause, n'essayez pas de traduire de manière littérale un programme écrit dans un langage impératif, cela est extrêmement maladroit étant donné que la logique de programmation en Prolog est radicalement différente.

Exécution d'un prédicat Prolog

Voici comment Prolog exécute un prédicat :

Prolog examine la première clause et évalue les buts qu'elle contient:

Prolog évalue le premier but. Ce but est susceptible de retourner :

1. Une solution ;

2. Plusieurs solutions ;

3. Aucune solution.

Lorsqu'un but est susceptible de retourner plusieurs solutions, on dit qu'il y a un point de choix. Le plus souvent en Prolog, on a plusieurs points de choix qui constituent ce qu'on appelle un arbre décisionnel.

Lorsqu'un but retourne au moins une solution, Prolog garde la première solution avant d'évaluer les buts suivants. Lorsqu'un but échoue (pas de solution), Prolog effectue un « retour arrière » (ou backtracking) sur le but précédent (et évalue la solution suivante, si elle existe). S'il n'y a pas de but précédent, la clause échoue.

Il arrive que Prolog rencontre l'instruction !, connue sous le nom de « cut » ou « coupe-choix ». Ce symbole signifie qu'aucun retour arrière ne sera effectué sur les buts précédant le coupe-choix. Si les buts précédents retournaient plusieurs solutions, seule la solution courante sera conservée.

Lorsque Prolog réussit à examiner tous les buts contenus dans le corps d'une clause, alors le prédicat retourne une solution.

Lorsque Prolog a fini d'évaluer une clause (qu'elle réussisse ou qu'elle échoue), Prolog examine la clause suivante, à la recherche d'autres solutions.

Ainsi :

On considère qu'il existe un OU inclusif entre les clauses d'un prédicat Prolog (disjonction).

On considère qu'il existe un ET entre les buts d'une clause. Ce « ET » est symbolisé par l'opérateur de conjonction ',' qui sépare les différents buts.

Motifs de programmation en Prolog

De manière à faciliter l'apprentissage de Prolog et à acquérir rapidement certaines techniques de programmation, j'ai écrit un article sur les motifs de programmation en Prolog : https://pcaboche.developpez.com/article/prolog/programmation_prolog/

Cet article s'adresse aussi bien aux débutants qu'aux personnes plus expérimentées.

Vous y découvrirez entre autres les techniques de base pour concevoir et écrire des prédicats Prolog aux moyens de motifs simples à mémoriser.

Bravo, vous avez maintenant compris le fonctionnement d'un programme Prolog !

Dans la section suivante, nous allons voir certaines erreurs à éviter ainsi que certains aspects de la programmation Prolog.

IV - Conseils pratiques

… sur le langage

Unification et variables libres

On présente souvent l'opération suivante :

predicat(X, X) :- ...

comme une comparaison entre les deux paramètres du prédicat. C'est faux !

En fait, ce prédicat est équivalent à :

predicat(X, Y) :- X=Y, ...

Si X et Y sont tous deux des variables liées (c'est-à-dire pour lesquelles on a affecté une valeur), alors l'opération se comportera comme une comparaison. Si en revanche l'une au moins des deux variables est libre, alors l'opération procédera à une unification entre X et Y. Ceci pose d'énormes problèmes lorsque l'on travaille sur des variables libres (par exemple, en Programmation Logique avec Contraintes)

Pour faire une comparaison sur des valeurs, il faut utiliser l'opérateur ==, l'opérateur = étant réservé à l'unification.

L'opérateur Not (\+)

L'opérateur Not (\+) permet la négation d'un prédicat.

Attention cependant, ceci n'a de sens que si les variables passées en paramètres au prédicat sont TOUTES unifiées.

En aucun cas un prédicat villesDifferentes/2 qui serait la négation de memeVille/2 ne renverrait l'ensemble des valeurs qui n'appartiendraient pas à la relation memeVille. Tout ce que le prédicat villesDifferentes/2 pourrait faire, c'est vérifier que deux personnes spécifiques habitent dans les deux villes différentes. C'est tout !

Le plus simple pour avoir la liste des personnes qui habitent dans des villes différentes est d'écrire un prédicat spécifique en adaptant le prédicat memeVille/2.

Cette erreur est courante chez les débutants.

Prédicats dynamiques et records

Prolog permet d'ajouter, d'enlever une ou toutes les clauses ou même de supprimer complètement un prédicat, et ce de manière dynamique, grâce aux prédicats assert/1, asserta/1, retract/1, retractAll/1, abolish/1 et abolish/2.

Exemple :

% Ajoute le fait que Julie habite à Lille
assert( habite(julie, lille) ).

La différence entre assert/1 et asserta/1 est que asserta/1 ajoute la clause en début de prédicat alors que assert/1 ajoute la clause en fin de prédicat (synonyme : assertz/1)

Ce mécanisme se révèle extrêmement pratique: le Prolog se comporte comme une base de données dans laquelle il est facile d'ajouter ou d'enlever des clauses en cours d'exécution (sans avoir à définir de structure de données particulière). L'avantage est que la consultation de ces clauses est extrêmement rapide, puisqu'elles font alors partie du programme. L'inconvénient est que l'ajout/suppression de ces clauses est couteux en termes de temps.

Si vous essayez de faire appel à un prédicat qui n'existe pas (ou de modifier les clauses d'un prédicat non dynamique), Prolog retournera une erreur. Il est donc nécessaire de déclarer au préalable les prédicats dynamiques comme ceci :

:- dynamic( prédicat/arité).

Exemple :

:- dynamic( habite/2 ).

Une autre manière de procéder pour avoir des relations dynamiques est d'utiliser un record. Un record associe une clef à une valeur. Ainsi il est possible de faire :

recorda( habiteLille, julie ).

pour associer Julie à la clef habiteLille. On utilise le prédicat recorded(+Clef, -Valeur) pour récupérer les valeurs associées à une clef particulière.

Cette manière de faire est beaucoup moins expressive que la précédente (on associe juste des clefs à des valeurs alors que dans l'autre cas on redéfinit des clauses) et donc ne répondra pas à tous les besoins. Elle est cependant plus rapide, car les données sont stockées en mémoire.

L'instruction findall

En Prolog, il est possible d'obtenir une liste de toutes les solutions d'un prédicat grâce au prédicat findall :

Exécution

| ?- findall(X, habite(X,paris), R).
R = [lucie,adeline,nicolas] ?

Exécution

| ?- findall((X,Y), memeVille(X,Y), R).
R = [(lucie,adeline), (lucie,nicolas), (adeline,lucie), (adeline,nicolas), (nicolas,lucie), (nicolas,adeline)] ?

Pour plus d'informations sur le prédicat findall (ainsi que sur les prédicats bagof et setof), voir cet article :
Prédicats findall, bagof et setof

Les opérateurs en Prolog

Prolog comprend de nombreux opérateurs arithmétiques, parmi lesquels :

+(X)

Plus X

-X

Moins X

X+Y

Addition

X-Y

Soustraction

X*Y

Produit

X/Y

Division (flottant)

X//Y

Division entière

X mod Y

Modulo (reste de la division entière)

float(X)

Entier le plus proche de X compris entre 0 et X

X/\Y

ET bit à bit

X\/Y

OU bit à bit

X#Y

OU EXCLUSIF bit à bit

\(X)

Inversion des bits de X (complément à 1)

X<<Y

Décalage de Y bits de X vers la gauche

X>>Y

Décalage de Y bits de X vers la droite

X=Y

Unification

X==Y

Egal

X\=Y

Différent

X<Y

Inférieur

X>Y

Supérieur

X=<Y

Inférieur ou égal

X>=Y

Supérieur ou égal

Moyen mnémotechnique : l'opérateur « Inférieur ou égal » est différent de celui du C ou Java, par exemple. Pour éviter toute confusion, il suffit de se rappeler qu'en Prolog, les opérateurs « Inférieur/Supérieur ou égal » ne forment jamais une flèche.

… sur l'environnement de développement

Les modules

Comme dans tout langage qui se respecte, il est possible d'organiser ses sources en modules et de préciser quelles fonctions sont accessibles depuis l'extérieur.

On déclare un module en ajoutant dans l'entête du fichier :

:- module(didactitiel, [habite/2]).

Le premier argument est le nom du module. Le deuxième argument est la liste de tous les prédicats accessibles par le module appelant (sous la forme prédicat/arité).

Pour appeler un module, on ajoute la ligne :

:- use_module(nomModule).

Le danger des « consult » successifs

Pour charger un programme Prolog, on utilise le prédicat consult avec comme argument le chemin d'accès du programme, sous forme d'une chaîne :

Exécution

| ?- consult('foo.pro').

Tous les prédicats sont alors évalués et on peut alors les exécuter.

Lorsque l'on développe en Prolog, on est souvent amené à modifier notre programme et donc à recharger le code source. Ce faisant, les prédicats ayant été modifiés sont remplacés par les nouveaux, alors que les autres prédicats restent en mémoire. Si un prédicat a été supprimé dans le fichier source, il reste en mémoire et les prédicats appelant semblent marcher. Il peut donc rester des traces des anciens chargements dans l'environnement de développement.

Le plus simple pour éviter ce problème est de régulièrement tester vos programmes en développement dans un environnement vierge de tout chargement antérieur.

Voilà, ce didacticiel nous a donné une bonne idée des possibilités de Prolog et a permis de
comprendre certains de ses mécanismes afin de les exploiter au mieux.

Le reste est une question de pratique !

V - Articles connexes

Programmation en Prolog

Une manière simple de programmer en Prolog à l'aide de motifs de programmation.
Accessible à tous (débutants et confirmés)

Programmation Logique avec Contraintes

Une introduction à la PLC avec un exemple simple de solveur de sudoku.

Prolog et
Algèbre Relationnelle

Une manière d'appréhender les prédicats Prolog au travers de l'algèbre relationnelle.

findall, bagof et setof

Article expliquant l'utilisation des prédicats findall/3, bagof/3, setof/3.

Tous les articles sur Prolog