Ú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, 22. února 2011
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. To appear in Theory and Practice of Logic Programming, 2010. http://arxiv.org/abs/1011.5640.
Hana Rudová, Logické programování I, 22. února 2011 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, 22. února 2011
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: množina pravidel a faktů 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, 22. února 2011 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, 22. únořa 2011
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, 22. února 2011
6
Úvod do Prologu
Dotaz
Dotaz: uživatel se ptá programu, zda jsou veci pravdivé
?- studuje( novak). ?- studuje( novotny).
% yes % no
splnitelný dotaz nesplnitelný dotaz
Odpověď na dotaz
A positivní - dotaz je splnitelný a uspěl
-í* negativní - dotaz je nesplnitelný a neuspel
Proměnné jsou behem výpoCtu instanciovány (= nahrazeny objekty)
-i- ?- clovek( novak, 18, Prace ).
A výsledkem dotazu je instanciace promenných v dotazu
-i- dosud nenainstanciovaná promenná: volná promenná
Hana Rudová, Logické programování I, 22. února 2011
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
JS> Odpověď na dotaz
A positivní - dotaz jě splnitelný a uspěl
-í* negativní - dotaz jě nesplnitelný a neuspěl
& Promenné jsou behem výpoctu instanciovány (= nahrazeny objekty)
-i- ?- clovek( novak, 18, Prace ).
A výsledkem dotazu je instanciace proměnných v dotazu
-i- dosud nenainstanciovaná promenná: volná proměnná
ií> Prolog umí generovat více odpovedí pokud existují
?- clovek( novak, Vek, Prace ). % všechna rešení pres ";"
Hana Rudová, Logické programování I, 22. února 2011 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, 22. února 2011
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, 22. února 2011 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, 22. února 2011
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, 22. únořa 2011 9 Úvod do Přologu
Výpocet odpovedi 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, 22. února 2011
10
Úvod do Prologu
Výpočet odpovedi 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, 22. února 2011
11
Úvod do Prologu
Odpoved' na dotaz ?- predek(robert, Potomek)
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(robert,Potomek) --> ???
Hana Rudová, Logické programování I, 22. února 2011
12
Ú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á cí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, 22. února 2011 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, 22. února 2011 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, 22. února 2011
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
JS> 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, 22. února 2011
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
& 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, 22. února 2011
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, k1 = k2 ... no,
Hana Rudová, Logické programování I, 22. února 2011
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, 22. února 2011
17
Syntaxe a význam Prologovských programu
Unifikace
Teřmy S a T jsou unifikovatelné, jestliže
1. S a T jsou konstanty a tyto konstanty jsou identičké;
2. S je přomenná a T čokoliv jiného - S je instančiována na T; Tje přomenná a S čokoliv jiného - T je instančiována na S
3. S a T jsou teřmy
JS* S a T mají stejný funktoř a ařitu a
M všečhny jejičh odpovídajíčí ařgumenty jsou unifikovatelné JÍ* výsledná substituče je uřčena unifikačí ařgumentu
Pří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á, Logičké přogřamování I, 22. únořa 2011
17
Syntaxe a význam Přologovskýčh přogřamu
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, 22. února 2011
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, 22. února 2011
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 identičké;
2. S je promenná a T čokoliv jiného - S je instančiována na T; Tje promenná a S čokoliv jiného - T je instančiována na S
B.Sa T jsou termy JS* S a T mají stejný funktor a aritu a
Ü všečhny jejičh odpovídajíčí argumenty jsou unifikovatelné JÍ* výsledná substituče je určena unifikačí 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
Hana Rudová, Logičké programování I, 22. února 20ll
17
Syntaxe a význam Prologovskýčh 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, 22. února 2011
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
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, 22. února 2011
17
Syntaxe a význam Prologovských programu
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
Hana Rudová, Logické programování I, 22. února 2011
18
Syntaxe a význam Prologovských programu
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ílu 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, 22. února 2011
18
Syntaxe a význam Prologovských programu
Deklarativní význam programu
Máme-li program a cíl G, pak deklarativní význam ríká:
cíl G je splnitelný práve tehdy, když cíl ?- ma_dite(petr).
existuje klauzule C v programu taková, že existuje instance I klauzule C taková, že hlava I je identická s G a všechny cíle v tele I jsou pravdivé.
Instance klauzule: promenné v klauzuli jsou substituovány termem
ma_dite(X)       rodic( X, Y ). % klauzule
ma_dite(petr)       rodic( petr, Z ).        % instance klauzule
Hana Rudová, Logické programování I, 22. února 2011
19
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šší:
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, 22. února 2011
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).
Hana Rudová, Logické programování I, 22. února 2011
21
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, 22. února 2011
21
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(a) a(1). ?- a(1). 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, 22. února 2011
21
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).
Hana Rudová, Logické programování I, 22. února 2011
21
Syntaxe a význam Prologovských programu
Poradí klauzulí a cílů
(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, 22. února 2011
21
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 případech stejný deklarativní ale odlišný procedurální význam
Hana Rudová, Logické programování I, 22. února 2011 21 Syntaxe a význam Prologovských 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).
?- 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, 22. února 2011
22
Syntaxe a význam Prologovských 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, 22. února 2011
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
M Priorita operátorů: operátor s nejvyšší prioritou je hlavní funktor
Hana Rudová, Logické programování I, 22. února 2011
24
Operátory, aritmetika
Operátory
JS* Infixová notače: 2*a + b*c
-í* Přefixová notače: +( *(2,a), *(b,c) ) přiořita +: 500, přiořita *: 400
M Přiořita opeřátořů: 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
Hana Rudová, Logičké přogřamování I, 22. únořa 2011
24
Opeřátořy, ařitmetika
Operátory
JS* Infixová notace: 2*a + b*c
-í* Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
M Priorita operátorů: 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
J> :- 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
Hana Rudová, Logické programování I, 22. února 2011
24
Operátory, aritmetika
Operátory
-í* Infixová notace: 2*a + b*c
& Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita *: 400
M Priorita operátorů: 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
J> :- 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 speciálních případů)
Hana Rudová, Logické programování I, 22. února 2011
24
Operátory, aritmetika
Typy operátorů
Typy operátoru
J* infixové operátory: xfx, xfy, yfx -i- prefixové operátory: fx, fy &> postfixové operátory: xf, yf
pr.   xfx = yfx pr.   fx ?- fy
x a y urcují prioritu argumentu
J* x reprezentuje argument, jehož priorita musí být striktne menší než u operátoru -i- y reprezentuje argument, jehož priorita je menší nebo rovna operátoru -fc a-b-c odpovídá (a-b)-c a ne a-(b-c): „-" odpovídá yfx
správně
priorita: 0 priorita: 0
chybně
priorita: 500
priorita: 500
Hana Rudová, Logické programování I, 22. února 2011
25
Operátory, aritmetika
Aritmetika
& 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
Hana Rudová, Logické programování I, 22. února 2011
26
Operátory, aritmetika
Aritmetika
-i* 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)
Hana Rudová, Logické programování I, 22. února 2011
26
Operátory, aritmetika
Aritmetika
& 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" jě speciální preddefinovaný operátor, který vynutí evaluaci
porovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
a pravá strana musí být vyhodnotitelný výraz (bez promenné) volání ?- X is Y + 1. způsobí chybu
Hana Rudová, Logické programování I, 22. února 2011
26
Operátory, aritmetika
Aritmetika
-i* Preddefinované operátory
+ , -i *i A ** mocnina, // celocíselné delení, 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)
a pravá strana musí být vyhodnotitelný výraz (bez promenné) 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, 22. února 2011
26
Operátory, aritmetika
Ařitmetika
Předdefinované opeřátořy
+ , -i *i A ** močnina, // celocíselné dělení, mod zbytek po delení
J* ?- X = 1 + 2. X = 1 + 2      = odpovídá unifikači
M ?- X is 1 + 2.
X = 3      „is" je speciální předdefinovaný opeřátoř, kteřý vynutí evaluači
pořovnej:      N = (1+1+1+1+1) N is (1+1+1+1+1)
a přavá střana musí být vyhodnotitelný výřaz (bez přomenné) volání ?- X is Y + 1. zpusobí čhybu
-i* Další spečiální předdefinované opeřátořy
>, <, >=, =<, =:= ařitmetická řovnost, =\= ařitmetická neřovnost
-i- pořovnej:      1+2 =:= 2+1 1+2 = 2+1
obe střany musí být vyhodnotitelný výřaz: volání ?- 1 < A + 2. zpusobí čhybu
Hana Rudová, Logičké přogřamování I, 22. únořa 2011 26 Opeřátořy, ařitmetika
Různé typy rovností a porovnání
X = Y      Xa Y jsou unifikovatelné
X \= Y     Xa Y nejsou unifikovatelné, (také \+ X = Y)
Hana Rudová, Logičké přogřamování I, 22. únořa 2011
27
Opeřátořy, ařitmetika
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, 22. února 2011
27
Operátory, aritmetika
Různé 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, 22. února 2011
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, 22. února 2011
27
Operátory, aritmetika
X = Y X \= Y
X == Y
X \== Y X is Y
X =:= Y X =\ = Y
X < Y
X @< Y
Různé typy rovností a porovnání
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
X a Y jsou si aritmeticky rovny
X a Y si aritmeticky nejsou rovny
aritmetická hodnota X je menší než Y (=<, >, >=)
term X předchá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
Hana Rudová, Logické programování I, 22. února 2011
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 @< 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í termů: 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, 22. února 2011
27
Operátory, aritmetika
Prolog: príklady
Příklad: průběh výpočtu
a :- b,c,d. b :- e,c,f,g. b :- g,h.
c.
d.
e :- i. e :- h.
gh.
i.
Jak vypadá průběh výpočtu pro dotaz ?- a.
Hana Rudová, Logické programování I, 22. února 2011
29
Prolog: príklad
Príklad: vež z kostek
Príklad: postavte vež zadané velikosti ze trí různe velkých kostek tak, že kostka smí ležet pouze na vetší kostce.
Hana Rudová, Logické programování I, 22. února 2011
30
Prolog: příklad
Príklad: vež z kostek
Príklad: postavte vež zadané velikosti ze trí různe velkých kostek tak, že kostka smí ležet pouze na vetší kostce.
kostka(mala).    kostka(stredni). kostka(velka).
vetsi(zeme,velka).   vetsi(zeme,stredni). vetsi(zeme,mala). vetsi(velka,stredni). vetsi(velka,mala). vetsi(stredni,mala).
% ?- postav_vez(vez(zeme,0), vez(Kostka,0)). % ?- postav_vez(vez(zeme,0), vez(Kostka,3)).
Hana Rudová, Logické programování I, 22. února 2011
30
Prolog: příklad
Príklad: vež z kostek
Príklad: postavte vež zadané velikosti ze trí různe velkých kostek tak, že kostka smí ležet pouze na vetší kostce.
kostka(mala).    kostka(stredni). kostka(velka).
vetsi(zeme,velka).   vetsi(zeme,stredni). vetsi(zeme,mala). vetsi(velka,stredni). vetsi(velka,mala). vetsi(stredni,mala).
% ?- postav_vez(vez(zeme,0), vez(Kostka,0)). % ?- postav_vez(vez(zeme,0), vez(Kostka,3)). postav_vez( Vez, Vez ).
postav_vez( Vstup, Vystup ) :- pridej_kostku( Vstup, Pridani ),
postav_vez( Pridani, Vystup ).
pridej_kostku( Vstup, Pridani ) :- Vstup = vez( Vrchol, Vyska ),
kostka( Kostka ), vetsi( Vrchol, Kostka ), NovaVyska is Vyska + 1, Pridani = vez( Kostka, NovaVyska ).
Hana Rudová, Logické programování I, 22. února 2011
30
Prolog: p ríklad