Vestavěné predikáty (pokračování) Všechna řešení II. Pokud neexistuje řešení bagof(X, P, S) neuspěje bagof: pokud nějaké řešení existuje několikrát, pak S obsahuje duplicity bagof, setof, findall: P je libovolný cíl vek( petr, 7 ). vek( anna, 5 ). vek( tomas, 5 ) . ?- bagofC Dite, ( vek( Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] bagof, setof, findall: na objekty shromažďované vX nejsou žádná omezení ?- bagofC Dite-Vek, vek( Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Všechna řešení ■ Backtracking vrací pouze jedno řešení po druhém ■ Všechna řešení dostupná najednou: bagof/3, setof/3, findall/3 ■ bagof ( X, P, S ): vrátí seznam S, všech objektů X takových, že P je splněno vek( petr, 7 ). vek( anna, 5 ). vek( tomas, 5 ). ?- bagofC Dite, vek( Dite, 5 ), Seznam ). Seznam = [ anna, tomas ] ■ Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagofC Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, 14. března 201 1 2 Existenční kvantifikátor „" " ■ Přidání existenčního kvantifikátoru ,," " => hodnota proměnné nemá význam ?- bagofC Dite, Vek"vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] ■ Anonymní proměnné jsou všeobecně kvantifikovány, i když jejich hodnota není (jako vždy) vracena na výstup ?- bagofC Dite, vek( Dite, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna,tomas] ■ Před operátorem ,," " může být i seznam ?- bagofC Vek ,[]meno,Prijmeni]"vek( ]meno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování I, 14. března 2011 3 Hana Rudová, Logické programování I, 14. března 201 1 4 Všechna řešení III. Testování typu termu ■ setof( X, P, S ): rozdíly od bagof ■ Sje uspořádaný podle @< ■ případné duplicity v S jsou eliminovány ■ findalK X, P, S ): rozdíly od bagof ■ všechny proměnné jsou existenčně kvantifikovány ?- findallf Dite, vek( Dite, Vek ), Seznam ). svS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou ■ výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S = [] ■ ?- bagof( Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findall( Dite, vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování I, 14. března 2011 5 Určení počtu výskytů prvku v seznamu count( X, S, N ) :- count( X, S, 0, N ). count( _, [], N, N ). count( X, [X|S], NO, N) :- !, NI is NO + 1, count( X, S, NI, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) N=3 :-? count( a, [a,b,X,Y], N). N=3 count( _, [], N, N ). count( X, [Y|S], NO, N ) :- nonvar(Y), X = Y, !, NI is NO + 1, count( X, S, NI, N ). count( X, [_|S], NO, N ) :- count( X, S, NO, N ). Hana Rudová, Logické programování I, 14. března 2011 Vestavěné predikáty var(X) X je volná proměnná nonvar(X) X není proměnná atom(X) X je atom (pavel, 'Pavel Novák', <-->) integer(X) X je integer Float(X) X je float atomic(X) X je atom nebo číslo compound(X) X je struktura Hana Rudová, Logické programování I, 14. března 201 1 Vestavěné predikáty Konstrukce a dekompozice atomu Atom (opakování) ■ řetězce písmen, čísel, „_" začínající malým písmenem: pavel, pavel_novak, x2 , x4_34 ■ řetězce speciálních znaků:+, <->, ===> ■ řetězce v apostrofech: ' Pavel ' , ?- 'ano'=A. A = ano Řetězec znaků v uvozovkách ■ př. "ano", "Pavel" ?- A="Pavel". A = [80,97,118,101,108] 'Pavel Novák' prsn ?- A="ano". A=[97,110,lll] ■ př. použití: konstrukce a dekompozice atomu na znaky, vstup a výstup do souboru Konstrukce atomu ze znaků, rozložení atomu na znaky name( Atom, SeznamASCIIKodu ) nameC ano, [97,110,111] ) Hana Rudová, Logické programování I, 14. března 201 1 name( ano, "ano" ) Vestavěné predikáty Konstrukce a dekompozice termu Rekurzivní rozklad 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 ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) arg( N, Term, Argument ) argC 2, a(9,e), e) Hana Rudová, Logické programování I, 14. března 2011 Vestavěné predikáty Příklad: dekompozice termu I. count_term( Integer, Term, N ) určí počet výskytů celého čísla v termu ■ ?- count_term( 1, a(l,2,b(x,z(a,b,1)),Y), N ). N=2 ■ count_term( X, T, N ) :- count_term( X, T, 0, N). count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N i s NO + 1. T, N, N ) :- atomic(T), !. T, N, N ) :- var(T), !. T, NO, N ) :- T =.. [ _ | Argumenty ], count_arg( X, Argumenty, NO, N ). count_arg( _, [], N, N ). count_arg( X, [ H | T ], NO, N ) :- count_term( X, H, 0, NI), N2 i s NO + NI, count_arg( X, T, N2, N ). ?- count_term( 1, [a,2,[b,c],[d,[e,f],Y]], N ). count_term( X, T, NO, N ) :- T = [_|_], !, count_arg( X, T, NO, N ). klauzuli přidáme před poslední klauzuli count_term/4 Hana Rudová, Logické programování I, 14. března 2011 Vestavěné predikáty Term je proměnná (var/l), atom nebo číslo (atomic/1) => konec rozkladu Term je seznam ([_ | _]) => []... řešen výše jako atomi c 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), !. ground(Term) :- var(Term), !, fail. groundC[H|T]) :- !, ground(H), ground(T). ground(Term) :- Term =.. [ _Funktor | Argumenty ], groundC Argumenty ). ?- ground(s(2,[a(l,3),b,c],X)). no ?- ground(s(2,[a(l,3),b,c])) . yes Hana Rudová, Logické programování I, 14. března 201 1 Vestavěné predikáty Cvičení: dekompozice termu Napište predikát substitute( Podterm, Term, Podterml, Terml), který nahradí všechny výskyty Podterm v Term termem Podterml a výsledek vrátí v Terml Předpokládejte, že Term a Podterm jsou termy bez proměnných ?- substitute( sin(x), 2*sin(x)*f(sin(x)), t, F ). F=2*t*f(t) Hana Rudová, Logické programování I, 14. března 201 1 Vestavěné predikáty Technika a styl programování v Prologu Technika a styl programování v Prologu Styl programování v Prologu ■ některá pravidla správného stylu ■ správný vs. špatný styl ■ komentáře Ladění Efektivita Styl programování v Prologu I. Cílem stylistických konvencí je ■ redukce nebezpečí programovacích chyb ■ psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují Některá pravidla správného stylu ■ krátké klauzule ■ krátké procedury; dlouhé procedury pouze s uniformní strukturou (tabulka) ■ klauzule se základními (hraničními) případy psát před rekurzivními klauzulemi ■ vhodnájmena procedur a proměnných ■ nepoužívat seznamy ([. . . ]) nebo závorky ({...}, (...)) pro termy pevné arity ■ vstupní argumenty psát před výstupními ■ struktura programu - jednotné konvence v rámci celého programu, např. ■ mezery, prázdné řádky, odsazení ■ klauzule stejné procedury na jednom místě; prázdné řádky mezi klauzulemi; každý cíl na zvláštním řádku Hana Rudová, Logické programování I, 14. března 2011 Technika a styl programování v Prologu Hana Rudová, Logické programování I, 14. března 201 1 14 Technika a styl programování v Prologu Správný styl programování konstrukce setříděného seznamu Seznam3 ze setříděných seznamů Seznámí, Seznam2: merge( Seznámí, Seznam2, Seznam3 ) merge( [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) merge( [], Seznam, Seznam ) merge( Seznam, [], Seznam ). % prevence redundantních řešení merge( [X|Telol], [Y|Telo2], [X|Te"lo3] ) :■ X < Y, !, merge( Telol, [Y|Telo2], Te"lo3 ). merge( Seznámí, [Y|Telo2], [Y|Te"lo3] ) :-merge( Seznámí, Te"lo2, Te"lo3 ). Hana Rudová, Logické programování I, 14. března 201 1 Technika a styl programování v Prologu Špatný styl programování Styl programování v Prologu II. merge( SI, S2, S3 ) 51 = [], ! , S3 = S2; 52 =[],!, S3 = SI 51 = [XI TI], 52 = [Y|T2], ( X < Y, !, Z = X, merge( TI, S2, T3 ); Z = Y, merge( SI, T2, T3) ), 53 = [ Z I T3 ]. % první seznam je prázdný % druhý seznam je prázdný % Z je hlava seznamu S3 Středník „;" může způsobit nesrozumitelnost klauzule ■ nedávat středník na konec řádku, používat závorky ■ v některých případech: rozdělení klauzle se středníkem do více klauzulí Opatrné používání operátoru řezu ■ preferovat použití zeleného řezu (nemění deklarativní sémantiku) ■ červený řez používat vjasně definovaných konstruktech negace: P, !, fail; true alternativy: Podmínka, !, Cill ; Cil2 Podmínka Opatrné používání negace „\+" ■ negace jako neúspěch: negace není ekvivalentní negaci v matematické logice Pozor na assert a retract: snižuji transparentnost chování programu \+ P ď U ; Cil 2 Hana Rudová, Logické programování 1,14. března 2011 17 Technika a styl programování v Prologu Dokumentace a komentáře ■ co program dělá, jak ho používat (jaký cíl spustit a jaké jsou očekávané výsledky), příklad použití ■ které predikáty jsou hlavní (top-level) ■ jak jsou hlavní koncepty (objekty) reprezentovány ■ doba výpočtu a paměťové nároky ■ jaké jsou limitace programu ■ zda jsou použity nějaké speciální rysy závislé na systému ■ jaký je význam predikátů v programu, jaké jsou jejich argumenty, které jsou vstupní a které výstupní (pokud víme) ■ vstupní argumenty „+", výstupní „-" mergeC +Seznaml, +Seznam2, -Seznam3 ) ■ ]menoPredikatu/Arita merge/3 ■ algoritmické a implementační podrobnosti Hana Rudová, Logické programování I,14.března2011 19 Technika a styl programování v Prologu Hana Rudová, Logické programování I, 14. března 201 1 1 8 Technika a styl programování v Prologu Ladění ■ Přepínače na trasování: trace/0, notrace/0 ■ Trasování specifického predikátu: spy/1, nospy/1 ■ spy( merge/3 ) ■ debug/0, nodebug/0: pro trasování pouze predikátů zadaných spy/1 ■ Libovolná část programu může být spuštěna zadáním vhodného dotazu: trasování cíle ■ vstupní informace: jméno predikátu, hodnoty argumentů při volání ■ výstupní informace ■ při úspěchu hodnoty argumentů splňující cíl ■ při neúspěchu indikace chyby ■ nové vyvolání přes stejný cíl je volán při backtrackingu Hana Rudová, Logické programování 1,14. března 201 1 20 Technika a styl programování v Prologu Krabičkový (4-branový) model Vizualizace řídícího toku (backtrackingu) na úrovni predikátu ■ Call: volání cíle ■ Exit: úspěšné ukončení volání cíle ■ Fail: volání cíle neuspělo ■ Redo: jeden z následujících cílů neuspěl a systém backtrackuje, aby nalezl alternativy k předchozímu řešení Call 1 -----> + predekC X, i Z ) :- rodicC X, Z ). 1 1 predekC X, Z ) :- rodicC X, Y ), <----------- ------+ predekC Y, Z ). Fail 1 I Exit +--------- I I + <-------- I Redo Hana Rudová, Logické programování I, 14. března 201 I Technika a styl programování v Prologu a(X) a(X) a(X) c(l). d(2). nonvar(X). c(X). d(X). Příklad: trasování I ?- a(X). Call I ------> + a(X) I a(X) <------+ a(X) Fai 1 I I Exi t nonvar(X).| ------> c(X). I d(X). + <------ I Redo 1 ? 1 1 Call : a(_463) ? 2 2 Call : nonvarC _463) ? 2 2 Fai 1 : nonvarC _463) ? 3 2 Call : c(_463) 7 3 2 Exit: c(l) ? 1 1 Exit: a(l) ? 1 1 Redo: a(l) ? 4 2 Call : d(_463) 7 4 2 Exit: d(2) ? 1 1 Exit: a(2) ? X = 2 ? no % trace I ?- Hana Rudová, Logické programování I, 14. března 201 1 Technika a styl programování v Prologu Efektivita ■ Čas výpočtu, paměťové nároky, a také časové nároky na vývoj programu ■ u Prologu můžeme častěji narazit na problémy s časem výpočtu a pamětí ■ Prologovské aplikace redukují čas na vývoj ■ vhodnost pro symbolické, nenumerické výpočty se strukturovanými objekty a relacemi mezi nimi ■ Pro zvýšení efektivity je nutno se zabývat procedurálními aspekty ■ zlepšení efektivity při prohledávání ■ odstranění zbytečného backtrackingu ■ zrušení provádění zbytečných alternativ co nejdříve ■ návrh vhodnějších datových struktur, které umožní efektivnější operace s objekty Zlepšení efektivity: základní techniky ■ Optimalizace posledního volání (LCO) a akumulátory ■ Rozdílové seznamy při spojování seznamů ■ Caching: uložení vypočítaných výsledků do programové databáze ■ Indexace podle prvního argumentu ■ např. v SICStus Prologu ■ při volání predikátu s prvním nainstaniovaným argumentem se používá hašovací tabulka zpřístupňující pouze odpovídající klauzule ■ zamestnanec( Prijmeni, Krestni]meno, Odděleni, ...) ■ Determinismus: ■ rozhodnout, které klauzule mají uspět vícekrát, ověřit požadovaný determinismus Hana Rudová, Logické programování 1,14. března 2011 23 Technika a styl programování v Prologu Hana Rudová, Logické programování 1,14. března 201 1 24 Technika a styl programování v Prologu