From 732b8f42029eced5e53debbff367131c2ea366ee Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Sun, 3 Apr 2016 18:11:08 +0200 Subject: Prolog: add introduction for the sets group and make it visible --- prolog/problems/sets/intro_sl.html | 281 +++++++++++++++++++++++++++++++++++++ 1 file changed, 281 insertions(+) create mode 100644 prolog/problems/sets/intro_sl.html (limited to 'prolog/problems/sets/intro_sl.html') diff --git a/prolog/problems/sets/intro_sl.html b/prolog/problems/sets/intro_sl.html new file mode 100644 index 0000000..3763628 --- /dev/null +++ b/prolog/problems/sets/intro_sl.html @@ -0,0 +1,281 @@ + + + + + Prolog: negacija in rez + + + + +

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. +

+ +
+ + + +
Graf (gozd) družinskih relacij
+
+ +
+?- 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.
+
+

+Zdaj vidiš, zakaj nismo negacije uporabljali takoj od začetka. Seveda je zelo +koristna, včasih brez nje preprosto ne gre. Vendar pa je potrebno biti previden. +Če se trikov in problemov zavedaš, potem je tudi negacija povsem obvladljiva. +Seveda pa, če se da, se je je najbolje izogniti. +

+ + + -- cgit v1.2.1