Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz: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

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.
/var/www/wiki/data/pages/pitel/msz/prolog.txt · Poslední úprava: 03. 07. 2012, 13.53:34 (upraveno mimo DokuWiki)