Reprezentace seznamu Seznamy 1 Seznam: [a, b, c], prázdný seznam [] 1 Hlava (libovolný objekt), tělo (seznam): .(Hlava, Telo) ■ všechny strukturované objekty stromy - i seznamy ■ funktordva argumenty ■ .(a, .(b, .(c, []))) = [a, b, c] ■ notace: [ Hlava | Telo ] = [a | Tel o] Telo je v [a | Tel o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] 1 Lze psát i: [a, b | Tel o] ■ před " |" je libovolný počet prvků seznamu , za " | "je seznam zbývajících prvků ■ [a.b.c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] ■ pozor: [ [a,b] | [c]]r[a,b| [c] ] 1 Seznam jako neúplná datová struktura: [a,b,c|T] ■ Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování 1,11. března 2007 2 Prvek seznamu ■ member( X, S ) ■ platí: member( b, [a,b,c] ). ■ neplatí: member( b, [[a,b]|[c]] ). ■ Xje prvek seznamu S, když ■ Xje hlava seznamu S nebo member( X, [ X | _ ] ). %(1) ■ Xje prvek těla seznamu S member( X, [ _ | Telo ] ) :- member( X, Telo ). %(2) ■ Další příklady použití: ■ memberCX,[1,2,3]) . ■ memberCl,[2,1,3,1]). Hana Rudová, Logické programování 1,11. března 2007 3 dle (1). □ yes dle(1). □ yes member(1,[2,1,3,1,4]) dle (2) member(1,[1,3,1,4]) dle (2) member(1,[3,1,4]) dle (2) member(1 ,[1,4]) dle (2) member(1 ,[4]) | dle (2) member(1,[]) dle (2) no Seznamy (pokračování) Optimalizace posledního volání LCO a akumulátor ■ Last Call Optimization (LCO) ■ Implementační technika snižující nároky na paměť ■ Mnoho vnořených rekurzivních volání je náročné na paměť ■ Použití LCO umožňuje vnořenou rekurzi s konstantními pamětovými nároky ■ Typický příklad, kdyje možné použití LCO: ■ procedura musí mít pouze jedno rekurzivní volání: v posledním cíli poslední klauzule ■ cíle předcházející tomuto rekurzivnímu volání musí být deterministické ■ p( ...):- ... % žádné rekurzivní volám' v těle klauzule p( ...):- ... % žádné rekurzivní voláni v těle klauzule p(...) :- !, p( ... ). % řez zajišťuje determinismus ■ Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování 1,11. března 2007 5 Seznamy max_list s akumulátorem Výpočet největšího prvku v seznamu max_"list(Seznam, Max) max_list([X], X). max_list([X|T], Max) :-max_li s t(T,MaxT), C MaxT >= X, !, Max = MaxT Max = X ). max_list([H|T],Max) :- max_list(T,H,Max). max_list([], Max, Max). max_list C[H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_list(T, H, Max ) max_list(T, CastecnyMax, Max) ). Hana Rudová, Logické programování 1,11. března 2007 7 Seznamy ■ Reformulace rekurzivní procedury, aby umožnila LCO ■ Výpočet délky seznamu length( Seznam, Délka ) lengthC [] , 0 ) . lengthC [ H | T ], Délka ) :- lengthC T, DelkaO ), Délka is 1 + DelkaO. ■ Upravená procedura, tak aby umožnila LCO: % lengthC Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' lengthC Seznam, Délka ) :- lengthC Seznam, 0, Délka ). % pomocný predikát lengthC □ , Délka, Délka ). % celková délka = započítaná délka lengthC [ H | T ], A, Délka ) :- A0 is A + 1, lengthC T, A0, Délka ). ■ Přídavný argument se nazývá akumulátor Hana Rudová, Logické programování 1,11. března 2007 6 Seznamy Akumulátor jako seznam ■ Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) ■ reverseC [], [] ) . reverseC [ H | T ], Opacny ) :-reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). ■ naivní reverse s kvadratickou složitosti ■ reverse pomocí akumulátoru s lineární složitostí *% reverseC Seznam, Akumulátor, Opacny ): % Opacny obdržíme přidáním prvků ze Seznam do Akumulátor v opačném poradi reversef Seznam, OpacnySeznam ) :- reversef Seznam, [], OpacnySeznam). reversef [], S, S ). reversef [ H | T ], A, Opacny ) :- reversef T, [ H | A ], Opacny ). % přidání H do akumulátoru ■ zpětná konstrukce seznamu (srovnej s předchozí dopřednou konstrukcí, např. append) Hana Rudová, Logické programování 1,11. března 2007 8 Seznamy Neefektivita při spojování seznamů Rozdílové seznamy Sjednocení dvou seznamů append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( SI, S2, S3 ). ?- append( [2,3], [1], S ). postupné volání cílů: append( [2,3], [1], S ) - append( [3], [1], S') - append( [], [1], S" ) Vždyje nutné projít celý první seznam Hana Rudová, Logické programování 1,11. března 2007 Akumulátor vs. rozdílové seznamy: reverse reverseC [] , [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). kvadratická složitost reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC [] , S, S ) . reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H | A ], Opacny ). akumulátor Oineárni) reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC □ , S-S ) . reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). Příklad: operace pro manipulaci s frontou ■ test na prázdnost, přidání na konec, odebrání ze začátku rozdílové seznamy Cl i neárni) Hana Rudová, Logické programování I, 1 1. března 2007 Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L Z1 A2 Z2 A1 L1 1 L2 \ -3- append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 L3 ■ ?- append( [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 = [2,3|Zl] - Z2 = [2,3| [1|Z2] ] - Z2 Zl = [1|Z2] S = [2,3,1|Z2]-Z2 1 Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování 1,11. března 2007 1 0 Vestavěné predikáty Vestavěné predikáty Predikáty pro řízení běhu programu ■ fail, true,... Různé typy rovností ■ unifikace, aritmetická rovnost, ... Databázové operace ■ změna programu (programové databáze) za jeho běhu Vstup a výstup Všechna řešení programu Testování typu termu ■ proměnná?, konstanta?, struktura?, ... Konstrukce a dekompozice termu ■ argumenty?, funktor?, ... Hana Rudová, Logické programování 1,11. března 2007 Vestavěné predikáty Příklad: databázové operace Caching: odpovědi na dotazyjsou přidány do programové databáze ■ ?- solve( problem, Solution), asserta( solve( problem, Solution) ). ■ :- dynamic solve/2. % nezbytné při použití v SICStus Prologu Příklad: uloz_trojice( Seznámí, Seznam2 ) :-member( XI, Seznámí ), member( X2, Seznam2 ), spocitej_treti( XI, X2, X3 ), assertz( trojice( XI, X2, X3 ) ), f a i 1. uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování 1,11. března 2007 Vestavěné predikáty Databázové operace Databáze: specifikace množiny relací Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly) Vestavěné predikáty pro změnu databáze během provádění programu: assert( Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování 1,11. března 2007 Vestavěné predikáty Vstup a výstup uživatelsky terminal program může číst data ze vstupního proudu (input stream) program může zapisovat data do výstupního proudu (output stream) dva aktivní proudy ■ aktivní vstupní proud ■ aktivní výstupní proud uživatelský terminál - user ■ datový vstup z terminálu user I chápán jako jeden ze vstupních proudů ■ datový výstup na terminál chápán jako jeden z výstupních proudů soubor 1 soubor 2 user —ta program —ta — vstupni proudy vystupni proudy Hana Rudová, Logické programováni 1,11. března 2007 Vestavěné predikáty Vstupní a výstupní proudy: vestavěné predikáty ■ změna (otevření) aktivního vstupního/výstupního proudu: see(S)/tell (S) ctěni( Soubor ) :- see( Soubor ), cteni_ze_souboru( Informace ), see( user ). ■ uzavření aktivního vstupního/výstupního proudu: seen/told ■ zjištění aktivního vstupního/výstupního proudu: seeing(S)/te"l"ling(S) ctěni( Soubor ) :- seeing( StarySoubor ), see( Soubor ), cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování 1,11. března 2007 Vestavěné predikáty Příklad čtení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, % zjištěni aktivniho proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? seen, see( StarySoubor ). % uzavřeni souboru % aktivace původniho proudu repeat. repeat repeat. % opakováni Sekvenční přístup k textovým souborům čtení dalšího termu: read(Term) ■ při čtení jsou termy odděleny tečkou | ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj C petre ). [ ahojC 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme ■ po dosažení konce souboru je vrácen atom end_of_f i le zápis dalšího termu: write(Term) ?- writeC ahoj ). ?- writeC 'Ahoj Petre!' ). nový řádek na výstup: nl N mezer na výstup: tab(N) čtení/zápis dalšího znaku: getO(Znak) , get(NeprazdnyZnak)/put(Znak) ■ po dosažení konce souboru je vrácena -1 Hana Rudová, Logické programování 1,11. března 2007 Vestavěné predikáty Čtení programu ze souboru Interpretování kódu programu ■ ?- consult(program). consultCprogram.pl') . consult( [programl, 'program2.pl'] ). [program]. [user]. zadávání kódu ze vstupu ukončené CTRL+D Kompilace kódu programu ■ ?- compile( [programl, 'program2.pl']). ■ další varianty podobně jako u interpretování ■ typické zrychlení: 5 až 10 krát Hana Rudová, Logické programování I, 11. března 2007 19 Vestavěné predikáty Hana Rudová, Logické programování I, 11. března 2007 20 Vestavěné predikáty Všechna řešení ■ Backtracking vrací pouze jedno řešení po druhém ■ Všechna řešení dostupná najednou: bagof/3 , setof/3, findall/3 ■ bagof( X, P, 5 ): vrátí seznam S, všech objektů X takových, že P je splněno vek( petr, 7 ). vek( anna, 5 ). vek( tomas, 5 ) . ?- bagofC Dite, vek( Dite, 5 ), Seznam ). Seznam = [ anna, tomas ] ■ Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagofC Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování I, I I. března 2007 21 Vestavěné predikáty Existenční kvantifikátor „" " ■ Přidání existenčního kvantifikátoru ,," " => hodnota proměnné nemá význam ?- bagofC Dite, Vek"vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] ■ Anonymní proměnné jsou všeobecně kvantifikovány, i když jejich hodnota není (jako vždy) vracena na výstup ?- bagofC Dite, vek( Dite, _Vek ), Seznam ). Seznam = [petr] ; Seznam = [anna,tomas] ■ Před operátorem „" " může být i seznam ?- bagof( Vek ,[Jméno,Prijmeni]"vekC Jméno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programováni 1,11. března 2007 23 Vestavěné predikáty Všechna řešení II. ■ Pokud neexistuje řešení bagof(X, P, S) neuspěje ■ bagof: pokud nějaké řešení existuje několikrát, pak S obsahuje duplicity ■ bagof, setof, findall: P je libovolný cíl vekC petr, 7 ). vekC anna, 5 ). vekC tomas, 5 ). ?- bagofC Dite, C vekC Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] ■ bagof, setof, findall: na objekty shromažďované vX nejsou žádná omezení ?- bagofC Dite-Vek, vekC Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programování 1,11. března 2007 22 Vestavěné predikáty Všechna řešení III. ■ setof ( X, P, S ): rozdíly od bagof ■ S je uspořádaný podle @< ■ případné duplicity v S jsou eliminovány ■ findalK X, P, S ): rozdíly od bagof ■ všechny proměnné jsou existenčně kvantifikovány ?- findalK Dite, vek( Dite, Vek ), Seznam ). ^vS jsou shromažďovány všechny možnosti i pro různá řešení => findall uspěje přesně jednou ■ výsledný seznam může být prázdný => pokud neexistuje řešení, uspěje a vrátí S = [] ■ ?- bagofC Dite, vekC Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findallC Dite, vek C Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování 1,11. března 2007 24 Vestavěné predikáty