Prolog : syntaxe

Les éléments de base dʼun programme Prolog sont les prédicats et les termes. Dans
connexe(a,X). connexe est un (symbole de) prédicat.
a est un terme (une constante).
X est un terme (une variable).
Il n yʼa pas de différence syntaxique entre prédicats et termes:
les termes aussi peuvent avoir des arguments:
membre(X,node(X,_,_)).
ici node(X,_,_) est un terme à trois arguments (un arbre binaire étiqueté, par exemple).

le lexique (simplifié)

Constantes : chaînes de caractères dont le premier est minuscule
variables : chaînes de caractères dont le premier est majuscule ou _
nombres : en notation décimale
les ponctuations : :- , . ( ) ; …
la grammaire (simplifiée) 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 )

Prolog : sémantique

Sémantique opérationnelle: un exemple
q(a).
p(X):-q(X).
p(b).
but: p(X)
Sémantique opérationnelle: lʼunification
Une substitution est une fonction partielle qui associe des termes
à des variables (quʼon peut noter comme un ensemble de couple (Var, terme). Par exemple σ0={ (X,zero), (Y,succ(T)) } est une substitution).
Lʼapplication dʼune substitution σ à un terme t, notée tσ, est le terme t dans lequel les variables de σ sont remplacées par les termes correspondants.
Par exemple add(X,Y)σ0 = add(zero, succ(T))
Deux termes t et s sont unifiés par la substitution σ si tσ ≡ sσ (c.à.d. si les deux termes résultants de la substitution sont identiques).
La substitution σ est lʼunificateur le plus général (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 σ.

Sémantique opérationnelle: lʼunification

Le prédicat 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
Sémantique opérationnelle: Arbre de dérivation
On considère un programme P=c1,…ck et un but G=g1,…,gl.
Soit ci= ti:- bi1,bi2,…,bili .
(si li = 0 alors ci est une assertion, sinon cʼest une règle).
On définit noeuds et arcs de lʼarbre de dérivation 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 dont la tête ts sʼunifie avec h1, avec mgu σ.
Alors on crée le noeud, de hauteur n + 1, H’= bs1σ,…,bslsσ, h2σ,…hlσ et on étiquette lʼarc de H à Hʼ par σ.
Une feuille est soit un but vide (succes), soit un but dont le premie prédicat ne sʼunifie avec aucune tête de clause (echec).
Sémantique opérationnelle: exemples dʼarbres de dérivation
Lʼexécution dʼun goal G pour un programme P a comme résultat lʼensemble de feuilles succes de lʼarbre de dérivation correspondant.
Plus précisément, pour chacune de ces feuilles, le résultat est lʼensemble des instantiations des variables de G qui se trouvent sur le chemin qui mène de la racine à la feuille en question.
Lʼarbre de dérivation est produit par un parcours en profondeur dʼabord. Donc lʼordre des clauses est important.
Par exemple, pour p(X):-p(X). p(a) le but p(X) ne donne aucun résultat (boucle), mais pour p(a). p(X):-p(X) le résultat X=a est atteint.

• Programmation logique et Prolog (PL)
– SWI-Prolog, Sicstus
• Programmation logique par contraintes (PLC)
– Sicstus
• Problèmes de satisfaction de contraintes (CSP/PC)
– Choco
• Les origines de Prolog
• Deux exemples de programmes
• Syntaxe
– Constantes, variables, termes, prédicats.
– Assertions, Règles, Buts.
• Sémantique
– Unification
– Arbres de dérivation
• Le langage