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
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title>Prolog: družinske relacije</title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<link rel="stylesheet" type="text/css" href="../../style.css" />
</head>
<body>
<h1>Prolog: družinske relacije</h1>
<p>
Prvi sklop je seveda namenjen spoznavanju prologa, obenem pa bomo obnovili naše
poznavanje družinskih relacij – tako je, ukvarjali se bomo s tetami, strici,
dedki, predniki in potomci.
</p>
<h2>Baza znanja</h2>
<p>
Načeloma je vse, kar prolog ve, zapisano v njegovi bazi znanja. Ta se tipično
naloži v sistem iz ene ali več datotek, <span class="codeq">CodeQ</span> to
bazo naloži samodejno. Baza pravzaprav ni nič drugega kot (preprost) prologov
program. Spodnja slika prikazuje bazo za ta sklop nalog.
</p>
<figure>
<a href="famrel.svg" target="_blank">
<img src="famrel.svg" />
</a>
<figcaption>Graf (gozd) družinskih relacij</figcaption>
</figure>
<p>
Baza seveda ni v grafični obliki – to je za nas, ljudi. Za prolog pa (njen
izsek) izgleda takole:
</p>
<pre>
parent(tina, william).
parent(thomas, william).
parent(thomas, sally).
parent(thomas, jeffrey).
parent(william, vanessa).
…
female(tina).
female(sally).
female(vanessa).
…
male(william).
male(thomas).
male(jeffrey).
…
</pre>
<p>
Kot vidiš, ni težko razbrati formata. In res je, to je povsem legalen prologov
program. Formalno bomo taki obliki stavka (v vsaki vrstici zgoraj je en stavek)
rekli dejstvo. V naši bazi imamo definirane tri relacije:
</p>
<ol>
<li>kdo je komu starš: relacija <code>parent/2</code>,</li>
<li>kdo je ženskega spola: relacija <code>female/1</code> in</li>
<li>kdo je moškega spola: relacija <code>male/1</code>.</li>
</ol>
<p>
Zadnji dve bi lahko definirali seveda tudi drugače, npr. kot
<code>gender(tina, female)</code>; to je povsem stvar sloga.
</p><p>
Ko je prolog bazo prebral, ve vse, kar je v njej zapisano. Obenem ve samo to,
kar je v njej zapisano, in nič drugega! Pozna torej relacije <code>parent/2</code>, <code>female/1</code>
in <code>male/1</code>. Zakaj jih pišem na tak način? Pred poševnico je ime relacije (kot
npr. ime funkcije ali procedure v kakšnem drugem jeziku), za poševnico pa
število argumentov. To je standarden zapis, ki ga boš videl v literaturi.
</p><p>
Opazil si, da se je zgoraj vsak stavek končal s piko. Pika seveda označuje
konec stavka, tako kot v slovenščini. Vsi stavki, ne glede na tip (trije tipi
so, jih bomo spoznali v kratkem) se končajo s piko! (Klicaj pomeni nekaj
drugega in tega si danes še ne želiš vedeti, verjemi mi.) Verjetno bo danes
tvoja najpogostejša napaka, da boš pozabil na piko (navada iz drugih jezikov).
Še posebej pa bodi pozoren, da stavka ne končaš s podpičjem, to pomeni nekaj
povsem drugega! 😉
</p>
<h2>Prvi koraki</h2>
<p>
Baza je torej naložena, tako da lahko začnemo z delom v prologu. Navadno to
poteka tako, da sistemu postavljamo vprašanja. Če odpreš stran s poljubno
nalogo, lahko v konzolo pišeš primere, ki so opisani v nadaljevanju.
</p><p>
Za začetek lahko prologu zastavimo preprosto vprašanje:
</p>
<pre>
?- parent(tina, william).
yes.
</pre>
<p>
To vprašanje bi se v slovenščini glasilo: je Tina starš od Williama? Prolog iz
baze znanja ve, da je Tina res starš od Williama, zato odgovori s
<code>true</code> ali <code>yes</code> (odvisno od dialekta prologa). Gotovo si
opazil tudi piko na koncu vprašanja. Tako je, čeprav gre za vprašalni tip
stavka (drugi tip, ki smo ga pravkar spoznali), je na koncu pika. Vprašaj je na
začetku, skoraj kot v španščini. 😊
</p><p>
Vprašajmo ga kaj bolj zapletenega. Na primer: kdo so Thomasovi otroci?
</p>
<pre>
?- parent(thomas, X).
X = william ;
X = sally ;
X = jeffrey ;
no.
</pre>
<p>
Aha! Kaj je tisto podpičje na koncu in zakaj je rešitev več? Podpičje v resnici
pomeni logični „ali“, po vsakem prologovem odgovoru (en odgovor, ena vrstica)
pa nas (če ve, da je rešitev več) prolog počaka, da mu lahko rečemo, da želimo
več odgovorov. S podpičjem (ali črko „n“ kot „next“) zahtevamo morebitne
dodatne rešitve, s pritiskom na tipko „Enter“ pa poizvedbo končamo.
</p>
<p>
Kot vidiš, so rešitve tri. Odgovor „no“ na koncu pa samo pomeni, da po tretji
rešitvi ni nobene rešitve več.
</p><p>
Zakaj so imena ljudi v bazi pisana z malo začetnico in zakaj je tisti <code>X</code> zgoraj
z veliko? Je to pomembno? Seveda je pomembno! Prolog avtomatsko ve, kakšnega
tipa je določen stavčni element: v splošnem vse, kar je pisano z veliko
začetnico, smatra za spremenljivke, vse z malo pa za konstante (tehnično za
atome, ampak za zdaj se ne vtikajmo v to). V večini drugih jezikov bi ljudi v
bazi verjetno pisali kot nize, jih obdali z narekovaji ali čim podobnim, v
prologu pa je to bolj preprosto. Skratka, zato so vsa imena ljudi z malo
začetnico – ne zaradi sloga, pač pa, ker tako mora biti. Sicer bi bil pomen
drugačen.
</p><p>
No, kaj pa tole vprašanje?
</p>
<pre>
?- parent(X, william).
X = tina ;
X = thomas.
</pre>
<p>
Čakaj, čakaj, kaj so tu vhodi in kaj izhodi? Tako je, kar navadi se: večinoma
so vsi argumenti lahko vhodi in izhodi hkrati. Nič ni strogo definirano. Temu
bomo pogovorno rekli, da prolog deluje v vse (več) smeri. Vprašali smo seveda,
kdo je starš od Williama.
</p><p>
Privoščimo si lahko še več.
</p>
<pre>
?- parent(X, Y).
X = tina, Y = william ;
X = thomas, Y = william ;
…
</pre>
<p>
Kako pa to ve? Seveda, saj je zapisano v bazi. Prolog nam je lepo začel
naštevati, kdo vse je komu starš. Pametno, pametno. To je navsezadnje tudi
pomen našega vprašanja.
</p><p>
Kaj pa je bila tista vejica med obema spremenljivkama zgoraj? Medtem ko
podpičje pomeni logični „ali“, vejica pomeni logični „in“. Izkoristimo to novo
znanje in vprašajmo prolog še nekaj malce bolj zapletenega, kdo vse so
<em>sinovi</em> od Thomasa? Sinovi so seveda osebe moškega spola, ki jim je
Thomas starš.
</p>
<pre>
?- parent(thomas, X), male(X).
X = william ;
X = jeffrey ;
no.
</pre>
<p>
Vejico ali podpičje lahko torej uporabimo tudi v vprašanju. Seveda! Če bi
želeli našteti npr. vse osebe v bazi, tako moške kot ženske, bi zapisali
naslednje vprašanje:
</p>
<pre>
?- male(X) ; female(X).
…
</pre>
<h2>Moj prvi program v prologu</h2>
<p>
Ne bo „Hello, world“, ker je prelahek in nesmiselen za logični jezik, kot je
prolog. Bo pa zato tisto, kar nas je večina spoznala kot svojo prvo besedo v
življenju – relacija mama. Skratka, <code>mother/2</code> bo naš ciljni
predikat, definiran takole: <code>mother(X, Y)</code> naj pomeni, da je
<code>X</code> mama od <code>Y</code>.
</p><p>
S tem, kar smo spoznali do sedaj, bi se tega lahko lotili tako, da pogledamo
osebe v bazi, kje relacija velja in te primere zapišemo, nekako takole:
</p>
<pre>
mother(tina, william).
mother(sally, andrew).
mother(sally, melanie).
mother(vanessa, susan).
…
</pre>
<p>
S tem pravzaprav ni nič narobe in bi povsem lepo delovalo. Problem je le, da je
zamudno, zelo zamudno. Seveda v nadaljevanju ne bomo popisovali relacij dejstvo
za dejstvom, ampak bomo stvari poskusili avtomatizirati oz. definirati.
Avtomatizacija je navsezadnje bistvena lastnost računalnikov.
</p><p>
Spoznali bomo še zadnji, tretji (poleg dejstva in vprašalnega stavka) tip
stavka: pravilo.
</p><p>
Kaj mora torej veljati, da je <code>X</code> mama od <code>Y</code>? Dve
stvari: da je <code>X</code> starš od <code>Y</code> in da je <code>X</code>
ženskega spola. S tem zadnjim ločimo mame od očetov. Pa zapišimo to s
prologovim pravilom:
</p>
<pre>
mother(X, Y) :-
parent(X, Y),
female(X).
</pre>
<p>
Poglejmo sestavne dele zapisanega. Piko na koncu že poznamo, ravno tako že
vemo, da vejica pomeni logični „in“. Torej je <code>X</code> starš <em>in</em>
ženska hkrati.
Kaj pa pomeni nenavadni operator <code>:-</code>, ki je tako značilen za
prolog? Ta operator nam definira pravilo, loči pa ga na dva dela: tisto pred :-
imenujemo glava stavka, tisto za njim pa telo stavka. Bere pa se zelo preprosto
takole: če logično velja telo stavka, potem iz tega sledi, da velja tudi glava
stavka.
</p><p>
Za naš primer to pomeni naslednje. <em>Če</em> velja, da je <code>X</code> starš
od <code>Y</code> in <em>hkrati</em> (vejica!) velja, da je <code>X</code>
ženskega spola, <em>potem</em> velja, da je <code>X</code> mama od
<code>Y</code>. Pravzaprav je kot pogojni stavek, kajne?
</p><p>
Še nekaj zelo pomembnega. Vsakič, ko sprogramiraš kakšno pravilo – in večina
programov bo preprosto množica enega ali več pravil – ga preberi tako, kot smo
ga prebrali zgoraj. To je najboljši način razhroščevanja v prologu! Če se ti
pravilo ob branju ne zdi smiselno, potem skoraj gotovo ni pravilno; kar zaupaj
svojemu občutku za logiko.
</p><p>
Za konec nekaj besed o slogu programiranja. Kot vidiš, sem pisal posamezne
konjunkte v svojo vrstico, celotno telo stavka pa sem tudi nekoliko zamaknil.
Vse to ni nujno potrebno, se pa tako veliko lažje bere in posledično lažje
najde morebitno napako.
</p><p>
Tako, sedaj si nared, da kaj tudi samostojno sprogramiraš. Vse relacije
(naloge) v tem sklopu so definirane tako, da je <code>X</code> v relaciji z
<code>Y</code> in ne obratno. Tako <code>father(X, Y)</code> pomeni, da je
<code>X</code> oče od <code>Y</code> in ne, da je <code>Y</code> oče od
<code>X</code>.
Naloge rešuj povsem naravno, ne obremenjuj se s tem, da morajo delovati v „vse
mogoče smeri“, kot je delovala relacija <code>parent/2</code>. Boš videl, da bo
to večinoma prišlo kar samo od sebe kot bonus. Sem se vrni, ko naletiš na prvo
rekurzijo, to je relacijo <code>ancestor/2</code>.
</p>
<!--
Tipično smo se prej ustavili že pri brother/sister zaradi potrebe po operatorju
\==, ampak sedaj to uredijo namigi. Poleg tega za konec (je to implementirano,
najbrž ni?) tam povemo kot zanimivost kaj bi bilo, če je \== prvi cilj v
telesu. -->
<h2>Prva rekurzija</h2>
<p>
Prolog načeloma ne uporablja standardnih kontrolnih struktur, kot so npr.
while ali for zanke, zamišljen je povsem drugače. Saj to si do sedaj že opazil.
Zato je rekurzija glavno orodje „avtomatizacije“ oz. nadomešča zanke.
</p><p>
Kako se je lotimo? Načeloma ima vsaka rekurzivna definicija robni primer in
splošni primer. Obojih je lahko tudi več. Tipično (to je seveda odvisno od
tvojega sloga) za vsak primer napišeš svoje pravilo.
</p><p>
Robni primer tipično predstavlja najbolj enostaven primer, ko relacija velja.
Spomnimo se matematične indukcije, rekurzija ji je zelo podobna! Tipično
najprej dokažeš, da relacija velja za n=1 (robni primer), potem pa se lotiš
težjega, splošnega primera takole: <em>predpostaviš</em>, da relacija velja za
nek n in poskusiš pokazati, da če je to res, da potem relacija velja tudi za
n+1. Pri rekurziji v splošnem primeru razmišljaš takole: kako lahko primer
preveden na enak, le kanček bolj enostaven primer? Najbolje je to videti na
primeru, definirajmo relacijo prednik, torej <code>ancestor/2</code>.
</p><p>
Začnimo takole: vprašajmo se, kdaj je nek <code>X</code> prednik od
<code>Y</code> na najbolj enostaven način? Predniki od <code>Y</code> so
njegovi starši, pa dedki in babice, pa pradedki in prababice, pa…. Naštevamo
(dodajamo predpono pra‐) lahko v nedogled. Ampak najbolj enostaven (najkrajši,
če relacije gledamo kot družinsko drevo) primer je? Starši, seveda! Robni
primer je torej:
</p>
<pre>
ancestor(X, Y) :-
parent(X, Y).
</pre>
<p>
Spomni se, da se to pravilo prebere kot: če je <code>X</code> starš od
<code>Y</code>, potem je <code>X</code> prednik od <code>Y</code>. Sliši se
smiselno, zato gremo naprej.
</p><p>
Kako bi se lotili splošnega primera? Kaj, če predpostavimo, da poznamo nekega
prednika od <code>Y</code>? Recimo mu <code>Z</code>. Potem so tudi
<code>Z</code>-jevi starši predniki od <code>Y</code>, kajne?
Znamo to izkoristititi? Seveda!
</p>
<pre>
ancestor(X, Y) :-
parent(X, Z),
ancestor(Z, Y).
</pre>
<p>
Zanimivo pravilo! Pravi naslednje: če (predpostavka!) je <code>Z</code> prednik
od <code>Y</code> in hkrati (vejica) je <code>X</code> starš od <code>Z</code>,
potem je <code>X</code> tudi prednik od <code>Y</code>. Logično, kajne?
</p><p>
Pomembno: doseg spremenljivk, kot so zgoraj <code>X</code>, <code>Y</code> in
<code>Z</code>, je omejen na trenutni stavek!
Globalnih spremeljivk ni – tehnično to ni čisto res, ampak za zdaj to ni
pomembo. 😊
Tako sta <code>X</code> in <code>Y</code> v prvem stavku (robni primer) druga
kot <code>X</code> in <code>Y</code> v drugem stavku (splošni primer).
</p><p>
Vidiš, kako smo relacijo prednik definirali s pomočjo same sebe? To lahko
storimo, če problem „zmanjšamo“. Če pogledamo družinsko drevo, je
<code>Z</code> en korak bližji prednik od <code>Y</code>, kot je to
<code>X</code>.
Tako je, ko smo postavili zahtevo <code>parent(X, Z)</code>, smo problem
„zmanjšali“ za en korak. Splošni primer se tako korak za korakom bliža robnemu
primeru, ki rekurzijo konča.
</p><p>
Brez skrbi, s precej vaje, ki jo omogačajo naloge v naslednjih sklopih, ti bo
rekurzija postala zelo domača. Spoznal jo boš do obisti, obljubim!
</p>
<h2>Slog programiranja</h2>
<p>
Kot si opazil, smo prejšni primer (prednik) rešili z dvema praviloma. Tukaj je
celotna rešitev:
</p>
<pre>
ancestor(X, Y) :-
parent(X, Y).
ancestor(X, Y) :-
parent(X, Z),
ancestor(Z, Y).
</pre>
<p>
Rešitev bi lahko zapisali tudi takole:
</p>
<pre>
ancestor(X, Y) :-
parent(X, Y)
;
parent(X, Z),
ancestor(Z, Y).
</pre>
<p>
Uporabili smo podpičje, logični „ali“. Preberimo pravilo: <em>če</em> je
<code>X</code> starš od <code>Y</code> <em>ali</em> če je <code>X</code> starš od
<code>Z</code> <em>in</em> je hkrati <code>Z</code> prednik od <code>Y</code>,
<em>potem</em> je <code>X</code> prednik od <code>Y</code>.
</p><p>
Tudi ta rešitev je pravilna. Pravzaprav boš kasneje videl, da je povsem enaka,
le zapisana je drugače. Katero verzijo uporabiš, je bolj ali manj stvar tvojega
sloga. Kasneje boš opazil, da je včasih ena verzija bolj primerna (krajša),
včasih pa druga.
</p><p>
Še dve pomembni opazki za konec:
</p>
<ul>
<li>
Spremenljivke imajo pravzaprav doseg ene veje (konjunkcije). Tako sta v drugem
primeru <code>X</code> in <code>Y</code> v cilju <code>parent(X, Y)</code>
druga kot za podpičjem.
</li>
<li>
Logični „in“ (vejica) ima prednost pred logičnim „ali“ (podpičje), točno tako,
kot si vajen iz logike. Če želiš spremeniti, kako so cilji povezani, lahko za
to seveda uporabiš navadne oklepaje – spet tako kot v logiki.
</li>
</ul>
</body>
</html>
|
