Sisteme Expert

(Deadline: 07.04.2019 23:59:59)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Laboratorul 3

Predicate care genereaza liste

In Prolog exista cateva predicate predefinite, descrise mai jos, care genereaza liste.

bagof(?Element, :Scop, ?Lista)

Va pune in Lista toate valorile lui Element (reprezentat in bagof ca variabila sau ca termen compus ce contine una sau mai multe variabile) care ideplinesc Scop. Daca in Scop exista variabile care nu se regasesc in Element, atunci pentru fiecare combinatie de valori posibile ale acestor variabile astfel incat Scop sa fie indeplinit se va calcula o Lista corespunzatoare. In cazul in care nu exista solutii ce pot fi puse in Lista, bagof returneaza no.

setof(?Element, :Scop, ?Lista)

Va pune in Lista toate valorile lui Element care ideplinesc Scop, insa Lista va fi ordonata si fara duplicate (elementele egale sunt eliminate). In cazul variabilelor libere din Scop, setof are comportament similar cu bagof.

findall(?Element, :Scop, ?Lista)

Va pune in Lista toate valorile lui Element care indeplinesc Scop. Spre deosebire de bagof, findall va pune toate solutiile in lista indiferent de variabilele libere existente in Scop, oferind astfel o singura solutie. In cazul in care nu exista solutii ce pot fi puse in Lista, findall spre deosebire de bagof se termina cu succes (returneaza yes) iar lista calculata va fi vida.

^ cuantificatorul existential

Variabila ^ predicat(...)
Este adevarat daca exista o valoare pentru variabila astfel incat predicatul sa aiba valoarea true
Se foloseste in general in parametrul al doilea al predicatelor bagof ori setof.

Exemplu simplu bagof, setof, findall

Mai jos aveti intreg programul cu toate exemplele. Sub acest cod va fi explicat fiecare exemplu(predicat) in parte continand setof, bagof, findall. Incercati sa cititi explicatiile si sa faceti interogarile pentru fiecare exemplu.

Acesta este un bagof simplu, care va pune toate solutiile lui a in lista L. Practic va puteti imagina ca bagof face interogarea a(X) cu "punct si virgula" ca sa obtina toate solutiile si acele solutii le pune in lista data in al treilea parametru. Observati interogarile:

Pentru a intelege mai usor ce s-a intamplat, sa urmarim detaliat comportamentul lui bagof, cu ajutorul lui trace.

Prima componenta a lui bagof e pe post de sablon. Practic arata forma elementelor ce vor fi puse in lista, si poate contine mai multe variabile. Aceste variabile sunt calculate de parametrul al doilea (conditia) al lui bagof. Iar in ultimul parametru (lista) se pun astfel toate solutiile de forma primului parametru cu variabilele care indeplinesc conditia din al doilea parametru. De exemplu, daca vrem ca sablonul nostru sa fie o structura (termen compus) de forma nr(X), unde X reprezinta toate valorile calculate din predicatul a: sol_a_nr(L):-bagof(nr(X),a(X),L).


Va avea ca output:

Deci observam ca lista rezultat cuprinde structuri de forma nr(X): nr(7), nr(0) etc.

La fel putem folosi si un operator pe post de sablon, pentru primul parametru. De exemplu:

Observam ca elementele sunt de forma X+1: 7+1,0+1 etc. Nu se face calculul deoarece nu s-a folosit niciun operator aritmetic pentru obtinerea rezultatului. Doar i-am impus forma X+1 prin primul parametru al lui bagof.

Sa trecem acum la findall ai carui parametri sunt exact la fel cu cei ai lui bagof. Pe acest exemplu simplu findall va da aceeasi solutie ca si bagof:

Cu outputul:

Ca si bagof, a dat lista cu toate solutiile lui a(X). Totusi exista diferente intre cele doua predicate.

O prima diferenta intre bagof si findall este ca in cazul lui bagof daca conditia nu da deloc solutii bagof esueaza(rezultatul e no). In schimb findall cand nu are solutii de pus in lista, pur si simplu calculeaza lista ca fiind vida si se termina cu succes.De exemplu, sol_a_m100 si all_m100 au aceeasi conditie (pe al doilea parametru), care va fi mereu falsa. Predicatul sol_a_m100 foloseste bagof, dar all_m100 foloseste findall:

Observam rezultatul:

Pana acum am avut doar conditii simple in al doilea parametru (doar apelul cate unui predicat). Insa putem avea teste mai complexe. In acest caz, testele se pun in paranteze pentru a fi vazute ca o unitate (altfel veti avea eroare de sintaxa):

Cu outputul:

Sa folosim acum si setof. Setof se comporta ca si bagof doar ca scoate duplicatele din solutii, si calculeaza lista ordonata crescator:

mult_sol_a(L):-setof(X,a(X),L).


Observam in output ca elementul 7 nu mai apare de 2 ori si lista e ordonata crescator:

Sa luam si un exemplu cu un sablon mai complex pentru elementele de pus in lista. Vrem ca in lista sa avem toate sumele posibile dintre elementele solutii ale lui a (putem avea si suma intre X si X).

Rezultatele vor fi:

Se observa in exemplul de mai sus ca setof a eliminat duplicatele in care elementele aveau exact aceeasi forma. Insa a ordonat dupa primul operand al expresiei.

Exemplu bagof, setof, findall, cuantificator existential - evidentiand modul de functionare al gruparii

Predicatele bagof si setof pot grupa solutiile din liste in functie de variabilele din conditie care nu se afla in primul parametru al lui bagof. Sa luam un exemplu:

Cu outputul:

In exemplul de mai sus cine sunt variabilele de grupare? G1 si G2. De ce? pentru ca sunt variabilele care se afla in conditie dar nu se afla si in primul parametru al lui bagof. Cum anume se realizeaza gruparea? Pentru fiecare set de valori posibile pentru G1 si G2 se cauta valorile pentru X astfel incat conditia b(G1,G2,X) sa fie adevarata, si aceste valori sunt puse in lista L, rezultand astfel cate o solutie pentru fiecare set de valori G1,G2. De exemplu pentru G1=a,G2=100, lista de valori posibile pentru X este [1,7].

Uneori insa nu vrem sa grupam dupa anumite variabile. De exemplu aici am vrea sa grupam doar dupa G1, nu si dupa G2. Aici intra in scena cuantificatorul existential. In parametrul 2, in fata conditiei, punem pe rand variabilele dupa care nu dorim sa grupam, urmate de ^. De exemplu:

Cu outputul:

Deci in exemplul de mai sus observam ca doar dupa G1 a grupat. De exemplu pentru G1=a valorile posibile pentru X sunt [1,5,7], indiferent de valorile lui G2.

Putem sa grupam si doar dupa G2:

Sau putem sa optam sa nu grupam nici dupa G1 si nici dupa G2 (sa avem toate solutiile posibile pentru X intr-o singura lista):

Atentie! Folosirea lui _ pentru valorile care "nu ne intereseaza" din conditie nu e un lucru prea recomandat, fiindca tot va grupa dupa variabila respectiva (chiar daca noi nu-i precizam numele, deoarece _ exact asta inseamna: o variabila anonima). tot_grupeaza(G2,L):-bagof(X,b(_,G2,X),L).


Observam in outputul de mai jos ca, desi nu mai este data si valoarea pentru G1, tot grupeaza dupa el, solutiile fiind identice cu cele date de predicatul grupare(G1,G2,L).

| ?- tot_grupeaza(G2,L).
L = [1,7,7],
G2 = 100 ? ;
L = [3,0],
G2 = 100 ? ;
L = [5],
G2 = 200 ? ;
L = [8],
G2 = 200 ? ;
no
| ?-

Si predicatul setof grupeaza, insa asa cum a fost precizat mai sus, scoate duplicatele din lista rezultat si da elementele in lista in ordine crescatoare:

Comparam prima solutie pentru setof cu prima solutie pentru bagof cu exact aceeasi conditie: | ?- grupare_doarG2(G2,L).
L = [1,3,7,0,7],
G2 = 100 ? ;

Deci fata de lista [1,3,7,0,7] observam ca al doilea 7 a disparut si lista a fost si calculata cu elementele in ordine crescatoare: [0,1,3,7].

Spre deosebire de bagof si setof, findall nu grupeaza!

De asta putem sa scriem conditia chiar folosind _

Exemplu bagof, setof, findall - folosite pentru parcurgere si prelucrare liste

Putem folosi cele trei predicate si ca sa ne simplificam munca la exercitiile cu liste, scapand de recursivitate. Pentru a realiza asta, ne vom folosi de predicatul member. Reamintim ca predicatul member apelat cu primul parametru neinstantiat si cu al doilea parametru egal cu o lista data, are ca solutii pe rand toate elementele listei:

Deci putem folosi member in cadrul conditiei. Cel mai simplu exemplu e:

Am pus _ pe ultimul parametru fiindca lista rezultat nu intereseaza in acest caz (in care voiam doar sa afisez elementele) - va fi oricum egala cu L.

Bazandu-ne pe aceeasi idee de parcurgere a listei, putem folosi setof pentru a calcula multimea elementelor listei (adica sa eliminam duplicatele):

Un alt exemplu: sa zicem ca avem o lista de structuri de forma [nr(1),nr(2),nr(7)] si vrem sa obtinem lista doar cu parametrii din structuri; in acest caz [1,2,7]

Scriind primul parametru al lui member sub forma nr(X) practic incercam sa unificam fiecre element al liste cu aceasta structura, calculandu-l astfel pe X (de exemplu, din nr(X) unificat cu nr(1) obtinem X=1 etc.)

Dar forma member(nr(X),Ls) nu doar calculeaza X ci face si testul ca elementele acceptate din din L sunt de forma nr(X). Daca un element nu e de aceasta forma, asa cum se vede in exemplul urmator, va fi sarit (adica nu va fi adaugat nimic pentru el in lista-rezultat).

Observatie: nr(1,2) nu se unifica cu nr(X) deoarece difera numarul de argumente al structurii nr.

Daca voiam ca pentru elementele de forma nr(X) doar sa eliminam numele structurii si sa ramanem cu X, iar celelalte tipuri de elemente doar sa le copiem in lista rezultat, trebuie sa schimbam conditia un pic:

Avem ori cazul cand Y e unificabil cu nr(X) (Y=nr(X)) si atunci il extragem pe X din structura. Ori cand e neunificabil (Y\=nr(X)) si atunci X-ul de pus in lista va fi chiar acel element Y:

O gresala (discutata si mai jos in sectiunea de "greseli frecvente") este sa spunem ca daca pe un caz am testat ca elementul e de forma nr(X), nu mai enevoie sa testam si pe al doilea caz conditia inversa:

elimina_nume_nr2(LS,Lrez):-bagof(X,Y^(member(Y,LS),(Y=nr(X);X=Y)),Lrez).

Dar, observam din output ca oricum va intra si pe cazul al doilea chiar daca avm o structura nr(X), si asta pentru ca dupa ce a terminat de evaluat primul caz, pur si simplu pentru a obtine toate solutiile, intra oricum si pe al doilea caz si pe altele daca sunt definite. Si daca nu e o conditie la inceput care sa-l opreasca sa intre, va face acel X=Y chiar si pentru structuri nr(_). Mai jos sunt evidentiate perechiile X, nr(X) generate pentru fiecare nr(X) din lista initiala:

Pentru a scapa totusi de testul de pe al doilea caz (fiindca practic pentru a avea programul corect testam de 2 ori daca Y o structura nr(X)) putem folosi operatorul -> sau predicatul if.

elimina_nume_nr_if(LS,Lrez):-bagof(X,Y^(member(Y,LS),(Y=nr(X) ->true; Y=X)),Lrez). | ?- elimina_nume_nr_if([nr(1),abc, 18, nr(2),nr(3), a(1,2),nr(1,2)],Lrez).
Lrez = [1,abc,18,2,3,a(1,2),nr(1,2)] ? ;
no
| ?-

Sa facem si invers acum; dintr-o lista de elemente sa obtinem lista de structuri de tip nr avand ca unic parametru chiar numarul corespunzator din lista initiala

Se observa ca elementul de pus in lista are forma nr(X), deci toate elementele din L vor fi de aceasta forma, unde X-urile vor fi pe rand toate elementele din LS (member(X,L))

Sa incercam acum sa facem o sortare a unei liste de structuri de forma a(X,Y) dupa al doilea parametru (adica dupa Y). De exemplu avem lista [a(w,2),a(b,0),a(z,5),a(q,1)] si vrem sa obtinem lista: [a(b,0),a(q,1),a(w,2),a(z,5)]. Vom presupune ca lista nu contine duplicate (altfel folosirea lui setof le va elimina). Predicatul setof foloseste compararea generala pentru sortare (<@) astfel ca daca are de comparat doi termeni compusi, intai compara numele structurilor. Daca acestea sunt egale compara parametrii de pe prima pozitie din fiecare structura. Daca si acestia sunt egali compara parametrii de pe a doua pozitie, si tot asa... Deci ca sa folosim setof in mod direct e clar ca nu putem lasa Y-ul pe a doua pozitie in structura, daca vrem sa sortam elementele dupa el. Asadar, avand in vedere ca in lista toate structurile au acelasi nume, vom scrie termenul-generator din primul parametru al lui setof sub forma a(Y,X), punand drept conditie member(a(X,Y),L).

Observam rezzultatul:

Acum ca avem elementele ordonate, doar trebuie sa rearanjam parametrii in structuri:

Si astfel obtinem rezultatul dorit:

Sa mai vedem un exemplu cu liste: vrem un predicat care primeste o lista de numere intregi si calculeaza lista continand ultima cifra a fiecarui numar.

Asa cum am generat liste pana acum, putem genera si matrici (liste de liste) cu ajutorul celor 3 predicate. Sa presupunem ca avem o lista de numere L si vrem sa calculam matricea M cu proprietatea ca M_i,j=L_i+L_j, unde M_i,j reprezinta elementul din M de pe linia i coloana j, iar L_i,L_j reprezinta elementele de pe pozitiile i si j din lista:

In exemplul de mai sus bagof-ul initial trebuie sa creeze o lista de liste (pe care o pune in M), deci primul sau parametru, L2 va trebui calculat ca lista. Cum anume? Pai cu un alt bagof. Astfel, mai intai ne luam cate un element X din lista L: member(X,L), apoi apelam un alt bagof in conditia caruia ne mai luam un element Y din L: member(Y,L) si calculam in Z suma lor: Z is X+Y, unde Z e elementul generic de pus in L2. Asta s-ar traduce prin: pentru un element X din L in L2 pun toate sumele de forma X+Y, cu Y fiind pe rand fiecare element din L.

Sa luam si un exemplu mai complex. Vrem ca folosind bagof/setof/findall sa calculam cate elemente de fiecare fel se afla intr-o lista. De exemplu, pentru lista: [a,b,b,a,c,b,b,c,a] vrem sa obtinem lista [st(a,3),st(b,4),st(c,2)]. O structura din lista respectiva are forma st(Elem, Nr_aparitii), de exemplu avem st(a,3) pentru ca a apare de 3 ori in lista initiala. Pentru a obtine acel numar de aparitii cumva trebuie sa le numaram, insa in bagof nu avem cum sa punem un contor din cauza intoarcerilor backtrackingului care ar sterge valorile calculate in contor. Astfel ne vine ideea: daca avem predicate care genereaza liste, sa calculam pentru fiecare element cate o lista a carei lungime sa fie egala cu numarul de aparitii ale elementului. De exemplu pentru a sa avem lista [a,a,a]. Cu alte cuvinte, sa grupam elementele din lista initiala in liste cu proprietatea ca elementele sunt egale (deci din lista initiala o sa avem grupul de a-uri, grupul de b-uri etc.)

Dupa cum se vede in exemplul de mai sus, am stabilit o variabila Y de grupare care sa fie egala chiar cu elementul de pus in lista, si astfel pentru fiecare element putem obtine lista de aparitii din lista initiala:

Ce urmeaza? Sa pune rezultatele din grup_elem_egale intr-o lista, calculand lungimea listelor de aparitii:

Alte exemple cu bagof, setof, findall

Sa presupunem ca avem faptele:

Vrem sa calculam echipa cu cei mai putini membri. E clar ca trebuie sa ne folosim de predicatul length pentru a calcula lungimile listelor. De asemenea, ar trebui cumva sa punem perechile de forma (Nume_echipa, Nr_membri) intr-o lista ca sa calculam minimul, deci avem de folosit bagof, setof sau findall. Insa ne aducem aminte ca setof face o ordonare crescatoare. Oare nu putem folosi asta in avantajul nostru? Sa presupunem ca structurile din lista de perechi vor avea forma st(Nume_echipa, Nr_membri). Daca aplicam setof, va ordona dupa numele echipei. De ce? pentru ca toate structurile au acelasi nume, deci va ordona dupa primul parametru. Dar noi vrem sa ordonam dupa numarul de membri... deci ce-ar fi sa scriem structura invers? st(Nr_membri, Nume_echipa). Iar acum primul element al listei generate de setof va contine chiar structura corespunzatoare echipei cu cei mai putini membri.

Acum sa presupunem ca vrem lista numelor echipelor ordonate dupa numarul de membri. Folosim lista generata de la setof-ul de la exemplul anterior pe care aplicam un bagof care sa extraga numele echipelor din structuri.

Predicatul findall cu 4 parametri

In Sicstus Prolog exista si varianta findall(?Element, :Scop, ?Lista, +FinalLista) cu 4 parametri, care, fata de findall-ul despre care am discutat pana acum, nu face decat sa adauge dupa lista calculata acel FinalLista, asa cum se vede in interogarea compusa de mai jos:

Predicatele bagof, setof, findall - greseli frecvente

O gresala care apare foarte des e folosirea lui ! in conditie. Cut opreste backtrackingul deci si generarea solutiilor in lista rezultat. De exemplu, vrem sa facem un predicat care primeste o lista L de atomi si numere si calculeaza o lista in care pentru ficare numar nr din L s-a adaugat nr² si pentru fiecare atom s-a adaugat atomul dublat. Adica pentru lista [2,a,5,bau,10] obtinem lista [4,aa,25,baubau,100]. Ne-am putea gandi aici ca avem nevoie de un if si ca putem folosi modul de scriere al lui if cu ajutorul lui cut: conditie, !, caz_da; caz_nu:

Insa vom observa ca lista calculata are doar un element, deoarece dupa evaluarea primului element face deja o intoarcere si ajunge la cut care il scoate din evaluarea conditiei, deci niciodata nu mai ajunge la ultimul element.

Poate va fi un pic mai clar de ce se intampla asa, daca urmarim trace-ul:

Am marcat mai sus iesirea din findall provocata de cut.

Totusi, cum putem rezolva?

1. Punem teste pentru fiecare caz (desi stim ca lista primita va fi doar din numere si atomi, pe o ramura testam ca elementul primit e numar, pe cealalta ca e atom): corect_findall_fara_cut(L,LS):-findall(X, (member(Y,L), (number(Y), X is Y*Y; atom(Y),atom_concat(Y,Y,X))), LS). | ?- corect_findall_fara_cut([2,a,5,bau,10],Ls).
   Ls = [4,aa,25,baubau,100] ? ;
   no
2. O alta varianta e folosind operatorul -> sau predicatul if. corect_findall_fara_cut2(L,LS):-findall(X, (member(Y,L), (number(Y)-> X is Y*Y; atom_concat(Y,Y,X))), LS). | ?- corect_findall_fara_cut2([2,a,5,bau,10],Ls).
   Ls = [4,aa,25,baubau,100] ? ;
   no
   | ?-
3. A treia varianta e sa extragem partea de calculare a lui X din conditie si sa facem un predicat auxiliar care face asta, folosind ! in acel predicat (astfel iesirea din predicat se va face in cel auxiliar si nu in conditia lui findall care ar intrerupe si procesarea celorlalte elemente: corect_findall_fara_cut3(L,LS):-findall(X, (member(Y,L), calculeaza(X,Y)), LS).
calculeaza(X,Y):-number(Y),!, X is Y*Y; atom_concat(Y,Y,X). | ?- corect_findall_fara_cut3([2,a,5,bau,10],Ls).
   Ls = [4,aa,25,baubau,100] ? ;
   no
   | ?-

O alta gresala este ca o variabila din primul parametru sa fie deja instantiata.De exemplu:

Expresiile X=1 si X=7 pot fi inlocuite cu orice alta expresie care calculeaza valoarea lui X si rezultatul va fi acelasi.

De ce se intampla asta? X e variabila pe care o foloseste bagof pentru a calcula ce pune in lista. Odata ce intra in bagof cu o valoare calculata, nu se mai poate schimba valoarea lui X. Astfel ca, daca nu exista niciun element de pus in lista care sa fie egal cu valoarea deja aflata in X, predicatul se va termina cu esec, sau, daca exista solutii posibile egale cu valoarea lui X le va pune doar pe acelea in lista (de aici si solutia [7,7]).

O alta gresala consta in necalcularea variabilelor din primul parametru. De exemplu:

Va calcula o lista, dar cu toate elementele neinstantiate

De ce avem rezultatul de mai sus? Pentru ca pentru fiecare a(Y) el pune un element X in lista L, doar ca este neinstantiat; de asta si apare in rezultat cu _Litera.