Prolog: negacija in rez

Kot ste videli, smo konjunkcijo in disjunkcijo spoznali že takoj v prvem sklopu. Verjetno ste se že tedaj spraševali, kako je s tretjo, na nek način komplementarno, logično operacijo, to je negacijo. Tako je, načrtno smo zavlačevali z njeno predstavitvijo! Boste hitro videli, zakaj. No, sedaj pa je vendarle napočil čas, da ugriznemo še v to jabolko.

Rez (`!`)

Začnimo z rezom, saj ga bomo kasneje potrebovali za definicijo negacije. Rez v prologu imenujemo posebej cilj, ki ga označimo s klicajem (!). Ta cilj vedno uspe (v tem smislu je enak kot true), a ima stranski učinek. Le-ta je, da prepreči ostale možne alternative. Poglejmo to kar na primeru. Za hip si spet naložimo dejstva o družinskih drevesih iz prvega sklopa, da lahko na njih naredimo nekaj demonstracij.

?- parent(thomas, X).
X = william ;
X = sally ;
X = jeffrey ;
no.

Zgornje vprašanje smo v naravnem jeziku interpretirali kot „kdo vse je otrok od Thomasa?“ Vidimo, da ima Thomas tri otroke. Zdaj pa bomo na različne načine našteli njegove vnuke in pri tem demonstrirali delovanje reza.

?- parent(thomas, X), parent(X, Y).
X = william, Y = vanessa ;
X = william, Y = patricia ;
X = sally, Y = andrew ;
X = sally, Y = melanie ;
no.

To vprašanje našteje vse vnuke; kar poskusi. No, saj si sprogramiral to v prvem sklopu. Vseh vnukov je… štirje so!

Kaj pa tole vprašanje?

?- parent(thomas, X), parent(X, Y), !.
X = william, Y = vanessa ;
no.

Oho! Klicaj (rez) je napravil svoje. Pomislimo, kaj se je zgodilo: ko je naletel na klicaj, je prolog zamrznil trenutno (delno) rešitev – vrednosti spremenljivk X in Y ter ni več dovolil drugih rešitev, čeprav smo videli, da obstajajo. To je navsezadnje njegova naloga.

Še bolj zanimiv/poučen primer:

?- parent(thomas, X), !, parent(X, Y).
X = william, Y = vanessa ;
X = william, Y = patricia ;
no.

Klicaj smo sedaj postavili med oba cilja. In dobili smo… samo vnuka preko prvega starša, torej Williama. Seveda, prolog je naletel na klicaj po tem, ko je našel prvo rešitev za cilj parent(thomas, X) in je zato zamrznil rešitev samo za spremenljivko X. Cilj parent(X, Y), ki je sedaj v resnici parent(william, Y) se izvaja normalno, v smislu, da se generirajo (na zahtevo) vse možne rešitve za Y.

Uporaba reza

Načeloma se rezu poskušamo izogibati. Seveda pa je včasih zelo koristen za optimizacijo, ko odrežemo veje kar sami, ker vemo, da jih ne potrebujemo. Dostikrat tudi skrajša kodo – če je to res potrebno v prologu, je veliko vprašanje :)

Kot ste videli, rez poreže rešitve (od tu mu tudi ime). To seveda dostikrat vpliva na prologovo „večsmernost“, ki je običajno zaželena lastnost. Rez jo večinoma prepreči.

Glavna uporaba reza pa je pri definiciji negacije.

Negacija v prologu

Negacija je v prologu definirana takole: poskusim dokazati, da velja cilj (predikat) P. Če mi to ne uspe, potem rečem, da velja ne P. Ali s primerom:

?- parent(jeffrey, X).
no.

Ta cilj odgovarja na vprašanje „ali je Jeffrey oče?“ Kot vidimo, prolog poskuša to dokazati, a je odgovor „no“. Zato rečemo, da velja ravno obratno: „Jeffrey ni oče.“ Skratka, če velja negacija v prologu, to pomeni, da prolog ni uspel dokazati cilja, ki ga negiramo!

Natančna definicija je naslednja:

not(P) :-
    P, !, fail
    ;
    true.

Kot vidiš, smo v tej definiciji uporabili rez. Preberimo logično: če velja, da je uspel cilj P, potem to rešitev zamrznemo (rez!) in rečemo „no“ – za to poskrbi cilj fail, ki nikoli ne uspe.

Do cilja true zaradi reza lahko pridemo samo, če P ne uspe in ne naletimo na klicaj. Kar poskusi.

Še komentar o sintaksi: za negacijo lahko uporabljamo predikat not (odvisno od verzije prologa), običajno pa preprosto uporabljamo operator \+. Spodnje vprašanje pomeni: „ali Jeffrey ni starš?“

?- \+ parent(jeffrey, X).
yes.

In še nekaj: rezultat negacije je vedno odgovor da ali ne, spremenljivkam se vrednosti ne priredijo. Ne pozabi, da v bistvu cilj pod negacijo ne uspe.

Primer uporabe

Sprogramirajmo predikat count(X, L, N), ki prešteje koliko elementov X se skriva v seznamu L in rezultat vrne v N.

Prva, naivna implementacija je naslednja. Razmišljajmo rekurzivno. V praznem seznamu je točno nič elementov X. Sicer pa imamo vsaj en element, to je glava seznama. Pa predpostavimo, da rekurzija lepo prešteje, koliko X-ov se skriva v repu (ki je krajši, torej si rekurzijo lahko privoščimo). Sedaj pa imamo dve možnosti: ali je glava enaka X, ali pa ni. V prvem primeru rezultatu rekurzije prištejemo ena, v drugem pa ne.

count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
count(X, [X|T], N) :-   % prva možnost: glava je enaka X
    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
    N is NT + 1.
count(X, [_|T], NT) :-  % druga možnost: glava ni enaka X
    count(X, T, NT).

Videti je v redu, tudi logično se bere nekako smiselno. Pa poglejmo, kaj pravi prolog.

?- count(a, [a,b,c,a,a,b,b,a,d], N).
N = 4.

Ha! Deluje! No no, ne tako hitro. Nismo poskusili dobiti vseh odgovorov. Zakaj pa bi jih potrebovali, boš vprašal. Jih ne, vendar nikoli ne veš, kdaj bodo nenadoma prišli v poštev, ko bo prolog poleg štetja počel še kaj v kombinaciji. In navsezadnje, saj nočeš, da vračamo najprej pravilen rezultat, potem pa… poglejmo kaj.

?- count(a, [a,b,c,a,a,b,b,a,d], N).
N = 4 ;
N = 3 ;
N = 3 ;
N = 2 ;
…

Hmmm. Kako, kako pa to dobimo? Hja, pomislimo. Ena možnost je, da glava enaka X, druga pa, da ni enaka X. A tega nikoli nismo zares povedali prologu. Druga veja je count(X, [_|T], NT), ki pa pove, da je prvi element (glava) seznama lahko karkoli. Karkoli! Torej tudi X. Obe veji si torej nista disjunktni, relacija med njima je OR in ne XOR, kot bi si želeli. Kako bi to naredili? Ena možnost je, da z rezom preprečimo drugo vejo, kadar prva uspe. Takole.

count(X, [], 0).          % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
count(X, [X|T], N) :- !,  % prva možnost: glava je enaka X
    count(X, T, NT),      % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
    N is NT + 1.
count(X, [_|T], NT) :-    % druga možnost: glava ni enaka X
    count(X, T, NT).

Kot vidiš je v tem primeru rez spremenil logični pomen programa (XOR med vejama namesto OR). Tudi zato se ga izogibamo, ker je to lahko nevarno – težje beremo program.

Druga možnost je uporaba negacije. V drugi veji negiramo cilj, da mora glava biti enaka X.

count(X, [], 0).        % robni pogoj: v praznem seznamu se nič ne skriva, tudi X ne ;)
count(X, [X|T], N) :-   % prva možnost: glava je enaka X
    count(X, T, NT),    % Hej, rekurzija, koliko X-ov se skriva v repu? Aha, NT, hvala!
    N is NT + 1.
count(X, [H|T], NT) :-  % druga možnost: glava ni enaka X
    \+ X = H,
    count(X, T, NT).

Seveda bi negiran cilj „X se ne more prilagoditi H“ lahko zapisali z operatorjem \=, a smo za demonstracijo uporabili negacijo.

Za konec

Če se da, se tudi negacije (tako kot reza) izogibamo. Ker vsebuje rez, ima enak negativen vpliv na „večsmernost“. Seveda to vedno ne gre, zato pa jo imamo – pravim samo, da se je izogni, če se da. Kje še lahko naletiš na probleme? V kombinaciji negacije s spremenljivkami, ki še nimajo vrednosti. Poglej tale primer, ki želi odgovor na vprašanje, ali ima Thomas kakšnega sina:

?- \+ female(X), parent(thomas, X).
no.

Kako, prosim? Prologu se je zmešalo! Saj Thomas ima kar dva sina! Ima, ima, ampak poglejmo, kaj smo vprašali. Mislili smo povsem logično: X ni ženska in je otrok od Thomasa. Vse lepo in prav. Aker je negacija definirana v prologu kot neuspeh cilja pod negacijo, je prologovo sklepanje naslednje: ali lahko dokažem (zadostim) cilj „X je ženska“? Lahko, v bazi je veliko žensk, izberem poljubno za X. Zato pa je negiran cilj seveda… napačen! Torej ne! Če bi stvari obrnili, tako da bi negiran cilj preverjali za konkretno vrednost za X, bi bilo vse, kot smo si zamislili. Takole:

?- parent(thomas, X), \+ female(X).
X = william ;
X = jeffrey.