Prolog

Prolog

Principy

Programy jsou ze 2 častí:

Vlastní program – Hornovy klauzule, které tvoří hypotetický základ pro důkaz.

Dotazy – cíle, predikáty, které chceme z dané hypotézy ověřit, zda platí nebo ne

Hornovy klauzule sa vyskytují ve 2 variantách:

Fakta – např. ditetem(andulka, jan).

Plné klauzule s hlavou a tělem (pravidlo) – např. vnukem(X,Y) :- ditetem(X,Z), ditetem(Z,Y).

Struktura

Termy – konstanty, proměnné, struktury

Klauzule

Cíle

Vyhodnocování

Vyhodnocování se provádí na základě SLD rezoluce – podcíle jsou expandované do hloubky.

Podcíle jsou v klauzili vyhodnocované zleva doprava.

Snaha unifikovat podcíl s hlavičkou faktu (klazule vložené do programu), potom je tělo této nalezené klauzule vyhodnocované zleva doprava a každý atom na pravé straně je zpracován do hloubky.

Při selhání se vykonává návrat (backtracking).

Unifikace

Robinsonův unifikační algoritmus

Nevykonáva se kontrola výskytu (neodhalí sa např. X = f(X), což můze vést na nekonečný výsledný term)v

Základní a jediná operácia v Prologuv

Využití:

Přiřazení (navázání) hodnoty k nějaké proměnné: proměnná = hodnota.

Test na rovnost (unifikovatelnost) termů (i složitějších struktur): term1 == term2

Výběr ze seznamu: L = [X|_]

Vytváření struktur: Y = [a, b, c]

Předávání parametru hodnotou (term je předaný jako skutečný argument)

Předávání parametru odkazem (proměnná je odevzdána jako skutečný argument)

Sdílení proměnných a vytváření synonym: a(P, Q) → a(X, X)

Vestavěné predikáty

Vetšinou nejsou znovuspustitelné

Nevyhnutelné pro praktické programování

Aritmetické operace pomocí is

Testování typu – integer(X), atom(X) (X je identifik8tor, konstanta)

Metalogické – test, zdaje proměnná navázaná …

Operace s klauzulemi – dynamické přídávání (assert) a odebírání (retract) klauzulí

Operátor řezu

Právě jednou uspívající operátor

Pokud se program při backtrackingu dostane k operátoru řezu, selže celý podcíl a všechny body znovuuspění mezi hlavičkou kaluzule a operátorem řezu jsou zapomenuty.

Správné použití:

chceme Prologu říct, že už se našlo hledané řešení a nemá cenu hledat dále (koncová podmínka):

sum_to(1, 1) :- !. sum_to(N, Res) :- N1 is N - 1, sum_to(N1, Res1), Res is Res1 + N.

Bylo dosaženo stavu který už nevede k řešení – checeme aby podcíl selhal:

not(P) :- call(P), !, fail. not(P).

Ukončení generování alternativních řešení:

is_integer(0). is_integer(X) :- is_integer(Y), X is Y + 1. divide(N1, N2, Result) :- is_integer(Result), Product1 is Result * N2, Product2 is (Result + 1) * N2, Product1 =< N1, Product2 > N1, !.

Nesprávné použití:

Nesprávné použití může zamezit nelezení všech výsledků nebo nalezené chybných výsledků!

S operátorem řezu mají predikáty silně vymezený charakter podle toho u kterých parametrů můžou mít volnou proměnnou a kde je třeba mít hodnotu.