Prolog (programski jezik)

Prolog (енгл. PROgramming in LOGic) je deklarativan programski jezik namenjen rešavanju zadataka simboličke prirode. Prolog se temelji na teorijskom modelu logike prvog reda. Početkom 1970-ih godina Alain Kolmerauer (енгл. Alain Colmerauer) i Filipe Rousel (енгл. Philippe Roussel) na Univerzitetu u Marselju (енгл. University of Aix-Marseille), zajedno sa Robertom Kovalskim (енгл. Robert Kowalski) sa Odeljka Veštačke Inteligencije (енгл. Department of Artifical Intelligence) na Univerzitetu u Edinburgu (енгл. University of Edinburgh), razvili su osnovni dizajn jezika Prolog.

Nastanak i razvoj

Predistorija:

• 1879. G. Frege - Predikatski račun (sredstvo za analizu formalne strukture cistog misljenja)
• 1915-1936. Gödel, Erban, Skulem, Turing - Osnovi teorije izračunljivosti.
• 1960. M. Foster, T. Elcock, ABSYS (ABerdeen SYStem) - Radi sa tvrđenjima (aksiomama) preko kojih se, nakon postavljanja pitanja, deduktivnim putem generiše odgovor.
• 1965. J.A. Robinson, Metod rezolucije.
• 1971. Pod rukovodstvom A. Colmerauer-a u Marselju kreiran Q-System.
• 1972. Q-System preimenovan u PROLOG. (Saradnici: Ph. Roussel, R. Pasero, J. Trudel)
• 1974. Na kongresu IFIP-a R. Kavalski predstavio PROLOG široj javnosti.
• 1977. D. Warren napravio implementaciju PROLOG-a za DEC-10 u Edinburgu. (Edinburški PROLOG).
• 1981. Seminari u Sirakuzi i Los Anđelesu.
• 1982. Prva međunarodna konferencija o PROLOG-u u Marselju.
• 1983. Japanski projekat o razvoju računara 5. generacije.
• 1993. Završen Japanski projekat razvoja računara 5.generacije.

Osamdesetih godina prošlog veka je postojala relativno mala grupa naučnika koja se bavila računarstvom, oni su verovali da je logičko programiranje najbolji način da se prevaziđe složenost imperativnih jezika, kao i problem proizvodnje velike količine pouzdanih softvera koji su bili potrebni. Postoje dva velika razloga zbog kojih logičko programiranje nije zaživelo. Prvi razlog, programi napisani u logičkom programskom jeziku nisu dovoljno efikasni kao programi napisani u nekom ekvivalentnom imperativnom jeziku. Drugi razlog, utvrđeno je da je oblast primene relativno mala. Postoji verzija Prolog-a koja podržava objektno-orijentisano programiranje, Prolog++ (Moss, 1994).

Osnovni pojmovi

Atomičke formule

Skup atomičkih formula nad signaturom L = (Σ, Π, ar) i skupom promenljivih V je skup za koji važi:

• logičke konstante > i ⊥ su atomičke formule;
• ako je p predikatski simbol za koji je ar(p) = n i t1 , t2 , ... , tn su termovi,

onda je p(t1, t2, ..., tn) atomička formula.

Dobro zasnovane formule (ili samo formule)

Skup dobro zasnovanih formula nad signaturom L = (Σ, Π, ar) i skupom promenljivih V je skup za koji važi:

• svaka atomička formula je dobro zasnovana formula;
• ako je A dobro zasnovana formula, onda je i (¬A) dobro zasnovana

formula;

• ako su A i B dobro zasnovane formule, onda su i (A ∧ B), (A ∨ B),

(A ⇒ B) i (A ⇔ B) dobro zasnovane formule;

• ako je A dobro zasnovana formula i x je promenljiva, onda su ((∀x)A)

i ((∃x)A) dobro zasnovane formule.

• Dobro zasnovane formule se mogu dobiti samo konačnom primenom

prethodnih pravila.

• Literal je atomička formula ili negacija atomičke formule.
• Klauza je disjunkcija literala.
• Pod terminom izraz podrazumevaju se termovi i (dobro zasnovane) formule.

O Prolog-u

To je deklarativan programski jezik namenjen rešavanju zadataka simboličke prirode. Pogodan za:

• podršku relacionim bazama podataka,
• rešavanje problema matematičke logike,
• rešavanje apstarktnih problema,
• razumevanje prirodnih jezika,
• automatizaciji u projektovanja,
• simboličko resavanje jednačina,
• razne oblasti veštačke inteligencije.

U Prolog-u se opisuju objekti i relacije među njima. Pošto je akcenat na relacijama reč je o relacionom programskom jeziku. Zasnovan je na jednobraznoj strukturi podataka- term (ne pravi se razlika između programa i podataka).

Program u Prolog-u je skup tvrđenja koja predstavljaju:

• činjenice o nekim objektima ili
• pravila koja pokazuju kako je rešenje povezano sa datim činjenicama tj. kako se iz njih izvodi.

Programiranje u Prolog-u sastoji se u:

• obezbeđivanju (proglasavanju) cinjenica o objektima i odnosima među njima,
• definisanju nekih pravila o objektima i odnosima među njima,
• formiranju upita (pitanja) o objektima i odnosima među njima.
• Omogucava dijalog korisnika i racunara - interpretativni jezik.

Razne implementacije Prolog-a: BProlog, GNU Prolog, JIProlog, Visual Prolog, SWI Prolog, ...

Prolog je uticao na razvoj raznih programskih jezika: ALF, Fril, Gödel, Mercury , Oz, Ciao, Visual Prolog, XSB, λProlog,....

Sintaksa

U Prologu-u term moze biti konstanta, promenljiva ili struktura. Konstanta može biti atom ili intidžer. Atom može biti string koji se sastoji od slova, cifara i donje crte, a počinje malim slovom, ili string bilo kojih ASCII karaktera ograničen apostrofima. Razlikuju se 4 kategorije slova:

• VSEA:

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

• MSEA:

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

• ADC:

  0, 1, 2, ..., 9

• SZ:

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

Promenljiva je bilo koji string koji se sastoji od slova, cifara i donje crte, a počinje velikim slovom ili donjom crtom (_). Strukture predstavljaju atomične propozicije predikatskog računa, i njihov generalni oblik je uvek isti:

  Funktor (parametar liste)

Konstante

Konstante služe za označavanje konkretnih objekata ili relacija. Konstanta može biti atom ili broj. Atom može biti nad slovima, ciframa i _ (alfanumerički), nad specijalnim znacima (specijalnoznačni), niz slova izmedju apostrofa (apostrofni).

Primeri alfanumeričkih atoma:

  marko, x1, i_ovo_je_atom,  brojJedinica, a11Z.

Primeri onih koji su alfanumerički:

  234xy, novi-beograd,  Promenljiva, _ne.

Primeri specijalnoznačnih:

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

Primeri apostrofnih:

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

Brojevi mogu biti:

• celi

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

• realni

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

Promenljive

Promenljiva je bilo koji string koji se sastoji od slova, cifara i donje crte, a počinje velikim slovom ili donjom crtom (_). Promenljive nisu odredjene tipovima. Dodeljivanje vrednosti, a samim tim i tipa, promenljivoj se naziva instanciranje. Instanciranje traje sve dok se ne završi neki cilj, to podrazumeva dokazivanje ili opovrgavanje tačnosti. Promenljiva kojoj vrednost nije odredjena naziva se neinstancirana. Primeri promeljivih:

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

Anonimna promenljiva je _ . Upotrebljava se kada ime promenljive nije potrebno:

  ?- poseduje (pavle, _ ). 

Ako se javi vise anonimnih promenljivih, one su međusobno nezavisne.

Strukture

Strukture ili predikati se grade od atoma i termova, i njihov generalni oblik je uvek isti:

  Funktor (parametar liste).

Svaku strukturu karakteriše: ime (funktor) i arnost (broj argumenata).

Funktor je bilo koji atom i njegova uloga je da identifikuje strukturu. Parametar liste može biti atom, promenljiva ili neka struktura. Parametar liste ne može biti izraz, recimo ako želimo da izrazimo funkciju koja izračunava apsolutnu vrednost:

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

U drugom slučaju ne bismo smeli da definišemo aps(X, -X), jer je -X izraz.

Strukture se mogu smatrati i objektima, u tom slučaju one dozvoljavaju činjenicama da budu navedene u termovima koji se sastoje od nekoliko povezanih atoma. U ovom slučaju strukture predstavljaju veze medju termovima. Struktura takodje može biti predikat, u kontekstu upita (pitanja). Strukture se javljaju u činjenicama, pravilama i upitima.

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

Komentari

U Prolog-programima se mogu koristiti komentari. Komentar je tekst između graničnika: /* i */ . Primeri:

  /* Ovo je moj prvi Prolog-program */ 

  /* budite oprezni pri koriscenju promenljive _ */ 

Semantika

Činjenice i pravila

Program pisan u Prolog programskom jeziku opisuje odnose, definisane putem klauza. Čist Prolog je ograničen na Hornove klauze. Postoje dve vrste klauza: činjenice i pravila.

Pravila su tvrdjenja o objektima i relacijama izmedju njih.

Pravila se sastoje od:

• Uslovnog dela ili tela (desna strana)
• Zaključka ili glave (leva strana)
• Separatora “:-“ koji ima značenje IF

Pravila su sledećeg oblika:

  Glava :- Telo

I čita se „Glava je tačno ako je Telo tačno“. Telo pravila se sastoji od poziva predikata, i naziva se ciljem pravila. Ugradjeni predikat ,/2 (operator arnosti 2, sa imenom „ , “) označava konjunkciju ciljeva, a ;/2 (operator arnosti 2, sa imenom „ ; “) označava disjunkciju. Konjunkcija i disjunkcija se mogu pojavljivati samo u Telu, ne i u Glavi pravila.

Pravila se mogu definisati rekurzivno, ali se ne smeju koristiti beskonačni ciklusi.

Činjenice su Hornove klauze bez nenegiranih literala. Pomoću činjenica opisuju se svojstva objekata, odnosno relacije medju njima.

Klauze sa praznim telom se nazivaju činjenice.

  mačak(Tom).

Što zači:

  mačak(Tom) :- True

Činjenice su komande u jednoj liniji sa tačkom na kraju:

  majka(jelena, sofija).

Ugradjeni predikat true/0 je uvek tačno.

Uzimajući u obzir prethodnu činjenicu, ako se postavi pitanje:

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

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

Skup činjenica formira bazu činjenica. Prolog činjenice shvata kao neku apsolutnu istinu, aksiome, ne proverava njihovu tačnost.

Većina ugradjenih predikata se, na osnovu njihove prirode, može koristiti u nekoliko različitih pravaca. Na primer, length/2 se može koristiti za odredjivanje dužine liste (length(Lista,L), date liste Lista ) , kao i da izgenerise listu dužine 5 (length(X,5)). Slično, append/3 može se koristiti da nadoveže dve liste (append(ListaA,ListaB,X), date su liste ListaA i ListaB), kao i da podeli listu na dva dela (append(X,Y,Lista), data je lista Lista).

Kao jezik opšte namene, Prolog omogućava mnoge ugradjene predikate za rad sa ulazno/izlaznim jedinicama, koristeći grafiku i druga sredstva za komunikaciju sa operativnim sistemom. Ovakvi predikati nemaju relacijsko značenje, već se samo koriste zbog svojih bočnih efekata. Na primer, predikat write/1 prikazuje term na ekranu.

Pomoću činjenica i pravila dobijaju se tvrdjenja, koja formiraju bazu znanja, na osnovu kojih Prolog vrši zaključivanja i na osnovu kojih daje odgovore.

Upiti

Interpreter pokušava da izvede upit koristeći činjenice i pravila iz baze znanja. Postoje dve vrste odgovora:

1. Yes/No: otac(toma, bojan).
2. Unifikacija/No: otac(X, bojan).

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

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

Unifikacija

Unifikacija (ujednačavanje) je jedna od najvažnijih operacija nad termima. Simbol za ovu operaciju je =. Unifikacija nad termima T i S se vrši na sledeći način:

• Ako su T i S konstante, unifikuju se ako predstavljaju isti objekat (konstantu).
• Ako je S promenljiva, a T proizvoljan objekat, unifikacija se vrši tako što se S-u dodeli T. Obrnuto, ako je S proizvoljan objekat, a T promenljiva, onda T primi vrednost S-a.
• Ako su S i T strukture, unifikacija se može izvršiti ako
  • imaju istu arnost i jednake funktore i
  • sve odgovarajuće komponente se mogu unifikovati.

Primer:

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

Unifikaciju možemo strožije definisati ako uvedemo pojam supstitucije.

Def 1. Supstitucija je preslikavanje između promenljivih i terma. Supstitucije se sastoji iz konačnog broja pravila preslikavanja oblika x → a ili y → f(a).

Def 2. (Primena supstitucije) Ako je σ oznaka za supstituciju, a t oznaka za term, onda se primena supstitucije σ na term t definiše na sledeći način: tσ

Prethodna operacija se ostvaruje tako što prođemo kroz argumente funkcije tražeći promenljive koje imaju odgovarajuća pravila zamene u supstituciji i zamenjujući ih supstitucionim termom. To znači, ako je: σ = { x → h(a) , y → b} i t=f(x,g(y),z), tada je tσ = f(h(a), g(b), z). Supstitucija može biti komponovana od primene jedne supstitucije na neku drugu. Primena supstitucije τ na θ ozna čava se sa θτ.

Def 3. (Unifikacija ) Dva terma t i u se mogu unifikovati ako i samo ako postoji supstitucija σ tako da važi tσ = uσ. Rezultujući term je t∪u. Supstitucija σ naziva se unifajer za terme t i u.

Def4. (Uopšten unifajer) Unifajer σ je uopšteni unifajer terma t i u ako ako za neki drugi unifajer θ postoji supstitucija τ tako da važi: σθ = τ.

Izvršavanje programa i primeri

Izvršavanje

Izvršavanje Prolog programa se postiže tako što korisnik postavi neki cilj, tj. upit. Svaki upit Prolog tretira kao cilj koji se treba dostići(ispuniti,ostvariti). Tada mehanizam Prolog programa pokušava da dokaže saglasnost cilja sa bazom znanja. U tom procesu baza znanja se pregleda od vrha ka dnu i moguće su dve situacije:

• Pronadjeno je tvrdjenje koje se uparuje sa postavljenim ciljem(uspesno je ostvaren cilj-uspeh)
• Nije pronadjeno tvrdjenje koje se uparuje sa postavljenim ciljem(cilj nije ispunjen-neuspeh).

U slučaju uspeha, korisnik može zahtevati da se ponovo dokaže saglasnost cilja sa bazom podataka.

Primer:

  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).

Rezultat datog upita koji bi bio tačan:

  ?- polusestra(Jovana,Jelena).
  Yes

Ukoliko želimo da pitamo ko su sve Jovanine sestre:

  ?- polusestra(Jovana,X)
  X = Jelena 

Uvek ćemo dobiti samo prvo rešenje, ukoliko želimo sva rešenja navodimo ";" iza odgovora.

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

"No" na kraju označava da ne postoji više rešenja datog upita.

Hello, world

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

Quick sort

  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).

Literatura

• [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/