IB013 Logické programování Hana Rudová jaro 2013 Hodnocení předmětu Průběžná písemná práce: až 30 bodů (základy programování v Prologu) ■ pro každého jediný termín: 26.března ■ alternativní termín pouze v případech závažných důvodů pro neúčast ■ vzor písemky na webu předmětu Závěrečná písemná práce: až 1 50 bodů ■ vzor písemky na webu předmětu ■ opravný termín možný jako ústní zkouška Zápočtový projekt: celkem až 40 bodů Hodnocení: součet bodů za projekt a za obě písemky ■ známka A za cca 1 75 bodů, známka F za cca 11 0 bodů ■ známka bude zapsána pouze těm, kteří dostanou zápočet za projekt Ukončení předmětu zápočtem: zápočet udělen za zápočtový projekt Hana Rudová, Logické programování I, 15. května 2013 2 Organizace předmětu Základní informace ■ Přednáška: účast není povinná, nicméně ... ■ Cvičení: účast povinná ■ individuální doplňující příklady za zmeškaná cvičení ■ nelze při vysoké neúčasti na cvičení ■ skupina 01, sudá středa, první cvičení 6.března, Hana Rudová ■ skupina 02, lichá středa, první cvičení 27.února, Adriana Strejčkova ■ Předpoklad: znalost základů výrokové a predikátové logiky, např. z IB1 01 ■ Web předmětu: interaktivní osnova v ISu ■ průsvitky dostupné postupně v průběhu semestru ■ sbírka příkladů včetně řešení (zveřejněna cca do 8.3.) ■ harmonogram výuky, předběžný obsah výuky během semestru ■ elektronicky dostupné materiály ■ informace o zápočtových projektech Hana Rudová, Logické programování I, 15. května 2013 3 Organizace předmětu Rámcový obsah predmetu Obsah přednášky ■ základy programování v jazyce Prolog ■ teorie logického programováni ■ logické programování s omezujícími podmínkami ■ DC gramatiky Obsah cvičení ■ zaměřeno na praktické aspekty, u počítačů ■ programování v Prologu ■ logické programování ■ logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 1 5. května 201 3 4 Organizace předmětu Literatura Bratko, I. Prolog Programming for Artificial Intelligence. Addison-Wesley, 2001. ■ prezenčně v knihovně Clocksin, W. F. - Mellish, Ch. S. Programming in Prolog. Springer, 1 994. Sterling, L. - Shapiro, E. Y. The art of Prolog : advanced programming techniques. MIT Press, 1 987. Nerode, A. - Shore, R. A. Logic for applications. Springer-Verlag, 1 993. ■ prezenčně v knihovně Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ prezenčně v knihovně Elektronicky dostupné materiály (viz web předmětu) Hana Rudová, Logické programování I, 1 5. května 201 3 5 Organizace předmětu Průběžná písemná práce ■ Pro každého jediný termín 26. března ■ Alternativní termín pouze v závažných důvodech pro neúčast ■ Celkem až 30 bodů (1 50 závěrečná písemka, 40 projekt) ■ 3 příklady, 40 minut ■ Napsat zadaný predikát, porovnat chování programů ■ Obsah: první čtyři přednášky a první dvě cvičení ■ Oblasti, kterých se budou příklady zejména týkat ■ unifikace ■ seznamy ■ backtracking ■ optimalizace posledního volání ■ řez ■ aritmetika ■ Ukázka průběžné písemné práce na webu Hana Rudová, Logické programování I, 15. května 2013 6 Organizace předmětu Zápočtové projekty ■ Zadání, dotazy, odevzdávání: Adriana Strejčkova ■ Týmová práce na projektech, až 3 řešitelé ■ zápočtové projekty dostupné přes web předmětu ■ Podrobné pokyny k zápočtovým projektům na webu předmětu ■ bodování, obsah předběžné zprávy a projektu ■ typ projektu: LP, CLP ■ Předběžná zpráva ■ podrobné zadání ■ vjakém rozsahu chcete úlohu řešit ■ které vstupní informace bude program používat a co bude výstupem programu ■ scénáře použití programu (tj. ukázky dvojic konkrétních vstupů a výstupů) Hana Rudová, Logické programování I, 1 5. května 201 3 7 Organizace předmětu Časový harmonogram k projektům ■ Zveřejnění zadání (většiny) projektů: 26. února ■ Zahájení registrace řešitelů projektu: 13. března, 19:00 ■ Předběžná analýza řešeného problému: 12. dubna ■ Odevzdání projektů: 17. května ■ Předvádění projektů (po registraci): 23.května - 20.června Hana Rudová, Logické programování I, 1 5. května 201 3 8 Organizace předmětu Software: SICStus Prolog ■ Doporučovaná implementace Prologu ■ Dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html ■ Komerční produkt ■ licence pro instalace na domácí počítače studentů ■ Používané IDE pro SICStus Prolog SPIDER ■ dostupné od verze SICStus 4.1.3 ■ http://www.si cs.se/si cstus/spi der ■ používá Eclipse SDK ■ Podrobné informace dostupné přes web předmětu ■ stažení SICStus Prologu (sw + licenční klíče) ■ pokyny k instalaci (SICStus Prolog, Eclipse, Spider) Hana Rudová, Logické programování I, 15. května 2013 9 Organizace předmětu SICStus IDE SPIDER ^ STCStus Debugging - My Prolog Project/imy_imcdule.pro - Eclipse SDK File Edit SICStus Source Navigate Search Project Run Favorites Window Help II i-:^ E [-9 SICStusDebu,,. | ■ : P- Debug ' Or «3> .If. Š I ^ ^ Prolog Top-level Configuration [SICStus Launch Configuration Typel] Prolog Target = call: 5uffbt[L3,_7551,c],_1810) EE my_predlL1810j p£j Prolog Top-le/el Process W= Variables £3 Name ♦ Suff G© Breakpoints Ifc *6 B * x Value [a, _7551, c] 1810 my_module.pro £3 \. /* -*- Mode:Prolog -*- */ :- roodule (rf_y_rcodule , [rc_y_predl/l , ir.y pred3/J £ T-'s.m-s" ^rjoufc export!undefined predicate ]) ■ : - use_rcodule (library (lists)- , [postf ±x./2f % varns ah out Importing undefined predicate suFFix/2 ¥ integrated Jielp falso for user predicatesJ It 1 OutNne kT\ e my_predl/l y my_pred2/2 suffixPList ?SLlffllO is true when List and Suffix are lists and Suffix is a suffix of List. It terminates only if List is proper, and has at most N+l solutions Suffixes are enumerated in descending order of length, (documentation formatting will be improved later!)_ rp.y_pzedl (X) : - EtiFF = [a., Singleton, c], assert: (seen xs [X} )■ „ ¥ varns about missing declaration ^nere dynaniic/1} suffix(Suff, X)r pielude(SuFF, X) . i warns about calling undefined predicate my_pred2(£, Xs) :- £ varn about non-trivial singleton variables ( foreach ("f, Xs) do write(S, Xs) ) f ( Foiea.clUY,Xs), pararaf [SJ ) do wiite(5F X3} ) ■ "■ ■ SICStu ^g^^^l Tasks] Hi Problems' £1 li D Tep level 1 in C:/Users/perm.EnCS-AD/runtime-EclipseAppfication42/My Prolog Project j i 2 2 Exit: assert (icy module: seen xs ( 13I0J) ? 3 2 Call: suffix([a,_7551,c],_1810> ? | 1 i n* Hana Rudová, Logické programování I, 1 5. května 201 3 10 převzato z http://www.sics.se/siestus/spider Organizace předmětu Úvod do Prologu Prolog ■ PROgramming in LOGic ■ část predikátové logiky prvního řádu ■ Deklarativní programování ■ specifikační jazyk, jasná sémantika, nevhodné pro procedurální postupy ■ Co dělat namísto Jak dělat ■ Základní mechanismy ■ unifikace, stromové datové struktury, automatický backtracking Hana Rudová, Logické programování I, 1 5. května 201 3 12 Úvod do Prologu Logické programování Historie ■ Rozvoj začíná po roce 1 970 ■ Robert Kowalski - teoretické základy ■ Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace ■ SICStus Prolog vyvíjen od roku 1 985 ■ Logické programování s omezujícími podmínkami - od poloviny 80. let Aplikace ■ rozpoznávání řeči, telekomunikace, biotechnologie, logistika, plánování, data mining, business rules, ... ■ SICStus Prolog —the first 25 years, Mats Carlsson, Per Mildner. Theory and Practice of Logic Programming, 12 (1-2): 35-66, 2012. http://arxiv.org/abs/1011.5640. Hana Rudová, Logické programování I, 15. května 2013 13 Úvod do Prologu Program = fakta + pravidla ■ (Prologovský) program je seznam programových klauzulí ■ programové klauzule: fakt, pravidlo ■ Fakt: deklaruje vždy pravdivé věci ■ clovek( novak, 18, student ). ■ Pravidlo: deklaruje věci, jejichž pravdivost závisí na daných podmínkách ■ studuje( X ) :- clovek( X, _Vek, student ). ■ alternativní (obousměrný) význam pravidel pro každé X, pro každé X, X studuje, jestliže Xje student, potom X je student X studuje ■ pracuje( X ) :- clovek( X, _Vek, CoDela ), prace( CoDela ). ■ Predikát: seznam pravidel a faktů se stejným funktorem a aritou ■ značíme: clovek/3, student/l; analogie procedury v procedurálních jazycích, Hana Rudová, Logické programování I, 15. května 2013 14 Úvod do Prologu Komentáře k syntaxi ■ Klauzule ukončeny tečkou ■ Základní příklady argumentů ■ konstanty: (tomas, anna) ... začínají malým písmenem ■ proměnné ■ X, Y ... začínají velkým písmenem ■ _, _A, _B ... začínají podtržítkem (nezajímá nás vracená hodnota) ■ Psaní komentářů clovek( novak, 18, student ). % komentář na konci řádku clovek( novotny, 30, učitel ). /-komentář */ Hana Rudová, Logické programování I, 1 5. května 201 3 Úvod do Prologu Dotaz ■ Dotaz: uživatel se ptá programu, zda jsou věci pravdivé ?- studuje( novak ). ?- studuje( novotny ). % no % yes splnitelný dotaz nesplnitelný dotaz ■ Odpověď na dotaz ■ positivní - dotaz je splnitelný a uspěl ■ negativní - dotaz je nesplnitelný a neuspěl ■ Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty) ■ ?- clovek( novak, 18, Prače ). Prače = student ■ výsledkem dotazu je instanciace proměnných v dotazu ■ dosud nenainstanciovaná proměnná: volná proměnná ■ Prolog umí generovat více odpovědí, pokud existují ?- clovek( novak, Vek, Prače ). % všechna řešení přes ";" Hana Rudová, Logické programování 1,15. května 2013 16 Úvod do Prologu Klauzule = fakt, pravidlo, dotaz Klauzule se skládá z hlavy a těla Tělo je seznam cílů oddělených čárkami, čárka = konjunkce Fakt: pouze hlava, prázdné tělo ■ rodic( pavla, robert ). Pravidlo: hlava i tělo ■ upracovany_clovek( X ) :- clovek( X, _Vek, Prace ), prace( Prace, tezka ). Dotaz: prázdná hlava, pouze tělo ■ ?- clovek( novak, Vek, Prace ). ?- rodic( pavla, Dite ), rodic( Dite, Vnuk ). Hana Rudová, Logické programování I, 1 5. května 201 3 Úvod do Prologu Rekurzivní pravidla predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2) rodic( Y, Z ). predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 1 5. května 201 3 18 Úvod do Prologu Příklad: rodokmen rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, eliska ). rodicC robert, anna ). rodic( robert, petr ). rodic( petr, jirka ). pavla tomas Rodiče robert eliska anna petr / / jirka Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 1 5. května 201 3 19 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas,robert) rodi rodi rodi rodi rodi c( pavla, robert ). c( tomas, robert ). c( tomas, eliska ). c( robert, anna ). c( robert, petr ). rodic( petr, jirka ). predek(tomas,robert) dle (1) t yes rodic(tomas,robert) predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 1 5. května 201 3 20 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas, petr) predek(tomas, petr) dle (1) t dle (2') no rodic( tomas, petr) rodic(tomas, Y) predek( Y, petr) rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, petr ). Y=robert t dle rodic(tomas, robert) predek( robert, petr) predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ) , % (2') predek( Y, Z ) . y dle (1) rodic(robert, petr) yes Hana Rudová, Logické programování I, 1 5. května 201 3 21 Úvod do Prologu Odpověď na dotaz s proměnnou pavla tomas Rodiče rodic( pavla, robert ). rodič C tomas, robert ). rodic( tomas, eliska ). robert eliska rodic( robert, anna ). / \ rodic( robert, petr ). / \ rodic( petr, ji rka ). anna petr / \ jirka ! Deti predekC X, Z ) :- rodicC X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ) . predek(petr,Potomek) --> ??? predek(robert,P) --> ??? Hana Rudová, Logické programování I, 1 5. května 201 3 22 Potomek=ji rka 1. P=anna, 2. P=petr, 3. P=jirka Úvod do Prologu Syntaxe a význam Prologovských programů Syntaxe Prologovských programů ■ Typy objektů jsou rozpoznávány podle syntaxe ■ Atom ■ řetězce písmen, čísel, „_" začínající malým písmenem: pavel , pavel_novak, x25 ■ řetězce speciálních znaků: <-->, ====> ■ řetězce v apostrofech: 'Pavel', 'Pavel Novák' ■ Celá a reálná čísla: 0, -1056, 0.35 ■ Proměnná ■ řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_" ■ anonymní proměnná: ma_dite(X) :- rodic( X, _ ). ■ hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodic( X, _ ) ■ lexikální rozsah proměnné je pouze jedna klauzule: prvni(X,X,X). prvni(X,X,_)■ Hana Rudová, Logické programování I, 1 5. května 201 3 24 Syntaxe a význam Prologovských programů Termy ■ Term - datové objekty v Prologu: datum( 1, kveten, 2003 ) ■ funktor: datum ■ argumenty: 1, kveten, 2003 ■ arita - počet argumentů: 3 ■ Všechny strukturované objekty v Prologu jsou stromy ■ trojuhelnik( bod(4,2), bod(6,4), bod(7,l) ) ■ Hlavní funktor termu - funktor v kořenu stromu odpovídající termu ■ troj uhel ni k je hlavní funktor v troj uhel ni k( bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 1 5. května 201 3 25 Syntaxe a význam Prologovských programů Unifikace ■ Termy jsou unifikovatelné, jestliže ■ jsou identické nebo ■ proměnné v obou termech mohou být instanciovány tak, že termyjsou po substituci identické ■ datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 ■ Hledáme nejobecnější unifikátor (most general unifier (MGU) ■ jiné instanciace?...Dl = 1, Ml = 5, Y2 = 2003 ... není MGU ■ ?- datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml. ■ Test výskytu (occurs check) ?- X=f(X). x = f(f(f(f(f(f(f(f(f(f(...)))))))))) Hana Rudová, Logické programování I, 1 5. května 201 3 26 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1. S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy ■ S a T mají stejný funktor a aritu a ■ všechny jejich odpovídající argumenty jsou unifikovatelné ■ výsledná substituce je určena unifikací argumentů Příklady: k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,l(l)) = A ... yes s(sss(2),B,ss(2)) s(sss(A),4,ss(3)) s(sss(A),4,ss(C)) s(sss(2),4,ss(2),s(l))... no s(sss(2),4,ss(A))... no s(sss(t(B)),4,ss(A))... A=t(B),C=t(B)... yes Hana Rudová, Logické programování I, 1 5. května 201 3 27 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů ■ p :- q, r. ■ Deklarativní: Co je výstupem programu? ■ p je pravdivé, jestliže q a r jsou pravdivé ■ Z q a r plyne p => význam mají logické relace ■ Procedurální: Jak vypočítáme výstup programu? ■ p vyřešíme tak, že nejprve vyřešíme q a pak r => kromě logických relací je významné i pořadí cílů ■ výstup ■ indikátor yes/no určující, zda byly cíle splněny ■ instanciace proměnných v případě splnění cílů Hana Rudová, Logické programování I, 1 5. května 201 3 28 Syntaxe a význam Prologovských programů Konjunce "," vs. disjunkce ";" cílů ■ Konjunce = nutné splnění všech cílů ■ p : - q, r. ■ Disjunkce = stačí splnění libovolného cíle ■ p :- q; r. p:-q. p : - r. ■ priorita středníku je vyšší (viz ekvivalentní zápisy): p :-q, r; s, t, u. p :- (q, r) ; (s, t, u). P :- q, r. p : - s, t, u. Hana Rudová, Logické programování I, 1 5. května 201 3 29 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílu (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l,l). % nenalezení odpovědi: nekonečný cyklus (c) a(X) :- b(X,Y), c(Y). ?- a(X). b(l,l). c(2). cd). (d) a(X) :- c(Y), b(X,Y). % změněné pořadí cílů v těle klauzule vzhledem k (c) b(l,l). c(2). c(l) . % náročnější nalezení první odpovědi než u (c) V obou případech stejný deklarativní ale odlišný procedurální význam Hana Rudová, Logické programování I, 1 5. května 201 3 30 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílu II. (1) a(X) :- c(Y), b(X,Y) (2) b(l,l). (3) c(2). (4) c(l). Vyzkoušejte si: (1) a(X) :- b(X,X), c(X) (3) a(X) :- b(Y,X), c(X) (4) b(2,2). (5) b(2,l). (6) c(l). ?- a(X). a(X) dle (1) c(Y), b(X,Y) dle(3)/Ý=2 dle(4KY=1 b(X,2) no b(X,1) dle (2) X=1 yes Hana Rudová, Logické programování I, 1 5. května 201 3 31 Syntaxe a význam Prologovských programů Cvičení: průběh výpočtu a :- b,c,d. b :- e,c,f,g. b :- g,h. c. d. e : - i . e : - h. g- h. i . Jak vypadá průběh výpočtu pro dotaz ?- a. Hana Rudová, Logické programování I, 1 5. května 201 3 32 Syntaxe a význam Prologovských programů Operátory, aritmetika Operátory Infixová notace: 2*a + b*c Prefixová notace:+( "(2, a), "(b, c) ) priorita +: 500, priorita *: 400 ■ prefixovou notaci lze získat predikátem display/l :- display((a:-s(0),b,c)). :-(a, ,(s(0), ,(b,c))) Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor Uživatelsky definované operátory: zna petr zna alese. zna( petr, alese). Definice operátoru: :- op( 600, xfx, zna ). priorita: 1 ..1200 ■ :- op( 1100, xfy, ; ). nestrukturované objekty: 0 :- op( 1000, xfy, , ). p :- q, r; s, t. p :- (q , r) ; (s, t). ; má vyšší prioritu než , ■ :- op( 1200, xfx, :- ). :-má nejvyšší prioritu Definice operátoru není spojena s datovými manipulacemi (kromě spec. případů) Hana Rudová, Logické programování I, 15. května 2013 34 Operátory, aritmetika Typy operátorů ■ Typy operátorů ■ infixové operátory: xfx, xfy, yfx př. xfx = yfx - ■ prefixové operátory: fx, fy př. fx ?- fy - ■ postfixové operátory: xf, yf ■ x a y určují prioritu argumentu ■ x reprezentuje argument, jehož priorita musí být striktně menší než u operátoru ■ y reprezentuje argument, jehož priorita je menší nebo rovna operátoru ■ a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx správne a by priorita: 500 priorita: 0 priorita: 0 priorita: 500 Hana Rudová, Logické programování I, 1 5. května 201 3 35 Operátory, aritmetika Aritmetika Předdefinované operátory + , -, *, /, "-mocnina,// celočíselné děleni, mod zbytek po dělení ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci ?- X i s 1 + 2. X = 3 „i s" je speciální předdefinovaný operátor, který vynutí evaluaci ■ porovnej: N = (1+1+1+1+1) N i s (1+1+1+1+1) ■ pravá strana musí být vyhodnotitelný výraz (bez proměnné) ■ výraz na pravé straně je nejdříve aritmeticky vyhodnocen a pak unifikován s levou stranou volání?- X is Y + 1. způsobí chybu Další speciální předdefinované operátory >, <, >=, =<, =: = aritmetická rovnost, =\= aritmetická nerovnost ■ porovnej: 1+2 =:= 2+1 1+2 = 2+1 ■ obě strany musí být vyhodnotitelný výraz: volání ?- 1 < A + 2. způsobí chybu Hana Rudová, Logické programování I, 15. května 2013 36 Operátory, aritmetika Různé typy rovností a porovnání X = Y XaY jsou u n ifi kováte Iné X \= Y XaY nejsou unifikovatelné, (také \+ X = Y) X == Y XaY jsou identické porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X \== Y XaY nejsou identické porovnej: ?- A \== B. ... yes ?- A=B, A \== B. ... A no X is Y Y je aritmeticky vyhodnoceno a výsledek je přiřazen X X =:= Y XaY jsou si aritmeticky rovny X =\= Y X a Y si aritmeticky nejsou rovny X < Y aritmetická hodnota X je menší než Y (=<, >, >=) X @< Y term X předchází term Y (@=<, @>, @>=) 1. porovnání termů: podle alfabetického n. aritmetického uspořádání 2. porovnání struktur: podle arity, pak hlavního funktoru a pak zleva podle argumentů ?- f( pavel, g(b)) @< f( pavel, h (a)). ... yes Hana Rudová, Logické programování I, 15. května 2013 37 Operátory, aritmetika Řez, negace Řez a upnutí f(X,0) f(X,2) f(X,4) - X < 3, ! . - 3 =< X, X < 6, ! - 6 =< X. přidání operátoru řezu ,,! ?- f(l,Y), Y>2. f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4). ?- fd,Y). Smazání řezu v (1) a (2) změní chování programu Upnutí: po splnění podcílů před řezem se už další klauzule neuvažují Hana Rudová, Logické programování I, 1 5. května 201 3 39 Rez, negace Řez a ořezání f(X,Y) :- s(X,Y). s(X,Y) :- Y i s X + 1. s(X,Y) :- Y i s X + 2. f(X,Y) :- s(X,Y), !. s(X,Y) :- Y is X + 1. s(X,Y) :- Y is X + 2. ?- fd,Z). ?- f(l,Z). Z = 2?; Z = 2?; Z = 3 ? ; no no ■ Ořezání: po splnění podcílů před řezem se už neuvažuje další možné splnění těchto podcílů ■ Smazání řezu změní chování programu Hana Rudová, Logické programování I, 1 5. května 201 3 40 Řez, negace Chování operátoru řezu Předpokládejme, že klauzule H :- TI, T2, Tm, !, ...Tn.je aktivována voláním cíle G, který je unifikovatelný s H. G=h(X,Y) V momentě, kdy je nalezen řez, existuje řešení cílů TI, ..., Tm Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také unifikovatelná s G X=1,Y=1 Ořezání: při provádění řezu se už další možné splnění cílů TI, ..., Tm nehledá a všechny ostatní alternativy jsou odstraněny Y=2 X=2 ?- h(X,Y). h(l,Y) :- tl(Y), ! h(2,Y) :- a. tl(l) :- b. tl(2) :- c. h(X,Y) X=l / \ X=2 tl(Y) a (vynechej: upnutí) Y=l / \ Y=2 b c (vynechej: ořezání) / Hana Rudová, Logické programování I, 1 5. května 201 3 41 Rez, negace Rez: návrat na rodiče ?- a(X). (1) a(X) :- h(X,Y). (2) a(X) :- d. (3) h(l,Y) :- tl(Y), !, e(X) (4) h(2,Y) :- a. (5) tl(l) :- b. (6) tl(2) :- c. (7) b :- c. (8) b :- d. (9) d. (10) e(l) . (11) e(2). a(x) h(X,Y) d X/ly tl(Y),!,e(X') upnutí □ Y/l / X b,!,e(X') ořezání c,!,e(X') d,!,e(X') no !,e(X') j e(X') X'/l X \ XV2 ■ Po zpracování klauzule s řezem se vracím až na rodiče této klauzule, tj. a(X) Hana Rudová, Logické programování I, 15. května 2013 42 Řez, negace c(X) :- p(X), c(X) :- v(X). Řez: příklad cl(X) :- p(X), !. cl(X) :- v(X). P(l). p(2) v(2). ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- cl(2). true ? ; %p(2) no ?_ X X X no c (X) = 1 ? = 2 ? = 21 %P(D %P(2) %v(2) ?- cl(X). X = 1 ? ; %p(l) no Hana Rudová, Logické programování I, 1 5. května 201 3 43 ■v Rez: cvičení 1. Porovnejte chování uvedených programů pro zadané dotazy. a(X,X) :- b(X). a(X,X) :- b(X),!. a(X,X) :- b(X),c. a(X,Y) :- Y is X+l. a(X,Y) :- Y is X+l. a(X,Y) :- Y is X+l. b(X) :- X > 10. b(X) :- X > 10. b(X) :- X > 10. c ■ - 1 ?- a(X,Y). ?- a(l,Y). ?- a(ll,Y). 2. Napište predikát pro výpočet maxima max( X, Y, Max ) Hana Rudová, Logické programování I, 1 5. května 201 3 44 Řez, negace Typy řezu Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet Poznámka: na vstupu pro X očekávám číslo Zelený řez: odstraní pouze neúspěšná odvození ■ f(X,l) :- X >= 0, !. f(X,-l) :- X < 0. bez řezu zkouším pro nezáporná čísla 2. klauzuli Modrý řez: odstraní redundantní řešení ■ f(X,l) :- X >= 0, !. f(0,l). f(X,-l) :- X < 0. bez řezu vrací f(0,l) 2x Červený řez: odstraní úspěšná řešení ■ f(X,l) :- X >= 0, !. f(_X,-l). bez řezu uspěje 2. klauzule pro nezáporná čísla Hana Rudová, Logické programování I, 1 5. května 201 3 45 Řez, negace Negace jako neúspěch ■ Speciální cíl pro nepravdu (neúspěch) fail a pravdu true ■ X a Y nejsou unifikovatelné: different (X, Y) ■ different^ X, Y ) :- X = Y, !, fail. differentC _X, _Y ). ■ Xje muž: muz(X) muz( X ) :- zena( X ), !, fail. muz( _X ). Hana Rudová, Logické programování I, 1 5. května 201 3 46 Řez, negace Negace jako neúspěch: operátor \+ different(X,Y) :- X = Y, !, fail. muz(X) :- zena(X), !, fail different(_X,_Y). muz(_X). Unární operátor \+ P ■ jestliže P uspěje, potom \+ P neuspěje \+(P) :- P, !, fail . ■ v opačném případě \+ P uspěje \+(_). differentC X, Y ) :- \+ X=Y. muz( X ) :- \+ zena( X ). Pozor: takto definovaná negace \+P vyžaduje konečné odvození P Hana Rudová, Logické programování I, 1 5. května 201 3 47 Řez, negace Negace a proměnné \+(P) :- P, !, fail . % (I) \+(_). % (II) dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumne( Auto ) :- % (4) \+ drahe( Auto ). ?- dobre( X ), rozumne( X ). Hana Rudová, Logické programování I, 1 5. května 201 3 dobre(X),rozumne(X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) \ dle (II) dle (I) ^ drahe(citroen),!5 fail ^ yes no 48 Řez, negace Negace \+(P) :- P, !, fail. % (I) \+C_). % (ID dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumneC Auto ) :- % (4) \+ drahe( Auto ). ?- rozumneC X ), dobre( X ). Hana Rudová, Logické programování I, 1 5. května 201 3 49 Pr°měnrEámne(X),dobre(X) dle (4) \+ drahe(X), dobre(X) dle (I) drahe(X),!,fail,dobre(X) dle (3), X/bmw !, fail, dobre(bmw) fail,dobre(bmw) no Řez, negace Bezpečný cíl ■ ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no ■ ?- rozumneC citroen ). yes ?- rozumne( X ). no ■ \+ P je bezpečný: proměnné P jsou v okamžiku volání P instanciovány ■ negaci používáme pouze pro bezpečný cíl P Hana Rudová, Logické programování I, 1 5. května 201 3 50 Řez, negace Chování negace ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no ?- draheC X ). PTÁME SE: existuje X takové, že drahe( X ) platí? ?- \+ drahe( X ). \+ drahe( X) :- drahe(X),!,fail. \+drahe(X). z definice \+ plyne: není dokazatelné, že existuje X takové, že drahe( X ) platí tj. pro všechna X platí \+ drahe( X ) TEDY: pro cíle s negací neplatí existuje X takové, že \+ drahe( X ) negace jako neúspěch není ekvivalentní negaci v matematické logice Negace jako neúspěch používá předpoklad uzavřeného světa pravdivé je pouze to, co je dokazatelné Hana Rudová, Logické programování I, 1 5. května 201 3 51 Řez, negace Predikáty na řízení běhu programu L ■ řez,,!" ■ fai 1: cíl, který vždy neuspěje true: cíl, který vždy uspěje ■ \+ P: negace jako neúspěch \+ P :- P, !, fail; true. ■ once(P): vrátí pouze jedno řešení cíle P once(P) :- P, !. ■ Vyjádření podmínky: P -> Q ; R ■ jestliže platí P tak Q (P -> Q ; R) : - P, ! , Q. ■ v opačném případě R (P -> Q ; R) :- R. ■ příklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. ■ P -> Q ■ odpovídá: (P -> Q; fail) ■ příklad: záporne (X) :- number(X) -> X < 0. Hana Rudová, Logické programování I, 15. května 201 3 52 Řez, negace Predikáty na řízení běhu programu II. ■ cal 1 (P): zavolá cíl P a uspěje, pokud uspěje P ■ nekonečná posloupnost backtrackovacích voleb: repeat repeat. repeat :- repeat. klasické použití: generuj akci X, proveď ji a otestuj, zda neskončit Hlava :- ... uloz_stav( StaryStav ), repeat, generujC X ), % deterministické: generuj, prováděj, testuj prováděj( X ), testuj( X ), i ■ > obnov_stav( StaryStav ), Hana Rudová, Logické programování I, 15. května 201 3 53 Řez, negace Seznamy Reprezentace seznamu ■ Seznam: [a, b, c], prázdný seznam [] ■ Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) ■ všechny strukturované objekty stromy - i seznamy ■ funktordva argumenty ■ .(a, .(b, .(c, []))) = [a, b, c] ■ notace: [ Hlava | Telo ] = [a | Tel o] Tel o je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ■ Lze psát i: [a,b|Telo] ■ před "I"je libovolný počet prvků seznamu , za"|"je seznam zbývajících prvků ■ [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] ■ pozor: [ [a,b] | [c] ] + [ a,b | [c] ] ■ Seznam jako neúplná datová struktura: [a,b,c|T] ■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 15. května 201 3 55 Seznamy Prvek seznamu memberC X, S ) platí: memberC b, [a,b,c] ). neplatí: memberC b, [[a,b]|[c]] ). X je prvek seznamu S, když ■ X je hlava seznamu S nebo memberC X, [ X | _ ] ). %(1) ■ X je prvek těla seznamu S memberC X, [ _ | Telo ] ) :- memberC X, Telo ). %C2) Příklady použití: ■ member(l,[2,1,3]). ■ member(X,[1,2,3]) . Hana Rudová, Logické programování I, 1 5. května 201 3 56 dle (1) □ yes dle (1 □ yes member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) dle (2) member(1,[3,1,4]) dle (2) member(1,[1,4]) dle (2) member(1,[4]) dle (2) member(1,[ ]) dle (2) no Seznamy Spojení seznamů append( LI, L2, L3 ) Platí: append( [a,b], [c,d], [a,b,c,d] ) Neplatí: append( [b,a], [c,d], [a,b,c,d] ), append( [a,[b]], [c,d], [a,b,c,d] ) Definice: ■ pokud je 1. argument prázdný seznam, pak 2. a 3. argument jsou stejné seznamy: append( [], S, S ). ■ pokud je 1. argument neprázdný seznam, pak má 3. argument stejnou hlavu jako 1 append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). X S1 S2 S3 Hana Rudová, Logické programování I, 1 5. května 201 3 57 Cvičení: append/2 appendC [], S, S ). % (1) append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). % (2) :- append([l,2],[3,4],A). I (2) I A=[1|B] I :- append([2],[3,4],B). I (2) I B=[2|C] => A=[1,2|C] I :- append([],[3,4],C). I CD I C=[3,4] => A=[l,2,3,4], I yes Hana Rudová, Logické programování I, 1 5. května 201 3 58 Seznamy Optimalizace posledního volání Last Call Optimization (LCO) Implementační technika snižující nároky na paměť Mnoho vnořených rekurzivních volání je náročné na paměť Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky Typický příklad, kdy je možné použití LCO: ■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule ■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické ■ p( ...):- ... % žádné rekurzivní voláni v těle klauzule p( ...):- ... % žádné rekurzivni voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 1 5. května 201 3 59 Seznamy LCO a akumulátor Reformulace rekurzivní procedury, aby umožnila LCO Výpočet délky seznamu length( Seznam, Délka ) length( [] , 0 ) . length( [ H | T ], Délka ) :- length( T, DelkaO ), Délka is 1 + DelkaO. Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát length( [] , Délka, Délka ). % celková délka = započítaná délka length( [ H | T ], A, Délka ) :- A0 is A + 1, length( T, A0, Délka ). Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 1 5. května 201 3 60 Seznamy max_list s akumu m Výpočet největšího prvku v seznamu max_li st (Seznam, Max) max_list([X], X). max_list([X|T], Max) :-max_li st(T,MaxT), ( MaxT >= X, !, Max = MaxT Max = X ). max_list([H|T],Max) :- max_li st(T,H,Max). max_list([], Max, Max). max_list([H|T], CastecnyMax, Max) :-( H > CastecnyMax, !, max_list(T, H, Max ) max_list(T, CastecnyMax, Max) ). Hana Rudová, Logické programování I, 1 5. května 201 3 61 Seznamy Akumulátor jako seznam Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverseC Seznam, OpacnySeznam ) ■ reverse( [], [] ). reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). ■ naivní reverse s kvadratickou složitosti reverse pomocí akumulátoru s lineární složitostí ■% reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi reverse( Seznam, OpacnySeznam ) :- reverse( Seznam, [], OpacnySeznam). reverse( [], S, S ). reverse( [ H | T ], A, Opacny) :- reverse( T, [ H | A ], Opacny ). % přidání H do akumulátoru ■ zpětná konstrukce seznamu (srovnej s předchozí dopřednou konstrukcí, např. append) Hana Rudová, Logické programování I, 15. května 2013 62 Seznamy reverse/2: cvičení reverse( Seznam, OpacnySeznam ) :- % (1) reverse( Seznam, [], OpacnySeznam). reverse( [], S, S ). % (2) reverse( [ H | T ], A, Opacny ) :- % (3) reverse( T, [ H | A ], Opacny ). ? - reverse([l,2,3],0). reverse([l,2,3],0) - (1) reverse([l,2,3], [], 0) - (3) reverse([2,3] , [1], 0) - (3) reverse([3] , [2,1], 0) - (3) reverse([], [3,2,1], 0) - (2) yes 0=[3,2,1] Hana Rudová, Logické programování I, 1 5. května 201 3 63 Seznamy Neefektivita při spojování seznamů Sjednocení dvou seznamů append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3 ). ?- append( [2,3], [1], S ). postupné volání cílů: append( [2,3], [1], S ) - append( [3], [1], S') - append( [], [1], S" Vždy je nutné projít celý první seznam Hana Rudová, Logické programování I, 1 5. května 201 3 64 Sez Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3,1|Z2]-Z2 ?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 = [2,3|Zl] - Z2 = [2,3| [1|Z2] ] - Z2 Zl = [1|Z2] S = [2,3,1|Z2]-Z2 Jednotková složitost, oblíbená technika ale není tak flexibilní A1 Z1 A2 mm L1 Z2 m L2 L3 Hana Rudová, Logické programování I, 1 5. května 201 3 65 Seznamy Akumulátor vs. rozdílové seznamy: reverse reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :-reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). kvadratická složitost reverse( Seznam, Opacny ) :- reverseO( Seznam, [], Opacny ). reverseO( [], S, S ). reverseO( [ H | T ], A, Opacny ) :- reverseO( T, [ H | A ], Opacny ). akumulátor (lineárni) reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[]). reverseO( [], S-S ). reverseO( [ H | T ], Opacny-OpacnyKonec ) :- rozdilové seznamy reverseO( T, Opacny-[ H | OpacnyKonec] ). (lineárni) Příklad: operace pro manipulaci s frontou ■ test na prázdnost, přidání na konec, odebrání ze začátku Hana Rudová, Logické programování I, 1 5. května 201 3 66 Seznamy Vestavěné predikáty Vestavěné predikáty ■ Predikáty pro řízení běhu programu ■ fail , true, ... ■ Různé typy rovností ■ unifikace, aritmetická rovnost, ... ■ Databázové operace ■ změna programu (programové databáze) za jeho běhu ■ Vstup a výstup ■ Všechna řešení programu ■ Testování typu termu ■ proměnná?, konstanta?, struktura?, ... ■ Konstrukce a dekompozice termu ■ argumenty?, funktor?, ... Hana Rudová, Logické programování I, 15. května 2013 68 Vestavěné predikáty Databázové operace Databáze: specifikace množiny relací Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly) Vestavěné predikáty pro změnu databáze během provádění programu: assertC Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 1 5. května 201 3 69 Vestavěné predikáty Příklad: databázové operace ■ Caching: odpovědi na dotazy jsou přidány do programové databáze ■ ?- solve( problem, Solution), asserta( solve( problem, Solution) ). ■ :- dynamic solve/2. % nezbytné při použití v SICStus Prologu ■ Příklad: uloz_trojice( Seznámí, Seznam2 ) :-member( XI, Seznámí ), member( X2, Seznam2 ), spocitej_treti( XI, X2, X3 ), assertz( trojice( XI, X2, X3 ) ), f ai 1 . uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování I, 15. května 2013 70 Vestavěné predikáty Vstup a výstup program může číst data ze vstupního proudu (input stream) program může zapisovat data do výstupního proudu (output stream) dva aktivní proudy ■ aktivní vstupní proud ■ aktivní výstupní proud uživatelský terminál - user ■ datový vstup z terminálu chápán jako jeden ze vstupních proudů ■ datový výstup na terminál chápán jako jeden z výstupních proudů soubor 1 soubor 2 user vstupní proudy uživatelsky terminal program user soubor 3 soubor 4 výstupní proudy Hana Rudová, Logické programování I, 1 5. května 201 3 71 Vestavěné predikáty Vstupní a výstupní proudy: vestavěné predikáty ■ změna (otevření) aktivního vstupního/výstupního proudu: see(S)/tell (S) ctěni( Soubor ) :- see( Soubor ), cteni_ze_souboru( Informace ), see( user ). ■ uzavření aktivního vstupního/výstupního proudu: seen/told ■ zjištění aktivního vstupního/výstupního proudu: seeing(S)/tel 1 i ng(S) ctěni( Soubor ) :- seeing( StarySoubor ), see( Soubor ), cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování I, 1 5. května 201 3 72 Vestavěné predikáty Sekvenční přístup k textovým souborům čtení dalšího termu: read(Term) ■ při čtení jsou termy odděleny tečkou I ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme ■ po dosažení konce souboru je vrácen atom end_of_fi le zápis dalšího termu: write(Term) ?- write ( ahoj ). ?- write( 'Ahoj Petre!' ). nový řádek na výstup: nl N mezer na výstup: tab(N) čtení/zápis dalšího znaku: getO(Znak) , get(NeprazdnyZnak)/put(Znak) ■ po dosažení konce souboru je vrácena -1 Hana Rudová, Logické programování I, 1 5. května 201 3 73 Vestavěné predikáty Příklad čtení ze souboru process_file( Soubor ) :- seeingC StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1e, i ■ » seen, see( StarySoubor ). repeat. repeat :- repeat. % zjištěni aktivního proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % opakováni Hana Rudová, Logické programování I, 1 5. května 201 3 74 Vestavěné predikáty Ctení programu ze souboru ■ Interpretování kódu programu ■ ?- consult(program). ■ ?- consultCprogram.pl') . ■ ?- consult( [programl, 'program2.pl'] ). ■ Kompilace kódu programu ■ ?- compile( [programl, 'program2.pl'] ). ■ ?- [program]. ■ ?- [user]. zadávání kódu ze vstupu ukončené CTRL+D ■ další varianty podobně jako u interpretování ■ typické zrychlení: 5 až 1 O krát Hana Rudová, Logické programování I, 1 5. května 201 3 75 Vestavěné predikáty Všechna řešení Backtracking vrací pouze jedno řešení po druhém Všechna řešení dostupná najednou: bagof/3, setof/3, findall/3 bagof ( X, P, S ): vrátí seznam S, všech objektů X takových, že P je splněno vek( petr, 7 ) . vek( anna, 5 ). vek( tomas, 5 ). ?- bagof( Dite, vek( Dite, 5 ), Seznam ). Seznam = [ anna, tomas ] Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagof( Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, 1 5. května 201 3 76 Vestavěné predikáty Všechna řešení II ■ Pokud neexistuje řešení bagof(X, P,S) neuspěje ■ bagof: pokud nějaké řešení existuje několikrát, pak S obsahuje duplicity ■ bagof, setof, findall: P je libovolný cíl vek( petr, 7 ) . vek( anna, 5 ). vek( tomas, 5 ). ?- bagof ( Dite, ( vek( Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] ■ bagof, setof, findall: na objekty shromažďované v X nejsou žádná omezení: X je term ?- bagof( Dite-Vek, vek( Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programování I, 1 5. května 201 3 77 Vestavěné predikáty Existenční kvantifikátor " Přidání existenčního kvantifikátoru „~ " =^> hodnota proměnné nemá význam ?- bagof( Dite, Vek"vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] Anonymní proměnné jsou všeobecně kvantifikovány, i když jejich hodnota není (jako vždy) vracena na výstup ?- bagof( Dite, vek( Dite, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna,tomas] Před operátorem „~ " může být i seznam ?- bagof( Vek ,[Jméno,Prijmeni]"vek( Jméno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování I, 1 5. května 201 3 78 Vestavěné predikáty Všechna řešení III ■ setof( X, P, S ): rozdíly od bagof ■ S je uspořádaný podle @< ■ případné duplicity v S jsou eliminovány ■ findall( X, P, S ): rozdíly od bagof ■ všechny proměnné jsou existenčně kvantifikovány ?- findall( Dite, vek( Dite, Vek ), Seznam ). => v S jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou ■ výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S = [] ■ ?- bagof( Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findall( Dite, vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování I, 15. května 2013 79 Vestavěné predikáty Testování typu termu var(X) X je volná proměnná nonvar(X) X není proměnná atom(X) X je atom (pavel, 'Pavel Novák', <-->) integer(X) X je integer float(X) X je float atomic(X) X je atom nebo číslo compound(X) X je struktura Hana Rudová, Logické programování I, 1 5. května 201 3 80 Vestavěné predikáty Určení počtu výskytů prvku v seznamu count( X, S, N ) :- count( X, S, 0, N ). count( _, [], N, N ). count( X, [X|S], NO, N) :- !, NI is NO + 1, count( X, S, NI, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) :-? count( a, [a,b,X,Y], N). N=3 N=3 count( _, [], N, N ). count( X, [Y|S], NO, N ) :- nonvar(Y), X = Y, !, NI is NO + 1, count( X, S, NI, N ). count( X, [_|S], NO, N ) :- count( X, S, NO, N ). Hana Rudová, Logické programování I, 1 5. května 201 3 81 Vestavěné predikáty Konstrukce a dekompozice atomu Atom (opakování) ■ řetězce písmen, čísel, „_" začínající malým písmenem: pavel , pavel_novak, x2 , x4_34 ■ řetězce speciálních znaků: +, <->, ===> ■ řetězce v apostrofech: ' Pavel' , 'Pavel Novák', 'prší', 'ano' ?- 'ano'=A. A = ano Řetězec znaků v uvozovkách ■ př. "ano", "Pavel" ?- A="Pavel". ?- A="ano". A = [80,97,118,101,108] A=[97,110,111] ■ př. použití: konstrukce a dekompozice atomu na znaky, vstup a výstup do souboru Konstrukce atomu ze znaků, rozložení atomu na znaky name( Atom, SeznamASCIIKodu ) name( ano, [97,110,111] ) name( ano, "ano" ) Hana Rudová, Logické programování I, 15. května 2013 82 Vestavěné predikáty Konstrukce a dekompozice termu ■ Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], call( Cil ) atom =. . X => X = [atom] ■ Pokud chci znát pouze funktor nebo některé argumenty, pak je efektivnější: functor( Term, Funktor, Arita ) functor( a(9,e), a, 2 ) functor(atom,atom,0) ) functor(l,l,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 1 5. května 201 3 83 Vestavěné predikáty Rekurzivní rozklad termu Term je proměnná (var/1), atom nebo číslo (atomic/1) => konec rozkladu procházení seznamu a rozklad každého prvku seznamu Term je složený (=. ./2 , f unctor/3) => procházení seznamu argumentů a rozklad každého argumentu Příklad: ground/1 uspěje, pokud v termu nejsou proměnné; jinak neuspěje ground(Term) :- atomic(Term), !. ground(Term) :- var(Term), !, fail. ground([H|T]) :- !, ground(H), ground(T). ground(Term) :- Term =.. [ _Funktor | Argumenty ], Term je seznam ([_|_]) => [] ... řešen výše jako atomic ground( Argumenty ). ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2,[a(l,3),b,c])). no yes Hana Rudová, Logické programování I, 1 5. května 201 3 84 Vestavěné predikáty Příklad: dekompozice termu L ■ count_term( Integer, Term, N ) určí počet výskytů celého čísla v termu ■ ?- count_term( 1, a(l,2,b(x,z(a,b,1)),Y), N ). N=2 ■ count_term( X, T, N ) :- count_term( X, T, 0, N). count_term( X, T, NO, N ) :- integer(T), X = T, !, N i s NO + 1. count_term( _, T, N, N ) :- atomic(T), !. count_term( _, T, N, N ) :- var(T), !. count_term( X, T, NO, N ) :- T =.. [ _ | Argumenty ], count_arg( X, Argumenty, NO, N ). count_arg( _, [], N, N ). count_arg( X, [ H | T ], NO, N ) :- count_term( X, H, 0, Nl), N2 i s NO + Nl, count_arg( X, T, N2, N ). ■ ?- count_term( 1, [a,2,[b,c],[d,[e,f],Y]], N ). count_term( X, T, NO, N ) :- T = [_|_], !, count_arg( X, T, NO, N ). klauzuli přidáme před poslední klauzuli count_term/4 Hana Rudová, Logické programování I, 15. května 2013 85 Vestavěné predikáty Cvičení: dekompozice termu ■ Napište predikát substitute( Podterm, Term, Podterml, Terml), který nahradí všechny výskyty Podterm v Term termem Podterml a výsledek vrátí v Terml ■ Předpokládejte, že Term a Podterm jsou termy bez proměnných ■ ?- substitute( sin(x), 2*sin(x)*f(sin(x)), t, F ). F=2*t*f(t) Hana Rudová, Logické programování I, 1 5. května 201 3 86 Vestavěné predikáty Technika a styl programování v Prologu Technika a styl programování v Prologu ■ Styl programování v Prologu ■ některá pravidla správného stylu ■ správný vs. špatný styl ■ komentáře ■ Ladění ■ Efektivita Hana Rudová, Logické programování I, 1 5. května 201 3 88 Technika a styl programování v Prologu Styl programování v Prologu L ■ Cílem stylistických konvencí je ■ redukce nebezpečí programovacích chyb ■ psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují ■ Některá pravidla správného stylu ■ krátké klauzule ■ krátké procedury; dlouhé procedury pouze s uniformní strukturou (tabulka) ■ klauzule se základními (hraničními) případy psát před rekurzivními klauzulemi ■ vhodná jména procedur a proměnných ■ nepoužívat seznamy ([. . .]) nebo závorky ({...}, (...)) pro termy pevné arity ■ vstupní argumenty psát před výstupními ■ struktura programu - jednotné konvence v rámci celého programu, např. ■ mezery, prázdné řádky, odsazení ■ klauzule stejné procedury na jednom místě; prázdné řádky mezi klauzulemi; každý cíl na zvláštním řádku Hana Rudová, Logické programování I, 1 5. května 201 3 89 Technika a styl programování v Prologu Správný styl programování ■ konstrukce setříděného seznamu Seznam3 ze setříděných seznamů Seznámí, Seznam2: merge( Seznámí, Seznam2, Seznam3 ) ■ mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) ■ merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :-X < Y, !, mergeC Telol, [Y|Telo2], Telo3 ). mergeC Seznámí, [Y|Telo2], [Y|Telo3] ) :-mergeC Seznámí, Telo2, Telo3 ). Hana Rudová, Logické programování I, 1 5. května 201 3 90 Technika a styl programování v Prologu Špatný styl programování mergeC SI, S2, S3 ) :- 51 =[],!, S3 = S2 ; % první seznam je prázdný 52 = [] , ! , S3 = SI; % druhý seznam je prázdný 51 = [X|TI], 52 = [Y|T2], ( X < Y, ! , Z = X, % Z je hlava seznamu S3 mergeC TI, S2, T3 ); Z = Y, mergeC SI, T2, T3) ), 53 = [Z | T3 ] . Hana Rudová, Logické programování I, 1 5. května 201 3 91 Technika a styl programování v Prologu Styl programování v Prologu II ■ Středník „;" může způsobit nesrozumitelnost klauzule ■ nedávat středník na konec řádku, používat závorky ■ v některých případech: rozdělení klauzle se středníkem do více klauzulí ■ Opatrné používání operátoru řezu ■ preferovat použití zeleného řezu (nemění deklarativní sémantiku) ■ červený řez používat v jasně definovaných konstruktech ■ Opatrné používání negace „\+" ■ negace jako neúspěch: negace není ekvivalentní negaci v matematické logice ■ Pozor na assert a retract: snižuji transparentnost chování programu negace: P, !, fail; true alternativy: Podminka, !, Cill ; Cil2 Podminka -> Cill Cil 2 \+ P Hana Rudová, Logické programování I, 1 5. května 201 3 92 Technika a styl programování v Prologu Dokumentace a komentáře ■ co program dělá, jak ho používat (jaký cíl spustit a jaké jsou očekávané výsledky), příklad použití ■ které predikáty jsou hlavní (top-level) ■ jak jsou hlavní koncepty (objekty) reprezentovány ■ doba výpočtu a paměťové nároky ■ jaké jsou limitace programu ■ zda jsou použity nějaké speciální rysy závislé na systému ■ jaký je význam predikátů v programu, jaké jsou jejich argumenty, které jsou vstupní a které výstupní (pokud víme) ■ vstupní argumenty „+", výstupní „-" merge( +Seznaml, +Seznam2 , -Seznam3 ) ■ JmenoPredikatu/Arita merge/3 ■ algoritmické a implementační podrobnosti Hana Rudová, Logické programování I, 1 5. května 201 3 93 Technika a styl programování v Prologu Ladění ■ Přepínače na trasování: trace/0, notrace/0 ■ Trasování specifického predikátu: spy/1, nospy/1 ■ spy( merge/3 ) ■ debug/0, nodebug/0: pro trasování pouze predikátů zadaných spy/1 ■ Libovolná část programu může být spuštěna zadáním vhodného dotazu: trasování cíle ■ vstupní informace: jméno predikátu, hodnoty argumentů při volání ■ výstupní informace ■ při úspěchu hodnoty argumentů splňující cíl ■ při neúspěchu indikace chyby ■ nové vyvolání přes stejný cíl je volán při backtrackingu Hana Rudová, Logické programování I, 1 5. května 201 3 94 Technika a styl programování v Prologu Krabičkový (4-branový) model ■ Vizualizace řídícího toku (backtrackingu) na úrovni predikátu ■ Call: volání cíle ■ Exit: úspěšné ukončení volání cíle ■ Fai 1: volání cíle neuspělo ■ Redo: jeden z následujících cílů neuspěl a systém backtrackuje, aby nalezl alternativy k předchozímu řešení Call Exit > + predek( X, Z ) :- rodic( X, Z ). + > < I predekC X, Z ) :- rodic( X, Y ), + predekC Y, Z ). + < Fail Redo Hana Rudová, Logické programování I, 1 5. května 201 3 95 Technika a styl programování v Prologu a (X) a (X) a (X) cd). d(2). - nonvar(X) - c(X). - d(X). Příklad: trasování a (X). Call I ------> + a(X) I a(X) <------+ a(X) Fai 1 I I Exi t nonvar(X).| ------> c(X). I d(X). + <------ I Redo ? X = 1 ? 1 1 Call : 2 2 Call : 2 2 Fai 1: 3 2 Call: 3 2 Exi t: 1 1 Exit: > 1 1 Redo: 4 2 Call: 4 2 Exi t: 1 1 Exi t: X = 2 ? no % trace I ?- a(_463) ? nonvar(_463) ? nonvar(_463) ? c(_463) ? c(l) ? a(l) ? a(l) ? d(_463) ? d(2) ? a(2) ? Hana Rudová, Logické programování I, 1 5. května 201 3 96 Technika a styl programování v Prologu Efektivita ■ Čas výpočtu, paměťové nároky, a také časové nároky na vývoj programu ■ u Prologu můžeme častěji narazit na problémy s časem výpočtu a pamětí ■ Prologovské aplikace redukují čas na vývoj ■ vhodnost pro symbolické, nenumerické výpočty se strukturovanými objekty a relacemi mezi nimi ■ Pro zvýšení efektivity je nutno se zabývat procedurálními aspekty ■ zlepšení efektivity při prohledávání ■ odstranění zbytečného backtrackingu ■ zrušení provádění zbytečných alternativ co nejdříve ■ návrh vhodnějších datových struktur, které umožní efektivnější operace s objekty Hana Rudová, Logické programování I, 1 5. května 201 3 97 Technika a styl programování v Prologu Zlepšení efektivity: základní techniky Optimalizace posledního volání (LCO) a akumulátory Rozdílové seznamy při spojování seznamů Caching: uložení vypočítaných výsledků do programové databáze Indexace podle prvního argumentu ■ např. v SICStus Prologu ■ při volání predikátu s prvním nainstaniovaným argumentem se používá hašovací tabulka zpřístupňující pouze odpovídající klauzule ■ zamestnanec( Prijmem', KrestniJméno, Odděleni, ...) ■ seznamy( [], ...) :- ... . seznamy( [H|T], ...) :- ... . Determinismus: ■ rozhodnout, které klauzule mají uspět vícekrát, ověřit požadovaný determinismus Hana Rudová, Logické programování I, 1 5. května 201 3 98 Technika a styl programování v Prologu Rezoluce v predikátové logice l.řádu Rezoluce ■ rezoluční princip: z F v A, G v ->A odvodit F v G ■ dokazovací metoda používaná ■ v Prologu ■ ve většině systémů pro automatické dokazování ■ procedura pro vyvrácení ■ hledáme důkaz pro negaci formule ■ snažíme se dokázat, že negace formule je nesplnitelná => formule je vždy pravdivá Hana Rudová, Logické programování I, 1 5. května 201 3 100 Rezoluce v PL1 Formule literál / ■ pozitivní literál = atomická formule p(ti, • • • ,tn) ■ negativní literál = negace atomické formule —>p(ŕi, ■ ■ ■ ,tn) ■ ti, ■ ■ ■ , tn jsou termy klauzule C = konečná množina literálů reprezentující jejich disjunkci ■ příklad: p(X) vq(aj) v ^p(Y) notace: {p(X),q(a,f),^p(Y)} ■ klauzule je pravdivá <=> je pravdivý alespoň jeden z jejích literálů ■ prázdná klauzule se značí □ a je vždy nepravdivá (neexistuje v ní pravdivý literál) formule F = množina klauzulí reprezentující jejich konjunkci ■ formule je v tzv. konjuktivní normální formě (konjunkce disjunkcí) ■ příklad: (p v q) a (-*p) A(pv^vr) notace: {{p,q}, {^p}, {p, ~^q,r}} ■ formule je pravdivá <=> všechny klauzule jsou pravdivé ■ prázdná formule je vždy pravdivá (neexistuje klauzule, která by byla nepravdivá) množinová notace: literál je prvek klauzule, klauzule je prvek formule, ... Hana Rudová, Logické programování I, 15. května 2013 101 Rezoluce v Splnitelnost [Opakování:] Interpretace 2 jazyka X je dána univerzem V a zobrazením, které přiřadí konstantě c prvek T>, funkčnímu symbolu f In n-ární operaci v T> a predikátovému symbolu p/n n-ární relaci. ■ příklad: F = {{/(a,i?) = f(b,a)},{f(f(a,a),b) = a}} interpretace li. T> = Z, a := 1, b := -1,/ := " + " Formule je splnitelná, existuje-li interpretace, pro kterou je pravdivá ■ formule je konjunkce klauzulí, tj. všechny klauzule musí být v dané interpretaci pravdivé ■ příklad (pokrač.): F je splnitelná (je pravdivá v 1\) Formule je nesplnitelná, neexistuje-li interpretace, pro kterou je pravdivá ■ tj. formule je ve všech iterpretacích nepravdivá ■ tj. neexistuje interpretace, ve které by byly všechny klauzule pravdivé ■ příklad: G = {{p(b)}, {p(a)}, {^p(a)}} je nesplnitelná {{p{a)} a {^p(a)} nemohou být zároveň pravdivé) Hana Rudová, Logické programování I, 15. května 2013 102 Rezoluce v PLI Rezoluční princip ve výrokové logice ■ Rezoluční princip = pravidlo, které umožňuje odvodit z klauzulí Ci u {1} a u C2 klauzuli C\ u C2 Ciuffl H}uc2 Ci u C2 ■ Ci u C2 se nazývá rezolventou původních klauzulí ■ příklad: {p,r} {~"T, 5} (p v r) a (->r v 5) obě klauzule (p v r) a (->r v s) musí být pravdivé protože r nestačí k pravdivosti obou klauzulí, musí být pravdivé p (pokud je pravdivé ->r) nebo s (pokud je pravdivé r), tedy platí klauzule p v s Hana Rudová, Logické programování I, 1 5. května 201 3 103 Rezoluce v PL1 Rezoluční důkaz ■ rezoluční důkaz klauzule C z formule F je konečná posloupnost Ci,... ,Cn = C klauzulí taková, že Q je buď klauzule z F nebo rezolventa Q, Q pro k J < í. ■ příklad: rezoluční důkaz {p} z formule F = {{p,r}, {q, ->r}, Q = {p, r} klauzule z F Cz = {q, ""^l klauzule z F Q = {p, g} rezolventa C\ a C2 Q = í-1^} klauzule z F C5 = {p} = C rezolventa C3 a C4 Hana Rudová, Logické programování I, 1 5. května 201 3 104 Rezoluce v PLI Rezoluční vyvrácení důkaz pravdivosti formule F spočívá v demonstraci nesplnitelnosti ->F ■ nesplnitelná => ^Fje nepravdivá ve všech interpretacích => F je vždy pravdivá začneme-li z klauzulí reprezentujících musíme postupným uplatňováním rezolučního principu dospět k prázdné klauzuli □ Příklad: F... ->a v a G — ->F... a a ->a G = ->F... {{a}, {->a}} Ci = {a},C2 = {^a} rezolventa C\ a C2 je □, tj. F je vždy pravdivá rezoluční důkaz □ z formule G se nazývá rezoluční vyvrácení formule G ■ a tedy G je nepravdivá ve všech interpretacích, tj. G je nesplnitelná Hana Rudová, Logické programování I, 15. května 2013 105 Rezoluce v PL1 Strom rezolučního důkazu ■ strom rezolučního důkazu klauzule C z formule G je binární strom: ■ kořen je označen klauzulí C, ■ listyjsou označeny klauzulemi z G a ■ každý uzel, který není listem, ■ má bezprostředními potomky označené klauzulemi C\ a C2 ■ je označen rezolventou klauzulí C\ a C2 ■ příklad: G = {{p,r}, {q, -.r}, {^q}, {^p}} {p,r} {q,^r} {^q} {^p} c = □ strom rezolučního vyvrácení (rezoluční důkaz □ z G) příklad: {{p,r}, {q, -.r}, {^q}, {^p, t}, {^s}, {s, ^t}} Hana Rudová, Logické programování I, 1 5. května 201 3 106 Rezoluce v PLI Substituce co s proměnnými? vhodná substituce a unifikace ■ f(X,a,g(Y)) < l,f(h(c),a,Z) < 1, X = h(c), Z = g{Y) => f(h(c),a,g(Y)) < 1 substituce je libovolná funkce 0 zobrazující výrazy do výrazů tak, že platí ■ 6{E) = E pro libovolnou konstantu E ■ 6(f(Ei, ■ ■ ■ ,En)) = f(6(Ei), ■ ■ ■ , 6{En)) pro libovolný funkční symbol / ■ 6(p(Ei, ■ ■ ■ ,En)) = p(6(Ei), ■ ■ ■ , 6{En)) pro libovolný predik. symbol p substituce je tedy homomorfismus výrazů, který zachová vše kromě proměnných - ty lze nahradit čímkoliv substituce zapisujeme zpravidla ve tvaru seznamu [Ai/gi, ■ ■ ■ ,Xn/gn] kde Xi jsou proměnné a §i substituované termy ■ příklad: p(X)[X/f(a)] = p(f(a)) přejmenování proměnných: speciální náhrada proměnných proměnnými ■ příklad: p(X)[X/Y] = p(Y) Hana Rudová, Logické programování I, 15. května 2013 107 Rezoluce v Unifikace Ztotožnění dvou literálů p, q pomocí vhodné substituce varianty rezoluční metody vylepšení prohledávání ■ zastavit prohledávání cest, které nejsou slibné ■ specifikace pořadí, jak procházíme alternativními cestami Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce v Varianty rezoluční metody Věta: Každé omezení rezoluce je korektní. ■ stále víme, že to, co jsme dokázali, platí T-rezoluce: klauzule účastnící se rezoluce nejsou tautologie úplná ■ tautologie nepomůže ukázat, že formule je nesplnitelná sémantická rezoluce: úplná zvolíme libovolnou interpretaci a pro rezoluci používáme jen takové klauzule, z nichž alespoň jedna je v této interpretaci nepravdivá ■ pokud jsou obě klauzule pravdivé, těžko odvodíme nesplnitelnost formule vstupní (input) rezoluce: neúplná alespoň jedna z klauzulí, použitá při rezoluci, je z výchozí vstupní množiny S ■ {{p,a), i^P,q}, {p,^q}, {^P,^q}} existuje rezoluční vyvrácení neexistuje rezoluční vyvrácení pomocí vstupní rezoluce Hana Rudová, Logické programování I, 15. května 2013 113 Rezoluce v PL1 Rezoluce a logické programování Lineární rezoluce varianta rezoluční metody ■ snaha o generování lineární posloupnosti místo stromu ■ v každém kroku kromě prvního můžeme použít bezprostředně předcházející rezolventu a k tomu buď některou z klauzulí vstupní množiny 5" nebo některou z předcházejících rezolvent lineární rezoluční důkaz C z S je posloupnost dvojic (Co,£o), ■ ■ ■ (Cn,Bn) taková, že C = Cn+\ a ■ Q a každá Bt jsou prvky S nebo některé Q, j < i ■ každá Q+i, í < n je rezolventa Q a Bt lineární vyvrácení S = lineární rezoluční důkaz □ z S Hana Rudová, Logické programování I, 15. května 2013 115 Rezoluce a logické programován Lineární rezoluce II příklad: S = {A\, A2, A3, A4} Ai = {p,q} A2 = {p,^q} A3 = {^p,q} A4 = {^p, ^q} S: vstupní množina klauzulí C{. střední klauzule C t B i íp,q}{p, -"27 \/ íp} {^p,q} Iq} {->p,- Ti,....->Tn} ■ Fakt: pouze jeden pozitivní literál ■ Prolog: H. Matematická logika: H Klauzule: {H} ■ Cílová klauzule: žádný pozitivní literál ■ Prolog: : - Ti,... Tn. Matematická logika: -Ti v ■ ■ ■ v ~^Tn Klauzule: {->7i, ■ ■ ■ ~^Tn} Hana Rudová, Logické programování I, 15. května 2013 117 Rezoluce a logické programování Logický program ■ Programová klauzule: právě jeden pozitivní literál (fakt nebo pravidlo) ■ Logický program: konečná množina programových klauzulí ■ Príklad: ■ logický program jako množina klauzulí: P = ÍPl,p2,P3) Pi = {p}, p2 = {p,^q}, P3 = {q} ■ logický program v prologovské notaci: P- p ■ -a- q. ■ cílová klauzule: G = {-^q} í^pI ípJ □ Hq} tel □ Střední klauzule jsou cílové klauzule Hana Rudová, Logické programování I, 1 5. května 201 3 119 Rezoluce a logické programování Lineární vstupní rezoluce Vstupní rezoluce na P u {G} ■ (opakování:) alespoň jedna z klauzulí použitá při rezoluci je z výchozí vstupní množiny ■ začneme s cílovou klauzulí: Co = G ■ boční klauzule jsou vždy z P (tj. jsou to programové klauzule) (Opakování:) Lineární rezoluční důkaz C z P je posloupnost dvojic {C0,B0), ... {Cn,Bn) taková, že C = Cn+1 a ■ Q a každá Bi jsou prvky P nebo některé Q, j < í ■ každá Ci+i, í < n je rezolventa Q a Bi Lineární vstupní (Linear Input) rezoluce (Ll-rezoluce) C z P u {G} posloupnost dvojic (Co,50), ... {Cn,Bn) taková, že C = Cn+i a ■ Co = G a každá #í JSOU prvky P lineární rezoluce + vstupní rezoluce ■ každá Ci+i, í < n je rezolventa Q a #í Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programování Cíle a fakta při lineární rezoluci ■ Věta: Je-li S nesplnitelná množina Hornových klauzulí, pak S obsahuje alespoň jeden cíl a jeden fakt. ■ pokud nepoužiji cíl, mám pouze fakta (1 požit.literál) a pravidla (1 požit.literál a alespoň jeden negat. literál), při rezoluci mi stále zůstává alespoň jeden požit, literál ■ pokud nepoužiji fakt, mám pouze cíle (negat.literály) a pravidla (1 požit.literál a alespoň jeden negat. literál), v rezolventě mi stále zůstávají negativní literály ■ Věta: Existuje-li rezoluční důkaz prázdné množiny z množiny S Hornových klauzulí, pak tento rezoluční strom má v listech jedinou cílovou klauzuli. ■ pokud začnu důkaz pravidlem a faktem, pak dostanu zase pravidlo ■ pokud začnu důkaz dvěma pravidly, pak dostanu zase pravidlo ■ na dvou faktech rezolvovat nelze => dokud nepoužiji cíl pracuji stále s množinou faktů a pravidel ■ pokud použiji v důkazu cílovou klauzulí, fakta mi ubírají negat.literály, pravidla mi je přidávají, v rezolventě mám stále samé negativní literály, tj. nelze rezolvovat s dalším cílem Hana Rudová, Logické programování I, 15. května 2013 121 Rezoluce a logické programování Korektnost a úplnost ■ Věta: Množina S Hornových klauzulí je nesplnitelná, právě když existuje rezoluční vyvrácení S pomocí vstupní rezoluce. ■ Korektnost platí stejně jako pro ostatní omezení rezoluce ■ Úplnost Ll-rezoluce pro Hornovy klauzule: Nechť P je množina programových klauzulí a G cílová klauzule. Je-li množina P u {G} Hornových klauzulí nesplnitelná, pak existuje rezoluční vyvrácení P u {G} pomocí Ll-rezoluce. ■ vstupní rezoluce pro (obecnou) formuli sama o sobě není úplná => Ll-rezoluce aplikovaná na (obecnou) formuli nezaručuje, že nalezeneme důkaz, i když formule platí! ■ Význam Ll-rezoluce pro Hornovy klauzule: ■ P = {Pi,...,Pn}, G = {Gi,..., Gm} ■ Ll-rezolucí ukážeme nesplnitelnost P\ a ■ ■ ■ a Pn a (->Gi v ■ ■ ■ v ^Gm) ■ pokud tedy předpokládáme, že program {Pi,...,Pn} platí, tak musí být nepravdivá (->Gi v ■ ■ ■ v ^Gm), tj. musí platit G\ a ■ ■ ■ a Gm Hana Rudová, Logické programování I, 1 5. května 201 3 1 22 Rezoluce a logické programování Uspořádané klauzule (definite clauses) Klauzule = množina literálů Uspořádaná klauzule (definite clause) = posloupnost literálů ■ nelze volně měnit pořadí literálů Rezoluční princip pro uspořádané klauzule: _{^Ap,..., ^An}_{B, ^Bp,..., ^Bm}_ {^A0,..., -"Aí-i, ^Bop,..., ^Bmp, -iAí+i, ..., ^An}<7 ■ uspořádaná rezolventa: {^Ao,..., -Aí-i, ~^Bop,..., -^Bmp, -At+i, ..., ^An}cr ■ p je přejmenování proměnných takové, že klauzule {Ao,..., An} a {B,Bo,.. .,Bm}p nemají společné proměnné ■ cr je nejobecnější unifikátor pro Ai a Bp ■ rezoluce je realizována na literálech -^Aicr aBpa ■ je dodržováno pořadí literálů, tj. {^Bqp, -^Bmp}a jde do uspořádané rezolventy přesně na pozici ^Aícr Hana Rudová, Logické programování I, 1 5. května 201 3 123 Rezoluce a logické programován Uspořádané klauzule II ■ Uspořádané klauzule _{^Ap,..., ^An}_{B, ^Bp,..., ^Bm}_ {^A0,..., -"Aí-i, ^Bop,..., ^Bmp, -iAí+i, ..., ^An}cr Hornovy klauzule ■ —Ao, ■ ■ ■ j An. B . ~Bq, ..., ■ — (Ao, ■ ■ ■, Ai_i,Bop,...,5m/9, Ai+i,..., An)(j. ■ Příklad: -nrd), ^i(X)} {r(Z), n^(z,X), ^r(3)} {-5(X),-^(l,A),-r(3),-ii(X)} : ŕ(Z) : -q(Z,X),r(3). :-5(X),^(l,A),r(3),ii(X). p = [X/A] a = [Z/l] Hana Rudová, Logické programování I, 1 5. května 201 3 1 24 Rezoluce a logické programování LD-rezoluce ■ LD-rezoluční vyvrácení množiny uspořádaných klauzulí P u {G} je posloupnost (Go, Co),..., (Gn, Cn) taková, že ■ Gí,Cí jsou uspořádané klauzule ■ G = G0 ■ Gn+i - □ ■ Gi je uspořádaná cílová klauzule ■ Ci je přejmenování klauzule z P ■ Ci neobsahuje proměnné, které jsou v Gj,j < i nebo vQ,fc<í ■ Gí+i,0 < i < n je uspořádaná rezolventa Gt a Cj ■ LD-rezoluce: korektní a úplná Hana Rudová, Logické programování I, 1 5. května 201 3 125 Rezoluce a logické programování SLD-rezoluce Lineární rezoluce se selekčním pravidlem = SLD-rezoluce (Selected Linear resolution for Definite clauses) ■ rezoluce ■ Selekční pravidlo ■ Lineární rezoluce ■ Definite (uspořádané) klauzule ■ vstupní rezoluce Selekční pravidlo R je funkce, která každé neprázdné klauzuli C přiřazuje nějaký z jejích literálů R{C) e C ■ při rezoluci vybírám z klauzule literál určený selekčním pravidlem Pokud se R neuvádí, pak se předpokládá výběr nejlevějšího literálu ■ nejlevější literál vybírá i Prolog Hana Rudová, Logické programování I, 1 5. května 201 3 1 26 Rezoluce a logické programován Lineární rezoluce se selekčním pravidlem P = {{p}ÁP,^q}Áq}}, G = {^q,^p} f^q,^p} (ql {^q,^p} ÍP) výběr y/ výběr | / nejlevějšího f^Pl ^ nejpravějšího í^l ^ literálu / literálu I / □ □ SLD-rezoluční vyvrácení P u {G} pomocí selekčního pravidla R je LD-rezoluční vyvrácení (Go, Co),..., (Gn, Cn) takové, že G = Go, Gn+\ = □ a R(Gi) je literál rezolvovaný v kroku i SLD-rezoluce - korektní, úplná Efektivita SLD-rezoluce je závislá na ■ selekčním pravidle # ■ způsobu výběru příslušné programové klauzule pro tvorbu rezolventy ■ v Prologu se vybírá vždy klauzule, která je v programu první Hana Rudová, Logické programování I, 1 5. května 201 3 1 27 Rezoluce a logické programován Příklad: SLD-strom :- t. t: t: V ■ P ■ q. s. u. : -t. -p,r. -s. -q,v. - u, w (1) (2) (3) (4) (5) (6) (7) :- s. v, r. fail u,w,r. (7) :- w,r. fail □ Hana Rudová, Logické programování I, 1 5. května 201 3 1 28 Rezoluce a logické programování Strom výpočtu (SLD-strom) SLD-strom je strom tvořený všemi možnými výpočetními posloupnostmi logického programu P vzhledem k cíli G kořenem stromu je cílová klauzule G v uzlech stromu jsou rezolventy (rodiče uzlu a programové klauzule) ■ číslo vybrané programové klauzule pro rezoluci je v příkladu uvedeno jako ohodnocení hrany listy jsou dvojího druhu: ■ označené prázdnou klauzulí - jedná se o úspěšné uzly (succes nodes) ■ označené neprázdnou klauzulí - jedná se o neúspěšné uzly (failure nodes) úplnost SLD-rezoluce zaručuje existenci cesty od kořene k úspěšnému uzlu pro každý možný výsledek příslušející cíli G Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programován Příklad: SLD-strom a výsledná substituce : -a(Z). a(X) : -b(X,Y),c(Y). a(X) : -c(X). fe(2,3). Ml,2). c(2). Cvičení: p(B) : -q(A,B),r(B). p (A) : -q(A,A). q(a, a). q(a, b). r(b). :— a(Z). (1) (2) (3) (4) (5) :-b(Z,Y), c(Y). [Z/2.Y/3] (3) / \(4) [Z/1 ,Y/2] (5) □ rz/ii (5) [Z/2] □ [Z/2] ve výsledné substituci jsou pouze proměnné z dotazu, výsledné substituce jsou [Z/l] a [Z/2] nezajímá mě substituce [172] Hana Rudová, Logické programování I, 1 5. května 201 3 1 30 Rezoluce a logické programování Výsledná substituce (answer substitution) q(a). p(a,b). :-q(X), p(X,Y). X=a, Y=b - q(X), p(X,Y). q(a). [X/a] :-p(a,Y). p(a,b). [Y/b] □ [X/a,Y/b] Každý krok SLD-rezoluce vytváří novou unifikační substituci 0i => potenciální instanciace proměnné ve vstupní cílové klauzuli Výsledná substituce (answer substitution) 0 — 0Q01 ' ' ' 0 n složení unifikací Hana Rudová, Logické programování I, 1 5. května 201 3 1 31 Rezoluce a logické programování Význam SLD-rezolučního vyvrácení P u {G} ■ Množina P programových klauzulí, cílová klauzule G ■ Dokazujeme nesplnitelnost (1) P A (VX)(-Gi(X) v -G2(X) v ■ ■ ■ v ^Gn(X)) kde G = {->Gi, ->G2, ■ ■ ■ , -"Gn} a X je vektor proměnných v G nesplnitelnost (1) je ekvivalentní tvrzení (2) a (3) (2) P h- -G (3) Ph-(3X)(Gi(X)A--- AGn(X)) a jedná se tak o důkaz existence vhodných objektů, které na základě vlastností množiny P splňují konjunkci literálů v cílové klauzuli ■ Důkaz nesplnitelnosti P u {G} znamená nalezení protipříkladu ten pomocí SLD-stromu konstruuje termy (odpověď) splňující konjunkci v (3) Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programování Výpočetní strategie Korektní výpočetní strategie prohledávání stromu výpočtu musí zaručit, že se každý (konečný) výsledek nalézt v konečném čase Korektní výpočetní strategie = prohledávání stromu do šířky ■ exponenciální paměťová náročnost ■ složité řídící struktury Použitelná výpočetní strategie = prohledávání stromu do hloubky ■ jednoduché řídící struktury (zásobník) ■ lineární paměťová náročnost ■ není ale úplná: nenalezne vyvrácení i když existuje ■ procházení nekonečné větve stromu výpočtu => na nekonečných stromech dojde k zacyklení ■ nedostaneme se tak na jiné existující úspěšné uzly Hana Rudová, Logické programování I, 1 5. května 201 3 1 33 Rezoluce a logické programován SLD-rezoluce v Prologu: úplnost Prolog: prohledávání stromu do hloubky => neúplnost použité výpočetní strategie Implementace SLD-rezoluce v Prologu není úplná logický program: q : -r. r : -q. dotaz: q. q, (D (2) (3) - r. :- q. q. □ Hana Rudová, Logické programování I, 1 5. května 201 3 1 34 Rezoluce a logické programování Test výskytu Kontrola, zda se proměnná vyskytuje v termu, kterým ji substituujeme ■ dotaz : -a(B,B). ■ logický program: a(X,f(X)). ■ by vedl k: [B/X], [X/f(X)] Unifikátor pro #(Xi,...,Xn) a g(f(X0,X0),f(X1,X1),... ,/(Xn_i,Xn_i)) ^1 =/(^Oi^o)i X2 = f(Xi, Xi),..., Xn = f(Xn-i,Xn-i) x2 = f (f (Xo,Xo),/(Xo,Xo)),... délka termu pro X^ exponenciálně narůstá ^> exponenciální složitost na ověření kontroly výskytu Test výskytu se při unifikaci v Prologu neprovádí Důsledek: 1-X = f(X) uspěje s X = f (f (f (f (f (f (f (f (f (f (...)))))))))) Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programován SLD-rezoluce v Prologu: korektnost ■ Implementace SLD-rezoluce v Prologu nepoužívá při unifikaci test výskytu => není korektní (1) t(X) : -p(X,X). : -t(X). p(Xj(X)). X = /(/(/(/(...)))))))))) problém se projeví (2) t: -p(X,X). : -t. p(X,f(X)). yes dokazovací systém nehledá unifikátor pro X a f(X) ■ Řešení: problém typu (2) převést na problém typu (1) ? ■ každá proměnná v hlavě klauzule se objeví i v těle, aby se vynutilo hledání unifikátoru (přidáme X = X pro každou X, která se vyskytuje pouze v hlavě) t: -p(X,X). p(X,f(X)):-X = X. ■ optimalizace v kompilátoru mohou způsobit opět odpověď „yes" Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programování Řízení implementace: řez nemá ale žádnou deklarativní sémantiku místo toho mění implementaci programu ová jako kterýkoliv jiný literál ořezání pokud uspěji => přeskočím řez a pokračuji jako by tam řez nebyl pokud ale neuspěji (a tedy i při backtrackingu) a vracím se přes řez => vracím se až na rodiče : -p. a zkouším další větev => nezkouším tedy další možnosti, jak splnit p upnutí => a nezkouším ani další možnosti, jak splnit q v SLD-stromu ořezání Hana Rudová, Logické programování I, 1 5. května 201 3 1 37 Rezoluce a logické programování Příklad: řez Hana Rudová, Logické programování I, 1 5. května 201 3 Rezoluce a logické programování Příklad: řez II b(X,Y),\,c(Y) c(X). a(X) : -a(X) : -&(2,3). b(l,2). c(2). s(X) : -a(X). s(X) : -p(X). p(B):-q(A,B),r(B) p (A) : A). q (a, a). q(a, b). (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) r{b). (12) Hana Rudová, Logické programování I, 1 5. května 201 3 :- s(X). :-b(X,Y),!,c(Y). [X/2.Y/3] (3^ (rez) :- c(3). fail 1 39 Rezoluce a logické programování Příklad: řez a(X) : -b(X,Y),c(Y),\. a(X) : -c(X). fc(2,3). Ml,2). c(2). s(X) : -a(X). : -p(X). p(B):-q(A,B),r(B). p (A) : -q(A, A). q(a, a). q(a, b). rib). (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) :-b(X,Y),c(Y),!. [X/2.Y/3] (3)/ \ (4) [X/1 ,Y/2] - c(3)J. •'- c(2J,/. fail (5) _ /. (rez) □ [X/11 Hana Rudová, Logické programování I, 1 5. května 201 3 140 Rezoluce a logické programování Operační a deklarativní sémantika Operační sémantika Operační sémantikou logického programu P rozumíme množinu O(P) všech atomických formulí bez proměnných, které lze pro nějaký cíl Q1 odvodit nějakým rezolučním důkazem ze vstupní množiny P u {§}. ^ímto výrazem jsou míněny všechny cíle, pro něž zmíněný rezoluční důkaz existuje. Deklarativní sémantika logického programu P ?? Hana Rudová, Logické programování I, 1 5. května 201 3 142 Sémantiky Opakování: interpretace ■ Interpretace 1 jazyka X je dána univerzem T> a zobrazením, které přiřadí konstantě c prvek V, funkčnímu symbolu f In n-ární operaci v V a predikátovému symbolu p/n n-ární relaci. ■ příklad: F = {{/(a,i?) = f(b,a)},{f(f(a,a),b) = a}} interpretace li. T> = Z, a := 1, b := -1,/ := " + " ■ Interpretace se nazývá modelem formule, je-li v ní tato formule pravdivá ■ interpretace množiny N s obvyklými operacemi je modelem formule ( 0 + s(0) = s(0)) Hana Rudová, Logické programování I, 1 5. května 201 3 143 Sémantiky Herbrandovy interpretace Omezení na obor skládající se ze symbolických výrazů tvořených z predikátových a funkčních symbolů daného jazyka ■ při zkoumání pravdivosti není nutné uvažovat modely nad všemi interpretacemi Herbrandovo univerzum: množina všech termů bez proměnných, které mohou být tvořeny funkčními symboly a konstantami daného jazyka Herbrandova interpretace: libovolná interpretace, která přiřazuje ■ proměnným prvky Herbrandova univerza ■ konstantám sebe samé ■ funkčním symbolům funkce, které symbolu f pro argumenty ti, ■ ■ ■ , tn přiřadí term f(tii ■ ■ ■ > tn) ■ predikátovým symbolům libovolnou funkci z Herbrand. univerza do pravdivostních hodnot Herbrandův model množiny uzavřených formulí T\ Herbrandova interpretace taková, že každá formule z T je v ní pravdivá. Hana Rudová, Logické programování I, 15. května 2013 144 Sémantiky Specifikace Herbrandova modelu Herbrandovy interpretace mají předdefinovaný význam funktorů a konstant Pro specifikaci Herbrandovy interpretace tedy stačí zadat relace pro každý predikátový symbol Příklad: Herbrandova interpretace a Herbrandův model množiny formulí lichy(s(0)). % (1) lichy(s(s(X))) :- lichy(X). % (2) 11 = 0 12 = ílichy(s(0))} % = {líchy(5(0)), líchy(5(5(5(0))))} 14 = {líchy(sn(0))\ntE {1,3,5,7,...}} 15 = {lichy(sn(0))\n e N}} není model (1) není model (2) není model (2) Herbrandův model (1) i (2) Herbrandův model (1) i (2) Hana Rudová, Logické programování I, 1 5. května 201 3 145 Sémantiky Příklad: Herbrandovy interpretace rodic(a,b). rodic(b,c). predek(X,Y) :- rodic(X,Y). predek(X,Z) :- rodic(X,Y), predek(Y,Z). 11 - {rodíc(a, b),rodíc(b, c), predek(a, b), predek(b, c),predek(a, c)} 12 - {rodičia,b),rodic{b,c), predek(a, b), predek(b, c),predek(a, c), predek(a, a)} li i i2 jsou Herbrandovy modely klauzulí Cvičení: Napište minimální Herbrandův model pro následující logický program. muz(petr). muz(pavel). zena(olga). zena(jitka). pary(X,Y) :- zena(X), muz(Y). Uveďte další model tohoto programu, který není minimální. Hana Rudová, Logické programování I, 1 5. května 201 3 146 Sémantiky Deklarativní a operační sémantika Je-li S množina programových klauzulí a M libovolná množina Herbrandových modelů S, pak průnik těchto modelů je opět Herbrandův model množiny S. Důsledek: Existuje nejmenší Herbrandův model množiny S, který značíme M(S). Deklarativní sémantikou logického programu P rozumíme jeho minimální Herbrandův model M(P). Připomenutí: Operační sémantikou logického programu P rozumíme množinu O(P) všech atomických formulí bez proměnných, které lze pro nějaký cíl Q1 odvodit nějakým rezolučním důkazem ze vstupní množiny P u {§}. ^ímto výrazem jsou míněny všechny cíle, pro něž zmíněný rezoluční důkaz existuje. Pro libovolný logický program P platí M(P) = O(P) Hana Rudová, Logické programování I, 1 5. května 201 3 147 Sémantiky Negace v logickém programování Negativní znalost ■ logické programy vyjadřují pozitivní znalost ■ negativní literály: pozice určena definicí Hornových klauzulí => nelze vyvodit negativní informaci z logického programu ■ každý predikát definuje úplnou relaci ■ negativní literál není logickým důsledkem programu ■ relace vyjádřeny explicitně v nejmenším Herbrandově modelu ■ nad(X,Y) : -na(X,Y). na(c,b). nad(X, Y) : -na(X, Z),nad(Z, Y). na(b, a). ■ nejmenší Herbrandův model: {na(b,a),na(c,b),nad(b,a),nad(c,b),nad(c,a)} ■ ani program ani model nezahrnují negativní informaci ■ a není nad c, a není na c ■ i v realitě je negativní informace vyjádřena explicitně zřídka, např. jízdní řád Hana Rudová, Logické programování I, 1 5. května 201 3 149 Negace v logickém programování Předpoklad uzavřeného světa ■ neexistence informace chápána jako opak: předpoklad uzavřeného světa (closed world assumption, CWA) ■ převzato z databází ■ určitý vztah platí pouze když je vyvoditelný z programu. P \£ A ■ „odvozovací pravidlo" (A je (uzavřený) term):-— (CWA) ~>A ■ pro SLD-rezoluci: P £ nad{a, c), tedy lze podle CWA odvodit ^nad{a, c) ■ problém: není rozhodnutelné, zda daná atomická formule je logickým důsledkem daného logického programu. ■ nelze tedy určit, zda pravidlo CWA je aplikovatelné nebo ne ■ CWA v logickém programování obecně nepoužitelná. Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programování Negace jako neúspěch (negation as failure) slabší verze CWA: definitivně neúspěšný (finitely failed) SLD-strom cíle : -A : -A má definitivně (konečně) neúspěšný SLD-strom , . _ _v -—- (negation as failuľe, N F) normální cíl: cíl obsahující i negativní literály ■ : -nad(c,a), -^nad(b,c). rozdíl mezi CWA a NF ■program nad(X,Y) : -nad(X,Y), cíl :-^nad(b,c) ■ neexistuje odvození cíle podle NF, protože SLD-strom : -nad(b,c) je nekonečný ■ existuje odvození cíle podle CWA, protože neexistuje vyvrácení: -nad(b,c) CWA i NF jsou nekorektní: A není logickým důsledkem programu P řešení: definovat programy tak, aby jejich důsledkem byly i negativní literály zúplnění logického programu Hana Rudová, Logické programování I, 15. května 2013 151 Negace v logickém programování Podstata zúplnění logického programu ■ převod všech if příkazů v logickém programu na iff ■ nad(X,Y) : -na(X,Y). nad(X,Y) : -na(X, Z), nad(Z, Y). ■ lze psát jako: nad(X, Y) : -(na(X, Y)) v (na(X, Z),nad(Z, Y)). ■ zúplnění: nad(X,Y) ^ (na(X,Y)) v (na(X,Z),nad(Z,Y)). ■ X je nad Y právě tehdy, když alespoň jedna z podmínek platí ■ tedy pokud žádná z podmínek neplatí, X není nad Y ■ kombinace klauzulí je možná pouze pokud mají identické hlavy ■ na(c, b). na(b, a). ■ lze psát jako: na(Xi,X2) : -X\ = c,X2 = b. na(Xi,X2) : -X\ = b,X2 = a. ■ zúplnění: na(Xi,X2) — (X\ = c,X2 = b) v (X\ = b,X2 = a). Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programování Zúplnění programu ■ Zúplnění programu P je: comp(P) := IFF(P) u CET ■ Základní vlastnosti: ■ comp(P) i= P ■ do programuje přidána pouze negativní informace ■ IFF(P): spojka : - v IF(P) je nahrazena spojkou ~ ■ IF(P): množina všech formulí l¥(q,P) pro všechny predikátové symboly q v programu P ■ Cíl: definovat IF(g,P) ■ defip/n) predikátu p/nje množina všech klauzulí predikátu pln Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programování na(XuX2) : -3Y(X1 = c,X2 = bJ{Y)) v {Xl = b,X2 = a,g). q/n predikátový symbol programu P na(c,b):-f(Y). na(b,a): -g. Xi,... ,Xn jsou „nové" proměnné, které se nevyskytují nikde v P Nechť C je klauzule ve tvaru q (říj ■ ■ ■ j tn) ■ — Li,..., Lm kde m > 0, ti,..., tn jsou termy a Li,... ,Lm jsou literály. Pak označme E(C) výraz 3Yi,..., Yfc(^i = ti,... ,Xn = tn,Li,.. .,Lm) kde Yi,..., Yfc jsou všechny proměnné v C. Nechť defiq/n) = {Ci,..., Cy}. Pak formuli IF(g,P) získáme následujícím postupem: gtYi,..., Xn) : -E(Ci) v E(C2) v ■ ■ ■ v E(Q) pro j > 0 a ^(Xi,... ,Xn) : - □ pro j = 0 [g/n není v programu P] Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programování Čiarková Teorie Rovnosti (CET) všechny formule jsou univerzálně kvantifikovány: 1. X = X 2. X = Y^Y = X 3. X = Y AY = Z ^ X = Z 4. pro každý f/m: Xi = Yi a ■ ■ ■ a Xm = Ym - f(Xu ... ,Xm) = f(Yi,..., Ym) 5. pro každý p lm\ Xi = Yi a ■ ■ ■ a Xm = Ym - (p(Xi,... ,Xm) - p(Yi,... ,Ym)) 6. pro všechny různé f/m a gin, (m, n > 0): f(Xi,.. .,Xm) =f= g(Y\,..., Yn) 7. pro každý f/m: f(Xi,...,Xm) = f(Yu ..., Ym) - Xi = Yi a ■ ■ ■ a Xm = Ym 8. pro každý term t obsahující X jako vlastní podterm: t =f= X X =f= Y je zkrácený zápis = Y) Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programování Korektnost a úplnost NF pravidla Korektnost NF pravidla: Nechť P logický program a : -A cíl. Jestliže : -A má definitivně neúspěšný SLD-strom, pak V(-A) je logickým důsledkem comp(P) (nebo-li comp(P) i= V(-A)) Úplnost NF pravidla: Nechť P je logický program. Jestliže comp(P) i= V(-A), pak existuje definitivně neúspěšný SLD-strom : -A. ■ zůstává problém: není rozhodnutelné, zda daná atomická formule je logickým důsledkem daného logického programu. ■ teorém mluví pouze o existenci definitivně neúspěšného SLD-stromu ■ definitivně (konečně) neúspěšný SLD-strom sice existuje, ale nemusíme ho nalézt ■ např. v Prologu: může existovat konečné odvození, ale program přesto cyklí (Prolog nenajde definitivně neúspěšný strom) Odvození pomocí NF pouze test, nelze konstruovat výslednou substituci ■ v (comp(P) n V(-iA)) je A všeob. kvantifikováno, v V(-A) nejsou volné proměnné Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programován Normální a stratifikované programy normální program: obsahuje negativní literály v pravidlech problém: existence zúplnění, která nemají žádný model ■ p : -~ip. zúplnění: p <- ->p rozdělení programu na vrstvy ■ vynucují použití negace relace pouze tehdy pokud je relace úplně definovaná ■ a. a. a:-^b,a. a:-^b,a. b. b : -^a. stratifi kovaný není st ratifikovaný normální program P je stratifi kovaný: množina predikátových symbolů programu lze rozdělit do disjunktních množin So, ■ ■ ■, Sm (Si = stratům) 9 p(...):-..., q(...),... e P, p e Sk => q £ So u ...u Sk ■ p(...):-..., ..), ... e P, p e Sk => q e So u ... u Sk-i Hana Rudová, Logické programování I, 1 5. května 201 3 1 57 Negace v logickém programování Stratifikované programy II program je m-stratifikovaný <==> m je nejmenší index takový, že So u ... u Sm je množina všech predikátových symbolů z P Věta: Zúplnění každého stratifikovaného programu má Herbrandův model. ■ p : nemá Herbrandův model ■ p : -~*p. ale není stratifikovaný stratifikované programy nemusí mít jedinečný minimální Herbrandův model ■ cykli: -^zastaví. ■ dva minimální Herbrandovy modely: {cykli}, {zastaví} ■ důsledek toho, že cykli: -^zastaví, je ekvivalentní cykli v zastaví Hana Rudová, Logické programování I, 1 5. května 201 3 Negace v logickém programován SLDNF rezoluce: úspěšné odvození ■ NF pravidlo: C. má konečně neúspěšný SLD-strom ■ Pokud máme negativní podcíl ->C v dotazu G, pak hledáme důkaz pro C ■ Pokud odvození C selže (strom pro C je konečně neúspěšný), pak je odvození G (i ->C) celkově úspěšné nahore(X) : -^blokovaný (X). blokovaný(X) : -na(Y,X). na(a, b). : -nahore(c). yes :- nahore(c). :— blokovaný(c). ' blokovaný(c). :— na(Y,c). Hana Rudová, Logické programování I, 1 5. května 201 3 FAIL 1 59 => úspěšné odvození Negace v logickém programování SLDNF rezoluce: neúspěšné odvození ■ NF pravidlo: :-C. má konečně neúspěšný SLD-strom ■ Pokud máme negativní podcíl ->C v dotazu G, pak hledáme důkaz pro C ■ Pokud existuje vyvrácení C s prázdnou substitucí (strom pro C je konečně úspěšný), pak je odvození G (i ->C) celkově neúspěšné nahore(X) : -^blokovaný (X). blokovaný(X) : -na(Y,X). na(_, _). : -nahore(X). no :- nahore(X). :- blokovaný(X). : - -i blokovany(X). : - na(YfX). Hana Rudová, Logické programování I, 1 5. května 201 3 □ 160 => neúspěšné odvození Negace v logickém programování SLDNF rezoluce: uvázlé odvození ■ NF pravidlo: C. má konečně neúspěšný SLD-strom ■ Pokud máme negativní podcíl ->C v dotazu G, pak hledáme důkaz pro C ■ Pokud existuje vyvrácení C s neprázdnou substitucí (strom pro C je konečně úspěšný), pak je odvození G (i ->C) uvázlé nahore(X) : -^blokovaný (X). blokovaný(X) : -na(Y,X). na(a, b). nahor e(X). : — nahore(X). - blokovany(X). ' blokovaný(X). :— na(Y,X). [Y/a,X/b] □ ÍX/bl => uvázlé odvození Hana Rudová, Logické programování I, 1 5. května 201 3 161 Negace v logickém programování Cvičení: SLDNF odvození Napište množinu SLDNF odvození pro uvedený dotaz. :- a(B). a(X) :- b(X), \+ c(X). a(X) :- d(X), Y is X+l, \+ c(Y), b(X). b(l). c(A) :- d(A). d(l). Hana Rudová, Logické programování I, 1 5. května 201 3 162 Negace v logickém programování SLD+ odvození P je normální program, Go normální cíl, R selekční pravidlo: SLD+-odvození Gq je buď konečná posloupnost (Go; Co),..., (Gi-i, Ci-i), Gi nebo nekonečná posloupnost (Go; Co), (Gi; Ci), (G2; C2),... kde v každém kroku m + l(m > 0), R vybírá pozitivní literál v Gm a dospívá k Gm+\ obvyklým způsobem. konečné SLD+-odvození může být: 1. úspěšné: Gt = □ 2. neúspěšné 3. blokované: Gi je negativní (např. ->A) Hana Rudová, Logické programování I, 1 5. května 201 3 1 63 Negace v logickém programován SLDNF rezoluce: pojmy ■ Úroveň cíle ■ P normální program, Go normální cíl, R selekční pravidlo: úroveň cíle Go se rovná ■ 0 <==> žádné SLD+-odvození s pravidlem R není blokováno ■ k + 1 <==> maximální úroveň cílů : -A, které ve tvaru ->A blokují SLD+-odvození Go, je k ■ nekonečná úroveň cíle: blokované SLDNF odvození ■ Množina SLDNF odvození = {(SLDNF odvození Go) u (SLDNF odvození: -A)} ■ při odvozování Go jsme se dostali k cíli ->A ■ SLDNF odvození cíle G ? Hana Rudová, Logické programování I, 1 5. května 201 3 164 Negace v logickém programování SLDNF rezoluce P normální program, Gq normální cíl, R selekční pravidlo: množina SLDNF odvození a podmnožina neúspěšných SLDNF odvození cíle G() jsou takové nejmenší množiny, že: ■ každé SLD+-odvození Gq je SLDNF odvození Gq ■ je-li SLD+-odvození (Gq] Co),..., G* blokováno na ->A ■ tj. Gi je tvaru : — Li,...,Im-i, -"A,Lm+i,... ,Ln pak ■ existuje-li SLDNF odvození: -A (pod P) s prázdnou cílovou substitucí, pak (ColCo),..., Cí je neúspěšné SLDNF odvození ■ je-li každé úplné SLDNF odvození: -A (pod R) neúspěšné pak (Gq] Co), ..., (Gj, £), (: — Li,...,L,m-iiLm+i,...,Ln) je (úspěšné) SLDNF odvození cíle Go ■ e označuje prázdnou cílovou substituci Hana Rudová, Logické programování I, 1 5. května 201 3 1 65 Negace v logickém programování Typy SLDNF odvození Konečné SLDNF-odvození může být: 1. úspěšné: Gt = □ 2. neúspěšné 3. uvázlé (flounder): Gije negativní (->A) a : -A je úspěšné s neprázdnou cílovou substitucí 4. blokované: Gt je negativní (->A) a : -A nemá konečnou úroveň. Hana Rudová, Logické programování I, 1 5. května 201 3 166 Negace v logickém programování Korektnost a úplnost SLDNF odvození ■ korektnost SLDNF-odvození: P normální program, : -G normální cíl a R je selekční pravidlo: je-li 0 cílová substituce SLDNF-odvození cíle : -G, pak G6 je logickým důsledkem comp(P) ■ implementace SLDNF v Prologu není korektní ■ Prolog neřeší uvázlé SLDNF-odvození (neprázdná substituce) ■ použití bezpečných cílů (negace neobsahuje proměnné) ■ úplnost SLDNF-odvození: SLDNF-odvození není úplné ■ pokud existuje konečný neúspěšný strom : -A, pak platí ale místo toho se odvozování: -A může zacyklit, tj. SLDNF rezoluce ^A neodvodí => ~^A tedy sice platí, ale SLDNF rezoluce ho nedokáže odvodit Hana Rudová, Logické programování I, 1 5. května 201 3 167 Negace v logickém programování Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP CP: elektronické materiály ■ Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ http://www.ics.uci.edu/~dechter/books/materials.html průsvitky ke knize ■ Barták R. Přednáška Omezující podmínky na MFF UK, Praha. ■ http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html ■ SICStus Prolog User's Manual. Kapitola o CLP(FD). ■ http://www.fi.muni.cz/~hanka/sicstus/doc/html/ ■ Příklady v distribuci SICStus Prologu: cca 60 příkladů, zdrojový kód ■ 1 i b/si cstus-*/li brary/clpfd/examples/ Hana Rudová, Logické programování I, 1 5. května 201 3 1 69 Logické programování s omezujícími podmínkami Probírané oblasti ■ Obsah ■ úvod: od LP k CLP ■ základy programování ■ základní algoritmy pro řešení problémů s omezujícími podmínkami ■ Příbuzné přednášky na Fl ■ PA163 Programování s omezujícími podmínkami ■ viz interaktivní osnova IS ■ PA167 Rozvrhování ■ http://www.fi.muni.cz/~hanka/rozvrhovani ■ zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Omezení (constraint) ■ Dána ■ množina (doménových) proměnných Y = {yi,...,yk} ■ konečná množina hodnot (doména) D = {Di,..., D^} Omezení c na Y je podmnožina D\ x ... x Dk ■ omezuje hodnoty, kterých mohou proměnné nabývat současně ■ Příklad: ■ proměnné: A,B ■domény: {0,1} pro A {1,2} pro B ■omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} ■ Omezení c definováno na yi,... y^ je splněno, pokud pro d\ e Di, ...d^^D^ platí (di,... dk) e c ■ příklad (pokračování): omezení splněno pro (0,1), (0,2), (1,2), není splněno pro (1,1) Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) ■ Dána ■ konečná množina proměnných X = {xi,.. .,xn} ■ konečná množina hodnot (doména) D = {Di,..., Dn} ■ konečná množina omezení C = {ci,..., cm} ■ omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem) ■ Příklad: ■ proměnné: A,B,C ■domény: {0,1} pro A {1,2} pro B {0,2} pro C ■ omezení: A^B, B^C Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Řešení CSP ■ Částečné ohodnocení proměnných (d\,..., dk), k < n ■ některé proměnné mají přiřazenu hodnotu ■ Úplné ohodnocení proměnných (di,..., dn) ■ všechny proměnné mají přiřazenu hodnotu ■ Řešení CSP ■ úplné ohodnocení proměnných, které splňuje všechna omezení ■ {d\,..., dn) e Di x ... x Dn je řešení (X, D, C) ■ pro každé ci e C na x^,.. .Xik platí (d^,... dik) g ct ■ Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Příklad: jednoduchý školní rozvrh proměnné: Jan, Petr, ... domény: {3,4, 5,6}, {3,4},... omezení: all_ch"stinct([Jan, Petr, . . .]) částečné ohodnocení: Jan=6, Anna=5, Marie=l úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 řešení CSP: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l optimalizace: ženy učí co nejdříve Anna+Eva+Mari e #= Cena minimalizace hodnoty proměnné Cena optimální řešení: Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l Hana Rudová, Logické programování I, 1 5. května 201 3 1 74 Logické programování s omezujícími podmínkám učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 CLP(FD) program ■ Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení ■ (1) a (2) deklarativní část ■ modelování problému ■ vyjádření problému splňování podmínek ■ (3) řídící část ■ prohledávání stavového prostoru řešení ■ procedura pro hledání řešení (enumeraci) se nazývá labeling ■ umožní nalézt jedno, všechna nebo optimální řešení Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu solve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], ... post_constraints( Variables ), all_distinct([Jan,Petr,...]) labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_minCVar,Min) , % výběr nejmenší hodnoty z domény C Var#=Min, labelingC Rest ) ■ Var#>Min , labelingC [Var|Rest] ) )■ Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Příklad: algebrogram ■ Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: ■ SEND + MORE = MONEY ■ různá písmena mají přiřazena různé cifry ■ S a M nejsou 0 ■ domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) ■ 1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E #= 10000*M + 1000*0 + 100*N + 10*E + Y ■ all_distinct( [S,E,N,D,M,0,R,Y] ) ■ labeling( [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování I, 1 5. května 201 3 Logické programování s omezujícími podmínkami Od LP k CLP I ■ CLP: rozšíření logického programování o omezující podmínky ■ CLP systémy se liší podle typu domény ■ CLP(JA) generický jazyk ■ CLP(FD) domény proměnných jsou konečné (Finite Domains) ■ CLP(R) doménou proměnných je množina reálných čísel ■ Cíl ■ využít syntaktické a výrazové přednosti LP ■ dosáhnout větší efektivity ■ Unifikace v LP je nahrazena splňováním podmínek ■ unifikace se chápe jako jedna z podmínek ■ A = B ■ A #< B, A in 0..9, domain([A, B] ,0,9), all_distinct([A, B,C]) Hana Rudová, Logické programování I, 1 5. května 201 3 1 78 Logické programování s omezujícími podmínkami Od LP k CLP II ■ Pro řešení podmínek se používají konzistenční techniky ■ consistency techniques, propagace omezení (constraint propagation) ■ omezení: A in 0..2, B in 0..2, B #< A domény po propagaci omezení B #< A: A in 1..2, B in 0..1 ■ Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky ■ Prohledávání doplněno konzistenčními technikami ■ A i n 1. . 2 , B in 0..1, B# Vyvolání dvou řešičů: unifikace + řešič omezení Hana Rudová, Logické programování I, 1 5. května 201 3 180 Logické programování s omezujícími podmínkami Operační sémantika CLP ■ CLP výpočet cíle G ■ Store množina aktivních omezení = prostor omezení (constraint store) ■ inicializace Store = 0 ■ seznamy cílů v G prováděny v obvyklém pořadí ■ pokud narazíme na cíl s omezením c\ NewStore = Store u {c} ■ snažíme se splnit c vyvoláním jeho řešiče ■ při neúspěchu se vyvolá backtracking ■ při úspěchu se podmínky v NewStore zjednoduší propagací omezení ■ zbývající cíle jsou prováděny s upraveným NewStore ■ CLP výpočet cíle G je úspěšný, pokud se dostaneme z iniciálního stavu (G, 0) do stavu (G\ Store), kde G' je prázdný cíl a Store je splnitelná. Hana Rudová, Logické programování I, 1 5. května 201 3 181 Logické programování s omezujícími podmínkami CLPCFD) v SICStus Prologu Systémy a jazyky pro CP IBMILOGCP 1987 ■ omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL ■ implementace podmínek založena na objektově orientovaném programování ■ špičkový komerční sw, vznikl ve Francii, nedávno zakoupen IBM ■ nyní nově volně dostupný pro akademické použití Swedish Institute of Computer Science: SICStus Prolog 1 985 ■ silná CLP(FD) knihovna, komerční i akademické použití IC-PARC, Imperiál College London, Cisco Systems: ECL*PSe 1 984 ■ široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r ■ od 2004 vlastní Cisco Systems volně dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris Mnoho dalších systémů: Choco, Gecode, Minion, Oz, SWI Prolog, ... Hana Rudová, Logické programování I, 1 5. května 201 3 183 CLPCFD) v SICStus Prologu CLP(FD) v SICStus Prologu ■ Vestavěné predikáty jsou dostupné v separátním modulu (knihovně) :- use_module(library(clpfd)). ■ Obecné principy platné všude nicméně standarty jsou nedostatečné ■ stejné/podobné vestavěné predikáty existují i jinde ■ CLP knihovny v SWI Prologu i ECLiPSe se liší Hana Rudová, Logické programování I, 1 5. května 201 3 CLPCFD) v SICStus Prologu Příslušnost k doméně: Range termy ?- domain( [A,B], 1,3). A in 1. . 3 B in 1. . 3 ?- A in 1..8, A #\= 4. A in (1..3) \/ (5..8) domain( +Variables, +Min, +Max) ?X in +Min..+Max Doména reprezentována jako posloupnost intervalů celých čísel ?- A in (1..3) \/ (8..15) \/ (5..9) \/ {100}. A in (1..3) \/ (5..15) \/ {100} Zjištění domény Range proměnné Var: ■A in 1..8, A #\= 4, fd_dom(A,Range). ■ A in 2..10, fd_dom(A,(1..3) \/ (5..8)). Range term: reprezentace nezávislá na implementaci ?X in +Range fd_dom(?Var,?Range) Range=(l..3) \/ (5..8) no Hana Rudová, Logické programování I, 1 5. května 201 3 185 CLPCFD) v SICStus Prologu Příslušnost k doméně: FDSet termy ■ FDSet term: reprezentace závislá na implementaci ■ ?- A in 1..8, A #\= 4, fd_set(A, FDSet) . f d_set (?Var , ?FDSet) A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] ■ ?- A in 1..8,A #\= 4, fd_set(A,FDSet) ,B in_set FDSet. ?X i n_set +FDSet A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] B in (1..3) \/ (5..8) ■ FDSet termy představují nízko-úrovňovou implementaci ■ FDSet termy nedoporučeny v programech ■ používat pouze predikáty pro manipulaci s nimi ■ omezit použití A in_set [ [11 2] , [61 9]] ■ Range termy preferovány Hana Rudová, Logické programování I, 15. května 2013 186 CLP(FD) v SICStus Prologu Další fd_. . . predikáty ■ fdset_to_list(+FDset, -List) vrací do seznamu prvky FDset ■ list_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu ■ fd_var(?Var) je Var doménová proměnná? ■ fd_min(?Var,?Min) nejmenší hodnota v doméně ■ fd_max(?Var,?Max) největší hodnota v doméně ■ fd_size(?Var, ?Size) velikost domény ■ fd_degree(?Var,?Degree) počet navázaných omezení na proměnné ■ mění se během výpočtu: pouze aktivní omezení, i odvozená aktivní omezení Hana Rudová, Logické programování I, 1 5. května 201 3 187 CLPCFD) v SICStus Prologu Aritmetická omezení Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= ■ A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4 ■ POZOR: neplést #=< a #>= s operátory pro implikaci: #<= #=> sum(Vari ables,RelOp,Suma) ■ domain([A,B,C,F],1,3), sum([A,B,C],#= ,F) ■ Vari abl es i Suma musí být doménové proměnné nebo celá čísla scalar_product(Coeffs,Vari ables,Rel Op,Seal arProduct) ■ domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) ■ Variables i Value musí být doménové proměnné nebo celá čísla, Coef f s jsou celá čísla ■ POZOR na pořadí argumentů, nejprve jsou celočíselné koeficienty, pak dom. proměnné ■ scalar_product(Coeffs, Variables, #= , Value, [consistency(domain)]) ■ silnější typ konzistence ■ POZOR: domény musí mít konečné hranice Hana Rudová, Logické programování I, 15. května 2013 188 CLP(FD) v SICStus Prologu Základní globální omezení ■ all_distinct(List) ■ všechny proměnné různé ■ cumulative(...) ■ disjunktivní a kumulativní rozvrhování ■ cumulatives(...) ■ kumulativní rozvrhování na více zdrojů Hana Rudová, Logické programování I, 1 5. května 201 3 189 CLPCFD) v SICStus Prologu Všechny proměnné různé al 1 _ch" sti nct(Vari abl es), al l_ch" fferent(Vari abl es) Proměnné v seznamu Vari abl es jsou různé all_ch"stinct a all_ch"fferent se liší úrovní propagace ■ all_ch"stinct má úplnou propagaci ■ all_ch"fferent má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny ■ all_distinct([Jan, Petr, Anna,Ota, Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 ■ all_different([Jan,Petr,Anna,Ota,Eva,Marie]) Jan in 3..6, Petr in 3..4, Anna in 2..5, Ota in 2..4, Eva in 3..4, Marie in 1..6 Hana Rudová, Logické programování I, 15. května 2013 190 CLP(FD) v SICStus Prologu učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Disjunktivní rozvrhování (unární zdroj) cumulative([task(Start, Duration, End, 1, Id) | Tasks]) Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly ■ příklad s konstantami: cumul ati ve([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 3 1 2 3 4 5 6 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná JanE#= Jan+3, PetrE#= Petr+1, AnnaE#= Anna+2, ... cumulative(task(Jan,3,JanE,1,1),task(Petr,1,PetrE,1,2),task(Anna,2,AnnaE,1,3 task(Ota,2,OtaE,1,4),task(Eva,2,EvaE,1,5),task(Mari e,3,Mari eE,1,6)]) Hana Rudová, Logické programování I, 1 5. května 201 3 191 CLPCFD) v SICStus Prologu Kumulativní rozvrhování cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [li mi t(Li mi t)]) Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy nepřekročila Limit Příklad s konstantami: cumulative([task(0,4,4,l,l) , task(l,2, 3,2,2) , task(3, 3 ,6,2 , 3) , task(4,2 ,6,1,4)], [limit(3)]) 2 3 1 1 1 1 l 1 2 3 4 5 6 Hana Rudová, Logické programování I, 15. května 2013 192 CLP(FD) v SICStus Prologu Kumulativní rozvrhování s více zdroji Rozvržení úloh tak, aby se nepřekrývaly a daná kapacita zdrojů nebyla překročena (limit zdroje chápán jako horní mez - bound(upper)) cumulati ves([task(Start,Du rati on,End,Demand,Machi neld)|Tasks], [machine(Id,Limit)IMachines],[bound(upper)]) Úlohy zadány startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (Machi neld) Zdroje zadány identifikátorem (Id) a kapacitou (Limit) Příklad: ?- domain([B,C],1,2), cumulatives([task(0,4,4,l,l),task(3,l,4,l,B), task(5,l,6,l,C)], [machi ne(l,1),machi ne(2,1)], [bound(upper)]). C in 1..2, B=2 Hana Rudová, Logické programování I, 15. května 2013 193 CLP(FD) v SICStus Prologu Příklad: kumulativní rozvrhování ■ Vytvořte rozvrh pro následující úlohy, tak aby nebyla překročena kapacita 1 3 zdroje, a minimalizujte celkovou dobu trvání úloha doba trvání kapacita tl 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 t7 4 11 Hana Rudová, Logické programování I, 1 5. května 201 3 194 CLPCFD) v SICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Li mi t, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in C.MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulative(Tasks, [li mi t(Li mi t)]), after(Ss, Ds, End), % koncový čas append(Ss, [End], Vars), labeling([mi ni mi ze(End)],Vars). vytvor_ulohy([] ,[],[] ,_Id, []). vytvor_ulohy([S|Ss], [D|Ds], [R|Rs], Id, [task(S,D,E,R,Id)|Tasks]):-Newld is Id+1, E #= S+D, vytvor_ulohy(Ss,Ds,Rs, Newld,Tasks). after([], [], _) . after([S|Ss], [D|Ds], End) :- E #>= S+D, after(Ss, Ds, End). Hana Rudová, Logické programování I, 15. května 2013 195 CLP(FD) v SICStus Prologu Vestavěné predikáty pro labeling ■ Instanciace proměnné Variable hodnotami v její doméně indomainC Variable ) hodnoty jsou instanciovány při backtrackingu ve vzrůstajícím pořadí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labelingC [] ). labelingC [Var | Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrůstajícím pořadí labelingC Rest ). ■ labelingC Options, Variables ) ?- A in 0..2, B in 0..2, B#< A, labeling([], [A, B]). Hana Rudová, Logické programování I, 1 5. května 201 3 1 96 CLPCFD) v SICStus Prologu Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables, Var, Rest) , select_value(Var,Value), ( Var #= Value, labeling( Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokračujeme se všemi proměnnými včetně Var )■ Statické uspořádání: určeno už před prohledáváním Dynamické uspořádání: počítá se během prohledávání Hana Rudová, Logické programování I, 15. května 2013 197 CLP(FD) v SICStus Prologu Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed first) ■ volíme pořadí tak, abychom výběr nemuseli opakovat ■ ?- domai n([A, B,C] ,1,2) , A#=B+C. optimální výběr A=2,B=1 ,C=1 je bez backtrackingu Parametry label i ng/2 ovlivňující výběr hodnoty př. labeling([down], Vars) ■ up: doména procházena ve vzrůstajícím pořadí (default) ■ down: doména procházena v klesajícím pořadí Parametry label i ng/2 řídící, jak je výběr hodnoty realizován ■ step: volba mezi X #= M, X #\= M (default) ■ viz dřívější příklad u "Uspořádání hodnot a proměnných" ■ enum: vícenásobná volba mezi všemi hodnotami v doméně ■ podobně jako při i ndomai n/1 Hana Rudová, Logické programování I, 1 5. května 201 3 198 CLPCFD) v SICStus Prologu Výběr proměnné ■ Obecný princip výběru proměnné: first-fail ■ výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu ■ vybereme proměnnou s nejmenší doménou ■ ?- domai n ([A, B, C] ,1,3) , A#<3, A#=B+C. nejlépe je začít s výběrem A ■ Parametry 1 abel i ng/2 ovlivňující výběr proměnné ■ leftmost: nejlevější (default) ■ ff: s (1) nejmenší velikostí domény fd_size(Var,Size) (2) (pokud s nejmenší velikostí domény více, tak) nejlevější z nich ■ f f c: s (1) nejmenší velikostí domény (2) největším množstvím omezením „čekajících" na proměnné fd_degree(Var, Si ze) (3) nejlevější z nich ■ min/max: s (1) nejmenší/největší hodnotou v doméně proměnné (2) nej levnější z nich fd_min(Var,Min)/fd_max(Var,Max) Hana Rudová, Logické programování I, 1 5. května 201 3 199 CLPCFD) v SICStus Prologu Hledání optimálního řešení (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: mi ni mi ze (F)/maxi mi ze (F) ■ Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Metoda větví a mezí (branch&bound) ■ algoritmus, který implementuje proceduru pro minimalizaci (duálně pro maximalizaci) ■ uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) ■ počítáme dolní odhad LB ceny částečného řešení LB je tedy nejlepší možná cena pro rozšíření tohoto řešení ■ procházíme strom a vyžadujeme, aby prozkoumávaná větev měla cenu LB < UB pokud je LB > UB, tak víme, že v této větvi není lepší řešení a odřízneme ji ■ přidává se tedy inkrementálně omezení LB# 0 c4 : X2 + xs - Xq = 0 Hana Rudová, Logické programování I, 1 5. května 201 3 Algoritmy pro CSP Binární CSP Binární CSP ■ CSP, ve kterém jsou pouze binární podmínky ■ unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP ■ není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) Každý CSP lze transformovat na "korespondující" binární CSP Výhody a nevýhody binarizace ■ získáváme unifikovaný tvar CSP problému, řada algoritmů navržena pro binární CSP ■ bohužel ale značné zvětšení velikosti problému Nebinární podmínky ■ složitější propagační algoritmy ■ lze využít jejich sémantiky pro lepší propagaci ■ příklad: al l_di sti nct vs. množina binárních nerovností Hana Rudová, Logické programování I, 15. května 2013 203 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC ■ každá hodnota z aktuální domény Ví proměnné splňuje všechny unární podmínky s proměnnou Ví Hranová konzistence (arc consistency) AC pro binární CSP ■ hrana (Vu Vj) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dt existuje hodnota y tak, že ohodnocení [Ví = x, Vj = y] splňuje všechny binární podmínky nad Vu Vj, ■ hranová konzistence je směrová ■ konzistence hrany {VuVj) nezaručuje konzistenci hrany (V), Ví) A 1..5 B A3..4 A řešení neexistuje ■ všechny domény jsou jednoprvkové => máme řešení ■ v obecném případě se alespoň zmenší prohledávaný prostor ■ Dostaneme potom řešení problému? NE ■ Víme alespoň zda řešení existuje? NE Hana Rudová, Logické programování I, 1 5. května 201 3 208 Algoritmy pro CSP k-konzistence Mají NC a AC něco společného? ■ NC: konzistence jedné proměnné ■ AC: konzistence dvou proměnných "... můžeme pokračovat CSP je k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) různých proměnných rozšířit do libovolné k-té proměnné 1,2,3 Pro obecné CSP, tedy i pro nebinární podmínky Hana Rudová, Logické programování I, 1 5. května 201 3 209 4-konzistentní graf Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšířit na (1,1,1) 1,2 — 1,2 -tH 1,2,3 není 2-konzistentní (3) nelze rozšířit (2.2) lze rozšířit na (2,2,2) (1.3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) ■ CSPje silně k-konzistentní právě tehdy, když je j-konzistentní pro každé j k-konzistence ■ Silná k-konzistence => j-konzistence Vj < k ■ k-konzistence 4> silná k-konzistence ■ NC = silná 1 -konzistence = 1 -konzistence ■ AC = (silná) 2-konzistence Hana Rudová, Logické programování I, 1 5. května 201 3 210 Algoritmy pro CSP Konzistence pro nalezení řešení ■ Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? ■ silná n-konzistence je nutná pro graf s n vrcholy ■ n-konzistence nestačí (viz předchozí příklad) ■ silná k-konzistence pro k B => min(A) = min(B)+l, max(B) = max(A)-l ■ příklad: A in 4. .10, B i n 6. . 18, A #> B mi n (A) = 6+1 => A in 7.. 10 max(B) = 10-1 => B in 6. .9 ■ podobně: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 1 5. května 201 3 214 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) ■ změna mi n (A)vyvolá pouze změnu mi n(B) amin(C) ■ změna max(A)vyvolá pouze změnu max(B) a max(C) , ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=l+2, max(A)=10+2 => A in 3..10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => min (A) =6 => A in 6.. 10 => min(B)=6-2 => B in 4.. 8 (nové vyvolání A #= B + 2) A #\= 8 => A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Logické programování I, 1 5. května 201 3 215 Algoritmy pro CSP Globální podmínky Propagace je lokální ■ pracuje se s jednotlivými podmínkami ■ interakce mezi podmínkami je pouze přes domény proměnných Jak dosáhnout více, když je silnější propagace drahá? Seskupíme několik podmínek do jedné tzv. globální podmínky Propagaci přes globální podmínku řešíme speciálním algoritmem navrženým pro danou podmínku Příklady: ■ al l_di sti nct omezení: hodnoty všech proměnných různé ■ seri al i zed omezení: rozvržení úloh zadaných startovním časem a dobou trvání tak, aby se nepřekrývaly Hana Rudová, Logické programování I, 1 5. května 201 3 216 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{Xi,... ,Xk} c V : card{D\ u ■ ■ ■ u Dk} > k stačí hledat Hallův interval J: velikost intervalu J je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo ■ U = {Xi,... ,Xk}, dom(U) = {D1u---uDk} ■ card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X + v ■ hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: 0(2n) - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hraničních bodů Hallových intervalů (1998) Hana Rudová, Logické programování I, 15. května 2013 217 Algoritmy pro CSP učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení ■ podmínky jsou užívány pasivně jako test ■ přiřazuji hodnoty proměnných a zkouším co se stane ■ vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj ■ úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) ■ zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky ■ umožňují odstranění nekonzistentních hodnot z domény proměnných ■ neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) ■ relativně rychlé (polynomiální) Používá se kombinace obou metod ■ postupné přiřazování hodnot proměnným ■ po přiřazení hodnoty odstranění nekonzistentních hodnot konzistenčními technikami Hana Rudová, Logické programování 1,15. května 2013 218 Algoritmy pro CSP Prohledávání do hloubky Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) Dvě fáze prohledávání s navracením ■ dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné ■ po vybrání hodnoty testujeme konzistenci ■ zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Proměnné dělíme na ■ minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) ■ aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota ■ budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 15. května 2013 219 Algoritmy pro CSP Základní algoritmus prohledávání do hloubky Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí Na začátku voláno jako 1 abel i ng (G, 1) proceduře labeling(G,a) if a > |uzly(G)| then return uzly(G) for Vx e Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC(G,a), LA(G,a R := 1abeling(G,a+1) if R ^ fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 1 5. května 201 3 220 Algoritmy pro CSP Backtracking (BT) ■ Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné ■ Backtracking tedy zajišťuje konzistenci podmínek ■ na všech minulých proměnných ■ na podmínkách mezi minulými proměnnými a aktuální proměnnou ■ proceduře BT(G,a) Q: ={(Vu V a) e hrany(G) , i < a} % hrany vedoucí z minulých proměnných do aktuální Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfc,Vm) z Q Consistent := not revise(Vfc,Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 1 5. května 201 3 221 Algoritmy pro CSP Příklad: backtracking Omezení: Vu V2, V3 in 1... 3, V1#=3xV3 Stavový prostor: l ■ červené čtverečky: chybný pokus o instanciaci, řešení neexistuje ■ nevyplněná kolečka: nalezeno řešení ■ černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Hana Rudová, Logické programování I, 1 5. května 201 3 222 Kontrola dopředu (FC - forward checking) FC je rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami proceduře FC(G,a) Q:={(Ví, Va) e hrany(G) , í > a] % přidání hran z budoucích do aktuální proměnné Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfc,Vm) z Q if revise((Vfc,Vm)) then Consistent := (|Dfc|>0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC Hrany z minulých proměnných do aktuální proměnné není nutno testovat Hana Rudová, Logické programování I, 1 5. května 201 3 223 Algoritmy pro CSP Příklad: kontrola dopředu ■ Omezení: Vu V2, V3 in 1... 3, c:V1#=3x V3 ■ Stavový prostor: Hana Rudová, Logické programování I, 1 5. května 201 3 224 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) LA je rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými proceduře LA(G,a) Q := {(Ví,Va) e h rany (G), í > a} % začínáme s hranami do a Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vt,Vm) z Q if revise((Vfc,Vm)) then Q := Q u {(VuVk)\(Vi,Vk) e hrany(G), í^k,í^m,í> a} Consistent := (|Dfc|>0) return Consistent end LA ■ Hrany z minulých proměnných do aktuální proměnné opět netestujeme ■ Tato LA procedura je založena na AC-3, lze použít i jiné AC algoritmy LA udržuje hranovou konzistenci: protože ale LA(G,a) používá AC-3, musíme zajistit iniciální konzistenci pomocí AC-3 ještě před startem prohledávání Hana Rudová, Logické programování I, 15. května 201 3 22 5 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: Vi,V2,V3 in 1...4, cl:V1#>V2, c2:V2#=3xV3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) • d => V-| in 2..4 V2in 1..3 c2 => V2=3 V3= 1 d => V-|= 4 V< 4, V2 3, V3 1ó Hana Rudová, Logické programování I, 1 5. května 201 3 226 Algoritmy pro CSP Přehled algoritmů proměnné Backtracking (BT) kontroluje v kroku a podmínky c(VuVa),...,c(Va-uVa) z minulých proměnných do aktuální proměnné BT Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l,Va),...,C(Vn,Va) z budoucích proměnných do aktuální proměnné Pohled dopředu (LA) kontroluje v kroku a podmínky VI(a < l < n), Vfc(a 10. 2. Ukažte, jak je dosaženo hranové konzistence v následujícím příkladu: domain([X,Y,Z],l ,5]), X #< Y, Z#= Y+l . Hana Rudová, Logické programování I, 1 5. května 201 3 229 Algoritmy pro CSP Implementace Prologu Literatura: Matýska L, Toman D.: Implementační techniky Prologu, Informační systémy, (1 990), 21-59. http://www.i cs.muni.cz/people/matyska/vyuka/1p/1p Opakování: ni pojmy Konečná množina klauzulí Hlava : - Tělo tvoří program P. Hlava je literál Tělo je (eventuálně prázdná) konjunkce literálů Ti,... Ta, a > 0 Literál je tvořen m-árním predikátovým symbolem (m/p) a m termy (argumenty) Term je konstanta, proměnná nebo složený term. Složený term s n termy na místě argumentů Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programování I, 1 5. května 201 3 231 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platili jednotlivé literály těla. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti ■ ■ ■ call Ta } Volání procedury s názvem Hlava uspěje, pokud uspěje volání všech procedur (literálů) v těle. Procedurální sémantika = podklad pro implementaci Hana Rudová, Logické programování I, 1 5. května 201 3 232 Implementace Prologu Abstraktní interpret Vstup: Logický program P a dotaz G. 1. Inicializuj množinu cílů S literály z dotazu G; S:=G 2. while ( S != empty ) do 3. Vyber AeS a dále vyber klauzuli A' : -Bi, . . . , Bn (n > 0) z programu P takovou, že 3a : A každá instanciace ekvivalentní zdrojovému termu ■ zdrojový term s proměnnými => dvě instance se mohou lišit aktuálními hodnotami proměnných, jedinečnost zajišťuje kopírování struktur nebo sdílení struktur Hana Rudová, Logické programování I, 15. května 2013 239 Implementace Prologu Kopírování struktur Příklad: a(b(X),c(X,Y),d), FUNCT a73 REF--1 REF--1 CONST d FUNCT c72 J i-- REF FREE Y FUNCT b/1 -— —► FREE X Hana Rudová, Logické programování I, 1 5. května 201 3 240 Implementace Prologu Kopírování struktur II ■ Term F s aritou A reprezentován A+l slovy: ■ funktor a arita v prvním slově ■ 2. slovo nese první argument (resp. odkaz na jeho hodnotu) ■ ■ A+l slovo nese hodnotu A-tého argumentu ■ Reprezentace vychází z orientovaných acyklických grafů: a/3 d i c/2 Y b/1 X ■ Vykopírována každá instance => kopírování struktur ■ Termy ukládány na globální zásobník Hana Rudová, Logické programování I, 15. května 2013 241 Implementace Prologu Sdílení struktur Vychází z myšlenky, že při reprezentaci je třeba řešit přítomnost proměnných Instance termu < kostra_termu; rámec > ■ kostra_termu je zdrojový term s očíslovanými proměnnými ■ rámec je vektor aktuálních hodnot těchto proměnných ■ í-tá položka nese hodnotu í-té proměnné v původním termu Hana Rudová, Logické programování I, 1 5. května 201 3 242 Implementace Prologu Sdílení struktur II Příklad: a(b(X),c(X,Y),d) reprezentuje < a(b($l),c($l,$2),d) ; [FREE, FREE] > kde symbolem $i označujeme í-tou proměnnou Implementace: < &kostra_termu; &rámec > (& vrací adresu objektu) Všechny instance sdílí společnou kostru_termu => sdílení struktur Hana Rudová, Logické programování I, 1 5. května 201 3 243 Implementace Prologu Srovnání: příklad Naivní srovnání: sdílení paměťově méně náročné Platí ale pouze pro rozsáhlé termy přítomné ve zdrojovém kódu Postupná tvorba termů: A = a(K,L,M), K = b(X), L = c(X,Y), M = d Sdílení termů: A kostra_a K M:d kostrab kostra_c X Y Hana Rudová, Logické programování I, 1 5. května 201 3 244 Implementace Prologu Srovnání: příklad - pokračování ■ Kopírování struktur: A = a(K,L,M), K = b(X), L = c(X,Y), M = d FUNCT a/3 REF -REF -CONST d FUNCT c/2 - REF FREE Y FUNCT b/1 FREE X tj. identické jako přímé vytvoření termu a(b(X) ,c(X,Y) ,d) Hana Rudová, Logické programování I, 1 5. května 201 3 245 Implementace Prologu Srovnání II ■ Složitost algoritmů pro přístup k jednotlivým argumentům ■ sdílení struktur: nutná víceúrovňová nepřímá adresace ■ kopírování struktur: bez problémů ■ jednodušší algoritmy usnadňují i optimalizace ■ Lokalita přístupů do paměti ■ sdílení struktur: přístupy rozptýleny po paměti ■ kopírování struktur: lokalizované přístupy ■ při stránkování paměti - rozptýlení vyžaduje přístup k více stránkám ■ Z praktického hlediska neexistuje mezi těmito přístupy zásadní rozdíl Hana Rudová, Logické programování I, 1 5. května 201 3 246 Implementace Prologu Řízení výpočtu ■ Dopředný výpočet ■ po úspěchu (úspěšná redukce) ■ jednotlivá volání procedur skončí úspěchem ■ klasické volání rekurzivních procedur ■ Zpětný výpočet (backtracking) ■ po neúspěchu vyhodnocení literálu (neúspěšná redukce) ■ nepodaří se unifikace aktuálních a formálních parametrů hlavy ■ návrat do bodu, kde zůstala nevyzkoušená alternativa výpočtu ■ je nutná obnova původních hodnot jednotlivých proměnných ■ po nalezení místa s dosud nevyzkoušenou klauzulí pokračuje dále dopředný výpočet Hana Rudová, Logické programování I, 1 5. května 201 3 247 Implementace Prologu Aktivační záznam ■ Volání (=aktivace) procedury ■ Aktivace sdílí společný kód, liší se obsahem aktivačního záznamu ■ Aktivační záznam uložen na lokálním zásobníku ■ Dopředný výpočet ■ stav výpočtu v okamžiku volání procedury ■ aktuální parametry ■ lokální proměnné ■ pomocné proměnné ('a la registry) ■ Zpětný výpočet (backtracking) ■ hodnoty parametrů v okamžiku zavolání procedury ■ následující klauzule pro zpracování při neúspěchu Hana Rudová, Logické programování I, 1 5. května 201 3 248 Implementace Prologu Aktivační záznam a roll-back Neúspěšná klauzule mohla nainstanciovat nelokální proměnné ■ a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných Využijeme vlastností logických proměnných ■ instanciovat lze pouze volnou proměnnou ■ jakmile proměnná získá hodnotu, nelze ji změnit jinak než návratem výpočtu => původní hodnoty všech proměnných odpovídají volné proměnné Stopa (trail): zásobník s adresami instanciovaných proměnných ■ ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu ■ při neúspěchu jsou hodnoty proměnných na stopě v úseku mezi aktuálním a uloženým vrcholem zásobníku změněny na „volná" Globální zásobník: pro uložení složených termů ■ ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu ■ při neúspěchu vrchol zásobníku snížen podle uschované hodnoty v aktivačním záznamu Hana Rudová, Logické programování I, 15. května 2013 249 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: ■ okolí (environment) - informace nutné pro dopředný běh programu ■ bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ■ ukládány na lokální zásobník ■ samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: ■ samostatná práce s každou částí aktivačního záznamu (optimalizace) ■ alokace pouze okolí pro deterministické procedury ■ možnost odstranění okolí po úspěšném vykonání (i nedeterministické) procedury (pokud okolí následuje po bodu volby dané procedury) ■ pokud je okolí na vrcholu zásobníku Hana Rudová, Logické programování I, 15. května 2013 2 50 Implementace Prologu Řez ■ Prostředek pro ovlivnění běhu výpočtu programátorem ■ a(X) :- b(X), !, c(X). b(l). b(2). a(3). cd). c(2). ■ Rez: neovlivňuje dopředný výpočet, má vliv pouze na zpětný výpočet ■ Odstranění alternativních větví výpočtu => odstranění odpovídajících bodů volby ■ tj. odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) => změna ukazatele na „nejmladší" bod volby => Vytváření deterministických procedur => Optimalizace využití zásobníku Hana Rudová, Logické programování I, 1 5. května 201 3 251 Implementace Prologu Interpret Prologu Základní principy: ■ klauzule uloženy jako termy ■ programová databáze ■ pro uložení klauzulí ■ má charakter haldy ■ umožňuje modifikováteInost prologovských programů za běhu (assert) ■ klauzule zřetězeny podle pořadí načtení ■ triviální zřetězení Vyhodnocení dotazu: volání procedur řízené unifikací Hana Rudová, Logické programování I, 1 5. května 201 3 252 Implementace Prologu Interpret - Základní princip 1. Vyber redukovaný literál („první", tj. nejlevejší literál cíle) 2. Lineárním průchodem od začátku databáze najdi klauzuli, jejíž hlava má stejný funktor a stejný počet argumentů jako redukovaný literál 3. V případě nalezení klauzule založ bod volby procedury 4. Založ dále okolí první klauzule (velikost odvozena od počtu lokálních proměnných v klauzuli) 5. Proveď unifikaci literálu a hlavy klauzule 6. Úspěch => přidej všechny literály klauzule k cíli („doleva", tj. na místo redukovaného literálu). Tělo prázdné => výpočet se s úspěchem vrací do klauzule, jejíž adresa je v aktuálním okolí. 7. Neúspěch unifikace => z bodu volby se obnoví stav a pokračuje se v hledání další vhodné klauzule v databázi. 8. Pokud není nalezena odpovídající klauzule, výpočet se vrací na předchozí bod volby (krátí se lokální i globální zásobník). 9. Výpočet končí neúspěchem: neexistuje již bod volby, k němuž by se výpočet mohl vrátit. 10. Výpočet končí úspěchem, jsou-li úspěšně redukovány všechny literály v cíli. Hana Rudová, Logické programování I, 15. května 201 3 2 53 Implementace Prologu Interpret - vlastnosti ■ Lokální i globální zásobník ■ při dopředném výpočtu roste ■ při zpětném výpočtu se zmenšuje Lokální zásobník se může zmenšit při dopředném úspěšném výpočtu deterministické procedury. ■ Unifikace argumentů hlavy - obecný unifikační algoritmus Současně poznačí adresy instanciovaných proměnných na stopu. ■ „Interpret": interpretCQuery, Vars) :- call(Query), success(Query, Vars). interpret(_,_) :- failure. ■ dotaz vsazen do kontextu této speciální nedeterministické procedury ■ tato procedura odpovídá za korektní reakci systému v případě úspěchu i neúspěchu Hana Rudová, Logické programování I, 15. května 2013 2 54 Implementace Prologu Optimalizace: Indexace Zřetězení klauzulí podle pořadí načtení velmi neefektivní Provázání klauzulí se stejným funktorem a aritou hlavy (tvoří jednu proceduru) ■ tj., indexace procedur Hash tabulka pro vyhledání první klauzule Možno rozhodnout (parciálně) determinismus procedury Hana Rudová, Logické programování I, 1 5. května 201 3 255 Implementace Prologu Indexace argumentů a(l) :- q(l). a(a) :- b(X). a([A|T]) :- c(A,T). ■ Obecně nedeterministická ■ Při volání s alespoň částečně instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspět) ■ Indexace podle prvního argumentu Základní typy zřetězení: ■ podle pořadí klauzulí (aktuální argument je volná proměnná) ■ dle konstant (aktuální je argument konstanta) ■ formální argument je seznam (aktuální argument je seznam) ■ dle struktur (aktuální argument je struktura) Hana Rudová, Logické programování I, 1 5. května 201 3 256 Implementace Prologu Indexace argumentů II ■ Složitější indexační techniky ■ podle všech argumentů ■ podle nejvíce diskriminujícího argumentu ■ kombinace argumentů (indexové techniky z databází) ■ zejména pro přístup k faktům Hana Rudová, Logické programování I, 1 5. května 201 3 257 Implementace Prologu Tail Recursion Optimization, TRO Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů Optimalizace koncové rekurze (Tail Recursion Optimisation), TRO: Okolí se odstraní před rekurzivním voláním posledního literálu klauzule, pokud je klauzule resp. její volání deterministické. Řízení se nemusí vracet: ■ v případě úspěchu se rovnou pokračuje ■ v případě neúspěchu se vrací na předchozí bod volby („nad" aktuální klauzulí) ■ aktuální klauzule nemá dle předpokladu bod volby Rekurzivně volaná klauzule může být volána přímo z kontextu volající klauzule. Hana Rudová, Logické programování I, 1 5. května 201 3 258 Implementace Prologu TRO - příklad Program: append([], L, L). append([A|X], L, [A|Y]) :- append(X, L, Y) Dotaz: ?- append([a,b,c], [x], L), append volán rekurzivně 4krát ■ bez TRO: 4 okolí, lineární paměťová náročnost ■ s TRO: 1 okolí, konstatní paměťová náročnost Hana Rudová, Logické programování I, 15. května 2013 2 59 Implementace Prologu Optimalizace posledního volání TRO pouze speciální případ obecné optimalizace posledního volání (Last Ca\\ Optimization), LCO Okolí (před redukcí posledního literálu) odstraňováno vždy, když leží na vrcholu zásobníku. Nutné úpravy interpretu ■ disciplina směrování ukazatelů ■ vždy „mladší" ukazuje na „starší" („mladší" budou odstraněny dříve) ■ z lokálního do globálního zásobníku vyhneme se vzniku „visících odkazů" při předčasném odstranění okolí ■ „globalizace" lokálních proměnných: lokální proměnné posledního literálu ■ nutno přesunout na globální zásobník ■ pouze pro neinstanciované proměnné Hana Rudová, Logické programování I, 15. května 2013 260 Implementace Prologu Warrenův abstraktní počítač, WAM L Navržen D.H.D. Warrenem v roce 1 983, modifikace do druhé poloviny 80. let Datové oblasti: ■ Oblast kódu (programová databáze) ■ separátní oblasti pro uživatelský kód (modifi kováte Iný) a vestavěné predikáty (nemění se) ■ obsahuje rovněž všechny statické objekty (texty atomů a funktorů apod.) ■ Lokální zásobník (Stack) ■ Stopa (Trail) ■ Globální zásobník n. ha\da(Heap) ■ Pomocný zásobník (Push Down List, PDL) ■ pracovní paměť abstraktního počítače ■ použitý v unifikaci, syntaktické analýze apod. Hana Rudová, Logické programování I, 1 5. května 201 3 261 Implementace Prologu Rozmístění datových oblastí ■ Příklad konfigurace Halda \ f Stopa / Zásobník \ f PDL / Oblast kodu ■ Halda i lokální zásobník musí růst stejným směrem ■ lze jednoduše porovnat stáří dvou proměnných srovnáním adres využívá se při zabránění vzniku visících odkazů Hana Rudová, Logické programování I, 1 5. května 201 3 262 Implementace Prologu Registry WAMu Stavové registry: P čitač adres (Program counter) CP adresa návratu (Continuation Pointer) E ukazatel na nejmladší okolí (Environment) B ukazatel na nejmladší bod volby (Backtrack point) TR vrchol stopy (TRail) H vrchol haldy (Heap) HB vrchol haldy v okamžiku založení posledního bodu volby (Heap o Backtrack point) S ukazatel, používaný při analýze složených termů (Structure pointer) CUT ukazatel na bod volby, na který se řezem zařízne zásobník Argumentové registry: A1,A2 , . . . (při předávání parametrů n. pracovní registry) Registry pro lokální proměnné: Y1,Y2, . . . ■ abstraktní znázornění lok. proměnných na zásobníku Hana Rudová, Logické programování I, 15. května 2013 263 Implementace Prologu Typy instrukcí WAMu ■ put instrukce - příprava argumentů před voláním podcíle ■ žádná z těchto instrukcí nevolá obecný unifikační algoritmus ■ get instrukce - unifikace aktuálních a formálních parametrů ■ vykonávají činnost analogickou instrukcím unify ■ obecná unifikace pouze při get_value ■ unify instrukce - zpracování složených termů ■ jednoargumentové instrukce, používají registr S jako druhý argument ■ počáteční hodnota S je odkaz na 1. argument ■ volání instrukce unify zvětší hodnotu S o jedničku ■ obecná unifikace pouze při unify_value a unify_local_value ■ Indexační instrukce - indexace klauzulí a manipulace s body volby ■ Instrukce řízení běhu - předávání řízení a explicitní manipulace s okolím Hana Rudová, Logické programování I, 15. května 2013 264 Implementace Prologu Instrukce put a get: příklad Příklad: a(X,Y,Z) :- b(f,X,Y,Z). get_var A1,A5 get_var A2,A6 get_var A3,A7 put_const AI,f put_value A2,A5 put_value A3,A6 put_value A4,A7 execute b/4 Hana Rudová, Logické programování I, 1 5. května 201 3 265 Implementace Prologu WAM - optimalizace 1. Indexace klauzulí 2. Generování optimální posloupnosti instrukcí WAMu 3. Odstranění redundancí při generování cílového kódu. ■ Příklad: a(X,Y,Z) :- b(f,X,Y,Z). naivní kód (vytvoří kompilátor pracující striktně zleva doprava) vs. optimalizovaný kód (počet registrů a tedy i počet instrukcí/přesunů v paměti snížen): get_var A1,A5 I get_var A3,A4 get_var A2,A6 I get_var A2,A3 get_var A3,A7 I get_var A1,A2 put_const AI,f | put_const AI,f put_value A2,A5 | execute b/4 put_value A3,A6 1 put_value A4,A7 1 execute b/4 | Hana Rudová, Logické programování I, 1 5. května 201 3 266 Implementace Prologu Instrukce WAMu get instrukce get_var Ai,Y get_value Ai,Y get_const Ai,C get_nil Ai get_struct Ai,F/N get_li st Ai put instrukce put_var Ai,Y put_value Ai, Y put_unsafe_value Ai,Y put_const Ai,C put_nil Ai put_struct Ai,F/N put_list Ai uni f y instrukce unify_var Y unify_value Y unify_local_value Y unify_const C uni fy_ni1 unify_void N instrukce řízení allocate deallocate call Proc/N,A execute Proc/N proceed indexační instrukce try_me_else Next retry_me_else Next trust_me_else fail try Next retry Next trust fail cut_last switch_on_term Var,Const,List,Struct save_cut Y switch_on_const Table load_cut Y switch_on_struct Table Hana Rudová, Logické programování I, 1 5. května 201 3 267 Implementace Prologu WAM - indexace ■ Provázání klauzulí: instrukce XX_me_else: ■ první klauzule: try_me_el se; založí bod volby ■ poslední klauzule: trust_me_el se; zruší nejmladší bod volby ■ ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu ■ Provázání podmnožiny klauzulí (podle argumentu): ■ try ■ retry ■ trust ■ „Rozskokové" instrukce (dle typu a hodnoty argumentu): ■ switch_on_term Var, Const, List, Struct výpočet následuje uvedeným návěstím podle typu prvního argumentu ■ swi tch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura) Hana Rudová, Logické programování I, 1 5. května 201 3 268 Implementace Prologu Příklad indexace instrukcí Proceduře a(atom) :- bodyl. a(l) :- body2. a(2) :- body3. a([X|Y]) a([X|Y]) a(s(N)) a(f(N)) - body4 - body5 body6. bodyľ. odpovídají instrukce a: L2: L3: L4: LI: Lla switch_on_term LI, L2, L3, L4 switch_on_const atom 1 2 try L7a trust L8a switch_on_struct s/l f/1 try_me_else L5 bodyl Lla L5a L6a L9a LlOa L5: retry_me_else L6 Hana Rudová, Logické programování I, 1 5. května 201 3 L5a: body2 L6: retry_me_else L7 L6a: body3 L7: retry_me_else L8 L7a: body4 L8: retry_me_else L9 L8a: body5 L9: retry_me_else L10 L9a: body6 L10: trust_me_else fail LlOa: body7 269 Implementace Prologu WAM - řízení výpočtu execute Proč: ekvivalentní příkazu goto proceed: zpracování faktů allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) deal locate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) call Proč,N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobníku) Možná optimalizace: vhodným uspořádáním proměnných lze dosáhnout postupného zkracování lokálního zásobníku a(A,B,C,D) :- b(D), c(A,C), d(B), e(A), f. generujeme instrukce allocate call b/1,4 call c/2,3 call d/1,2 call e/1,1 deallocate execute f/0 Hana Rudová, Logické programování I, 15. května 2013 270 Implementace Prologu WAM - řez Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby ■ příklad: ?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické cut_last: B := CUT save_cut Y: Y : = CUT load_cut Y: B := Y Hodnota registru B je uchovávána v registru CUT instrukcemi cal 1 a execute. Je-li řez prvním predikátem klauzule, použije se rovnou cut_last. V opačném případě se použije jako první instrukce save_cut Y a v místě skutečného volání řezu se použije load_cut Y. Příklad: a(X,Z) :- b(X), !, c(Z). a(2,Z) :- !, c(Z). a(X,Z) :- d(X,Z). odpovídá save_cut Y2; get A2,Y1; call b/1,2; load_cut Y2; put Y1,A1; execute c/1 get_const AI,2; cut_last; put A2,A1; execute c/1 execute d/2 Hana Rudová, Logické programování I, 15. května 2013 271 Implementace Prologu