Prolog Úvod do Prologu 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 Logické programování Historie ■ Rozvoj začíná po roce 1 970 ■ Robert Kowalski - teoretické základy ■ Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace ■ SICStus Prolog vyvíjen od roku 1 985 ■ Logické programování s omezujícími podmínkami - od poloviny 80. let Aplikace ■ rozpoznávání řeči, telekomunikace, biotechnologie, logistika, plánování, data mining, business rules, ... ■ SICStus Prolog—the first 2 5 years, Mats Carlsson, Per Mildner. Theory and Practice of Logic Programming, 12 (1-2): 35-66, 2012. http://arxiv.org/abs/1011.5640. Hana Rudová, Logické programování I, 25. února 2013 3 Úvod do Prologu Hana Rudová, Logické programování I, 25. února 201 3 2 Ú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 ) :- clovekC 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 Xje student X studuje ■ pracujeC X ) :- clovekC X, _Vek, CoDela ), praceC CoDela ). ■ Predikát: seznam pravidel a faktů se stejným funktorem a aritou ■ značíme: clovek/3, student/l; analogie procedury v procedurálních jazycích, Hana Rudová, Logické programování 1,25. února 2013 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é ■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í I, 25. února 2013 5 Ú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_c"lovek( X ) :- c"lovek( X, _Vek, Prace ), praceC Prace, tezka ). ■ Dotaz: prázdná hlava, pouze tělo ■ ?- clovekC novak, Vek, Prace ). ?- rodicC pavla, Dite ), rodic( Dite, Vnuk ). 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 ). Prace = student ■ výsledkem dotazuje 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í 1,25. února 2013 6 Úvod do Prologu Rekurzivní pravidla predekC X, Z ) :- rodic( X, Z ). % CD predekC X, Z ) :- rodic( X, Y ), % (2) rodic( Y, Z ). predekC X, Z ) :- rodic( X, Y ), % (2') predekC Y, Z ). Hana Rudová, Logické programování I, 25. února 2013 7 Úvod do Prologu Hana Rudová, Logické programování 1,25. února 2013 8 Úvod do Prologu Příklad: rodokmen Výpočet odpovědi na dotaz ?- predek(tomas,robert) rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, e "liská ). rodic( robert, anna ). rodic( robert, petr ). rodic( petr, jirka ). predek( X, Z ) :- rodic( X, Z ) % (D predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 25. února 2013 Úvod do Prologu rodi rodi rodi rodi rodi c( pavla, robert ). c( tomas, robert ) . c( tomas, eli ska ). c( robert, anna ). c( 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, 25. února 201 3 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas, petr) 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 dle rodic(tomas, robert) predek( robert, petr) predekC X, Z ) predekC X, Z ) rodicC X, Z ). % Cl) rodicC X, Y ), % (2') predekC Y, Z ). dle (1) rodic(robert, petr) Hana Rudová, Logické programování I, 25. února 201 3 yes Úvod do Prologu Odpověď na dotaz s proměnnou rodicC pavla, robert ). rodicC tomas, robert ). rodicC tomas, eliska ). rodicC robert, anna ). rodicC robert, petr ). rodicC petr, jirka ). predekC X, Z ) :- rodicC X, Z ). predekC X, Z ) :- rodicC X, Y ), predekC Y, Z ). predekCpetr,Potomek) --> ??? predekCrobert,P) --> ??? Hana Rudová, Logické programování 1,25. února 201 3 1. P=anna, 2. Potomek=ji rka P=petr, 3. P=jirka Úvod do Prologu Syntaxe Prologovských programů Syntaxe a význam Prologovských programu 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 ■ trojuhelnikje hlavní funktor v trojuhelnik( bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 25. února 2013 Syntaxe a význam Prologovských programů 1 Typy objektů jsou rozpoznávány podle syntaxe 1 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 1 Proměnná ■ řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_" ■ anonymní proměnná: ma_dite(X) :- rodic( X, _ ). ■ hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodic( X, _ ) ■ lexikální rozsah proměnné je pouze jedna klauzule: prvni(X,X,X). prvni(X,X,_). Hana Rudová, Logické programování 1,25. února 201 3 1 4 Syntaxe a význam Prologovských programů Unifikace 1 Termy jsou unifikovatelné, 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 1 Hledáme nejobecnější unifikátor (most generál unifler (MGU) • jiné instanciace? ... Dl = 1, Ml = 5 , Y2 = 2003 ... není MCU ■ ?- datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml. 1 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, 25. února 201 3 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,1(1)) = A ... yes s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(l))... no s(sssCA),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, 25. února 2013 17 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů ■ p :- q, r. ■ Deklarativní: Co je výstupem programu? ■ p je pravdivé, jestliže q a r jsou pravdivé ■ Z q a r plyne p => význam mají logické relace ■ Procedurální: Jak vypočítáme výstup programu? ■ p vyřešíme tak, že nejprve vyřešíme q a pak r => kromě logických relací je významné i pořadí cílů ■ výstup ■ indikátor yes/no určující, zda byly cíle splněny ■ instanciace proměnných v případě splnění cílů Hana Rudová, Logické programování 1,25. února 201 3 1 8 Syntaxe a význam Prologovských programů Konjunce "," vs. disjunkce ";" cílů ■ Konjunce = nutné splnění všech cílů " P :- q, r. ■ Disjunkce = stačí splnění libovolného cíle ■ p :- q; r. p :- q. p :- r. ■ priorita středníku je vyšší (viz ekvivalentní zápisy): p :- q, r; s, t, u. P :- Cq, r) ; (s, t, u). P :- q, r. p : - s , t, u . Hana Rudová, Logické programování I, 25. února 2013 19 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í 1,25. února 201 3 20 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů II. Cvičení: průběh výpočtu (1) a(X) :- c(Y), b(X,Y). (2) b(l,l). (3) c(2). (4) c(l). Vyzkoušejte si: (1) a(X) :- b(X,X), c(X). (3) a(X) :- b(Y,X), c(X). (4) b(2,2). (5) b(2,l). (6) c(l). Hana Rudová, Logické programování I, 25. února 201 3 ?- 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, aritmetika 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, 25. února 201 3 Syntaxe a význam Prologovských programu priorita +: 500, priorita *: 400 Operátory Infixová notace: 2*a + b*c Prefixová notace: +( *(2,a), *(b,c) ) ■ prefixovou notaci lze získat predikátem display/l :- display((a:-s(0),b,c)). :-(a, ,(s(0), ,(b,c))) Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor Uživatelsky definované operátory: zna petr zna alese. zna( petr, alese). Definice operátoru: :- op( 600, xfx, zna ). priorita: i ..i 200 ■ :- opC 1100, xfy, ; ). nestrukturované objekty: 0 :- op( 1000, xfy, , ). p :- q, r; s, t. p :- (q, r) ; (s, t). ; má vyšší prioritu než , ■ :- op( 1200, xfx, :- ). :-má nejvyšší prioritu Definice operátoru není spojena s datovými manipulacemi (kromě spec. případů) Hana Rudová, Logické programování 1,25. února 201 3 Operátory, aritmetika Typy operátorů Typy operátorů ■ infixové operátory: xfx, xfy, yfx př. xfx = yfx - ■ prefixové operátory: fx, fy př. fx ?- fy- ■ postfixové operátory: xf, yf x a y určují prioritu argumentu ■ x reprezentuje argument, jehož priorita musí být striktně menší než u operátoru ■ y reprezentuje argument, jehož priorita je menší nebo rovna operátoru ■ a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx / správne chybně c; © priorita: 0 priorita: 0 priorita: 500 Hana Rudová, Logické programování I, 25. února 2013 priorita: 500 Operátory, aritmetika Různé typy rovností a porovnání X = Y X a Y jsou unifikovatelné X \= Y X a Y nejsou unifikovatelné, (také \+ X = Y) X == Y X a Y jsou identické porovnej: ?-A == B. ... no ?-A=B, A==B. ... B = A yes X \== Y X a Y 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 X a Y si aritmeticky nejsou rovny X < Y aritmetická hodnota X je menší než Y (=<, >, >=) X @< Y term X předchází term Y (@=<, @>, @>=) 1. porovnání termů: podle alfabetického n. aritmetického uspořádání 2. porovnání struktur: podle arity, pak hlavního funktoru a pak zleva podle argumentů ?- f( pavel, g(b)) @< f( pavel, h(a)). .. .yes Hana Rudová, Logické programování I, 25. února 2013 Operátory, aritmetika Aritmetika 1 Předdefinované operátory + , -, *, /, '■'•"■'•'mocnina,// celočíselné dělení, mod zbytek po dělení 1 ?- X = 1 + 2. X=l + 2 = odpovídá unifikaci ■ ?- X i s 1 + 2. X = 3 „i s" je speciální předdefinovaný operátor, který vynutí evaluaci ■ porovnej: N = (1+1+1+1+1) N i s (1+1+1+1+1) ■ pravá strana musí být vyhodnotitelný výraz (bez proměnné) ■ výraz na pravé straně je nejdříve aritmeticky vyhodnocen a pak unifikován s levou stranou volání?- X i s Y + 1. způsobí chybu 1 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í 1,25. února 2013 26 Operátory, aritmetika