Backtracking, unifikace, aritmetika Syntaxe logického programu Term: M univerzální datová struktura (slouží také pro príkazy jazyka) -• definovaný rekurzivně M konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaků (operátory) -• proměnné: pojmenované (alfanumerické řetězce začínající velkým písmenem), anonymní (začínají podtržítkem) M složený term: funktor, arita, argumenty struktury jsou opět termy Hana Rudová, Logické programování I, 9. března 2010 2 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu M Program: množina predikátů (v jednom nebo více souborech). -• Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity -• Klauzule: věty ukončené tečkou, se skládají z hlavy a těla. Prázdné tělo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvoří literal (složený term), tělo seznam literálů. Literálům v těle nebo v dotazu říkáme cíle. Dotazem v prostředí interpretu se spouští programy či procedury. Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování I, 9. března 2010 3 Backtracking, unifikace, aritmetika Sicstus Prolog minimum I M Spustení interpretu: V unixu přidáme modul module add sicstus a spustíme příkazem sicstus Pracovním adresářem je aktuální (tam kde byl spuštěn). V MS Windows standardně z nabídky Start/Programs nebo pomocí ikony, nastavíme pracovní adresář pomocí File/Working directory, v případě potřeby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. Hana Rudová, Logické programování I, 9. března 2010 4 Backtracking, unifikace, aritmetika Sicstus Prolog minimum II M Načtení programu: tzv. konzultace Editor není integrován, takže program editujeme externě ve svém oblíbeném editoru. Pak ho načteme z příkazové řádky v interpretu příkazem ?- consult(jmeno). nebo pomocí zkrácené syntaxe ?- [jméno]. % (předpokládá se přípona .pl) pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofu ?- ['D:\prolog\moje\programy\jmeno.pl']. V MS Windows lze také pomocí nabídky File/Consult Hana Rudová, Logické programování I, 9. března 2010 5 Backtracking, unifikace, aritmetika Sicstus Prolog minimum III -• Spouštění programů/procedur/predikátů je zápis dotazů, př. ?- muj_prech'kat(X,Y) . ?- suma(l,2,Y), vypis('Výsledek je ',Y). Každý příkaz ukončujeme tečkou. -• Přerušení a zastavení cyklícího programu: Ctrl-C -• Ukončení interpretu příkazem ?- halt. Hana Rudová, Logické programování I, 9. března 2010 6 Backtracking, unifikace, aritmetika Příklad rodič (pet r, filip). rodic(petr, lenka). rodic(pavel, j an). rodic(adam, petr). rodic(tomas, michal). rodič(michal, radek). rodic(eva, filip). rodic(jana, lenka). rodic(pavla, petr). rodic(pavla, tomas). rodic(lenka, vera). otec(Otec,Ditě) :- rodič(Otec,Ditě), Hana Rudová, Logické programování I, 9. března 2010 rodokmen 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). 7 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? «• Kdo je otcem Petra? -• Jaké děti má Pavla? -• Ma Petr dceru? -• Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 9. března 2010 8 Backtracking, unifikace, aritmetika Backtracking: Středníkem si vyžádáme další řešení I ?- otecCpetr,lenka). yes I ?- otecCpetr,jan). no | ?- otecCKdo,petr). Kdo = adam ? ; no | ?- rodicCpavla,Dite). Ditě = petr ? ; Ditě = tomas ? ; no | ?- otecCpetr,Dcera),zenaCDcera). Dcera = lenka ? ; no Hana Rudová, Logické programování I, 9. března 2010 reseni přikladu | ?- otecC0tec,Syn),muzCSyn). Syn = filip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = michal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- 9 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty -• prababicka(Prababicka,Pravnouce) -• nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) Hana Rudová, Logické programování I, 9. března 2010 10 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty -• prababicka(Prababicka,Pravnouce) -• nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodič), zena(Prababicka), rodič(Prarodič,Rodič), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 9. března 2010 10 Backtracking, unifikace, aritmetika Backtracking: nevlastni_bratr(Bratr,Sourozenec):-rodíc_v(X,Bratr), muz(Bratr), rodíc_v(X,Sourozenec), /* tento test není nutný, ale zvyšuje efektivitu */ Bratr \== Sourozenec, rodic_v(Y,Bratr), Y \== X, rodic_v(Z,Sourozenec), Z \== X, Z \== Y. Hana Rudová, Logické programování I, 9. března 2010 reseni přikladu II /* nevhodne umisteni testu - vypočet "bloudi" v neúspešných vetvi ch */ nevlastni_bratr2(Bratr,Sourozenec):- rodic_v(X,Bratr), rodic_v(X,Sourozenec), rodic_v(Y,Bratr), rodic_v(Z,Sourozenec), Y \== X, Z \== X, Z \== Y, muz(Bratr). 11 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru M 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? -• Nahraďte ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,Y):-rodic(X,Y),přint(X),přint('? '). Pozorujte rozdíly v délce výpočtu dotazu nevlastni_bratr(filip,X) při změně pořadí testů v definici predikátu nevlastni_bratr/2 Hana Rudová, Logické programování I, 9. března 2010 12 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta la */ potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). /* varianta lb - jine poradí odpovedi, nepřímí potomci mají přednost */ potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovedi, pak cykli */ potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 9. března 2010 13 Backtracking, unifikace, aritmetika I ?- nevlastni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = fi lip, 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 I ?- nevlastni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr? jana X = fi lip, 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, 9. března 2010 14 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proč? 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,plus) 6. s(l,a(X,q(w)))=s(Y,a(2,Z)) 7. s(l,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(l,a(P,q(R)))=s(Z,a(X,Y)) Hana Rudová, Logické programování I, 9. března 2010 15 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proč? 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,plus) 6. s(l,a(X,q(w)))=s(Y,a(2,Z)) 7. s(l,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(l,a(P,q(R)))=s(Z,a(X,Y)) Neuspěje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v případech 4),7) a 8) přestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen proměnných. Hana Rudová, Logické programování I, 9. března 2010 15 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 příkladu predikátu suma/3. suma(0,X,X). /*klauzule A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /^klauzule B*/ pomocí substitučních rovnic při odvozování odpovědi na dotaz ?- suma(s(0),s(0),X0). Hana Rudová, Logické programování I, 9. března 2010 16 Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ suma(s(X),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(Xl),Yl,s(Zl)) ==> xi = 0, Yl = s(0), s(Zl) = X0 ==> suma(0,s(0),Zl) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznačíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Zl = s(0) ==> X0 = s(sCO)) X0 = s(sCO)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 9. března 2010 17 Backtracking, unifikace, aritmetika Vícesměrnost predikátů Logický program lze využít vícesměrně, například jako M výpočet kdo je otcem Petra? ?- otec(X,petr) . kolik je 1+1??- suma(s(0),s(0),X). -• test je Jan otcem Petra? ?- otec(jan,petr) . Je 1+1 2??- suma(s(0),s(0),s( (0))). -• generátor které dvojice otec-dítě známe? ?-otec(X,Y) . Které X a Y dávají v součtu 2? ?- suma(X,Y,s(s(0))) . ... ale pozor na levou rekurzi, volné proměnné, asymetrii, a jiné záležitosti Následující dotazy ?-suma(X,s(0),Z). ?-suma(s(0),X,Z). nedávají stejné výsledky. Zkuste šije odvodit pomocí substitučních rovnic. Hana Rudová, Logické programování I, 9. března 2010 18 Backtracking, unifikace, aritmetika Aritmetika Zavádíme z praktických důvodů, ale aritmetické predikáty již nejsou vícesměrné, protože v každém aritmetickém výrazu musí být všechny proměnné instaciovany číselnou konstantou. Důležitý rozdíl ve vestavěných predikátech is/2 vs. =/2 vs. =:=/2 is/2: < konstanta nebo proměnná > is < aritmetický výraz > výraz na pravé straně je nejdříve aritmeticky vyhodnocen a pak unifkován s levou stranou =/2: < libovolný term > = < libovolný term > levá a pravá strana jsou unifikovány "=:="/2 ,,=\="/2 M>=72 M=<72 < 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 nejdříve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování I, 9. března 2010 19 Backtracking, unifikace, aritmetika Aritmetika: příklady Jak se liší následující dotazy (na co se kdy ptáme)? Které uspějí (kladná odpověď), které neuspějí (záporná odpověď), a které jsou špatně (dojde k chybě)? Za jakých předpokladů byty neúspěšné případně špatné uspěly? l.X = Y+ 1 7. 1 + 1 = 1 + 1 13. 1 <= 2 2.X is Y+ 1 8. 1 + 1 is 1 + 1 3.X = Y 9. 1 + 2 =:= 2 + 1 4.X==Y 10. X\==Y 5. 1 + 1 = 2 H.X=\= Y 6.2 = 1+1 12.1+2 =\= 1-2 17. sin(X) =:= sin(2+Y) 14. 1 =< 2 1 5. sin(X) is sin(2) 16. sin(X) = sin(2+Y) Nápověda: '='/2 unifikace, '=='/2 test na identitu, '=:='/2 aritmetická rovnost, '\=='/2 negace testu na identitu, '=\='/2 aritmetická nerovnost Hana Rudová, Logické programování I, 9. března 2010 20 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? sl(0,X,X). sl(s(X),Y,s(Z)):-sl(X,Y,Z). s2(X,Y,Z):- Z is X + Y. Hana Rudová, Logické programování I, 9. března 2010 21 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? sl(0,X,X). sl(s(X),Y,s(Z)):-sl(X,Y,Z). s2(X,Y,Z):- Z is X + Y. sl/3 je vícesměrný- umí sčítat, odečítat, generovat součty, ale pracuje jen s nezápornými celými čísly s2/3 umí pouze sčítat, ale také záporná a reálná čísla Hana Rudová, Logické programování I, 9. března 2010 21 Backtracking, unifikace, aritmetika Operátory Definice operátorů umožňuje přehlednější infixový zápis binárních a unárních predikátů, příklad: definice op(l 200,Y,':-') umožňuje zápis a:-print(s(s(0))),b,c). pro výraz :-(aM(print(s(s(0)))M(b,c))). Prefixovou notaci lze získat predikátem display/l. Vyzkoušejte ch'splay((a:-print(s(s(0))) ,b,c)) . di spiay(a+b+c-d-e*f*g-h+i). display([l,2,3,4,5]). Definice standardních operátorů najdete na konci manuálu. Hana Rudová, Logické programování I, 9. března 2010 22 Backtracking, unifikace, aritmetika Závěr Dnešní látku jste pochopili dobře, pokud víte -• jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci, -• jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (příklad nevlastni_bratr/2), -• k čemu dojde po unifikaci X=a(X), M proč neuspěje dotaz ?- X=2, sin(X) is sin(2). -• za jakých předpokladů uspějí tyto cíle X=Y, X==Y, X=:=Y, -• a umíte odvodit pomocí substitučních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 9. března 2010 23 Backtracking, unifikace, aritmetika