41
MOGUČNOSTI PROCEDURALNOG PROGRAMIRANJA U PROGRAMSKOM JEZIKU PROLOG
INFORMATICA 3/89
Keywords: procedural programming, Prolog, matrix multiplication
Iztok Z. Race, Mašinski fakultet, Beograd
SAŽETAK
Programski jezik PROLOG kao deklarativni programski jezik se bi trio razlikuje od proceduralnih programskih jezika, jer prvenstveno opisuje posmatrani problem, a ne način kako se rešava neki problem. U skladu sa tako koncipiranim programskim jezikom., bitno se razlikuju programi pisani u PROLOG-jeziku od programa pisanih u proceduralnim jezicima. Zbog toga se mora govoriti i o drugačijem načinu razmišljanja programsra pri li kom izrade programa u programskom jeziku PROLOG. U radu ■je dato moguče rešenje za neke uobičajene programske strukture i strukture podataka iz proceduralnih jezika, te ilustracija mogučnosti proceduralnog programiranja u PROLOG-jeziku na primeru množenja matrica.
1. PROLOG KAO DEKLARATIVNI PROGRAMSKI JEZIK
naglim razvojem njenom primenom u aktivnostima,	za
kao orude u ovoj
Poslednjih godi na, veštačke inteligenci je i raznorodnim ljudskim programski jezik PROLOG oblasti, izuzetno raste interesovanje.
PROLOG-jezik je nastao iz ideje da se predikatska logika posmatra kao programski Jezik. Zbog toga, program u ovom jeziku opisuje relacije izmedu pojedinih objekata, i pravila na osnovu kojih se iz postoječih relacija mogu dokazati nove. To je bitna razlika koja odvaja ovaj jezik od proceduralnih jezika kao što su npr. FORTRAN, BASIC ili PASCAL. U proceduralnim jezicima se program sastoji iz niza koraka u kojima se opisuje kako da računar izvrši odredena izračunavanja. U PROLOG-jeziku je program opis problema koji se posmatra, dok se sam način na koji se problem rešava direktno ne opisuje. Drugim rečima, proceduralni programski jezici opisuju kako se rešava pojedini problem, dok deklarativni programski jezici opisuju šta je posmatrani problem.
PROLOG-Jezik se od proceduralnih Jezika razlikuje u nizu osobina. 'Promenljive u PROLOG-jeziku dobijaju vrednost samo u toku pokušaja zadovoljenja odredene rečenice PROLOG-jezika. Njihova vrednost je trenutna i vezana je za trajanje razmatranja date rečenice. Na taj način promenljiva ne predstavlja striktno odredenu memorijsku lokaciju. Sa druge strane, proceduralni jezici imaju velik broj sličnih programskih struktura ili struktura podataka koje ne postoje u PROLOG-jeziku poput if-then-else strukture, peti ji ili nizova. Nasuprot tome PROLOG-Jezik ima svoje osnovne mehanizme koji ga izdvajaju
od ostalih jezika kao što su automatski backtracking i cut-predikat. Ovi mehanizmi omogudavaju da se pojedini problemi u programskom Jeziku PROLOG reše na drugačiji i bolji način, što sa svoje strane može predstavljati teškodu prilikom pisanja programa u ovom jeziku, pogotovu ako se prilikom programiranja koriste načini razmišljanja iz drugih programskih Jezika.
Ponekad je, u kompleksni Jim problemima koji se rešavaju u PROLOG-jeziku, potrebno izvršiti odredena izračunavanja, za koja su proceduralni jezici daleko efikasniji. Od načina na koji se problem postavi u PROLOG-jeziku vrlo Cesto zavisi i brzina, a ponekad i ukupan uspeh datog rešenja. U radu se ukazuje na neke od mogudih pristupa tom problemu.'
2. PREDSTAVLJANJE NEKIH STRUKTURA PROGRAMSKOM JEZIKU PROLOG
PODATAKA U
Promenljive. U mnogim programskim jezicima promenljive predstavijaju odredene memorijske lokacije, čiji sadržaji ostaju nepromenjeni sve dok se ne izračuna neka druga vrednost i memoriše kao novi sadržaj posmatrane memorijske promenljive. Za razliku od tog pristupa, promenljive u programskom jeziku PROLOG imaju naglašeno lokalan karakter, tj. one su aktuelne samo u okviru rečenice u kojoj se spominju. Takode je karakteristično da svaki pokušaj izmene vrednosti več postavljene memorijske promenljive, u ovom programskom jeziku završava neuspehom.
Zbog ekstremne lokalnosti promenljivih u PROLOG-jeziku, prenos parametara se vrši na jedan od sledeča dva načina:
- funkcijskim pozivom
42
- upisivanjem vrednosti promenljive kao činjenice.
Primer funkcijskog poziva u PROLOG-jeziku bi bi o:
liste, ili kao niz činjenica.
Stek se predstavlja pomodu liste na taj način što se oformi struktura
stekC C vrh,...,dno]3
alCPl,P2,... D.
al C P1, P2,. . . 3 : -. . . , a2C P1, P2,. . . 5 ,. . .
čime se vrednosti promenljivih P1.P2,... u predikatu al, postavijaju na vrednosti promenljivih u predikatu a2, pa se na taj način i obavlja prenos parametara.
Upi si vanje vrednosti promenljive kao činjenice u bazu podataka PROLOG-jezika se vrši pomodu sistemskog predikata asserta ili assertz. Tako bi npr. rečenica:
gde su elementi liste, redom elementi u steku, od elementa na vrhu steka Coznačenog sa vrh3 do elementa na dnu steka Coznačenog sa dno3. Dodavanje novog elementa na stek se vrši zadovoljenjem predikata push, koji može imati sledeči oblik:
pushCElement,Stek,C Element:Stek]3.
dok se izbacivanje elementa sa vrha steka može realizovati na sledeči način u PROLOG-jeziku:
asser tzC vr ednostC a2,10003 3 .
u bazu podataka Cna njen kraj3 upisala PROLOG-činjenicu vrednostCa2,10003. Na taj način se, formiranjem ovakve strukture . u bazi podataka PROLOG-jezika, može predstaviti promenljiva a2 kojoj je pridružena vrednost 1000, odnosno relacija vrednost koja se uspostavlja izmedu atoma Cimena promenljive3 a2 i atoma Csadržaja promenljive3 1000. Promena ove vrednosti, na recimo 500, se vrši, pomodu sistemskih predikata retract i assertz, odnosno tako Sto se prvo obriše stara vrednost, a zatim upiše nova, odnosno, u PROLOG-jeziku:
popC_,C],C]3:-writeC'Stack underflow'3. popC Element,C Element!Stek],Stek 3 .
Prva rečenica kojom je opisan predikat pop odgovara stanju kada se pokušava da izbaci element iz praznog steka, dok druga rečenica odgovara izbacivanju elementa u regularnom slučaju.
Stek se može predstaviti i kao niz činjenica u PROLOG-jeziku, oblika:
stekCvrh3.
stekC el ementrrO.
retractCvrednostCa2,_33, asser tzC vr ednostC a2,5003 3.
To, dinamički gledano odgovara činjenici da atomi a2 i 1000 više nisu u relaciji vrednost, i da je ta relacija uspostavljena izmedu atoma a2 i 500. Tako se pomodu relacija može predstaviti izmena sadržaja memorijske promenljive u proceduralnim jezicima. Pri tome se mora naglasi ti, da za razliku od situacije kod proceduralnih jezika, atom a2 Coznačava ime promenljive3 može biti u relaciji sa više atoma koji označavaju vrednosti istovremeno, što može korisno poslužiti pri rešavanju nekih problena.
Nizovi. U PROLOG - jeziku nema nizova za razliku od mnogih drugih Jezika. Zato se, ukoliko je potrebno odredene podatke strukturirati u niz, oni unose u bazu podataka PROLOG-jezika slično promenlji vama:
assertzC vr ednostC aC1,23,55033.
stekCdno3.
Pri tome se ubacivanje elemenata u stek vrši zadovoljavanjem predikata push koji ima sledeči oblik:
pushC Element,Stek 3:-
Struktura=.. CStek,Element], assertaCStruktura3.
Zadovoljavanjem predikata pop se vrši izbacivanje elemenata iz steka:
popC Element,Stek3: -
Struktura=. . CStek,Element], poplCStruktura3 .
poplCStruktura3:-
retractCStruktura3,!.
poplCStruktura3: -
writeC"Stack underflow'3.
Strukturiranje se može izvršiti i na druge slične načine.
Pokaživači. Pokaživači se u PROLOG jeziku realizuju na taj način što se doda j oš jedno polje u postojedu strukturu promenljive koje ukazuje na neku drugu promenljivu. Tako strukturisana promenljiva ima oblik:
aCindexm,...,indexp3
gde promenljiva u nizu a sa indeksom indexm Ima pokazivač koji pokazuje na promenljivu sa indeksom indexp.
Stekovi. Stekovi u programskom jeziku PROLOG, uglavnom se predstavijaju ili kao
Zadovoljavanje predikata pop se vrši na taj način što se prvo zadovolji univ-predikat i tako formira struktura čiji je funktor sadržaj promenljive Stek Ckoja za vrednost ima ime steka3 a Jedini argument nepostavlJena promenljiva Element. Zatim se zadovoljava predikat popi. Ukoliko postoji u bazi podataka PROLOG-jezika struktura sa gore odredenim funktorom Cprva takva na vrhu3 se izbacuje iz baze Ci iz steka3. Time se, ujedno i postavlja promenljiva Element u strukturi i predikatu pop. U slučaju da u bazi podataka takva struktura ne postoji, Javlja se odgovarajuda poruka.
Niska Cqueue3. Niske se mogu implementirati u PROLOG-jeziku kao liste, pa se
43
formira slededa struktura:
niskaC[ početak.....kraj D
medutim takvo rešenje ima svojih loäih strana, koje se uočavaju prilikom umetanja novih elemenata na kraj niske. Da bi postavili element iza elementa koji Je na kraju liste, moramo zadovoljiti predikat insert koji može i mati sledeči oblik:
i nsertC Element, [], [ElementD. insertCElement,[G!R],[G!R1]3:-i nsertC Element,R,R13.
Izbacivanje elemenata iz liste u takvom rešenju je daleko jednostavnije obzirom da je element koji se izbacuje iz niske prvi element liste kojom je niska predstavljena. Tako bi predikat delete kojim obezbedujemo tu funkciju mogao da ima oblik:
deleteC_, [], t D: -
writeC'Queue underflow'3,!. deleteCPočetak,[Početak! R],R3.
Mnogo efikasnije reSenje se postiže upotrebom sistemskog predikata assertz, u kojem se niska predstavlja u obliku činjenica u PROLOG-jeziku tipa:
niskaCpočetak}.
niskaCelementnO.
niskaCkraj}.
Predikati insert i delete koji nam služe za manipulaciju sa niskom bi u ovom slučaju i mali oblik:
i nsertCElement,Ni ska3: -
Struktura=..[Niska,Element], assertzCStruktura3.
deleteC Element, Ni sk a3 : -
Struktura=. . [Niska,Element], del et el C Struktura!).
deletelCStruktura3:-
retractCStrukturah,!. deletelCStrukturaD:-
writeC'Queue underflow'3.
Drveta i grafovi se mogu predstaviti na razne načine koji variraju od rešenja da se celo drvo Cili graf3 predstavi kao lista do reSenja da se prvo čvorovi drveta Čgrafa3 predstave u obliku činjenica u PROLOG-jeziku a potom, takode i veze koje poštoje medu ti m čvorovima. Tako se graf može predstaviti slededom strukturom u PROLOG-jeziku:
grafC [ [čvorl,Cčvorll.....čvorlk] ].....
C[čvorn,[čvornl,. . . .čvornm]]]}
gde su čvorl.....čvorn imena čvorova u grafu uz
koje je pridružena lista imena čvorova sa kojima je svaki od tih čvorova u vezi. Graf se može predstaviti i na sledeči način:
grafCčvorl, [čvorll.... ,čvorlk]3.
grafCčvorn,[čvornl.....čvornmD.
ili:
grafCčvorl3.
grafCčvorn}. grafCčvorl,čvorll}.
gr af C č vor n, č vor nnO.
gde se činjenice sa funktorom graf i jednim argumentom odnose na čvorove grafa, a one činjenice sa istim funktorom i dva argumenta na veze koje postoje u grafu. Ovo su samo neke od varijanata predstavljanja grafa Cdrveta3 u PROLOG-jeziku. Svaka od varijanata mora da bude prvenstveno prilagodena problemu. U zavisnosti od izabrane varijante su i predikati koji omoguduju manipulaciju tako predstavljenim grafovima ili drvetima.
3. PREDSTAVLJANJE NEKIH UOBIČAJENIH PROGRAMSKIH STRUKTURA U PROLOG JEZIKU
if-then-else Cif-therO struktura se javlja u formi:
if uslov then naredbal else naredba2
ili
if uslov then naredba.
Prvi oblik se u PROLOG-jeziku implementira
kao:
if_then_elseCUslov,Naredbal,Naredba23: -Uslov,!, Naredbal.
if_then_elseCUslov,Naredbal,Naredbaa3:-Nar edba2.
ili:
i f_then_elseC Uslov,Naredbal,Naredba33:-C C Uslov,!,Nar edbal3;Nar edba23.
Ovde su Uslov, Naredbal i Naredba2 promenljive koje se postavljaju na imena predikata koji opisuju traženi uslov i odgovarajude naredbe.
U drugom obliku Cif-then3 se Javljaju problemi u slučaju neispunjenja uslova. Tada se mora obrati ti pažnja na to da predikat bude zadovoljen i u slučaju da postavljeni uslov ni je ispunjen, poŠto bi pad predikata mogao da prouzroči i neizvršenje programa. Tako bi odgovarajudi predikat imao oblik:
if_thenCUslov,Naredba3: -Uslov,!, Naredba. if_then.
ili:
if_thenCUslov,Naredba3: -
CCUslov,!,Naredba};true3.
44
OCito Je da se ovakve strukture mogu dalje usložnjavati i da se na sliCan naCin može predstaviti i naredba višestrukog grananja C case naredba u PASCAL-jezi ku).
while-do petlja ima oblik:
while uslov do naredba.
Ukoliko petlja nije beskonaCna,	uslov je funkcija argumenata koji menjaju svoje
vrednosti unutar ciklusa tokom	izvrSenja naredbe. Jedan od mogudih pristupa je da se ova
programska struktura u PROLOG-jeziku	predstavi rekurzivnim reSenjem:
whi1e_doC Us1ov,Nar edba):-notCUslov),!.
while_doCUslov,Naredba):-Naredba,
while doCUslov,Naredba).
svoje nedostatke u reženju programskog memorisanju koje je mehani zma
Ovo rešenje ima rekurzivnom pristupu ciklusa u PROLOG-jeziku i parametara u rekurzivnom pozivu potrebno zbog obezbedenja backtracking-a.
Rešenje može da ima i slededi oblik u kome se koristi sistemski predikat repeat:
while_doCUslov,Naredba):-Uslov,
repeat_whileCNaredba,Uslov).
while_doC_,_).
repeat_whileCNaredba,Uslov}: -repeat, Naredba, notCUslov).
U ovom rešenju je izbegnuto nepotrebno memorisanje parametara u rekurzivnom pozivu koje Je glavni nedostatak prethodno navedenog reSenja.
Komponovane naredbe visokog nivoa u velikim sistemima se javljaju kao poseban problem prilikom izgradnje aplikacija u PROLOG-jeziku. Naime, vrlo Cesto se dešava da je potrebno po odredenom redosledu zadovoljiti neke predikate, bez potrebe memorisanja puta kojim se proSlo Cradi eventualnog backtracking-a). U ovakvoj situaciji predikati u PROLOG-jeziku se ne posmatraju u svom deklarativnom, ved prvenstveno u proceduralnom znaCenju. Tako se predikati posmatraju kao procedure koje obavljaju odredenu akciju. Memorisanje puta kojim se prošlo se prekida sistemskim predikatom fail. Parametri koji se prenose izmedu tako posmatranih procedura se mogu upi si vati u bazu podataka PROLOG-Jezika pomodu sistemskih predikata asserta i assertz, kao i Citati i brisati pomodu predikata retract. Primera radi komponovana naredba:
begin naredbal;naredba2;...;naredbak end
bi bila realizovana zadovoljenjem predikata komp_naredba:
komp_naredba: -naredbal, fail.
komp_naredba:-nar edbaS, fail.
komp_naredba: -naredbak.
Na ovaj naCin Je mogude, vodedi raCuna o tome kada Je potreban pojedini predikat u svom proceduralnom, a kada u deklarativnom znaCenJu, izgraditi dosta velike sisteme koji imaju i proceduralne delove.
4. PRIMER PROCEDURALNOG PROGRAMIRANJA U PROLOG-JEZIKU - MNOŽENJE MATRICA
KlasiCan proceduralni problem je izrada programa za množenje matrica. Neka su matrice a i b date u obliku Cinjeni ca u PROLOG-jeziku, na
naCin koji je naveden predstavljanje nizova:
vrednostCaCl,1),Vali).
tekstu
vr ednostC aC 1, M) , Val M) vrednostCaCS.l),Va21)
vrednostCaCN, M),VaNM3 vrednostCbCl,1).Vbil)
vrednostCbCl,K),VblK) vrednostCbC2,l),Vb21)
N, M, K postavljene
i na
Program za i formiranje
vr ednos tC bC M, K) , VbMK) .
i neka su promenljive
Vali,. . . ,VaNM.Vbll.....VbMK
konkretne numeriCke vrednosti, množenje tako zadati h matrica odgovarajudih Cinjenica o matrici-rezultatu u bazi podataka ima slededi oblik:
mnozenje_matricaCA,B.C):-
Struktural=. .CA.A1.A2], Struktura2=..CB.A2.B2]. Struktura3=..CC.A1.B2],
vrednostCStruktural,VI), vrednostCStruktura§,V2), element_prodCStruktura3,VI,V2,V), assertzCvrednostCStruktura3, V)), fail.
množenje_matricaC_,_,_) .
element jprodCStruktura3,VI,V2,V):-
retractCvrednostCStruktura3,V3)),!,
V	is V3+V1*V2.
element_prodCStruktura3,Vl,V2,V): -
V	is V1*V2.
Pozivom mnozenje_matricaCa,b,c) u PROLOG bazi podataka se formiraju strukture vrednost koje odgovaraju matrici c koja je rezultat množenja matrica a i b. Koristedi univ-predikat i ne postaviJaJudi promenljive A1.A2 i B2 formiraju se odgovarajude strukture koje odgovaraju onim elementima matrice koji se trenutno množe
45
CStruktural i Struktura25 i koji se trenutno izračunava CStruktura33. Kao elementi ovakvih struktura, nalaze se promenljive koje dobijaju vrednosti koje odgovaraju indeksima matrice. Pomodu tih promenljivih se uspostavlJaju i relacije unutar baze podataka PROLOG-jezika i tirne obezbeduje množenje odgovarajudih članova matrica i upi si vanje rezultata na odgovarajuče mesto. Zadovoljavanjem predikata vrednost dobijaju se konkretne vrednosti za elemente matrica	sa	konkretnim	indeksima.
Zadovoljavanjem predikata element_prod se sračunava proizvod vrednosti dva odgovarajuda elementa matrica i dodaje na ukupan meduzbir pri	izračunavanju	elemenata	u
matrici-rezultatu. Tako izračunata vrednost Cmeduzbir	ili	konačni	element
matrice-proizvoda3 se pomodu sistemskog_ predikata assertz upisuje u bazu podataka PROLOG-jezika.	Nakon ovoga predikat
množenje_matrica pada Csistemski predikat fail3 i pokušava da se ponovo zadovolji postavi jajudi nove vrednosti promenljivih A1.A2 i B2. One su odredene činjenicama vrednost u bazi podataka PROLOG-jezika. Nastavijajudi tako,-- iscrpljujudi skup svih proizvoda elemenata matrica definisanih činjenicom vrednost koji zadovoljavaju relacije odredene u definisanim strukturama, dobija se konačan rezultat. Druga rečenica	koja	definiše	predikat
mnozenje_matrica služi isključivo da bi predikat na kraju bi o zadovoljen.
Interesantno Je primetiti da činjenice o vrednostima elemenata matrice u bazi • podataka ne moraju uopšte biti poredane ni po vrstama ni po kolonama, i da matrice ne moraju biti kompletne Cmogu nedostajati pojedini elementi} da bi bilo izračunato ono Sto se u tom slučaju mo2e izračunati u množenju takvih matrica.
Važno Je takode primetiti da se korišdenjem sistemskog predikata fail može postidi da se neprekidnim ponovnim zadovoljavanjem žel jeni h predikata ponavlja odredena procedura Cposmatrajudi proceduralno značenje tih predikata3. Izmenom nekih elemenata Cupisivanjem ili brisanjem u bazi podataka PROLOG-jezika pomodu asser ta,assertz i retracO može se različito uticati na trajanje tih ponavljanja. Na taj način se mogu dati rešenja u programskim ciklusima, a tirne se i izbegava odgovarajude rekurzivno rešenje koje je nepogodno zbog memorisanja predenog puta.
5. UMESTO ZAKLJUČKA
Ovaj rad ima dve namene. Prva je da programerima koji su početnici u pisanju programa u PROLOG-jeziku omogudi da svoje proceduralne programe lako prevedu u PROLOG-jezik. Ipak se mora naglasiti da tako prevedeni programi nisu najsretnije rešenje. Bez obzira na to dosta velik broj programera razmišlja proceduralno prilikom izrade svojih programa. Na taj način se dolazi i do druge namene rada. Naime, radom se želelo pokazati da se iskusan programer u drugim programskim jezicima, prilikom programiranja	u
PROLOG-jeziku mora osi obodi ti nekih rani je stečenih dogmi u gledanju na pojedine probleme. Lep primer za to je množenje matrica. Uobičajena navika iz drugih programskih jezika
je da procedura bude tačno završena C da ne "padne" tokom izvrSavanja!). U ' vedini programskih jezika se takva mogudnost "pada" ni ne razmatra. "SideM-efekti tokom izvršenja procedure se uglavnom posmatraju kao nepovoljna osobina, pa se ili i zbegavaju, ili upotreblJavaju u ograničenim količinama. Otuda je često miSljenje koje ide linijom manjeg otpora da se "side"-efekat izbacuje iz razmišljanja tokom izrade procedura. 0 "padu" procedure tokom njenog izvršenja se u početku pisanja programa u PROLOG-jeziku uglavnom ne razmišlja. Rešenje koje je dato za problem množenja matrica ilustruje neprestano "padanje" predikata množenje_matri ca Cposmatranog kao procedurah kao i "side"-efekte dobijene tom prilikom Cupis novoizračunatih meduzbirova u bazu podataka PROLOG-jezika pomodu sistemskih predikata assertz i retracO.
Usvajanjem ovakvog načina razmišljanja prilikom pisanja programa u PROLOG-jeziku bitno se doprinosi poboljšanju stila pisanja tih programa, a i efikasnosti njihovog izvršenja.
6. LITERATURA
1.	Bratko, Ivan, Inteligentni -informacijski sistemi, Univerza Edvarda Kardelja v Ljubljani, Fakulteta za elektrotehniko, Ljubljana, 1984
2.	Clocksin, W. F., Melish, C. S. , Programming in Prolog, Springer Verlag, Berlin Heidelberg New York, 1981
3.	Munakata, Toshinori. Procedurally Oriented Programming Techniques in Prolog, IEEE Expert, Summer 1986, str 41-47
4.	Race, Iztok Z., Programska implementacija ekspertnog sistema za dijagnostiku u PROLOG-jeziku, magi starski rad, Univerzi tet u Beogradu, Prirodno matematički fakultet, Matematički fakultet, Beograd, 1988
5.	Sterling, Leon, Shapiro, Ehud, The Art of Prolog: Advanced Programming Techniques, The MIT Press, Cambridge, Massachusetts, London, England, 1986