INFORMATICA 4/1980
PROLOG: OSNOVE IN PRINCIPI
STRUKTURIRANJA PODATKOV
IVAN BRATKO, MATJAŽ GAMS
UDK:519.682 FAKULTETA ZA ELEKTRONIKO IN INSTITUT JOŽE STEFAN, UUBUANA
Prolog je programski jezik, osnovan na formalni logiki. Prograra v Prologu definiramo z množico
trditev in ne s postopkom kot v običajnih, postopkovno orientiranih jezikih. Zato ga štejemo
med t.i. nepostopkovne ali deklarativne jezike. Izvajanje programa ustreza formalnemu
dokazovanju izreka, da iz danih trditev (podatkov) sledijo ustrezni rezulta.ti. Nekatere značilnosil
Prologa močno olajšujejo prograrairanje operacij na logično kompleksnih podatkovnih .strukturah in
pa sistemov umetne inteligence. V uvodnem delu tega članka so opisane nekatere osnovne kompo-
nente Prologa. Sledijo primeri iraplementaoije podatkovnih struktur, ki kažejo, kako Prologova
sintaksa omogoča strukturiranje podatkov brez uporabe kazalcev, kot je to običajno v drugih
jezikih, npr. v Pasoalu.
PROLOG: FUNDAMENTALS AND PRINCIPLES FOR DATA STRUCTURING. Prolog is a programming language ba3ed
on formal logic. In Prolog, programs are defined by a set of assertions and not by a proceclure
as in usual, procedurally oriented languages. Therefore it is called a nonprocedura] or
declarative language. The execution of a Prolog program corresponds to a formal proof of a theorem
that the results of the program logically follow from the given assertions (data). Some of Prolog
features greately facilitate the programming of operations on logically oomplex data structures
and of artifioial intelligence systeras. This paper presents the basics of Prolog; follovied by a
number of examples of implementation of data structures in Prolog. The examples illustrate how
the Prolog syntax oan be used for data structuring without the use of pointers as e.g. in Pascal
or other "usual" languages.
1. ZNACILNOSTI PROLOGA IN PRIMER PROGRAMA
U zgodnjih sedemdesetih letih je veljala
naslednja groba klasifikacija programskih je-
zikov (Sammet 19 69):
"Vse programske jezike lahko razdelimo v dve
skupini: v eni je Lisp, v drugi pa vsi ostali
jeziki."
S tem -Je bila podčrtana razlika med prog-
ramskim jezikom umetne inteligence Lispom
(npr. Siklossy 1976) in ostalimi ^normalnimi"
programskimi jeziki, kot so Algol, Fortran,
Cobol, PLl idr. Odkar eksistira Prolog pa bi
bilo uraestno to klasifikacijo popraviti tako-
le: Vse jezike lahko razdelimo v dve skupini:
v prvi je Prolog, v drugi pa vsi ostali jezi-
ki (vključno z Lispora).
Prolog je enostaven, vendar močan prog-
ramskl jezik. Njegova matemationa osnova je
formalna logika, v podobnem smislu kot tvbri-
jo matematično oanovo Fortrana in njemu soro-
dnih Jezikov aritmetični izrazi. Osnova Pro-
loga je bila razvita na univerzi v Marseilleu
(Roussel 1975) kot praktična realizaoija ide-
Je, da Je mogooe materaatično logiko uporabiti
tudi kot programski jezik (npr. Kowalski 197H
Izrazi predikatnega računa prvega reda,
ki tvorijo sintakso Prologa, omogočajo enos-
tavno definiranje relaclj raed podatki in pa
atrukturlranje podatkov. Zato je Prolog pose-
bno mocan pri aimboličnem, nenumeričnem pro-
cesiranju in pri delu z bogatimi podatkovnimi
strukturami. Mnoge formalizme iz teorije poda-
tkovnih baz, npr. relacijaki model, lahko upo-
rabimo praktiono neposredrio kot program v Pro-
logu« Močria komponenta Prologa Je tudi nede-
terminizem in z njim povezano avtomatsko vra-
čanje(automatio backtracking), ki raočno olaj-
šuje programiranje a]f;oritmov kombinatorične
narave.
Tiato, kar tako moono razlikuje Prolog od
ostalih pomembnejaih jezikov Je, da je Prolog
nepostopkovni ali deklarativni jezik, za raz-
liko od drugih, ki 30 vsi v bistvu poatopkovnV
(ali prooeduralni) . V "konvencionalnih" je-
zikih zato opisujemo postopke, torej kako pr±-
derao od danih podatkov do rezultatov. Ideja
Prologa pa je, da opišemo samo,' kakšna' je re-
lacija med podatki in rezultati. Prologov pre-
vajalnik pa mora satn poiakati postopek opera-
oij, ki prevede podatke v rezultšate tako, da
le-ti- uatrezajo zahtevani relaciji.
To razliko med postopkovnimi in nepoatop-
kovnimi jeziki opisujeta naalova dveh zname-
nitih publikacij. Prva (Wirth 1975) se nanaša
na poatopkovne jezike (Pascal), druga pa na
nepoatopkovne (Konalaki 1979):
Wirth: "Programa = Algorithms +
Data St.ruoturea"
Kowalski: "Algorithm = Loglo + Control".
Logika pove., kaj naj program naredi, med-
tem ko (v Prologu skromna.) kontrolna komponen-
ta dolooa, kako bo interpreter nalogo dejanako
izvedel.
Za Prolog je značilno, da prograraa ne de-
finiramo z zaporedjem operacij (tako kot v
običajnih, poatopkovnih jezikih), temveo ?
množico relaoij oz. predikatov. Tako je npr. v
Paacalu znacilna operaoija prireditveni ata-
•vek, npr.:
Y:= f(X)

41
Ta stavek se izvrši tako, da vzamemo vred-
nost X, izračunamo vrednost funkcije f(X) in
to vredncst priredimo spremenljivki Y. Torej
lahko gornji stavek ponazorimo z diagratnom .
kjer je X vhod in Y izhod.
Ekvivalentno definicijo bi v Prologu na-
pisali z izrazom:
f(X,Y)
ki bi ga lahko prebrali kot : X in Y sta v re-
laciji f. Taka izjava deluje raed izvajanjem
programa takole: če je znan X, potern se izra-
cuna Y tako, da je ta Y v relaciji f z X. Če
pa je znan Y, potem se izračuna X tako, da je
apet Y v relaciji f z X. Taka izjava f(X,Y)
deluje v obeh smereh: enkrat je vhod X in iz-
hod Y, drugie pa obratno:
Obstajajo pa še druge možnosti, npr.:
(l)Znana sta oba, X in Y; potem se izjava
f(X,Y) obnaša kot neke vrste kretnica, ki
teatira, a1i sta dana X in Y v relaciji
3 f. .
(2)Noben od X in Y ni znan; v tem prirneru se
prograra obnaša tako, kot da bi Prolog pri-
redil sprernenljivkama X in Y vse možne pa-
re vrednosti, ki so v relaciji f.
Drug primer značilnega stavka v konven-
cionalnem jeziku je npr.:
if N > 0 then N := N-l;
kar lahko beremo kot: "Če je vrednost spre-
menljivke na lokaciji N večja od 0, potein za-
rnenjaj vrednost na lokaciji N s staro vrednos-
tjo minus 1".
Značilen primer stavka v Prologu pa je
npr. :
potomec(X,Y):-otrok(X,Y).
kar beremo takole:
"X je eden izmed potomcev od Y, če je X
eden izmed otrok od Y" ali pa
"Ce je X otrok od Y, iz tega sledi, da je
X potomec. od Y" . ,
Ta trditev velja za vsak X in Y. Operator
:- deluje kot logična implikacija z desne v
levo (v niatematiki navadno ^nak •<— ).
Kot primer programa v Prologu vzemimo im-
plementacijo nekaterih sorodstvenih relacij.
Slika 1 kaže priiner družinskega drevesa, ki ga
v Prologu lahko opišerno z naslednjimi stavki:
otrok(dare,tom).
otrok(bor,dare).
otrok(črt,tom).
Ti dve izjavi opišemo v Prologu z:
potoraec(X,Y) :- otrok(X,Y).
potomec(X,Y) :- otrok(Z,Y), potomec(X,Z).
Slika 1. Primer družinskega drevesa.
Te stavke lahko beremo npr. "Dare je otrok
od Tom" alj. pa "Dare in Toin sta v relaciji
otrok" .
Napišimo še stavke v Proiogu, ki definira-
jo relacijo "potomec", na osnovi naslednjega
razmišljanja (glej sliko' 2).
(a) X je potomec od Y, če je X otrok od Y, ali
(b) X je potomec od Y, če eksistira 7., tak, da
(1) Z je otrok od Y in
(2) X je potomec od Z.
jtomec
otrok
'otomec
potomec
Slika 2. Definicija relacije "potomec".
Zdaj lahko postavimo Prologovemu. sistemu že
nekaj vprašanj, npr: "Kdo je otrok od Toma in
kdo je Borov oče?" To storimo z naslerinjim
Stavkom v Prologu:
?-otrok(X,tom),otrok(bor,Y).
Odgovor, ki ga dobimo, je:
X=dare, Y=dare;
X=črt, Y=dare
Kot vidirao, sta bila na vprašanje rriožna
dva odgovora (ker ima Tom dva otroka). Prologov
interpreter je poiskal oba.
Vprašajmo še, kdo so Tomovi potomci:
?- potomec(X,tom).
X=dare;
X=Qrt;
X=bor;
Ta primer ilustrira način programiranja v
Prologu, ki je močno razlicen od programiranja
v konvencionalnih jezikih. V primerjavi s temi
jeziki v Prologu ne eksistirajo konstrukti, kot
so:
-krmilni konstrukti, npr. goto, while, repeat;
-prirejanje vrednosti spremenljivkam in spre-
minjanje vrednosti spremenljivk;
-dznake stavkov, globalna iraena spremenljivk.
Nekatere implementacije Prologa so:
-interpreter v fortranu (napisan na univerzi v
Marseillu) ;
-interpreter v assemblerju za DEC-10 (univerza
v Edinburghu);
-kompilator, napisan v Prologii in deloraa v ass-
emblerju za DEC-10 (Edinburgh);
-interpreter v assemblerju za PDP 11/3^ CEdin.)
-interpreter v Lispu za CDC CYBER (Linkoping).
2. NEKATERI ELEMENTI JEZIKA IN
ENOSTAVNI STAVKI
Programer v Prologu opiše svoj problem na
deklarativen način, medtem ko mora Prologov si-
stem pri izvajanju programa vendarle izvršiti
določen postopek, torej ga mora interpretatira-
ti " postopkovno" ; zato ločimo dva pornena (oz.
semantiki) programov v Prologu: deklarativni In
postopkovnl pomen programa.
Tako npr. stavek v Prologu
P :- Q, R.
(ki je ekvivalenten zapiau v raatematični logiki
P-^RAR ) lahko beremo na nas.lednje načine:
(1) Deklarativno:
"0 i n R i in p 1 i c i r a P " a 1 i
"Iz 0 in R sledi P"
(2) Postopkovno:
" Z a t o , d a r e š i m o P m o r a m o r e š i t i Q i n R "
a.li "En način za izvršitev procedure P je:
pokliči proceduro Q in zatem proceduro R."

42
Program v Prologu lahko zato razumemo kot
množico logičnih trditev, ki jih mora Prologov
sistem ovreči ali pa dokazati njihovo resnič-
nost. Zato je izvajanje prograrna v Prologu de-
jansko dokazovanje trditev,- ki so postavljene
v programu... S tega ^tališča je Prologov inter-
preter avtomatski dokazovalnik izrekov. Stavki
v Prologu.imajo obliko
P :-
Lava stavka telo stavka
Ta stavek pomeni: "P je res, oe so Q in R
in S res". Q, R in S se imenujejo cilji. Šte-
vilo eiljev v stavku je poljubno, lahko tudi
enako nič. Stavek brez ciljev je enotin 3ta-
vek, npr.
P.
kar porneni: "P je vedno res".
Z enostavnimi stavki opisujemo enostavna
dejstva, npr.
otrok(dare,tom).
Vprašalni stavki se začenjajo z vprašajetn,
?-P, Q.
To pomeni "ali sta P in Q resnična" oz.
"reši P in Q".
Elementarni podatkovni objekti so:
(1)"atomi", npr.:
david, a, nil, tom, dare
(2)cela števila, npr.:
5, 0, -973
(3)apremenljivke (se lččijo od atomov po ve-
liki začetnici) npr.:
X,y, B23, List, Pilot
Spremenljivke lahko dobijo vrednost med
izvajanjern programa. Sestavljeni podatkovni
objekti 30 izrazl. Primer izraza, ki opisuje
točko v tridimenzionalnem prostoru, je
toeka(X,Y,Z)
funktor arguinenti
Z uporabo funktorjev lahko gradimo izra-
ze, v katerih 90 vgnezdeni podizrazi. Na ta
način Jahko strukturiraino naše podatkovne
objekte. Podatkovno strukturo, ki jo imenuje-
ino seznam, (znano predvsem iz programskega
jezika Lisp) Lahko npr. zgradimo z uporabo
funktorja "." (pike). Sezriam je zaporedje
podatkov, ki ga lahko definiramo takole:
•'lezriaiii je bodisi (l)prazno zaporedje, ki ga
po dogovoru navadno ozruicimo z nil (no-item-
list), bodiai (2) irna prvi element (imenovan
glava) in pa preostanek (imeriovan rep); pri
tem je glava laliko kafkoli, rop pa rnora bitl
seznam (lnliko fcudi prazen). Primer seznama
imen je npr. :
tina , te ja , ma jqj
Glava tega seznaina je "ana", rep pa je
" te ja , rna ja" .
V Prologu siriemo uporab 1 jatj. za yeznaine
prav tako notaeijo, kot smo jo uporabili v
gornjem pramefii. Vendar ,je to le aintaksna
nadgradnja Prologove predatavitve aeznarnov s
funktorjem ".". Ta funktor1 ima dva argumenta,
od katerih je pr'vi glava seznama, drugi pa
rep seznaina. Tako je
^na , teja , ma jij
ekvivalentno zapisu
. (ana , Cteja ,ma J3 )
kar je ekvivalentno
. (ana, . (teja, [raaja] ))
oz. naprej
. (ana , . (te ja , . (nia Ja ,nil )) )
Nazorno l.aliko ponazarjnmo izraze grafično
z uporabo dreves. V takih drevesih so v not-
ranjih vozliščih funktorji, v zunanjih pa ele-
mentarni podatki. Primeri ponazarjanja z dre-
vesi so:
X = a + b
točka(X,Y,Z)
L = £ana, teja, raaja]
Če pišemo Rep = fteja.majaj ,
potern je koristna uporaba operatorja "|", ki
povezuje glavo in rep:
L = [ana I Rep]
iO
Slika 3. Strukturi ran jo podatkov <> družini.
Dejstvo, da eksiaLira druSina na :sliki 3,
laliko opišemo
Prologu:
druž
(os
0:3
(rus,
(rua,
(rus,
(rus,
z nao.l ednjim enoLiniin :itavkom v
aci, danr(30, innj, l.ycjt))),
ana , danr( 15, inuj, 1951)),
tom, dani'( 5, maj, 1973)),
eva, danr( 5, ma.j, 1973) )j
Pri tem smo uvedli funktorje:
dfužC družina ) , on(oaebii), dant'(dan rojuLva).

43
Leksikalni doseg spremenljivk v stavkih
Prologa je ornejen na stavek sam. Tako lahko v
dveh stavkih nastopa ime spremenljivke X, ven-
dar to ni enasarna spremenl jivka, temveč dve
povsem razliSni spremeriljivki. Poglejmo nekaj
primerov, ki ilustrirajo to pravilo:
l.Trditev "Vsakdo zaupa samemu sebi" napišemo
lahko z naslednjim stavkom:
zaupa(X,X).
2.Trditev "Vsak moški X je poročen, če eksis-
tira družina, v kateri je X mož":
poročen(X) :- druž(X, _, _).
Črtice oznaoujejo "slepe" spremenljivke.
3. Trditev:"Katerikoli osebi A in B sta poro-
čeni med seboj, če eksistira družina, v kate-
ri je A mož in B žena", ali pa "oe eksisti-
- ra družina, kjer je B mož in A žena. " To
trditev opisujeta naslednja stavka:
zakonca(A.B) :- druž(A,B,_).
zakonca(A.B) :- druž(B,A,_).
Ta stavek lahko zapišerao krajše:
zakoncafA,B):- druž(A,B,_); druž(B,A,_).
Podpičje označuje disjunkcijo raed dverna
ciljema.
3.- DEKLARATIVNA IN POSTOPKOVNA SEMANTIKA
TER IZVAJANJE PROGRAMOV
Kot smo že omenili, lahko programe v Pro-
logu gledamo na dva načina: prvič deklarativ-
no in drugič postopkovno. Ker imajo programi v
Prologu deklarativni in postopkovni pomen, ek-
sistirata tudi dve semantiki Prologa. Deklara-
tivn.i. pomen Prologovega programa govori o rela-
cijah med podatki oz. atrukturami. Torej v ne-
kem smislu opisuje zakonitosti, ki se jim pod-
rejajo objekti, ki nastopajo v programu, neod-
visno od samega postopka. Ta nepostopkovni,
deklarativni vidik Prologovih programov dviga
Prolog izredno visoko v hierarhiji programskih
jezikov.
Vendar pa mora Prologov interpreter priti
do iskanih rezultatov vseeno po nekem postop-
ku, zato je potrebna (kot neke vrste nujno
zlo) tudi postopkovna semantika, ki natančno
predpisuje, po kakšnem postopku se program iz-
vaja. S stališoa programiranja pa je nadvse
pomerabno to, da lahko programer v načelu raz-
mišlja na en ali drug način, saj se programer-
ju ni treba spuščati v detalje samega postopka.
Izkaže se, da je pogosto mnogo lažje rešiti
problem na deklarativen način. Deklarativna
semantika Prologa definira, kdaj je kaka izja-
va v Prologovern programu resniona, tj. da Je
izjava dejstvo: "Dani oilj je dejstvo, če je
ta cilj "primer" glave kakega stavka in so pri
tem vsi cilji (če eksistirajo) v telesu tega
stavka tudi dejstva. Primer stavka (ali izra-
za) dobimo s substituoijo vsake od njegovih
spremenljivk z nekim drugim izrazom na^ vseh
mestih, kjer se spremenljivka pojavlja."
Postopkovna semantika Prologa pa je dana
z naslednjirai pravili:
l.Za izpolnitev cilja je treba med seboj "pri-
lagoditi" ta cilj in glavo kakega stavka in
zatem izpeljati vse cilje v telesu tega stav
ka ("prilagajanje" izrazov je pojasnjeno
kasneje).
2.Cilje v telesu Izvršuj od leve prbti desni.
3-Cilj poskušaj prilagoditi glavam stavkov po
vrsti od zgoraj navzdol.
t.Kadar ni mogoče (več) prilagoditi cilja no-
beni glavi, se "vrni nazaj" in poskušaj iz-
polniti prejšnji cilj na kakšen drug način
(angl. backtraok).
5.če niti prilagajnnje niti vračanje ni več
mogoče, potem cilja ni mogoče izpolniti.
Prilagajanje dveh izrazov je proces, ki
spremenljivkam v obeh izrazih priredi take
vrednosti, da postaneta po tej substituciji
spremenljivk oba izraza identična. Prilagodi-
tev je torej množica prireditev vrednosti sp-
remenljivkam tako, da se oba izraza izenaoita.
Npr. izraza
tooka(X,Y,3) in
točka(2,Y1,Z)
se prilagodita takole: X = 2, Y=Y1, Z=3.
Pri izvajanju Prologovega programa iščemo
vedno najbolj splošno prilagoditev. Najsploš-
nejša prilagoditev je tista prilagoditev, ki
izenači oba izraza in pri tem čimmanj natančno
specifioira vrednosti spremenljivk. V gornjem
prirneru je možna tudi naslednja, manj splošna
prilagoditev :
X = 2, Y=5, Yl=5, Z=3-
Ta izenači oba izraza in rezultat prilaga-
janja je točka(2,5,3). Vendar pa ni najsplošne-
jša, ker sta vrednosti spremenljivk Y in Yl po
nepotrebnem povsem specificirani. Za prilago-
ditev zadošča. namreč že omejitev Y=Y1.
Slika 4 kaže še en primer prilagajanja.
1. izraz
druž(os(zajc,jože,danr(5,marec,1931)),X,Z)
2. izraz
druž(V,os(zajc,jana,D),nil)
os X Z
os nl
jože
jc ia
S macec
Najsplošnejša prilagoditev:
V= ostzajo^jož^
X= os(zajc,jana,D)
Z= nil •
Slika f. Primer prilagajanja izrazov.
Izkaže se, da je prilagajanje izrazov iz-
redno močno programirno orodje in da lahko že
s samim prilagajanjem rešujemo problemc. Naa-
lednji program npr. izračuna s samim pril.agaja-
njem, katere dalji.ce so hkrati hori zonLalne in
vertikalne. Slika 5 iluatrira način, ki smo ga
izbrali za popis nekaterili pojinov iz ravninnke
geometrije.
Točka je dana z dverna koordinatamn, npr,
t(X,Y), daljioa pa z dvema V.oSkama: daljica(Tl,
T2). Naslednji program definira, kdaj je kaka
da 1 j ioa vert i ka 1 nsi oz . hor i v-on ta 1 na :
vertikalna(dal jica( t(X, Yl)., t(X, Y2))) .
horizontalna(daljica(t(Xl,Y),t(X2,Y))).
Ta program že zadošča, da. lahko zastavimo
nekaj vprašanj v obliki ci.lj-ev. za Pro,Logov.

44
interpreter (odgovori računalnika so podčrta-
ni., komentarji pa v oklepajih):
?-vertikalna(daljica(t(0,l),t(0,2))).
Yes; (odgovor je da)
?-vertikalna(daljica(t(l,2),t(2,3)).
No; (odgovof je: ta daljica ni vertikalna).
Vprašajmo še, ali eksistira aaijiea, ki je
hkrati vertikalna in horizontalna:
?-vertikalna(D),horizontalna(D).
D=daljica(t(X,Y),t(X,Y))
Odgovor pomeni: da, to je vsaka daljica,
ki je degenerirana v eno s.-imo točko.
V
Slika 5: Opis nekaterih geometrijskih pojraov
v Prologu.
.Naslednji primeri bodo ilustrirali postop-
kovni pomen Prologovih programov.
Primer 1: relacija"ded-vnuk"
To relacijo lahko opišerao deklarativno ta-
kole: X je ded od Y, če je X roditelj od Z in
obenem Z roditelj od Y, ter X je moški. To,
skupaj s še nekaterimi enostavnimi trditvami,
zapišemo v Prologu takole:
ded(X,Y) :- roditeij(X,Z),
roditelj(Z,Y),
rnoški(X).'
moški(tone).
moški(peter).
ženska(ana).
ženska(eva).
moški(rok).
rodite.lj(ana,eva).
roditelj(tone,eva).
roditelj(eva,rok).
roditelj(peter,rok).
Zastavimo vprašanje : Kdo je Rokov ded?
?-ded(X,rok).
Zasledujmo izvajanje programa, to je pos-
topkovni poraen programa:
cilj je ded(X,rok)
Ta cilj se prilagodi z glavo stavka
ded(X,Y):-
Pri tem postane Y=rok, generirajo pa se
podcilji (v telesu stavka, s katerim se je
prilagodil tekoči ci1j ):
podcilj 1: roditelj(X,Z)
podcilj 2: roditelj(Z,rok)
podcilj 3: moški(X)
Podcilj 1 lahko izpolnimo tako, da ga pri-
lagodimo prvemu izmed stavkov "roditeljC...)".
Tako dobimo prilagoditev
X.= ana , Z = eva
Po tej prilagoditvi je podcilj 1 izpolnjen
(ker v telesu atavka "roditelj..." ni bilo več
nobenega cilja). Zato je na vrsti podcilj 2, 'ki
Je po prilagoditvi postal
roditelj(eva,rok)
Ta podcilj je trivialen, 3aj je že shran-
jen kot dejstvo v našera programu. Naslednji,
tj. tretji podoilj, je
raoški(ana)
Ta podcilj se ne prilega glavi nobenega
stavka, zato ga ni mogoče izpolniti. Zato se
izvajanje programa vrne nazaj in skuša prejš-
nje podcilje izpolniti na drug način. Podcilja
2 ni rnogoče izpolniti na noben drug naoin, zato
pa je to mogooe s podoiljem 1:
roditelj(X,Z)
in sicer takole:
X=tone, Z=eva
Podcilj postane zdaj roditelj(eva,rok ) .
To je že enotin stavek v programu. Preos-
tane še oilj raoški(tone), ki je prav tako tri-
vialno izpolnjen. S tem so vsi podcilji iz-
polnjeni. Izpiše se rešitev, ki je definirana
s prilagoditvami :
X=tone
Primer 2: konkatenacija seznamov
Napiširno proceduro za konkatenacijo (spaja-
nje) eeznamov, tako da bo predikafc
conc(Ll,L2,L3) izpolnjen,
oe je seznara L3 konkatenacija seznarnov Ll in
L2, npr.:
oono( (a , b] , |č,d,e] , (a.b.c.d.ej )
Idejo za to prooeduro lahko izraziino dekla-
rativno:
(1 )Konkatenaeija kateregakoli seznaina L s praz-
nim seznamora je seznam L.
(2)Če konkateniramo seznam oblike[xil-3 (glava
je X, rep pa Ll) s seznamom L2, dobirao seznam,
katerega glava je X, rep pa konkatenaoija sez-
namov Ll in L2 :
X Ll
L3
Ti dve trditvi izrazimo v Prologu takole:
)
,L2, [XIL3J ) :- cono( Ll, L2 , L3).
conc( C
conc(
Proceduro eonc lahko uporabljarno na razne
načine. Npr. tako, da podamo vrednosti prvih
dveh argumentov in kot rezultat dobimo njeno
konkatenacijo. Rolj zanimiv primer uporabe je,
če je podan tretji argument, kot rezultat pa
dobimo prva dva seznama, tako da je njuna kon-
katenacija enaka tretjerau. Če je močno tretji
(dani) seznam sestaviti iz dveh aeznnmov na veo
načinov, potem dobimo kot rezultat vse možne
rešitve:
?-conc([a,b}, [l,2,3],X).
X=[a,b,],2,31

45
?-oonc(Ll,L2, [a , b , cj ).
Ll:=C3,L2=[a,b,e3}
LlCai',L2=Cb,c3;
= Ca.bJ ,
Ll=Ca,b,c3,L2 =
Ta zgled iluatriira nedeterminizem v Prolo-
gu: če je.možnih več rešitev, Prologov inter-
preter generira vse, razen če tega.na poseben
načinne prepovemo. Definirajmo še relacijo
member.(X,L)
ki je izpoinjena, če je X eleraent seznama L. To
relacijo lahko na nepostopkoven način definiramg
takole: X je element seznama L, če eksistira-
ta dva podseznama seznama L tako, da je glava
drugega podseznama enaka X:
member(X,L) :- oonc(Ll, [X IL2],L).
Kako deluje ta presenetljiva rešitev, kaže
slika 6.
Slika 6. Izvajanje procedure
member ob vprašanju:
?- meraberCb ,£.a , b ,c}) .
Vcasih že vnaprej vemo, da je generiranje
alternativnih rešitev nepotrebno oz. nesmiselno
V takih primerih bi Prologov program po nepot-
rebnem trošil čas in prostor, zato imarao na vol
jo dodatni krmilni element, ki prepreči iskanje
alternativnih rešitev. Ta krmilni element je ti
cut operator", ki ga označujemo s klicajem. Za
primer definirajmo relacijo
max(A,B,M)
tako, da je M vrednost večjega od A in B. To
lahko storimo z:
max(X,X,X) . , .. : ,.,:'•.
max(X,Y,Y) :- X< Y. , . ...
max(X,.Y,X) :-.. Y< X.: .... ; ., ,
Kako se obnaša ta procedura,. če zastavimo
cilj: .,.:.,..
?-max(2,3,M),M<2. . .. . .
Prvi podcilj1uspe tako, da M postane 3.
Drugi podcilj postane 3<2 in ne uspe. Zato se
izvajanje vrne na prvi podcilj in ga poskusi
zadovoljiti še na kak drug naoin,' torej posku-
si z:
max(2,3,M) :- 3<2.
Seveda tudi. to ne uspe in s, tetn ne uspe
tudi eelotni oilj. Iz naravne rela.cije max ve-
mo, da lahko uspe kvečjemu eden izmed stavkov
procedure max. Ko je uspel v gornjem poizkusu
drugi stavek te procedure, je jasno, da tretji
stavek ne more več uspeti. Zato je vračanje na
ta stavek brezplodno. To vračanje lahko prep-
rečimo z naslednjo dopolnitvijo prooedure max:
max(X,X,X) :-!.
max(X,Y,Y) :- X
max(X,Y,X) :- Y
Y,
Matanoen pomen operatorja "!", imenovanega
"cut", je: "!" se obnaša kot cilj, ki vedno us-
pe, pri tem pa povzroči kot stranski učinek,
da se prepreči vračanje na prejšnje podoilje
pred klicajem.
Naslednji primer nadalje pojasnjuje obna-
šanje operatorja "cut".
P :- Q1,Q2.
P :- R.
Ta procedura definira naslednjo logično
zvezo raed izjavami P,Q1,Q2 in R:
P <=9Q1 A Q2 VR
Zdaj postavimo "out" takole:
P :- 01,I,Q2.
P :- R.
Logična zveza med izjavami ae spremeni v:
P <=^Q1 A Q2 VwQl A R
1. ZAKLJUCEK
V sestavku smo pokazali nekatere značilnosti
Prologa, predvsem tiste, zaradi katerih je način
razrnišljanja pri programiranju v Prologu
drugačen kot pri prograiniranju v postopkovnih
jezikih. Sintaksa predikatnega računa, na
kateri teinelji Prolog, je zelo posrečena za
opis relacij med podatki. Po eni strani ta
sintaksa omogoča delo s podatkovnimi struktu-
rami, ne da bi pri tem eksplicitno uporabljali
kazalce. Vsak sestavljeni podatkovni objekt v
Prologu lahko ponazoritno z drevesom. Po drugi
strani pa lahko to sintakso uporabljamo
direktno kot jezik za postavljanje vprašanj
(query language) za relacijski model
podatkovnih baz. Že sam mehanizem prilagajanja
zadošča za dokaj zahtevno iskanje relacijskih
odnosov v bazi podatkov (to je v množioi
trditev, zapisanih v programu v Prologu).

46
Opisani primeri so poveoini nakazali
možnosti strukturiranja in iskanja podatkov.
Nekatere druge operacije, ki zahtevajo več
procesiranja na seznamskih, drevesnih in
grafskih strukturah, so opisane v (Bratko,
Gams 1981). •.Tam je poudarek na primerjavi
Prologa z običajnimi jeziki, zato so te
operacije implementirane še v Pascalu kot
predstavniku konvencionalnih jezikov.
LITERATURA
Bratko I., Gams M. (198.1, / pripravi)
Prolog: prooesiranje podatkovnih struktur
in primerjava s Pascalom. Ljubljana: '
Informatika.
2. Kowalski R. (1974) Predicate logio as a
programraing language. Proc. IFIP Congress
74. North-Holland.
3. Kowalski R. (1979) Algorithm - Logic +
Control. CACM, Vol. 22, No. 7, 572-595.
4. Pereira L., Pereira F., Warren D.H.D.
(1978) User's Guide to DEC System 10
Prolog. University of Edinburgh, Departrnent
of Artificial Intelligence.
5. Roussel P. (1975) Prolog: rnanual d'utiliaa-
tion. Raport interne GIAVER de Luminy,
Universite d'Aix, Marseille.
6. Saramet J. (1969) Prograraming Languages:
History and Fundamentals. Prentice-Hal1.
7. Wirth N. (1976) Prograins = Algorithras +
Data Structures. Prentice-Hal1.
8. Siklossy L. (1976) Lef s Talk Usp.
Prentlco-Hall .