Vestavěné predikáty a jejich použití

Jan Hric, KTI MFF UK1997-2010c (oprava 4.5.)

http://kti.ms.mff.cuni.cz/~hric/

Vestavěné predikáty

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í spracování + práce s databází

práce s množinami řešení

Aritmetika “speciální” predikáty, které vyhod. výrazy

důsledek neexistence typů operátorová syntax

is/2 vyhodnotí výraz napravo a unifikuje s levou stranou ?- is(X,1+3), X is 2+2.

is je operátor, oba zápisy jsou možné a rovnocenné

>/2, </2, >=/2, =</2, - porov. ar. výr. =:=/2, =\=/2

vyhodnotí obě strany a porovná výsledky

Aritmetické funkce

které se vyhodnocují: (viz help a manuál, impl.) + - * / // mod ^ max min rand/1 ip fp ln log sin cos asin atan ... bitové: /\ \/ << >> \

! Nevyhodnocuje se při předávání parametrů Chybně 1: faktorial(N,...):- faktorial(N-1,...),...

Přesněji: synt. OK, sem. chybně: ((2-1)-1)-1 Chybně 2: faktorial(N,...):- N is N-1, ...

Dtto; proměnnou nelze měnit „na místě“, správně:...N1 is N-1,…

Délka seznamu

aritmetika je jednosměrná (a nedeklarativní)length([],0). % mod (+,?)length([_|L],N):- length(L,N1), N is N1+1.

seznam dané délky (z anonymních prom.)length1(0,[]). % mod (+,?)length1(N,[_|L]):- % impl. N>0,N1 is N-1,length1(N1,L). test N>0: pro deklarativní správnost, brání cyklu rozdíl: (+,+) neúspěch: l. po návratě z rek., l1. v

hloubce

Unární aritmetika

V Prologu: číselné hodn. lze repr. pomocí termů Dat. typ: 0 pro 0, s(N) pro n+1 (tj. následníka)?- plus(s(s(0)),s(s(s(0))), X). % 2+3 je ?X=s(s(s(s(s(0))))) I jiné reprezentace čísel: délkou seznamu

?- komb(3,[a,b,c,d,e],K). vs ?- komb(s(s(s(0))),[a,b,c,d,e],K).vs ?- K=[_,_,_],komb([a,b,c,d,e],K). %|K| = 3DC: prostřední prvek, první (a druhá) polovina s.

Insertsort

% insert(+X,+L,-V):- zatřídí X do uspořádaného L a výsledek je V; L je seznam čísel (protože používáme <...)

insert(X,[],[X]).insert(X,[Y|L],[X,Y|L]):- X=<Y.insert(X,[Y|L],[Y|V]) :- X>Y, insert(X,L,V).% isort(+L,-V) :- utřídí L do Visort([],[]).isort([X|L],V):- isort(L,V1),

insert(X,V1,V). zobecnění: porovnávací procedura jako parametr

Mergesort

% msort(+I::[Int],-O::[Int]) :- utřídí I do Omsort([],[]).msort([X],[X]). %nutné obě koncové podm. msort(I,O):- I=[_,_|_], /*%I má aspoň dva prvky*/ mergesplit(I,I1,I2), msort(I1,O1), msort(I2,O2), merge(O1,O2,O). metoda: rozděl a panuj jinak: mergesplit/3 obsahuje stráž-podmínku

ale pak není univerzální

Slití seznamů: merge/3

Slije uspořádané (číselné) seznamy, vyloučí vícenásobné

% merge(+L1,+L2,-L)merge([],L,L).merge(L,[],L):- L\=[]. % bez opakovaných řešení merge([X1|L1],[X2|L2],[X1|L]):- X1<X2, merge(L1,[X2|L2],L).merge([X1|L1],[X2|L2],[X2|L]):- X1>X2, merge([X1|L1],L2,L).merge([X1|L1],[X2|L2],[X1|L]):- % bez opak. prvků X1=X2, merge(L1,L2,L). % test nutný pro dekl. spr.

Rozdělení: mergesplit/3

/* mergesplit(+L,-L1,-L2):- * rozdělí L na sudé (L1) a liché (L2) */mergesplit([],[],[]).mergesplit([X],[X],[]).mergesplit([X,Y|L],[X|L1],[Y|L2]):- mergesplit(L,L1,L2). viz autotest z minulé přednášky

Stavba Haldy Stavba min-haldy přeuspořádáním ze stromu

Použitelné taky pro heapsortheapify(v,v).heapify(t(L,X,R),H):- heapify(L,HL), heapify(R,HR),

adjust(X,HL,HR,H).adjust(X,HL,HR,t(HL,X,HR)):-

tree_gt(X,HL),tree_gt(X,HR).adjust(X,t(L,X1,R),HR,t(HL,X1,HR)):- X>X1,

tree_gt(X1,HR),adjust(X,L,R,HL).adjust(X,HL,t(L,X1,R),t(HL,X1,HR)):- X>X1,

tree_gt(X1,HL),adjust(X,L,R,HR).tree_gt(X,v).% progr. technika: lifting, „zvednutí“ =<tree_gt(X,t(_L,X1,_R)) :- X=<X1.

Symbolické derivace der(výraz, X, derivovaný_výraz), bez zjednodušováníder(N,X,0) :- number(N). % test číslader(X,X,1). % bez symb. parametrů, jiných proměnných a parciálních derivací der(Y,X,0) :- atom(Y), X\=Y. % derivace podle jiné prom.anebo symb. konstantyder(X^N,X,N*X^N1):- N > 0, N1 is N-1.der(sin(X),X,cos(X)). % pro každou funkci 1 fakt (A)der(cos(X),X,-sin(X)). % anebo: …, (-1)*sin(X) ), když nemáte unární mínus. der(e^X,X,e^X). der(log(X),X,1/X). der(F+G,X,DF+DG):- % pro každý způsob skládání fcí (tj. operátor) 1 pravidlo

der(F,X,DF),der(G,X,DG).der(F-G,X,DF-DG):-der(F,X,DF),der(G,X,DG).der(F*G,X, F*DG+DF*G):-der(F,X,DF),der(G,X,DG).der(1/F,X,-DF/(F*F)):-der(F,X,DF). % spec. případ další klauzuleder(F/G,X,(G*DF-F*DG)/(G*G)):-der(F,X,DF),der(G,X,DG). Bez zjednodušování: ?- der(3*x+2,x,D). –> D=(3*1+0*x)+0

Druhá derivace : nepřehledná Proměnné: doménové vs. Prologovské Zde bez složených funkcí, lze implementovat rozepsáním podle vnější fce :

der(sin(U),X,cos(U)*DU):-der(U,X,DU). % nahradí fakt (A) Anebo změnou reprezentace termů: př.: t(sin,[t(^(2),[x])]) der(t(F,[G]),X,t(DF,[G])*DG):- der(G,X,DG), derF(F,DF). derF(sin,cos). derF(exp,exp). % atd., nedokonalé: log potřebuje jiné (samostatné) pravidlo

N-arní stromy struktura: t(sezn. podstromů f(klic,hodn,podstrom)) % hranově ohodnocené stromy

Místo seznamů i jiné struktury: BVS ! Vzájemně rekurzivní dat. strukturu ( t/1 a seznamy) zpracujeme vzájemně rek. Predikáty Varianta: vrcholově ohodncené stromy: t(HodnotaVrch, [podstromy] )

t([f(k1,h1,v),f(k2,h2,t([f(k21,h21,v),f(k22,h22,v)])),f(k3,h3,v)]) Vyhledání složeného klíče s proměnou délkou (podle cesty), tj. vyhledávaní řetězcůfind([K],t(Ts),H):- member(f(K,H,_),Ts).find([K|Ks],t(Ts),H):- member(f(K,_,Ps),Ts), % jednoprvkový seznam …

find(Ks,Ps,H). % … uspěje, ale pak v rekurzi neuspěje prázdný?- find([k2,k21], T, H).H =h21;no Datová struktura TRIE: vyhl. podle řetězců Použitelné pro implemenataci vnořených záznamů s pojmenovanými položkami

Seznamy atribut-hodnota, zde jsou hodnoty strukturovány Vlastně dopředný vyhledávací strom v alg. Aho-Corasicková

Ale nelze jednoduše odkázat a dostat se na daný podstrom Aplikace: reprezentace XML, HTML … a jejich zpracování

Logické formule struktura: true/0, false/0,

p/1…proměnné, explicitní funkční symbol Nevhodné je negativní vymezení: atomy různé od true a false jsou proměnné

and/2, or/2, non/1, imp/2, ekv/2, (xor/2, nand/2…) je_lf(LF) .. LF je správně utvořená log. formule je_lf(true). je_lf(false). je_lf(p(_)). % elementární f.je_lf(and(A,B)):- je_lf(A), je_lf(B). % kontroluje funkční s. a #arg.je_lf(or(A,B)):- je_lf(A), je_lf(B).je_lf(non(A)):- je_lf(A).je_lf(imp(A,B)):- je_lf(A), je_lf(B).je_lf(ekv(A,B)):- je_lf(A), je_lf(B). % a další spojky…%nelze: je_lf(F(A,B)):- (F=and ; F=or ; F=imp ; F=ekv),… Pro „dávkové“ ověření korektnosti vstupu z neověřeného zdroje do

nekontrolujícího programu (prog. bez kontrol jsou přehlednější / kratší / lepší) Dvě vrstvy interface: vnitřní nekontrolujíci, vnější kontrolující

Zjednodušování LF

zjedn(F,V) … zjednoduší f. odstraněním konstantzjedn(true,true). zjedn(false,false). zjedn(p(X),p(X)).zjedn(and(F,G),V):- zjedn(F,VF), zjedn(G,VG),

zjedn_and(VF,VG,V). % další log. spojky analogickyzjedn(non(F),V):- zjedn(F,VF), zjedn_non(VF,V).zjedn_and(true,F,F). zjedn(F,true,F).zjedn_and(false,F,false). zjedn_and(F,false,false).zjedn_and(F,G,and(F,G)):-

F\=true, F\=false, G\=true, G\=false.zjedn_non(true,false). zjedn_non(false,true). zjedn_non(F,non(F)) :- F\=true, F\=false. Podobně zjednodušování aritmetických výrazů, např. pro derivace

Vyhodnocení LF 1/2

eval(LF,Ps,V) .. Vyhodnotí LF s prom. Ps do Veval(true,_Ps,true). eval(false,_Ps,false).eval(p(X),Ps,V):-lookup(X,Ps,V). % vyhledání proměnnéeval(and(F,G),Ps,V):-eval(F,Ps,VF), eval(G,Ps,VG), eval_and(VF,VG,V). % analogicky or, noneval(imp(F,G),Ps,V) :- eval(or(non(F),G),Ps,V). %převedení%eval(ekv(F,G),Ps,V) :- % nevhodné, exp. složitost % eval(or(and(F,G),and(non(F),non(G))),Ps,V).eval(ekv(F,G),Ps,V) :- eval(F,Ps,VF), eval(G,Ps,VG),

eval(or(and(VF,VG),and(non(VF),non(VG))),Ps,V).

Vyhodnocení LF 2/2

Vlastní sprac. spojekeval_and(false,_VG,false).eval_and(VF,false,false):-VF\=false. %bez opak. řeš. eval_and(VF,VG,true):-VF\=false,VG\=false. DC: rozšířit LF o sprac. konstanty unk/0 ve významu

hodnota není známá, výsledek může být unk opatrně: eval_ekv(X,X,true). % zdá se OK, ale platí

pouze pro X=true a X=false -> přidat podmínky ?- eval_ekv(unk,unk, true). ?? %rozšíření programu není OK

Typy: btree a log. fle

neformálně: typy pomocí BNF (Backus-Naurova forma) bude (více) formálně: typy v Haskellu

<Btree> ::= v | t( <Btree> , <Hodn> , <Btree>) dtto bin. strom, s “typem” parametrů<Btree(a)> ::= v | t( <Btree(a)> , <a> , <Btree(a)>) Typ l.f.<lf> ::= true | false | p( <Atom> )

| and( <lf>, <lf> ) | or( <lf>, <lf> ) | non( <lf>) | imp( <lf>, <lf> ) | ekv( <lf>, <lf> )

ad p/1: doménová jména proměnných jsou vnořeny v p/1 mají „samostatný namespace“: p(x), p(1), p(true), p(and)

Autotest

převést stručné seznamy čísel na úplné: rozvin/2 ../2 je aritm. posl., krok je daný rozdílem prvních dvou

členů když nejsou, tak default kroku je 1 .. považujme za operátor

jinak je nutné psát: [..(1,10),9,..(8,1)] [1..6] ==> [1,2,3,4,5,6] [1,3..6] ==> [1,3,5] [5,4.. -1] ==> [5,4,3,2,1,0,-1]

jiná konvence: neuvedený krok je +1 nebo -1 podle pořadí mezí: [5.. -1]

Práce s programem

consult(Soubor)anebo v menu

compile(Soubor) listing(Co)

Co je Predikat, Predikat/Arita, seznam předcházejících

?- listing([append/3, member]).?- listing.

seznam všech nakonzultovaných predikátů

I/O Termový

write(X) výpis termu display(X) výpis bez operátorů, vše v prefixním tvaru writeq(X) výpis v zpětně čitatelném tvaru, speciálně apostrofy print(X)

používá portray/1 pro uživatelský výpis (idea: late binding – TVM)Bin. strom: <<v|2|v>|3|v>, nebo <<2>|3|<<4>|5|v>>

zkracuje (dlouhé) výpisy: vypíše „horní“ část termu, pak „…“ read(X) čtení jednoho termu s tečkou (a bílým znakem)

term(s(teckou),[na,konci]). pokud může následovat operátor, musím mít konvenci, jak term ukončit ! Syntaktická analýza zdarma (pokud reprezentujete vstup termem) Používá se při čtení klauzulí programu: za tečkou nesmí být EOF

znakový nl, get(X),get0(X), put(X) X je Ascii kód jednoho přečteného/vypsaného znaku (tj. číslo)

ovládání proudů (vstupního a výstupního) formátovaný I/O, spolupráce s OS - viz manuálBacktracking nevrací přečtené/vypsané data

Ovládání proudů

vstupní a výstupní proud (stream) aktuálními proudy jsou použity write, nl, read

vstupní proud see(+Soubor) přesměruje vstup na Soubor

jméno je atom, často v apostrofech’c:/home/m.pl’ seeing(?S) vrátí jméno akt. vstup. proudu seen/0 přesměruje na stand. vstup, zvaný user klávesnice

výstupní proud - analogicky tell/1, telling/1, told/0 ?-tell(’m.pl’),write(hello),told.

výpis (generovaného) programu „zdarma“ user je obrazovka

Řetězce a ascii kódy

řetězce jsou seznamy ascii kódů znaků následující zápisy jsou totožné: ”abc” [97,98,99] % výpis [0’a,0’b,0’c]

Ř. využijeme, pokud potřebujeme přístup na znaky, často stačí (a jsou správnou d.s.) atomy

Použitelné pro vstup, čitatelný výst. nutno naprogramovat ascii kódy znaků:

0’a = 97 ! zápis ’a’ je atom a

Autotest

třídění výběrem: vybere se minimum jako hlava výsledku a

dále rekurze quicksort

průnik, sjednocení: pro uspořádané seznamy (čísel)

napište predikát, který interní formu řetězců vypíše jako posloupnost znaků v uvozovkách (včetně okrajových uvozovek) [97,99,98] ~> “acb”

Převod do DNF

dnf(F,V).. V je ekv. formule k F v DNF

Zavěsné mobily (rybičky) Vyváženost, bezpečnost mobilu: vracíme seznam “chybných” mobilů

(pod)mobily nejsou pojmenované, vracíme celou strukturu mobilu jiné možnosti: (jednoznačné) jméno ve struktuře, polohu chyby vůči kořeni

D.s.: m(DelkaL-MobilL, DelkaR-MobilR) nebo z(Hmotnost)jeVyv(z(H), H, V, V). %mod(+,-,+,-)jeVyv(m(DL-ML,DR-MR),H,V1,V0):- % do V0 se vloží výstupní hodn., podle větve jeVyv(ML,HL,V1,V2), jeVyv(MR,HR,V2,V3), % „stav“ V - 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. % sémantiku dodá doménový expert

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 (jeBezpKoren(DL,D1, DR,D2) -> V0=V3

; V0 = [m(DL-ML,DR-MR)|V3] ). jeBezpKoren(DL,D1, DR,D2) :- DL+DR > D1+D2. Programátorský idiom: tok dat předáváním stavu, tj. akumulátor

Při předávání do/z/mezi voláním procedur se stav může změnit – zde: V3 na V0 Programy jsou strukturou podobné, liší se výkonnou částí : chtěli bychom abstrakci

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í 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 )) )) )

Slití seznamů: merge/3

Slije uspořádané (číselné) seznamy, vyloučí vícenásobné

% merge(+L1,+L2,-L)merge([],L,L).merge(L,[],L).merge([X1|L1],[X2|L2],[X|L]):- X1<X2 -> X=X1,merge(L1,[X2|L2],L) ; X1>X2 -> X=X2,merge([X1|L1],L2,L) ; /*X1=X2*/ X=X1,merge(L1,L2,L). varianta: každá větev samostatněmerge([X1|L1],[X2|L2],[X1|L]):- % X1 ve výst. X1<X2, merge(L1,[X2|L2],L).