Prolog je logický programovací jazyk. Patří mezi tzv. deklarativní programovací jazyky, ve kterých programátor popisuje pouze cíl výpočtu, přičemž přesný postup, jakým se k výsledku program dostane, je ponechán na libovůli systému. Prolog se snaží o pokud možno abstraktní vyjádření faktů a logických vztahů mezi nimi s potlačením imperativní složky. Prolog je využíván především v oboru umělé inteligence a v počítačové lingvistice (obzvláště zpracování přirozeného jazyka, pro nějž byl původně navržen). Syntaxe jazyka je velice jednoduchá a snadno použitelná právě proto, že byl původně určen pro počítačově nepříliš gramotné lingvisty. Prolog je založen na predikátové logice prvního řádu; konkrétně se omezuje na Hornovy klauzule. Běh programu je pak představován aplikací dokazovacích technik na zadané klauzule. Základními využívanými přístupy jsou unifikace, rekurze a backtracking.
Prolog se dobře hodí pro specifické úlohy, které těží z logických dotazů založených na pravidlech, jako je prohledávání databází, systémy hlasového ovládání a vyplňování šablon.
Historie
Jméno „Prolog“ bylo vybráno Philippem Rousselem jako zkratka z „PROgrammation en LOGique“ (francouzsky 'programování v logice'). Byl vytvořen kolem roku 1972 Alainem Colmerauerem ve spolupráci s Philippem Rousselem, na základě procedurálního výkladu Hornovy klauzule od Roberta Kowalskiho. Prolog v sobě zahrnuje mnoho z automatických odvozujících systémů vyvíjených v letech 1960 až 1970. Přímým předchůdcem Prologu jsou Q-systémy.
Prolog je příklad programovacího jazyka čtvrté generace. Japonský Projekt počítačů páté generace, který začal v roce 1981, si ho vybral za vývojový jazyk a tím zaměřil značnou pozornost na tento jazyk a jeho schopnosti. Od těch dob se Prolog rozvětvil do mnoha oborů, přičemž se vyvíjel jako nové logické jazyky. Mezi těmito druhy Prologu jsou určité rozdíly, část v sémantice, část v syntaxi. Přesto nebývá problém přeorientovat se z jednoho na druhý.
Datové typy Jednotnou datovou strukturou, se kterou Prolog pracuje, je tzv. term – pojem převzatý z formální logiky. Základní členění termů: term struktura jednoduchý term proměnná konstanta číslo atom
Atomy Atomy lze dle konstrukce rozdělit do třech kategorií: řetězce znaků začínající malým písmenem obsahující pouze písmena, číslice a podtržítko – např.: otec franta novy_Clen2 posloupnost znaků uzavřená v apostrofech (některé implementace používají uvozovky) – např.: 'Pepa 26. 6. 2007' 'velký les' atomy skládající se pouze ze speciálních znaků – např.: , ; <*!*> :-)
Čísla Původní Prolog podporoval pouze celá čísla. Řada implementací pracuje s reálnými i racionálními čísly a s neohraničenými celými čísly.
Například: ?- X is 2^200, Y is (3 rdiv 8) + (4 rdiv 9). X = 1606938044258990275541962092341162602522202993782792835301376 Y = 59 rdiv 72
Proměnné Proměnné začínají velkým písmenem nebo podtržítkem a nesmí obsahovat speciální znaky. Vyskytují se v pravidlech, kde popisují účastníky vztahu, nebo v dotazech, kde reprezentují hledané objekty. Rozsah platnosti proměnné je pouze jedna klauzule, stejnojmenná proměnná v sousední klauzuli nemá s touto nic společného, i když je třeba součásti stejného predikátu. Hodnotu získává pomocí srovnávání (unifikace) a po jejím přiřazení se již dále nemění, pokud se použité pravidlo, které ji přiřadilo, neodvolá (backtracking).
Z pohledu interpretu lze proměnné rozdělit na dva typy: volné – jejich hodnota zatím není známá a interpret se ji snaží nalézt vázané – z dřívějších kroků řešení již plyne její hodnota, tedy je s ní svázána
Příklad použití proměnných:
klauzule: rodic(jana,petr). rodic(otto,eva). dite(X,Y) :- rodic(Y,X). dotazy: ?- rodic(X,petr). X = jana ; No ?- dite(X,jana). X = petr ; No
Speciálním typem je tzv. anonymní proměnná. Značí se jako podtržítko a používá se v pravidlech. Její hodnota není podstatná a Prolog ji ve výsledcích nezobrazuje.
Příklad: predikát, zda X je dítě je_dite(X) :- dite(X,_).
Struktury Struktury jsou tvořeny z funktoru a argumentů. Počet argumentů udává aritu struktury. Některé operátory mohou být používány také v infixovém tvaru. Strukturou tedy mohou být i klauzule, kde se jako funktor používá infixový operátor :- .
Příklady: muz(adam). %funktor muz má aritu 1 datum(27,6,2007). %funktor datum má aritu 3 okamzik(datum(27,6,2007),cas(13,54)). %funktor okamzik má aritu 2 prarodic(X,Y) :- rodic(X,Z), rodic(Z,Y).
V jednom programu se mohou vyskytovat dva stejně pojmenované funktory, pokud mají různé arity. Speciálním případem struktur jsou seznamy a řetězce .
Seznamy Seznamy jsou definovány induktivně: Prázdný seznam je označen atomem [ ] , k reprezentaci neprázdného seznamu slouží binární funktor tečka '.' . Neprázdný seznam je tedy tzv. tečkový pár (terminologie pochází z jazyka LISP) .(Hlava,Tělo), kde Hlava je první prvek seznamu a Tělo je seznam tvořený zbývajícími prvky seznamu. Pro zjednodušení zápisu lze použít výčet prvků v hranatých závorkách (oba zápisy jsou ekvivalentní).
Příklad: .(a,.(b,.(c,[ ]))) . [a,b,c] .
Pro práci se seznamy se často využívá operátor '|', který umožňuje přístup k jednotlivým částem seznamu. Seznam lze pak zapsat jako [Začátek|Tělo], kde Začátek je výčet (nikoliv seznam) prvků tvořící začátek definovaného seznamu a Tělo je seznam (nikoliv výčet) tvořící zbytek definovaného seznamu (je-li prázdný, nemusí se uvádět).
Častým zdrojem chyb je právě záměna operátoru '|' a čárky.
Řetězce Řetězce jsou sekvence znaků uzavřené v uvozovkách, které jsou ekvivalentní seznamu (číselných) kódů jednotlivých znaků v místní znakové sadě nebo v Unicode, pokud systém podporuje Unicode.
Příklad: ?- Xs = "Πρόλογ". Xs = [928, 961, 972, 955, 959, 947]
Programování v Prologu Programování v Prologu se výrazně liší od programování v běžných procedurálních jazycích jako například C. Program popisuje vztahy definované pomocí klauzulí. Čistý Prolog se omezuje na Hornovy klauzule, tedy predikátovou logiku prvního řádu. Základem Prologu je databáze klauzulí, které lze dále rozdělit na fakta a pravidla, nad kterými je možno klást dotazy formou tvrzení, u kterých Prolog zhodnocuje jejich pravdivost (dokazatelnost z údajů obsažených v databázi). Nejjednoduššími klauzulemi jsou fakta, která pouze vypovídají o vlastnostech objektu nebo vztazích mezi objekty. Složitějšími klauzulemi jsou pravidla, která umožňují pomocí implikace odvozovat nová fakta. Zapisují se ve tvaru hlavička :- tělo, kde hlavička definuje odvozovaný fakt, tělo podmínky, za nichž je pravdivý, obsahuje jeden či více cílů. Pokud se interpretu podaří odvodit, že tělo je pravdivé, ověřil tím pravdivost hlavičky.
Například lze do databáze uložit fakt, že Monika je dívka: dívka(monika). Poté lze dokazatelnost tohoto faktu prověřit otázkou, na kterou Prolog odpoví yes (ano): ?- dívka(monika). yes. Také se lze zeptat na všechny objekty, o kterých je známo, že jsou dívky (středníkem požadujeme další výsledky): ?- dívka(X). X = monika; no.
Pravidla (závislosti) se zapisují pomocí implikací, např. syn(A,B) :- rodič(B,A), muž(A). Tedy: pokud B je rodičem A a zároveň je A muž, pak A je synem B.
Predikát Predikát lze charakterizovat jako sadu klauzulí se stejným jménem a stejnou aritou. Může obsahovat fakta i pravidla, které fungují jako alternativy – platnost predikátu lze dokázat libovolnou z nich. Pravdivost predikátu vyjadřují dvě logické konstanty – true, fail. Při vyhodnocování pravidel lze využít základní logické operátory: konjunkce (AND) – čárka ',' – pokud některá část selže, další se nevyhodnocují disjunkce (OR) – středník ';' – disjunkci lze také zapsat tak, že pravidlo rozepíšeme na více řádků, např.: raz(X) :- dva(X); tri(X). je totéž co raz(X) :- dva(X). raz(X) :- tri(X).
Rekurze Rekurze v Prologu nahrazuje cykly, tudíž je velmi často používána. Například predikát pro nalezení předka: predek(X,Y) :- rodic(X,Y). predek(X,Y) :- rodic(X,Z), predek(Z,Y). Při používání rekurze je třeba dávat pozor na pořadí klauzulí, které Prolog prochází zleva doprava. Jejich prohození může vést ke snížení efektivity algoritmu nebo až k nekonečnému cyklu. Například prohození klauzulí ve výše uvedeném příkladu by mělo za následek nekonečný cyklus. predek(X,Y) :- predek(X,Z), rodic(Z,Y).
Reverzibilita Funkční programování může být považováno za podmnožinu logického programování, pokud lze funkce uvažovat jako zvláštní případ relací. Právě díky relační povaze vestavěných predikátů, je typicky možné jej používat v několika směrech. Například klasická funkce length, která se používá pro určení délky seznamu, dokáže stejně dobře generovat kostru seznamu požadované délky nebo dokonce kostry seznamu a jejich délky.
Příklad použití length pro generování seznamu (ukazatele na vnitřní proměnné si Prolog značí ve tvaru _Gčíslo) ?- length(Ls, L). Ls = [], L = 0 ;
Ls = [_G358], L = 1 ;
Ls = [_G358, _G361], L = 2
Obdobně lze použít append jednak pro spojení dvou seznamů: ?- append([a,b,c], [d,e], Ls). Ls = [a,b,c,d,e]
stejně tak pro rozdělení jednoho seznamu na dva: ?- length(Xs, 2), append(Xs, Ys, [a,b,c,d,e]). Xs = [a,b] Ys = [c,d,e]
Z toho důvodu poměrně malá knihovna predikátů vystačí na mnoho programů. Další způsob využití predikátů je testování pravdivosti, pokud jsou známy všechny argumenty. Predikát vrací hodnotu Yes, když vztah platí. V ostatních případech No.
?- append([x], [], [x]). Yes
?- append([x], [y], [x]). No
Operátory Operátor je z pohledu Prologu pouze jiný způsob zápisu struktury. Strukturu s funktorem + (běžné sčítání) bychom měli správně zapisovat takto jako strukturu +(A,B). Prolog nám však povoluje i tento infixový zápis A+B.
+Tabulka standardních operátorů operátor význam :- definice pravidla ?- otázka ; logické nebo , logické a = porovnání \= opak = is vyčíslení <, >, =<, >= porovnání ==, \== porovnání bez přiřazení =:=, =\= porovnání s vyhodnocením +, -, *, /, mod, div standardní matematické funkce not, \+ negace
Kromě těchto vestavěných operátorů si lze vytvořit libovolné vlastní operátory. Tyto operátory definujeme následujícím způsobem: :-op(priorita, specifikator, jmeno). Priorita je číselná hodnota, která udává, v jakém pořadí se mají operátory vyhodnocovat, jestliže výraz obsahuje více operátorů. Vyšší číslo znamená nižší prioritu vyhodnocení. Pokud výraz obsahuje operátory se stejnou prioritou, musí program vědět, jakým směrem má při výpočtu postupovat. Proto se v operátoru definuje specifikátor. Specifikátory rozdělujeme podle směru vyhodnocení a postavení vzhledem k operandu následujícím způsobem: Infixový binární operátor: yfx směr vyhodnocení zleva; příkladem použití jsou aritmetické operátory xfy směr vyhodnocení zprava; příkladem je operátor is xfx nemá smysl hovořit o směru vyhodnocení, protože nalevo i napravo mohou být pouze operátory s vyšší vyhodnocovací prioritou; příkladem použití jsou porovnání. Prefixový unární operátor: fx – operátor stojí před operandem; příkladem je operátor not. Lze definovat i postfixový unární operátor: xf – operátor stojí za operandem, ale žádný standardní operátor tento specifikátor nepoužívá.
Standardně definované operátory: :-op(1200, xfx, ':-'). :-op(1200, fx,[ :-, ?-]). :-op(1100, xfy, ';'). :-op(1000, xfy, ','). :-op(700, xfx, [ =, \=, is, <, >, =<, >=, ==, =\=, \==, =:=]). :-op(500, yfx, [ +, -]). :-op(500, fx, [ +, -, not]). :-op(400, yfx, [ *, /, div]). :-op(300, xfx, mod).
Negace – not Negace v Prologu je chápána trochu jinak než v hovoru. V běžné řeči, a především v klasické logice, jsou výrok A i jeho negace not A výroky o témže světě. Výroky „je hezká“ a „není hezká“ jsou hodnocením nějakého objektu. Naproti tomu v Prologu jehezka(X) %je konstatováním vlastnosti objektu X, zatímco jeho negace not jehezka(X) %znamená jen, že z programu nelze odvodit platnost predikátu jehezka(X).