Backtracking, unifikace, aritmetika Syntaxe logického programu Term: JS> univerzální datová struktura (slouží také pro příkazy jazyka) ii> definovaný rekurzivně & konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaku (operátory) proměnné: pojmenované (alfanumerické retezce začínající anonymní (zacínají podtržítkem) složený term: funktor, arita, argumenty struktury jsou opet termy Hana Rudová, Logické programování I, 4. brezna 2011 2 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu & Program: množina predikátu (v jednom nebo více souborech). & Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity & Klauzule: vety ukoncené teckou, se skládají z hlavy a tela. Prázdné telo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvorí literál (složený term), telo seznam literálů. Literálům v tele nebo v dotazu ríkáme cíle. Dotazem v prostredí interpretu se spouští programy ci procedury. & pr. otec(Otec,Dite) i- rodic(Otec,Dite), muz(Otec). rodicCpetr, jana). i- otec(Otec, jana). Sémantika logického programu: procedury = databáze faktu a pravidel = logické formule Hana Rudová, Logické programování I, 4. brezna 2011 3 Backtracking, unifikace, aritmetika : SICStus Debugging - My Prolog Project/rny_rnodule.pro - Eclipse SDK dow Help O ' EH 1 $ SICStus Debu... | " % Debug eT\^ % 0»» D ■ 1 3. o> .ß % 1 ^ Q n"1 M= Variables eTX^*« Breakpoints] to *í B ^ " n' ^ Prolog Top-level Configuration [SICStus Launch Configuration Type 1] Name Value jj^ Prolog Target ❖ Suff [a, .7551, c] = call: suffix[[a,_7551,c],_1810] ❖ X _1810 = rny_predlL1810] ^ Prolog Top-level Process rny_rnodule,pro S3 /* -*- Mode .-Prolog □ Outline */ :- ir.odule (ir.y_rr.odule, [it.y_predl/i, it.y pred3/J £ c=rr.s about exporting undefined predicate ]> ■ dl :- use_ir.odule (library (lists) , [postfix/5, Í varus about importing undefined predicate suffix/5 £ integrated help {also for- user predicatesj If * my_predl/l MS Windows: používání IDE SPIDER: z nabídky All Programs -> IDE -> Eclipse 3.6 Jr príkazový rádek: z nabídky All Programs -> IDE -> SICStus 4.1.3 nastavíme pracovní adresár pomocí File/Working directory, v prípade potreby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. C- Iniciální nastavení SICStus IDE v Eclipse pomocí Help->Cheat Sheets->Initial set up of paths to installed SICStus Prolog s cestou "C:\Program Files (x86)\SICStus Prolog VC9 4.L3\bin\sicstus.exe" návod: http://www.sics.se/sicstus/spider/site/prerequisites.html#SettingUp Hana Rudová, Logické programování I, 4. března 2011 Backtracking, unifikace, aritmetika SICStus Prolog: konzultace & Otevření souboru: File->Open File & Přístup k příkazové řádce pro zadávání dotazU: SICStus->Open Toplevel & NaCtení programu: tzv. konzultace prímo z Menu: SICStus->Consult Prolog Code (okno s programem aktivní) nebo zadáním na příkazový rádek po uložení souboru (Ctrl+S) ?- consult(rodokmen). pokud uvádíme celé jméno prípadne cestu, dáváme jej do apostrofů ?- consult('D:\prolog\moje\programy\rodokmen.pl'). JS> V Eclipse lze nastavit Key bindings, pracovní adresár, ... Hana Rudová, Logické programování I, 4. brezna 2011 6 Backtracking, unifikace, aritmetika SICStus Prolog: spouštění a přerušení výpočtu Spouštění programů/procedur/predikátů je zápis dotazů na příkazové řádce (v okne TopLevel, kůrzor můsí být na konci posledního řádků s | ?- ), př. ?- predek(petr,lenka). ?- predek(X,Y). Každý příkaz ůkonCůjeme teCkoů. & Prerušení a zastavení cyklícího programu: pomocí ikony Restařt Přolog z okna Toplevel Hana Růdová, Logické přogřamování I, 4. března 2011 7 Backtracking, unifikace, aritmetika Příklad rodokmen rodicCpetr, filip). rodicCpetr, lenka). rodicCpavel, jan). rodic(adam, petr). rodic(tomas, michal). rodic(michal, radek). rodic(eva, filip). rodic(jana, lenka). rodic(pavla, petr). rodic(pavla, tomas). rodic(lenka, vera). otec(Otec,Dite) :- rodic(Otec,Dite), muz(petr). muz(filip). muz(pavel). muz(jan). muz(adam). muz(tomas). muz(michal). muz(radek). zena(eva). zena(lenka). zena(pavla). zena(jana). zena(vera). muz(Otec). Hana Rudová, Logické programování I, 4. března 2011 8 Backtracking, unifikace, aritmetika Backtracking: příklady V pracovním adresáři vytvořte program rodokmen.pl. Načtěte program v interpretu (konzultujte). V interpretu Sicstus Prologu pokládejte dotazy: Je Petr otcem Lenky? & Je Petr otcem Jana? JS> Kdo je otcem Petra? & Jaké deti má Pavla? JS> Ma Petr dceru? Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 4. brezna 2011 9 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů Středníkem si vyžádáme další řešení | ?- otec(petr,lenka). yes | ?- otec(petr,jan). no | ?- otec(Kdo,petr). Kdo = adam ? ; no | ?- rodic(pavla,Dite). Dite = petr ? ; Dite = tomas ? ; no | ?- otec(petr,Dcera),zena(Dcera). Dcera = lenka ? ; no Hana Růdová, Logické přogřamování I, 4. b řezna 2011 | ?- otec(Otec,Syn),muz(Syn). Syn = filip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = michal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- 10 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Predek) rodic(Predek,Potomek). potomek(Potomek,Predek) rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) nápoveda: využijte X \== Y (X a Y nejsou identické) Hana Rudová, Logické programování I, 4. března 2011 11 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Predek) :- rodic(Predek,Potomek). potomek(Potomek,Predek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) nápoveda: využijte X \== Y (X a Y nejsou identické) Rešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodic), zena(Prababicka), rodic(Prarodic,Rodic), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 4. brezna 2011 11 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodic(X,Bratr), muz(Bratr), rodic(X,Sourozenec), /* tento test neni nutny, ale zvysuje efektivitu */ Bratr \== Sourozenec, rodic(Y,Bratr), Y \== X, rodic(Z,Sourozenec), Z \== X, Z \== Y. /* nevhodne umisteni testu -vypocet "bloudi" v neuspesnych vetvich */ nevlastni_bratr2(Bratr,Sourozenec):-rodic(X,Bratr), rodic(X,Sourozenec), rodic(Y,Bratr), rodic(Z,Sourozenec), Y \ == X, Z \ == X, Z \== Y, muz(Bratr). Hana Rudová, Logické programování I, 4. března 2011 12 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru -í* Zkuste předem odhadnout (odvodit) pořadí, v jakém budou nalezeni potomci Pavly? Jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci? Nahrad'te ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,y):-rodicCX,Y),printCX),printC'? '). Pozorujte rozdíly v délce výpoctu dotazu nev1astni_bratr(fi1ip,X) pri zmene poradí testů v definici predikátu nev1astni_bratr/2 Hana Rudová, Logické programování I, 4. brezna 2011 13 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta 1a */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). /* varianta 1b - jine poradi odpovedi, neprimi potomci maji prednost */ potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhe klauzuli, na dotaz potomek(X,pavla) vypise odpovedi, pak cykli */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 4. brezna 2011 14 Backtracking, unifikace, aritmetika | ?- nev1astni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = filip, Y = lenka ? ; petr? pavel? pavel? adam? adam? tomas? tomas? michal? michal? eva? eva? jana? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? lenka? no | ?- nev1astni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr? jana X = filip, Y = lenka ? ; petr? petr? petr? petr? eva? jana? petr? eva? petr? petr? petr? jana? jana? petr? jana? pavel? pavel? pavel? pavel? adam? adam? adam? adam? pavla? pavla? adam? pavla? tomas? tomas? tomas? tomas? michal? michal? michal? michal? eva? eva? petr? petr? eva? eva? petr? eva? jana? jana? petr? petr? jana? jana? petr? jana? pavla? pavla? adam? adam? pavla? pavla? adam? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? lenka? lenka? lenka? lenka? no Hana Rudová, Logické programování I, 4. b rezna 2011 15 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proC? Co je výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,p1us) 6. s(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Hana Rudová, Logické programování I, 4. b rezna 2011 16 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proc? Co je výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,p1us) 6. s(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Neuspeje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v případech 4),7) a 8) prestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen proměnných. Hana Rudová, Logické programování I, 4. brezna 2011 16 Backtracking, unifikace, aritmetika Mechanismus unifikace I Unifikace v průběhu dokazování predikátu odpovídá předávání parametrů při provádění procedury, aleje důležité uvědomit si rozdíly. Celý proces si ukážeme na príkladu predikátu suma/3. suma(0,X,X). /*klauzule A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /*klauzule B*/ pomocí substituCních rovnic pri odvozování odpovedi na dotaz ?- suma(s(0),s(0),X0). Hana Rudová, Logické programování I, 4. brezna 2011 17 Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ suma(sCX),Y,s(Z)):-suma(X,Y,Z). /*B*/ ?- suma(s(0),s(0),X0). 1. dotaz unifikujeme s hlavou klauzule B, s A nejde unifikovat (1. argument) suma(s(0),s(0),X0) = suma(s(X1),Y1,s(Z1)) ==> X1 = 0, Y1 = s(0), s(Z1) = X0 ==> suma(0,s(0),Z1) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznacíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Z1 = s(0) ==> X0 = s(s(0)) X0 = s(s(0)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 4. brezna 2011 18 Backtracking, unifikace, aritmetika Vícesmernost predikátů Logický přogřam lze vyůžít vícesmeřne, například jako JS> výpocet kdo je otcem Petřa? ?- otec(X,petr). kolikje 1+1? ?- suma(s(0),s(0),X). iS* test je Jan otcem Petřa? ?- otec(jan,petr). Je 1+1 2??- suma(s(0),s(0),s((0)) ). & geneřátoř kteřé dvojice otec-díte známe? ?-otec(X,Y). Kteřé X a Y dávají v soůctů 2? ?- suma(X,Y,s(s(0)) ). ... ale pozoř na levoů řekůřzi, volné přomenné, asymetřii, a jiné záležitosti Následůjící dotazy ?-suma(X,s(0),Z). ?-suma(s(0),X,Z). nedávají stejné výsledky. Zkůste si je odvodit pomocí sůbstitůcních řovnic. Hana Růdová, Logické přogřamování I, 4. března 2011 19 Backtřacking, ůnifikace, ařitmetika Aritmetika Zavádíme z praktických duvodu, ale aritmetické predikáty již nejsou vícesmerné, protože v každém aritmetickém výrazu musí být všechny promenné instaciovány císelnou konstantou. Duležitý rozdíl ve vestavených predikátech is/2 vs. =/2 vs. =:=/2 is/2: < konstanta nebo promenná > is < aritmetický výraz > výraz na pravé straneje nejdríve aritmeticky vyhodnocen a pak unifkován s levou stranou =/2: < libovolný term > = < libovolný term > levá a pravá strana jsou unifikovány "=:="/2 "=\="/2 ">="/2 "=<"/2 < aritmetický výraz > =:= < aritmetický výraz > < aritmetický výraz > =\= < aritmetický výraz > < aritmetický výraz > =< < aritmetický výraz > < aritmetický výraz > >= < aritmetický výraz > levá i pravá strana jsou nejdríve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování I, 4. b rezna 2011 20 Backtracking, unifikace, aritmetika Aritmetika: příklady Jak se liší následující dotazy (na co se kdy ptáme)? Které uspejí (kladná odpoved ' ), které neuspejí (záporná odpoved'), a které jsou špatne (dojde k chybe)? Za jakých predpokladu by ty neúspešné prípadne špatné uspely? 1. X = Y+ 1 2. X is Y+ 1 3. X = Y 4. X== Y 5. 1 + 1 = 2 6. 2 = 1 + 1 7. 1 + 1 = 1 + 1 8. 1 + 1 is 1 + 1 9. 1 + 2 =:= 2 + 1 10. X \== Y 11. X=\= Y 12.1+2 =\= 1-2 13. 1 <= 2 14. 1 =< 2 15. sin(X) is sin(2) 16. sin(X) = sin(2+Y) 17. sin(X) =:= sin(2+Y) Nápoveda: '='/2 unifikace, '=='/2 test na identitu, '=:='/2 aritmetická rovnost, '\==' /2 negace testu na identitu, '=\=' /2 aritmetická nerovnost Hana Rudová, Logické programování I, 4. brezna 2011 21 Backtracking, unifikace, aritmetika Aritmetika: príklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. Hana Rudová, Logické programování I, 4. b rezna 2011 22 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty s1/3 a s2/3? Co umí s1/3 navíc oproti s2/3 a naopak? s1(0,X,X). s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. s1/3 je vícesmerný- umí scítat, odecítat, generovat soucty, ale pracuje jen s nezápornými celými císly s2/3 umí pouze scítat, ale také záporná a reálná císla Hana Rudová, Logické programování I, 4. b rezna 2011 22 Backtracking, unifikace, aritmetika Operátory Definice operátoru umožnuje prehlednejší infixový zápis binárních a unárních predikátů, príklad: definice op(1200,Y,':-') umožnuje zápis a:-print(s(s(0))),b,c). pro výraz :-Ca,,CprintCsCs(0))),,Cb,c))). Prefixovou notaci lze získat predikátem display/1. Vyzkoušejte ch'splay((a:-print(s(s(0))),b,c)). display(a+b+c-d-e*f*g-h+i). display([1,2,3,4,5]). Definice standardních operátoru najdete na konci manuálu. Hana Rudová, Logické programování I, 4. b rezna 2011 23 Backtracking, unifikace, aritmetika Zaver Dnešní látku jste pochopili dobre, pokud víte -i* jaký vliv má poradí klauzulí a cílu v predikátu potomek/2 na jeho funkci, -í* jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (príklad nevlastni_bratr/2), -i* k cemu dojde po unifikaci X=a(X), -i* proc neuspeje dotaz ?- X=2, sin(X) is sin(2). za jakých predpokladu uspejí tyto cíle X=Y, X==Y, X=:=Y, & a umíte odvodit pomocí substitucních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 4. b rezna 2011 24 Backtracking, unifikace, aritmetika