Cvičení: append/2 Seznamy (pokračování) Optimalizace posledního volání 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í I, 14. března 2011 3 Seznamy appendC [], S, S ). % CD appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). % (2) :- append([l,2],[3,4],A). I (2) I A=[1|B] I :- append([2],[3,4],B) . I (2) I B=[2|C] => A=[1,2|C] I :- append([],[3,4],C). I CD | C=[3,4] => A=[l,2,3,4], I yes Hana Rudová, Logické programování I, 14. března 201 1 2 Seznamy 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 | 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, 14. března 201 1 4 Seznamy max_list s akumulátorem Výpočet největšího prvku v seznamu max_1ist(Seznam, Max) max_listC[X], X). max_listC[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_listC[], Max, Max). max_list([H|T], CastecnyMax, Max) :-C H > CastecnyMax, !, max_list(T, H, Max ) max_1ist(T, CastecnyMax, Max) ). Hana Rudová, Logické programování I, 14. března 2011 5 Seznamy 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, 14. března 2011 Akumulátor jako seznam 1 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 i 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, 14. března 201 1 6 Seznamy Rozdílové seznamy 1 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] 1 Reprezentace prázdného seznamu: L-L A1 Z1 A2 Z2 L1 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 1 Jednotková složitost, oblíbená technika ale není tak flexibilní Hana Rudová, Logické programování I, 14. března 201 1 8 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í 1,14. března 2011 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í I, 14. března 2011 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í I, 14. března 201 1 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í I, 14. března 2011 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í I, 14. března 2011 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, 14. března 201 1 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í I, 14. března 201 1 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, i ■ i seen, see( StarySoubor ). repeat. repeat % zjištěni aktivního proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % opakováni Čtení programu ze souboru Interpretování kódu programu ■ ?- consult(program). ■ ?- consu1tCprogram.pl') . ■ ?- consultC [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 repeat. Hana Rudová, Logické programování I, 14. března 201 I 17 Vestavěné predikáty Hana Rudová, Logické programování I, 14. března 201 I 18 Vestavěné predikáty