Optimalizace posledního volání Seznamy (pokračování) LCO a akumulátor 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 I 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í I, 18. března 2010 3 Seznamy ■ 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, kdy je 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é ■ pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC ...):- ... % žádné rekurzivní voláni v těle klauzule pC-..) :- !, pC ■■■ )■ % řez zajišťuje determinismus ■ Tento typ rekurze lze převést na iteraci Hana Rudová, Logické programování I, 18. března 2010 2 Seznamy max_list s akumulátorem Výpočet největšího prvku v seznamu max_"list(Seznam, Max) max_listC[X], X). max_listC[X|T], Max) :-max_li st CT,MaxT), C MaxT >= X, !, Max = MaxT Max = X ). max_listC[H|T],Max) :- max_listCT,H,Max). max_listC[], Max, Max). max_li st C[H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_listCT, H, Max ) max_listCT, CastecnyMax, Max) ). Hana Rudová, Logické programování I, 18. března 2010 4 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í I, 18. března 2010 5 Seznamy Rozdílové seznamy 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 A1 Z1 A2 Z2 L1 1 L2 \ append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 L3 [2,3|Z1]-Z2 [2,3,1|Z2]-Z2 ?- 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 Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování I, 18. března 2010 7 Neefektivita při spojování seznamů 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í I, 18. března 2010 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] ). rozdílové seznamy Cl i neárni) Příklad: operace pro manipulaci s frontou ■ test na prázdnost, přidání na konec, odebrání ze začátku Hana Rudová, Logické programování I, 18. března 2010 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 ) asserta( Klauzule ) assertz( Klauzule ) retract( Klauzule ) přidání Klauzule do programu přidání na začátek přidání na konec smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 18. března 2010 Vestavěné predikáty Vestavěné predikáty Predikáty pro řízení běhu programu ■ fai 1 , true, ... Různé typy rovností ■ unifikace, aritmetická rovnost, ... Databázové operace ■ změna programu (programové databáze) zajeho 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í I, 18. března 2010 Vestavěné predikáty Příklad: databázové operace Caching: odpovědi na dotazy jsou 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 ) ), fai 1. uloz_trojice( _, _ ) :- !. Hana Rudová, Logické programování I, 18. března 2010 Vestavěné predikáty Vstup a výstup Vstupní a výstupní proudy: vestavěné predikáty uživatelsky terminal vstupni proudy 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 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 program —k soubor 4 vystupni proudy Hana Rudová, Logické programování I, 1 8. března 2010 Vestavěné predikáty 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_file zápis dalšího termu: write(Term) ?- writeC ahoj ). ?- write( '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í I, 18. března 2010 Vestavěné predikáty změna (otevření) aktivního vstupního/výstupního proudu: see(S)/te"l"l (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í I, 18. března 2010 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 Hana Rudová, Logické programování I, 18. března 2010 Vestavěné predikáty Čtení programu ze souboru Interpretování kódu programu ■ ?- consult(program). ■ ?- consult('program.pl'). ■ ?- consult( [programl, 'program2.pl'] ). Kompilace kódu programu ■ ?- compile( [programl, 'program2.pl']). ■ ?- [program]. ■ ?- [user]. zadávání kódu ze vstupu ukončené CTRL+D ■ další varianty podobně jako u interpretování ■ typické zrychlení: 5 až 10 krát Hana Rudová, Logické programování I, 18. března 2010 17 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 vek( petr, 7 ). vek( anna, 5 ). vek( tomas, 5 ) . ?- bagofC Dite, ( vek( Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] bagof, setof, findall: na objekty shromažďované vX nejsou žádná omezení ?- bagofC Dite-Vek, vek( Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programování I, 18. března 2010 19 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, S ): 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í 1,18. března 2010 18 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 ?- bagofC Vek ,[]meno,Prijmeni]"vek( ]meno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování I, 18. března 2010 20 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 findalKX, P, S ): rozdíly od bagof ■ všechny proměnné jsou existenčně kvantifikovány ?- findallf Dite, vek( Dite, Vek ), Seznam ). svS 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 = [] ■ ?- bagof( Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] ?- findaIK Dite, vek( Dite, Vek ), Seznam ). Seznam = [petr,anna,tomas] Hana Rudová, Logické programování I, 18. března 2010 21 Vestavěné predikáty