cap 1 elem baza prolog fn

7/21/2019 Cap 1 Elem Baza Prolog FN

1/36

Capitolul 1

Elemente de bazale limbajului

Prolog

nceputul programrii logice poate fi atribuit lui R. Kowalski i A. Colmerauer ise situeaz la nceputul anilor '70. Kowalski a plecat de la o formul logic detipul:

S1S2... SnS

care are, n logica cu predicate de ordinul nti, semnificaia declarativconformcreiaS1S2... Sn implicS, adicdacS1i S2... i Sn sunt fiecare adevrateatunci i Seste adevrat, i a propus o interpretare proceduralasociat. Conformacestei interpretri, formula de mai sus poate fi scrissub forma:

SdacS1i S2... i Sn

i poate fi executatca o procedura unui limbaj de programare recursiv, unde Seste antetul procedurii i S1, S2, ... Sncorpul acesteia. Deci, pe lnginterpretareadeclarativ, logic, a unei astfel de formule, aceasta poate fi interpretatprocedural astfel: pentru a executa Sse executS1i S2... i Sn.

n aceeai perioad, A. Colmerauer i colectivul lui de cercetare de laUniversitatea din Marsilia, au dezvoltat un limbaj de implementare a acesteiabordri, pe care l-au denumit Prolog, abreviere de la "Programmation etLogique". De atunci i pn n prezent, limbajul Prolog s-a impus ca cel maiimportant limbaj de programare logici s-au dezvoltat numeroase implementri,att ale unor interpretoare ct i ale unor compilatoare ale limbajului.

Limbajul Prolog este un limbaj declarativ, susinut de o componentprocedural. Spre deosebire de limbajele procedurale, cum ar fi C sau Java, n carerezolvarea problemei este specificatprintr-o serie de pai de execuie sau aciuni,ntr-un limbaj declarativ problema este specificat prin descrierea universului

problemei i a relaiilor sau funciilor existente ntre obiecte din acest univers.Exemple de astfel de limbaje sunt cele funcionale, de exemplu Lisp, Scheme, ML,i cele logice, de exemplu Prolog.

Dei iniial a fost gndit pentru scrierea programelor de prelucrare alimbajului natural, Prolog a devenit cu timpul, un limbaj de uz general, fiind o


2/36

2 CAPITOLUL 1

unealt important n aplicaiile de inteligen artificial. Anumite clase deprobleme pot fi rezolvate mai uor n Prolog, dect n orice alt limbaj procedural.Pentru aceste probleme, un program Prolog poate avea de 10 ori mai pu ine linii

dect echivalentul lui n C++ sau Java. Astfel de probleme sunt n principal celededicate prelucrrilor simbolice sau care necesitun proces de cutare a soluieintr-un spaiu posibil de transformri ale problemei, n acest ultim caz structura decontrol implicit a mainii Prolog facilitnd implementarea.

Prezentarea ce urmeaz a limbajului Prolog, este n principal orientat pedescrierea limbajului Prolog standard. Exemplele de programe din aceast parte,ct i din partea a doua, sunt rulate utiliznd interpretorul SWI-Prolog subWindows, mediul de programare SWI-Prolog i particularitile lui sintactice fiindprezentate n anex.

1.1 Entitile limbajului Prolog

Limbajul Prolog este un limbaj logic, descriptiv, care permite specificareaproblemei de rezolvat, n termenii unor fapte cunoscute despre obiecteleuniversului problemei i a relaiilor existente ntre aceste obiecte. Execuia unuiprogram Prolog constn deducerea implicaiilor acestor fapte i relaii, programuldefinind astfel o mulime de consecine ce reprezint nelesul sau semnificaiadeclarativa programului.

Un program Prolog conine urmtoarele entiti:

faptedespre obiecte i relaiile existente ntre aceste obiecte;

reguli despre obiecte i relaiile dintre ele, care permit deducerea(inferarea) de noi fapte pe baza celor cunoscute;

ntrebri, numite i scopuri, despre obiecte i relaiile dintre ele, la careprogramul rspunde pe baza faptelor i regulilor existente.

1.1.1 Fapte

Faptele sunt predicate de ordinul nti de aritate n, considerate adevrate. Elestabilesc relaii ntre obiectele universului problemei. Numrul de argumente alefaptelor este dat de aritatea (numrul de argumente) corespunztoare a

predicatelor.


3/36

ELEMENTE DE BAZALE LIMBAJULUI PROLOG 3

Exemple:

Interpretarea particulara predicatului i a argumentelor acestuia depinde deprogramator. Ordinea argumentelor, odat fixat, este important i trebuiepstratla orice altutilizare a faptului, cu aceeai semnificaie. Mulimea faptelorunui program Prolog formeazbaza de cunotine Prolog. Se va vedea mai trziu

cn baza de cunotinte a unui program Prolog sunt incluse i regulile Prolog.

1.1.2 Scopuri

Obinerea consecinelor sau a rezultatului unui program Prolog se face prin fixareaunor scopuri, care pot fi adevrate sau false, n funcie de coninutul bazei decunotine Prolog. Scopurile sunt predicate, pentru care se dorete aflarea valoriide adevr n contextul faptelor existente n baza de cunotine. Cum scopurile potfi vzute ca ntrebri, rezultatul unui program Prolog este rspunsul la o ntrebare(sau la o conjuncie de ntrebri). Acest rspuns poate fi afirmativ, yes, saunegativ, no. Se va vedea mai trziu c programul Prolog, n cazul unui rspunsafirmativ la o ntrebare, poate furniza i alte informaii din baza de cunotine.

Exemplu

Considernd baza de cunotine specificat anterior, se pot pune diversentrebri, cum ar fi:

?-iubeste(mihai, maria).yes deoarece acest fapt existn baza de cunotine?-papagal(coco).yes?-papagal(mihai).no deoarece acest fapt nuexistn baza de cunotine

?-inalt(gelu).no

Fapt: Aritate:

papagal(coco). 1iubete(mihai, maria). 2iubete(mihai, ana). 2frumoas(ana). 1bun(gelu). 1deplaseaz(cub, camera1, camera2). 3


4/36

4 CAPITOLUL 1

1.1.3 Variabile

n exemplele prezentate pn acum, argumentele faptelor i ntrebrilor au fost

obiecte particulare, numite i constante sau atomi simbolici. Predicatele Prolog, caorice predicate n logica cu predicate de ordinul I, admit ca argumente i obiectegenerice numite variabile. n Prolog, prin convenie, numele argumentelorvariabile ncepe cu liter, iar numele constantelor simbolice ncepe cu litermic.O variabil poate fi instaniat (legat), dac exist un obiect asociat acesteivariabile, sau neinstaniat (liber), dac nu se tie nc ce obiect va desemnavariabila.

La fixarea unui scop Prolog, care conine variabile, acestea suntneinstaniate, iar sistemul ncearc satisfacerea acestui scop, cutnd printrefaptele din baza de cunotine un fapt, care se poate identifica cu scopul, printr-oinstaniere adecvata variabilelor din scopul dat. Este vorba de fapt, de un proces

de unificare a predicatului scop cu unul din predicatele fapte, existente n baza decunotine.

La ncercarea de satisfacere a scopului, cutarea se face ntotdeauna pornindde la nceputul bazei de cunotine. Dac se ntlnete un fapt, cu un simbolpredicativ identic cu cel al scopului, variabilele din scop se instaniaz conformalgoritmului de unificare i valorile variabilelor astfel obinute sunt afiate, carspuns 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 comportsistemul Prolog n cazul n care existmai multe fapte nbaza de cunotine care unificcu ntrebarea pus? n acest caz existmai multerspunsuri la ntrebare, corespunznd mai multor soluii ale scopului fixat. Primasoluie este dat de prima unificare i exist attea soluii, cte unificri diferiteexist. La realizarea primei unificri, se marcheaz faptul care a unificat i care

reprezintprima soluie. La obinerea urmtoarei soluii, cutarea este reluatde lamarcaj n jos, n baza de cunotine. Obinerea primei soluii este de obicei numitsatisfacerea scopului, iar obinerea altor soluii, resatisfacerea scopului. Lasatisfacera unui scop, cutarea se face ntotdeauna de la nceputul bazei decunotine. La resatisfacerea unui scop, cutarea se face ncepnd de la marcajulstabilit de satisfacerea anterioara acelui scop.


5/36


Sistemul Prolog, fiind un sistem interactiv, permite utilizatorului obinereafie a primului rspuns, fie a tuturor rspunsurilor. n cazul n care, dupafiareatuturor rspunsurilor, un scop nu mai poate fi resatisfcut, sistemul rspunde no.

Exemple:

?-iubeste(mihai, X).X = maria; tastnd caracterul ; i Enter, cerem o nou

soluieX = ana;no?-iubeste(Cine, PeCine).Cine = mihai, PeCine = maria;Cine = mihai, PeCine = ana;no

Existdeci dousoluii pentru scopul iubeste(mihai, X)i tot dousoluiipentru scopul iubeste(Cine, PeCine), considernd tot baza de cunotineprezentatn seciunea 1.1.1.

1.1.4 Reguli

O regulProlog exprimun fapt care depinde de alte fapte i este de forma:

S:-S1, S2, Sn.

cu semnificaia prezentat la nceputul acestui capitol. Fiecare Si, i= 1,ni Sau

forma faptelor Prolog, deci sunt predicate, cu argumente constante, variabile saustructuri. Faptul Scare definete regula, se numete antetde regul, iar S1, S2, Snformeazcorpulregulii i reprezintconjuncia de scopuri, care trebuie satisfcutepentru ca antetul regulii sfie satisfcut.

Fie urmtoarea bazde cunotine Prolog:

frumoasa(ana). % 1bun(vlad). % 2cunoaste(vlad, maria). % 3cunoaste(vlad, ana). % 4iubeste(mihai, maria). % 5

iubeste(X, Y) :- % 6bun(X),cunoaste(X, Y),frumoasa(Y).


6/36

6 CAPITOLUL 1

Se observ c enunul (6) definete o regul Prolog; relaiaiubeste(Cine, PeCine), fiind definit att printr-un fapt (5) ct i printr-o regul(6).

n condiiile existenei regulilor n baza de cunotine Prolog, satisfacereaunui scop se face printr-un procedeu similar cu cel prezentat n Seciunea 1.1.2,dar unificarea scopului se ncearcatt cu fapte din baza de cunotine, ct i cuantetul regulilor din baz. La unificarea unui scop cu antetul unei reguli, pentru aputea satisface acest scop trebuie satisfcut regula. Aceasta revine la a satisfacetoate faptele din corpul regulii, deci conjuncia de scopuri.

Scopurile din corpul regulii devin subscopuri, a cror satisfacere se vancerca printr-un mecanism similar cu cel al satisfacerii scopului iniial.

Pentru baza de cunotine descrismai sus, satisfacerea scopului

?-iubeste(vlad, ana).

se va face n urmtorul mod. Scopul unific cu antetul regulii (6) i duce lainstanierea variabilelor din regula (6): X = vlad i Y = ana. Pentru ca aceastntrebare s fie adevrat, trebuie ndeplinit regula, deci fiecare subscop dincorpul acesteia. Aceasta revine la ndeplinirea scopurilor bun(vlad), care reueteprin unificare cu faptul (2), cunoaste(vlad, ana), care reuete prin unificare cufaptul (4), i a scopului frumoasa(ana), care reuete prin unificare cu faptul (1).n consecin, regula a fost ndeplinit, deci i ntrebarea iniialeste adevrat, iarsistemul rspunde yes.

Ce se ntmpldacse pune ntrebarea:

?-iubeste(X, Y).

Prima soluie a acestui scop este datde unificarea cu faptul (5), iar rspunsul este:

X = mihai, Y = maria

Sistemul Prolog va pune un marcaj n dreptul faptului (5) care a satisfcutscopul. Urmtoarea soluie a scopului iubeste(X, Y) se obine ncepnd cutareade la acest marcaj n continuare, n baza de cunotine. Scopul unificcu antetulregulii (6) i se vor fixa trei noi subscopuri de ndeplinit, bun(X), cunoaste(X, Y)i frumoasa(Y). Scopul bun(X) este satisfcut de faptul (2) i variabila X este

instaniat cu valoarea vlad, X = vlad . Se ncearc acum satisfacerea scopuluicunoaste(vlad, Y), care este satisfcut de faptul (3) i determin instaniereaY = maria. Se introduce n baza de cunotine un marcaj asociat scopuluicunoaste(vlad, Y), care a fost satisfcut de faptul (3).


7/36


Se ncearcapoi satisfacerea scopului frumoasa(maria). Acesta eueaz. nacest moment, sistemul intr ntr-un proces de backtracking, n care se ncearcresatisfacerea scopului anterior satisfcut, cunoaste(vlad, Y), n sperana c o

noua soluie a acestui scop va putea satisface i scopul curent care a euat,frumoasa(Y). Resatisfacerea scopului cunoaste(vlad, Y)se face pornind cutareade la marcajul asociat scopului n jos, deci de la faptul (3) n jos. O nousoluie(resatisfacere) a scopului cunoaste(vlad, Y)este datde faptul (4), care determininstanierea Y = ana. n acest moment, se ncearc satisfacerea scopuluifrumoasa(ana). Cum este vorba de un nou scop, cutarea se face de la nceputulbazei de cunotine i scopul frumoasa(ana) este satisfcut de faptul (1). nconsecin a doua soluie a scopului iubeste(X, Y) este obinut i sistemulrspunde:

X = vlad, Y = ana

urmnd un mecanism de backtracking, descris intuitiv n figura 1.1, prinprezentarea arborilor de deducie construii de sistemul Prolog.

Figura 1.1. Mecanismul de satisfacere a scopurilor n Prolog

La ncercarea de resatisfacere a scopului iubeste(X, Y), printr-un mecanismsimilar, se observ c nu mai exist alte solutii. n concluzie, fiind dat baza defapte i reguli Prolog anterioar, comportarea sistemului Prolog este:

?-iubeste(X, Y).

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


8/36

8 CAPITOLUL 1

X = mihai, Y = maria;X = vlad, Y = ana;no

Observaii:

La satisfacerea unei conjuncii de scopuri n Prolog, se ncearcsatisfacerea fiecrui scop pe rnd, de la stnga la dreapta. Primasatisfacere a unui scop determin plasarea unui marcaj n baza decunotine n dreptul faptului sau regulii care a determinat satisfacereascopului.

Dacun scop nu poate fi satisfcut (eueaz), sistemul Prolog se ntoarcei ncearcresatisfacerea scopului din stnga, pornind cutarea n baza decunotine de la marcaj n jos. nainte de resatisfacerea unui scop, se

elimin toate instanierile de variabile, determinate de ultima satisfacerea acestuia. Dac cel mai din stnga scop din conjuncia de scopuri nupoate fi satisfcut, ntreaga conjuncie de scopuri eueaz.

Aceast comportare a sistemului Prolog, n care se ncearc n modrepetat satisfacerea i resatisfacerea scopurilor din conjunciile descopuri definete mecanismul de backtracking din Prolog.

n capitolul 4 se va discuta pe larg structura de control a sistemuluiProlog, mecanismul fundamental de backtracking i modurile n care sepoate modifica parial acest mecanism.

1.1.5 Un program Prolog simpluSimplitatea i expresivitatea limbajului Prolog poate fi pus n eviden deurmtorul exemplu, care permite definirea rapida unor relaii de asociere.

capitala(burundi,bujumbura).capitala(bahamas,nassau).capitala(africa_de_sud,pretoria).capitala(canada,otawa).capitala(chile,santiago).capitala(elvetia,berna).capitala(danemarca,copenhaga).

capitala(somalia,mogadiscio).capitala(slovenia,ljubljana).

continent(burundi,africa).continent(bahamas,america_de_nord).


9/36


continent(africa_de_sud,africa).continent(canada,america_de_nord).continent(chile,america_de_sud).

continent(elvetia,europa).continent(danemarca,europa).continent(somalia,africa).continent(slovenia,europa).capitala_continent(Oras,Cont):-capitala(Tara,Oras),continent(Tara,Cont).

Pentru ntrebarea

?- capitala_continent(bujumbura,Cont). Cont = africa.

sistemul Prolog indic continentul n care se afl capitala Bujumbura. Deasemenea, se pot cere programului toate continentele asociate capitalelor indicaten baza de date Prolog astfel:

?-capitala_continent(Capitala,Cont).Capitala = bujumbura

Cont = africa ;

Capitala = nassau

Cont = america_de_nord ;

Capitala = pretoria

Cont = africa ;

Capitala = otawa

Cont = america_de_nord ;

Capitala = santiago

Cont = america_de_sud ;

Capitala = berna

Cont = europa ;

Capitala = copenhaga

Cont = europa ;

Capitala = mogadiscio

Cont = africa ;

Capitala = ljubljana

Cont = europa ;

No


10/36

10 CAPITOLUL 1

1.2 Sintaxa limbajului Prolog

Aa cum s-a artat n seciunea anterioar, un program Prolog este format din

fapte, reguli i ntrebri, acestea fiind construite pe baza predicatelor definite deutilizator sau predefinite. n orice sistem Prolog, exist o mulime de predicatepredefinite, unele dintre acestea fiind predicate standard, iar altele depinznd deimplementare. Argumentele predicatelor Prolog, prin analogie cu logicapredicatelor de ordinul I, se numesc termeni, i pot fi constante, variabile saustructuri.

Clasificarea obiectelor n Prolog este prezentatn figura 1.2.

Figura 1.2. Clasificarea obiectelor n Prolog

1.2.1 Constante

Constantele definesc obiecte specifice, particulare, sau relaii particulare. Exist

dou tipuri de constante: atomi i numere. Atomii sunt constante simbolice carencep, de obicei, cu o literi pot conine litere, cifre i caracterul _. Existialte caractere ce pot forma atomi speciali, care au o semnificaie aparte n limbaj.Atomiipot desemna:

obiecte constante care sunt argumentele predicatelor, de exemplu atomiimihaii marian faptul iubeste(mihai, maria);

predicate Prolog, fie cele definite de utilizator, fie cele predefinite nsistem; de exemplu atomul iubesten faptul iubeste(mihai, maria);

atomi speciali, de exemplu atomii :- i ?-;

diverse alte reguli de construcie sintactic a atomilor depind deimplementare.

Numerele pot fi ntregi sau reale; sintaxa particular acceptat, ct idomeniile de definiie depinznd de implementare. Un numar ntreg este un ir decifre zecimale, eventual precedate de un semn. Exemple de numere ntregi: 1 +23

obiecte

obiecte elementare

structuri

constante

variabile

atomi

iruri de caractere

numere ntregi

numere reale


11/36


1515 0 -97. Numerele reale depind de implementarea de Prolog. n general, elesunt reprezentate ntr-o form similar celor din limbaje gen Pascal, C, etc.Exemple de numere reale: 3.14 -0.0035 100.2 +12.02.

1.2.2 Variabile

Variabilele sunt, din punct de vedere sintactic, tot atomi, dar ele au o semnifica iespecial, aa cum s-a artat n Seciunea 1.1.3. Spre deosebire de regulile generaleadmise pentru construcia atomilor, numele unei variabile poate ncepe i cusimbolul _, ceea ce indic o variabil anonim. Utilizarea unei variabileanonime semnific faptul c nu intereseaz valoarea la care se va instania aceavariabil.

De exemplu, interogarea ?- iubeste( _, maria). semnific faptul c sentreabdacexistcineva care o iubete pe Maria, dar nu intereseazcine anume.Limbajul Prolog face distincia ntre litere mari i litere mici (este case sensitive).Se reamintete c, din punctul de vedere al conveniei Prolog, numele oricreivariabile trebuie snceapfie cu litermare, fie cu _.

n Prolog existsituaii n care o variabilapare o singurdatntr-o regula,caz n care nu avem nevoie de un nume pentru ea, deoarece nu este referitdectntr-un singur loc. De exemplu, dacdorim sscriem o regulcare ne spune daccineva este fiul cuiva, o soluie ar fi:

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

Se observ c s-a denumit cu Z un printe anonim. n acest caz, nu

intereseaz cine apare pe post de printe. Pentru a nu ncrca regulile cu numeinutile, care pot distrage atenia i ngreuia citirea programelor, se pot consideraastfel de variabile ca anonime, notate cu underscore _. Deci regula anterioarsepoate rescrie astfel:

este_fiu(X) :- parinte( _ , X).

Variabilele din Prolog nu sunt identiceca semnificaie cu variabilele Pascalsau C, fiind mai curnd similare cu variabilele n sens matematic. O variabil,odat ce a primit o valoare, nu mai poate fi modificat. Acest lucru eliminefectele laterale care sunt permise n limbajele procedurale. O variabil Prologneinstaniat semnific ceva necunoscut. Pentru structurile de date, care nu sunt

variabile i care au nume, numele lor ncepe cu minuscul, urmatde litere, cifresau underscore.

Reprezentarea irurilor depinde de implementarea Prolog. n SWI-Prolog,interpretor care se aliniaz la standardul Edinbourg Prolog, irurile se reprezintntre caractere '.


12/36

12 CAPITOLUL 1

Exemple de iruri de caractere:

'Constantin Noica'

''

Diferena dintre iruri i atomi este urmtoarea: irurile au o reprezentareinternmai relaxati nu pot fi folosite pe post de atomi, n timp ce atomii au deobicei reprezentri interne consumatoare de memorie, n ideea cei trebuie regsiirapid, cautrile Prolog facndu-se n general dupaceti atomi.

1.2.3 Structuri

O structur Prolog este un obiect ce desemneaz o colecie de obiecte corelatelogic, care formeaz componentele structurii. Un exemplu este structura asociatobiectului carte, care este format din componentele: titlu carte, autor, i an

apariie. Un fapt ce referrelaia de posedare a unei cri de Prolog de ctre Mihaipoate fi exprimat astfel:

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

unde carte(prolog, clocksin, 1997) este o structur cu numele carte i cu treicomponente: prolog, clocksin i 1997. Se admit i structuri imbricate, de exemplu:

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

unde predicatul poseda are dou argumente: primul argument este constantamihai, iar cel de-al doilea este structura carte(prolog ....), cu doucomponente, a

doua componentfiind structura autori(clocksin, mellish).n Prolog, o structurse definete prin specificarea:

(1) numelui structurii (functorul structurii);

(2) elementelor structurii (componentele structurii).

Fie tipul punct(X, Y). Atunci tipul segment poate fi reprezentat casegment(P1, P2). De exemplu, un segment, avnd capetele n punctele (1, 1) si(2, 3), poate fi reprezentat astfel:

segment(punct(1, 1), punct(2, 3)).

Structurile Prolog pot fi utilizate pentru reprezentarea structurilor de date(liste, arbori). De exemplu, un arbore binar poate fi reprezentat n Prolog printr-ostructur cu functorul arb si trei componente: rdcina, subarbore stng sisubarbore drept. Astfel, structura

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


13/36


reprezintun arbore binar cu cheia din rdcina barbu, cu subarborele drept vid icu subarborele stng format dintr-un singur nod cu cheia ada.

Exist i cazuri n care un obiect poate avea constitueni compui deadncime variabil. Astfel se ajunge la al doilea tip de recursivitate n Prolog, ianume, recursivitatea obiectelor. De exemplu, un arbore binar, cu chei numericepoate fi definit astfel:

1) Nodul vid este un arbore; putem nota acest nod vid prin constantanil;

2) Un nod frunzeste un arbore, de exemplu nod(15, nil, nil);

3) Un nod cu succesor stng i succesor drept este un arbore, deexemplunod(20, ArbStng, ArbDrept).

De exemplu, reprezentarea n Prolog a arborelui

este nod(1, nod(2, nod(4, nil, nil), nod(5, nod(7, nil, nil), nil)), nod(3, nil, nod(6,nil, nil)))

Observaii:

Sintaxa structurilor este aceeai cu cea a faptelor Prolog. Un predicatProlog poate fi vzut ca o structur a crui functor este numelepredicatului, iar argumentele acestuia reprezintcomponentele structurii.

Considerarea predicatelor Prolog ca structuri prezint un interesdeosebit; att datele ct i programele n Prolog au aceeai form, ceea ce

faciliteaz tratarea uniform i sinteza dinamic de programe. ncapitolul 4 se vor prezenta predicate predefinite n Prolog, care permitsinteza i execuia dinamica programelor Prolog.

1

2 3

4 5 6

7


14/36

14 CAPITOLUL 1

1.2.4 Operatori

Uneori este convenabil s se scrie anumii functori (nume de structuri sau

predicate) n form infixat. Aceasta este o form sintacticce mrete claritateaprogramului, cum ar fi cazul operatorilor aritmetici sau al operatorilor rela ionali.

Limbajul Prolog ofer o mulime de operatori, unii care se regsesc naproape orice implementare, iar alii care sunt specifici unei versiuni particulare deimplementare a limbajului. n continuare se vor prezenta o parte dintre operatoriidin prima categorie.

(1) Operatori aritmetici

Operatorii aritmetici binari, cum ar fi +, -, *, /, pot fi scrii n Prolog n notaieinfixat; de exemplu:

1 + 2*(X * Y) / Z

Aceast sintax este de fapt o rescriere infixat a formei prefixate a structurilorechivalente:

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

Este important de reinut coperatorii aritmetici sunt o rescriere infixataunor structuri, deoarce valoarea expresiei astfel definit nu este calculat.Evaluarea expresiei se face la cerere, n cazul n care se folosete operatorulpredefinit infixat is, de exemplu:

X is 1 + 2.

va avea ca efect instanierea variabilei Xla valoarea 3.

(2) Operatori relaionali

Operatorii relaionali sunt predicate predefinite infixate. Un astfel de operator esteoperatorul de egalitate=. Predicatul (operatorul) de egalitate X = Yreuete dacaX unificcu Y. Din aceasta cauz, dndu-se un scop de tipul X = Y, regulile dedecizie care indicdacscopul se ndeplinete sau nu sunt urmtoarele:

DacXeste variabil neinstaniat, iar Yeste instaniat la orice obiectProlog, atunci scopul reuete. Ca efect lateral, X se va instania laaceeai valoare cu cea a lui Y. De exemplu:

?-carte(barbu, poezii) = X.

este un scop care reuete i X se instaniazla carte(barbu, poezii).

Dacatt Xct i Ysunt variabile neinstaniate, scopul X = Yreuete,variabila Xeste legatla Yi reciproc. Aceasta nseamncori de cte


15/36


ori una dintre cele dou variabile se instaniaz la o anumit valoare,cealaltvariabila se va instania la aceeai valoare.

Atomii i numerele sunt ntotdeauna egali cu ei nii.

Dou structuri sunt egale dac au acelai functor, acelai numr decomponente i fiecare component dintr-o structur este egal cucomponenta corespunztoare din cealaltstructur. De exemplu, scopul:

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

este satisfcut, iar ca efect lateral se fac instanierile:

X = barbiliani Y = riga_crypto.

Operatorul de inegalitate \= se definete ca un predicat opus celui deegalitate. Scopul X \= Y reuete dac scopul X = Ynu este satisfcut i eueazdacX = Y reuete. n plus, existpredicatele relaionale de inegalitate, definiteprin operatorii infixai >,


16/36

16 CAPITOLUL 1

operatorul predefinit mod, se poate scrie un predicat Prolog cu efectsimilar. O definiie posibil a predicatului modulo(X, Y, Z), cusemnificaia argumentelor Z = X mod Y , presupunnd 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. Plecnd de la predicatul modulo definit anterior, se poate definipredicatul de calcul al celui mai mare divizor comun a dou numere,conform algoritmului lui Euclid, presupunnd X > 0, Y > 0 , astfel:

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

La ntrebarea

?-cmmdc(15, 25, C).C=5

rspunsul sistemului este corect. n cazul n care se ncearc obinereaunor noi soluii (pentru semnificaia cmmdc acest lucru este irelevant,dar intereseazdin punctul de vedere al funcionrii sistemului Prolog) seobserv c sistemul intr ntr-o bucl infinit, datorit imposibilitiiresatisfacerii scopului modulo(X, Y, Z)pentru Y = 0. Dacla definiiapredicatului modulose adaugfaptul:

modulo(X, 0, X).

atunci predicatul modulo(X, Y, Z) va genera la fiecare resatisfacereaceeai soluie, respectiv soluia corect, la infinit. Cititorul este sftuits traseze execuia predicatului cmmdc n ambele variante deimplementare a predicatului modulo.

3. Doi copii pot juca un meci ntr-un turneu de tenis dacau aceeai vrsta.Fie urmtorii copii i vrstele lor:

copil(peter, 9).copil(paul, 10).copil(chris, 9).copil(susan, 9).

Toate perechile de copii care pot juca un meci ntr-un turneu de tenissunt calculate de predicatul:


17/36


pot_juca(Pers1, Pers2) :-

copil(Pers1, Varsta), copil(Pers2, Varsta), Pers1 \= Pers2.

4. S scriem un program care s i gseasc Anei un partener la bal. Eadorete s mearg cu un brbat care este nefumator sau vegetarian.Pentru aceasta dispunem de o baza de date cu informa ii despre civabrbai:

barbat(gelu). barbat(bogdan). barbat(toma).fumator(toma). fumator(dan).vegetarian(gelu).Pentru a exprima doleanele Anei, vom scrie doureguli:

Ana se ntlnete cu X dacX este brbat i nu este fumtor.

Ana se ntlnete cu X dacX este brbat i este vegetarian.

Adic:

ana_se_intalneste_cu(X) :-barbat(X), not(fumator(X)).ana_se_intalneste_cu(X) :-barbat(X), vegetarian(X).

5. Un program Prolog este o niruire de fapte (facts) i reguli(rules) carepoart denumirea de clauze (clauses). Faptele i regulile au o structuracomun, ceea ce permite sinteza dinamicde cod, care este adaugat nbaza de cunotine. Un fapt poate fi privit ca o regulcare are ca premiz(ipotez) scopul true, care este adevrat ntotdeauna. Astfel:

fapt.

este echivalent cu

fapt :-true.

O regula frantet, deci de forma:

:-scop.

determinexecuia automata scopului scop la reconsultarea bufer-uluin care apare. Efectul este similar cu cel obinut la introducerea nfereastra principala ntrebrii:

?-scop.

Exemple de ntrebari:

place(ellen, tennis). % lui ellen i place tenisulplace(john, fotbal). % lui john i place fotbalulplace(tom, baseball). % lui tom place baseball-ulplace(eric, not). % lui eric i place notul


18/36

18 CAPITOLUL 1

place(mark, tenis). % lui mark i place tenisulplace(bill, X) :-place(tom, X). % lui bill i place ce i place lui tom

% Ce sporturi i plac lui john??-place(john, X).X = fotbal

% Cui i place tenisul??-place(Y, tenis).Y = ellen;

Y = mark

% Putem pune i ntrebri particulare:?-place(ellen, tenis).yes?-place(ellen, fotbal).no?-place(bill, baseball).yes

1.2.5 Liste

O listeste o structurde date ce reprezinto secvenordonatde zero sau maimulte elemente. O listpoate fi definitrecursiv astfel:

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

(2) o listeste o structurcu doucomponente: primul element din list(capul listei) i restul listei (lista format din urmatoarele elementedin lista).

Sfritul unei liste este de obicei reprezentat ca lista vid.

n Prolog structura de list este reprezentat printr-o structur standard,predefinit, al crei functor este caracterul . i are dou componente: primulelement al listei i restul listei. Lista videste reprezentatprin atomul special [ ].De exemplu, o list cu un singur element a se reprezint n Prolog, prin notaie

prefixatastfel .(a, [ ]), iar o listcu trei elemene, a, b, c, se reprezintca:

.(a, .(b, .(c, [ ]))).

Deoarece structura de listeste foarte des utilizatn Prolog, limbajul ofero sintax alternativ pentru descrierea listelor, format din elementele listei


19/36


separate de virguli ncadrate de paranteze drepte. De exemplu, cele dou listeanterioare pot fi exprimate astfel:

[a][a, b, c]

Aceast sintax a listelor este general i valabil n orice implementareProlog. O operaie frecventasupra listelor este obinerea primului element dintr-olisti a restului listei, deci a celor doucomponente ale structurii de list. Aceastoperaie este realizat n Prolog de operatorul de scindare a listelor | scris suburmtoarea form:

[Prim |Rest]

Variabila Primstpe postul primului element din list, iar variabila Restpe

postul listei care conine toate elementele din list cu excepia primului. Acestoperator poate fi aplicat pe orice listcare conine cel puin un element. Daclistaconine exact un element, Restva reprezenta lista vid. ncercarea de identificare astructurii [Prim | Rest]cu o listvidduce la eec. Mergnd mai departe, se potobine chiar primele elemente ale listei i restul listei. Iatcteva echivalene:

[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 oricestructuri. n consecinse pot construi liste de liste.

Exemple:

1. Se poate defini urmtoarea structurde list:[carte(barbu, poezii), carte(clocksin, prolog)]

2. Considernd urmtoarele fapte existente n baza de cunotine Prolog

pred([1, 2, 3, 4]).pred([coco, sta, pe, [masa, alba]]).

se pot pune urmtoarele ntrebri obinnd rspunsurile specificate:

?-pred([Prim | Rest]).Prim = 1, Rest = [2, 3, 4];Prim = coco, Rest = [sta, pe, [masa, alba]];no

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


20/36

20 CAPITOLUL 1

3. Un predicat util n multe aplicaii este cel care testeazapartenena unuielement la o listi care se definete astfel:

% membru(Element, Lista)membru(Element, [Element | _ ]).membru(Element, [ _ | RestLista]) :-membru(Element, RestLista).

Funcionarea acestui scurt program Prolog poate fi urmrit cerndrspunsul sistemului la urmtoarele scopuri:

?-membru(b, [a, b, c]). %1yes?-membru(X, [a, b, c]). %2X = a;X = b;

X = c;no?-membru(b, [a, X, b]). %3X = b;X = _G302;

no

Deci pentru cazul n care primul argument este o variabil (%2), existtrei soluii posibile ale scopului membru(Element, Lista). Dac listaconine o variabil(%3), existdousoluii pentru forma listei: [a, b, b],cnd X se instaniazla bi predicatul reuete cu bmembru pe a doua

poziie, i [a, _ , b], caz n care variabila X este neinstaniat lucrumarcat de sistem printr-un indentificator arbitrar de forma _G302 ipredicatul reuete cu bmembru pe a treia poziie.

Observaii:

Exemplul 3 pune n eviden o facilitate deosebit de interesant alimbajului Prolog, respectiv puterea generativ a limbajului. Predicatulmembrupoate fi utilizat att pentru testarea apartenenei unui element lao list, ct i pentru generarea, pe rnd, a elementelor unei liste, prinresatisfacere succesiv. n anumite contexte de utilizare, aceastfacilitatepoate fi folositoare, iar n altele ea poate genera efecte nedorite atunci

cnd predicatul membru este utilizat n definirea altor predicate, aacum se va arta n partea a doua a lucrrii.

La definirea unui predicat p, care va fi utilizat n definirea altorpredicate, trebuie ntotdeauna s se analizeze numrul de soluii ct isoluiile posibile ale predicatului p. Acest lucru este necesar, deoarece


21/36


dacpapare ntr-o conjuncie de scopuri p1,, pi-1, p ,pi+1,, pni unuldintre scopurile pi+1,, pn eueaz, mecanismul de backtracking dinProlog va ncerca resatisfacerea scopului p. Numrul de soluii, precum

i soluiile scopului p influeneaz astfel, n mod evident, numrul desoluii, ct i soluiile conjunciei de scopuri p1,, pi-1, p ,pi+1,, pn.Exemple n acest sens i modaliti de reducere a numrului total desoluii ale unui corp vor fi prezentate n capitolul 4.

1.3 Limbajul Prolog i logica cu predicate de ordinul

nti

Limbajul Prolog este un limbaj de programare logic. Dei conceput iniial pentrudezvoltarea unui interpretor de limbaj natural, limbajul s-a impus ca o solu ie

practicde construire a unui demonstrator automat de teoreme folosind rezoluia.Demonstrarea teoremelor prin metoda rezoluiei necesitca axiomele i teorema sfie exprimate n forma clauzal. Sintaxa i semantica limbajului Prolog permitutilizarea numai a unei anumite forme clauzale a formulelor bine formate: clauzeHorn distincte. Se prezint n continuare, pe scurt, noiunile logice de bazsemnificative pentru limbajul Prolog.

1.3.1 Clauze Horn

Definiie. Se numete clauzo disjuncie de literali. Un literal este un predicatsau un predicat negat. Se numete clauzHorno clauzcare conine cel mult un

literal pozitiv.

Definiie. Se numete clauz vid o clauz far nici un literal; clauza vid senoteaz, prin convenie, cu.

Deoarece faptele i regulile Prolog sunt n formclauzal, forma particulara clauzelor fiind clauze Horn distincte, acestea din urmse mai numesc i clauzeProlog.

Definiie. Se numete clauz Horn o clauz care conine cel mult un literalpozitiv. O clauzHorn poate avea una din urmtoarele patru forme:

(1) o clauzunitarpozitivformatdintr-un singur literal pozitiv;

(2) o clauznegativformatnumai din literali negai;

(3) o clauzformatdintr-un literal pozitiv i cel puin un literal negativ,numiti clauzHorn mixt;

(4) clauzvid( ).


22/36

22 CAPITOLUL 1

Definiie. Se numete clauzHorn distinct o clauz care are exact un literalpozitiv, ea fiind fie o clauzunitarpozitiv, fie o clauzHorn mixt.

Clauzele Horn unitare pozitive se reprezint n Prolog prin fapte, iarclauzele Horn mixte prin reguli. O clauzHorn mixtde forma:

S1S2SnS

se exprimn Prolog prin regula:

S:-S1, S2, Sn.

Semnificaia intuitiva unei reguli Prolog are un corespondent clar n logicacu predicate de ordinul I dacse ine cont de faptul co clauzHorn mixtpoateproveni din urmtoarea formulbine format:

S1S2SnS

Variabilele din clauzele distincte se transform n variabile Prolog,constantele din aceste formule n constante Prolog, iar func iile pot fi asimilate custructuri Prolog. Deci argumentele unui predicat Prolog au forma termenilor dincalculul cu predicate de ordinul I.

Exemple:

1. Fie urmtoarele enunuri: Orice sportiv este puternic. Oricine este inteligentiputernic va reui n via. Oricine este puternic, va reui n viasau va ajunge

btu. Existun sportiv inteligent. Gelu este sportiv.Exprimnd enunurile nlogica cu predicate de ordinul I se obin urmtoarele formule bine formate:

A1.

(

x) (sportiv(x)

puternic(x))A2. (x) (inteligent(x) puternic(x) reuete(x))

A3. (x) (puternic(x) (reuete(x) btu(x)))

A4. (x) (sportiv(x) inteligent(x))

A5. Sportiv(gelu)

Axiomele se transformn forma clauzali se obin urmtoarele clauze:

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)


23/36


Clauzele C1, C2, C4, C4' i C5 pot fi transformate n Prolog deoarecesunt clauze Horn distincte, dar clauza C3 nu poate fi transformat nProlog. Programul Prolog care se obine prin transformarea acestor

clauze este urmtorul:

puternic(X) :-sportiv(X).reuseste(X) :-inteligent(X), puternic(X).sportiv(a).inteligent(a).sportiv(gelu).

2. Fie urmtoarele enunuri:

(a) Orice numr raional este un numr real.

(b)Existun numr prim.

(c) Pentru fiecare numr x existun numr y astfel nct x < y .

Dacse noteazcu prim(x)x este numr prim, cu rational(x)x estenumr raional, cu real(x)x este numr reali cu mai_mic(x, y)xeste mai mic dect y,reprezentarea sub formde formule bine formaten calculul cu predicate de ordinul I este urmtoarea:

A1. (x) (raional(x) real(x))

A2. (x) prim(x)

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

Reprezentarea n formclauzaleste:

C1. ~ rational(x) real(x)

C2. prim(a)

C3. mai_mic(x, mai_mare(x))

unde mai_mare(x) este funcia Skolem care nlocuiete variabila ycuantificatexistenial. Forma Prolog echivalenta acestor clauze este:

real(X) :-rational(X).prim(a).mai_mic(X, mai_mare(X)).

unde mai_mare(x) este o structurProlog.

Este evident c nu orice axiom poate fi transformat n Prolog i c,dintr-un anumit punct de vedere, puterea expresiv a limbajului este inferioarcelei a logicii cu predicate de ordinul I. Pe de altparte, limbajul Prolog ofero


24/36

24 CAPITOLUL 1

mulime de predicate de ordinul II, adicpredicate care acceptca argumente altepredicate Prolog, care nu sunt permise n logica cu predicate de ordinul I. Acestlucru oferlimbajului Prolog o putere de calcul superioarcelei din logica clasic.

Uneori, aceste predicate de ordinul II, existente n Prolog, pot fi folosite pentru amodela versiuni de programe Prolog, echivalente cu o mul ime de axiome, care nuau o reprezentare n clauze Horn distincte. Se propune cititorului, dupparcurgerea seciunii urmtoare, srevinla Exemplul 1 i sncerce gsirea uneiforme Prolog relativ echivalente (cu un efect similar) cu clauza C3.

1.3.2 Respingere rezolutiv

Limbajul Prolog demonstreaz scopuri (teoreme) prin metoda respingeriirezolutive. Strategia rezolutivutilizatn Prolog este strategia rezoluiei de intrareliniar. Aplicarea principiului rezoluiei n logica cu predicate de ordinul I, implic

construirea rezolventului a doi literali complementari, care fie sunt identici, fie aufost fcui identici, prin aplicarea substituiei, definitde cel mai general unificatoral celor doi literali asupra clauzelor ce conin aceti doi literali.

Definiie. Fie clauzele:

(C1) P P ... P ... P1 2 i n

(C2) Q Q ... ~ Q ... Q1 2 j m

numite clauze printe i cel mai general unificator al literalilor Pi si Qj, cuP = Qi j . Atunci C = rez (C ,C ) = (C -{P }) (C -{~ Q })1 2 1 i 2 j este un

rezolvent binaral clauzelor C1si C2.

Observaie. Rezolventul a dou clauze nu este unic. Aplicarea rezoluiei ntredou clauze care rezolv poate genera diveri rezolveni n cazul n care n celedou clauze exist mai muli literali complementari care, prin unificare, pot fifcui identici.

Demonstrarea teoremelor aplicnd metoda respingerii prin rezoluie poate fidescris de algoritmul urmtor. Enunurile care descriu problema trebuieexprimate n modelul logic i formeaz mulimea de axiome A. Concluzia caretrebuie obinut, deci rezolvarea problemei, este teorema de demonstrat.

Algoritm: Respingerea prin rezoluie n logica cu predicate de ordinul I1. Convertete setul de axiome A n formclauzali obine mulimea declauze S0

2. Neagteorema de demonstrat, transformteorema negatn formclauzala i adaugrezultatul obinut la S0, S S0


25/36


3. repet

3.1. Selecteazo pereche de clauze C1, C2

3.2. Fie literalii L C1 1 si ~ L C2 2 3.3. Aplicunificarea i calculeaz= mgu(L , L )1 2

3.4. dac

atunci

3.4.1. DeterminC = rez(C ,C )1 2

3.4.2. dacC

atunciS S {C}

pn s-a obinut clauza vid() sau

nu mai existnici o pereche de clauze care rezolvsauo cantitate predefinitde efort a fost epuizat

4. dacs-a obinut clauza vid

atunciteorema este adevarat(este demonstrat)

5. altfel

5.1. dacnu mai existnici o pereche de clauze care rezolv

atunciteorema este fals

5.2. altfelnu se poate spune nimic despre adevrul teoremei

sfrsit.

Observaii:

In cazul n care s-a obinut clauza vid, metoda respingerii prin rezoluiegaranteaz faptul cteorema este adevarat, deci demonstrabilpe bazasetului de axiome A.

Reciproc, dacteorema este adevarat, se poate obine clauza vid, dupun numr finit de execuii ale pasului 3, cu condiia ca strategia derezoluie sfie complet.

Condiia de oprire a ciclului, "o cantitate predefinit de efort a fostepuizat" a fost introdus, deoarece metoda demonstrrii teoremelor prin

respingere rezolutiv este semidecidabil n logica cu predicate deordinul I. In cazul n care concluzia T de demonstrat este fals, deci nueste teorem, este posibil sa se ajung n situaia n care, dac avemnoroc, "nu mai existnici o pereche de clauze care rezolv". Atunci sepoate concluziona cteorema este fals. Dar este de asemenea posibil ca


26/36

26 CAPITOLUL 1

pasul 3 sse execute la infinit, dacT nu este teorem. Din acest motiv,se introduce o cantitate predefinitde efort (resurse de timp sau spaiu) laepuizarea creia algoritmul se oprete. In acest caz, s-ar putea ca teorema

sa fie adevarat, dar efortul predefinit impus sa fie prea mic, sau se poateca T snu fie teorem. Rezultdeci c, nu se poate spune nimic despreadevrul teoremei.

Strategia rezoluiei liniare are la baz urmatoarea idee: orice rezolventobinut n rezoluie este utilizat ca unul din cei doi rezolveni pe baza crora seobine urmtorul rezolvent. Astfel, daca S este mulimea iniialde clauze, C0Sclauza de pornire, atunci:

C1{Rez(C0, Ci)| C0, CiS}

Ck+1{Res(Ck, Ci)| Ci{Ck-1, Ck-2, ..}S}, k=1, 2, 3,

Strategia rezoluiei de intrare liniar este un caz particular al strategieirezoluiei liniare, n care una din clauzele care rezolvaparine ntotdeauna setuluiinitial de axiome. Astfel, dacS este mulimea iniialde clauze, C0S clauza depornire, atunci:

C1{Rez(C0, Ci)| C0, CiS}

Ck+1{Res(Ck, Ci)| CiS}, k=1, 2, 3,

Strategia rezoluiei liniare de intrare este o strategie rezolutiv foarteeficient, dar nu este o strategie care, dei nu este complet n general, estecompletpentru clauze Horn. Aceaststrategie este deosebit de eficientdin punctde vedere al implementrii i jutificastfel forma restricionata clauzelor Prolog(clauze Horn).

1.4 Structura de control a limbajului Prolog

Spre deosebire de limbajele de programare clasice, n care programul defineteintegral structura de control i fluxul de prelucrri de date, n Prolog exist unmecanism de control predefinit.

1.4.1 Seminificaia declarativi procedural

Semnificaia declarativ a unui program Prolog se refer la interpretarea strictlogica clauzelor acelui program, rezultatul programului fiind reprezentat de toateconsecinele logice ale acestuia. Semnificaia declarativdetermindacun scopeste adevrat (poate fi satisfcut) i, n acest caz, pentru ce instane de variabileeste adevrat scopul. Se reamintete co instana unei clauze este clauza de baz


27/36


(clauza frvariabile) obinutprin instanierea variabilelor din clauza iniial. naceste condiii semnificaia declarativ a unui program Prolog se poate definiprecum urmeaz:

Definiie. Un scop S este adevrat ntr-un program Prolog, adic poate fisatisfcut sau derivlogic din program, daci numai dac:

1. existo clauzCa programului;

2. existo instanIa clauzei Castfel nct:

2.1. antetul lui Isfie identic cu cel al lui S;

2.2. toate scopurile din corpul lui I sunt adevrate, deci pot fisatisfcute.

Observaii:

n definiia de mai sus clauzele refer att fapte, ct i reguli Prolog.Antetul unei clauze este antetul regulii, dacclauza este o regulProlog(clauzHorn mixt) i este chiar faptul, dacclauza este un fapt Prolog(clauz unitarpozitiv). Corpul unui fapt este considerat vid i un fapteste un scop, care se ndeplinete ntotdeauna.

n cazul n care ntrebarea pus sistemului Prolog este o conjuncie descopuri, definiia anterioarse aplicfiecrui scop din conjuncie.

Semnificaia procedurala unui program Prolog se refer la modul n caresistemul ncearc satisfacerea scopurilor, deci la strategia de control utilizat.Diferena dintre semnificaia declarativi semnificaia proceduraleste aceea c

cea de a doua definete, pe lnga relaiile logice specificate de program, i ordineade satisfacere a scopurilor i subscopurilor. n prima seciune a acestui capitol s-afcut o prezentare informala modalitii procedurale de satisfacere a scopurilor nProlog. n continuare, se rafineaz aceast comportare. Din punct de vedereprocedural, un program Prolog poate fi descris de schema bloc prezentatn figura1.3.

Indicator SUCCES sau INSUCCES

Instanele variabilelor din scopuri

Conjuncii

de scopuri

Execuie sistem

Prolog

Program Prolog

Figura 1.3. Comportarea procedurala sistemului Prolog


28/36

28 CAPITOLUL 1

Semnificaia procedural a unui program Prolog poate fi descris deurmtorul algoritm, n care L = {S1, S2, , Sn} este lista de scopuri de satisfcut,iar B este lista de instanieri (unificri) ale variabilelor din scopuri, iniial vid.

Aceastlistse va actualiza la fiecare apel.

Algoritm. Strategia de control Prolog

SATISFACE(L,B)

1. dacL = {} % lista vid

atunci afieazB intoarceSUCCES.

2. Fie S1 primul scop din L i p predicatul referit de S1. Parcurge clauzeleprogramului, de la prima clauz sau de la ultimul marcaj fixat, asociat lui p,pnce se gsete o clauzC al crei antet unificcu S1.

3. dacnu existo astfel de clauz

atuncintoarceINSUCCES.

4. Fie Cde forma H :- D1,,Dm, m0. Plaseazun marcaj n dreptul clauzei C,asociat lui p. (Hconine predicatul p).

5. Redenumete variabilele din C i obtine C' astfel nct s nu existe nici ovariabil comun ntre C' i L; C' este de tot forma H :- D1,,Dm. curedenumirile fcute.

6. L {D1,,Dm,S2,,Sn} % dacCeste fapt, atunci Lse va reduce

7. Fie B1instanierea variabilelor care rezultdin unificarea lui S1cu H.

8. Substituie variabilele din L cu valorile date de B1i obine:

L {D1,,Dm,S2,,Sn }.9. BBB1.

10.dacSATISFACE(L, B)=SUCCES

atunci afieazB intoarceSUCCES.

11.repetde la1.

sfrit

Observaii:

Algoritmul de mai sus reprezint de fapt implementarea strategieirezolutive de intrare liniar utilizat de limbajul Prolog, pentru care se

impune o ordine prestabilitde considerare a clauzelor.

Algoritmul aratfuncionarea sistemului pentru gsirea primei soluii.


29/36


Indicatorul SUCCES/INSUCCES corespunde rspunsurilor de yes,respectiv no, date de sistemul Prolog la ncercarea de satisfacere a uneiliste de scopuri.

1.4.2 Ordinea clauzelor i a scopurilor

Urmtoarele dou exemple pun n eviden diferena dintre semnificaiadeclarativi semnificaia procedurala programelor Prolog. Primul exemplu esteun scurt program care definete relaiile de printe i strmo existente ntremembrii unei familii. Se dau patru definiii posibile ale relaiei de strmo, str1,str2, str3 i str4, toate fiind perfect corecte din punct de vedere logic, deci dinpunct de vedere a semnificaiei 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).

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

% Se schimbordinea regulilor:

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

% Se schimbordinea scopurilor n prima variant:str3(X, Z) :-parinte(X, Z).str3(X, Z) :-str3(X, Y), parinte(Y, Z).

% Se schimbatt ordinea regulilor, ct i ordinea scopurilor:str4(X, Z) :-str4(X, Y), parinte(Y, Z).str4(X, Z) :-parinte(X,Z).


30/36

30 CAPITOLUL 1

Figura 1.4. Arborele genealogic definit de programul Prolog

Figura 1.4 prezintarborele genealogic definit de faptele Prolog anterioare.n raport cu semantica declarativ a limbajului se pot schimba, fr a modifica

nelesul logic, att ordinea clauzelor care definesc relaia de strmo, ct iordinea scopurilor n corpul regulii de aflare a strmoilor. Schimbnd ordineaclauzelor, se obine din predicatul str1 definiia alternativ a relaiei de strmostr2; schimbnd ordinea scopurilor din corpul regulii n varianta ini ialse obinedefiniia predicatului str3; i, schimbnd att ordinea clauzelor, ct i ordineascopurilor n regul, se obine predicatul str4.

Comportarea programului folosind cele patru definiii alternative, dac sedorete aflarea adevrului relaiei de strmo pentru perechile (ada, miu) i(mia, roco), este cea prezentatn continuare.

?-str1(ada, misu).

yes

Pentru acest scop, arborele de deducie este prezentat n figura 1.5.

Figura 1.5. Arborele de deducie a scopului str1(ada, misu)

vali ada

gelu mia

lina miu

roco

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


31/36


?-str2(ada, misu).yes?-str3(ada, misu).yes

Pentru scopul str3(ada, misu), arborele de deducie este cel prezentat nfigura 1.6.

Figura 1.6. Arborele de deducie a scopului str3(ada, misu)

?-str4(ada, misu).% buclinfinita; mesaj de depire a stivei (ERROR: Out of local stack)

Pentru acest scop, arborele de deducie este cel prezentat n figura 1.7.

Figura 1.7. Arborele de deducie (infinit) a scopului str4(ada, misu)

Din punctul de vedere al semnificaiei procedurale, cele patru definiii nusunt echivalente. Primele dou, str1i str2, pot da rspuns pozitiv sau negativ laorice ntrebare, dar str2 este mai ineficient dect str1. Cititorul poate ncerca

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

str4(ada, misu)

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

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

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

arbore infinit

...


32/36

32 CAPITOLUL 1

trasarea arborelui de deducie al satisfacerii scopului str2(ada, misu) icompararea acestuia cu cel corespunztor satisfacerii scopului str1(ada, misu).Definiia str4produce o buclinfinitdatoritintrrii infinite n recursivitate. Este

evident o definiie greit din punct de vedere procedural. Definiia relaiei destrmostr3este o definiie "capcan". Dupcum se poate observdin arborele dededucie prezentat, rspunsul sistemului este afirmativ, n cazul n care exist orelaie de strmontre cele doupersoane argumente ale predicatului. n cazul ncare o astfel de relaie nu exist, sistemul intrntr-o bucl infinit, cum ar fi, deexemplu, pentru persoanele miai roco.

?-str1(mia, roco).no?-str2(mia, roco).no

?-str3(mia, roco).% buclinfinit; mesaj de depire a stivei

n acest caz, arborele de deducie al scopului str3(mia, roco) este prezentatn figura 1.8. Datorit semnificaiei procedurale a limbajului Prolog, trebuieurmrit cu atenie modul de definire a unui predicat, att din punctul de vedere alordinii clauzelor, ct i din punctul de vedere al ordinii scopurilor n corpulregulilor.

Figura 1.8. Arbore de deducie infinit pentru un scop fals

Al doilea exemplu se referla rezolvarea n Prolog a urmtoarei probleme.O maimuse gsete la ua unei camere i o bananse aflagatde plafon ncentrul camerei. Lng fereastra camerei se aflo cutie pe care maimua o poatefolosi pentru a se urca pe ea i a ajunge la banan. Maimua tie s facurmtoarele micri: smeargpe sol, sse urce pe cutie, sdeplaseze cutia dac

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


33/36


este lngcutie, sapuce banana daceste pe cutie i cutia este n centrul camerei.Se cere sse scrie un program Prolog care sdescrie aceastproblemi care spoatrspunde dac, dintr-o configuraie iniialspecificatprin poziia maimuei

i a cubului, maimua poate apuca banana, dupexecuia unei secvene de micri.

Reprezentarea universului problemei n Prolog este specificat dup cumurmeaz. Starea iniialeste:

(1) Maimua este la u.

(2) Maimua este pe sol.

(3) Cutia este la fereastr.

(4) Maimua nu are banana.

i poate fi descrisprin structura Prolog:

stare(la_usa, pe_sol, la_fereastra, nu_are_banana)

Starea finaleste aceea n care maimua are banana

stare( _ , _ , _ , are_banana)

Micrile cunoscute de maimu, deci operatorii de tranziie dintr-o stare n alta,sunt:

(m1) Apucbanana. apuc

(m2) Urcpe cutie. urc

(m3) Mutcutia. mut(Poziia1, Poziia2)(m4) Merge (maimua se deplaseazpe sol). merge(Poziia1, Poziia2)

i sunt reprezentate prin structurile Prolog indicate la dreapta micrilor.

Dintr-o anumit stare numai anumite micri sunt permise. De exemplu,maimua nu poate apuca banana dect dac este urcat pe cutie i cutia este ncentrul camerei, adicsub banan. Micrile permise pot fi reprezentate n Prologprin predicatul de deplasare deplcu trei argumente:

depl(Stare1, Micare, Stare2)

care transform problema din starea Stare1 n starea Stare2, prin efectuareamicrii legale Micaren starea Stare1. Se observc, reprezentarea aleasesteo reprezentare a problemei, folosind spaiul strilor.

Stare1 Stare2Micare


34/36

34 CAPITOLUL 1

Soluia problemei este completat prin adugarea predicatuluipoatelua(Stare),care va reui, dacmaimua poate ajunge din starea iniialStarentr-o stare final, n care poate lua banana, stare finaldescrisde:

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)% Micri 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 rspunde afirmativ: maimua este fericiti mnncbanana.

O analizatenta programului conduce la concluzia cprogramul dsoluiinumai pentru anumite situaii. n primul rnd, strategia de control a micrilormaimuei este impus de ordinea clauzelor care definesc predicatul depl. Astfel,maimua prefernti sapuce, apoi surce, apoi smute cubul i numai la urms mearga prin camer. Dac clauza corespunztoare micriimerge(Pozitia1, Pozitia2)ar fi fost pusca prima clauzn definiia predicatuluide deplasare, maimua ar fi mers la infinit prin camer, frsmai ajungsmute

cubul sau s apuce banana. Chiar pentru ordinea dat a clauzelor, dac se punentrebarea

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


35/36


Deci, dacintereseazdin ce poziii maimua poate lua banana, rezolvarea datnueste total satisfctoare, deoarece programul are o infinitate de soluii. La cererearepetata unei soluii, se va afia ntotdeauna valoarea:

X = la_fereastra

Considernd din nou modelul spaiului strilor, se observ c n acest cazeste vorba de un spaiu de cutare de tip graf, n care o aceeai stare poate fidescoperit i redescoperit la infinit, prin parcurgerea unui ciclu de tranziii destri n acest graf. Astfel de cazuri trebuie tratate prin introducerea unor liste destri parcurse, care smpiedice parcurgerea repetata unor stri deja parcurse.

Pericolul de apariie a unor cicluri infinite, datoritparcurgerii unui spaiude cutare graf nu este specific limbajului Prolog i poate s apar n oriceimplementare, n aceste cazuri. Ceea ce este neobinuit, n raport cu alte limbaje

este faptul c, semnificaia declarativ a programului este corect, indiferent deordonarea clauzelor, n timp ce programul este procedural incorect, avndcomportri diferite n funcie de aceast ordonare. Rezolvarea problemei ar maitrebui completatcu afiarea strilor i a micrilor executate de maimu, pentru aajunge n starea final, n care ea poate apuca banana. Modaliti de eliminare aciclurilor infinite, de tipul celor ce apar n aceast problem, vor fi discutate incapitolele urmtoare.

1.5 Exerciii propuse

EP1. Exprimai in Prolog urmatoarele fapte:

1) susan are un cal;

2) rex mannca carne;

3) aurul este pretios;

4) maina este un Mercedes albastru cu capacitatea de cinci cltori.

EP2. Se considerurmtoarele fapte, exprimate n Prolog:

masina(mercedes, albastru, 5).masina(chrysler, rosu, 4).masina(ford, gri, 8).

masina(datsun, rosu, 5).

Sse exprime urmtoarele ntrebri n Prolog:

1) Ce tipuri de maini au cinci locuri pentru cltori?

2) Ce maini sunt roii?


36/36

36 CAPITOLUL 1

3) Sse transcrie urmtoarea reguln Prolog:

X este o masinmare dacpoate transporta cel putin 5 cltori.

EP3. Se do bazde fapte de forma:

parinte(Parinte, Copil).barbat(Persoana).femeie(Persoana).

Se cere:

1) Sse introduccteva fapte de aceastform.

2) Sse scrie regulile care definesc urmatoarele relaii de rudenie:

tata(Tata, Copil).mama(Mama, Copil).

fiu(Parinte, Copil).fiica(Parinte, Copil).bunic(Bunic, Copil).bunica(Bunica, Copil).nepot(Bunic, Copil).nepoata(Bunic, Copil).

3) Sse punurmatoarele ntrebri:

Cine este parintele lui Dan?

Cine este fiu?

Cine este bunic?

Cine este fiu si tat?

EP4. S se descrie principalele operatii logice n Prolog: not, or, and, xor, nor,nand. Pentru aceasta se considerfaptele

op_not(Variabila, Rezultat) siop_or(Variabila1,Variabila2, Rezultat).

Sse scrie:

1) faptele necesare descrierii lui op_notsi op_or;

2) regulile necesare construciei celorlali operatori pe baza lui op_notsi op_or. Se cer reguli pentru:

op_and(Var1, Var2, Rezultat).op_xor(Var1, Var2, Rezultat).op_nor(Var1, Var2, Rezultat).op_nand(Var1, Var2, Rezultat).

cap 1 elem baza prolog fn

Documents