Vestavěné predikáty (pokračování) Všechna řešení M 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 ). ?- bagof( Ditě, vek( Ditě, 5 ), Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 2 Všechna řešení M 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 ). ?- bagof( Ditě, vek( Ditě, 5 ), Seznam ). Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, 1 7. března 2009 2 Všechna řešení M 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 ). ?- bagof( Ditě, vek( Ditě, 5 ), Seznam ). Seznam = [ anna, tomas ] -• Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagof( Ditě, vek( Ditě, Vek ), Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 2 Všechna řešení M 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 ). ?- bagof( Ditě, vek( Ditě, 5 ), Seznam ). Seznam = [ anna, tomas ] -• Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagof( Ditě, vek( Ditě, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, 1 7. března 2009 2 Všechna řešení IL -• 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 ). ?- bagof( Ditě, ( vek( Ditě, 5 ), Ditě \= anna ), Seznam ). Seznam = [ tomas ] Hana Rudová, Logické programování I, 1 7. března 2009 3 Všechna řešení IL -• 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 ). ?- bagof( Ditě, ( vek( Ditě, 5 ), Ditě \= anna ), Seznam ). Seznam = [ tomas ] -• bagof, setof, findall: na objekty shromažďované v X nejsou žádná omezení ?- bagof( Dite-Vek, vek( Ditě, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programování I, 1 7. března 2009 3 Existenční kvantifikátor „" " -• Přidání existenčního kvantifikátoru „Ä " ^> hodnota proměnné nemá význam ?- bagof( Ditě, Vek~vek( Ditě, Vek ), Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 4 Existenční kvantifikátor „" " -• Přidání existenčního kvantifikátoru „Ä " ^> hodnota proměnné nemá význam ?- bagof( Ditě, Vek~vek( Ditě, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování I, 1 7. března 2009 4 Existenční kvantifikátor „ » Přidání existenčního kvantifikátoru „Ä " ^> hodnota proměnné nemá význam ?- bagof( Ditě, Vek~vek( Ditě, 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 ?- bagof( Ditě, vek( Ditě, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna,tomas] Hana Rudová, Logické programování I, 1 7. března 2009 4 Existenční kvantifikátor „ » Přidání existenčního kvantifikátoru „Ä " ^> hodnota proměnné nemá význam ?- bagof( Ditě, Vek~vek( Ditě, 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 ?- bagof( Ditě, vek( Ditě, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna,tomas] Před operátorem „~ " může být i seznam ?- bagof( Vek ,[Jméno,Přijmeni]~vek( Jméno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování I, 1 7. března 2009 4 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány Hana Rudová, Logické programování I, 1 7. března 2009 5 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány -• findall( X, P, S ): rozdíly od bagof M všechny proměnné jsou existenčně kvantifikovány ?- findaIK Ditě, vek( Ditě, Vek ), Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 5 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány -• findall( X, P, S ): rozdíly od bagof M všechny proměnné jsou existenčně kvantifikovány ?- findaIK Ditě, vek( Ditě, Vek ), Seznam ). =>vS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou Hana Rudová, Logické programování I, 1 7. března 2009 5 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány -• findall( X, P, S ): rozdíly od bagof M všechny proměnné jsou existenčně kvantifikovány ?- findaIK Ditě, vek( Ditě, Vek ), Seznam ). =>vS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou M výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S Hana Rudová, Logické programování I, 1 7. března 2009 5 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány -• findall( X, P, S ): rozdíly od bagof M všechny proměnné jsou existenčně kvantifikovány ?- findaIK Ditě, vek( Ditě, Vek ), Seznam ). =>vS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou M výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S -• ?- bagof( Ditě, vek( Ditě, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findall( Ditě, vek( Ditě, Vek ), Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 5 Všechna řešení III. -• setof( X, P, S ): rozdíly od bagof M S je uspořádaný podle @< 3 případné duplicity v S jsou eliminovány -• findall( X, P, S ): rozdíly od bagof M všechny proměnné jsou existenčně kvantifikovány ?- findaIK Ditě, vek( Ditě, Vek ), Seznam ). =>vS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou M výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S -• ?- bagof( Ditě, vek( Ditě, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findall( Ditě, vek( Ditě, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování I, 1 7. března 2009 5 Testování typu termu var(X) X je volná proměnná nonvar(X) X není proměnná Hana Rudová, Logické programování I, 17. března 2009 6 Vestavěné predikáty var(X) nonvar(X) Testovaní typu termu X je volná proměnná X není proměnná atom(X) integer(X) float (X) atomic(X) X je atom (pavel , 'Pavel Novák', <- X je integer X je float X je atom nebo číslo ->) Hana Rudová, Logické programování I, 1 7. března 2009 Vestavěné predikáty Testovaní typ var(X) X je volná proměnná nonvar(X) X není proměnná atom(X) X je atom (pavel , : 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, 1 7. března 2009 6 u termu Pavel Novák', <-->) Vestavěné predikáty Určení počtu výskytů prvku v seznamu count( X, S, N ) Hana Rudová, Logické programování I, 17. března 2009 7 Vestavěné predikáty Určení počtu výskytů prvku v seznamu count( X, S, N ) :- count( X, S, 0, N ). Hana Rudová, Logické programování I, 17. března 2009 7 Vestavěné predikáty Určení počtu výskytů prvku v seznamu count( X, S, N ) :- count( X, S, 0, N ). count( _, [], N, N ). Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty 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) :- !, Nl is NO + 1, count( X, S, Nl, N). Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty 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) :- !, Nl is NO + 1, count( X, S, Nl, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty 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) :- !, Nl is NO + 1, count( X, S, Nl, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) N=3 Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty 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) :- !, Nl is NO + 1, count( X, S, Nl, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) :-? count( a, [a,b,X,Y], N). N=3 Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty 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) :- !, Nl is NO + 1, count( X, S, Nl, N). count( X, [_|S], NO, N) :- count( X, S, NO, N). :-? count( a, [a,b,a,a], N ) :-? count( a, [a,b,X,Y], N). N=3 N=3 Hana Rudová, Logické programování I, 1 7. března 2009 7 Vestavěné predikáty Určení počtu výskytů prvku v seznamu count( X, S, N ) :- count( X, S, 0, N ). count( _, [], N, N ). countC X, [X|S], NO, N) :- !, Nl is NO + 1, countC X, S, Nl, N) countC X, [_|S], NO, N) :- countC X, S, NO, N). :-? countC a, [a,b,a,a], N ) :-? countC a, [a,b,X,Y], N). N=3 N=3 countC _, [], N, N ). countC X, [Y|S], NO, N ) :- nonvarCY), X = Y, !, Nl is NO + 1, countC X, S, Nl, N ) countC X, [_|S], NO, N ) :- countC X, S, NO, N ). Hana Rudová, Logické programování I, 17. března 2009 7 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 M řetězce speciálních znaků:+, <->, ===> M řetězce v apostrofech: 'Pavel', Pavel Novák', 'prší', 'ano' ?- 'ano'=A. A = ano Hana Rudová, Logické programování I, 1 7. března 2009 8 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 M řetězce speciálních znaků:+, <->, ===> M řetězce v apostrofech: 'Pavel', Pavel Novák', 'prší', 'ano' ?- 'ano'=A. A = ano M Řetězec znaků v uvozovkách * př. "ano", "Pavel" ?- A="Pavel". ?- A="ano". A = [80,97,118,101,108] A=[97,110,111] M př. použití: konstrukce a dekompozice atomu na znaky, vstup a výstup do souboru Hana Rudová, Logické programování I, 1 7. března 2009 8 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 M řetězce speciálních znaků:+, <->, ===> M řetězce v apostrofech: 'Pavel', Pavel Novák', 'prší', 'ano' ?- 'ano'=A. A = ano M Řetězec znaků v uvozovkách * př. "ano", "Pavel" ?- A="Pavel". ?- A="ano". A = [80,97,118,101,108] A=[97,110,111] M př. použití: konstrukce a dekompozice atomu na znaky, vstup a výstup do souboru 3 Konstrukce atomu ze znaků, rozložení atomu na znaky name( Atom, SeznamASCIIKodu ) name( ano, [97,110,111] ) name( ano, "ano" ) Hana Rudová, Logické programování I, 17. března 2009 8 Vestavěné predikáty Konstrukce a dekompozice termu M Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Hana Rudová, Logické programování I, 17. března 2009 9 Vestavěné predikáty Konstrukce a dekompozice termu M Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], call( Cil ) Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty 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 Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty 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] Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty 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 ) functorC a(9,e), a, 2 ) Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty 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 ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty 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 ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) arg( N, Term, Argument ) arg( 2, a(9,e), e) Hana Rudová, Logické programování I, 1 7. března 2009 9 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu Hana Rudová, Logické programování I, 17. března 2009 10 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je složený (=. ./2 , functor/3) ^> procházení seznamu argumentů a rozklad každého argumentu Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 M Příklad: ground/1 uspěje, pokud v termu nejsou proměnné; jinak neuspěje Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 g round(Term) :- atomic(Term), !. Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 g round(Term) :- atomic(Term), !. ground(Term) :- var(Term), !, fail. Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 g round(Term) :- atomic(Term), !. ground(Term) :- var(Term), !, fail. ground([H|T]) :- !, ground(H), ground(T). Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 g round(Term) :- atomic(Term), !. ground(Term) :- var(Term), !, fail. ground([H|T]) :- !, ground(H), ground(T). ground(Term) :- Term =.. [ _Funktor | Argumenty ], groundC Argumenty ). Hana Rudová, Logické programování I, 1 7. března 2009 1 0 Vestavěné predikáty Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_ | _]) => [] ... řešen výše jako atomic 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 g round(Term) :- atomic(Term), !. ground(Term) :- var(Term), !, fail. ground([H|T]) :- !, ground(H), ground(T). ground(Term) :- Term =.. [ _Funktor | Argumenty ], groundC Argumenty ). ?- 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, 17. března 2009 10 Vestavěné predikáty Příklad: dekompozice termu I. -• count_term( Integer, Term, N ) určí počet výskytů celého čísla v termu Hana Rudová, Logické programování I, 17. března 2009 1 1 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,l)),Y), N ). N=2 Hana Rudová, Logické programování I, 17. března 2009 1 1 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,l)),Y), N ). N=2 3 count_term( X, T, N ) :- count_term( X, T, 0, N). Hana Rudová, Logické programování I, 17. března 2009 1 1 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,l)),Y), N ). N=2 3 count_term( X, T, N ) :- count_term( X, T, 0, N). count_term( X, T, NO, N ) :- integer(T), X = T, !, N is NO + 1. Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). N=2 3 count_term( X, T, N ) :- count_term( X, T, 0, N). count_term( X, T, NO, N ) :- integer(T), X = T, !, N is NO + 1. count_term( _, T, N, N ) :- atomic(T), !. Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). N=2 3 count_term( X, T, N ) :- count_term( X, T, 0, N). count_term( X, T, NO, N ) :- integer(T), X = T, !, N is NO + 1. count_term( _, T, N, N ) :- atomic(T), !. count_term( _, T, N, N ) :- var(T), !. Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) T, N, N ) T, N, N ) T, NO, N ) - integer(T), X = T, !, N is NO + 1 atomic(T), !. var(T), !. - T =.. [ _ | Argumenty ], Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) T, N, N ) T, N, N ) T, NO, N ) - integer(T), X = T, !, N is NO + 1 atomic(T), !. var(T), !. - T =.. [ _ | Argumenty ], count_arg( X, Argumenty, NO, N ). Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) T, N, N ) T, N, N ) T, NO, N ) - integer(T), X = T, !, N is NO + 1 atomic(T), !. var(T), !. - T =.. [ _ | Argumenty ], count_arg( X, Argumenty, NO, N ). count_arg( _, [], N, N ). Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N is 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, Nl), Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N is 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, Nl), N2 is NO + Nl, Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N is 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, Nl), N2 is NO + Nl, count_arg( X, T, N2, N ). Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N is 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, Nl), N2 is NO + Nl, count_arg( X, T, N2, N ). ?- count_term( 1, [a,2,[b,c],[d,[e,f],Y]], N ). Hana Rudová, Logické programování I, 1 7. března 2009 1 1 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,l)),Y), N ). count_term( X, T, N ) :- count_term( X, T, 0, N). N=2 count_term( X count_term( _ count_term( _ count_term( X T, NO, N ) :- integer(T), X = T, !, N is 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, Nl), N2 is NO + Nl, count_arg( X, T, N2, N ). M ?- 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, 17. března 2009 1 1 Vestavěné predikáty Cvičení: dekompozice termu -• Napište predikát substituteC 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 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, 1 7. března 2009 1 2 Vestavěné predikáty Technika a styl programování v Prologu Technika a styl programování v Prologu -• Styl programování v Prologu M některá pravidla správného stylu M správný vs. špatný styl M komentáře -• Ladění -• Efektivita Hana Rudová, Logické programování I, 1 7. března 2009 1 4 Technika a styl programování v Prologu Styl programování v Prologu I. -• Cílem stylistických konvencí je 3 redukce nebezpečí programovacích chyb 3 psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Technika a styl programování v Prologu Styl programování v Prologu I. -• Cílem stylistických konvencí je 3 redukce nebezpečí programovacích chyb 3 psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují -• Některá pravidla správného stylu M krátké klauzule -• krátké procedury; dlouhé procedury pouze s uniformní strukturou (tabulka) Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Technika a styl programování v Prologu Styl programování v Prologu I. -• Cílem stylistických konvencí je 3 redukce nebezpečí programovacích chyb 3 psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují -• Některá pravidla správného stylu M krátké klauzule -• krátké procedury; dlouhé procedury pouze s uniformní strukturou (tabulka) M klauzule se základními (hraničními) případy psát před rekurzivními klauzulemi M vhodná jména procedur a proměnných -i* nepoužívat seznamy ([. . .]) nebo závorky ({...}, (...)) pro termy pevné arity 3 vstupní argumenty psát před výstupními Hana Rudová, Logické programování I, 1 7. března 2009 1 5 Technika a styl programování v Prologu 23 Styl programování v Prologu I. -• Cílem stylistických konvencí je 3 redukce nebezpečí programovacích chyb 3 psaní čitelných a srozumitelných programů, které se dobře ladí a modifikují -• Některá pravidla správného stylu M krátké klauzule -• krátké procedury; dlouhé procedury pouze s uniformní strukturou (tabulka) M klauzule se základními (hraničními) případy psát před rekurzivními klauzulemi M vhodná jména procedur a proměnných -i* nepoužívat seznamy ([. . .]) nebo závorky ({...}, (...)) pro termy pevné arity 3 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í S* 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, 1 7. března 2009 1 5 Technika a styl programování v Prologu 23 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 ) 3 merge( [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :- Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :-X < Y, !, Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :-X < Y, !, mergeC Telol, [Y|Telo2], Telo3 ). Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :-X < Y, !, mergeC Telol, [Y|Telo2], Telo3 ). mergeC Seznámí, [Y|Telo2], [Y|Telo3] ) :- Hana Rudová, Logické programování I, 1 7. března 2009 1 6 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 ) M mergeC [2,4,7], [1,3,4,8], [1,2,3,4,4,7,8] ) -• merge( [], Seznam, Seznam ) :- ! . % prevence redundantních řešení merge( Seznam, [], Seznam ). mergeC [X|Telol], [Y|Telo2], [X|Telo3] ) :-X < Y, !, mergeC Telol, [Y|Telo2], Telo3 ). mergeC Seznámí, [Y|Telo2], [Y|Telo3] ) :-mergeC Seznámí, Telo2, Telo3 ). Hana Rudová, Logické programování I, 1 7. března 2009 1 6 Technika a styl programování v Prologu Špatný styl programování mergeC SI, S2, S3 ) 51 = [] , ! , S3 = S2 52 =[],!, S3 = SI 51 = [X|T1], 52 = [Y|T2], ( X < Y, !, Z = X, merge( TI, S2, T3 ) ; Z = Y, merge( SI, T2, T3) ) 53 = [ Z | T3 ]. % první seznam je prázdný % druhý seznam je prázdný % Z je hlava seznamu S3 Hana Rudová, Logické programování I, 1 7. března 2009 17 Technika a styl programování v Prologu Styl programování v Prologu II. M Středník „;" může způsobit nesrozumitelnost klauzule M nedávat středník na konec řádku, používat závorky 3 v některých případech: rozdělení klauzle se středníkem do více klauzulí Hana Rudová, Logické programování I, 1 7. března 2009 1 8 Technika a styl programování v Prologu Styl programování v Prologu II. M Středník „;" může způsobit nesrozumitelnost klauzule M nedávat středník na konec řádku, používat závorky 3 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 v jasně definovaných konstruktech negace: P, !, fail; true \+ P alternativy: Podmínka, !, Cill ; Cil2 Podminka -> Cill ; Cil2 Hana Rudová, Logické programování I, 1 7. března 2009 1 8 Technika a styl programování v Prologu Styl programování v Prologu II. M Středník „;" může způsobit nesrozumitelnost klauzule M nedávat středník na konec řádku, používat závorky 3 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 v jasně definovaných konstruktech negace: P, !, fail; true \+ P alternativy: Podmínka, !, Cill ; Cil2 Podminka -> Cill ; Cil2 -• Opatrné používání negace „\+" 3 negace jako neúspěch: negace není ekvivalentní negaci v matematické logice Hana Rudová, Logické programování I, 1 7. března 2009 1 8 Technika a styl programování v Prologu Styl programování v Prologu II. M Středník „;" může způsobit nesrozumitelnost klauzule M nedávat středník na konec řádku, používat závorky 3 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 v jasně definovaných konstruktech negace: P, !, fail; true \+ P alternativy: Podmínka, !, Cill ; Cil2 Podminka -> Cill ; Cil2 -• Opatrné používání negace „\+" 3 negace jako neúspěch: negace není ekvivalentní negaci v matematické logice M Pozor na assert a retract: snižuji transparentnost chování programu Hana Rudová, Logické programování I, 1 7. března 2009 1 8 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í Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M jak jsou hlavní koncepty (objekty) reprezentovány Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M jak jsou hlavní koncepty (objekty) reprezentovány -• doba výpočtu a paměťové nároky Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M jak jsou hlavní koncepty (objekty) reprezentovány -• doba výpočtu a paměťové nároky -• jaké jsou limitace programu Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M 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 Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M jak jsou hlavní koncepty (objekty) reprezentovány -• doba výpočtu a paměťové nároky -• jaké jsou limitace programu M zda jsou použity nějaké speciální rysy závislé na systému M jaký je význam predikátů v programu, jaké jsou jejich argumenty, které jsou vstupní a které výstupní (pokud víme) M vstupní argumenty „+", výstupní „-" merge( +Seznaml, +Seznam2, -Seznam3 ) 3 JmenoPredikatu/Arita merge/3 Hana Rudová, Logické programování I, 1 7. března 2009 1 9 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) M jak jsou hlavní koncepty (objekty) reprezentovány -• doba výpočtu a paměťové nároky -• jaké jsou limitace programu M zda jsou použity nějaké speciální rysy závislé na systému M jaký je význam predikátů v programu, jaké jsou jejich argumenty, které jsou vstupní a které výstupní (pokud víme) M vstupní argumenty „+", výstupní „-" merge( +Seznaml, +Seznam2, -Seznam3 ) 3 JmenoPredikatu/Arita merge/3 M algoritmické a implementační podrobnosti Hana Rudová, Logické programování I, 1 7. března 2009 1 9 Technika a styl programování v Prologu Ladění -• Přepínače na trasování: trace/O, notrace/O -• Trasování specifického predikátu: spy/1, nospy/1 M spyC merge/3 ) -• debug/0, nodebug/0: pro trasování pouze predikátů zadaných spy/1 Hana Rudová, Logické programování I, 1 7. března 2009 20 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 M spyC 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 M vstupní informace: jméno predikátu, hodnoty argumentů při volání -• výstupní informace -i* při úspěchu hodnoty argumentů splňující cíl J* 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í I, 1 7. března 2009 20 Technika a styl programování v Prologu Krabičkový (4-branový) model Vizualizace řídícího toku (backtrackingu) na úrovni predikátu M Call: volání cíle 3 Exit: úspěšné ukončení volání cíle -• Fail: volání cíle neuspělo 3 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 | | Exit -------------------------> + predek( X, Z ) :- rodic( X, Z ). +---------------> | predekC X, Z ) :- rodic( X, Y ), | <------------------------------+ predek( Y, Z ). + <------------- Fail I I Redo Hana Rudová, Logické programování I, 1 7. března 2009 21 Technika a styl programování v Prologu Příklad a (X) - nonvar(X). a (X) - c(X). a (X) - d(X). cd). d(2). Call 1 1 Exi t -> + a(X) :- nonvar(X).| ----------> I a(X) :- c(X). | <----------- -- + a(X) :- d(X). + <---------- Fan" 1 | I Redo Hana Rudová, Logické programování I, 1 7. března 2009 trasování 22 Technika a styl programování v Prologu Příklad a (X) - nonvar(X). a (X) - c(X). a (X) - d(X). cd). d(2). Call 1 1 Exi t -> + a(X) :- nonvar(X).| ----------> I a(X) :- c(X). | <----------- -- + a(X) :- d(X). + <---------- Fan" 1 | I Redo Hana Rudová, Logické programování I, 1 7. března 2009 trasování I ?- a(X). 1 1 Call: a(_463) ? 2 2 Call: nonvar(_463) ? 2 2 Fail: nonvar(_463) ? 2 2 Technika a styl programování v Prologu Příklad a (X) - nonvar(X). a (X) - c(X). a (X) - 0(X). cd). 0(2). Call 1 1 Exi t -> + a(X) :- nonvar(X).| ------> | a(X) :- c(X). | <------ -- + a(X) :- d(X). + <------ Fan" 1 | I Redo Hana Rudová, Logické programování I, 1 7. března 2009 trasování ?_ a(X). 1 1 Call a(_463) ? 2 2 Call nonvar(_463) ? 2 2 Fail nonvar(_463) ? 3 2 Call c(_463) ? 3 2 Exit c(D ? 1 1 Exit a(l) ? X = 1 ? 2 2 Technika a styl programování v Prologu Příklad a (X) - nonvar(X). a (X) - c(X). a (X) - d(X). cd). d(2). Call 1 1 Exi t -> + a(X) :- nonvar(X).| ------> I a(X) :- c(X). | <------ -- + a(X) :- d(X). + <------ Fan" 1 | I Redo Hana Rudová, Logické programování I, 1 7. března 2009 trasování ?_ X = 1 ? a(X). 1 1 Call a(_463) ? 2 2 Call nonvar(_463) ? 2 2 Fail nonvar(_463) ? 3 2 Call c(_463) ? 3 2 Exit c(D ? 1 1 Exit a(l) ? ľ > 1 1 Redo a(l) ? 4 2 Call d(_463) ? 2 2 Technika a styl programování v Prologu Příklad a (X) - nonvar(X). a (X) - c(X). a (X) - 0(X). cd). 0(2). Call 1 1 Exi t -> + a(X) :- nonvar(X).| ------> | a(X) :- c(X). | <------ -- + a(X) :- d(X). + <------ Fan" 1 | I Redo Hana Rudová, Logické programování I, 1 7. března 2009 trasování 1 ?- a(X). 1 1 Call a(_463) ? 2 2 Call nonvar(_463) ? 2 2 Fail nonvar(_463) ? 3 2 Call c(_463) ? 3 2 Exit c(D ? ? 1 1 Exit a(l) ? X = 1 ? ■ > 1 1 Redo a(l) ? 4 2 Call d(_463) ? 4 2 Exit d(2) ? 1 1 Exit a(2) ? X = 2 ? ■ > no % trace l ?- 2 2 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 3 u Prologu můžeme častěji narazit na problémy s časem výpočtu a pamětí M Prologovské aplikace redukují čas na vývoj 3 vhodnost pro symbolické, nenumerické výpočty se strukturovanými objekty a relacemi mezi nimi Hana Rudová, Logické programování I, 1 7. března 2009 23 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 3 u Prologu můžeme častěji narazit na problémy s časem výpočtu a pamětí M Prologovské aplikace redukují čas na vývoj 3 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 3 zlepšení efektivity při prohledávání 3 odstranění zbytečného backtrackingu «i* 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 Hana Rudová, Logické programování I, 1 7. března 2009 23 Technika a styl programování v Prologu Zlepšení efektivity: základní techniky M 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 Hana Rudová, Logické programování I, 1 7. března 2009 24 Technika a styl programování v Prologu Zlepšení efektivity: základní techniky M 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 M např. v SICStus Prologu 3 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 M zamestnanecC Prijmeni, KrestniJméno, Odděleni, ...) Hana Rudová, Logické programování I, 1 7. března 2009 24 Technika a styl programování v Prologu Zlepšení efektivity: základní techniky M 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 M např. v SICStus Prologu 3 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 M zamestnanecC Prijmeni, KrestniJméno, Odděleni, ...) M Determinismus: M rozhodnout, které klauzule mají uspět vícekrát, ověřit požadovaný determinismus Hana Rudová, Logické programování I, 1 7. března 2009 24 Technika a styl programování v Prologu