IB013 Logické programování I Hana Rudová jaro 2012 Hodnocení předmětu Průběžná písemná práce: až 30 bodů (základy programování v Prologu) M pro každého jediný termín: 22.března 3 alternativní termín pouze v případech závažných důvodů pro neúčast 3 vzor písemky na webu předmětu Závěrečná písemná práce: až 1 50 bodů 3 vzor písemky na webu předmětu 3 opravný termín možný jako ústní zkouška M Zápočtový projekt: celkem až 40 bodů M Hodnocení: součet bodů za projekt a za obě písemky M známka A za cca 1 75 bodů, známka F za cca 1 1 0 bodů 3 známka bude zapsána pouze těm, kteří dostanou zápočet za projekt M Ukončení předmětu zápočtem: zápočet udělen za zápočtový projekt Hana Rudová, Logické programování I, 29. února 201 2 2 Organizace předmětu Základní informace Přednáška: účast není povinná, nicméně ... Cvičení: účast povinná 3 individuální doplňující příklady za zmeškaná cvičení & nelze při vysoké neúčasti na cvičení M skupina 01, sudý pátek, první cvičení 24.února skupina 02, lichý pátek, první cvičení 2.března Web předmětu: interaktivní osnova v ISu M průsvitky dostupné postupně v průběhu semestru 3 harmonogram výuky, předběžný obsah výuky pro jednotlivé přednášky během semestru 3 elektronicky dostupné materiály M informace o zápočtových projektech Hana Rudová, Logické programování I, 29. února 201 2 3 Organizace předmětu Rámcový obsah předmětu Obsah přednášky M základy programování v jazyce Prolog M teorie logického programováni M logické programování s omezujícími podmínkami implementace logického programováni Obsah cvičení zaměřeno na praktické aspekty, u počítačů M programování v Prologu M logické programování M DCG gramatiky logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 29. února 2012 4 Organizace předmětu Literatura Bratko, I. Prolog Programming for Artificial Intelligence. Addison-Wesley, 2001. prezenčně v knihovně Clocksin, W. F. - Mellish, Ch. S. Programming in Prolog. Springer, 1 994. 3 Sterling, L. - Shapiro, E. Y. The art of Prolog : advanced programming techniques. MIT Press, 1 987. M Nerode, A. - Shore, R. A. Logic for applications. Springer-Verlag, 1 993. 3 prezenčně v knihovně M Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. M prezenčně v knihovně + Elektronicky dostupné materiály (viz web předmětu) Hana Rudová, Logické programování I, 29. února 201 2 5 Organizace předmětu rrubezna písemná prace M Pro každého jediný termín 22. března Alternativní termín pouze v závažných důvodech pro neúčast M Celkem až 30 bodů (1 50 závěrečná písemka, 40 projekt) Hana Rudová, Logické programování I, 29. února 201 2 6 Organizace předmětu zna písemná prace M Pro každého jediný termín 22. března Alternativní termín pouze v závažných důvodech pro neúčast M Celkem až 30 bodů (1 50 závěrečná písemka, 40 projekt) M 3 příklady, 40 minut M Napsat zadaný predikát, porovnat chování programů M Obsah: první čtyři přednášky a první dvě cvičení Oblasti, kterých se budou příklady zejména týkat M unifikace seznamy backtracking optimalizace posledního volání 3 řez M aritmetika Ukázka průběžné písemné práce na webu Hana Rudová, Logické programování I, 29. února 201 2 6 Organizace předmětu Zápočtové projekty M Týmová práce na projektech, až 3 řešitelé 3 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 3 bodování, obsah předběžné zprávy a projektu M typ projektu: LP, CLP, DCG 3 CLP a LP: Adriana Strejčkova -L DCG: Miloš Jakubíček, Vojtěch Kovář Předběžná zpráva 3 podrobné zadání M vjakém rozsahu chcete úlohu řešit 3 které vstupní informace bude program používat a co bude výstupem programu 3 scénáře použití programu (tj. ukázky dvojic konkrétních vstupů a výstupů) Hana Rudová, Logické programování I, 29. února 201 2 7 Organizace předmětu Časový harmonogram k projektům M Zveřejnění zadání (většiny) projektů: 27. února Zahájení registrace řešitelů projektu: 7. března, 19:00 M Předběžná analýza řešeného problému: 13. dubna Termín pro odevzdání projektů: 18. května M Předvádění projektů (po registraci): 21.května - 22.června Hana Rudová, Logické programování I, 29. února 201 2 8 Organizace předmětu Software: SICStus Prolog M Doporučovaná implementace Prologu Dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html Komerční produkt licence pro instalace na domácí počítače studentů 3 Nové IDE pro SICStus Prolog SPIDER M dostupné až od verze SICStus 4.1.3 M http://www.sics.se/sicstus/spider používá Eclipse SDK Podrobné informace dostupné přes web předmětu stažení SICStus Prologu (sw + licenční klíče) pokyny k instalaci (SICStus Prolog, Eclipse, Spider) Hana Rudová, Logické programování I, 29. února 201 2 9 Organizace předmětu SICStus IDE SPIDER i SICStus Debugging - My Prolog ProjecVnny_rnodule.pro - Eclipse SDK File Edit SICStus Source Navigate Search Project Run Favorites Window Help r^Twii^i Ef [ < SICStus Debu,, Debug S Or 3. ^ _ß =» ^ Prolog Top-level Configuration [SICStus Launch Configuration Typel] j§ Prolog Target = call: 5uffixC[a,_;551.c],_1810) = my_predl[_1810] Prolog Top-level Process M= Variables £Í\% Breakpoints'] fei *t= B ' " Name Value ♦ Suff [a, _7551, c] « X JL810 ♦ my_module.pro /* Mbde.-Prolog */ module Cir.y_rf.od.alef [my_predl/l, my pred3/J * t^ams about exporting undefined predicate use_niQdule (library (lists), [postfix/^, £ parn^ about importing undefined predicate suffix/5 £ integrated help (also for user predicates) □1 Outline £3 G my_predl/l O my_pred2/2 -suffixPList ?Suffix5 is true when List and Suffix are lists and Suffix is a suffix of List, It terminates only if List is proper, and has at most N+l solutions, Suffixes are enumerated in descending order of length. (documentation formatting will be Emproved later!]_ my_pre:dl (X} :- Stiff = [a. Singleton, c], dssert(seen (X)}, % ^srcj about missing declaration {here dynamic/1} suf fix [Suff, X}, pjcelude (Suff , X} . % Yarns about calling undefined predicate rr.y_pred2 (S, Xs) :- % varn about non-trivial singleton variables I fareach(Y,Xs} do write(S, Xs) >, ( foreach(Y,X3}, param([S]} do write(S, Xs} > ■ □ SICStiKJ^^ Jťl Task] rjg Problems] □ Toplevel 1 in C:/Users/perm.SICS-AD/runtime-EclipseApplication42/My Prolog Project 2 Exit: assert (ray module : seen xs ( 1810}} ? 2 Call: suffix([a, 7551,c],1810} ? | Hana Rudová, Logické programování I, 29. února 201 2 10 převzato z http://www.sics.se/sicstus/spider Organizace předmětu Úvod do Prologu Prolog M PROgramming in LOGic M část predikátové logiky prvního řádu M Deklarativní programování M specifikační jazyk, jasná sémantika, nevhodné pro procedurální postupy M Co dělat namísto Jak dělat M Základní mechanismy M unifikace, stromové datové struktury, automatický backtracking Hana Rudová, Logické programování I, 29. února 201 2 12 Úvod do Prologu Logické programování Historie M Rozvoj začíná po roce 1 970 Robert Kowalski - teoretické základy M Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace M SICStus Prolog vyvíjen od roku 1985 Logické programování s omezujícími podmínkami - od poloviny 80. let Aplikace M rozpoznávání řeči, telekomunikace, biotechnologie, logistika, plánování, data mining, business rules, ... M SICStus Prolog — the first 25 years, Mats Carlsson, Per Mildner. Theory and Practice of Logic Programming, 12 (1-2): 35-66, 2012. http://arxiv.org/abs/1011.5640. Hana Rudová, Logické programování I, 29. února 2012 13 Úvod do Prologu Program = fakta + pravidla (Prologovský) program je seznam programových klauzulí M programové klauzule: fakt, pravidlo M 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 M studuje( X ) :- clovek( X, _Vek, student ). 3 alternativní (obousměrný) význam pravidel pro každé X, pro každé X, X studuje, jestliže Xje student, potom X je student X studuje M pracuje( X ) :- clovek( X, _Vek, CoDela ), prace( CoDela ). Hana Rudová, Logické programování I, 29. února 201 2 14 Úvod do Prologu Program = fakta + pravidla (Prologovský) program je seznam programových klauzulí M programové klauzule: fakt, pravidlo M 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 M studuje( X ) :- clovek( X, _Vek, student ). 3 alternativní (obousměrný) význam pravidel pro každé X, pro každé X, X studuje, jestliže Xje student, potom X je student X studuje M pracuje( X ) :- clovek( X, _Vek, CoDela ), prace( CoDela ). Predikát: seznam 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, 29. února 2012 14 Úvod do Prologu Komentáře k syntaxi M Klauzule ukončeny tečkou M Základní příklady argumentů 3 konstanty: (tomas, anna) ... začínají malým písmenem M proměnné X, Y ... začínají velkým písmenem & _, _A, _B ... začínají podtržítkem (nezajímá nás vracená hodnota) M Psaní komentářů clovek( novak, 18, student ). % komentář na konci řádku clovek( novotny, 30, učitel ). /* komentář */ Hana Rudová, Logické programování I, 29. února 201 2 Úvod do Prologu Dotaz Dotaz: uživatel se ptá programu, zda jsou věci pravdivé ?- studuje( novak ). % yes splnitelný dotaz ?- studuje( novotny ). % no nesplnitelný dotaz M Odpověď na dotaz 3 positivní - dotaz je splnitelný a uspěl 3 negativní - dotaz je nesplnitelný a neuspěl Hana Rudová, Logické programování I, 29. února 201 2 16 Úvod do Prologu Dotaz Dotaz: uživatel se ptá programu, zda jsou věci pravdivé ?- studuje( novak ). % yes splnitelný dotaz ?- studuje( novotny ). % no nesplnitelný dotaz M Odpověď na dotaz 3 positivní - dotaz je splnitelný a uspěl 3 negativní - dotaz je nesplnitelný a neuspěl M Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty) 3 ?- clovek( novak, 18, Prace ). Prace = student M výsledkem dotazu je instanciace proměnných v dotazu 3 dosud nenainstanciovaná proměnná: volná proměnná Hana Rudová, Logické programování I, 29. února 201 2 16 Úvod do Prologu Dotaz Dotaz: uživatel se ptá programu, zda jsou věci pravdivé ?- studuje( novak ). % yes splnitelný dotaz ?- studuje( novotny ). % no nesplnitelný dotaz M Odpověď na dotaz 3 positivní - dotaz je splnitelný a uspěl 3 negativní - dotaz je nesplnitelný a neuspěl M Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty) 3 ?- clovek( novak, 18, Prace ). Prace = student M výsledkem dotazu je instanciace proměnných v dotazu 3 dosud nenainstanciovaná proměnná: volná proměnná M 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, 29. února 2012 16 Úvod do Prologu Klauzule = fakt, pravidlo, dotaz M Klauzule se skládá z hlavy a těla Tělo je seznam cílů oddělených čárkami, čárka = konjunkce M Fakt: pouze hlava, prázdné tělo 3 rodic( pavla, robert ). Pravidlo: hlava i tělo M upracovany_clovek( X ) :- clovek( X, _Vek, Prace ), prace( Prace, tezka ). Dotaz: prázdná hlava, pouze tělo M ?- clovek( novak, Vek, Prace ). ?- rodic( pavla, Dite ), rodic( Dite, Vnuk ). Hana Rudová, Logické programování I, 29. února 201 2 Úvod do Prologu Rekurzivní pravidla predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2) rodicC Y, Z ). Hana Rudová, Logické programování I, 29. února 201 2 18 Úvod do Prologu Rekurzivní pravidla predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2) rodicC Y, Z ). predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 29. února 201 2 18 Úvod do Prologu Příklad: rodokmen rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, anna ). rodic( robert, petr ). rodic( petr, jirka ). pavla^ v tomas Rodiče > \/ robert / \ eliska / anna \ petr / / jirka Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 29. února 201 2 19 Úvod do Prologu Výpočet odpovědi na dotaz ?- predek(tomas,robert) rodi rodi rodi rodi rodi c( pavla, robert ). c( tomas, robert ). c( tomas, eli ska ). c( robert, anna ). c( robert, petr ). rodic( petr, jirka ). predek(tomas,robert) dle (1) Y yes rodic(tomas,robert) predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Hana Rudová, Logické programování I, 29. února 201 2 20 Ú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 ). predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). Y=robert t dle rodic(tomas, robert) predek( robert, petr) t dle (1) rodic(robert, petr) yes Hana Rudová, Logické programování I, 29. února 201 2 21 Úvod do Prologu Odpověď na dotaz s proměnnou pavla tomas Rodiče rodi c( pavla, robert ). rodi c( tomas, robert ). \ / \ rodi c( tomas, el i ska ). robert eliska rodi c( robert, anna ). / \ rodi c( robert, petr ). / \ rodi c( petr, ji rka ). anna petr z / jirka ! Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). predek(petr,Potomek) --> ??? Hana Rudová, Logické programování I, 29. února 201 2 22 Úvod do Prologu Odpověď na dotaz s proměnnou rodic( pavla, robert ). rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, anna ). rodic( robert, petr ). rodic( petr, ji rka ). pavla^ tomas i Rodiče \ / robert / \ eliska [ \ i / anna \ : petr i / i / jirka ■ Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). predek(petr,Potomek) --> ??? Potomek=jirka Hana Rudová, Logické programování I, 29. února 201 2 22 Úvod do Prologu Odpověď na dotaz s proměnnou pavla tomas i Rodiče rodi c( pavla, robert ). / \ ' rodi c( tomas, robert ). \ ! rodi c( tomas, el i ska ). robert eliska[ rodi c( robert, anna ). y / \ \ ! rodi c( robert, petr ). / \ : rodi c( petr, ji rka ). anna petr i / i / jirka ■ Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). predek(petr,Potomek) --> ??? predek(robert,P) --> ??? Hana Rudová, Logické programování I, 29. února 201 2 22 Potomek=ji rka Úvod do Prologu Odpověď na dotaz s proměnnou pavla tomas « Rodiče rodi c( pavla, robert ). / \ ' rodi c( tomas, robert ). \ ! rodi c( tomas, el i ska ). robert eliska] rodi c( robert, anna ). v ! rodi c( robert, petr ). \ [ rodi c( petr, ji rka ). anna petr i / i / jirka ■ Deti predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2') predek( Y, Z ). predek(petr,Potomek) --> ??? Potomek=jirka predek(robert,P) --> ??? 1. P=anna, 2. P=petr, 3. P=jirka Hana Rudová, Logické programování I, 29. února 2012 22 Úvod do Prologu Syntaxe a význam Prologovských programů Syntaxe Prologovských programu M Typy objektů jsou rozpoznávány podle syntaxe Atom M řetězce písmen, čísel, „_" začínající malým písmenem: pavel , pavel_novak, x2 5 M řetězce speciálních znaků: <-->, ====> řetězce v apostrofech: 'Pavel', 'Pavel Novák' Celá a reálná čísla: 0, -1056, 0.35 M Proměnná 3 řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_" 3 anonymní proměnná: ma_dite(X) :- rodic( X, _ ). S» hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodic( X, _ ) 3 lexikální rozsah proměnné je pouze jedna klauzule: prvni(X,X,X). prvni(X,X,_)■ Hana Rudová, Logické programování I, 29. února 201 2 24 Syntaxe a význam Prologovských programů Termy M Term - datové objekty v Prologu: datum( 1, kveten, 2003 ) funktor: datum * argumenty: 1, kveten, 2003 3 arita - počet argumentů: 3 Všechny strukturované objekty v Prologu jsou stromy 3 trojuhelnik( bod(4,2), bod(6,4), bod(7,l) ) M Hlavní funktor termu - funktor v kořenu stromu odpovídající termu * trojuhelni k je hlavní funktor v trojuhelni k( bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 29. února 201 2 2 5 Syntaxe a význam Prologovských programů Unifikace Termy jsou unifikovatelné, jestliže jsou identické nebo 3 proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické M datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 Hana Rudová, Logické programování I, 29. února 201 2 26 Syntaxe a význam Prologovských programů Unifikace M Termy jsou unifikovatelné, jestliže M jsou identické nebo 3 proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické «• datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 Hledáme nejobecnější unifikátor (most general unifier (MGU) M jiné instanciace? ... Dl = 1, Ml = 5, Y2 = 2003 ... není MGU 3 ?- datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml. Hana Rudová, Logické programování I, 29. února 201 2 26 Syntaxe a význam Prologovských programů Unifikace M Termy jsou unifikovatelné, jestliže M jsou identické nebo 3 proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické «• datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 Hledáme nejobecnější unifikátor (most general unifier (MGU) M jiné instanciace? ... Dl = 1, Ml = 5, Y2 = 2003 ... není MGU 3 ?- datum( Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml. M 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, 29. února 201 2 26 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M výsledná substituce je určena unifikací argumentů Příklady: k = k ... yes, kl = k2 ... no, Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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))... Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... no Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... no s(sss(A),4,ss(C)) = s(sss(t(B)),4,ss(A))... Hana Rudová, Logické programování I, 29. února 201 2 27 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1 . S a T jsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; T je proměnná a S cokoliv jiného - T je instanciována na S 3. S a T jsou termy J SaT mají stejný funktor a aritu a M všechny jejich odpovídající argumenty jsou unifikovatelné M 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 s(sss(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, 29. února 201 2 27 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů M p :- q, r. Deklarativní: Co je výstupem programu? M p je pravdivé, jestliže q a r jsou pravdivé J Zqa r plyne p => význam mají logické relace Hana Rudová, Logické programování I, 29. února 201 2 28 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů M p :- q, r. Deklarativní: Co je výstupem programu? M p je pravdivé, jestliže q a r jsou pravdivé J Zqa r plyne p => význam mají logické relace Procedurální: Jak vypočítáme výstup programu? M 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ů M výstup ^ indikátor yes/no určující, zda byly cíle splněny St instanciace proměnných v případě splnění cílů Hana Rudová, Logické programování I, 29. února 201 2 28 Syntaxe a význam Prologovských programů Deklarativní význam programu 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 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é. Hana Rudová, Logické programování I, 29. února 201 2 29 Syntaxe a význam Prologovských programů Konjunce vs. disjunkce ";" cílů Konjunce = nutné splnění všech cílů M p :- q, r. 3 Disjunkce = stačí splnění libovolného cíle p : - q; r. p:-q. p : - r. 3 priorita středníku je vyšší (viz ekvivalentní zápisy): p :- q, r; s, t, u. p :- (q, r) ; (s, t, u). P :- q, r. p : - s , t, u. Hana Rudová, Logické programování I, 29. února 201 2 30 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l) a(X) :- b(X,Y), a(Y). b(l,l). Hana Rudová, Logické programování I, 29. února 201 2 31 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l,l). Hana Rudová, Logické programování I, 29. února 201 2 31 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l, 1) . % nenalezení odpovědi: nekonečný cyklus Hana Rudová, Logické programování I, 29. února 201 2 31 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l, 1) . % nenalezení odpovědi: nekonečný cyklus (c) a(X) :- b(X,Y), c(Y). ?- a(X). b(l,l). c(2). c(l). Hana Rudová, Logické programování I, 29. února 201 2 31 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l, 1) . % 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) b(l,l). c(2). c(l). Hana Rudová, Logické programování I, 29. února 201 2 31 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů (a) a(l). ?- a(l). a(X) :- b(X,Y), a(Y). b(l,l). (b) a(X) :- b(X,Y), a(Y) . % změněné pořadí klauzulí v programu vzhledem k (a) a(l). b(l, 1) . % 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) 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, 29. února 201 2 31 Syntaxe a význam Prologovských programů í klauzulí a cílu I. (1) a(X) :- c(Y), b(X,Y) (2) b(l,l). (3) c(2). (4) c(l). ?- a(X). a(X) dle (1) c(Y), b(X,Y) dle(3)/Ý=2 dle(4kY=1 b(X,2) no b(X,1) dle (2) X=1 yes Hana Rudová, Logické programování I, 29. února 201 2 32 Syntaxe a význam Prologovských programů í klauzulí a cílu I. (1) a(X) :- c(Y), b(X,Y) (2) b(l,l). (3) c(2). (4) c(l). Vyzkoušejte si: (1) a(X) :- b(X,X), c(X) (3) a(X) :- b(Y,X), c(X) (4) b(2,2). (5) b(2,l). (6) c(l). ?- a(X). a(X) dle (1) c(Y), b(X,Y) dle(3)/Ý=2 dle(4kY=1 b(X,2) no b(X,1) dle (2) X=1 yes Hana Rudová, Logické programování I, 29. února 201 2 32 Syntaxe a význam Prologovských programů Cvičení: průběh výpočtu a : - b,c,d. b :- e,c,f,g. b :- g,h. c. d. e : - i. e : - h. g- h. i. Jak vypadá průběh výpočtu pro dotaz ?- a. Hana Rudová, Logické programování I, 29. února 201 2 33 Syntaxe a význam Prologovských programů