Úvod do logického programovania v jazyku Prolog

Deklaratívne programovanie a logické programovanie

Deklaratívna paradigma programovania predstavuje prístup, v ktorom sa dôraz kladie na špecifikáciu vlastností problému, nie na explicitný opis postupnosti krokov vedúcich k dosiahnutiu výsledku. Programátor formuluje problém prostredníctvom vzťahov, obmedzení a požadovaných vlastností riešenia, pričom samotný proces výpočtu je ponechaný na vykonávací mechanizmus daného jazyka (interpreter alebo prekladač). Naproti tomu imperatívna paradigma vyžaduje explicitnú špecifikáciu riadiaceho toku programu a jednotlivých operácií, ktoré vedú k dosiahnutiu požadovaného cieľa.

Medzi hlavných predstaviteľov deklaratívnej paradigmy patria funkcionálne programovanie, logické programovanie a dopytovacie jazyky, ako je SQL, používané na prácu s relačnými databázami.

Logické programovanie je subparadigma deklaratívneho programovania založená na formálnych princípoch matematickej logiky, konkrétne na Hornovom fragmente predikátovej logiky, kde:

• Program je chápaný ako množina logických tvrdení (klauzúl), ktoré vyjadrujú fakty a pravidlá definujúce vzťahy medzi objektmi danej domény.
• Výpočet je realizovaný prostredníctvom rezolučného dokazovacieho systému, ktorý využíva unifikáciu a systematické spätné prehľadávanie (backtracking) na odvodenie odpovedí na položené otázky.

Riešenie problému v logickom programovaní spočíva vo formulovaní znalostnej bázy pozostávajúcej z faktov a pravidiel. Programátor následne kladie dopyty (queries), pričom systém sa snaží dokázať ich pravdivosť vzhľadom na definovanú množinu tvrdení. Výpočet tak nadobúda charakter logického dokazovania.

PROLOG – ZÁKLADNÝ MODEL

                                +---------------+
                                |  Používateľ   |
                                +---------------+
                                    │
                                    │  ?- dopyt.
                                    ▼
                                +---------------+
                                |  Interpreter  |
                                +---------------+
                                    │
                                    │  pracuje nad
                                    ▼
                                +------------------+ 
                                | ZNALOSTNOU BÁZOU |
                                | (program.pl)     |
                                | fakty + pravidlá |
                                +------------------+
                                    │
                                    │  SLD-rezolúcia
                                    ▼
                                +---------------+
                                |  Výpočet      |
                                +---------------+
                                    │
                                    ▼
                                +---------------+
                                |  Odpoveď      |
                                +---------------+
    

Logické programovanie je vhodné najmä pre úlohy, ktoré možno prirodzene formalizovať pomocou relácií a obmedzení, napríklad:

• problémy s obmedzeniami (constraint satisfaction problems),
• plánovanie a rozhodovanie,
• úlohy umelej inteligencie,
• spracovanie prirodzeného jazyka,
• reprezentácia a spracovanie znalostí.

Najznámejším jazykom logického programovania je Prolog (programming in logic), vyvinutý v 70. rokoch 20. storočia. Pôvodne bol navrhnutý na spracovanie prirodzeného jazyka, avšak postupne sa jeho využitie rozšírilo do viacerých oblastí informatiky vrátane umelej inteligencie, expertných systémov a systémov založených na obmedzeniach.

V súčasnosti existuje viacero implementácií jazyka Prolog. V rámci tohto predmetu budeme pracovať s implementáciou SWI-Prolog, ktorá je Turingovsky úplná, open-source, aktívne vyvíjaná a poskytuje rozsiahlu podporu knižníc a nástrojov pre praktické aplikácie.

Rozdiel medzi deklaratívnym a imperatívnym programovaním

Pre lepšie pochopenie rozdielov medzi jednotlivými paradigmami uvedieme jednoduchý príklad výpočtu faktoriálu. Cieľom nie je optimalizácia riešenia, ale demonštrácia spôsobu, akým jednotlivé paradigmy formulujú problém a jeho riešenie.

Imperatívne programovanie

V imperatívnom programovaní programátor píše kód, ktorý popisuje, ako sa má problém riešiť, krok za krokom.

Napríklad v imperatívnom jazyku C je možné napísať funkciu na výpočet faktoriálu nasledovne:

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

V imperatívnych jazykoch programátor explicitne popisuje, ako sa má faktoriál vypočítať, pomocou cyklu a akumulátora.

Funkcionálne programovanie

Vo funkcionálnej paradigme programovania, ktorá je tiež deklaratívna, je možné napísať funkciu na výpočet faktoriálu v jazyku OCaml nasledovne:

let rec factorial n =
    if n = 0 then 1
    else n * factorial (n - 1)

Vo funkcionálnom programovaní sa riešenie vyjadruje pomocou rekurzie a skladania funkcií bez explicitnej manipulácie so stavom alebo riadiacimi štruktúrami typu cyklus.

Logické programovanie

Na rozdiel od imperatívneho a funkcionálneho prístupu Prolog nedefinuje funkciu v tradičnom zmysle, ale reláciu medzi vstupom a výstupom. Výpočet je realizovaný ako dokazovanie cieľa vzhľadom na definované pravidlá, pričom dopyt predstavuje cieľ, ktorý sa Prolog snaží dokázať.

factorial(0, 1).            % Faktoriál nuly je 1
factorial(N, Result) :-     % Faktoriál N je Result
    N > 0,                  % N musí byť kladné číslo
    N1 is N - 1,            % Vypočítame N-1 pre ďalší krok
    factorial(N1, Result1), % Rekurzívne zavoláme factorial pre N-1
    Result is N * Result1.  % Výsledok je N krát faktoriál N-1

% Dopyt na výpočet faktoriálu 5
?- factorial(5, X).
X = 120.

V Prologu programátor opisuje vzťahy medzi faktami a pravidlami, a necháva na Prologu, aby sa postaral o to, ako dosiahnuť výsledok.

Úvod do jazyka Prolog

Program v Prologu sa skladá z:

• faktov,
• pravidiel,
• dopytov (queries).

Fakty a pravidlá sú množinou predpokladov (Γ), zatiaľ čo dopyt je záver (φ), ktorý chceme dokázať.

Vykonanie logického programu je dôkaz: $$ \Gamma \vdash \varphi $$ že záver (dopyt) je pravdivý vzhľadom na množinu predpokladov (fakty a pravidlá).

Fakt je základná jednotka informácie, ktorá je vždy pravdivá. Fakt môže byť atóm alebo predikát (vlastnosť alebo relácia). Napríklad:

výrok.              % Tento fakt (atóm) je pravdivý, ale neobsahuje informácie
človek(sokrates).   % Tento fakt (vlastnosť - unárny predikát) vyjadruje, že Sokrates je človek
väčší(5, 3).        % Tento fakt (relácia - binárny predikát) vyjadruje, že 5 je väčšie ako 3.

Pravidlo je logický vzťah, ktorý sa odvodzuje z faktov. Napríklad:

smrteľný(X) :- človek(X). % Toto pravidlo vyjadruje, že X je smrteľný, ak X je človek.

Dopyt (query) je otázka, na ktorú chceme získať odpoveď. Napríklad:

?- smrteľný(sokrates).
true.                   

Základná práca s jazykom Prolog a jeho interpreterom

V nasledujúcej sekcii budú demonštrované základné prístupy pre prácu s jazykom Prolog, konkrétne ako načítať program, aktualizovať ho a ako pracovať s dopytmi.

Súbor s programom v Prologu má príponu .pl. Tento súbor obsahuje fakty a pravidlá, ktoré definujú logický program, t.j. našu znalostnú bázu (množinu predpokladov Γ). Prostredníctvom interpretera Prologu môžeme načítať tento súbor a klásť dopyty, ktoré nám umožňujú získať odpovede na základe danej znalostnej bázy.

V prípade SWI-Prologu sa interpreter spustí príkazom swipl v termináli. Po spustení interpretera môžeme načítať program pomocou príkazu:

?- [filename].   % Bez prípony .pl

alebo

?- consult('filename.pl').

Po aktualizácii programu (napr. pridaní nových faktov alebo pravidiel) je potrebné znovu načítať program, aby sa zmeny prejavili. To sa dá dosiahnuť pomocou príkazu:

?- reconsult('filename.pl').

alebo jednoducho znovu načítaním programu pomocou:

?- [filename].    

V SWI-Prologu je možné použiť aj príkaz make. ktorý automaticky znovu načíta všetky súbory, ktoré boli zmenené od posledného načítania.

Pre ukončenie práce s interpreterom SWI-Prolog (swipl) slúži príkaz:

?- halt.

Pre vyčistenie obrazovky v termináli je možné použiť príkaz:

?- shell(clear).   % Pre Linux/macOS
?- shell(cls).     % Pre Windows

Komentáre v Prologu je možné písať dvoma spôsobmi:

• Jednoriadkový komentár sa začína znakom '%'
• Viacriadkový komentár sa uzatvára medzi '/' a '/'

% Toto je jednoriadkový komentár

/*
Toto je viacriadkový komentár
*/

Syntax jazyka Prolog

Základnou jednotkou v Prologu je term, ktorý môže byť:

• atóm,
• číslo,
• premenná,
• zložený term (funktor s argumentmi).

Atómy a čísla sú konštanty.

Atómy

Atómy sú základné symboly, ktoré reprezentujú konkrétne objekty alebo koncepty. Začínajú malým písmenom a môžu obsahovať písmená, číslice, a podčiarkovníky:

  pes, mačka, auto, človek, dom, x, y, z, abc123, aa_b_1

Akýkoľvek reťazec, ktorý je uzavretý v jednoduchých úvodzovkách, je tiež atóm, bez ohľadu na to, aké znaky obsahuje:

  'Mačka je zviera!'

Reťazce, ktoré pozostávajú len zo špeciálnych znakov: +, -, *, =, <, >, :, & ... sú tiež atómy:

  +, -***, <----->

Čísla

Čísla sú špeciálny typ termu v Prologu. Nie sú to atómy. SWI-Prolog podporuje:

• integer (integer),
• float (aproximované reálne čísla),
• rational (presné racionálne čísla – zlomky).

Celé čísla (integer)

Príklady:

  5, -10, 0, 123456

SWI-Prolog podporuje aj veľmi veľké celé čísla (bez pevného limitu veľkosti).

Overenie typu:

?- integer(5).
true.

?- integer(3.14).
false.

Aproximované reálne čísla (float)

Príklady:

  3.14, -0.001, 0.0, 1.0e-5 ...
  1.0e3.   % vedecký zápis (1000.0)

Overenie typu:

?- float(3.14).
true.

Racionálne čísla (rational)

SWI-Prolog podporuje presné racionálne čísla, ktoré sú reprezentované ako zlomky p/q (kde p a q sú celé čísla).

Na ich vytvorenie sa používa aritmetický operátor rdiv.

Príklady:

?- X is 1 rdiv 3.
X = 1 rdiv 3.

?- Y is 2 rdiv 4.
Y = 1 rdiv 2.   % zlomok sa automaticky zjednoduší

rdiv vykonáva presné delenie bez zaokrúhľovania, na rozdiel od operátora /, ktorý vracia float.

Porovnanie:

?- X is 1/3.
X = 0.3333333333333333.   % float – aproximácia

?- Y is 1 rdiv 3.
Y = 1 rdiv 3.             % rational – presná hodnota

Overenie typu:

?- rational(1 rdiv 3).
true.

?- rational(0.5).
false.

Racionálne čísla sú vhodné na presné matematické výpočty, kde je potrebné vyhnúť sa chybám spôsobeným zaokrúhľovaním.

?- X is 0.1 + 0.2 + 0.3.
X = 0.6000000000000001.

?- Y is 1 rdiv 10 + 2 rdiv 10 + 3 rdiv 10.  
Y = 6 rdiv 10.   % presný výsledok. 

?- Z is float(1 rdiv 10 + 2 rdiv 10 + 3 rdiv 10).
Z = 0.6.

Premenné

Premenné reprezentujú neznáme hodnoty. Začínajú veľkým písmenom alebo podčiarkovníkom (_). Príklady platných premenných:

  X, Y, Z, Vek, Osoba, _Temp, _

Premenné v pravidlách a faktoch sú všeobecne kvantifikované na úrovni klauzuly.

Anonymná premenná

Znak " _ " (podčiarkovník samostatne bez úvodzoviek) je anonymná premenná. Každý výskyt " _ " je nová, nezávislá premenná.

Napríklad:

človek(peter).
?- človek(_).
true.

Anonymná premenná "_" sa používa vtedy, keď nás hodnota nezaujíma.

Zložené termy

Zložený term (compound term) pozostáva z:

• funktora (predikátu alebo relácie),
• argumentov,

v tvare:

funktor(argument1, argument2, ..., argumentN)

Funktor je atóm.

Počet argumentov sa nazýva arita. Príklad:

bod(2, 3).
zviera(mačka).
auto(znacka(škoda), farba(cervena)).

V príklade:

bod(2, 3)

• Funktor je "bod"
• Arita je 2

Konvencia zápisu predikátov a termov je:

• Funktor začína malým písmenom.
• Argumenty môžu byť atómy, čísla, premenné alebo ďalšie termy.

Identita predikátu alebo termu je daná dvojicou:

    nazov/aritа

Napríklad:

   bod/2, človek/1, auto/2

bod(1,2) a bod(1,2,3) sú rozdielne termy, pretože majú inú aritu.

Vnorené termy

Argumentom zloženého termu môže byť ďalší term. Napríklad:

strom(uzol(5), uzol(7)).
rodic(otec(jan), dieta(peter)).

Prolog nemá špeciálnu objektovú štruktúru — všetko je reprezentované pomocou termov.

Kontrola typu

Pre kontrolu typu termu Prolog poskytuje vstavané predikáty:

• var(X) - X je voľná premenná
• nonvar(X) - X nie je voľná premenná
• atom(X) - X je atóm
• integer(X) - X je celé číslo
• number(X) - X je číslo
• compound(X) - X je zložený term
• a mnoho ďalších... (viac informácií v dokumentácii SWI-Prolog)

Napríklad:

?- compound(bod(1,2)).
true.
?- compound(5).
false.
?- atom(bod).
true.
?- functor(bod(1,2), F, A).
F = bod,
A = 2.

Fakty

Sú atómy (nulárne predikáty) alebo predikáty (vlastnosti alebo relácie t.j. unárne alebo n-árne predikáty), ktoré sú vždy pravdivé.

Napríklad:

výrok.            % Tento fakt (atóm) je pravdivý, ale neobsahuje informácie
človek(sokrates). % Tento fakt (vlastnosť) hovorí, že Sokrates je človek
menší(3, 5).      % Tento fakt (relácia) hovorí, že 3 je menšie než 5.   

Pravidlá

Pravidlo vyjadruje obrátenú logickú implikáciu. Má tvar:

  hlava :- telo.

Číta sa: "ak platí telo, tak platí hlava". V jazyku logiky sa zapisuje ako implikácia: $$ telo \Rightarrow hlava $$

• Hlava pravidla je term, ktorý sa stane pravdivým, ak sú splnené podmienky v tele pravidla.
• Telo pravidla pozostáva z jednej alebo viacerých podmienok (termov), ktoré musia byť splnené, aby hlava pravidla bola pravdivá.

Príklad pravidla:

smrtelny(X) :- clovek(X).

Čo v jazyku logiky znamená: $$(\forall X) (clovek(X) \Rightarrow smrtelny(X))$$

Dané pravidlo hovorí, že: X je smrteľný, ak X je človek.

Telo pravidla môže obsahovať viac podmienok. Vytvoriť zložené podmienky umožňujú logické spojky:

• Konjunkcia (AND) - používame čiarku (,) Znamená: všetky podmienky musia platiť.
• Disjunkcia (OR) - používame bodkočiarku (;) Znamená: stačí, aby platila aspoň jedna podmienka.

Príklad pravidla s viacerými podmienkami prepojenými prostredníctvom konjunkcie:

stary_rodic(X, Y) :-
    rodic(X, Z),
    rodic(Z, Y).

Čo v jazyku logiky je možné vyjadriť ako nasledujúcu formulu: $$(\forall X) (\forall Y) (\forall Z) (rodic(X,Z) \wedge rodic(Z,Y) \Rightarrow stary\_rodic(X,Y))$$

Príklad pravidla s viacerými podmienkami prepojenými prostredníctvom disjunkcie:

domace_zviera(X) :-
    pes(X);
    macka(X).

Čo v jazyku logiky je možné vyjadriť ako nasledujúcu formulu: $$(\forall X) (macka(X) \vee pes(X) \Rightarrow domace\_zviera(X))$$

Dané pravidlo hovorí, že: X je domáce zviera, ak je pes ALEBO mačka.

Pričom ekvivalentné tvrdenie je možné vytvoriť prostredníctvom dvoch pravidiel:

domace_zviera(X) :- pes(X).
domace_zviera(X) :- macka(X).

Fakt je špeciálny prípad pravidla bez tela. Napríklad:

clovek(sokrates).

V jazyku logiky je možné tento fakt vyjadriť ako: $$ \top \Rightarrow clovek(sokrates), $$ alebo len: $$ clovek(sokrates). $$

Dopyty

Vytvorenej znalostnej báze (faktov a pravidiel) je možné klásť dopyty, ktoré umožňujú získať odpovede na základe v nej definovaných informácií (prostredníctvom interpretera Prologu).

Dopyt sa zadáva pomocou znaku "?-" a následne termu, ktorý chceme dokázať. Napríklad:

?- smrtelny(sokrates).
true. 

Má rovnakú štruktúru ako telo pravidla. To znamená, že môžeme vytvárať zložité dopyty kombináciou viacerých termov pomocou logických spojok. Dopyty môžu obsahovať premenné, ktoré nám umožňujú získať konkrétne hodnoty, ktoré spĺňajú dané podmienky. Napríklad:

?- stary_rodic(X, Y), muz(X). 

Taktiež, je možné zadávať dopyty aj s disjunkciou:

?- domace_zviera(X); zviera(X).   

Rozsah viditeľnosti premennej (scope)

Rozsah viditeľnosti premennej je obmedzený na jednu klauzulu.

Klauzula je jeden fakt alebo jedno pravidlo.

Premenná existuje iba počas vykonávania daného pravidla alebo dopytu. Po jeho skončení zaniká.

p(X) :- q(X).
r(X) :- s(X).

rodic(jan, peter).
rodic(peter, anna).
stary_rodic(X, Y) :-
    rodic(X, Z),
    rodic(Z, Y).

?- rodic(X, Y).
X = jan,
Y = peter ;
X = peter,
Y = anna.

  smrtelny(X) :- clovek(X).

  ?- clovek(X).

  p(X) :- q(X).
  r(X) :- v(X), q(X).

  ?- p(X), r(X).

Vstavané predikáty

Jazyk Prolog poskytuje množinu vstavaných predikátov (built-in predicates), ktoré umožňujú vykonávať základné operácie a kontrolu v rámci programu. Medzi najdôležitejšie patria:

• Equality: =
• Nonequality: \=
• Garantovaný úspech: true
• Garantovaný neúspech: false, fail
• Výstup z programu: write, writeln, format
• Pomoc: help

Rovnosť (=)

Operátor "=" je predikát rovnosti. Zápis:

  X = Y

je ekvivalentný zápisu:

  =(X, Y)

"=" je iba infixová (operátorová) forma predikátu =/2.

Tento predikát nevykonáva aritmetický výpočet, ale vykonáva unifikáciu termov.

Napríklad:

?- X = 5.
X = 5.

?- 5 = 5.
true.

?- 5 = 6.
false.

?- bod(X,2) = bod(1,Y).
X = 1,
Y = 2.

?- 2+3 = 5.
false.

Nerovnosť (\=)

Operátor "\=" je predikát nerovnosti.

Zápis:

  X \= Y

je ekvivalentný zápisu:

  \=(X, Y)

Tento predikát zlyhá, ak sa termy unifikujú, a uspeje, ak sa termy unifikovať nedajú.

Napríklad:

?- 5 \= 6.
true. 

?- 5 \= 5.
false.

?- bod(X,2) \= bod(1,Y).
false.

?- bod(X,2) \= bod(X,3).
true.

?- 2+3 \= 5.
true.

true

Predikát true vždy uspeje.

?- true.
true.

false a fail

Predikáty false a fail vždy zlyhajú.

?- false. 
false.

?- fail.
false.

Používajú sa najmä v riadení toku programu. Podrobnejšie informácie o riadení toku programu a využití predikátov true, false a fail budú predstavené v nasledujúcich prednáškach.

Výstup z programu

Pre výstup z programu knižnice jazyka Prolog obsahujú viacero predikátov, ktoré umožňujú vypísať informácie na obrazovku. Medzi najdôležitejšie patria:

• write(Term) - vypíše term bez zalomenia riadku
• writeln(Term) - vypíše term a pridá nový riadok
• format(...) - formátovaný výstup
• nl - vypíše nový riadok

?- write(ahoj).
ahoj
true.

Pomoc

Vstavaný predikát help poskytuje prístup k nápovede a dokumentácii v rámci SWI-Prologu. Je možné ho použiť na získanie informácií o konkrétnych predikátoch a funkciách.

Napríklad:

?- help(length).

length(?List, ?Length)                                                 [ISO]
    True if Length represents the number of elements in List. This predicate
    is a true relation  and can  be used  to find  the length  of a  list or
    produce a list (holding variables)  of length  Length. The  predicate is
    non-deterministic, producing  lists of  increasing length  if List  is a
    partial list and Length is a variable.

        ?- length(List,4).
        List = [_27940,_27946,_27952,_27958].
        
        ?- length(List,Length).
        List = [], Length = 0 ;
        List = [_24698], Length = 1 ;
        List = [_24698,_25826], Length = 2
        ...
...

SLD-rezolúcia ako základ Prologu

Prolog je implementáciou špeciálneho prípadu rezolučnej stratégie, nazývanej SLD-rezolúcia.

Využíva sa na dokazovanie dopytov vzhľadom na množinu faktov a pravidiel definovaných v Prologu. SLD-rezolúcia je založená na dvoch kľúčových konceptoch:

• Hornove klauzuly,
• cieľovo orientované dokazovanie.

1) Hornove klauzuly

Každé pravidlo v Prologu má tvar:

   H :- B1, B2, ..., Bn.

V jazyku logiky sa toto pravidlo zapisuje ako implikacie: $$ (B1 \wedge B2\ \wedge\ ...\ \wedge\ Bn) \Rightarrow H $$ To je tzv. definitívna klauzula (definite clause).

Fakt je špeciálny prípad:

   H.

čo zodpovedá: $$ \top \Rightarrow H $$ Každý Prolog program je množinou Hornových klauzulí, ktoré sú základom pre SLD-rezolúciu.

2) Cieľovo orientované dokazovanie

Dopyt má tvar:

   ?- A1, A2, ..., Ak.

je ekvivalentný zápisu: $$ A1 \wedge A2\ \wedge\ ...\ \wedge\ Ak $$

Prolog sa pokúša dokázať konjunkciu cieľov pomocou postupného odstraňovania jedného cieľa naraz. Pričom SLD rezolučná stratégia používa:

• lineárny dôkazový strom.
• výberový (selektívny) mechanizmus.

3) Výberová stratégia Prologu

Vykonávanie výpočtu v Prologu začína výberom ľavého najvnútornejšieho cieľa.

Napríklad pri cieli:

   ?- A, B, C.

1. Najprv sa rieši A.
2. Po jeho úspechu B.
3. Potom C.

4) Rezolučný krok v Prologu

Majme aktuálny cieľ:

   G = H, A1, A2, ..., An

a pravidlo:

   H :- B1, ..., Bm

potom, pravidlo sa unifikuje s cieľom pomocou unifikátora $θ$ tak, že vznikne nový cieľ (rezolventa):

   (B1, ..., Bm, A2, ..., An)θ

To je jeden rezolučný krok.

5) Operačná sémantika Prologu

Prolog používa:

• SLD-rezolúciu
• prehľadávanie do hĺbky (depth-first search)
• spätné prehľadávanie (backtracking)
• bez occurs-check, to znamená X = f(X) je unifikovateľné.

To znamená:

• nie je garantovaná úplnosť,
• môže dôjsť k nezastaveniu výpočtu.

Occurs-check a jeho vplyv na Prolog

Prolog ignoruje v unifikácii kontrolu "occurs-check" (napr. X = f(X)). Z tohto dôvodu je možné dokazovať tvrdenia, ktoré nie sú logicky platné v klasickej logike prvého rádu.

Rozhodnutie ignorovať occurs-check má historické a praktické dôvody:

• Kontrola occurs-check by pri každom viazaní premennej vyžadovala rekurzívne prehľadanie celého termu, čo by výrazne spomaľovalo unifikáciu.

• Prolog bol navrhnutý ako efektívny praktický jazyk, preto sa používa rýchlejšia unifikácia bez tejto kontroly.

Výsledkom je, že Prolog nepracuje nad doménou konečných Herbrandových stromov, ale nad doménou tzv. racionálnych (cyklických) stromov.

test :- p(X,X).
p(Y,f(Y)).

?- test.
true.

?- p(X,f(X)) = p(g(Y),Y).

    Y = f(g(Y))

V štandardnej knižnici existuje predikát, ktorý vykonáva bezpečnú unifikáciu:

?- unify_with_occurs_check(p(X,f(X)), p(g(Y),Y)).
false.

Tento predikát zachováva konzistentnosť voči klasickej logike prvého rádu, ale je výpočtovo náročnejší.

Odpoveď na dopyty v Prologu

Všeobecný model spracovania dopytu v Prologu je možné si predstaviť ako "čiernu skrinku", ktorá obsahuje znalostnú bázu (fakty a pravidlá) a rezolučný mechanizmus Prologu, ktorý sa pokúša dokázať dopyt na základe tejto bázy. Zjednodušená schéma je nasledovná:

            +---------------------------+
            |       BÁZA ZNALOSTÍ       |
            |    (fakty + pravidlá Γ)   |
            +---------------------------+
                       ^
                       |
                       |
   DOPYT  ?- φ  ------>|
                       |
                       v
                +--------------+
                |    PROLOG    |
                |  (rezolúcia) |
                |    Γ ⊢ φ ?   |
                +--------------+
                       |
                       v
                    ODPOVEĎ

Proces v krokoch:

1. Používateľ zadá dopyt: ?- φ.

2. Prolog sa pokúsi dokázať $φ$ pomocou faktov a pravidiel z $Γ$.

3. Ak nájde dôkaz: vypíše riešenie.

4. Ak dôkaz neexistuje: false.

Cyklus pre ďalšie riešenia (backtracking):

   Po nájdení prvého riešenia:

    vypíš riešenie
        |
        v
    čakaj na vstup používateľa

        ak používateľ stlačí ";"
            - vráť sa k poslednému rozhodovaciemu bodu a hľadaj ďalšie riešenie
        inak
           - skonči

Zjednodušene:

• Dopyt vstupuje do "čiernej skrinky".
• Prolog systematicky skúša nájsť možné dôkazy.
• Každé riešenie zodpovedá jednej úspešnej dôkazovej vetve.
• ";" spôsobí návrat späť a hľadanie ďalšej vetvy.

Vykonanie dopytu môže viesť k rôznym výsledkom:

• Úspech (success): Prolog našiel riešenie, ktoré odpovedá dopytu.
• Neúspech (failure): Prolog nenašiel žiadne riešenia, ktoré odpovedajú dopytu.
• Zacyklenie (looping): Prolog sa môže dostať do nekonečného cyklu, ak nie je správne navrhnutý program alebo dopyt.

Príklad: Sokrates je smrteľný

Pre demonštráciu procesu dokazovania v Prologu použijeme klasický príklad:

Všetci ľudia sú smrteľní. 
Sokrates je človek. 
-------------------------
Sokrates je smrteľný.

Preklad do Prologu:

Znalostná báza:

   1) smrtelny(X) :- clovek(X).
   2) clovek(sokrates).

Dopyt:

      ?- smrtelny(sokrates).

Postup pri hľadaní dôkazu (SLD-rezolúcia):

Cieľ:
    smrtelny(sokrates)

        |
        |  unifikácia s pravidlom (1)
        |  smrtelny(X) :- clovek(X)
        |  X = sokrates
        v

    clovek(sokrates)

        |
        |  unifikácia s faktom (2)
        v

     (úspech)

Celý proces je možné vizualizovať pomocou SLD dôkazového stromu:

clovek(sokrates)     smrtelny(X) :- clovek(X)   smrtelny(sokrates) 
        |                       |                       |
        |                       |                       |
        |                       -------------------------
        |                                   |
        |                                   |  X = sokrates
        |                                   v
        |                             clovek(sokrates)
        |                                   |
        |                                   |
        -------------------------------------
                        | 
                        v
                      úspech

Unifikácia v Prologu

Unifikácia je základná operácia v Prologu. Je to proces porovnávania a spájania termov. Unifikácia sa používa pri dokazovaní dopytov, keď Prolog porovnáva cieľ s faktami a pravidlami v znalostnej báze. Pričom platia nasledujúce pravidlá:

• Atómy je možné unifikovať iba s identickými atómmi.
• Premenné môžu byť unifikované s akýmkoľvek termom (atóm, číslo, zložený term), a stávajú sa inštanciou tohto termu.
• Zložené termy sa unifikujú, ak majú rovnaký funktor (názov), aritu, a všetky ich argumenty sa unifikujú.

V rámci tejto sekcie budú demonštrované rôzne príklady unifikácie, ktoré ilustrujú tieto pravidlá a ukazujú, ako Prolog pracuje s rôznymi typmi termov.

Atóm s atómom

Atómy sa unifikujú iba ak sú identické.

?- a = a.
true.

?- a = b.
false.

Premenná s atómom

Premenná sa stáva inštanciou atómu.

?- X = a.
X = a.

Premenná s číslom

?- X = 5.
X = 5.

Premenná s premennou

Obe premenné sa navzájom zviažu. Zatiaľ nemajú priradenú konkrétnu hodnotu.

?- X = Y.
X = Y.

Zložené termy – úspech

• Rovnaký funktor (bod)
• Rovnaká arita (2)
• Argumenty sa úspešne unifikovali.

?- bod(X,2) = bod(1,Y).
X = 1,
Y = 2.

Zložené termy – rozdielny funktor

Funktory sa nezhodujú.

?- bod(1,2) = bodik(1,2).
false.

Zložené termy – rozdielna arita

Rozdielny počet argumentov.

?- bod(1,2) = bod(1,2,3).
false.

Vnorené termy

Unifikácia prebieha rekurzívne.

?- f(g(X), Y) = f(g(a), b).
X = a,
Y = b.

Konflikt v argumentoch

?- bod(X,X) = bod(1,2).
false.

Premenná X by musela byť súčasne 1 aj 2, čo nie je možné.

Cyklus (bez occurs-check)

SWI-Prolog štandardne nepoužíva occurs-check. V klasickej logike by táto unifikácia zlyhala.

?- X = f(X).
X = f(X).

Programovacie konvencie v Prologu

V tejto sekcii sú uvedené základné programovacie konvencie, ktoré by mali byť dodržiavané pri písaní Prolog programov. Dodržiavanie týchto konvencií zlepšuje čitateľnosť, údržbu a zrozumiteľnosť kódu.

Rôzne predikáty sú oddelené medzerou

rodic(jan, peter).
rodic(peter, anna).
rodic(anna, martin).

stary_rodic(X, Y) :-
    rodic(X, Z),
    rodic(Z, Y).

Jeden predikát v jednom riadku

Krátke jednoduché klauzuly môžu byť v jednom riadku.

muz(jan).

zena(anna).

clovek(X) :- muz(X).
clovek(X) :- zena(X).

stary_rodic(X, Y) :-
    rodic(X, Z),      % komentár k tejto časti pravidla
    rodic(Z, Y).

Všetky argumenty sú oddelené medzerou

bod(2, 3).

auto(znacka(skoda), farba(cervena)).

vzdialenost(bod(0, 0), bod(3, 4), 5).

Krátke klauzuly

Ak je telo príliš dlhé, je vhodné ho rozdeliť na podklauzuly.

Menej vhodné (dlhé telo):

plnolety_student(X) :-
    student(X),
    vek(X, V),
    V >= 18,
    zapisany(X, semester),
    ma_platnu_kartu(X).

Vhodnejšie rozdelenie:

dospely(X) :-
    vek(X, V),
    V >= 18.

aktivny_student(X) :-
    student(X),
    zapisany(X, semester).

plnolety_student(X) :-
    aktivny_student(X),
    dospely(X).

Používanie rozumných pomenovaní

Menej vhodné:

s(X, Y) :- r(X, Z), r(Z, Y).

Vhodnejšie:

stary_rodic(X, Y) :-
    rodic(X, Z),
    rodic(Z, Y).

Konzistentné pomenovanie

Využívanie jednotných názvov:

rodic/2, stary_rodic/2, prarodic/2

nie:

rodic/2, dedko/2, old_parent/2

Organizácia znalostnej bázy

V zdrojovom súbore musia byť všetky klauzuly rovnakého predikátu (rovnaký názov/arita) uvedené za sebou ako jeden súvislý blok.

To znamená:

• všetky fakty s tým istým názvom za sebou
• všetky pravidlá s tým istým názvom za sebou
• nesmú byť prerušené iným predikátom

Správna organizácia

zena(anna).
zena(eva).
zena(maria).

muz(jan).
muz(peter).
muz(jozef).

rodic(jan, peter).
rodic(peter, anna).
rodic(anna, jozef).

stary_rodic(X, Y) :-
    rodic(X, Z),
    rodic(Z, Y).

Nesprávna organizácia

rodic(jan, peter).
muz(jan).
rodic(peter, anna).   % klauzuly rodic/2 sú rozdelené
zena(anna).
rodic(anna, martin).

:- discontiguous rodic/2.

Príklad: Farebné mapy a teoréma štyroch farieb

Teoréma štyroch farieb je matematická veta, ktorá tvrdí, že každú mapu je možné vyfarbiť použitím najviac štyroch farieb tak, aby žiadne dve susedné krajiny nemali rovnakú farbu.

V nasledujúcej úlohe sa pokúsime aplikovať túto teorému na jednoduchú mapu, ktorá obsahuje osem krajín (C1 až C8). Cieľom je vyfarbiť tieto krajiny pomocou štyroch rôznych farieb tak, aby sa žiadne susediace krajiny nedotýkali rovnakou farbou.

                                +-----------+-----------+
                                |     C1    |     C2    |
                                |           +-----+-----+
                                |           | C3  | C4  |
                                +-----+-----+-----+     |
                                | C5  |     C6    |     |
                                +-----+---------+-+-----+
                                |         C7    |   C8  |
                                +---------------+-------+

farba(cervena).
farba(modra).
farba(zelena).
farba(zlta).

rozdielna(X,Y) :- X \= Y.

vysledok :- 
    farba(C1), farba(C2), farba(C3), farba(C4), 
    farba(C5), farba(C6), farba(C7), farba(C8),
   
    rozdielna(C1,C2),
    rozdielna(C1,C3),
    rozdielna(C1,C5),
    rozdielna(C1,C6),
   
    rozdielna(C2,C3),
    rozdielna(C2,C4),
   
    rozdielna(C3,C4),
    rozdielna(C3,C6),
   
    rozdielna(C4,C6),
    rozdielna(C4,C8),
   
    rozdielna(C5,C6),
    rozdielna(C5,C7),
   
    rozdielna(C6,C8),
    rozdielna(C6,C7),
   
    rozdielna(C7,C8),
   
    print([C1,C2,C3,C4,C5,C6,C7,C8]), nl.

?- vysledok.
[cervena,modra,zelena,cervena,modra,zlta,cervena,modra]
true .

?- vysledok.
[cervena,modra,zelena,cervena,modra,zlta,cervena,modra]
true ;
[cervena,modra,zelena,cervena,modra,zlta,cervena,zelena]
true ;
[cervena,modra,zelena,cervena,modra,zlta,zelena,modra]
true ;
[cervena,modra,zelena,cervena,zelena,modra,cervena,zelena]
true ;
[cervena,modra,zelena,cervena,zelena,modra,cervena,zlta]
true
...

?- findall(1, vysledok, L), length(L, N).
[cervena,modra,zelena,cervena,modra,zlta,cervena,modra]
[cervena,modra,zelena,cervena,modra,zlta,cervena,zelena]
[cervena,modra,zelena,cervena,modra,zlta,zelena,modra]
            *
            *
            *
[zlta,zelena,modra,zlta,zelena,cervena,zlta,zelena]
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|…],
N = 408.

Literatúra

1. Endriss, U. (2021). An Introduction to Prolog Programming [Lecture notes]. Institute for Logic, Language and Computation, Universiteit van Amsterdam. Dostupné online https://staff.fnwi.uva.nl/u.endriss/teaching/prolog/prolog.pdf
2. Rice, A., & Beresford, A. (n.d.). Prolog basics – Programming in Prolog [Lecture slides]. University of Cambridge, Computer Laboratory. Dostupné online https://www.cl.cam.ac.uk/teaching/2526/Prolog/annotated-slides.pdf
3. Bratko, I. (2001). Prolog Programming for Artificial Intelligence (3rd ed.). Pearson Education.
4. Bramer, M. (2005). Logic programming with Prolog. Springer.
5. Triska, M. (2005–2026). The Power of Prolog [Online book]. Dostupné online https://www.metalevel.at/prolog
6. Blackburn, P., Bos, J., & Striegnitz, K. (2003). Learn Prolog Now! (Version 1.2.5) [Online textbook]. Dostupné online https://cs.union.edu/~striegnk/learn-prolog-now/html/index.html
7. Fernández, M. (2014). Operational semantics of Prolog. In Programming Languages and Operational Semantics (pp. 167–177). Springer, London. Dostupné online https://doi.org/10.1007/978-1-4471-6368-8_8
8. Luger, George F., and William A. Stubblefield. AI algorithms, data structures, and idioms in Prolog, Lisp, and Java. Pearson Addison-Wesley, 2009.
9. Csenki, Attila. Prolog Techniques. Bookboon, 2009.
10. Tate, Bruce. Programmer Passport: Prolog. The Pragmatic Programmers LLC, 2022.
11. Matthews, Clive. An introduction to natural language processing through Prolog. Routledge, 2016.