From 7335a43bbbb82de66132f12e504f2fbea736a45c Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Sun, 28 Feb 2016 19:32:04 +0100 Subject: Prolog: add general and family relations intro --- prolog/problems/family_relations/intro_sl.html | 378 +++++++++++++++++++++++++ 1 file changed, 378 insertions(+) create mode 100644 prolog/problems/family_relations/intro_sl.html (limited to 'prolog/problems/family_relations/intro_sl.html') diff --git a/prolog/problems/family_relations/intro_sl.html b/prolog/problems/family_relations/intro_sl.html new file mode 100644 index 0000000..0e1147b --- /dev/null +++ b/prolog/problems/family_relations/intro_sl.html @@ -0,0 +1,378 @@ + + + + + Prolog: družinske relacije + + + + + +

Prolog: družinske relacije

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

+ +

Baza znanja

+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, CodeQ to +bazo naloži samodejno. Baza pravzaprav ni nič drugega kot (preprost) prologov +program. Spodnja slika prikazuje bazo za ta sklop nalog. +

+ +

+ +

+Baza seveda ni v grafični obliki – to je za nas, ljudi. Za prolog pa (njen +izsek) izgleda takole: +

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

+ +

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

kdo je komu starš: relacija parent/2,
kdo je ženskega spola: relacija female/1 in
kdo je moškega spola: relacija male/1.

+Zadnji dve bi lahko definirali seveda tudi drugače, npr. kot +gender(tina, female); to je povsem stvar sloga. +

+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 parent/2, female/1 +in male/1. 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. +

+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! 😉 +

+ +

Prvi koraki

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

+Za začetek lahko prologu zastavimo preprosto vprašanje: +

+?- parent(tina, william).
+yes.
+

+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 +true ali yes (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. 😊 +

+Vprašajmo ga kaj bolj zapletenega. Na primer: kdo so Thomasovi otroci? +

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

+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 črno „n“ kot „next“) zahtevamo morebitne +dodatne rešitve, s pritiskom na tipko „Enter“ pa poizvedbo končamo. +

+Kot vidiš, so rešitve tri. Odgovor „no“ na koncu pa samo pomeni, da po tretji +rešitvi ni nobene rešitve več. +

+Zakaj so imena ljudi v bazi pisana z malo začetnico in zakaj je tisti X 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. +

+No, kaj pa tole vprašanje? +

+?- parent(X, william).
+X = tina ;
+X = thomas.
+

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

+Privoščimo silahko še več. +

+?- parent(X, Y).
+X = tina, Y = william ;
+X = thomas, Y = william ;
+…
+

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

+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 +sinovi od Thomasa? Sinovi so seveda osebe moškega spola, ki jim je +Thomas starš. +

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

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

+?- male(X) ; female(X).
+…
+

+ +

Moj prvi program v prologu

+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, mother/2 bo naš ciljni +predikat, definiran takole: mother(X, Y) naj pomeni, da je +X mama od Y. +

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

+mother(tina, william).
+mother(sally, andrew).
+mother(sally, melanie).
+mother(vanessa, susan).
+…
+

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

+Spoznali bomo še zadnji, tretji (poleg dejstva in vprašalnega stavka) tip +stavka: pravilo. +

+Kaj mora torej veljati, da je X mama od Y? Dve +stvari: da je X starš od Y in da je X +ženskega spola. S tem zadnjim ločimo mame od očetov. Pa zapišimo to s +prologovim pravilom: +

+mother(X, Y) :-
+    parent(X, Y),
+    female(X).
+

+Poglejmo sestavne dele zapisanega. Piko na koncu že poznamo, ravno tako že +vemo, da vejica pomeni logični „in“. Torej je X starš in +ženska hkrati. +Kaj pa pomeni nenavadni operator :-, 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. +

+Za naš primer to pomeni naslednje. Če velja, da je X starš +od Y in hkrati (vejica!) velja, da je X +ženskega spola, potem velja, da je X mama od +Y. Pravzaprav je kot pogojni stavek, kajne? +

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

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

+Tako, sedaj si nared, da kaj tudi samostojno sprogramiraš. Vse relacije +(naloge) v tem sklopu so definirane tako, da je X v relaciji z +Y in ne obratno. Tako father(X, Y) pomeni, da je +X oče od Y in ne, da je Y oče od +X. +Naloge rešuj povsem naravno, ne obremenjuj se s tem, da morajo delovati v „vse +mogoče smeri“, kot je delovala relacija parent/2. 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 ancestor/2. +

+ + +

Prva rekurzija

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

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

+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: predpostaviš, 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 ancestor/2. +

+Začnimo takole: vprašajmo se, kdaj je nek X prednik od +Y na najbolj enostaven način? Predniki od Y 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: +

+ancestor(X, Y) :-
+    parent(X, Y).
+

+Spomni se, da se to pravilo prebere kot: če je X starš od +Y, potem je X prednik od Y. Sliši se +smiselno, zato gremo naprej. +

+Kako bi se lotili splošnega primera? Kaj, če predpostavimo, da poznamo nekega +prednika od Y? Recimo mu Z. Potem so tudi +Z-jevi starši predniki od Y, kajne? +Znamo to izkoristititi? Seveda! +

+ancestor(X, Y) :-
+    parent(X, Z),
+    ancestor(Z, Y).
+

+Zanimivo pravilo! Pravi naslednje: če (predpostavka!) je Z prednik +od Y in hkrati (vejica) je X starš od Z, +potem je X tudi prednik od Y. Logično, kajne? +

+Pomembno: doseg spremenljivk, kot so zgoraj X, Y in +Z, je omejen na trenutni stavek! +Globalnih spremeljivk ni – tehnično to ni čisto res, ampak za zdaj to ni +pomembo. 😊 +Tako sta X in Y v prvem stavku (robni primer) druga +kot X in Y v drugem stavku (splošni primer). +

+Vidiš, kako smo relacijo prednik definirali s pomočjo same sebe? To lahko +storimo, če problem „zmanjšamo“. Če pogledamo družinsko drevo, je +Z en korak bližji prednik od Y, kot je to +X. +Tako je, ko smo postavili zahtevo parent(X, Z), smo problem +„zmanjšali“ za en korak. Splošni primer se tako korak za korakom bliža robnemu +primeru, ki rekurzijo konča. +

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

+ +

Slog programiranja

+Kot si opazil, smo prejšni primer (prednik) rešili z dvema praviloma. Tukaj je +celotna rešitev: +

+ancestor(X, Y) :-
+    parent(X, Y).
+ancestor(X, Y) :-
+    parent(X, Z),
+    ancestor(Z, Y).
+

+Rešitev bi lahko zapisali tudi takole: +

+ancestor(X, Y) :-
+    parent(X, Y)
+    ;
+    parent(X, Z),
+ancestor(Z, Y).
+

+Uporabili smo podpičje, logični „ali“. Preberimo pravilo: če je +X starš od Y ali če je X starš od +Z in je hkrati Z prednik od Y, +potem je X prednik od Y. +

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

+Še dve pomembni opazki za konec: +

+Spremenljivke imajo pravzaprav doseg ene veje (konjunkcije). Tako sta v drugem +primeru X in Y v cilju parent(X, Y) +druga kot za podpičjem. +
+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. +

+ + + -- cgit v1.2.1