Testování typu termu
var(X) nonvar(X)
X je volná proměnná X není proměnná
Vestavěné predikáty (pokračování)
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
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í 1,11. března 2007
Vestavěné predikáty
Hana Rudová, Logické programování 1,11. března 2007
Vestavěné predikáty
Konstrukce a dekompozice atomu
1 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', Pavel Novák',  'prší', 'ano' ?- 'ano'=A. A = ano
1 Řetězec znaků v uvozovkách
■ př. "ano", "Pavel"
?- A="Pavel". ?- A="ano".
A = [80,97,118,101,108] A=[97,110,111]
■ 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] )
nameC ano, "ano" )
Hana Rudová, Logické programování 1,11. března 2007 4 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í 1,11. března 2007
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í 1,11. března 2007
Vestavěné predikáty
Term je proměnná (var/l), atom nebo číslo (atomic/1) => konec rozkladu
Term je seznam ([_|_]) =>
procházení seznamu a rozklad každého prvku seznamu
Term je složený (=../2 , 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í 1,11. března 2007
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 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í 1,11. března 2007
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í 1,11. března 2007
Technika a styl programování v Prologu
Hana Rudová, Logické programování 1,11. března 2007 1 0
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|Te"lol],  [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í 1,11. března 2007
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,11. března 2007 1 3 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í 1,11. března 2007 1 5 Technika a styl programování v Prologu
Hana Rudová, Logické programování 1,11. března 2007 1 4 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,11. března 2007 1 6 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
Redo
Hana Rudová, Logické programování 1,11. března 2007
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)	?
3	2	Exit:	c(l) ?	
1	1	Exit:	a(l) ?	
1	1	Redo:	a(l) ?	
4	2	Call :	d(_463)	?
4	2	Exit:	d(2) ?	
1	1	Exit:	a(2) ?	
X = 2 ? no
% trace I ?-
Hana Rudová, Logické programování 1,11. března 2007
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
■ zamestnanecC 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,11. března 2007 19 Technika a styl programování v Prologu Hana Rudová, Logické programování 1,11. března 2007 20 Technika a styl programování v Prologu