IB013 Logické programování I (průsvitky ze cvičení)
Hana Rudová
jaro 2012
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 8. května 201 2
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, 18. května 2012 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 8. května 201 2
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:
3 používání IDE SPIDER: z nabídky All Programs -> IDE -> Eclipse 3.7
příkazový řádek: z nabídky All Programs -> IDE -> SICStus Prolog VC9 4.2.0 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 (x86)\SICStus Prolog VC9 4.2.0\bin\sicstus.exe"
návod: http://www. si cs. se/sicstus/spider/site/prerequi sites. html#Setti ngLIp
Hana Rudová, Logické programování I, 18. května 2012 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 8. května 201 2
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 8. května 201 2
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 8. května 201 2
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 8. května 201 2
10
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
3 prababicka(Prababicka,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 8. května 201 2
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 8. května 201 2
12
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, 18. května 2012 13 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 8. května 201 2
14
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 8. května 201 2
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, 18. května 2012 16 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 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 8. května 201 2
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, 18. května 2012 18 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 8. května 201 2
19
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.
Hana Rudová, Logické programování I, 1 8. května 201 2
20
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 8. května 201 2
21
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, 18. května 201 2 23 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 8. května 201 2
24
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 8. května 201 2
24
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 8. května 201 2
25
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 prefixC SI, S2 ) :-DÚ: suffix(Sl,S2)
M last( X, S ) :-
append([3,2],  [6],  [3,2,6]). X=6, S=[3,2,6]
Hana Rudová, Logické programování I, 1 8. května 201 2
25
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 prefixC SI, S2 ) :-DÚ: suffix(Sl,S2)
M last( 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 8. května 201 2
25
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 prefixC SI, S2 ) :-DÚ: suffix(Sl,S2)
M last( 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)
% sublist(+S,+ASB) sublist(S,ASB) :-
POZOR na efektivitu, bez append lze často napsat efektivněji
Hana Rudová, Logické programování I, 1 8. května 201 2
25
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é rekurzivní 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 8. května 201 2
26
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, 18. května 201 2 27 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 8. května 201 2
27
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 8. května 201 2
27
Seznamy, řez
Akumulátor a sunuli st (S, Sum)
?- sum_list( [2,3,4], Sum ). s akumulátorem:
Hana Rudová, Logické programování I, 1 8. května 201 2
28
Seznamy, řez
Výpočet faktoriálu f act(N, F)
s akumulátorem:
Hana Rudová, Logické programování I, 1 8. května 201 2
29
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 > 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)
-wri te(rl). -p(X),write(r2). -write(r3).
:-write(pl). :-a(X),b(X),!,
c(X),d(X),write(p2). :-write(p3).
: -wri te(al) . :-write(a2).
:- X > O, write(bl). :- X < O, write(b2).
:- X mod 2 =:= 0, write(cl) :- X mod 3 =:= 0, write(c2)
:- abs(X) < 10, write(dl). :- 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)
Hana Rudová, Logické programování I, 1 8. května 201 2
30
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 8. května 201 2
31
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 8. května 201 2
31
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 8. května 201 2
32
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 8. května 201 2
32
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 8. května 201 2
33
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 8. května 201 2
34
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ůvodniho proudu
6 vestavěný predikát
Hana Rudová, Logické programování I, 1 8. května 201 2
36
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 ?- writeCa(l)), write('.'), nl, write(a(2)), write('.'), nl.
a(l).
a(2).
yes
M seeing, see, seen, read
M 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 8. května 201 2 37 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 8. května 201 2
38
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 8. května 201 2
39
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 8. května 201 2 40 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 8. května 201 2
41
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 8. května 201 2
42
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 8. května 201 2
43
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 8. května 201 2
44
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 8. května 201 2
45
Vstup/výstup, databázové operace, rozklad termu
not_occurs(A,B)
Predikát not_occurs(A, B) uspěje, pokud se proměnná A nevyskytuje v termu B. Tj. platí jedno z
B je atom nebo číslo NEBO 3 B je proměnná různá od A NEBO
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 8. května 201 2
46
Vstup/výstup, databázové operace, rozklad termu
Definite-Clause Grammars (DCG) Gramatiky uspořádaných klauzulí
Syntaktická analýza
Významná aplikace Prologu: syntaktická analýza M sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun. noun_phrase --> noun.
verb_phrase --> verb, noun_phrase. verb_phrase --> verb.
determiner --> [the], determiner --> [a].
noun --> [student]. noun --> [dcg].
verb --> [1 i kes].
M I ?- sentence([a, student, likes, dcg]). yes
Hana Rudová, Logické programování I, 1 8. května 201 2 48
Gramaticky uspořádaných klauzulí
DCG a CFG
DCG (DC gramatiky) jsou rozšířením bezkontextových gramatik (CFG) M Implementace DCG využívá rozdílových seznamů
Formální podobnosti mezi DCG a CFG: CFG: pravidla tvaru x — y, kde
M x E N je neterminál
M y e (N u T)* je konečná posloupnost terminálů a neterminálů
3 DCG: pravidla tvaru <hlava> --> <tělo>
<hl ava> je opět neterminál M <tělo> je opět konečná posloupnost terminálů a neterminálů
Pravidlo <hlava> --> <tělo> znamená, že
3 jedním z možných tvarů <hlavy> je <tělo>, neboli M <hl avu> je možno přepsat na <tělo>
Hana Rudová, Logické programování I, 18. května 2012 49 Gramaticky uspořádaných klauzulí
Rozdíly a rozšíření DCG oproti CFG
M Neterminál může být téměř libovolný term, ovšem kromě seznamu, proměnné a čísla.
* neterminál muže být složený term, tj. neterminálům lze přidat argumenty.
M Terminál může být libovolný term, s tím, že terminály a posloupnosti terminálů uzavíráme do hranatých závorek - jako seznamy.
* hranaté závorky tedy odlišují terminály od neterminálů
Pravá strana pravidla může obsahovat dodatečné podmínky v podobě prologovských podcílů. Tyto podmínky uzavíráme do složených závorek.
M podmínky slouží jen pro testování, negenerují žádnou větnou formu
Levá strana pravidla může dokonce vypadat i tak, že neterminál je následován posloupností terminálů.
M Tělo pravidla smí obsahovat řez.
M nepodporováno všemi Prology
Hana Rudová, Logické programování I, 18. května 201 2 50 Gramaticky uspořádaných klauzulí
Příklad: gramatika
3 sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun_phrase2. noun_phrase --> noun_phrase2.
noun_phrase2 --> noun.
noun_phrase2 --> adjective, noun_phrase2.
verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.
determiner --> [the].        noun --> [boy].
determiner --> [a]. noun --> [song].
verb --> [sings]. adjective --> [young].
M I ?- sentence(S, []).
S = [the,song,sings] ? ;
S = [the,song,sings,the,song] ?
I ?- sentence([the, young, boy, sings, a, song],[]). yes
Hana Rudová, Logické programování I, 1 8. května 201 2
51
Gramaticky uspořádaných klauzulí
Příklad: binární čísla
DC gramatika number rozeznávající binární čísla:
number --> [0]. number --> [1]. number --> [0], number, number --> [1], number.
I ?- number([0,l,0,l,l],  []). yes
Napište DCG number2 pro rozpoznání binárních čísel bez vedoucích nul.
Napište DCG number3 rozpoznávající binární čísla, které jsou mocninou dvojky.
Hana Rudová, Logické programování I, 1 8. května 201 2
52
Gramaticky uspořádaných klauzulí
Příklad: neterminály s argumentem
3 DC gramatika digits generuje binární čísla zapsaná jedinou číslicí:
digits --> same(O). digits --> same(l). same(N) --> [N]. same(N) --> [N], same(N).
?- digits([l,1,0,1] , []).
no
I ?- digits([l,l,l], []).
yes
M Upravte kód tak, aby byly akceptovány jen korektní věty:
s --> np, vp. np --> [zeny]. np --> [muzi]. vp --> [pracovali]. vp --> [pracovaly].
?- s([zeny, pracovali], []). yes
Nápověda: přidejte proměnnou pro rod (pro np a vp )
Hana Rudová, Logické programování I, 18. května 201 2 53 Gramaticky uspořádaných klauzulí
Generativní/rozpoznávací síla DCG: větší než CFG
DCG dokáží generovat/rozpoznávat jazyky typu 0
M Cvičení: napište DCG gramatiku generující jazyk anbncn
M ?- abc(X,[]). X = [] ; X = [a, b, c] ; X = [a, a, b, b, c, c] ; X = [a, a, a, b, b, b, c, c, c] ;
Nápověda: využijte a(s(s(s(0)))), b(s(s(s(0)))), c(s(s(s(0))))
Hana Rudová, Logické programování I, 1 8. května 201 2
54
Gramaticky uspořádaných klauzulí
Pomocné podmínky v těle pravidel
J E -> T + E | T Vyhodnocování výrazů
T -> num
expr(X) --> term(A),  [+], expr(B), {X is A+B}.
expr(X) --> term(X).
term(X) --> [X], {number(X)}.
?- expr(X,  [l,+,2,+,2],  []). X = 5
Cvičení: přidejte operaci násobení
E -> N + E | N N -> T * N | T T -> num
Hana Rudová, Logické programování I, 1 8. května 201 2
55
Gramaticky uspořádaných klauzulí
Komplexní vyhodnocování výrazů
E -> T + E I T - E I T T -> F * T | F / T | F F -> (E)  | f
expr(X) --> term(Y), [+], expr(Z), {X i s Y+Z}. expr(X) --> term(Y), [-], expr(Z), {X i s Y-Z}. expr(X) --> term(X).
term(X) --> factor(Y), [*], term(Z), {X i s Y*Z}. term(X) --> factor(Y), [/], term(Z), {X i s Y/Z}, term(X) --> factor(X).
factor(X) --> ['('], expr(X), [')']. factor(X) --> [X], {integer(X)}.
% vyhodnoceni výrazu 3+(4/2)-(2*6/3)
?- expr(X,[3,+,'(',4,/,2,')',-,'(',2,*,6,/,3,')'],[]). X = 1
Argument neterminálu je použit jako výstupní proměnná, která v sobě nese hodnotu příslušného aritmetického výrazu.
Hana Rudová, Logické programování I, 18. května 201 2 56 Gramaticky uspořádaných klauzulí
Přepis do Prologu
Přepis do prologovského programu pomocí append/3:
3 Větu reprezentujeme seznamem slov [the,young,boy,sings,a,song]
3 Pravidlová část - neterminál chápeme jako unární predikát, jehož argumentem je ta větná složka, kterou daný neterminál popisuje
sentence(S) :- append(NP,VP,S),
noun_phrase(NP), verb_phrase(VP).
3 Slovníková část - zapisujeme ji pomocí faktů:
determiner( [the]). noun([boy]). determi ner([a]).
Predikát append/3 zde nedeterministicky rozděluje aktuální větnou část na dva díly, což je velký zdroj neefektivnosti.
Lepší řešení poskytují rozdílové seznamy.
Hana Rudová, Logické programování I, 18. května 201 2 57 Gramaticky uspořádaných klauzulí
Přepis do Prologu pomocí rozdílových seznamů
M Rozdílové seznamy reprezentovány dvěma argumenty, první představuje neúplný seznam a druhý jeho zbytek append(S-Sl, SI -SO, S-SO)
M Při volání predikátu S-SO je spojením: S-S3, S3-S2, S2-S1, SI -SO
sentence/2 je druhý argument prázdný; neúplný seznam tím uzavíráme tj. S0=[ ]
sentence(S,SO):- noun_phrs(S,SI), verb_phrs(Sl,SO).
noun_phrs(S,SO):- determiner(S,SI), noun_phrs2(Sl,SO). noun_phrs(S,SO):- noun_phrs2(S,SO).
noun_phrs2(S,SO):- adjective(S,SI), noun_phrs2(Sl,SO). noun_phrs2(S,SO):- noun(S,S0).
verb_phrs(S,SO):- verb(S,S0).
verb_phrs(S,SO):- verb(S,Sl), noun_phrs(Sl,SO).
determi ner([the|S],S). noun([boy|S],S).
determi ner([a|S],S). noun([song|S],S).
verb( [sings|S],S). adjective([young|S],S).
?- sentence([the,young,boy,sings,a,song],[]). yes
Hana Rudová, Logické programování I, 18. května 201 2 58 Gramaticky uspořádaných klauzulí
Derivační strom analýzy
?- sentence(Tree,  [the,young,boy,sings,a,song],[]). Tree=s( np( det(the), np2( adj(young), np2(n(boy) ) ) ), vp( v(sings), np( det(a), np2( n(song) ) ) ) )
np
vp
det
np2
v
np
the   adj   np2 sings det np2
young n
a n
boy
song
Hana Rudová, Logické programování I, 1 8. května 201 2
59
Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu
Neterminály opatříme argumentem:
sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP). noun(n(mama)) --> [mama]. noun(n(kralika)) --> [králika]. verb(v(pekla)) --> [pekla].
M Doplňte gramatiku, aby platilo:
| ?- sentence(X,  [mama,pekla,králika], []).
X = s(np(n(mama)),vp(v(pekla),np(n(kralika)))) yes
Hana Rudová, Logické programování I, 1 8. května 201 2
60
Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu
Pokud však rozšíříme slovník:
noun(n(tata)) --> [tata]. verb(v(pekl)) --> [pekl].
Narazíme na problém se shodou podmetu a prísudku (mimo stávající problém „králíka pekla máma"):
?- sentence(_,[tata, pekla, král ika],[]). yes
?- sentence(_,[mama, pekl, král ika],[]). yes
Proto rozšiřte neterminály o další argumenty (rod, pád)
Hana Rudová, Logické programování I, 1 8. května 201 2
61
Gramaticky uspořádaných klauzulí
Vestavěné nástroje
operátor --> definován jako ?-op(1200,xfx,-->) .
predikáty ph rase/2, ph rase/3, které slouží k jednoduché tokenizaci
?- phrase(abc,[a,b,c]). % Yes
?- phrase(abc,[a,b,c,d],[d]).        % Yes
Hana Rudová, Logické programování I, 1 8. května 201 2
62
Gramaticky uspořádaných klauzulí
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 J SaM 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 8. května 201 2
64
Omezující podmínky
Jazykové prvky
Nalezněte řešení pro algebrogram
DONALD + GERALD = ROBERT
Struktura programu
algebrogramC [D,0,N,A,L,G,E,R,B,T] ) domai n(...),
all_distinct(...),  ... #= 1abeli ng(...).
% domény proměnných % omezeni
% prohledáváni stavového prostoru
Knihovna pro CLP(FD)
:- use_module(library(clpfd))
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 8. května 201 2
65
1abeli ng([],Seznam)
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
Hana Rudová, Logické programování I, 1 8. května 201 2
66
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 8. května 201 2
66
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) :- domeny(Ukoly,Začátky,Tasks),
cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky).
domény(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, 18. května 2012 67 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 8. května 201 2
68
Omezující podmínky
Plánování: výstup II
quicksort(S, Sorted) :- quicksortl(S,Sorted-[]).
quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :-
split(X, Tail, Small, Big),
quicksortl(Small, A1-[X|A2]),
quicksortl(Big, A2-Z2).
split(_X,  [],  [], []).
split(X, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). split(X,  [Y|T], Small,  [Y|Big]) :- split(X, T, Small, Big).
greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2.
Hana Rudová, Logické programování I, 1 8. května 201 2
69
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 8. května 201 2
70
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 8. května 201 2
71
Omezující podmínky
Kumulativní rozvrhování
M 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
Hana Rudová, Logické programování I, 1 8. května 201 2
72
Omezující podmínky
Kumulativní rozvrhování
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
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 8. května 201
1 2   72 3
6
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ě
domeny(Ukoly,Začátky,Tasks), cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky).
ukoly_lide(Zacatky) :- % 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, 18. května 201 2 73 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 8. května 201 2
74
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 8. května 201 2
74
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í cumulati ve/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 8. května 201 2
75
Omezující podmínky
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 8. května 201 2
77
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 8. května 201 2 77 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 8. května 201 2
78
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 8. května 201 2
78
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 8. května 201 2
78
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 8. května 201 2
79
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 8. května 201 2
80
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 8. května 201 2
81
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 8. května 201 2
82
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 8. května 201 2 83
-[],  [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 8. května 201 2
84
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ární složitost, rozdílové seznamy
reverse( Seznam, Opacny ) :- reverseO( Seznam, ). reverseO( [], ).
reverseO( [ H | T ], ) :-
reverseO( T, ).
Hana Rudová, Logické programování I, 1 8. května 201 2
84
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 8. května 201 2
84
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]
Hana Rudová, Logické programování I, 1 8. května 201 2
85
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 8. května 201 2
86
Všechna řešení, třídění, rozdílové seznamy
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 8. května 201 2
87
Poděkováni