Syntaxe et structure de des données

Une syntaxe très simple (notation BNF – Backus-Naur Form -) qui repose sur la notion de terme (servant de base pour décrire les données et les programmes).

< fait > ::= < terme > .
< règle > ::= < terme > :- < termes > .
< requête > ::= < termes > .
< terme > ::= < nombre > | < atome > | < variable > | < atome > ( < termes >)
< termes > ::= < terme > | < terme > , < termes >

avec
::= peut être
| ou
< > pour les symboles non terminaux

• Un terme est donc soit une constante (qui se subdivise en nombre ou atome), soit une variable soit une structure (ou terme composé).

• A l’aide des faits et des règles, on crée donc des programmes en Prolog qui est une séquence (donc l’ordre a de l’importance) de clauses. Une clause s’est :

Une version brève …

< fait > ::= foncteur(arg₁, arg₂, …, arg_n) .
< règle > ::= tête :- corps .
< requête > ::= ?-fait

• Il est assez simple de faire tourner en rond l’interpréteur Prolog. Par exemple avec :
p :- p.
?- p.

Un peu plus subtil ; en principe on peut appeler une règle de plusieurs façons (e.g, frere(jean,V) ou frere(B,anne)) mais il arrive que l’interpréteur réponde que sous une seule forme et que pour l’autre il tourne en rond.

1. Constantes, variables, structures

• Prolog possède des constantes qui se subdivisent en atomes et nombres. Les atomes comprennent les noms (roi, jules, marie05, nil), les symboles (comme « :- » ou « + ») et les chaînes de caractères (délimités par « ‘ »).

Les nombres peuvent êtres des entiers (34, -45, +12) ou des réels (-34.14,0.987, -0.4e+2).

• Les variables qui débutent par une majuscule (Fils, X, Z67, U_02) ou « _ » (qui correspondent à une inconnue anonyme ou muette comme _, _X1).

• Les structures (ou terme composé) permettent de regrouper des éléments reliés logiquement. Elles débutent par un atome (dénommé foncteur) puis entre parenthèses, les arguments séparés d’un virgule (« , »). Exemple :
parent(anne,hubert).
roi(louisXV, france, regne(1715, 1774), bourbon).
employe(nom,numero,date(jour,mois,an)).
point(x,y).
segment(point(x1,y1),point(x2,y2)).
triangle(point(x1,y1),point(x2,y2),point(x3,y3)).
Ouvrage (auteur(‘Adam Smith’, annee(1723, 1790)),economie, ouvrage(‘la Richesse des Nations', 1776),cote(yl8,2345)) .

Le foncteur est le nom de la relation et l’arité le nombre d’arguments d’une relation.

2. Opérateurs

• Les opérateurs en Prolog sont des atomes (composés de symbole(s)) qui sont des foncteurs. On les rencontre essentiellement pour le calcul arithmétique. Prolog permet d’écrire les opérations de base comme :
+(3,4)
*(3,4)
+(4,(5,5))

Mais la notation préfixée n’est pas toujours la meilleure présentation et l’on préfère écrire : 3+4, 3 * 4 ou 4 + 5 * 5 ou, pour certains opérateurs, soit en notation préfixée (-3, √n), soit en notation postfixée (n !).

En tout cas, l’emploi de parenthèses permet de préciser l’ordre de l’évaluation. Mais, en l’absence de celles-ci, une expression comme « 4 + 5 * 5 » possède deux évaluations possibles. Il faut donc préciser :
- la préséance des opérateurs ;
- l’associativité.

La préséance se définit habituellement par un ordre de priorité (avec 1 la plus forte priorité). Habituellement, les opérateurs binaires « * » et « / » ont une priorité plus forte que « + » et « - » (mais attention l’opérateur unitaire « + » et « - » aura une plus forte priorité que « * » et « / »).

L’associativité permet de dire si l’expression « 16/4/2 » doit être évaluée comme « (16/4)/2 » (associatif à gauche) ou comme « 16/(4/2) » (associatif à droite).

En Prolog, les opérateurs peuvent être définis par le prédicat
op(ClasseDePriorité, Notation, Nom).

Dans laquelle, la notation est fx (préfixée), xfy (infixée) ou xf (postfixée) pour « f » l’opérateur, « x », « y » les arguments et « y » pour un argument de même ou de priorité supérieure (dont ClasseDePriorité plus petit), et « x » pour un argument de priorité supérieure.

Les opérations arithmétiques se définissent ainsi :
op(500,yfx,’+’).
op(500,yfx,’-’).
op(400,yfx,’/’).
op(400,yfx,’//’).
op(400,yfx,’*’).
op(400,yfx,’mod’). % nom pour un opérateur
op(200,fy,’-’)

3. L’unification (« = »)

• L’unification n’est pas un simple « pattern matching » (appariement exact de modèles) qui retourne vrai si deux termes sont égaux. L’unification rend égaux les deux termes. Et il faut bien le comprendre pour programmer en Prolog.

Appel
?- X = Y

Dans ce cas, l’interprète utilise son algorithme d’unification pour rendre égaux X et Y. Trois cas sont possibles pour une unification réussie, à savoir :

1. X et Y sont des constantes et elles sont égales ;

2. X ou Y est (sont) une variable libre ; dans ce cas il y a succès et la variable libre est liée au terme représenté par la seconde variable (si les deux sont des variables libres, elles co-référencent alors sur le même objet) ;

3. X et Y sont des termes composés. Il y a succès si les deux ont le même foncteur, le même nombre d’arguments et si les arguments (dans l'ordre) s’unifient l’un avec l’autre.

Appel
?- alpha = alpha
?- 23 = 24
?- 23 = alpha
?- alpha = X
?- N = 24
?- N = M
?- N = date(6,juin,1944).
?- lettre(C) = mot(toto)
?- syntagme(D,Nom,Adj) = syntagme(X,Y,Z)
?- auteur(X, action) = auteur(smith, action)
?- auteur(dijsktra, routing) = auteur(X, Y, A)
?- foo(X, X) = foo(a, b)
?- foo(X, a(b,c)) = foo(Z, a(Z,c))
?- a(b,C,d(e,F,g(h,i,J))) = a(B,C,d(E,f,g(H,i,j)))

4. Arithmétique

• L’arithmétique en Prolog se base sur les opérateurs suivants :
X + Y
X - Y
X * Y
X ^ Y % X a la puissance Y
X / Y
X // Y % division entière
X mod Y % modulo (reste de la division) • Que donne la question suivante :
?- 2 + 3 = 5

Prolog est basé sur une évaluation paresseuse des expressions arithmétiques. Il faut utiliser l’opérateur is pour forcer l’évaluation numérique (avec l’absence de toute inconnue dans la partie droite du is) !

• Voici quelques exemples
X is 22/5
X = 4.4
X is 22//5
X = 4
X is 14 mod 3
X = 2 • Et rien ne vous empêche de chercher tous les nombres …
entier(0).
entier(N) :- entier(N1), N is N1+1.

Pour les comparaisons de nombres (mais pas de variables ou de termes composés), on peut utiliser les opérateurs suivants :
X =:= Y % vrai si X et Y représente le même nombre
X =\= Y % vrai si X et Y représente des nombres différents
X < Y % vrai si X est strictement plus petit que Y
X > Y
X =< Y % et non pas <=
X >= Y % et non pas =>

• Avec un petit peu d’arithmétique, on peut donner les règles (foncteur gcd) pour trouver le plus grand diviseur commun (soit D) de deux nombres (soit X et Y), on peut utiliser l’algorithme d’Euclide qui correspond aux règles suivantes : 1. si X = Y, alors D = X ; 2. si X < Y, alors D est le gcd de X et de la différence Y – X ; 3. si Y < X, alors utiliser la règle 2 en changeant X et Y. Il s’écrit de la manière suivante :
gcd(X,X,X).
gcd(X,Y,D) :- X < Y, Y1 is Y-X, gcd(X,Y1,D).
gcd(X,Y,D) :- Y < X, gcd(Y,X,D). Autre exemple, le nombre de Fibonacci :
fibo(1,1).
fibo(2,1).
fibo(N,F) :- N > 2, N1 is N-1, fibo(N1,F1),
N2 is N-2, fibo(N2,F2), F is F1+F2.

5. Listes

La liste (séquence ordonnée d'éléments de longueur variable) est la principale structure en Prolog. Les éléments peuvent être des constantes (atomes ou nombres) ou des termes composés. Pour l’interpréteur Prolog, la liste peut être :

- une liste vide notée [] ou .() ;

- une liste composée d’un élément de tête et d’un reste comprenant la liste sans le premier élément ; cette idée se note [T|R].

Les éléments d’une liste sont séparés (comme les arguments) par une virgule « , ». Exemple de listes :
[a] % ou .(a, []).
[a,b,c] % ou .(a, .(b, .(c, []))).
[la,souris,grise,trottine].
[jean,aime,[les,vins,canadiens]].
[la,souris,grise,trottine].
[jan,fev,mar,avr,mia,juin,juil,aout,sept,oct,nov,dec].
[tennis, ski, musique].
[bach, mozart, beethoven, beatles].

Les deux notations sont possibles mais évidemment la notation avec des parenthèses droites est plus simple. Mais les formes suivantes sont aussi équivalentes :
[a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]

On utilise aussi des modèles (pattern) pour imposer un certain type de listes, comme, par exemple :
[X]. % liste composée d’un élément
[X,Y]. % liste composée de deux éléments
[X,Y,Z]. % liste composée de trois éléments

Les unifications suivantes sont possibles :
[X] = [tintin].
[X] = [123].
[X] = [roi(tintin,Belgique)].
[X] = [[la, souris, grise]].

• Grâce à la notation [T|R], on peut traiter des listes de longueur variable car on dit simplement qu’une liste est composée d’un élément en tête (ou d’une tête) et d’un reste (éventuellement vide) qui est la liste sans son premier élément.

• Les listes suivantes peuvent s’unifier si :

Prédicats (récursifs) sur les listes

• Il est très utile de savoir si un élément apparaît (au moins une fois) dans une liste. Habituellement, ce prédicat se nomme member et correspond aux règles suivantes :

1. c’est vérifié si la tête de liste est l’élément recherché ;

2. si l’élément recherché est quelque part dans le reste de la liste. Il s’écrit de la manière suivante :
member(X,[X|_]). % ou member(X,[Y|_]) :- X=Y.
member(X,[_|R]) :- member(X,R).

Un élément appartient à une liste si c’est le premier élément (cas simple) ou bien s’il apparaît dans le reste (soit la liste sans le premier élément, via un appel récursif).

• Le prédicat islist(L) qui retourne true si L est une liste. C’est vrai si :

1. c’est une liste vide ;

2. le reste est une liste, quelque soit le premier élément.
islist([]). % une liste vide est une liste
islist([_|R]) :- islist(R). % ou islist([T|R]):-islist(R).

Le comportement attendu, par exemple avec islist(X) ? Mais on peut s’appuyer simplement sur l’unification.

• Le prédicat length(L,N) qui retourne true si L est une liste composée de N éléments. Les règles sont les suivantes :

1. la liste vide a une longueur de 0 ;

2. la longueur est 1 de plus que la liste sans l’élément de tête.
length([],0). % si la liste est vide, c’est 0
length([_|R],N) :- length(R,Nr), N is Nr + 1.

• Le prédicat append(L1,L2,L) qui retourne true si L est une liste composé des éléments de L1 puis des éléments de L2.
append([],L,L). % si la 2e est vide, c’est simple
append([T|R1],L,[T|R2]) :- append(R1,L,R2).