Úvod do Prologu
Prolog
-í* PROgramming in LOGic
Část predikátové logiky prvního rádu
C- Deklarativní programování
J* specifikační jazyk, jasná sémantika, nevhodné pro procedurální postupy Co dělat namísto Jak dělat
JS> Základní mechanismy
unifikace, stromové datové struktury, automatický backtracking
Hana Rudová, Logické programování I, 25. února 2013
2
Úvod do Prologu
Logické programování
Historie
C- Rozvoj začíná po roce 1970
& Robert Kowalski - teoretické základy
& Alain Colmerauer, David Warren (Warren Abstract Machine) - implementace
SICStus Prolog vyvíjen od roku 1985 JS> Logické programování s omezujícími podmínkami - od poloviny 80. let
Aplikace
& rozpoznávání reci, telekomunikace, biotechnologie, logistika, plánování, data mining, business rules, ...
SICStus Prolog — the first 25 years, Mats Carlsson, Per Mildner. Theory and Practice of Logic Programming, 12 (1-2): 35-66, 2012. http://arxiv.org/abs/1011.5640.
Hana Rudová, Logické programování I, 25. února 2013 3 Úvod do Prologu
Program = fakta + pravidla
(Prologovský) program je seznam programových klauzulí
i> programové klauzule: fakt, pravidlo
Fakt: deklaruje vždy pravdivé veci
-fc clovek( novak, 18, student ).
Pravidlo: deklaruje veci, jejichž pravdivost závisí na daných podmínkách
J* studuje( X )      clovek( X, _Vek, student ). A alternativní (obousměrný) význam pravidel
pro každé X, pro každé X,
X studuje, jestliže X je student, potom
X je student X studuje
-4» pracuje( X )      clovek( X, _Vek, CoDela ), prace( CoDela ).
Hana Rudová, Logické programování I, 25. února 2013
4
Úvod do Prologu
Program = fakta + pravidla
JS> (Prologovský) program je seznam programových klauzulí
i> programové klauzule: fakt, pravidlo
& Fakt: deklaruje vždy pravdivé veci
-fc clovek( novak, 18, student ).
& Pravidlo: deklaruje veci, jejichž pravdivost závisí na daných podmínkách
J* studuje( X )      clovek( X, _Vek, student ). A alternativní (obousměrný) význam pravidel
pro každé X, pro každé X,
X studuje, jestliže Xje student, potom
X je student X studuje
-4» pracuje( X )      clovek( X, _Vek, CoDela ), prace( CoDela ).
JS> Predikát: seznam pravidel a faktu se stejným funktorem a aritou
S> znacíme: clovek/3, student/1; analogie procedury v procedurálních jazycích,
Hana Rudová, Logické programování I, 25. února 2013 4 Úvod do Prologu
Komentáře k syntaxi
C Klauzule ukončeny tečkou
& Základní příklady argumentu
-i- konstanty: (tomas, anna) ... začínají malým písmenem i* přomenné
X, Y ... začínají velkým písmenem
_, _A, _B ... začínají podtržítkem (nezajímá nás vracená hodnota)
£ Psaní komentářů
clovek( novak, 18, student ). % komentář na konči řádku
clovek( novotny, 30, ucitel ). /* komentář */
Hana Rudová, Logičké přogřamování I, 25. únořa 2013
5
Úvod do Přologu
Dotaz
Dotaz: uživatel se ptá programu, zda jsou veci pravdivé
?- studuje( novak ). % yes        splnitelný dotaz
?- studuje( novotny ). % no nesplnitelný dotaz
Odpoveď na dotaz
a positivní - dotaz je splnitelný a uspel
± negativní - dotaz je nesplnitelný a neuspel
Hana Rudová, Logické programování I, 25. února 2013
6
Úvod do Prologu
Dotaz
Dotaz: uživatel se ptá programu, zda jsou veci pravdivé
?- studuje( novak ). ?- studuje( novotny ).
Odpověď na dotaz
% yes % no
positivní - dotaz jě splnitelný a uspěl negativní - dotaz jě nesplnitelný a neuspěl
splnitělný dotaz něsplnitělný dotaz
Proměnné jsou behem výpoCtu instanciovány (= nahrazeny objekty)
?- clovek( novak, 18, Prace ). Prace = student
-í* výsledkem dotazu je instanciace proměnných v dotazu
A dosud nenainstanciovaná promenná: volná proměnná
Hana Rudová, Logické programování I, 25. února 2013
6
Úvod do Prologu
Dotaz
Dotaz: uživatel se ptá programu, zda jsou veci pravdivé
?- studuje( novak ). % yes        splnitelný dotaz
?- studuje( novotny ). % no nesplnitelný dotaz
Odpoveď na dotaz
A positivní - dotaz je splnitelný a uspel
± negativní - dotaz je nesplnitelný a neuspel
Proměnné jsou behem výpoCtu instanciovány (= nahrazeny objekty)
?- clovek( novak, 18, Prace ). Prace = student
-í* výsledkem dotazu je instanciace promenných v dotazu
A dosud nenainstanciovaná promenná: volná promenná
& Prolog umí generovat více odpovedí, pokud existují
?- clovek( novak, Vek, Prace ). % všechna rešení pres ";"
Hana Rudová, Logické programování I, 25. února 2013 6 Úvod do Prologu
Klauzule = fakt, pravidlo, dotaz
Klauzule se skláda z hlavy a tela & Telo je seznam cílů oddelených čárkami, cárka = konjunkce
& Fakt: pouze hlava, prázdné telo
Jť rodic( pavla, robert ).
-í* Pravidlo: hlava i telo
upracovany_clovek( X )      clovek( X, _Vek, Prace ), prace( Prace, tezka ).
& Dotaz: prázdná hlava, pouze telo
J* ?- clovek( novak, Vek, Prace ).
?- rodic( pavla, Dite ), rodic( Dite, Vnuk ).
Hana Rudová, Logické programování I, 25. února 2013
7
Úvod do Prologu
Rekurzivní pravidla
predek( X, Z ) :- rodic( X, Z). % (1)
predek( X, Z ) :- rodic( X, Y ), % (2)
rodic( Y, Z).
Hana Rudová, Logické programování I, 25. února 2013 8 Úvod do Prologu
Rekurzivní pravidla
predek( X, Z ) :- rodic( X, Z). % (1)
predek( X, Z ) :- rodic( X, Y ), % (2)
rodic( Y, Z).
predek( X, Z ) :- rodic( X, Y ), % (2')
predek( Y, Z).
Hana Rudová, Logické programování I, 25. února 2013
8
Úvod do Prologu
Příklad: rodokmen
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
pavla \		tomas	Rodice
	\ / robert / \	\ eliska	
/ anna		\ petr /	
	jirka		Deti
predek( X, Z ) :- rodic( X, Z ). % (1)
predek( X, Z ) :- rodic( X, Y ), % (2')
predek( Y, Z ).
Hana Rudová, Logičké přogřamování I, 25. únořa 2013 9 Úvod do Přologu
VýpoCet odpovědi na dotaz ?- predek(tomas,robert)
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
predek(tomas,robert)
dle (1)
yes
rodic(tomas,robert)
predek( X, Z )       rodic( X, Z ). % (1)
predek( X, Z )       rodic( X, Y ), % (2')
predek( Y, Z ).
Hana Rudová, Logické programování I, 25. února 2013
10
Úvod do Prologu
Výpocet odpovědi na dotaz ?- predek(tomas, petr)
predek(tomas, petr)
dle (1)
t
dle (2')
no
rodic( tomas, petr)
rodic(tomas, Y) predek( Y, petr)
rodic( tomas, robert ). rodic( tomas, eliska ). rodic( robert, petr ).
Y=robert
dle rodic(tomas, robert)
predek( robert, petr)
predek( X, Z ) :- rodic( X, Z ). % (1) predek( X, Z ) :- rodic( X, Y ), % (2')
predek( Y, Z ).
t
dle (1)
rodic(robert, petr)
yes
Hana Rudová, Logické programování I, 25. února 2013
Úvod do Prologu
Odpověd' na dotaz s proměnnou
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
pavla \		tomas	Rodice
	\/ robert / \	\ eliska	
/ anna		\ petr /	
	/ jirka		Deti
predek( X, Z ) :- rodic( X, Z).        % (1) predek( X, Z ) :- rodic( X, Y ),        % (2')
predek( Y, Z ).
predek(petr,Potomek) --> ???
Hana Rudová, Logické programování I, 25. února 2013
12
Úvod do Prologu
Odpoved' na dotaz s promennou
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
pavla \		tomas	Rodice
	\/ robert / \	\ eliska	
/ anna		\ petr /	
	/ jirka		Deti
predek( X, Z )       rodic( X, Z).        % (1) predek( X, Z )       rodic( X, Y ),        % (2')
predek( Y, Z).
predek(petr,Potomek) --> ??? Potomek=jirka
Hana Rudová, Logické programování I, 25. února 2013
12
Úvod do Prologu
Odpověď na dotaz s proměnnou
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
pavla \		tomas	Rodice
	\/ robert / \	\ eliska	
/ anna		\ petr /	
	/ jirka		Deti
predek( X, Z ) :- rodic( X, Z).        % (1) predek( X, Z ) :- rodic( X, Y ),        % (2')
predek( Y, Z ).
predek(petr,Potomek) --> ??? predek(robert,P) --> ???
Hana Rudová, Logické programování I, 25. února 2013
12
Potomek=jirka
Úvod do Prologu
Odpoved' na dotaz s přomennou
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, eliska ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
pavla \		tomas	Rodice
	\/ robert / \	\ eIiska	
/ anna		\ petr /	
	/ jirka		Deti
predek( X, Z ) i- rodic( X, Z ).        % (1) predek( X, Z ) i- rodic( X, Y ),        % (2')
predek( Y, Z ).
predek(petr,Potomek) --> ??? predek(robert,P) --> ???
Hana Rudová, Logičké programování I, 25. února 2G13
12
Potomek=jirka 1. P=anna, 2. P=petr, 3. P=jirka
Úvod do Prologu
Syntaxe a význam Prologovských programů
Syntaxe Prologovských programů
Typy objektů jsou rozpoznávány podle syntaxe Atom
3 retezce písmen, císel, „_" zacínající malým písmenem: pavel, pavel_novak, x25
a r etezce speciálních znaků: <-->, ====>
-i- r etezce v apostrofech: 'Pavel',  'Pavel Novák'
JS> Celá a reálná Čísla: 0, -1056, 0.35 & Promenná
-k r etezce písmen, císel, „_" zacínající velkým písmenem nebo „_"
3 anonymní promenná: ma_dite(X) :- rodic( X, _ ).
3 hodnotu anonymní promenné Prolog na dotaz nevrací: ?- rodic( X, _ )
š» lexikální rozsah promenné je pouze jedna klauzule:
prvni(X,X,X). prvni(X,X,_).
Hana Rudová, Logické programování I, 25. února 2013 14 Syntaxe a význam Prologovských programu
Termy
M Term - datové objekty v Prologu: datum( 1, kveten, 2003 )
a funktor: datum a argumenty: 1, kveten, 2003 &> arita - pocet argumentu: 3 M Všechny strukturované objekty v Prologu jsou stromy
trojuhelnik( bod(4,2), bod(6,4), bod(7,1) )
-í* Hlavní funktor termu - funktor v korenu stromu odpovídající termu
-i- trojuhelnikje hlavní funktor v trojuhelnik( bod(4,2), bod(6,4), bod(7,1) )
Hana Rudová, Logické programování I, 25. února 2013 15 Syntaxe a význam Prologovských programu
Unifikace
Termy jsou unifikovatelné, jestliže
jsou identické nebo
Jť promenné v obou termech mohou být instanciovány tak, že termyjsou po substituci identické
a datum( D1, M1, 2003 ) = datum( 1, M2, Y2)      operátor = D1 =1, M1 = M2, Y2 = 2003
Hana Rudová, Logické programování I, 25. února 2013
16
Syntaxe a význam Prologovských programu
Unifikace
Termy jsou unifikovatelné, jestliže
& jsou identické nebo
Jť promenné v obou termech mohou být instanciovány tak, že termyjsou po substituci identické
a datum( D1, M1, 2003 ) = datum( 1, M2, Y2)      operátor = D1 =1, M1 = M2, Y2 = 2003
& Hledáme nejobecnejší unifikátor (most generál unifier (MGU)
jiné instanciace? ... D1 = 1, M1 = 5, Y2 = 2003 ... není MGU ?- datum( D1, M1, 2003 ) = datum( 1, M2, Y2), D1 = M1.
Hana Rudová, Logické programování I, 25. února 2013
16
Syntaxe a význam Prologovských programu
Unifikace
Termy jsou unifikovatělné, jestliže
jsou identické nebo
Jť promenné v obou termech mohou být instanciovány tak, že termyjsou po substituci identické
a datum( D1, M1, 2003 ) = datum( 1, M2, Y2)      operátor = D1 =1, M1 = M2, Y2 = 2003
JS> Hledáme nejobecnější unifikátor (most generál unifier (MGU)
jiné instanciace? ... D1 = 1, M1 = 5, Y2 = 2003 ... není MGU ?- datum( D1, M1, 2003 ) = datum( 1, M2, Y2), D1 = M1.
& Test výskytu (occurs check)
?- X=f(X).
x = f(f(f(f(f(f(f(f(f(f(...))))))))))
Hana Rudová, Logické programování I, 25. února 2013
16
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, kl = k2 ... no,
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))...
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))... no
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, k1 = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes
s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))... no
s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))...
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes
s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))... no
s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... no
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, k1 = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes
s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))... no
s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... no
s(sss(A),4,ss(C)) = s(sss(t(B)),4,ss(A))...
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identické;
2. S je promenná a T cokoliv jiného - S je instanciována na T; Tje promenná a S cokoliv jiného - T je instanciována na S
3. S a T jsou termy
JS* S a T mají stejný funktor a aritu a
M všechny jejich odpovídající argumenty jsou unifikovatelné JÍ* výsledná substituce je urcena unifikací argumentu
Príklady:
k = k ... yes, k1 = k2 ... no, A = k(2,3) ... yes, k(s,a,l(1)) = A ... yes
s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(1))... no
s(sss(A),4,ss(3)) = s(sss(2),4,ss(A))... no
s(sss(A),4,ss(C)) = s(sss(t(B)),4,ss(A))... A=t(B),C=t(B)... yes
Hana Rudová, Logické programování I, 25. února 2013
17
Syntaxe a význam Prologovských programu
Deklarativní a procedurální význam přogřamu
p :- q, r.
& Deklařativní: Co je výstupem přogřamu?
a p je přavdivé, jestliže q a r jsou přavdivé
s Z q a r plyne p
=> význam mají logičké řelače
Hana Rudová, Logičké přogřamování I, 25. únořa 2013
18
Syntaxe a význam Přologovskýčh přogřamu
Deklarativní a procedurální význam programů
p :- q, r.
Deklarativní: Co je výstupem programu?
a p je pravdivé, jestliže q a r jsou pravdivé
s Z q a r plyne p
=> význam mají logické relace
Procedurální: Jak vypocítáme výstup programu?
-fc p vyřešíme tak, že nejprve vyřešíme q a pak r
=> krome logických relací je významné i poradí cílů a výstup
indikátor yes/no urcující, zda byly cíle splneny instanciace promenných v prípade splnení cílu
Hana Rudová, Logické programování I, 25. února 2013
18
Syntaxe a význam Prologovských programu
Konjunce "," vs. disjunkce ";" cílů
Konjunce = nutné splnení všech cílů
p :- q, r.
JS> Disjunkce = stací splnení libovolného cíle
ap:-q;r. p:-q.
p r.
a priorita středníku je vyšší (viz ekvivalentní zápisy):
p      q, r; s, t, u.
p      (q, r) ; (s, t, u).
p      q, r. p      s, t, u.
Hana Rudová, Logické programování I, 25. února 2013
19
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(a) a(1). ?- a(1).
a(X) :- b(X,Y), a(Y). b(1,1).
Hana Rudová, Logické programování I, 25. února 2013
20
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(a) a(1). ?- a(1). a(X) :- b(X,Y), a(Y).
b(1,1).
(b) a(X) :- b(X,Y), a(Y).       % zmenené poradí klauzulí v programu vzhledem k (a) a(1).
b(1,1).
Hana Rudová, Logické programování I, 25. února 2013
20
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(a) a(1). ?- a(1). a(X) :- b(X,Y), a(Y).
b(1,1).
(b) a(X) :- b(X,Y), a(Y).        % zmenené poradí klauzulí v programu vzhledem k (a) a(1).
b(1,1). % nenalezení odpovedi: nekonecný cyklus
Hana Rudová, Logické programování I, 25. února 2013
20
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílu
(a) a(1). ?- a(1). a(X) :- b(X,Y), a(Y).
b(1,1).
(b) a(X) :- b(X,Y), a(Y).       % zmenené poradí klauzulí v programu vzhledem k (a) a(1).
b(1,1). % nenalezení odpovedi: nekonečný cyklus
(c) a(X) :- b(X,Y), c(Y). ?- a(X). b(1,1).
c(2). c(1).
Hana Rudová, Logické programování I, 25. února 2013
20
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílu
(a) a(1).
a(X) :- b(X,Y), a(Y). b(1,1).
?- a(1).
(b) a(X) :- b(X,Y), a(Y).        % zmenené poradí klauzulí v programu vzhledem k (a) a(1).
b(1,1). % nenalezení odpovedi: nekonecný cyklus
(c) a(X) :- b(X,Y), c(Y).
b(1,1). c(2).
c(1).
(d) a(X) :- c(Y), b(X,Y).
b(1,1). c(2).
c(1).
?- a(X).
% zmenené poradí cílu v tele klauzule vzhledem k (c)
Hana Rudová, Logické programování I, 25. února 2013
20
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(a) a(1). ?- a(1). a(X) b(X,Y), a(Y).
b(1,1).
(b) a(X) b(X,Y), a(Y).        % zmenené poradí klauzulí v programu vzhledem k (a) a(1).
b(1,1). % nenalezení odpovedi: nekonecný cyklus
(c) a(X)       b(X,Y), c(Y). ?- a(X).
b(1,1). c(2).
c(1).
(d) a(X)      c(Y), b(X,Y).      % zmenené poradí cílu v tele klauzule vzhledem k (c) b(1,1).
c(2).
c(1). % nárocnejší nalezení první odpovedi než u (c)
V obou prípadech stejný deklarativní ale odlišný procedurální význam
Hana Rudová, Logické programování I, 25. února 2013 20 Syntaxe a význam Prologovských programu
Pořadí klauzulí a cílů II.
(1) a(X)  i- c(Y), b(X,Y).
(2) b(l,l).
(3) c(2).
(4) c(l).
?- a(X). a(X)
dle (1)
c(Y), b(X,Y) dle (3)/^Y=2    dle (4\ Y=1
b(X,2) no
b(X,1)
dle (2)
X=1
yes
Hana Rudová, Logičké programování I, ZS. února ZGlS
Syntaxe a význam Prologovskýčh programu
Poradí klauzulí a cílů II.
(1) a(X)  :- c(Y), b(X,Y).
(2) b(1,1).
(3) c(2).
(4) c(1).
Vyzkoušejte si:
(1) a(X) :- b(X,X), c(X).
(3) a(X) :- b(Y,X), c(X).
(4) b(2,2).
(5) b(2,1).
(6) c(1).
?- a(X). a(X)
dle (1)
c(Y), b(X,Y) dle (3)/^Y=2    dle (4\ Y=1
b(X,2) no
b(X,1)
dle (2)
X=1
yes
Hana Rudová, Logické programování I, 25. února 2013
21
Syntaxe a význam Prologovských programu
CviCení: průbeh výpoCtu
a :- b,c,d. b :- e,c,f,g. b :- g,h.
c.
d.
e :- i. e :- h.
gh.
i.
Jak vypadá pmbeh výpoctu pro dotaz ?- a.
Hana Rudová, Logické programování I, 25. února 2013
22
Syntaxe a význam Prologovských programu
Operátory, aritmetika
Operátory
-í* Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
± prefixovou notaci lze získat predikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
Hana Rudová, Logické programování I, 25. února 2013
24
Operátory, aritmetika
Operátory
-í* Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
± prefixovou notaci lze získat predikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
M Priorita operátorU: operátor s nejvyšší prioritou je hlavní funktor
-í* Uživatelsky definované operátory: zna
petr zna alese.      zna( petr, alese).
& Definice operátoru: :- op( 600, xfx, zna ). priorita: 1..1200
Hana Rudová, Logické programování I, 25. února 2013
24
Operátory, aritmetika
Operátory
Infixová notače: 2*a + b*c
Přefixová notače: +( *(2,a), *(b,c) ) přiořita +: 500, přiořita *: 400
± přefixovou notači lze získat předikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
Přiořita opeřátořU: opeřátoř s nejvyšší přiořitou je hlavní funktoř
Uživatelsky definované opeřátořy: zna
petr zna alese.      zna( petr, alese).
Definiče opeřátořu: :- op( 600, xfx, zna ). přiořita: 1..1200
:- op( 1100, xfy, ; ). nestřuktuřované objekty: 0
:- op( 1000, xfy, , ).
p :- q,r; s,t. p :- (q,r) ; (s,t).      ; má vyšší přiořitu než ,
:- op( 1200, xfx, :- ).       :- má nejvyšší přiořitu
Hana Rudová, Logičké programování I, 2S. února 2Gl3
24
Opeřátořy, ařitmetika
Operátory
-í* Infixová notace: 2*a + b*c
JS> Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
± prefixovou notaci lze získat predikátem display/1
:- display((a:-s(0),b,c)). :-(a,  ,(s(0), ,(b,c)))
M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
& Uživatelsky definované operátory: zna
petr zna alese.      zna( petr, alese).
JS> Definice operátoru: :- op( 600, xfx, zna ). priorita: 1..1200
:- op( 1100, xfy, ; ). nestrukturované objekty: 0
:- op( 1000, xfy, , ).
p :- q,r; s,t. p :- (q,r) ; (s,t).      ; má vyšší prioritu než ,
:- op( 1200, xfx, :- ).       :- má nejvyšší prioritu
-í* Definice operátoru není spojena s datovými manipulacemi   (krome spec. prípadu)
Hana Rudová, Logické programování I, 25. února 2013 24 Operátory, aritmetika
Typy operátorů
Typy operátorůu
pr.   xfx = yfx pr.   fx ?- fy
-i- infixové operátory: xfx, xfy, yfx
prefixové operátory: fx, fy a postfixové operátory: xf, yf
x a y urcují prioritu argumentu
x reprezentuje argument, jehož priorita musí být striktne menší než u operátoru y reprezentuje argument, jehož priorita je menší nebo rovna operátoru a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx
chybně
správně
/   \  \   p no rita: 0 p no rita: 0
a
by
p rio rita: 500
Hana Rudová, Logické programování I, 25. února 2013
priorita: 500
25
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
Hana Rudová, Logické programování I, 25. února 2013
26
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" jě speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
Hana Rudová, Logické programování I, 25. února 2013
26
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celočíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) a výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. zpusobí chybu
Hana Rudová, Logické programování I, 25. února 2013
26
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" je speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) a výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. zpusobí chybu
JS> Další speciální preddefinované operátory
>, <, >=, =<, =:= aritmetická rovnost, =\= aritmetická nerovnost
-i- porovnej:      1+2 =:= 2+1 1+2 = 2+1
Hana Rudová, Logické programování I, 25. února 2013
26
Operátory, aritmetika
Aritmetika
JS> Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikaci
M ?- X is 1 + 2.
X = 3      „is" jě speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
pravá strana musí být vyhodnotitelný výraz (bez promenné) a výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifikován s levou stranou volání ?- X is Y + 1. zpusobí chybu
JS> Další speciální preddefinované operátory
>, <, >=, =<, =:= aritmetická rovnost, =\= aritmetická nerovnost
-i- porovnej:      1+2 =:= 2+1 1+2 = 2+1
-fc obe strany musí být vyhodnotitelný výraz: volání ?- 1 < A + 2. zpusobí chybu
Hana Rudová, Logické programování I, 25. února 2013 26 Operátory, aritmetika
Ruzné typy rovností a porovnání
X = Y      Xa Y jsou unifikovatelné
X \= Y     Xa Y nejsou unifikovatelné, (také \+ X = Y)
Hana Rudová, Logické programování I, 25. února 2013
27
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y      Xa Y jsou unifikovatelné
X \= Y     Xa Y nejsou unifikovatelné, (také \+ X = Y)
X == Y     Xa Y jsou identické
porovnej:   ?-A == B. ... no      ?-A=B, A==B.
Hana Rudová, Logické programování I, 25. února 2013
27
Operátory, aritmetika
Ruzné typy rovností a porovnání
X=Y
X \= Y
X == Y
X \== Y
Xa Y jsou unifikovatelné
Xa Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Hana Rudová, Logické programování I, 25. února 2013
27
Operátory, aritmetika
Různé typy rovností a porovnání
X = Y X \= Y
X == Y
X \== Y
X is Y X =:= Y
X =\= Y
X < Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Y je aritmeticky vyhodnoceno a výsledek je přiřazen X
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
Hana Rudová, Logické programování I, 25. února 2013
27
Operátory, aritmetika
X = Y X \= Y X == Y
X \== Y
X is Y
X =:= Y X =\= Y
X < Y
X @< Y
Ruzné typy řovností a porovnání
Xa Y jsou unifikovatelné
Xa Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej: ?- A == B. ... no ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
X a Y jsou si ařitmetičky řovny
X a Y si ařitmetičky nejsou řovny
ařitmetičká hodnota X je menší než Y (=<, >, >=)
teřm X předčhází teřm Y (@=<, @>, @>=)
1. pořovnání teřmu: podle alfabetičkého n. ařitmetičkého uspořádání
2. pořovnání střuktuř: podle ařity, pak hlavního funktořu a pak
zleva podle ařgumentu
Hana Rudová, Logičké přogřamování I, 25. únořa 2013
27
Opeřátořy, ařitmetika
Různé typy rovností a porovnání
X = Y X \= Y
X == Y X \== Y
X is Y
X =:= Y X =\= Y
X < Y
X @< Y
X a Y jsou unifikovatelné
X a Y nejsou unifikovatelné, (také \+ X = Y)
X a Y jsou identické
porovnej:   ?- A == B. ... no      ?- A=B, A==B. ... B = A yes X a Y nejsou identické
porovnej:   ?- A \== B. ... yes      ?- A=B, A \== B. ... A no
Y je aritmeticky vyhodnoceno a výsledek je prirazen X
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
term X predchází term Y (@=<, @>, @>=)
1. porovnání termu: podle alfabetického n. aritmetického usporádání
2. porovnání struktur: podle arity, pak hlavního funktoru a pak
zleva podle argumentu ?- f( pavel, g(b)) @< f( pavel, h(a)). ... yes
Hana Rudová, Logické programování I, 25. února 2013
27
Operátory, aritmetika