Програмски језик Prolog¶

Развојно окружење¶

Програмски језик Prolog може и да се интерпретира и да се компилира, мада се чешће интерпретира. Популарне савремене имплементације су SWI-Prolog и GNU-Prolog. Ми вам препоручујемо коришћење онлјан окружења за SWI-Prolog (https://swish.swi-prolog.org/).

Основни појмови језика¶

Логичко програмирање и језик Prolog су у тесној вези са математичком логиком. Prolog програм се задаје помоћу базе знања, која садржи чињенице и правила закључивања. Чињенице су атомичке формуле облика:

P(c1, ..., cn).

Ово одговара атомичкој формули \(P(c_1, \ldots, c_n)\) у којој је предикат \(P\) примењен на низ константи \(c_1\) до \(c_n\). На пример, једна чињеница у бази знања може бити:

grk(sokrat).

Приметимо да су и име предиката grk и име sokrat написани малим словима (што није правописно исправно), јер се називи свих предиката и називи свих константи морају писати малим словима.

Правила извођења су облика

H :- B1, ..., Bn.

где су и H и B1 до Bn атомичке формуле облика

Bi(t1, ..., tm)

у којима су термови t1 до tm обично променљиве (мада могу бити и константе).

Свако правило извођења одговара импликацији \(B_1 \wedge \ldots \wedge B_n \Rightarrow H\), тј. клаузули \(\neg B_1 \vee \ldots \wedge \neg B_n \vee H\) (обратите пажњу на необичан смер импликације, тј. на запис \(H \Leftarrow B_1 \wedge \ldots \wedge B_n\). Формула H се назива глава правила, конјункција формула B1 до Bn тело, а симбол :- се назива врат и он представља наопако записану импликацију, тј. логички везник \(\Leftarrow\).

Све променљиве су имплицитно универзално квантификоване. На пример, правила

covek(X) :- grk(X).
smrtan(X) :- covek(X).

означавају реченице \((\forall X)(\mathrm{grk}(X) \Rightarrow \mathrm{covek}(X))\), тј. сви Грци су људи и \((\forall x)(\mathrm{covek}(X) \Rightarrow \mathrm{smrtan}(X))\) тј., сви људи су смртни.

Поред базе знања, последњи део Prolog програма је упит који је облика

?- A1, ..., An

где су A1 до An предикати облика:

Ai(t1, ..., tm)

Упит одговара клаузули \(\neg A_1 \vee \ldots \vee \neg A_n\). која је негација формуле \(A_1 \wedge \ldots \wedge A_n\). Та формула је логичка последица базе знања ако и само ако се додавањем клаузуле упита међу клаузуле базе знања може добити празна формула.

На пример, циљ може бити:

?- smrtan(sokrat).

На овај упит Prolog одговара са true, што значи да је та формула логичка последица базе знања. Заиста, ако је Сократ Грк, ако су сви Грци људи и ако су сви људи смртни, тада је и Сократ смртан.

Дакле Prolog програм (база знања и упит) представља скуп клаузула специјалног облика. Такве клаузуле се називају Хорнове клаузуле и за њих је карактеристично да имају највише један позитиван и све остале негативне литерале. Prolog методом резолуције, уз коришћење унификације изводи празну клаузулу и, ако успе, показује вредности променљивих које су до тога довеле. Захваљујући специјалној структури Хорнових клаузула механизам резолуције је много ефикаснији него у случају коришћења клаузула произвољног облика. Са друге стране, наравно, не може се било која логичка формула изразити у клаузалној форми коришћењем искључиво Хорнових клаузула.

У нашем примеру, клаузуле нашег програма

grk(sokrat).
covek(X) :- grk(X).
smrtan(X) :- covek(X).
?- smrtan(sokrat).

су

Резолуцијом средње две клаузуле добија се клаузула \(\neg \mathrm{grk}(X) \vee \mathrm{smrtan}(X)\), која се онда може резолвирати са првом и четвртом клаузулом (након инстанцијације унификатором \(X=\mathrm{sokrat}\)) и тако извести празна клаузула.

Обратите пажњу на то да Prolog закључке изводи искључиво на основу чињеница и правила, која су екплицитно кодирана кроз базу знања. На пример, одговор на упит

?- smrtan(platon).

је false, јер се додавањем клаузуле \(\neg \mathrm{smrtan}(\mathrm{platon})\) из базе знања не може извести празна клаузула (јер се на основу наше базе знања не може закључити да је Платон Грк).

Ако упит садржи променљиве, Prolog исписује и вредности тих променљивих које доводе до извођења празне клаузуле. На пример, на упит

?- smrtan(X).

Prolog одговара са X = sokrat. Ако после затражимо друга решења, добићемо одговор false, јер друга решења не постоје. Ако би база знања садржала и чињеницу

grk(platon).

Добили бисмо решења X=sokrat, X=platon и након тога одговор false, што значи да, осим ових, нема више решења.

Опишимо и процедуру коју Prolog систем спроводи током израчунавања решења упита ?- smrtan(X). Током решавања текућег упита Prolog покушава да пронађе или чињеницу или главу неког правила која је једнака или се може унификовати са тим упитом. У нашој бази знања се налази правило smrtan(X) :- covek(X)., па се упит даље своди на проналажење X за које важи covek(X) тј. на подупит ?- covek(X) (овим је заправо направљен један корак резолуције). Поново се претражује база знања и проналази се правило covek(X) :- grk(X)., па се упит своди на проналажење X за које важи grk(X) тј. подупит ?- grk(X) (овим је направљен још један корак резолуције). Новом претрагом базе се проналази да се тај упит може унификовати са чињеницом grk(sokrat) уз унификатор X=sokrat. Подсетимо се, унификацијом се проналази замена променљивих вредностима тако да два израза постану једнака – у овом случају се након замене X=sokrat упит ?- grk(X) и чињеница grk(sokrat) изједначавају. И овим је направљен један корак резолуције и добијена је празна клаузула. Зато је упит успешно решен и приказује се решење X=sokrat.

Тражење наредног решења захтева да се вратимо корак уназад (да урадимо бектрекинг) и да потражимо друго решење за упит ?- grk(X). Ако у бази постоји чињеница grk(platon) она се може унификовати са овим упитом, уз унификатор X=platon, па се тако проналази и друго решење. Након захтева за трећим решењем, примећује се да не постоји трећа чињеница нити глава правила извођења која се може унификовати са grk(X). Зато се враћамо корак уназад, примећујемо да не постоји неко друго правило закључивања нити чињеница која би се могла унификовати са упитом ?- covek(X), након чега се исто закључује и за полазни упит ?- smrtan(X) и тако се установљава да нема других решења.

Пример: породично стабло¶

Кодирајмо за почетак које особе чине ужу породицу Симпсон (све су представљене константама) и ког су пола.

musko(homer).
zensko(mardz).
musko(bart).
zensko(liza).
zensko(megi).

Дефинишимо правила којима закључујемо ко су особе у породици Симпсон. Мушке особе су особе и женске особе су особе. Додајемо зато следећа два правила извођења.

% osobe u porodici Simpson su ili muske ili zenske osobe
osoba(X) :- musko(X).
osoba(X) :- zensko(X).

Не заборавимо да импликација важи здесна налево, тј. овде су дата правила \((\forall X)(\mathrm{musko}(X) \Rightarrow \mathrm{osoba}(X))\) и \((\forall X)(\mathrm{zensko}(X) \Rightarrow \mathrm{osoba}(X))\). Уместо два правила могуће је навести и једно правило:

% osobe u porodici Simpson su ili muske ili zenske osobe
osoba(X) :- musko(X) ; zensko(X).

Оператор ; је оператор дисјункције, па је овим задана импликација \((\forall X)(\mathrm{musko}(X) \vee \mathrm{zensko}(X) \Rightarrow \mathrm{osoba}(X))\), која приликом превођења у клаузалну форму даје потпуно исте две клаузуле \(\neg \mathrm{musko}(X) \vee \mathrm{osoba}(X)\) и \(\neg \mathrm{zensko}(X) \vee \mathrm{osoba}(X)\), као и када се особа опише помоћу два независна правила.

Коректност овог правила можемо проверити постављањем упита

?- osoba(X).

Ако је све како треба, требало би да добијемо пет одговора X=homer, X=mardz, X=bart, X=liza, X=megi и затим одговор false, који означава да су ово једина решења.

Проширимо базу знања односима родитељ-дете

roditelj(homer, bart).
roditelj(homer, liza).
roditelj(homer, megi).
roditelj(mardz, bart).
roditelj(mardz, liza).
roditelj(mardz, megi).

Дефинишимо на основу овога предикате otac, majka, sin и cerka.

% osnovna pravila izvodjenja za uzu porodicu
otac(X, Y) :- musko(X), roditelj(X, Y).
majka(X, Y) :- zensko(X), roditelj(X, Y).
sin(X, Y) :- musko(Y), roditelj(X, Y).
cerka(X, Y) :- zensko(Y), roditelj(X, Y).

Прво правило се може тумачити као импликација

тј. ако је X мушко и родитељ је особи Y онда је X отац особи Y. Остала правила се тумаче аналогно.

Можемо проверити ова правила постављањем разних упита. На пример, ко су Хомерове ћерке

?- cerka(homer, X)

Prolog проналази два решења X=liza и X=megi.

Покушајмо да дефинишемо сада релације брат и сестра. Особа X је брат особи Y ако је X мушко и ако имају заједничког родитеља. Желимо, дакле, да кодирамо импликацију

Она није у Хорновом облику, али се лако може проверити да је еквивалентна следећој импликацији, која јесте у Хорновом облику.

На основу овога долазимо до следећих правила:

brat(X, Y) :- musko(X), roditelj(Z, X), roditelj(Z, Y).
sestra(X, Y) :- zensko(X), roditelj(Z, X), roditelj(Z, Y).

Покушајмо да тестирамо ова правила тиме што ћемо проверити коме је све Барт брат. Постављамо упит

?- brat(bart, X)

Prolog проналази тачне одговоре X=liza и X=megi, али проналази и нетачан одговор X=bart, што значи да је Барт сам свој брат. Заиста, то се потпуно уклапа у наше правило (Барт је мушко и има заједничког родитеља као Барт). Да бисмо избегли овај погрешан одговор, потребно је да додамо услов да су променљиве X и Y различите. То можемо изразити помоћу X \= Y. Негација и различитост у Prolog-у су веома суптилна места и треба их добро разумети да се не би правиле грешке, али ћемо се том темом посебно бавити касније. У овом контексту исправно је предикате дефинисати на следећи начин.

brat(X, Y) :- musko(X), roditelj(Z, X), roditelj(Z, Y),  X \= Y.
sestra(X, Y) :- zensko(X), roditelj(Z, X), roditelj(Z, Y), X \= Y.

Приметимо да се решење X=liza проналази два пута и да се решење X=megi такође проналази два пута. То је због тога што се у оба случаја проналази једном заједнички родитељ Хомер, а у другом заједнички родите Марџ (променљива Z може да узме две различите вредности, што се не види, јер се на крају исписују само вредности променљиве Y).

Проширимо сада базу знања чињеницама о Абрахаму и Мони, Хомеровим ма, и Кленсију и Жаклин, Марџиним родитељима.

% baza znanja za babe i dede (po ocu)
musko(abraham).
roditelj(abraham, homer).
zensko(mona).
roditelj(mona, homer).
% baza znanja za babe i dede (po majci)
musko(klensi).
roditelj(klensi, mardz).
zensko(zeklin).
roditelj(zeklin, mardz).

Добијамо упозорење да су чињенице које се односе на предикате musko, zensko и roditelj раштркане по програму. Да бисмо ово упозорење избегли, можемо или да групишемо све чињенице за исти предикат, или да издамо наредбу:

:- discontiguous musko/1, zensko/1, roditelj/2.

Сада једноставно можемо да дефинишемо предикате деда и баба.

deda(X, Y) :- otac(X, Z), roditelj(Z, Y).
baba(X, Y) :- majka(X, Z), roditelj(Z, Y).

Међутим, још интересантније су дефиниције предиката којима се описују преци и потомци, јер су те дефиниције у суштини рекурзивне. Довољно је да дефинишемо, на пример, релацију предак, јер се релација потомак може веома једноставно дефинисати преко релације предак (то јој је заправо супротна релација).

potomak(X, Y) :- predak(Y, X).

Приметимо да је ова дефиниција исправна без обзира на то што још није дефинисана релација predak. Чим она буде дефинисана, моћи ћемо да користимо и дефиницију релације potomak. Наиме, базу знања у идеалном случају треба схватити као скуп правила чијим се коришћењем изводе закључци и редослед навођења правила не би требало да утиче на резултат рада програма (видећемо касније да се од овог идеалног случаја често одступа, да би се постигла већа ефикасност).

Родитељ неке особе јој је сигурно предак. Такође, било који предак њеног родитеља јој је такође предак.

predak(X, Y) :- roditelj(X, Y).
predak(X, Y) :- roditelj(Z, Y), predak(X, Z).

Прво правило, наравно, можемо да тумачимо као

док друго правило можемо да тумачимо као

али и еквивалентно као

Наравно, претходна два правила можемо објединити коришћењем дисјункције.

predak(X, Y) :- roditelj(X, Y) ; roditelj(Z, Y), predak(X, Z).

На овај начин можемо да сазнамо, на пример, све Мегине претке. На упит

?- predak(X, megi)

добијамо одговоре X=homer, X=mardz, X=klensi, X=zeklin, X=abraham и X=mona, при чему редослед одговора зависи од редоследа навођења чињеница у бази знања.

Проширите, за вежбу, базу знања чињеницама о Хомеровом брату и Марџиним сестрама и дефинишите предикате стриц, тетка и ујак.

Нагласимо још једном декларативну природу претходних програма. Ни у једном тренутку није било потребе да описујемо начин извођења закључака. Довољно је било да опишемо услове који треба да важе, а систем је тај који својим уграђеним алгоритмима проналази вредности које задовољавају дате услове. За логичко програмирање се каже да алгоритам обједињава логику и контролу, при чему програмер задаје логику, а контролу извршава систем. Систем може да примени различите стратегије извршавања (доказивања теорема) да би што ефикасније дошао до решења.

Функције¶

За разлику од функционалних, али и императивних и објектно-оријентисаних језика, где програмери углавном дефинишу функције које на основу задатих аргумената израчунавају резултате, основу PrologA чине предикати, тј. релације. Писање функција није директно подржано. Ипак, већ смо видели да се релације постављањем одговарајућих упита могу користити и као функције. На пример, у функционалном језику написали бисмо функцију brat(X) која би као параметар примала особу, а као резултат враћала њеног брата. У прологу смо дефинисали предикат brat(X, Y), а затим смо, на пример, помоћу упита brat(X, liza) могли да „израчунамо“ да је Лизин брат Барт. Могли смо заправо и више од тога. Упитом brat(bart, X) могли смо да израчунамо чији је све брат Барт. Дакле, једна релација, у зависности од тога како се упит поставља нам омогућава више израчунавања, тј. у себи крије више функција. Видећемо да ово често може да буде изненађујуће, тј. да добијамо „гратис“ могућност неких израчунавања која нисмо имали у виду када смо дефинисали релацију.

Дакле, уместо дефинисања функција облика

Prolog допушта дефинисање релација облика

које се онда могу користити као функције тако што се аргументи \(x_1\) до \(x_n\) фиксирају у упиту, а y се зада као променљива чија се вредност аутоматски одређује. При том, сви аргументи релације су симетрични и могуће је да било који од њих (па и више њих истовремено) буду задати као променљиве чије се вредности одређују.

Негација као неуспех¶

Сви предикати са десне стране правила су задавани у позитивном облику (ако изузмемо пример различитости две променљиве, што је негативни облик). Prolog даје подршку за негацију, али је та негација специфична и не понаша се исто као класична логичка негација. Тај облик негације се назива негација као неуспех (енг. negation as failure).

Покушајмо да дефинишемо предикат женско, као негацију предиката мушко.

% Negacija kao neuspeh
zensko(X) :- not(musko(X)).

Очекујемо да се ово може тумачити као импликација \((\forall X)(\neg \mathrm{musko}(X) \Rightarrow \mathrm{zensko}(X))\). Међутим, упити показују на неуобичајено понашање.

?- zensko(homer).  % false
?- zensko(mardz).  % true
?- zensko(X).      % false

Prolog успешно одређује да Хомер није женско, да Марџ јесте женско, међутим, када се упита да наброји женске особе, добија се да не постоји ни једна. Понашање операције not је такво да она успева ако и само ако јој аргумент не успева.

• Упит zensko(homer) се своди на упит not(musko(homer)). Пошто упит musko(homer) успева, упит zensko(homer) не успева и исправно се враћа резултат false.

• Упит zensko(mardz) се своди на упит not(musko(mardz)). Пошто упит musko(mardz) не успева, упит zensko(mardz) успева и исправно се враћа резултат false.

• Упит zensko(X) се своди на упит not(musko(X)). Упит musko(X) успева, при чему се добија вредност X=homer. Међутим, пошто подупит musko(X) успева, упит not(musko(X)), по дефиницији негације, не успева, па самим тим zensko(X) враћа неисправан резултат false.

Негација у Prolog-у има другачије понашање од класичне логичке негације!

Третман негације се може сматрати једном од слабих тачака језика Prolog, јер се у случају употребе негације значење програма не изражава више помоћу јасних правила класичне математичке логике.