Introduction à PROLOG

Remarque préliminaire : ce support de cours correspond à un module de 20 heures, destiné à des étudiants en deuxième année d'IUT. Ce cours n'est plus maintenu...

1. Syntaxe et terminologie Prolog
• Les termes
• Les relations, ou atomes logiques
• Les clauses
• Les programmes Prolog
• Exécution d'un programme Prolog
2. Signification (sémantique) d'un programme Prolog
• Définitions préliminaires
• Dénotation d'un programme Prolog
• Signification opérationnelle
3. Les Listes
4. La coupure
• Signification operationnelle
• Les applications de la coupure
5. Quelques prédicats prédéfinis de SWI-Prolog
6. Sujets de TP
• Les listes
• Problèmes de cryptographie
• Le zèbre
• Amos Judd

 

• http://kti.ms.mff.cuni.cz/~bartak/prolog/learning.html
• http://www.cbl.leeds.ac.uk/~paul/prologbook/

 

1. Syntaxe et terminologie Prolog

1.a. Les termes

• Les variables représentent des objets inconnus de l'univers. Syntaxiquement, une variable est une chaîne alpha-numérique commençant par une majuscule (ex. Var, X, Var_longue_2) ou par un sous-ligné (ex. _objet, _21). La variable anonyme est notée ``_'' et représente un objet dont on ne souhaite pas connaître la valeur.

Attention: Une variable Prolog s'apparente plus à une variable mathématique qu'à une variable informatique. Elle représente toujours le même objet (inconnu) tout au long de sa durée de vie et ne peut pas changer de valeur.

• Les termes élémentaires (ou termes atomiques) représentent les objets simples connus de l'univers. On distingue trois sortes de termes élémentaires:
• les nombres: entiers ou flottants,
• les identificateurs (parfois appelés atomes): un identificateur est une chaîne alpha-numérique commençant par une minuscule (ex. toto, aX12, jean_Paul_2),
• les chaînes de caractères entre guillemets (ex. "Toto est \#\{@", "123").

 
• Les termes composés représentent les objets composés (structurés) de l'univers. Syntaxiquement, un terme composé est de la forme:

foncteur(t₁, ..., t_n)

ou foncteur est une chaîne alpha-numérique commençant par une minuscule, et t₁, ..., t_n sont des termes (variables, termes élémentaires ou termes composés). Le nombre d'arguments n est appelé arité du terme.

Par exemple, adresse(18,"rue des lilas",Ville) est un terme composé de foncteur adresse et d'arité 3, dont les deux premiers arguments sont les termes élémentaires 18 et "rue des lilas" et le troisième argument est la variable Ville.

De même, cons(a,cons(X,nil)) est un terme composé de foncteur cons et d'arité 2, dont le premier argument est le terme élémentaire a et le deuxième argument le terme composé cons(X,nil).

1.b. Les relations, ou atomes logiques

symbole-de-prédicat(t₁, ..., t_n )

Par exemple,

pere(toto,paul)

De même,

habite(X,adresse(12,"rue r",nice))

1.c. Les clauses

• Un fait est de la forme:

A.

ou A est un atome logique, et signifie que la relation définie par A est vraie (sans condition). Par exemple, le fait

pere(toto,paul).

indique que la relation ``toto est le père de paul '' est vraie.

Une variable dans un fait est quantifiée universellement. Par exemple, le fait

egal(X,X).

indique que la relation ``X est égal à X '' est vraie pour toute valeur (tout terme) que X peut prendre.
• Une règle est de la forme:

A₀ :- A₁ , ... , A_n.

ou A₀, A₁ , ... , A_n sont des atomes logiques. Une telle règle signifie que la relation A₀ est vraie si les relations A ₁ et ... et A_n sont vraies. A₀ est appelé tête de clause et A₁, ... , A_n est appelé corps de clause.

Une variable apparaissant dans la tête d'une règle (et éventuellement dans son corps) est quantifiée universellement. Une variable apparaissant dans le corps d'une clause mais pas dans sa tête est quantifiée existentiellement. Par exemple, la clause

meme_pere(X,Y) :- pere(P,X), pere(P,Y).

se lit: ``pour tout X et pour tout Y, meme_pere(X,Y) est vrai s'il existe un P tel que pere(P,X) et pere(P,Y) soient vrais''.

1.d. Les programmes Prolog

Chaque paquet définit un prédicat et est constitué d'un ensemble de clauses dont l'atome de tête a le même symbole de prédicat et la même arité. L'ordre dans lequel les clauses sont définies est significatif. Intuitivement, deux clauses d'un même paquet sont liées par un ou logique. Par exemple, le prédicat personne défini par les deux clauses:

personne(X) :- homme(X).
personne(X) :- femme(X).

1.e. Exécution de programmes Prolog

?- pere(toto,X), pere(X,Y).

2. Signification (sémantique) d'un programme Prolog

2.a Définitions préliminaires

Substitution :

Une substitution (notée s) est une fonction de l'ensemble des variables dans l'ensemble des termes. Par exemple,

s = { X <- Y, Z <- f(a,Y) }

est la substitution qui ``remplace'' Xpar Y, Zpar f(a,Y), et laisse inchangée toute autre variable que Xet Z.

Par extension, une substitution peut être appliquée à un atome logique. Par exemple,

s(p(X,f(Y,Z))) = p(s(X),f(s(Y),s(Z))) = p(Y,f(Y,f(a,Y)))

Instance :

Une instance d'un atome logique A est le résultat s(A) de l'application d'une substitution s sur A.

Par exemple, pere(toto,paul)est une instance de pere(toto,X).
 

Unificateur :

Un unificateur de deux atomes logiques A1 et A2 est une substitution s telle que s(A1) = s(A2).

Par exemple, soit A1 = p(X,f(X,Y)), et soit A2 = p(a,Z),

s = { X <- a, Z <- f(a,Y) }

est un unificateur de A1et A2car s(A1) = s(A2) = p(a,f(a,Y)).
 

Unificateur plus général :

Un unificateur sde deux atomes logiques A1 et A2 est le plus général (upg) si pour tout autre unificateur s' de A1 et A2, il existe une autre substitution s'' telle que s' = s''(s).

Par exemple,

s = { X <- Y }

est un upg de p(X,b)et p(Y,b), tandis que

s' = { X <- a, Y <- a }

n'est pas un upg de p(X,b)et p(Y,b).

L' algorithme de Robinson calcule un upg de deux termes, ou rend "echec" si les deux termes ne sont pas unifiables.

2.b. Dénotation d'un programme Prolog

parent(paul,jean).
parent(jean,anne).
parent(anne,marie).

homme(paul).
homme(jean).

pere(X,Y) :- parent(X,Y), homme(X).

grand_pere(X,Y) :- pere(X,Z), parent(Z,Y).

E_0 = { parent(paul,jean), parent(jean,anne), parent(anne,marie), homme(paul), homme(jean) }

E_1 = { pere(paul,jean), pere(jean,anne) }

E_2 = { grand_pere(paul,anne), grand_pere(jean,marie) }

Malheureusement, la dénotation d'un programme est souvent un ensemble infini et n'est donc pas calculable de façon finie. Considérons par exemple le programme P suivant:

plus(0,X,X).
plus(succ(X),Y,succ(Z)) :- plus(X,Y,Z).

E_0 = { plus(0,X,X) }

E_1 = { plus(succ(0),X,succ(X)) }

E_2 = { plus(succ(succ(0)),X,succ(succ(X))) }

E_3 = { plus(succ(succ(succ(0))),X,succ(succ(succ(X)))) }

2.c. Signification opérationnelle

Pour prouver un but composé d'une suite d'atomes logiques

(par exemple, But = [A_1, A_2, .., A_n]),

l'interprête Prolog commence par prouver le premier de ces atomes logiques (A_1). Pour cela, il cherche une clause dans le programme dont l'atome de tête s'unifie avec le premier atome logique à prouver

(par exemple, la clause A'_0 :- A'_1, A'_2, ..,A'_r
telle que upg(A_1,A'_0) = s)

Puis l'interprête Prolog remplace le premier atome logique à prouver (A_1) dans le but par les atomes logiques du corps de la clause, en leur appliquant la substitution (s). La nouveau but à prouver devient

But = [s(A'_1), s(A'_2), .., s(A'_r), s(A_2), .., s(A_n)]

L'interprête Prolog recommence alors ce processus, jusqu'à ce que le but à prouver soit vide, c'est à dire jusqu'à ce qu'il n'y ait plus rien à prouver. A ce moment, l'interprête Prolog a prouvé le but initial ; si le but initial comportait des variables, il affiche la valeur de ces variables obtenue en leur appliquant les substitutions successivement utilisées pour la preuve

Il existe généralement plusieurs clauses dans le programme Prolog dont l'atome de tête s'unifie avec le premier atome logique à prouver. Ainsi, l'interprête Prolog va successivement répéter ce processus de preuve pour chacune des clauses candidates. Par conséquent, l'interprête Prolog peut trouver plusieurs réponses à un but.

procedure prouver(But: liste d'atomes logiques ) 
    si But = [] alors 
        /* le but initial est prouvé */
        /* afficher les valeurs des variables du but initial */
    sinon soit But = [A_1, A_2, .., A_n]
        pour toute clause (A'_0 :- A'_1, A'_2, ..,A'_r) du programme:
            (ou les variables ont été renommées)
            s <- upg(A_1 ,A'_0)
            si s != echec alors
                prouver([s(A'_1), s(A'_2), .. s(A'_r), s(A_2), .. s(A_n)], s(But-init}))
            finsi
        finpour
    finsi
fin prouver

Remarques

• la stratégie de recherche n'est pas complète, dans la mesure ou l'on peut avoir une suite infinie d'appels récursifs,
• la stratégie de recherche dépend d'une part de l'ordre de définition des clauses dans un paquet (si plusieurs clauses peuvent être utilisées pour prouver un atome logique, on considère les clauses selon leur ordre d'apparition dans le paquet), et d'autre part de l'ordre des atomes logiques dans le corps d'une clause (on prouve les atomes logiques selon leur ordre d'apparition dans la clause).

3. Les listes

Notations:

• la liste .(X,L) est également notée [X|L] ,
• la liste .(X1, .(X2, L)) est également notée [X1, X2|L],
• la liste .(X1, .(X2, ..., .(Xn, L) ... )) est également notée [X1, X2, ..., Xn|L],
• la liste [X1, X2, X3, ..., Xn|[]] est également notée [X1, X2, X3, ..., Xn].

Une liste est une structure récursive: la liste Liste = [X|L] est composée d'un élément de tête X et d'une queue de liste L qui est elle-même une liste. Par conséquent, les relations Prolog qui ``manipulent'' les listes seront généralement définies par

• une ou plusieurs clauses récursives, définissant la relation sur la liste [X|L] en fonction de la relation sur la queue de liste L,
• une ou plusieurs clauses non récursives assurant la terminaison de la manipulation, et définissant la relation pour une liste particulière (par exemple, la liste vide, ou la liste dont l'élément de tête vérifie une certaine condition...).

4. La coupure

4.a. Signification opérationnelle de la coupure

La coupure est un prédicat sans signification logique (la coupure n'est ni vraie ni fausse), utilisée pour "couper" des branches de l'arbre de recherche.

La coupure est toujours "prouvée" avec succès dans la procédure prouver décrite au paragraphe 2.c. La "preuve" de la coupure a pour effet de bord de modifier l'arbre de recherche: elle coupe l'ensemble des branches en attente créées depuis l'appel de la clause qui a introduit la coupure.

Considérons par exemple le programme Prolog suivant:

p(X,Y) :- q(X), r(X,Y).
p(c,c1).

q(a).
q(b).

r(a,a1).
r(a,a2).

r(b,b1).
r(b,b2).
r(b,b3).

prouver([p(Z,T)])
b1 : s = {Z <- X, T <- Y}
---- prouver([q(X),r(X,Y)])
b11 : s = {X <- a}
----- prouver([r(a,Y)])
b111 : s = {Y <- a1}
------ prouver([],[p(a,a1)] --> solution1 = {Z=a, T=a1}

b112 : s = {Y <- a2}
------ prouver([]) --> solution2 = {Z=a, T=a2}

b12 : s = {X <- b}
----- prouver([r(b,Y)])
b121 : s = {Y <- b1}
------ prouver([]) --> solution3 = {Z=b, T=b1}

b122 : s = {Y <- b2}
------ prouver([]) --> solution4 = {Z=b, T=b2}

b123 : s = {Y <- b3}
------ prouver([]) --> solution5 = {Z=b, T=b3}

b2 : s = {Z <- c, T <- c1}
---- prouver([]) --> solution6 = {Z=c, T=c1}

si on définit p par
p(X,Y) :- q(X), r(X,Y), !.
p(c,c1).
Prolog donne la solution 1 puis coupe toutes les branches en attente (b112, b12 et b2).

si on définit p par

p(X,Y) :- q(X), !, r(X,Y).
p(c,c1).
Prolog donne les solutions 1 et 2 puis coupe les branches en attente (b12 et b2).

si on définit p par

p(X,Y) :- !, q(X), r(X,Y).
p(c,c1).
Prolog donne les solutions 1, 2, 3, 4 et 5 puis coupe la branche en attente (b2).

1. ?- element(L,[[a,b],[c,d,e]]), element(X,L).
2. ?- element(L,[[a,b],[c,d,e]]), element(X,L), !.
3. ?- element(L,[[a,b],[c,d,e]]), !, element(X,L).
4. ?- !, element(L,[[a,b],[c,d,e]]), element(X,L).

4.b. Les applications de la coupure

• Recherche de la première solution
• Exprimer le déterminisme
• La négation
• Le "si-alors-sinon"

 

5. Quelques prédicats prédéfinis de SWI-Prolog

Edition et chargement de programmes:

Comparaison de termes:

Arithmétique:

Expr1 =:= Expr2

Var is Expr

Entrées/Sorties:

Format peut contenir des séquences particulières permettant d'afficher des caractères spéciaux:

Format peut également contenir des séquences particulières pour inclure des éléments de la liste L. La séquence dépend de la nature de l'élement à afficher:

Par exemple, l'exécution de

writef("ceci %t l'%s %t  n et j'affiche X=%t",[est,"exemple numero",45,X])

ceci est l'exemple numero 45
et j'affiche X=toto