Prolog

Prolog

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

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)

• 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í

Cut (logic programming)

• Predikát, který uspěje právě jednou.
• 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.