Prolog (programovací jazyk)

Prolog

Paradigma	logické programování
Vznik	1972
Autor	Alain Colmerauer a Philippe Roussel
Hlavní implementace	BProlog, GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP-Prolog
Dialekty	ISO Prolog, Edinburgh Prolog

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:^[která?]

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

Je tedy negace výrok o programu, ne o objektu X, ten (ta) X může být hezká – ba překrásná, ale někdo to zapomněl zanést do programu – a už platí not hezka(X), a pro program X hezká není. S negací ve smyslu Prologu se setkáváme v soudnictví: Komu jsme nedokázali, že vrah je, ten vrahem (ve smyslu práva) není.

Porovnání – =

Operátor = uspěje, pokud se oba argumenty povede unifikovat. Porovnání může nabývat čtyř různých významů:

• Pokud je jedna proměnná specifikovaná a druhá nespecifikovaná, stanou se obě proměnné specifikované stejnou hodnotou.
• Pokud jsou obě proměnné specifikované, porovnají se. Přitom integrity a atomy jsou rovny pouze samy se sebou.
• Jsou-li obě proměnné nespecifikovány, stanou se sdílenými. Stane-li se později jedna z nich specifikovanou, bude stejnou hodnotou specifikována i druhá proměnná.
• Pokud se jedná o 2 struktury, pak jsou si rovny, jestliže mají stejný funktor, souhlasí počet komponent a korespondující komponenty jsou si rovny.

Vyčíslení – is

Operátor is zapisuje ve tvaru Číslo is Výraz a vydá true, pokud je Číslo (zpravidla volná proměnná) úspěšně unifikováno s výsledkem Výrazu. Všechny proměnné, které se (případně) vyskytují ve Výrazu, musí být v okamžiku splňování cíle konkretizovány na číselnou hodnotu, jinak dojde k běhové chybě. Obdobně dojde k běhové chybě, pokud je proměnná Číslo již konkretizována na nečíselnou hodnotu. Ukázka funkce operátoru porovnání a vyčíslení na predikátu pro výpočet obsahu kružnice:

obsah_kruhu(Polomer,Obsah) :- Obsah is 3.14 * Polomer * Polomer.
obsah_kruhu2(Polomer,Obsah) :- Obsah = 3.14 * Polomer * Polomer.
?- obsah_kruhu(5,Y).
     Y = 78.5
     Yes
?- obsah_kruhu2(5,Y).
     Y = 3.14*5*5
     Yes

Příklady použití operátorů

?- 2+5 = 5+2.
     no                % tyto dva termy nelze unifikovat
?- 2+5 =:= 5+2.
     yes.              % oba aritmetické výrazy mají stejnou hodnotu
?- X is Y+2.           % běhová chyba - nedefinovaný aritmetický výraz
?- X<3.                % běhová chyba - výraz vlevo nelze vyčíslit
?- X is 2+3, Y is 2*X , Z is 12-3, Y is Z .
     no                % za jednotlivé proměnné se postupně substituovala čísla  X=5 , Y=10 a Z=9,
                       % při vyhodnocování predikátu Y is Z byla tedy proměnná Y již konkretizována a
                       % její hodnota různá od hodnoty proměnné Z
?- X is 7 , X is X+1 .
    no                 % za X substituovalo 7, což není rovno 8

Vstupy a výstupy

Pro pohodlnější práci nabízejí konkrétní implementace Prologu řadu předdefinovaných predikátů, které nazýváme vestavěné predikáty. Jako každý plnoprávný programovací jazyk nabízí i Prolog predikáty pro klasický vstup ze souboru a výstup do souboru. Tyto predikáty už nemají relační význam a přesahují čistě logickou podmnožinu jazyka. Pravdivostní hodnota některých predikátů pro vstup a výstup je vždy true, proto se často používají v kombinaci s predikátem fail.

Příklad notoricky známého programu „Ahoj světe“:

?- write('Ahoj světe').
     Ahoj světe
     Yes

V různých implementacích Prologu jsou i různé vestavěné predikáty. Proto by si každý uživatel měl zjistit, co všechno nabízí implementace, kterou používá. Existují však vestavěné predikáty, které jsou považovány za standardní a jsou obsaženy v (téměř) každé implementaci.

• Ke změně aktuálního vstupu a výstupu slouží predikáty:
  • see(F) -nastaví aktuální vstup ze souboru F
  • seen(F) -uzavře vstupní soubor F a obnoví aktuální vstup z klávesnice ( jako by zavolal see(user) )
  • seeing(-F) -dotaz na aktuální vstupní soubor
  • tell(F) -nastaví aktuální výstup do souboru F
  • told(F) -uzavře výstupní soubor F a obnoví aktuální výstup na obrazovku ( jako by zavolal tell(user) )
  • telling(-F) -dotaz na aktuální výstupní soubor
• Základním typem vstupu (resp. výstupu) v Prologu je vstup (resp. výstup) termů. Slouží k němu predikáty:
  • read(?T) -přečte z aktuálního vstupu jeden term (ukončený tečkou) a unifikuje jej s argumentem T
  • write(+T) -vystoupí instance termu T s právě platnými hodnotami substitucí za proměnné v termu T obsažené
• Dalším typem je vstup a výstup znaků. Slouží k němu např. tyto predikáty:
  • get0(?Z) -přečte jeden znak z aktuálního vstupu, uspěje pokud jej lze unifikovat s termem Z
  • get(Z) -chová se stejně, pouze ignoruje (přeskakuje), řídicí znaky (ASCII < 32)
  • put(Z) -výstup znaku do aktuálního výstupu (ne řídicí znaky)
  • tab(N) -vystoupí N mezer (N přirozené číslo)
  • nl -přechod na novou řádku ( pascalské writeln ) .

Vyhodnocování

Mějme databázi:

muj_pritel(petr).
muj_pritel(marek).
muj_pritel(Pritel) :- markuv_pritel(Pritel),petruv_pritel(Pritel).
markuv_pritel(lenka).
markuv_pritel(jirka).
petruv_pritel(jirka).
petruv_pritel(petra).

Na otázku muj_pritel (Kdo). získáme následující odpovědi:

     Kdo = petr ;
     Kdo = marek ;
     Kdo = jirka ;
     no

Při vyhodnocování se vždy prohledává databáze od shora dolů a na hladinách, kde existují alternativy, se pak pokračuje zleva doprava. O splnění cílů rozhoduje tzv. srovnání (unifikace). Srovná se vždy aktuální cíl s faktem či hlavou pravidla v databázi. Součástí úspěšného srovnání je i případný vznik vazby proměnné na hodnotu. Pokud nedojde k splnění cíle, může Prologovský program použít tzv. navracení (backtracking), při kterém dojde ke zrušení vazeb proměnných na hodnoty a hledání jiného řešení. Po nalezení řešení může navracení vyvolat i uživatel a to stisknutím klávesy středník.

V našem případě se tedy nejprve Prolog pokusí porovnat muj_pritel(Kdo) a muj_pritel(petr). Proměnná Kdo byla nespecifikována, a tak mohla vzniknout vazba na atom petr. Cíl je splněn, Prolog vypíše první odpověď. Pokud máme zájem o vyhledání alternativního řešení, požádáme Prolog o znovusplnění cíle. Tedy použijeme klávesu středník. Prolog zruší vazbu na atom petr, označí si již splněný fakt a pokouší se najít další řešení. Protože databáze se prohledává směrem dolů, dalším porovnáním bude muj_pritel(Kdo) a muj_pritel(marek). Vzniká nová vazba proměnné Kdo a to na atom marek. Cíl je opět splněn, vypíše se druhá odpověď. Po stisku klávesy středník dojde ke zrušení vazby proměnné Kdo na atom marek, označení použitého faktu a hledání dalšího cíle. Při hledání další odpovědi pracuje Prolog s pravidlem a postupuje následovně:

• Nespecifikované proměnné Kdo a Pritel se stanou sdílenými, tzn. obě proměnné mohou mít vazbu na jedinou hodnotu.
• Vyhledá se první Markův přítel, což je v našem případě Lenka a na proměnné Kdo i Pritel se naváže hodnota lenka.
• Poté hledá predikát petruv_pritel(lenka), toto hledání je však neúspěšné.
• Proto se použije navrácení.
• Prolog se vrátí k predikátu markuv_pritel(Pritel), zruší vazbu na proměnnou lenka a snaží se najít jinou vazbu, což v našem případě bude atom jirka.
• Nyní tedy program hledá vazbu na predikát petruv_pritel(jirka), tento predikát najde, čímž splní cíl a je vypsána odpověď Jirka.

Další hledání probíhá podobně a je neúspěšné. Proto je poslední odpověď no. Z výše napsaného vyplývá, že Prolog prohledává strom programu (derivační strom) shora dolů a na hladinách. Tam, kde existují alternativy, pak zleva doprava.

Strategii vyhodnocování můžeme pozměnit pomocí některých vestavěných predikátů:

Selhání – fail

Jedná se o vestavěný predikát, který nemůže být nikdy splněn, tudíž vždy nutí program se vracet. Predikát fail se dá použít například v pravidlech, kde je třeba najít všechna řešení. Například:

muz(pavel).
muz(petr).
zena(petra).
vypis:-muz(X),write(X),nl,fail.

Pravidlo vypis vypíše všechny muže z databáze. Pokud bychom nepoužili predikát fail, vypsalo by se pouze první řešení. Tato technika se často označuje jako konstruktivní selhání.

Řez - !

Řez je vestavěný predikát, značený vykřičníkem '!' , který se používá, pokud chceme zakázat programu či uživateli, aby používal navracení. Často se používá u predikátu, které mají mít nanejvýše jedno řešení – tzv. determinovaný predikát. Řez si lze představit jako jednosměrku pro daný predikát. Pouze pokud se nepodaří najít řešení uvnitř řezu, je predikát opuštěn jako neúspěšný (pomocí portu fail) a řez je odvolán. Řez se používá ze dvou důvodů. Buď kvůli funkčnosti, nebo efektivnosti programu. Proto rozlišujeme dva základní druhy řezu. Zelený a červený řez. Zelený má vliv pouze na efektivnost programu, zatímco bez červeného by program správně nefungoval.

Příklad použití červeného řezu:

max1(X,Y,X):-X>Y,!.
max1(X,Y,Y).

Příklad použití zeleného řezu:

max2(X,Y,X):-X>Y,!.
max2(X,Y,Y):-Y>=X.

Oba predikáty (max1 i max2) vyberou ze dvou čísel maximum. Predikát max2 by sice fungoval i bez řezu, ale pokud by bylo maximem X, dovolil by uživateli pomocí středníku návrat a hledání jiného řešení, které jistě neexistuje. Zde se tedy jedná o zelený řez. U predikátu max1 by mohla nastat podobná situace. Pokud by větší číslo bylo X, dovolil by uživateli návrat a zde by za maximum počítač označil chybně i Y. Predikát by tedy nefungoval správně, a proto se jedná o řez červený.

Řez se často využívá v kombinaci s predikátem selhání. Technika se označuje jako řez-selhání (cut-fail). Například máme-li k dispozici fakta muz(), lze snadno vytvořit predikát zena():

zena(X) :- muz(X), !, fail.
zena(X).

Pokud je X mužem, nemůže být ženou – řez zabrání hledání alternativ pro zena(X) a následné selhání určí výsledek.

Konvence a doporučení

Obecné doporučení:

• používat mnemotechnické identifikátory
• nezapomínat na dekompozici – složité konstrukce rozdělit na více jednodušších
• pokud se nelze vyhnout vedlejším efektům u predikátů, tak je alespoň důkladně okomentovat
• dávat přednost negaci před řezem
• rozepsání pravidla na více řádků je čitelnější nežli logická spojka (;)

Prolog používá obvykle dva typy komentářů:

• /* komentář */
• % komentář až do konce řádku

Při komentování predikátu je vhodné (někdy i nutné) sdělit, jak se mají které argumenty použít. Využívá se proto všeobecně uznávaná konvence, která specifikuje argument umístěním jednoho z těchto tří znaků ( + - ?) před argument. Význam jednotlivých znaků:

- „výstupní argument“ – autor komentáře dává najevo, že v dotazech má na odpovídajícím místě stát nekonkretizovaná proměnná,

+ „vstupní“ parametr – autor komentáře dává najevo, že v dotazech má na odpovídajícím místě stát již konkretizovaný term,

? argument může být jak vstupní, tak i výstupní tj. v dotazech může na odpovídajícím místě stát „cokoli“ .

Příklad vzorově okomentovaného predikátu:

% predek(?Pred,?Pot) Pred je předkem potomka Pot
predek(Rod,Pot):- rodic(Rod,Pot).    % Rod je rodičem potomka Pot
predek(Pred,Pot):-
     rodic(Pred,MlPred),             % Pred je rodičem mladšího
     predek(MlPred,Pot).             % předka Mlpred potomka Pot

Implementace

ISO Prolog

ISO Prolog standard se skládá ze dvou částí. ISO/IEC 13211-1, vydaný v roce 1995, má za cíl standardizovat existující praktiky mnoha implementací základních prvků Prologu. Ujasnil aspekty jazyka, které byly dříve nejednoznačné a vede k přenositelným programům. ISO/IEC 13211-2, vydaný v roce 2000, přidává do standardu podporu pro moduly. Standard je udržován skupinou ISO/IEC JTC1/SC22/WG17. ANSI X3J17 je US Technical Advisory Group pro tento standard.

Kompilace

Kvůli efektivnosti je kód Prologu obvykle kompilován do abstraktního strojového kódu, často ovlivněného register-based sadou instrukcí Warren Abstract Machine (WAM). Některé implementace používají abstraktní interpretaci k odvození informace o typu a módu predikátů v době kompilace nebo kompilují do skutečného strojového kódu pro vysokou výkonnost. Návrh efektivních metod implementace kódu Prologu je oblastí aktivního výzkumu v komunitě logického programování. V některých implementacích jsou užity různé jiné metody zpracování. Mezi některé patří binarizace klauzulí a zásobníkově založené virtuální stroje.

Koncová rekurze

Prolog obyčejně implementuje známou optimalizační metodu zvanou optimalizace koncového volání (tail call optimization (TCO)) pro deterministické predikáty vykazující koncovou rekurzi nebo, obecněji, koncové volání: Rámec zásobníku patřící klauzuli je zahozen před vykonáním volání v koncové pozici. Proto jsou deterministické koncově-rekurzivní predikáty vykonány s konstantním zásobníkovým prostorem jako smyčky v jiných jazycích.

Indexace termů

Nalezení klauzulí unifikovatelných s termem v dotazu je většinou lineární. Indexace termů používá datovou strukturu, která umožňuje sublineární čas vyhledání. Indexace ovlivňuje pouze výkon programu, neovlivňuje sémantiku.

Tabling

Některé Prologové systémy, (BProlog, XSB a Yap), implementují memorizační metodu zvanou tabling, která osvobozuje uživatele od manuálního přechovávání mezivýsledků.

Implementace v hardware

Během projektu Páté Generace Počítačových Systémů probíhaly pokusy o implementaci Prologu do hardwaru s cílem dosažení rychlejšího výkonu s dedikovanými architekturami. Dále má Prolog mnoho vlastností, které dovolují zrychlení skrze paralelní provádění. Novější přístup spočíval ve zkompilování vyhrazených programů Prologu na programovatelné hradlové pole. Nicméně, rychlý vývoj v oblasti hardwaru pro všeobecné účely neustále předstihuje více specializované architektury.

Rozšíření

Z Prologu byly vyvinuty různé implementace, které rozšiřují možnosti logického programování v mnoha směrech. Mezi ně patří typy, módy, CLP, objektově orientované logické programování (OOLP), souběžnost, lineární logika (LLP), funkcionální programování a schopnosti programování logiky vyššího řádu, plus interoperabilita se znalostní bází:

Typy

Prolog je netypový jazyk. Pokusy o přidání typů se datují zpět do 80. let 20. století, a do roku 2008 stále existují pokusy rozšířit Prolog o typy. Informace o typu je užitečná nejen pro typovou bezpečnost, ale také při úvaze nad programem Prologu.

Módy

Syntaxe Prologu nespecifikuje, které argumenty predikátu jsou vstupy a které výstupy. Nicméně tato informace je důležitá a je doporučeno mít tuto informaci mít uvedenu v komentářích. Módy poskytují cenné informace při uvažování o programech prologu a mohou být také použity pro urychlení provedení.

Omezující podmínky

Logické programování s omezujícími podmínkami rozšiřuje Prolog o koncepty z constraint satisfaction. Takový program umožňuje omezení ve tvaru klauzulí, jako například: A(X,Y) :- X+Y>0. Tento přístup je vhodný pro rozsáhlé problémy kombinatorické optimalizace. Tímto je užitečný pro aplikace v průmyslovém prostředí, jako automatizovaná tvorba rozvrhů a plánování výroby. Většina systémů Prologu je dodávána s alespoň jedním constraint solverem pro konečné domény, a často také se solvery pro jiné domény jako racionální čísla.

Programování vyššího řádu

HiLog a λProlog rozšiřují Prolog o vlastnosti programování vyššího řádu. ISO Prolog nyní podporuje vestavěné predikáty call/2, call/3, ... které usnadňují programování vyššího řádu a lambda abstrakce.

maplist(_Cont, [], []).
maplist(Cont, [X1|X1s], [X2|X2s]) :-
   call(Cont, X1, X2),
   maplist(Cont, X1s, X2s).

Objektová orientace

Logtalk je objektově orientovaný logický programovací jazyk, který může užít většinu implementací Prologu jako back-endový kompilátor. Jakožto multi-paradigmový jazyk podporuje jak prototypy, tak i třídy.

Oblog je malé, přenosné, objektově orientované rozšíření Prologu od Margaret McDougall z EdCAAD, University of Edinburgh.

Objlog byl frame-based jazyk kombinující objekty a Prolog II z CNRS, Marseille, Francie.

Grafika

Prologové systémy, které poskytují grafickou knihovnu jsou SWI-Prolog, Visual-prolog a B-Prolog.

Souběžnost

Prolog-MPI je open-source rozšíření SWI-Prologu pro distribuované výpočty přes Message Passing Interface. Existuje více různých souběžných programovacích jazyků Prologu.

Programování webů

Některé implementace Prologu, například SWI-Prolog, podporují server-side programování webů s podporou pro webové protokoly, HTML a XML. Existují také rozšíření pro podporu formátů sémantických webů jako RDF a OWL (Web Ontology Language). Prolog byl také navržen jako client-side jazyk.

Adobe Flash

Cedar je základní interpreter Prologu, který je zdarma. Od verze4 a výše Cedar podporuje FCA (Flash Cedar App). Tímto poskytuje novou platformu k programování v Prologu pomocí ActionScriptu.

Ostatní

• F-logic rozšiřuje Prolog o rámce/objekty pro reprezentaci znalostí.
• OW Prolog byl vytvořen jako odpověď na nedostatek grafiky a rozhraní v Prologu.

Rozhraní k jiným jazykům

Existují frameworky, které dokáží přemostit mezi Prologem a jinými jazyky:

• Logic Server API umožňuje jak rozšíření, tak vložení Prologu do C, C++, Javy, VB, Delphi, .NET, a jakéhokoli jazyku/prostředí, kde je možné volat .dll nebo .so. Je implementováno pro Amzi! Prolog Amzi! Prolog + Logic Server, ale API specifikace mohou být zpřístupněny pro jakoukoli implementaci.
• JPL je obousměrné Java Prolog přemostění, dodávané s SWI-Prologem, umožňující Javě a Prologu vzájemné volání (rekurzivně). Je známo, že má dobrou souběžnost a je pod aktivním vývojem.
• InterProlog, knihovna přemostění mezi Javou a Prologem, implementuje obousměrné volání predikátů/metod mezi oběma jazyky. Java objekty mohou být namapovány na termy Prologu a naopak. Umožňuje vývoj GUI a jiných funkcí v Javě při ponechání logického zpracování ve vrstvě Prologu. Podporuje XSB, SWI-Prolog a YAP.
• Prova poskytuje nativní integraci syntaxe s Javou, agent messaging a reakční pravidla. Pozice Provy je jako rule-based skriptovací (RBS) systém pro middleware. Tento jazyk je průkopníkem v kombinování imperativního a deklarativního programování.
• PROL je embeddable Prolog engine pro Javu. Obsahuje malé IDE a pár knihoven.
• GNU Prolog for Java je implementace ISO Prologu jakožto knihovny Javy (gnu.prolog).
• Ciao poskytuje rozhraní k C,C ++, Javě, a relačním databázím.
• C#-Prolog je interpreter Prologu napsaný v C#. Je možné jej snadno integrovat do C# programů. Charakteristiky: spolehlivý a poměrně rychlý interpreter, rozhraní přes příkazovou řádku, Windows rozhraní, vestavěné DCG, XML-predikáty, SQL-predikáty, rozšířitelný. Kompletní zdrojový kód je volně k dispozici včetně generátoru parserů, který může být použit pro přidání rozšíření pro zvláštní účely.

Externí odkazy

• SWI-Prolog – implementace Prologu pod GNU licencí
• Strawberry Prolog – implementace Prologu
• Tutoriál k Prologu (anglicky, Caly Poly Pomona)
• Bartákův tutoriál k Prologu (anglicky, KTIML MFF UK)
• Úvod do programování v Prologu (česky, KSVI MFF UK)
• Manuál Prologu s řešenými příklady (česky, FIM UHK)
• Přednášky (1. až 5.) a cvičení pro podporu předmětu „Alternativní metody programování“ (česky, FM TUL)
• Artificial Intelligence through Prolog (anglicky, Neil C. Rowe)
• Learn Prolog Now! (anglicky)

Autoritní data	NKC: ph117111 PSH: 12525 BNF: cb11970224v (data) LCCN: sh85107397 NLI: 987007538888605171 SUDOC: 027719774