Unifikace
-=-=-=-=-=-
Computers are useless. They can only give you answers.
-- Pablo Picasso
Možná vás zajímá, jak prolog vlastně najde výsledek. Postup
není tak přímočarý, jako u procedurálních jazyků, ale přesto
celkem jednoduchý. Jeho základem je unifikace. Pokud zadáte dotaz
predikát(parametry), prolog začne prohledávat databázi a hledat
definice predikátů, dokud nenajde odpovídající jméno a počet
parametrů. Potom se pokusí predikát zunifikovat z vaším dotazem.
Postupuje tak, že nejprve se pokusí zunifikovat jméno predikátu
a potom jednotlivé dotazy v jeho těle (postupně). Unifikace probíhá
podle následujících pravidel:
Dva termy jsou unifikovatelné kdyz:
1) jsou shodné
2) poměné v obou termech můžu substituovat tak, aby platilo 1)
Rozhodnutí zda S a T jsou unifikovatelné probíhá tedy takto:
1) Pokud S i T jsou stejné konstanty, potom jsou unifikovatelné
2) Pokud S je proměná a T je term, potom jsou unifikovatelné a
provede se substituce S=T (a obráceně)
3) Pokud S a T jsou struktury potom jsou unifikovatelné pokud
a) mají shodný funktor a počet parametrů
b) odpovídající dvojice parametrů jsou unifikovatelné
Základní trik je v tom, že v případě, že prolog neuspěje
a nějaké dva termy uprostřed těla predikátu se nepodaří vyplnit,
vrátí se zpět až k poslední volné proměné a zkusí udělat jinou
substituci, pokud ani to neuspěje, zkusí další atd. až vyčerpá
všechny možnosti. Potom se vrátí ještě o proměnou zpět. V případě že
se vrátí úplně na začátek, pokusí se najít další definici predikátu
a teprve v případě, že už další neexistuje, neuspěje. Postupuje tedy
backtracingem.
Můžu napsat následující rekurzivní definici potomka:
r(a,b). % (r1) rodic(anna, bohous).
r(b,c). % (r2) rodic(bohous,cyril).
r(c,d). % (r3) rodic(cyril,dana).
p(X,Y) :- r(X,Y). % (p1) potomek(X,Y) :- r(X,Y).
p(X,Y) :- r(X,Z), p(Z,Y). % (p2) potomek(X,Y) :- r(X,Z), potomek(Z,Y).
Tady je poprvé, co jsme použili dvou podmínek pro definici
potomka. Prolog se napřed pokusí naplnit první - tedy X je potomkem
Y pokud Y je rodič X. A teprve v případě neúspěchu vezme rodiče X
(Z) a zkusí zjistit stejným postupem, jestli Z je potomek X.
Tedy pokud se budu ptát ob tři generace, třikrát se provede
druhá podmínka, než se podaří unifikovat první.
Takto bude probíhat výpočet:
(novy cíl, podle které klauzule, lokální substituce)
?- p(a,X). %vyhledej všechny potomky anny
r(a,X) (p1) {X1/a,Y1/X}
úspěch,"X=b" (r1) {X/b}
r(a,Z1),p(Z1,X) (p2) {X1/a,Y1/X}
p(b,X) (r1) {Z1/b}
r(b,X) (p1) {X2/b, Y2/X}
úspěch,"X=c" (r2) {X/c}
r(b,Z2),p(Z2,X) (p2) {X2/b,Y2/X}
p(c,X) (r2) {Z2/c}
r(c,X) (p1) {X3/c, Y3/X}
úspěch,"X=d" (r3) {X/d}
r(c,Z3),p(Z3,X) (p2) {X3/c,Y3/X}
p(d,X) (r3) {Z3/d}
r(d,X) (p1) {X4/d,Y4/X}
neúspěch ...
"no"
Znalosti tohoto postupu lze zneužívat pro různé účely. Můžu
programy různě optimalizovat. Například můžu napsat i následující
definici potomka:
p(X,Y) :- r(X,Z), p(Z,Y). % (p2) potomek(X,Y) :- r(X,Z), potomek(Z,Y).
p(X,Y) :- r(X,Y). % (p1) potomek(X,Y) :- r(X,Y).
(pravidla jsou prohozena) Tato definice je samozřejmě také
správně. Ale v případě, že se budu ptát, jestli Cyryl je potomek
Bohouše, první podmínka napřed dojde až na začátek rodokmenu, tedy
k Anně a pak se bude postupně vracet. Provádění tedy bude pomalejší.
Můžu napsat ještě jednu definici:
p(X,Y) :- p(Z,Y), r(X,Y). % (p2) potomek(X,Y) :- potomek(Z,Y), r(X,Z).
p(X,Y) :- r(X,Y). % (p1) potomek(X,Y) :- r(X,Y).
I tato definice je správně, ale nebude fungovat, protože prolog
na to, aby zjistil, jestli X je potomek Y, napřed se pokusí vyhledat
všechny potomky X, ale to se mu nepodaří, protože rekurze nikdy
nezkončí - Poprvé se za Z v p(Z,Y) dosadí volná proměná. Potom se
ale bude hledat potomek kohokoliv a teprve později zjištovat, jestli
je opravdu potomkem X, zůstane tedy volná proměná a znova se bude
hledat potomek kohokoliv.
Z toho vyplívá, že je dobré vždy psát konkrétnější definice
napřed - Prolog má potom méně možností. Také je dobry vždy psát
ukončující podmínku rekurze před její definicí.
Unifikaci můžu zneužít i pro jiné věci. Například pro emulaci
smyčky. Pokud chci v bludišti od textovky vypsat všechny cesty
vedoucí ven z místnosti, můžu napsat například:
connect(zachod,zahrada).
connect(zachod,chodba). zachod<--->chodba<--->zahrada
connect(chodba,zachod). | ^
connect(zahrada,chodba). +----------------------+
connect(chodba,zahrada).
cesty(L) :- %vypíše všechny cesty s místnosti
connect(L,X), %zjistí cestu z L a do X uloží cil-tady se dela backtracin
write(X), %vypíše cílovou místnost
write(' '), %oddělí slova
fail. %selže,aby se systém pokusil najít další cestu a také ji v
cesty(_) :- %tohle se vyvolá,když už není žádná cesta k vypsání
nl. %nový řadek-konec výpisu
Predikát cesta používá několik vestavěných predikátů v prologu.
Write slouží k vypsání daného termu, nl vypíše novou řádku a fail je
predikát, který je vždy "no".
V tom je právě ten fígl. Predikát cesty se napřed najde první
cestu z L do X - connect(L,X). Potom write tuto cestu vypíše
a nakonec se najede na fail. Prolog se tedy vrátí na nejbližší
rozcestí - connect(L,X) a zkusí jinou cestu, tu také vypíše a vrátí
se zpět atd. až nakonec už žádná další cesta není a prolog tedy
najde další definici, ověří platnost predikátů nl, ten vypíše novou
řádku a uspěje. Výpočet je tedy hotov.
výheň