Úvod do Prologu Prolog -• PROgramming in LOGic M část predikátové logiky prvního řádu -• Deklarativní programování M specifikacní jazyk, jasná sémantika, nevhodné pro procedurální postupy M Co dělat namísto Jak dělat -• Základní mechanismy -• unifikace, stromové datové struktury, automatický backtracking Hana Rudová, Logické programování I, 1 7. února 2009 2 Úvod do Prologu Prolog: historie a současnost -• Rozvoj začíná po roce 1 970 3 Robert Kowalski - teoretické základy 3 Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace -• pozdější rozšíření Prologu o logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 1 7. února 2009 3 Úvod do Prologu Prolog: historie a současnost -• Rozvoj začíná po roce 1 970 3 Robert Kowalski - teoretické základy 3 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 M zavedené aplikační oblasti, nutnost přidání inteligence Jt hypotéky; pediatrický sw; konfigurace a pravidla pro stanovení ceny objednávky; testovací nástroje, modelové testování; ... M 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? 3* 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. února 2009 3 Úvod do Prologu Program = fakta + pravidla 3 (Prologovský) program je seznam programových klauzulí 3 programové klauzule: fakt, pravidlo -• Fakt: deklaruje vždy pravdivé věci 3 clovek( novak, 18, student ). M Pravidlo: deklaruje věci, jejichž pravdivost závisí na daných podmínkách 3 studujeC X ) :- clovek( X, _Vek, student ). 3 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 3 pracujeC X ) :- clovek( X, _Vek, CoDela ), prace( CoDela ). Hana Rudová, Logické programování I, 1 7. února 2009 4 Úvod do Prologu Program = fakta + pravidla 3 (Prologovský) program je seznam programových klauzulí M programové klauzule: fakt, pravidlo -• Fakt: deklaruje vždy pravdivé věci 3 clovek( novak, 18, student ). M Pravidlo: deklaruje věci, jejichž pravdivost závisí na daných podmínkách 3 studujeC X ) :- clovek( X, _Vek, student ). M 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 3 pracujeC X ) :- clovek( X, _Vek, CoDela ), prace( CoDela ). -• Predikát: množina pravidel a faktů se stejným funktorem a aritou 3 značíme: clovek/3, student/l; analogie procedury v procedurálních jazycích, Hana Rudová, Logické programování I, 17. února 2009 4 Ú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é 3* X, Y ... začínají velkým písmenem -i* _, _A, _B ... začínají podtržítkem (nezajímá nás vracená hodnota) -• Psaní komentářů clovek( novak, 18, student ). % komentář na konci řádku clovek( novotny, 30, učitel ). /* komentář */ Hana Rudová, Logické programování I, 1 7. února 2009 5 Úvod do Prologu 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 M positivní - dotaz je splnitelný a uspěl 3 negativní - dotaz je nesplnitelný a neuspěl Hana Rudová, Logické programování I, 1 7. února 2009 6 Úvod do Prologu 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 M positivní - dotaz je splnitelný a uspěl M negativní - dotaz je nesplnitelný a neuspěl 3 Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty) M ?- clovekC novak, 18, Prace ). -• výsledkem dotazu je instanciace proměnných v dotazu 3 dosud nenainstanciovaná proměnná: volná proměnná Hana Rudová, Logické programování I, 17. února 2009 6 Úvod do Prologu 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 M positivní - dotaz je splnitelný a uspěl M negativní - dotaz je nesplnitelný a neuspěl 3 Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty) M ?- clovekC novak, 18, Prace ). M výsledkem dotazu je instanciace proměnných v dotazu 3 dosud nenainstanciovaná proměnná: volná proměnná -• Prolog umí generovat více odpovědí pokud existují ?- clovek( novak, Vek, Prace ). % všechna řešení přes ";" Hana Rudová, Logické programování I, 17. února 2009 6 Úvod do Prologu Klauzule = fakt, pravidlo, dotaz -• Klauzule se skládá z hlavy a těla -• Tělo je seznam cílů oddělených čárkami, čárka = konjunkce -• Fakt: pouze hlava, prázdné tělo -• rodic( pavla, robert ). -• Pravidlo: hlava i tělo -• upracovany_clovek( X ) :- clovek( X, _Vek, Prace ), prace( Prace, tezka ). M Dotaz: prázdná hlava, pouze tělo -• ?- clovek( novak, Vek, Prace ). ?- rodicC pavla, Ditě ), rodic( Ditě, Vnuk ). Hana Rudová, Logické programování I, 1 7. února 2009 7 Úvod do Prologu Rekurzivní pravidla predekC X, Z ) :- rodic( X, Z ). % (1) predekC X, Z ) :- rodic( X, Y ), % (2) rodicC Y, Z ). Hana Rudová, Logické programování I, 17. února 2009 8 Úvod do Prologu Rekurz predekC X, Z ) :- rodic( X, Z ). predekC X, Z ) :- rodic( X, Y ), rodicC Y, Z ). predekC X, Z ) :- rodicC X, Y ), predekC Y, Z). Hana Rudová, Logické programování I, 1 7. února 2009 pravidla % CD % (2) % C2') Příklad: rodokmen rodi rodi rodi rodi rodi c( pavla, robert ). c( tomas, robert ). c( tomas, eliska ). 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. února 2009 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas,robert) rodi rodi rodi rodi rodi c( pavla, robert ). c( tomas, robert ). c( tomas, eliska ). c( robert, anna ). c( robert, petr ). rodic( petr, jirka ). predek(tomas, robert) yes dle (1) Y rodic(tomas,robert) predek( X, Z ) :- rodic( X, Z ). predek( X, Z ) :- rodic( X, Y ), predek( Y, Z ). % (D % (2') Hana Rudová, Logické programování I, 1 7. února 2009 10 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas, petr) predek(tomas, petr) dle (1) Y Y dle (2') no rodic( tomas, petr) rodic(tomas, Y) predek( Y, petr) rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, petr ). Y=robert Y dle rodic(tomas, robert) predek( robert, petr) predekC X, Z ) :- rodic( X, Z ). % (1) predekC X, Z ) :- rodic( X, Y ), % (2') predekC Y, Z ). Y dle (1) rodic(robert, petr) yes Hana Rudová, Logické programování I, 1 7. února 2009 1 1 Úvod do Prologu Odpověď na dotaz ?- predek(robert, Potomek) rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, anna ). rodic( robert, petr ). rodic( petr, ji rka ). predek( X, Z ) :- rodic( X, Z ). predekC X, Z ) :- rodic( X, Y ), predekC Y, Z ) predek(robert,Potomek) --> ??? Hana Rudová, Logické programování I, 1 7. února 2009 12 Úvod do Prologu Syntaxe a význam Prologovských programů Syntaxe Prologovských programu M 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ů: <-->, ====> 3 řetězce v apostrofech: 'Pavel', 'Pavel Novák' -• Celá a reálná čísla: 0, -1056, 0.35 M Proměnná M řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_" M anonymní proměnná: ma_dite(X) :- rodic( X, _ ). «i* hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodic( X, _ ) M lexikální rozsah proměnné je pouze jedna klauzule: prvni(X,X,X). prvni(X,X,_)■ Hana Rudová, Logické programování I, 1 7. února 2009 1 4 Syntaxe a význam Prologovských programů Termy M Term - datové objekty v Prologu: datum( 1, kveten, 2003 ) M funktor: datum 3 argumenty: 1, kveten, 2003 3 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 3 trojuhelnikje hlavní funktor v trojuhelnikC bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 1 7. února 2009 15 Syntaxe a význam Prologovských programů Unifikace -• Termy jsou unifikovatelné, jestliže M jsou identické nebo M proměnné v obou termech mohou být instanciovany tak, že termyjsou po substituci identické M datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl =1, Ml = M2, Y2 = 2003 Hana Rudová, Logické programování I, 1 7. února 2009 16 Syntaxe a význam Prologovských programů Unifikace -• Termy jsou unifikovatelné, jestliže M jsou identické nebo M proměnné v obou termech mohou být instanciovany tak, že termyjsou po substituci identické M datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl =1, Ml = M2, Y2 = 2003 -• Nejobecnější unifikátor (most general unifier (MGU) M jiné instanciace? ...Dl = 1, Ml = 5, Y2 = 2003 ^ ?- datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml. Hana Rudová, Logické programování I, 1 7. února 2009 16 Syntaxe a význam Prologovských programů Unifikace -• Termy jsou unifikovatelné, jestliže M jsou identické nebo M proměnné v obou termech mohou být instanciovany tak, že termyjsou po substituci identické M datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl =1, Ml = M2, Y2 = 2003 -• Nejobecnější unifikátor (most general unifier (MGU) M 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, 1 7. února 2009 1 6 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstantyjsou identické; 2. S je proměnná a T cokolivjineho - S je instanciovana na T; Tje proměnná a S cokolivjineho - Tje instanciovana na S 3. S a T jsou termy význam mají logické relace Hana Rudová, Logické programování I, 1 7. února 2009 1 8 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů -• p :- q, r. -• Deklarativní: Co je výstupem programu? 3 p je pravdivé, jestliže q a r jsou pravdivé J Zqar plyne p => význam mají logické relace -• Procedurální: Jak vypočítáme výstup programu? -• p vyřešíme tak, že nejprve vyřešíme q a pak r => kromě logických relací je významné i pořadí cílů -• výstup ±* indikátor yes/no určující, zda byly cíle splněny instanciace proměnných v případě splnění cílů Hana Rudová, Logické programování I, 1 7. února 2009 1 8 Syntaxe a význam Prologovských programů Deklarativní význam programu Máme-li program a cíl G, pak deklarativní význam říká: cíl G 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 G a všechny cíle v těle I jsou pravdivé. Instance klauzule: proměnné v klauzuli jsou substituovány termem M ma_dite(X) :- rodic( X, Y ). % klauzule ma_dite(petr) :- rodic( petr, Z ). % instance klauzule Hana Rudová, Logické programování I, 1 7. února 2009 19 Syntaxe a význam Prologovských programů Konjunce "," vs. disjunkce ";" cílů -• Konjunce = nutné splnění všech cílů M p :- q, r. -• Disjunkce = stačí splnění libovolného cíle M p :- q; r. p :- q. p : - r. -• priorita středníku je vyšší: p :- q, r; s, t, u. p :- (q, r) ; (s, t, u). p :- q, r. p :- s, t, u. Hana Rudová, Logické programování I, 1 7. února 2009 20 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). bCl.l). Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). bCl.l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). bCl.l). Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu 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, 1) . % nenalezení odpovědi: nekonečný cyklus Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). bCl.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). bCl.l). c(2). cd). Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). bCl.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). bCl.l). c(2). cd). (d) a(X) :- c(Y), b(X,Y). % změněné pořadí cílů v těle klauzule vzhledem k (c) b(l,l). c(2). cd). Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů r^v I'll i' 'i ° Poradí klauzuli a cílu 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, 1) . % nenalezení odpovědi: nekonečný cyklus (c) a(X) :- b(X,Y), c(Y). ?- a(X). b(l,l). c(2). cd). (d) a(X) :- c(Y), b(X,Y). % změněné pořadí cílů v těle klauzule vzhledem k (c) b(l,l). c(2). c(l) . % náročnější nalezení první odpovědi než u (c) V obou případech stejný deklarativní ale odlišný procedurální význam Hana Rudová, Logické programování I, 1 7. února 2009 21 Syntaxe a význam Prologovských programů (1) a(X) :- c(Y), b(X,Y) (2) b(l,l). (3) c(2). (4) c(l). Hana Rudová, Logické programování I, 1 7. února 2009 klauzulí a cílu I. ?- a(X). a(X) dle(1) c(Y), b(X,Y) dle(3)/Y=2 dle(4KY=1 b(X,2) no b(X,1) dle (2) X=1 yes 22 Syntaxe a význam Prologovských programů (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, 1 7. února 2009 klauzulí a cílu I. ?- a(X). a(X) dle(1) c(Y), b(X,Y) dle(3)/Y=2 dle(4KY=1 b(X,2) no b(X,1) dle (2) X=1 yes 22 Syntaxe a význam Prologovských programů Operátory, aritmetika Operátory -• Infixová notace: 2*a + b*c -• Prefixová notace:+( *(2,a), *(b>,c) ) priorita +: 500, priorita *: 400 M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor Hana Rudová, Logické programování I, 1 7. února 2009 24 Operátory, aritmetika Operátory -• Infixová notace: 2*a + b*c -• Prefixová notace:+( *(2,a), *(b>,c) ) priorita +: 500, priorita *: 400 M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor -• Uživatelsky definované operátory: zna petr zna alese. zna( petr, alese). -• Definice operátoru: :- op( 600, xfx, zna ). priorita: l..l200 Hana Rudová, Logické programování I, 1 7. února 2009 24 Operátory, aritmetika Operátory -• Infixová notace: 2*a + b*c -• Prefixová notace:+( *(2,a), *(b>,c) ) priorita +: 500, priorita *: 400 M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor -• Uživatelsky definované operátory: zna petr zna alese. zna( petr, alese). -• Definice operátoru: :- op( 600, xfx, zna ). priorita: l..l200 -• :- op( 1100, xfy, ; ). nestrukturované objekty: 0 :- op( 1000, xfy, , ). p :- q, r; s, t. p :- (q, r) ; (s, t). ; má vyšší prioritu než , M :- op( 1200, xfx, :- ). :-má nejvyšší prioritu Hana Rudová, Logické programování I, 1 7. února 2009 24 Operátory, aritmetika Operátory -• Infixová notace: 2*a + b*c -• Prefixová notace:+( *(2,a), *(b>,c) ) priorita +: 500, priorita *: 400 M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor -• Uživatelsky definované operátory: zna petr zna alese. zna( petr, alese). -• Definice operátoru: :- op( 600, xfx, zna ). priorita: l..l200 -• :- op( 1100, xfy, ; ). nestrukturované objekty: 0 :- op( 1000, xfy, , ). p :- q, r; s, t. p :- (q, r) ; (s, t). ; má vyšší prioritu než , M :- op( 1200, xfx, :- ). :-má nejvyšší prioritu -• Definice operátoru není spojena s datovými manipulacemi (kromě speciálních případů) Hana Rudová, Logické programování I, 17. února 2009 24 Operátory, aritmetika Typy operátorů Typy operátorů M infixové operátory: xfx, xfy, yfx M prefixové operátory: fx, fy -• postfixové operátory: xf, yf př. xfx = yfx př. fx ?- fy v ■ * x a y určuji prioritu argumentu M x reprezentuje argument, jehož priorita musí být striktně menší než u operátoru 3 y reprezentuje argument, jehož priorita je menší nebo rovna operátoru M a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx správne priorita: 0 priorita: 0 priorita: 500 Hana Rudová, Logické programování níuFJSÄä00 25 Operátory, aritmetika Aritmetika -• Předdefinované operátory + , -, *i /, ** mocnina, // celočíselné děleni, mod zbytek po dělení M ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci J?-Xis 1+2. X = 3 „is" je speciální předdefinovaný operátor, který vynutí evaluaci Hana Rudová, Logické programování I, 1 7. února 2009 26 Operátory, aritmetika Aritmetika -• Předdefinované operátory + , -, *i /, ** mocnina, // celočíselné děleni, mod zbytek po dělení M ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci J?-Xis 1+2. X = 3 „is" je speciální předdefinovaný operátor, který vynutí evaluaci 3 porovnej: N = (1+1+1+1+1) N is (1+1+1+1+1) Hana Rudová, Logické programování I, 1 7. února 2009 26 Operátory, aritmetika Aritmetika -• Předdefinované operátory + , -, *i /, ** mocnina, // celočíselné děleni, mod zbytek po dělení M ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci J?-Xis 1+2. X = 3 „is" je speciální předdefinovaný operátor, který vynutí evaluaci 3 porovnej: N = (1+1+1+1+1) N is (1+1+1+1+1) S pravá strana musí být vyhodnotitelný výraz (bez proměnné) volání?- X is Y + 1. způsobí chybu Hana Rudová, Logické programování I, 1 7. února 2009 26 Operátory, aritmetika Aritmetika -• Předdefinované operátory + , -, *i /, ** mocnina,// celočíselné děleni, mod zbytek po dělení M ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci M ?- X is 1 + 2. X = 3 „is" je speciální předdefinovaný operátor, který vynutí evaluaci -• porovnej: N = (1+1+1+1+1) N is (1+1+1+1+1) ^ pravá strana musí být vyhodnotitelný výraz (bez proměnné) volání?- X is Y + 1. způsobí chybu -• Další speciální předdefinované operátory >, <, >=, =<, =: = aritmetická rovnost, =\= aritmetická nerovnost M porovnej: 1+2 =:= 2+1 1+2 = 2+1 Hana Rudová, Logické programování I, 1 7. února 2009 26 Operátory, aritmetika Aritmetika -• Předdefinované operátory + , -, *i /, ** mocnina,// celočíselné děleni, mod zbytek po dělení M ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci M ?- X is 1 + 2. X = 3 „is" je speciální předdefinovaný operátor, který vynutí evaluaci -• porovnej: N = (1+1+1+1+1) N is (1+1+1+1+1) ^ pravá strana musí být vyhodnotitelný výraz (bez proměnné) volání?- X is Y + 1. způsobí chybu -• Další speciální předdefinované operátory >, <, >=, =<, =: = aritmetická rovnost, =\= aritmetická nerovnost M porovnej: 1+2 =:= 2+1 1+2 = 2+1 M obě strany musí být vyhodnotitelný výraz: volání ?- 1 < A + 2. způsobí chybu Hana Rudová, Logické programování I, 17. února 2009 26 Operátory, aritmetika Různé typy rovností a porovnání X = Y XaY jsou unifikovatelné X \= Y XaY nejsou unifikovatelné, (také \+ X = Y) Hana Rudová, Logické programování I, 1 7. února 2009 27 Operátory, aritmetika 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. Hana Rudová, Logické programování I, 1 7. února 2009 27 Operátory, aritmetika 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 Hana Rudová, Logické programování I, 1 7. února 2009 27 Operátory, aritmetika 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 is 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 (=<, >, >=) Hana Rudová, Logické programování I, 1 7. února 2009 27 Operátory, aritmetika 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 is 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ů Hana Rudová, Logické programování I, 1 7. února 2009 27 Operátory, aritmetika 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 is 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. února 2009 27 Operátory, aritmetika Prolog: příklady Příklad: průběh a :- b,c,d. b :- e,c,f,g. b :- g,h. c. d. e : - i . e : - h. g- h. i . Jak vypadá průběh výpočtu pro dotaz ?- a. Hana Rudová, Logické programování I, 1 7. února 2009 29 i/ý počtu 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. Hana Rudová, Logické programování I, 17. února 2009 30 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(stredni). kostka(velka). vetsi(zeme,velká). vetsi(zeme,střední). vetsi(zeme,mala). vetsi(velka,strední). vetsi(velká,mal a). vetsi(stredni,mala). % ?- postav_vez(vez(zeme,0), vez(Kostka,0)). % ?- postav_vez(vez(zeme,0), vez(Kostka,3)). Hana Rudová, Logické programování I, 1 7. února 2009 30 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(stredni). kostka(velka). vetsi(zeme,velká). vetsi(zeme,střední). vetsi(zeme,mala). vetsi(velka,strední). vetsi(velká,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 is Vyska + 1, Přidáni = vez( Kostka, NovaVyska ). Hana Rudová, Logické programování I, 17. února 2009 30 Prolog: příklad