Programovací jazyk Prolog

Představme si programy v logickém jazyce jako axiomy nějaké logické teorie, ve které se poté můžeme dotazovat na platnost logických formulí. Prolog je příkladem takového jazyka.

Základní částí syntaxe jazyka Prolog jsou predikáty, skládající se z jejich názvu a pevného počtu parametrů (arity). Parametry mohou být atomy, proměnné, či další predikáty. Počet parametrů není daný názvem predikátu; můžeme mít více predikátů se stejným názvem, ale odlišnou aritou. Tudíž, pokud budeme mluvit o konkrétním predikátu, budeme navíc kromě názvu uvádět i jeho aritu, oddělenou lomítkem.

Atomy a predikáty začínají malým písmenem nebo znakem, za predikáty navíc následují závorky, uvnitř kterých najdeme jejich parametry oddělené čárkou. Proměnné začínají velkými písmeny. Příklad predikátu je pak predikat(atom,Promenna), jenž budeme značit predikat/2.

Speciální forma predikátů jsou relace, které mají přiřazený operátor. Ten se pak píše podobně, jako v jiných jazycích. Například relace atom > jinyatom je syntaktickou zkratku za predikát >(atom, jinyatom). V jazyce rovněž najdeme jiné objekty, které můžeme použít jako parametry predikátů. Příkladem takových objektů jsou čísla nebo seznamy.

Jestliže za predikát napíšeme tečku, vytvoříme fakt – axiom, který vždy platí. Libovolný predikát můžeme dále podmínit užitím operátoru :-, za kterým následuje další predikát. Tak dostaneme Hornovskou klauzuli ve tvaru A :- B., jenž odpovídá implikaci B → A. Podmíněným klauzulím budeme říkat pravidla.

Každou klauzuli můžeme rozdělit na hlavu a tělo, kde tělo implikuje hlavu. Pro fakt je pak z definice tělo prázdné. Existují i klauzule s prázdnou hlavou, které mají speciální význam a vyhodnotí se již při překladu.

Rodinné vztahy

Ukažme si nyní způsob užití Prologu přes program, kterým popíšeme rodinné vztahy.

Začneme popisovat fakty. Nejprve popíšeme, že adam, jan, martin, petr a vojtech jsou muži. Dále popíšeme, že alena, martina, petra jsou ženy.

muz(adam).
muz(jan).
muz(martin).
muz(petr).
muz(vojtech).

zena(alena).
zena(martina).
zena(petra).

Zde využíváme nedeterminismus Prologu – jestliže zapíšeme stejný predikát jako hlavu vícekrát a následně se ji pokusíme splnit, pokusí se Prolog splnit každou variantu.

Dále mějme fakta, že někteří lidé jsou rodiči jiných lidí. Takový fakt popíšeme predikátem rodic/2.

% rodic(R, D) :- R je rodicem D.
rodic(adam, martin).
rodic(adam, jan).

rodic(jan, martina).
rodic(alena, martina).

rodic(petra, adam).
rodic(petr, alena).

Nyní chceme tato fakta zkombinovat do složitějších výroků. Započněme pravidlem otcovství. Víme, O je otcem D, jestliže O je rodič D a navíc O je muž. V matematické logice zformalizujeme daný výrok jako rodic(O, D) ∧ muz(O) → otec(O, D). Tento výrok je navíc korektní Hornovskou klauzulí, jelikož A → B je ekvivalentní ¬A ∨ B.

Tuto klauzuli můžeme tedy přepsat do Prologu. Konjunkci predikátů v Prologu zapíšeme jejich oddělením čárkou. Konjunkce rodic/2 a muz/1 bude tělo, zatímco predikát otec/2 bude hlava.

otec(Otec, Dite) :- rodic(Otec, Dite), muz(Otec).
syn(Syn, Rodic) :- rodic(Rodic, Syn), muz(Syn).

Jak se pravidla vyhodnocují? Prolog při pokusu o splnění pravidla používá unifikaci. Ta se pokouší nahradit proměnné takovými predikáty, které se následně pokusí splnit, aby za jednu proměnnou mohl všude dosadit stejný term (de facto jde o unifikaci používanou v rezoluci).

Cvičení: Napište výroky matka/2, dcera/2, prarodic/2 značící, že osoba na první pozici je v daném vztahu s osobou na druhé pozici.

Pokračujme dále. Nechť je výrok sourozenec(X, Y) splněn, jestliže různé osoby X a Y sdílejí alespoň jednoho rodiče. Přímočarým postupem dojdeme k pravidlu sourozenec(X, Y) :- rodic(Z, X), rodic(Z, Y). To ale ještě nestačí. Musíme říci, že X a Y jsou různé osoby. Toho docílíme relací X \= Y značící, že X a Y nejsou unifikovatelné.

sourozenec(X, Y) :- rodic(R, X), rodic(R, Y), X \= Y.

Cvičení: Zapište pravidla pro predikáty bratr/2, stryc/2 a cousin/2 (český výraz bohužel není).

Nakonec bychom radi popsali vztah předka. Víme, že osoba A je předkem S, jestliže je jejím rodičem nebo rodičem jiného předka S.

predek(A, S) :- rodic(A, S).
predek(A, S) :- rodic(A, A2), predek(A2, S).

K zapsaní tohoto pravidla jsme použili rekurzi. Ta se zastaví buď na základním případu, nebo uprostřed vyhodnocování dojde k nesplnění, pak se postupně vrací z rekurze nesplnění. Může se i stát, že se rekurze zacyklí, někdy to i Prolog sám zjistí.

Cvičení: Zapište pravidlo pribuzny(A, B) splněné právě, když dvě různé osoby A a B sdílejí předka.

Spuštění programu a dotazování

Fakta a pravidla jsme zapsali do souboru rodinne-vztahy.pl. Nyní bychom rádi tento soubor zpracovali a začali se dotazovat.

Existují dva způsoby, jak spustit program. První způsob je prostě spustit interpret přímo se souborem, například jako parametr příkazové řádky, přetáhnutím souboru do programu nebo přes asociace souborů (pozor, příponu .pl sdílí i skripty jazyku Perl).

Taktéž můžeme nejprve spustit interpret Prologu a z něj pak načíst program. Toho můžeme docílit napsáním dotazu consult('rodinne-vztahy.pl').. Existuje i zkratka přes dotaz ['rodinne-vztahy.pl'].. Pokud název souboru je korektní atom, můžeme vynechat i apostrofy, též lze vynechat příponu. V případě, že se program nachází v jiném adresáři, můžeme se do něj přesunout pomocí dotazu cd('cesta/do/adresare')..

Po načtení se dostaneme do dotazovací konzole, kde na nás čeká prompt ?-. Zkusme tedy položit jednoduché dotazy bez proměnných.

?- muz(martin).
true.

?- muz(alena).
false.

?- otec(jan, martina).
true.

Protože jsme do dotazu nepřidali žádné proměnné, naší odpovědí je splnitelnost formule. Přidejme tedy do dotazu proměnné.

Při dotazování se může stát, že existuje více variant, kdy je dotaz splněn. V takovém případě se nevrátíme na prompt ?-, ale Prolog bude čekat, zda chceme jinou variantu. Jestliže jinou variantu chceme, stiskneme ;. Jinak dotaz ukončíme ..

?- syn(X, adam).
X = martin ;
X = jan.

?- sourozenec(martin, Y).
Y = jan ;
false.

?- predek(X, jan).
X = adam ;
X = petra ;
false.

Cvičení: Zkuste si napsat další fakta a pravidla a položit na ně vlastní dotazy.