28 - Prolog - způsob vyhodnocení (základní princip, unifikace, chování vestavěných predikátů, operátor řezu /vhodné a nevhodné užití) Flashcards
Hornovy klauzule
logický program = libovolná konečná množina programových Hornových klauzulí.
Logické programování = deklarativní, teoretický model zachovávající úplnost
• Hornovy klauzule = klauzule s nejvýše jedním pozitivním literálem, ostatní jsou negované (dají se reprezentovat jako implikace)
○ ¬ p V ¬ q V ⋯ V ¬ t V u
○ Hornovu klauzuli tak lze obecně zapsat jako implikaci ve formě (p ∧ q ∧⋯ ∧ t)⇒ u
Vyhodnocování (odvozování/dokazování) cílů - SLD-rezoluce
rezoluce - dokazuje se NEsplnitelnost formulí - rezoluční strom, v kořenu je dokazovaná formule C, v listech jsou jednotlivé klauzule S, ze kterých je možné C dokázat, ve vnitřních listech resolventy
○ SLD rezoluce = lineární vstupní rezoluce se selekčním pravidlem
§ selekční pravidlo = libovolná funkce, která vybere literál z každé uspořádané cílové klauzule
§ pomocí selekčního pravidla algoritmizujeme výběr literálu z cílové klauzule, na které se bude rezolvovat
§ SLD-rezoluce je korektní a úplná pro Hornovy klauzule
Vyhodnocování
• Vyhodnocování se provádí na základě SLD rezoluce.
○ SLD rezoluce- podcíle jsou expandovány do hloubky. Tedy je-li hledán nějaký podcíl, tak jsou hlavičky klauzulí/faktů vložených do programu prohledávány shora dolů, až je možné nějakou hlavičku s podcílem unifikovat. Jakmile proběhne unifikace, je tělo klauzule zpracováváno zleva doprava s tím, že každý atom na pravé straně je opět vyhodnocován do hloubky. Pokud je jedná o fakt, nebo jsou všechny atomy na pravé straně uspokojeny, uspěje celý podcíl a následně celý cíl. Pokud něco nelze unifikovat / uspokojit, následuje selhální. To vyvolá proces navracení (backtracking),kdy se proces vrací do místa prohledávání a snaží se najít jinou hlavičku, pro kterou by prohledávání mohlo uspět. Takto se snaží najít řešení do doby, dokud neuspěje, nebo neselže i hlavní cíl (na command line se vypíše ‘no’).
* Podcíle jsou expandované do hloubky (ztráta obecnosti - možné uváznutí v nekonečné větvi SLD-stromu i pokud by další větev nalezla řešení). * Podcíle jsou vybírané zleva doprava. * Snaha unifikovat podcíl s hlavičkou faktu (klauzule vložené do programu), potom je tělo odpovídající nalezené klauzule procházené zleva doprava a každý atom na pravé straně je zpracovávaný do hloubky. * Při selhání podcíle se vykonává návrat (backtracking) - vyhodnocovací mechanismus se snaží navrátit backtracking do místa prohledávání a znovu, pro právě selhávající (dílčí) podcíl, se snaží najít jinou hlavičku, kde by uspěl. * Backtracking lze explicitně vyvolat i v případě úspěšného nalezní - potom jsou prohledávány další možnosti.
Unifikace = vyhodnocování - přiřazení hodnoty k proměnné, test na rovnost, selekce,… - prostě kroky vyhodnocování jednotlivých formulí
• Unifikace je v Prologu základní a jedinou operací, která řídí vyhodnocení a díky níž se dostáváme k výsledku
• Probíhá při vyhodnocení SLD rezolucí, když zadáme cíl a potom u všech (dílčích) podcílů, nebo explicitně zadáním predikátu =, či jeho negované formy =
• Probíhá podle Robinsonova unifikačního algoritmu - nevykonává se kontrola výskytu (neodhalí se např. X = f(X), co může vést na nekonečný výsledný term).
Využití
• Přiřazení (navázání) hodnoty k nějaké proměnné: = (lze zapsat i opačně)
• Test na rovnost (unifikovatelnost), i složitých struktur: =
• Selektor položek z datových struktur/seznamů: = [ | ]
• Vytváření datových struktur/seznamů: = [1,2,3]
• Předávání parametrů hodnotou, kdy term je předán jako skutečný argument.
• Předávání parametrů odkazem, kdy je předána proměnná (volná, nenavázaná) jako skutečný argument.
• Sdílení proměnných, vytváření synonym.
Co je to prolog
- logický DEKLARATIVNÍ programovací jazyk (programátor popisuje pouze cíl výpočtu, přičemž přesný postup, jakým se k výsledku program dostane, je ponechán na libovůli systému)
- Prolog se snaží o pokud možno abstraktní vyjádření faktů a logických vztahů mezi nimi s potlačením imperativní složky
- Prolog je využíván především v oboru umělé inteligence a v počítačové lingvistice (obzvláště zpracování přirozeného jazyka, pro nějž byl původně navržen).
- Syntaxe jazyka je velice jednoduchá a snadno použitelná pravě proto, že byl původně určen pro počítačově nepříliš gramotné lingvisty.
- Prolog je založen na predikátové logice prvního řádu; konkrétně se omezuje na Hornovy klauzule !
Běh programu je pak představován aplikací dokazovacích technik na zadané klauzule. Základními využívanými přístupy jsou unifikace, rekurze a backtracking.
Prolog datové typy - termy
Jednotnou datovou strukturou, se kterou Prolog pracuje, je tzv. term - pojem převzatý z formální logiky. Základní členění termů: • term ○ struktura ○ jednoduchý term § proměnná § konstanta □ číslo □ atom
Prolog datové typy - Atomy
Atomy lze dle konstrukce rozdělit do třech kategorií:
• řetězce znaků začínající malým písmenem obsahující pouze písmena, číslice a podtržítko - např: otec franta novy_Clen2
• posloupnost znaků uzavřená v apostrofech (některé implementace používají uvozovky) - např: ‘Pepa 26.6.2007’ ‘velký les’
• atomy skládající se pouze ze speciálních znaků - např: , ; :-)
Prolog datové typy - Čísla
Původní Prolog podporoval pouze celá čísla. Řada implementací pracuje s reálnými i racionálními čísly a s neohraničenými celými čísly.
Například:
?- X is 2^200, Y is (3 rdiv 8) + (4 rdiv 9).
X = 1606938044258990275541962092341162602522202993782792835301376
Y = 59 rdiv 72
Prolog datové typy - Proměnné
začínají velkým písmenem nebo podtržítkem a nesmí obsahovat speciální znaky!
- Vyskytují se v pravidlech, kde popisují účastníky vztahu, nebo v dotazech, kde reprezentují hledané objekty
- Rozsah platnosti proměnné je pouze jedna klauzule, stejnojmenná proměnná v sousední klauzuli nemá s touto nic společného, i když je třeba součásti stejného predikátu
- Hodnotu získává pomocí srovnávání (unifikace) a po jejím přiřazení se již dále nemění, pokud se použité pravidlo, které ji přiřadilo, neodvolá (backtracking).
Z pohledu interpretu lze proměnné rozdělit na dva typy:
• volné - jejich hodnota zatím není známá a interpret se ji snaží nalézt
• vázané - z dřívějších kroků řešení již plyne její hodnota, tedy je s ní svázána
klauzule:
rodic(jana,petr).
rodic(otto,eva).
dite(X,Y) :- rodic(Y,X).
dotazy: ?- rodic(X,petr). X = jana ; No ?- dite(X,jana). X = petr ; No
Speciálním typem je tzv. anonymní proměnná. Značí se jako podtržítko a používá se v pravidlech. Její hodnota není podstatná a Prolog ji ve výsledcích nezobrazuje.
Příklad: predikát, zda X je dítě
je_dite(X) :- dite(X,_).
Prolog datové typy - Struktury, seznamy a řetězce
Struktury (píšou se jako funkce, mají aritu)
Struktury jsou tvořeny z funktoru a argumentů (složených termů - funktor - jméno, arita (často použití jako operátory - A < B místo < (AB))). Počet argumentů udává aritu struktury. Některé operátory mohou být používány také v infixovém tvaru. Strukturou tedy mohou být i klauzule, kde se jako funktor používá infixový operátor :- .
Příklady:
muz(adam). %funktor muz má aritu 1
datum(27,6,2007). %funktor datum má aritu 3
okamzik(datum(27,6,2007),cas(13,54)). %funktor okamzik má aritu 2
prarodic(X,Y) :- rodic(X,Z), rodic(Z,Y).
V jednom programu se mohou vyskytovat dva stejně pojmenované funktory, pokud mají různé arity. Speciálním případem struktur jsou seznamy a řetězce.
Seznamy
Seznamy jsou definovány induktivně: Prázdný seznam je označen atomem [ ] , k reprezentaci neprázdného seznamu slouží binární funktor tečka ‘.’ . Neprázdný seznam je tedy tzv. tečkový pár (terminologie pochází z jazyka LISP) .(Hlava,Tělo), kde Hlava je první prvek seznamu a Tělo je seznam tvořený zbývajícími prvky seznamu. Pro zjednodušení zápisu lze použít výčet prvků v hranatých závorkách (oba zápisy jsou ekvivalentní).
Příklad:
.(a,.(b,.(c,[ ]))) .
[a,b,c] .
Pro práci se seznamy se často využívá operátor ‘|’, který umožňuje přístup k jednotlivým částem seznamu. Seznam lze pak zapsat jako [Začátek|Tělo], kde Začátek je výčet (nikoliv seznam) prvků tvořící začátek definovaného seznamu a Tělo je seznam (nikoliv výčet) tvořící zbytek definovaného seznamu (je-li prázdný, nemusí se uvádět).
přímo v [] s využitím | - [head, body], [head | body] - např: [a, b, c] [a | [b, c]]
Častým zdrojem chyb je právě záměna operátoru ‘|’ a čárky.
Řetězce
Řetězce jsou sekvence znaků uzavřené v uvozovkách, které jsou ekvivalentní seznamu (číselných) kódů jednotlivých znaků v místní znakové sadě nebo v Unicode, pokud systém podporuje Unicode.
Příklad:
?- Xs = “Πρόλογ”.
Xs = [928, 961, 972, 955, 959, 947]
Program
= Množina programových Hornových klauzulí.
• Proč? Protože rezoluce dvou Horneových klausulí vyústí v další Horneovu klausuli.
• fakta ○ Hornovy klauzule bez negativního literálu ○ např. ditetem(andulka, jan). ○ vlastně se jedná o pravidla s prázdným tělem • pravidla ○ Hornovy klauzule s aspoň 1 negativním literálem ○ např. vnukem(X,Y) :- ditetem(X,Z), ditetem(Z,Y). ○ hlava a tělo pravidla • cíle ○ Hornovy klauzule bez pozitivního literálu ○ reprezentují dotazy – spuštění výpočtu ○ např. ?- vnukem(petr, pavel) • fakta a pravidla tvoří hypotetický základ pro důkaz
cíle jsou predikáty, které chceme z dané hypotézy ověřit, zda platí nebo ne
Operátor řezu
Predikát řezu slouží k vyjádření negace a zrychlení prologovských programů. Značí se vykřičníkem „!“. Názornou představu o predikátu řezu si můžeme udělat už z jeho názvu – pokud použijeme řez v nějaké větvi výpočtu, řez zakáže použít další možné větve tohoto výpočtu, tedy zakáže další backtrackování. Nejlepší bude příklad:
a(X) :- b(X), !, c(X).
a(X) :- d(X).
Prolog zde zkouší splnit první řádek. Pokud se splní predikát b(X), dojdeme k predikátu řezu. Ten okamžitě uspěje, ale přitom zakáže nový vstup do predikátu, ve kterém se nachází, tedy nesmíme už znovou zkoušet splnit predikát a(X). Pokud tedy neuspěje následující predikát c(X), Prolog už díky řezu v prvním řádku nesmí zkoušet další možnost v druhém řádku. Odřezali jsme tedy druhou větev výpočtu. Kdyby v prvním řádku nebyl operátor řezu, Prolog by zkoušel splnit nejprve první řádek, a kdyby se mu to nepovedlo, skočil by hned na druhý tak, jak to známe.
Operátor řezu lze použít dvěma způsoby:
1. Operátor řezu jako tzv. zelený řez, ten nemění význam programu, pouze ho urychluje tím, že uřezává neperspektivní větve zbytečné pro výpočet, ale program by fungoval i bez něj.
max2(X,Y,X):-X>Y,!.
max2(X,Y,Y):-Y>=X.
2. Operátor řezu jako tzv. červený řez, kterým změníme průběh vyhodnocování programu. (je nutný, aby program fungoval správně)
max(X,Y,Z):-X>Y,!, X=Z.
max(X,Y,Y).
Negace
Jak už jsme prozradili, negaci v Prologu tvoříme pomocí řezu. Ukážeme si tedy definici vestavěného predikátu not(A), který uspěje, pokud neuspěje A.
not(A) :- A, !, fail.
not(A).
Predikát not(A) se nejprve pokusí splnit cíl A. Pokud se A splní, zakážeme zkoušet další větve výpočtu a přikážeme predikátu selhat. Pokud se cíl A nesplní, Prolog zastaví vyhodnocování tohoto řádku, tudíž se nedostaneme ani k operátoru řezu, takže nezakážeme další větev, která se automaticky splní.
