IB01 3 Logické programování I (průsvitky ze cvičení) Hana Rudová jaro 2011 Backtracking, unifikace, aritmetika Syntaxe logického programu Term: ■ univerzální datová struktura (slouží také pro příkazy jazyka) ■ definovaný rekurzivně ■ 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) ■ složený term: funktor, arita, argumenty struktury jsou opět termy Hana Rudová, Logické programování I, 1 3. května 2011 3 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu ■ 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. ■ př. otec(Otec,Dite) :- rodic(Otec,Dite), muz(Otec). rodic(petr, jana). :- otec(Otec, jana). Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování I, 1 3. května 2011 4 Backtracking, unifikace, aritmetika .# SICStus Debugging - My Prolog Project/my_mcdule.pro - Eclipse SDK File Edit SICStus Source Navigate Search Project Run Favorites Window Help H * El ilii i X ý SICStus Debu... | P- Debug ^ u> DD ■ : - 3. ^ .g % | ^ § = □ ' 00= Variables !Sľ\í% Breakpoints] B v ° -J Prolog Top-level Configuration [SICStus Launch Configuration Typel] JjS Prolog Target Name Value <» Suff [a, _7551, c] = call: suffix([a,_7551,c],_181(l} ❖ X _1810 = my_predl(_131u] Prolog Top-le/el Process 1 $ my_module,pro £3 \^ /* Mode .-Prolog V : - ico dul e [ mymndul [nty_p r e dl/1, my pred3/,3 f if=rns aiout ejtportina undefined predicate ]J ■ - u3e_reoduIe (lifcrary (lists), (pcstf ±x./2, f irarni atoout importing undefined predicate suffix/£ t integrated help (also for user predicates) a- Outline \^ O my_predl/l ■ft- rny_preti2/2 suffrxPList ?Suffbd istruewrhen List and Suffix are lists and Suffix is a suffix of List. It terminates only if List i: proper, and has at most N+l solutions. Suffixes are enumerated in descending order of length, (documentation formatting will be improved tat er!)_ rr.y_predl [X) : - Suff = [a,Singleton,c], assert (seen xs (X) ) , £ varus aiioufc missing' declaration ^fcere dynajiic/ij suffix(Suff, X), prelude(Suff, X). ¥ varus aiout calling undefined predicate rr_y_predS (£, Xs) :- * yarn aiiout non-trivial singleton variables ( foreach[YjrXs) do write(S, Xs} do forea.cn (Y,Xs) , param( [S] ) write(S, Xs} ) ■ - SICStus £3 . ^ Tasks] [I, Problems Toplevel 1 in C:/Users/perm.SICS-AD/runtime-EclipseAppNcation42/My Prolog Project 2 2 Exit: assert [iry_module : seen_xs (_131Q)} ? 3 2 Call: suffix([a,7551,c],1810) ? | rn Hana Rudová, Logické programování I, 1 3. května 2011 5 Backtracking, unifikace, aritmetika SICStus Prolog: spouštění programu UNIX: module add sicstus-4.1.3 eclipse % použiváni IDE SPIDER sicstus % použiváni pres při kazový řádek MS Windows: ■ používání IDE SPIDER: z nabídky All Programs -> IDE -> Eclipse 3.6 ■ příkazový řádek: z nabídky All Programs -> IDE-> SICStus 4.1.3 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. Iniciální nastavení SICStus IDE v Eclipse pomocí Help->Cheat Sheets->lnitial set up of paths to installed SICStus Prolog s cestou "C:\Program Files (x86)\SICStus Prolog VC9 4.1.3\bin\sicstus.exe" návod: http://www.sics.se/sicstus/spider/site/prerequisites.html#SettingLIp Hana Rudová, Logické programování I, 1 3. května 2011 6 Backtracking, unifikace, aritmetika SICStus Prolog: konzultace Otevření souboru: File->Open File Přístup k příkazové řádce pro zadávání dotazů: SICStus->Open Toplevel Načtení programu: tzv. konzultace přímo z Menu: SICStus->Consult Prolog Code (okno s programem aktivní) nebo zadáním na příkazový řádek po uložení souboru (Ctrl+S) ?- consult(rodokmen). pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofů ?- consult('D:\prolog\moje\programy\rodokmen.pl'). V Eclipse lze nastavit Key bindings, pracovní adresář, ... Hana Rudová, Logické programování I, 1 3. května 2011 7 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 okně TopLevel, kurzor musí být na konci posledního řádku s | ?-), př. ?- predek(petr,lenka). ?- predek(X,Y). Každý příkaz ukončujeme tečkou. ■ Přerušení a zastavení cyklícího programu: pomocí ikony Restart Prolog p* z okna Toplevel Hana Rudová, Logické programování I, 1 3. května 2011 8 Backtracking, unifikace, aritmetika Příklad rodokmen rodic(petr, filip). muz(petr). rodic(petr, lenka). muz(filip). rodi c(pavel, j an). muz(pavel). rodic(adam, petr). muz(jan). rodic(tomas, michal). muz(adam). rodic(michal, radek). muz(tomas). rodic(eva, filip). muz(mi chal). rodic(jana, lenka). muz(radek). rodic(pavla, petr). rodi c(pavla, tomas). zena(eva). rodic(lenka, vera). zena(lenka). zena(pavla). zena(jana). zena(vera). otec(Otec,Dite) :- rodic(Otec,Dite), muz(Otec). Hana Rudová, Logické programování I, 1 3. května 2011 9 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, 1 3. května 2011 10 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 Rudová, Logické programování I, 1 3. května 2011 | ?- otec(0tec,Syn),muz(Syn). Syn = filip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = mi chal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- 11 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Předek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty ■ prababicka(Prababicka,Pravnouce) ■ neviastni_bratr(Neviastni_bratr,Nevíastni_sourozenec) nápověda: využijte X \== Y (X a Y nejsou identické) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababička,Prarodič), zena(Prababicka), rodi c(Prarodi c,Rodi c), rodi c(Rodi c,Pravnouce). Hana Rudová, Logické programování I, 1 3. května 2011 12 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodi c(X,Bratr), muz(Bratr), rodi c(X,Sou rozenec), /* tento test neni nutný, ale zvyšuje efektivitu */ Bratr \== Sourozenec, rodi c(Y,Bratr), Y \== X, rodi c(Z,Sou rozenec), Z \== X, Z \== Y. /* nevhodné umisteni testu - vypočet "bloudi" v neúspěšných větvich nevíastni_bratr2(Bratr,Sourozenec):-rodi c(X,Bratr), rodi c(X,Sou rozenec), rodi c(Y,Bratr), rodic(Z,Sourozenec), Y \== X, Z \== X, Z \== Y, muz(Bratr). Hana Rudová, Logické programování I, 1 3. května 2011 13 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? ■ 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):-rodič(X,Y),print(X),print('? '). 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, 1 3. května 2011 14 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta la */ potomek(Potomek,Předek):-rodic(Předek,Potomek) . potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). /* varianta lb - jine poradi odpovedi, neprimi potomci maji 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),rodic(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Předek):-potomek(Potomek,X),rodic(Predek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 1 3. května 201 1 1 5 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? 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, 1 3. května 2011 16 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, 1 3. května 2011 1 7 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, 1 3. května 2011 18 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),Z1) 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(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, 1 3. května 2011 19 Backtracking, unifikace, aritmetika Vícesměrnost predikátů Logický program lze využít vícesměrně, například jako ■ výpočet kdo je otcem Petra??- otec(X, petr) . kolikje 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, 1 3. května 2011 20 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é instaciovány čí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 ">="/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 nejdříve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování I, 13. května 2011 21 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ů by ty neúspěšné případně špatné uspěly? 1. 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 1 1. X =\= Y 6. 2 = 1 + 1 1 2. 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, 1 3. května 2011 22 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, 1 3. května 2011 23 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:-přint(s(s(0))),b,c). pro výraz :-(a,,(print(s(s(0))),,(b,c))). Prefixovou notaci lze získat predikátem display/l. Vyzkoušejte display((a:-přint(s(s(0))),b,c)). d i s play(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, 1 3. května 2011 24 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), ■ 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, 1 3. května 2011 25 Backtracking, unifikace, aritmetika Seznamy, řez Reprezentace seznamu ■ Seznam: [a, b, c], prázdný seznam [] ■ Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) ■ všechny strukturované objekty stromy - i seznamy ■ funktordva argumenty ■ .(a, .(b, .(c, []))) = [a, b, c] ■ notace: [ Hlava | Telo ] = [a | Tel o] Tel o je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] ■ Lze psát i: [a,b|Telo] ■ před "I"je libovolný počet prvků seznamu , za"|"je seznam zbývajících prvků ■ [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] ■ pozor: [ [a,b] | [c] ] + [ a,b | [c] ] ■ Seznam jako neúplná datová struktura: [a,b,c|T] ■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 13. května 201 1 27 Seznamy, řez Cvičení: append/2 append( [], S, S ). % (1) appendC [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). % (2) :- append([l,2],[3,4],A). I (2) I A=[1|B] :- append([2],[3,4],B). I (2) I B=[2|C] => A=[1,2|C] :- append([],[3,4],C). I (D I C=[3,4] => A=[l,2,3,4], yes Předchůdce a následník prvku X v seznamu S hledej(S,X,Pred,Po) :- append( _S1, [ Pred,X,Po | _S2 ], S) Hana Rudová, Logické programování I, 1 3. května 2011 28 Seznamy, řez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). Napište následující predikáty pomocí append/3: ■ prefixC SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2) ■ last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] ■ member( X, S ) :- append( SI, [X|S2], S ). append([3,4,l], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) ■ % sublist(+S,+ASB) sublist(S,ASB) :- append( AS, B, ASB ), append( A, S, AS ). POZOR na efektivitu, bez append lze často napsat efektivněji Hana Rudová, Logické programování I, 13. května 201 1 29 Seznamy, řez Optimalizace posledního volání ■ Last Call Optimization (LCO) ■ Implementační technika snižující nároky na paměť ■ Mnoho vnořených rekurzivních volání je náročné na paměť ■ Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky ■ Typický příklad, kdy je možné použití LCO: ■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule ■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické ■ p( ...):- ... % žádné rekurzivní voláni v těle klauzule p( ...):- ... % žádné rekurzivni voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus ■ Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 1 3. května 2011 30 Seznamy, řez LCO a akumulátor Reformulace rekurzivní procedury, aby umožnila LCO Výpočet délky seznamu length( Seznam, Délka ) length( [] , 0 ) . length( [ H | T ], Délka ) :- length( T, DelkaO ), Délka is 1 + DelkaO. Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + počet prvků v Seznam'' length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát length( [] , Délka, Délka ). % celková délka = započítaná délka length( [ H | T ], A, Délka ) :- A0 is A + 1, length( T, A0, Délka ). Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 1 3. května 2011 31 Seznamy, řez Akumulátor a sum_l i st(S, Sum) ?- sum_list( [2,3,4], Sum ). bez akumulátoru: sum_li st( [], 0 ). sum_list( [H|T], Sum ) :- sum_list( T, SumT ), Sum is H + SumT. s akumulátorem: sum_list( S, Sum ) :- sum_list( S, 0, Sum ). sum_list( [], Sum, Sum ). sunuli st( [H|T], A, Sum ) :- AI is A + H, sum_list( T, AI, Sum). Hana Rudová, Logické programování I, 1 3. května 2011 32 Seznamy, řez Výpočet faktoriálu fact(N, F) s akumulátorem: fact( N, F ) :- fact (N, 1, F ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, Al is N * A, Nl i s N - 1, fact( Nl, Al, F ). Hana Rudová, Logické programování I, 1 3. května 2011 33 Seznamy, řez r (X) r (X) r (X) -wri te(rl) . -p(X),write(r2) -wri te(r3) . Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si středníkem vyžádejte navracení): (1) X=l,r(X). (2) X=3,r(X). (3) X=0,r(X). (4) X= -6,r(X) p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). ■ fez v predikátu p/1 neovlivní alternativy p(X):-write(P3). predikátu r/1 a(X):-write(al). ■ dokud nebyl proveden řez, alternativy a(X) :-write(a2). ... ..... predikátu a/l se uplatňuji, pr. neúspech b(X):- X > 0, write(bl). b/1 v dotazu (3) b(X):- X < 0, write(b2). 1 při neúspěchu cíle za řezem se výpočet navrací až k volající proceduře r/1, viz (1) 1 alternativy vzniklé po provedení řezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4) Hana Rudová, Logické programování I, 13. května 201 1 34 Seznamy, řez c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). I ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no I ?- X=0,r(X) rl X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ? no I ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no I ?- X= -6, r rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no Hana Rudová, Logické programování I, 1 3. května 2011 35 Seznamy, řez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Není, následující dotaz uspěje: ?- max(2 ,1,1). Uveďte dvě možnosti opravy, se zachováním použití řezu a bez. max(X,Y,X) :-X>=Y. max(X, Y, Z) : -X>=Y, ! ,Z=X. max(X,Y,Y):-Y>X. max(X,Y,Y). Problém byl v definici, v první klauzuli se tvrdilo: X=Z a X>=Y => true správná definice je: X>=Y => Z=X Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu. Hana Rudová, Logické programování I, 1 3. května 2011 36 Seznamy, řez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). ■ meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) ■ mem2/2 najde jenom první výskyt, taky váže proměnné ■ mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty? mem4(H,[K|_]) :- H==K. mem4(H,[K|T]) :- mem4(H,T). mem2(H,[H|_]) mem2(H,[_|T]) mem2(H,T). mem3(H,[K|_]) :- H==K. mem3(H,[K|T]) :- H\==K, mem3(H,T). Hana Rudová, Logické programování I, 1 3. května 201 1 37 Seznamy, řez Rez: delete delete( X, [X|S], S ). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,SI). Napište predikát delete(X, S, SI), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspěje). delete( _X, [] , [] ). delete( X, [X|S], SI) :- !, delete(X,S,SI). delete( X, [Y|S], [Y|S1] ) :- delete(X,S,SI). Hana Rudová, Logické programování I, 1 3. května 2011 38 Seznamy, řez Seznamy: intersection(A,B,C) DÚ: Napište predikát pro výpočet průniku dvou seznamů. Nápověda: využijte predikát member/2 DÚ: Napište predikát pro výpočtu rozdílu dvou seznamů. Nápověda: využijte predikát member/2 Hana Rudová, Logické programování I, 1 3. května 2011 39 Seznamy, řez Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z(Jmeno, Při jmeni ,Pohlavi,Vek,Prače, Fi rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,novy,m,40,mechanik,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretářka,škoda). z(jana,dankova,z,35,asi stentka,škoda). z(lenka,meri nska,z,35,ucetni,škoda). z(roman,maly,m,35,manažer,cs). z(alena,novotna,z,40,uci telka,zs_stara). z(davi d,novy,m,30,uci tel,zs_stara). z(petra,spi ckova,z,45,uklizecka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, zQmeno, Pri jmeni,_,_,_,_), L) ■ ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a zQmeno, Pri jmeni , S ,V, Pr, F) , L ). ■ Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs ?- findall( c O, P, Firma), ( z O , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), ?- bagof( J-P, [S,V,Pr]a(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( P-J, [S,V,Pr]a(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 1 3. května 2011 41 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findalK c(P,J), z(P, J , z,_,_,_) , L) , length(L, N) . ?- findalK c(P,J), z(P, J ,m,_,_,_) , L), length(L,N). ?- bagof(c(P, J) , [Ve,Pr,Fi]Az(P,J,S,Ve,Pr,Fi), L), length(L,N). ?- findalK S-N, ( bagof (c(P, J) , [Ve, Pr, Fi]Az(P, J ,S,Ve, Pr, Fi) , L) , length(L,N) ), Dvoj i ce ). Hana Rudová, Logické programování I, 1 3. května 2011 42 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( zQmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-J, [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). 4. findal1(Přijmeni, ( z(_,PřijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(Jl-P,J2-P), ( z(Jl,P,m,_,_,_),z(J2,P,m,_,_,_), J1@l ), S). Hana Rudová, Logické programování I, 1 3. května 201 1 43 Všechna řešení, třídění, rozdílové seznamy bubblesort(S,Sorted) Seznam S seřaďte tak, že ■ nalezněte první dva sousední prvky X a Y v S tak, že X>Y, vyměňte pořadí X a Y a získate SI; swap(S,Sl) a seřaďte SI rekurzivně bubblesortem ■ pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam bubblesort(S,Sorted) :- swap (S,S1), !, % Existuje použitelný swap v S? bubblesort(Sl, Sorted). bubblesort(Sorted,Sorted). % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Restl]) :-X>Y. swap([X|Rest],[X|Restl]) :-swap(Rest,Restl). % swap prvnich dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické programování I, 1 3. května 2011 44 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že ■ vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky ■ seřaďte Small do SortedSmall ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S spi it(X, Seznam, Small,Big) rekurzivně quicksortem rekurzivně quicksortem append qui cksort ([] , []) . quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted) splitCX, [], [], []). split(X, [Y|T], [Y|Small], Big) :- X>Y, !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). Hana Rudová, Logické programování I, 1 3. května 2011 45 Všechna řešení, třídění, rozdílové seznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že konec rekurze pro S=[] ■ seřaďte tělo T seznamu S rekurzivně insertsortem ■ vložte hlavu X do seřazeného těla tak, insert(X,SortedT,Sorted) že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insertsort([], []) . insertsort([X|T],Sorted) :- insertsort(T,SortedT), % seřazeni těla insert(X,SortedT,Sorted). % vloženi X na vhodné místo insert(X,[Y|Sorted],[Y|Sortedl]) :-X > Y, !, i nsert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování I, 1 3. května 2011 46 Všechna řešení, třídění, rozdílové seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] ... L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L Z1 A2 L3 ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, Al-[]). append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 append( [l,2,3,4,5]-[4,5], [4,5]-[], Hana Rudová, Logické programování I, 1 3. května 201 1 47 [l,2,3,4,5]-[] ). Všechna řešení, třídění, rozdílové reverse(Seznam, Opacny) % kvadratická složitost reverse( [] , [] ) . reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineárni složitost, rozdilové seznamy reverse( Seznam, Opacny ) :- reverseO( Seznam, Opacny-[] ). reverseO( [], S-S ). reverseO( [ H | T ], Opacny-OpacnyKonec ) :- reverseO( T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 1 3. května 2011 48 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že ■ vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky ■ seřaďte Small do SortedSmall ■ seřaďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), qui cksortKSmal 1 , AI- [X | A2]) , quicksortl(Big, A2-Z2). append(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 1 3. května 201 1 49 Všechna řešení, třídění, rozdílové seznamy DÚ: pal i ndrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,1 5,1 2] pal indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 1 3. května 2011 50 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Ctení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1e, i ■ » seen, see( StarySoubor ). repeat. repeat :- repeat. % zjištěni aktivniho proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % vestavěný predikát Hana Rudová, Logické programování I, 1 3. května 2011 52 Vstup/výstup, databázové operace, rozklad termu Predikáty pro vstup a výstup I ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme I ?- write(a(l)), write('.'), nl, write(a(2)), write('.'), nl. a(l). a(2). yes ■ seeing, see, seen, read ■ telling, tell, told, write ■ standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 1 3. května 2011 53 Vstup/výstup, databázové operace, rozklad termu Příklad: vstup/výstup Napište predikát uloz_do_souboru( Soubor ), který načte několik fakt ze vstupu a uloží je do souboru Soubor. I ?- uloz_do_souboru( 'soubor.pl' ). I: fakt(mi rek, 18). I: fakt(pavel,4). I: end_of_file. yes I ?- consult(soubor). % consulting /home/hanka/soubor.pi... % consulted /home/hanka/soubor.pi in module user, 0 msec % 376 bytes yes I ?- 1 isting(fakt/2) . % pozor:listing/1 lze použít pouze při consult/1 (ne u compile/1) faktOnirek, 18). fakt(pavel, 4). yes Hana Rudová, Logické programování I, 1 3. května 2011 54 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeing( StaryVstup ), tellingC StaryVystup ), see( user ), tell( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1 e, i ■ > seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- write( Term ), write('.'), nl. Hana Rudová, Logické programování I, 1 3. května 201 1 55 Vstup/výstup, databázové operace, rozklad termu Databázové operace Databáze: specifikace množiny relací Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly) Vestavěné predikáty pro změnu databáze během provádění programu: assertC Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule Pozor: retract/1 lze použít pouze pro dynamické klauzule (přidané pomocí assert) a ne pro statické klauzule z programu Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 1 3. května 2011 56 Vstup/výstup, databázové operace, rozklad termu Databázové operace: příklad Napište predikát vytvor_program/0, který načte několik klauzulí ze vstupu a uloží je do programové databáze. | ?- vytvor_program. |: fakt(pavel, 4). |: pravidlo(X,Y) :- fakt(X,Y). |: end_of_file. yes | ?- listing(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clause( pravidlo(A, B) , C) . % clause/2 použitelný pouze pro dynamické klauzule C = fakt(A,B) ? yes Hana Rudová, Logické programování I, 1 3. května 2011 57 Vstup/výstup, databázové operace, rozklad termu Databázové operace: implementace vytvo r_p rog ram :- seeing( StaryVstup ), see( user ), repeat, read( Term ), uloz_term( Term ), Term == end_of_fi1 e, i ■ > seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assert( Term ). Hana Rudová, Logické programování I, 1 3. května 2011 58 Vstup/výstup, databázové operace, rozklad termu Konstrukce a dekompozice termu ■ Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], call( Cil ) atom =. . X => X = [atom] ■ Pokud chci znát pouze funktor nebo některé argumenty, pak je efektivnější: functor( Term, Funktor, Arita ) functor( a(9,e), a, 2 ) functor(atom,atom,0) ) functor(l,l,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 1 3. května 2011 59 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu Term je proměnná (var/1), atom nebo číslo (atomic/1) => konec rozkladu Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu Term je složený (=. ./2 , f unctor/3) => procházení seznamu argumentů a rozklad každého argumentu Příklad: ground/1 uspěje, pokud v termu nejsou proměnné; jinak neuspěje ground(Term) :- atomic(Term), !. % Term je atom nebo číslo NEBO ground(Term) :- var(Term), !, fail. % Term není proměnná NEBO ground([H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani těl ground(Term) % neobsahuji proměnné NEBO Term =.. [ _Funktor | Argumenty ], % je Term složený ground( Argumenty ). % a jeho argumenty % neobsahuji proměnné ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2,[a(l,3),b,c])). no Hana Rudová, Logické programování I, 1 3. května 2011 60 yes Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S a T bez proměnných, které uspějí, pokud je S podtermem termu T. Tj. musí platit alespoň jedno z ■ podterm S je právě term T NEBO ■ podterm S se nachází v hlavě seznamu T NEBO ■ podterm S se nachází v těle seznamu T NEBO ■ T je složený term (compound/1) a S je podtermem některého argumentu T ■otestujte :- subterm(l, 2) . pokud nepoužijeme (compound/1), pak tento dotaz cyklí ■otestujte :- subterm(a, [1,2]) . ověřte, zda necyklí (nutný červený řez níže) | ?- subterm(sin(3),b(c,2,[l,b],sin(3),a)) . yes subterm(T,T) :- ! . subterm(S,[H|_]) :- subterm(S,H), !. subterm(S, [_|T]) :- !, subterm(S,T) . subterm(S,T) :- compound(T), T=..[_|Argumenty], subterm(S,Argumenty). Hana Rudová, Logické programování I, 1 3. května 2011 61 Vstup/výstup, databázové operace, rozklad termu same(A,B) Napište predikát same(A, B), který uspěje, pokud mají termy A a B stejnou strukturu. Tj. musí platit právě jedno z ■ A i B jsou proměnné NEBO ■ pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO ■ A i B jsou atomic a u n ifi kováte Iné NEBO ■ A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO ■ A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([l,3,sin(X),s(a,3)],[l,3,sin(X),s(a,3)]). yes same(A,B) :- var(A), var(B), !. same(A,B) :- var(A), !, fail. same(A,B) :- var(B), !, fail. same(A,B) :- atomic(A), atomic(B), !, A==B. same([HA|TA],[HB|TB]) :- !, same(HA,HB), same(TA,TB). same(A,B) :- A=..[F|ArgA], B=..[F|ArgB], same(ArgA,ArgB). Hana Rudová, Logické programování I, 1 3. května 2011 62 Vstup/výstup, databázové operace, rozklad termu D.Ú. unify (A, B) Napište predikát unify(A, B), který unifikuje termy A a B a provede zároveň kontrolu výskytu pomocí not_occurs(Var,Term). I ?- unify([Y,3,sin(a(3)),sCa,3)],[l,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes unify(A,B) unify(A,B) unify(A,B) fy(A,B) um uni - var(A), var(B), !, A=B. - var(A), !, not_occurs(A,B), A=B. - var(B), !, not_occurs(B,A), B=A. - atomic(A), atomic(B), !, A==B. fy([HAITA],[HBITB]) :- !, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[F|ArgA], B=..[F|ArgB], unify(ArgA,ArgB). Hana Rudová, Logické programování I, 1 3. května 2011 63 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A, B) uspěje, pokud se proměnná A nevyskytuje v termu B. Tj. platí jedno z ■ B je atom nebo číslo NEBO ■ B je proměnná různá od A NEBO ■ B je seznam a A se nevyskytuje ani v těle ani v hlavě NEBO ■ B je složený term a A se nevyskytuje v jeho argumentech not_occurs(_,B) :- atomic(B), !. not_occurs(A,B) :- var(B), !, A\==B. not_occurs(A,[H|T]) :- !, not_occurs(A,H), not_occurs(A,T). not_occurs(A,B) :- B=..[_|Arg], not_occurs(A,Arg). Hana Rudová, Logické programování I, 1 3. května 201 1 64 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Algebrogram ■ Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: ■ různá písmena mají přiřazena různé cifry ■ S a M nejsou 0 ■ Proměnné: S,E,N,D,M,O,R,Y ■ Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y ■ 1 omezení pro nerovnost: all_di sti nct([S, E,N, D,M,0, R, Y]) ■ 1 omezení pro rovnosti: SEND + MORE MONEY 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE #= 10000*M + 1000*0 + 100*N + 10*E + Y MONEY Hana Rudová, Logické programování I, 1 3. května 2011 66 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram DONALD + GERALD = ROBERT Struktura programu algebrogramC [D,0,N,A,L,G,E,R,B,T] ) domai n(...), all_dis tinct(...), ... #= labeling(...). % domény proměnných % omezeni % prohledáváni stavového prostoru Knihovna pro CLP(FD) Domény proměnných Omezení Aritmetické omezení :- use_module(library(clpfd)) domain( Seznam, MinValue, MaxValue ) all_distinct( Seznam ) Procedura pro prohledávání stavového prostoru A*B + C #= D labeling([],Seznam) Hana Rudová, Logické programování I, 1 3. května 2011 67 Omezující podmínky Algebrogram: řešení :- use_module(library(clpfd)). donald(LD):- % domény LD=[D,0,N,A,L,G,E,R,B,T], domain(LD,0,9), domain([D,G,R],1,9), % omezeni all_distinct(LD), 100000-D + 10000*0 + 1000*N + 100*A + 10*L + D 100000*G + 10000*E + 1000*R + 100*A + 10*L + D #= 100000*R + 10000*0 + 1000*B + 100*E + 10*R + T, % prohledáváni stavového prostoru labeling([] ,LD) . Hana Rudová, Logické programování I, 1 3. května 2011 68 Disjunktivní rozvrhování (unární zdroj) cumulative([task(Start, Duration, End, 1, Id) | Tasks]) Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly ■ příklad s konstantami: cumulative([task(0,2,2,1,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) Start, Duration, End, Id musí být doménové proměnné s konečnými mezemi nebo celá čísla Hana Rudová, Logické programování I, 1 3. května 2011 69 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejdřívější čas, kdy může být zahájen. Nalezněte startovní čas každého úkolu tak, aby se jednotlivé úkoly nepřekrývaly. Úkoly jsou zadány následujícím způsobem: % ukol(Id,Doba,Mi nStart,MaxKonec) ukol(1,4,8,70). ukol(2,2,7,60). ukol(3,1,2,25). ukol(4,6,5,55). ukol(5,4,1,45). ukol(6,2,4,35). ukol(7,8,2,25) . ukol(8,5,0,20). ukol(9,1,8,40). ukol(10,7,4,50). ukol(11,5,2,50). ukol(12,2,0,35). ukol(13,3,30,60). ukol(14,5,15,70). ukol(15,4,10,40). Kostra řešení: ukoly(Zacatky) :- domeny(Ukoly,Zacatky,Tasks), cumulative(Tasks), 1abeli ng([],Začátky). domeny(Ukoly,Zacatky,Tasks) :- findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování I, 13. května 201 1 70 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- připrav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([], [] , []) . připrav([ukol(Id,Doba,MinStart,MaxKonec)|Úkoly], [Z|Zacatky], [ukol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :-připrav(Ukoly,Začátky,Vstup). ti skni([]) :- nl . tiskni([V|Vystup]) :- V=ukol(Id,Doba,Mi nStart,MaxKonec,Z), K is Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,Mi nStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 1 3. května 2011 71 Omezující podmínky Plánování: výstup II quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :- split(X, Tail, Small, Big), quicksortl(Small, A1-[X|A2]), quicksortl(Big, A2-Z2). split(_X, [], [], []). split(X, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 1 3. května 2011 72 Omezující podmínky Plánování a domény Napište predikát nastav_domeny/3, který na základě datové struktury [ukol (Id,Doba,MinStart,MaxKonec) | Úkoly] vytvoří doménové proměnné Začátky pro začátky startovních dob úkolů a strukturu Tasks vhodnou pro omezení cumul ati ve/l, jejíž prvky jsou úlohy ve tvaru task(Začátek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Začátky,-Tasks) nastav_domeny([],[],[]). nastav_domeny([ukol(Id,Doba,Mi nStart,MaxKonec)|Ukoly],[Z|Začátky], [task(Z,Doba,K,l,Id)ITasks]) :-MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, K #= Z + Doba, nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování I, 1 3. května 2011 73 Omezující podmínky D.Ú- Plánování a precedence: precedence(Tasks) Rozšiřte řešení předchozího problému tak, aby umožňovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno před B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,l). Pro určení úlohy vTasks lze použít nthl(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). precedence(Tasks) :- findal1(prec(A,B),prec(A,B),P), omezeni_precedence(P,Tasks). omezeni_precedence([],_Tasks). omezeni_precedence([prec(A,B)|Přec],Tasks) :- nthl(A,Tasks,task(ZA,DA,_KA,l,A)), nthl(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování I, 13. května 201 1 74 Omezující podmínky Kumulativní rozvrhování cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [li mi t(Li mi t)]) Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy nepřekročila Limit Příklad s konstantami: cumulative([task(0,4,4,l,l) , task(l,2, 3,2,2) , task(3, 3 ,6,2 , 3) , task(4,2 ,6,1,4)], [limit(3)]) 2 3 1 1 1 1 l 1 2 3 4 5 6 Hana Rudová, Logické programování I, 13. května 201 1 75 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že ■ odstraňte omezení na nepřekrývání úkolů ■ přidejte omezení umožňující řešení každého úkolu zadaným člověkem (každý člověk může zpracovávat nejvýše tolik úkolů jako je jeho kapacita) % clovek(Id,Kapacita,IdUkoly) ... clovek Id zpracovává úkoly v seznamu IdUkoly clovek(l,2,[1,2,3,4,5]). clovek(2,l,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). li de(Tasks,Lide) :- findall(clovek(Kdo,Kapacita,Úkoly),clovek(Kdo,Kapacita,Úkoly), Lide), omezeni_li de(Li de,Tasks). omezeni_lide([],_Tasks). omezeni_lide([clovek(_Id,Kapacita,UkolyCloveka)|Lide],Tasks) :-omezeni_clovek(UkolyCloveka,Kapacita,Tasks), omezeni_li de(Li de,Tasks). Hana Rudová, Logické programování I, 1 3. května 2011 76 Omezující podmínky Plánování a lidé (pokračování) Napište predikát omezeni_clovek(UkolyCloveka, Kapaci ta,Tasks) , který ze seznamu Tasks vybere úlohy určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezeni cumulative/2 s danou kapacitou člověka Kapacita. Pro nalezeni úlohy v Tasks lze použit nthl(N,Tasks,NtyPrvek) z kni hovny :- use_module(library(lists)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni_clovek(UkolyCloveka,Kapaci ta,Tasks,[]). omezeni_clovek([],Kapacita,_Tasks,TasksC) :- cumulative(TasksC,[li mi t(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nthl(U,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapaci ta,Tasks,[TU|TasksC]). Hana Rudová, Logické programování I, 13. května 201 1 77 Omezující podmínky Stromy, grafy Stromy Uzly stromu Tree jsou reprezentovány termy ■ tree(Left,Value,Right): Left a Right jsou opět stromy, Value je ohodnocení uzlu ■ leaf(Value): Value je ohodnoceni uzlu ■ Příklad: 6 / \ / \ / \ 2 8 / \ / 14 7 / \ 3 5 tree(tree(leaf(l), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) ) Hana Rudová, Logické programování I, 13. května 201 1 79 Stromy, grafy Stromy: hledáni prvku in(X,T) Predikát in(X,T) uspěje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve stromě T, jestliže ■ X je listem stromu T, jinak leaf(X) ■ X je kořen stromu T, jinak tree(Left,X,Right) ■ X je menší než kořen stromu T, pak se nachází v levém podstromu T, jinak ■ X se nachází v pravém podstromu T in(X, leaf(X)) :- ! . in(X, tree(_,X,_)) :- ! . in(X, tree(Left, Root, Right) ) :- XV, pak vznikne nový strom s kořenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(L,V,R) a XV, !. add(leaf(V), X, tree(leaf(X),V,[]) ) :- !. XV, !, add(R,X,Rl). add(tree(L,V,R), X, tree(Ll,V,R)) :- X true) 4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodic), ( nonvar(Rodic) -> true ; Rodi c = Uzel, arg(V,Graf,SousediV), prochazej_sousedy(Sousedi V,V,Graf,Parents) ), prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 13. května 201 1 88 Stromy, grafy DÚ: Procházení grafu do šířky Napište predikát bfs(U,G,P) pro procházení grafu G do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu G do šířky (pro každý uzel stromu známe jeho rodiče). graf([2,3],[1,3], [1,2]) . graf([2,4,6],[1,3],[2],[1,5],[4,6], [1,5]) . 1--2 1--2 5--4 5--4 \ I I II I \| | 6--1--2--3 6--1--2--3 3 3 11=4: rodic(4, 1, 2, empty, 4, 1) U=2: rodič(2,empty,2) Hana Rudová, Logické programování I, 1 3. května 2011 89 Stromy, grafy Poděkování Průsviky ze cvičení byly připraveny na základě materiálů dřívějších cvičících tohoto předmětu. Speciální poděkování patří ■ Adrianě Strejčkové Další podklady byly připraveny ■ Alešem Horákem ■ Miroslavem Nepilem ■ Evou Žáčkovou Hana Rudová, Logické programování I, 1 3. května 2011 90 Poděkováni