1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title>Prolog: negacija in rez</title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<link rel="stylesheet" type="text/css" href="../../style.css" />
</head>
<body>
<h1>Prolog: negacija in rez</h1>
<p>
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.
</p>
<h2>Rez (<code>!</code>)</h2>
<p>
Začnimo z rezom, saj ga bomo kasneje potrebovali za definicijo negacije. Rez v
prologu imenujemo posebej cilj, ki ga označimo s klicajem (<code>!</code>). Ta
cilj vedno uspe (v tem smislu je enak kot <code>true</code>), 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.
</p>
<figure>
<a href="famrel.svg" target="_blank">
<img src="famrel.svg" />
</a>
<figcaption>Graf (gozd) družinskih relacij</figcaption>
</figure>
<pre>
?- parent(thomas, X).
X = william ;
X = sally ;
X = jeffrey ;
no.
</pre>
<p>
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.
</p>
<pre>
?- parent(thomas, X), parent(X, Y).
X = william, Y = vanessa ;
X = william, Y = patricia ;
X = sally, Y = andrew ;
X = sally, Y = melanie ;
no.
</pre>
<p>
To vprašanje našteje vse vnuke; kar poskusi. No, saj si sprogramiral to v prvem
sklopu. Vseh vnukov je… štirje so!
</p>
<p>
Kaj pa tole vprašanje?
</p>
<pre>
?- parent(thomas, X), parent(X, Y), !.
X = william, Y = vanessa ;
no.
</pre>
<p>
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
<code>X</code> in <code>Y</code> ter ni več dovolil drugih rešitev, čeprav smo
videli, da obstajajo. To je navsezadnje njegova naloga.
</p>
<p>
Še bolj zanimiv/poučen primer:
</p>
<pre>
?- parent(thomas, X), !, parent(X, Y).
X = william, Y = vanessa ;
X = william, Y = patricia ;
no.
</pre>
<p>
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 <code>parent(thomas, X)</code> in je zato zamrznil rešitev
samo za spremenljivko <code>X</code>. Cilj <code>parent(X, Y)</code>, ki je
sedaj v resnici <code>parent(william, Y)</code> se izvaja normalno, v smislu, da
se generirajo (na zahtevo) vse možne rešitve za <code>Y</code>.
</p>
<h2>Uporaba reza</h2>
<p>
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 :)
</p>
<p>
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.
</p>
<p>
Glavna uporaba reza pa je pri definiciji negacije.
</p>
<h2>Negacija v prologu</h2>
<p>
Negacija je v prologu definirana takole: poskusim dokazati, da velja cilj
(predikat) <code>P</code>. Če mi to ne uspe, potem rečem, da velja ne
<code>P</code>. Ali s primerom:
</p>
<pre>
?- parent(jeffrey, X).
no.
</pre>
<p>
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!
</p>
<p>
Natančna definicija je naslednja:
</p>
<pre>
not(P) :-
P, !, fail
;
true.
</pre>
<p>
Kot vidiš, smo v tej definiciji uporabili rez. Preberimo logično: če velja, da
je uspel cilj <code>P</code>, potem to rešitev zamrznemo (rez!) in rečemo „no“
– za to poskrbi cilj <code>fail</code>, ki nikoli ne uspe.
</p>
<p>
Do cilja true zaradi reza lahko pridemo samo, če <code>P</code> ne uspe in ne
naletimo na klicaj. Kar poskusi.
</p>
<p>
Še komentar o sintaksi: za negacijo lahko uporabljamo predikat <code>not</code>
(odvisno od verzije prologa), običajno pa preprosto uporabljamo operator
<code>\+</code>. Spodnje vprašanje pomeni: „ali Jeffrey ni starš?“
</p>
<pre>
?- \+ parent(jeffrey, X).
yes.
</pre>
<p>
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.
</p>
<h2>Primer uporabe</h2>
<p>
Sprogramirajmo predikat <code>count(X, L, N)</code>, ki prešteje koliko
elementov <code>X</code> se skriva v seznamu <code>L</code> in rezultat vrne v
<code>N</code>.
</p>
<p>
Prva, naivna implementacija je naslednja. Razmišljajmo rekurzivno. V praznem
seznamu je točno nič elementov <code>X</code>. Sicer pa imamo vsaj en element,
to je glava seznama. Pa predpostavimo, da rekurzija lepo prešteje, koliko
<code>X</code>-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 <code>X</code>, ali
pa ni. V prvem primeru rezultatu rekurzije prištejemo ena, v drugem pa ne.
</p>
<pre>
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).
</pre>
<p>
Videti je v redu, tudi logično se bere nekako smiselno. Pa poglejmo, kaj pravi
prolog.
</p>
<pre>
?- count(a, [a,b,c,a,a,b,b,a,d], N).
N = 4.
</pre>
<p>
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.
</p>
<pre>
?- count(a, [a,b,c,a,a,b,b,a,d], N).
N = 4 ;
N = 3 ;
N = 3 ;
N = 2 ;
…
</pre>
<p>
Hmmm. Kako, kako pa to dobimo? Hja, pomislimo. Ena možnost je, da glava enaka
<code>X</code>, druga pa, da ni enaka <code>X</code>. A tega nikoli nismo zares
povedali prologu. Druga veja je <code>count(X, [_|T], NT)</code>, ki pa pove, da
je prvi element (glava) seznama lahko karkoli. Karkoli! Torej tudi
<code>X</code>. 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.
</p>
<pre>
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).
</pre>
<p>
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.
</p>
<p>
Druga možnost je uporaba negacije. V drugi veji negiramo cilj, da mora glava
biti enaka <code>X</code>.
</p>
<pre>
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).
</pre>
<p>
Seveda bi negiran cilj „<code>X</code> se ne more prilagoditi H“ lahko zapisali
z operatorjem <code>\=</code>, a smo za demonstracijo uporabili negacijo.
</p>
<h2>Za konec</h2>
<p>
Č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:
</p>
<pre>
?- \+ female(X), parent(thomas, X).
no.
</pre>
<p>
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: <code>X</code> 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 „<code>X</code> je ženska“? Lahko, v bazi je
veliko žensk, izberem poljubno za <code>X</code>. Zato pa je negiran cilj
seveda… napačen! Torej ne! Če bi stvari obrnili, tako da bi negiran cilj
preverjali za konkretno vrednost za <code>X</code>, bi bilo vse, kot smo si
zamislili. Takole:
</p>
<pre>
?- parent(thomas, X), \+ female(X).
X = william ;
X = jeffrey.
</pre>
<p>
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.
</p>
</body>
</html>
|
