IB015 Neimperativní programování
Neimperativní programování v Prologu
Jiří Barnat
Logické programovaní a Prolog
Logické programování
• Deklarativní programovací paradigma
• Mechanická dedukce nových informací na základě uvedených údajů a jejich vzájemných vztahů.
• Výpočet = logické dokazování.
• Nej používanější (jediný) programovací jazyk
Prolog
IB015 Neimperativní programování - 09
str. 2/35
Logické programovaní a Prolog
Logické programování
• Deklarativní programovací paradigma
• Mechanická dedukce nových informací na zákla údajů a jejich vzájemných vztahů.
• Výpočet = logické dokazování.
• Nej používanější (jediný) programovací jazyk
Prolog
• Třešnička na dortu neimperativního programování.
IB015 Neimperativní programování - 09
Četnost, oblasti a způsoby použití
Četnost použití Prologu
• Logické programování se masově nerozšířilo.
• Okrajový, specificky používaný programovací prostředek.
• http://langpop.com/ (2011) - Prolog ani není uveden.
Typické oblasti použití Prologu
• Umělá inteligence, zpracování jazyka, rozvrhování.
• Řešení deklarativně zadaných úloh.
Moderní způsoby použití Prologu
• Vložené použití ve větší (i imperativní) aplikaci.
• Deduktivní databáze.
IB015 Neimperativní programování - 09
str. 3/35
Logické výpočetní paradigma
Logické výpočetní paradigma
• program = databáze faktů a pravidel + cíl
• výpočet = dokazovaní cíle metodou unifikace a SLD rezoluce
• výsledek = pravda/nepravda, prípadne seznam hodnot volných proměnných, pro které je cíl pravdivý vzhledem k databázi faktů a pravidel.
Příklad programu
• databáze faktů a pravidel
pocasi(prsi).
stav(mokro)  :- pocasi(prsi).
• cíl a výsledek
?-stav(mokro). ?-stav(X).
true. X = mokro.
IB015 Neimperativní programování - 09
str. 4/35
Implementace Prologu
SlCStus Prolog
• "State-of-the-art" implementace prologu.
• Komerční produkt.
• http://sicstus.sics.se/
SWI-Prolog
• Relativně úplná a kompatibilní implementace.
• Freeware.
• http://swi-prolog.org
A další ...
• YAP: Yet Another Prolog
http://www.dec.fc.up.pt/~vsc/Yap/
IB015 Neimperativní programovaní - 09
str. 5/35
Sekce
Úvodní intuitivní příklady
IB015 Neimperativní programování - 09
Interaktivní uživatelské prostředí Prologu
SWI-Prolog
• Spouštěno příkazem swipl.
Textové interaktivní prostředí
• Standardní výzva: ?-
• Veškeré povely uživatele musí být zakončeny tečkou.
Základní povely
» Ukončení prostředí: hait.
• Nápověda: help.
• Nactenisouborujmeno.pl: consuit(jméno).
• Též alternativně: [jméno].
IB015 Neimperativní programování - 09
str. 7/35
Notace databáze fakt
Struktura jednoduchých příkladů
• Databáze fakt a pravidel uvedena v externím souboru.
• Dotazy kladené skrze interpreter.
• Přípona souboru .pl nebo .pro.
Notace fakt
• Fakta začínají malým písmenem a končí tečkou.
• Fakty jsou konstanty (nulární relace) a n-ární relace.
• Počet parametrů udáván u jména za lomítkem: jmeno/N.
Příklady
• tohleJeFakt.
• tohleTaky(parametri,parametr2.....parametrN).
• fakt /* a /* zanořeny */ komentár */ .
IB015 Neimperativní programování - 09
str. 8/35
Jednoduché dotazy na fakta a relace
Databáze fakt
• je_teplo. neprši.
kamarádi(vincenc,kvido). /* Znají se od mateřské školy, kamarádi(vincenc.ferenc). /* Poznali se na pískovišti.
Dotazy na databázi
• ?- je_teplo. tme.
• ?- prsi.
ERROR: Undefined prsi/0.
• ?- kamarádi(vincenc,kvido) . t nie.
• ?- kamarádi(ferenc.vincenc). false.
IB015 Neimperativní programovaní - 09
Dotazy s využitím proměnných
Proměnné
• Jména začínají velkým písmenem nebo podtržítkem.
• Je možné je (mimojiné) využít v dotazech.
• Interpreter se pokusí najít vyhovující přiřazení.
Dotazy s využitím proměnných
• ?- kamarádi(vincenc,X) . X = kvido ;
X = ferenc.
• ?- kamarádi(X,Y). X = vincenc,
Y = kvido ; X = vincenc,
Y = ferenc.
IB015 Neimperativní programování - 09
Interakce s uživatelem
Odpověď interpretru zakončená tečkou
• Indikuje, že nejsou další možnosti.
Odpověď interpretru nezakončená tečkou
• Výzva pro uživatele, zda chce hledání možných řešení ukončit (uživatel vloží tečku), nebo zda si přeje, aby bylo hledáno další řešení (uživatel vloží středník).
Porovnejte
• ?- kamarádi(vincenc,X).
X = kvido ; /* uživatel vložil středník */ X = ferenc.
• ?- kamarádi(vincenc,X).
X = kvido . /* uživatel vložil tečku */
IB015 Neimperativní programování - 09
str. 11/35
Databáze s pravidly
Pravidla v databázi
• Zápis:     clovek(X)   :- zena(X) .
• Význam: Pokud platí zena(x), pak platí ciovek(x). Disjunkce
• Zápis:       clovek(X)  :- zena(X) ; muz(X).
• Alternativní zápis:
clovek(X)   :- zena(X). clovek(X)   :- muz(X).
• Význam: (zena(X) V muz(X)) =>- clovek(X). Konjunkce
• Zápis:     unikat (X)   :- zena(X) , muz(X) .
• Význam: (zena(X) A muz(X)) =>- unikat(X).
IB015 Neimperativní programování - 09
str. 12/35
Dotazy na databáze s pravidly
Databáze:
• clovek(X)  :- zena(X). zena(bozena_nemcova) .
Příklady dotazů
• ?-zena(bozena_nemcova) . true.
• ?-clovek(bozena_nemcova) . true.
• ?-zena(jirik). false.
• ?- clovek(X).
X = bozenajiemcova.
IB015 Neimperativní programovaní - 09
Dotazy na databáze s pravidly - lokalita proměnných
Rozsah platnosti proměnných
• Použití proměnné je lokalizováno na dané pravidlo.
Příklad
• clovek(X)  :- zena(X); muz(X). unikat(X)  :- zena(X), muz(X). zena(bozena_nemcova) . zena(serena_will). muz( jara_cimrman) . muz(serena_will).
• ?- clovek(X). X = bozena_nemcova ; X = serena_will ; X = jara_c imrman ; X = serena_will.
?- unikat(X). X = serena_will.
IB015 Neimperativní programování - 09
str. 14/35
Sekce
Termy - Základní stavební kameny
IB015 Neimperativní programování - 09
str. 15/35
Syntax Prologu
Pozorování
• Fakta, pravidla a dotazy jsou tvořeny z termů.
Termy
• Atomy.
• Čísla.
• Proměnné.
• Strukturované termy.
IB015 Neimperativní programování - 09
str. 16/35
Objekty Prologu - Atomy
Atomy
• Řetězce začínající malým písmenem, obsahujicí písmena číslice a znak podtržítko.
• Libovolné řetězce uzavřené v jednoduchých uvozovkách. Příklady:
• Atomy:       pepa,  'pepa',  'Pepa', '2'.
• Neatomy:    Pepa, 2, ja a on, holmes&watson.
Test na bytí atomem
• atom/l - Pravda, pokud parametr je nestrukturovaným atom.
IB015 Neimperativní programování - 09
str. 17/35
Objekty Prologu - Čísla
Čísla
• Celá i desetinná čísla, používá se desetinná tečka.
?- A is 2.5 * 1.3. A = 3.25.
• Porovnání s aritmetickým vyhodnocením pomocí =:=.
?- 4 =:= 3+1. ?- 4 == 3+1. ?- 4 = 3+1.
true. falše. falše.
• Aritmetické vyhodnocení a přiřazení pomocí is.
?- A is 2*3. ?- A == 2*3. ?- A = 2*3.
A = 6. falše. A = 2*3.
Testy na bytí číslem
• number/i - Pravda, pokud je parametr číslo.
• float/i - Pravda, pokud je parametr desetinné číslo.
• =\=/2 - Aritmetická neekvivalence.
IB015 Neimperativní programování - 09
str. 18/35
Objekty Prologu - Strukturované termy
Strukturované termy
• Funktor (název relace) následovaný sekvencí argumentů.
• Pro funktor platí stejná syntaktická omezení jako pro atomy.
• Argumenty se uvádějí v závorkách, oddělené čárkou.
• Mezi funktorem a seznamem argumentů nesmí být mezera.
• Argumentem může být libovolný term.
• Rekurze je možná.
Arita
• Počet argumentů strukturovaného termu.
• Identifikace strukturovaného termu: funktor/N.
• Stejný funktor s jinou aritou označuje jiný term.
• Je možné současně definovat termy term/2 i term/3.
IB015 Neimperativní programování - 09
str. 19/35
Sekce
Unifikace v Prologu
IB015 Neimperativní programování - 09
Unifikace
Definice
• Dva termy jsou unifikovatelné, pokud jsou identické, anebo je možné zvolit hodnoty proměnných použitých v unifikovaných termech tak, aby po dosazení těchto hodnot byly termy identické.
Operátor =/2
• Realizuje unifikaci v Prologu.
• Lze zapisovat infixově.
• Binární operátor ne-unifikace: \=, tj. ve standardní notaci \=/2. Příklady
• ?- =(slovo,slovo). ?- a(A, [ble.ble]) = a(b(c(d)),B). true.                                 A = b(c(d)),
B = [ble, ble] .
?- =(slovo,X). X = slovo.
IB015 Neimperativní programování - 09 str. 21/35
Algoritmus unifikace
1) Pokud jsou termi a term2 konstanty (atomy, čísla), pak se unifikují, jestliže jsou tyto termy shodné.
2) Pokud je termi proměnná a term2 je libovolný term, pak se unifikují a proměnná termi je instanciována hodnotou term2. Podobně, pokud je term2 proměnná a termi je libovolný term, pak se unifikují a proměnná term2 je instaciována hodnotou
terml.
3) Pokud jsou terml a term2 strukturované termy tak se unifikují, pouze pokud mají stejný funktor a aritu, všechny korespondující páry argumentů se unifikují, a všechny instanciace proměnných z vnořených unifikací jsou kompatibilní.
4) Nic jiného.
IB015 Neimperativní programování - 09
str. 22/35
Příklady unifikace
• ?- snida(karel,lívance) = snida(Kdo,Co). Kdo = karel,
Co = lívance.
• ?- snida(karel,Jídlo) = snida(Osoba,marmelada). Jídlo = marmeláda,
Osoba = karel.
• ?- cdcko(29.beatles,yellow_submarine) = cdcko(A,B,help). falše.
• ?- fce(X,val) = fce(val,X). X = val.
• ?- partneri(eva.X) = partneri(X,vasek). falše.
• ?- fce(X,Y) = fce(Z,Z). X = Y, Y = Z.
IB015 Neimperativní programování - 09 str. 23/35
Unifikace rekurzivních výrazů
Příklad
• Uvažme následující dotaz na Prolog:
?- x = otec(X).
• Jsou unifikovatelné termy, kde jeden term je proměnná a přitom je vlastním podvýrazem druhého termu?
Nekorektnost algoritmu
• Podle definice ne, neboť neexistuje hodnota této proměnné taková, aby po dosazení nastala identita termů.
• Dle algorimu na přechozím slajdu, však k unifikaci dojde:
?- x = otec(X). X = otec(X).
Poznámka
• Některé implementace Prologu mohou při této unifikaci cyklit.
IB015 Neimperativní programování - 09
str. 24/35
Unifikace s kontrolou sebevýskytu.
Kontrola sebevýskytu
• Algoritmus je možné modifikovat tak, aby dával korektní odpověď. Pokud se samostatná proměnná vyskytuje jako podvýraz v druhém termu, termy se neunifikují.
• V praxi se často jedná o nadbytečný test, unifikace je velice častá operace, z důvodu výkonnosti se tento test vynechává.
unify_with_occurs_check/2
• Specifický operátor unifikace s testem na sebevýskyt.
• ?- unif y_with_occurs_check(X,otec (X) ) . falše.
IB015 Neimperativní programování - 09
str. 25/35
Programovaní s unifikací
Pozorování
• Unifikace je jeden z fundamentu logického programovaní.
• Pomocí unifikace můžeme odvozovat i sémantickou informaci.
Příklad
• vertical(line(point(X,Y).point(X,Z))). horizontal(line(point(X,Y).point(Z,Y))).
?- horizontál(line(point(2,3).point(12,3))). tme.
?- vertical(line(point(l,l),X)). X = point (1, _G2240) .
IB015 Neimperativní programování - 09
str. 26/35
Sekce
Jak Prolog počítá
IB015 Neimperativní programování - 09
Výpočet v Prologu
Teorie
• Výpočet = dokazovaní.
• Kódovaní problému pomocí Hornových klauzulí.
• Dokazovaní Selektivní Lineární Definitní rezolucí.
• Při výpočtu Prologu se konstruuje a prochází SLD strom.
V rámci IB015
• Princip výpočtu s využitím příkladů a neformální demonstrace postupu bez intelektuální zátěže odpovídajícího teoretického fundamentu.
IB015 Neimperativní programování - 09
str. 28/35
Pořadí faktů v databázi
Pozorování
• Při výpočtu Prolog vždy využívá fakta v tom pořadí, v jakém jsou uvedeny v programu.
Příklad
• players(flink,gta5). players(f link,worlcLof _tanks) . players(f link,master_of_orion) .
• ?- players(flink,X). X = gta5 ;
X = worlcLof _tanks ; X = master_of _orion.
• ?- players(flink,X). X = gta5 .
/* uživatel vložil ; */ /* uživatel vložil ; */
/* uživatel vložil . */
IB015 Neimperativní programování - 09
str. 29/35
Príbeh slečny Prology, aneb jak s pravidly
svaly(honza) . svaly(karel) .
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
■v(X)
p(karel). p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X).
IB015 Neimperativní programovaní - 09
str.
Príbeh slečny Prology
v(X) :- p(X), s(X) v(nouma) .
p(karel). p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X).
X=_G1
?- p(_G1), s(_G1)
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel). p(milos) . p(honza) .
s (tomas) . s (honza) . s(karel).
G1 =karel
?-v(X).
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p(honza) .
s (tomas) . s (honza) . s(karel).
?-v(X).
G1 =karel
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel
X= G1
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel). p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ;
X= G1
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ;
X= G1
G1 =karel
?- s(karel)
?	-PLG1), sLG1)		
_G1 =	=milos		
	?- s(milos)		
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ;
X= G1
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p(honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ;
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel). p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ;
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel). p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ; honza
/* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ; honza ;
/* uživatel vložil ; */ /* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ; honza ;
X=nouma
/* uživatel vložil ; */ /* uživatel vložil ; */
IB015 Neimperativní programovaní - 09
str. 31/35
Príbeh slečny Prology
v(X) :- p(X), s(X). v(nouma) .
p(karel) . p(milos) . p (honza) .
s(tomas). s (honza) . s(karel).
?-v(X). karel ; honza ; nouma.
/* uživatel vložil ; */ /* uživatel vložil ; */
X=nouma
IB015 Neimperativní programovaní - 09
str. 31/35
Konstrukce výpočetního stromu
• Pro první podcíl v daném vrcholu se prohledává databáze faktů a pravidel vždy od začátku. Pro každou nalezenou vyhovující položku je vytvořen nový vrchol.
• Vrchol je vytvořen tak, že první podcíl se unifikuje s hlavou nalezené položky, a v nově vzniklém vrcholu je nahrazen tělem nalezené položky (fakta mají prázdné tělo, cíl je "vynechán").
• Hrana vedoucí do nového vrcholu je anotována unifikačním přiřazením. Proměnné vyskytující se v těle pravidla, které nejsou dotčeny unifikací, jsou označeny čerstvou proměnnou.
• Prázdné vrcholy (listy) značí úspěch, hodnoty hledaných proměnných vyplývají z unifikačních přiřazenních na cestě od listu ke kořeni stromu.
• Vrcholy, pro které se nepodařilo nalézt položku v databázi vyhovující prvnímu podcíli jsou označeny podvrcholem fail.
IB015 Neimperativní programování - 09
str. 32/35
Výpočet s rekurzí
-f(G1)
r(a,b). r (a, c) . f (a).
f(X):-f(Y),r(Y,X).
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
r(a,b). r (a, c) . f (a).
f(X):-f(Y),r(Y,X).
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
[f(X):-f(Y),r(Y,X)] X=G1, Y=G2
r(a,b). r(a,c). f (a).
f(X):-f(Y),r(Y,X).
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
?- f(G1)
?-r(a,G1)
r(a,b). r(a,c). f (a).
f(X):-f(Y),r(Y,X).
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
?- f(G1)
r(a,b). r(a,c). f (a).
f(X):-f(Y),r(Y,X).
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
?- f(G1)
r(a,b). r(a,c). f (a).
f (X):-i (Y) ,r(Y,X) .
IB015 Neimperativní programování - 09
str.
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
str. 33/35
Výpočet s rekurzí
IB015 Neimperativní programovaní - 09
str. 33/35
Rizika výpočtu a doporučení
Pozorování
• Strom je procházen algoritmem prohledávání do hloubky.
• Výpočet nad nekonečnou větví stromu prakticky končí chybovou hláškou o nedostatečné velikosti paměti zásobníku.
• Použití levorekurzivních pravidel (první podcíl v těla pravidla je rekurzivní použití hlavy pravidla) často vede k nekonečné větvi, a to i v případě, kdy počet vyhovujících přiřazení na původní dotaz je konečný.
• Pořadí faktů a pravidel v databázi neovlivní počet úspěšných listů ve výpočetním stromu, ale ovlivní jejich umístění (tj. pořadí, ve kterém budou nalezeny a prezentovány uživateli.)
Doporučení
• Používají se pravorekurzivní definice pravidel.
• Fakta se uvádějí před pravidly.
IB015 Neimperativní programování - 09 str. 34/35
Domácí cvičení
Příklad
• S využitím znalostí prezentovaných v této přednášce naprogramujte nad databází měst:
mesto(prague). mesto(viena). mesto(warsaw). mesto(roma). mesto(paris) . mesto(madrid).
predikát triMesta/3, který je pravdivý pokud jako argumenty dostane tři různá města uvedené v databázi.
Nekonečný výpočet
• Narhněte program v jazyce Prolog takový, aby ze zadání bylo zřejmé, že odpověď na určený dotaz je pravdivá, ovšem výpočet Prologu k tomuto výsledků nikdy nedospěje.
IB015 Neimperativní programování - 09
str. 35/35