ia3

Lucrarea nr. 3

Cuprins:

1. Aspectul procedural al unui text Prolog

Un text Prolog poate fi privit din punct de vedere declarativ sau procedural. Declarativ textul Prolog ne specifica care va fi rezultatul unei intrebari. Modul in care se ajunge la un anumit raspuns este dat de intelesul procedural. Abilitatea Prologului de a rezolva detaliile procedurale permite ca programatorul sa se concentreze pe aspectul declarativ. Uneori insa, este nevoie sa fim constienti de modul in care sint satisfacute tintele. Pentru ca la o intrebare sa se raspunda pozitiv, variabilele din tinte trebuie legate astfel incit raspunsul sa fie o consecinta logica a clauzelor din program.

Pentru a intelege cum satisface Prologul tintele, sa urmarim citeva exemple simple. Consideram exemplul din lucrarea precedenta, cu relatia parent definita prin cele patru axiome:

    parent( pam, bob).
    parent( tom, bob).
    parent( tom, john).
    parent( bob, pat).

si intrebarea

?- parent(X,bob).

Procedura care incearca sa raspunda la intrebarea noastra va incerca sa potriveasca tinta "parent(X, bob)." cu una din capurile de clauze pe care le are in baza sa de cunostinte. Reuseste o prima potrivire cu axioma "parent(pam,bob).", legand variabila X cu pam. Pentru aceasta clauza nu exista o conditie ce
trebuie verificata si in consecinta ne raspunde ca

X = pam

Sa presupunem acum ca noi vrem sa aflam si alte raspunsuri posibile la intrebarea noastra. Prologul, ca sa poata relua cautarea de noi alternative din locul in care a gasit ultimul raspuns, inainte de a da raspunsul anterior, si-a notat ca dupa clauza testata mai erau si alte clauze care pot fi incercate. In acest moment se va relua procesul de la clauza "parent(tom,bob)." care va reusi in mod similar cu raspunsul anterior, marcand si in acest caz punctul de revenire de la care poate incerca cautarea de noi solutii. Raspunsul in acest caz va fi:

X = tom

Daca in continuare cerem un nou raspuns, cautarea va incepe de la clauza a treia. In acest caz nu se mai poate potrivi tinta cu nici una din clauzele ramase, raspunsul fiind:

No

Datorita faptului ca in acest caz nu mai sint alte clauze care se pot testa nu a ramas nici punct de revenire.

Prologul foloseste aceste puncte de revenire si pentru a cauta solutii noi la o tinta partiala care a fost deja satisfacuta, in cazul in care restul intrebarii nu poate fi satisfacut. Cosideram intrebarea:

?- parent(X,Y), parent(X,john).

Prima data in acest caz "parent(X,Y)" va fi potrivit cu "parent(pam,bob)". legand X=pam, Y=bob. Urmatoarea tinta partiala "parent(pam,john)" (X fiind legat deja cu pam) nu poate fi satisfacuta si in consecinta Prologul va cauta sa gaseasca o alternativa de la ultimul punct de revenire lasat. In acest moment "parent(X,Y)" va fi potrivit cu clauza "parent( tom, bob).", si deoarece "parent(tom,john)" poate fi satisfacut, vom afla raspunsul:

X = tom
Y = bob

In acest caz Prologul a lasat inca un punct de revenire pentru tinta partiala "parent(X,john)" sau mai exact pentru "parent(tom,john)". Daca se doreste un nou raspuns procesul se va relua de la ultimul punct de revenire lasat, neexistind insa alte raspunsuri la intrebarea noastra.

Sa consideram acum procesul de cautare a predecesorilor, cu ajutorul predicatului

predecessor(X1,Y1):-parent(X1,Y1).
predecessor(X2,Z2):-parent(Y2,Z2), predecessor(X2,Y2).

si intrebarea

?- predecessor(X,pat).

Prima data se incearca potrivirea tintei cu capul primei clauze. Aceasta tentativa reuseste si se inlocuieste tinta anterioara cu "parent(X,pat)",
lasand in modul obisnuit punctul de revenire pe a doua clauza. La rindul sau, subtinta reuseste prin ultima clauza parent si se obtine raspunsul

X = bob

Daca cerem un nou raspuns, se va relua cu a doua clauza predecesor. In acest caz tinta noastra va fi inlocuita cu "parent(_Y2,pat),predecessor(X,_Y2)". Din aceasta prima subtinta se potriveste cu "parent(bob,pat).", si se trece la satisfacerea tintei "predecessor(X,bob)", care va fi potrivita cu prima clauza predecessor, respectiv prima clauza parent, raspunsul fiind:

X = pam

Sa vedem care sunt in acest moment punctele de revenire. Ultima alternativa a fost la potrivirea cu "parent(pam,bob)". Inainte ca "predecessor(X,bob)" sa fie inlocuit cu "parent(X,bob)", s-a mai lasat si un punct de revenire pentru urmatoarea clauza predecessor. Inca un punct de revenire ar putea sa fie pentru primul pas in acest rationament, adica potrivirea lui "parent(_Y2,pat)" cu "parent(bob, pat)", dar aceasta este ultima clauza parent si nu ofera o noua alternativa. Cand se cauta o solutie noua backtrackingul se va reporni de la ultimul punct de alternativa lasat, trecandu-se in caz de esec la punctele de revenire imediat anterioare. Daca stiva de puncte de revenire se goleste, atunci Prologul va raspunde No la intrebarea noastra.

Alternativele generate de operatorul SAU (;) sunt tratate similar ca si cele generate de clauze multiple. De exemplu, predicatul predecesor definit anterior il putem rescrie in forma echivalenta

predecessor(X,Z):-parent(X,Z);
parent(Y,Z), predecessor(X,Y).

In mod uzual, aceste puncte de revenire le putem privi ca o stiva de pointeri spre puncte care marcheaza locul de unde trebuie reluat procesul de satisfacere a raspunsului.

Problema: Consideram predicatul a/1 definit prin

a(1).
a(2).

Specificati (fara a intreba Prologul) care vor fi raspunsurile Prologului la intrebarea

?- a(X),a(Y); a(Z).

2. Unificarea si compararea termenilor

In timpul satisfacerii unei tinte o operatie foarte frecventa este potrivirea intre doi termeni (predicat sau obiect). Doi termeni se potrivesc daca sunt identici sau variabilele din cei doi termeni se pot instantia astfel incat termenii rezultatele sa fie identice. In cazul constantelor atomice, regula de identitate este evidenta, iar in cazul structurilor regula este ca cele doua structuri trebuie sa aiba acelasi functor, aceeasi aritate, iar argumentele de pe aceeasi pozitie sa fie identice. Potrivirea a doi termeni poate fi necesara atunci cand se compara o tinta cu un cap de clauza, sau cand se cere in mod explicit unificarea sau compararea a doi termeni (obiecte) cu ajutorul unui predicat predefinit. Regulile de identitate sunt aceleasi in fiecare caz.

2.1. Predicate de unificare

Predicatul Arg1 = Arg2 reuseste prin unificarea lui Arg1 cu Arg2

Exemplu:

    ?- a(X) = a(1).
    X = 1
    Yes
    ?- a(b(1),X) = a(Y,c).
    X = c
    Y = b(1)
    Yes
    ?- X=f(Y). % argumentul lui X va denota acelasi obiect % ca si Y
    X = f(_G217)
    Y = _G217
    Yes

Predicatul Arg1 \= Arg2 reuseste daca cele doua argumente nu pot fi unificate; variabilele din componenta celor doi termeni nu-si schimba valoarea.

Exemplu:

    ?- a(X) \= a(1).
    No
    ?- a(X,Y) \= a(1).
    X = _G493
    Y = _G494
    Yes

2.2. Predicate de comparare sintactica

Aceste predicate nu incearca sa unifice sau sa inlocuiasca variabile. Ele compara argumentele sale in forma in care se afla in momentul apelului. Regulile de ordine sunt urmatoarele:

Variabila < Numar < Atom < String < Termen
Variabila veche < Variabila noua
Numerele sint comparate dupa valoare
Atomii si Stringurile sint comparate alfabetic
Termenii sint comparati in ordinea: functor, aritate, argumente

Predicatul Arg1 == Arg2 reuseste daca Arg1 si Arg2 sint identici.
Exemplu:

    ?- a(X)==a(1).
    No
    ?- a(X)==a(Y).
    No
    ?- a(X)==a(X).
    X = _G469
    Yes

Predicatul Arg1 \== Arg2 reuseste daca argumentele sint diferite.

Arg1 @< Arg2

Arg1 @=< Arg2

Arg1 @> Arg2

Arg1 @>= Arg2

Obs. Acest mod de comparare este diferit de cel descris la operatiile aritmetice.
De exemplu
    ?- abs(-2) < 5.   /* comparare aritmetica */
    Yes
    ?- abs(-2) @< 5. /* comparare sintactica */
    No

3. Structuri de control

S-a vazut in lucrarea precedenta ca predicatele, avand valori logice, pot fi combinate cu operatorii SI-SAU.

Operatorul de negare (\+) inverseaza valoarea logica a predicatului. Astfel, "\+ Goal" reuseste daca expresia predicativa Goal nu poate fi demonstrata. Un aspect
important este ca variabilele libere din Goal nu sunt legate, indiferent de succesul sau insuccesul lui Goal.
De exemplu:

    ?- \+ (X=1,X=2).
    X = _G265
    Yes
    ?- \+ (X=1,X=1).
    No

Predicatul true reuseste intotdeauna, iar fail esuaza intotdeauna.

Predicatul repeat ofera un numar infinit de puncte de reluare. Semantica acestui predicat poate fi definita prin:

repeat.
repeat:-repeat.

Predicatul Cut(notat prin !) sterge din stiva toti pointerii ce marcheaza puncte de reluare pina la CutParent. In mod uzual, CutParent este tinta care a cauzat executarea clauzei curente.
De exemplu pentru un set de clauze dat:

    t0 :- t1.
    t0.
    t1 :- a, b, !, fail; c.
    t1 :- d.
    a. a. b. b. c. d.

vom avea urmatoarele rspunsuri la intrebari:

    ?- t0.
    Yes
    ?- t1.
    No

Cut taie alternativele pentru a, b si t1 (adica latura "t1:-c"si"t1:-d").

Cu ajutorul lui Cut se pot implementa de exemplu constructii de tip if-then-else.
De exemplu:

    interv(X,1) :- X<1, !.
    interv(X,2) :- /* X>=1 */ X<2, !.
    interv(X,high). /* X>=2 */

Constructia anterioara poate fi definta si cu ajutorul constructiei IF-THEN-ELSE (->) din Prolog:

    interv(X,Y) :- X<1 -> Y=1;
                   X<2 -> Y=2;
                   Y=high.

O constructie de forma "Condition -> Then ; Else" are asigurata semantica asteptata prin faptul ca operatorul '->' are prioritate mai mare decit operatorul ';'. Intre ',' si '->' prioritar este operatorul SI. Acest punct de vedere legat de prioritate nu este insa perfect, in sensul ca, in constructia "Condition -> Then ; Else", ';' nu este chiar operatorul SAU in sensul ca el nu va oferi un punct de revenire in backtracking.

    ?- true -> X=1; X=2.
    X = 1 ;
    No /* si nu X=2 */

4. Depanarea programelor

Depanarea programelor sub SWI-Prolog se bazeaza pe conceptul de port (actiunile care se pot lua in timpul satisfacerii unei tinte). Cele mai importante porturi
sunt: 'call', 'exit', 'redo', 'fail' si 'unify'. Debuggerul este lansat fie de predicatul (comanda) trace/0 fie atunci cand se atinge un punct de 'spy'. Comanda trace are semnificatia de "trace the next query". De fiecare data se afiseaza numele portului, adancimea de recursiune si tinta de care este legata actiunea.

    ?- trace,min(3,2,X).
        Call: ( 3) min(3, 2, _G507) ?
        Unify: ( 3) min(3, 2, 3) ?
        Call: ( 4) 3 < 2 ?
        Fail: ( 4) 3 < 2 ?
        Redo: ( 3) min(3, 2, _G507) ?
        Unify: ( 3) min(3, 2, 2) ?
        Exit: ( 3) min(3, 2, 2) ?

X = 2

Un anumit tip de port poate fi vizibil sau nu. Acest fanion poate fi modificat cu predicatul "visible(Port)". Argumentul +Name face vizibil, iar -Name face invizibil portul cu numele specificat. Daca Name este 'all' atunci se refera la toate tipurile de porturi.

Un alt fanion de port se refera la interactivitatea cu utilizatorul. Daca este setat, atunci utilizatorul poate specifica o anumita optiune. Acest fanion se seteaza cu "leash(Port)", avand acelasi parametru ca si visible.

?- visible(+all), leash(-unify).

Punctele de spy se pot seta cu ajutorul predicatului "spy(Pred)", unde 'Pred' este un nume de predicat, optional putandu-se specifica si aritatea sa. Aceste puncte pot fi sterse cu "nospy(Pred)" sau "nospyall".

Optiunile cele mai importante pe care le poate alege utilizatorul (in situatia in care fanionul de leash este setat):

Creep(c, \n)
continua executia pina la urmatorul port

Abort(a)
intrerupe executia

Fail(f)
forteaza esuarea acestei tinte

Leap(l)
continua executia pina la urmatorul punct de spy

Skip(s)
continua executia pina la urmatorul port a tintei curente

Help(h)
afiseaza optiunile posibile