Partea I

Limbajul Prolog

Începutul programării logice poate fi atribuit lui R. Kowalski ºi A. Colmerauer ºi se situează

la începutul anilor '70. Kowalski a plecat de la o formulă logică de tipul:

S1 Ù S2 Ù ... Sn ® S

care are, în logica cu predicate de ordinul întâi semnificaţia declarativă conform căreia

S1 Ù S2 Ù ... Sn  implicã S, adică dacă S1 ºi S2 ... ºi Sn sunt fiecare adevărate atunci şi S este

adevărat, şi a propus o interpretare proceduralã asociată. Conform acestei interpretări,

formula de mai sus poate fi scrisã sub forma:

S dacã S1 ºi S2 ... ºi Sn

ºi poate fi executatã ca o procedurã a unui limbaj de programare recursiv, unde S este

antetul procedurii ºi S1, S2, ... Sn corpul acesteia. Deci, pe lângã interpretarea declarativã,

logică, a unei astfel de formule, formula poate fi interpretatã procedural astfel: pentru a

executa S se executã S1 ºi S2 ... ºi Sn.

În aceeaºi perioadã, A. Colmerauer ºi colectivul lui de cercetare de la Universitatea din

Marsilia au dezvoltat un limbaj de implementare a acestei abordări, pe care l-au denumit

Prolog, abreviere de la "Programmation et Logique". De atunci ºi pînã în prezent, limbajul

Prolog s-a impus ca cel mai important limbaj de programare logicã şi s-au dezvoltat

numeroase implementãri, atât ale unor interpretoare cât ºi ale unor compilatoare ale

limbajului.

Limbajul Prolog este un limbaj declarativ susţinut de o componentă procedurală. Spre

deosebire de limbajele procedurale, cum ar fi C sau Pascal, în care rezolvarea problemei

este specificată printr-o serie de paşi de execuţie sau acţiuni, într-un limbaj declarativ

problema este specificată prin descrierea universului problemei şi a relaţiilor sau funcţiilor

existente între obiecte din acest univers. Exemple de astfel de limbaje sunt cele funcţionale,

de exemplu Lisp, Scheme, ML, şi cele logice, de exemplu Prolog.

Deºi iniþial a fost gândit pentru un set restrâns de probleme, Prolog a devenit cu

timpul un limbaj de uz general, fiind o unealtã importantã în aplicaþiile de inteligenþã

artificialã [CM84, Bra88, SS86]. Pentru multe probleme, un program Prolog are cam de 10

ori mai puþine linii decât echivalentul lui în Pascal.

În 1983, cercetãtorii din Japonia au publicat un plan ambiþios de creare a unor

calculatoare de generaþia a 5-a pentru care Prolog era limbajul de asamblare. Planul nu a

reuºit, dar acest proiect a marcat o dezvoltare deosebitã a interpretoarelor ºi compilatoarelor

de Prolog, precum ºi o creºtere mare a numãrului de programatori în acest limbaj.

Multe clase de probleme poate fi rezolvate în Prolog, existând anumite categorii care

sunt rezolvabile mult mai uºor în Prolog decât în orice alt limbaj procedural. Astfel de

probleme sunt în principal cele dedicate prelucrării simbolice sau care necesitã un proces de

căutare a soluţiei într-un spaţiu posibil de transformări ale problemei.

Prezentarea limbajului Prolog ce urmează este în principal orientată pe descrierea

limbajului Prolog standard. Exemplele de programe din această parte cât şi din partea a

doua sunt rulate utilizând interpretorul ARITY Prolog pe microcalculatoare de tip IBM/PC,

mediul de programare ARITY Prolog şi particularităţile lui sintactice fiind prezentate în

partea a doua.

1 Entitãþile limbajului Prolog

Limbajul Prolog este un limbaj logic, descriptiv, care permite specificarea problemei de

rezolvat în termenii unor fapte cunoscute despre obiectele universului problemei ºi a

relaþiilor existente între aceste obiecte. Execuþia unui program Prolog constã în deducerea

implicaþiilor acestor fapte ºi relaþii, programul definind astfel o mulþime de consecinþe ce

reprezintã înþelesul sau semnificaþia declarativã a programului.

Un program Prolog conþine urmãtoarele entitãþi:

· fapte despre obiecte ºi relaþiile existente între aceste obiecte;

· reguli despre obiecte ºi relaţiile dintre ele, care permit deducerea (inferarea) de noi

fapte pe baza celor cunoscute;

· întrebãri, numite ºi scopuri, despre obiecte ºi relaţiile dintre ele, la care programul

rãspunde pe baza faptelor ºi regulilor existente.

1.1 Fapte

Faptele sunt predicate de ordinul întâi de aritate n considerate adevãrate. Ele stabilesc

relaþii între obiectele universului problemei. Numãrul de argumente ale faptelor este dat de

aritatea (numãrul de argumente) corespunzãtoare a predicatelor.

Exemple:

Fapt: Aritate:

papagal(coco). 1

iubeºte(mihai, maria). 2

iubeºte(mihai, ana). 2

frumoasã(ana). 1

bun(gelu). 1

deplaseazã(cub, camera1, camera2). 32

Interpretarea particularã a predicatului ºi a argumentelor acestuia depinde de

programator. Ordinea argumentelor, odatã fixatã, este importantã ºi trebuie pãstratã la orice

altã utilizare a faptului, cu aceeaºi semnificaþie. Mulþimea faptelor unui program Prolog

formeazã baza de cunoºtinþe Prolog. Se va vedea mai târziu cã în baza de cunoºtinte a unui

program Prolog sunt incluse ºi regulile Prolog.

1.2 Scopuri

Obþinerea consecinþelor sau a rezultatului unui program Prolog se face prin fixarea unor

scopuri care pot fi adevãrate sau false, în funcþie de conþinutul bazei de cunoºtinþe Prolog.

Scopurile sunt predicate pentru care se doreºte aflarea valorii de adevãr în contextul faptelor

existente în baza de cunoºtinþe. Cum scopurile pot fi vãzute ca întrebãri, rezultatul unui

program Prolog este rãspunsul la o întrebare (sau la o conjuncþie de întrebãri). Acest

rãspuns poate fi afirmativ, yes, sau negativ, no. Se va vedea mai târziu cã programul Prolog,

în cazul unui rãspuns afirmativ la o întrebare, poate furniza ºi alte informaþii din baza de

cunoºtinþe.

Exemplu

Considerând baza de cunoºtinþe specificatã anterior, se pot pune diverse întrebãri, cum

ar fi:

?- iubeste(mihai, maria).

yes deoarece acest fapt existã în baza de cunoºtinþe

?- papagal(coco).

yes

?- papagal(mihai).

no deoarece acest fapt nu existã în baza de cunoºtinþe

?- inalt(gelu).

no

1.3 Variabile

În exemplele prezentate pânã acum, argumentele faptelor ºi întrebãrilor au fost obiecte

particulare, numite ºi constante sau atomi simbolici. Predicatele Prolog, ca orice predicate în

logica cu predicate de ordinul I, admit ca argumente ºi obiecte generice numite variabile. În

Prolog, prin convenþie, numele argumentelor variabile începe cu literã iar numele

constantelor simbolice începe cu literã micã. O variabilã poate fi instanþiatã (legatã) dacã

existã un obiect asociat acestei variabile, sau neinstanþiatã (liberã) dacã nu se ºtie încã ce

obiect va desemna variabila.

La fixarea unui scop Prolog care conþine variabile, acestea sunt neinstanþiate iar

sistemul încearcã satisfacerea acestui scop cãutând printre faptele din baza de cunoºtinþe un

fapt care poate identifica cu scopul, printr-o instanþiere adecvatã a variabilelor din scopul

3

dat. Este vorba de fapt de un proces de unificare a predicatului scop cu unul din predicatele

fapte existente în baza de cunoºtinþe.

La încercarea de satisfacere a scopului, cãutarea se face întotdeauna pornind de la

începutul bazei de cunoºtinþe. Dacã se întâlneºte un fapt cu un simbol predicativ identic cu

cel al scopului, variabilele din scop se instanþiazã conform algoritmului de unificare ºi

valorile variabilelor astfel obþinute sunt afiºate ca rãspuns la satisfacerea acestui scop.

Exemple:

?- papagal(CineEste).

CineEste = coco

?- deplaseaza(Ce, DeUnde, Unde).

Ce = cub, DeUnde = camera1, Unde = camera2

?- deplaseaza(Ce, Aici, Aici).

no

Cum se comportã sistemul Prolog în cazul în care existã mai multe fapte în baza de

cunoºtinþe care unificã cu întrebarea pusã? În acest caz existã mai multe rãspunsuri la

întrebare, corespunzând mai multor soluþii ale scopului fixat. Prima soluþie este datã de

prima unificare ºi existã atâtea soluþii câte unificãri diferite existã. La realizarea primei

unificãri se marcheazã faptul care a unificat ºi care reprezintã prima soluþie. La obþinerea

urmãtoarei soluþii, cãutarea este reluatã de la marcaj în jos în baza de cunoºtinþe. Obþinerea

primei soluþii este de obicei numitã satisfacerea scopului iar obþinerea altor soluþii,

resatisfacerea scopului. La satisfacera unui scop cãutarea se face întotdeauna de la

începutul bazei de cunoºtinþe. La resatisfacerea unui scop, cãutarea se face începând de la

marcajul stabilit de satisfacerea anterioarã a acelui scop.

Sistemul Prolog, fiind un sistem interactiv, permite utilizatorului obþinerea fie a

primului rãspuns, fie a tuturor rãspunsurilor. În cazul în care, dupã afiºarea tuturor

rãspunsurilor, un scop nu mai poate fi resatisfãcut, sistemul rãspunde no.

Exemple:

?- iubeste(mihai, X).

X = maria; tastând caracterul “;” ºi Enter, cerem o nouã soluþie

X = ana;

no

?- iubeste(Cine, PeCine).

Cine = mihai, PeCine = maria;

Cine = mihai, PeCine = ana;

no

4

Existã deci douã soluþii pentru scopul iubeste(mihai, X) ºi tot douã soluþii pentru

scopul iubeste(Cine, PeCine), considerând tot baza de cunoºtinþe prezentatã în secþiunea

1.1.

1.4 Reguli

O regulã Prolog exprimã un fapt care depinde de alte fapte ºi este de forma:

S :- S1, S2, …Sn.

cu semnificaþia prezentatã la începutul acestui capitol. Fiecare Si, i = 1,n ºi S au forma

faptelor Prolog, deci sunt predicate, cu argumente constante, variabile sau structuri. Faptul S

care defineºte regula, se numeºte antet de regulã, iar S1, S2, …Sn formeazã corpul regulii ºi

reprezintã conjuncþia de scopuri care trebuie satisfãcute pentru ca antetul regulii sã fie

satisfãcut.

Fie urmãtoarea bazã de cunoºtinþe Prolog:

frumoasa(ana). % 1

bun(vlad). % 2

cunoaste(vlad, maria). % 3

cunoaste(vlad, ana). % 4

iubeste(mihai, maria). % 5

iubeste(X, Y) :- % 6

bun(X),

cunoaste(X, Y),

frumoasa(Y).

Se observã cã enunþul (6) defineºte o regulã Prolog; relaþia iubeste(Cine, PeCine),

fiind definitã atât printr-un fapt (5) cât ºi printr-o regulã (6).

În condiþiile existenþei regulilor în baza de cunoºtinþe Prolog, satisfacerea unui scop

se face printr-un procedeu similar cu cel prezentat în Secþiunea 1.2, dar unificarea scopului

se încearcã atât cu fapte din baza de cunoºtinþe, cât ºi cu antetul regulilor din bazã. La

unificarea unui scop cu antetul unei reguli, pentru a putea satisface acest scop trebuie

satisfãcutã regula. Aceasta revine la a satisface toate faptele din corpul regulii, deci

conjuncþia de scopuri. Scopurile din corpul regulii devin subscopuri a cãror satisfacere se

va încerca printr-un mecanism similar cu cel al satisfacerii scopului iniþial.

Pentru baza de cunoºtinþe descrisã mai sus, satisfacerea scopului

?- iubeste(vlad, ana).

se va face în urmãtorul mod. Scopul unificã cu antetul regulii (6) ºi duce la instanþierea

variabilelor din regula (6): X = vlad ºi Y = ana. Pentru ca acest scop sã fie îndeplinit,

trebuie îndeplinitã regula, deci fiecare subscop din corpul acesteia. Aceasta revine la

îndeplinirea scopurilor bun(vlad), care reuºeºte prin unificare cu faptul (2),

5

cunoaste(vlad, ana), care reuºeºte prin unificare cu faptul (4), ºi a scopului frumoasa(ana),

care reuºeºte prin unificare cu faptul (1). În consecinþã, regula a fost îndeplinitã, deci ºi

întrebarea iniþialã este adevaratã, iar sistemul rãspunde yes.

Ce se întîmplã dacã se pune întrebarea:

?- iubeste(X, Y).

Prima soluþie a acestui scop este datã de unificarea cu faptul (5), iar rãspunsul este:

X = mihai, Y = maria

Sistemul Prolog va pune un marcaj în dreptul faptului (5) care a satisfãcut scopul.

Urmãtoarea soluþie a scopului iubeste(X, Y) se obþine începând cãutarea de la acest marcaj

în continuare în baza de cunoºtinþe. Scopul unificã cu antetul regulii (6) ºi se vor fixa trei

noi subscopuri de îndeplinit, bun(X), cunoaste(X, Y) ºi frumoasa(Y). Scopul bun(X) este

satisfãcut de faptul (2) ºi variabila X este instanþiatã cu valoarea vlad, X = vlad . Se

încearcã acum satisfacerea scopului cunoaste(vlad, Y), care este satisfãcut de faptul (3) ºi

determinã instanþierea Y = maria. Se introduce în baza de cunoştinţe un marcaj asociat

scopului cunoaste(vlad, Y), care a fost satisfãcut de faptul (3). Se încearcã apoi satisfacerea

scopului frumoasa(maria). Acesta eºueazã. În acest moment sistemul intrã într-un proces

de backtracking în care se încearcã resatisfacerea scopului anterior satisfãcut,

cunoaste(vlad, Y), în speranþa cã o noua soluþie a acestui scop va putea satisface ºi scopul

curent care a eºuat, frumoasa(Y). Resatisfacerea scopului cunoaste(vlad, Y) se face

pornind cãutarea de la marcajul asociat scopului în jos, deci de la faptul (3) în jos. O nouã

soluþie (resatisfacere) a scopului cunoaste(vlad, Y) este datã de faptul (4) care determinã

instanþierea Y = ana. În acest moment se încearcã satisfacerea scopului frumoasa(ana).

Cum este vorba de un nou scop, cãutarea se face de la începutul bazei de cunoºtinþe ºi

scopul frumoasa(ana) este satisfãcut de faptul (1). În consecinþã a doua soluþie a scopului

iubeste(X, Y) este obþinutã ºi sistemul rãspunde:

X = vlad, Y = ana

urmând un mecanism de backtracking, descris intuitiv în figura 1 prin prezentarea arborilor

de deducþie construiþi de sistemul Prolog.

6

Figura 1. Mecanismul de satisfacere a scopurilor în Prolog

La încercarea de resatisfacere a scopului iubeste(X, Y), printr-un mecanism similar, se

observã cã nu mai existã alte solutii. În concluzie, fiind datã baza de fapte ºi reguli Prolog

anterioarã, comportarea sistemului Prolog este:

?- iubeste(X, Y).

X = mihai, Y = maria;

X = vlad, Y = ana;

no

Observaþii:

· La satisfacerea unei conjuncþii de scopuri în Prolog, se încearcã satisfacerea

fiecãrui scop pe rând, de la stânga la dreapta. Prima satisfacere a unui scop

determinã plasarea unui marcaj în baza de cunoºtinþe în dreptul faptului sau

regulii care a determinat satisfacerea scopului.

· Dacã un scop nu poate fi satisfãcut (eºueazã), sistemul Prolog se întoarce ºi încearcã

resatisfacerea scopului din stânga, pornind cãutarea în baza de cunoºtinþe de la

marcaj în jos. Înainte de resatisfacerea unui scop se eliminã toate instanþierile de

variabile determinate de ultima satisfacere a acestuia. Dacã cel mai din stânga

iubeste(X,Y)

%5 iubeste(mihai,maria)

SUCCES

solutie 1: X=mihai, Y=maria

iubeste(X,Y)

bun(X)

%2 bun(vlad)

SUCCES

cunoaste(X,Y)

%3 cunoaste(vlad,maria)

%6 frumoasa(Y)

frumoasa(maria)

%4 cunoaste(vlad,ana)

%1 frumoasa(ana)

solutie 2: X=vlad, Y=ana

cunoaste(vlad,Y)

SUCCES SUCCES

SUCCESINSUCCES

7

scop din conjuncþia de scopuri nu poate fi satisfãcut, întreaga conjuncþie de

scopuri eºueazã.

· Aceastã comportare a sistemului Prolog în care se încearcã în mod repetat

satisfacerea ºi resatisfacerea scopurilor din conjuncþiile de scopuri se numeºte

backtracking.

· În Secþiunea 4 se va discuta pe larg structura de control a sistemului Prolog,

mecanismul fundamental de backtracking ºi modurile în care se poate modifica

parþial acest mecanism.

1.5 Un program Prolog simplu

Simplitatea ºi expresivitatea limbajului Prolog poate fi pusã în evidentã de urmãtorul

exemplu de descriere a unui circuit logic "poartã ªI". Se considerã poarta ªI ca fiind

construitã prin conectarea unei "porþi ªI-NU" cu un inversor. Întregul circuit este definit de

relaþia:

poarta_si(Intrare1, Intrare2, Iesire)

pe baza relaþiilor

poarta_si_nu(Intrare1, Intrare2, Iesire)

inversor(Intrare, Iesire).

În figura 2 este prezentatã schema porþii ªI în care se observã cã inversorul este

construit dintr-un tranzistor cu sursa conectatã la masã ºi un rezistor cu un capãt conectat la

alimentare. Poarta tranzistorului este intrarea inversorului, în timp ce celãlalt capãt al

rezistorului trebuie conectat la colectorul tranzistorului care formeazã ieºirea inversorului.

Figura 2. Un circuit logic poartã ªI

Variabilele comune între predicate sunt utilizate pentru a specifica legãturile comune.

rezistor(alimentare, n1).

n1

n2 n3

n4n5

8

rezistor(alimentare, n2).

tranzistor(n2, masa, n1).

tranzistor(n2, masa, n1).

tranzistor(n3, n4, n2).

tranzistor(n5, masa, n4).

inversor(Intrare, Iesire) :-

tranzistor(Intrare, masa, Iesire),

rezistor(alimentare, Iesire).

poarta_si_nu(Intrare1, Intrare2, Iesire) :-

tranzistor(Intrare1, X, Iesire),

tranzistor(Intrare2, masa, X),

rezistor(alimentare, Iesire).

poarta_si(Intrare1, Intrare2, Iesire) :-

poarta_si_nu(Intrare1, Intrare2, X),

inversor(X, Iesire).

Pentru întrebarea

?- poarta_si(In1, In2, Iesire).

In1 = n3, In2= n5, Iesire = n1

rãspunsul sistemului Prolog confirmã faptul cã circuitul descris este o poartã ªI, identificând

intrãrile ºi ieºirile corespunzãtoare.

2 Sintaxa limbajului Prolog

Aºa cum s-a arãtat în secþiunea anterioarã, un program Prolog este format din fapte, reguli

ºi întrebãri, acestea fiind construite pe baza predicatelor definite de utilizator sau predefinite.

În orice sistem Prolog existã o mulþime de predicate predefinite, unele dintre acestea fiind

predicate standard, iar altele depinzând de implementare. Argumentele predicatelor Prolog,

prin analogie cu logica predicatelor de ordinul I, se numesc termeni, ºi pot fi constante,

variabile sau structuri.

2.1 Constante

Constantele definesc obiecte specifice, particulare, sau relaþii particulare. Existã douã tipuri

de constante: atomi ºi numere. Atomii sunt constante simbolice care încep, de obicei, cu o

literã ºi pot conþine litere, cifre ºi caracterul “_”. Existã ºi alte caractere ce pot forma atomi

speciali, care au o semnificaþie aparte în limbaj. Atomii pot desemna:

· obiecte constante care sunt argumentele predicatelor, de exemplu atomii mihai ºi

maria în faptul iubeste(mihai, maria);

9

· predicate Prolog, fie cele definite de utilizator, fie cele predefinite în sistem; de

exemplu atomul iubeste în faptul iubeste(mihai, maria);

· atomi speciali, de exemplu atomii “:-” ºi “?”- ;

· diverse alte reguli de construcþie sintacticã a atomilor depind de implementare.

Numerele pot fi întregi sau reale; sintaxa particularã acceptatã cât ºi domeniile de

definiţie depinzând de implementare. Detalii despre formatul numerelor şi a altor tipuri de

constante din mediul ARITY Prolog sunt descrise în partea a doua.

2.2 Variabile

Variabilele sunt, din punct de vedere sintactic, tot atomi, dar ele au o semnificaþie specialã,

aºa cum s-a arãtat în Secþiunea 1.3. Spre deosebire de regulile generale admise pentru

construcþia atomilor, numele unei variabile poate începe ºi cu simbolul “_”, ceea ce indicã o

variabilã anonimã. Utilizarea unei variabile anonime semnifică faptul cã nu intereseazã

valoarea la care se va instanþia acea variabilã.

De exemplu, interogarea ?- iubeste( _, maria). semnificã faptul cã se întreabã dacã

existã cineva care o iubeºte pe Maria, dar nu intereseazã cine anume. Limbajul Prolog face

distincþia între litere mari ºi litere mici (este case sensitive). Se reaminteºte cã, din punctul

de vedere al convenţiei Prolog, numele oricãrei variabile trebuie sã înceapă fie cu literã

mare, fie cu “_”.

2.3 Structuri

O structurã Prolog este un obiect ce desemneaza o colecþie de obiecte corelate logic, care

formeazã componentele structurii. Un exemplu este structura asociatã obiectului carte, care

este formatã din componentele: titlu carte, autor, ºi an apariţie. Un fapt ce referã relaþia de

posedare a unei cãrþi de Prolog de cãtre Mihai poate fi exprimat astfel:

poseda(mihai, carte(prolog, clocksin, 1981)).

unde carte(prolog, clocksin, 1981) este o structurã cu numele carte ºi cu trei componente:

prolog, clocksin ºi 1981. Se admit ºi structuri imbricate, de exemplu:

poseda(mihai, carte(prolog, autori(clocksin, mellish), 1981)).

unde predicatul poseda are douã argumente: primul argument este constanta mihai, iar cel

de-al doilea este structura carte(prolog ....), cu douã componente, a doua componentã fiind

structura autori(clocksin, mellish).

În Prolog, o structurã se defineºte prin specificarea:

(1) numelui structurii ( functorul structurii);

(2) elementelor structurii (componentele structurii).

10

Structurile Prolog pot fi utilizate pentru reprezentarea structurilor de date, de exemplu

liste sau arbori. În Secþiunea 2.6 se vor prezenta structuri Prolog predefinite care permit

lucrul cu liste. Un arbore binar poate fi reprezentat în Prolog tot printr-o structurã, de

exemplu:

arb(barbu, arb(ada, vid, vid), vid).

reprezintã un arbore binar cu cheia din rãdãcina barbu, cu subarborele drept vid ºi cu

subarborele stâng format dintr-un singur nod cu cheia ada.

Observaþii:

· Sintaxa structurilor este aceeaºi cu cea a faptelor Prolog. Un predicat Prolog poate fi

vãzut ca o structurã a cãrui functor este numele predicatului, iar argumentele

acestuia reprezintã componentele structurii.

· Considerarea predicatelor Prolog ca structuri prezintã un interes deosebit; atât datele

cât ºi programele în Prolog au aceeaºi formã, ceea ce faciliteazã tratarea uniformã

ºi sinteza dinamicã de programe. În Secþiunea 4.3 se vor prezenta predicate

predefinite în Prolog care permit sinteza ºi execuþia dinamicã a programelor

Prolog.

2.4 Operatori

Uneori este convenabil sã se scrie anumiþi functori (nume de structuri sau predicate) în

formă infixatã. Aceasta este o formã sintacticã ce mãreºte claritatea programului, cum ar fi

cazul operatorilor aritmetici sau al operatorilor relaþionali.

Limbajul Prolog oferã o mulþime de operatori, unii care se regãsesc în aproape orice

implementare, iar alþii care sunt specifici unei versiuni particulare de implementare a

limbajului. În continuare se vor prezenta o parte dintre operatorii din prima categorie.

(1) Operatori aritmetici

Operatorii aritmetici binari, cum ar fi +, -, *, /, pot fi scriºi în Prolog în notaþie infixatã; de

exemplu:

1 + 2*(X * Y) / Z

Aceasta sintaxa este de fapt o rescriere infixatã a formei prefixate a structurilor echivalente:

+(1, 2) / (*(X, Y), Z)

Este important de reþinut cã operatorii aritmetici sunt o rescriere infixatã a unor

structuri deoarce valoarea expresiei astfel definitã nu este calculatã. Evaluarea expresiei se

face la cerere în cazul în care se foloseste operatorul predefinit infixat is, de exemplu:

X is 1 + 2.

11

va avea ca efect instanþierea variabilei X la valoarea 3.

(2) Operatori relaþionali

Operatorii relaţionali sunt predicate predefinite infixate. Un astfel de operator este

operatorul de egalitate =. Predicatul (operatorul) de egalitate funcþioneazã ca ºi cum ar fi

definit prin urmãtorul fapt:

X = X.

iar încercarea de a satisface un scop de tipul X = Y se face prin încercarea de a unifica X cu

Y. Din aceasta cauzã, dându-se un scop de tipul X = Y, regulile de decizie care indică dacã

scopul se îndeplineºte sau nu sunt urmãtoarele:

· Dacã X este variabilă neinstanþiatã, iar Y este instanþiatã la orice obiect Prolog,

atunci scopul reuºeºte. Ca efect lateral, X se va instanþia la aceeaºi valoare cu cea

a lui Y. De exemplu:

?- carte(barbu, poezii) = X.

este un scop care reuºeºte ºi X se instanþiazã la carte(barbu, poezii).

· Dacă atât X cât ºi Y sunt variabile neinstanþiate, scopul X = Y reuºeºte, variabila X

este legatã la Y ºi reciproc. Aceasta înseamnã cã ori de câte ori una dintre cele

douã variabile se instanþiazã la o anumitã valoare, cealaltã variabila se va

instanþia la aceeaºi valoare.

· Atomii ºi numerele sunt întotdeauna egali cu ei înºiºi. De exemplu, urmãtoarele

scopuri au rezultatul marcat drept comentariu:

mihai = mihai % este satisfãcut

mare = mic % eºueazã

102 = 102 % reuºeºte

1010 = 1011 % eºueazã

· Douã structuri sunt egale dacã au acelaºi functor, acelaºi numãr de componente ºi

fiecare componentã dintr-o structurã este egalã cu componenta corespunzãtoare

din cealaltã structurã. De exemplu, scopul:

autor(barbilian, ciclu(uvedenrode, poezie(riga_crypto))) =

autor(X, ciclu(uvedenrode, poezie(Y)))

este satisfãcut, iar ca efect lateral se fac instanþierile:

X = barbilian ºi Y = riga_crypto.

Operatorul de inegalitate \= se defineºte ca un predicat opus celui de egalitate. Scopul

X \= Y reuºeºte dacã scopul X = Y nu este satisfãcut ºi eºueazã dacã X = Y reuºeºte. În plus,

12

existã predicatele relaþionale de inegalitate definite prin operatorii infixaþi >, <, =<, >=, cu

semnificaþii evidente.

Un operator interesant este =:=. El face numai evaluare aritmeticã ºi nici o instanþiere.

Exemplu:

?- 1 + 2 =:= 2 + 1.

yes

?- 1 + 2 = 2 + 1.

no

Predicatul = = testeazã echivalenþa a douã variabile. El considerã cele douã variabile

egale doar dacã ele sunt deja partajate. X = = Y reuºeºte ori de câte ori X = Y reuºeºte, dar

reciproca este falsã:

?- X = = X.

X=_23 %variabilă neinstanţiată

?- X= =Y.

no

?- X=Y, X= =Y.

X=_23, Y=_23 % X şi Z variabile neinstanţiate partajate

În cele mai multe implementãri Prolog existã predefinit operatorul de obþinere a

modulului unui numãr, mod; scopul

X is 5 mod 3.

reuºeºte ºi X este instanþiat la 2.

Comentariile dintr-un program Prolog sunt precedate de caracterul “%”.

Exemple:

1. Presupunând cã nu existã operatorul predefinit mod, se poate scrie un predicat

Prolog cu efect similar. O definiþie posibilã a predicatului modulo(X, Y, Z), cu

semnificaþia argumentelor Z = X mod Y , presupunând X, Y > 0, este:

% modulo(X, Y, Z)

modulo(X, Y, X) :- X < Y.

modulo(X, Y, Z) :- X >= Y, X1 is X - Y, modulo(X1, Y, Z).

2. Plecând de la predicatul modulo definit anterior, se poate defini predicatul de calcul

al celui mai mare divizor comun al douã numere, conform algoritmului lui Euclid,

presupunând X > 0, Y > 0, astfel:

% cmmdc(X, Y, C)

cmmdc(X, 0, X).

13

cmmdc(X, Y, C) :- modulo(X, Y, Z), cmmdc(Y, Z, C).

La întrebarea

?- cmmdc(15, 25, C).

C=5

rãspunsul sistemului este corect. În cazul în care se încearcã obþinerea unor noi

soluþii (pentru semnificaþia cmmdc acest lucru este irelevant, dar intereseazã din

punctul de vedere al funcþionãrii sistemului Prolog) se observã ca sistemul intrã

într-o buclã infinitã datorita imposibilitãþii resatisfacerii scopului modulo(X, Y, Z)

pentru Y = 0. Dacã la definiþia predicatului modulo se adaugã faptul:

modulo(X, 0, X).

atunci predicatul modulo(X, Y, Z) va genera la fiecare resatisfacere aceeaºi soluþie,

respectiv solutia corectã, la infinit. Cititorul este sfãtuit sã traseze execuþia

predicatului cmmdc în ambele variante de implementare a predicatului modulo.

3. Calculul ridicãrii unui număr natural la o putere naturalã se poate face definind

urmãtorul predicat:

% expo(N, X, XlaN)

expo( _ , 0, 0).

expo(0, _ , 1).

expo(N, X, Exp) :- N > 0, N1 is N - 1, expo(N1, X, Z), Exp is Z * X.

2.5 Operatori definiţi de utilizator

Limbajul Prolog permite definirea de noi operatori de cãtre programator prin introducerea în

program a unor clauze de formã specialã, numite directive. Directivele acþioneazã ca o

definire de noi operatori ai limbajului în care se specificã numele, precedenþa ºi tipul

(infixat, prefixat sau postfixat) operatorului. Se reaminteºte faptul cã orice operator Prolog

este de fapt o structurã care are ca functor numele operatorului ºi ca argumente argumentele

operatorului, dar este scris într-o sintaxã convenabilã. La definirea de noi operatori în

Prolog, se creeazã de fapt noi structuri cãrora le este permisã o sintaxã specialã, conform

definiþiei corespunzãtoare a operatorului. Din acest motiv, nu se asociazã nici o operaþie

operatorilor definiþi de programator. Operatorii noi definiþi sunt utilizaþi ca functori numai

pentru a combina obiecte în structuri ºi nu pentru a executa acþiuni asupra datelor, deºi

denumirea de operator ar putea sugera o astfel de acþiune.

De exemplu, în loc de a utiliza structura:

are(coco, pene)

se poate defini un nou operator are

14

:- op(600, xfx, are).

caz în care este legalã expresia

coco are pene.

Definirea de noi operatori se face cu ajutorul directivei:

:- op(precedenþã-operator, tip-operator, nume-operator).

Operatorii sunt atomi iar precedenta lor trebuie sã fie o valoare întreagă într-un anumit

interval ºi corelatã cu precedenþa operatorilor predefiniþi în limbaj. Tipul operatorilor

fixeazã caracterul infixat, prefixat sau postfixat al operatorului ºi precedenþa operanzilor

sãi. Tipul operatorului se defineºte utilizând una din urmãtoarele forme standard:

(1) operatori infixaþi: xfx xfy yfx

(2) operatori prefixaþi: fx fy

(3) operatori postfixaþi: xf yf

unde f reprezintã operatorul, iar x ºi y operanzii sãi. Utilizarea simbolului x sau a simbolului

y depinde de precedenþa operandului faþã de operator. Precedenþa operanzilor se defineºte

astfel:

· un argument între paranteze sau un argument nestructurat are precedenþa 0;

· un argument de tip structurã are precedenþa egalã cu cea a functorului operator.

Observaþie: În ARITY Prolog, cu cât valoare-precedenþã-operator este mai mare, cu

atât operatorul are o precedenþã mai micã ºi invers.

Semnificaþiile lui x ºi y în stabilirea tipului operatorului sunt urmãtoarele:

· x reprezintã un argument (operand) cu precedenþã strict mai micã decât cea a

functorului (operatorului) f

precedenþa( x ) < precedenþa( f )

· y reprezintã un argument (operand) cu precedenþã mai micã sau egalã cu cea a

functorului (operandului) f

precedenþa( y ) £ precedenþa( f )

Aceste reguli ajutã la eliminarea ambiguitãþii operatorilor multipli cu aceeaºi

precedenþã. De exemplu, operatorul predefinit în Prolog - (minus) este definit din punct de

vedere al tipului ca yfx, ceea ce înseamnã cã structura a - b - c este interpretatã ca (a - b) - c

ºi nu ca a - (b - c) . Dacã acest operator ar fi fost definit ca xfy, atunci interpretarea structurii

a - b - c ar fi fost a - (b - c) .

15

Numele operatorului poate fi orice atom Prolog care nu este deja definit în Prolog. Se

poate folosi ºi o listã de atomi, dacã se definesc mai mulþi operatori cu aceeaºi precedenþã

ºi acelaºi tip.

Exemple:

:- op(100, xfx, [este, are]).

:- op(100, xf, zboara).

coco are pene.

coco zboara.

coco este papagal.

bozo este pinguin.

?- Cine are pene.

Cine = coco

?- Cine zboara.

Cine = coco

?- Cine este Ce.

Cine = coco, Ce = papagal;

Cine = bozo, Ce = pinguin;

no

În condiþiile în care se adaugã la baza de cunoºtinþe anterioarã ºi definiþia operatorilor

daca, atunci ºi si

:- op(870, fx, daca).

:- op(880, xfx, atunci).

:- op(880, xfy, si).

urmãtoarea structurã este validã în Prolog:

daca Animalul are pene

ºi Animalul zboara

atunci Animalul este pasare.

2.6 Liste

O listã este o structurã de date ce reprezintã o secvenþã ordonatã de zero sau mai multe

elemente. O listã poate fi definitã recursiv astfel:

(1) lista vidã (lista cu 0 elemente) este o listă

(2) o listã este o structurã cu douã componente: primul element din listã (capul

listei) ºi restul listei (lista formatã din urmatoarele elemente din lista).

Sfârºitul unei liste este de obicei reprezentat ca lista vidã.

16

În Prolog structura de listã este reprezentatã printr-o structurã standard, predefinitã, al

cãrei functor este caracterul “.” ºi are douã componente: primul element al listei ºi restul

listei. Lista vidã este reprezentatã prin atomul special [ ]. De exemplu, o listã cu un singur

element a se reprezintã în Prolog, prin notaţie prefixată astfel:

.(a, [ ]) având sintaxa in ARITY Prolog '.'(a, [ ])

iar o listã cu trei elemene, a, b, c, se reprezintã ca:

.(a, . (b, . (c, [ ]))) cu sintaxa în ARITY Prolog '.'(a, '. '(b, '. '(c, [ ]))).

Deoarece structura de listã este foarte des utilizatã în Prolog, limbajul oferã o sintaxã

alternativã pentru descrierea listelor, formatã din elementele listei separate de virgulã ºi

încadrate de paranteze drepte. De exemplu, cele douã liste anterioare pot fi exprimate astfel:

[a]

[a, b, c]

Această sintaxă a listelor este generală şi valabilă în orice implementare Prolog. O

operaþie frecventã asupra listelor este obþinerea primului element dintr-o listã ºi a restului

listei, deci a celor douã componente ale structurii de listã. Aceasta operaþie este realizatã în

Prolog de operatorul de scindare a listelor “|” scris sub urmãtoarea formã:

[Prim | Rest]

Variabila Prim stã pe postul primului element din listã, iar variabila Rest pe postul

listei care conþine toate elementele din listă cu excepţia primului. Acest operator poate fi

aplicat pe orice listã care conþine cel puþin un element. Dacã lista conþine exact un

element, Rest va reprezenta lista vidã. Încercarea de identificare a structurii [Prim | Rest]

cu o listã vidã duce la eºec. Mergând mai departe, se pot obþine chiar primele elemente ale

listei ºi restul listei. Iatã câteva echivalenþe:

[a, b, c] = [a | [b, c] ] = [a, b | [c] ] = [a, b, c | [ ] ] = [a | [b | [c] ] ] = [a | [b | [c |

[ ] ] ] ].

În Prolog elementele unei liste pot fi atomi, numere, liste ºi în general orice structuri.

În consecinþã se pot construi liste de liste.

Exemple:

1. Se poate defini urmãtoarea structurã de listã:

[carte(barbu, poezii), carte(clocksin, prolog)]

2. Considerând urmãtoarele fapte existente în baza de cunoºtinþe Prolog

pred([1, 2, 3, 4]).

pred([coco, sta, pe, [masa, alba]]).

17

se pot pune urmãtoarele întrebãri obþinând rãspunsurile specificate:

?- pred([Prim | Rest]).

Prim = 1, Rest = [2, 3, 4];

Prim = coco, Rest = [sta, pe, [masa, alba]];

no

?- pred([ _, _ , _ , [ _ | Rest]])

Rest = [alba]

3. Un predicat util în multe aplicaþii este cel care testeazã apartenenþa unui element la

o listã ºi care se defineºte astfel:

% membru(Element, Lista)

membru(Element, [Element | _ ]).

membru(Element, [ _ | RestulListei]) :- membru(Element, RestListei).

Funcþionarea acestui scurt program Prolog poate fi urmãritã cerând rãspunsul

sistemului la urmãtoarele scopuri:

?- membru(b, [a, b, c]). %1

yes

?- membru(X, [a, b, c]). %2

X = a;

X = b;

X = c;

no

?- membru(b, [a, X, b]). %3

X = b;

X = _0038;

no

Deci pentru cazul în care primul argument este o variabilã (%2) existã trei soluþii

posibile ale scopului membru(Element, Lista). Dacă lista conþine o variabilã (%3)

existã douã soluþii pentru forma listei ([a, b, b] sau [a, _ , b]).

4. Un alt predicat util este cel de concatenare a douã liste L1 ºi L2, rezultatul

concatenãrii obþinându-se în lista L3, iniţial neinstanţiată.

% conc(L1, L2, L3)

conc([], L2, L2). % lista vidã concatenatã cu L2 este L2.

conc([Prim1|Rest1], Lista2, [Prim1|Rest3]) :-

conc(Rest1, Lista2, Rest3).% lista rezultatã este primul element

% al sublistei curente din L1 concatenat

18

% cu lista întoarsã de apelul recursiv.

?- conc([a, b], [c, d, e], L3).

L3 = [a, b, c, d, e];

no

?- conc([a, b], [c, d, e], L3).

L3 = [a, b, c, d, e]. % “.” şi Enter când nu cãutãm alte soluþii

yes

?- conc(L1, [c, d, e], [a, b, c, d, e]).

L1 = [a, b];

no

?- conc([a, b], L2, [a, b, c, d, e]).

L2 = [c, d, e];

no

?- conc(L1, L2, [a, b]).

L1 = [ ], L2 = [a, b];

L1 = [a], L2 = [b];

L1 = [a, b], L2 = [ ];

no

Se observã cã pentru cazul în care predicatul de concatenare are un singur argument

neinstanþiat existã o singurã soluþie, iar pentru cazul în care primele douã

argumente sunt neinstanþiate (variabile) se obþin mai multe soluþii,

corespunzãtoare tuturor variantelor de liste care prin concatenare genereazã cea de a

treia listã.

5. Urmãtorul exemplu defineºte predicatul de testare a existenþei unei sortãri în ordine

crescãtoare a elementelor unei liste de întregi. Predicatul reuºeºte dacã elementele

listei sunt sortate crescãtor ºi eºueazã în caz contrar.

% sortcresc(Lista)

sortcresc([ ]). % lista vidã se considerã sortatã

sortcresc([ _ ]). % lista cu un singur element este sortatã

sortcresc([X, Y | Rest]) :- X = < Y, sortcresc([Y | Rest]).

?- sortcresc([1, 2, 3, 4]).

yes

?- sortcresc([1, 3, 5, 4]).

no

?- sortcresc([ ]).

yes

Dacã se considerã cã lista vidã nu este o listã sortatã crescãtor atunci se poate

elimina faptul:

19

sortcresc([ ]).

din definiþia predicatului sortcresc, comportarea lui pentru liste diferite de lista

vidã rãmânând aceeaºi.

Observaþii:

· Exemplul 3 pune în evidenþã o facilitate deosebit de interesantã a limbajului

Prolog, respectiv puterea generativã a limbajului. Predicatul membru poate fi

utilizat atât pentru testarea apartenenþei unui element la o listã, cât ºi pentru

generarea, pe rând, a elementelor unei liste prin resatisfacere succesivã. În

anumite contexte de utilizare aceastã facilitate poate fi folositoare, iar în altele ea

poate genera efecte nedorite atunci când predicatul membru este utilizat în

definirea altor predicate, aºa cum se va arãta în partea a doua a lucrării.

· Aceeaºi capacitate generativã a limbajului Prolog poate fi observatã ºi în Exemplul

4 unde în funcþie de combinaþiile de argumente instanþiate ºi neinstanþiate,

predicatul conc poate produce rezultate relativ diferite.

· La definirea unui predicat p care va fi utilizat în definirea altor predicate trebuie

întotdeauna sã se analizeze numãrul de soluþii ºi soluþiile posibile ale

predicatului p. Acest lucru este necesar deoarece dacã p apare într-o conjuncþie

de scopuri p1,…, pi-1, p ,pi+1,…, pn ºi unul dintre scopurile pi+1,…, pn eºueazã,

mecanismul de backtracking din Prolog va încerca resatisfacerea scopului p.

Numãrul de soluþii ºi soluþiile scopului p influenþeazã astfel, în mod evident,

numãrul de soluþii ºi soluþiile conjuncþiei de scopuri p1,…, pi-1, p ,pi+1,…, pn.

Exemple în acest sens ºi modalitãþi de reducere a numãrului total de soluþii ale

unui corp vor fi prezentate în Secþiunea 4.2.

3 Limbajul Prolog ºi logica cu predicate de ordinul I

Limbajul Prolog este un limbaj de programare logicã. Deşi conceput iniţial pentru

dezvoltarea unui interpretor de limbaj natural, limbajul s-a impus ca o soluþie practicã de

construire a unui demonstrator automat de teoreme folosind rezoluþia. Demonstrarea

teoremelor prin metoda rezoluþiei necesitã ca axiomele ºi teorema sã fie exprimate în forma

clauzalã, adică o disjuncţie de literali, unde un literal este un predicat sau un predicat negat.

Pentru detalii despre noţiunea de clauză şi modul de transformare a unei formule din logica

cu predicate de ordinul I în formă clauzală se poate consulta [Flo93]. Sintaxa ºi semantica

limbajului Prolog permit utilizarea numai a unei anumite forme clauzale a formulelor bine

formate: clauze Horn distincte.

Deoarece faptele ºi regulile Prolog sunt în formã clauzalã, forma particularã a

clauzelor fiind clauze Horn distincte, ele se mai numesc ºi clauze Prolog.

20

Definiþie. Se numeºte clauzã Horn o clauzã care conþine cel mult un literal pozitiv. O

clauzã Horn poate avea una din urmãtoarele patru forme:

(1) o clauzã unitarã pozitivã formatã dintr-un singur literal pozitiv (literal

nenegat);

(2) o clauzã negativã formatã numai din literali negaþi;

(3) o clauzã formatã dintr-un literal pozitiv ºi cel puþin un literal negativ, numitã

ºi clauzã Horn mixtã;

(4) clauzã vidã ( · ).

Definiþie. Se numeºte clauzã Horn distinctã o clauzã care are exact un literal pozitiv, ea

fiind fie o clauzã unitarã pozitivã, fie o clauzã Horn mixtã.

Clauzele Horn unitare pozitive se reprezintã în Prolog prin fapte, iar clauzele Horn

mixte prin reguli. O clauzã Horn mixtã de forma:

~S1 Ú ~S2 Ú…Ú ~Sn Ú S

se exprimã în Prolog prin regula:

S :- S1, S2, …Sn.

Semnificaþia intuitivã a unei reguli Prolog are un corespondent clar în logica cu

predicate de ordinul I dacã se þine cont de faptul cã o clauzã Horn mixtã poate proveni din

urmãtoarea formulã bine formatã:

S1 Ù S2 Ù…Ù Sn ® S

Variabilele din clauzele distincte se transformã în variabile Prolog, constantele din

aceste formule în constante Prolog, iar funcþiile pot fi asimilate cu structuri Prolog. Deci

argumentele unui predicat Prolog au forma termenilor din calculul cu predicate de ordinul I.

Exemple:

1. Fie urmãtoarele enunþuri: Orice sportiv este puternic. Oricine este inteligent ºi

puternic va reuºi în viaþã. Oricine este puternic va reuºi în viaþã sau va ajunge

bãtãuº. Existã un sportiv inteligent. Gelu este sportiv. Exprimând enunþurile în

logica cu predicate de ordinul I se obþin urmãtoarele formule bine formate:

A1. ("x) (sportiv(x) ® puternic(x))

A2. ("x) (inteligent(x) Ù puternic(x) ® reuºeºte(x))

A3. ("x) (puternic(x) ® (reuºeºte(x) Ú bãtãuº(x)))

A4. ($x) (sportiv(x) Ù inteligent(x))

A5. Sportiv(gelu)

Axiomele se transformã în forma clauzalã ºi se obþin urmãtoarele clauze:

21

C1. ~ sportiv(x) Ú puternic(x)

C2. ~ inteligent(x) Ú ~ puternic(x) Ú reuseste(x)

C3. ~ puternic(x) Ú reuseste(x) Ú bataus(x)

C4. sportiv(a)

C4'. inteligent(a)

C5. sportiv(gelu)

Clauzele C1, C2, C4, C4' ºi C5 pot fi transformate în Prolog deoarece sunt clauze

Horn distincte, dar clauza C3 nu poate fi transformatã în Prolog. Programul Prolog

care se obþine prin transformarea acestor clauze este urmãtorul:

puternic(X) :- sportiv(X).

reuseste(X) :- inteligent(X), puternic(X).

sportiv(a).

inteligent(a).

sportiv(gelu).

2. Fie urmãtoarele enunþuri:

(a) Orice numãr raþional este un numãr real.

(b) Existã un numãr prim.

(c) Pentru fiecare numãr x existã un numãr y astfel încât x < y .

Dacã se noteazã cu prim(x) “x este numãr prim”, cu rational(x) ”x este numãr

raþional”, cu real(x) “x este numãr real” ºi cu mai_mic(x, y) “x este mai mic

decât y“, reprezentarea sub formã de formule bine formate în calculul cu predicate

de ordinul I este urmãtoarea:

A1. ("x) (raþional(x) ® real(x))

A2. ($x) prim(x)

A3. ("x) ($y) mai_mic(x, y)

Reprezentarea în formã clauzalã este:

C1. ~ rational(x) Ú real(x)

C2. prim(a)

C3. mai_mic(x, mai_mare(x))

unde mai_mare(x) este funcþia Skolem care înlocuieºte variabila y cuantificatã

existenþial. Forma Prolog echivalentã a acestor clauze este:

real(X) :- rational(X).

prim(a).

22

mai_mic(X, mai_mare(X)).

unde mai_mare(x) este o structurã Prolog.

Este evident cã nu orice axiomã poate fi transformatã în Prolog ºi cã, dintr-un anumit

punct de vedere, puterea expresivã a limbajului este inferioarã celei a logicii cu predicate de

ordinul I. Pe de altã parte, limbajul Prolog oferã o mulþime de predicate de ordinul II, adicã

predicate care acceptã ca argumente alte predicate Prolog, care nu sunt permise în logica cu

predicate de ordinul I. Acest lucru oferã limbajului Prolog o putere de calcul superioarã

celei din logica clasicã. Uneori, aceste predicate de ordinul II existente în Prolog pot fi

folosite pentru a modela versiuni de programe Prolog echivalente cu o mulþime de axiome

care nu au o reprezentare în clauze Horn distincte.

Se propune cititorului, dupã parcurgerea secþiunii urmãtoare, sã revinã la Exemplul 1

ºi sã încerce gãsirea unei forme Prolog relativ echivalente (cu un efect similar) cu clauza

C3.

Limbajul Prolog demonstreazã scopuri (teoreme) prin metoda respingerii rezolutive

[Flo93]. Strategia rezolutivã utilizatã este strategia de intrare liniară, strategie care nu este în

general completă dar este completă pentru clauze Horn. Această strategie este deosebit de

eficientă din punct de vedere al implementării şi jutifică astfel forma restricţionată a

clauzelor Prolog.

4 Structura de control a limbajului Prolog

În această secţiune se prezintă în detaliu structura de control specifică sistemului Prolog.

Spre deosebire de limbajele de programare clasice, în care programul defineşte integral

structura de control şi fluxul de prelucrări de date, în Prolog există un mecanism de control

predefinit.

4.1 Semnificaþia declarativã ºi proceduralã a programelor Prolog

Semnificaþia declarativã a unui program Prolog se referã la interpretarea strict logicã a

clauzelor acelui program, rezultatul programului fiind reprezentat de toate consecinþele

logice ale acestuia. Semnificaþia declarativã determinã dacã un scop este adevãrat (poate fi

satisfãcut) ºi, în acest caz, pentru ce instanþe de variabile este adevãrat scopul. Se

reaminteºte cã o instanþã a unei clauze este clauza de bazã (clauza fãrã variabile) obþinutã

prin instanþierea variabilelor din clauza iniþialã. În aceste condiþii semnificaþia declarativã

a unui program Prolog se poate defini precum urmeazã:

Definiþie. Un scop S este adevãrat într-un program Prolog, adicã poate fi satisfãcut sau

derivă logic din program, dacã ºi numai dacã:

1.1 existã o clauzã C a programului;

23

1.2 existã o instanþã I a clauzei C astfel încât:

1.2.1 antetul lui I sã fie identic cu cel al lui S;

1.2.2 toate scopurile din corpul lui I sunt adevãrate, deci pot fi satisfãcute.

Observaþii:

· În definiþia de mai sus clauzele referã atât fapte cât ºi reguli Prolog. Antetul unei

clauze este antetul regulii dacã clauza este o regulã Prolog (clauzã Horn mixtã) ºi

este chiar faptul dacã clauza este un fapt Prolog (clauzã unitarã pozitivã). Corpul

unui fapt este considerat vid ºi un fapt este un scop care se îndeplineºte

întotdeauna.

· În cazul în care întrebarea pusã sistemului Prolog este o conjuncþie de scopuri,

definiþia anterioarã se aplicã fiecãrui scop din conjuncþie.

Semnificaþia proceduralã a unui program Prolog se referã la modul în care sistemul

încearcã satisfacerea scopurilor, deci la strategia de control utilizatã. Diferenþa dintre

semnificaþia declarativã ºi semnificaþia proceduralã este aceea cã cea de a doua defineºte,

pe lânga relaþiile logice specificate de program, ºi ordinea de satisfacere a scopurilor ºi

subscopurilor. În prima secþiune a acestui capitol s-a fãcut o prezentare informalã a

modalitãþii procedurale de satisfacere a scopurilor în Prolog. În continuare se rafinează

această comportare. Din punct de vedere procedural, un program Prolog poate fi descris de

schema bloc prezentatã în figura 3.

Figura 3. Comportarea proceduralã a sistemului Prolog

Semnificaþia proceduralã a unui program Prolog poate fi descrisã de urmãtorul

algoritm în care L = {S1, S2, …, Sn} este lista de scopuri de satisfãcut, iar B este lista de

instanþieri (unificări) ale variabilelor din scopuri, iniþial vidã. Aceastã listã se va actualiza

la fiecare apel.

Algoritm. Strategia de control Prolog

SATISFACE(L,B)

1. dacã L = {} % lista vidã

atunci afiºeazã B ºi întoarce SUCCES.

2. Fie S1 ¬ primul scop din L ºi p predicatul referit de S1. Parcurge clauzele programului, de la prima clauzã sau de la ultimul marcaj fixat, asociat lui p, pânã ce se gãseºte o clauzã C al cãrei antet unificã cu S1.

Execuþie

sistem Prolog

conjuncþiide scopuri

program Prolog

indicator SUCCES/INSUCCES

instanþele variabilelor din scopuri

24

3. dacã nu existã o astfel de clauzã

atunci întoarce INSUCCES.

4. Fie C de forma H :- D1,…,Dm, m³0. Plaseazã un marcaj în dreptul clauzei C, asociat lui p. (H conþine predicatul p).

5. Redenumeºte variabilele din C ºi obtine C' astfel încât sã nu existe nici o variabilã comunã între C' ºi L; C' este de tot forma H :- D1,…,Dm. cu redenumirile făcute.

6. L’ ¬ { D1,…,Dm, S2,…,Sn } % dacã C este fapt, atunci L se va reduce

7. Fie B1 instanþierea variabilelor care rezultã din unificarea lui S1 cu H.

8. Substituie variabilele din L’ cu valorile date de B1 ºi obþine:

L” ¬ { D1’,…,Dm’, S2’,…,Sn’ }.

9. B ¬ B È B1.

10. dacã SATISFACE(L”, B)=SUCCES

atunci afiºeazã B ºi întoarce SUCCES.

11. repetă de la 1.

sfârºit

Observaþii:

· Algoritmul de mai sus reprezintã de fapt implementarea strategiei rezolutive de

intrare liniară utilizată de limbajul Prolog, pentru care se impune o ordine

prestabilită de considerare a clauzelor.

· Algoritmul aratã funcþionarea sistemului pentru gãsirea primei soluþii.

· Indicatorul SUCCES/INSUCCES corespunde rãspunsurilor de yes, respectiv no,

date de sistemul Prolog la încercarea de satisfacere a unei liste de scopuri.

Urmãtoarele douã exemple pun în evidenþã diferenþa dintre semnificaþia declarativã

ºi semnificaþia proceduralã a programelor Prolog. Primul exemplu este un scurt program

care defineºte relaþiile de pãrinte ºi strãmoº existente între membrii unei familii. Se dau

patru definiþii posibile ale relaþiei de strãmoº, str1, str2, str3 ºi str4, toate fiind perfect

corecte din punct de vedere logic, deci din punct de vedere a semnificaþiei declarative a

limbajului.

% parinte(IndividX, IndividY)

% stramos(IndividX, IndividZ)

parinte(vali, gelu).

parinte(ada, gelu).

parinte(ada, mia).

parinte(gelu, lina).

parinte(gelu, misu).

parinte(misu, roco).

25

str1(X, Z) :- parinte(X, Z).

str1(X, Z) :- parinte(X, Y), str1(Y, Z).

% Se schimbã ordinea regulilor:

str2(X, Z) :- parinte(X, Y), str2(Y, Z).

str2(X, Z) :- parinte(X, Z).

% Se schimbã ordinea scopurilor în prima variantã:

str3(X, Z) :- parinte(X, Z).

str3(X, Z) :- str3(X, Y), parinte(Y, Z).

% Se schimbã atât ordinea regulilor, cât ºi ordinea scopurilor:

str4(X, Z) :- str4(X, Y), parinte(Y, Z).

str4(X, Z) :- parinte(X,Z).

Figura 4. Arborele genealogic definit de programul Prolog

Figura 4 prezintă arborele genealogic definit de faptele Prolog anterioare. În raport cu

semantica declarativã a limbajului se pot schimba, fãrã a modifica înþelesul logic, atât

ordinea clauzelor care definesc relaþia de strãmoº, cât ºi ordinea scopurilor în corpul regulii

de aflare a strãmoºilor. Schimbând ordinea clauzelor se obþine din predicatul str1 definiþia

alternativã a relaþiei de strãmoº str2; schimbând ordinea scopurilor din corpul regulii în

varianta iniþialã se obþine definiþia predicatului str3; ºi, schimbând atât ordinea clauzelor,

cât ºi ordinea scopurilor în regulã, se obþine predicatul str4.

Comportarea programului folosind cele patru definiþii alternative, dacã se doreºte

aflarea adevãrului relaþiei de strãmoº pentru perechile (ada, miºu) ºi (mia, roco), este cea

prezentatã în continuare.

?- str1(ada, misu).

yes

vali ada

gelu mia

lina mişu

roco

26

Pentru acest scop, arborele de deducþie este prezentat în figura 5.

Figura 5. Arborele de deducţie a scopului str1(ada, misu)

?- str2(ada, misu).

yes

?- str3(ada, misu).

yes

Pentru scopul str3(ada, misu), arborele de deducþie este cel prezentat în figura 6.

Figura 6. Arborele de deducţie a scopului str3(ada, misu)

?- str4(ada, misu).

% buclã infinita; eventual mesaj de depãºire a stivei

Pentru acest scop, arborele de deducþie este cel prezentat în figura 7.

str1(ada, misu)

parinte(ada, misu)

INSUCCES

parinte(ada, Y), str1(Y, misu)

parinte(ada, gelu)

Y=gelu

SUCCES

str1(gelu, misu)

parinte(gelu, misu)

SUCCES

str3(ada, misu)

parinte(ada, misu)

INSUCCES

str3(ada, Y), parinte(Y, misu)

parinte(ada, Y')

Y=Y'

SUCCES

parinte(gelu, misu)

SUCCES

parinte(ada, gelu)

Y'=gelu

27

Figura 7. Arborele de deducţie (infinit) a scopului str4(ada, misu)

Din punctul de vedere al semnificaþiei procedurale, cele patru definiþii nu sunt

echivalente. Primele douã, str1 şi str2, pot da rãspuns pozitiv sau negativ la orice întrebare,

dar str2 este mai ineficientã decât str1. Cititorul poate încerca trasarea arborelui de

deducþie al satisfacerii scopului str2(ada, misu) ºi compararea acestuia cu cel

corespunzãtor satisfacerii scopului str1(ada, misu). Definiþia str4 produce o buclã infinitã

datoritã intrãrii infinite în recursivitate. Este evident o definiþie greºitã din punct de vedere

procedural. Definiþia relaþiei de strãmoº str3 este o definiþie "capcanã". Dupã cum se poate

observã din arborele de deducþie prezentat, rãspunsul sistemului este afirmativ în cazul în

care existã o relaþie de strãmoº între cele douã persoane argumente ale predicatului. În cazul

în care o astfel de relaþie nu existã, sistemul intrã într-o buclă infinitã, cum ar fi, de

exemplu, pentru persoanele mia ºi roco.

?- str1(mia, roco).

no

?- str2(mia, roco).

no

?- str3(mia, roco).

% buclã infinitã; eventual mesaj de depãºire a stivei

În acest caz, arborele de deducþie al scopului str3(mia, roco) este prezentat în figura

8. Datoritã semnificaþiei procedurale a limbajului Prolog trebuie urmãrit cu atenþie modul

de definire a unui predicat atât din punctul de vedere al ordinii clauzelor, cât ºi din punctul

de vedere al ordinii scopurilor în corpul regulilor.

str4(ada, misu)

str4(ada, Y), parinte(Y, misu)

str4(ada, Y'), parinte(Y', Y)

str4(ada, Y"), parinte(Y", Y)

arbore infinit...

28

Figura 8. Arbore de deducţie infinit pentru un scop fals

Al doilea exemplu se referã la rezolvarea în Prolog a urmãtoarei probleme. O

maimuþã se gãseºte la uºa unei camere ºi o bananã se aflã agãþatã de plafon în centrul

camerei. Lângã fereastra camerei se aflã o cutie pe care maimuþa o poate folosi pentru a se

urca pe ea ºi a ajunge la bananã. Maimuþa ºtie sã facã urmãtoarele miºcãri: sã meargã pe

sol, sã se urce pe cutie, sã deplaseze cutia dacã este lângã cutie, sã apuce banana dacã este

pe cutie ºi cutia este în centrul camerei. Se cere sã se scrie un program Prolog care sã

descrie aceastã problema ºi care sã poatã rãspunde dacã, dintr-o configuraþie iniþialã

specificatã prin poziþia maimuþei ºi a cubului, maimuþa poate apuca banana dupã execuþia

unei secvenþe de miºcãri.

Reprezentarea universului problemei în Prolog este specificată după cum urmează.

Starea iniþialã este:

(1) Maimuþa este la uºã.

(2) Maimuþa este pe sol.

(3) Cutia este la fereastrã.

(4) Maimuþa nu are banana.

şi poate fi descrisã prin structura Prolog:

stare(la_usa, pe_sol, la_fereastra, nu_are_banana)

Starea finalã este aceea în care maimuþa are banana

stare( _ , _ , _ , are_banana)

Miºcãrile cunoscute de maimuþã, deci operatorii de tranziþie dintr-o stare în alta, sunt:

(m1) Apucã banana. apucã

(m2) Urcã pe cutie. urcã

(m3) Mutã cutia. mutã(Poziþia1, Poziþia2)

str3(mia, roco)

parinte(mia, roco)

INSUCCES

str3(mia, Y), parinte(Y, roco)

parinte(mia, Y)

INSUCCES

str3(mia, Y'), parinte(Y', Y)

parinte(mia, Y')

INSUCCES

str3(mia, Y"), parinte(Y", Y')

parinte(mia, Y")

INSUCCES

...arbore infinit

29

(m4) Merge (maimuþa se deplaseazã pe sol). merge(Poziþia1, Poziþia2)

şi sunt reprezentate prin structurile Prolog indicate la dreapta miºcãrilor.

Dintr-o anumitã stare numai anumite miºcãri sunt permise. De exemplu, maimuţa nu

poate apuca banana decât dacã este urcatã pe cutie şi cutia este în centrul camerei, adicã sub

bananã. Miºcãrile permise pot fi reprezentate în Prolog prin predicatul de deplasare depl cu

trei argumente:

depl(Stare1, Miºcare, Stare2)

care transformã problema din starea Stare1 în starea Stare2 prin efectuarea miºcãrii legale

Miºcare în starea Stare1. Se observã cã reprezentarea aleasã este o reprezentare a

problemei folosind spaþiul stãrilor [Flo93].

Soluþia problemei este completatã prin adãugarea predicatului poatelua(Stare) care

va reuºi dacă maimuţa poate ajunge din starea iniþialã Stare într-o stare finalã în care poate

lua banana, stare finalã descrisã de:

poate_lua(stare( _ , _ , _ , are_banana)).

Programul Prolog complet este prezentat în continuare.

% Structura stare:

% stare(poz_o_maimuta, poz_v_maimuta, poz_cub, are_nu_are_banana)

% Miºcãri admise: apucã, urca, muta(Pozitia1, Pozitia2), merge(Pozitia1, Pozitia2),

% reprezentate tot prin structuri.

% Predicate:

% depl(Stare1, Miscare, Stare2)

% poate_lua(Stare)

depl(stare(la_centru, pe_cutie, la_centru, nu_are_banana),

apuca, stare(la_centru, pe_cutie, la_centru, are_banana)).

depl(stare(P, pe_sol, P, H), urca, stare(P, pe_cutie, P, H)).

depl(stare(P1, pe_sol, P1, H), muta(P1, P2), stare(P2, pe_sol, P2, H)).

depl(stare(P1, pe_sol, B, H), merge(P1, P2), stare(P2, pe_sol, B, H)).

poate_lua(stare( _ , _ , _ , are_banana)).

poate_lua(Stare1) :- depl(Stare1, Miscare, Stare2), poate_lua(Stare2).

La întrebarea

?- poate_lua(stare(la_usa, pe_sol, la_fereastra, nu_are_banana)).

yes

sistemul rãspunde afirmativ: maimuţa este fericitã şi mãnâncã banana.

Stare1 Stare2Mişcare

30

O analizã atentã a programului conduce la concluzia cã programul dã soluþii numai

pentru anumite situaþii. În primul rând, strategia de control a miºcãrilor maimuþei este

impusã de ordinea clauzelor care definesc predicatul depl. Astfel, maimuţa preferã întâi sã

apuce, apoi sã urce, apoi sã mute cubul şi numai la urmã sã mearga prin camerã. Dacã

clauza corespunzãtoare miºcãrii merge(Pozitia1, Pozitia2) ar fi fost pusã ca prima clauzã în

definiþia predicatului de deplasare, maimuţa ar fi mers la infinit prin camerã fãrã sã mai

ajungã sa mute cubul sau sã apuce banana. Chiar pentru ordinea datã a clauzelor, dacă se

pune întrebarea

?- poate_lua(stare(X, pe_sol, la_fereastra, nu_are_banana)).

deci dacă intereseazã din ce poziþii maimuţa poate lua banana, rezolvarea datã nu este total

satisfãcãtoare deoarece programul are o infinitate de soluþii. La cererea repetatã a unei

soluþii, se va afiºa întotdeauna valoarea:

X = la_fereastra

Considerând din nou modelul spaþiului stãrilor, se observã cã în acest caz este vorba

de un spaþiu de cãutare de tip graf în care o aceeaºi stare poate fi descoperitã şi

redescoperitã la infinit prin parcurgerea unui ciclu de tranziþii de stãri în acest graf. Aºa

cum este arãtat în [Flo93], astfel de cazuri trebuie tratate prin introducerea unor liste de stãri

parcurse (listele FRONTIERA şi TERITORIU) care sã împiedice parcurgerea repetatã a

unor stãri deja parcurse.

Pericolul de apariþie a unor cicluri infinite datoritã parcurgerii unui spaþiu de cãutare

graf nu este specific limbajului Prolog şi poate sã aparã în orice implementare, în aceste

cazuri. Ceea ce este neobiºnuit în raport cu alte limbaje este faptul cã semnificaþia

declarativã a programului este corectã, indiferent de ordonarea clauzelor, în timp ce

programul este procedural incorect, având comportãri diferite în funcþie de aceastã

ordonare. Rezolvarea problemei ar mai trebui completatã cu afiºarea stãrilor şi a miºcãrilor

executate de maimuţã pentru a ajunge în starea finalã în care ea poate apuca banana.

Modalităţi de eliminare a ciclurilor infinite de tipul celor ce apar în această problemă vor fi

discutate in partea a doua a lucrării.

4.2 Controlul procesului de backtracking: cut şi fail

Sistemul Prolog intrã automat într-un proces de backtraking dacă acest lucru este necesar

pentru satisfacerea unui scop. Acest comportament poate fi în unele situaþii deosebit de util,

dar poate deveni foarte ineficient în alte situaţii. Se considerã urmãtorul exemplu de

program în care se definesc valorile unei funcþii:

f(X, 0) :- X < 3. % 1

f(X, 2) :- 3 =< X, X < 6. % 2

f(X, 4) :- 6 =< X. % 3

La întrebarea:

31

?- f(1, Y).

Y = 0

sistemul rãspunde indicând cã valoarea funcþiei pentru X=1 este Y=0. Dacã se pune

întrebarea formatã din conjuncþia de scopuri:

?- f(1, Y), 2 < Y.

no

sistemul semnaleazã eºec. Arborii de deducţie corespunzători acestor răspunsuri sunt

prezentaţi în figura 9.

Figura 9. Arborii de deducţie a scopurilor f(1,Y) şi f(1,Y),2 < Y

Se observã cã se încearcã resatisfacerea primului scop cu regulile 2 şi 3, deºi acest

lucru este evident inutil datoritã semanticii acestor reguli. Cel care a scris aceste reguli poate

cu uºurinþã constata cã, dacă o valoare mai micã decât 3 pentru X duce la eºecul scopului S

din conjuncþia de scopuri f(X, Y), S, este inutil sã se încerce resatisfacerea scopului f,

deoarece aceasta nu este posibilã [Bra88]. Se poate împiedica încercarea de resatisfacere a

scopului f(X, Y) prin introducerea predicatului cut.

Predicatul cut, notat cu atomul special !, este un predicat standard, fãrã argumente,

care se îndeplineºte (este adevãrat) întotdeauna şi nu poate fi resatisfãcut.

Predicatul cut are urmãtoarele efecte laterale:

· La întâlnirea predicatului cut toate selecþiile fãcute între scopul antet de regulã şi

cut sunt "îngheþate", deci marcajele de satisfacere a scopurilor sunt eliminate,

ceea ce duce la eliminarea oricãror altor soluþii alternative pe aceasta porþiune.

O încercare de resatisfacere a unui scop între scopul antet de regula şi scopul

curent va eºua.

· Dacã clauza în care s-a introdus predicatul cut reuºeºte, toate clauzele cu acelasi

antet cu aceasta, care urmeazã clauzei în care a apãrut cut vor fi ignorate. Ele nu

se mai folosesc în încercarea de resatisfacere a scopului din antetul clauzei care

conþine cut.

· Pe scurt, comportarea predicatului cut este urmãtoarea:

f(1,Y)

f(1,0)

X=1Y=0

1<3

SUCCES

f(1,Y), 2<Y

f(1,0)

X=1Y=0

2<0

INSUCCES

1=<3

f(1,2)

X=1Y=2

f(1,4)

X=1Y=4

INSUCCES

3=<1 6=<1

INSUCCES

32

(C1) H :- D1, D2, …, Dm, !, Dm+1, …, Dn.

(C2) H :- A1, …, Ap.

(C3) H.

Dacă D1, D2, …, Dm sunt satisfãcute, ele nu mai pot fi resatisfãcute datoritã lui cut.

Dacã D1, …, Dm sunt satisfãcute, C2 şi C3 nu vor mai fi utilizate pentru

resatisfacerea lui H. Resatisfacerea lui H se poate face numai prin resatisfacerea

unuia din scopurile Dm+1, …, Dn, dacă acestea au mai multe soluţii.

Utilizând predicatul cut, definiþia funcþiei f(X, Y) poate fi rescrisã mult mai eficient

astfel:

f(X, 0) :- X < 3, !.

f(X, 2) :- 3 =< X, X < 6, !.

f(X, 4) :- 6 =< X.

Predicatul cut poate fi util în cazul în care se doreºte eliminarea unor paºi din deducþie

care nu conþin soluþii sau eliminarea unor cãi de cãutare care nu conþin soluþii. El permite

exprimarea în Prolog a unor structuri de control de tipul:

dacă condiþie atunci acþiune1

altfel acþiune2

astfel:

daca_atunci_altfel(Cond, Act1, Act2) :- Cond, !, Act1.

daca_atunci_altfel(Cond, Act1, Act2) :- Act2.

Se observã însã cã existã douã contexte diferite în care se poate utiliza predicatul cut:

într-un context predicatul cut se introduce numai pentru creºterea eficienþei programului,

caz în care el se numeºte cut verde; în alt context utilizarea lui cut modificã semnificaþia

proceduralã a programului, caz în care el se numeºte cut roºu.

Exemplul de definire a funcþiei f(X, Y) cu ajutorul lui cut este un exemplu de cut

verde. Adãugarea lui cut nu face decât sã creascã eficienþa programului, dar semnificaþia

proceduralã este aceeaºi, indiferent de ordinea în care se scriu cele trei clauze.

Utilizarea predicatului cut în definirea predicatului asociat structurii de control

daca_atunci_altfel introduce un cut roºu deoarece efectul programului este total diferit

dacă se schimbã ordinea clauzelor. Introducerea unui cut roºu modificã corespondenþa

dintre semnificaþia declarativã şi semnificaþia proceduralã a programelor Prolog.

Se considerã exemplul de definire a predicatului de aflare a minimului dintre douã

numere, în urmãtoarele douã variante:

min1(X, Y, X) :- X =< Y, !. % cut verde

33

min1(X, Y, Y) :- X > Y.

min2(X, Y, X) :- X =< Y, !. % cut roºu

min2(X, Y, Y).

În definiþia predicatului min1 se utilizeazã un cut verde; el este pus pentru creºterea

eficienþei programului, dar ordinea clauzelor de definire a lui min1 poate fi schimbatã fãrã

nici un efect asupra rezultatului programului. În cazul predicatului min2 se utilizeazã un cut

roºu, asemãnãtor structurii daca_atunci_altfel. Dacã se schimbã ordinea clauzelor de

definire a predicatului min2:

min2(X, Y, Y).

min2(X, Y, X) :- X =< Y, !.

rezultatul programului va fi evident incorect pentru valori X < Y.

În anumite cazuri efectul introducerii predicatului cut poate fi mai subtil. Se considerã

din nou definiþia predicatului membru:

membru(X, [X | _]).

membru(X, [ _ |Y]) :- membru(X, Y).

şi o definiþie alternativã

membru1(X, [X| _]) :- !.

membru1(X, [ _ |Y]) :- membru1(X, Y).

Introducerea predicatului cut în definiţia primei clauze a predicatului membru1 este

justificatã datoritã creºterii eficienþei programului. Odatã ce s-a descoperit cã un element

este membru al unei liste, este inutilã încercarea de resatisfacere a scopului. Cu toate acestea

predicatul cut de mai sus nu este un cut verde, deoarece el schimbã comportarea

programului în cazul în care se pun întrebãri în care X este variabila neinstanþiatã în

predicatele membru şi membru1.

?- membru(X, [a, b, c]).

X = a;

X = b;

X = c;

no

trei soluþii pentru membru

?- membru1(X, [a, b, c]).

X = a;

no

o soluþie pentru membru1.

34

Efectul introducerii predicatului cut asupra semnificaþiei declarative a programelor

Prolog poate fi rezumat astfel:

p :- a, b. % Semnificaþia declarativã este:

p :- c. % (a Ù b) Ú c% indiferent de ordinea clauzelor (în general).

p :- a, !, b. % Semnificaþia declarativã este:

p :- c. % (a Ù b) Ú (~ a Ù c).

p :- c. % Semnificaþia declarativã este:

p :- a, !, b. % c Ú (a Ù b).

Oportunitatea utilizãrii unui cut roºu sau a unui cut verde este, dintr-un anumit punct

de vedere, similarã cu cea a utilizãrii sau nu a salturilor în limbajele de programare clasicã.

Dacă s-ar rescrie predicatul daca_atunci_altfel folosind un cut verde, definiþia lui ar fi:

daca_atunci_altfel(Cond, Act1, Act2) :- Cond, !, Act1.

daca_atunci_altfel(Cond, Act1, Act2) :- not (Cond), !, Act2.

unde predicatul not(Cond) este satisfãcut dacă scopul Cond nu este satisfãcut. O astfel de

definiþie implicã evaluarea lui Cond de douã ori şi, dacă Cond se defineºte ca o conjuncþie

de scopuri, posibil sofisticate, atunci ineficienþa utilizãrii unui cut verde în acest caz este

evidentã. De la caz la caz, programatorul în Prolog trebuie sã aleagã între claritate, deci

pãstrarea corespondenþei semnificaþiei declarative cu cea proceduralã, şi eficienþã.

În multe situaþii intereseazã atât condiþiile de satisfacere a scopurilor, cât şi condiþiile

de nesatisfacere a acestora, deci de eºec. Fie urmãtoarele fapte Prolog:

bun(gelu).

bun(vlad).

bun(mihai).

Pe baza acestor fapte se poate obþine un rãspuns afirmativ despre bunãtatea lui Gelu,

Vlad şi Mihai şi un rãspuns negativ dacă se întreabã despre bunãtatea oricãrei alte persoane.

Din acest exemplu se poate vedea cã limbajul Prolog foloseºte un model de raþionament

minimal numit ipoteza lumii închise. Conform acestui model, tot ceea ce nu este ºtiut de

program, deci afirmat explicit ca adevãrat în program, este considerat fals.

Limbajul Prolog permite exprimarea directã a eºecului unui scop cu ajutorul

predicatului fail. Predicatul fail este un predicat standard, fãrã argumente, care eºueaza

întotdeauna. Datoritã acestui lucru introducerea unui predicat fail într-o conjuncþie de

scopuri, de obicei la sfârºit, cãci dupã fail tot nu se mai poate satisface nici un scop,

determinã intrarea în procesul de backtracking.

Dacã fail se întâlneste dupã predicatul cut, nu se mai face backtracking. Enunþul "Un

individ este rãu dacă nu este bun." se poate exprima astfel:

35

bun(gelu).

bun(vlad).

bun(mihai).

rau(X) :- bun(X), !, fail.

rau(X).

?- rau(gelu).

no

?- rau(mihai).

no

?- rau(petru).

yes

Dacã predicatul fail este folosit pentru a determina eºecul, cum este cazul exemplului

de mai sus, este de obicei precedat de predicatul cut, deoarece procesul de backtracking pe

scopurile care îl preced este inutil, scopul eºuând oricum datoritã lui fail.

Existã cazuri în care predicatul fail este introdus intenþionat pentru a genera procesul

de backtracking pe scopurile care îl preced, proces interesant nu din punctul de vedere al

posibilitãþii de resatisfacere a scopului ce conţine fail, ci din punctul de vedere al efectului

lateral al acestuia.

rosu(mar).

rosu(cub).

rosu(soare).

afisare(X) :- rosu(X), write(X), fail.

afisare( _ ).

Scopul afisare(X) va afiºa toate obiectele roºii cunoscute de programul Prolog datoritã

procesului de backtracking generat de fail; în acest fel s-a relizat prin fail o iteraţie peste

faptele rosu( ). Clauza afisare( _ ) este adãugatã pentru ca rãspunsul final la satisfacerea

scopului sã fie afirmativ. În acest caz, introducerea unui cut înainte de fail ar fi determinat

numai afiºarea primului obiect roºu din program.

Revenind la combinaþia !,fail, se considerã în continuare implementarea în Prolog a

afirmaþiei: "Mihai iubeºte toate sporturile cu excepþia boxului". Aceastã afirmaþie poate fi

exprimatã în pseudocod sub forma:

dacă X este sport ºi X este box

atunci Mihai iubeºte X este fals

altfeldacă X este sport

atunci Mihai iubeºte X este adevãrat

şi tradusã în Prolog astfel:

36

iubeste(mihai, X) :- sport(X), box(X), !, fail.

iubeste(mihai, X) :- sport(X).

Predicatul cut utilizat aici este un cut roºu. Combinaþia !, fail este deseori utilizatã în

Prolog şi are rolul de negaþie. Se mai spune cã limbajul Prolog modeleazã negaþia ca eºec

al satisfacerii unui scop (negaţia ca insucces), aceasta fiind de fapt o particularizare a

ipotezei lumii închise. Combinaþia !, fail este echivalentã cu un predicat standard existent în

Prolog, predicatul not. Predicatul not admite ca argument un predicat Prolog şi reuºeºte

dacă predicatul argument eºueazã. Utilizând acest predicat, ultimul exemplu dat se poate

exprima în Prolog astfel:

iubeste(mihai, X) :- sport(X), not(box(X)).

iubeste(mihai, X) :- sport(X).

Un alt predicat standard este predicatul call, care admite ca argument un predicat

Prolog şi are ca efect încercarea de satisfacere a predicatului argument. Predicatul call

reuºeºte dacă predicatul argument reuşeşte şi eºueazã în caz contrar. Utilizând acest predicat,

se poate explicita efectul general al predicatului standard not în urmãtorul mod:

not(P) :- call(P), !, fail.

not(P).

Atât predicatul not cât şi predicatul call sunt predicate de ordinul II în Prolog deoarece

admit ca argumente alte predicate. Secþiunea urmãtoare va prezenta mai multe astfel de

predicate.

4.3 Predicate predefinite ale limbajului Prolog

Predicatele prezentate pânã acum, cu excepþia predicatului call, sunt predicate bazate pe

logica cu predicate de ordinul I, modelul Prolog cu semnificaþia declarativã a programelor

urmãrind îndeaproape modelul logic. În continuare se prezintã o serie de predicate Prolog

care nu mai pot fi asimilate cu logica cu predicate de ordinul I, respectiv: predicate ce decid

asupra caracterului unor argumente, predicate de control a fluxului de execuţie a

programului şi predicate de ordinul II, numite uneori şi metapredicate. Metapredicatele

acceptã ca argumente alte predicate Prolog, fapte sau reguli, şi sunt interesante în special

prin efectul lateral pe care îl produc. Toate tipurile de predicate menţionate reprezintã

extinderea modelului programării logice cu tehnici de programare care cresc puterea de

calcul a limbajului. Majoritatea predicatelor prezentate în continuare sunt standard şi se

găsesc predefinite în orice implementare, o parte sunt specifice mediului ARITY Prolog,

acestea fiind indicate ca atare. O implementare particulară poate conþine şi alte predicate

predefinite suplimentare celor prezentate aici.

(a) Predicate de clasificare a termenilor

· var(X)

37

Predicatul var(X) reuºeºte dacă X este o variabilã neinstanþiatã şi eºueazã în cazul în

care X este o variabila instanþiatã sau o constantã.

Exemple:

?- var(5).

no

?- var(mihai).

no

?- var(X).

yes

· novar(X)

Predicatul novar(X) este adevãrat dacă X nu este o variabilã neinstanþiatã. Acest

predicat este opusul prdicatului var(X) şi s-ar putea defini astfel:

novar(X) :- var(X), !, fail.

novar( _ ).

· atom(X)

Predicatul atom(X) reuºeºte dacă X este un atom Prolog şi eºueazã în caz contrar.

Exemple:

?- atom(coco).

yes

?- atom(100).

no

?- atom(carte(prolog, clocksin)).

no

· integer(X)

Predicatul integer(X) reuşeşte dacă X este un numãr întreg.

Se considerã urmatorul exemplu de program Prolog care transformã o expresie

reprezentatã printr-o sumã de variabile şi constante într-o expresie care conþine suma

variabilelor plus o constantã care reprezintã suma tuturor constantelor din expresie [CM84].

Predicatul simplif are douã argumente: primul argument este forma iniþialã a expresiei,

argument instanþiat, iar cel de al doilea reprezintã expresia simplificatã, sintetizatã de

program.

% simplif(Expresie_iniþialã, Expresie_simplificatã)

% Predicat ajutator simpl

% simpl(Ex_iniþialã, Suma_acumulatã, Ex_simplificatã).

simplif(Expr, Expr1) :- simpl(Expr, 0, Expr1).

38

simpl(Expr + A, N, Expr1) :-

integer(A), !,

N1 is N + A,

simpl(Expr, N1, Expr1).

simpl(Expr + A, N, Expr1 + A) :-

atom(A), !,

simpl(Expr, N, Expr1).

simpl(Rest, N, N1) :-

integer(Rest), !,

N1 is Rest + N.

simpl(Rest, 0, Rest) :- !.

simpl(Rest, N, N + Rest).

La întrebarea

?- simplif(x + 40 + y + 1 + 55 + x + 2, E).

programul rãspunde

E = 98 + x + y + x

În programul de mai sus definirea predicatului simplif s-a fãcut pe baza unui predicat

ajutãtor simpl care conþine un argument suplimentar. Acest argument, instanþiat la 0 în

cazul primului apel, este folosit ca o variabilã de acumulare pentru calculul sumei

constantelor întregi din expresie.

· atomic(X)

Pe baza predicatelor atom(X) şi integer(X) se poate defini predicatul atomic(X) care

este adevãrat dacă X este fie întreg, fie atom Prolog:

atomic(X) :- atom(X).

atomic(X) :- integer(X).

De multe ori predicatul atomic(X) este predefinit în sistem.

(b) Predicate de control

Predicatul true reuºeºte întotdeauna, iar fail eºueazã întotdeauna.

Predicatul repeat simuleazã structurile de control repetitive din limbajele clasice de

programare. El are o infinitate de soluþii, putându-se resatisface de oricâte ori este nevoie,

fãrã a umple stiva. Definiþia lui ar putea fi:

repeat.

repeat :- repeat.

39

Acest predicat este predefinit in mediul ARITY. În ARITY Prolog existã şi alte

predicate predefinite care simuleazã structurile de control din programarea procedurală:

ifthen(+Conditie, +Scop), pentru dacã-atunci; ifthenelse(+Conditie, +Scop-then, +Scop-

else), pentru dacã-atunci-altfel; ºi case([Conditie1 -> Scop1, … Conditien -> Scopn | Scop-

default), sau case([Conditie1 -> Scop1, … Conditien -> Scopn), pentru case.

O predicat echivalent ciclului for, care nu este prefedinit în ARITY, se poate

implementa astfel:

% for(Variabla, ValoareInitiala, ValoareFinala, Pas)

for(I, I, I, 0).

for( _, _ , _ , 0) :- !, fail.

for(I, I, F, S) :-

S > 0, (I > F, !, fail ; true)

; S < 0, (I < F, !, fail ; true).

for(V, I, F, S) :- I1 is I + S, for(V, I1, F, S).

Exemple de apeluri:

a :- for(X, 10, -10, -3.5), write(X), tab(2), fail ; true.

b :- for(X, -10, 10, 3.5), write(X), tab(2), fail ; true.

c :- for(X, 10, 10, 0), write(X), tab(2), fail ; true.

?- a.

10 6.5 3.0 -0.5 -4.0 -7.5

yes

?- b.

-10 -6.5 -3.0 0.5 4.0 7.5

yes

?- c.

10

yes

Predicatul for eºueazã pentru apeluri incorecte (cicluri infinite) de genul:

for(X, -10, 10, 0).

for(X, 10, -10, 2).

for(X, -10, 10, -2).

(c) Predicate de tratare a clauzelor drept termeni

Predicatele din aceastã categorie permit: construirea unei structuri care reprezintã o

clauzã în baza de cunoºtinte, identificarea clauzelor din program, adãugarea sau eliminarea

unor clauze, reprezentate printr-o structurã, în baza de cunoºtinþe a sistemului.

· clause(Antet, Corp)

40

Satisfacerea scopului clause(Antet, Corp) necesitã unificarea argumentelor Antet şi

Corp cu antetul şi corpul unei clause existente în baza de cunoºtinþe Prolog. La apelul

acestui predicat, Antet trebuie sã fie instanþiat astfel încât predicatul principal al clauzei sã

fie cunoscut. Dacã nu existã clauze pentru acest predicat, scopul eşuează. Dacã existã mai

multe clauze care definesc predicatul Antet, scopul clause(Antet, Corp) va avea mai multe

soluþii, fiecare soluþie corespunzând unei clauze de definire a predicatului Antet. Dacã o

clauzã este fapt, Corp se instanþiazã la constanta true.

Exemplu. Considerând definiþia predicatului de concatenare a douã liste ca fiind deja

introdusã în baza de cunoºtinþe Prolog:

% conc(Lista1, Lista2, ListaRez)

conc([], L, L).

conc([Prim|Rest1], L2, [Prim|Rest3]) :- conc(Rest1, L2, Rest3).

se obþin urmãtoarele rezultate:

?- clause(conc(A, B, C), Corp).

A = [ ], B = _004C, C = _004C, Corp = true;

A = [_00F0|_00F4], B = _004C, C = [_00F0|_00FC],

Corp = conc (_00F4, _004C, _00FC);

no

Utilizând predicatul clause se poate defini un predicat listc de afiºare a clauzelor care

definesc un predicat:

% listc(Antet) - afiºeazã toatã clauzele din baza de cunoºtinþe

% care definesc scopul Antet

listc(Antet) :-

clause(Antet, Corp),

afis(Antet, Corp),

write('.'), nl, fail.

listc( _ ).

afis(Antet, true) :- !, write(Antet). %1

afis(Antet, Corp) :- write(Antet), write(':'), write('-'), write(Corp).

Efectul acestui program, coinsiderând definiþia anterioarã a scopului conc, este urmãtorul:

?- listc(conc(_, _, _)).

conc([], _0034, _0034).

conc([_0108|_010C], _0034, [_0108|_0114]:-conc(_010C, _0034, _0114).

În definirea primei clauze a predicatului afis utilizarea predicatului cut este esenþialã

deoarece afiºarea clauzelor este bazatã pe procesul de backtracking generat intenþionat de

41

introducerea predicatului fail în prima clauzã a predicatului listc. Regula %1 din predicatul

afis este necesarã deoarece faptele sunt reguli având corpul format din scopul true. Aceastã

reprezentare ne aratã cã faptele ºi regulile au aceeaºi reprezentare în Prolog (toate reprezintã

clauze).

Exemplu. Pentru urmãtorul predicat:

p(1).

p(X) :- X > 2, X < 5.

p(X).

predicatul clause dă urmãtoarele rãspunsuri:

?- clause(p(X), Corp).

X = 1, Corp = true ;

X = _0038, Corp = _0038 > 2 , _0038 < 5 ;

X = _0038, Corp = true.

· asserta(Clauza), assertz(Clauza), assert(Clauza),

Predicatul asserta(Clauza) reuşeşte întotdeauna o singurã datã şi are ca efect lateral

adãugarea clauzei Clauza la începutul bazei de cunoºtinþe Prolog. Predicatele

assertz(Clauza) ºi assert(Clauza) au o comportare similarã, cu excepþia faptului cã

argumentul Clauza este adãugat la sfârºitul bazei de cunoºtinþe. Argumentul Clauza trebuie

sã fie instanþiat la o valoare ce reprezintã o clauzã Prolog. Acþiunea de adãugare a unei

clauze prin asserta, assert sau assertz nu este eliminatã de procesul de backtracking.

Clauza adãugatã va fi eliminatã numai în urma unei cereri explicite prin intermediul

predicatului retract.

· retract(Clauza)

Predicatul retract(Clauza) are ca efect eliminarea din baza de cunoºtinþe a unei

clauze care unificã cu argumentul Clauza. Predicatul reuşeşte dacă o astfel de clauza exista;

la fiecare resatisfacere se eliminã din baza de cunoştinţe o nouã clauzã care unificã cu

argumentul. Clauza trebuie sa fie argument instanþiat la apel. Odatã ce o clauzã este

eliminatã din baza de cunoştinţe prin retract, clauza nu va mai fi readaugatã dacă se face

backtracking pe retract.

Exemplu.

adaug :- asserta(prezent(nero)), asserta(prezent(cezar)).

scot :-retract(prezent(nero)).

actiune1 :- adaug, listc(prezent(X)).

actiune2 :- scot, listc(prezent(X)).

?- actiune1.

prezent(nero).

prezent(cezar).

42

?- actiune2.

prezent(cezar).

Utilizând predicatul retract, se poate defini un predicat care are rolul de a elimina din

baza de cunoştinţe toate clauzele care definesc un predicat. Acest predicat, numit

retractall(Antet), este predefinit în anumite implementãri Prolog. Definiþia lui pe baza

predicatului retract este:

% retractall(Antet) - eliminã toate clauzele care definesc scopul Antet

retractall(Antet) :- retract(Antet), fail.

retractall(Antet) :- retract( (Antet :- Corp) ), fail.

retractall( _ ).

Observaþie: În ARITY Prolog, atunci când se adaugã/eliminã o regulã în/din baza de date

în mod dinamic cu assert/retract regula trebuie pusã între paranteze rotunde sau datã ca o

structurã:

assert( (p(X) :- X=1 ; X=2) ).

retract( ':-'(p(X), ';'(X=1, X=2))).

Predicatele asserta, assertz şi retract pot fi utile în diverse situaþii datoritã efectelor

lor laterale. Ele pot simula, de exemplu, un fel de mecanism de variabile globale în Prolog.

Se considerã exemplul de implementare a unui generator de numere aleatoare în Prolog. Se

defineºte predicatul aleator(R, N) care genereazã un număr aleator N în intervalul [1..R]

pornind de la o sãmânþã fixatã şi folosind metoda congruenþei liniare. De fiecare datã când

trebuie generat un număr aleator, valoarea acestuia este determinatã folosind sãmânþa

existentã şi o nouã sãmânþã este calculatã şi memoratã ca fapt Prolog până la noul apel.

Vechea sãmânþã este eliminatã din baza de cunoştinţe .

% aleator(R, N) - instanþiazã N la un număr aleator între 1 şi R

samanta(11).

aleator(R, N) :-

samanta(S),

modul(S, R, N1),

N is N1 + 1,

retract(samanta(S)),

N2 is (125 * S +1),

modul(N2, 4096, SamantaNoua),

asserta(samanta(SamantaNoua)).

modul(X, Y, X) :- X < Y.

modul(X,Y,Z) :- % Predicatul modulo este predefinit

X >= Y, % în anumite implementãri

X1 is X - Y,

43

modul(X1, Y, Z).

La apelul predicatului se obþin urmãtoarele rezultate:

?- aleator(100, N).

N = 14

?- aleator(100, N).

N = 27

?- aleator(100, N).

N = 48

Dacă se doreºte afiºarea continuã a numerelor aleatoare, o primã variantã este aceea de

a crea un ciclu infinit de afiºare a acestor numere, efect realizat de predicatul nr_aleat(R)

care afiºeazã numere aleatoare în intervalul [1..R].

% nr_aleat(R) - afiºeazã la infinit numere aleatoare între 1 şi R

nr_aleat(R) :- repeat, aleator(R, X), write(X), nl, fail.

Predicatul fail introdus în definiþia predicatului nr_aleat(R) determinã intrarea în

procesul de backtracking şi datoritã predicatului repeat, cele douã scopuri aleator(R, X) şi

write(X) se vor satisface la infinit. Trebuie observat faptul cã numai scopul repeat se

resatisface; scopurile aleator şi write sunt la prima satisfacere de fiecare datã.

În cazul în care se doreºte construirea unui ciclu care se va termina dacă o anumitã

condiþie este îndeplinitã, se poate reformula predicatul de generare a numerelor aleatoare

astfel:

nr_aleat1(R) :-

repeat, aleator(R, X), write(X), nl,

write('Continuati? [d/n]'), read('n').

Apelând predicatul se va obþine urmãtoarea secvenþã de numere aleatoare:

?- nr_aleat1(10).

4

Continuati? d.

7

Continuati? d.

8

Continuati? n.

yes

· functor(Term, Funct, N)

Predicatul reuşeşte dacă cele trei argumente unificã astfel: Term este o structurã cu

functor Funct şi aritate N. Predicatul poate fi folosit în douã moduri:

44

(1) Term este argument instanþiat şi predicatul reuşeşte dacă Term este atom sau

structurã şi eşuează în caz contrar. În caz de succes, Funct şi N sunt

instanþiate la functorul, respectiv aritatea lui Term. Un atom este

considerat ca fiind o structurã de aritate 0.

(2) Term este argument neinstanþiat iar Funct şi N sunt instanþiate, specificând

functorul şi numãrul de argumente. În acest caz scopul reuşeşte

întotdeauna şi Term va fi instanþiat la o structurã cu functorul şi

numãrul de argumente specificate. Argumentele structurii construite în

acest mod sunt neinstanþiate.

Exemple:

?- functor(auto(honda, culoare(roºie)), Funct, N).

Funct = auto, N = 2

?- functor(a + b, F, N).

F = +, N = 2

?- functor(albastru, F, N).

F = albastru, N = 0

?- functor [a, b, c], !, 3).

no

?- functor(Term, pasi_plan, 3).

Term = pasi_plan(_0, _0, _0)

· arg (N, Term, Arg)

Predicatul arg (N, Term, Arg) are ca efect obþinerea celui de al N-lea argument al

unei structuri Term, acest argument devenind instanþierea lui Arg. N şi Term trebuie sã fie

argumente instanþiate. Arg poate fi instanþiat, caz în care predicatul reuşeşte dacă Arg este

argumentul N din structura Term, sau Arg poate fi neinstanþiat, caz în care se va instanþia

la cel de al N-lea argument al lui Term.

?- arg(2, poseda(mihai, frumoasa(portocala)), Arg).

Arg = frumoasa(portocala).

?- arg (2,[a, b, c], X).

X = [b, c]

?- arg(1, a + (b + c), b).

no

· Scop = .. [Functor | ListArg]

Predicatul =.., numit univ, este un predicat folosit ca operator infixat. El poate fi

folosit în trei moduri:

45

(1) Scop este instanþiat. În acest caz predicatul reuşeşte, dacă Scop este o

structurã, iar Functor şi ListArg se instanþiazã la functorul, respectiv

lista argumentelor acelei structuri.

(2) Scop este neinstanþiat, iar Functor şi ListArg sunt instanþiate la un functor,

respectiv la o listã de argumente a unei structuri. Dacã valorile lui

Functor şi ListArg sunt corecte, predicatul reuşeşte şi Scop va fi

instanþiat la structura creatã cu functorul şi lista de argumente date.

(3) Toþi trei parametrii sunt instanþiati şi predicatul reuşeşte dacă Functor şi

ListArg sunt functorul, respectiv lista argumentelor structurii Scop.

Acest predicat are o importanþã deosebitã în Prolog deoarece el permite sinteza

dinamicã a scopurilor Prolog, deci construirea de clauze pe parcursul execuþiei

programului. Lucrul acesta este posibil deoarece clauzele Prolog au tot forma unor structuri

formate din functor şi argument, sintaxa codului fiind aceeaºi cu sintaxa datelor în Prolog.

Exemple:

?- sir(a, b, c) =.. X.

X = [sir, a, b, c]

?- (f(a) + g(b)) =.. [+, f(X), Y].

X = a, Y = g(b)

?- a + b + c =.. L. % a + b + c = '+'(a, '+'(b, c))

L=[+, a+b, c]

?- a * b + c =.. L. % a * b + c = '+'('*'(a, b), c)

L = [+, a * b, c]

?- a + b * c =.. L. % a + b * c = '+'(a, '*'(b, c))

L = [+, a, b * c]

?- Scop =.. [parinte, mihai, gina].

Scop = parinte(mihai, gina)

?- Scop =.. [membru, a, [a, b, c]].

Scop = membru(a, [a, b, c])

?- conc([1, 2], [3], [1, 2, 3]) =.. [Functor | ListArg]

Functor = conc, ListArg = [[1, 2], [3], [1, 2, 3]]

?- S =.. [f, X, a,Y].

S = f( _004C, a, _0060 ), X = _004C, Y = _0060

?- f =.. L.

L = [f]

46

Folosind univ putem verifica faptul cã listele se reprezintã prin structuri cu punct de

forma: '.'(PrimulElement, RestulListei). Lista [1, 2] este totuna cu '.'(1, [2]) sau cu

'.'(1, '.'(2, []).

Exemplu.

?- [1,2] =.. L.

L = [. , 1, [2]].

· listing, listing(+Nume), listing(+Nume/Aritate), listing(+[Nume/Aritate…])

Predicatul listing tipãreºte din baza de cunoştinţe toate clauzele, toate clauzele unui

predicat sau toate clauzele unor predicate dintr-o listã. De exemplu, pentru predicatele:

p.

p(1).

p(X) :- X > 2, X < 5.

p(X).

p(1,2).

p(X,Y) :- X < Y.

se pot face urmãtoarele interogãri (redenumirile variabilelor sunt făcute automat de sistem):

?- listing(p/1).

p(1).

p(A) :- A > 2, A < 5.

p(A).

yes

?- listing([p/0, p/2]).

p.

p(1,2).

p(A, B) :- A < B.

yes

(d) Predicate pentru execu þ ia dinamic ã a scopurilor

· call(Scop)

Se presupune cã argumentul Scop este instanþiat la un scop Prolog. Predicatul

call(Scop) reuşeşte dacă Scop reuşeşte şi eşuează în caz contrar. La prima vedere acest

predicat pare redundant deoarece execuþia scopului Scop se poate face direct în Prolog.

Dacã se doreste execuþia dinamicã a scopurilor care au fost sintetizate pe parcursul

execuþiei unui program Prolog, atunci predicatul call este necesar. În plus, dacă nu se

cunoaşte scopul de executat, de exemplu se doreºte execuþia a diverse scopuri cu argumente

47

diferite sau cu aceleaºi argumente, se poate folosi predicatul call cu argument o variabilã

care se va instanþia în funcþie de întrebarea utilizatorului sau de context.

Execuþia dinamicã a scopurilor poate fi exprimatã prin urmãtoarea secvenþã de

scopuri:

... obþine(Functor), calculeazã(ArgList), Scop =.. [Functor | ArgList], call(Scop), ...

Se prezintã în continuare diverse variante de predicate Prolog care aplicã un predicat

primit ca argument fiecãrui element al unei liste sau al mai multor liste, rezultatele fiecãrei

aplicãri fiind cumulate într-o listã rezultat. Acest tip de predicate reprezintã o categorie de

prelucrãri ale listelor, frecvent întâlnite şi necesare.

Se defineºte întâi predicatul mapcar(Pred, ListaArg, ListaRez) care primeºte douã

argumente instanþiate Pred şi ListaArg şi calculeazã ListaRez. Pred este un predicat

Prolog care are la rândul lui douã argumente: primul, instanþiat, este folosit în prelucrare

pentru obþinerea celui de al doilea şi este obþinut ca element curent din ListaArg; cel de al

doilea, neinstanþiat, este calculat de Pred şi este depus ca element curent în ListaRez. În

programul care urmeazã se vor folosi ca predicate Pred urmãtoarele:

· prim(Lista, El) care obþine primul element dintr-o listã,

· neg(Element, -Element) care schimbã semnul unui element şi

· adaug(Nume, NumeFrumos) care adaugã în faþa unui nume apelativul de politeþe

dna dacă persoana este femeie şi dl dacă persoana este bãrbat.

Se observã cã argumentele lui Pred din definiþia lui mapcar pot fi atât elemente atomice

(atomi sau numere) cât şi liste.

% Se definesc predicatele de prelucrare a listelor: mapcar, mapcar2 şi mapcarnl.

prim([], []).

prim([X | _ ], X).

neg(X, -X).

adaug(Nume, NumeFrumos) :-

write(Nume),

write(' este femeie sau barbat (f/b)? '),

read(Sex),

(Sex = b, NumeFrumos = [dl, Nume] ;

Sex = f, NumeFrumos = [dna, Nume]).

% mapcar(Pred, ListaArg, ListaRez) - evalueazã predicatul

% Pred pentru fiecare element din lista ListaArg şi

% construieºte rezultatul în ListaRez.

% Predicatul Pred are douã argumente, atomice sau liste.

mapcar( _ , [], []).

mapcar(P, [Arg | RestArg], [X | Rest]) :-

48

Scop =.. [P, Arg, X],

call(Scop),

mapcar(P, RestArg, Rest).

În definirea scopului adaug s-a utilizat simbolul ;. Acesta este un operator predefinit

în Prolog care marcheazã o disjuncþie de scopuri, deci are semnificaţia de disjuncþie logicã.

Efectul operatorului ; poate fi reprezentat în urmãtorul fel:

X ; X :- X.

X ; Y :- Y.

Deci aºa cum operatorul Prolog , corespunde unei conjuncþii de scopuri, operatorul ;

corespunde unei disjuncþii de scopuri.

Comportarea acestui program este urmãtoarea:

?- mapcar(prim, [[alain, turing], [ada, byron]], Rez).

Rez = [alain, ada]

?- mapcar(neg, [1, 2, 3, 4], Rez).

Rez = [-1, -2, -3, -4]

?- mapcar(adaug, [maria, mihai, george, ana], Rez).

maria este femeie sau barbat (f/b)? f

mihai este femeie sau barbat (f/b)? b

george este femeie sau barbat (f/b)? b

ana este femeie sau barbat (f/b)? f

Rez = [[dna, maria], [dl, mihai], [dl, george], [dna, ana]]

Dacã se doreste execuþia unor prelucrãri similare, dar pentru predicate Prolog care

admit trei argumente, primele doua instanþiate şi cel de al treilea sintetizat de predicatul

Pred pe baza primelor douã, se poate defini de o maniera similarã predicatul:

mapcar2(Pred, ListaArgPrim, ListaArgSecund, ListaRez)

Se va demonstra funcþionarea acestui predicat în cazurile în care predicatul Pred, care

se mapeazã pe elementele listelor ListaArgPrim şi ListaArgSecund, este întâi

plus(A, B, Rez) care calculeazã în Rez suma lui A şi B, apoi conc(List1, Lista2, ListaRez)

care concateneazã douã liste şi depune rezultatul în ListaRez. Argumentele predicatului

Pred pot fi argumente atomice sau liste.

conc([], L, L).

conc([X|Rest], L, [X|Rest1]) :- conc(Rest, L, Rest1).

plus(A, B, Rez) :- Rez is A + B.

% mapcar2(Pred, ListaArgPrim, ListaArgSecund, ListaRez) -

% evalueazã predicatul Pred pentru fiecare pereche

% de argumente, unul din ListaArgPrim, celãlalt din ListaArgSecund

49

% şi construieºte rezultatul în ListaRez.

% Predicatul Pred are trei argumente, atomice sau liste.

mapcar2( _ , [], _ , []).

mapcar2(P, [Arg1 | RestArg1], [Arg2 | RestArg2], [X | Rest]) :-

Scop =.. [P, Arg1, Arg2, X],

call(Scop),

mapcar2(P, RestArg1, RestArg2, Rest).

?- mapcar2(plus, [1, 2, 3, 4], [10, 20, 30, 40], Rez).

Rez = [11, 22, 33, 44]

?- mapcar2(conc, [[1, 2], [a, b]], [[3, 4], [c, d]], Rez).

Rez = [[1, 2, 3, 4], [a, b, c, d]]

Se observã cã este necesarã definirea unui predicat de tip mapcar diferit pentru fiecare

categorie de aritate N a predicatelor care pot instanþia legal Pred. Dacă se impune restricţia

conform cãreia predicatul Pred poate avea numai argumente atomice, atunci se poate defini

predicatul mapcarnl(Pred, ListaListeArg, ListaRez) cu un efect similar. ListaListeArg

este fie o listã de elemente atomice, dacă Pred are douã argumente, dintre care primul

instanþiat va fi obþinut ca elementul curent al acestei liste, fie o listã de liste, unde fiecare

element listã din ListaListeArg conþine primele N-1 argumente atomice ale lui Pred.

% mapcarnl(Pred, ListaListeArg, ListaRez) -

% evalueazã predicatul Pred cu primele N-1 argumente din lista

% ListaListeArg şi construieºte rezultatul în ListaRez.

% Predicatul Pred poate avea oricâte argumente, dar toate trebuie sa fie atomice.

mapcarnl(_, [], []).

Mapcarnl(P, [Arg|RestArg], [X|Rest]) :-

(atomic(Arg), FormaScop = [P,Arg,X] ;

not atomic(Arg), conc([P], Arg, Temp), conc(Temp, [X], FormaScop)),

Scop =.. FormaScop,

call(Scop),

mapcarnl(P, RestArg, Rest).

?- mapcarnl(neg, [1, 2, 3, 4], Rez]

Rez = [-1, -2, -3, -4]

?- mapcarnl[[1, 10], [2, 20], [3, 30], [4, 40]], Rez).

Rez = [11, 22, 33, 44].

· findall(X, Scop, Lista)

Predicatul findall(X, Scop, Lista) are ca efect obþinerea tuturor termenilor X care

satisfac predicatul Scop în baza de cunoştinţe a programului şi cumularea acestor termeni

în lista Lista. Scop trebuie sã fie instanþiat la un predicat Prolog în care, în mod normal,

50

trebuie sã aparã X. Dacã Scop nu reuºeºte, findall reuºeºte, instanþiind Lista la lista vidã

(această ultimă caracteristică este specifică mediului ARITY).

Exemple:

prieten(vlad, ana).

prieten(vlad, george).

prieten(vlad, mihai).

prieten(liviu, ana).

?- findall(X, prieten(vlad, X), L).

X = _0038, L = [ana, george, mihai]

Efectul predicatului findall poate fi explicat şi prin definiþia explicitã a unui predicat

cu acelaºi efect: find_all(X, Scop, Lista)

% find_all(Arg, Scop, Lista) -

% are acelaºi efect ca predicatul standard findall(Arg, Scop, Lista).

prieten(vlad, ana).

prieten(vlad, george).

prieten(vlad, mihai).

prieten(liviu, ana).

find_all(X, S, _) :- asserta(stiva(baza_stivei)),

call(S), % Scopul S conþine X.

asserta(stiva(X)), fail.

find_all( _ , _ , L) :- colecteaza([], M), !, L = M.

colecteaza(S, L) :- urmator(X), !, colecteaza([X | S], L).

colecteazã(L, L).

urmãtor(X) :- retract(stiva(X)), !, X \= baza_stivei.

?- find_all(X, prieten(vlad, X), L).

X = _0038, L = [ana, george, mihai].

?- find_all(X, prieten(toma, X), L).

X = _0038, L = []

În definiþia predicatului find_all se observã utilizarea unei tehnici de programare

Prolog interesante. Utilizând predicatul asserta se simuleazã o structurã de stivã în Prolog.

Baza stivei este marcata de faptul stiva(baza_stivei) şi în stivã se introduc, ca fapte

suplimentare adãugate la începutul bazei de cunoştinţe Prolog, valorile X care satisfac

scopul S sub forma stiva(X), cu X instanþiat de apelul call(S). Acest lucru este executat

pentru toate soluþiile posibile ale predicatului call(S) datoritã predicatului fail introdus în

51

finalul definiþiei primei clauze a predicatului find_all. În acest fel toate valorile lui X din

baza de cunoştinţe Prolog care satisfac S sunt introduse în stiva simulatã. Cea de a doua

clauzã a predicatului find_all, care se executã dupã ce nu mai existã nici o posibilitate de

resatisfacere a primeia, are ca scop golirea stivei şi colectarea valorilor introduse în stivã,

până la baza ei, stiva(baza_stivei), în lista M.

· bagof(X, Scop, Lista)

Predicatul bagof(X, Scop, Lista) are ca efect colectarea în Lista a tuturor termenilor

X care satisfac Scop, þinând cont de diversele instanþieri posibil diferite ale celorlalte

variabile din Scop. Scop este un argument care trebuie sã fie instanþiat la un scop Prolog.

Dacă Scop nu conþine alte variabile în afara lui X, atunci efectul predicatului bagof este

identic cu cel al lui findall. Dacã Scop nu reuºeºte cel puþin o datã atunci bagof eºueazã.

Exemple:

clasificare(a, vocala).

clasificare(b, consoana).

clasificare(c, consoana).

clasificare(d, consoana).

clasificare(e, vocala).

clasificare(f, consoana).

?- findall(X, clasificare(X, C), L).

X = _0038, C = _004C, L = [a, b, c, e, f] % o soluþie

?- bagof(X, clasificare(X, C), L).

X = _0038, C = consoana, L = [b, c, d, f];

X = _0038, C = vocala, L = [a, e]

no % douã soluþii

· setof(X, Scop, Lista)

Predicatul setof(X, Scop, Lista) are acelaºi efect cu predicatul bagof, cu excepþia

faptului cã valorile cumulate în lista Lista sunt sortate crescãtor şi se eliminã apariþiile

multiple de valori, deci Lista devine o mulþime ordonatã.Dacã Scop nu reuºeºte cel puþin o

datã atunci setof eºueazã.

Considerând faptele de definire a consoanelor şi variabilelor prezentate anterior, se

poate construi urmãtorul exemplu, în care mai introducem douã fapte:

asserta(clasificare(d, consoana)).

asserta(clasificare(e, vocala)).

?- bagof(X, clasificare(X, C), L).

X = _0038, C = consoana, L = [d, b, c, d, f]; % consoana d apare de douã ori

X = _0038, C = vocala, L = [e, a, e]; % vocala e apare de douã ori

no

52

?- setof(X, clasificare(X, C), L).

X = _0038, C = consoana, L = [b, c, d, f]; % consoanele apar o singurã datã

X = _0038, C = vocala, L = [a, e]; % vocalele apar o singurã datã

no

4.4 Direcþia de construire a soluþiilor

Majoritatea programelor Prolog se bazeazã pe recursivitate. Ca în orice limbaj de

programare recursiv, parametrii de ieºire ai subprogramelor, deci argumentele sintetizate ale

predicatelor în cazul limbajului Prolog, pot fi calculate fie pe ramura de avans în

recursivitate, fie pe ramura de revenire din recursivitate. Se considerã douã variante de

definire a predicatului de numãrare a elementelor dintr-o listã. Prima varianta,

nr_elem(Lista, NrElem), construieºte soluþia (calculeazã numãrul de elemente din listã) pe

ramura de revenire din recursivitate.

% nr_elem(Lista, NrElem)

nr_elem([], 0).

nr_elem([ _ | Rest], N) :- nr_elem(Rest, N1), N is N1 + 1.

A doua variantã, nr_elem2(Lista, NrElem) calculeazã numãrul de elemente din listã

pe ramura de avans în recursivitate. Pentru a realiza acest lucru, se foloseºte un predicat

ajutãtor nr_elem1(Lista, NrAcumulat, NrElem) care are un argument suplimentar faþã de

predicatul nr_elem2. Acest argument, NrAcumulat, are rolul de variabilã de acumulare a

numãrului de elemente din listã pe mãsura avansului în recursivitate şi este instanþiat la

primul apel la valoarea 0. În momentul atingerii punctului de oprire din recursivitate, deci în

cazul în care lista ajunge vidã, valoarea acumulata în argumentul NrAcumulat este copiatã

în cel de-al treilea parametru al predicatului nr_elem_1. Se face apoi revenirea din apelurile

recursive succesive fãrã a efectua nici o altã prelucrare, predicatul nr_elem_1 reuşeşte şi

trimite valoarea calculatã în NrElem predicatului iniþial nr_elem2.

% nr_elem2(Lista, NrElem)

% nr_elem1(Lista, NrAcumulat, NrElem)

nr_elem2(Lista, N) :- nr_elem1(Lista, 0, N).

nr_elem1([], N, N).

nr_elem1([ _ | Rest], N1, N2) :- N is N1 + 1, nr_elem1(Rest, N, N2).

O abordare similarã se poate vedea în cazul celor douã variante de definire a

predicatului de intersecþie a douã liste (determinarea elementelor comune celor douã liste).

Prima variantã, inter(Lista1, Lista2, ListaRez), calculeazã soluþia (lista intersecþie) pe

ramura de revenire din recursivitate. Cea de a doua variantã, int(Lista1, Lista2, ListaRez),

calculeazã soluþia pe ramura de avans în recursivitate, utilizând

int1(Lista1, Lista2, ListaAcumulare, ListaRez) ca predicat ajutãtor cu parametrul

suplimentar ListaAcumulare, instanþiatã la primul apel la lista vidã.

53

% inter(Lista1, Lista2, ListaRez)

member(Elem, [Elem|_]) :- !.

member(Elem, [_|Rest]) :- member(Elem, Rest).

inter([], _, []).

inter([Prim|Rest], Lista2, [Prim|LRez]) :-

member(Prim, Lista2), !,

inter(Rest, Lista2, LRez).

inter([ _ | Rest], Lista2, LRez) :- inter(Rest, Lista2, LRez).

% int(Lista1, Lista2, ListaRez)

% int1(Lista1, Lista2, ListaAcumulare, ListaRez)

int(L1, L2, LRez) :- int1(L1, L2, [], LRez).

int1([], _, L, L).

int1([Prim|Rest], L, L1, L2) :-

member(Prim,L), !,

int1(Rest, L, [Prim | L1], L2).

int1([ _ | Rest], L, L1, L2) :- int1(Rest, L, L1, L2).

Aceastã tehnicã de programare, des întîlnitã în programele Prolog, are o serie de

avantaje, printre care o claritate crescutã şi, în principal, utilizarea definiþiilor de predicate

recursive la urmã. Un predicat recursiv la urmã este un predicat în care apelul recursiv al

acestuia este ultimul scop din conjuncþia de scopuri care îl defineºte şi pentru care nu mai

existã nici o regulã posibilã de aplicat dupã apelul recursiv. Un astfel de predicat are

avantajul cã poate fi apelat recursiv de oricâte ori fãrã a genera o depãºire a stivei. În plus

execuþia unui astfel de predicat este mai eficientã.

Pentru a pune în evidenþã aceastã comportare se definesc patru variante ale unui

predicat care afiºeazã (numãrã) valori întregi succesive la infinit, începând de la o valoare

fixatã N.

% Predicatele numãrã(N), numãrã1(N), rãu_numãrã(N) şi rãu_numãrã1(N)

% afiºeazã întregi succesivi pornind de la valoarea N.

numara(N) :- write(N), nl, N1 is N + 1, numara(N1).

numara1(N) :- N >= 0, !, write(N), nl, N1 is N + 1, numara1(N1).

numara1( _ ) :- write("Valoare negativa.").

rau_numara(N) :- write(N), nl, N1 is N + 1, rau_numara(N1), nl.

rau_numara1(N) :- N >= 0, write(N), nl, N1 is N + 1, rau_numara1(N1).

rau_numara1(N) :- N < 0, write("Valoare negativa.").

54

Primele douã variante ale acestui predicat, numara(N) ºi numaraa(N), sunt predicate

recursive la urmã. Predicatul numara(N) este definit printr-o singurã regulã şi apelul

recursiv este ultimul scop al definiþiei. Predicatul numara1(N) este definit prin douã reguli,

dar, datoritã predicatului cut din prima regulã, dacă N ³ 0 nu mai existã nici o altã regulã

posibilã de aplicat în momentul apelului recursiv. Ambele variante vor numãra la infinit

începând de la N şi afiºând valori succesive. Urmãtoarele douã variante, rau_numara(N) şi

rau_numara1(N), nu sunt predicate recursive la urmã. Predicatul rau_numara(N) nu are

apelul recursiv ca ultim scop în definiþie, iar rau_numara1(N) are o variantã (regula)

neîncercatã în momentul apelului recursiv. Execuþia ambelor predicate se va opri dupã un

anumit număr de valori afiºate, cu afiºarea unui mesaj de eroare cauzat de depãºirea stivei.

55