Le langage 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
  
  

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.

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

Lancez votre interpréteur Prolog :

swi-prolog

Chargez votre programme grâce à la commande consult :

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

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

• Hello world !

   

  Sélectionnez

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

  Exécution :

  Exécution

  Sélectionnez

  | ?- printHelloWorld.
  Hello world !
   
  yes

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

   

  Sélectionnez

  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

  Sélectionnez

  | ?- 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 :

| ?- 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

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

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.

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.

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 :

| ?- habite(jean, Ville).

nous renvoie :

Ville = belfort ?

Inversement, l'opération :

| ?- 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 :

| ?-  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 :

| ?-  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é ».

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 ?

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.

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.

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).

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 ).

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 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.

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.

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 :

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.

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

Unification et variables libres▲

predicat(X, X) :- ...

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

L'opérateur Not (\+)▲

Prédicats dynamiques et records▲

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

:- dynamic( habite/2 ).

recorda( habiteLille, julie ).

L'instruction findall▲

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

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

Les opérateurs en Prolog▲

Les modules▲

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

:- use_module(nomModule).

Le danger des « consult » successifs▲

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