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í 1,11. března 2013 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í 1,11. března 2013 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í 1,11. března 2013 4 Seznamy Akumulátor jako seznam Nalezení seznamu, ve kterém jsou prvky v opačném pořadí reverse( Seznam, OpacnySeznam ) ■ reverseC [], [] ) . reverse( [ 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 reverse( Seznam, OpacnySeznam ) :- reverse( Seznam, [], OpacnySeznam). reverse( [], S, S ). reverse( [ 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, 11. března 2013 5 Seznamy Neefektivita při spojování seznamů Sjednocení dvou seznamů appendC [], S, S ). appendC [X|S1], 52, [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 2013 Seznamy reverse/2: cvičení reverseC Seznam, OpacnySeznam ) :- % Cl) reverseC Seznam, [], OpacnySeznam). reverseC [], S, S ). % (V) reverseC [ H | T ], A, Opacny ) :- % C3) reverseC T, [ H | A ], Opacny ). ? - reverse([l,2,3],0). reverseC[l,2,3] ,0) - CD reverse([l,2,3], [], 0) - C3) reverseC[2,3], [1], 0) - (3) reverseC[3], [2,1], 0) - C3) reverseCH , [3,2,1] , 0) - (2) yes 0=[3,2,1] Hana Rudová, Logické programování 1,11. března 201 3 Sezri,imy 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 \ 1 12 \ appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 [2,3] [1] [2,3,1] [2,3|Z1]-Z1 [1|Z2]-Z2 [2,3,1|Z2]-Z2 L3 ?- appendC [2,3|Z1]-Z1, [1|Z2]-Z2, S ). S = AI - Z2 = [2,3|Z1] - Z2 = [2,31 [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í 1,11. března 201 3 Sezri,imy 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, 1 1. března 2013 9 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 2013 11 Vestavěné predikáty 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 201 3 Vestavěné predikáty Príklad: databázové operace Vstup a výstup 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 2013 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)/telling(S) ctěni( Soubor ) :- seeing( StarySoubor ), see( Soubor ), cteni_ze_souboru( Informace ), seen, see( StarySoubor ). Hana Rudová, Logické programování 1,11. března 2013 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 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 —k program —k vystupni proudy Hana Rudová, Logické programování I, 11. března 201 3 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_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 201 3 Vestavěné predikáty Příklad čtení ze souboru process_file( Soubor ) :- seeingC 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, I I. března 2013 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 ). ?- bagof( Ditě, vek( Dite, 5 ), Seznam ). Seznam = [ anna, tomas ] Volné proměnné v cíli P jsou všeobecně kvantifikovány ?- bagof( Dite, vek( Dite, Vek ), Seznam ). Vek = 7, Seznam = [ petr ]; Vek = 5, Seznam = [ anna, tomas ] Hana Rudová, Logické programování 1,11. března 2013 Vestavěné predikáty Čtení programu ze souboru Interpretování kódu programu ■ ?- consult(program). •7- consu1tCprogram.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í 1,11. března 201 3 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 ). ?- bagof( Dite, ( vek( Dite, 5 ), Dite \= anna ), Seznam ). Seznam = [ tomas ] bagof, setof, findall: na objekty shromažďované vX nejsou žádná omezení: Xje term ?- bagof( Dite-Vek, vek( Dite, Vek ), Seznam ). Seznam = [petr-7,anna-5,tomas-5] Hana Rudová, Logické programováni 1,11. března 201 3 Vestavěné predikáty Existenční kvantifikátor „ Všechna řešení III. ■ Přidání existenčního kvantifikátoru „" " => hodnota proměnné nemá význam ?- bagof( 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,Přijmeni]"vek( Jméno, Prijmeni, Vek ), Seznam ). Seznam = [7,5,5] Hana Rudová, Logické programování 1,11. března 2013 21 Vestavěné predikáty ■ 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 ). => v S 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 ] ?- findalK Dite, vek( Dite, Vek ), Seznam ). Seznam = [petr.anna.tomas] Hana Rudová, Logické programování 1,11. března 201 3 22 Vestavěné predikáty