Пролог (програмски језик)

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Prolog (енгл. PROgramming in LOGic) је декларативан програмски језик намењен решавању задатака симболичке природе. Пролог се темељи на теоријском моделу логике првог реда. Почетком 1970-их година Алаин Колмерауер (енгл. Alain Colmerauer) и Филипе Роусел (енгл. Philippe Roussel) на Универзитету у Марсељу (енгл. University of Aix-Marseille), заједно са Робертом Ковалским (енгл. Robert Kowalski) са Одељка Вештачке Интелигенције (енгл. Department of Artifical Intelligence) на Универзитету у Единбургу (енгл. University of Edinburgh), развили су основни дизајн језика Пролог.

Настанак и развој уреди

Предисторија:

1879. Г. Фреге - Предикатски рачун (средство за анализу формалне структуре цистог мисљења)
1915-1936. Гöдел, Ербан, Скулем, Туринг - Основи теорије израчунљивости.
1960. M. Фостер, Т. Елцоцк, АБСYС (АБердеен СYСтем) - Ради са тврђењима (аксиомама) преко којих се, након постављања питања, дедуктивним путем генерише одговор.
1965. Ј.А. Робинсон, Метод резолуције.
1971. Под руководством А. Цолмерауер-а у Марсељу креиран Q-Сyстем.
1972. Q-Сyстем преименован у ПРОЛОГ. (Сарадници: Пх. Роуссел, Р. Пасеро, Ј. Трудел)
1974. На конгресу ИФИП-а Р. Кавалски представио ПРОЛОГ широј јавности.
1977. D. Wаррен направио имплементацију ПРОЛОГ-а за ДЕЦ-10 у Единбургу. (Единбуршки ПРОЛОГ).
1981. Семинари у Сиракузи и Лос Анђелесу.
1982. Прва међународна конференција о ПРОЛОГ-у у Марсељу.
1983. Јапански пројекат о развоју рачунара 5. генерације.
1993. Завршен Јапански пројекат развоја рачунара 5.генерације.

Осамдесетих година прошлог века је постојала релативно мала група научника која се бавила рачунарством, они су веровали да је логичко програмирање најбољи начин да се превазиђе сложеност императивних језика, као и проблем производње велике количине поузданих софтвера који су били потребни. Постоје два велика разлога због којих логичко програмирање није заживело. Први разлог, програми написани у логичком програмском језику нису довољно ефикасни као програми написани у неком еквивалентном императивном језику. Други разлог, утврђено је да је област примене релативно мала. Постоји верзија Пролог-а која подржава објектно-оријентисано програмирање, Пролог++ (Мосс, 1994).

Основни појмови уреди

Атомичке формуле уреди

Скуп атомичких формула над сигнатуром L = (Σ, Π, ар) и скупом променљивих V је скуп за који важи:

логичке константе > и ⊥ су атомичке формуле;
ако је п предикатски симбол за који је ар(п) = н и т1 , т2 , ... , тн су термови,

онда је п(т1, т2, ..., тн) атомичка формула.

Добро засноване формуле (или само формуле) уреди

Скуп добро заснованих формула над сигнатуром L = (Σ, Π, ар) и скупом променљивих V је скуп за који важи:

свака атомичка формула је добро заснована формула;
ако је А добро заснована формула, онда је и (¬А) добро заснована

формула;

ако су А и Б добро засноване формуле, онда су и (А ∧ Б), (А ∨ Б),

(А ⇒ Б) и (А ⇔ Б) добро засноване формуле;

ако је А добро заснована формула и x је променљива, онда су ((∀x)А)

и ((∃x)А) добро засноване формуле.

Добро засноване формуле се могу добити само коначном применом

претходних правила.

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

О Пролог-у уреди

То је декларативан програмски језик намењен решавању задатака симболичке природе. Погодан за:

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

У Пролог-у се описују објекти и релације међу њима. Пошто је акценат на релацијама реч је о релационом програмском језику. Заснован је на једнобразној структури података- терм (не прави се разлика између програма и података).

Програм у Пролог-у је скуп тврђења која представљају:

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

Програмирање у Пролог-у састоји се у:

обезбеђивању (прогласавању) цињеница о објектима и односима међу њима,
дефинисању неких правила о објектима и односима међу њима,
формирању упита (питања) о објектима и односима међу њима.
Омогуцава дијалог корисника и рацунара - интерпретативни језик.

Разне имплементације Пролог-а: БПролог, ГНУ Пролог, ЈИПролог, Висуал Пролог, СWИ Пролог, ...

Пролог је утицао на развој разних програмских језика: АЛФ, Фрил, Гöдел, Мерцурy , Оз, Циао, Висуал Пролог, XСБ, λПролог,....

Синтакса уреди

У Прологу-у терм мозе бити константа, променљива или структура. Константа може бити атом или интиџер. Атом може бити стринг који се састоји од слова, цифара и доње црте, а почиње малим словом, или стринг било којих АСЦИИ карактера ограничен апострофима. Разликују се 4 категорије слова:

ВСЕА:

  A, B, C, ..., X, Z

МСЕА:

  a,  b,  c, ...,  x,  z

АДЦ:

  0, 1, 2, ..., 9

СЗ:

  štampajući:   ! "  #  $ % & ' (  ) = - ~ | \ [ ] _ @ + ; * : < > , ? /
  neštampajući :  <TAB>,<CR>, <SPACE>, ...

Променљива је било који стринг који се састоји од слова, цифара и доње црте, а почиње великим словом или доњом цртом (_). Структуре представљају атомичне пропозиције предикатског рачуна, и њихов генерални облик је увек исти:

  Funktor (parametar liste)

Константе уреди

Константе служе за означавање конкретних објеката или релација. Константа може бити атом или број. Атом може бити над словима, цифрама и _ (алфанумерички), над специјалним знацима (специјалнозначни), низ слова измедју апострофа (апострофни).

Примери алфанумеричких атома:

  marko, x1, i_ovo_je_atom,  brojJedinica, a11Z.

Примери оних који су алфанумерички:

  234xy, novi-beograd,  Promenljiva, _ne.

Примери специјалнозначних:

  <--->,  ::=,   :-,  ===>,  ?-, ...

Примери апострофних:

  'Marko Kraljevic', '1Covek', 'Mister-Dzon'...

Бројеви могу бити:

цели

  (235, -45, 0, 73636 -23873, ...)

реални

  (2.35, -0.456,  3.4e-3,  0.123E+10, .)

Променљиве уреди

Променљива је било који стринг који се састоји од слова, цифара и доње црте, а почиње великим словом или доњом цртом (_). Променљиве нису одредјене типовима. Додељивање вредности, а самим тим и типа, променљивој се назива инстанцирање. Инстанцирање траје све док се не заврши неки циљ, то подразумева доказивање или оповргавање тачности. Променљива којој вредност није одредјена назива се неинстанцирана. Примери промељивих:

  X, Y, Ko, Sta, Nepoznata, A11,  I_Ovo, ..
  _takodje,  _123,  _ , .

Анонимна променљива је _ . Употребљава се када име променљиве није потребно:

  ?- poseduje (pavle, _ ).

Ако се јави висе анонимних променљивих, оне су међусобно независне.

Структуре уреди

Структуре или предикати се граде од атома и термова, и њихов генерални облик је увек исти:

  Funktor (parametar liste).

Сваку структуру карактерише: име (функтор) и арност (број аргумената).

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

  aps(X,Y) :- X >= 0 .
  aps(X,Y) :- X < 0, Y = -X.

У другом случају не бисмо смели да дефинишемо апс(X, -X), јер је -X израз.

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

  poseduje (milan, kola).
  voli(ana,X) :- voli(pavle,X).

Коментари уреди

У Пролог-програмима се могу користити коментари. Коментар је текст између граничника: /* и */ . Примери:

  /* Ovo je moj prvi Prolog-program */

  /* budite oprezni pri koriscenju promenljive _ */

Семантика уреди

Чињенице и правила уреди

Програм писан у Пролог програмском језику описује односе, дефинисане путем клауза. Чист Пролог је ограничен на Хорнове клаузе. Постоје две врсте клауза: чињенице и правила.

Правила су тврдјења о објектима и релацијама измедју њих.

Правила се састоје од:

Условног дела или тела (десна страна)
Закључка или главе (лева страна)
Сепаратора “:-“ који има значење ИФ

Правила су следећег облика:

  Glava :- Telo

I чита се „Глава је тачно ако је Тело тачно“. Тело правила се састоји од позива предиката, и назива се циљем правила. Уградјени предикат ,/2 (оператор арности 2, са именом „ , “) означава конјункцију циљева, а ;/2 (оператор арности 2, са именом „ ; “) означава дисјункцију. Конјункција и дисјункција се могу појављивати само у Телу, не и у Глави правила.

Правила се могу дефинисати рекурзивно, али се не смеју користити бесконачни циклуси.

Чињенице су Хорнове клаузе без ненегираних литерала. Помоћу чињеница описују се својства објеката, односно релације медју њима.

Клаузе са празним телом се називају чињенице.

  mačak(Tom).

Што зачи:

  mačak(Tom) :- True

Чињенице су команде у једној линији са тачком на крају:

  majka(jelena, sofija).

Уградјени предикат труе/0 је увек тачно.

Узимајући у обзир претходну чињеницу, ако се постави питање:

  Da li je Tom mačak?
  ?- mačak(Tom)
  Yes

  Ko su mačke?
  ?- mačak(X)
  X=Tom

Скуп чињеница формира базу чињеница. Пролог чињенице схвата као неку апсолутну истину, аксиоме, не проверава њихову тачност.

Већина уградјених предиката се, на основу њихове природе, може користити у неколико различитих праваца. На пример, ленгтх/2 се може користити за одредјивање дужине листе (ленгтх(Листа,L), дате листе Листа ) , као и да изгенерисе листу дужине 5 (ленгтх(X,5)). Слично, аппенд/3 може се користити да надовеже две листе (аппенд(ЛистаА,ЛистаБ,X), дате су листе ЛистаА и ЛистаБ), као и да подели листу на два дела (аппенд(X,Y,Листа), дата је листа Листа).

Као језик опште намене, Пролог омогућава многе уградјене предикате за рад са улазно/излазним јединицама, користећи графику и друга средства за комуникацију са оперативним системом. Овакви предикати немају релацијско значење, већ се само користе због својих бочних ефеката. На пример, предикат wрите/1 приказује терм на екрану.

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

Упити уреди

Интерпретер покушава да изведе упит користећи чињенице и правила из базе знања. Постоје две врсте одговора:

Yес/Но: отац(тома, бојан).
Унификација/Но: отац(X, бојан).

  ?- knjiga(X, ivo_andic, Y, 2000).

  datum(1, mart, 2001), kniga(Naslov, ivo_andric, 256, God)

Унификација уреди

Унификација (уједначавање) је једна од најважнијих операција над термима. Симбол за ову операцију је =. Унификација над термима Т и С се врши на следећи начин:

Ако су Т и С константе, унификују се ако представљају исти објекат (константу).
Ако је С променљива, а Т произвољан објекат, унификација се врши тако што се С-у додели Т. Обрнуто, ако је С произвољан објекат, а Т променљива, онда Т прими вредност С-а.
Ако су С и Т структуре, унификација се може извршити ако
- имају исту арност и једнаке функторе и
- све одговарајуће компоненте се могу унификовати.

Пример:

  ?-datum(D,M,2010)=datum(10, mart,G).
  D=10
  M=mart
  G=2010
  yes

Унификацију можемо строжије дефинисати ако уведемо појам супституције.

Деф 1. Супституција је пресликавање између променљивих и терма. Супституције се састоји из коначног броја правила пресликавања облика x → а или y → ф(а).

Деф 2. (Примена супституције) Ако је σ ознака за супституцију, а т ознака за терм, онда се примена супституције σ на терм т дефинише на следећи начин: тσ

Претходна операција се остварује тако што прођемо кроз аргументе функције тражећи променљиве које имају одговарајућа правила замене у супституцији и замењујући их супституционим термом. То значи, ако је: σ = { x → х(а) , y → б} и т=ф(x,г(y),з), тада је тσ = ф(х(а), г(б), з). Супституција може бити компонована од примене једне супституције на неку другу. Примена супституције τ на θ озна чава се са θτ.

Деф 3. (Унификација ) Два терма т и у се могу унификовати ако и само ако постоји супституција σ тако да важи тσ = уσ. Резултујући терм је т∪у. Супституција σ назива се унифајер за терме т и у.

Деф4. (Уопштен унифајер) Унифајер σ је уопштени унифајер терма т и у ако ако за неки други унифајер θ постоји супституција τ тако да важи: σθ = τ.

Извршавање програма и примери уреди

Извршавање уреди

Извршавање Пролог програма се постиже тако што корисник постави неки циљ, тј. упит. Сваки упит Пролог третира као циљ који се треба достићи(испунити,остварити). Тада механизам Пролог програма покушава да докаже сагласност циља са базом знања. У том процесу база знања се прегледа од врха ка дну и могуће су две ситуације:

Пронадјено је тврдјење које се упарује са постављеним циљем(успесно је остварен циљ-успех)
Није пронадјено тврдјење које се упарује са постављеним циљем(циљ није испуњен-неуспех).

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

Пример:

  majka_dete(Ana, Jovana).
  otac_dete(Pera, Jovana).
  otac_dete(Pera, Jelena).
  otac_dete(Pera, Tamara).
  otac_dete(Mika, Pera).
  polusestra(X,Y) :- roditelj_dete(Z,X), roditelj_dete(Z,Y).
  roditelj_dete(X,Y) :-  otac_dete(X,Y).
  roditelj_dete(X,Y) :-  majka_dete(X,Y).

Резултат датог упита који би био тачан:

  ?- polusestra(Jovana,Jelena).
  Yes

Уколико желимо да питамо ко су све Јованине сестре:

  ?- polusestra(Jovana,X)
  X = Jelena

Увек ћемо добити само прво решење, уколико желимо сва решења наводимо ";" иза одговора.

   ?- polusestra(Jovana,X)
   X = Jelena ;
   X = Tamara ;
   No

"Но" на крају означава да не постоји више решења датог упита.

Хелло, wорлд уреди

  ?- write('Hello world!'), nl.
  Hello world!
  true.
  ?-

Qуицк сорт уреди

  partition([], _, [], []).
  partition([X|Xs], Pivot, Smalls, Bigs) :-
      (   X @< Pivot ->
          Smalls = [X|Rest],
          partition(Xs, Pivot, Rest, Bigs)
      ;   Bigs = [X|Rest],
          partition(Xs, Pivot, Smalls, Rest)
      ).
  quicksort([])     --> [].
  quicksort([X|Xs]) -->
      { partition(Xs, X, Smaller, Bigger) },
      quicksort(Smaller), [X], quicksort(Bigger).

Литература уреди

[1]
Concepts of programming languages, Robert W. Sebesta
Programming Language Pragmatics, Michael L. Scott
Skripta Veštačka inteligencija, Predrag Janičić, Mladen Nikolić
B-Prolog http://www.picat-lang.org/bprolog/download/manual.pdf
http://www.hakank.org/bprolog/