IB013 Logické programování (průsvitky ze cvičení) Hana Rudová jaro 2013 Backtracking, unifikace, aritmetika Syntaxe logického programu Term: M univerzální datová struktura (slouží také pro příkazy jazyka) M 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, 1 5. května 201 3 3 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu Program: množina predikátů (v jednom nebo více souborech). M Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity M 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. M 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, 15. května 201 3 4 Backtracking, unifikace, aritmetika SICStus Debugging - My Prolog Project/my_nnodule.pro - Eclipse SDK File Edit SICStus Source Navigate Search Project Run Favorites Window Help- fil $ SICStus Debu... | • " % Debug sTX^ % D> DD I ^ 3. ^ .(» ^, ^ v ° ^ M= Variables E^X^** Breakpoints] to *í B ^ " n> ^ Prolog Top-level Configuration [SICStus Launch Configuration Type 1] 5» Prolog Target Name Value ♦ Suff [a, _7551, c] = call: suffix[[a,_7551,c],_181u] ❖ X _iaio = rny_predlL1810] [:. Prolog Top-level Process rny_module,pro S3 ^ /* Mode:Prolog \n°- Outline V ir.o d-al e (my_mo dul e, [ my_pre dl /1, my pred3/.3 * rams about exporting undefined predicate ]> ■ usemodule(library(lists), [postfix/5, * yarns about importing undefined predicate suffix/2 4 integrated help (also for user predicatesJ 1[ la Q my_predl/l ■v rny_pred2/2 suffixPList ?SuffbO istrue 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 improved Eater!) my_predl(X) :- Suff = [a,Singleton,c], assert(seen xs(X)), £ warns about missing declaration (here dynamic/1) suffix {Suff, X), prelude(Suff, X). $ warns about calling undefined predicate ir.y_pred2 (S, Xs) :- $ varn about non-trivial singleton variables ( foreach(Y,Xs} do write(S, X3) > , ( foreach(Y,Xs}, parair. ( [5] ) do write(S, Xs) > ■ □ SICStus ^^-g] Tasks] BE Problems]^ i. dp ^ m ^ m ~ ° g n ľoptevel 1 in C:/Users/perm,SlCS-AD/runtime-EclipseApplication42/My Prolog Project 2 2 Exit: assert (ray_niodule : seen_xs (_1810)) ? 3 2 Call: suffix([a, 7551,c], 1810) ? I Hana Rudová, Logické programování I, 1 5. května 201 3 5 Backtracking, unifikace, aritmetika SICStus Prolog: spouštění programu M UNIX: module add sicstus-4.1.3 eclipse % použiváni IDE SPIDER sicstus % použiváni přes při kazový řádek MS Windows: M používání IDE SPIDER: C:\Eclipse3.7\eclipse.exe - Shortcut příkazový řádek: z nabídky All Programs -> SICStus Prolog VC1 0 4.2.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. M 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\SICStus Prolog VC10 4.2.3\bin\sicstus-4.2.3.exe" návod: http://www. si cs. se/sicstus/spider/site/prerequi sites. html#Setti ngLIp Hana Rudová, Logické programování I, 15. května 201 3 6 Backtracking, unifikace, aritmetika SICStus Prolog: konzultace M Otevření souboru: File->Open File 3 Přístup k příkazové řádce pro zadávání dotazů: SICStus->Open Toplevel M 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'). M V Eclipse lze nastavit Key bindings, pracovní adresář, ... Hana Rudová, Logické programování I, 1 5. května 201 3 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,1enka). ?- predek(X,Y). Každý příkaz ukončujeme tečkou. 3 Přerušení a zastavení cyklícího programu: pomocí ikony Restart Prolog p* z okna Toplevel Hana Rudová, Logické programování I, 1 5. května 201 3 8 Backtracking, unifikace, aritmetika Příklad rodokmen rodič (pet r, filip). rodic(petr, lenka). rodi c(pavel, j an). 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(fi lip). muz(pavel). muz(jan). muz(adam). muz(tomas). muz(mi chal). muz(radek). zena(eva). zena(lenka). zena(pavla). zena(jana). zena(vera). muz(Otec). Hana Rudová, Logické programování I, 1 5. května 201 3 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? M Je Petr otcem Jana? Kdo je otcem Petra? M Jaké děti má Pavla? Ma Petr dceru? M Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 1 5. května 201 3 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 Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů Středníkem si vyžádáme další řešení | ?- otec(petr,1enka). 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 5. května 201 3 | ?- 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(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty (pomocí rodic/2, muz/1, zena/l) prababi cka(Prababi cka,Pravnouce) neviastni_bratr(Nevlastni_bratr,Nevíastni_sourozenec) nápověda: využijte X \== Y (X a Y nejsou identické) Hana Rudová, Logické programování I, 1 5. května 201 3 12 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 (pomocí rodic/2, muz/1, zena/l) 3 prababicka(Prababicka,Pravnouce) neví astni_bratr(Nevlastni_bratr,Nevíastni_sourozenec) nápověda: využijte X \== Y (X a Y nejsou identické) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodič), zena(Prababicka), rodi c(Prarodi c,Rodi c), rodi c(Rodi c,Pravnouce). Hana Rudová, Logické programování I, 15. května 2013 12 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II neviastni_bratr(Bratr,Sourozenec):-rodi c(X,Bratr), muz(Bratr), rodic(X,Sourozenec), /* tento test neni nutný, ale zvyšuje efektivitu * Bratr \== Sourozenec, rodi c(Y,Bratr), Y \== X, rodic(Z,Sourozenec), Z \== X, Z \== Y. / /* nevhodné umisteni testu - vypočet "bloudi" v neúspěšných větvich */ nevlastni_bratr2(Bratr,Sourozenec):-rodi c(X,Bratr), rodic(X,Sourozenec), rodi c(Y,Bratr), rodic(Z,Sourozenec), Y \== X, Z \== X, Z \== Y, muz(Bratr). Hana Rudová, Logické programování I, 1 5. května 201 3 1 3 Backtracking, unifikace, aritmetika Backtracking: porovnání 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 M varianta 1: testy co nejdříve správně varianta 2: všechny testy umístěte na konec chybně Co uvidíme po nahrazení predikátu rodic/2 predikátem rodic_v/2 v predikátech nevlastni_bratr/2 a nevlastni_bratr2/2 a spuštění? Hana Rudová, Logické programování I, 1 5. května 201 3 14 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, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). M Zkuste předem odhadnout (odvodit) pořadí, v jakém budou nalezeni potomci Pavly? :- potomek(X,pavla). M Jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci? rodic(petr, filip). rodic(petr, lenka). rodic(pavel, 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). Hana Rudová, Logické programování I, 1 5. května 201 3 16 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). /* varianta lb - jine poradi odpovědi, neprimi potomci maji přednost */ Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). /* varianta lb - jine poradi odpovědi, neprimi potomci maji přednost */ potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). /* varianta lb - jine poradi odpovědi, neprimi potomci maji přednost */ potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovědi, pak cykli */ Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). /* varianta lb - jine poradi odpovědi, neprimi potomci maji přednost */ potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovědi, pak cykli */ potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). Hana Rudová, Logické programování I, 1 5. května 201 3 Backtracking, unifikace, aritmetika Backtracking: řešení III potomek(Potomek,Předek):-rodi c(Predek,Potomek). potomek(Potomek,Předek):-rodi c(Předek,X),potomek(Potomek,X). /* varianta la */ potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodi c(Predek,Potomek). /* varianta lb - jine poradi odpovedi, neprimi potomci maji přednost */ potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovedi, pak cykli */ potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ Hana Rudová, Logické programování I, 15. května 2013 17 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, 1 5. května 201 3 18 Backtracking, unifikace, aritmetika Unifikace:při 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, 15. května 2013 18 Backtracking, unifikace, aritmetika Mechanismus unifikace 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 5. května 201 3 19 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, 15. května 201 3 20 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) . kolik je 1+1? ?- suma(s(0) ,s(0) ,X) . M test je Jan otcem Petra? ?- otec(jan, petr) . Je 1+1 2??- suma(s(0) ,s(0) ,s((0)) ). M 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 D.Ú. 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 5. května 201 3 21 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 unifiková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, 15. května 201 3 22 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 11. 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 5. května 201 3 23 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, 1 5. května 201 3 24 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 i s 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 5. května 201 3 24 Backtracking, unifikace, aritmetika Závěr Dnešní látku jste pochopili dobře, pokud víte M 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), M 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, M 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 5. května 201 3 25 Backtracking, unifikace, aritmetika Seznamy, řez Reprezentace seznamu M Seznam: [a, b, c], prázdný seznam [] M Hlava (libovolný objekt), tělo (seznam): . (Hlava, Telo) 3 všechny strukturované objekty stromy - i seznamy 3 funktordva argumenty * .(a, .(b, .(c, []))) = [a, b, c] 3 notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] M Lze psát i: [a,b|Telo] M před "|" je libovolný počet prvků seznamu , za "|" je seznam zbývajících prvků M [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] 3 pozor: [ [a,b] I [c] ] ^ [ a,b | [c] ] Seznam jako neúplná datová struktura: [a,b,c|T] 3 Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 15. května 201 3 27 Seznamy, řez Cvičení: append/2 append( [], S, S ). % (1) append( [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 Hana Rudová, Logické programování I, 1 5. května 201 3 28 Seznamy, řez Cvičení: append/2 append( [], S, S ). % (1) append( [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) | B=[2|C] => A=[1,2|C] :- append([],[3,4],C)■ I (D | 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 I _S2 ], S) Hana Rudová, Logické programování I, 1 5. května 201 3 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: M prefix( SI, S2 ) :-DÚ: suffix(Sl,S2) Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) last( X, S ) :- append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) M last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) M last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] M memberC X, 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) Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) M last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] M 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) Hana Rudová, Logické programování I, 1 5. května 201 3 29 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: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) M last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] M 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) :- Hana Rudová, Logické programování I, 1 5. května 201 3 29 Seznamy, řez Seznamy a append appendC [], S, S ) . append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3). Napište následující predikáty pomocí append/3: M prefix( SI, S2 ) :- append( SI, _S3, S2). DÚ: suffix(Sl,S2) M last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] memberC 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) M % 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, 15. května 201 3 29 Seznamy, řez Optimalizace posledního volání M Last Call Optimization (LCO) Implementační technika snižující nároky na paměť M Mnoho vnořených rekurzivních volání je náročné na paměť M 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: M procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule M cíle předcházející tomuto rekurzivnímu volání musí být deterministické M p( ...):-.. . % žádné rekurzivní voláni v těle klauzule p( ...):- ... % žádné rekurzivni voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus M Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 1 5. května 201 3 30 Seznamy, řez LCO a akumulátor M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ). length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO. Hana Rudová, Logické programování I, 15. května 201 3 31 Seznamy, řez LCO a akumulátor M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ). length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO. M Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' Hana Rudová, Logické programování I, 1 5. května 201 3 31 Seznamy, řez LCO a akumulátor M Reformulace rekurzivní procedury, aby umožnila LCO M Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ). length( [ H | T ], Délka ) :- length( T, Del kaO ), Délka is 1 + DelkaO. M Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): length( Seznam, Délka ) :- length( Seznam, 0, Délka ). % pomocný predikát length ( [H | T ] , A, Délka ) :- AO is A + 1, length ( T, AO, Del ka ). M Přídavný argument se nazývá akumulátor CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam length( [] , Délka, Délka ). Hana Rudová, Logické programování I, 1 5. května 201 3 31 Seznamy, řez Akumulátor a sum_l i st(S, Sum) ?- sum_~h'st( [2,3,4], Sum ). s akumulátorem: sum_list( S, Sum ) :- sum_list( S, 0, Sum ). sum_list( [], Sum, Sum ). sum_list( [H|T], A, Sum ) :- Al i s A + H, sum_list( T, Al, Sum). Hana Rudová, Logické programování I, 1 5. května 201 3 32 Seznamy, řez Výpočet faktoriálu f act(N, F) s akumulátorem: Hana Rudová, Logické programování I, 1 5. května 201 3 33 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 is N - 1, fact( Nl, Al, F ). Hana Rudová, Logické programování I, 1 5. května 201 3 33 Seznamy, řez r(X):-wri te(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) : -wri te(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). 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). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X) r (X r (X r (X P (X P (X P (X a (X a (X b (X b (X c (X c (X d (X d (X -wri te(rl). -p(X),write(r2) -write(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) -write(pl) . -a(X),b(X), ! , c(X) ,d(X) ,write(p2). & řez v predikátu p/1 neovlivní alternativy -write(P3). predikátu r/1 -write(al). ^ dokud nebyl proveden řez, alternativy -write(a2). „ „ predikátu a/l se uplatňuji, pr. neúspech - x > o, write(bl). b/1 v dotazu (3) - X < 0, write(b2). M při neúspěchu cíle za řezem se výpočet - X mod 2 =:= 0, write(cl). - - i i - j - /i ■ /i\ navrací az k volající proceduře r/1, viz (1) - X mod 3 =:= 0, write(c2). alternativy vzniklé po provedení řezu se - abs(X) < 10, write(dl). , , N zachovávají - další možnosti predikátu - write(d2). c/1 viz (2) a (4) Hana Rudová, Logické programování I, 15. května 201 3 34 Seznamy, řez 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 > 0, write(bl). b(X):- X < 0, 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). r(X):-wri te(rl). r(X):-p(X),write(r2). r(X):-wri te(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 > 0, write(bl). b(X):- X < 0, 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). r(X):-write(rl). rl r(X):-p(X),write(r2) . X = 1 ? ; r(X):-wri te(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 > 0, write(bl). b(X):- X < 0, 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). r(X):-wri te(rl). r(X):-p(X),write(r2). r(X):-wri te(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 > 0, write(bl). b(X):- X < 0, 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 ? ; I ?- X=l,r(X) r(X):-write(rl). rl r(X):-p(X),write(r2) . X = 1 ? ; r(X):-write(r3). plr2 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 > 0, write(bl). b(X):- X < 0, 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). X = 1 ? ; alblr3 X = 1 ? ; I ?- X=l,r(X) r(X):-write(rl). rl r(X):-p(X),write(r2) . X = 1 ? ; r(X):-write(r3). plr2 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 > 0, write(bl). b(X):- X < 0, 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). X = 1 ? ; alblr3 X = 1 ? ; no I ?- X=l,r(X) r(X):-write(rl). rl r(X):-p(X),write(r2) . X = 1 ? ; r(X):-write(r3). plr2 p(X):-write(pl). p(X):-a(X),b(X),!, c(X) ,d(X) ,write(p2) p(X):-write(p3). X = 1 ? ; alblr3 X = 1 ? ; no a(X):-write(al). , ?_ x=0>r(x) a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, 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) r(X):-write(rl). rl r(X):-p(X),write(r2) . X = 1 ? ; r(X):-write(r3). plr2 p(X):-write(pl). p(X):-a(X),b(X),!, c(X) ,d(X) ,write(p2) p(X):-write(p3). X = 1 ? ; alblr3 X = 1 ? ; no a(X):-write(al). , ?_ x=0>r(x) a(X):-write(a2). ^ b(X):- X > 0, write(bl). X = 0 ? ; b(X):- X < 0, 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). r(X) :-wri te(rl). rl r(X) :-p(X), wri te(r2). X = 1 ? ; r(X) :-write(r3). plr2 P(X) :-write(pl). X = 1 ? ; P(X) :-a(X),b(X),!, alblr3 c(X) ,d(X) ,write(p2) . X = 1 ? ; P(X) :-write(p3). no a(X) :-write(al). 1 ?- X=0,r(X). a(X) :-write(a2). rl b(X) : - X > 0, write(bl) . X = 0 ? ; b(X) :- X < 0, write(b2) . plr2 X = 0 ? ; 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) : - wri te(d2) . I ?- X=l,r(X). r(X) :-wri te(rl). rl r(X) :-p(X), wri te(r2). X = 1 ? ; r(X) :-write(r3). plr2 P(X) :-write(pl). X = 1 ? ; P(X) :-a(X),b(X),!, alblr3 c(X) ,d(X) ,write(p2) . X = 1 ? ; P(X) :-write(p3). no a(X) :-write(al). 1 ?- X=0,r(X). a(X) :-write(a2). rl b(X) : - X > 0, write(bl) . X = 0 ? ; b(X) :- X < 0, write(b2) . plr2 X = 0 ? ; c(X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c(X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d(X) :- abs(X) < 10, write(dl). d(X) : - wri te(d2) . I ?- X=l,r(X). r(X) :-wri te(rl). rl r(X) :-p(X), wri te(r2). X = 1 ? ; r(X) :-write(r3). plr2 P(X) :-write(pl). X = 1 ? ; P(X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P(X) :-write(p3). no a(X) :-write(al). 1 ?- X=0,r(X). a(X) :-write(a2). rl b(X) : - X > 0, write(bl) . X = 0 ? ; b(X) :- X < 0, write(b2) . plr2 X = 0 ? ; c(X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c(X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d(X) :- abs(X) < 10, write(dl). r3 d(X) : - wri te(d2) . X = 0 ? ; I ?- X=l,r(X). r(X) :-wri te(rl). rl r(X) :-p(X), wri te(r2). X = 1 ? ; r(X) :-write(r3). plr2 P(X) :-write(pl). X = 1 ? ; P(X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P(X) :-write(p3). no a(X) :-write(al). 1 ?- X=0,r(X). a(X) :-write(a2). rl b(X) : - X > 0, write(bl) . X = 0 ? ; b(X) :- X < 0, write(b2) . plr2 X = 0 ? ; c(X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c(X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d(X) :- abs(X) < 10, write(dl). r3 d(X) : - wri te(d2) . X = 0 ? ; no ?- X=l,r(X) r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 P (X) :-write(pl). X = 1 ? ; P (X) :-a(X),b(X),!, alblr3 c (X) ,d(X) ,write(p2) . X = 1 ? ; P (X) :-write(p3). no a (X) :-write(al). 1 ?- X=0,r(X). a (X) :-write(a2). rl b (X) : - X > 0, write(bl) . X = 0 ? ; b (X) :- X < 0, write(b2) . plr2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; ?- X=3,r(X) no ?- X=l,r(X) r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 P (X) :-write(pl). X = 1 ? ; P (X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P (X) :-write(p3). no a (X) :-write(al). 1 ?- X=0,r(X). a (X) :-write(a2). rl b (X) : - X > 0, write(bl) . X = 0 ? ; b (X) :- X < 0, write(b2). plr2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X=3,r(X) rl X = 3 ? ; ?- X=l,r(X) r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 P (X) :-write(pl). X = 1 ? ; P (X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P (X) :-write(p3). no a (X) :-write(al). 1 ?- X=0,r(X). a (X) :-write(a2). rl b (X) : - X > 0, write(bl) . X = 0 ? ; b (X) :- X < 0, write(b2) . plr2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; I ?- X=3,r(X) rl X = 3 ? ; plr2 X = 3 ? ; no ?- X=l,r(X) r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 P (X) :-write(pl). X = 1 ? ; P (X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P (X) :-write(p3). no a (X) :-write(al). 1 ?- X=0,r(X). a (X) :-write(a2). rl b (X) : - X > 0, write(bl) . X = 0 ? ; b (X) :- X < 0, write(b2). plr2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X=3,r(X) rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; ?- X=l,r(X) r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 P (X) :-write(pl). X = 1 ? ; P (X) :-a(X),b(X),!, alblr3 c (X) ,d(X) ,write(p2) . X = 1 ? ; P (X) :-write(p3). no a (X) :-write(al). 1 ?- X=0,r(X). a (X) :-write(a2). rl b (X) : - X > 0, write(bl) . X = 0 ? ; b (X) :- X < 0, write(b2) . plr2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X=3,r(X) rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2) . plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X= -6, r(X). I ?- X=l,r(X). r(X) :-wri te(rl). rl r(X) :-p(X), wri te(r2). X = 1 ? ; r(X) :-write(r3). plr2 P(X) :-write(pl). X = 1 ? ; P(X) :-a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; P(X) :-write(p3). no a(X) :-write(al). 1 ?- X=0,r(X). a(X) :-write(a2). rl b(X) : - X > 0, write(bl) . X = 0 ? ; b(X) :- X < 0, write(b2). plr2 X = 0 ? ; c(X) :- X mod 2 =:= 0, write(cl). ala2p3r2 c(X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; d(X) :- abs(X) < 10, write(dl). r3 d(X) : - wri te(d2) . X = 0 ? ; no I ?- X= -6, r(X). rl I ?- X=3,r(X). X = -6 ? ; rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X= -6, r(X). rl X = -6 ? ; plr2 X = -6 ? ; 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X),wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no I ?- X= -6, r(X). rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; 1 ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X),wri te(r2). X = 1 ? ; r (X) :-write(r3). plr2 1 ?- X=3,r(X). P (X) :-write(pl). X = 1 ? ; rl P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; c(X),d(X),write(p2). X = 1 ? ; 7 plr2 P (X) :-write(p3). no X = 3 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 a (X) :-write(a2). rl X = 3 ? ; d2p2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no ?- X= -6, r(X) rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r (X r (X r (X P (X P (X ■write(rl) . ■p(X), wri te(r2). ■write(r3) . ■write(pl) . -a(X),b(X),!, c(X),d(X),write(p2) I ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; I ?- X=3,r(X). rl X = 3 ? ; plr2 ?- X= -6, r(X) rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 P (X) :-write(p3). no X = 3 ? ; X = -6 ? a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 d2p2r2 a (X) :-write(a2). rl X = 3 ? ; X = -6 ? d2p2r2 c2dlp2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; X = -6 ? b (X) :- X < 0, write(b2). plr2 r3 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no r (X r (X r (X P (X P (X ■write(rl) . ■p(X), wri te(r2). ■write(r3) . ■write(pl) . -a(X),b(X),!, c(X),d(X),write(p2) I ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; I ?- X=3,r(X). rl X = 3 ? ; plr2 ?- X= -6, r(X) rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 P (X) :-write(p3). no X = 3 ? ; X = -6 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 d2p2r2 a (X) :-write(a2). rl X = 3 ? ; X = -6 ? ; d2p2r2 c2dlp2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; X = -6 ? ; b (X) :- X < 0, write(b2). plr2 r3 d2p2r2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; X = -6 ? ; c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no r (X r (X r (X P (X P (X -write(rl) . ■p(X),wri te(r2). ■write(r3) . ■write(pl) . -a(X),b(X),!, c (X) ,d(X) ,write(p2) I ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; I ?- X=3,r(X). rl X = 3 ? ; plr2 ?- X= -6, r(X) rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 P (X) :-write(p3). no X = 3 ? ; X = -6 ? ; a (X) :-write(al). 1 ?- X=0,r(X). alblc2dlp2r2 d2p2r2 a (X) :-write(a2). rl X = 3 ? ; X = -6 ? ; d2p2r2 c2dlp2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; X = -6 ? ; b (X) :- X < 0, write(b2) . plr2 r3 d2p2r2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; X = -6 ? ; r3 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no X = -6 ? ; d (X) :- abs(X) < 10, write(dl). r3 d (X) : - wri te(d2) . X = 0 ? ; no | ?- X=l,r(X). r (X) :-wri te(rl). rl r (X) :-p(X), wri te(r2). 1 ?- X= - -6, r(X) X = 1 ? ; i ■ * % rl r (X) :-write(r3). plr2 | ?- X=3,r(X). X = -6 ? P (X) :-write(pl). X = 1 ? ; rl plr2 P (X) :-a(X),b(X),!, alblr3 X = 3 ? ; X = -6 ? « c(X),d(X),write(p2). X = 1 ? ; plr2 alb2cldlp2r2 P (X) :-write(p3). no X = 3 ? ; X = -6 ? j a (X) :-write(al). | ?- X=0,r(X). alblc2dlp2r2 d2p2r2 a (X) :-write(a2). rl X = 3 ? ; X = -6 ? j d2p2r2 c2dlp2r2 b (X) : - X > 0, write(bl) . X = 0 ? ; X = 3 ? ; X = -6 ? j b (X) :- X < 0, write(b2). plr2 r3 d2p2r2 X = 0 ? ; c (X) :- X mod 2 =:= 0, write(cl). ala2p3r2 X = 3 ? ; X = -6 ? j r3 c (X) :- X mod 3 =:= 0, write(c2). X = 0 ? ; no X = -6 ? d (X) :- abs(X) < 10, write(dl). r3 no d (X) : - wri te(d2) . X = 0 ? ; no Hana Rudová, Logické programování I, 1 5. května 201 3 35 Seznamy, řez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Hana Rudová, Logické programování I, 1 5. května 201 3 36 Seznamy, řez Rez: 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. Hana Rudová, Logické programování I, 1 5. května 201 3 36 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 5. května 201 3 36 Seznamy, řez Řez: 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). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). Hana Rudová, Logické programování I, 1 5. května 201 3 37 Seznamy, řez Řez: 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). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). M 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) Hana Rudová, Logické programování I, 1 5. května 201 3 37 Seznamy, řez Řez: 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). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). M 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é Hana Rudová, Logické programování I, 1 5. května 201 3 37 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? 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 5. května 201 3 37 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 5. května 201 3 37 Seznamy, řez Rez: del ete deleteC X, [X|S], S ). deleteC X, [Y|S], [Y|S1] ) :- delete(X,S,SI). Napište predikát delete(X,S,Sl), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspěje). Hana Rudová, Logické programování I, 1 5. května 201 3 38 Seznamy, řez Rez: delete deleteC X, [X|S], S ). deleteC 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). deleteC _X, [] , [] ). deleteC X, [X|S], SI ) :- !, delete(X,S,SI). deleteC X, [Y|S], [Y|S1] ) :- delete(X,S,SI). Hana Rudová, Logické programování I, 1 5. května 201 3 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 5. května 201 3 39 Seznamy, řez 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_file, i ■ » seen, see( StarySoubor ). repeat. repeat :- repeat. 6 zjištěni aktivního proudu vo otevřeni souboru Soubor vo čteni termu Term vo manipulace s termem vo je konec souboru? vo uzavřeni souboru 6 aktivace původního proudu 6 vestavěný predikát Hana Rudová, Logické programování I, 1 5. května 201 3 41 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 M seeing, see, seen, read telling, tell, told, write see/tel1(Soubor) M pokud Soubor není otevřený: otevření a aktivace 3 pokud Soubor otevřený: pouze aktivace (tj. udělá z něj aktivní vstupní/výstupní stream) standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 1 5. května 201 3 42 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. | ?- uloz_do_souboru( 'soubor.pl' ). |: fakt(mi rek, 18). |: fakt(pavel,4). |: end_of_file. | ?- 1 isting(fakt/2) . % pozor:listing/1 lze použít pouze při consult/1 (ne u compile/1) fakt(mi rek, 18). fakt(pavel, 4). yes | ?- consult(soubor). yes yes Hana Rudová, Logické programování I, 1 5. května 201 3 43 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeing( StaryVstup ), telling( StaryVystup ), see( user ), tel 1( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_fi1e, i ■ j seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_fi 1e) :- !. process_term( Term ) :- write( Term ), write('.'), nl. Hana Rudová, Logické programování I, 1 5. května 201 3 44 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: assert( 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 5. května 201 3 45 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). |: pravid~lo(X,Y) :- fakt(X,Y). |: end_of_fi1 e. yes | ?- 1 isting(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clause( pravidlo (A, B) , C) . % cl ause/2 použitelný pouze pro dynamické klauzule C = fakt(A,B) ? yes Hana Rudová, Logické programování I, 1 5. května 201 3 46 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_fi1e, i ■ j seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assert( Term ). Hana Rudová, Logické programování I, 1 5. května 201 3 47 Vstup/výstup, databázové operace, rozklad termu Konstrukce a dekompozice termu M 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 ) fu ncto r(atom,atom,0) i functor(l,l,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 1 5. května 201 3 48 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu Term je proměnná (var/1), atom nebo číslo (atomic/1) => konec rozkladu M Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu Term je složený (=. ./2 , functor/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ělo ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2, [a(l,3),b,c])). no yes Hana Rudová, Logické programování I, 1 5. května 201 3 49 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 M 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 M otestujte :- subterm(l,2) . pokud nepoužijeme (compound/1), pak tento dotaz cyklí M otestujte :- subterm(a, [1,2]) . ověřte, zda necyklí (nutný červený řez níže) | ?- subterm(sin(3),b(c,2,[1,b],sin(3),a)). yes Hana Rudová, Logické programování I, 1 5. května 201 3 50 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 M 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 M otestujte :- subterm(l,2) . pokud nepoužijeme (compound/1), pak tento dotaz cyklí M otestujte :- subterm(a, [1,2]) . ověřte, zda necyklí (nutný červený řez níže) | ?- subterm(sin(3),b(c,2,[1,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 5. května 201 3 50 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 M A i B jsou proměnné NEBO M pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO M A i B jsou atomic a unifikovatelné NEBO M A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO M A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([1,3,sin(X),s(a,3)],[l,3,sin(X),s(a,3)]). yes Hana Rudová, Logické programování I, 1 5. května 201 3 51 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 M A i B jsou proměnné NEBO M pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO M A i B jsou atomic a unifikovatelné NEBO M A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO -M A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([1,3,si n(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes same(A,B) same(A,B) same(A,B) same(A,B) same(A,B) - var(A), var(B), !. - var(A), !, fai1. - var(B), !, fail. - atomic(A), !, atomic(B), A==B. - atomi c(B), !, fai1. Yo jen kvůli vyšši efektivitě 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 5. května 201 3 51 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)),s(a,3)],[l,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes Hana Rudová, Logické programování I, 1 5. května 201 3 52 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). | ?- unify([Y,3,sin(a(3)),s(a,3)],[l,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes unify(A,B) unify(A,B) unify(A,B) unify(A,B) unify(A,B) - 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. - atomi c(B), !, fai1. unify([HA|TA],[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 5. května 201 3 52 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 3 B je atom nebo číslo NEBO B je proměnná různá od A NEBO 3 B je seznam a A se nevyskytuje ani v těle ani v hlavě NEBO 3 B je složený term a A se nevyskytuje v jeho argumentech Hana Rudová, Logické programování I, 1 5. května 201 3 53 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 M 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 5. května 201 3 53 Vstup/výstup, databázové operace, rozklad termu Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z( Jméno, Prijmem' , Pohlavi , Vek, Prace, F i rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,ji rku,m,40,mechanik,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(hana,ji rku,z,35,kuchařka,zs_stara). z(roman,maly,m,35,manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,ji rku,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). M Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_S,_V,_Pr,_F),L). ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L ). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,_S,V,Pr,F) , L). Hana Rudová, Logické programování I, 1 5. května 201 3 55 Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z( Jméno, Prijmem' , Pohlavi , Vek, Prace, F i rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,ji rku,m,40,mechanik,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(hana,ji rku,z,35,kuchařka,zs_stara). z(roman,maly,m,35,manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,ji rku,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). M Najděte jméno a příjmení všech lidí. ?- findal1(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_S,_V,_Pr,_F),L). ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L ). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,_S,V,Pr,F) , L). Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs ?- findal1( c(J,P,Firma), ( z(J,P,Firma), ( Firma=skoda ; Firma=cs ) ), ?- bagof( J-P, [S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( P-J, [S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 1 5. května 201 3 5 5 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findallC c(PJ), z(P, 3 ,z,_,_,_) , L) , length(L,N). ?- findallC c(PJ), z(P, 3 ,m, _,_,_) , L) , 1 ength(L, N) . Hana Rudová, Logické programování I, 1 5. května 201 3 56 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findalK c(PJ), z(P, 3 , z,_,_,_) , L) , 1 ength(L, N) . ?- findalK c(PJ), z(P, 3 ,m,_,_,_) , L) , length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]az(P,3,S,Ve,Pr,Fi), L), 1ength(L,N). Hana Rudová, Logické programování I, 1 5. května 201 3 56 Všechna řešení, třídění, rozdílové seznamy Všechna řešení Kolik žen a mužů je v databázi? ?- findalK c(PJ), z(P, 3 , z,_,_,_) , L) , 1 ength(L, N) . ?- findalK c(PJ), z(P, 3 ,m,_,_,_) , L) , length(L,N). ?- bagof(c(P,J), [Ve,Pr,Fi]az(P,3,S,Ve,Pr,Fi), L), 1ength(L,N). ?- findalK S-N, ( bagof (c(P, J) , [Ve, Pr, Fi]az(P, 3 ,S,Ve, Pr, Fi) , L) , length(L,N) ), Dvojice ). Hana Rudová, Logické programování I, 1 5. května 201 3 56 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? Hana Rudová, Logické programování I, 1 5. května 201 3 57 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Přijmeni, z(_,Přijmeni,z,_,_,_), L). Hana Rudová, Logické programování I, 1 5. května 201 3 57 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) \= vs. @< 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, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). Hana Rudová, Logické programování I, 1 5. května 201 3 57 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) \= vs. @< 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, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). Hana Rudová, Logické programování I, 1 5. května 201 3 57 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) \= vs. @< 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findal1(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findal1(Jmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setofCP-J, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findal1(Prijmeni, ( z(_,PrijmeniP,zs_stara), (P=ucitel;P=ucitelka) ), L). Hana Rudová, Logické programování I, 1 5. května 201 3 57 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) \= vs. @< 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, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-J, [S,V,Pr,F]AzO,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@30 ), L). 3. setof(P-J, [S,V,Pr,F]AzO,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 5. května 201 3 57 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; a seřaďte SI pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam swap(S,Sl) rekurzivně bubblesortem bubblesort(S,Sorted) :- swap(S,SI), !, bubblesort(Sl, Sorted) bubblesort(Sorted,Sorted). % Existuje použitelný swap v S? % Jinak je seznam seřazený swap([X,YI Rest],[Y,X|Rest]) : X>Y. swap([X|Rest],[XIRestl]) :-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 5. května 201 3 58 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] 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 např. vyberte hlavu S split(X,Seznam,Small,Big) seřaďte Small do SortedSmall rekurzivně quicksortem seřaďte Big do SortedBig rekurzivně quicksortem setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování I, 1 5. května 201 3 59 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že M 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 M seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append quicksort([] , []) . quicksort([X|T], Sorted) : - split(X, T, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmal1, [X|SortedBig], Sorted) Hana Rudová, Logické programování I, 1 5. května 201 3 59 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že M 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 M seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] např. vyberte hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append quicksort([] , []) . quicksort([X|T], Sorted) :- split(X, T, Small, Big), quicksort(Smal1, SortedSmall), quicksort(Big, SortedBig), append(SortedSmal1, [X|SortedBig], Sorted) split(X, [], [], []). 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 5. května 201 3 59 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, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insert(X,SortedT,Sorted) Hana Rudová, Logické programování I, 1 5. května 201 3 60 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=[] M seřaďte tělo T seznamu S rekurzivně insertsortem M 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, !, insert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování I, 1 5. května 201 3 60 Všechna řešení, třídění, rozdílové seznamy 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 A1 Z1 A2 Z2 V V v \ L1 L2 ^-^ L3 ^ ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, Al-[]). 3 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 5. května 201 3 61 -[], [l,2,3,4,5]-[] ). Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [], [] ). reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). Hana Rudová, Logické programování I, 1 5. května 201 3 62 Všechna řešení, třídění, rozdílové seznamy 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, ). reverseO( [], ). reverseO( [ H | T ], ) :- reverseO( T, ). Hana Rudová, Logické programování I, 1 5. května 201 3 62 Všechna řešení, třídění, rozdílové seznamy 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 5. května 201 3 62 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 3 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 M seřaďte Small do SortedSmall 3 seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S, ). quicksortl( [] , ) . quicksortl([X|T], ) :- spi i t(X, T, Small, Big), qui cksortl(Smal1, ), quicksortl(Big, ). appendCAl-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování I, 1 5. května 201 3 63 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 M 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 M seřaďte Small do SortedSmall M seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). qui cksortl( [],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), quicksortKSmall , A1-[X|Z1]) , qui cksortl(Bi g, Z1-Z2). append(Al-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování I, 1 5. května 201 3 63 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,15,12] Hana Rudová, Logické programování I, 1 5. května 201 3 64 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,15,12] pal indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 1 5. května 201 3 64 Všechna řešení, třídění, rozdílové seznamy Logické programování s omezujícími podmínkami Algebrogram 3 Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: * ruzna písmena mají přiřazena různé cifry M S a M nejsou 0 * Proměnné: S,E,N,D,M,O,R,Y 3 Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y 1 omezení pro nerovnost: all_distinct([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 5. května 201 3 66 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram DONALD + GERALD = ROBERT Struktura programu algebrogram( [D,0,N,A,L,G,E,R,B,T] ) domai n(...), all_distinct(...), ... #= 1abeli ng(...). % domény proměnných % omezeni % prohledáváni stavového prostoru Knihovna pro CLP(FD) :- use_module(libraryCclpfd)) Domény proměnných Omezení Aritmetické omezení domain( Seznam, MinValue, MaxValue ) all_distinct( Seznam ) A*B + C #= D Procedura pro prohledávání stavového prostoru Hana Rudová, Logické programování I, 1 5. května 201 3 67 1abeli ng([],Seznam) 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 5. května 201 3 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 Hana Rudová, Logické programování I, 1 5. května 201 3 69 Omezující podmínky 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,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 3 1 2 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 5. května 201 3 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(Začátky) :- domény(Ukoly,Začátky,Tasks), cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky). domeny(Ukoly,Zacatky,Tasks) :- findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,Mi nStart,MaxKonec), Ukoly), nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování I, 15. května 201 3 70 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- připrav(Ukoly,Zacatky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([] ,[],[]). připrav([ukol(Id,Doba,MinStart,MaxKonec)|Úkoly], [Z|Zacatky], [ukol(Id,Doba,MinStart,MaxKonec,Z)|Vstup]) :-připrav(Ukoly,Zacatky,Vstup). ti skni([]) :- nl . tiskni([V|Vystup]) :- V=ukol(Id,Doba,MinStart,MaxKonec,Z), K is Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 1 5. května 201 3 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), quicksortlCSmall, 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 5. května 201 3 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í cumulati ve/l, jejíž prvky jsou úlohy ve tvaru task(Zacatek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Začátky,-Tasks) Hana Rudová, Logické programování I, 1 5. května 201 3 73 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í cumulati ve/l, jejíž prvky jsou úlohy ve tvaru task(Zacatek,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 i s MaxKonec-Doba, Z in MinStart..MaxStart, K #= Z + Doba, nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování I, 1 5. května 201 3 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)). Hana Rudová, Logické programování I, 1 5. května 201 3 74 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([přec(A,B)|Přec],Tasks) :-nthl(A,Tasks,task(ZA,DA,_KA,1,A)), nthl(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Přec,Tasks). Hana Rudová, Logické programování I, 1 5. května 201 3 74 Omezující podmínky Kumulativní rozvrhování M cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [limit(Limit)]) 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 Hana Rudová, Logické programování I, 1 5. května 201 3 75 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)],[li mi t(3)]) Hana Rudová, Logické programování I, 1 5. května 201 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že M 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) ukoly(Zacatky) :- % původně domény(Ukoly,Začátky,Tasks), cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky). ukoly_lide(Začátky) :- % upravená verze domeny(Ukoly,Začátky,Tasks), 1 i de(Tasks,Li de), 1abeli ng([],Začátky), ti skni_li de(Li de,Úkoly,Začátky). Hana Rudová, Logické programování I, 15. května 201 3 76 Omezující podmínky Plánování a lidé % 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]). Hana Rudová, Logické programování I, 1 5. května 201 3 77 Omezující podmínky Plánování a lidé % clovek(Id,Kapacita,IdUkoly) % človek 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]). 1 i de(Tasks,Lide) :- findal1(clovek(Kdo,Kapacita,Úkoly),clovek(Kdo,Kapacita,Úkoly), Lide), omezeni_li de(Li de,Tasks). omezeni_1i de([],_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 5. května 201 3 77 Omezující podmínky Plánování a lidé (pokračování) Napište predikát omezeni _clovek(UkolyCloveka, Kapacita, Tas ks), který ze seznamu Tasks vybere úlohy určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou člověka Kapacita. Pro nalezení úlohy v Tasks lze použít nthl(N ,Tasks, NtyPrvek) z knihovny :- use_module(library(lists)). Hana Rudová, Logické programování I, 1 5. května 201 3 78 Omezující podmínky Plánování a lidé (pokračování) Napište predikát omezeni _clovek(UkolyCloveka, Kapacita, Tas ks), který ze seznamu Tasks vybere úlohy určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou člověka Kapacita. Pro nalezení úlohy v Tasks lze použít nthl(N,Tasks, NtyPrvek) z knihovny :- use_module(library(lists)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni _clovek(UkolyCloveka,Kapaci ta,Tas ks,[]). omezeni_clovek([],Kapacita,_Tasks,TasksC) :- cumulative(TasksC,[li mi t(Kapacita)]). omezeni_clovek([UIUkolyCloveka],Kapacita,Tasks,TasksC) :- nthl(U,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování I, 1 5. května 201 3 78 Omezující podmínky 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ří M Adrianě Strejčkové Další podklady byly připraveny M Alešem Horákem M Miroslavem Nepilem Evou Žáčkovou M Janem Ryglem Hana Rudová, Logické programování I, 1 5. května 201 3 79 Poděkováni