I BO 1 3 Logické programování I Hana Rudová jaro 2007 Základní informace Přednáška: účast není povinná Cvičení: zápočet udělen za zápočtový projekt Web předmětu na IS: Studijní materiály -> Titulní strana https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3 524;kod=IB013;qurl=/el/1433/jaro2007/IB013/index.qwarp ■ průsvitky dostupné postupně v průběhu semestru ■ harmonogram výuky ■ předběžný obsah výuky pro jednotlivé přednášky během semestru ■ elektronicky dostupné materiály 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 ■ implementace logického programováni Hana Rudová, Logické programování I, 17. května 2007 3 Organizace předmětu Hodnocení předmětu ■ Zápočtový projekt: celkem až 40 bodů ■ Průběžná písemná práce: až 30 bodů (základy programování v Prologu) ■ pro každého jediný termín: 19. března ■ alternativní termín pouze v případech závažných důvodů pro neúčast ■ Závěrečná písemná práce: až 1 50 bodů ■ cca tři řádné termíny písemky, vzor písemky na webu předmětu ■ žádná opravná písemka ■ opravný termín: ústní zkouška ■ alternativní termín po dohodě jen v případech závažných důvodů pro neúčast spíše formou delší ústní zkoušky ■ 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 Hana Rudová, Logickě programování I, 17. května 2007 2 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, 17. května 2007 4 Organizace předmětu Software: SICStus Prolog Cvičení Doporučovaná implementace Prologu Dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html Komerční produkt Zakoupena licence pro instalace na domácí počítače studentů Podrobné informace na webu předmětu Hana Rudová, Logické programování I, 17. května 2007 Organizace předmětu Průběžná písemná práce Pro každého jediný termín 19. 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ů 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, 17. května 2007 Organizace předmětu 1 Zaměřeno na praktické aspekty, u počítačů 1 Skupiny: ■ skupina 01, sudé pondělí, první cvičení 19.února ■ skupina 02, liché pondělí, první cvičení 26.února 1 Zápočtové projekty: Adriana Strejčkova ■ 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 ■ vystavení projektů na webu předmětu: do 28.února ■ zahájení registrace řešitelů projektu: 14. března ■ předběžná analýza řešeného problému: 4. dubna ■ termín pro odevzdání projektů: 18. května ■ předvádění projektů (po registraci): 28.května - 1 5.června Hana Rudová, Logickě programování I, 17. května 2007 6 Organizace předmětu Úvod do Prologu Prolog Prolog: historie a současnost PROgramming in LOCic ■ čá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 Rozvoj začíná po roce 1 970 ■ Robert Kowalski - teoretické základy ■ Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace ■ pozdější rozšíření Prologu o logické programování s omezujícími podmínkami Prolog v současnosti ■ zavedené aplikační oblasti, nutnost přidání inteligence ■ hypotéky; pediatrický sw; konfigurace a pravidla pro stanovení ceny objednávky; testovací nástroje, modelové testování; ... ■ náhrada procedurálního kódu Prologem vede k ■ desetinásobnému zmenšení kódu, řádově menšímu času na vývoj, jednodušší údržbě ■ efektivita Prologu? ■ zrychlení počítačů + výrazné zvětšení nároků sw => ve prospěch kompaktnosti i rychlosti Prologu Hana Rudová, Logické programování I, 17. května 2007 Úvod do Prologu Hana Rudová, Logické programování I, 17. května 2007 Úvod do Prologu Program = fakta + pravidla (Prologovský) program je seznam programových klauzulí ■ programové klauzule: fakt, pravidlo Fakt: deklaruje vždy pravdivé věci ■ clovekC novak, 18, student ). Pravidlo: deklaruje věci, jejichž pravdivost závisí na daných podmínkách ■ studujeC X ) :- c"lovek( X, _Vek, student ). ■ alternativní (obousměrný) význam pravidel pro každé X, pro každé X, X studuje, jestliže X je student, potom X je student X studuje ■ pracujeC X ) :- c"lovek( X, _Vek, CoDela ), praceC CoDela ). Predikát: množina 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í 1,17. května 2007 11 Ú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ářů clovekC novak, 18, student ). % komentář na konci řádku clovekC novotny, 30, učitel ). /* komentář '■'•'/ Hana Rudová, Logické programování 1,17. května 2007 12 Úvod do Prologu Dotaz Klauzule = fakt, pravidlo, dotaz Dotaz: uživatel se ptá programu, zda jsou věci pravdivé ?- studujeC novak). % yes splnitelný dotaz ?- studujeC novotny). % no 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) ■ ?- clovekC novak, 18, Prace ). ■ 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í ?- clovekC novak, Vek, Prace ). % všechna řešení přes ";" Hana Rudová, Logické programování I, 17. května 2007 13 Úvod do Prologu ■ 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 ■ rodicC pavla, robert ). ■ Pravidlo: hlava i tělo ■ upracovany_c"lovek( X ) :- clovekC X, _Vek, Prace ), praceC Prace, tezka ). ■ Dotaz: prázdná hlava, pouze tělo ■ ?- clovekC novak, Vek, Prace ). ?- rodicC pavla, Dite ), rodic( Dite, Vnuk ). Hana Rudová, Logické programování I, 17. května 2007 14 Úvod do Prologu edek( X, Z ) edek( X, Z ) Rekurzivní pravidla edekC X, Z ) :- rodicC X, Z ). rodicC X, Y ), rodicC Y, Z ). rodicC X, Y ), predekC Y, Z ). % CD % (2) % C2') Příklad: rodokmen rod rod rod rod rod c( pavla, robert ). c( tomas, robert ) . c( tomas, eli ska ). c( robert, anna ). c( robert, petr ). rodic( petr, jirka ). predek( X, Z ) :- rodic( X, Z ). % (D predek( X, Z ) :- rodic( X, Y ), predek( Y, Z ). % (2') Hana Rudová, Logické programování I, 1 7. května 2007 1 5 Úvod do Prologu Hana Rudová, Logické programování I, 1 7. května 2007 1 6 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas,robert) Výpočet odpovědi na dotaz ?- predek(tomas, petr) rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, anna ). rodic( robert, petr ). rodic( petr, jirka ). yes predek(tomas,robert) dle (1) rodic(tomas,robert) predek( X, Z ) predek( X, Z ) rodic( X, Z ). % (1) rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 17. května 2007 17 Úvod do Prologu Odpověď na dotaz ?- predek(robert, Potomek) rodicC pavla, robert ). rodicC tomas, robert ). rodicC tomas, eliska ). rodicC robert, anna ). rodicC robert, petr ). rodicC petr, jirka ). predekC X, Z ) predekC X, Z ) rodicC X, Z ). rodicC X, Y ), predekC Y, Z ). predekCrobert,Potomek) —> ??? Hana Rudová, Logické programování I, 17. května 2007 Úvod do Prologu predek(tomas, petr) dle (1) dle (2') no rodic( tomas, petr) rodic(tomas, Y) predek( Y, petr) rodicC tomas, robert ). rodicC tomas, eliska ). rodicC robert, petr ). Y=robert predekC X, Z ) predekC X, Z ) rodicC X, Z ) . % CD rodicC X, Y ), % (2') predekC Y, Z ). dle rodic(tomas, robert) predek( robert, petr) dle (1) rodic(robert, petr) yes Hana Rudová, Logické programování I, 17. května 2007 Úvod do Prologu Syntaxe a význam Prologovských programu 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: první(X,X,X). první(X,X,_). Hana Rudová, Logické programování I, 1 7. května 2007 21 Syntaxe a význam Prologovských programů Unifikace Termy jsou u n ifí kováte Iné, jestliže ■ jsou identické nebo ■ proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické ■ datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 Nejobecnější unifikátor (most generál unifler (MGU) ■ jiné instanciace? ...Dl =1, Ml = 5, Y2 = 2003 ■ ?- 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, 17. května 2007 23 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 ■ trojuhelnikC bod(4,2), bod(6,4), bod(7,l) ) ■ Hlavní funktor termu - funktor v kořenu stromu odpovídající termu ■ trojuhelni k je hlavní funktor v trojuhel ni k( bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 17. května 2007 22 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1. SaTjsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; Tje proměnná a S cokoliv jiného - Tje 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(2),4,ss(2),s(l))... no sCsss(A),4,ss(3)) = s(sss(2),4,ss(A))... no s(sss(A),4,ss(C)) = s(sss(t(B)),4,ss(A))... A=t(B),C=t(B)... yes Hana Rudová, Logické programování I, 17. května 2007 24 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ů Deklarativní význam programu Máme-li program a cíl C, pak deklarativní význam říká: cíl C je splnitelný právě tehdy, když cíl ?- ma_dite(petr). existuje klauzule C v programu taková, že existuje instance I klauzule C taková, že hlava I je identická s Ca všechny cíle v těle I jsou pravdivé. Instance klauzule: proměnné v klauzuli jsou substituovány termem ■ ma_dite(X) :- rodic( X, Y ). % klauzule ma_dite(petr) :- rodic( petr, Z ). % instance klauzule Hana Rudová, Logické programování I, 17. května 2007 25 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šší: p :- q, r; s, t, u. P :- Cq, r) ; (s, t, u). P :- q, r. p : - s , t, u . Hana Rudová, Logické programování I, 17. května 2007 27 Syntaxe a význam Prologovských programu Hana Rudová, Logické programování I, 17. května 2007 26 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů Ca) 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). c(l). (d) a(X) :- c(Y), b(X,Y). % změněné pořadí cílů v těle klauzule vzhledem k (c) bCl.D. 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, 17. května 2007 28 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů II. (1) a(X) :- c(Y), b(X,Y). (2) b(l,l). (3) c(2). (4) c(l). Vyzkoušejte si: a(X) :- b(X,X), c(X). a(X) :- b(X,Y), c(X). b(2,2). b(2,l). c(l). Hana Rudová, Logické programování I, 17. května 2007 ?- a(X). a(X) dle (1) c(Y), b(X,Y) dle {3)//Y=2 dle (4)\Y=1 b(X,2) b(X,1) no dle (2) X=1 yes Syntaxe a význam Prologovských programů Operátory Infixová notace: 2*a + b*c Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400 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 ). ■ :- op( 1100, xfy, ; ). :- 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ě speciálních případů) priorita: 1..1200 nestrukturované objekty: 0 Hana Rudová, Logické programování I, 17. května 2007 Operátory, aritmetika Operátory, aritmetika Typy operátorů př. xfx = yfx -př. fx ?- fy - Typy operátorů ■ infixové operátory: xfx, xfy, yfx ■ prefixové operátory: 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 chybně c; © priorita: 0 priorita: 0 priorita: 500 priorita: 500 Hana Rudová, Logické programování I, 17. května 2007 Operátory, aritmetika Aritmetika Předdefinované operátory + , -, *, /, '■'•"■'•'mocnina,// celočíselné dělení, 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é) volání?- X i s 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, 17. května 2007 33 Operátory, aritmetika Prolog: příklady Různé typy rovností a porovnání X = Y XaY jsou unifikovatelné 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 i s Y Y je aritmeticky vyhodnoceno a výsledek je přiřazen X X =:= Y X a Y jsou si aritmeticky rovny X =\= Y XaY 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, 17. května 2007 Operátory, aritmetika Příklad: 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, 17. května 2007 36 Prolog: příklad Příklad: věž z kostek Příklad: postavte věž zadané velikosti ze tří různě velkých kostek tak, že kostka smí ležet pouze na větší kostce. kostka(mala). kostka(st redni). kostka(velka). vetsi(zeme,velka). vetsi(zeme,stredni). vetsi(zeme,mal a). vetsi(velka,st redni). vetsi(velka,mal a). vetsi(stredni,mala). % ?- postav_vez(vez(zeme,0), vez(Kostka,0)). % ?- postav_vez(vez(zeme,0), vez(Kostka,3)). postav_vez( Vez, Vez ). postav_vez( Vstup, Vystup ) :- pridej_kostku( Vstup, Přidáni ), postav_vez( Přidáni, Vystup ). pridej_kostku( Vstup, Přidáni ) :- Vstup = vez( Vrchol, Vyska ), kostka( Kostka ), vetsi( Vrchol, Kostka ), NovaVyska i s Vyska + 1, Přidáni = vez( Kostka, NovaVyska ). Rez, negace Hana Rudová, Logické programování I, 17. května 2007 Prolog: příklad Řez a upnutí Rez a ořezání f(X,0) f(X,2) f(X,4) X < 3, ! . 3 =< X, X < 6, ! 6 =< X. přidání operátoru řezu , , ! ' ' f(X,Y) s(X,Y) s(X,Y) s(X,Y). Y is X + 1. Y is X + 2. f(X,Y) s(X,Y) s(X,Y) s(X,Y), !. Y is X + 1. Y is X + 2. 6 ?- f(l,Y), Y>2. f(X,0) :- X < 3, !. %(1) f(X,2) :- X < 6, !. %(2) f(X,4). ?- fCl.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í ?- fCl,Z). Z = 2 ? ; Z = 3 ? ; no ?- fCl,Z). Z = 2 ? ; 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, 17. května 2007 Hana Rudová, Logické programování I, 17. května 2007 Chování operátoru řezu Předpokládejme, že klauzule H :- TI, T2, Tm, !, aktivována voláním cíle C, který je unifikovatelný s H. V momentě, kdy je nalezen řez, existuje řešení cílů TI.....Tm Ořezání: při provádění řezu se už další možné splnění cílů TI, .. nehledá a všechny ostatní alternativy jsou odstraněny Upnutí: dále už nevyvolávám další klauzule, jejichž hlava je také unifikovatelná s C .Tn. je G=h(X,Y) X=1,Y=1 Tm Y=2 X=2 ?- h(X,Y). h(l,Y) h(2,Y) tl(Y), !. a. tl(l) tl(2) b. 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, 17. května 2007 Řez: cvičení 1. Porovnejte chování uvedených programů pro zadané dotazy. a(X,X) :- b(X). a(X,Y) :- Y is X+l. b(X) :- X > 10. ?- a(X,Y). ?- aCl.Y). ?- a(ll,Y). a(X,X) a(X,Y) bCX) :- :- b(X),!. :- Y is X+l. X > 10. a(X,X) a(X,Y) b(X) :-c :- ! . :- b(X),c. :- Y is X+l. X > 10. 2. Napište predikát pro výpočet maxima max( X, Y, Max ) c(X) c(X) PCX). v(X). Rez: příklad cl(X) :- p(X), ! cl(X) :- v(X). Pd). P(2). v(2). ?- c(2). true ? ; %p(2) true ? ; %v(2) no ?- cl(2). true ? ; %p(2) no ?- c(X). X = 1 ? X = 2 ? X = 2 ? no %P(D %P(2) %v(2) ?- cl(X). X = 1 ? ; %p(l) no Hana Rudová, Logické programování I, 17. května 2007 Typy řezu Zlepšení efektivity programu: určíme, které alternativy nemá smysl zkoušet 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áni I, 17. května 2007 43 Rez, negace Hana Rudová, Logické programování I, 17. května 2007 Negace jako neúspěch Negace jako neúspěch: operátor \+ Speciální cíl pro nepravdu (neúspěch) fail a pravdu true Xa Y nejsou unifikovatelné: different(X, Y) differentC X, Y ) :- X = Y, !, fail. differentC _X, _Y ). Xje muž: muz(X) muz( X ) :- zena( X ), !, fail. muz( _X ). different(X,Y) :- X different(_X,_Y). Y, !, fail. muz(X) :- zena(X), !, fail 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, 17. května 2007 45 Negace a proměnné \+(P) :- P, !, fail. % (I) \+(_). % (ID dobre( citroen ). dobre( bmw ). drahe( bmw ). rozumne( Auto ) :-\+ drahe( Auto ). % (D % (2) % (3) % (4) ?- dobre( X ), rozumne( X ). d ob re (X), rozum n e (X) dle (1), X/citroen rozumne(citroen) dle (4) \+ drahe(citroen) \ dle (II) dle (I) drahe(citroen),!, fail □ yes no Hana Rudová, Logické programování I, 17. května 2007 47 Hana Rudová, Logické programování I, 17. května 2007 Negace a proměn \+(P) :- P, !, fail. % (I) \+(_). % (ID dobre( citroen ). % (1) dobre( bmw ). % (2) drahe( bmw ). % (3) rozumne( Auto ) :- % (4) \+ drahe( Auto ). ?- rozumne( X ), dobre( X ). b'žTimne(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 Hana Rudová, Logické programování I, 17. května 2007 Bezpečný cíl ?- rozumneC citroen ). yes ?- rozumne( X ). no ?- \+ drahe( citroen ). yes ?- \+ drahe( X ). no \+ Pje bezpečný: proměnné Pjsou 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, 17. května 2007 Predikáty na řízení běhu programu I. ř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 prípade R (P -> Q ; R) :- R. ■ príklad: min(X,Y,Z) : - X =< Y -> Z = X ; Z = Y. P -> Q ■ odpovídá: (P -> Q; fail) ■ príklad: zaporne(X) :- number(X) -> X < 0. Hana Rudová, Logické programování I, 17. května 2007 51 Chování negace ?- \+ drahe( citroen ). ?- \+ drahe( X ). Negace jako neúspěch používá předpoklad uzavřeného světa pravdivé je pouze to, co je dokazatelné yes no ?- \+ 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 ) ■ ?- drahe( X ). VÍME: existuje X takové, že drahe( X ) platí 1 ALE: pro cíle s negací neplatí existuje X takové, že \+ drahe( X ) p negace jako neúspěch není ekvivalentní negaci v matematické logice Hana Rudová, Logické programování I, 17. května 2007 50 Řez, negace Predikáty na řízení běhu programu II. 1 cal 1 (P): zavolá cíl P a uspěje, pokud uspěje P 1 nekonečná posloupnost backtrackovacích voleb: repeat repeat. repeat :- repeat. klasické použití: generuj akci X, proveď ji a otestuj, zda neskončit Hlava :- ... u"loz_stav( StaryStav ), repeat, generuje X ), % deterministické: generuj, prováděj, testuj prováděj( X ), testuj( X ), i obnov_stav( StaryStav ), Hana Rudová, Logické programování I, 17. května 2007 Reprezentace seznamu Seznamy 1 Seznam: [a, b, c], prázdný seznam [] 1 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] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ' Lze psát i: [a, b | Tel o] ■ před " |" 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]]r[a,b| [c] ] 1 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, 17. května 2007 54 Prvek seznamu ■ member( X, S ) ■ platí: member( b, [a,b,c] ). ■ neplatí: member( b, [[a,b]|[c]] ). ■ Xje prvek seznamu S, když ■ Xje hlava seznamu S nebo member( X, [ X | _ ] ). %(1) ■ Xje prvek těla seznamu S member( X, [ _ | Telo ] ) :- member( X, Telo ). %(2) ■ Další příklady použití: ■ memberCX,[1,2,3]) . ■ memberCl,[2,1,3,1]). Hana Rudová, Logické programování I, 17. května 2007 55 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 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, 17. května 2007 Příklady použití append appencK [] , S, S ) . appencK [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). Spojení seznamů: append( [a,b,c], [1,2,3], S ). S = [a,b,c,1,2,3] append( [a, [b,c], d], [a, [], b], S ). S = [a, [b,c], d, a, [], b] ] Dekompozice seznamu na dva seznamy: append ( SI, S2 , [a, b ]). SI = [], S2 = [a, b] ; SI = [a], S2 = [b] ? ; SI = [a,b], S2 = [] Vyhledávání v seznamu:append( Pred, [ c | Za ], [a,b,c,d,e] ). Pred = [a,b], Za = [d,e] Předchůdce a následník: append( _, [Pred ,c,Za|_], [a, b,c,d,e] ). Pred = b, Za = d Hana Rudová, Logické programování I, 17. května 2007 57 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, kdyje 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ám' v těle klauzule p( ...):- ... % žádné rekurzivní voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus Tento typ rekurze lze převést na iteraci Smazání prvku seznamu delete( X, S, SI ) ■ Seznam SI odpovídá seznamu S, ve kterém je smazán prvek X ■ jestliže X je hlava seznamu S, pak výsledkem je tělo S delete( X, [X|Telo], Telo). ■ jestliže X je v těle seznamu, pak X je smazán až v těle delete( X, [Y|Telo], [Y|Telol] ) :- delete( X, Telo, Telol ). ■ delete smaže libovolný výskyt prvku pomocí backtrackingu ?- delete(a, [a,b,a,a], S). S = [b,a,a]; S = [a,b,a]; S = [a,b,a] ■ delete, který smaže pouze první výskyt prvku X ■ delete( X, [X|Telo], Telo) :- !. delete( X, [Y|Telo], [Y|Telol] ) :- delete( X, Telo, Telol). Hana Rudová, Logické programování I, 17. května 2007 58 Seznamy LCO a akumulátor ■ Reformulace rekurzivní procedury, aby umožnila LCO ■ Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ) . lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. ■ Upravená procedura, tak aby umožnila LCO: % lengthC Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' lengthC Seznam, Délka ) :- lengthC Seznam, 0, Délka ). % pomocný predikát lengthC □ , Délka, Délka ). % celková délka = započítaná délka lengthC [ H | T ], A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ). ■ Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 17. května 2007 59 Seznamy Hana Rudová, Logické programování I, 17. května 2007 max_list s akumulátorem Výpočet největšího prvku v seznamu max_1ist(Seznam, Max) max_"list([X] , X) . max_"h'st([X|T] , Max) :-max_li s t(T,MaxT), C MaxT >= X, !, Max = MaxT Max = X ). max_"list([H|T] ,Max) :- max_"list(T,H,Max) . max_listC[], Max, Max). max_list([H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_list(T, H, Max ) max_1ist(T, CastecnyMax, Max) ). Hana Rudová, Logické programování I, 17. května 2007 61 Seznamy Akumulátor jako seznam ■ Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) ■ reverseC [], [] ) . 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 reversef Seznam, OpacnySeznam ) :- reversef Seznam, [], OpacnySeznam). reversef [], S, S ). reversef [ H | T ], A, Opacny ) :- reversef 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, 17. května 2007 62 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ždyje nutné projít celý první seznam Hana Rudová, Logické programování I, 17. května 2007 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 Z1 A2 Z2 A1 L1 L2 \ -3- append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 L3 ?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 = [2,3|Z1] - Z2 = [2,3| [1|Z2] ] Zl = [1|Z2] S = [2,3,1|Z2]-Z2 Z2 Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování I, 17. května 2007 Akumulátor vs. rozdílové seznamy: reverse reverseC [] , [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). kvadratická složitost reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC [] , S, S ) . reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H | A ], Opacny ). akumulátor Oineárni) reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [] , S-S ) . reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). rozdílové seznamy Cl i neá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 7. května 2007 65 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, 17. května 2007 67 Vestavěné predikáty 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: assert( 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, 17. května 2007 Vestavěné predikáty Príklad: databázové operace Vstup a výstup Caching: odpovědi na dotazyjsou 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 a i 1. uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování I, 17. května 2007 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)/telling(S) ctěni( Soubor ) :- seeing( StarySoubor ), see( Soubor ), cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování I, 17. května 2007 Vestavěné predikáty uživatelsky terminal vstupní proudy 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 user I 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 —k program —k výstupní proudy Hana Rudová, Logické programování I, 17. května 2007 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 | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj C petre ). [ ahojC 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme ■ po dosažení konce souboru je vrácen atom end_of_f i le zápis dalšího termu: write(Term) ?- writeC ahoj ). ?- writeC '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, 17. května 2007 Vestavěné predikáty Príklad čtení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, % zjištění aktivního proudu % otevření souboru Soubor % čtení termu Term % manipulace s termem % je konec souboru? seen, see( StarySoubor ). % uzavření souboru % aktivace původního proudu repeat. repeat repeat. % opakování Hana Rudová, Logické programování I, 17. května 2007 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 ). ?- bagofC Dite, vek( Dite, 5 ), Seznam ). Seznam = [ anna, tomas ] Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagofC Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, 17. května 2007 Vestavěné predikáty Čtení programu ze souboru Interpretování kódu programu ■ ?- consult(program). ■ ?- consult('program.pl'). ■ ?- consult( [programl, 'program2.pl'] ). ■ ?- [program]. ■ ?- [user]. zadávání kódu ze vstupu ukončené CTRL+D Kompilace kódu programu ■ ?- compile( [programl, 'program2.pl']). ■ další varianty podobně jako u interpretování ■ typické zrychlení: 5 až 10 krát Hana Rudová, Logické programování I, 17. května 2007 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 ). ?- bagofC Dite, ( vek( Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] bagof, setof, findall: na objekty shromažďované vX nejsou žádná omezení ?- bagofC Dite-Vek, vek( Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programování I, 17. května 2007 Vestavěné predikáty Existenční kvantifikátor „" " ■ Přidání existenčního kvantifikátoru ,," " => hodnota proměnné nemá význam ?- bagofC Dite, Vek'vekC 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 ?- bagofC Dite, vek( Dite, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna.tomas] ■ Před operátorem ,," " může být i seznam ?- bagofC Vek ,[]meno,Přijmeni]"vek( ]meno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování I, 17. května 2007 77 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 ■ findaIK X, P, S ): rozdíly od bagof ■ všechny proměnné jsou existenčně kvantifikovány ?- findaIK Dite, vek( Dite, Vek ), Seznam ). svS 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 = [] ■ ?- bagofC Dite, vekC Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findaIK Dite, vekC Dite, Vek ), Seznam ). Seznam = [petr.anna.tomas] Hana Rudová, Logické programování I, 17. května 2007 78 Vestavěné predikáty Testování typu termu Určení počtu výskytů prvku v seznamu var(X) nonvar(X) atom(X) i nteger(X) float (X) atomi c(X) compound(X) X je volná proměnná X není proměnná X je atom (pavel, 'Pavel Novák', <-->) X je integer X je float X je atom nebo číslo X je struktura count( X, S, N ) :- count( X, S, 0, N ). count( _, [], N, N ). count( X, [X|S], NO, N) :- !, Nl is NO + 1, count( X, S, Nl, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) N=3 :-? count( a, [a,b,X,Y], N). N=3 count( _, [], N, N ). count( X, [Y|S], NO, N ) :- nonvar(Y), X = Y, !, Nl is NO + 1, count( X, S, Nl, N ). count( X, [_|S], NO, N ) :- count( X, S, NO, N ). Hana Rudová, Logické programování I, 17. května 2007 79 Vestavěné predikáty Hana Rudová, Logické programování I, 17. května 2007 80 Vestavěné predikáty Konstrukce a dekompozice atomu Konstrukce a dekompozice termu 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 ) nameC ano, [97,110,111] ) nameC ano, "ano" ) Hana Rudová, Logické programování I, 17. května 2007 81 Vestavěné predikáty ■ 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 ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) arg( N, Term, Argument ) argC 2, a(9,e), e) Hana Rudová, Logické programování I, 17. května 2007 82 Vestavěné predikáty Rekurzivní rozklad termu Term je proměnná (var/l), atom nebo číslo (atomic/1) => konec rozkladu Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu Term je složený (=../2 , functor/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. groundC[H|T]) :- !, ground(H), ground(T). ground(Term) :- Term =.. [ _Funktor | Argumenty ], groundC 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, 17. května 2007 83 Vestavěné predikáty Příklad: dekompozice termu I. ■ 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 is 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, NI), N2 is NO + NI, 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, 17. května 2007 84 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 bez proměnných) , Technika a styl programovaní v Prologu ■ ?- substitute( sin(x), 2*sin(x)*f(sin(x)), t, F ). F=2*t*f(t) Hana Rudová, Logické programování I, 17. května 2007 85 Vestavěné predikáty 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 7. května 2007 87 Technika a styl programování v Prologu Styl programování v Prologu I. ■ 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ájmena 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 7. května 2007 88 Technika a styl programování v Prologu Správný styl programování Špatný styl programování konstrukce setříděného seznamu Seznam3 ze setříděných seznamů Seznámí, Seznam2: merge( Seznámí, Seznam2, Seznam3 ) merge( [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 ). merge( [X|Telol], [Y|Telo2], [X|Te"lo3] ) :-X < Y, !, merge( Telol, [Y|Telo2], Te"lo3 ). mergeC Seznatnl, [Y|Telo2], [Y|Te"lo3] ) :-merge( Seznámí, Te"lo2, Te"lo3 ). merge( 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 merge( TI, S2, T3 ); Z = Y, merge( SI, T2, T3) ), 53 = [ Z | T3 ]. Hana Rudová, Logické programování I, 1 7. května 2007 89 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 negace: P, !, fail; true \+ P alternativy: Podmínka, !, Cill ; Cil2 Podmínka -> Cill ; Ci 12 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 Hana Rudová, Logické programování I, 1 7. května 2007 91 Technika a styl programování v Prologu Hana Rudová, Logické programování I, 1 7. května 2007 90 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í „-" mergeC +Seznaml, +Seznam2, -Seznam3 ) ■ ]menoPredikatu/Anta merge/3 ■ algoritmické a implementační podrobnosti Hana Rudová, Logické programování I, 1 7. května 2007 92 Technika a styl programování v Prologu Ladění Krabičkový (4-branový) model 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, 17. května 2007 Technika a styl programování v Prologu a(X) a(X) a(X) c(l). d(2). nonvar(X)■ c(X). d(X). Příklad: trasování I ?- a(X). Call I ------> + a(X) I a(X) <------+ a(X) Fai 1 I I Exit nonvar(X)■I ------> c(X). I d(X). + <------ I Redo 1 ? 1 1 Call : a(_463) 7 2 2 Call : nonvarC _463) ? 2 2 Fai 1 : nonvarC _463) ? 3 2 Call : c(_463) 7 3 2 Exi t: cCD ? 1 1 Exi t: a CD ? 1 1 Redo: a CD ? 4 2 Call : d(_463) 7 4 2 Exi t: d(2) ? 1 1 Exi t: a(2) ? X = 2 ? no % trace I ?- Hana Rudová, Logické programování I, 17. května 2007 Technika a styl programování v Prologu Vizualizace řídícího toku (backtrackingu) na úrovni predikátu ■ Cal 1: 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 Fail 1 Exit predekC X, Z ) :- rodicC X, Z ). +---------> i predekC X, Z ) :- rodicC X, Y ) , 1 1 predekC Y, Z ). + <--------- 1 Redo Hana Rudová, Logické programování I, 17. května 2007 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, 17. května 2007 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 Predikátová logika l.řádll ■ 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 ■ zamestnanecC Prijmeni, Krestni]meno, Odděleni, ...) Determinismus: ■ rozhodnout, které klauzule mají uspět vícekrát, ověřit požadovaný determinismus Hana Rudová, Logické programování I, I 7. května 2007 97 Technika a styl programování v Prologu Teorie logického programování PROLOG: PROgramming in LOCic, část predikátové logiky l.řádu ■ fakta: rodic(petr.petrik), VXa(X) ■ klauzule: VXVY rodic(X.Y) => predek(X.Y) Predikátová logika I. řádu (PL1) ■ soubory objektů: lidé, čísla, body prostoru, ... ■ syntaxe PL1, sémantika PL1, pravdivost a dokazatelnost Rezoluce ve výrokové logice, v PL1 ■ dokazovací metoda Rezoluce v logickém programování Backtracking, řez, negace vs. rezoluce Hana Rudová, Logické programování I, 17. května 2007 99 Teorie logického programování Predikátová logika I. řádu (PL1) Abeceda jazyka £ PL1 se skládá ze symbolů: ■ proměnné X, Y, ... označují libovolný objekt z daného oboru ■ funkční symboly f, g, ... označují operace (příklad: +, x ) ■ arita = počet argumentů, n-ární symbol, značíme f/n ■ nulární funkční symboly - konstanty: označují význačné objekty (příklad: 0, 1, ...) ■ predikátové symboly p,q, ... pro vyjádření vlastností a vztahů mezi objekty ■ arita = počet argumentů, n-ární symbol, značíme p/n příklad: <, e ■ logické spojky a, v, =>, = ■ kvantifikátory V, 3 ■ logika I. řádu používá kvantifikaci pouze pro individua (odlišnost od logik vyššího řádu) ■ v logice 1. řádu nelze: v E : V A s K, V f : K -> K ■ závorky: ),( Hana Rudová, Logické programování I, 17. května 2007 100 Predikátová logika Jazyky PLI Term, atomická formule, formule ■ Specifikace jazyka £ je definována funkčními a predikátovými symboly symboly tedy určují oblast, kterou jazyk popisuje ■ Jazyky s rovností: obsahují predikátový symbol pro rovnost „=" Příklady ■ jazyk teorie uspořádání ■ jazyk s =, binární prediátový symbol < ■ jazyk teorie množin ■ jazyk s =, binární predikátový symbol e ■ jazyk elementární aritmetiky ■ jazyk s =, nulární funkční symbol 0 pro nulu, unární funkční symbol s pro operaci následníka, binární funkční symboly pro sčítání + a násobení x Hana Rudová, Logické programování I, 17. května 2007 101 Predikátová logika ■ Term nad abecedou JA ■ každá proměnná z je term ■ je-li f/n z a ti.....tn jsou termy, pak f(t\.....tn) je také term ■ každý term vznikne konečným počtem užití přechozích kroků f( X, g(X,0)) ■ Atomická formule (atom) nad abecedou JA ■ je-li p/n z a ti.....tn jsou termy, pak p(t\.....tn) je atomická formule f(X) < g(X,0) ■ Formule nad abecedou JA ■ každá atomická formule je formule ■ jsou-li F a G formule, pak také (-ip), (F a G), (F v G), (F => G), (F = G) jsou formule ■ je-li X proměnná a F formule, pak také (VX F) a (3X F) jsou formule ■ každá formule vznikne konečným počtem užití přechozích kroků (3X ((f(X) = 0) a p(0))) Hana Rudová, Logické programování I, 17. května 2007 102 Predikátová logika Interpretace ■ Interpretace 1 jazyka L nad abecedou JA je dána ■ neprázdnou množinou T> (také značíme \1\, nazývá se univerzum) a ■ zobrazením, které ■ každé konstantě cei přiřadí nějaký prvek T> ■ každému funkčnímu symbolu f/n e JA přiřadí n-ární operaci nad T> ■ každému predikátovému symbolu p/n e JA přiřadí n-ární relaci nad T> ■ Příklad: uspořádání na R ■ jazyk: predikátový symbol menší/2 ■ interpretace: univerzum K; zobrazení: mensí(x,y) := x < y ■ Příklad: elementární aritmetika nad množinou N (včetně 0) ■ jazyk: konstanta zero, funční symboly s/l, plus/2 ■ interpretace: ■ univerzum N; zobrazení: zero := 0, s(x):=l + x, plus(x,y) := x + y Hana Rudová, Logické programování I, 17. května 2007 103 Predikátová logika Sémantika formulí ■ Ohodnocení proměnné qp(X): každé proměnném je přiřazen prvek \1\ ■ Hodnota termu (plus(s(zero),X)) = cp(s(zero)) + cp(X) = (1 + cp(zero)) + 0= (1 + 0)+ 0=1 ■ Každá dobře utvořená formule označuje pravdivostní hodnotu (pravda, nepravda) v závislosti na své struktuře a interpretaci Pravdivá formule 1 \=v Q: formule Q označena pravda Neravdivá formule 1 t^g, q: formule Q označena nepravda ■ příklad: p/1 predikátový symbol, tj. p s p := {(1), (3), (5>,...} '1 N p (zero) a p (s (zero)) iff '1 N p (zero) a 'i N p (s (zero)) iff (q}(zero)) e p a (q?(s(zero))) e p iff (q}(zero)) e p a <(1 + q?(zero)) e p iff <0)epa G lze odvodit G ■ rezoluční princip: z formulí F v A, G v odvodit F v G ■ F je dokazatelná z formulí A\, ■ ■ ■ ,An A\, ■ ■ ■ ,An\- F existuje-li důkaz F z A\, ■ ■ ■ ,An ■ Dokazatelné formule v teorii T' nazýváme teorémy teorie T' Hana Rudová, Logické programování I, 17. května 2007 106 Predikátová logika Rezoluce v predikátové logice I. řádu Hana Rudová, Logické programování I, 17. května 2007 107 Predikátová logika Rezoluce ■ rezoluční princip: z F v A, G v - formule je vždy pravdivá Hana Rudová, Logické programování I, 17. května 2007 109 Rezoluce v PL1 Formule ■ literál / ■ pozitivní literál = atomická formule p(t\, ■ ■ ■ ,tn) ■ negativní literál = negace atomické formule ->p(t\, ■ ■ ■ ,tn) ■ klauzule C = konečná množina literálů reprezentující jejich disjunkci ■ příklad: p(X) v q(a,f) v -ip(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: (pvij)A (->p) a (p v -iq v r) notace: {{p,g}, {->p}, {p, -^,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, 17. května 2007 1 10 Rezoluce v PL1 Splnitelnost ■ [Opakování:] Interpretace 1 jazyka £ je dána univerzem T> 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/nn-ámi relaci. ■ příklad: F = {{f (a, b) = f (b,a)}, {f (f (a, a), b) = a}} interpretace 'h: D = 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 'h) ■ 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(«)}} je nesplnitelná ({p(a)\ a {-ip(a)} nemohou být zároveň pravdivé) Hana Rudová, Logické programování 1,17. května 2007 11 1 Rezoluce v PL1 Rezoluční princip ve výrokové logice ■ Rezoluční princip = pravidlo, které umožňuje odvodit z klauzulí Ci u {1} a {-ii} u Cz klauzuli C\ u Cz Ciujíl M}uC2 Ci uC2 ■ Q u C2 se nazývá rezolventou původních klauzulí ■ příklad: {p,r} {^t,s} (pvr)A(^rví) {p,s} p v s obě klauzule (pvr)a (-ir v s) musí být pravdivé protože r nestačí k pravdivosti obou klauzulí, musí být pravdivé p (pokud je pravdivé - -iF je nepravdivá ve všech interpretacích => F je vždy pravdivá začneme-li z klauzulí reprezentujících -iF, musíme postupným uplatňováním rezolučního principu dospět k prázdné klauzuli □ Příklad: F ... -ifl v a -■F ... a A -ia ^F...{{fl},{^fl}} Ci = {a},C2 = í-ia} rezolventa Ci a C2 je □, tj. F je vždy pravdivá rezoluční důkaz □ z formule F se nazývá rezoluční vyvrácení formule F Hana Rudová, Logické programování I, 17. května 2007 Rezoluce v PL1 Substituce co s proměnnými? vhodná substituce a unifikace ■ f(X,a,g(Y)) < l,f(h(c),a,Z) < 1, X = hic), Z = g(Y) => f(h(c),a,g(Y)) < 1 substituce je libovolná funkce 9 zobrazující výrazy do výrazů tak, že platí ■ 9(E) = E pro libovolnou konstantu E ■ 9(f (Ei, ■ ■ ■ ,En)) =f(0(Ei), ■ ■ ■ , 6(En)) pro libovolný funkční symbol / ■ 9(p(Ei, ■ ■ ■ ,En)) = p(9(Ei), ■ ■ ■ , 9(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/%n] kde Xi jsou proměnné a §í 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, 17. května 2007 Rezoluce v PL1 Unifikace Rezoluční princip v PL1 ■ Ztotožnění dvou literálů p, q pomocí vhodné substituce a takové, že per = qa nazýváme unifikací a příslušnou substituci unifikátorem. ■ Unifikátorem množiny S literálů nazýváme substituce 9 takovou, že množina S9 = {te\t e S} má jediný prvek. ■ příklad: S = { datum( Dl, Ml, 2003 ), datum( 1, M2, Y2) } unifikátor 6 = [Dl/l, Ml/2, M2/2, Y2/2003] S0 = { datum( 1, 2, 2003 ) } ■ Unifikátor a množiny S nazýváme nejobecnějším unifikátorem (mgu - most generál unifier), jestliže pro libovolný unifikátor 9 existuje substituce A taková, že 9 = ctA. ■ příklad (pokrač.): nejobecnější unifikátor a = [Dl /l, Y2/2003, Ml /M2], A=[M2/2] Hana Rudová, Logické programování I, 17. května 2007 117 Rezoluce v PL1 Příklad: rezoluce v PL1 ■ příklad: d = {p(X,Y), q(Y)} C2={^q(a), s(X,W)} ■ přejmenování proměnných: p = [XIZ] Ci = {p(Z,Y), q(Y)} C2 = {^q(a), s(X,W)} ■ nejobecnější unifikátor: a = [Y/a] Ci = {p(Z,a), q(a)} C2={^q(a), s(X,W)} ■ rezoluční princip: C = {p(Z, a), s(X, W)} ■ vyzkoušejte si: Ci = {q(X), -.r(y), p(X,Y), p(f(Z)J(Z))} C2 = {n(Y), -.r(^), -.p(/(a),/(a)), ^p(f(W),f(W)} Hana Rudová, Logické programování 1,17. května 2007 119 Rezoluce v PL1 ■ základ: ,....., . . . CrUffl M)uC2 ■ rezoluční princip ve výrokové logice -—-—- Li u c2 ■ substituce, unifikátor, nejobecnější unifikátor ■ rezoluční princip v PL1 je pravidlo, které ■ připraví příležitost pro uplatnění vlastního rezolučního pravidla nalezením vhodného unifikátoru ■ provede rezoluci a získá rezolventu Q u {A} {^B}uC2 C\pu u C2u ■ kde p je přejmenováním proměnných takové, že klauzule (C\ uA)p a {B} u C2 nemají společné proměnné ■ a je nejobecnější unifikátor klauzulí Ap a B Hana Rudová, Logické programování 1,17. května 2007 1 18 Rezoluce v PL1 Rezoluce v PL1 ■ Obecný rezoluční princip v PL1 Ci u {Au ■ ■ ■ ,Am} {-.ďi, ■■■,-.£„} u C2 Čiper u C2u ■ kde p je přejmenováním proměnných takové, že množiny klauzulí {A\p, ■ ■ ■ ,Amp} a {Bi, ■ ■ ■ ,Bn} nemají společné proměnné ■ a je nejobecnější unifikátor množiny {A\p, ■ ■ ■ ,Amp,B\, ■ ■ ■ ,Bn} ■ příklad: Ai = a(X) vs. {^Bi,^B2\ = {-*a(b), ^a(Z)} vjednom kroku potřebuji vyrezolvovat zároveň B\ i Bz ■ Rezoluce v PL1 ■ korektní: jestliže existuje rezoluční vyvrácení F, pak F je nesplnitelná ■ úplná: jestliže F je nesplnitelná, pak existuje rezoluční vyvrácení F Hana Rudová, Logické programování 1,17. května 2007 120 Rezoluce v PL1 Zefektivnění rezoluce rezoluce je intuitivně efektivnější než axiomatické systémy ■ axiomatické systémy: který z axiomů a pravidel použít? ■ rezoluce: pouze jedno pravidlo stále ale příliš mnoho možností, jak hledat důkaz v prohledávacím prostoru problém SAT= {SIS je splnitelná } NP úplný, nicméně: menší prohledávací prostor vede k rychlejšímu nalezení řešení strategie pro zefektivnění prohledávání => 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, 17. května 2007 121 Rezoluce v PL1 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,í?}, í-'P.q.}, {p,"■, ■■■ {Cn,Bn) taková, že C = Cn+i a ■ Co a každá Bi jsou prvky S nebo některé C,, j < i ■ každá Ci+i, i < n je rezolventa Q a Bi ■ lineární vyvrácení S = lineární rezoluční důkaz □ z S C„ B„ C \/ C, B j \/ C7 Hana Rudová, Logické programování I, 17. května 2007 124 Rezoluce a logické programování Lineární rezoluce II. Prologovská notace příklad: S = {Ai, A2, A3, A4} Ai = {p,q} A2 = {p, A3 = {^p,q} A4 = {-p, -q} S: vstupní množina klauzulí (',: střední klauzule B{. boční klauzule C i B i {p,q}{p, -iq} \/ (pí l^p,q} \/ iq] {-tn Jí — Ti v ■ ■ ■ v ->tn Pravidlo: jeden pozitivní a alespoň jeden negativní literál ■ Prolog: Jí : - Ti, ■ ■ ■ , tn. Matematická logika: Jí <= Ti a ■ ■ ■ a tn ■ Jí <= T Jí v-T Jí v -.Ti v ■ ■ ■ v -T„ Klauzule: {Jí,-.Tj.....- Fakt: pouze jeden pozitivní literál ■ Prolog: Jí. Matematická logika: Jí Klauzule: {Jí} Cílová klauzule: žádný pozitivní literál ■ Prolog: : - Ti,... tn. Matematická logika: -Ti v ■ ■ ■ v -T„ Klauzule: -Ti,- Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Lineární rezoluce pro Hornovy klauzule Začneme s cílovou klauzulí: Co = G Boční klauzule vybíráme z programových klauzulí P G={-.q,-.p} P= {P1.P2.P3} ■ Pi = {p}, P2 = {p,^q}, P3 = {q} :-q,p. p. P--q, q. {^q,^p} Iq} f-v.-ip} Iq} l^pl (p>^ql \/ \/ {-ip} (pJ {->qJ M \/ \/ □ □ Střední klauzule jsou cílové klauzule Hana Rudová, Logické programování I, 17. května 2007 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 S je posloupnost dvojic (C0,Bo>, ■ ■ ■ (Cn,Bn) taková, že C = Cn+i a ■ Co a každá Bí jsou prvky S nebo některé Cj, j < í ■ každá Cí+i, í < n je rezolventa C; a Bí ■ Lineární vstupní (Linear ínput) rezoluce (Ll-rezoluce) C z P u {G} posloupnost dvojic (Co,Bo), ■ ■ ■ (Cn,Bn) taková, že C = Cn+\ a ■ Co = G a každá K, jsou prvky P lineární rezoluce + vstupní rezoluce ■ každá Cf+i, i < n je rezolventa Q a Bi Hana Rudová, Logické programování I, 17. května 2007 129 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 (-iGi v ■ ■ ■ v -iGm) ■ pokud tedy předpokládáme, že program {Pi.....Pn\ platí, tak musí být nepravdivá (-iGi v ■ ■ ■ v -iGm), tj- musí platit Gi a ■ ■ ■ a Gm Hana Rudová, Logické programování I, 17. května 2007 131 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í 1,17. května 2007 130 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, ->Bq, . . . , -ifiml_ {-*A0,-ifioP, ■ ■ ■, ^Bmp, -lAf+i,..., -iA„}cr ■ uspořádaná rezolventa: {-*Ao....."vlí-i, ->BoP....._,J?mP, ~vlí+i.....^An}a ■ p je přejmenování proměnných takové, že klauzule {Aq.....An\ a {B,Bq.....Bm}p nemají společné proměnné ■ Ap, ..., ~>An}_{B, -ij?p,..., _ ^o,..., -*Ai-i, -ifioP, ■ ■ ■, ^Bmp, -lAf+i,..., ^An}a Hornovy klauzule Příklad: _: -Ap,... ,An._B : -B0,... ,Bm._ : - (A0, ...,Ai-i,B0p,..., Bmp,Ai+i, ...,An)a. {->s(X), -.t(l), --u(X)} {ř(Z), ->q(Z,X), -.r(3)} {-.í(A-),-.q(l,A),-.r(3),-.u(A-)} : -5(jy),ř(l),M(X). ř(Z) : -q(Z,X),r(3). : -5(A'),íj(l,A),r(3),M(A'). p = [A"/A] o- = [Z/l] Hana Rudová, Logické programování I, 1 7. května 2007 1 33 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ů i? (C) e C ■ při rezoluci vybírám s 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, 17. května 2007 135 Rezoluce a logické programování 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 = Go ■ Gn+i = □ ■ Gi je uspořádaná cílová klauzule ■ Cíje přejmenování klauzule z P ■ Q neobsahuje proměnné, které jsou v Gj, j < í nebo v C^, k < í ■ Gí+i,0 < i < n je uspořádaná rezolventa Gi a Ci LD-rezoluce: korektní a úplná Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Lineární rezoluce se selekčním pravidlem P = {{p},{p,^q}Aq}}, G={^q,^p} {^q,^p} Iq} {^q,^p} fpl | y výběr | / výběr nejlevějšího literálu výběr nejpravějšího Í^I ^ literálu □ □ 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(Gí) je literál rezolvovaný v kroku i SLD-rezoluce - korektní, úplná Efektivita SLD-rezoluce je závislá na ■ selekčním pravidle R ■ 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, 17. května 2007 Rezoluce a logické programování Příklad: SLD-strom Strom výpočtu (SLD-strom) ř : -p,r. t: -s. P '■ -q, v. p : -u, w. q. s. u. (1) (2) (3) (4) (5) (6) (7) 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řeny stromyjsou programové klauzule a cílová klauzule G v uzlech jsou rezolventy výchozím kořenem rezoluce je cílová klauzule G listyjsou 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 7. května 2007 Rezoluce a logické programování Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Příklad: SLD-strom a výsledná substituce Výsledná substituce {answer substitution) : -a(Z). a(X) : -b(X,Y),c(Y). a(X) : -c(X). b(2,3). b(l,2). c(2). Cvičení: p(B) : -q(A,E),r(E). p(A) : -q(A,A). q(a, a). q(a, b). r(b). a(Z). (1) (2) (3) (4) (5) (1) \(2) b(Z,Y), c(Y). :- c(Z). [Z/2.Y/3] (3)/ \í4) [Z/1 ,Y/2] \ (5) [Z/2] c(3). - c(2). (5) □ [Z/2] fail □ ÍZ/11 ve výsledné substituci jsou pouze proměnné z dotazu výsledné substituce jsou [Z/l] a [Z/2] nezajímá mě substituce [Y12] q(a). p(a,b). .-q(X), p(X,Y). X=a, Y=b q(X),p(XJ). 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 0í => potenciální instanciace proměnné ve vstupní cílové klauzuli Výsledná substituce (answer substitution) 9 = 9q9i ■ ■ ■ 0n složení unifikací Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Význam SLD-rezolučního vyvrácení P u {G} Výpočetní strategie Množina P programových klauzulí, cílová klauzule G Dokazujeme nesplnitelnost (1) P a (VX)^Gi(X) v ^Gz(X) v ■ ■ ■ v -.G„(*)) kde G = {->G\, ~ neúplnost použité výpočetní strategie Implementace SLD-rezoluce v Prologu ■ není úplná logický program: q : -r. (1) r:-q. (2) q. (3) dotaz: : -q. 7 q. (3) □ Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování 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, 17. května 2007 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)). ■ vede k: [B/X], [X/f(X)] Unifikátor pro g(Xi,... ,Xn) a 0(/(*o,*o),/(*i,*i), ■ ■ ■ ,/(*n-i,*n-i)) Xi=f(Xo,Xo), Xz = f(Xi,X\),..., Xn = f(Xn-i,Xn-i) X2 = f(f(X0,Xo),f(X0,Xo)),... délka termu pro Xt 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: ? -X = f(X) uspěje s X = /(/(/(/(/(/(/(/(/(/(...)))))))))) Hana Rudová, Logické programování I, 17. května 2007 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). P(XJ(X)). (2) t:-p(X,X). P(XJ(X)). : -t(X). X = /(/(/(/(...)))))))))) problém se projeví 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ě) ř : -p(X,X). P(XJ(X)):-X = X. ■ optimalizace v kompilátoru mohou způsobit opět odpověď „yes" Hana Rudová, Logické programování I, 17. května 2007 Rezoluce a logické programování Příklad: řez ř : -p,r. t: -s. p : -q(X),\,v. p : -u, w. q(a). q(b). s. u. (D (2) (3) (4) (5) (6) (7) (8) (1)/ \^) - p, r. [X/a] q(X),!,v,r. a (5) "\ !,v,r. (!) v, r. fail Hana Rudová, Logické programování I, 1 7. května 2007 Rezoluce a logické programování Řízení implementace: řez nemá ale žádnou deklarativní sémantiku místo toho mění implementaci programu p : -q,!, v. ře^l^ňfeWÍřÚV^hovája ko kterýkoliv jiný literál 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, 17. května 2007 146 Rezoluce a logické programování a(X) : -b(X,Y),\,c(Y). a(X) : -c(X). fc(2,3). fc(l,2). c(2). s(X) : -a(X). s(X) : -p(X). p(B) : -q(A,E),r(E). p (A) : -q(A,A). q(a, a). q(a, b). Příklad: řez II (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) r(b). (12) Hana Rudová, Logické programování I, 17. května 2007 [X/2.Y/3] (3) (rez) !,c(3). c(3). fail Rezoluce a logické programování Příklad: řez a(X):-b(X,Y),c(Y),\. (1) a(X) : -c(X). (2) b(2,3). (3) b(l,2). (4) c(2). (5) í(A-) : -a(X). (6) í(A-) :-p(A-). (7) p(E) :-q(A,E),r(E). (8) p(A) (9) q(a,a). (10) a zobrazením, které přiřadí konstantě c prvek T>, funkčnímu symbolu f In n-ární operaci v D a predikátovému symbolu pln n-ární relaci. ■ příklad: F = {{f(a,b)=f(b,a)}, {f(f(a,a),b) = a}} interpretace 'h: D = Z,a:= l,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í 1,17. května 2007 151 Sémantiky Hana Rudová, Logické programování 1,17. května 2007 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(ti, ■■■,(„) ■ 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 P je v ní pravdivá. Hana Rudová, Logické programování I, 1 7. května 2007 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) 21 = 0 22 = {líchy(s(0))} 13 = {Uchy (5(0)), líchy (s(s(s(Q))))} 24 = {líchy (sn(Q))\n e {1,3,5,7,...}} 25 = {líchy(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, 17. května 2007 Příklad: Herbrandovy interpretace rodič(a,b). rodi c(b,c). predek(X,Y) :- rodic(X,Y). predek(X,Z) :- rodic(X,Y), predek(Y,Z). 1\ = {rodícia, b),rodíc(b, c), predekia, b), predekib, c), predekia, c)} I2 = {rodíc(a,b),rodíc(b,c), predekia, b), predekib, c), predekia, c), predekia, a)} 1\ i ?2 jsou Herbrandovy modely klauzulí 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). ■ 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 g1 odvodit nějakým rezolučním důkazem ze vstupní množiny P u {Cj}. ^í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, 17. května 2007 1 5 5 Sémantiky Hana Rudová, Logické programování I, 17. května 2007 Negativní znalost Negace v logickém programování 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). ■ nej menší 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 Předpoklad uzavřeného světa neexistence informace chápána jako opak: předpoklad uzavřeného světa (dosed world assumption, CWA) převzato z databází určitý vztah platí pouze když je vyvoditelný z programu. P if A „odvozovací pravidlo" (A je (uzavřený) term): ->A (CWA) pro SLD-rezoluci: P ý= nad(a, c), tedy lze podle CWA odvodit - 0, t\,..., tn jsou termy a L\,... ,Lm jsou literály. Pak označme E(C) výraz 3Yi,Yu(X\ = t\,... ,Xn = tn,L\,... ,Lm) kde Y\,..., ľk jsou všechny proměnné v C. Nechť def(q/n) = {Ci,...,C„}. Pak formuli l¥(q,P) získáme následujícím postupem: q(X1,...,Xn) : -E(Ci) VE(C2) v ■ ■ ■ v E(C,) pro j > 0a q(X\,... ,Xn) : - □ pro j = 0 [q/n není v programu P Hana Rudová, Logické programování 1,17. května 2007 163 Negace v logickém programování Clarkova Teorie Rovnosti (CET) všechny formule jsou univerzálně kvantifikovány: 1. X = X 2. X=Y^Y = X 3. X=YaY = Z^X = Z 4. pro každý f/m: Xi = Yi a ■ ■ ■ a Xm = Ym - f(Xu ..., Xm) = f(Ylt..., Ym) 5. pro každý p/m: Xx = Yx a ■ ■ ■ a Xm = Ym - (p(Xu ..., Xm) - p(Yu... ,Ym)) 6. pro všechny různé f/m a g/n, (m, n > 0): f(X\,... ,Xm) ± g(Y\,..., Yn) 7. pro každý f/m: f(X1,...,Xm) = f(Y1,...,Ym) —► X\ = Y\ /\ ■ ■ ■ /\ Xm = Ym 8. pro každý term ř obsahující X jako vlastní podterm: ř ^ X X ± Y je zkrácený zápis -<(X = Y) Hana Rudová, Logické programování I, 17. května 2007 164 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(-iA) je logickým důsledkem comp(P) (nebo-li comp(P) i= V(-iA)) Úplnost NF pravidla: Nechť P je logický program. Jestliže comp(P) i= V(-iA), 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) i= V(-vi)) je A všeob. kvantifikováno, v V(-vl) nejsou volné proměnné Hana Rudová, Logické programování I, 17. května 2007 Negace v logickém programování St ratifikované 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 :-~p. zúplnění: p «- -ip rozdělení programu na vrstvy ■ vynucují použití negace relace pouze tehdy pokud je relace úplně definovaná a. a: --li?, a. b. a. a: --ib, a. b : --ifl. stratifikovaný není stratifikovaný normální program P je stratifikovaný: množina predikátových symbolů programu lze rozdělit do disjunktních množin So,...,Sm (Si = stratům) ■ p(...):-..., q(...),... e P, p e Sk => q e S0 u ... u Sk ■ p(...):-..., -. q e S0 u ... u Sk-i Hana Rudová, Logické programování I, 17. května 2007 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 existuje vyvrácení C s prázdnou substitucí (strom pro C je konečně úspěšný), pak je odvození G (i -,(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é: Gi = □ 2. neúspěšné 3. blokované: Gj je negativní (např. - -iA tedy sice platí, ale SLDNF rezoluce ho nedokáže odvodit Typy SLDNF odvození Konečné SLDNF-odvození může být: 1. úspěšné: Gi = □ 2. neúspěšné 3. uvázlé (flounder): Gj je negativní (^A) a : -A je úspěšné s neprázdnou cílovou substitucí 4. blokované: Gj je negativní (^A) a : -A nemá konečnou úroveň. Hana Rudová, Logické programování 1,17. května 2007 1 74 Negace v logickém programování Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP Hana Rudová, Logické programování I, 17. května 2007 175 Negace v logickém programování CP: elektronické materiály Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ http://www.ics.uci.edu/~dechter/ics-275a/fal 1-2001/readi ngs.html Barták R. Přednáška Omezující podmínky na MFF UK, Praha. ■ http://kti.ms.mff.cuni.cz/~bartak/podmi nky/prednaska.html SICStus Prolog User's Manual, 2004. Kapitola o CLP(FD). ■ http://www.fi.muni.cz/~hanka/sicstus/doc/html / Příklady v distribuci SICStus Prologu: cca 25 příkladů, zdrojový kód ■ ai sa:/software/sicstus-3.10.1/1ib/sicstus-3.10.1/1 i brary/clpfd/examples/ Constraint Programming Online ■ http://si ash.math.uni pd.it/cp/index.php 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 ■ http://www.fi.muni.cz/~hanka/cp ■ PA167 Rozvrhování ■ http://www.fi.muni.cz/~hanka/rozvrhováni ■ zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 17. května 2007 177 Logické programování s omezujícími podmínkami Historie a současnost 1963 interaktivní grafika (Sutherland: Sketchpad) Polovina 80. let: logické programování omezujícími podmínkami Od 1990: komerční využití Už v roce 1996: výnos řádově stovky milionů dolarů Aplikace - příklady ■ Lufthansa: krátkodobé personální plánování ■ reakce na změny při dopravě (zpoždění letadla, ...) ■ minimalizace změny v rozvrhu, minimalizace ceny ■ Nokia: automatická konfigurace sw pro mobilní telefony ■ Renault: krátkodobé plánování výroby, funkční od roku 1995 Hana Rudová, Logické programování I, 17. května 2007 179 Logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 1 7. května 2007 1 78 Logické programování s omezujícími podmínkám Omezení (constraint) ■ Dána ■ množina (doménových) proměnných Y = {y\,..., yt] ■ konečná množina hodnot (doména) D = {Di,... ,DjJ Omezení c na ľ je podmnožina D\ x ... x Dt ■ 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 y\,.. .yt je splněno, pokud pro di e D\, ... dt e Dt platí (d\,... dt) 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 7. května 2007 1 80 Logické programování s omezujícími podmínkám Problém splňování podmínek (CSP) Řešení CSP Dána ■ konečná množina proměnných X = {x\, ...,xn} ■ konečná množina hodnot (doména) D = {Di,... ,Dn} ■ konečná množina omezení C = {c\,..., 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, 17. května 2007 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í: a"l"l_distinct([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+Marie #= Cena minimalizace hodnoty proměnné Cena optimální řešení: Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Hana Rudová, Logické programování I, 1 7. května 2007 Logické programování s omezujícími podmínkami Částečné ohodnocení proměnných (d\,dk),k < n ■ některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (d\,dn) ■ všechny proměnné mají přiřazenu hodnotu Řešení CSP ■ úplné ohodnocení proměnných, které splňuje všechna omezení ■ (di,..., dn) e Di x ... x Dn je řešení (X,D, C) ■ pro každé cí e c na x^,.. .Xík platí (tií1,.. .dík) e cí Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 17. května 2007 Logické programování s omezujícími podmínkami CLPCFD) 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, 17. května 2007 Logické programování s omezujícími podmínkami Kód CLPCFD) programu Příklad: algebrogram % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], ... post_constraints( Variables ), a]]_distinct([]an,Petr,...]) labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_min(Var,Min) , % výběr nejmenší hodnoty z domény ( Var#=Min, labeling( Rest ) i Var#>Min , labeling( [Var|Rest] ) Hana Rudová, Logické programování I, 17. května 2007 185 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(JZI) generický jazyk ■ CLP(FD) domény proměnných jsou konečné (Finite Domains) ■ CLP(K) 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), a]]_distinct([A, B,C]) Hana Rudová, Logické programování I, 17. května 2007 187 Logické programování s omezujícími podmínkami ■ 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 7. května 2007 1 86 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 i n 0. . 2 , B i n 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 in 1..2, B in 0..1, B# #= I #\= I #< I #=< I #> I #>= ■ A + B #=< 3, A #\= (C - 4) * C D - 5) , A/2 #= 4 sum(Variables,RelOp,Suma) ■ domain([A,B,C,F],1,3) , sum([A,B,C],#= ,F) sealar_product(Coeffs.Variables,RelOp,Seal arProduct) ■ domain([A,B,C,F],1,6) , scalar_product( [1,2,3],[A,B,C],#= ,F) Hana Rudová, Logické programování I, 17. května 2007 197 CLP(fD) v SICStus Prologu Příklad: reifikace Přesně N prvků v seznamu S je rovno X: exactly(X, S, N) exactlyC [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). ■ | ?- domain([A,B,C,D,E,N],1,2), exactly(1,[A,B,C,D,E],N),A#< 2,B#< 2. A = 1, B = 1, C = 2, D = 2, E = 2, N = 2 Vyzkoušejte si ■ greaters(X,S,N): presne N prvků v seznamu S je větší než X ■ atleast(X,S, N): alespoň N prvků v seznamu S je rovno X ■ atmost(X,S,N): nejvýše N prvků v seznamu S je rovno X Hana Rudová, Logické programování 1,17. května 2007 199 CLP(f d) v SICStus Prologu ■ Výroková omezení pozor na efektivitu ■ \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence,... ■ X #> 4 #/\ Y #< 6 ■ za předpokladu A in 1..4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je príliš slabá (propagační algoritmy príliš obecné) ■ Reifikace pozor na efektivitu ■ Constraint #<=> Bool Bool in 0.. 1 v závislosti na tom, zda je Constrai nt splněn ■ príklad: A in 1..10 #<=> Bool ■ za předpokladu X in 3.. 10, Y in 1..4, Bool in 0..1 porovnej rozdíl mezi X# Bool X = 3, Y = 4 X in 3..1 0, Y in 1 ..4, Bool in 0..1 Hana Rudová, Logické programování I, 17. května 2007 198 CLP(fD) v SICStus Prologu Základní kombinatorická omezení ■ element(N,List,X) ■ omezení na konkrétní prvek seznamu ■ all_distinct(List) ■ všechny proměnné různé ■ seri ali zed(Starts,Du rati ons) ■ disjunktivní rozvrhování ■ disjoint2(Rectangles) ■ nepřekrývání obdélníků ■ cumulative(Starts,Durations,Resources,Limit) ■ kumulativní rozvrhování Hana Rudová, Logické programování 1,17. května 2007 200 CLP(f d) v SICStus Prologu Výskyty prvků v seznamu Všechny proměnné různé element(N,List,X) ■ N-tý prvek v seznamu Li st je roven X ■ | ?- A in 2..10, B in 1..3, element( N, [A,B], X ), X#< 2. B=l,N = 2,X=l,Ain 2..10 a"l"l_di sti nct (Vari abl es), a"l"l_di f f e rent (Vari abl es) Proměnné v seznamu Variables jsou různé a"l"l_distinct a a "l"l_di fferent se liší úrovní propagace ■ a"l"l_distinct má úplnou propagaci ■ a"l"l_different má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny ■ all_di sti nct([Jan,Petr,Anna,Ota,Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 ■ all_differentC[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 učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Hana Rudová, Logické programování I, 17. května 2007 CLP(fD>vSICStus Prologu Disjunktivní rozvrhování seri a Ji zed(Starts,Du rati ons) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Du rati ons) tak, aby se nepřekrývaly ■ příklad s konstantami: serialized([0,3,5],[2,l ,1]) 3 1 I 1 2 3 4 5 6 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná ■ D in 1..2, C = 3, seriál ized([Jan,Petr,Anna,Ota,Eva,Marie], [D,D,D,C,C,C]) Hana Rudová, Logické programování I, 17. května 2007 CLP(fD)vSICStus Prologu Hana Rudová, Logické programování I, 17. května 2007 CLP(fD)vSICStus Prologu Nepřekrývání obdélníků di sjoi nt2(Rectangles) disjoint2( [Name(X, Délka, Y, Vyska) di sjoi ntl(Li nes) ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Delka,Vyska mohou být z oboru celých čísel ■ příklad s konstantami: disjoint2([rect(0,3,0,l),rect(l,3,1,2),rect(4,2,2,-2)]) l 1 2 3 4 5 6 ■ příklad: vytvoření rozvrhu za předpokladu, že učitelé učí v různých místnostech D in 1..2, C = 3, disjoint2( class(Jan,D,Ml,l), class(Petr,D,M2,1), class(Petr,D,M3,1), ...] Hana Rudová, Logické programování I, 17. května 2007 204 CLP(fD) v SICStus Prologu Kumulativní rozvrhování Příklad: kumulativní rozvrhování cumulative(Starts,Durations,Resources,Limit) Úlohyjsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit Příklad s konstantami: cumulative([0,l ,3],[4,2,3],[1,2,2],3) 3 Hana Rudová, Logické programování I, 17. května 2007 CLP(fD>vSICStus Prologu Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( 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 ? TabelingC [] ). TabelingC [Var|Rest] ) indomain C Var ), TabelingC Rest ). % výběr nejlevější proměnné k instanciaci % výběr hodnot ve vzrůstajícím pořadí labeling( Options, Variables ) ?- A in 0..2, B in 0..2, B#< A, labeling([], [A, B]). Hana Rudová, Logické programování I, 17. května 2007 207 CLP(fD)vSICStus Prologu 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 18, 4], 1, 11], % koncový čas schedulers, End) :-TengthCSs, 7), Ds = [16, 6, 13, 7, 5, Rs = [2, 9, 3, 7, 10, domainCSs, 0, 51), domain C [End] , 0, 69), afterCSs, Ds, End), cumulative(Ss, Ds, Rs, 13), appendCSs, [End], Vars), ]abe]ing([minimize(End)], Vars). after([], [], _) . after([S|Ss], [D|Ds], E) :- E #>= S+D, afterCSs, Ds, E) . I ?- schedulers, End). Ss = Ss = [0,16,9,9,4,4,0], End = 22 ? Hana Rudová, Logické programování I, 17. května 2007 CLP(fD>vSICStus 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 labelingC [] ). labelingC Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), C Var #= Value, labelingC Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labelingC Variables ) % proto pokračujeme se všemi proměnnými včetně Var ). 1 Statické uspořádání: určeno už před prohledáváním 1 Dynamické uspořádání: počítá se během prohledávání Hana Rudová, Logické programování 1,17. května 2007 208 CLP(f d) v SICStus Prologu Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed prst) ■ 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 Tabel 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 labeling/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 indomain/1 ■ bisect: volba mezi X #=< Mid, X #> Mi d ■ vjednom kroku labelingu nedochází nutně k instanciaci proměnné Hana Rudová, Logické programování 1,17. května 2007 209 CLP(f d) v SICStus Prologu Hledání optimálního řešení (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: minimize(F)/maximize(F) ■ Cena #= A+B+C, labeling([minimize(Cena)] , [A,B,C]) Metoda větví a mezí (branch&bound) ■ 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 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: nej levější (default) ■ ff: s (a) nejmenší velikostí domény fd_size(Var,Size) (b) nejlevější z nich ■ ffc: s (a) nejmenší velikostí domény (b) největším množstvím omezením „čekajících" na proměnné fd_degree(Var,Size) (c) nejlevější z nich ■ min/max: s (a) nejmenší/největší hodnotou v doméně proměnné (b) nejlevnějšíz nich fd_min(Var,Min)/fd_max(Var,Max) Hana Rudová, Logické programování 1,17. května 2007 210 CLP(f d) v SICStus Prologu Algoritmy pro řešení problému splňování podmínek (CSP) Hana Rudová, Logické programování I, 17. května 2007 CLP(fD) v SICStus Prologu Grafová reprezentace CSP Reprezentace podmínek ■ intenzionální (matematická/logická formule) ■ extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek ■ vrchol = proměnná, hyperhrana = podmínka Hana Rudová, Logické programování I, 17. května 2007 213 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: a"l"l_different vs. množina binárních nerovností Hana Rudová, Logické programování 1,17. května 2007 214 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 (Vj, V,) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y tak, že ohodnocení [Ví = x, V, = y] splňuje všechny binární podmínky nad Vu V,. ■ hranová konzistence je směrová ■ konzistence hrany (Ví, Vj) nezaručuje konzistenci hrany (Vj,Ví) » l„ I 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 NE NE Hana Rudová, Logické programování I, 17. května 2007 Algoritmy pro CSP Řešení nebinárních podmínek S n-árními podmínkami se pracuje přímo Podmínka je obecně hranově konzistentní (CAC), právě když pro každou proměnnou Ví z této podmínky a každou hodnou xeD; existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí ■A + B = C, A in 1..3, B in 2..4, C in 3..7je obecně hranově konzistentní Využívá se sémantika podmínek ■ speciální typy konzistence pro globální omezení ■ viz all_distinct ■ konzistence mezí ■ propagace pouze při změně nejmenší a největší hodnoty v doméně proměnné Pro různé podmínky lze použít různý druh konzistence ■ A# B=> min(A) = min(B)+l, max(B) = max(A)-l ■ příklad: A in 4. . 10, B in 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, 17. května 2007 220 Algoritmy pro CSP Konzistence mezí a aritmetická omezení Globální podmínky 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 min (A) vyvolá pouze změnu min (B) amin(C) ■ změna max(A)vyvolá pouze změnu max(B) amax(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 ■ 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: ■ all_different omezení: hodnoty všech proměnných různé ■ serialized 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, 17. května 2007 Algoritmy pro CSP Propagace pro all_ch"stinet 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{Di u ■ ■ ■ u Dk} > k stačí hledat Hallův interval J: velikost intervalu / je rovna počtu proměnných, jejichž doména je v J Inferenční pravidlo ■ U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ uDk] • card(U) = card(dom(U)) ^Vve dom(U), VX e (V - U),X ± v ■ hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: 0(2") - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hraničních bodů Hallových intervalů (1 998) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Hana Rudová, Logické programování I, 17. května 2007 Algoritmy pro CSP Hana Rudová, Logické programování I, 17. května 2007 Algoritmy pro CSP 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í I, 17. května 2007 224 Algoritmy pro CSP Prohledávání s navracením Přehled algoritmů Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky 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, 17. května 2007 Algoritmy pro CSP Základní algoritmus prohledávání s navracením ■ Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí ■ Na začátku voláno jako 1 abel i ng (C, 1) procedure labeling(G,a) if a > |uzly(G)| then return uzly(G) for V x e Da do if consistent(G.a) then % consistentCG,a) je nahrazeno FC, LA, ... R := labeling(G,a + 1) if R 4= 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, 17. května 2007 Algoritmy pro CSP BT Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Vfl),...,c(Vfl-i,Vfl) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky \^ c(V«,V«+i),...,c(Vfl,V„) z aktuální proměnné do budoucích proměnných Pohled dopředu (LA) kontroluje v kroku a podmínky ^ /I Vi(a < i < n), Vfe(a a] % přidání hran z aktuální proměnné do budoucích prom. Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((V(;, Vm)) then Consistent := (|Djt|>0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC ■ Hrany z aktuální proměnné do minulých proměnných není nutno testovat Hana Rudová, Logické programování I, 17. května 2007 230 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) ■ LA je rozšíření FC, LA zajišťuje hranovou konzistenci ■ LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými ■ procedure LA(C,íi) Q := {(Vi,Va) e hrany(G), í > a] % začináme s hranami do a Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((VJt, Vm)) then Q := Q u {(V;, Vit) I (V;, Vit) e hrany(G), í + k, í + m, í > a] Consistent := (\Dk\ > 0) return Consistent end LA ■ Hrany z aktuální proměnné do minulých proměnných opět netestujeme Hana Rudová, Logické programování I, 17. května 2007 231 Algoritmy pro CSP Hana Rudová, Logické programování I, 17. května 2007 232 Algoritmy pro CSP Příklad: pohled dopředu Omezení: V1.V2.V3 in 1...4, Vx# > V2, V2# = 3 x V3 Stavový prostor: Implementace Prologu Literatura: Matýska L., Toman D.: Implementační techniky Prologu , Informační systémy, (1 990),21-59.http://www.ics.muni.cz/people/matyska/vyuka/lp/lp.hl Ó Hana Rudová, Logické programování I, 17. května 2007 233 Algoritmy pro CSP Opakování: základní 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 a n termy na místě argumentů Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programováni I, 17. května 2007 23 5 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li 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áni I, 17. května 2007 236 Implementace Prologu Abstraktní interpret Abstraktní interpret - pokračování Vstup: Logický program P a dotaz C. 1. Inicializuj množinu cílů S literály z dotazu C; S:=C 2. while ( S != empty ) do 3. Vyber AeS a dále vyber klauzuli A' : -Bi , . . . ,B„ (n > 0) z programu P takovou, že 3cr : Aer = A' cr; rj je nejobecnější unifikátor. Pokud neexistuje A' nebo cr, ukonči cyklus. 4. Nahraď A v S cíli Bi až B„. 5. Aplikuj (r na C a S. 6. end while 7. Pokud S==empty, pak výpočet úspešne skončil a výstupem je C se všemi aplikovanými substitucemi. Pokud S!=empty, výpočet končí neúspěchem. Hana Rudová, Logické programování I, 17. května 2007 Implementace Prologu Nedeterminismus interpetu 1. Selekční pravidlo: výběr cíle A z množiny cílů S ■ neovlivňuje výrazně výsledek chování interpretu 2. Způsob prohledávání stromu výpočtu: výběr klauzule A' z programu P ■ je velmi důležitý, všechny klauzule totiž nevedou k úspěšnému řešení Vztah k úplnosti: 1. Selekční pravidlo neovlivňuje úplnost ■ možno zvolit libovolné v rámci SLD rezoluce 2. Prohledávání stromu výpočtu do šířky nebo do hloubky „Prozření" - automatický výběr správné klauzule ■ vlastnost abstraktního interpretu, kterou ale reálné interprety nemají Hana Rudová, Logické programování I, 17. května 2007 Implementace Prologu Kroky (3) až (5) představují redukci (logickou inferenci) cíle A. Počet redukcí za sekundu (LIPS) == indikátor výkonu implementace Věta Existuje-li instance C dotazu C, odvoditelná z programu P v konečném počtu kroků, pak bude tímto interpretem nalezena. Hana Rudová, Logické programování I, 17. května 2007 Implementace Prologu Prohledávání do šířky 1. Vybereme všechny klauzule Ar, které je možno unifikovat s literálem A ■ nechť je těchto klauzulí q 2. Vytvoříme q kopií množiny S 3. V každé kopii redukujeme A jednou z klauzulí Ar. ■ aplikujeme příslušný nejobecnější unifikátor 4. V následujících krocích redukujeme všechny množiny Sí současně. 5. Výpočet ukončíme úspěchem, pokud se alespoň jedna z množin Sí stane prázdnou. ■ Ekvivalence s abstraktnímu interpretem ■ pokud jeden interpret neuspěje, pak neuspěje i druhý ■ pokud jeden interpret uspěje, pak uspěje i druhý Hana Rudová, Logické programování I, 17. května 2007 Implementace Prologu Prohledávání do hloubky 1. Vybereme všechny klauzule A' i, které je možno unifikovat s literálem A. 2. Všechny tyto klauzule zapíšeme na zásobník. 3. Redukci provedeme s klauzulí na vrcholu zásobníku. 4. Pokud v nějakém kroku nenajdeme vhodnou klauzuli A', vrátíme se k předchozímu stavu (tedy anulujeme aplikace posledního unifikátoru cr) a vybereme ze zásobníku další klauzuli. 5. Pokud je zásobník prázdný, končí výpočet neúspěchem. 6. Pokud naopak zredukujeme všechny literály v S, výpočet končí úspěchem. ■ Není úplné, tj. nemusí najít všechna řešení ■ Nižší paměťová náročnost než prohledávání do šířky ■ Používá se v Prologu Hana Rudová, Logické programování I, 17. května 2007 241 Implementace Prologu Reprezentace objektů ■ Beztypový jazyk ■ Kontrola „typů" za běhu výpočtu ■ Informace o struktuře součástí objektu Typy objektů ■ Primitivní objekty: ■ konstanta ■ číslo ■ volná proměnná ■ odkaz (reference) ■ Složené (strukturované) objekty: ■ struktura ■ seznam Hana Rudová, Logické programování I, 17. května 2007 242 Implementace Prologu Reprezentace objektů II Příznaky (tags): Objekt Příznak volná proměnná FREE konstanta CONST celé číslo INT odkaz REF složený term FUNCT Obsah adresovatelného slova: hodnota a příznak. Primitivní objekty uloženy přímo ve slově Složené objekty ■ jsou instance termu ve zdrojovém textu, tzv. zdrojového termu ■ zdrojový term bez proměnných => 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, 17. května 2007 Implementace Prologu Příklad: a(b(X),c(X,Y),d), Kopírování struktur FUNCT a/3 REF REF CONST d FUNCT c/2 REF FREE Y FUNCT b/1 FREE X Hana Rudová, Logické programování I, 17. května 2007 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 najeho hodnotu) ■ ■ A+l slovo nese hodnotu A-tého argumentu Reprezentace vychází z orientovaných acyklických grafů: a/3 c/2 b/1 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, 17. května 2007 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 i-tou proměnnou. Implementace: < &kostra_termu; &rámec > (& vrací adresu objektu) Všechny instance sdílí společnou kostru_termu => sdílení struktur 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 ■ i-tá položka nese hodnotu i-té proměnné v původním termu Hana Rudová, Logické programování I, 17. května 2007 246 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ů: kostra_a M:d kostra_b ^ kostra_c X —i Hana Rudová, Logické programování I, 17. května 2007 247 Implementace Prologu Hana Rudová, Logické programování I, 17. května 2007 248 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, 17. května 2007 249 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 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, 17. května 2007 2 50 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, 17. května 2007 251 Implementace Prologu Hana Rudová, Logické programování I, 17. května 2007 252 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, 17. května 2007 253 Implementace Prologu Řez Prostředek pro ovlivnění běhu výpočtu programátorem ■ a(X) :- b(X), !, c(X). a(3). b(l). b(2). c(l). c(2). Řez: 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, 17. května 2007 255 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, 17. května 2007 2 54 Implementace Prologu Warrenův abstraktní počítač, WAM I. 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 (modifikovatelný) 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. ba\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, 17. května 2007 2 56 Implementace Prologu Rozmístění datových oblastí Příklad konfigurace Halda > i Stopa i Zásobník ' PDL i 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, 17. května 2007 257 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ů ■ obecná unifikace pouze při get_va"lue 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_va"lue a unify_1oca"l_va"lue 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, 17. května 2007 259 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é: Yl, Y2, . . . ■ abstraktní znázornění lok. proměnných na zásobníku Hana Rudová, Logické programování I, 17. května 2007 2 58 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_va"lue A2.A5 put_va"lue A3.A6 put_va"lue A4.A7 execute b/4 Hana Rudová, Logické programování I, 17. května 2007 260 Implementace Prologu Instrukce WAMu WAM - indexace get instrukce put instrukce unify instrukce get_var Ai,Y put_var Ai ,Y unify_var Y get_value Ai ,Y put_value Ai ,Y unify_value Y get_const Ai,C put_unsafe_value Ai,Y unify_local_value Y get_nil Ai put_const Ai ,C unify_const C get_struct Ai,F/N put_ni1 Ai u n i fy_n i1 get_list Ai put_struct Ai,F/N unify_void N put_li St Ai instrukce řízení indexační instrukce allocate try_me_else Next try Next deallocate retry_me_else Next retry Next call Proc/N,A trust_me_else fail trust fail execute Proc/N proceed 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, 17. května 2007 261 Implementace Prologu ■ Provázání klauzulí: instrukce XX_me_el se: ■ první klauzule: try_me_else; založí bod volby ■ poslední klauzule: trust_me_else; 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 ■ switch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura) Hana Rudová, Logické programování I, 17. května 2007 262 Implementace Prologu Příklad indexace instrukcí Proceduře a(atom) :- bodyl. a(l) :- body2. a(2) :- body3. odpovídají instrukce aCĽXIY]) aCĽXIY]) aCs(N)) : a(fCN)) : - body4. - body5. body6. bodyľ. a: switch_on_term LI, L2, L3, L4 L5a: body2 L2: switch_on_const atom :Lla L6: retry. _me_ _el se L7 1 :L5a L6a: body3 2 :L6a L7: retry. _me_ _el se L8 L3: try L7a L7a: body4 trust L8a L8: retry. _me_ _el se L9 L4: switch_on_struct s/l :L9a L8a: body5 f/1 :L10a L9: retry. _me_ _el se L10 LI: try_me_else L5 L9a: body6 Lla: bodyl L10: trust. _me_ _el se fail L5: retry_me_else L6 LlOa bodyľ Hana Rudová, Logické programování 1, 17. května 2007 263 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) deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) cal 1 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 Implementace Prologu Hana Rudová, Logické programování I, 17. května 2007 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 1oad_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 1oad_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; 1oad_cut Y2; put Yl.Al; execute c/1 get_const AI,2; cut_last; put A2.A1; execute c/1 execute d/2 Hana Rudová, Logické programování I, 17. května 2007 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 | get_var A3.A4 get_var A2.A6 | get_var A2.A3 get_var A3.A7 | 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, 17. května 2007 266 Implementace Prologu