lab3

IA Laborator 3 Scopul: Definirea ideilor de unificare, backtracking si recursivitate in Prolog. Controlul backtracking-ului: predicatele cut si fail. Negatia in Prolog.

PARTEA 1: SUPORT LABORATOR

Procesul de unificare constă în asocierea (matching) unei întrebări (goal) cu o anumită clauză, cu scopul de a găsi o solutie la întrebare. Dar pentru un set de clauze date si pentru o singură întrebare pot exista mai multe clauze care se pot asocia respectivei întrebări; deci se pot găsi mai multe solutii pentru aceeasi întrebare. Căutarea solutiilor alternative este posibilă datorită procesului de backtracking.

1. Unificarea

Unificarea se defineste ca fiind procesul de asociere între o întrebare si o clauză. Asocierea (matching)

Termenul de asociere se poate folosi cu diverse semnificatii, de exemplu : • asocierea unei întrebări cu o clauză

• asocierea unei variabile cu o constantă

• asocierea a două variabile, etc. În general, există 4 cazuri distincte de asociere, considerând nivelul cel mai de jos al acestui proces:

(1) Structurile identice se asociază evident între ele. Astfel, având o clauză (un fapt) de forma : părinte(mircea, ioana). (f) si o întrebare : părinte(mircea, ioana) (g)

evident structurile clauzei si a întrebării sunt identice. În consecintă, se asociază :

- predicatul din întrebarea (g) cu predicatul din clauza (f) -axioma - primul argument din întrebarea (g) cu primul argument din clauza (f) - al doilea argument din întrebarea (g) cu al doilea argument din clauza (f)

Ca urmare, se poate spune că întrebarea (g) se asociază cu clauza (f), mai exact (g) se unifică cu (f).

IA 2010 – Laborator 3

2

(2) O asociere se poate face si când apar una sau mai multe variabile libere.

Fie clauza (fapt) : părinte (mircea, ioana). (f) si întrebarea : părinte(mircea, X). (g)

care se traduce prin : ''Al cui părinte este Mircea?'' În cadrul procesului de asociere (matching) dintre (g) si (f), are loc :

- asocierea între predicatele întrebării (g) si a clauzei (f) - asocierea între primul argument din întrebare si clauza (f) - asocierea între variabila X din întrebare si argumentul ''ioana'' din clauză; aceasta este posibilă doar dacă variabila X este liberă, iar în urma procesului de asociere, variabila X se leagă de valoarea ''ioana''.

Nota: Dacă în momentul în care se încearcă asocierea, variabila X ar fi ''legată'', asocierea reuseste doar dacă X ar fi legată de valoarea ''ioana''. Această situatie este de fapt o variantă a cazului (1). Variabilele rămân ''legate'' până în momentul obtinerii unei solutii pentru acea instantiere a lor, după care devin ''libere'' si, dacă este cazul, se caută alte solutii. Astfel, singura posibilitate ca o variabilă dintr-o întrebare să fie ''legată'' în momentul încercării unei asocieri este ca întrebarea să fie compusă, să implice mai multi pasi; variabila poate deveni ''legată'' într-un pas anterior.

Exemplu:

părinte(mircea, X) and părinte(X, anca).

adică : ''Găseste pe cineva care este copilul lui Mircea si este părintele Ancai.'' Întrebarea este compusă de fapt din două sub-întrebări, si întotdeauna când se ajunge la a doua subîntrebare, variabila X este ''legată'' de o valoare. Prima sub-întrebare se asociază conform cazului (2), a doua subîntrebare conform cazului (1).

(3) Două variabile libere se asociază între ele.

Fie clauzele : tata (mircea, ioana). (f)

părinte(mircea, X) :- tata(mircea, X). (r)

si întrebarea : părinte (mircea, Y) (g)

Procesul de obtinere a solutiilor la întrebarea dată este următorul: (3.1.) Se unifică întrebarea (g) cu capul regulii (r) astfel :

- se asociază predicatele ''părinte'' pentru (g) si (r)

- se asociază primul argument (care are valoarea ''mircea'') din (g) cu cel din (r).

- se asociază variabila liberă Y din (g) cu variabila liberă X din (r); ca urmare cele două


3

variabile se leagă între ele, procesul decurge în continuare tratandu-le ca o singură variabilă. Când una dintre ele se leagă de o valoare, automat si cealaltă se leagă de aceeasi valoare. Când se face o asemenea asociere, variabilele devin ''variabile libere comune'' (free sharing variables).

(3.2.) După realizarea unificării între întrebarea (g) si capul regulii (r), noua întrebare pentru care se caută una sau mai multe solutii este : tata(mircea, X) (g1)

obtinută din corpul regulii (r).

(3.3.) Noua întrebare (g1) se unifică cu clauza (f), moment în care, conform cazului (3.2.), variabila X devine ''legată'' de valoarea ''ioana''. Variabila X fiind comună cu variabila Y, rezultă că si Y se leagă de aceeasi valoare ''ioana''.

(4) O variabilă anonimă (''_'') se asociază întotdeauna cu orice.

Fie clauzele : tata (mircea, ioana). (f1)

tata (sandu, ana). (f2)

si întrebarea : tata (X, _) (g)

tradusă astfel : ''Cine este tată ?'', fără a se cere si cine este copilul. (4.1.) În primul rând se încearcă unificarea întrebării (g) cu clauza (f1):

- se asociază predicatele ''tata'' pentru (g) si (a1).

- se asociază variabila liberă X din (g) cu valoarea ''mircea'' din (a1); variabila X devine ''legată'' de valoarea ''mircea'' - variabila anonimă din (g) se asociază cu orice ar fi pe pozitia argumentului doi din (a1).

(4.2.) Se returnează o solutie X = mircea. (4.3.) Se revine la clauza (f2), unde întrebarea (g) încearcă o nouă unificare; în prealabil variabila X a devenit ''liberă''. De data aceasta X se ''leagă'' de valoarea ''sanda'' , iar variabila anonimă din (g) se asociază cu argumentul ''ana'' din (f2).

(4.4.) Se returnează a doua solutie X = sandu.

Nota: In cadrul procesului de unificare a 2 termeni se mai foloseste termenul de ''instantiere'' în loc de ''legare'' a unei variabile de o valoare. Astfel, în exemplul de mai sus se poate spune că variabila X se instantiază cu valoarea ''mircea'', apoi cu valoarea ''sandu''.

2. Backtracking

Este o metodă folosită de Visual Prolog pentru obtinerea unei solutii (eventual mai multe solutii) pentru o anumită problemă. Din momentul în care sistemul Visual Prolog începe căutarea unei solutii pentru o


4

întrebare dată, se poate ajunge în situatia de a decide între două sau mai multe posibile căi pe care să se continue căutarea; în acest caz se fixează un indicator pentru acest punct de ramificare (punct de

backtracking) si se selectează prima cale pentru căutare. Dacă se termină căutarea pe această variantă, se revine la ''punctul de backtracking'' si se reia căutarea unei solutii pe următoarea cale disponibilă. În continuare, se va folosi si notiunea de sub-întrebare (sub-scop) pentru a exprima mai exact faptul că o întrebare (scop) poate fi compusă din mai multe sub-întrebări. Cele patru principii de bază ale procesului de backtracking sunt: (1) Sub-întrebările trebuie să fie satisfăcute (rezolvate) în ordinea în care apar.

(2) Clauzele sunt testate în ordinea în care apar în program (de la începutul la sfîrsitul

programului).

(3) Când o sub-întrebare se unifică cu capul unei reguli, corpul acelei reguli este cel care urmează

să fie satisfăcut (rezolvat). Deci corpul regulii constituie un nou set de sub-întrebări (sub-scopuri)

ce trebuie rezolvate.

(4) O întrebare (scop) este satisfăcută când se găseste câte o axiomă pentru procesul de unificare

cu fiecare sub-întrebare pozitionată la extremitătile arborelui de sub-întrebări.

Algoritmul de căutare a solutiilor

Astfel, pentru a rezolva o sub-întrebare oarecare, sistemul Visual Prolog începe căutarea cu prima clauză din setul de clauze care definesc predicatul ce apare în sub-întrebare. Pot exista două situatii distincte : (1) Să se realizeze o unificare între sub-întrebare si una din clauze, caz în care :

(a) - dacă mai există o altă clauză care ar putea să se unifice cu aceeasi sub-întrebare, sistemul PROLOG fixează un pointer (indicator, punct de backtracking) la următoarea clauză, după cea pentru care s-a reusit unificarea. (b) - toate variabilele ''libere'' din sub-întrebare, care se asociază cu valori din clauză devin variabile ''legate'' de valorile corespunzătoare. (c) - dacă clauza cu care s-a reusit unificarea sub-întrebării este capul unei reguli, urmează evaluarea corpului acelei reguli. Termenii ce formează corpul devin sub-întrebări care trebuie satisfăcute în ordinea în care apar, pentru a putea spune că apelul la acea clauză a reusit.

(2) Să nu se găsească nici o clauză care să se unifice cu sub-întrebarea dată. Sistemul PROLOG revine la ultimul pointer de backtracking, eliberează de valori toate variabilele care au fost ''legate'' după momentul pozitionării acelui indicator de backtracking, apoi încearcă să resatisfacă subîntrebarea ce era activă în acel punct.


5

Exemplu:

PREDICATES

nondeterm place(symbol,symbol)

gust(symbol,symbol)

nondeterm mancare(symbol)

CLAUSES

place(paul,X):-mancare(X),gust(X,bun).

gust(pizza,bun).

gust(mere_verzi,rau).

mancare(mere_verzi).

mancare(pizza).

Pentru a explicita mai bine ceea ce înseamnă tehnica backtracking se va testa acest program cu următorul goal:

place(paul, Ce).

Când Visual Prolog începe satisfacerea unui obiectiv, începe căutarea unei posibile unificări începând

de la începutul programului.

O primă potrivire se va găsi cu prima clauză din program şi varibila Ce se va unifica cu variabila

X. Această potrivire cu antetul regulii va determina ca Prolog să încerce să satisfacă şi corpul regulii. Pentru aceasta va fi apelat primul subobiectiv al acestei reguli şi anume: mancare(X).

Când se face un apel, de asemenea Prolog va începe căutarea de la început spre sfârşit.

Prin încercarea satisfacerii primului obiectiv, Visual Prolog va începe de sus în jos încercând o

potrivire cu fiecare fapt sau antet al unei reguli. Se va lega astfel variabila liberă X cu mere_verzi. Deoarece mai există şi alte fapte în continuare şi se mai pot găsi şi alte soluŃii, Prolog va pune un punct de întrerupere (backtrack point) chiar aici, după faptul mancare(mere_verzi). Acest punct va reŃine poziŃia în care se va întoarce Prolog pentru a căuta alte soluŃii dacă mai sunt.

Dacă un apel a găsit o potrivire, el se va încheia cu success, şi se va încerca în continuare

satisfacerea următorului subobiectiv.

În cazul de faŃă următorul subobiectiv va fi gust(mere_verzi,bun) Nu se va găsi în program nici un fapt care să conducă la satisfacerea acestui subobiectiv, deci,

prolog automat va reveni la punctual de întrerupere lăsat prin mecanismul backtracking. În cazul de faŃă, punctual de întrerupere a fost pus la faptul mancare(mere_verzi)

Odată ce o variabilă a fost legată, într-un program Prolog, singura modalitate de a deveni liberă

este prin backtracking.


6

La revenire la un punct de întrerupere, prolog va elibera toate variabilele legate după acest punct şi va căuta o altă soluŃie pentru apelul iniŃial. Acest apel, în cazul de faŃă a fost mancare(X), aşa că variabila X din acest moment nu va mai fi legată cu mere_verzi, ea devenind o variabilă liberă. Se va găsi în continuare o nouă potrivire şi variabila X va fi legată cu pizza.

În continuare, prolog va încerca din nou satisfacerea următorului obiectiv din apelul iniŃial, cu noua variabilă legată X. Acest nou subobiectiv este în cazul de faŃă gust(pizza, bun), pentru satisfacerea căruia din nou va începe căutarea de la început. De data aceasta se va găsi o potrivire şi obiectivul se va încheia cu success. Deoarece variabila Ce din obiectivul iniŃial este unificată cu variabila X din regula place, şi variabila X este legată cu valoarea pizza, şi variabila Ce va fi legată cu valoarea pizza şi Prolog va afişa soluŃia

Ce=pizza

1 Solution

3. Controlul procesului de backtracking: cut si fail

După cum am arătat mai înainte pentru satisfacerea scopului în PROLOG se utilizează tehnica backtracking. Procesul de resatisfacere prin backtracking poate fi oprit de programator cu ajutorul predicatului cut, simbolizat prin caracterul !. Cut este un predicat fără argumente. În poziŃia în care apare interzice revenirea, blocând astfel căutarea de noi soluŃii. Semnul “!” aşezat între clauzele pi şi pi+1 ale scopului blochează resatisfacerea clauzei pi. Un efect asemănător se obŃine utilizând tăietura (semnul “!”) în corpul unei reguli, deoarece pentru satisfacerea corpului unei reguli PROLOG utilizează backtracking. Fie urmatoarele clauze:.

(1) debitor(popescu, ionescu).

(2) debitor(georgescu, ionescu).

(3) creditor(cristescu, popescu).

(4) creditor(vasilescu, ionescu).

(5) are_obligatii(X, Y) :- debitor(Y, X).

(6) are_obligatii(X, Y) :- creditor(X, Y).

Să presupunem că scopul programului este are_obligatii(X, Y). Reprezentăm arborele de căutare corespunzător scopului are_obligatii(X, Y). SăgeŃile indică modul în care se avansează şi respectiv, se revine la puncte deja explorate, în căutarea tuturor soluŃiilor posibile.


7

Răspunsul la interogare este:

X = ionescu, Y = popescu

X = ionescu, Y = georgescu

X =cristescu, Y = popescu

X = vasilescu , Y = ionescu

4 Solutions

Modificăm cele două reguli anterioare, introducând tăietura

(5) are_obligatii(X, Y) :- debitor(Y, X), !.

(6) are_obligatii(X, Y) :- creditor(X, Y), !.

şi analizăm efectul său asupra modului în care se va parcurge arborele de căutare.

După parcurgerea nodurilor 1 şi 3, se întâlneşte tăietura care blochează revenirea. Rezultatul


8

obŃinut este X = ionescu, Y = popescu

1 Solution

Un scop eşuează în Prolog dacă toate încercările posibile de a-l satisface prin revenire pe urme (backtracking) eşuează. Eşuarea poate fi exprimată în PROLOG printr-un predicat predefinit, care are valoarea de adevăr “fals”, şi anume predicatul fail. Predicatul fail este utilizat pentru forŃarea revenirii pe urme. Următoarele exemple vor pune în evidenŃă forŃarea backtrackingului cu ajutorul acestui predicat. Pentru a înŃelege exemplele este necesar să precizăm semnificaŃia predicatelor “nl“ şi “write”. Predicatul “write” este un predicat predefinit a cărui valoare logică este “adevărat” şi care nu se resatisface niciodată. Clauza “write(X)” determină afişarea pe ecran a valorii legate de variabila X. Predicatul “nl” este un predicat predefinit care determină trecerea la linie nouă.

/* Program 1 */

domains

nume = symbol

predicates

client(nume)

afis_clienti

clauses

client(popescu).

client(ionescu).

client(vasilecu).

afis_clienti : - client(X), write(X), nl.

/* Program 2 */

domains

nume = symbol

predicates

client(nume)

afis_clienti

clauses

client(popescu).

client(ionescu).

client(vasilecu).

afis_clienti : - client(X), write(X), nl, fail.

La interogarea: afis_clienti, primul program va răspunde

popescu

Yes

în timp ce al doilea program va răspunde popescu


9

ionescu

vasilescu

No

În primul program, pentru scopului afis_clienti se leagă variabila X la primul obiect care satisface clauza client(X), după care se afişează pe ecran obiectul respectiv (popescu). Deoarece predicatul write nu se resatisface nu se mai încearcă nici resatisfacerea scopului. Utilizarea, în cel de-al doilea program al predicatului fail în corpul clauzei determină dezlegarea variabilei X şi legarea ei la următorul obiect care face clauza client(X) adevărată. Mesajul “no” de la sfârşit este determinat de faptul că scopul eşuează. Putem evita obŃinerea acestui mesaj modificând programul în felul următor:

/* Program 3 */

domains

nume = symbol

predicates

client(nume)

afis_clienti

clauses

client(popescu).

client(ionescu).

client(vasilecu).

afis_clienti : - client(X), write(X), nl, fail.

afis_clenti.

Răspunsul la aceeaşi interogare este:

popescu

ionescu

vasilescu

Yes

4. Negatia in Prolog

Cu ajutorul predicatului fail se poate programa în PROLOG negaŃia. Să presupunem că vrem să exprimăm următoarea regulă: “Dacă cererea pentru un produs creşte şi producŃia nu creşte, atunci preŃul produsului creşte”. Aceasta se poate realiza cu programul următor:

domains

produs=symbol

predicates

creste_cerere(produs)

creste_productie(produs)

np(produs)


10

creste_pret(produs)

clauses

creste_cerere(mat_de_constructie).

creste_cerere(confectii).

creste_productie(confectii).

np(X):- creste_productie(X),!,fail. /*1*/

np(_). /*2*/

creste_pret(X):-creste_cerere(X),np(X).

Predicatul np(X) definit în acest program este satisfăcut dacă şi numai dacă preŃul produsului X nu creşte. Folosim tăietura , !, pentru a evita activarea clauzei notate cu 2. Dacă pentru un anumit produs producŃia creşte, tăietura va împiedica PROLOG să revină pe urme la regula 2, iar predicatul fail va duce la eşuarea capului regulii 1, deci va rezulta că pentru acel produs anume preŃul nu creşte. Să considerăm un produs pentru care se menŃionează în baza de fapte că cererea creşte. Dacă pentru acel produs nu se menŃionează în baza de fapte că producŃia creşte, atunci regula 1 va eşua, iar PROLOG va reveni pe urme, activând regula 2, al cărui cap va fi satisfăcut. Iată şi răspunsurile la câteva interogări: creste_pret(confectii)

No

creste_pret(mat_de_constructii)

Yes

creste_pret(X)

X = mat_de_constructii

1 Solution

O încercare diferită de exprima negaŃia în Prolog o constituie predicatul special not. NegaŃia predicatului p(arg1, arg2,…, argn) se exprimă prin not(p(arg1, arg2,…, argn)). Predicatul not(p(arg1,

arg2,…, argn)) are valoarea logică “adevărat” dacă predicatul p(arg1, arg2,…, argn) nu se poate satisface. În caz contrar, are valoarea fals. Rescriem programul de mai sus folosind predicatul not.

domains

produs=symbol

predicates

creste_cerere(produs)

creste_productie(produs)

creste_pret(produs)

clauses

creste_cerere(mat_de_constructie).

creste_cerere(confectii).

creste_productie(confectii).


11

creste_pret(X):-creste_cerere(X), not(creste_productie(X)).

Să considerăm un alt exemplu şi să analizăm răspunsurile sistemului PROLOG: predicates

patrat_perfect(integer)

clauses

patrat_perfect(4).

patrat_perfect(25).

Goal: patrat_perfect(16)

No

Goal: not(patrat_perfect(9))

Yes

Răspunsul “no” la prima interogare nu trebuie interpretat ca “16 nu este pătrat perfect”. Ceea ce se înŃelege de fapt prin răspunsul “no” este că, după ce s-au verificat toate clauzele acestui program, sistemul PROLOG nu poate considera 16 pătrat perfect. Răspunsul la a doua interogare este “yes” deoarece clauza patrat_perfect(9) eşuează neputând fi dedusă din cauzele programului. Acest mecanism de “gândire” al sistemului PROLOG se bazează pe ipoteza lumii închise (Closed World

Assumption) : Dacă o afirmaŃie A nu este exprimată nici direct, nici indirect într-un program P, ceea

ce înseamnă că ea nu este nici fapt şi nici concluzie bazată pe datele unui program P, atunci acceptăm

că este valabilă negaŃia sa.

PARTEA a-II-a: EXERCITII

1. Exprimati in Prolog urmatoarele fapte:

a) susan are un cal; b) rex mănâncă carne; c) aurul este preŃios; d) maşina este un mercedes albastru cu capacitatea de cinci călători

2. Traduceti în limbaj natural următoarea întrebare Visual Prolog si precizati răspunsul posibil: părinte(vali, X), părinte(X, Y), părinte(Y, roco).

3. Doi copii pot juca un meci într-un turneu de tenis dacă au aceeaşi vârstă. Fie următorii copii şi vârstele lor:

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

Definiti un predicat din care rezulta toate perechile de copii care pot juca un meci într-un turneu de tenis.


12

4. Scrieti un program care să îi găseasca Anei un partener la bal. Ea doreşte sa mearga cu un bărbat care este nefumător sau vegetarian. Pentru aceasta dispunem de o bază de date cu informaŃii despre câŃiva bărbaŃii:

barbat(gelu). barbat(bogdan). barbat(toma). fumator(toma). fumator(dan).

vegetarian(gelu). 4. Se dau următoarele enunŃuri:

1) Oricine poate citi este literat. 2) Delfinii nu sunt literaŃi. 3) AnumiŃi delfini sunt inteligenŃi.

Să se demonstreze în Prolog că: “Există fiinŃe inteligente care nu pot citi”.

lab3

Documents