Prolog
Úvod do Prologu
PROgramming in LOCic
■ část predikátové logiky prvního řádu Deklarativní programování
■ specifikační jazyk, jasná sémantika, nevhodné pro procedurální postupy
■ Co dělat namísto Jak dělat Základní mechanismy
■ unifikace, stromové datové struktury, automatický backtracking
Prolog: historie a současnost
■ Rozvoj začíná po roce 1 970
■ Robert Kowalski - teoretické základy
■ Alain Colmerauer, David Warren (Warren AbstractMachine) - implementace
■ pozdější rozšíření Prologu o logické programování s omezujícími podmínkami
■ Prolog v současnosti
■ zavedené aplikační oblasti, nutnost přidání inteligence
■ hypotéky; pediatrický sw; konfigurace a pravidla pro stanovení ceny objednávky; testovací nástroje, modelové testování; ...
■ náhrada procedurálního kódu Prologem vede k
■ desetinásobnému zmenšení kódu, řádově menšímu času na vývoj, jednodušší údržbě
■ efektivita Prologu?
■ zrychlení počítačů + výrazné zvětšení nároků sw => ve prospěch kompaktnosti i rychlosti Prologu
Hana Rudová, Logické programování I, 17. února 2009 3 Úvod do Prologu
Hana Rudová, Logické programování I, 17. února 2009 2 Úvod do Prologu
Program = fakta + pravidla
■ (Prologovský) program je seznam programových klauzulí
■ programové klauzule: fakt, pravidlo
■ Fakt: deklaruje vždy pravdivé věci
■ clovekC novak, 18, student ).
■ Pravidlo: deklaruje věci, jejichž pravdivost závisí na daných podmínkách
■ studujeC X ) :- c"lovek( X, _Vek, student ).
■ alternativní (obousměrný) význam pravidel
pro každé X, pro každé X,
X studuje, jestliže X je student, potom
Xje student X studuje
■ pracujeC X ) :- c"lovek( X, _Vek, CoDela ), praceC CoDela ).
■ Predikát: množina pravidel a faktů se stejným funktorem a aritou
■ značíme: clovek/3, student/l; analogie procedury v procedurálních jazycích,
Hana Rudová, Logické programování I, 17. února 2009 4 Úvod do Prologu
Komentáře k syntaxi
■ Klauzule ukončeny tečkou
■ Základní příklady argumentů
■ konstanty: (tomas , anna) ... začínají malým písmenem
■ proměnné
■X, Y ... začínají velkým písmenem
■ _, _A, _B ... začínají podtržítkem (nezajímá nás vracená hodnota)
■ Psaní komentářů
clovekC novak, 18, student ). % komentář na konci řádku
clovekC novotny, 30, učitel ). /* komentář '■'•'/
Hana Rudová, Logické programování I, 17. února 2009 5 Úvod do Prologu
Klauzule = fakt, pravidlo, dotaz
■ Klauzule se skládá z hlavy a těla
■ Tělo je seznam cílů oddělených čárkami, čárka = konjunkce
■ Fakt: pouze hlava, prázdné tělo
■ rodicC pavla, robert ).
■ Pravidlo: hlava i tělo
■ upracovany_c"lovek( X ) :- clovekC X, _Vek, Prace ), praceC Prace, tezka ).
■ Dotaz: prázdná hlava, pouze tělo
■ ?- clovekC novak, Vek, Prace ).
?- rodicC pavla, Ditě ), rodicC Dite, Vnuk ).
Hana Rudová, Logické programování I, 17. února 2009 7 Úvod do Prologu
Dotaz
■ Dotaz: uživatel se ptá programu, zda jsou věci pravdivé
?- studuje( novak). % yes        splnitelný dotaz
?- studuje( novotny). % no nesplnitelný dotaz
■ Odpověď na dotaz
■ positivní - dotaz je splnitelný a uspěl
■ negativní - dotaz je nesplnitelný a neuspěl
■ Proměnné jsou během výpočtu instanciovány (= nahrazeny objekty)
■ ?- clovekC novak, 18, Prace ).
■ výsledkem dotazuje instanciace proměnných v dotazu
■ dosud nenainstanciovaná proměnná: volná proměnná
■ Prolog umí generovat více odpovědí pokud existují
?- clovekC novak, Vek, Prace ). % všechna řešení přes ";"
Hana Rudová, Logické programování I, 17. února 2009 6 Úvod do Prologu
Rekurzivní pravidla
predekC X, Z ) :- rodicC X, Z ). % (1)
predekC X, Z ) :- rodicC X, Y ), % C2)
rodicC Y, Z ).
predekC X, Z ) :- rodicC X, Y ), % C2')
predekC Y, Z ).
Hana Rudová, Logické programování I, 17. února 2009 8 Úvod do Prologu
Příklad: rodokmen
Výpočet odpovědi na dotaz ?- predek(tomas,robert)
rodic( pavla, robert ).
rodic( tomas, robert ).
rodic( tomas, e "liská ).
rodic( robert, anna ).
rodic( robert, petr ).
rodic( petr, jirka ).
predek( X, Z ) :- rodic( X, Z )
% (D
predek( X, Z ) :- rodic( X, Y ), % (2')
predek( Y, Z ).
Hana Rudová, Logické programování I, 17. února 2009
Úvod do Prologu
rodi rodi rodi rodi rodi
c( pavla, robert ).
c( tomas, robert ) .
c( tomas, eli ska ).
c( robert, anna ).
c( robert, petr ).
rodic( petr, jirka ).
yes
predek(tomas,robert)
dle (1)
rodic(tomas, robert)
predek( X, Z ) predek( X, Z )
rodic( X, Z ). % (1)
rodic( X, Y ), % (2')
predek( Y, Z ).
Hana Rudová, Logické programování I, 17. února 2009
Úvod do Prologu
Výpočet odpovědi na dotaz ?- predek(tomas, petr)
predek(tomas, petr)
dle (1)
dle (2')
no     rodic( tomas, petr)
rodic(tomas, Y) predek( Y, petr)
rodicC tomas, robert ). rodicC tomas, eliska ). rodicC robert, petr ).
Y=robert
dle rodic(tomas, robert)
predek( robert, petr)
predekC X, Z ) predekC X, Z )
rodicC X, Z ). % Cl) rodicC X, Y ), % (2') predekC Y, Z ).
dle (1)
rodic(robert, petr)
Hana Rudová, Logické programování I, 17. února 2009
yes
Úvod do Prologu
Odpověď na dotaz ?- predek(robert, Potomek)
rodicC pavla, robert ).
rodicC tomas, robert ).
rodicC tomas, eliska ).
rodicC robert, anna ).
rodicC robert, petr ).
rodicC petr, jirka ).
predekC X, Z ) predekC X, Z )
rodicC X, Z ). rodicC X, Y ), predekC Y, Z ).
predekCrobert,Potomek) --> ???
Hana Rudová, Logické programování 1,17. února 2009 1 2
Úvod do Prologu
Syntaxe Prologovských programů
Syntaxe a význam Prologovských programu
Termy
Term - datové objekty v Prologu: datum( 1, kveten, 2003 )
■ funktor: datum
■ argumenty: 1, kveten, 2003
■ arita - počet argumentů: 3
Všechny strukturované objekty v Prologu jsou stromy
■ trojuhelnikC bod(4,2), bod(6,4), bod(7,l) )
Hlavní funktor termu - funktor v kořenu stromu odpovídající termu
■ trojuhelnikje hlavní funktor v trojuhelnik( bod(4,2), bod(6,4), bod(7,l) )
Hana Rudová, Logické programování I, 17. února 2009
Syntaxe a význam Prologovských programů
1 Typy objektů jsou rozpoznávány podle syntaxe 1 Atom
■ řetězce písmen, čísel, „_" začínající malým písmenem: pavel , pavel_novak, x25
■ řetězce speciálních znaků: <-->, ====>
■ řetězce v apostrofech: 'Pavel', 'Pavel Novák'
' Celá a reálná čísla: 0, -1056, 0.35 1 Proměnná
■ řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_"
■ anonymní proměnná: ma_dite(X) :- rodic( X, _ ).
■ hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodic( X, _ )
■ lexikální rozsah proměnné je pouze jedna klauzule:
prvni(X,X,X). prvni(X,X,_).
Hana Rudová, Logické programování I, 17. února 2009 14 Syntaxe a význam Prologovských programů
Unifikace
1 Termy jsou unifikovatelné, jestliže
■ jsou identické nebo
■ proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické
■ datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2)      operátor = Dl = 1, Ml = M2, Y2 = 2003
1 Nejobecnější unifikátor (most generál unifler (MGU)
■ jiné instanciace?...Dl = 1, Ml = 5, Y2 = 2003
■ ?- datumC Dl, Ml, 2003 ) = datum( 1, M2, Y2), Dl = Ml.
1 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, 17. února 2009
Syntaxe a význam Prologovských programů
Unifikace
Termy S a T jsou unifikovatelné, jestliže
1. SaTjsou konstanty a tyto konstanty jsou identické;
2. S je proměnná a T cokoliv jiného - S je instanciována na T; Tje proměnná a S cokoliv jiného - Tje instanciována na S
3. S a T jsou termy
■ S a T mají stejný funktor a aritu a
■ všechny jejich odpovídající argumenty jsou unifikovatelné
■ výsledná substituce je určena unifikací argumentů
Příklady:
k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,1(1)) = A ... yes s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(l))... no s(sssCA),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, 17. února 2009 17 Syntaxe a význam Prologovských programů
Deklarativní význam programu
Máme-li program a cíl C, pak deklarativní význam říká:
cíl C je splnitelný právě tehdy, když cíl ?- ma_dite(petr).
existuje klauzule C v programu taková, že existuje instance I klauzule C taková, že hlava Ije identická s Ca všechny cíle v těle Ijsou pravdivé.
Instance klauzule: proměnné v klauzuli jsou substituovány termem
■ ma_dite(X) :- rodic( X, Y). % klauzule
ma_dite(petr) :- rodic( petr, Z ).        % instance klauzule
Deklarativní a procedurální význam programů
■ p :- q, r.
■ Deklarativní: Co je výstupem programu?
■ p je pravdivé, jestliže q a r jsou pravdivé
■ Z q a r plyne p
=> význam mají logické relace
■ Procedurální: Jak vypočítáme výstup programu?
■ p vyřešíme tak, že nejprve vyřešíme q a pak r => kromě logických relací je významné i pořadí cílů
■ výstup
■ indikátor yes/no určující, zda byly cíle splněny
■ instanciace proměnných v případě splnění cílů
Hana Rudová, Logické programování 1,17. února 2009 1 8 Syntaxe a význam Prologovských programů
Konjunce "," vs. disjunkce ";" cílů
■ Konjunce = nutné splnění všech cílů
■ p :- q, r.
■ Disjunkce = stačí splnění libovolného cíle
■ p :- q; r. p :- q.
p :- r.
■ priorita středníku je vyšší: p :-q, r; s, t, u.
P :- Cq, r) ; (s, t, u).
P :- q, r. p : - s , t, u .
Hana Rudová, Logické programování I, 17. února 2009 19 Syntaxe a význam Prologovských programů Hana Rudová, Logické programování I, 17. února 2009 20 Syntaxe a význam Prologovských programů
Pořadí klauzulí a cílů
Ca) a(l).
a(X)  :- b(X,Y), a(Y). b(l,l).
?- a(l).
(b) a(X)  :- b(X,Y), a(Y). a(l). b(l,l).
% změněné pořadí klauzulí v programu vzhledem k (a) % nenalezení odpovědi: nekonečný cyklus
(c) a(X)  :- b(X,Y), c(Y). ?- a(X). b(l,l).
c(2). c(l).
(d) a(X) :- c(Y), b(X,Y).      % změněné pořadí cílů v těle klauzule vzhledem k (c) bCl.D.
c(2).
c(l) . % náročnější nalezení první odpovědi než u (c)
V obou případech stejný deklarativní ale odlišný procedurální význam
Hana Rudová, Logické programování I, 17. února 2009
Syntaxe a význam Prologovských programů
Operátory, aritmetika
Pořadí klauzulí a cílů II.
(1) a(X)  :- c(Y), b(X,Y).
(2) b(l,l).
(3) c(2).
(4) c(l).
Vyzkoušejte si:
a(X)  :- b(X,X), c(X).
a(X)  :- b(X,Y), c(X).
b(2,2).
b(2,l).
c(l).
Hana Rudová, Logické programování I, 17. února 2009
?- a(X).
a(X)
dle (1
c(Y), b(X,Y) dle (3j/Ý=2    dle (4)\Y=1
b(X,2) b(x>1) no dle (2) X=1
yes
Syntaxe a význam Prologovských programů
Operátory
Infixová notace: 2*a + b*c
Prefixová notace: +( *(2,a), *(b,c) ) priorita +: 500, priorita*: 400
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 ).
■ :- op( 1100, xfy,  ; ). :- 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 (kromě speciálních případů)
priorita: 1..1200 nestrukturované objekty: 0
Hana Rudová, Logické programování I, 17. února 2009
Operátory, aritmetika
Typy operátorů
■ Typy operátorů
■ infixové operátory: xfx, xfy, yfx př.   xfx =   yfx -
■ prefixové operátory: fx, fy př.   fx ?-   fy-
■ postfixové operátory: xf, yf
■ x a y určují prioritu argumentu
■ x reprezentuje argument, jehož priorita musí být striktně 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
priorita: 500
Hana Rudová, Logické programování I, 17. února 2009 25 Operátory, aritmetika
Aritmetika
■ Předdefinované operátory
+ , -, *, /, '■'•"■'•'mocnina,// celočíselné dělení, mod zbytek po dělení
■ ?- X = 1 + 2. X=l + 2      = odpovídá unifikaci
■ ?- X i s 1 + 2.
X = 3      „i s" je speciální předdefinovaný operátor, který vynutí evaluaci
■ porovnej:      N = (1+1+1+1+1) N i s (1+1+1+1+1)
■ pravá strana musí být vyhodnotitelný výraz (bez proměnné) volání?- X i s Y + 1. způsobí chybu
■ Další speciální předdefinované operátory
>, <, >=, =<, =:= aritmetická rovnost, =\= aritmetická nerovnost
■ porovnej:      1+2 =:= 2+1 1+2 = 2+1
■ obě strany musí být vyhodnotitelný výraz: volání ?- 1 < A + 2. způsobí chybu
Hana Rudová, Logické programování I, 17. února 2009 26 Operátory, aritmetika
Různé typy rovností a porovnání
X = Y       X a Y jsou unifikovatelné
X \= Y     X a Y nejsou unifikovatelné, (také \+ X = Y)
X == Y     X a Y jsou identické
porovnej:   ?-A == B. ... no      ?-A=B, A==B. ... B = A yes X \== Y    X a Y nejsou identické
porovnej:   ?- A \== B. .. .yes      ?- A=B, A \== B. ... A no X i s Y     Y je aritmeticky vyhodnoceno a výsledek je přiřazen X X =:= Y   X a Y jsou si aritmeticky rovny X =\= Y    X a Y si aritmeticky nejsou rovny X < Y       aritmetická hodnota X je menší než Y (=<, >, >=) X @< Y    term X předchází term Y (@=<, @>, @>=)
1. porovnání termů: podle alfabetického n. aritmetického uspořádání
2. porovnání struktur: podle arity, pak hlavního funktoru a pak
zleva podle argumentů ?- f( pavel, g(b)) @< f( pavel, h(a)). .. .yes
Prolog: příklady
Hana Rudová, Logické programování I, 17. února 2009
Operátory, aritmetika
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.
g-
h.
i.
Jak vypadá průběh výpočtu pro dotaz ?- a.
Hana Rudová, Logické programováni I, 17. února 2009 29 Prolog: přiklad
Příklad: věž z kostek
Příklad: postavte věž zadané velikosti ze tří různě velkých kostek tak, že kostka smí ležet pouze na větší kostce.
kostka(mala).    kostka(stredni).    kostka(velka).
vetsi(zeme,velka).    vetsi(zeme,st redni).    vetsi(zeme,mal a). vetsi(velka,st redni).    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, Přidáni ),
postav_vez( Přidáni, Vystup ).
pridej_kostku( Vstup, Přidáni )  :- Vstup = vez( Vrchol, Vyska ),
kostka( Kostka ), vetsi( Vrchol, Kostka ), NovaVyska i s Vyska + 1, Přidáni = vez( Kostka, NovaVyska ).
Hana Rudová, Logické programováni I, 17. února 2009 30 Prolog: přiklad