Prolog (add)
Jan Hric, KTI MFF UK,1997-2007ahttp://kti.ms.mff.cuni.cz/~hric
DodatkyVyhledávací stroj Aho-Corasicková 0-6
Mobily – pověšené rybičky – viz p4
log. Vyrazy viz p4
Řešení podmínek, v konečných doménách – dokončit
- algebrogramy
AC0 – stroj Aho-Corasicková Vzorky: 0a1b2, 0b3a4, 0a1c5; n=|T|, k=|vzorky| , s=|abeceda|% interface out/2, out(Vzorky/stav, Pozice/zbytek textu), taky dále% ac_Stav(TextVstupni), stav stroje = stav prog. (aktuální predikát)ac_0([a|T]):- ac_1(T). % goto(0,a)=1 Aac_0([b|T]):- ac_3(T). % anebo použít řez (na zač.), kl. „C“ je default Bac_0([P|T]):- P\=a,P\=b, ac_0(T). % goto(Abeceda,0)=0, rozepsat Cac_1([b|T]):- out([ab],T), ac_2(T). % out(2)= {ab} Dac_1([c|T]):- out([ac],T), ac_5(T). % out je pro všechny stroje stejná Eac_1([P|T]):- P\=b,P\=c, ac_0([P|T]). % fail(1)=0, bez čtení znaku, lépe s “!”
Fac_2(T):- ac_3(T). % fail(2)=3, !konstrukce je v jiném pořadí Gac_3([a|T]):- !, out([ba],T), ac_4(T). % varianta s !: determinismus Hac_3(T):- ac_0(T). % ošetřuje pouze zbylá písmena (P\=a), viz. řez Iac_4(T):- ac_1(T). % Jac_5(T):- ac_0(T). % K Víc abstrakce: stav AC stroje jako (explicitní) data (místo IP) I tento způsob se používá, při synt. analýze rekurzivním sestupem
AC1: (virtuální) stroj Aho-Corasicková, simulátor Vzorky: 0a1b2, 0b3a4, 0a1c5; n=|T|, k=|vzorky| , s=|abeceda|% interface out/2, out(Vzorky/stav, Pozice/zbytek textu), taky dále% ac1(Stav,TextVstupni), ac1(0,[a|T]):- ac1(1,T). % goto(0,a)=1 Aac1(0,[b|T]):- ac1(3,T). % Bac1(0,[P|T]):- P\=a,P\=b, ac1(0,T). % goto(Abeceda,0)=0, rozepsat Cac1(1,[b|T]):- out([ab],T), ac1(2,T). % out(2)= {ab} Dac1(1,[c|T]):- out([ac],T), ac1(5,T). % Eac1(1,[P|T]):- P\=b,P\=c, ac1(0,[P|T]). % fail(1)=0,bez čtení znaku !! Fac1(2,T):- ac1(3,T). % fail(2)=3, !konstrukce je v jiném pořadí Gac1(3,[a|T]):- !, out([ba],T), ac1(4,T). % varianta s !: determinismus
Hac1(3,T):- ac1(0,T). % ošetřuje pouze zbylá písmena (P\=a), viz. řez Iac1(4,T):- ac1(1,T). % Jac1(5,T):- ac1(0,T). % K Výhoda explicitní reprezentace: lépe se ladí/trasuje, vypisuje … Stavy nemusí být čísla, ale odpovídající „prefixy“ (anebo obojí )
AC2: rozskoky, 1 kl.= 1 stav
% ac2(Stav.Text)ac2(0,[P|T):- P=a -> ac2(1,T)
; P=b -> ac2(3,T) % bez: out([],T) optimalizace; ac2(0,T) . % goto(_,0)=0, zarážka v 0
ac2(1,[P|T]):- P=b -> out([ab],T),ac2(2,T); P=c -> out([ac],T), ac2(5,T); ac2(0,[P|T]). % fail(1)=0
ac2(3,[P|T]):- P=a -> out([ba],T),ac2(4,T); ac2(0,[P|T]). % fail(3)=0
ac2(2,T):- ac2(3,T). % fail(2)=3ac2(4,T):- ac2(1,T). ac2(S,T):- S=5, ac2(0,T). % když fail(S)=0, záchytná kl. - catchAll
AC3: interpret (vygenerované) databáze
% ac3(Stav,Text), interface: goto_def/2, goto_fnc/3, fail_fnc/2ac3(S,[P|T]):- goto_def(S,P)
-> goto_fnc(S,P,S1), out(S1,In), ac3(S1,T); fail_fnc(S,S1), ac3(S1,[P|T]) . %vstup stejný
% možná implementace goto_def, ale chci paměť O(k), ne O(s.k)goto_def(S, P) :- goto_fnc(S, P, _S1).- Nevýhoda AC3: pouze 1 stroj (v databázi)- Řešení: pojmenovat stroj, předávat jméno vždy v 1. argumentu,
taky přidat do procedur interface: AC4- (Lepší) idea: Místo jména, tj. symbolické reprezentace použít
(v_Prologu) konkrétní reprezentaci termem (! jedním); - V C++, (PHP), FLEX: zlinearizovaná reprezentace (string ), generovaná,
pro inicializaci pole „instrukcí“ a dat, …
AC5: interpret struktury % ac5(ACRepr,StavRepr,Text,AccVystup,Vystup) % typ ACRepr: [NStav-f(Out,Fail,[Pism-Nstav])]ac5(AC,S,[P|T],V1,V0):- S=f(Out,Fail,Gotos), ( lookup(P,Gotos,NStav1) % O(s) až O(log s), penalizace
-> out(Out,T,V1,V2), % Out taky [] (prázdný)lookup(NStav1,AC,S1), % O(k) až O(log k)ac5(AC, S1,T,V2,V0)
; lookup(Fail,AC,S1), % penalizaceac5(AC,S1,[P|T],V1,V0) % při fail – bez „čtení“ P
) . ?- AC=[0-f([],err,[a-1,b-3,c-0]), 1-f([],0,[b-2]), 2-f([ab],3,[]),..],
lookup(0,AC,S0), % inicializaceac5(AC, S0, Text, [], Vystup). % chci Vystup
AC : porovnání přístupu AC0 - AC2: rychlý, generujeme program, v konkrétní
syntaxi, tj. složitější na generování AC5, AC4: pomalejší, generujeme d.s. (postupně)
Konkrétní strukturu (+ interface) lze změnit Místo seznamů vyhledávací stromy : O(k) -> O(log k)
Porovnání přístupů (experimentální informatika): změřit Implementace AC 0-6, repr. d.s., impl. (optimalizace) Prologu
Interpret DSL – Domain Specific Language Datová struktura je popis (jednoúčelového) jazyka (Př.: vzorky v grep-u, stringy při volání SQL)
Zkombinování přístupů: vytvoříme data pro AC5automaticky pomocí částečného vyhodnocování (partial evaluation) z dat a interpretu AC5 vytvoříme AC0/AC1-like
(Generování AC1)
Příklad: jedna klauzule
genAC1(g(S,P,S0),Out, Kl) :-
Kl = (ac1(S,[P|Ps]) :- !, out(Out,Ps), ac1(S0,Ps) ) .
genAC1(f(S,S0), Kl) :-
Kl = (ac1(S, Ps) :- ac1(S0,Ps) ). % řez v minulých kl. Generování AC0 je složitější, musíme vytvořit jména
procedur Generování: z logického hlediska je jedno, zda
generujeme do a) souboru nebo b) databáze
AC6 on-the-fly, vstupy
Možnosti vstupu (pro kompilátor): ac6([[a,b], [b,a], [a,c]], Text). Písmena jako atomy ac6([ab, ba, ac], Text). Slova jako atomy ac6([“ab“, “ba“, “ac“], Text). řetězce
AC6: Kompilace on-the-fly, tj. za běhuac6(Vz,T,Out):- mk_ac6(Vz,AC), /*save,*/ ac6a(AC,T,Out). Interní struktura AC je schovaná (kompilace taky, srv. grep) možnost uschovat kompilovanou verzi (správa a la make) Text nemusí mít stejnou reprezentaci jako vzorky, kriterium:
Komp.: aby se jednoduše pracovalo Běh: rychlost
Používat explicitní data, vhodnou (termovou) reprezentaci, vhodný interface (a knihovny) …
Zavěsné mobily – viz p4 Vyváženost, bezpečnost mobilu: vracíme seznam “chybných” mobilů D.s.: m(DelkaL-MobilL, DelkaR-MobilR) nebo z(Hmotnost)jeVyv(z(H), H, V, V).jeVyv(m(DL-ML,DR-MR),H,V1,V0):- % do V0 se vloží správná hodn., podle větve jeVyv(ML,HL,V1,V2), jeVyv(MR,HR,V2,V3), % „stav“ - tok dat V1->V2->V3->V0 H is HL+HR, % celková hmotnost (jeVyvKoren(DL,HL,DR,HR) -> V0 = V3 % „přiřazení“ výstupu V0
; V0 = [m(DL-ML,DR-MR)|V3] ). % dtto, se změnoujeVyvKoren(DL,HL, DR,HR):- DL*HL=:=DR*HR.
jeBezp(z(_H),0,V,V).jeBezp(m(DL-ML,DR-MR), D,V1,V0):- jeBezp(ML,D1,V1,V2), jeBezp(MR,D2,V2,V3), D is max(DL+D1,DR+D2), % delší rameno D (jeBezpKoren(DL,D1, DR,D2) -> V0=V3
; V0 = [m(DL-ML,DR-MR)|V3] ). jeBezpKoren(DL,D1, DR,D2) :- DL+DR < D1+D2.
Insert do AVL stromu strukt: v/0, t(Levy,Koren, < = >, Pravy) i(+Strom, +Y, -NovyStrom, +deltaHloubky: inc,noinc)i(v,Y,t(v,Y,=,v),inc). % dále pouze přidávání do levého podstromui(t(L,X,V,R),Y,t(L0,X,V0,R),DH0):-Y@<X,(V= =;V= <),
i(L,Y,L0,DH), upd0(V,DH,V0,DH0). %bez změny hloubkyi(t(t(LL,LX,LV,LR),X,>,R), Y ,t(LL0,LX,LV0,t(LR,X,=,R),DH0):-
Y@<LX, (LV= =;LV= <), i(LL,Y,LL0,DH), upd1(LV,DH,LV0,DH0). %jednoduchá rotace
i(t(t(LL,LX,LV,t(LLL,LLX,LLV,LLR)), X,V,R), Y, t(t(LL,LX,V1,LLL0),LLX,=,t(LLR,X,V3,R)), noinc):- %dvojitá r.Y@<LLX, LX@=<Y, i(LLL,Y,LLL0,DH), upd2(left,LLV,…).
i(t(t(LL,LX,LV,t(LLL,LLX,LLV,LLR)),X,V,R), Y, t(t(LL,LX,V1,LLL),LLX,=,t(LLR0,X,V3,R)), noinc):- Y@>=LLX, LX@=<X, i(LLR,Y,LLR0,DH), upd2(right,…).
upd0(V,D,V0,D0):- member(f(V,D,V0,D0), [f(X,noinc,X,noinc), f(=,inc,>,inc), f(<,inc, =,noinc)]). % seznam případů místo klauzulí
upd1(V,D,V0,D0):- member(f(V,D,V0,D0), [f(=,noinc,<,noinc), f(=,inc,=,inc), f(<,inc,<,inc)]). % ??
upd2(S,V,D,V1,V2,noinc):- member(f(S,V,D,V1,V2), [f(left,>,noinc,>,<), f(_,=,noinc,>,<), f(left,>,inc,=,<), f(left,=,inc,=,=), f(right,>,inc,>,=), f(right,=,inc,>,=)]).
Jiná reprezentace: vyvážení jako čísla -1, 0, +1 .
N dam
N neohrožujících se dam na šachovniciqueens(N,Qs):- range(1,N,Ns), permutation(Ns,Qs), safe(Qs).
%generuj a testujsafe([]).safe([Q|Qs]):- safe(Qs), not attack(Q,Qs).attack(X,Xs):- attack(X,1,Xs).attack(X,N,[Y|Ys]):- X is Y+N ; X is Y-N.attack(X,N,[Y|Ys]):- N1 is N+1, attack(X,N1,Ys).range(N,N,[N]). % gen. seznam čísel medzi M a N, expl. repr.range(M,N,[M|Ns]):-M<N, M1 is M+1, range(M1,N,Ns).
Logické výrazy
DFS
390 Okompilator 460
Seznam všech řešení
Všechny kombinace dané velikosti v seznamu
komb(0,_,[[]]).
komb(N,[],[[]]):- N>0. % vždy uspěje, i s prázdným výsl.
komb(N,[X|L],V):- N>0, N1 is N-1,
komb(N1,L,V1), komb(N,L,V2),
map_insert(X,V1,V11),
append(V11,V2,V).
map_insert(X,[],[]).
map_insert(X,[L|Ls],[[X|L]|Ls0]):-map_insert(Ls,Ls0).
Reseni omezujicich podminek
Viz prednasky R. Bartaka Mnoho uloh lze zformulovat jako reseni podminek v
konecnych domenach: algebrogramy, barveni grafu, sudoku, krizovka
algebrogramy
konkrétní interface: několik možností 1. alg([“AB*AB=CAB“,“A+D=C“],V). % a vztah „A“-A 2. alg([a([A,B],*,[A,B],[C,A,B]),a([A],+,[D],[C])],V).
Metody 1. Generuj a testuj, najednou 2. Generuj postupně a testuj co nejdřív 3. Generuj ve vhodném pořadí, nejvíce omezené prom. nejdřív
Pořadí staticky předpočítané, např.: některé prvky jsou známé (algebr. S čísly, sudoku) nebo různě variabilní (křížovka, s tajenkou)
4. Dynamický výběr proměnných, podle počtu možných hodnot A další: Constraint (Logic) Programming, zde konečné domény
Voláme testy, tj. omezení, nejdřív a systém si je uloží, pak generuje ahned vylučuje nepřípustné hodnoty.
Algebrobramy
Interface g/1, t/1 – generuj a testuj1. g(A),g(B),g(C),g(D),t(…).2. g(A),g(B),g(C),t([a([A,B],*,[A,B],[C,A,B])]), g(D),…3. g(B),t([a([B],*,[B],[_,B])]), g(A), t(…), g(C),t(..,),…
Pořadí testů volíme, abychom mohli co nejdřív (#gen.) otestovat co nejvíc (#testů) a co nejvíc prořezali (#výsl.)
t/1 považuje volné proměnné za existenční
4. idea: Ke každé proměnné si pamatujeme seznam hodnot, pro které existuje nejaké řešení (nemožné hodnoty vyloučíme), dynamicky vybíráme nejvíce omezenou proměnnou.
g(X):-member(X,[0,1,2,3,4,5,6,7,8,9]).
Generuje a testuj
%
?- gen1([A11,A12,A13,..,A21,A22,A23,..], [1,2,3,4,5,6,7,8,9]),
data1([A22-3,A42-5,..]),
test1([alldiff([A11,A12..A19]),..alldiff([A11,A21..A91])
alldiff([A11,A12,A13,A21,A22,A23,A31,A32,A33]),..]).- Neefektivni- Lepe: gen. castecne a testuj; gen. v poradi , gen.
dynamicky
Programování s omezujícími podmínkami
Prolog řeší rovnice nad “symbolickými” výrazy jiné domény: reálná čísla, konečné domény, řetězce,
množiny, grafy ... interface Prolog - řešič
Prolog posílá podmínky (a odebírá), deklarativně řešič vrací “soustava podmínek je řešitelná” na konci výpočtu: nějaký tvar řešení
zjednodušené podmínky (vyřešený tvar) posloupnost řešení
př.: rovnice nad reálnými čísly vyřešené lineární rovnice a nerovnice s par. zbylé nelineární podm.
Konečné domény
řešení kombinatorických problémů grafy, plánování ... místo “generuj a testuj”: “omez a generuj” obarvení grafu n barvami
pro v_i prom. X_i pro hranu v_i - v_j podm. X_i\=X_j domény: X_i :: {1,2,..n}
Prakticky používané systémy Eclipse ILOG solver - knihovny řešiče a interface pro C