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.

Graf (gozd) družinskih relacij

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:

  1. kdo je komu starš: relacija parent/2,
  2. kdo je ženskega spola: relacija female/1 in
  3. 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 si lahko š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: