Cours Prolog programmation

Syntaxe

Les el´ements de base d’un programme Prolog sont les pr´edicats et les termes.
Dans connexe(a,X). connexe est un (symbole de) pr´edicat.
a est un terme (une constante).
X est un terme (une variable).
Il n’y a pas de diff´erence syntaxique entre pr´edicats et termes: les termes aussi peuvent avoir des arguments:
membre(X,node(X, , )).
ici node(X, , ) est un terme a` trois arguments (un arbre binaire etiquet´e, par exemple).

Syntaxe : le lexique (simplifie)

constantes chaˆınes de caract`eres dont le premier est minuscule
variables chaˆınes de caract`eres dont le premier est majuscule, ou
nombres en notation d´ecimale
les punctuations :- , . ( ) ; …
Syntaxe: la grammaire (simplifi´ee) programme-prolog ::= clause { clause } clause ::= assertion | regle assertion ::= predicat.
predicat ::= constante [ ( liste-termes ) ] regle ::= predicat :- corps .
corps ::= predicat { , predicat } liste-termes ::= terme { , terme } terme ::= terme-simple | terme-complexe
terme-simple ::= constante | variable | nombre terme-complexe ::= constante ( liste-termes )

Semantique operationnelle: un exemple

q(a).
p(X):-q(X).
p(b).
but: p(X)
p(X ) p(X )
X =B
q(X ) yes
X =A
yes
p(X )
xx X =B
x
xx
q(X ) yes
X =A
yes
Arbre de d´erivation de p(X)

Semantique operationnelle: l’unification (1)

Une substitution est une fonction partielle qui associe des termes a` des variables (qu’on peut noter comme un ensemble de couples (Var, terme). Par exemple σ0={ (X,zero), (Y,succ(T)) } est une substitution).
L’application d’une substitution σ `a un terme t, not´ee tσ, est le terme t dans lequel les variables de σ sont remplac´ees par les termes correspondants.
Par exemple add(X,Y)σ0 = add(zero, succ(T))
Deux termes t et s sont unifi´es par la substitution σ si tσ ≡ sσ (c.a`.d. si les deux termes r´esultants de la substitution sont identiques).
La substitution σ est l’unificateur le plus g´en´eral (mgu) de t et s s’il unifie t et s et si tout autre unificateur de t et s s’obtient par instanciation de σ.
Le pr´edicat binaire infixe = de Prolog calcule les unificateurs (mgu)
?- f(X)=f(g(a,Y)).
X = g(a,Y)
?- f(X,X)=f(g(a,Y),g(Z,b)).
X = g(a,b),
Y = b,
Z = a
?- X=f(X).
X = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f… Segmentation fault
Pas de OCCUR CHECK!

Semantique operationnelle: arbres de derivation

On consid`ere un programme P=c1,…cK et un but G=g1,…,gL .
Soit c = t :- b1,b2,…,bLI . (si lI = 0 alors cI est une assertion, sinon c’est une r`egle).
On d´efinit noeuds et arcs de l’arbre de d´erivation de G pour P par induction (sur la hauteur):
• la racine est G.
• Soit H=h1,…hL un noeud de hauteur n, et soit cS une clause de P dont la tˆete tS s’unifie avec h1, avec mgu σ.
Alors on cr´ee le noeud, de hauteur n + 1, H’= b1S σ,…,bLSS σ, h2σ,…hL σ et on ´etiquette l’arc de H `a H’ par σ.
Une feuille est soit un but vide (succes), soit un but dont le premier pr´edicat ne s’unifie avec aucune tˆete de clause (echec).

Semantique operationnelle: exemples d’arbres de derivation

P = p(a). p(b). p(c).
G= p(X)
p(X )
X =A xx FFF X=C
xxxX =B FFF
xx FF
x
yes yes yes
P= p(a). p(b). q(b).
G= p(X),q(X)
p(X ), q(X )
X =A ssss
ssssss X =B
q(a) q(b)
yes
L’ex´ecution d’un goal G pour un programme P a comme r´esultat l’ensemble de feuilles succes de l’arbre de d´erivation correspondant.
Plus pr´ecisement, pour chacune de ces feuilles, le r´esultat est l’ensemble des instantiations des variables de G qui se trouvent sur le chemin qui m`ene de la racine a` la feuille en question.
L’arbre de d´erivation est produit de mani`ere pr´efixe (parcours en profondeur d’abord).
Donc l’ordre des clause est important. Par exemple, pour p(X):-p(X). p(a) le but p(X) ne donne aucun r´esultat (boucle), mais pour p(a). p(X):-p(X) le r´esultat X=a est atteint.

• Les origines du Prolog
• Deux exemples de programmes.
• Syntaxe
– Constantes, variables, termes, predicats.
– Assertions, Regles, Buts.
• Semantique
– Unification
– Arbres de derivation
• 2`eme partie
– L’arithmetique en Prolog