Reprezentace (6)

Jan Hric, KTI MFF UK,1997-2010ahttp://kti.ms.mff.cuni.cz/~hric

Reprezentace - úvod objekty světa okolo, matematiky ... reprezentujete v

programovacím jazyku musíte se syntakticky přizpůsobit

konečný zápis může reprezentovat i nekonečné objekty př.: reprezentace intervalů [1..10],[1...]

Reprezentace (posloupností)

v procedurálních prog. jazycích explicitní – jako datová struktura [1,2,3]

Lze předávat, generovat, používat různými způsoby implicitní - posloupnost hodnot nějaké proměnné (for i:=...)

Akumulátor: length(N, …):-N1 is N+1, length(N1, …).

navíc v Prologu explicitní – fakty v databázi data(1). data(2). data(3).

nevhodné, pokud se data mění a vytvářejí (např. grafy) nevhodný styl programování – procedurální se stavem

implicitní - posloupnost řešení poskytovaná backtrackingem X=1; X=2; X=3; no

výhody, nevýhody převody reprezentací

Reprezentace - příklady délka seznamu reprezentuje číslo

?- X=[_,_,_],kombinace([1,2,3,4],X). lze použít pro backtracking, nevhodné pro seznam řešení

termy jsou dostatečně obecné: a:=b+1:- op( 599, xfx, := ).?- cc(var(a):=var(b)+con(1), CC).

ohodnocené grafy (explicitně v d.s.) graf([V-OV],[h(V1,V2,OH)]) [V1-OV-[V2-OH]] seznam sousedů

hradlové sítě: jména hradel místo směrníků [hr(Jmeno,Op,[Arg])] explicitní jména, musím hledat v d.s. Argumenty: h(14) vs. v(14); h14 vs. v14

Komplexní čísla: reprezentace variant compl(rect, x, y) vs. compl(polar, z, fi) (nebo rect(x,y) a polar(z,fi) ) procedury: 1. převedou na vhodnou r., 2. rozeberou případy,

3.připouští jen argumenty ve správné repr. – uživatel se přizpůsobí volající proc. mají být polymorfní – změny/rozšíření r. se v nich neprojeví

(Reprezentace stavů a výpočtů)

reprezentovat (a teda předávat či vracet) lze stavy: [1..10] ~~> [2..10]

speciálně: stav reprezentuje, co ještě zbývá zpracovat

výpočty: mk_and(P,Q,PandQ):- PandQ = (P,Q). pokud programy pouze analyzujeme: „jednota“ programu a dat

– přímočará reprezentace programů jako termů, někdy problémy s proměnnými

– reifikace klauzulí a cílů jako termů (tj. datových struktur) pokud programy generujeme a voláme: využívá se interpretační

charakter jazyka výpočet se aktivuje vestavěným predikátem call/1, (call/n) ...

(Reprezentace (pokrač.))

reprezentace reprezentace (při zpracovávání zdr. textů) v C: ”Hello world\\n”

lineární reprezentace - vstup a výstup reprezentace musí mít daný význam (sémantiku) -

vztah k objektům reprezentaci lze zvolit, dobrá volba usnadňuje

implementaci různé funktory pro jednotlivé druhy reprezentovaného

objektu (tagy) parametrický průchod reprezentací - interpret, konkrétní

operace jako argumenty (foreach)

Reprezentace, převod

reprezentace termů: f(a1,..,an) ==> [f, a1 , ... , an] podtržení znamená reprezentaci jde o převod n-árního stromu na binární: seznamová ’.’/2

převodní predikát r/2: g(a,b([1]))=[g,[a],[b,[.,1,[]]]]

r(X,[X]):- atomic(X). % nemusí být, platí Atom=..[Atom] r(X,[F|RA]):- compound(X), % test vyloučí volnou proměnnou X X=..[F|A], r_arg(A,RA).r_arg([],[]).r_arg([A|As],[R|Rs]):- r(A,R), r_arg(As,Rs). zvolená reprezentace umožňuje přístup k funktoru v čistém

Prologu (místo functor/3) Derivace složených funkcí - viz

Autotest

opačný převod z reprezentace na term převod z n-árního stromu na binární

typ n-árního: s(vrchol ,[podstromy] )

Grafy Prohledávání do hloubky, přidat start, …-depth_first(G,Answer):-

start(Start), % lépe v parametru (1)depth_star(G,[Start],[Start],Answer), % vlastní start (2) % depth_star(gr,otevrene,dostupné,answer), dostupne=otevr+uzavrsolution(Answer).

depth_star(_G,[X|_], _, X). % každý prohledaný vrchol se vydá, anebo% … :-solution(X). – vede ke kopírování kódu (3)

depth_star(G,[X|Open],Closed, Y):-children(G,X,Children), % deti aktualniho X v G (4)ord_union(Closed,Children,Closed1,Children1),% knih.: ord_union(+Stare, +Nove, -Sjednoceni, -Opravdu_nove) append(Children1, Open, Open2), % změnit pro jiné prohledávání

% např. pro best-first si vrcholy nesou ocenění (5)depth_star(G,Open2,Closed1,Y).

Přístup ke grafu G je pouze pomocí children/3 – polymorfní v G (3): idea: předávat solution/1 jako parametr

Grafy Prohledávání do šířkybreadth_first(G, Answer):-

start(Start), queue(Start, Open), % vytvoření jednoprvkové frontybreadth_star(G,Open,[Start],Answer), % b_s(g,otevrene, dostupne, answer)solution(Answer).

breadth_star(G, Open, Closed, Y) :-queue_head(X, Open1, Open),( Y = X % výstupní substituce; children(G, X, Children), % deti aktualniho X v G ord_union(Closed,Children,Closed1,Children1),

% knihovna: ord_union(Stare_prvky, Nove, Sjednoceni, Skutecne_nove) queue_last_list(Children1, Open1, Open2), breadth_star(G, Open2,Closed1,Y)).

Příklad tail-rekurzivního predikátu, tj. optimalizace posledního volání výhoda: simuluje while cyklus, tj. v konstantní paměti (bez zásobníku) Rek. volání je poslední, používá se akumulátor; často lze převést na tento tvar

Dat. struktura fronta

strukt: q(s(..s(0)..), [X1,..Xn, Y1,..], [Y1..]) %q(delka, front, back)queue(q(0,B,B)). % queue(Queue) prazdna, initqueue(X, q(s(0), [X|B], B)). % queue(X,Queue) jednoprvkovaqueue_head(X, q(N,F,B), q(s(N),[X|F], B)). % X je navic v 3. arg v

hlavequeue_head_list(…):- … % pro symetriiqueue_last(X, q(N,F,[X|B]), q(s(N),F,B)). % X je navic v 3. arg na

konciqueue_last_list([], Queue, Queue).queue_last_list([X|Xs], Queue1, Queue):-

queue_last(X, Queue1, Queue2),queue_last_list(Xs, Queue2, Queue).

Operace v O(1), čítač délky je zahrnut ve struktuře 2. a 3. arg. jako akumulátor; vkládání a odeb. se liší vstupem a výst.

(+,-,+) odebírá, (+,+,-) vkládá – na konec pouze jednou

Vestavěné predikáty (opět)

aritmetika výpočty, porovnávání

vstup/výstup spracování termů a atomů

testy druhu, porovnávání, vytváření a dekompozice

řízení výpočtu práce s množinami řešení práce s databází

Řízení výpočtu

A,B A;B A->B;C true/0 vždy uspěje fail/0 nikdy neuspěje

debug(X):-write([X]),fail ; true. repeat/0 nekonečně krát backtrackuje

repeat. %implementacerepeat:-repeat.Příklad použití; musí skončit úspěšně, řez kvůli backtrackingu

Pokud transformace neuspěje, soubory se neuzavřou.spracuj_soubor(Fi,Fo):- see(Fi), tell(Fo), repeat, read(X), (X=end_of_file,!,seen(Fi),told(Fo)%konec souboru, úspěch ;transformuj(X,Y), write(Y), write(’. ’), fail ).

Řez ! !/0 zvaný ‘řez’

zakáže další možné řešení cílů v klauzuli před sebou i jiné klauzule k aktuálnímu volání

nemá deklarativní význam (sémantiku) “dosud zvolená cesta výpočtu je jediná správná” podobá se goto => nepoužívat, nahrazovat not a ->

navrhovat d.s. umožňující rozskoky podle funktoru (viz. Haskell)

p :- test1, !, telo1.p :- test2, !, telo2.p :- telo3. %záchytná klauzule: not(test1), not(test2)

Třetí klauzule je nedeklarativní Prohozením pořadí klauzulí vznikne chybný program

Příklad: parciální derivaceder(X, X, 1) :- !. % zpracuje pouze X, test je X[1] = X[2]

der(Y, X, 0) :- atom(Y). % zpracuje ostatní (dom.) proměnné, tj. atomy Červený řez: mění význam programu vs. zelený řez: optimalizuje

Negace I

Negace není v čistém Prologu (a teorii SLD rezoluce) nelze odvodit negativní tvrzení ? pro které X platí, že není rodič Adama

implementace: negace neúspěchem “co není zakázáno, je povoleno” co se nepodaří dokázat (v konečném počtu kroků), to neplatí

předpoklad uzavřeného světa (CWA) – co není v db., to neplatí

not(X) X nesmí obsahovat volné proměnné (volné proměnné způsobí běhovou chybu)not(X):- X,!,fail. % term X se převede na cíl a zavolá se not(X). pokud X neobsahuje volné proměnné, not je korektní \+(X) … negace, dovoluje volné proměnné, je nekorektní

trade-off - kompromis not/1 a \+ /1 jsou operátory

Negace II

\+(X) může obsahovat volné proměnné => je nekorektní (a nedeklarativní)

Program: p(a).

?- X=c, \+p(X).

X=c uspěje, OK

?- \+p(X), X=c. záleží na pořadí

no špatně; našlo X=a X je při volání \+ volná proměnná, substituce se neuchová

?- p(X), X=c. pro porovnání

no

Negace

Příklad

notmember(X,[]).

notmember(X,[Y|L]) :- X\=Y, notmember(X,L). Procedura notmember/2 nevzniká odvozením z member/2, ale

je to samostatná procedura Vztah sémantik member/2 a notmember/2 není zaručen

if - then - else

v těle můžeme používat kromě čárky a středníku: If -> Then ; Else

podmínka se vyhodnocuje 1x, uvnitř částí Then a Else se může backtrackovat

nebacktrackuje se mezi Then a podmínkou, mezi Then a Else

if1->(then % ”->“ a “;” jsou binární operátory stejné

;(if2->(then2% priority asociované doprava

;(if3->(then3

;else3 )) )) )

-> omezuje backtracking v klauzuli, ale nemá vliv na ostatní klauzule predikátu Sémantika: „lokální“ řez v klauzuli

sjednoceni(X,Y,V):-sjednotí X a Y do V. a) deklarativní, ale neefektivní (2 testy)sjednoceni([],Y,Y). sjednoceni([X|Xs],Ys,V):- member(X,Ys), sjednoceni(Xs,Ys,V).sjednoceni([X|Xs],Ys,[X|V]):- not(member(X,Ys)), sjednoceni(Xs,Ys,V). b) nedeklarativní 3.klauzule

Bez řezu dostavám první správné řešení, ale další s opakujícími se prvky

sjednoceni([],Y,Y). sjednoceni([X|Xs],Ys,V):- member(X,Ys),!, sjednoceni(Xs,Ys,V).sjednoceni([X|Xs],Ys,[X|V]):- sjednoceni(Xs,Ys,V). c) strukturovaný program, efektivní, explicitní unifikace sjednoceni([],Y,Y). sjednoceni([X|Xs],Ys,V):- (member(X,Ys)-> V=V1; V=[X|V1]), sjednoceni(Xs,Ys,V1).

(Programování vyšších řádů)

map, fold, foreach ....

(HTML a Prolog M. Hermenegildo, systém PiLLoW) Jmeno$Atr ($/2 je infixní operátor)

img$[src=’images/map.gif’,alt=’A map’] <img src=”images/map.gif” alt=”A map”>

jmeno(Text) (term s funktorem jmeno/1) address(’webmaster@mff.cuni.cz’) <address>webmaster@mff.cuni.cz</address>

jmeno(Atr,Text) (term s funktorem jmeno/2) a([href=’http://www.xx.y/’],’XX home’) <a href=”http://www.xx.y/”>XX home</a>

env(Jmeno,Atr,Text) (pomocné, obecné) env(a,[href=’http://www.xx.y/’],’XX home’)

<a href=”http://www.xx.y/”>XX home</a>