Wikipedija:Peskovnik

Pozdravljeni v Peskovniku Wikipedije! Na tej strani lahko po mili volji vadite in preizkušate urejanje. Za urejanje kliknite tukaj ali zavihek uredi kodo zgoraj (oziroma uredi za urejanje v VisualEditorju), vnesite spremembe in, ko ste končali, kliknite gumb Shrani stran. Vsebina tu ne bo ostala trajno. Stran na vsake toliko izpraznimo. Prosimo vas, da v peskovnik(-e) ne dodajate avtorsko zavarovane, žaljive ali profane vsebine. Če imate glede Wikipedije kakršna koli vprašanja, jih postavite pod lipo. Hvala! Če ste se registrirali in ste trenutno prijavljeni, lahko tukaj poiščete ali ustvarite svoj lastni peskovnik. Za lažji dostop do osebnega peskovnika kliknite na povezavo »Peskovnik« na vrhu strani (v menuju pod vašim imenom). Če povezave ne vidite, v vaših nastavitvah obkljukajte v razdelku Uporabniški vmesnik vrstico »Moj peskovnik«. Za eksperimentiranje lahko uporabljate tudi predloge X1, X2, X3, X4, X5 in X6.

Več podatkov: Uvod v Wikipedijo Najpogostejša vprašanja Pravila in smernice

Peskovnik

'Prolog je visokonivojski programski jezik, ki temelji na predikatni logiki prvega reda. Njegovo ime je okrajšava za programmation en logique, kar v francoščini pomeni "programiranje v logiki". Prolog je najpomembnejši predstavnik paradigme logičnega programiranja in je tesno povezan z umetno inteligenco (UI) in računalniškim jezikoslovjem. Za razliko od imperativnih jezikov, kot sta C ali Java, ki programerju narekujejo, da opiše natančen postopek (algoritem) za rešitev problema, je Prolog deklarativen jezik. Program v Prologu ni zaporedje ukazov, temveč zbirka dejstev in pravil, ki opisujejo relacije in lastnosti v določenem problemskem svetu. Ta zbirka tvori bazo znanja (ang. knowledge base). Izvajanje programa se sproži z zastavitvijo poizvedbe (ang. query), na katero poskuša sistem odgovoriti z logičnim sklepanjem na podlagi podane baze znanja.

Prolog je bil eden prvih logičnih programskih jezikov in ostaja najbolj priljubljen in razširjen predstavnik te paradigme, z več brezplačnimi in komercialnimi implementacijami. Uporablja se na področjih, kot so ekspertni sistemi, obdelava naravnega jezika, simbolno računanje, avtomatsko dokazovanje izrekov, avtomatizirano načrtovanje in razvoj deduktivnih podatkovnih baz.

Zgodovina

Zasnova in razvoj

Prolog je nastal kot rezultat združitve dveh na videz ločenih raziskovalnih področij v zgodnjih 70. letih 20. stoletja: praktične obdelave naravnega jezika in teoretičnega avtomatskega dokazovanja izrekov. Njegov razvoj je neločljivo povezan z delom dveh ključnih skupin: ene v Franciji in druge v Združenem kraljestvu.

V Marseillu je skupina za umetno inteligenco na Univerzi Aix-Marseille, ki jo je vodil Alain Colmerauer, delala na sistemu za komunikacijo s človekom v francoščini. Njihov cilj ni bil ustvariti nov programski jezik, temveč praktično orodje za obdelavo naravnega jezika. Predhodnik Prologa je bil Colmerauerjev sistem, imenovan Q-systems, ki je bil zasnovan za avtomatsko prevajanje in je temeljil na prepisovanju drevesnih struktur.

Hkrati je Robert Kowalski na Univerzi v Edinburghu razvijal teoretične osnove logičnega programiranja. Njegov ključni prispevek je bila proceduralna interpretacija Hornovih stavkov, ki je pokazala, da se lahko podmnožica predikatne logike uporabi kot učinkovit računski model. Kowalski je skupaj z Donaldom Kuehnerjem razvil tudi metodo sklepanja, imenovano SL-resolucija (Linear resolution with Selection function), ki je postala teoretični temelj izvajalnega mehanizma Prologa.

Do preboja je prišlo, ko sta se ti dve raziskovalni smeri srečali. Leta 1971 je Kowalski obiskal Colmerauerjevo skupino v Marseillu, kar je sprožilo intenzivno izmenjavo idej. Colmerauerjeva ekipa je v SL-resoluciji prepoznala formalni mehanizem, ki so ga potrebovali za svoj sistem, medtem ko je Kowalski v njihovem delu videl praktično uporabo svojih teoretičnih konceptov.

Prvi sistem Prolog je bil razvit poleti in jeseni leta 1972 s sodelovanjem Alaina Colmerauerja in Philippeja Roussela. Ime "Prolog", ki ga je predlagala Rousselova žena Jacqueline, je bilo skovano kot okrajšava za programmation en logique. Prvi tolmač za Prolog sta v programskem jeziku Fortran napisala Gerard Battani in Henri Meloni.

Zasnova Prologa je bila pragmatičen kompromis med logično popolnostjo in računsko učinkovitostjo. Medtem ko so splošni sistemi za dokazovanje izrekov logično popolni, so pogosto prepočasni za praktično uporabo. Colmerauerjeva skupina se je zavestno odločila, da bo sistem omejila na Hornove stavke in uporabila poenostavljeno, linearno strategijo sklepanja. Ta odločitev je žrtvovala popolnost v zameno za predvidljiv in učinkovit izvajalni model, podoben klicanju procedur v tradicionalnih jezikih. Ta kompromis je omogočil, da je Prolog postal praktičen programski jezik in ne le teoretično orodje, hkrati pa je vodil do uvedbe "nečistih" proceduralnih elementov, kot je operator reza, za nadzor nad izvajanjem.

Poznejši razvoj in vpliv

Po začetnem razvoju v Marseillu se je težišče razvoja Prologa preselilo na Univerzo v Edinburghu, kjer je David H. D. Warren razvil prvi učinkovit prevajalnik za Prolog, ki je temeljil na abstraktnem stroju, kasneje poimenovanem Warren Abstract Machine (WAM). Ta razvoj je bistveno izboljšal zmogljivost Prologa in postavil temelje za t. i. "edinburški Prolog", katerega sintaksa je postala de facto standard za večino sodobnih implementacij.

Največji mednarodni zagon je Prolog doživel v 80. letih z japonskim projektom Računalniki pete generacije (Fifth Generation Computer Systems, FGCS). Japonska vlada je vložila ogromna sredstva v desetletni projekt, katerega cilj je bil razvoj računalnikov za umetno inteligenco, ki bi temeljili na masivno paralelnem procesiranju in logičnem programiranju. Prolog in njegove različice so bili izbrani za osrednji jezik tega projekta. Čeprav projekt FGCS ni dosegel vseh svojih ambicioznih komercialnih ciljev, je močno spodbudil raziskave na področju logičnega programiranja in prispeval k razvoju številnih naprednih tehnik.

Zaradi naraščajočega števila različnih dialektov in implementacij se je pojavila potreba po standardizaciji. Leta 1995 je Mednarodna organizacija za standardizacijo (ISO) objavila standard ISO Prolog (ISO/IEC 13211), ki je formaliziral jedro jezika in zagotovil večjo prenosljivost programov med različnimi sistemi.

Logična in deklarativna paradigma

Prolog spada v družino deklarativnih programskih jezikov, kar pomeni, da programer opiše, kaj želi doseči, in ne, kako naj se to izvede. To je v ostrem nasprotju z imperativnimi jeziki (kot so C, Python ali Java), kjer programer specificira natančno zaporedje korakov, ki jih mora računalnik izvesti za rešitev problema.

Osnovna ideja logičnega programiranja je, da program predstavlja formalni opis problema v jeziku logike. Robert Kowalski je to idejo povzel v znameniti enačbi: $Algoritem=Logika+Kontrola$ V idealnem logičnem programiranju programer prispeva del Logika (dejstva in pravila, ki opisujejo problem), medtem ko programski jezik oziroma njegov izvajalni sistem zagotavlja del Kontrola (strategijo iskanja rešitve, tj. kako uporabiti logiko za izpeljavo odgovora).

V praksi pa programiranje v Prologu zahteva razumevanje obeh komponent. Čeprav programer zapiše le logični del, mora biti seznanjen z vgrajenim kontrolnim mehanizmom Prologa – vračanjem (ang. backtracking). Vrstni red pravil in ciljev v pravilih namreč neposredno vpliva na učinkovitost in včasih celo na to, ali bo program našel rešitev. Zaradi tega in zaradi obstoja proceduralnih konstruktov, kot je operator reza (!), se Prolog pogosto opisuje kot jezik, ki ni povsem deklarativen. Učinkovit programer v Prologu mora znati logiko problema zapisati tako, da optimalno vodi vgrajeni iskalni mehanizem.

Sintaksa in osnovni gradniki

Program v Prologu je sestavljen iz zaporedja stavkov (ang. clauses). Vsak stavek se zaključi s piko (.). Osnovni gradnik vseh podatkov in programov v Prologu je term.

Termi

Prolog ima en sam podatkovni tip, imenovan term (ang. term). Vse podatkovne strukture, vključno s preprostimi podatki in kompleksnimi strukturami, so termi. Ločimo štiri osnovne vrste termov:

• Atomi so simbolične konstante, ki predstavljajo določene objekte ali koncepte. Zapisujejo se z malo začetnico in so lahko sestavljeni iz črk, števk in podčrtaja (npr. slovenija, jabolko, oseba_1). Atomi, ki se začnejo z veliko črko, vsebujejo presledke ali druge posebne znake, morajo biti zapisani med enojnimi narekovaji (npr. 'Janez Novak', 'Ljubljana').
• Števila so lahko cela števila (npr. 10, -5) ali realna števila (npr. 3.14).
• Spremenljivke so označevalci za vrednosti, ki med izvajanjem poizvedbe še niso določene. Imena spremenljivk se vedno začnejo z veliko črko ali podčrtajem (npr. X, Oseba, _Rezultat). Posebna spremenljivka je anonimna spremenljivka _, ki se uporablja, kadar nas vrednost spremenljivke ne zanima.
• Sestavljeni termi (ali strukture) so najsplošnejša oblika termov in predstavljajo kompleksne podatkovne strukture. Sestavljeni so iz funktorja (ki je atom) in enega ali več argumentov (ki so prav tako termi), zapisanih v oklepajih. Število argumentov se imenuje arnost strukture. Na primer, knjiga('Martin Krpan', avtor('Fran', 'Levstik')) je sestavljen term s funktorjem knjiga in arnostjo 2.

Posebna primera sestavljenih termov sta:

• Seznami so urejene zbirke elementov. Prazni seznam se zapiše kot [] (kar je atom). Neprazen seznam se interno predstavlja s funktorjem . in arnostjo 2, kjer je prvi argument glava seznama, drugi pa preostanek (rep) seznama. Na primer, seznam [1, 2, 3] je le sintaktični sladkor za zapis '.'(1, '.'(2, '.'(3, []))).
• Nizi so običajno predstavljeni kot seznami znakovnih kod.

Stavki: Dejstva, pravila in poizvedbe

Baza znanja v Prologu je sestavljena iz dveh vrst stavkov: dejstev in pravil. Poizvedbe so način, kako uporabnik interagira z bazo znanja.

• Dejstva (ang. facts) so brezpogojne trditve, ki veljajo v problemskem svetu. Predstavljajo osnovne informacije v bazi znanja. Sintaktično so to stavki brez telesa. Na primer, dejstvo clovek(sokrat). trdi, da je Sokrat človek. To je enakovredno pravilu clovek(sokrat) :- true., kjer true vedno velja.
• Pravila (ang. rules) so pogojne trditve, ki omogočajo sklepanje novih dejstev iz obstoječih. Zapisana so v obliki Glava :- Telo., kar beremo kot "Glava velja, če velja Telo".
  • Glava (ang. head) je en sam sestavljen term.
  • Telo (ang. body) je sestavljeno iz enega ali več ciljev (ang. goals), ki so prav tako sestavljeni termi.
  • Vejica (,) med cilji predstavlja logično konjunkcijo (IN).
  • Podpičje (;) predstavlja logično disjunkcijo (ALI).

Na primer, pravilo smrtnik(X) :- clovek(X). določa, da je X smrtnik, če je X človek.

• Poizvedbe (ang. queries) so vprašanja, ki jih zastavimo sistemu Prolog. Zapisane so s predpono ?- in so sestavljene iz enega ali več ciljev. Sistem poskuša dokazati, da cilji v poizvedbi logično sledijo iz dejstev in pravil v bazi znanja. Na primer, poizvedba ?- smrtnik(sokrat). sprašuje, ali je Sokrat smrtnik.

Mehanizem izvajanja

Izvajalni mehanizem Prologa temelji na dveh ključnih konceptih: unifikaciji in vračanju. Skupaj omogočata avtomatsko iskanje rešitev za zastavljene poizvedbe. Logično gledano, Prolog uporablja metodo sklepanja, imenovano SLD-resolucija.

Unifikacija

Unifikacija (ang. unification) je postopek, s katerim Prolog poskuša poiskati takšno prireditev vrednosti spremenljivkam, da postaneta dva terma enaka. To je več kot le prirejanje vrednosti; je močan mehanizem za primerjavo vzorcev in dekonstrukcijo podatkovnih struktur. Pravila unifikacije so:

1. Če je en term neinicializirana spremenljivka, se ta poveže z drugim termom.
2. Dva atoma ali dve števili se unificirata, če sta enaka.
3. Dva sestavljena terma se unificirata, če imata enak funktor in enako arnost ter če se vsi njuni pripadajoči argumenti rekurzivno unificirajo.

Unifikacija se zgodi implicitno, ko Prolog poskuša najti stavek v bazi znanja, katerega glava se ujema s trenutnim ciljem v poizvedbi. Eksplicitno jo lahko sprožimo z operatorjem =/2. Na primer, poizvedba ?- f(X, b) = f(a, Y). bo uspešna in bo spremenljivki X priredila vrednost a, spremenljivki Y pa vrednost b.

Vračanje

Vračanje (ang. backtracking) je temeljna strategija, s katero Prolog sistematično preiskuje prostor možnih rešitev. Ko Prolog poskuša zadovoljiti cilj, išče v bazi znanja od zgoraj navzdol prvi stavek, katerega glava se unificira s ciljem.

• Če najde takšno ujemanje (točka izbire), si zapomni to mesto in poskuša zadovoljiti cilje v telesu pravila (če obstajajo).
• Če katerikoli cilj spodleti, se sistem samodejno vrne na zadnjo točko izbire, razveljavi vse prireditve spremenljivk, narejene od takrat, in poskusi z naslednjim možnim ujemanjem (naslednjim stavkom v bazi znanja).
• Če so vsi cilji uspešno zadovoljeni, je poizvedba uspela in Prolog vrne najdene vrednosti spremenljivk. Uporabnik lahko nato zahteva iskanje dodatnih rešitev, kar sproži vračanje in iskanje po alternativnih poteh.

Ta mehanizem ustreza globinskemu iskanju po drevesu dokazovanja. Unifikacija in vračanje sta neločljivo povezana: unifikacija omogoča preverjanje posamezne poti v iskalnem drevesu, medtem ko vračanje omogoča prehod na drugo pot, ko se trenutna izkaže za neuspešno. Skupaj tvorita jedro Prologove zmožnosti avtomatskega iskanja rešitev.

Kontrola izvajanja: Rez in negacija

Prolog ponuja tudi mehanizme za eksplicitno kontrolo nad procesom vračanja.

• Rez (ang. cut), zapisan kot !, je poseben cilj, ki vedno uspe, vendar ima pomemben stranski učinek: prepreči vračanje. Ko izvajanje preide rez, se sistem "zaveže" vsem izbiram, narejenim do te točke v trenutnem pravilu, in odreže vse ostale alternativne poti za cilje pred rezom ter alternativna pravila za isti predikat. Uporaba reza lahko bistveno poveča učinkovitost programa, vendar uniči njegovo čisto deklarativno naravo in lahko vodi do težko razumljive kode.
• Negacija kot neuspeh (ang. negation as failure), običajno zapisana kot \+ ali not, je Prologov način za izražanje negacije. Cilj \+ G uspe, če poskus dokazovanja cilja G spodleti. Ta pristop temelji na predpostavki zaprtega sveta (ang. closed-world assumption), ki pravi, da je vse, česar ni mogoče dokazati kot resnično na podlagi dane baze znanja, neresnično.

Primeri programiranja

% === Dejstva: Osnovne informacije ===
% starš(Starš, Otrok).
starš(boris, branko).
starš(ana, branko).
starš(boris, cvetka).
starš(ana, cvetka).
starš(branko, darja).
starš(eva, darja).


moski(boris).
moski(branko).
zenska(ana).
zenska(cvetka).
zenska(darja).
zenska(eva).


% === Pravila: Definiranje novih relacij ===
% X je oče od Y, če je X starš od Y in je X moški.
oče(X, Y) :- starš(X, Y), moski(X).


% X je dedek od Y, če je X oče od Z in je Z starš od Y.
dedek(X, Y) :- oče(X, Z), starš(Z, Y).


% X je prednik od Y, če je X starš od Y (osnovni primer).
prednik(X, Y) :- starš(X, Y).
% X je prednik od Y, če je X starš od Z in je Z prednik od Y (rekurzivni korak).
prednik(X, Y) :- starš(X, Z), prednik(Z, Y).


% === Obdelava seznamov ===
% Element je član seznama, če je glava seznama.
član(Element, [Element|_]).
% Element je član seznama, če je član repa seznama.
član(Element, [_|Rep]) :- član(Element, Rep).


% Združevanje dveh seznamov (append).
% Združevanje praznega seznama z L da L.
sestavi([], L, L).
% Združevanje [G|R] z L da [G|NoviRep], kjer je NoviRep rezultat združevanja R z L.
sestavi([G|R], L, [G|NoviRep]) :- sestavi(R, L, NoviRep).

Primeri poizvedb:

% Kdo je oče od Branka?
?- oče(Oce, branko).
Oce = boris.


% Kdo so vsi predniki Darje?
?- prednik(X, darja).
X = branko ;
X = eva ;
X = boris ;
X = ana ;
false.


% Ali je 'c' član seznama [a, b, c, d]?
?- član(c, [a, b, c, d]).
true.


% Združi dva seznama.
?- sestavi([a, b], [c, d], Rezultat).
Rezultat = [a, b, c, d].

Področja uporabe

Zaradi svoje zasnove, ki temelji na logiki in simbolni manipulaciji, je Prolog še posebej primeren za določena področja računalništva.

• Umetna inteligenca (UI): To je bilo zgodovinsko najpomembnejše področje uporabe Prologa. Njegova sposobnost predstavljanja znanja v obliki pravil in dejstev ga dela idealnega za razvoj ekspertnih sistemov, ki posnemajo sklepanje človeških strokovnjakov. Uporablja se tudi za avtomatizirano načrtovanje, kjer sistem išče zaporedje akcij za dosego cilja, ter za avtomatsko dokazovanje izrekov. Znan primer sodobne uporabe je sistem IBM Watson, ki je Prolog uporabljal za napredno primerjanje vzorcev pri analizi stavčnih struktur naravnega jezika.
• Obdelava naravnega jezika (NLP): Prolog je bil prvotno zasnovan prav za ta namen. Njegova struktura omogoča, da se slovnična pravila zapišejo neposredno kot pravila v Prologu, kar močno poenostavi pisanje razčlenjevalnikov (ang. parsers). Mnoge implementacije Prologa vključujejo poseben formalizem, imenovan slovnice z definitnimi stavki (Definite Clause Grammars – DCG), ki je sintaktični sladkor za pisanje slovnic in se interno prevede v standardne stavke Prologa.
• Podatkovne baze in simbolno računanje: Prolog lahko obravnavamo kot napreden poizvedbeni jezik za deduktivne podatkovne baze, kjer sistem ne vrača le eksplicitno shranjenih podatkov, temveč tudi dejstva, ki jih je mogoče izpeljati s pomočjo pravil. Zaradi svoje zmožnosti manipulacije s simboli je uporaben tudi na področju simbolne matematike.

Implementacije in dialekti

Skozi leta se je razvilo veliko število implementacij Prologa, od odprtokodnih projektov do visoko zmogljivih komercialnih sistemov. Vsaka implementacija ima svoje prednosti in je pogosto usmerjena v specifične namene uporabe.

Primerjava pogostih implementacij Prologa

Implementacija	Licenca	Glavne značilnosti	Tipična uporaba
SWI-Prolog	Odprtokodna (BSD)	Obsežne knjižnice, podpora za večnitnost, vgrajen spletni strežnik, logično programiranje z omejitvami (CLP), odlično razvojno okolje, velika in aktivna skupnost.	Raziskave, izobraževanje (pogosto na slovenskih univerzah, npr. FRI UL), hitra izdelava prototipov, spletne aplikacije.
SICStus Prolog	Komercialna	Visoka zmogljivost, stroga skladnost z ISO standardom, robustne knjižnice (še posebej za CLP(FD)), enostavna vgradljivost v druge sisteme (C, Java, .NET).	Industrijske in komercialne aplikacije, ki zahtevajo visoko zanesljivost in zmogljivost, kritični sistemi.
GNU Prolog	Odprtokodna (GPL)	Prevajalnik v izvorno (native) kodo, kar omogoča ustvarjanje hitrih, samostojnih izvršljivih datotek. Vključuje učinkovit reševalnik omejitev nad končnimi domenami (CLP(FD)).	Samostojne aplikacije, kjer sta pomembni hitrost izvajanja in majhnost izvršljive datoteke.

Poleg teh obstajajo tudi številne druge implementacije, kot so Ciao Prolog, B-Prolog, ECLiPSe in druge, vsaka s svojimi specifičnimi razširitvami in poudarki.

Razširitve

Osnovni Prolog je bil skozi leta razširjen z dodatnimi zmožnostmi, ki so povečale njegovo izrazno moč in področje uporabe.

• Logično programiranje z omejitvami (Constraint Logic Programming – CLP): Je ena najpomembnejših razširitev Prologa. CLP združuje paradigmo logičnega programiranja z učinkovitimi tehnikami reševanja omejitev. Namesto preproste unifikacije CLP omogoča definiranje in reševanje kompleksnih omejitev nad različnimi domenami, kot so cela števila (CLP(FD)), realna števila (CLP(R)) ali Booleove vrednosti (CLP(B)). To je izjemno uporabno za reševanje kombinatoričnih problemov, kot so razporejanje, optimizacija in dodeljevanje virov.
• Objektno usmerjeno programiranje: Čeprav Prolog v osnovi ni objektno usmerjen, so bili razviti sistemi, ki to paradigmo integrirajo z logičnim programiranjem. Najbolj znan primer je Logtalk, ki je objektno usmerjena razširitev, združljiva z večino implementacij Prologa. Omogoča definiranje objektov, razredov, dedovanja in drugih konceptov, kar olajša strukturiranje večjih programov.

Prolog v Sloveniji

Prolog in logično programiranje imata pomembno vlogo v slovenskem akademskem prostoru. Sta del temeljnih predmetov pri študiju računalništva in informatike na vodilnih slovenskih univerzah.

• Na Fakulteti za računalništvo in informatiko (FRI) Univerze v Ljubljani se študentje srečajo z logičnim programiranjem in Prologom v okviru več predmetov, kjer spoznavajo osnove deklarativnega programiranja in njegove uporabe v umetni inteligenci.
• Tudi na Fakulteti za elektrotehniko, računalništvo in informatiko (FERI) Univerze v Mariboru je logično programiranje del študijskega programa, kar kaže na trajen pomen te paradigme v izobraževanju bodočih računalniških strokovnjakov.

Glej tudi

• Logično programiranje
• SWI-Prolog
• SICStus Prolog
• Mercury
• Answer set programming
• Umetna inteligenca

Zunanje povezave

• Uradna spletna stran SWI-Prolog
• Uradna spletna stran SICStus Prolog
• Uradna spletna stran GNU Prolog
• "Learn Prolog Now!" – priljubljen brezplačen spletni učbenik
• SWISH – spletni urejevalnik in okolje za SWI-Prolog